001/*
002 * Copyright (C) 2007 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.base.Preconditions.checkState;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.base.Objects;
025import com.google.common.collect.Multiset.Entry;
026import com.google.common.primitives.Ints;
027
028import java.io.Serializable;
029import java.util.AbstractSet;
030import java.util.Collection;
031import java.util.Collections;
032import java.util.Iterator;
033import java.util.NoSuchElementException;
034import java.util.Set;
035
036import javax.annotation.Nullable;
037
038/**
039 * Provides static utility methods for creating and working with {@link
040 * Multiset} instances.
041 *
042 * @author Kevin Bourrillion
043 * @author Mike Bostock
044 * @author Louis Wasserman
045 * @since 2 (imported from Google Collections Library)
046 */
047@GwtCompatible
048public final class Multisets {
049  private Multisets() {}
050
051  /**
052   * Returns an unmodifiable view of the specified multiset. Query operations on
053   * the returned multiset "read through" to the specified multiset, and
054   * attempts to modify the returned multiset result in an
055   * {@link UnsupportedOperationException}.
056   *
057   * <p>The returned multiset will be serializable if the specified multiset is
058   * serializable.
059   *
060   * @param multiset the multiset for which an unmodifiable view is to be
061   *     generated
062   * @return an unmodifiable view of the multiset
063   */
064  public static <E> Multiset<E> unmodifiableMultiset(
065      Multiset<? extends E> multiset) {
066    return new UnmodifiableMultiset<E>(checkNotNull(multiset));
067  }
068
069  private static class UnmodifiableMultiset<E>
070      extends ForwardingMultiset<E> implements Serializable {
071    final Multiset<? extends E> delegate;
072
073    UnmodifiableMultiset(Multiset<? extends E> delegate) {
074      this.delegate = delegate;
075    }
076
077    @SuppressWarnings("unchecked")
078    @Override protected Multiset<E> delegate() {
079      // This is safe because all non-covariant methods are overriden
080      return (Multiset<E>) delegate;
081    }
082
083    transient Set<E> elementSet;
084
085    @Override public Set<E> elementSet() {
086      Set<E> es = elementSet;
087      return (es == null)
088          ? elementSet = Collections.<E>unmodifiableSet(delegate.elementSet())
089          : es;
090    }
091
092    transient Set<Multiset.Entry<E>> entrySet;
093
094    @SuppressWarnings("unchecked")
095    @Override public Set<Multiset.Entry<E>> entrySet() {
096      Set<Multiset.Entry<E>> es = entrySet;
097      return (es == null)
098          // Safe because the returned set is made unmodifiable and Entry
099          // itself is readonly
100          ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
101          : es;
102    }
103
104    @SuppressWarnings("unchecked")
105    @Override public Iterator<E> iterator() {
106      // Safe because the returned Iterator is made unmodifiable
107      return (Iterator<E>) Iterators.unmodifiableIterator(delegate.iterator());
108    }
109
110    @Override public boolean add(E element) {
111      throw new UnsupportedOperationException();
112    }
113
114    @Override public int add(E element, int occurences) {
115      throw new UnsupportedOperationException();
116    }
117
118    @Override public boolean addAll(Collection<? extends E> elementsToAdd) {
119      throw new UnsupportedOperationException();
120    }
121
122    @Override public boolean remove(Object element) {
123      throw new UnsupportedOperationException();
124    }
125
126    @Override public int remove(Object element, int occurrences) {
127      throw new UnsupportedOperationException();
128    }
129
130    @Override public boolean removeAll(Collection<?> elementsToRemove) {
131      throw new UnsupportedOperationException();
132    }
133
134    @Override public boolean retainAll(Collection<?> elementsToRetain) {
135      throw new UnsupportedOperationException();
136    }
137
138    @Override public void clear() {
139      throw new UnsupportedOperationException();
140    }
141
142    @Override public int setCount(E element, int count) {
143      throw new UnsupportedOperationException();
144    }
145
146    @Override public boolean setCount(E element, int oldCount, int newCount) {
147      throw new UnsupportedOperationException();
148    }
149
150    private static final long serialVersionUID = 0;
151  }
152
153  /**
154   * Returns an immutable multiset entry with the specified element and count.
155   *
156   * @param e the element to be associated with the returned entry
157   * @param n the count to be associated with the returned entry
158   * @throws IllegalArgumentException if {@code n} is negative
159   */
160  public static <E> Multiset.Entry<E> immutableEntry(
161      @Nullable final E e, final int n) {
162    checkArgument(n >= 0);
163    return new AbstractEntry<E>() {
164      @Override
165      public E getElement() {
166        return e;
167      }
168      @Override
169      public int getCount() {
170        return n;
171      }
172    };
173  }
174
175  /**
176   * Returns a multiset view of the specified set. The multiset is backed by the
177   * set, so changes to the set are reflected in the multiset, and vice versa.
178   * If the set is modified while an iteration over the multiset is in progress
179   * (except through the iterator's own {@code remove} operation) the results of
180   * the iteration are undefined.
181   *
182   * <p>The multiset supports element removal, which removes the corresponding
183   * element from the set. It does not support the {@code add} or {@code addAll}
184   * operations, nor does it support the use of {@code setCount} to add
185   * elements.
186   *
187   * <p>The returned multiset will be serializable if the specified set is
188   * serializable. The multiset is threadsafe if the set is threadsafe.
189   *
190   * @param set the backing set for the returned multiset view
191   */
192  static <E> Multiset<E> forSet(Set<E> set) {
193    return new SetMultiset<E>(set);
194  }
195
196  /** @see Multisets#forSet */
197  private static class SetMultiset<E> extends ForwardingCollection<E>
198      implements Multiset<E>, Serializable {
199    final Set<E> delegate;
200
201    SetMultiset(Set<E> set) {
202      delegate = checkNotNull(set);
203    }
204
205    @Override protected Set<E> delegate() {
206      return delegate;
207    }
208
209    @Override
210    public int count(Object element) {
211      return delegate.contains(element) ? 1 : 0;
212    }
213
214    @Override
215    public int add(E element, int occurrences) {
216      throw new UnsupportedOperationException();
217    }
218
219    @Override
220    public int remove(Object element, int occurrences) {
221      if (occurrences == 0) {
222        return count(element);
223      }
224      checkArgument(occurrences > 0);
225      return delegate.remove(element) ? 1 : 0;
226    }
227
228    transient Set<E> elementSet;
229
230    @Override
231    public Set<E> elementSet() {
232      Set<E> es = elementSet;
233      return (es == null) ? elementSet = new ElementSet() : es;
234    }
235
236    transient Set<Entry<E>> entrySet;
237
238    @Override
239    public Set<Entry<E>> entrySet() {
240      Set<Entry<E>> es = entrySet;
241      return (es == null) ? entrySet = new EntrySet() : es;
242    }
243
244    @Override public boolean add(E o) {
245      throw new UnsupportedOperationException();
246    }
247
248    @Override public boolean addAll(Collection<? extends E> c) {
249      throw new UnsupportedOperationException();
250    }
251
252    @Override
253    public int setCount(E element, int count) {
254      checkNonnegative(count, "count");
255
256      if (count == count(element)) {
257        return count;
258      } else if (count == 0) {
259        remove(element);
260        return 1;
261      } else {
262        throw new UnsupportedOperationException();
263      }
264    }
265
266    @Override
267    public boolean setCount(E element, int oldCount, int newCount) {
268      return setCountImpl(this, element, oldCount, newCount);
269    }
270
271    @Override public boolean equals(@Nullable Object object) {
272      if (object instanceof Multiset) {
273        Multiset<?> that = (Multiset<?>) object;
274        return this.size() == that.size() && delegate.equals(that.elementSet());
275      }
276      return false;
277    }
278
279    @Override public int hashCode() {
280      int sum = 0;
281      for (E e : this) {
282        sum += ((e == null) ? 0 : e.hashCode()) ^ 1;
283      }
284      return sum;
285    }
286
287    /** @see SetMultiset#elementSet */
288    class ElementSet extends ForwardingSet<E> {
289      @Override protected Set<E> delegate() {
290        return delegate;
291      }
292
293      @Override public boolean add(E o) {
294        throw new UnsupportedOperationException();
295      }
296
297      @Override public boolean addAll(Collection<? extends E> c) {
298        throw new UnsupportedOperationException();
299      }
300    }
301
302    /** @see SetMultiset#entrySet */
303    class EntrySet extends AbstractSet<Entry<E>> {
304      @Override public int size() {
305        return delegate.size();
306      }
307      @Override public Iterator<Entry<E>> iterator() {
308        return new Iterator<Entry<E>>() {
309          final Iterator<E> elements = delegate.iterator();
310
311          @Override
312          public boolean hasNext() {
313            return elements.hasNext();
314          }
315          @Override
316          public Entry<E> next() {
317            return immutableEntry(elements.next(), 1);
318          }
319          @Override
320          public void remove() {
321            elements.remove();
322          }
323        };
324      }
325      // TODO(kevinb): faster contains, remove
326    }
327
328    private static final long serialVersionUID = 0;
329  }
330
331  /**
332   * Returns the expected number of distinct elements given the specified
333   * elements. The number of distinct elements is only computed if {@code
334   * elements} is an instance of {@code Multiset}; otherwise the default value
335   * of 11 is returned.
336   */
337  static int inferDistinctElements(Iterable<?> elements) {
338    if (elements instanceof Multiset) {
339      return ((Multiset<?>) elements).elementSet().size();
340    }
341    return 11; // initial capacity will be rounded up to 16
342  }
343
344  /**
345   * Returns an unmodifiable <b>view</b> of the intersection of two multisets.
346   * An element's count in the multiset is the smaller of its counts in the two
347   * backing multisets. The iteration order of the returned multiset matches the
348   * element set of {@code multiset1}, with repeated occurrences of the same
349   * element appearing consecutively.
350   *
351   * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
352   * based on different equivalence relations (as {@code HashMultiset} and
353   * {@code TreeMultiset} are).
354   *
355   * @since 2
356   */
357  public static <E> Multiset<E> intersection(
358      final Multiset<E> multiset1, final Multiset<?> multiset2) {
359    checkNotNull(multiset1);
360    checkNotNull(multiset2);
361
362    return new AbstractMultiset<E>() {
363      @Override public int count(Object element) {
364        int count1 = multiset1.count(element);
365        return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
366      }
367
368      @Override Set<E> createElementSet() {
369        return Sets.intersection(
370            multiset1.elementSet(), multiset2.elementSet());
371      }
372
373      @Override public Set<Entry<E>> entrySet() {
374        return entrySet;
375      }
376
377      final Set<Entry<E>> entrySet = new AbstractSet<Entry<E>>() {
378        @Override public Iterator<Entry<E>> iterator() {
379          final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
380          return new AbstractIterator<Entry<E>>() {
381            @Override protected Entry<E> computeNext() {
382              while (iterator1.hasNext()) {
383                Entry<E> entry1 = iterator1.next();
384                E element = entry1.getElement();
385                int count
386                    = Math.min(entry1.getCount(), multiset2.count(element));
387                if (count > 0) {
388                  return Multisets.immutableEntry(element, count);
389                }
390              }
391              return endOfData();
392            }
393          };
394        }
395
396        @Override public int size() {
397          return elementSet().size();
398        }
399
400        @Override public boolean contains(Object o) {
401          if (o instanceof Entry) {
402            Entry<?> entry = (Entry<?>) o;
403            int entryCount = entry.getCount();
404            return (entryCount > 0)
405                && (count(entry.getElement()) == entryCount);
406          }
407          return false;
408        }
409
410        @Override public boolean isEmpty() {
411          return elementSet().isEmpty();
412        }
413      };
414    };
415  }
416
417  /**
418   * Implementation of the {@code equals}, {@code hashCode}, and
419   * {@code toString} methods of {@link Multiset.Entry}.
420   */
421  abstract static class AbstractEntry<E> implements Multiset.Entry<E> {
422    /**
423     * Indicates whether an object equals this entry, following the behavior
424     * specified in {@link Multiset.Entry#equals}.
425     */
426    @Override public boolean equals(@Nullable Object object) {
427      if (object instanceof Multiset.Entry) {
428        Multiset.Entry<?> that = (Multiset.Entry<?>) object;
429        return this.getCount() == that.getCount()
430            && Objects.equal(this.getElement(), that.getElement());
431      }
432      return false;
433    }
434
435    /**
436     * Return this entry's hash code, following the behavior specified in
437     * {@link Multiset.Entry#hashCode}.
438     */
439    @Override public int hashCode() {
440      E e = getElement();
441      return ((e == null) ? 0 : e.hashCode()) ^ getCount();
442    }
443
444    /**
445     * Returns a string representation of this multiset entry. The string
446     * representation consists of the associated element if the associated count
447     * is one, and otherwise the associated element followed by the characters
448     * " x " (space, x and space) followed by the count. Elements and counts are
449     * converted to strings as by {@code String.valueOf}.
450     */
451    @Override public String toString() {
452      String text = String.valueOf(getElement());
453      int n = getCount();
454      return (n == 1) ? text : (text + " x " + n);
455    }
456  } 
457
458  /**
459   * An implementation of {@link Multiset#equals}.
460   */
461  static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) {
462    if (object == multiset) {
463      return true;
464    }
465    if (object instanceof Multiset) {
466      Multiset<?> that = (Multiset<?>) object;
467      /*
468       * We can't simply check whether the entry sets are equal, since that
469       * approach fails when a TreeMultiset has a comparator that returns 0
470       * when passed unequal elements.
471       */
472
473      if (multiset.size() != that.size()
474          || multiset.entrySet().size() != that.entrySet().size()) {
475        return false;
476      }
477      for (Entry<?> entry : that.entrySet()) {
478        if (multiset.count(entry.getElement()) != entry.getCount()) {
479          return false;
480        }
481      }
482      return true;
483    }
484    return false;
485  }
486
487  /**
488   * An implementation of {@link Multiset#addAll}.
489   */
490  static <E> boolean addAllImpl(
491      Multiset<E> self, Collection<? extends E> elements) {
492    if (elements.isEmpty()) {
493      return false;
494    }
495    if (elements instanceof Multiset) {
496      Multiset<? extends E> that = cast(elements);
497      for (Entry<? extends E> entry : that.entrySet()) {
498        self.add(entry.getElement(), entry.getCount());
499      }
500    } else {
501      Iterators.addAll(self, elements.iterator());
502    }
503    return true;
504  }
505
506  /**
507   * An implementation of {@link Multiset#removeAll}.
508   */
509  static boolean removeAllImpl(
510      Multiset<?> self, Collection<?> elementsToRemove) {
511    Collection<?> collection = (elementsToRemove instanceof Multiset)
512        ? ((Multiset<?>) elementsToRemove).elementSet() : elementsToRemove;
513
514    return self.elementSet().removeAll(collection);
515  }
516
517  /**
518   * An implementation of {@link Multiset#retainAll}.
519   */
520  static boolean retainAllImpl(
521      Multiset<?> self, Collection<?> elementsToRetain) {
522    Collection<?> collection = (elementsToRetain instanceof Multiset)
523        ? ((Multiset<?>) elementsToRetain).elementSet() : elementsToRetain;
524
525    return self.elementSet().retainAll(collection);
526  }
527
528  /**
529   * An implementation of {@link Multiset#setCount(Object, int)}.
530   */
531  static <E> int setCountImpl(Multiset<E> self, E element, int count) {
532    checkNonnegative(count, "count");
533
534    int oldCount = self.count(element);
535
536    int delta = count - oldCount;
537    if (delta > 0) {
538      self.add(element, delta);
539    } else if (delta < 0) {
540      self.remove(element, -delta);
541    }
542
543    return oldCount;
544  }
545
546  /**
547   * An implementation of {@link Multiset#setCount(Object, int, int)}.
548   */
549  static <E> boolean setCountImpl(
550      Multiset<E> self, E element, int oldCount, int newCount) {
551    checkNonnegative(oldCount, "oldCount");
552    checkNonnegative(newCount, "newCount");
553
554    if (self.count(element) == oldCount) {
555      self.setCount(element, newCount);
556      return true;
557    } else {
558      return false;
559    }
560  }
561  
562  /**
563   * An implementation of {@link Multiset#elementSet}.
564   */
565  static <E> Set<E> elementSetImpl(Multiset<E> self){
566    return new ElementSetImpl<E>(self);
567  }
568  
569  private static final class ElementSetImpl<E> extends AbstractSet<E>
570      implements Serializable {
571    private final Multiset<E> multiset;
572    
573    ElementSetImpl(Multiset<E> multiset) {
574      this.multiset = multiset;
575    }
576
577    @Override public boolean add(E e) {
578      throw new UnsupportedOperationException();
579    }
580
581    @Override public boolean addAll(Collection<? extends E> c) {
582      throw new UnsupportedOperationException();
583    }
584
585    @Override public void clear() {
586      multiset.clear();
587    }
588
589    @Override public boolean contains(Object o) {
590      return multiset.contains(o);
591    }
592
593    @Override public boolean containsAll(Collection<?> c) {
594      return multiset.containsAll(c);
595    }
596
597    @Override public boolean isEmpty() {
598      return multiset.isEmpty();
599    }
600
601    @Override public Iterator<E> iterator() {
602      final Iterator<Entry<E>> entryIterator = multiset.entrySet().iterator();
603      return new Iterator<E>() {
604
605        @Override public boolean hasNext() {
606          return entryIterator.hasNext();
607        }
608
609        @Override public E next() {
610          return entryIterator.next().getElement();
611        }
612
613        @Override public void remove() {
614          entryIterator.remove();
615        }
616      };
617    }
618
619    @Override public boolean remove(Object o) {
620      int count = multiset.count(o);
621      if (count > 0) {
622        multiset.remove(o, count);
623        return true;
624      }
625      return false;
626    }
627
628    @Override public int size() {
629      return multiset.entrySet().size();
630    }
631
632    private static final long serialVersionUID = 0;
633  }
634  
635  /**
636   * An implementation of {@link Multiset#iterator}.
637   */
638  static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) {
639    return new MultisetIteratorImpl<E>(
640        multiset, multiset.entrySet().iterator());
641  }
642
643  static final class MultisetIteratorImpl<E> implements Iterator<E> {
644    private final Multiset<E> multiset;
645    private final Iterator<Entry<E>> entryIterator;
646    private Entry<E> currentEntry;
647    /** Count of subsequent elements equal to current element */
648    private int laterCount;
649    /** Count of all elements equal to current element */
650    private int totalCount;
651    private boolean canRemove;
652
653    MultisetIteratorImpl(
654        Multiset<E> multiset, Iterator<Entry<E>> entryIterator) {
655      this.multiset = multiset;
656      this.entryIterator = entryIterator;
657    }
658
659    @Override
660    public boolean hasNext() {
661      return laterCount > 0 || entryIterator.hasNext();
662    }
663
664    @Override
665    public E next() {
666      if (!hasNext()) {
667        throw new NoSuchElementException();
668      }
669      if (laterCount == 0) {
670        currentEntry = entryIterator.next();
671        totalCount = laterCount = currentEntry.getCount();
672      }
673      laterCount--;
674      canRemove = true;
675      return currentEntry.getElement();
676    }
677
678    @Override
679    public void remove() {
680      checkState(
681          canRemove, "no calls to next() since the last call to remove()");
682      if (totalCount == 1) {
683        entryIterator.remove();
684      } else {
685        multiset.remove(currentEntry.getElement());
686      }
687      totalCount--;
688      canRemove = false;
689    }
690  }
691  
692  /**
693   * An implementation of {@link Multiset#size}.
694   */
695  static int sizeImpl(Multiset<?> multiset) {
696    long size = 0;
697    for (Entry<?> entry : multiset.entrySet()) {
698      size += entry.getCount();
699    }
700    return Ints.saturatedCast(size);
701  }
702
703  static void checkNonnegative(int count, String name) {
704    checkArgument(count >= 0, "%s cannot be negative: %s", name, count);
705  }
706
707  /**
708   * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
709   */
710  static <T> Multiset<T> cast(Iterable<T> iterable) {
711    return (Multiset<T>) iterable;
712  }
713}