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.List;
 import java.util.Set;
 
Provides static utility methods for creating and working with Multiset instances.

See the Guava User Guide article on Multisets.

Author(s):
Kevin Bourrillion
Mike Bostock
Louis Wasserman
Since:
2.0 (imported from Google Collections Library)
 
 public final class Multisets {
   private Multisets() {}

  
Returns an unmodifiable view of the specified multiset. Query operations on the returned multiset "read through" to the specified multiset, and attempts to modify the returned multiset result in an java.lang.UnsupportedOperationException.

The returned multiset will be serializable if the specified multiset is serializable.

Parameters:
multiset the multiset for which an unmodifiable view is to be generated
Returns:
an unmodifiable view of the multiset
 
   public static <E> Multiset<E> unmodifiableMultiset(
       Multiset<? extends E> multiset) {
     if (multiset instanceof UnmodifiableMultiset ||
         multiset instanceof ImmutableMultiset) {
       // Since it's unmodifiable, the covariant cast is safe
       @SuppressWarnings("unchecked")
       Multiset<E> result = (Multiset<E>) multiset;
       return result;
     }
     return new UnmodifiableMultiset<E>(checkNotNull(multiset));
   }

  
Simply returns its argument.

Deprecated:
no need to use this
Since:
10.0
 
   @Deprecated public static <E> Multiset<E> unmodifiableMultiset(
       ImmutableMultiset<E> multiset) {
     return checkNotNull(multiset);
   }
 
   static class UnmodifiableMultiset<E>
       extends ForwardingMultiset<E> implements Serializable {
     final Multiset<? extends E> delegate;
 
     UnmodifiableMultiset(Multiset<? extends E> delegate) {
       this. = delegate;
    }
    @SuppressWarnings("unchecked")
    @Override protected Multiset<E> delegate() {
      // This is safe because all non-covariant methods are overriden
      return (Multiset<E>) ;
    }
    transient Set<E> elementSet;
    Set<E> createElementSet() {
      return Collections.<E>unmodifiableSet(.elementSet());
    }
    @Override
    public Set<E> elementSet() {
      Set<E> es = ;
      return (es == null) ?  = createElementSet() : es;
    }
    transient Set<Multiset.Entry<E>> entrySet;
    @SuppressWarnings("unchecked")
    @Override public Set<Multiset.Entry<E>> entrySet() {
      Set<Multiset.Entry<E>> es = ;
      return (es == null)
          // Safe because the returned set is made unmodifiable and Entry
          // itself is readonly
          ?  = (Set) Collections.unmodifiableSet(.entrySet())
          : es;
    }
    @SuppressWarnings("unchecked")
    @Override public Iterator<E> iterator() {
      // Safe because the returned Iterator is made unmodifiable
      return (Iterator<E>) Iterators.unmodifiableIterator(.iterator());
    }
    @Override public boolean add(E element) {
      throw new UnsupportedOperationException();
    }
    @Override public int add(E elementint occurences) {
      throw new UnsupportedOperationException();
    }
    @Override public boolean addAll(Collection<? extends E> elementsToAdd) {
      throw new UnsupportedOperationException();
    }
    @Override public boolean remove(Object element) {
      throw new UnsupportedOperationException();
    }
    @Override public int remove(Object elementint occurrences) {
      throw new UnsupportedOperationException();
    }
    @Override public boolean removeAll(Collection<?> elementsToRemove) {
      throw new UnsupportedOperationException();
    }
    @Override public boolean retainAll(Collection<?> elementsToRetain) {
      throw new UnsupportedOperationException();
    }
    @Override public void clear() {
      throw new UnsupportedOperationException();
    }
    @Override public int setCount(E elementint count) {
      throw new UnsupportedOperationException();
    }
    @Override public boolean setCount(E elementint oldCountint newCount) {
      throw new UnsupportedOperationException();
    }
    private static final long serialVersionUID = 0;
  }

  
Returns an unmodifiable view of the specified sorted multiset. Query operations on the returned multiset "read through" to the specified multiset, and attempts to modify the returned multiset result in an java.lang.UnsupportedOperationException.

The returned multiset will be serializable if the specified multiset is serializable.

Parameters:
sortedMultiset the sorted multiset for which an unmodifiable view is to be generated
Returns:
an unmodifiable view of the multiset
Since:
11.0
  @Beta
  public static <E> SortedMultiset<E> unmodifiableSortedMultiset(
      SortedMultiset<E> sortedMultiset) {
    return new UnmodifiableSortedMultiset<E>(checkNotNull(sortedMultiset));
  }
  private static final class UnmodifiableSortedMultiset<E>
      extends UnmodifiableMultiset<E> implements SortedMultiset<E> {
    private UnmodifiableSortedMultiset(SortedMultiset<E> delegate) {
      super(delegate);
    }
    @Override
    protected SortedMultiset<E> delegate() {
      return (SortedMultiset<E>) super.delegate();
    }
    @Override
    public Comparator<? super E> comparator() {
      return delegate().comparator();
    }
    @Override
      return Collections.unmodifiableSortedSet(delegate().elementSet());
    }
    @Override
    public SortedSet<E> elementSet() {
      return (SortedSet<E>) super.elementSet();
    }
    private transient UnmodifiableSortedMultiset<E> descendingMultiset;
    @Override
    public SortedMultiset<E> descendingMultiset() {
      if (result == null) {
        result = new UnmodifiableSortedMultiset<E>(
            delegate().descendingMultiset());
        result.descendingMultiset = this;
        return  = result;
      }
      return result;
    }
    @Override
    public Entry<E> firstEntry() {
      return delegate().firstEntry();
    }
    @Override
    public Entry<E> lastEntry() {
      return delegate().lastEntry();
    }
    @Override
    public Entry<E> pollFirstEntry() {
      throw new UnsupportedOperationException();
    }
    @Override
    public Entry<E> pollLastEntry() {
      throw new UnsupportedOperationException();
    }
    @Override
    public SortedMultiset<E> headMultiset(E upperBoundBoundType boundType) {
      return unmodifiableSortedMultiset(
          delegate().headMultiset(upperBoundboundType));
    }
    @Override
    public SortedMultiset<E> subMultiset(
        E lowerBoundBoundType lowerBoundType,
        E upperBoundBoundType upperBoundType) {
          lowerBoundlowerBoundTypeupperBoundupperBoundType));
    }
    @Override
    public SortedMultiset<E> tailMultiset(E lowerBoundBoundType boundType) {
      return unmodifiableSortedMultiset(
          delegate().tailMultiset(lowerBoundboundType));
    }
    private static final long serialVersionUID = 0;
  }

  
