View Javadoc
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 javax.annotation.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
61     * returned collection is a live view of {@code unfiltered}; changes to one
62     * affect the other.
63     *
64     * <p>The resulting collection's iterator does not support {@code remove()},
65     * but all other collection methods are supported. When given an element that
66     * doesn't satisfy the predicate, the collection's {@code add()} and {@code
67     * addAll()} methods throw an {@link IllegalArgumentException}. When methods
68     * such as {@code removeAll()} and {@code clear()} are called on the filtered
69     * collection, only elements that satisfy the filter will be removed from the
70     * underlying collection.
71     *
72     * <p>The returned collection isn't threadsafe or serializable, even if
73     * {@code unfiltered} is.
74     *
75     * <p>Many of the filtered collection's methods, such as {@code size()},
76     * iterate across every element in the underlying collection and determine
77     * which elements satisfy the filter. When a live view is <i>not</i> needed,
78     * it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
79     * and use the copy.
80     *
81     * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
82     * as documented at {@link Predicate#apply}. Do not provide a predicate such
83     * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
84     * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
85     * functionality.)
86     *
87     * <p><b>{@code Stream} equivalent:</b> {@link java.util.stream.Stream#filter Stream.filter}.
88     */
89    // TODO(kevinb): how can we omit that Iterables link when building gwt
90    // javadoc?
91    public static <E> Collection<E> filter(Collection<E> unfiltered, Predicate<? super E> predicate) {
92      if (unfiltered instanceof FilteredCollection) {
93        // Support clear(), removeAll(), and retainAll() when filtering a filtered
94        // collection.
95        return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
96      }
97  
98      return new FilteredCollection<E>(checkNotNull(unfiltered), checkNotNull(predicate));
99    }
100 
101   /**
102    * Delegates to {@link Collection#contains}. Returns {@code false} if the
103    * {@code contains} method throws a {@code ClassCastException} or
104    * {@code NullPointerException}.
105    */
106   static boolean safeContains(Collection<?> collection, @Nullable Object object) {
107     checkNotNull(collection);
108     try {
109       return collection.contains(object);
110     } catch (ClassCastException | NullPointerException e) {
111       return false;
112     }
113   }
114 
115   /**
116    * Delegates to {@link Collection#remove}. Returns {@code false} if the
117    * {@code remove} method throws a {@code ClassCastException} or
118    * {@code NullPointerException}.
119    */
120   static boolean safeRemove(Collection<?> collection, @Nullable Object object) {
121     checkNotNull(collection);
122     try {
123       return collection.remove(object);
124     } catch (ClassCastException | NullPointerException e) {
125       return false;
126     }
127   }
128 
129   static class FilteredCollection<E> extends AbstractCollection<E> {
130     final Collection<E> unfiltered;
131     final Predicate<? super E> predicate;
132 
133     FilteredCollection(Collection<E> unfiltered, Predicate<? super E> predicate) {
134       this.unfiltered = unfiltered;
135       this.predicate = predicate;
136     }
137 
138     FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) {
139       return new FilteredCollection<E>(unfiltered, Predicates.<E>and(predicate, newPredicate));
140       // .<E> above needed to compile in JDK 5
141     }
142 
143     @Override
144     public boolean add(E element) {
145       checkArgument(predicate.apply(element));
146       return unfiltered.add(element);
147     }
148 
149     @Override
150     public boolean addAll(Collection<? extends E> collection) {
151       for (E element : collection) {
152         checkArgument(predicate.apply(element));
153       }
154       return unfiltered.addAll(collection);
155     }
156 
157     @Override
158     public void clear() {
159       Iterables.removeIf(unfiltered, predicate);
160     }
161 
162     @Override
163     public boolean contains(@Nullable Object element) {
164       if (safeContains(unfiltered, element)) {
165         @SuppressWarnings("unchecked") // element is in unfiltered, so it must be an E
166         E e = (E) element;
167         return predicate.apply(e);
168       }
169       return false;
170     }
171 
172     @Override
173     public boolean containsAll(Collection<?> collection) {
174       return containsAllImpl(this, collection);
175     }
176 
177     @Override
178     public boolean isEmpty() {
179       return !Iterables.any(unfiltered, predicate);
180     }
181 
182     @Override
183     public Iterator<E> iterator() {
184       return Iterators.filter(unfiltered.iterator(), predicate);
185     }
186 
187     @Override
188     public Spliterator<E> spliterator() {
189       return CollectSpliterators.filter(unfiltered.spliterator(), predicate);
190     }
191 
192     @Override
193     public void forEach(Consumer<? super E> action) {
194       checkNotNull(action);
195       unfiltered.forEach(
196           (E e) -> {
197             if (predicate.test(e)) {
198               action.accept(e);
199             }
200           });
201     }
202 
203     @Override
204     public boolean remove(Object element) {
205       return contains(element) && unfiltered.remove(element);
206     }
207 
208     @Override
209     public boolean removeAll(final Collection<?> collection) {
210       return removeIf(collection::contains);
211     }
212 
213     @Override
214     public boolean retainAll(final Collection<?> collection) {
215       return removeIf(element -> !collection.contains(element));
216     }
217 
218     @Override
219     public boolean removeIf(java.util.function.Predicate<? super E> filter) {
220       checkNotNull(filter);
221       return unfiltered.removeIf(element -> predicate.apply(element) && filter.test(element));
222     }
223 
224     @Override
225     public int size() {
226       int size = 0;
227       for (E e : unfiltered) {
228         if (predicate.apply(e)) {
229           size++;
230         }
231       }
232       return size;
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 java.util.stream.Stream#map Stream.map}.
267    */
268   public static <F, T> Collection<T> transform(
269       Collection<F> fromCollection, Function<? super F, T> function) {
270     return new TransformedCollection<>(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     for (Object o : c) {
334       if (!self.contains(o)) {
335         return false;
336       }
337     }
338     return true;
339   }
340 
341   /**
342    * An implementation of {@link Collection#toString()}.
343    */
344   static String toStringImpl(final Collection<?> collection) {
345     StringBuilder sb = newStringBuilderForCollection(collection.size()).append('[');
346     boolean first = true;
347     for (Object o : collection) {
348       if (!first) {
349         sb.append(", ");
350       }
351       first = false;
352       if (o == collection) {
353         sb.append("(this Collection)");
354       } else {
355         sb.append(o);
356       }
357     }
358     return sb.append(']').toString();
359   }
360 
361   /**
362    * Returns best-effort-sized StringBuilder based on the given collection size.
363    */
364   static StringBuilder newStringBuilderForCollection(int size) {
365     checkNonnegative(size, "size");
366     return new StringBuilder((int) Math.min(size * 8L, Ints.MAX_POWER_OF_TWO));
367   }
368 
369   /**
370    * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
371    */
372   static <T> Collection<T> cast(Iterable<T> iterable) {
373     return (Collection<T>) iterable;
374   }
375 
376   /**
377    * Returns a {@link Collection} of all the permutations of the specified
378    * {@link Iterable}.
379    *
380    * <p><i>Notes:</i> This is an implementation of the algorithm for
381    * Lexicographical Permutations Generation, described in Knuth's "The Art of
382    * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The
383    * iteration order follows the lexicographical order. This means that
384    * the first permutation will be in ascending order, and the last will be in
385    * descending order.
386    *
387    * <p>Duplicate elements are considered equal. For example, the list [1, 1]
388    * will have only one permutation, instead of two. This is why the elements
389    * have to implement {@link Comparable}.
390    *
391    * <p>An empty iterable has only one permutation, which is an empty list.
392    *
393    * <p>This method is equivalent to
394    * {@code Collections2.orderedPermutations(list, Ordering.natural())}.
395    *
396    * @param elements the original iterable whose elements have to be permuted.
397    * @return an immutable {@link Collection} containing all the different
398    *     permutations of the original iterable.
399    * @throws NullPointerException if the specified iterable is null or has any
400    *     null elements.
401    * @since 12.0
402    */
403   @Beta
404   public static <E extends Comparable<? super E>> Collection<List<E>> orderedPermutations(
405       Iterable<E> elements) {
406     return orderedPermutations(elements, Ordering.natural());
407   }
408 
409   /**
410    * Returns a {@link Collection} of all the permutations of the specified
411    * {@link Iterable} using the specified {@link Comparator} for establishing
412    * the lexicographical ordering.
413    *
414    * <p>Examples: <pre>   {@code
415    *
416    *   for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) {
417    *     println(perm);
418    *   }
419    *   // -> ["a", "b", "c"]
420    *   // -> ["a", "c", "b"]
421    *   // -> ["b", "a", "c"]
422    *   // -> ["b", "c", "a"]
423    *   // -> ["c", "a", "b"]
424    *   // -> ["c", "b", "a"]
425    *
426    *   for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) {
427    *     println(perm);
428    *   }
429    *   // -> [1, 1, 2, 2]
430    *   // -> [1, 2, 1, 2]
431    *   // -> [1, 2, 2, 1]
432    *   // -> [2, 1, 1, 2]
433    *   // -> [2, 1, 2, 1]
434    *   // -> [2, 2, 1, 1]}</pre>
435    *
436    * <p><i>Notes:</i> This is an implementation of the algorithm for
437    * Lexicographical Permutations Generation, described in Knuth's "The Art of
438    * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The
439    * iteration order follows the lexicographical order. This means that
440    * the first permutation will be in ascending order, and the last will be in
441    * descending order.
442    *
443    * <p>Elements that compare equal are considered equal and no new permutations
444    * are created by swapping them.
445    *
446    * <p>An empty iterable has only one permutation, which is an empty list.
447    *
448    * @param elements the original iterable whose elements have to be permuted.
449    * @param comparator a comparator for the iterable's elements.
450    * @return an immutable {@link Collection} containing all the different
451    *     permutations of the original iterable.
452    * @throws NullPointerException If the specified iterable is null, has any
453    *     null elements, or if the specified comparator is null.
454    * @since 12.0
455    */
456   @Beta
457   public static <E> Collection<List<E>> orderedPermutations(
458       Iterable<E> elements, Comparator<? super E> comparator) {
459     return new OrderedPermutationCollection<E>(elements, comparator);
460   }
461 
462   private static final class OrderedPermutationCollection<E> extends AbstractCollection<List<E>> {
463     final ImmutableList<E> inputList;
464     final Comparator<? super E> comparator;
465     final int size;
466 
467     OrderedPermutationCollection(Iterable<E> input, Comparator<? super E> comparator) {
468       this.inputList = ImmutableList.sortedCopyOf(comparator, input);
469       this.comparator = comparator;
470       this.size = calculateSize(inputList, comparator);
471     }
472 
473     /**
474      * The number of permutations with repeated elements is calculated as
475      * follows:
476      * <ul>
477      * <li>For an empty list, it is 1 (base case).</li>
478      * <li>When r numbers are added to a list of n-r elements, the number of
479      * permutations is increased by a factor of (n choose r).</li>
480      * </ul>
481      */
482     private static <E> int calculateSize(
483         List<E> sortedInputList, Comparator<? super E> comparator) {
484       int permutations = 1;
485       int n = 1;
486       int r = 1;
487       while (n < sortedInputList.size()) {
488         int comparison = comparator.compare(sortedInputList.get(n - 1), sortedInputList.get(n));
489         if (comparison < 0) {
490           // We move to the next non-repeated element.
491           permutations = IntMath.saturatedMultiply(permutations, IntMath.binomial(n, r));
492           r = 0;
493           if (permutations == Integer.MAX_VALUE) {
494             return Integer.MAX_VALUE;
495           }
496         }
497         n++;
498         r++;
499       }
500       return IntMath.saturatedMultiply(permutations, IntMath.binomial(n, r));
501     }
502 
503     @Override
504     public int size() {
505       return size;
506     }
507 
508     @Override
509     public boolean isEmpty() {
510       return false;
511     }
512 
513     @Override
514     public Iterator<List<E>> iterator() {
515       return new OrderedPermutationIterator<E>(inputList, comparator);
516     }
517 
518     @Override
519     public boolean contains(@Nullable Object obj) {
520       if (obj instanceof List) {
521         List<?> list = (List<?>) obj;
522         return isPermutation(inputList, list);
523       }
524       return false;
525     }
526 
527     @Override
528     public String toString() {
529       return "orderedPermutationCollection(" + inputList + ")";
530     }
531   }
532 
533   private static final class OrderedPermutationIterator<E> extends AbstractIterator<List<E>> {
534 
535     List<E> nextPermutation;
536     final Comparator<? super E> comparator;
537 
538     OrderedPermutationIterator(List<E> list, Comparator<? super E> comparator) {
539       this.nextPermutation = Lists.newArrayList(list);
540       this.comparator = comparator;
541     }
542 
543     @Override
544     protected List<E> computeNext() {
545       if (nextPermutation == null) {
546         return endOfData();
547       }
548       ImmutableList<E> next = ImmutableList.copyOf(nextPermutation);
549       calculateNextPermutation();
550       return next;
551     }
552 
553     void calculateNextPermutation() {
554       int j = findNextJ();
555       if (j == -1) {
556         nextPermutation = null;
557         return;
558       }
559 
560       int l = findNextL(j);
561       Collections.swap(nextPermutation, j, l);
562       int n = nextPermutation.size();
563       Collections.reverse(nextPermutation.subList(j + 1, n));
564     }
565 
566     int findNextJ() {
567       for (int k = nextPermutation.size() - 2; k >= 0; k--) {
568         if (comparator.compare(nextPermutation.get(k), nextPermutation.get(k + 1)) < 0) {
569           return k;
570         }
571       }
572       return -1;
573     }
574 
575     int findNextL(int j) {
576       E ak = nextPermutation.get(j);
577       for (int l = nextPermutation.size() - 1; l > j; l--) {
578         if (comparator.compare(ak, nextPermutation.get(l)) < 0) {
579           return l;
580         }
581       }
582       throw new AssertionError("this statement should be unreachable");
583     }
584   }
585 
586   /**
587    * Returns a {@link Collection} of all the permutations of the specified
588    * {@link Collection}.
589    *
590    * <p><i>Notes:</i> This is an implementation of the Plain Changes algorithm
591    * for permutations generation, described in Knuth's "The Art of Computer
592    * Programming", Volume 4, Chapter 7, Section 7.2.1.2.
593    *
594    * <p>If the input list contains equal elements, some of the generated
595    * permutations will be equal.
596    *
597    * <p>An empty collection has only one permutation, which is an empty list.
598    *
599    * @param elements the original collection whose elements have to be permuted.
600    * @return an immutable {@link Collection} containing all the different
601    *     permutations of the original collection.
602    * @throws NullPointerException if the specified collection is null or has any
603    *     null elements.
604    * @since 12.0
605    */
606   @Beta
607   public static <E> Collection<List<E>> permutations(Collection<E> elements) {
608     return new PermutationCollection<E>(ImmutableList.copyOf(elements));
609   }
610 
611   private static final class PermutationCollection<E> extends AbstractCollection<List<E>> {
612     final ImmutableList<E> inputList;
613 
614     PermutationCollection(ImmutableList<E> input) {
615       this.inputList = input;
616     }
617 
618     @Override
619     public int size() {
620       return IntMath.factorial(inputList.size());
621     }
622 
623     @Override
624     public boolean isEmpty() {
625       return false;
626     }
627 
628     @Override
629     public Iterator<List<E>> iterator() {
630       return new PermutationIterator<E>(inputList);
631     }
632 
633     @Override
634     public boolean contains(@Nullable Object obj) {
635       if (obj instanceof List) {
636         List<?> list = (List<?>) obj;
637         return isPermutation(inputList, list);
638       }
639       return false;
640     }
641 
642     @Override
643     public String toString() {
644       return "permutations(" + inputList + ")";
645     }
646   }
647 
648   private static class PermutationIterator<E> extends AbstractIterator<List<E>> {
649     final List<E> list;
650     final int[] c;
651     final int[] o;
652     int j;
653 
654     PermutationIterator(List<E> list) {
655       this.list = new ArrayList<E>(list);
656       int n = list.size();
657       c = new int[n];
658       o = new int[n];
659       Arrays.fill(c, 0);
660       Arrays.fill(o, 1);
661       j = Integer.MAX_VALUE;
662     }
663 
664     @Override
665     protected List<E> computeNext() {
666       if (j <= 0) {
667         return endOfData();
668       }
669       ImmutableList<E> next = ImmutableList.copyOf(list);
670       calculateNextPermutation();
671       return next;
672     }
673 
674     void calculateNextPermutation() {
675       j = list.size() - 1;
676       int s = 0;
677 
678       // Handle the special case of an empty list. Skip the calculation of the
679       // next permutation.
680       if (j == -1) {
681         return;
682       }
683 
684       while (true) {
685         int q = c[j] + o[j];
686         if (q < 0) {
687           switchDirection();
688           continue;
689         }
690         if (q == j + 1) {
691           if (j == 0) {
692             break;
693           }
694           s++;
695           switchDirection();
696           continue;
697         }
698 
699         Collections.swap(list, j - c[j] + s, j - q + s);
700         c[j] = q;
701         break;
702       }
703     }
704 
705     void switchDirection() {
706       o[j] = -o[j];
707       j--;
708     }
709   }
710 
711   /**
712    * Returns {@code true} if the second list is a permutation of the first.
713    */
714   private static boolean isPermutation(List<?> first, List<?> second) {
715     if (first.size() != second.size()) {
716       return false;
717     }
718     Multiset<?> firstMultiset = HashMultiset.create(first);
719     Multiset<?> secondMultiset = HashMultiset.create(second);
720     return firstMultiset.equals(secondMultiset);
721   }
722 }