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 }