Returns an immutable multiset entry with the specified element and count. The entry will be serializable if e is.

Parameters:
e the element to be associated with the returned entry
n the count to be associated with the returned entry
Throws:
java.lang.IllegalArgumentException if n is negative
  public static <E> Multiset.Entry<E> immutableEntry(@Nullable E eint n) {
    return new ImmutableEntry<E>(en);
  }
  static final class ImmutableEntry<E> extends AbstractEntry<E> implements
      Serializable {
    @Nullable final E element;
    final int count;
    ImmutableEntry(@Nullable E elementint count) {
      this. = element;
      this. = count;
      checkArgument(count >= 0);
    }
    @Override
    @Nullable public E getElement() {
      return ;
    }
    @Override
    public int getCount() {
      return ;
    }
    private static final long serialVersionUID = 0;
  }

  
Returns a multiset view of the specified set. The multiset is backed by the set, so changes to the set are reflected in the multiset, and vice versa. If the set is modified while an iteration over the multiset is in progress (except through the iterator's own remove operation) the results of the iteration are undefined.

The multiset supports element removal, which removes the corresponding element from the set. It does not support the add or addAll operations, nor does it support the use of setCount to add elements.

The returned multiset will be serializable if the specified set is serializable. The multiset is threadsafe if the set is threadsafe.

Parameters:
set the backing set for the returned multiset view
  static <E> Multiset<E> forSet(Set<E> set) {
    return new SetMultiset<E>(set);
  }

  
  private static class SetMultiset<E> extends ForwardingCollection<E>
      implements Multiset<E>, Serializable {
    final Set<E> delegate;
    SetMultiset(Set<E> set) {
       = checkNotNull(set);
    }
    @Override protected Set<E> delegate() {
      return ;
    }
    @Override
    public int count(Object element) {
      return .contains(element) ? 1 : 0;
    }
    @Override
    public int add(E elementint occurrences) {
      throw new UnsupportedOperationException();
    }
    @Override
    public int remove(Object elementint occurrences) {
      if (occurrences == 0) {
        return count(element);
      }
      checkArgument(occurrences > 0);
      return .remove(element) ? 1 : 0;
    }
    transient Set<E> elementSet;
    @Override
    public Set<E> elementSet() {
      Set<E> es = ;
      return (es == null) ?  = new ElementSet() : es;
    }
    transient Set<Entry<E>> entrySet;
    @Override public Set<Entry<E>> entrySet() {
      Set<Entry<E>> es = ;
      if (es == null) {
        es =  = new EntrySet<E>() {
          @Override Multiset<E> multiset() {
            return SetMultiset.this;
          }
          @Override public Iterator<Entry<E>> iterator() {
            return new TransformedIterator<E, Entry<E>>(.iterator()) {
              @Override
              Entry<E> transform(E e) {
                return Multisets.immutableEntry(e, 1);
              }
            };
          }
          @Override public int size() {
            return .size();
          }
        };
      }
      return es;
    }
    @Override public boolean add(E o) {
      throw new UnsupportedOperationException();
    }
    @Override public boolean addAll(Collection<? extends E> c) {
      throw new UnsupportedOperationException();
    }
    @Override
    public int setCount(E elementint count) {
      checkNonnegative(count"count");
      if (count == count(element)) {
        return count;
      } else if (count == 0) {
        remove(element);
        return 1;
      } else {
        throw new UnsupportedOperationException();
      }
    }
    @Override
    public boolean setCount(E elementint oldCountint newCount) {
      return setCountImpl(thiselementoldCountnewCount);
    }
    @Override public boolean equals(@Nullable Object object) {
      if (object instanceof Multiset) {
        Multiset<?> that = (Multiset<?>) object;
        return this.size() == that.size() && .equals(that.elementSet());
      }
      return false;
    }
    @Override public int hashCode() {
      int sum = 0;
      for (E e : this) {
        sum += ((e == null) ? 0 : e.hashCode()) ^ 1;
      }
      return sum;
    }

    
    class ElementSet extends ForwardingSet<E> {
      @Override protected Set<E> delegate() {
        return ;
      }
      @Override public boolean add(E o) {
        throw new UnsupportedOperationException();
      }
      @Override public boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException();
      }
    }
    private static final long serialVersionUID = 0;
  }

  
