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