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

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