Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   /*
    * Copyright (C) 2007 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 java.util.Arrays;
  import java.util.EnumSet;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  import java.util.TreeSet;
  
Static utility methods pertaining to java.util.Set instances. Also see this class's counterparts Lists, Maps and com.google.common.collect.Queues.

See the Guava User Guide article on Sets.

Author(s):
Kevin Bourrillion
Jared Levy
Chris Povirk
Since:
2.0 (imported from Google Collections Library)
  
  @GwtCompatible(emulated = true)
  public final class Sets {
    private Sets() {}

  
java.util.AbstractSet substitute without the potentially-quadratic removeAll implementation.
  
    abstract static class ImprovedAbstractSet<E> extends AbstractSet<E> {
      @Override
      public boolean removeAll(Collection<?> c) {
        return removeAllImpl(thisc);
      }
  
      @Override
      public boolean retainAll(Collection<?> c) {
        return super.retainAll(checkNotNull(c)); // GWT compatibility
      }
    }

  
Returns an immutable set instance containing the given enum elements. Internally, the returned set will be backed by an java.util.EnumSet.

The iteration order of the returned set follows the enum's iteration order, not the order in which the elements are provided to the method.

Parameters:
anElement one of the elements the set should contain
otherElements the rest of the elements the set should contain
Returns:
an immutable set containing those elements, minus duplicates
  
    // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
    @GwtCompatible(serializable = true)
    public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
        E anElement, E... otherElements) {
      return ImmutableEnumSet.asImmutable(EnumSet.of(anElementotherElements));
    }

  
Returns an immutable set instance containing the given enum elements. Internally, the returned set will be backed by an java.util.EnumSet.

The iteration order of the returned set follows the enum's iteration order, not the order in which the elements appear in the given collection.

Parameters:
elements the elements, all of the same enum type, that the set should contain
Returns:
an immutable set containing those elements, minus duplicates
 
   // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
   @GwtCompatible(serializable = true)
   public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
       Iterable<E> elements) {
     if (elements instanceof ImmutableEnumSet) {
       return (ImmutableEnumSet<E>) elements;
     } else if (elements instanceof Collection) {
       Collection<E> collection = (Collection<E>) elements;
       if (collection.isEmpty()) {
         return ImmutableSet.of();
       } else {
         return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection));
       }
     } else {
       Iterator<E> itr = elements.iterator();
       if (itr.hasNext()) {
         EnumSet<E> enumSet = EnumSet.of(itr.next());
         Iterators.addAll(enumSetitr);
         return ImmutableEnumSet.asImmutable(enumSet);
       } else {
         return ImmutableSet.of();
       }
     }
   }

  
Returns a new EnumSet instance containing the given elements. Unlike java.util.EnumSet.copyOf(java.util.Collection), this method does not produce an exception on an empty collection, and it may be called on any iterable, not just a Collection.
 
   public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable,
       Class<E> elementType) {
     EnumSet<E> set = EnumSet.noneOf(elementType);
     Iterables.addAll(setiterable);
     return set;
   }
 
   // HashSet
 
  
Creates a mutable, empty HashSet instance.

Note: if mutability is not required, use ImmutableSet.of() instead.

Note: if E is an java.lang.Enum type, use java.util.EnumSet.noneOf(java.lang.Class) instead.

Returns:
a new, empty HashSet
 
   public static <E> HashSet<E> newHashSet() {
     return new HashSet<E>();
   }

  
Creates a mutable HashSet instance containing the given elements in unspecified order.

Note: if mutability is not required and the elements are non-null, use an overload of ImmutableSet.of() (for varargs) or ImmutableSet.copyOf(java.lang.Object[]) (for an array) instead.

Note: if E is an java.lang.Enum type, use java.util.EnumSet.of(java.lang.Enum,java.lang.Enum[]) instead.

Parameters:
elements the elements that the set should contain
Returns:
a new HashSet containing those elements (minus duplicates)
 
   public static <E> HashSet<E> newHashSet(E... elements) {
     HashSet<E> set = newHashSetWithExpectedSize(elements.length);
     Collections.addAll(setelements);
     return set;
   }

  
Creates a HashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth. This behavior cannot be broadly guaranteed, but it is observed to be true for OpenJDK 1.6. It also can't be guaranteed that the method isn't inadvertently oversizing the returned set.

Parameters:
expectedSize the number of elements you expect to add to the returned set
Returns:
a new, empty HashSet with enough capacity to hold expectedSize elements without resizing
Throws:
java.lang.IllegalArgumentException if expectedSize is negative
 
   public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
     return new HashSet<E>(Maps.capacity(expectedSize));
   }

  
Creates a mutable HashSet instance containing the given elements in unspecified order.

Note: if mutability is not required and the elements are non-null, use ImmutableSet.copyOf(java.lang.Iterable) instead.

Note: if E is an java.lang.Enum type, use newEnumSet(java.lang.Iterable,java.lang.Class) instead.

Parameters:
elements the elements that the set should contain
Returns:
a new HashSet containing those elements (minus duplicates)
 
   public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
     return (elements instanceof Collection)
         ? new HashSet<E>(Collections2.cast(elements))
         : newHashSet(elements.iterator());
   }

  
Creates a mutable HashSet instance containing the given elements in unspecified order.

Note: if mutability is not required and the elements are non-null, use ImmutableSet.copyOf(java.lang.Iterable) instead.

Note: if E is an java.lang.Enum type, you should create an java.util.EnumSet instead.

Parameters:
elements the elements that the set should contain
Returns:
a new HashSet containing those elements (minus duplicates)
 
   public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
     HashSet<E> set = newHashSet();
     Iterators.addAll(setelements);
     return set;
   }

  
Creates a thread-safe set backed by a hash map. The set is backed by a java.util.concurrent.ConcurrentHashMap instance, and thus carries the same concurrency guarantees.

Unlike HashSet, this class does NOT allow null to be used as an element. The set is serializable.

Returns:
a new, empty thread-safe Set
Since:
15.0
 
   public static <E> Set<E> newConcurrentHashSet() {
     return newSetFromMap(new ConcurrentHashMap<E, Boolean>());
   }

  
Creates a thread-safe set backed by a hash map and containing the given elements. The set is backed by a java.util.concurrent.ConcurrentHashMap instance, and thus carries the same concurrency guarantees.

Unlike HashSet, this class does NOT allow null to be used as an element. The set is serializable.

Parameters:
elements the elements that the set should contain
Returns:
a new thread-safe set containing those elements (minus duplicates)
Throws:
java.lang.NullPointerException if elements or any of its contents is null
Since:
15.0
 
   public static <E> Set<E> newConcurrentHashSet(
       Iterable<? extends E> elements) {
     Set<E> set = newConcurrentHashSet();
     Iterables.addAll(setelements);
     return set;
   }
 
   // LinkedHashSet
 
  
Creates a mutable, empty LinkedHashSet instance.

Note: if mutability is not required, use ImmutableSet.of() instead.

Returns:
a new, empty LinkedHashSet
 
   public static <E> LinkedHashSet<E> newLinkedHashSet() {
     return new LinkedHashSet<E>();
   }

  
Creates a LinkedHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth. This behavior cannot be broadly guaranteed, but it is observed to be true for OpenJDK 1.6. It also can't be guaranteed that the method isn't inadvertently oversizing the returned set.

Parameters:
expectedSize the number of elements you expect to add to the returned set
Returns:
a new, empty LinkedHashSet with enough capacity to hold expectedSize elements without resizing
Throws:
java.lang.IllegalArgumentException if expectedSize is negative
Since:
11.0
 
   public static <E> LinkedHashSet<E> newLinkedHashSetWithExpectedSize(
       int expectedSize) {
     return new LinkedHashSet<E>(Maps.capacity(expectedSize));
   }

  
Creates a mutable LinkedHashSet instance containing the given elements in order.

Note: if mutability is not required and the elements are non-null, use ImmutableSet.copyOf(java.lang.Iterable) instead.

Parameters:
elements the elements that the set should contain, in order
Returns:
a new LinkedHashSet containing those elements (minus duplicates)
 
   public static <E> LinkedHashSet<E> newLinkedHashSet(
       Iterable<? extends E> elements) {
     if (elements instanceof Collection) {
       return new LinkedHashSet<E>(Collections2.cast(elements));
     }
     LinkedHashSet<E> set = newLinkedHashSet();
     Iterables.addAll(setelements);
     return set;
   }
 
   // TreeSet
 
  
Creates a mutable, empty TreeSet instance sorted by the natural sort ordering of its elements.

Note: if mutability is not required, use ImmutableSortedSet.of() instead.

Returns:
a new, empty TreeSet
 
   public static <E extends ComparableTreeSet<E> newTreeSet() {
     return new TreeSet<E>();
   }

  
Creates a mutable TreeSet instance containing the given elements sorted by their natural ordering.

Note: if mutability is not required, use ImmutableSortedSet.copyOf(java.lang.Iterable) instead.

Note: If elements is a SortedSet with an explicit comparator, this method has different behavior than java.util.TreeSet.(java.util.SortedSet), which returns a TreeSet with that comparator.

Parameters:
elements the elements that the set should contain
Returns:
a new TreeSet containing those elements (minus duplicates)
 
   public static <E extends ComparableTreeSet<E> newTreeSet(
       Iterable<? extends E> elements) {
     TreeSet<E> set = newTreeSet();
     Iterables.addAll(setelements);
     return set;
   }

  
Creates a mutable, empty TreeSet instance with the given comparator.

Note: if mutability is not required, use ImmutableSortedSet.orderedBy(comparator).build() instead.

Parameters:
comparator the comparator to use to sort the set
Returns:
a new, empty TreeSet
Throws:
java.lang.NullPointerException if comparator is null
 
   public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
     return new TreeSet<E>(checkNotNull(comparator));
   }

  
Creates an empty Set that uses identity to determine equality. It compares object references, instead of calling equals, to determine whether a provided object matches an element in the set. For example, contains returns false when passed an object that equals a set member, but isn't the same instance. This behavior is similar to the way IdentityHashMap handles key lookups.

Since:
8.0
 
   public static <E> Set<E> newIdentityHashSet() {
     return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
   }

  
Creates an EnumSet consisting of all enum values that are not in the specified collection. If the collection is an java.util.EnumSet, this method has the same behavior as java.util.EnumSet.complementOf(java.util.EnumSet). Otherwise, the specified collection must contain at least one element, in order to determine the element type. If the collection could be empty, use complementOf(java.util.Collection,java.lang.Class) instead of this method.

Parameters:
collection the collection whose complement should be stored in the enum set
Returns:
a new, modifiable EnumSet containing all values of the enum that aren't present in the given collection
Throws:
java.lang.IllegalArgumentException if collection is not an EnumSet instance and contains no elements
 
   public static <E extends Enum<E>> EnumSet<E> complementOf(
       Collection<E> collection) {
     if (collection instanceof EnumSet) {
       return EnumSet.complementOf((EnumSet<E>) collection);
     }
     checkArgument(!collection.isEmpty(),
         "collection is empty; use the other version of this method");
     Class<E> type = collection.iterator().next().getDeclaringClass();
     return makeComplementByHand(collectiontype);
   }

  
Creates an EnumSet consisting of all enum values that are not in the specified collection. This is equivalent to java.util.EnumSet.complementOf(java.util.EnumSet), but can act on any input collection, as long as the elements are of enum type.

Parameters:
collection the collection whose complement should be stored in the EnumSet
type the type of the elements in the set
Returns:
a new, modifiable EnumSet initially containing all the values of the enum not present in the given collection
 
   public static <E extends Enum<E>> EnumSet<E> complementOf(
       Collection<E> collectionClass<E> type) {
     checkNotNull(collection);
     return (collection instanceof EnumSet)
         ? EnumSet.complementOf((EnumSet<E>) collection)
         : makeComplementByHand(collectiontype);
   }
 
   private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
       Collection<E> collectionClass<E> type) {
     EnumSet<E> result = EnumSet.allOf(type);
     result.removeAll(collection);
     return result;
   }

  
Returns a set backed by the specified map. The resulting set displays the same ordering, concurrency, and performance characteristics as the backing map. In essence, this factory method provides a java.util.Set implementation corresponding to any java.util.Map implementation. There is no need to use this method on a java.util.Map implementation that already has a corresponding java.util.Set implementation (such as java.util.HashMap or java.util.TreeMap).

Each method invocation on the set returned by this method results in exactly one method invocation on the backing map or its keySet view, with one exception. The addAll method is implemented as a sequence of put invocations on the backing map.

The specified map must be empty at the time this method is invoked, and should not be accessed directly after this method returns. These conditions are ensured if the map is created empty, passed directly to this method, and no reference to the map is retained, as illustrated in the following code fragment:

  Set<Object> identityHashSet = Sets.newSetFromMap(
       new IdentityHashMap<Object, Boolean>());

This method has the same behavior as the JDK 6 method Collections.newSetFromMap(). The returned set is serializable if the backing map is.

Parameters:
map the backing map
Returns:
the set backed by the map
Throws:
java.lang.IllegalArgumentException if map is not empty
 
   public static <E> Set<E> newSetFromMap(Map<E, Booleanmap) {
     return Platform.newSetFromMap(map);
   }

  
An unmodifiable view of a set which may be backed by other sets; this view will change as the backing sets do. Contains methods to copy the data into a new set which will then remain stable. There is usually no reason to retain a reference of type SetView; typically, you either use it as a plain java.util.Set, or immediately invoke immutableCopy() or copyInto(java.util.Set) and forget the SetView itself.

Since:
2.0 (imported from Google Collections Library)
 
   public abstract static class SetView<E> extends AbstractSet<E> {
     private SetView() {} // no subclasses but our own
 
    
Returns an immutable copy of the current contents of this set view. Does not support null elements.

Warning: this may have unexpected results if a backing set of this view uses a nonstandard notion of equivalence, for example if it is a java.util.TreeSet using a comparator that is inconsistent with java.lang.Object.equals(java.lang.Object).

 
     public ImmutableSet<E> immutableCopy() {
       return ImmutableSet.copyOf(this);
     }

    
Copies the current contents of this set view into an existing set. This method has equivalent behavior to set.addAll(this), assuming that all the sets involved are based on the same notion of equivalence.

Returns:
a reference to set, for convenience
 
     // Note: S should logically extend Set<? super E> but can't due to either
     // some javac bug or some weirdness in the spec, not sure which.
     public <S extends Set<E>> S copyInto(S set) {
       set.addAll(this);
       return set;
     }
   }

  
Returns an unmodifiable view of the union of two sets. The returned set contains all elements that are contained in either backing set. Iterating over the returned set iterates first over all the elements of set1, then over each element of set2, in order, that is not contained in set1.

Results are undefined if set1 and set2 are sets based on different equivalence relations (as java.util.HashSet, java.util.TreeSet, and the java.util.Map.keySet() of an IdentityHashMap all are).

Note: The returned view performs better when set1 is the smaller of the two sets. If you have reason to believe one of your sets will generally be smaller than the other, pass it first.

Further, note that the current implementation is not suitable for nested union views, i.e. the following should be avoided when in a loop: union = Sets.union(union, anotherSet);, since iterating over the resulting set has a cubic complexity to the depth of the nesting.

 
   public static <E> SetView<E> union(
       final Set<? extends E> set1final Set<? extends E> set2) {
     checkNotNull(set1"set1");
     checkNotNull(set2"set2");
 
     final Set<? extends E> set2minus1 = difference(set2set1);
 
     return new SetView<E>() {
       @Override public int size() {
         return set1.size() + set2minus1.size();
       }
       @Override public boolean isEmpty() {
         return set1.isEmpty() && set2.isEmpty();
       }
       @Override public Iterator<E> iterator() {
         return Iterators.unmodifiableIterator(
             Iterators.concat(set1.iterator(), set2minus1.iterator()));
       }
       @Override public boolean contains(Object object) {
         return set1.contains(object) || set2.contains(object);
       }
       @Override public <S extends Set<E>> S copyInto(S set) {
         set.addAll(set1);
         set.addAll(set2);
         return set;
       }
       @Override public ImmutableSet<E> immutableCopy() {
         return new ImmutableSet.Builder<E>()
             .addAll(set1).addAll(set2).build();
       }
     };
   }

  
Returns an unmodifiable view of the intersection of two sets. The returned set contains all elements that are contained by both backing sets. The iteration order of the returned set matches that of set1.

Results are undefined if set1 and set2 are sets based on different equivalence relations (as HashSet, TreeSet, and the keySet of an IdentityHashMap all are).

Note: The returned view performs slightly better when set1 is the smaller of the two sets. If you have reason to believe one of your sets will generally be smaller than the other, pass it first. Unfortunately, since this method sets the generic type of the returned set based on the type of the first set passed, this could in rare cases force you to make a cast, for example:

   Set<Object> aFewBadObjects = ...
   Set<String> manyBadStrings = ...

   // impossible for a non-String to be in the intersection
   SuppressWarnings("unchecked")
   Set<String> badStrings = (Set) Sets.intersection(
       aFewBadObjects, manyBadStrings);

This is unfortunate, but should come up only very rarely.

 
   public static <E> SetView<E> intersection(
       final Set<E> set1final Set<?> set2) {
     checkNotNull(set1"set1");
     checkNotNull(set2"set2");
 
     final Predicate<ObjectinSet2 = Predicates.in(set2);
     return new SetView<E>() {
       @Override public Iterator<E> iterator() {
         return Iterators.filter(set1.iterator(), inSet2);
       }
       @Override public int size() {
         return Iterators.size(iterator());
       }
       @Override public boolean isEmpty() {
         return !iterator().hasNext();
       }
       @Override public boolean contains(Object object) {
         return set1.contains(object) && set2.contains(object);
       }
       @Override public boolean containsAll(Collection<?> collection) {
         return set1.containsAll(collection)
             && set2.containsAll(collection);
       }
     };
   }

  
Returns an unmodifiable view of the difference of two sets. The returned set contains all elements that are contained by set1 and not contained by set2. set2 may also contain elements not present in set1; these are simply ignored. The iteration order of the returned set matches that of set1.

Results are undefined if set1 and set2 are sets based on different equivalence relations (as HashSet, TreeSet, and the keySet of an IdentityHashMap all are).

 
   public static <E> SetView<E> difference(
       final Set<E> set1final Set<?> set2) {
     checkNotNull(set1"set1");
     checkNotNull(set2"set2");
 
     final Predicate<ObjectnotInSet2 = Predicates.not(Predicates.in(set2));
     return new SetView<E>() {
       @Override public Iterator<E> iterator() {
         return Iterators.filter(set1.iterator(), notInSet2);
       }
       @Override public int size() {
         return Iterators.size(iterator());
       }
       @Override public boolean isEmpty() {
         return set2.containsAll(set1);
       }
       @Override public boolean contains(Object element) {
         return set1.contains(element) && !set2.contains(element);
       }
     };
   }

  
Returns an unmodifiable view of the symmetric difference of two sets. The returned set contains all elements that are contained in either set1 or set2 but not in both. The iteration order of the returned set is undefined.

Results are undefined if set1 and set2 are sets based on different equivalence relations (as HashSet, TreeSet, and the keySet of an IdentityHashMap all are).

Since:
3.0
 
   public static <E> SetView<E> symmetricDifference(
       Set<? extends E> set1Set<? extends E> set2) {
     checkNotNull(set1"set1");
     checkNotNull(set2"set2");
 
     // TODO(kevinb): Replace this with a more efficient implementation
     return difference(union(set1set2), intersection(set1set2));
   }

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

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

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

Many of the filtered set's methods, such as size(), iterate across every element in the underlying set 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 com.google.common.base.Predicate.apply(java.lang.Object). Do not provide a predicate such as Predicates.instanceOf(ArrayList.class), which is inconsistent with equals. (See Iterables.filter(java.lang.Iterable,com.google.common.base.Predicate) for related functionality.)

 
   // TODO(kevinb): how to omit that last sentence when building GWT javadoc?
   public static <E> Set<E> filter(
       Set<E> unfilteredPredicate<? super E> predicate) {
     if (unfiltered instanceof SortedSet) {
       return filter((SortedSet<E>) unfilteredpredicate);
     }
     if (unfiltered instanceof FilteredSet) {
       // Support clear(), removeAll(), and retainAll() when filtering a filtered
       // collection.
       FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
       Predicate<E> combinedPredicate
           = Predicates.<E>and(filtered.predicatepredicate);
       return new FilteredSet<E>(
           (Set<E>) filtered.unfilteredcombinedPredicate);
     }
 
     return new FilteredSet<E>(
         checkNotNull(unfiltered), checkNotNull(predicate));
   }
 
   private static class FilteredSet<E> extends FilteredCollection<E>
       implements Set<E> {
     FilteredSet(Set<E> unfilteredPredicate<? super E> predicate) {
       super(unfilteredpredicate);
     }
 
     @Override public boolean equals(@Nullable Object object) {
       return equalsImpl(thisobject);
     }
 
     @Override public int hashCode() {
       return hashCodeImpl(this);
     }
   }

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

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

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

Many of the filtered set's methods, such as size(), iterate across every element in the underlying set 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 com.google.common.base.Predicate.apply(java.lang.Object). Do not provide a predicate such as Predicates.instanceOf(ArrayList.class), which is inconsistent with equals. (See Iterables.filter(java.lang.Iterable,com.google.common.base.Predicate) for related functionality.)

Since:
11.0
 
   public static <E> SortedSet<E> filter(
       SortedSet<E> unfilteredPredicate<? super E> predicate) {
     return Platform.setsFilterSortedSet(unfilteredpredicate);
   }
 
       SortedSet<E> unfilteredPredicate<? super E> predicate) {
     if (unfiltered instanceof FilteredSet) {
       // Support clear(), removeAll(), and retainAll() when filtering a filtered
       // collection.
       FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
       Predicate<E> combinedPredicate
           = Predicates.<E>and(filtered.predicatepredicate);
       return new FilteredSortedSet<E>(
           (SortedSet<E>) filtered.unfilteredcombinedPredicate);
     }
 
     return new FilteredSortedSet<E>(
         checkNotNull(unfiltered), checkNotNull(predicate));
   }
 
   private static class FilteredSortedSet<E> extends FilteredSet<E>
       implements SortedSet<E> {
 
     FilteredSortedSet(SortedSet<E> unfilteredPredicate<? super E> predicate) {
       super(unfilteredpredicate);
     }
 
     @Override
     public Comparator<? super E> comparator() {
       return ((SortedSet<E>) ).comparator();
     }
 
     @Override
     public SortedSet<E> subSet(E fromElement, E toElement) {
       return new FilteredSortedSet<E>(((SortedSet<E>) ).subSet(fromElementtoElement),
           );
     }
 
     @Override
     public SortedSet<E> headSet(E toElement) {
       return new FilteredSortedSet<E>(((SortedSet<E>) ).headSet(toElement), );
     }
 
     @Override
     public SortedSet<E> tailSet(E fromElement) {
       return new FilteredSortedSet<E>(((SortedSet<E>) ).tailSet(fromElement), );
     }
 
     @Override
     public E first() {
       return iterator().next();
     }
 
     @Override
     public E last() {
       SortedSet<E> sortedUnfiltered = (SortedSet<E>) ;
       while (true) {
         E element = sortedUnfiltered.last();
         if (.apply(element)) {
           return element;
         }
         sortedUnfiltered = sortedUnfiltered.headSet(element);
       }
     }
   }

  
Returns every possible list that can be formed by choosing one element from each of the given sets in order; the "n-ary Cartesian product" of the sets. For example:
   Sets.cartesianProduct(ImmutableList.of(
       ImmutableSet.of(1, 2),
       ImmutableSet.of("A", "B", "C")))

returns a set containing six lists:

  • ImmutableList.of(1, "A")
  • ImmutableList.of(1, "B")
  • ImmutableList.of(1, "C")
  • ImmutableList.of(2, "A")
  • ImmutableList.of(2, "B")
  • ImmutableList.of(2, "C")

The result is guaranteed to be in the "traditional", lexicographical order for Cartesian products that you would get from nesting for loops:

   for (B b0 : sets.get(0)) {
     for (B b1 : sets.get(1)) {
       ...
       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
       // operate on tuple
     
   }}

Note that if any input set is empty, the Cartesian product will also be empty. If no sets at all are provided (an empty list), the resulting Cartesian product has one element, an empty list (counter-intuitive, but mathematically consistent).

Performance notes: while the cartesian product of sets of size m, n, p is a set of size m x n x p, its actual memory consumption is much smaller. When the cartesian set is constructed, the input sets are merely copied. Only as the resulting set is iterated are the individual lists created, and these are not retained after iteration.

Parameters:
sets the sets to choose elements from, in the order that the elements chosen from those sets should appear in the resulting lists
<B> any common base class shared by all axes (often just java.lang.Object)
Returns:
the Cartesian product, as an immutable set containing immutable lists
Throws:
java.lang.NullPointerException if sets, any one of the sets, or any element of a provided set is null
Since:
2.0
 
   public static <B> Set<List<B>> cartesianProduct(
       List<? extends Set<? extends B>> sets) {
     return CartesianSet.create(sets);
   }

  
Returns every possible list that can be formed by choosing one element from each of the given sets in order; the "n-ary Cartesian product" of the sets. For example:
   Sets.cartesianProduct(
       ImmutableSet.of(1, 2),
       ImmutableSet.of("A", "B", "C"))

returns a set containing six lists:

  • ImmutableList.of(1, "A")
  • ImmutableList.of(1, "B")
  • ImmutableList.of(1, "C")
  • ImmutableList.of(2, "A")
  • ImmutableList.of(2, "B")
  • ImmutableList.of(2, "C")

The result is guaranteed to be in the "traditional", lexicographical order for Cartesian products that you would get from nesting for loops:

   for (B b0 : sets.get(0)) {
     for (B b1 : sets.get(1)) {
       ...
       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
       // operate on tuple
     
   }}

Note that if any input set is empty, the Cartesian product will also be empty. If no sets at all are provided (an empty list), the resulting Cartesian product has one element, an empty list (counter-intuitive, but mathematically consistent).

Performance notes: while the cartesian product of sets of size m, n, p is a set of size m x n x p, its actual memory consumption is much smaller. When the cartesian set is constructed, the input sets are merely copied. Only as the resulting set is iterated are the individual lists created, and these are not retained after iteration.

Parameters:
sets the sets to choose elements from, in the order that the elements chosen from those sets should appear in the resulting lists
<B> any common base class shared by all axes (often just java.lang.Object)
Returns:
the Cartesian product, as an immutable set containing immutable lists
Throws:
java.lang.NullPointerException if sets, any one of the sets, or any element of a provided set is null
Since:
2.0
 
   public static <B> Set<List<B>> cartesianProduct(
       Set<? extends B>... sets) {
     return cartesianProduct(Arrays.asList(sets));
   }
 
   private static final class CartesianSet<E>
       extends ForwardingCollection<List<E>> implements Set<List<E>> {
     private transient final ImmutableList<ImmutableSet<E>> axes;
     private transient final CartesianList<E> delegate;
 
     static <E> Set<List<E>> create(List<? extends Set<? extends E>> sets) {
       ImmutableList.Builder<ImmutableSet<E>> axesBuilder =
           new ImmutableList.Builder<ImmutableSet<E>>(sets.size());
       for (Set<? extends E> set : sets) {
         ImmutableSet<E> copy = ImmutableSet.copyOf(set);
         if (copy.isEmpty()) {
           return ImmutableSet.of();
         }
         axesBuilder.add(copy);
       }
       final ImmutableList<ImmutableSet<E>> axes = axesBuilder.build();
       ImmutableList<List<E>> listAxes = new ImmutableList<List<E>>() {
 
         @Override
         public int size() {
           return axes.size();
         }
 
         @Override
         public List<E> get(int index) {
           return axes.get(index).asList();
         }
 
         @Override
         boolean isPartialView() {
           return true;
         }
       };
       return new CartesianSet<E>(axesnew CartesianList<E>(listAxes));
     }
 
     private CartesianSet(
         ImmutableList<ImmutableSet<E>> axesCartesianList<E> delegate) {
       this. = axes;
       this. = delegate;
     }
    @Override
    protected Collection<List<E>> delegate() {
      return ;
    }
    @Override public boolean equals(@Nullable Object object) {
      // Warning: this is broken if size() == 0, so it is critical that we
      // substitute an empty ImmutableSet to the user in place of this
      if (object instanceof CartesianSet) {
        CartesianSet<?> that = (CartesianSet<?>) object;
        return this..equals(that.axes);
      }
      return super.equals(object);
    }
    @Override
    public int hashCode() {
      // Warning: this is broken if size() == 0, so it is critical that we
      // substitute an empty ImmutableSet to the user in place of this
      // It's a weird formula, but tests prove it works.
      int adjust = size() - 1;
      for (int i = 0; i < .size(); i++) {
        adjust *= 31;
        adjust = ~~adjust;
        // in GWT, we have to deal with integer overflow carefully
      }
      int hash = 1;
      for (Set<E> axis : ) {
        hash = 31 * hash + (size() / axis.size() * axis.hashCode());
        hash = ~~hash;
      }
      hash += adjust;
      return ~~hash;
    }
  }

  
Returns the set of all possible subsets of set. For example, powerSet(ImmutableSet.of(1, 2)) returns the set {{, {1}, {2}, {1, 2}}}.

Elements appear in these subsets in the same iteration order as they appeared in the input set. The order in which these subsets appear in the outer set is undefined. Note that the power set of the empty set is not the empty set, but a one-element set containing the empty set.

The returned set and its constituent sets use equals to decide whether two elements are identical, even if the input set uses a different concept of equivalence.

Performance notes: while the power set of a set with size n is of size 2^n, its memory usage is only O(n). When the power set is constructed, the input set is merely copied. Only as the power set is iterated are the individual subsets created, and these subsets themselves occupy only a small constant amount of memory.

Parameters:
set the set of elements to construct a power set from
Returns:
the power set, as an immutable set of immutable sets
Throws:
java.lang.IllegalArgumentException if set has more than 30 unique elements (causing the power set size to exceed the int range)
java.lang.NullPointerException if set is or contains null
Since:
4.0
See also:
Power set article at Wikipedia
  @GwtCompatible(serializable = false)
  public static <E> Set<Set<E>> powerSet(Set<E> set) {
    return new PowerSet<E>(set);
  }
  private static final class SubSet<E> extends AbstractSet<E> {
    private final ImmutableMap<E, IntegerinputSet;
    private final int mask;
    SubSet(ImmutableMap<E, IntegerinputSetint mask) {
      this. = inputSet;
      this. = mask;
    }
    @Override
    public Iterator<E> iterator() {
      return new UnmodifiableIterator<E>() {
        final ImmutableList<E> elements = .keySet().asList();
        int remainingSetBits = ;
        @Override
        public boolean hasNext() {
          return  != 0;
        }
        @Override
        public E next() {
          int index = Integer.numberOfTrailingZeros();
          if (index == 32) {
            throw new NoSuchElementException();
          }
           &= ~(1 << index);
          return .get(index);
        }
      };
    }
    @Override
    public int size() {
      return Integer.bitCount();
    }
    @Override
    public boolean contains(@Nullable Object o) {
      Integer index = .get(o);
      return index != null && ( & (1 << index)) != 0;
    }
  }
  private static final class PowerSet<E> extends AbstractSet<Set<E>> {
    final ImmutableMap<E, IntegerinputSet;
    PowerSet(Set<E> input) {
      ImmutableMap.Builder<E, Integerbuilder = ImmutableMap.builder();
      int i = 0;
      for (E e : checkNotNull(input)) {
        builder.put(ei++);
      }
      this. = builder.build();
      checkArgument(.size() <= 30,
          "Too many elements to create power set: %s > 30".size());
    }
    @Override public int size() {
      return 1 << .size();
    }
    @Override public boolean isEmpty() {
      return false;
    }
    @Override public Iterator<Set<E>> iterator() {
      return new AbstractIndexedListIterator<Set<E>>(size()) {
        @Override protected Set<E> get(final int setBits) {
          return new SubSet<E>(setBits);
        }
      };
    }
    @Override public boolean contains(@Nullable Object obj) {
      if (obj instanceof Set) {
        Set<?> set = (Set<?>) obj;
        return .keySet().containsAll(set);
      }
      return false;
    }
    @Override public boolean equals(@Nullable Object obj) {
      if (obj instanceof PowerSet) {
        PowerSet<?> that = (PowerSet<?>) obj;
        return .equals(that.inputSet);
      }
      return super.equals(obj);
    }
    @Override public int hashCode() {
      /*
       * The sum of the sums of the hash codes in each subset is just the sum of
       * each input element's hash code times the number of sets that element
       * appears in. Each element appears in exactly half of the 2^n sets, so:
       */
      return .keySet().hashCode() << (.size() - 1);
    }
    @Override public String toString() {
      return "powerSet(" +  + ")";
    }
  }

  
