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