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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.base.Preconditions.checkState;
022
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.base.Objects;
025 import com.google.common.collect.Multiset.Entry;
026 import com.google.common.primitives.Ints;
027
028 import java.io.Serializable;
029 import java.util.AbstractSet;
030 import java.util.Collection;
031 import java.util.Collections;
032 import java.util.Iterator;
033 import java.util.NoSuchElementException;
034 import java.util.Set;
035
036 import 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
048 public 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 }