Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2008 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.math.LongMath.binomial;
 
 
 import java.util.List;
 
 import  javax.annotation.Nullable;

Provides static methods for working with Collection instances.

Author(s):
Chris Povirk
Mike Bostock
Jared Levy
Since:
2.0 (imported from Google Collections Library)
 
 public final class Collections2 {
   private Collections2() {}

  
Returns the elements of unfiltered that satisfy a predicate. The returned collection is a live view of unfiltered; changes to one affect the other.

The resulting collection's iterator does not support remove(), but all other collection methods are supported. When given an element that doesn't satisfy the predicate, the collection's add() and addAll() methods throw an IllegalArgumentException. When methods such as removeAll() and clear() are called on the filtered collection, only elements that satisfy the filter will be removed from the underlying collection.

The returned collection isn't threadsafe or serializable, even if unfiltered is.

Many of the filtered collection's methods, such as size(), iterate across every element in the underlying collection and determine which elements satisfy the filter. When a live view is not needed, it may be faster to copy Iterables.filter(unfiltered, predicate) and use the copy.

Warning: predicate must be consistent with equals, as documented at Predicate.apply. Do not provide a predicate such as Predicates.instanceOf(ArrayList.class), which is inconsistent with equals. (See Iterables.filter(Iterable, Class) for related functionality.)

 
   // TODO(kevinb): how can we omit that Iterables link when building gwt
   // javadoc?
   public static <E> Collection<E> filter(
       Collection<E> unfilteredPredicate<? super E> predicate) {
     if (unfiltered instanceof FilteredCollection) {
       // Support clear(), removeAll(), and retainAll() when filtering a filtered
       // collection.
       return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
     }
 
     return new FilteredCollection<E>(
         checkNotNull(unfiltered), checkNotNull(predicate));
   }

  
Delegates to Collection.contains. Returns false if the contains method throws a ClassCastException.
 
  static boolean safeContains(Collection<?> collectionObject object) {
    try {
      return collection.contains(object);
    } catch (ClassCastException e) {
      return false;
    }
  }
  static class FilteredCollection<E> implements Collection<E> {
    final Collection<E> unfiltered;
    final Predicate<? super E> predicate;
    FilteredCollection(Collection<E> unfiltered,
        Predicate<? super E> predicate) {
      this. = unfiltered;
      this. = predicate;
    }
    FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) {
      return new FilteredCollection<E>(,
          Predicates.<E>and(newPredicate));
      // .<E> above needed to compile in JDK 5
    }
    @Override
    public boolean add(E element) {
      checkArgument(.apply(element));
      return .add(element);
    }
    @Override
    public boolean addAll(Collection<? extends E> collection) {
      for (E element : collection) {
        checkArgument(.apply(element));
      }
      return .addAll(collection);
    }
    @Override
    public void clear() {
      Iterables.removeIf();
    }
    @Override
    public boolean contains(Object element) {
      try {
        // unsafe cast can result in a CCE from predicate.apply(), which we
        // will catch
        @SuppressWarnings("unchecked")
        E e = (E) element;
        /*
         * We check whether e satisfies the predicate, when we really mean to
         * check whether the element contained in the set does. This is ok as
         * long as the predicate is consistent with equals, as required.
         */
        return .apply(e) && .contains(element);
      } catch (NullPointerException e) {
        return false;
      } catch (ClassCastException e) {
        return false;
      }
    }
    @Override
    public boolean containsAll(Collection<?> collection) {
      for (Object element : collection) {
        if (!contains(element)) {
          return false;
        }
      }
      return true;
    }
    @Override
    public boolean isEmpty() {
      return !Iterators.any(.iterator(), );
    }
    @Override
    public Iterator<E> iterator() {
      return Iterators.filter(.iterator(), );
    }
    @Override
    public boolean remove(Object element) {
      try {
        // unsafe cast can result in a CCE from predicate.apply(), which we
        // will catch
        @SuppressWarnings("unchecked")
        E e = (E) element;
        // See comment in contains() concerning predicate.apply(e)
        return .apply(e) && .remove(element);
      } catch (NullPointerException e) {
        return false;
      } catch (ClassCastException e) {
        return false;
      }
    }
    @Override
    public boolean removeAll(final Collection<?> collection) {
      checkNotNull(collection);
      Predicate<E> combinedPredicate = new Predicate<E>() {
        @Override
        public boolean apply(E input) {
          return .apply(input) && collection.contains(input);
        }
      };
      return Iterables.removeIf(combinedPredicate);
    }
    @Override
    public boolean retainAll(final Collection<?> collection) {
      checkNotNull(collection);
      Predicate<E> combinedPredicate = new Predicate<E>() {
        @Override
        public boolean apply(E input) {
          // See comment in contains() concerning predicate.apply(e)
          return .apply(input) && !collection.contains(input);
        }
      };
      return Iterables.removeIf(combinedPredicate);
    }
    @Override
    public int size() {
      return Iterators.size(iterator());
    }
    @Override
    public Object[] toArray() {
      // creating an ArrayList so filtering happens once
      return Lists.newArrayList(iterator()).toArray();
    }
    @Override
    public <T> T[] toArray(T[] array) {
      return Lists.newArrayList(iterator()).toArray(array);
    }
    @Override public String toString() {
      return Iterators.toString(iterator());
    }
  }

  
