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