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