001/* 002 * Copyright (C) 2008 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkNonnegative; 022import static java.util.Objects.requireNonNull; 023 024import com.google.common.annotations.GwtCompatible; 025import com.google.common.base.Function; 026import com.google.common.base.Predicate; 027import com.google.common.base.Predicates; 028import com.google.common.math.IntMath; 029import com.google.common.primitives.Ints; 030import java.util.AbstractCollection; 031import java.util.ArrayList; 032import java.util.Arrays; 033import java.util.Collection; 034import java.util.Collections; 035import java.util.Comparator; 036import java.util.Iterator; 037import java.util.List; 038import javax.annotation.CheckForNull; 039import org.checkerframework.checker.nullness.qual.Nullable; 040 041/** 042 * Provides static methods for working with {@code Collection} instances. 043 * 044 * <p><b>Java 8 users:</b> several common uses for this class are now more comprehensively addressed 045 * by the new {@link java.util.stream.Stream} library. Read the method documentation below for 046 * comparisons. These methods are not being deprecated, but we gently encourage you to migrate to 047 * streams. 048 * 049 * @author Chris Povirk 050 * @author Mike Bostock 051 * @author Jared Levy 052 * @since 2.0 053 */ 054@GwtCompatible 055@ElementTypesAreNonnullByDefault 056public final class Collections2 { 057 private Collections2() {} 058 059 /** 060 * Returns the elements of {@code unfiltered} that satisfy a predicate. The returned collection is 061 * a live view of {@code unfiltered}; changes to one affect the other. 062 * 063 * <p>The resulting collection's iterator does not support {@code remove()}, but all other 064 * collection methods are supported. When given an element that doesn't satisfy the predicate, the 065 * collection's {@code add()} and {@code addAll()} methods throw an {@link 066 * IllegalArgumentException}. When methods such as {@code removeAll()} and {@code clear()} are 067 * called on the filtered collection, only elements that satisfy the filter will be removed from 068 * the underlying collection. 069 * 070 * <p>The returned collection isn't threadsafe or serializable, even if {@code unfiltered} is. 071 * 072 * <p>Many of the filtered collection's methods, such as {@code size()}, iterate across every 073 * element in the underlying collection and determine which elements satisfy the filter. When a 074 * live view is <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, 075 * predicate)} and use the copy. 076 * 077 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at 078 * {@link Predicate#apply}. Do not provide a predicate such as {@code 079 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link 080 * Iterables#filter(Iterable, Class)} for related functionality.) 081 * 082 * <p><b>{@code Stream} equivalent:</b> {@link java.util.stream.Stream#filter Stream.filter}. 083 */ 084 // TODO(kevinb): how can we omit that Iterables link when building gwt 085 // javadoc? 086 public static <E extends @Nullable Object> Collection<E> filter( 087 Collection<E> unfiltered, Predicate<? super E> predicate) { 088 if (unfiltered instanceof FilteredCollection) { 089 // Support clear(), removeAll(), and retainAll() when filtering a filtered 090 // collection. 091 return ((FilteredCollection<E>) unfiltered).createCombined(predicate); 092 } 093 094 return new FilteredCollection<E>(checkNotNull(unfiltered), checkNotNull(predicate)); 095 } 096 097 /** 098 * Delegates to {@link Collection#contains}. Returns {@code false} if the {@code contains} method 099 * throws a {@code ClassCastException} or {@code NullPointerException}. 100 */ 101 static boolean safeContains(Collection<?> collection, @CheckForNull Object object) { 102 checkNotNull(collection); 103 try { 104 return collection.contains(object); 105 } catch (ClassCastException | NullPointerException e) { 106 return false; 107 } 108 } 109 110 /** 111 * Delegates to {@link Collection#remove}. Returns {@code false} if the {@code remove} method 112 * throws a {@code ClassCastException} or {@code NullPointerException}. 113 */ 114 static boolean safeRemove(Collection<?> collection, @CheckForNull Object object) { 115 checkNotNull(collection); 116 try { 117 return collection.remove(object); 118 } catch (ClassCastException | NullPointerException e) { 119 return false; 120 } 121 } 122 123 static class FilteredCollection<E extends @Nullable Object> extends AbstractCollection<E> { 124 final Collection<E> unfiltered; 125 final Predicate<? super E> predicate; 126 127 FilteredCollection(Collection<E> unfiltered, Predicate<? super E> predicate) { 128 this.unfiltered = unfiltered; 129 this.predicate = predicate; 130 } 131 132 FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) { 133 return new FilteredCollection<E>(unfiltered, Predicates.<E>and(predicate, newPredicate)); 134 // .<E> above needed to compile in JDK 5 135 } 136 137 @Override 138 public boolean add(@ParametricNullness E element) { 139 checkArgument(predicate.apply(element)); 140 return unfiltered.add(element); 141 } 142 143 @Override 144 public boolean addAll(Collection<? extends E> collection) { 145 for (E element : collection) { 146 checkArgument(predicate.apply(element)); 147 } 148 return unfiltered.addAll(collection); 149 } 150 151 @Override 152 public void clear() { 153 Iterables.removeIf(unfiltered, predicate); 154 } 155 156 @Override 157 public boolean contains(@CheckForNull Object element) { 158 if (safeContains(unfiltered, element)) { 159 @SuppressWarnings("unchecked") // element is in unfiltered, so it must be an E 160 E e = (E) element; 161 return predicate.apply(e); 162 } 163 return false; 164 } 165 166 @Override 167 public boolean containsAll(Collection<?> collection) { 168 return containsAllImpl(this, collection); 169 } 170 171 @Override 172 public boolean isEmpty() { 173 return !Iterables.any(unfiltered, predicate); 174 } 175 176 @Override 177 public Iterator<E> iterator() { 178 return Iterators.filter(unfiltered.iterator(), predicate); 179 } 180 181 @Override 182 public boolean remove(@CheckForNull Object element) { 183 return contains(element) && unfiltered.remove(element); 184 } 185 186 @Override 187 public boolean removeAll(final Collection<?> collection) { 188 boolean changed = false; 189 Iterator<E> itr = unfiltered.iterator(); 190 while (itr.hasNext()) { 191 E e = itr.next(); 192 if (predicate.apply(e) && collection.contains(e)) { 193 itr.remove(); 194 changed = true; 195 } 196 } 197 return changed; 198 } 199 200 @Override 201 public boolean retainAll(final Collection<?> collection) { 202 boolean changed = false; 203 Iterator<E> itr = unfiltered.iterator(); 204 while (itr.hasNext()) { 205 E e = itr.next(); 206 if (predicate.apply(e) && !collection.contains(e)) { 207 itr.remove(); 208 changed = true; 209 } 210 } 211 return changed; 212 } 213 214 @Override 215 public int size() { 216 int size = 0; 217 for (E e : unfiltered) { 218 if (predicate.apply(e)) { 219 size++; 220 } 221 } 222 return size; 223 } 224 225 @Override 226 public @Nullable Object[] toArray() { 227 // creating an ArrayList so filtering happens once 228 return Lists.newArrayList(iterator()).toArray(); 229 } 230 231 @Override 232 @SuppressWarnings("nullness") // b/192354773 in our checker affects toArray declarations 233 public <T extends @Nullable Object> T[] toArray(T[] array) { 234 return Lists.newArrayList(iterator()).toArray(array); 235 } 236 } 237 238 /** 239 * Returns a collection that applies {@code function} to each element of {@code fromCollection}. 240 * The returned collection is a live view of {@code fromCollection}; changes to one affect the 241 * other. 242 * 243 * <p>The returned collection's {@code add()} and {@code addAll()} methods throw an {@link 244 * UnsupportedOperationException}. All other collection methods are supported, as long as {@code 245 * fromCollection} supports them. 246 * 247 * <p>The returned collection isn't threadsafe or serializable, even if {@code fromCollection} is. 248 * 249 * <p>When a live view is <i>not</i> needed, it may be faster to copy the transformed collection 250 * and use the copy. 251 * 252 * <p>If the input {@code Collection} is known to be a {@code List}, consider {@link 253 * Lists#transform}. If only an {@code Iterable} is available, use {@link Iterables#transform}. 254 * 255 * <p><b>{@code Stream} equivalent:</b> {@link java.util.stream.Stream#map Stream.map}. 256 */ 257 public static <F extends @Nullable Object, T extends @Nullable Object> Collection<T> transform( 258 Collection<F> fromCollection, Function<? super F, T> function) { 259 return new TransformedCollection<>(fromCollection, function); 260 } 261 262 static class TransformedCollection<F extends @Nullable Object, T extends @Nullable Object> 263 extends AbstractCollection<T> { 264 final Collection<F> fromCollection; 265 final Function<? super F, ? extends T> function; 266 267 TransformedCollection(Collection<F> fromCollection, Function<? super F, ? extends T> function) { 268 this.fromCollection = checkNotNull(fromCollection); 269 this.function = checkNotNull(function); 270 } 271 272 @Override 273 public void clear() { 274 fromCollection.clear(); 275 } 276 277 @Override 278 public boolean isEmpty() { 279 return fromCollection.isEmpty(); 280 } 281 282 @Override 283 public Iterator<T> iterator() { 284 return Iterators.transform(fromCollection.iterator(), function); 285 } 286 287 @Override 288 public int size() { 289 return fromCollection.size(); 290 } 291 } 292 293 /** 294 * Returns {@code true} if the collection {@code self} contains all of the elements in the 295 * collection {@code c}. 296 * 297 * <p>This method iterates over the specified collection {@code c}, checking each element returned 298 * by the iterator in turn to see if it is contained in the specified collection {@code self}. If 299 * all elements are so contained, {@code true} is returned, otherwise {@code false}. 300 * 301 * @param self a collection which might contain all elements in {@code c} 302 * @param c a collection whose elements might be contained by {@code self} 303 */ 304 static boolean containsAllImpl(Collection<?> self, Collection<?> c) { 305 for (Object o : c) { 306 if (!self.contains(o)) { 307 return false; 308 } 309 } 310 return true; 311 } 312 313 /** An implementation of {@link Collection#toString()}. */ 314 static String toStringImpl(final Collection<?> collection) { 315 StringBuilder sb = newStringBuilderForCollection(collection.size()).append('['); 316 boolean first = true; 317 for (Object o : collection) { 318 if (!first) { 319 sb.append(", "); 320 } 321 first = false; 322 if (o == collection) { 323 sb.append("(this Collection)"); 324 } else { 325 sb.append(o); 326 } 327 } 328 return sb.append(']').toString(); 329 } 330 331 /** Returns best-effort-sized StringBuilder based on the given collection size. */ 332 static StringBuilder newStringBuilderForCollection(int size) { 333 checkNonnegative(size, "size"); 334 return new StringBuilder((int) Math.min(size * 8L, Ints.MAX_POWER_OF_TWO)); 335 } 336 337 /** 338 * Returns a {@link Collection} of all the permutations of the specified {@link Iterable}. 339 * 340 * <p><i>Notes:</i> This is an implementation of the algorithm for Lexicographical Permutations 341 * Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, 342 * Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the 343 * first permutation will be in ascending order, and the last will be in descending order. 344 * 345 * <p>Duplicate elements are considered equal. For example, the list [1, 1] will have only one 346 * permutation, instead of two. This is why the elements have to implement {@link Comparable}. 347 * 348 * <p>An empty iterable has only one permutation, which is an empty list. 349 * 350 * <p>This method is equivalent to {@code Collections2.orderedPermutations(list, 351 * Ordering.natural())}. 352 * 353 * @param elements the original iterable whose elements have to be permuted. 354 * @return an immutable {@link Collection} containing all the different permutations of the 355 * original iterable. 356 * @throws NullPointerException if the specified iterable is null or has any null elements. 357 * @since 12.0 358 */ 359 public static <E extends Comparable<? super E>> Collection<List<E>> orderedPermutations( 360 Iterable<E> elements) { 361 return orderedPermutations(elements, Ordering.natural()); 362 } 363 364 /** 365 * Returns a {@link Collection} of all the permutations of the specified {@link Iterable} using 366 * the specified {@link Comparator} for establishing the lexicographical ordering. 367 * 368 * <p>Examples: 369 * 370 * <pre>{@code 371 * for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) { 372 * println(perm); 373 * } 374 * // -> ["a", "b", "c"] 375 * // -> ["a", "c", "b"] 376 * // -> ["b", "a", "c"] 377 * // -> ["b", "c", "a"] 378 * // -> ["c", "a", "b"] 379 * // -> ["c", "b", "a"] 380 * 381 * for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) { 382 * println(perm); 383 * } 384 * // -> [1, 1, 2, 2] 385 * // -> [1, 2, 1, 2] 386 * // -> [1, 2, 2, 1] 387 * // -> [2, 1, 1, 2] 388 * // -> [2, 1, 2, 1] 389 * // -> [2, 2, 1, 1] 390 * }</pre> 391 * 392 * <p><i>Notes:</i> This is an implementation of the algorithm for Lexicographical Permutations 393 * Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, 394 * Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the 395 * first permutation will be in ascending order, and the last will be in descending order. 396 * 397 * <p>Elements that compare equal are considered equal and no new permutations are created by 398 * swapping them. 399 * 400 * <p>An empty iterable has only one permutation, which is an empty list. 401 * 402 * @param elements the original iterable whose elements have to be permuted. 403 * @param comparator a comparator for the iterable's elements. 404 * @return an immutable {@link Collection} containing all the different permutations of the 405 * original iterable. 406 * @throws NullPointerException If the specified iterable is null, has any null elements, or if 407 * the specified comparator is null. 408 * @since 12.0 409 */ 410 public static <E> Collection<List<E>> orderedPermutations( 411 Iterable<E> elements, Comparator<? super E> comparator) { 412 return new OrderedPermutationCollection<E>(elements, comparator); 413 } 414 415 private static final class OrderedPermutationCollection<E> extends AbstractCollection<List<E>> { 416 final ImmutableList<E> inputList; 417 final Comparator<? super E> comparator; 418 final int size; 419 420 OrderedPermutationCollection(Iterable<E> input, Comparator<? super E> comparator) { 421 this.inputList = ImmutableList.sortedCopyOf(comparator, input); 422 this.comparator = comparator; 423 this.size = calculateSize(inputList, comparator); 424 } 425 426 /** 427 * The number of permutations with repeated elements is calculated as follows: 428 * 429 * <ul> 430 * <li>For an empty list, it is 1 (base case). 431 * <li>When r numbers are added to a list of n-r elements, the number of permutations is 432 * increased by a factor of (n choose r). 433 * </ul> 434 */ 435 private static <E> int calculateSize( 436 List<E> sortedInputList, Comparator<? super E> comparator) { 437 int permutations = 1; 438 int n = 1; 439 int r = 1; 440 while (n < sortedInputList.size()) { 441 int comparison = comparator.compare(sortedInputList.get(n - 1), sortedInputList.get(n)); 442 if (comparison < 0) { 443 // We move to the next non-repeated element. 444 permutations = IntMath.saturatedMultiply(permutations, IntMath.binomial(n, r)); 445 r = 0; 446 if (permutations == Integer.MAX_VALUE) { 447 return Integer.MAX_VALUE; 448 } 449 } 450 n++; 451 r++; 452 } 453 return IntMath.saturatedMultiply(permutations, IntMath.binomial(n, r)); 454 } 455 456 @Override 457 public int size() { 458 return size; 459 } 460 461 @Override 462 public boolean isEmpty() { 463 return false; 464 } 465 466 @Override 467 public Iterator<List<E>> iterator() { 468 return new OrderedPermutationIterator<E>(inputList, comparator); 469 } 470 471 @Override 472 public boolean contains(@CheckForNull Object obj) { 473 if (obj instanceof List) { 474 List<?> list = (List<?>) obj; 475 return isPermutation(inputList, list); 476 } 477 return false; 478 } 479 480 @Override 481 public String toString() { 482 return "orderedPermutationCollection(" + inputList + ")"; 483 } 484 } 485 486 private static final class OrderedPermutationIterator<E> extends AbstractIterator<List<E>> { 487 @CheckForNull List<E> nextPermutation; 488 final Comparator<? super E> comparator; 489 490 OrderedPermutationIterator(List<E> list, Comparator<? super E> comparator) { 491 this.nextPermutation = Lists.newArrayList(list); 492 this.comparator = comparator; 493 } 494 495 @Override 496 @CheckForNull 497 protected List<E> computeNext() { 498 if (nextPermutation == null) { 499 return endOfData(); 500 } 501 ImmutableList<E> next = ImmutableList.copyOf(nextPermutation); 502 calculateNextPermutation(); 503 return next; 504 } 505 506 void calculateNextPermutation() { 507 int j = findNextJ(); 508 if (j == -1) { 509 nextPermutation = null; 510 return; 511 } 512 /* 513 * requireNonNull is safe because we don't clear nextPermutation until we're done calling this 514 * method. 515 */ 516 requireNonNull(nextPermutation); 517 518 int l = findNextL(j); 519 Collections.swap(nextPermutation, j, l); 520 int n = nextPermutation.size(); 521 Collections.reverse(nextPermutation.subList(j + 1, n)); 522 } 523 524 int findNextJ() { 525 /* 526 * requireNonNull is safe because we don't clear nextPermutation until we're done calling this 527 * method. 528 */ 529 requireNonNull(nextPermutation); 530 for (int k = nextPermutation.size() - 2; k >= 0; k--) { 531 if (comparator.compare(nextPermutation.get(k), nextPermutation.get(k + 1)) < 0) { 532 return k; 533 } 534 } 535 return -1; 536 } 537 538 int findNextL(int j) { 539 /* 540 * requireNonNull is safe because we don't clear nextPermutation until we're done calling this 541 * method. 542 */ 543 requireNonNull(nextPermutation); 544 E ak = nextPermutation.get(j); 545 for (int l = nextPermutation.size() - 1; l > j; l--) { 546 if (comparator.compare(ak, nextPermutation.get(l)) < 0) { 547 return l; 548 } 549 } 550 throw new AssertionError("this statement should be unreachable"); 551 } 552 } 553 554 /** 555 * Returns a {@link Collection} of all the permutations of the specified {@link Collection}. 556 * 557 * <p><i>Notes:</i> This is an implementation of the Plain Changes algorithm for permutations 558 * generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, 559 * Section 7.2.1.2. 560 * 561 * <p>If the input list contains equal elements, some of the generated permutations will be equal. 562 * 563 * <p>An empty collection has only one permutation, which is an empty list. 564 * 565 * @param elements the original collection whose elements have to be permuted. 566 * @return an immutable {@link Collection} containing all the different permutations of the 567 * original collection. 568 * @throws NullPointerException if the specified collection is null or has any null elements. 569 * @since 12.0 570 */ 571 public static <E> Collection<List<E>> permutations(Collection<E> elements) { 572 return new PermutationCollection<E>(ImmutableList.copyOf(elements)); 573 } 574 575 private static final class PermutationCollection<E> extends AbstractCollection<List<E>> { 576 final ImmutableList<E> inputList; 577 578 PermutationCollection(ImmutableList<E> input) { 579 this.inputList = input; 580 } 581 582 @Override 583 public int size() { 584 return IntMath.factorial(inputList.size()); 585 } 586 587 @Override 588 public boolean isEmpty() { 589 return false; 590 } 591 592 @Override 593 public Iterator<List<E>> iterator() { 594 return new PermutationIterator<E>(inputList); 595 } 596 597 @Override 598 public boolean contains(@CheckForNull Object obj) { 599 if (obj instanceof List) { 600 List<?> list = (List<?>) obj; 601 return isPermutation(inputList, list); 602 } 603 return false; 604 } 605 606 @Override 607 public String toString() { 608 return "permutations(" + inputList + ")"; 609 } 610 } 611 612 private static class PermutationIterator<E> extends AbstractIterator<List<E>> { 613 final List<E> list; 614 final int[] c; 615 final int[] o; 616 int j; 617 618 PermutationIterator(List<E> list) { 619 this.list = new ArrayList<E>(list); 620 int n = list.size(); 621 c = new int[n]; 622 o = new int[n]; 623 Arrays.fill(c, 0); 624 Arrays.fill(o, 1); 625 j = Integer.MAX_VALUE; 626 } 627 628 @Override 629 @CheckForNull 630 protected List<E> computeNext() { 631 if (j <= 0) { 632 return endOfData(); 633 } 634 ImmutableList<E> next = ImmutableList.copyOf(list); 635 calculateNextPermutation(); 636 return next; 637 } 638 639 void calculateNextPermutation() { 640 j = list.size() - 1; 641 int s = 0; 642 643 // Handle the special case of an empty list. Skip the calculation of the 644 // next permutation. 645 if (j == -1) { 646 return; 647 } 648 649 while (true) { 650 int q = c[j] + o[j]; 651 if (q < 0) { 652 switchDirection(); 653 continue; 654 } 655 if (q == j + 1) { 656 if (j == 0) { 657 break; 658 } 659 s++; 660 switchDirection(); 661 continue; 662 } 663 664 Collections.swap(list, j - c[j] + s, j - q + s); 665 c[j] = q; 666 break; 667 } 668 } 669 670 void switchDirection() { 671 o[j] = -o[j]; 672 j--; 673 } 674 } 675 676 /** Returns {@code true} if the second list is a permutation of the first. */ 677 private static boolean isPermutation(List<?> first, List<?> second) { 678 if (first.size() != second.size()) { 679 return false; 680 } 681 ObjectCountHashMap<?> firstCounts = counts(first); 682 ObjectCountHashMap<?> secondCounts = counts(second); 683 if (first.size() != second.size()) { 684 return false; 685 } 686 for (int i = 0; i < first.size(); i++) { 687 if (firstCounts.getValue(i) != secondCounts.get(firstCounts.getKey(i))) { 688 return false; 689 } 690 } 691 return true; 692 } 693 694 private static <E extends @Nullable Object> ObjectCountHashMap<E> counts( 695 Collection<E> collection) { 696 ObjectCountHashMap<E> map = new ObjectCountHashMap<>(); 697 for (E e : collection) { 698 map.put(e, map.get(e) + 1); 699 } 700 return map; 701 } 702}