Returns a collection that applies function to each element of fromCollection. The returned collection is a live view of fromCollection; changes to one affect the other.

The returned collection's add() and addAll() methods throw an UnsupportedOperationException. All other collection methods are supported, as long as fromCollection supports them.

The returned collection isn't threadsafe or serializable, even if fromCollection is.

When a live view is not needed, it may be faster to copy the transformed collection and use the copy.

If the input Collection is known to be a List, consider Lists.transform. If only an Iterable is available, use Iterables.transform.

  public static <F, T> Collection<T> transform(Collection<F> fromCollection,
      Function<? super F, T> function) {
    return new TransformedCollection<F, T>(fromCollectionfunction);
  }
  static class TransformedCollection<F, T> extends AbstractCollection<T> {
    final Collection<F> fromCollection;
    final Function<? super F, ? extends T> function;
    TransformedCollection(Collection<F> fromCollection,
        Function<? super F, ? extends T> function) {
      this. = checkNotNull(fromCollection);
      this. = checkNotNull(function);
    }
    @Override public void clear() {
      .clear();
    }
    @Override public boolean isEmpty() {
      return .isEmpty();
    }
    @Override public Iterator<T> iterator() {
      return Iterators.transform(.iterator(), );
    }
    @Override public int size() {
      return .size();
    }
  }

  
Returns true if the collection self contains all of the elements in the collection c.

This method iterates over the specified collection c, checking each element returned by the iterator in turn to see if it is contained in the specified collection self. If all elements are so contained, true is returned, otherwise false.

Parameters:
self a collection which might contain all elements in c
c a collection whose elements might be contained by self
  static boolean containsAllImpl(Collection<?> selfCollection<?> c) {
    checkNotNull(self);
    for (Object o : c) {
      if (!self.contains(o)) {
        return false;
      }
    }
    return true;
  }

  
An implementation of Collection.toString().
  static String toStringImpl(final Collection<?> collection) {
    StringBuilder sb
        = newStringBuilderForCollection(collection.size()).append('[');
        sb, Iterables.transform(collectionnew Function<ObjectObject>() {
          @Override public Object apply(Object input) {
            return input == collection ? "(this Collection)" : input;
          }
        }));
    return sb.append(']').toString();
  }

  
Returns best-effort-sized StringBuilder based on the given collection size.
    checkArgument(size >= 0, "size must be non-negative");
    return new StringBuilder((int) Math.min(size * 8L, .));
  }

  
Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
  static <T> Collection<T> cast(Iterable<T> iterable) {
    return (Collection<T>) iterable;
  }
  static final Joiner STANDARD_JOINER = Joiner.on(", ").useForNull("null");

  
Returns a Collection of all the permutations of the specified Iterable.

