001 /*
002 * Copyright (C) 2008 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.checkNotNull;
020
021 import com.google.common.annotations.GwtCompatible;
022 import com.google.common.annotations.GwtIncompatible;
023 import com.google.common.collect.Serialization.FieldSetter;
024 import com.google.common.primitives.Ints;
025
026 import java.io.IOException;
027 import java.io.InvalidObjectException;
028 import java.io.ObjectInputStream;
029 import java.io.ObjectOutputStream;
030 import java.util.ArrayList;
031 import java.util.Arrays;
032 import java.util.Collections;
033 import java.util.Iterator;
034 import java.util.List;
035 import java.util.Map;
036 import java.util.Set;
037
038 import javax.annotation.Nullable;
039
040 /**
041 * An immutable hash-based multiset. Does not permit null elements.
042 *
043 * <p>Its iterator orders elements according to the first appearance of the
044 * element among the items passed to the factory method or builder. When the
045 * multiset contains multiple instances of an element, those instances are
046 * consecutive in the iteration order.
047 *
048 * @author Jared Levy
049 * @since 2 (imported from Google Collections Library)
050 */
051 @GwtCompatible(serializable = true)
052 public class ImmutableMultiset<E> extends ImmutableCollection<E>
053 implements Multiset<E> {
054
055 /**
056 * Returns the empty immutable multiset.
057 */
058 @SuppressWarnings("unchecked") // all supported methods are covariant
059 public static <E> ImmutableMultiset<E> of() {
060 return (ImmutableMultiset<E>) EmptyImmutableMultiset.INSTANCE;
061 }
062
063 /**
064 * Returns an immutable multiset containing a single element.
065 *
066 * @throws NullPointerException if {@code element} is null
067 * @since 6 (source-compatible since release 2)
068 */
069 @SuppressWarnings("unchecked") // generic array created but never written
070 public static <E> ImmutableMultiset<E> of(E element) {
071 return copyOfInternal(element);
072 }
073
074 /**
075 * Returns an immutable multiset containing the given elements, in order.
076 *
077 * @throws NullPointerException if any element is null
078 * @since 6 (source-compatible since release 2)
079 */
080 @SuppressWarnings("unchecked") //
081 public static <E> ImmutableMultiset<E> of(E e1, E e2) {
082 return copyOfInternal(e1, e2);
083 }
084
085 /**
086 * Returns an immutable multiset containing the given elements, in order.
087 *
088 * @throws NullPointerException if any element is null
089 * @since 6 (source-compatible since release 2)
090 */
091 @SuppressWarnings("unchecked") //
092 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
093 return copyOfInternal(e1, e2, e3);
094 }
095
096 /**
097 * Returns an immutable multiset containing the given elements, in order.
098 *
099 * @throws NullPointerException if any element is null
100 * @since 6 (source-compatible since release 2)
101 */
102 @SuppressWarnings("unchecked") //
103 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
104 return copyOfInternal(e1, e2, e3, e4);
105 }
106
107 /**
108 * Returns an immutable multiset containing the given elements, in order.
109 *
110 * @throws NullPointerException if any element is null
111 * @since 6 (source-compatible since release 2)
112 */
113 @SuppressWarnings("unchecked") //
114 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
115 return copyOfInternal(e1, e2, e3, e4, e5);
116 }
117
118 /**
119 * Returns an immutable multiset containing the given elements, in order.
120 *
121 * @throws NullPointerException if any element is null
122 * @since 6 (source-compatible since release 2)
123 */
124 @SuppressWarnings("unchecked") //
125 public static <E> ImmutableMultiset<E> of(
126 E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
127 int size = others.length + 6;
128 List<E> all = new ArrayList<E>(size);
129 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
130 Collections.addAll(all, others);
131 return copyOf(all);
132 }
133
134 /**
135 * Returns an immutable multiset containing the given elements.
136 *
137 * <p>The multiset is ordered by the first occurrence of each element. For
138 * example, {@code ImmutableMultiset.of(2, 3, 1, 3)} yields a multiset with
139 * elements in the order {@code 2, 3, 3, 1}.
140 *
141 * @throws NullPointerException if any of {@code elements} is null
142 * @deprecated use {@link #copyOf(Object[])}.
143 * @since 2 (changed from varargs in release 6)
144 */
145 @Deprecated
146 public static <E> ImmutableMultiset<E> of(E[] elements) {
147 return copyOf(Arrays.asList(elements));
148 }
149
150 /**
151 * Returns an immutable multiset containing the given elements.
152 *
153 * <p>The multiset is ordered by the first occurrence of each element. For
154 * example, {@code ImmutableMultiset.copyOf([2, 3, 1, 3])} yields a multiset
155 * with elements in the order {@code 2, 3, 3, 1}.
156 *
157 * @throws NullPointerException if any of {@code elements} is null
158 * @since 6
159 */
160 public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
161 return copyOf(Arrays.asList(elements));
162 }
163
164 /**
165 * Returns an immutable multiset containing the given elements.
166 *
167 * <p>The multiset is ordered by the first occurrence of each element. For
168 * example, {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3))} yields
169 * a multiset with elements in the order {@code 2, 3, 3, 1}.
170 *
171 * <p>Note that if {@code c} is a {@code Collection<String>}, then {@code
172 * ImmutableMultiset.copyOf(c)} returns an {@code ImmutableMultiset<String>}
173 * containing each of the strings in {@code c}, while
174 * {@code ImmutableMultiset.of(c)} returns an
175 * {@code ImmutableMultiset<Collection<String>>} containing one element (the
176 * given collection itself).
177 *
178 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
179 * is an {@code ImmutableMultiset}, no copy will actually be performed, and
180 * the given multiset itself will be returned.
181 *
182 * @throws NullPointerException if any of {@code elements} is null
183 */
184 public static <E> ImmutableMultiset<E> copyOf(
185 Iterable<? extends E> elements) {
186 if (elements instanceof ImmutableMultiset) {
187 @SuppressWarnings("unchecked") // all supported methods are covariant
188 ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
189 return result;
190 }
191
192 @SuppressWarnings("unchecked") // the cast causes a warning
193 Multiset<? extends E> multiset = (elements instanceof Multiset)
194 ? (Multiset<? extends E>) elements
195 : LinkedHashMultiset.create(elements);
196
197 return copyOfInternal(multiset);
198 }
199
200 private static <E> ImmutableMultiset<E> copyOfInternal(E... elements) {
201 return copyOf(Arrays.asList(elements));
202 }
203
204 private static <E> ImmutableMultiset<E> copyOfInternal(
205 Multiset<? extends E> multiset) {
206 long size = 0;
207 ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
208
209 for (Entry<? extends E> entry : multiset.entrySet()) {
210 int count = entry.getCount();
211 if (count > 0) {
212 // Since ImmutableMap.Builder throws an NPE if an element is null, no
213 // other null checks are needed.
214 builder.put(entry.getElement(), count);
215 size += count;
216 }
217 }
218
219 if (size == 0) {
220 return of();
221 }
222 return new ImmutableMultiset<E>(builder.build(), Ints.saturatedCast(size));
223 }
224
225 /**
226 * Returns an immutable multiset containing the given elements.
227 *
228 * <p>The multiset is ordered by the first occurrence of each element. For
229 * example,
230 * {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3).iterator())}
231 * yields a multiset with elements in the order {@code 2, 3, 3, 1}.
232 *
233 * @throws NullPointerException if any of {@code elements} is null
234 */
235 public static <E> ImmutableMultiset<E> copyOf(
236 Iterator<? extends E> elements) {
237 Multiset<E> multiset = LinkedHashMultiset.create();
238 Iterators.addAll(multiset, elements);
239 return copyOfInternal(multiset);
240 }
241
242 private final transient ImmutableMap<E, Integer> map;
243 private final transient int size;
244
245 // These constants allow the deserialization code to set final fields. This
246 // holder class makes sure they are not initialized unless an instance is
247 // deserialized.
248 @GwtIncompatible("java serialization is not supported.")
249 @SuppressWarnings("unchecked")
250 // eclipse doesn't like the raw types here, but they're harmless
251 private static class FieldSettersHolder {
252 static final FieldSetter<ImmutableMultiset> MAP_FIELD_SETTER
253 = Serialization.getFieldSetter(ImmutableMultiset.class, "map");
254 static final FieldSetter<ImmutableMultiset> SIZE_FIELD_SETTER
255 = Serialization.getFieldSetter(ImmutableMultiset.class, "size");
256 }
257
258 ImmutableMultiset(ImmutableMap<E, Integer> map, int size) {
259 this.map = map;
260 this.size = size;
261 }
262
263 public int count(@Nullable Object element) {
264 Integer value = map.get(element);
265 return (value == null) ? 0 : value;
266 }
267
268 @Override public UnmodifiableIterator<E> iterator() {
269 final Iterator<Map.Entry<E, Integer>> mapIterator
270 = map.entrySet().iterator();
271
272 return new UnmodifiableIterator<E>() {
273 int remaining;
274 E element;
275
276 public boolean hasNext() {
277 return (remaining > 0) || mapIterator.hasNext();
278 }
279
280 public E next() {
281 if (remaining <= 0) {
282 Map.Entry<E, Integer> entry = mapIterator.next();
283 element = entry.getKey();
284 remaining = entry.getValue();
285 }
286 remaining--;
287 return element;
288 }
289 };
290 }
291
292 public int size() {
293 return size;
294 }
295
296 @Override public boolean contains(@Nullable Object element) {
297 return map.containsKey(element);
298 }
299
300 /**
301 * Guaranteed to throw an exception and leave the collection unmodified.
302 *
303 * @throws UnsupportedOperationException always
304 */
305 public int add(E element, int occurrences) {
306 throw new UnsupportedOperationException();
307 }
308
309 /**
310 * Guaranteed to throw an exception and leave the collection unmodified.
311 *
312 * @throws UnsupportedOperationException always
313 */
314 public int remove(Object element, int occurrences) {
315 throw new UnsupportedOperationException();
316 }
317
318 /**
319 * Guaranteed to throw an exception and leave the collection unmodified.
320 *
321 * @throws UnsupportedOperationException always
322 */
323 public int setCount(E element, int count) {
324 throw new UnsupportedOperationException();
325 }
326
327 /**
328 * Guaranteed to throw an exception and leave the collection unmodified.
329 *
330 * @throws UnsupportedOperationException always
331 */
332 public boolean setCount(E element, int oldCount, int newCount) {
333 throw new UnsupportedOperationException();
334 }
335
336 @Override public boolean equals(@Nullable Object object) {
337 if (object == this) {
338 return true;
339 }
340 if (object instanceof Multiset) {
341 Multiset<?> that = (Multiset<?>) object;
342 if (this.size() != that.size()) {
343 return false;
344 }
345 for (Entry<?> entry : that.entrySet()) {
346 if (count(entry.getElement()) != entry.getCount()) {
347 return false;
348 }
349 }
350 return true;
351 }
352 return false;
353 }
354
355 @Override public int hashCode() {
356 // could cache this, but not considered worthwhile to do so
357 return map.hashCode();
358 }
359
360 @Override public String toString() {
361 return entrySet().toString();
362 }
363
364 // TODO: Serialization of the element set should serialize the multiset, and
365 // deserialization should call multiset.elementSet(). Then
366 // reserialized(multiset).elementSet() == reserialized(multiset.elementSet())
367 // Currently, those object references differ.
368 public Set<E> elementSet() {
369 return map.keySet();
370 }
371
372 private transient ImmutableSet<Entry<E>> entrySet;
373
374 public Set<Entry<E>> entrySet() {
375 ImmutableSet<Entry<E>> es = entrySet;
376 return (es == null) ? (entrySet = new EntrySet<E>(this)) : es;
377 }
378
379 private static class EntrySet<E> extends ImmutableSet<Entry<E>> {
380 final ImmutableMultiset<E> multiset;
381
382 public EntrySet(ImmutableMultiset<E> multiset) {
383 this.multiset = multiset;
384 }
385
386 @Override public UnmodifiableIterator<Entry<E>> iterator() {
387 final Iterator<Map.Entry<E, Integer>> mapIterator
388 = multiset.map.entrySet().iterator();
389 return new UnmodifiableIterator<Entry<E>>() {
390 public boolean hasNext() {
391 return mapIterator.hasNext();
392 }
393 public Entry<E> next() {
394 Map.Entry<E, Integer> mapEntry = mapIterator.next();
395 return
396 Multisets.immutableEntry(mapEntry.getKey(), mapEntry.getValue());
397 }
398 };
399 }
400
401 public int size() {
402 return multiset.map.size();
403 }
404
405 @Override public boolean contains(Object o) {
406 if (o instanceof Entry) {
407 Entry<?> entry = (Entry<?>) o;
408 if (entry.getCount() <= 0) {
409 return false;
410 }
411 int count = multiset.count(entry.getElement());
412 return count == entry.getCount();
413 }
414 return false;
415 }
416
417 // TODO: Revert once this class is emulated in GWT.
418 @Override public Object[] toArray() {
419 Object[] newArray = new Object[size()];
420 return toArray(newArray);
421 }
422
423 // TODO: Revert once this class is emulated in GWT.
424 @Override public <T> T[] toArray(T[] other) {
425 int size = size();
426 if (other.length < size) {
427 other = ObjectArrays.newArray(other, size);
428 } else if (other.length > size) {
429 other[size] = null;
430 }
431
432 // Writes will produce ArrayStoreException when the toArray() doc requires
433 Object[] otherAsObjectArray = other;
434 int index = 0;
435 for (Entry<?> element : this) {
436 otherAsObjectArray[index++] = element;
437 }
438 return other;
439 }
440
441 @Override public int hashCode() {
442 return multiset.map.hashCode();
443 }
444
445 @GwtIncompatible("not needed in emulated source.")
446 @Override Object writeReplace() {
447 return this;
448 }
449
450 private static final long serialVersionUID = 0;
451 }
452
453 /**
454 * @serialData the number of distinct elements, the first element, its count,
455 * the second element, its count, and so on
456 */
457 @GwtIncompatible("java.io.ObjectOutputStream")
458 private void writeObject(ObjectOutputStream stream) throws IOException {
459 stream.defaultWriteObject();
460 Serialization.writeMultiset(this, stream);
461 }
462
463 @GwtIncompatible("java.io.ObjectInputStream")
464 private void readObject(ObjectInputStream stream)
465 throws IOException, ClassNotFoundException {
466 stream.defaultReadObject();
467 int entryCount = stream.readInt();
468 ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
469 long tmpSize = 0;
470 for (int i = 0; i < entryCount; i++) {
471 @SuppressWarnings("unchecked") // reading data stored by writeMultiset
472 E element = (E) stream.readObject();
473 int count = stream.readInt();
474 if (count <= 0) {
475 throw new InvalidObjectException("Invalid count " + count);
476 }
477 builder.put(element, count);
478 tmpSize += count;
479 }
480
481 FieldSettersHolder.MAP_FIELD_SETTER.set(this, builder.build());
482 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, Ints.saturatedCast(tmpSize));
483 }
484
485 @GwtIncompatible("java serialization not supported.")
486 @Override Object writeReplace() {
487 return this;
488 }
489
490 private static final long serialVersionUID = 0;
491
492 /**
493 * Returns a new builder. The generated builder is equivalent to the builder
494 * created by the {@link Builder} constructor.
495 */
496 public static <E> Builder<E> builder() {
497 return new Builder<E>();
498 }
499
500 /**
501 * A builder for creating immutable multiset instances, especially
502 * {@code public static final} multisets ("constant multisets").
503 *
504 * <p>Example:
505 * <pre> {@code
506 * public static final ImmutableMultiset<Bean> BEANS
507 * = new ImmutableMultiset.Builder<Bean>()
508 * .addCopies(Bean.COCOA, 4)
509 * .addCopies(Bean.GARDEN, 6)
510 * .addCopies(Bean.RED, 8)
511 * .addCopies(Bean.BLACK_EYED, 10)
512 * .build();}</pre>
513 *
514 * <p>Builder instances can be reused - it is safe to call {@link #build}
515 * multiple times to build multiple multisets in series. Each multiset
516 * is a superset of the multiset created before it.
517 */
518 public static final class Builder<E> extends ImmutableCollection.Builder<E> {
519 private final Multiset<E> contents = LinkedHashMultiset.create();
520
521 /**
522 * Creates a new builder. The returned builder is equivalent to the builder
523 * generated by {@link ImmutableMultiset#builder}.
524 */
525 public Builder() {}
526
527 /**
528 * Adds {@code element} to the {@code ImmutableMultiset}.
529 *
530 * @param element the element to add
531 * @return this {@code Builder} object
532 * @throws NullPointerException if {@code element} is null
533 */
534 @Override public Builder<E> add(E element) {
535 contents.add(checkNotNull(element));
536 return this;
537 }
538
539 /**
540 * Adds a number of occurrences of an element to this {@code
541 * ImmutableMultiset}.
542 *
543 * @param element the element to add
544 * @param occurrences the number of occurrences of the element to add. May
545 * be zero, in which case no change will be made.
546 * @return this {@code Builder} object
547 * @throws NullPointerException if {@code element} is null
548 * @throws IllegalArgumentException if {@code occurrences} is negative, or
549 * if this operation would result in more than {@link Integer#MAX_VALUE}
550 * occurrences of the element
551 */
552 public Builder<E> addCopies(E element, int occurrences) {
553 contents.add(checkNotNull(element), occurrences);
554 return this;
555 }
556
557 /**
558 * Adds or removes the necessary occurrences of an element such that the
559 * element attains the desired count.
560 *
561 * @param element the element to add or remove occurrences of
562 * @param count the desired count of the element in this multiset
563 * @return this {@code Builder} object
564 * @throws NullPointerException if {@code element} is null
565 * @throws IllegalArgumentException if {@code count} is negative
566 */
567 public Builder<E> setCount(E element, int count) {
568 contents.setCount(checkNotNull(element), count);
569 return this;
570 }
571
572 /**
573 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
574 *
575 * @param elements the elements to add
576 * @return this {@code Builder} object
577 * @throws NullPointerException if {@code elements} is null or contains a
578 * null element
579 */
580 @Override public Builder<E> add(E... elements) {
581 super.add(elements);
582 return this;
583 }
584
585 /**
586 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
587 *
588 * @param elements the {@code Iterable} to add to the {@code
589 * ImmutableMultiset}
590 * @return this {@code Builder} object
591 * @throws NullPointerException if {@code elements} is null or contains a
592 * null element
593 */
594 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
595 if (elements instanceof Multiset) {
596 @SuppressWarnings("unchecked")
597 Multiset<? extends E> multiset = (Multiset<? extends E>) elements;
598 for (Entry<? extends E> entry : multiset.entrySet()) {
599 addCopies(entry.getElement(), entry.getCount());
600 }
601 } else {
602 super.addAll(elements);
603 }
604 return this;
605 }
606
607 /**
608 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
609 *
610 * @param elements the elements to add to the {@code ImmutableMultiset}
611 * @return this {@code Builder} object
612 * @throws NullPointerException if {@code elements} is null or contains a
613 * null element
614 */
615 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
616 super.addAll(elements);
617 return this;
618 }
619
620 /**
621 * Returns a newly-created {@code ImmutableMultiset} based on the contents
622 * of the {@code Builder}.
623 */
624 @Override public ImmutableMultiset<E> build() {
625 return copyOf(contents);
626 }
627 }
628 }