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.math.LongMath.binomial;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.base.Function;
026import com.google.common.base.Joiner;
027import com.google.common.base.Predicate;
028import com.google.common.base.Predicates;
029import com.google.common.math.IntMath;
030import com.google.common.primitives.Ints;
031
032import java.util.AbstractCollection;
033import java.util.ArrayList;
034import java.util.Collection;
035import java.util.Collections;
036import java.util.Comparator;
037import java.util.Iterator;
038import java.util.List;
039
040import 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
051public 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}