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