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