Returns the expected number of distinct elements given the specified elements. The number of distinct elements is only computed if elements is an instance of Multiset; otherwise the default value of 11 is returned.
  static int inferDistinctElements(Iterable<?> elements) {
    if (elements instanceof Multiset) {
      return ((Multiset<?>) elements).elementSet().size();
    }
    return 11; // initial capacity will be rounded up to 16
  }

  
Returns an unmodifiable view of the intersection of two multisets. An element's count in the multiset is the smaller of its counts in the two backing multisets. The iteration order of the returned multiset matches the element set of multiset1, with repeated occurrences of the same element appearing consecutively.

Results are undefined if multiset1 and multiset2 are based on different equivalence relations (as HashMultiset and TreeMultiset are).

Since:
2.0
  public static <E> Multiset<E> intersection(
      final Multiset<E> multiset1final Multiset<?> multiset2) {
    checkNotNull(multiset1);
    checkNotNull(multiset2);
    return new AbstractMultiset<E>() {
      @Override
      public int count(Object element) {
        int count1 = multiset1.count(element);
        return (count1 == 0) ? 0 : Math.min(count1multiset2.count(element));
      }
      @Override
      Set<E> createElementSet() {
        return Sets.intersection(
            multiset1.elementSet(), multiset2.elementSet());
      }
      @Override
      Iterator<Entry<E>> entryIterator() {
        final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
        return new AbstractIterator<Entry<E>>() {
          @Override
          protected Entry<E> computeNext() {
            while (iterator1.hasNext()) {
              Entry<E> entry1 = iterator1.next();
              E element = entry1.getElement();
              int count = Math.min(entry1.getCount(), multiset2.count(element));
              if (count > 0) {
                return Multisets.immutableEntry(elementcount);
              }
            }
            return endOfData();
          }
        };
      }
      @Override
      int distinctElements() {
        return elementSet().size();
      }
    };
  }

  
