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