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