An implementation for java.util.Set.hashCode().
  static int hashCodeImpl(Set<?> s) {
    int hashCode = 0;
    for (Object o : s) {
      hashCode += o != null ? o.hashCode() : 0;
      hashCode = ~~hashCode;
      // Needed to deal with unusual integer overflow in GWT.
    }
    return hashCode;
  }

  
  static boolean equalsImpl(Set<?> s, @Nullable Object object) {
    if (s == object) {
      return true;
    }
    if (object instanceof Set) {
      Set<?> o = (Set<?>) object;
      try {
        return s.size() == o.size() && s.containsAll(o);
      } catch (NullPointerException ignored) {
        return false;
      } catch (ClassCastException ignored) {
        return false;
      }
    }
    return false;
  }

  
Remove each element in an iterable from a set.
  static boolean removeAllImpl(Set<?> setIterator<?> iterator) {
    boolean changed = false;
    while (iterator.hasNext()) {
      changed |= set.remove(iterator.next());
    }
    return changed;
  }
  static boolean removeAllImpl(Set<?> setCollection<?> collection) {
    checkNotNull(collection); // for GWT
    if (collection instanceof Multiset) {
      collection = ((Multiset<?>) collection).elementSet();
    }
    /*
     * AbstractSet.removeAll(List) has quadratic behavior if the list size
     * is just less than the set's size.  We augment the test by
     * assuming that sets have fast contains() performance, and other
     * collections don't.  See
     * http://code.google.com/p/guava-libraries/issues/detail?id=1013
     */
    if (collection instanceof Set && collection.size() > set.size()) {
      return Iterators.removeAll(set.iterator(), collection);
    } else {
      return removeAllImpl(setcollection.iterator());
    }
  }
New to GrepCode? Check out our FAQ X