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
017package com.google.common.collect;
018
019import com.google.common.annotations.GwtCompatible;
020import com.google.common.annotations.GwtIncompatible;
021
022import java.io.IOException;
023import java.io.ObjectInputStream;
024import java.io.ObjectOutputStream;
025import java.util.Collection;
026import java.util.Comparator;
027import java.util.Set;
028import java.util.SortedMap;
029import java.util.SortedSet;
030import java.util.TreeMap;
031import java.util.concurrent.atomic.AtomicInteger;
032
033import javax.annotation.Nullable;
034
035/**
036 * A multiset which maintains the ordering of its elements, according to either
037 * their natural order or an explicit {@link Comparator}. In all cases, this
038 * implementation uses {@link Comparable#compareTo} or {@link
039 * Comparator#compare} instead of {@link Object#equals} to determine
040 * equivalence of instances.
041 *
042 * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as
043 * explained by the {@link Comparable} class specification. Otherwise, the
044 * resulting multiset will violate the {@link Collection} contract, which it is
045 * specified in terms of {@link Object#equals}.
046 *
047 * @author Neal Kanodia
048 * @author Jared Levy
049 * @since 2 (imported from Google Collections Library)
050 */
051@GwtCompatible(emulated = true)
052@SuppressWarnings("serial") // we're overriding default serialization
053public final class TreeMultiset<E> extends AbstractMapBasedMultiset<E> {
054
055  /**
056   * Creates a new, empty multiset, sorted according to the elements' natural
057   * order. All elements inserted into the multiset must implement the
058   * {@code Comparable} interface. Furthermore, all such elements must be
059   * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
060   * {@code ClassCastException} for any elements {@code e1} and {@code e2} in
061   * the multiset. If the user attempts to add an element to the multiset that
062   * violates this constraint (for example, the user attempts to add a string
063   * element to a set whose elements are integers), the {@code add(Object)}
064   * call will throw a {@code ClassCastException}.
065   *
066   * <p>The type specification is {@code <E extends Comparable>}, instead of the
067   * more specific {@code <E extends Comparable<? super E>>}, to support
068   * classes defined without generics.
069   */
070  @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
071  public static <E extends Comparable> TreeMultiset<E> create() {
072    return new TreeMultiset<E>();
073  }
074
075  /**
076   * Creates a new, empty multiset, sorted according to the specified
077   * comparator. All elements inserted into the multiset must be <i>mutually
078   * comparable</i> by the specified comparator: {@code comparator.compare(e1,
079   * e2)} must not throw a {@code ClassCastException} for any elements {@code
080   * e1} and {@code e2} in the multiset. If the user attempts to add an element
081   * to the multiset that violates this constraint, the {@code add(Object)} call
082   * will throw a {@code ClassCastException}.
083   *
084   * @param comparator the comparator that will be used to sort this multiset. A
085   *     null value indicates that the elements' <i>natural ordering</i> should
086   *     be used.
087   */
088  public static <E> TreeMultiset<E> create(Comparator<? super E> comparator) {
089    return new TreeMultiset<E>(comparator);
090  }
091
092  /**
093   * Creates an empty multiset containing the given initial elements, sorted
094   * according to the elements' natural order.
095   *
096   * <p>The type specification is {@code <E extends Comparable>}, instead of the
097   * more specific {@code <E extends Comparable<? super E>>}, to support
098   * classes defined without generics.
099   */
100  @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
101  public static <E extends Comparable> TreeMultiset<E> create(
102      Iterable<? extends E> elements) {
103    TreeMultiset<E> multiset = create();
104    Iterables.addAll(multiset, elements);
105    return multiset;
106  }
107
108  private TreeMultiset() {
109    super(new TreeMap<E, AtomicInteger>());
110  }
111
112  private TreeMultiset(Comparator<? super E> comparator) {
113    super(new TreeMap<E, AtomicInteger>(comparator));
114  }
115
116  /**
117   * {@inheritDoc}
118   *
119   * <p>In {@code TreeMultiset}, the return type of this method is narrowed
120   * from {@link Set} to {@link SortedSet}.
121   */
122  @Override public SortedSet<E> elementSet() {
123    return (SortedSet<E>) super.elementSet();
124  }
125
126  @Override public int count(@Nullable Object element) {
127    try {
128      return super.count(element);
129    } catch (NullPointerException e) {
130      return 0;
131    } catch (ClassCastException e) {
132      return 0;
133    }
134  }
135
136  @Override Set<E> createElementSet() {
137    return new SortedMapBasedElementSet(
138        (SortedMap<E, AtomicInteger>) backingMap());
139  }
140
141  private class SortedMapBasedElementSet extends MapBasedElementSet
142      implements SortedSet<E> {
143
144    SortedMapBasedElementSet(SortedMap<E, AtomicInteger> map) {
145      super(map);
146    }
147
148    SortedMap<E, AtomicInteger> sortedMap() {
149      return (SortedMap<E, AtomicInteger>) getMap();
150    }
151
152    @Override
153    public Comparator<? super E> comparator() {
154      return sortedMap().comparator();
155    }
156
157    @Override
158    public E first() {
159      return sortedMap().firstKey();
160    }
161
162    @Override
163    public E last() {
164      return sortedMap().lastKey();
165    }
166
167    @Override
168    public SortedSet<E> headSet(E toElement) {
169      return new SortedMapBasedElementSet(sortedMap().headMap(toElement));
170    }
171
172    @Override
173    public SortedSet<E> subSet(E fromElement, E toElement) {
174      return new SortedMapBasedElementSet(
175          sortedMap().subMap(fromElement, toElement));
176    }
177
178    @Override
179    public SortedSet<E> tailSet(E fromElement) {
180      return new SortedMapBasedElementSet(sortedMap().tailMap(fromElement));
181    }
182
183    @Override public boolean remove(Object element) {
184      try {
185        return super.remove(element);
186      } catch (NullPointerException e) {
187        return false;
188      } catch (ClassCastException e) {
189        return false;
190      }
191    }
192  }
193
194  /*
195   * TODO(jlevy): Decide whether entrySet() should return entries with an
196   * equals() method that calls the comparator to compare the two keys. If that
197   * change is made, AbstractMultiset.equals() can simply check whether two
198   * multisets have equal entry sets.
199   */
200
201  /**
202   * @serialData the comparator, the number of distinct elements, the first
203   *     element, its count, the second element, its count, and so on
204   */
205  @GwtIncompatible("java.io.ObjectOutputStream")
206  private void writeObject(ObjectOutputStream stream) throws IOException {
207    stream.defaultWriteObject();
208    stream.writeObject(elementSet().comparator());
209    Serialization.writeMultiset(this, stream);
210  }
211
212  @GwtIncompatible("java.io.ObjectInputStream")
213  private void readObject(ObjectInputStream stream)
214      throws IOException, ClassNotFoundException {
215    stream.defaultReadObject();
216    @SuppressWarnings("unchecked") // reading data stored by writeObject
217    Comparator<? super E> comparator
218        = (Comparator<? super E>) stream.readObject();
219    setBackingMap(new TreeMap<E, AtomicInteger>(comparator));
220    Serialization.populateMultiset(this, stream);
221  }
222
223  @GwtIncompatible("not needed in emulated source")
224  private static final long serialVersionUID = 0;
225}