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

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