    001    /*
    002     * Copyright (C) 2007 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkNotNull;
    020
    021    import com.google.common.annotations.GwtCompatible;
    022    import com.google.common.annotations.GwtIncompatible;
    023
    024    import java.io.IOException;
    025    import java.io.ObjectInputStream;
    026    import java.io.ObjectOutputStream;
    027    import java.util.Comparator;
    028    import java.util.Iterator;
    029    import java.util.Set;
    030    import java.util.SortedMap;
    031    import java.util.SortedSet;
    032    import java.util.TreeMap;
    033
    034    import javax.annotation.Nullable;
    035
    036    /**
    037     * A multiset which maintains the ordering of its elements, according to either
    038     * their natural order or an explicit {@link Comparator}. In all cases, this
    039     * implementation uses {@link Comparable#compareTo} or {@link
    040     * Comparator#compare} instead of {@link Object#equals} to determine
    041     * equivalence of instances.
    042     *
    043     * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as
    044     * explained by the {@link Comparable} class specification. Otherwise, the
    045     * resulting multiset will violate the {@link java.util.Collection} contract,
    046     * which is specified in terms of {@link Object#equals}.
    047     *
    048     * @author Neal Kanodia
    049     * @author Jared Levy
    050     * @since 2.0 (imported from Google Collections Library)
    051     */
    052    @GwtCompatible(emulated = true)
    053    @SuppressWarnings("serial") // we're overriding default serialization
    054    public final class TreeMultiset<E> extends AbstractMapBasedMultiset<E>
    055        implements SortedIterable<E> {
    056
    057      /**
    058       * Creates a new, empty multiset, sorted according to the elements' natural
    059       * order. All elements inserted into the multiset must implement the
    060       * {@code Comparable} interface. Furthermore, all such elements must be
    061       * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
    062       * {@code ClassCastException} for any elements {@code e1} and {@code e2} in
    063       * the multiset. If the user attempts to add an element to the multiset that
    064       * violates this constraint (for example, the user attempts to add a string
    065       * element to a set whose elements are integers), the {@code add(Object)}
    066       * call will throw a {@code ClassCastException}.
    067       *
    068       * <p>The type specification is {@code <E extends Comparable>}, instead of the
    069       * more specific {@code <E extends Comparable<? super E>>}, to support
    070       * classes defined without generics.
    071       */
    072      public static <E extends Comparable> TreeMultiset<E> create() {
    073        return new TreeMultiset<E>();
    074      }
    075
    076      /**
    077       * Creates a new, empty multiset, sorted according to the specified
    078       * comparator. All elements inserted into the multiset must be <i>mutually
    079       * comparable</i> by the specified comparator: {@code comparator.compare(e1,
    080       * e2)} must not throw a {@code ClassCastException} for any elements {@code
    081       * e1} and {@code e2} in the multiset. If the user attempts to add an element
    082       * to the multiset that violates this constraint, the {@code add(Object)} call
    083       * will throw a {@code ClassCastException}.
    084       *
    085       * @param comparator the comparator that will be used to sort this multiset. A
    086       *     null value indicates that the elements' <i>natural ordering</i> should
    087       *     be used.
    088       */
    089      public static <E> TreeMultiset<E> create(
    090          @Nullable Comparator<? super E> comparator) {
    091
    092        return (comparator == null)
    093               ? new TreeMultiset<E>()
    094               : new TreeMultiset<E>(comparator);
    095      }
    096
    097      /**
    098       * Returns an iterator over the elements contained in this collection.
    099       */
    100      @Override
    101      public Iterator<E> iterator() {
    102        // Needed to avoid Javadoc bug.
    103        return super.iterator();
    104      }
    105
    106      /**
    107       * Creates an empty multiset containing the given initial elements, sorted
    108       * according to the elements' natural order.
    109       *
    110       * <p>This implementation is highly efficient when {@code elements} is itself
    111       * a {@link Multiset}.
    112       *
    113       * <p>The type specification is {@code <E extends Comparable>}, instead of the
    114       * more specific {@code <E extends Comparable<? super E>>}, to support
    115       * classes defined without generics.
    116       */
    117      public static <E extends Comparable> TreeMultiset<E> create(
    118          Iterable<? extends E> elements) {
    119        TreeMultiset<E> multiset = create();
    120        Iterables.addAll(multiset, elements);
    121        return multiset;
    122      }
    123
    124      private final Comparator<? super E> comparator;
    125
    126      @SuppressWarnings("unchecked")
    127      private TreeMultiset() {
    128        this((Comparator) Ordering.natural());
    129      }
    130
    131      private TreeMultiset(@Nullable Comparator<? super E> comparator) {
    132        super(new TreeMap<E, Count>(checkNotNull(comparator)));
    133        this.comparator = comparator;
    134      }
    135
    136      /**
    137       * Returns the comparator associated with this multiset.
    138       *
    139       * @since 11.0
    140       */
    141      @Override
    142      public Comparator<? super E> comparator() {
    143        return comparator;
    144      }
    145
    146      /**
    147       * {@inheritDoc}
    148       *
    149       * <p>In {@code TreeMultiset}, the return type of this method is narrowed
    150       * from {@link Set} to {@link SortedSet}.
    151       */
    152      @Override public SortedSet<E> elementSet() {
    153        return (SortedSet<E>) super.elementSet();
    154      }
    155
    156      @Override public int count(@Nullable Object element) {
    157        try {
    158          return super.count(element);
    159        } catch (NullPointerException e) {
    160          return 0;
    161        } catch (ClassCastException e) {
    162          return 0;
    163        }
    164      }
    165
    166      @Override
    167      public int add(E element, int occurrences) {
    168        if (element == null) {
    169          comparator.compare(element, element);
    170        }
    171        return super.add(element, occurrences);
    172      }
    173
    174      @Override Set<E> createElementSet() {
    175        return new SortedMapBasedElementSet(
    176            (SortedMap<E, Count>) backingMap());
    177      }
    178
    179      private class SortedMapBasedElementSet extends MapBasedElementSet
    180          implements SortedSet<E>, SortedIterable<E> {
    181
    182        SortedMapBasedElementSet(SortedMap<E, Count> map) {
    183          super(map);
    184        }
    185
    186        SortedMap<E, Count> sortedMap() {
    187          return (SortedMap<E, Count>) getMap();
    188        }
    189
    190        /**
    191         * {@inheritDoc}
    192         *
    193         * @since 10.0
    194         */
    195        @Override
    196        public Comparator<? super E> comparator() {
    197          return sortedMap().comparator();
    198        }
    199
    200        @Override
    201        public E first() {
    202          return sortedMap().firstKey();
    203        }
    204
    205        @Override
    206        public E last() {
    207          return sortedMap().lastKey();
    208        }
    209
    210        @Override
    211        public SortedSet<E> headSet(E toElement) {
    212          return new SortedMapBasedElementSet(sortedMap().headMap(toElement));
    213        }
    214
    215        @Override
    216        public SortedSet<E> subSet(E fromElement, E toElement) {
    217          return new SortedMapBasedElementSet(
    218              sortedMap().subMap(fromElement, toElement));
    219        }
    220
    221        @Override
    222        public SortedSet<E> tailSet(E fromElement) {
    223          return new SortedMapBasedElementSet(sortedMap().tailMap(fromElement));
    224        }
    225
    226        @Override public boolean remove(Object element) {
    227          try {
    228            return super.remove(element);
    229          } catch (NullPointerException e) {
    230            return false;
    231          } catch (ClassCastException e) {
    232            return false;
    233          }
    234        }
    235      }
    236
    237      /*
    238       * TODO(jlevy): Decide whether entrySet() should return entries with an
    239       * equals() method that calls the comparator to compare the two keys. If that
    240       * change is made, AbstractMultiset.equals() can simply check whether two
    241       * multisets have equal entry sets.
    242       */
    243
    244      /**
    245       * @serialData the comparator, the number of distinct elements, the first
    246       *     element, its count, the second element, its count, and so on
    247       */
    248      @GwtIncompatible("java.io.ObjectOutputStream")
    249      private void writeObject(ObjectOutputStream stream) throws IOException {
    250        stream.defaultWriteObject();
    251        stream.writeObject(elementSet().comparator());
    252        Serialization.writeMultiset(this, stream);
    253      }
    254
    255      @GwtIncompatible("java.io.ObjectInputStream")
    256      private void readObject(ObjectInputStream stream)
    257          throws IOException, ClassNotFoundException {
    258        stream.defaultReadObject();
    259        @SuppressWarnings("unchecked") // reading data stored by writeObject
    260        Comparator<? super E> comparator
    261            = (Comparator<? super E>) stream.readObject();
    262        setBackingMap(new TreeMap<E, Count>(comparator));
    263        Serialization.populateMultiset(this, stream);
    264      }
    265
    266      @GwtIncompatible("not needed in emulated source")
    267      private static final long serialVersionUID = 0;
    268    }