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