1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
22
23 import com.google.common.annotations.Beta;
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.base.Function;
26 import com.google.common.base.Predicate;
27 import com.google.common.base.Predicates;
28 import com.google.common.math.IntMath;
29 import com.google.common.primitives.Ints;
30 import java.util.AbstractCollection;
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Collection;
34 import java.util.Collections;
35 import java.util.Comparator;
36 import java.util.Iterator;
37 import java.util.List;
38 import java.util.Spliterator;
39 import java.util.function.Consumer;
40 import org.checkerframework.checker.nullness.qual.Nullable;
41
42 /**
43 * Provides static methods for working with {@code Collection} instances.
44 *
45 * <p><b>Java 8 users:</b> several common uses for this class are now more comprehensively addressed
46 * by the new {@link java.util.stream.Stream} library. Read the method documentation below for
47 * comparisons. These methods are not being deprecated, but we gently encourage you to migrate to
48 * streams.
49 *
50 * @author Chris Povirk
51 * @author Mike Bostock
52 * @author Jared Levy
53 * @since 2.0
54 */
55 @GwtCompatible
56 public final class Collections2 {
57 private Collections2() {}
58
59 /**
60 * Returns the elements of {@code unfiltered} that satisfy a predicate. The returned collection is
61 * a live view of {@code unfiltered}; changes to one affect the other.
62 *
63 * <p>The resulting collection's iterator does not support {@code remove()}, but all other
64 * collection methods are supported. When given an element that doesn't satisfy the predicate, the
65 * collection's {@code add()} and {@code addAll()} methods throw an {@link
66 * IllegalArgumentException}. When methods such as {@code removeAll()} and {@code clear()} are
67 * called on the filtered collection, only elements that satisfy the filter will be removed from
68 * the underlying collection.
69 *
70 * <p>The returned collection isn't threadsafe or serializable, even if {@code unfiltered} is.
71 *
72 * <p>Many of the filtered collection's methods, such as {@code size()}, iterate across every
73 * element in the underlying collection and determine which elements satisfy the filter. When a
74 * live view is <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered,
75 * predicate)} and use the copy.
76 *
77 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
78 * {@link Predicate#apply}. Do not provide a predicate such as {@code
79 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link
80 * Iterables#filter(Iterable, Class)} for related functionality.)
81 *
82 * <p><b>{@code Stream} equivalent:</b> {@link java.util.stream.Stream#filter Stream.filter}.
83 */
84 // TODO(kevinb): how can we omit that Iterables link when building gwt
85 // javadoc?
86 public static <E> Collection<E> filter(Collection<E> unfiltered, Predicate<? super E> predicate) {
87 if (unfiltered instanceof FilteredCollection) {
88 // Support clear(), removeAll(), and retainAll() when filtering a filtered
89 // collection.
90 return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
91 }
92
93 return new FilteredCollection<E>(checkNotNull(unfiltered), checkNotNull(predicate));
94 }
95
96 /**
97 * Delegates to {@link Collection#contains}. Returns {@code false} if the {@code contains} method
98 * throws a {@code ClassCastException} or {@code NullPointerException}.
99 */
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 /**
356 * Returns a {@link Collection} of all the permutations of the specified {@link Iterable}.
357 *
358 * <p><i>Notes:</i> This is an implementation of the algorithm for Lexicographical Permutations
359 * Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7,
360 * Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the
361 * first permutation will be in ascending order, and the last will be in descending order.
362 *
363 * <p>Duplicate elements are considered equal. For example, the list [1, 1] will have only one
364 * permutation, instead of two. This is why the elements have to implement {@link Comparable}.
365 *
366 * <p>An empty iterable has only one permutation, which is an empty list.
367 *
368 * <p>This method is equivalent to {@code Collections2.orderedPermutations(list,
369 * Ordering.natural())}.
370 *
371 * @param elements the original iterable whose elements have to be permuted.
372 * @return an immutable {@link Collection} containing all the different permutations of the
373 * original iterable.
374 * @throws NullPointerException if the specified iterable is null or has any null elements.
375 * @since 12.0
376 */
377 @Beta
378 public static <E extends Comparable<? super E>> Collection<List<E>> orderedPermutations(
379 Iterable<E> elements) {
380 return orderedPermutations(elements, Ordering.natural());
381 }
382
383 /**
384 * Returns a {@link Collection} of all the permutations of the specified {@link Iterable} using
385 * the specified {@link Comparator} for establishing the lexicographical ordering.
386 *
387 * <p>Examples:
388 *
389 * <pre>{@code
390 * for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) {
391 * println(perm);
392 * }
393 * // -> ["a", "b", "c"]
394 * // -> ["a", "c", "b"]
395 * // -> ["b", "a", "c"]
396 * // -> ["b", "c", "a"]
397 * // -> ["c", "a", "b"]
398 * // -> ["c", "b", "a"]
399 *
400 * for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) {
401 * println(perm);
402 * }
403 * // -> [1, 1, 2, 2]
404 * // -> [1, 2, 1, 2]
405 * // -> [1, 2, 2, 1]
406 * // -> [2, 1, 1, 2]
407 * // -> [2, 1, 2, 1]
408 * // -> [2, 2, 1, 1]
409 * }</pre>
410 *
411 * <p><i>Notes:</i> This is an implementation of the algorithm for Lexicographical Permutations
412 * Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7,
413 * Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the
414 * first permutation will be in ascending order, and the last will be in descending order.
415 *
416 * <p>Elements that compare equal are considered equal and no new permutations are created by
417 * swapping them.
418 *
419 * <p>An empty iterable has only one permutation, which is an empty list.
420 *
421 * @param elements the original iterable whose elements have to be permuted.
422 * @param comparator a comparator for the iterable's elements.
423 * @return an immutable {@link Collection} containing all the different permutations of the
424 * original iterable.
425 * @throws NullPointerException If the specified iterable is null, has any null elements, or if
426 * the specified comparator is null.
427 * @since 12.0
428 */
429 @Beta
430 public static <E> Collection<List<E>> orderedPermutations(
431 Iterable<E> elements, Comparator<? super E> comparator) {
432 return new OrderedPermutationCollection<E>(elements, comparator);
433 }
434
435 private static final class OrderedPermutationCollection<E> extends AbstractCollection<List<E>> {
436 final ImmutableList<E> inputList;
437 final Comparator<? super E> comparator;
438 final int size;
439
440 OrderedPermutationCollection(Iterable<E> input, Comparator<? super E> comparator) {
441 this.inputList = ImmutableList.sortedCopyOf(comparator, input);
442 this.comparator = comparator;
443 this.size = calculateSize(inputList, comparator);
444 }
445
446 /**
447 * The number of permutations with repeated elements is calculated as follows:
448 *
449 * <ul>
450 * <li>For an empty list, it is 1 (base case).
451 * <li>When r numbers are added to a list of n-r elements, the number of permutations is
452 * increased by a factor of (n choose r).
453 * </ul>
454 */
455 private static <E> int calculateSize(
456 List<E> sortedInputList, Comparator<? super E> comparator) {
457 int permutations = 1;
458 int n = 1;
459 int r = 1;
460 while (n < sortedInputList.size()) {
461 int comparison = comparator.compare(sortedInputList.get(n - 1), sortedInputList.get(n));
462 if (comparison < 0) {
463 // We move to the next non-repeated element.
464 permutations = IntMath.saturatedMultiply(permutations, IntMath.binomial(n, r));
465 r = 0;
466 if (permutations == Integer.MAX_VALUE) {
467 return Integer.MAX_VALUE;
468 }
469 }
470 n++;
471 r++;
472 }
473 return IntMath.saturatedMultiply(permutations, IntMath.binomial(n, r));
474 }
475
476 @Override
477 public int size() {
478 return size;
479 }
480
481 @Override
482 public boolean isEmpty() {
483 return false;
484 }
485
486 @Override
487 public Iterator<List<E>> iterator() {
488 return new OrderedPermutationIterator<E>(inputList, comparator);
489 }
490
491 @Override
492 public boolean contains(@Nullable Object obj) {
493 if (obj instanceof List) {
494 List<?> list = (List<?>) obj;
495 return isPermutation(inputList, list);
496 }
497 return false;
498 }
499
500 @Override
501 public String toString() {
502 return "orderedPermutationCollection(" + inputList + ")";
503 }
504 }
505
506 private static final class OrderedPermutationIterator<E> extends AbstractIterator<List<E>> {
507 @Nullable List<E> nextPermutation;
508 final Comparator<? super E> comparator;
509
510 OrderedPermutationIterator(List<E> list, Comparator<? super E> comparator) {
511 this.nextPermutation = Lists.newArrayList(list);
512 this.comparator = comparator;
513 }
514
515 @Override
516 protected List<E> computeNext() {
517 if (nextPermutation == null) {
518 return endOfData();
519 }
520 ImmutableList<E> next = ImmutableList.copyOf(nextPermutation);
521 calculateNextPermutation();
522 return next;
523 }
524
525 void calculateNextPermutation() {
526 int j = findNextJ();
527 if (j == -1) {
528 nextPermutation = null;
529 return;
530 }
531
532 int l = findNextL(j);
533 Collections.swap(nextPermutation, j, l);
534 int n = nextPermutation.size();
535 Collections.reverse(nextPermutation.subList(j + 1, n));
536 }
537
538 int findNextJ() {
539 for (int k = nextPermutation.size() - 2; k >= 0; k--) {
540 if (comparator.compare(nextPermutation.get(k), nextPermutation.get(k + 1)) < 0) {
541 return k;
542 }
543 }
544 return -1;
545 }
546
547 int findNextL(int j) {
548 E ak = nextPermutation.get(j);
549 for (int l = nextPermutation.size() - 1; l > j; l--) {
550 if (comparator.compare(ak, nextPermutation.get(l)) < 0) {
551 return l;
552 }
553 }
554 throw new AssertionError("this statement should be unreachable");
555 }
556 }
557
558 /**
559 * Returns a {@link Collection} of all the permutations of the specified {@link Collection}.
560 *
561 * <p><i>Notes:</i> This is an implementation of the Plain Changes algorithm for permutations
562 * generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7,
563 * Section 7.2.1.2.
564 *
565 * <p>If the input list contains equal elements, some of the generated permutations will be equal.
566 *
567 * <p>An empty collection has only one permutation, which is an empty list.
568 *
569 * @param elements the original collection whose elements have to be permuted.
570 * @return an immutable {@link Collection} containing all the different permutations of the
571 * original collection.
572 * @throws NullPointerException if the specified collection is null or has any null elements.
573 * @since 12.0
574 */
575 @Beta
576 public static <E> Collection<List<E>> permutations(Collection<E> elements) {
577 return new PermutationCollection<E>(ImmutableList.copyOf(elements));
578 }
579
580 private static final class PermutationCollection<E> extends AbstractCollection<List<E>> {
581 final ImmutableList<E> inputList;
582
583 PermutationCollection(ImmutableList<E> input) {
584 this.inputList = input;
585 }
586
587 @Override
588 public int size() {
589 return IntMath.factorial(inputList.size());
590 }
591
592 @Override
593 public boolean isEmpty() {
594 return false;
595 }
596
597 @Override
598 public Iterator<List<E>> iterator() {
599 return new PermutationIterator<E>(inputList);
600 }
601
602 @Override
603 public boolean contains(@Nullable Object obj) {
604 if (obj instanceof List) {
605 List<?> list = (List<?>) obj;
606 return isPermutation(inputList, list);
607 }
608 return false;
609 }
610
611 @Override
612 public String toString() {
613 return "permutations(" + inputList + ")";
614 }
615 }
616
617 private static class PermutationIterator<E> extends AbstractIterator<List<E>> {
618 final List<E> list;
619 final int[] c;
620 final int[] o;
621 int j;
622
623 PermutationIterator(List<E> list) {
624 this.list = new ArrayList<E>(list);
625 int n = list.size();
626 c = new int[n];
627 o = new int[n];
628 Arrays.fill(c, 0);
629 Arrays.fill(o, 1);
630 j = Integer.MAX_VALUE;
631 }
632
633 @Override
634 protected List<E> computeNext() {
635 if (j <= 0) {
636 return endOfData();
637 }
638 ImmutableList<E> next = ImmutableList.copyOf(list);
639 calculateNextPermutation();
640 return next;
641 }
642
643 void calculateNextPermutation() {
644 j = list.size() - 1;
645 int s = 0;
646
647 // Handle the special case of an empty list. Skip the calculation of the
648 // next permutation.
649 if (j == -1) {
650 return;
651 }
652
653 while (true) {
654 int q = c[j] + o[j];
655 if (q < 0) {
656 switchDirection();
657 continue;
658 }
659 if (q == j + 1) {
660 if (j == 0) {
661 break;
662 }
663 s++;
664 switchDirection();
665 continue;
666 }
667
668 Collections.swap(list, j - c[j] + s, j - q + s);
669 c[j] = q;
670 break;
671 }
672 }
673
674 void switchDirection() {
675 o[j] = -o[j];
676 j--;
677 }
678 }
679
680 /** Returns {@code true} if the second list is a permutation of the first. */
681 private static boolean isPermutation(List<?> first, List<?> second) {
682 if (first.size() != second.size()) {
683 return false;
684 }
685 Multiset<?> firstMultiset = HashMultiset.create(first);
686 Multiset<?> secondMultiset = HashMultiset.create(second);
687 return firstMultiset.equals(secondMultiset);
688 }
689 }