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
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019
020import com.google.common.annotations.GwtIncompatible;
021import com.google.errorprone.annotations.CanIgnoreReturnValue;
022import java.io.Serializable;
023import java.util.Arrays;
024import java.util.Collection;
025import java.util.Collections;
026import java.util.Comparator;
027import java.util.Iterator;
028import java.util.List;
029
030/**
031 * A {@link SortedMultiset} whose contents will never change, with many other important properties
032 * detailed at {@link ImmutableCollection}.
033 *
034 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
035 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
036 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
037 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
038 * collection will not correctly obey its specification.
039 *
040 * <p>See the Guava User Guide article on <a href=
041 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
042 * immutable collections</a>.
043 *
044 * @author Louis Wasserman
045 * @since 12.0
046 */
047@GwtIncompatible // hasn't been tested yet
048public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E>
049    implements SortedMultiset<E> {
050  // TODO(lowasser): GWT compatibility
051
052  /**
053   * Returns the empty immutable sorted multiset.
054   */
055  @SuppressWarnings("unchecked")
056  public static <E> ImmutableSortedMultiset<E> of() {
057    return (ImmutableSortedMultiset) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
058  }
059
060  /**
061   * Returns an immutable sorted multiset containing a single element.
062   */
063  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) {
064    RegularImmutableSortedSet<E> elementSet =
065        (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element);
066    long[] cumulativeCounts = {0, 1};
067    return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, 1);
068  }
069
070  /**
071   * Returns an immutable sorted multiset containing the given elements sorted by their natural
072   * ordering.
073   *
074   * @throws NullPointerException if any element is null
075   */
076  @SuppressWarnings("unchecked")
077  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) {
078    return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
079  }
080
081  /**
082   * Returns an immutable sorted multiset containing the given elements sorted by their natural
083   * ordering.
084   *
085   * @throws NullPointerException if any element is null
086   */
087  @SuppressWarnings("unchecked")
088  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) {
089    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
090  }
091
092  /**
093   * Returns an immutable sorted multiset containing the given elements sorted by their natural
094   * ordering.
095   *
096   * @throws NullPointerException if any element is null
097   */
098  @SuppressWarnings("unchecked")
099  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
100      E e1, E e2, E e3, E e4) {
101    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
102  }
103
104  /**
105   * Returns an immutable sorted multiset containing the given elements sorted by their natural
106   * ordering.
107   *
108   * @throws NullPointerException if any element is null
109   */
110  @SuppressWarnings("unchecked")
111  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
112      E e1, E e2, E e3, E e4, E e5) {
113    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
114  }
115
116  /**
117   * Returns an immutable sorted multiset containing the given elements sorted by their natural
118   * ordering.
119   *
120   * @throws NullPointerException if any element is null
121   */
122  @SuppressWarnings("unchecked")
123  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
124      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
125    int size = remaining.length + 6;
126    List<E> all = Lists.newArrayListWithCapacity(size);
127    Collections.addAll(all, e1, e2, e3, e4, e5, e6);
128    Collections.addAll(all, remaining);
129    return copyOf(Ordering.natural(), all);
130  }
131
132  /**
133   * Returns an immutable sorted multiset containing the given elements sorted by their natural
134   * ordering.
135   *
136   * @throws NullPointerException if any of {@code elements} is null
137   */
138  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) {
139    return copyOf(Ordering.natural(), Arrays.asList(elements));
140  }
141
142  /**
143   * Returns an immutable sorted multiset containing the given elements sorted by their natural
144   * ordering. To create a copy of a {@code SortedMultiset} that preserves the
145   * comparator, call {@link #copyOfSorted} instead. This method iterates over {@code elements} at
146   * most once.
147   *
148   * <p>Note that if {@code s} is a {@code Multiset<String>}, then {@code
149   * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>}
150   * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)}
151   * returns an {@code ImmutableSortedMultiset<Multiset<String>>} containing one element (the given
152   * multiset itself).
153   *
154   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
155   * safe to do so. The exact circumstances under which a copy will or will not be performed are
156   * undocumented and subject to change.
157   *
158   * <p>This method is not type-safe, as it may be called on elements that are not mutually
159   * comparable.
160   *
161   * @throws ClassCastException if the elements are not mutually comparable
162   * @throws NullPointerException if any of {@code elements} is null
163   */
164  public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) {
165    // Hack around E not being a subtype of Comparable.
166    // Unsafe, see ImmutableSortedMultisetFauxverideShim.
167    @SuppressWarnings("unchecked")
168    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
169    return copyOf(naturalOrder, elements);
170  }
171
172  /**
173   * Returns an immutable sorted multiset containing the given elements sorted by their natural
174   * ordering.
175   *
176   * <p>This method is not type-safe, as it may be called on elements that are not mutually
177   * comparable.
178   *
179   * @throws ClassCastException if the elements are not mutually comparable
180   * @throws NullPointerException if any of {@code elements} is null
181   */
182  public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) {
183    // Hack around E not being a subtype of Comparable.
184    // Unsafe, see ImmutableSortedMultisetFauxverideShim.
185    @SuppressWarnings("unchecked")
186    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
187    return copyOf(naturalOrder, elements);
188  }
189
190  /**
191   * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
192   * Comparator}.
193   *
194   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
195   */
196  public static <E> ImmutableSortedMultiset<E> copyOf(
197      Comparator<? super E> comparator, Iterator<? extends E> elements) {
198    checkNotNull(comparator);
199    return new Builder<E>(comparator).addAll(elements).build();
200  }
201
202  /**
203   * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
204   * Comparator}. This method iterates over {@code elements} at most once.
205   *
206   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
207   * safe to do so. The exact circumstances under which a copy will or will not be performed are
208   * undocumented and subject to change.
209   *
210   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
211   */
212  public static <E> ImmutableSortedMultiset<E> copyOf(
213      Comparator<? super E> comparator, Iterable<? extends E> elements) {
214    if (elements instanceof ImmutableSortedMultiset) {
215      @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts
216      ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements;
217      if (comparator.equals(multiset.comparator())) {
218        if (multiset.isPartialView()) {
219          return copyOfSortedEntries(comparator, multiset.entrySet().asList());
220        } else {
221          return multiset;
222        }
223      }
224    }
225    elements = Lists.newArrayList(elements); // defensive copy
226    TreeMultiset<E> sortedCopy = TreeMultiset.create(checkNotNull(comparator));
227    Iterables.addAll(sortedCopy, elements);
228    return copyOfSortedEntries(comparator, sortedCopy.entrySet());
229  }
230
231  /**
232   * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by
233   * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which
234   * always uses the natural ordering of the elements.
235   *
236   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
237   * safe to do so. The exact circumstances under which a copy will or will not be performed are
238   * undocumented and subject to change.
239   *
240   * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent
241   * collection that is currently being modified by another thread.
242   *
243   * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null
244   */
245  public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) {
246    return copyOfSortedEntries(
247        sortedMultiset.comparator(), Lists.newArrayList(sortedMultiset.entrySet()));
248  }
249
250  private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries(
251      Comparator<? super E> comparator, Collection<Entry<E>> entries) {
252    if (entries.isEmpty()) {
253      return emptyMultiset(comparator);
254    }
255    ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size());
256    long[] cumulativeCounts = new long[entries.size() + 1];
257    int i = 0;
258    for (Entry<E> entry : entries) {
259      elementsBuilder.add(entry.getElement());
260      cumulativeCounts[i + 1] = cumulativeCounts[i] + entry.getCount();
261      i++;
262    }
263    return new RegularImmutableSortedMultiset<E>(
264        new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator),
265        cumulativeCounts,
266        0,
267        entries.size());
268  }
269
270  @SuppressWarnings("unchecked")
271  static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) {
272    if (Ordering.natural().equals(comparator)) {
273      return (ImmutableSortedMultiset<E>) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
274    } else {
275      return new RegularImmutableSortedMultiset<E>(comparator);
276    }
277  }
278
279  ImmutableSortedMultiset() {}
280
281  @Override
282  public final Comparator<? super E> comparator() {
283    return elementSet().comparator();
284  }
285
286  @Override
287  public abstract ImmutableSortedSet<E> elementSet();
288
289  transient ImmutableSortedMultiset<E> descendingMultiset;
290
291  @Override
292  public ImmutableSortedMultiset<E> descendingMultiset() {
293    ImmutableSortedMultiset<E> result = descendingMultiset;
294    if (result == null) {
295      return descendingMultiset =
296          this.isEmpty()
297              ? emptyMultiset(Ordering.from(comparator()).reverse())
298              : new DescendingImmutableSortedMultiset<E>(this);
299    }
300    return result;
301  }
302
303  /**
304   * {@inheritDoc}
305   *
306   * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
307   *
308   * @throws UnsupportedOperationException always
309   * @deprecated Unsupported operation.
310   */
311  @CanIgnoreReturnValue
312  @Deprecated
313  @Override
314  public final Entry<E> pollFirstEntry() {
315    throw new UnsupportedOperationException();
316  }
317
318  /**
319   * {@inheritDoc}
320   *
321   * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
322   *
323   * @throws UnsupportedOperationException always
324   * @deprecated Unsupported operation.
325   */
326  @CanIgnoreReturnValue
327  @Deprecated
328  @Override
329  public final Entry<E> pollLastEntry() {
330    throw new UnsupportedOperationException();
331  }
332
333  @Override
334  public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType);
335
336  @Override
337  public ImmutableSortedMultiset<E> subMultiset(
338      E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) {
339    checkArgument(
340        comparator().compare(lowerBound, upperBound) <= 0,
341        "Expected lowerBound <= upperBound but %s > %s",
342        lowerBound,
343        upperBound);
344    return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType);
345  }
346
347  @Override
348  public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType);
349
350  /**
351   * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the
352   * comparator has a more general type than the set being generated, such as creating a {@code
353   * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder}
354   * constructor instead.
355   *
356   * @throws NullPointerException if {@code comparator} is null
357   */
358  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
359    return new Builder<E>(comparator);
360  }
361
362  /**
363   * Returns a builder that creates immutable sorted multisets whose elements are ordered by the
364   * reverse of their natural ordering.
365   *
366   * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
367   * Comparable<? super E>} as a workaround for javac <a
368   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
369   */
370  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
371    return new Builder<E>(Ordering.natural().reverse());
372  }
373
374  /**
375   * Returns a builder that creates immutable sorted multisets whose elements are ordered by their
376   * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This
377   * method provides more type-safety than {@link #builder}, as it can be called only for classes
378   * that implement {@link Comparable}.
379   *
380   * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
381   * Comparable<? super E>} as a workaround for javac <a
382   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
383   */
384  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
385    return new Builder<E>(Ordering.natural());
386  }
387
388  /**
389   * A builder for creating immutable multiset instances, especially {@code public static final}
390   * multisets ("constant multisets"). Example:
391   *
392   * <pre> {@code
393   *
394   *   public static final ImmutableSortedMultiset<Bean> BEANS =
395   *       new ImmutableSortedMultiset.Builder<Bean>(colorComparator())
396   *           .addCopies(Bean.COCOA, 4)
397   *           .addCopies(Bean.GARDEN, 6)
398   *           .addCopies(Bean.RED, 8)
399   *           .addCopies(Bean.BLACK_EYED, 10)
400   *           .build();}</pre>
401   *
402   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
403   * multiple multisets in series.
404   *
405   * @since 12.0
406   */
407  public static class Builder<E> extends ImmutableMultiset.Builder<E> {
408    /**
409     * Creates a new builder. The returned builder is equivalent to the builder generated by
410     * {@link ImmutableSortedMultiset#orderedBy(Comparator)}.
411     */
412    public Builder(Comparator<? super E> comparator) {
413      super(TreeMultiset.<E>create(checkNotNull(comparator)));
414    }
415
416    /**
417     * Adds {@code element} to the {@code ImmutableSortedMultiset}.
418     *
419     * @param element the element to add
420     * @return this {@code Builder} object
421     * @throws NullPointerException if {@code element} is null
422     */
423    @CanIgnoreReturnValue
424    @Override
425    public Builder<E> add(E element) {
426      super.add(element);
427      return this;
428    }
429
430    /**
431     * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}.
432     *
433     * @param element the element to add
434     * @param occurrences the number of occurrences of the element to add. May be zero, in which
435     *        case no change will be made.
436     * @return this {@code Builder} object
437     * @throws NullPointerException if {@code element} is null
438     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
439     *         would result in more than {@link Integer#MAX_VALUE} occurrences of the element
440     */
441    @CanIgnoreReturnValue
442    @Override
443    public Builder<E> addCopies(E element, int occurrences) {
444      super.addCopies(element, occurrences);
445      return this;
446    }
447
448    /**
449     * Adds or removes the necessary occurrences of an element such that the element attains the
450     * desired count.
451     *
452     * @param element the element to add or remove occurrences of
453     * @param count the desired count of the element in this multiset
454     * @return this {@code Builder} object
455     * @throws NullPointerException if {@code element} is null
456     * @throws IllegalArgumentException if {@code count} is negative
457     */
458    @CanIgnoreReturnValue
459    @Override
460    public Builder<E> setCount(E element, int count) {
461      super.setCount(element, count);
462      return this;
463    }
464
465    /**
466     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
467     *
468     * @param elements the elements to add
469     * @return this {@code Builder} object
470     * @throws NullPointerException if {@code elements} is null or contains a null element
471     */
472    @CanIgnoreReturnValue
473    @Override
474    public Builder<E> add(E... elements) {
475      super.add(elements);
476      return this;
477    }
478
479    /**
480     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
481     *
482     * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset}
483     * @return this {@code Builder} object
484     * @throws NullPointerException if {@code elements} is null or contains a null element
485     */
486    @CanIgnoreReturnValue
487    @Override
488    public Builder<E> addAll(Iterable<? extends E> elements) {
489      super.addAll(elements);
490      return this;
491    }
492
493    /**
494     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
495     *
496     * @param elements the elements to add to the {@code ImmutableSortedMultiset}
497     * @return this {@code Builder} object
498     * @throws NullPointerException if {@code elements} is null or contains a null element
499     */
500    @CanIgnoreReturnValue
501    @Override
502    public Builder<E> addAll(Iterator<? extends E> elements) {
503      super.addAll(elements);
504      return this;
505    }
506
507    /**
508     * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code
509     * Builder}.
510     */
511    @Override
512    public ImmutableSortedMultiset<E> build() {
513      return copyOfSorted((SortedMultiset<E>) contents);
514    }
515  }
516
517  private static final class SerializedForm<E> implements Serializable {
518    final Comparator<? super E> comparator;
519    final E[] elements;
520    final int[] counts;
521
522    @SuppressWarnings("unchecked")
523    SerializedForm(SortedMultiset<E> multiset) {
524      this.comparator = multiset.comparator();
525      int n = multiset.entrySet().size();
526      elements = (E[]) new Object[n];
527      counts = new int[n];
528      int i = 0;
529      for (Entry<E> entry : multiset.entrySet()) {
530        elements[i] = entry.getElement();
531        counts[i] = entry.getCount();
532        i++;
533      }
534    }
535
536    Object readResolve() {
537      int n = elements.length;
538      Builder<E> builder = new Builder<E>(comparator);
539      for (int i = 0; i < n; i++) {
540        builder.addCopies(elements[i], counts[i]);
541      }
542      return builder.build();
543    }
544  }
545
546  @Override
547  Object writeReplace() {
548    return new SerializedForm<E>(this);
549  }
550}