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