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