001 /*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the
010 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
011 * express or implied. See the License for the specific language governing permissions and
012 * limitations under the License.
013 */
014
015 package com.google.common.collect;
016
017 import static com.google.common.base.Preconditions.checkNotNull;
018
019 import com.google.common.annotations.Beta;
020 import com.google.common.annotations.GwtIncompatible;
021
022 import java.io.Serializable;
023 import java.util.Arrays;
024 import java.util.Collection;
025 import java.util.Collections;
026 import java.util.Comparator;
027 import java.util.Iterator;
028 import java.util.List;
029
030 /**
031 * An immutable {@code SortedMultiset} that stores its elements in a sorted array. Some instances
032 * are ordered by an explicit comparator, while others follow the natural sort ordering of their
033 * elements. Either way, null elements are not supported.
034 *
035 * <p>Unlike {@link Multisets#unmodifiableSortedMultiset}, which is a <i>view</i> of a separate
036 * collection that can still change, an instance of {@code ImmutableSortedMultiset} contains its
037 * own private data and will <i>never</i> change. This class is convenient for {@code public static
038 * final} multisets ("constant multisets") and also lets you easily make a "defensive copy" of a
039 * set provided to your class by a caller.
040 *
041 * <p>The multisets returned by the {@link #headMultiset}, {@link #tailMultiset}, and
042 * {@link #subMultiset} methods share the same array as the original multiset, preventing that
043 * array from being garbage collected. If this is a concern, the data may be copied into a
044 * correctly-sized array by calling {@link #copyOfSorted}.
045 *
046 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
047 * {@link #containsAll(Collection)}, and {@link #equals(Object)} implementations must check whether
048 * a provided object is equivalent to an element in the collection. Unlike most collections, an
049 * {@code ImmutableSortedMultiset} doesn't use {@link Object#equals} to determine if two elements
050 * are equivalent. Instead, with an explicit comparator, the following relation determines whether
051 * elements {@code x} and {@code y} are equivalent:
052 *
053 * <pre> {@code
054 *
055 * {(x, y) | comparator.compare(x, y) == 0}}</pre>
056 *
057 * With natural ordering of elements, the following relation determines whether two elements are
058 * equivalent:
059 *
060 * <pre> {@code
061 *
062 * {(x, y) | x.compareTo(y) == 0}}</pre>
063 *
064 * <b>Warning:</b> Like most multisets, an {@code ImmutableSortedMultiset} will not function
065 * correctly if an element is modified after being placed in the multiset. For this reason, and to
066 * avoid general confusion, it is strongly recommended to place only immutable objects into this
067 * collection.
068 *
069 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as it has no public or
070 * protected constructors. Thus, instances of this type are guaranteed to be immutable.
071 *
072 * <p>See the Guava User Guide article on <a href=
073 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
074 * immutable collections</a>.
075 *
076 * @author Louis Wasserman
077 * @since 12.0
078 */
079 @Beta
080 @GwtIncompatible("hasn't been tested yet")
081 public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E>
082 implements SortedMultiset<E> {
083 // TODO(user): GWT compatibility
084
085 private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural();
086
087 private static final ImmutableSortedMultiset<Comparable> NATURAL_EMPTY_MULTISET =
088 new EmptyImmutableSortedMultiset<Comparable>(NATURAL_ORDER);
089
090 /**
091 * Returns the empty immutable sorted multiset.
092 */
093 @SuppressWarnings("unchecked")
094 public static <E> ImmutableSortedMultiset<E> of() {
095 return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET;
096 }
097
098 /**
099 * Returns an immutable sorted multiset containing a single element.
100 */
101 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) {
102 return RegularImmutableSortedMultiset.createFromSorted(
103 NATURAL_ORDER, ImmutableList.of(Multisets.immutableEntry(checkNotNull(element), 1)));
104 }
105
106 /**
107 * Returns an immutable sorted multiset containing the given elements sorted by their natural
108 * ordering.
109 *
110 * @throws NullPointerException if any element is null
111 */
112 @SuppressWarnings("unchecked")
113 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) {
114 return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
115 }
116
117 /**
118 * Returns an immutable sorted multiset containing the given elements sorted by their natural
119 * ordering.
120 *
121 * @throws NullPointerException if any element is null
122 */
123 @SuppressWarnings("unchecked")
124 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) {
125 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
126 }
127
128 /**
129 * Returns an immutable sorted multiset containing the given elements sorted by their natural
130 * ordering.
131 *
132 * @throws NullPointerException if any element is null
133 */
134 @SuppressWarnings("unchecked")
135 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
136 E e1, E e2, E e3, E e4) {
137 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
138 }
139
140 /**
141 * Returns an immutable sorted multiset containing the given elements sorted by their natural
142 * ordering.
143 *
144 * @throws NullPointerException if any element is null
145 */
146 @SuppressWarnings("unchecked")
147 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
148 E e1, E e2, E e3, E e4, E e5) {
149 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
150 }
151
152 /**
153 * Returns an immutable sorted multiset containing the given elements sorted by their natural
154 * ordering.
155 *
156 * @throws NullPointerException if any element is null
157 */
158 @SuppressWarnings("unchecked")
159 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
160 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
161 int size = remaining.length + 6;
162 List<E> all = Lists.newArrayListWithCapacity(size);
163 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
164 Collections.addAll(all, remaining);
165 return copyOf(Ordering.natural(), all);
166 }
167
168 /**
169 * Returns an immutable sorted multiset containing the given elements sorted by their natural
170 * ordering.
171 *
172 * @throws NullPointerException if any of {@code elements} is null
173 */
174 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) {
175 return copyOf(Ordering.natural(), Arrays.asList(elements));
176 }
177
178 /**
179 * Returns an immutable sorted multiset containing the given elements sorted by their natural
180 * ordering. To create a copy of a {@code SortedMultiset} that preserves the
181 * comparator, call {@link #copyOfSorted} instead. This method iterates over {@code elements} at
182 * most once.
183 *
184 * <p>Note that if {@code s} is a {@code multiset<String>}, then {@code
185 * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>}
186 * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)}
187 * returns an {@code ImmutableSortedMultiset<multiset<String>>} containing one element (the given
188 * multiset itself).
189 *
190 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
191 * safe to do so. The exact circumstances under which a copy will or will not be performed are
192 * undocumented and subject to change.
193 *
194 * <p>This method is not type-safe, as it may be called on elements that are not mutually
195 * comparable.
196 *
197 * @throws ClassCastException if the elements are not mutually comparable
198 * @throws NullPointerException if any of {@code elements} is null
199 */
200 public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) {
201 // Hack around E not being a subtype of Comparable.
202 // Unsafe, see ImmutableSortedMultisetFauxverideShim.
203 @SuppressWarnings("unchecked")
204 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
205 return copyOf(naturalOrder, elements);
206 }
207
208 /**
209 * Returns an immutable sorted multiset containing the given elements sorted by their natural
210 * ordering.
211 *
212 * <p>This method is not type-safe, as it may be called on elements that are not mutually
213 * comparable.
214 *
215 * @throws ClassCastException if the elements are not mutually comparable
216 * @throws NullPointerException if any of {@code elements} is null
217 */
218 public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) {
219 // Hack around E not being a subtype of Comparable.
220 // Unsafe, see ImmutableSortedMultisetFauxverideShim.
221 @SuppressWarnings("unchecked")
222 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
223 return copyOfInternal(naturalOrder, elements);
224 }
225
226 /**
227 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
228 * Comparator}.
229 *
230 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
231 */
232 public static <E> ImmutableSortedMultiset<E> copyOf(
233 Comparator<? super E> comparator, Iterator<? extends E> elements) {
234 checkNotNull(comparator);
235 return copyOfInternal(comparator, elements);
236 }
237
238 /**
239 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
240 * Comparator}. This method iterates over {@code elements} at most once.
241 *
242 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
243 * safe to do so. The exact circumstances under which a copy will or will not be performed are
244 * undocumented and subject to change.
245 *
246 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
247 */
248 public static <E> ImmutableSortedMultiset<E> copyOf(
249 Comparator<? super E> comparator, Iterable<? extends E> elements) {
250 checkNotNull(comparator);
251 return copyOfInternal(comparator, elements);
252 }
253
254 /**
255 * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by
256 * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which
257 * always uses the natural ordering of the elements.
258 *
259 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
260 * safe to do so. The exact circumstances under which a copy will or will not be performed are
261 * undocumented and subject to change.
262 *
263 * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent
264 * collection that is currently being modified by another thread.
265 *
266 * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null
267 */
268 @SuppressWarnings("unchecked")
269 public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) {
270 Comparator<? super E> comparator = sortedMultiset.comparator();
271 if (comparator == null) {
272 comparator = (Comparator<? super E>) NATURAL_ORDER;
273 }
274 return copyOfInternal(comparator, sortedMultiset);
275 }
276
277 @SuppressWarnings("unchecked")
278 private static <E> ImmutableSortedMultiset<E> copyOfInternal(
279 Comparator<? super E> comparator, Iterable<? extends E> iterable) {
280 if (SortedIterables.hasSameComparator(comparator, iterable)
281 && iterable instanceof ImmutableSortedMultiset<?>) {
282 ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) iterable;
283 if (!multiset.isPartialView()) {
284 return (ImmutableSortedMultiset<E>) iterable;
285 }
286 }
287 ImmutableList<Entry<E>> entries =
288 (ImmutableList) ImmutableList.copyOf(SortedIterables.sortedCounts(comparator, iterable));
289 if (entries.isEmpty()) {
290 return emptyMultiset(comparator);
291 }
292 verifyEntries(entries);
293 return RegularImmutableSortedMultiset.createFromSorted(comparator, entries);
294 }
295
296 private static <E> ImmutableSortedMultiset<E> copyOfInternal(
297 Comparator<? super E> comparator, Iterator<? extends E> iterator) {
298 @SuppressWarnings("unchecked") // We can safely cast from IL<Entry<? extends E>> to IL<Entry<E>>
299 ImmutableList<Entry<E>> entries =
300 (ImmutableList) ImmutableList.copyOf(SortedIterables.sortedCounts(comparator, iterator));
301 if (entries.isEmpty()) {
302 return emptyMultiset(comparator);
303 }
304 verifyEntries(entries);
305 return RegularImmutableSortedMultiset.createFromSorted(comparator, entries);
306 }
307
308 private static <E> void verifyEntries(Collection<Entry<E>> entries) {
309 for (Entry<E> entry : entries) {
310 checkNotNull(entry.getElement());
311 }
312 }
313
314 @SuppressWarnings("unchecked")
315 static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) {
316 if (NATURAL_ORDER.equals(comparator)) {
317 return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET;
318 }
319 return new EmptyImmutableSortedMultiset<E>(comparator);
320 }
321
322 private final transient Comparator<? super E> comparator;
323
324 ImmutableSortedMultiset(Comparator<? super E> comparator) {
325 this.comparator = checkNotNull(comparator);
326 }
327
328 @Override
329 public Comparator<? super E> comparator() {
330 return comparator;
331 }
332
333 // Pretend the comparator can compare anything. If it turns out it can't
334 // compare two elements, it'll throw a CCE. Only methods that are specified to
335 // throw CCE should call this.
336 @SuppressWarnings("unchecked")
337 Comparator<Object> unsafeComparator() {
338 return (Comparator<Object>) comparator;
339 }
340
341 private transient Comparator<? super E> reverseComparator;
342
343 Comparator<? super E> reverseComparator() {
344 Comparator<? super E> result = reverseComparator;
345 if (result == null) {
346 return reverseComparator = Ordering.from(comparator).<E>reverse();
347 }
348 return result;
349 }
350
351 private transient ImmutableSortedSet<E> elementSet;
352
353 @Override
354 public ImmutableSortedSet<E> elementSet() {
355 ImmutableSortedSet<E> result = elementSet;
356 if (result == null) {
357 return elementSet = createElementSet();
358 }
359 return result;
360 }
361
362 abstract ImmutableSortedSet<E> createElementSet();
363
364 abstract ImmutableSortedSet<E> createDescendingElementSet();
365
366 transient ImmutableSortedMultiset<E> descendingMultiset;
367
368 @Override
369 public ImmutableSortedMultiset<E> descendingMultiset() {
370 ImmutableSortedMultiset<E> result = descendingMultiset;
371 if (result == null) {
372 return descendingMultiset = new DescendingImmutableSortedMultiset<E>(this);
373 }
374 return result;
375 }
376
377 /**
378 * {@inheritDoc}
379 *
380 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
381 *
382 * @throws UnsupportedOperationException always
383 */
384 @Override
385 public final Entry<E> pollFirstEntry() {
386 throw new UnsupportedOperationException();
387 }
388
389 /**
390 * {@inheritDoc}
391 *
392 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
393 *
394 * @throws UnsupportedOperationException always
395 */
396 @Override
397 public Entry<E> pollLastEntry() {
398 throw new UnsupportedOperationException();
399 }
400
401 @Override
402 public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType);
403
404 @Override
405 public ImmutableSortedMultiset<E> subMultiset(
406 E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) {
407 return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType);
408 }
409
410 @Override
411 public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType);
412
413 /**
414 * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the
415 * comparator has a more general type than the set being generated, such as creating a {@code
416 * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder}
417 * constructor instead.
418 *
419 * @throws NullPointerException if {@code comparator} is null
420 */
421 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
422 return new Builder<E>(comparator);
423 }
424
425 /**
426 * Returns a builder that creates immutable sorted multisets whose elements are ordered by the
427 * reverse of their natural ordering.
428 *
429 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code
430 * Comparable<? super E>} as a workaround for javac <a
431 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
432 */
433 public static <E extends Comparable<E>> Builder<E> reverseOrder() {
434 return new Builder<E>(Ordering.natural().reverse());
435 }
436
437 /**
438 * Returns a builder that creates immutable sorted multisets whose elements are ordered by their
439 * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This
440 * method provides more type-safety than {@link #builder}, as it can be called only for classes
441 * that implement {@link Comparable}.
442 *
443 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code
444 * Comparable<? super E>} as a workaround for javac <a
445 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
446 */
447 public static <E extends Comparable<E>> Builder<E> naturalOrder() {
448 return new Builder<E>(Ordering.natural());
449 }
450
451 /**
452 * A builder for creating immutable multiset instances, especially {@code public static final}
453 * multisets ("constant multisets"). Example:
454 *
455 * <pre> {@code
456 *
457 * public static final ImmutableSortedMultiset<Bean> BEANS =
458 * new ImmutableSortedMultiset.Builder<Bean>()
459 * .addCopies(Bean.COCOA, 4)
460 * .addCopies(Bean.GARDEN, 6)
461 * .addCopies(Bean.RED, 8)
462 * .addCopies(Bean.BLACK_EYED, 10)
463 * .build();}</pre>
464 *
465 * Builder instances can be reused; it is safe to call {@link #build} multiple times to build
466 * multiple multisets in series.
467 *
468 * @since 12.0
469 */
470 public static class Builder<E> extends ImmutableMultiset.Builder<E> {
471 private final Comparator<? super E> comparator;
472
473 /**
474 * Creates a new builder. The returned builder is equivalent to the builder generated by
475 * {@link ImmutableSortedMultiset#orderedBy(Comparator)}.
476 */
477 public Builder(Comparator<? super E> comparator) {
478 super(TreeMultiset.<E>create(comparator));
479 this.comparator = checkNotNull(comparator);
480 }
481
482 /**
483 * Adds {@code element} to the {@code ImmutableSortedMultiset}.
484 *
485 * @param element the element to add
486 * @return this {@code Builder} object
487 * @throws NullPointerException if {@code element} is null
488 */
489 @Override
490 public Builder<E> add(E element) {
491 super.add(element);
492 return this;
493 }
494
495 /**
496 * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}.
497 *
498 * @param element the element to add
499 * @param occurrences the number of occurrences of the element to add. May be zero, in which
500 * case no change will be made.
501 * @return this {@code Builder} object
502 * @throws NullPointerException if {@code element} is null
503 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
504 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element
505 */
506 @Override
507 public Builder<E> addCopies(E element, int occurrences) {
508 super.addCopies(element, occurrences);
509 return this;
510 }
511
512 /**
513 * Adds or removes the necessary occurrences of an element such that the element attains the
514 * desired count.
515 *
516 * @param element the element to add or remove occurrences of
517 * @param count the desired count of the element in this multiset
518 * @return this {@code Builder} object
519 * @throws NullPointerException if {@code element} is null
520 * @throws IllegalArgumentException if {@code count} is negative
521 */
522 @Override
523 public Builder<E> setCount(E element, int count) {
524 super.setCount(element, count);
525 return this;
526 }
527
528 /**
529 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
530 *
531 * @param elements the elements to add
532 * @return this {@code Builder} object
533 * @throws NullPointerException if {@code elements} is null or contains a null element
534 */
535 @Override
536 public Builder<E> add(E... elements) {
537 super.add(elements);
538 return this;
539 }
540
541 /**
542 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
543 *
544 * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset}
545 * @return this {@code Builder} object
546 * @throws NullPointerException if {@code elements} is null or contains a null element
547 */
548 @Override
549 public Builder<E> addAll(Iterable<? extends E> elements) {
550 super.addAll(elements);
551 return this;
552 }
553
554 /**
555 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
556 *
557 * @param elements the elements to add to the {@code ImmutableSortedMultiset}
558 * @return this {@code Builder} object
559 * @throws NullPointerException if {@code elements} is null or contains a null element
560 */
561 @Override
562 public Builder<E> addAll(Iterator<? extends E> elements) {
563 super.addAll(elements);
564 return this;
565 }
566
567 /**
568 * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code
569 * Builder}.
570 */
571 @Override
572 public ImmutableSortedMultiset<E> build() {
573 return copyOf(comparator, contents);
574 }
575 }
576
577 private static final class SerializedForm implements Serializable {
578 Comparator comparator;
579 Object[] elements;
580 int[] counts;
581
582 SerializedForm(SortedMultiset<?> multiset) {
583 this.comparator = multiset.comparator();
584 int n = multiset.entrySet().size();
585 elements = new Object[n];
586 counts = new int[n];
587 int i = 0;
588 for (Entry<?> entry : multiset.entrySet()) {
589 elements[i] = entry.getElement();
590 counts[i] = entry.getCount();
591 i++;
592 }
593 }
594
595 @SuppressWarnings("unchecked")
596 Object readResolve() {
597 int n = elements.length;
598 Builder<Object> builder = orderedBy(comparator);
599 for (int i = 0; i < n; i++) {
600 builder.addCopies(elements[i], counts[i]);
601 }
602 return builder.build();
603 }
604 }
605
606 @Override
607 Object writeReplace() {
608 return new SerializedForm(this);
609 }
610 }