Returns true if subMultiset.count(o) <= superMultiset.count(o) for all o.

Since:
10.0
  @Beta
  public static boolean containsOccurrences(
      Multiset<?> superMultisetMultiset<?> subMultiset) {
    checkNotNull(superMultiset);
    checkNotNull(subMultiset);
    for (Entry<?> entry : subMultiset.entrySet()) {
      int superCount = superMultiset.count(entry.getElement());
      if (superCount < entry.getCount()) {
        return false;
      }
    }
    return true;
  }

  
Modifies multisetToModify so that its count for an element e is at most multisetToRetain.count(e).

To be precise, multisetToModify.count(e) is set to Math.min(multisetToModify.count(e), multisetToRetain.count(e)). This is similar to intersection (multisetToModify, multisetToRetain), but mutates multisetToModify instead of returning a view.

In contrast, multisetToModify.retainAll(multisetToRetain) keeps all occurrences of elements that appear at all in multisetToRetain, and deletes all occurrences of all other elements.

Returns:
true if multisetToModify was changed as a result of this operation
Since:
10.0
  @Beta public static boolean retainOccurrences(Multiset<?> multisetToModify,
      Multiset<?> multisetToRetain) {
    return retainOccurrencesImpl(multisetToModifymultisetToRetain);
  }

  
Delegate implementation which cares about the element type.
  private static <E> boolean retainOccurrencesImpl(
      Multiset<E> multisetToModifyMultiset<?> occurrencesToRetain) {
    checkNotNull(multisetToModify);
    checkNotNull(occurrencesToRetain);
    // Avoiding ConcurrentModificationExceptions is tricky.
    Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
    boolean changed = false;
    while (entryIterator.hasNext()) {
      Entry<E> entry = entryIterator.next();
      int retainCount = occurrencesToRetain.count(entry.getElement());
      if (retainCount == 0) {
        entryIterator.remove();
        changed = true;
      } else if (retainCount < entry.getCount()) {
        multisetToModify.setCount(entry.getElement(), retainCount);
        changed = true;
      }
    }
    return changed;
  }

  
For each occurrence of an element e in occurrencesToRemove, removes one occurrence of e in multisetToModify.

Equivalently, this method modifies multisetToModify so that multisetToModify.count(e) is set to Math.max(0, multisetToModify.count(e) - occurrencesToRemove.count(e)).

This is not the same as multisetToModify. removeAll(occurrencesToRemove), which removes all occurrences of elements that appear in occurrencesToRemove. However, this operation is equivalent to, albeit more efficient than, the following:

   for (E e : occurrencesToRemove) {
     multisetToModify.remove(e);
   }

Returns:
true if multisetToModify was changed as a result of this operation
Since:
10.0
  @Beta public static boolean removeOccurrences(
      Multiset<?> multisetToModifyMultiset<?> occurrencesToRemove) {
    return removeOccurrencesImpl(multisetToModifyoccurrencesToRemove);
  }

  