Notes: This is an implementation of the algorithm for Lexicographical Permutations Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the first permutation will be in ascending order, and the last will be in descending order.

Duplicate elements are considered equal. For example, the list [1, 1] will have only one permutation, instead of two. This is why the elements have to implement Comparable.

An empty iterable has only one permutation, which is an empty list.

This method is equivalent to Collections2.orderedPermutations(list, Ordering.natural()).

Parameters:
elements the original iterable whose elements have to be permuted.
Returns:
an immutable Collection containing all the different permutations of the original iterable.
Throws:
NullPointerException if the specified iterable is null or has any null elements.
Since:
12.0
  @Beta public static <E extends Comparable<? super E>>
      Collection<List<E>> orderedPermutations(Iterable<E> elements) {
    return orderedPermutations(elements, Ordering.natural());
  }

  
Returns a Collection of all the permutations of the specified Iterable using the specified Comparator for establishing the lexicographical ordering.

Examples:

   for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) {
     println(perm);
   
   // -> ["a", "b", "c"]
   // -> ["a", "c", "b"]
   // -> ["b", "a", "c"]
   // -> ["b", "c", "a"]
   // -> ["c", "a", "b"]
   // -> ["c", "b", "a"]

   for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) {
     println(perm);
   }
   // -> [1, 1, 2, 2]
   // -> [1, 2, 1, 2]
   // -> [1, 2, 2, 1]
   // -> [2, 1, 1, 2]
   // -> [2, 1, 2, 1]
   // -> [2, 2, 1, 1]}

Notes: This is an implementation of the algorithm for Lexicographical Permutations Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the first permutation will be in ascending order, and the last will be in descending order.

Elements that compare equal are considered equal and no new permutations are created by swapping them.

An empty iterable has only one permutation, which is an empty list.

Parameters:
elements the original iterable whose elements have to be permuted.
comparator a comparator for the iterable's elements.
Returns:
an immutable Collection containing all the different permutations of the original iterable.
Throws:
NullPointerException If the specified iterable is null, has any null elements, or if the specified comparator is null.
Since:
12.0
  @Beta public static <E> Collection<List<E>> orderedPermutations(
      Iterable<E> elementsComparator<? super E> comparator) {
    return new OrderedPermutationCollection<E>(elementscomparator);
  }
  private static final class OrderedPermutationCollection<E>
      extends AbstractCollection<List<E>> {
    final ImmutableList<E> inputList;
    final Comparator<? super E> comparator;
    final int size;
        Comparator<? super E> comparator) {
      this. = Ordering.from(comparator).immutableSortedCopy(input);
      this. = comparator;
      this. = calculateSize(comparator);
    }

    
The number of permutations with repeated elements is calculated as follows:
  • For an empty list, it is 1 (base case).
  • When r numbers are added to a list of n-r elements, the number of permutations is increased by a factor of (n choose r).
    private static <E> int calculateSize(
        List<E> sortedInputListComparator<? super E> comparator) {
      long permutations = 1;
      int n = 1;
      int r = 1;
      while (n < sortedInputList.size()) {
        int comparison = comparator.compare(
            sortedInputList.get(n - 1), sortedInputList.get(n));
        if (comparison < 0) {
          // We move to the next non-repeated element.
          permutations *= binomial(nr);
          r = 0;
          if (!isPositiveInt(permutations)) {
            return .;
          }
        }
        n++;
        r++;
      }
      permutations *= binomial(nr);
      if (!isPositiveInt(permutations)) {
        return .;
      }
      return (intpermutations;
    }
    @Override public int size() {
      return ;
    }
    @Override public boolean isEmpty() {
      return false;
    }
    @Override public Iterator<List<E>> iterator() {
      return new OrderedPermutationIterator<E>();
    }
    @Override public boolean contains(@Nullable Object obj) {
      if (obj instanceof List) {
        List<?> list = (List<?>) obj;
        return isPermutation(list);
      }
      return false;
    }
    @Override public String toString() {
      return "orderedPermutationCollection(" +  + ")";
    }
  }
  private static final class OrderedPermutationIterator<E>
      extends AbstractIterator<List<E>> {
    final Comparator<? super E> comparator;
        Comparator<? super E> comparator) {
      this. = Lists.newArrayList(list);
      this. = comparator;
    }
    @Override protected List<E> computeNext() {
      if ( == null) {
        return endOfData();
      }
      ImmutableList<E> next = ImmutableList.copyOf();
      return next;
    }
    void calculateNextPermutation() {
      int j = findNextJ();
      if (j == -1) {
         = null;
        return;
      }
      int l = findNextL(j);
      Collections.swap(jl);
      int n = .size();
      Collections.reverse(.subList(j + 1, n));
    }
    int findNextJ() {
      for (int k = .size() - 2; k >= 0; k--) {
        if (.compare(.get(k),
            .get(k + 1)) < 0) {
          return k;
        }
      }
      return -1;
    }
    int findNextL(int j) {
      E ak = .get(j);
      for (int l = .size() - 1; l > jl--) {
        if (.compare(ak.get(l)) < 0) {
          return l;
        }
      }
      throw new AssertionError("this statement should be unreachable");
    }
  }

  
