1/*
2 * Copyright (C) 2007 Google Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import com.google.common.annotations.GwtCompatible;
20
21import java.io.IOException;
22import java.io.ObjectInputStream;
23import java.io.ObjectOutputStream;
24import java.util.Comparator;
25import java.util.Set;
26import java.util.SortedMap;
27import java.util.SortedSet;
28import java.util.TreeMap;
29import java.util.Collection;
30import java.util.concurrent.atomic.AtomicInteger;
31
32import javax.annotation.Nullable;
33
34/**
35 * A multiset which maintains the ordering of its elements, according to either
36 * their natural order or an explicit {@link Comparator}. In all cases, this
37 * implementation uses {@link Comparable#compareTo} or {@link
38 * Comparator#compare} instead of {@link Object#equals} to determine
39 * equivalence of instances.
40 *
41 * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as
42 * explained by the {@link Comparable} class specification. Otherwise, the
43 * resulting multiset will violate the {@link Collection} contract, which it is
44 * specified in terms of {@link Object#equals}.
45 *
46 * @author Neal Kanodia
47 * @author Jared Levy
48 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
49 */
50@GwtCompatible
51@SuppressWarnings("serial") // we're overriding default serialization
52public final class TreeMultiset<E> extends AbstractMapBasedMultiset<E> {
53
54  /**
55   * Creates a new, empty multiset, sorted according to the elements' natural
56   * order. All elements inserted into the multiset must implement the
57   * {@code Comparable} interface. Furthermore, all such elements must be
58   * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
59   * {@code ClassCastException} for any elements {@code e1} and {@code e2} in
60   * the multiset. If the user attempts to add an element to the multiset that
61   * violates this constraint (for example, the user attempts to add a string
62   * element to a set whose elements are integers), the {@code add(Object)}
63   * call will throw a {@code ClassCastException}.
64   *
65   * <p>The type specification is {@code <E extends Comparable>}, instead of the
66   * more specific {@code <E extends Comparable<? super E>>}, to support
67   * classes defined without generics.
68   */
69  @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
70  public static <E extends Comparable> TreeMultiset<E> create() {
71    return new TreeMultiset<E>();
72  }
73
74  /**
75   * Creates a new, empty multiset, sorted according to the specified
76   * comparator. All elements inserted into the multiset must be <i>mutually
77   * comparable</i> by the specified comparator: {@code comparator.compare(e1,
78   * e2)} must not throw a {@code ClassCastException} for any elements {@code
79   * e1} and {@code e2} in the multiset. If the user attempts to add an element
80   * to the multiset that violates this constraint, the {@code add(Object)} call
81   * will throw a {@code ClassCastException}.
82   *
83   * @param comparator the comparator that will be used to sort this multiset. A
84   *     null value indicates that the elements' <i>natural ordering</i> should
85   *     be used.
86   */
87  public static <E> TreeMultiset<E> create(Comparator<? super E> comparator) {
88    return new TreeMultiset<E>(comparator);
89  }
90
91  /**
92   * Creates an empty multiset containing the given initial elements, sorted
93   * according to the elements' natural order.
94   *
95   * <p>The type specification is {@code <E extends Comparable>}, instead of the
96   * more specific {@code <E extends Comparable<? super E>>}, to support
97   * classes defined without generics.
98   */
99  @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
100  public static <E extends Comparable> TreeMultiset<E> create(
101      Iterable<? extends E> elements) {
102    TreeMultiset<E> multiset = create();
103    Iterables.addAll(multiset, elements);
104    return multiset;
105  }
106
107  private TreeMultiset() {
108    super(new TreeMap<E, AtomicInteger>());
109  }
110
111  private TreeMultiset(Comparator<? super E> comparator) {
112    super(new TreeMap<E, AtomicInteger>(comparator));
113  }
114
115  /**
116   * {@inheritDoc}
117   *
118   * <p>In {@code TreeMultiset}, the return type of this method is narrowed
119   * from {@link Set} to {@link SortedSet}.
120   */
121  @Override public SortedSet<E> elementSet() {
122    return (SortedSet<E>) super.elementSet();
123  }
124
125  @Override public int count(@Nullable Object element) {
126    try {
127      return super.count(element);
128    } catch (NullPointerException e) {
129      return 0;
130    } catch (ClassCastException e) {
131      return 0;
132    }
133  }
134
135  @Override Set<E> createElementSet() {
136    return new SortedMapBasedElementSet(
137        (SortedMap<E, AtomicInteger>) backingMap());
138  }
139
140  private class SortedMapBasedElementSet extends MapBasedElementSet
141      implements SortedSet<E> {
142
143    SortedMapBasedElementSet(SortedMap<E, AtomicInteger> map) {
144      super(map);
145    }
146
147    SortedMap<E, AtomicInteger> sortedMap() {
148      return (SortedMap<E, AtomicInteger>) getMap();
149    }
150
151    public Comparator<? super E> comparator() {
152      return sortedMap().comparator();
153    }
154
155    public E first() {
156      return sortedMap().firstKey();
157    }
158
159    public E last() {
160      return sortedMap().lastKey();
161    }
162
163    public SortedSet<E> headSet(E toElement) {
164      return new SortedMapBasedElementSet(sortedMap().headMap(toElement));
165    }
166
167    public SortedSet<E> subSet(E fromElement, E toElement) {
168      return new SortedMapBasedElementSet(
169          sortedMap().subMap(fromElement, toElement));
170    }
171
172    public SortedSet<E> tailSet(E fromElement) {
173      return new SortedMapBasedElementSet(sortedMap().tailMap(fromElement));
174    }
175
176    @Override public boolean remove(Object element) {
177      try {
178        return super.remove(element);
179      } catch (NullPointerException e) {
180        return false;
181      } catch (ClassCastException e) {
182        return false;
183      }
184    }
185  }
186
187  /*
188   * TODO: Decide whether entrySet() should return entries with an equals()
189   * method that calls the comparator to compare the two keys. If that change
190   * is made, AbstractMultiset.equals() can simply check whether two multisets
191   * have equal entry sets.
192   */
193
194  /**
195   * @serialData the comparator, the number of distinct elements, the first
196   *     element, its count, the second element, its count, and so on
197   */
198  private void writeObject(ObjectOutputStream stream) throws IOException {
199    stream.defaultWriteObject();
200    stream.writeObject(elementSet().comparator());
201    Serialization.writeMultiset(this, stream);
202  }
203
204  private void readObject(ObjectInputStream stream)
205      throws IOException, ClassNotFoundException {
206    stream.defaultReadObject();
207    @SuppressWarnings("unchecked") // reading data stored by writeObject
208    Comparator<? super E> comparator
209        = (Comparator<? super E>) stream.readObject();
210    setBackingMap(new TreeMap<E, AtomicInteger>(comparator));
211    Serialization.populateMultiset(this, stream);
212  }
213
214  private static final long serialVersionUID = 0;
215}
216