Delegate that cares about the element types in occurrencesToRemove.
  private static <E> boolean removeOccurrencesImpl(
      Multiset<E> multisetToModifyMultiset<?> occurrencesToRemove) {
    // TODO(user): generalize to removing an Iterable, perhaps
    checkNotNull(multisetToModify);
    checkNotNull(occurrencesToRemove);
    boolean changed = false;
    Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
    while (entryIterator.hasNext()) {
      Entry<E> entry = entryIterator.next();
      int removeCount = occurrencesToRemove.count(entry.getElement());
      if (removeCount >= entry.getCount()) {
        entryIterator.remove();
        changed = true;
      } else if (removeCount > 0) {
        multisetToModify.remove(entry.getElement(), removeCount);
        changed = true;
      }
    }
    return changed;
  }

  
Implementation of the equals, hashCode, and toString methods of Multiset.Entry.
  abstract static class AbstractEntry<E> implements Multiset.Entry<E> {
    
Indicates whether an object equals this entry, following the behavior specified in Multiset.Entry.equals(java.lang.Object).
    @Override public boolean equals(@Nullable Object object) {
      if (object instanceof Multiset.Entry) {
        Multiset.Entry<?> that = (Multiset.Entry<?>) object;
        return this.getCount() == that.getCount()
            && Objects.equal(this.getElement(), that.getElement());
      }
      return false;
    }

    
Return this entry's hash code, following the behavior specified in Multiset.Entry.hashCode().
    @Override public int hashCode() {
      E e = getElement();
      return ((e == null) ? 0 : e.hashCode()) ^ getCount();
    }

    
Returns a string representation of this multiset entry. The string representation consists of the associated element if the associated count is one, and otherwise the associated element followed by the characters " x " (space, x and space) followed by the count. Elements and counts are converted to strings as by String.valueOf.
    @Override public String toString() {
      String text = String.valueOf(getElement());
      int n = getCount();
      return (n == 1) ? text : (text + " x " + n);
    }
  }

  
An implementation of Multiset.equals(java.lang.Object).
  static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) {
    if (object == multiset) {
      return true;
    }
    if (object instanceof Multiset) {
      Multiset<?> that = (Multiset<?>) object;
      /*
       * We can't simply check whether the entry sets are equal, since that
       * approach fails when a TreeMultiset has a comparator that returns 0
       * when passed unequal elements.
       */
      if (multiset.size() != that.size()
          || multiset.entrySet().size() != that.entrySet().size()) {
        return false;
      }
      for (Entry<?> entry : that.entrySet()) {
        if (multiset.count(entry.getElement()) != entry.getCount()) {
          return false;
        }
      }
      return true;
    }
    return false;
  }

  
  static <E> boolean addAllImpl(
      Multiset<E> selfCollection<? extends E> elements) {
    if (elements.isEmpty()) {
      return false;
    }
    if (elements instanceof Multiset) {
      Multiset<? extends E> that = cast(elements);
      for (Entry<? extends E> entry : that.entrySet()) {
        self.add(entry.getElement(), entry.getCount());
      }
    } else {
      Iterators.addAll(selfelements.iterator());
    }
    return true;
  }

  
  static boolean removeAllImpl(
      Multiset<?> selfCollection<?> elementsToRemove) {
    Collection<?> collection = (elementsToRemove instanceof Multiset)
        ? ((Multiset<?>) elementsToRemove).elementSet() : elementsToRemove;
    return self.elementSet().removeAll(collection);
  }

  
  static boolean retainAllImpl(
      Multiset<?> selfCollection<?> elementsToRetain) {
    Collection<?> collection = (elementsToRetain instanceof Multiset)
        ? ((Multiset<?>) elementsToRetain).elementSet() : elementsToRetain;
    return self.elementSet().retainAll(collection);
  }

  
  static <E> int setCountImpl(Multiset<E> self, E elementint count) {
    checkNonnegative(count"count");
    int oldCount = self.count(element);
    int delta = count - oldCount;
    if (delta > 0) {
      self.add(elementdelta);
    } else if (delta < 0) {
      self.remove(element, -delta);
    }
    return oldCount;
  }

  
  static <E> boolean setCountImpl(
      Multiset<E> self, E elementint oldCountint newCount) {
    checkNonnegative(oldCount"oldCount");
    checkNonnegative(newCount"newCount");
    if (self.count(element) == oldCount) {
      self.setCount(elementnewCount);
      return true;
    } else {
      return false;
    }
  }
  static abstract class ElementSet<E> extends AbstractSet<E> {
    abstract Multiset<E> multiset();
    @Override public void clear() {
      multiset().clear();
    }
    @Override public boolean contains(Object o) {
      return multiset().contains(o);
    }
    @Override public boolean containsAll(Collection<?> c) {
      return multiset().containsAll(c);
    }
    @Override public boolean isEmpty() {
      return multiset().isEmpty();
    }
    @Override public Iterator<E> iterator() {
      return new TransformedIterator<Entry<E>, E>(multiset().entrySet().iterator()) {
        @Override
        E transform(Entry<E> entry) {
          return entry.getElement();
        }
      };
    }
    @Override
    public boolean remove(Object o) {
      int count = multiset().count(o);
      if (count > 0) {
        multiset().remove(ocount);
        return true;
      }
      return false;
    }
    @Override public int size() {
      return multiset().entrySet().size();
    }
  }
  static abstract class EntrySet<E> extends AbstractSet<Entry<E>>{
    abstract Multiset<E> multiset();
    @Override public boolean contains(@Nullable Object o) {
      if (o instanceof Entry) {
        @SuppressWarnings("cast")
        Entry<?> entry = (Entry<?>) o;
        if (entry.getCount() <= 0) {
          return false;
        }
        int count = multiset().count(entry.getElement());
        return count == entry.getCount();
      }
      return false;
    }
    @SuppressWarnings("cast")
    @Override public boolean remove(Object o) {
      return contains(o)
          && multiset().elementSet().remove(((Entry<?>) o).getElement());
    }
    @Override public void clear() {
      multiset().clear();
    }
  }

  
