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
022 import com.google.common.annotations.GwtCompatible;
023 import com.google.common.base.Objects;
024
025 import java.io.Serializable;
026 import java.util.AbstractSet;
027 import java.util.Collection;
028 import java.util.Collections;
029 import java.util.Iterator;
030 import java.util.Set;
031
032 import javax.annotation.Nullable;
033
034 /**
035 * Provides static utility methods for creating and working with {@link
036 * Multiset} instances.
037 *
038 * @author Kevin Bourrillion
039 * @author Mike Bostock
040 * @since 2 (imported from Google Collections Library)
041 */
042 @GwtCompatible
043 public final class Multisets {
044 private Multisets() {}
045
046 /**
047 * Returns an unmodifiable view of the specified multiset. Query operations on
048 * the returned multiset "read through" to the specified multiset, and
049 * attempts to modify the returned multiset result in an
050 * {@link UnsupportedOperationException}.
051 *
052 * <p>The returned multiset will be serializable if the specified multiset is
053 * serializable.
054 *
055 * @param multiset the multiset for which an unmodifiable view is to be
056 * generated
057 * @return an unmodifiable view of the multiset
058 */
059 public static <E> Multiset<E> unmodifiableMultiset(
060 Multiset<? extends E> multiset) {
061 return new UnmodifiableMultiset<E>(checkNotNull(multiset));
062 }
063
064 private static class UnmodifiableMultiset<E>
065 extends ForwardingMultiset<E> implements Serializable {
066 final Multiset<? extends E> delegate;
067
068 UnmodifiableMultiset(Multiset<? extends E> delegate) {
069 this.delegate = delegate;
070 }
071
072 @SuppressWarnings("unchecked")
073 @Override protected Multiset<E> delegate() {
074 // This is safe because all non-covariant methods are overriden
075 return (Multiset) delegate;
076 }
077
078 transient Set<E> elementSet;
079
080 @Override public Set<E> elementSet() {
081 Set<E> es = elementSet;
082 return (es == null)
083 ? elementSet = Collections.<E>unmodifiableSet(delegate.elementSet())
084 : es;
085 }
086
087 transient Set<Multiset.Entry<E>> entrySet;
088
089 @SuppressWarnings("unchecked")
090 @Override public Set<Multiset.Entry<E>> entrySet() {
091 Set<Multiset.Entry<E>> es = entrySet;
092 return (es == null)
093 // Safe because the returned set is made unmodifiable and Entry
094 // itself is readonly
095 ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
096 : es;
097 }
098
099 @SuppressWarnings("unchecked")
100 @Override public Iterator<E> iterator() {
101 // Safe because the returned Iterator is made unmodifiable
102 return (Iterator) Iterators.unmodifiableIterator(delegate.iterator());
103 }
104
105 @Override public boolean add(E element) {
106 throw new UnsupportedOperationException();
107 }
108
109 @Override public int add(E element, int occurences) {
110 throw new UnsupportedOperationException();
111 }
112
113 @Override public boolean addAll(Collection<? extends E> elementsToAdd) {
114 throw new UnsupportedOperationException();
115 }
116
117 @Override public boolean remove(Object element) {
118 throw new UnsupportedOperationException();
119 }
120
121 @Override public int remove(Object element, int occurrences) {
122 throw new UnsupportedOperationException();
123 }
124
125 @Override public boolean removeAll(Collection<?> elementsToRemove) {
126 throw new UnsupportedOperationException();
127 }
128
129 @Override public boolean retainAll(Collection<?> elementsToRetain) {
130 throw new UnsupportedOperationException();
131 }
132
133 @Override public void clear() {
134 throw new UnsupportedOperationException();
135 }
136
137 @Override public int setCount(E element, int count) {
138 throw new UnsupportedOperationException();
139 }
140
141 @Override public boolean setCount(E element, int oldCount, int newCount) {
142 throw new UnsupportedOperationException();
143 }
144
145 private static final long serialVersionUID = 0;
146 }
147
148 /**
149 * Returns an immutable multiset entry with the specified element and count.
150 *
151 * @param e the element to be associated with the returned entry
152 * @param n the count to be associated with the returned entry
153 * @throws IllegalArgumentException if {@code n} is negative
154 */
155 public static <E> Multiset.Entry<E> immutableEntry(
156 @Nullable final E e, final int n) {
157 checkArgument(n >= 0);
158 return new AbstractEntry<E>() {
159 public E getElement() {
160 return e;
161 }
162 public int getCount() {
163 return n;
164 }
165 };
166 }
167
168 /**
169 * Returns a multiset view of the specified set. The multiset is backed by the
170 * set, so changes to the set are reflected in the multiset, and vice versa.
171 * If the set is modified while an iteration over the multiset is in progress
172 * (except through the iterator's own {@code remove} operation) the results of
173 * the iteration are undefined.
174 *
175 * <p>The multiset supports element removal, which removes the corresponding
176 * element from the set. It does not support the {@code add} or {@code addAll}
177 * operations, nor does it support the use of {@code setCount} to add
178 * elements.
179 *
180 * <p>The returned multiset will be serializable if the specified set is
181 * serializable. The multiset is threadsafe if the set is threadsafe.
182 *
183 * @param set the backing set for the returned multiset view
184 */
185 static <E> Multiset<E> forSet(Set<E> set) {
186 return new SetMultiset<E>(set);
187 }
188
189 /** @see Multisets#forSet */
190 private static class SetMultiset<E> extends ForwardingCollection<E>
191 implements Multiset<E>, Serializable {
192 final Set<E> delegate;
193
194 SetMultiset(Set<E> set) {
195 delegate = checkNotNull(set);
196 }
197
198 @Override protected Set<E> delegate() {
199 return delegate;
200 }
201
202 public int count(Object element) {
203 return delegate.contains(element) ? 1 : 0;
204 }
205
206 public int add(E element, int occurrences) {
207 throw new UnsupportedOperationException();
208 }
209
210 public int remove(Object element, int occurrences) {
211 if (occurrences == 0) {
212 return count(element);
213 }
214 checkArgument(occurrences > 0);
215 return delegate.remove(element) ? 1 : 0;
216 }
217
218 transient Set<E> elementSet;
219
220 public Set<E> elementSet() {
221 Set<E> es = elementSet;
222 return (es == null) ? elementSet = new ElementSet() : es;
223 }
224
225 transient Set<Entry<E>> entrySet;
226
227 public Set<Entry<E>> entrySet() {
228 Set<Entry<E>> es = entrySet;
229 return (es == null) ? entrySet = new EntrySet() : es;
230 }
231
232 @Override public boolean add(E o) {
233 throw new UnsupportedOperationException();
234 }
235
236 @Override public boolean addAll(Collection<? extends E> c) {
237 throw new UnsupportedOperationException();
238 }
239
240 public int setCount(E element, int count) {
241 checkNonnegative(count, "count");
242
243 if (count == count(element)) {
244 return count;
245 } else if (count == 0) {
246 remove(element);
247 return 1;
248 } else {
249 throw new UnsupportedOperationException();
250 }
251 }
252
253 public boolean setCount(E element, int oldCount, int newCount) {
254 return setCountImpl(this, element, oldCount, newCount);
255 }
256
257 @Override public boolean equals(@Nullable Object object) {
258 if (object instanceof Multiset) {
259 Multiset<?> that = (Multiset<?>) object;
260 return this.size() == that.size() && delegate.equals(that.elementSet());
261 }
262 return false;
263 }
264
265 @Override public int hashCode() {
266 int sum = 0;
267 for (E e : this) {
268 sum += ((e == null) ? 0 : e.hashCode()) ^ 1;
269 }
270 return sum;
271 }
272
273 /** @see SetMultiset#elementSet */
274 class ElementSet extends ForwardingSet<E> {
275 @Override protected Set<E> delegate() {
276 return delegate;
277 }
278
279 @Override public boolean add(E o) {
280 throw new UnsupportedOperationException();
281 }
282
283 @Override public boolean addAll(Collection<? extends E> c) {
284 throw new UnsupportedOperationException();
285 }
286 }
287
288 /** @see SetMultiset#entrySet */
289 class EntrySet extends AbstractSet<Entry<E>> {
290 @Override public int size() {
291 return delegate.size();
292 }
293 @Override public Iterator<Entry<E>> iterator() {
294 return new Iterator<Entry<E>>() {
295 final Iterator<E> elements = delegate.iterator();
296
297 public boolean hasNext() {
298 return elements.hasNext();
299 }
300 public Entry<E> next() {
301 return immutableEntry(elements.next(), 1);
302 }
303 public void remove() {
304 elements.remove();
305 }
306 };
307 }
308 // TODO: faster contains, remove
309 }
310
311 private static final long serialVersionUID = 0;
312 }
313
314 /**
315 * Returns the expected number of distinct elements given the specified
316 * elements. The number of distinct elements is only computed if {@code
317 * elements} is an instance of {@code Multiset}; otherwise the default value
318 * of 11 is returned.
319 */
320 static int inferDistinctElements(Iterable<?> elements) {
321 if (elements instanceof Multiset) {
322 return ((Multiset<?>) elements).elementSet().size();
323 }
324 return 11; // initial capacity will be rounded up to 16
325 }
326
327 /**
328 * Returns an unmodifiable <b>view</b> of the intersection of two multisets.
329 * An element's count in the multiset is the smaller of its counts in the two
330 * backing multisets. The iteration order of the returned multiset matches the
331 * element set of {@code multiset1}, with repeated occurrences of the same
332 * element appearing consecutively.
333 *
334 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
335 * based on different equivalence relations (as {@code HashMultiset} and
336 * {@code TreeMultiset} are).
337 *
338 * @since 2
339 */
340 public static <E> Multiset<E> intersection(
341 final Multiset<E> multiset1, final Multiset<?> multiset2) {
342 checkNotNull(multiset1);
343 checkNotNull(multiset2);
344
345 return new AbstractMultiset<E>() {
346 @Override public int count(Object element) {
347 int count1 = multiset1.count(element);
348 return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
349 }
350
351 @Override Set<E> createElementSet() {
352 return Sets.intersection(
353 multiset1.elementSet(), multiset2.elementSet());
354 }
355
356 @Override public Set<Entry<E>> entrySet() {
357 return entrySet;
358 }
359
360 final Set<Entry<E>> entrySet = new AbstractSet<Entry<E>>() {
361 @Override public Iterator<Entry<E>> iterator() {
362 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
363 return new AbstractIterator<Entry<E>>() {
364 @Override protected Entry<E> computeNext() {
365 while (iterator1.hasNext()) {
366 Entry<E> entry1 = iterator1.next();
367 E element = entry1.getElement();
368 int count
369 = Math.min(entry1.getCount(), multiset2.count(element));
370 if (count > 0) {
371 return Multisets.immutableEntry(element, count);
372 }
373 }
374 return endOfData();
375 }
376 };
377 }
378
379 @Override public int size() {
380 return elementSet().size();
381 }
382
383 @Override public boolean contains(Object o) {
384 if (o instanceof Entry) {
385 Entry<?> entry = (Entry<?>) o;
386 int entryCount = entry.getCount();
387 return (entryCount > 0)
388 && (count(entry.getElement()) == entryCount);
389 }
390 return false;
391 }
392
393 @Override public boolean isEmpty() {
394 return elementSet().isEmpty();
395 }
396 };
397 };
398 }
399
400 /**
401 * Implementation of the {@code equals}, {@code hashCode}, and
402 * {@code toString} methods of {@link Multiset.Entry}.
403 */
404 abstract static class AbstractEntry<E> implements Multiset.Entry<E> {
405 /**
406 * Indicates whether an object equals this entry, following the behavior
407 * specified in {@link Multiset.Entry#equals}.
408 */
409 @Override public boolean equals(@Nullable Object object) {
410 if (object instanceof Multiset.Entry) {
411 Multiset.Entry<?> that = (Multiset.Entry<?>) object;
412 return this.getCount() == that.getCount()
413 && Objects.equal(this.getElement(), that.getElement());
414 }
415 return false;
416 }
417
418 /**
419 * Return this entry's hash code, following the behavior specified in
420 * {@link Multiset.Entry#hashCode}.
421 */
422 @Override public int hashCode() {
423 E e = getElement();
424 return ((e == null) ? 0 : e.hashCode()) ^ getCount();
425 }
426
427 /**
428 * Returns a string representation of this multiset entry. The string
429 * representation consists of the associated element if the associated count
430 * is one, and otherwise the associated element followed by the characters
431 * " x " (space, x and space) followed by the count. Elements and counts are
432 * converted to strings as by {@code String.valueOf}.
433 */
434 @Override public String toString() {
435 String text = String.valueOf(getElement());
436 int n = getCount();
437 return (n == 1) ? text : (text + " x " + n);
438 }
439 }
440
441 static <E> int setCountImpl(Multiset<E> self, E element, int count) {
442 checkNonnegative(count, "count");
443
444 int oldCount = self.count(element);
445
446 int delta = count - oldCount;
447 if (delta > 0) {
448 self.add(element, delta);
449 } else if (delta < 0) {
450 self.remove(element, -delta);
451 }
452
453 return oldCount;
454 }
455
456 static <E> boolean setCountImpl(
457 Multiset<E> self, E element, int oldCount, int newCount) {
458 checkNonnegative(oldCount, "oldCount");
459 checkNonnegative(newCount, "newCount");
460
461 if (self.count(element) == oldCount) {
462 self.setCount(element, newCount);
463 return true;
464 } else {
465 return false;
466 }
467 }
468
469 static void checkNonnegative(int count, String name) {
470 checkArgument(count >= 0, "%s cannot be negative: %s", name, count);
471 }
472 }