001 /*
002 * Copyright (C) 2008 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.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, emulated = true)
052 // TODO(user): write an efficient asList() implementation
053 public class ImmutableMultiset<E> extends ImmutableCollection<E>
054 implements Multiset<E> {
055
056 /**
057 * Returns the empty immutable multiset.
058 */
059 @SuppressWarnings("unchecked") // all supported methods are covariant
060 public static <E> ImmutableMultiset<E> of() {
061 return (ImmutableMultiset<E>) EmptyImmutableMultiset.INSTANCE;
062 }
063
064 /**
065 * Returns an immutable multiset containing a single element.
066 *
067 * @throws NullPointerException if {@code element} is null
068 * @since 6 (source-compatible since release 2)
069 */
070 @SuppressWarnings("unchecked") // generic array created but never written
071 public static <E> ImmutableMultiset<E> of(E element) {
072 return copyOfInternal(element);
073 }
074
075 /**
076 * Returns an immutable multiset containing the given elements, in order.
077 *
078 * @throws NullPointerException if any element is null
079 * @since 6 (source-compatible since release 2)
080 */
081 @SuppressWarnings("unchecked") //
082 public static <E> ImmutableMultiset<E> of(E e1, E e2) {
083 return copyOfInternal(e1, e2);
084 }
085
086 /**
087 * Returns an immutable multiset containing the given elements, in order.
088 *
089 * @throws NullPointerException if any element is null
090 * @since 6 (source-compatible since release 2)
091 */
092 @SuppressWarnings("unchecked") //
093 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
094 return copyOfInternal(e1, e2, e3);
095 }
096
097 /**
098 * Returns an immutable multiset containing the given elements, in order.
099 *
100 * @throws NullPointerException if any element is null
101 * @since 6 (source-compatible since release 2)
102 */
103 @SuppressWarnings("unchecked") //
104 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
105 return copyOfInternal(e1, e2, e3, e4);
106 }
107
108 /**
109 * Returns an immutable multiset containing the given elements, in order.
110 *
111 * @throws NullPointerException if any element is null
112 * @since 6 (source-compatible since release 2)
113 */
114 @SuppressWarnings("unchecked") //
115 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
116 return copyOfInternal(e1, e2, e3, e4, e5);
117 }
118
119 /**
120 * Returns an immutable multiset containing the given elements, in order.
121 *
122 * @throws NullPointerException if any element is null
123 * @since 6 (source-compatible since release 2)
124 */
125 @SuppressWarnings("unchecked") //
126 public static <E> ImmutableMultiset<E> of(
127 E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
128 int size = others.length + 6;
129 List<E> all = new ArrayList<E>(size);
130 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
131 Collections.addAll(all, others);
132 return copyOf(all);
133 }
134
135 /**
136 * Returns an immutable multiset containing the given elements.
137 *
138 * <p>The multiset is ordered by the first occurrence of each element. For
139 * example, {@code ImmutableMultiset.of(2, 3, 1, 3)} yields a multiset with
140 * elements in the order {@code 2, 3, 3, 1}.
141 *
142 * @throws NullPointerException if any of {@code elements} is null
143 * @deprecated use {@link #copyOf(Object[])}. <b>This method is scheduled for
144 * deletion in January 2012.</b>
145 * @since 2 (changed from varargs in release 6)
146 */
147 @Deprecated
148 public static <E> ImmutableMultiset<E> of(E[] elements) {
149 return copyOf(Arrays.asList(elements));
150 }
151
152 /**
153 * Returns an immutable multiset containing the given elements.
154 *
155 * <p>The multiset is ordered by the first occurrence of each element. For
156 * example, {@code ImmutableMultiset.copyOf([2, 3, 1, 3])} yields a multiset
157 * with elements in the order {@code 2, 3, 3, 1}.
158 *
159 * @throws NullPointerException if any of {@code elements} is null
160 * @since 6
161 */
162 public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
163 return copyOf(Arrays.asList(elements));
164 }
165
166 /**
167 * Returns an immutable multiset containing the given elements.
168 *
169 * <p>The multiset is ordered by the first occurrence of each element. For
170 * example, {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3))} yields
171 * a multiset with elements in the order {@code 2, 3, 3, 1}.
172 *
173 * <p>Despite the method name, this method attempts to avoid actually copying
174 * the data when it is safe to do so. The exact circumstances under which a
175 * copy will or will not be performed are undocumented and subject to change.
176 *
177 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
178 * is an {@code ImmutableMultiset}, no copy will actually be performed, and
179 * the given multiset itself will be returned.
180 *
181 * @throws NullPointerException if any of {@code elements} is null
182 */
183 public static <E> ImmutableMultiset<E> copyOf(
184 Iterable<? extends E> elements) {
185 if (elements instanceof ImmutableMultiset) {
186 @SuppressWarnings("unchecked") // all supported methods are covariant
187 ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
188 if (!result.isPartialView()) {
189 return result;
190 }
191 }
192
193 Multiset<? extends E> multiset = (elements instanceof Multiset)
194 ? Multisets.cast(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 @Override boolean isPartialView() {
264 return map.isPartialView();
265 }
266
267 @Override
268 public int count(@Nullable Object element) {
269 Integer value = map.get(element);
270 return (value == null) ? 0 : value;
271 }
272
273 @Override public UnmodifiableIterator<E> iterator() {
274 final Iterator<Map.Entry<E, Integer>> mapIterator
275 = map.entrySet().iterator();
276
277 return new UnmodifiableIterator<E>() {
278 int remaining;
279 E element;
280
281 @Override
282 public boolean hasNext() {
283 return (remaining > 0) || mapIterator.hasNext();
284 }
285
286 @Override
287 public E next() {
288 if (remaining <= 0) {
289 Map.Entry<E, Integer> entry = mapIterator.next();
290 element = entry.getKey();
291 remaining = entry.getValue();
292 }
293 remaining--;
294 return element;
295 }
296 };
297 }
298
299 @Override
300 public int size() {
301 return size;
302 }
303
304 @Override public boolean contains(@Nullable Object element) {
305 return map.containsKey(element);
306 }
307
308 /**
309 * Guaranteed to throw an exception and leave the collection unmodified.
310 *
311 * @throws UnsupportedOperationException always
312 */
313 @Override
314 public int add(E 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 @Override
324 public int remove(Object element, int occurrences) {
325 throw new UnsupportedOperationException();
326 }
327
328 /**
329 * Guaranteed to throw an exception and leave the collection unmodified.
330 *
331 * @throws UnsupportedOperationException always
332 */
333 @Override
334 public int setCount(E element, int count) {
335 throw new UnsupportedOperationException();
336 }
337
338 /**
339 * Guaranteed to throw an exception and leave the collection unmodified.
340 *
341 * @throws UnsupportedOperationException always
342 */
343 @Override
344 public boolean setCount(E element, int oldCount, int newCount) {
345 throw new UnsupportedOperationException();
346 }
347
348 @Override public boolean equals(@Nullable Object object) {
349 if (object == this) {
350 return true;
351 }
352 if (object instanceof Multiset) {
353 Multiset<?> that = (Multiset<?>) object;
354 if (this.size() != that.size()) {
355 return false;
356 }
357 for (Entry<?> entry : that.entrySet()) {
358 if (count(entry.getElement()) != entry.getCount()) {
359 return false;
360 }
361 }
362 return true;
363 }
364 return false;
365 }
366
367 @Override public int hashCode() {
368 // could cache this, but not considered worthwhile to do so
369 return map.hashCode();
370 }
371
372 @Override public String toString() {
373 return entrySet().toString();
374 }
375
376 @Override
377 public Set<E> elementSet() {
378 return map.keySet();
379 }
380
381 private transient ImmutableSet<Entry<E>> entrySet;
382
383 @Override
384 public Set<Entry<E>> entrySet() {
385 ImmutableSet<Entry<E>> es = entrySet;
386 return (es == null) ? (entrySet = new EntrySet<E>(this)) : es;
387 }
388
389 private static class EntrySet<E> extends ImmutableSet<Entry<E>> {
390 final ImmutableMultiset<E> multiset;
391
392 public EntrySet(ImmutableMultiset<E> multiset) {
393 this.multiset = multiset;
394 }
395
396 @Override public UnmodifiableIterator<Entry<E>> iterator() {
397 final Iterator<Map.Entry<E, Integer>> mapIterator
398 = multiset.map.entrySet().iterator();
399 return new UnmodifiableIterator<Entry<E>>() {
400 @Override
401 public boolean hasNext() {
402 return mapIterator.hasNext();
403 }
404 @Override
405 public Entry<E> next() {
406 Map.Entry<E, Integer> mapEntry = mapIterator.next();
407 return
408 Multisets.immutableEntry(mapEntry.getKey(), mapEntry.getValue());
409 }
410 };
411 }
412
413 @Override
414 public int size() {
415 return multiset.map.size();
416 }
417
418 @Override boolean isPartialView() {
419 return multiset.isPartialView();
420 }
421
422 @Override public boolean contains(Object o) {
423 if (o instanceof Entry) {
424 Entry<?> entry = (Entry<?>) o;
425 if (entry.getCount() <= 0) {
426 return false;
427 }
428 int count = multiset.count(entry.getElement());
429 return count == entry.getCount();
430 }
431 return false;
432 }
433
434 // TODO(hhchan): Revert once this class is emulated in GWT.
435 @Override public Object[] toArray() {
436 Object[] newArray = new Object[size()];
437 return toArray(newArray);
438 }
439
440 // TODO(hhchan): Revert once this class is emulated in GWT.
441 @Override public <T> T[] toArray(T[] other) {
442 int size = size();
443 if (other.length < size) {
444 other = ObjectArrays.newArray(other, size);
445 } else if (other.length > size) {
446 other[size] = null;
447 }
448
449 // Writes will produce ArrayStoreException when the toArray() doc requires
450 Object[] otherAsObjectArray = other;
451 int index = 0;
452 for (Entry<?> element : this) {
453 otherAsObjectArray[index++] = element;
454 }
455 return other;
456 }
457
458 @Override public int hashCode() {
459 return multiset.map.hashCode();
460 }
461
462 @GwtIncompatible("not needed in emulated source.")
463 @Override Object writeReplace() {
464 return this;
465 }
466
467 private static final long serialVersionUID = 0;
468 }
469
470 /**
471 * @serialData the number of distinct elements, the first element, its count,
472 * the second element, its count, and so on
473 */
474 @GwtIncompatible("java.io.ObjectOutputStream")
475 private void writeObject(ObjectOutputStream stream) throws IOException {
476 stream.defaultWriteObject();
477 Serialization.writeMultiset(this, stream);
478 }
479
480 @GwtIncompatible("java.io.ObjectInputStream")
481 private void readObject(ObjectInputStream stream)
482 throws IOException, ClassNotFoundException {
483 stream.defaultReadObject();
484 int entryCount = stream.readInt();
485 ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
486 long tmpSize = 0;
487 for (int i = 0; i < entryCount; i++) {
488 @SuppressWarnings("unchecked") // reading data stored by writeMultiset
489 E element = (E) stream.readObject();
490 int count = stream.readInt();
491 if (count <= 0) {
492 throw new InvalidObjectException("Invalid count " + count);
493 }
494 builder.put(element, count);
495 tmpSize += count;
496 }
497
498 FieldSettersHolder.MAP_FIELD_SETTER.set(this, builder.build());
499 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, Ints.saturatedCast(tmpSize));
500 }
501
502 @GwtIncompatible("java serialization not supported.")
503 @Override Object writeReplace() {
504 return this;
505 }
506
507 private static final long serialVersionUID = 0;
508
509 /**
510 * Returns a new builder. The generated builder is equivalent to the builder
511 * created by the {@link Builder} constructor.
512 */
513 public static <E> Builder<E> builder() {
514 return new Builder<E>();
515 }
516
517 /**
518 * A builder for creating immutable multiset instances, especially {@code
519 * public static final} multisets ("constant multisets"). Example:
520 * <pre> {@code
521 *
522 * public static final ImmutableMultiset<Bean> BEANS =
523 * new ImmutableMultiset.Builder<Bean>()
524 * .addCopies(Bean.COCOA, 4)
525 * .addCopies(Bean.GARDEN, 6)
526 * .addCopies(Bean.RED, 8)
527 * .addCopies(Bean.BLACK_EYED, 10)
528 * .build();}</pre>
529 *
530 * Builder instances can be reused; it is safe to call {@link #build} multiple
531 * times to build multiple multisets in series. Each multiset is a superset of
532 * the multiset created before it.
533 *
534 * @since 2 (imported from Google Collections Library)
535 */
536 public static final class Builder<E> extends ImmutableCollection.Builder<E> {
537 private final Multiset<E> contents = LinkedHashMultiset.create();
538
539 /**
540 * Creates a new builder. The returned builder is equivalent to the builder
541 * generated by {@link ImmutableMultiset#builder}.
542 */
543 public Builder() {}
544
545 /**
546 * Adds {@code element} to the {@code ImmutableMultiset}.
547 *
548 * @param element the element to add
549 * @return this {@code Builder} object
550 * @throws NullPointerException if {@code element} is null
551 */
552 @Override public Builder<E> add(E element) {
553 contents.add(checkNotNull(element));
554 return this;
555 }
556
557 /**
558 * Adds a number of occurrences of an element to this {@code
559 * ImmutableMultiset}.
560 *
561 * @param element the element to add
562 * @param occurrences the number of occurrences of the element to add. May
563 * be zero, in which case no change will be made.
564 * @return this {@code Builder} object
565 * @throws NullPointerException if {@code element} is null
566 * @throws IllegalArgumentException if {@code occurrences} is negative, or
567 * if this operation would result in more than {@link Integer#MAX_VALUE}
568 * occurrences of the element
569 */
570 public Builder<E> addCopies(E element, int occurrences) {
571 contents.add(checkNotNull(element), occurrences);
572 return this;
573 }
574
575 /**
576 * Adds or removes the necessary occurrences of an element such that the
577 * element attains the desired count.
578 *
579 * @param element the element to add or remove occurrences of
580 * @param count the desired count of the element in this multiset
581 * @return this {@code Builder} object
582 * @throws NullPointerException if {@code element} is null
583 * @throws IllegalArgumentException if {@code count} is negative
584 */
585 public Builder<E> setCount(E element, int count) {
586 contents.setCount(checkNotNull(element), count);
587 return this;
588 }
589
590 /**
591 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
592 *
593 * @param elements the elements to add
594 * @return this {@code Builder} object
595 * @throws NullPointerException if {@code elements} is null or contains a
596 * null element
597 */
598 @Override public Builder<E> add(E... elements) {
599 super.add(elements);
600 return this;
601 }
602
603 /**
604 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
605 *
606 * @param elements the {@code Iterable} to add to the {@code
607 * ImmutableMultiset}
608 * @return this {@code Builder} object
609 * @throws NullPointerException if {@code elements} is null or contains a
610 * null element
611 */
612 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
613 if (elements instanceof Multiset) {
614 Multiset<? extends E> multiset = Multisets.cast(elements);
615 for (Entry<? extends E> entry : multiset.entrySet()) {
616 addCopies(entry.getElement(), entry.getCount());
617 }
618 } else {
619 super.addAll(elements);
620 }
621 return this;
622 }
623
624 /**
625 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
626 *
627 * @param elements the elements to add to the {@code ImmutableMultiset}
628 * @return this {@code Builder} object
629 * @throws NullPointerException if {@code elements} is null or contains a
630 * null element
631 */
632 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
633 super.addAll(elements);
634 return this;
635 }
636
637 /**
638 * Returns a newly-created {@code ImmutableMultiset} based on the contents
639 * of the {@code Builder}.
640 */
641 @Override public ImmutableMultiset<E> build() {
642 return copyOf(contents);
643 }
644 }
645 }