An implementation of Multiset.iterator().
  static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) {
    return new MultisetIteratorImpl<E>(
        multisetmultiset.entrySet().iterator());
  }
  static final class MultisetIteratorImpl<E> implements Iterator<E> {
    private final Multiset<E> multiset;
    private final Iterator<Entry<E>> entryIterator;
    private Entry<E> currentEntry;
    
Count of subsequent elements equal to current element
    private int laterCount;
    
Count of all elements equal to current element
    private int totalCount;
    private boolean canRemove;
        Multiset<E> multisetIterator<Entry<E>> entryIterator) {
      this. = multiset;
      this. = entryIterator;
    }
    @Override
    public boolean hasNext() {
      return  > 0 || .hasNext();
    }
    @Override
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      if ( == 0) {
         = .next();
         =  = .getCount();
      }
      --;
       = true;
      return .getElement();
    }
    @Override
    public void remove() {
      Iterators.checkRemove();
      if ( == 1) {
        .remove();
      } else {
      }
      --;
       = false;
    }
  }

  
An implementation of java.util.Collection.size().
  static int sizeImpl(Multiset<?> multiset) {
    long size = 0;
    for (Entry<?> entry : multiset.entrySet()) {
      size += entry.getCount();
    }
    return Ints.saturatedCast(size);
  }
  static void checkNonnegative(int countString name) {
    checkArgument(count >= 0, "%s cannot be negative: %s"namecount);
  }

  
Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
  static <T> Multiset<T> cast(Iterable<T> iterable) {
    return (Multiset<T>) iterable;
  }
  private static final Ordering<Entry<?>> DECREASING_COUNT_ORDERING = new Ordering<Entry<?>>() {
    @Override
    public int compare(Entry<?> entry1Entry<?> entry2) {
      return Ints.compare(entry2.getCount(), entry1.getCount());
    }
  };

  
Returns a copy of multiset as an ImmutableMultiset whose iteration order is highest count first, with ties broken by the iteration order of the original multiset.

Since:
11.0
  @Beta
  public static <E> ImmutableMultiset<E> copyHighestCountFirst(Multiset<E> multiset) {
    List<Entry<E>> sortedEntries =
    return ImmutableMultiset.copyFromEntries(sortedEntries);
  }