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