Returns a Collection of all the permutations of the specified Collection.

Notes: This is an implementation of the Plain Changes algorithm for permutations generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2.

If the input list contains equal elements, some of the generated permutations will be equal.

An empty collection has only one permutation, which is an empty list.

Parameters:
elements the original collection whose elements have to be permuted.
Returns:
an immutable Collection containing all the different permutations of the original collection.
Throws:
NullPointerException if the specified collection is null or has any null elements.
Since:
12.0
  @Beta public static <E> Collection<List<E>> permutations(
      Collection<E> elements) {
    return new PermutationCollection<E>(ImmutableList.copyOf(elements));
  }
  private static final class PermutationCollection<E>
      extends AbstractCollection<List<E>> {
    final ImmutableList<E> inputList;
      this. = input;
    }
    @Override public int size() {
      return IntMath.factorial(.size());
    }
    @Override public boolean isEmpty() {
      return false;
    }
    @Override public Iterator<List<E>> iterator() {
      return new PermutationIterator<E>();
    }
    @Override public boolean contains(@Nullable Object obj) {
      if (obj instanceof List) {
        List<?> list = (List<?>) obj;
        return isPermutation(list);
      }
      return false;
    }
    @Override public String toString() {
      return "permutations(" +  + ")";
    }
  }
  private static class PermutationIterator<E>
      extends AbstractIterator<List<E>> {
    final List<E> list;
    final int[] c;
    final int[] o;
    int j;
    PermutationIterator(List<E> list) {
      this. = new ArrayList<E>(list);
      int n = list.size();
       = new int[n];
       = new int[n];
      for (int i = 0; i < ni++) {
        [i] = 0;
        [i] = 1;
      }
       = .;
    }
    @Override protected List<E> computeNext() {
      if ( <= 0) {
        return endOfData();
      }
      ImmutableList<E> next = ImmutableList.copyOf();
      return next;
    }
    void calculateNextPermutation() {
       = .size() - 1;
      int s = 0;
      // Handle the special case of an empty list. Skip the calculation of the
      // next permutation.
      if ( == -1) {
        return;
      }
      while (true) {
        int q = [] + [];
        if (q < 0) {
          switchDirection();
          continue;
        }
        if (q ==  + 1) {
          if ( == 0) {
            break;
          }
          s++;
          switchDirection();
          continue;
        }
        Collections.swap( - [] + s - q + s);
        [] = q;
        break;
      }
    }
    void switchDirection() {
      [] = -[];
      --;
    }
  }

  
Returns true if the second list is a permutation of the first.
  private static boolean isPermutation(List<?> first,
      List<?> second) {
    if (first.size() != second.size()) {
      return false;
    }
    Multiset<?> firstSet = HashMultiset.create(first);
    Multiset<?> secondSet = HashMultiset.create(second);
    return firstSet.equals(secondSet);
  }
  private static boolean isPositiveInt(long n) {
    return n >= 0 && n <= .;
  }
New to GrepCode? Check out our FAQ X