jars/icu4j-4_4_2-src/main/tests/translit/src/com/ibm/icu/dev/test/util/CollectionUtilities.java

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