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