jars/icu4j-4_2_1-src/src/com/ibm/icu/dev/test/util/CollectionUtilities.java

   1 //##header J2SE15
   2 /*
   3  *******************************************************************************
   4  * Copyright (C) 1996-2009, International Business Machines Corporation and    *
   5  * others. All Rights Reserved.                                                *
   6  *******************************************************************************
   7  */
   8 package com.ibm.icu.dev.test.util;
   9
  10 import java.util.Collection;
  11 import java.util.Comparator;
  12 import java.util.HashMap;
  13 import java.util.Iterator;
  14 import java.util.Map;
  15 import java.util.SortedSet;
  16
  17 //#if defined(FOUNDATION10) || defined(J2SE13)
  18 //#else
  19 import java.util.regex.Matcher;
  20 //#endif
  21
  22 import com.ibm.icu.text.Transliterator;
  23 import com.ibm.icu.text.UTF16;
  24 import com.ibm.icu.text.UnicodeSet;
  25 import com.ibm.icu.text.UnicodeSetIterator;
  26
  27 /**
  28  * Utilities that ought to be on collections, but aren't
  29  */
  30 public final class CollectionUtilities {
  31
  32     public static String join(Object[] array, String separator) {
  33         StringBuffer result = new StringBuffer();
  34         for (int i = 0; i < array.length; ++i) {
  35             if (i != 0) result.append(separator);
  36             result.append(array[i]);
  37         }
  38         return result.toString();
  39     }
  40
  41     public static String join(Collection collection, String separator) {
  42         StringBuffer result = new StringBuffer();
  43         boolean first = true;
  44         for (Iterator it = collection.iterator(); it.hasNext();) {
  45             if (first) first = false;
  46             else result.append(separator);
  47             result.append(it.next());
  48         }
  49         return result.toString();
  50     }
  51
  52     /**
  53      * Utility like Arrays.asList()
  54      */
  55     public static Map asMap(Object[][] source, Map target, boolean reverse) {
  56         int from = 0, to = 1;
  57         if (reverse) {
  58             from = 1; to = 0;
  59         }
  60         for (int i = 0; i < source.length; ++i) {
  61             target.put(source[i][from], source[i][to]);
  62         }
  63         return target;
  64     }
  65
  66     public static Collection addAll(Iterator source, Collection target) {
  67         while (source.hasNext()) {
  68             target.add(source.next());
  69         }
  70         return target; // for chaining
  71     }
  72
  73     public static int size(Iterator source) {
  74         int result = 0;
  75         while (source.hasNext()) {
  76             source.next();
  77             ++result;
  78         }
  79         return result;
  80     }
  81
  82
  83     public static Map asMap(Object[][] source) {
  84         return asMap(source, new HashMap(), false);
  85     }
  86
  87     /**
  88      * Utility that ought to be on Map
  89      */
  90     public static Map removeAll(Map m, Collection itemsToRemove) {
  91         for (Iterator it = itemsToRemove.iterator(); it.hasNext();) {
  92             Object item = it.next();
  93             m.remove(item);
  94         }
  95         return m;
  96     }
  97
  98     public Object getFirst(Collection c) {
  99         Iterator it = c.iterator();
 100         if (!it.hasNext()) return null;
 101         return it.next();
 102     }
 103
 104     public static Object getBest(Collection c, Comparator comp, int direction) {
 105         Iterator it = c.iterator();
 106         if (!it.hasNext()) return null;
 107         Object bestSoFar = it.next();
 108         if (direction < 0) {
 109             while (it.hasNext()) {
 110                 Object item = it.next();
 111                 int compValue = comp.compare(item, bestSoFar);
 112                 if (compValue < 0) {
 113                     bestSoFar = item;
 114                 }
 115             }
 116         } else {
 117             while (it.hasNext()) {
 118                 Object item = it.next();
 119                 int compValue = comp.compare(item, bestSoFar);
 120                 if (compValue > 0) {
 121                     bestSoFar = item;
 122                 }
 123             }
 124         }
 125         return bestSoFar;
 126     }
 127
 128     public interface ObjectMatcher {
 129         /**
 130          * Must handle null, never throw exception
 131          */
 132         boolean matches(Object o);
 133     }
 134
 135     public static class InverseMatcher implements ObjectMatcher {
 136         ObjectMatcher other;
 137         public ObjectMatcher set(ObjectMatcher toInverse) {
 138             other = toInverse;
 139             return this;
 140         }
 141         public boolean matches(Object value) {
 142             return !other.matches(value);
 143         }
 144     }
 145
 146     public static Collection removeAll(Collection c, ObjectMatcher f) {
 147         for (Iterator it = c.iterator(); it.hasNext();) {
 148             Object item = it.next();
 149             if (f.matches(item)) it.remove();
 150         }
 151         return c;
 152     }
 153
 154     public static Collection retainAll(Collection c, ObjectMatcher f) {
 155         for (Iterator it = c.iterator(); it.hasNext();) {
 156             Object item = it.next();
 157             if (!f.matches(item)) it.remove();
 158         }
 159         return c;
 160     }
 161
 162     public static boolean containsSome(Collection a, Collection b) {
 163         // fast paths
 164         if (a.size() == 0 || b.size() == 0) return false;
 165         if (a == b) return true; // must test after size test.
 166
 167         if (a instanceof SortedSet && b instanceof SortedSet) {
 168             SortedSet aa = (SortedSet) a;
 169             SortedSet bb = (SortedSet) b;
 170             aa.containsAll(null);
 171             Comparator bbc = bb.comparator();
 172             Comparator aac = aa.comparator();
 173             if (bbc == null) {
 174                 if (aac == null) {
 175                     Iterator ai = aa.iterator();
 176                     Iterator bi = bb.iterator();
 177                     Comparable ao = (Comparable) ai.next(); // these are ok, since the sizes are != 0
 178                     Comparable bo = (Comparable) bi.next();
 179                     while (true) {
 180                         int rel = ao.compareTo(bo);
 181                         if (rel < 0) {
 182                             if (!ai.hasNext()) return false;
 183                             ao = (Comparable) ai.next();
 184                         } else if (rel > 0) {
 185                             if (!bi.hasNext()) return false;
 186                             bo = (Comparable) bi.next();
 187                         } else {
 188                                 return true;
 189                         }
 190                     }
 191                 }
 192             } else if (bbc.equals(a)) {
 193                 Iterator ai = aa.iterator();
 194                 Iterator bi = bb.iterator();
 195                 Object ao = ai.next(); // these are ok, since the sizes are != 0
 196                 Object bo = bi.next();
 197                 while (true) {
 198                     int rel = aac.compare(ao, bo);
 199                     if (rel < 0) {
 200                         if (!ai.hasNext()) return false;
 201                         ao = ai.next();
 202                     } else if (rel > 0)  {
 203                         if (!bi.hasNext()) return false;
 204                         bo = bi.next();
 205                     } else {
 206                         return true;
 207                     }
 208                 }
 209             }
 210         }
 211         for (Iterator it = a.iterator(); it.hasNext();) {
 212             if (b.contains(it.next())) return true;
 213         }
 214         return false;
 215     }
 216
 217     public static boolean containsAll(Collection a, Collection b) {
 218         // fast paths
 219         if (a == b) return true;
 220         if (b.size() == 0) return true;
 221         if (a.size() == 0) return false;
 222
 223         if (a instanceof SortedSet && b instanceof SortedSet) {
 224             SortedSet aa = (SortedSet) a;
 225             SortedSet bb = (SortedSet) b;
 226             Comparator bbc = bb.comparator();
 227             Comparator aac = aa.comparator();
 228             if (bbc == null) {
 229                 if (aac == null) {
 230                     Iterator ai = aa.iterator();
 231                     Iterator bi = bb.iterator();
 232                     Comparable ao = (Comparable) ai.next(); // these are ok, since the sizes are != 0
 233                     Comparable bo = (Comparable) bi.next();
 234                     while (true) {
 235                         int rel = ao.compareTo(bo);
 236                         if (rel == 0) {
 237                             if (!bi.hasNext()) return true;
 238                             if (!ai.hasNext()) return false;
 239                             bo = (Comparable) bi.next();
 240                             ao = (Comparable) ai.next();
 241                         } else if (rel < 0) {
 242                             if (!ai.hasNext()) return false;
 243                             ao = (Comparable) ai.next();
 244                         } else {
 245                             return false;
 246                         }
 247                     }
 248                 }
 249             } else if (bbc.equals(a)) {
 250                 Iterator ai = aa.iterator();
 251                 Iterator bi = bb.iterator();
 252                 Object ao = ai.next(); // these are ok, since the sizes are != 0
 253                 Object bo = bi.next();
 254                 while (true) {
 255                     int rel = aac.compare(ao, bo);
 256                     if (rel == 0) {
 257                         if (!bi.hasNext()) return true;
 258                         if (!ai.hasNext()) return false;
 259                         bo = bi.next();
 260                         ao = ai.next();
 261                     } else if (rel < 0) {
 262                         if (!ai.hasNext()) return false;
 263                         ao = ai.next();
 264                     } else {
 265                         return false;
 266                     }
 267                 }
 268             }
 269         }
 270         return a.containsAll(b);
 271     }
 272
 273     public static boolean containsNone(Collection a, Collection b) {
 274         return !containsSome(a, b);
 275     }
 276
 277     /**
 278      * Used for results of getContainmentRelation
 279      */
 280     public static final int
 281         ALL_EMPTY = 0,
 282         NOT_A_SUPERSET_B = 1,
 283         NOT_A_DISJOINT_B = 2,
 284         NOT_A_SUBSET_B = 4,
 285         NOT_A_EQUALS_B = NOT_A_SUBSET_B | NOT_A_SUPERSET_B,
 286         A_PROPER_SUBSET_OF_B = NOT_A_DISJOINT_B | NOT_A_SUPERSET_B,
 287         A_PROPER_SUPERSET_B = NOT_A_SUBSET_B | NOT_A_DISJOINT_B,
 288         A_PROPER_OVERLAPS_B = NOT_A_SUBSET_B | NOT_A_DISJOINT_B | NOT_A_SUPERSET_B;
 289
 290     /**
 291      * Assesses all the possible containment relations between collections A and B with one call.<br>
 292      * Returns an int with bits set, according to a "Venn Diagram" view of A vs B.<br>
 293      * NOT_A_SUPERSET_B: a - b != {}<br>
 294      * NOT_A_DISJOINT_B: a * b != {}  // * is intersects<br>
 295      * NOT_A_SUBSET_B: b - a != {}<br>
 296      * Thus the bits can be used to get the following relations:<br>
 297      * for A_SUPERSET_B, use (x & CollectionUtilities.NOT_A_SUPERSET_B) == 0<br>
 298      * for A_SUBSET_B, use (x & CollectionUtilities.NOT_A_SUBSET_B) == 0<br>
 299      * for A_EQUALS_B, use (x & CollectionUtilities.NOT_A_EQUALS_B) == 0<br>
 300      * for A_DISJOINT_B, use (x & CollectionUtilities.NOT_A_DISJOINT_B) == 0<br>
 301      * for A_OVERLAPS_B, use (x & CollectionUtilities.NOT_A_DISJOINT_B) != 0<br>
 302      */
 303      public static int getContainmentRelation(Collection a, Collection b) {
 304         if (a.size() == 0) {
 305             return (b.size() == 0) ? ALL_EMPTY : NOT_A_SUPERSET_B;
 306         } else if (b.size() == 0) {
 307             return NOT_A_SUBSET_B;
 308         }
 309         int result = 0;
 310         // WARNING: one might think that the following can be short-circuited, by looking at
 311         // the sizes of a and b. However, this would fail in general, where a different comparator is being
 312         // used in the two collections. Unfortunately, there is no failsafe way to test for that.
 313         for (Iterator it = a.iterator(); result != 6 && it.hasNext();) {
 314             result |= (b.contains(it.next())) ? NOT_A_DISJOINT_B : NOT_A_SUBSET_B;
 315         }
 316         for (Iterator it = b.iterator(); (result & 3) != 3 && it.hasNext();) {
 317             result |= (a.contains(it.next())) ? NOT_A_DISJOINT_B : NOT_A_SUPERSET_B;
 318         }
 319         return result;
 320     }
 321
 322     public static String remove(String source, UnicodeSet removals) {
 323         StringBuffer result = new StringBuffer();
 324         int cp;
 325         for (int i = 0; i < source.length(); i += UTF16.getCharCount(cp)) {
 326             cp = UTF16.charAt(source, i);
 327             if (!removals.contains(cp)) UTF16.append(result, cp);
 328         }
 329         return result.toString();
 330     }
 331
 332 //#if defined(FOUNDATION10) || defined(J2SE13)
 333 //#else
 334      /**
 335       * Does one string contain another, starting at a specific offset?
 336       * @param text
 337       * @param offset
 338       * @param other
 339       * @return
 340       */
 341         public static int matchesAt(CharSequence text, int offset, CharSequence other) {
 342             int len = other.length();
 343             int i = 0;
 344             int j = offset;
 345             for (; i < len; ++i, ++j) {
 346                 char pc = other.charAt(i);
 347                 char tc = text.charAt(j);
 348                 if (pc != tc) return -1;
 349             }
 350             return i;
 351         }
 352
 353         /**
 354          * Returns the ending offset found by matching characters with testSet, until a position is found that doen't match
 355          * @param string
 356          * @param offset
 357          * @param testSet
 358          * @return
 359          */
 360         public int span(CharSequence string, int offset, UnicodeSet testSet) {
 361             while (true) {
 362                 int newOffset = testSet.matchesAt(string, offset);
 363                 if (newOffset < 0) return offset;
 364             }
 365         }
 366
 367         /**
 368          * Returns the ending offset found by matching characters with testSet, until a position is found that does match
 369          * @param string
 370          * @param offset
 371          * @param testSet
 372          * @return
 373          */
 374         public int spanNot(CharSequence string, int offset, UnicodeSet testSet) {
 375             while (true) {
 376                 int newOffset = testSet.matchesAt(string, offset);
 377                 if (newOffset >= 0) return offset;
 378                 ++offset; // try next character position
 379                 // we don't have to worry about surrogates for this.
 380             }
 381         }
 382 //#endif
 383
 384     public static String prettyPrint(UnicodeSet uset, boolean compressRanges, UnicodeSet toQuote, Transliterator quoter,
 385             Comparator ordering, Comparator spaceComparator) {
 386         PrettyPrinter pp = new PrettyPrinter().setCompressRanges(compressRanges);
 387         if (toQuote != null) pp.setToQuote(toQuote);
 388         if (ordering != null) pp.setOrdering(ordering);
 389         if (spaceComparator != null) pp.setSpaceComparator(spaceComparator);
 390         return pp.toPattern(uset);
 391     }
 392
 393     public static class MultiComparator implements Comparator {
 394         private Comparator[] comparators;
 395
 396         public MultiComparator (Comparator[] comparators) {
 397             this.comparators = comparators;
 398         }
 399
 400         /* Lexigraphic compare. Returns the first difference
 401          * @return zero if equal. Otherwise +/- (i+1)
 402          * where i is the index of the first comparator finding a difference
 403          * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
 404          */
 405         public int compare(Object arg0, Object arg1) {
 406             for (int i = 0; i < comparators.length; ++i) {
 407                 int result = comparators[i].compare(arg0, arg1);
 408                 if (result == 0) continue;
 409                 if (result > 0) return i+1;
 410                 return -(i+1);
 411             }
 412             return 0;
 413         }
 414     }
 415
 416     /**
 417      * Modifies Unicode set to flatten the strings. Eg [abc{da}] => [abcd]
 418      * Returns the set for chaining.
 419      * @param exemplar1
 420      * @return
 421      */
 422     public static UnicodeSet flatten(UnicodeSet exemplar1) {
 423         UnicodeSet result = new UnicodeSet();
 424         boolean gotString = false;
 425         for (UnicodeSetIterator it = new UnicodeSetIterator(exemplar1); it.nextRange();) {
 426             if (it.codepoint == UnicodeSetIterator.IS_STRING) {
 427                 result.addAll(it.string);
 428                 gotString = true;
 429             } else {
 430                 result.add(it.codepoint, it.codepointEnd);
 431             }
 432         }
 433         if (gotString) exemplar1.set(result);
 434         return exemplar1;
 435     }
 436
 437     /**
 438      * For producing filtered iterators
 439      */
 440     public static abstract class FilteredIterator implements Iterator {
 441         private Iterator baseIterator;
 442         private static final Object EMPTY = new Object();
 443         private static final Object DONE = new Object();
 444         private Object nextObject = EMPTY;
 445         public FilteredIterator set(Iterator baseIterator) {
 446             this.baseIterator = baseIterator;
 447             return this;
 448         }
 449         public void remove() {
 450             throw new UnsupportedOperationException("Doesn't support removal");
 451         }
 452         public Object next() {
 453             Object result = nextObject;
 454             nextObject = EMPTY;
 455             return result;
 456         }
 457         public boolean hasNext() {
 458             if (nextObject == DONE) return false;
 459             if (nextObject != EMPTY) return true;
 460             while (baseIterator.hasNext()) {
 461                 nextObject = baseIterator.next();
 462                 if (isIncluded(nextObject)) {
 463                     return true;
 464                 }
 465             }
 466             nextObject = DONE;
 467             return false;
 468         }
 469         abstract public boolean isIncluded(Object item);
 470     }
 471
 472     public static class PrefixIterator extends FilteredIterator {
 473         private String prefix;
 474         public PrefixIterator set(Iterator baseIterator, String prefix) {
 475             super.set(baseIterator);
 476             this.prefix = prefix;
 477             return this;
 478         }
 479         public boolean isIncluded(Object item) {
 480             return ((String)item).startsWith(prefix);
 481         }
 482     }
 483
 484 //#if defined(FOUNDATION10) || defined(J2SE13)
 485 //#else
 486     public static class RegexIterator extends FilteredIterator {
 487         private Matcher matcher;
 488         public RegexIterator set(Iterator baseIterator, Matcher matcher) {
 489             super.set(baseIterator);
 490             this.matcher = matcher;
 491             return this;
 492         }
 493         public boolean isIncluded(Object item) {
 494             return matcher.reset((String)item).matches();
 495         }
 496     }
 497 //#endif
 498 }