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