001 /*
002 * Copyright (C) 2007 Google Inc.
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 com.google.common.annotations.GwtCompatible;
020 import com.google.common.annotations.GwtIncompatible;
021
022 import java.io.IOException;
023 import java.io.ObjectInputStream;
024 import java.io.ObjectOutputStream;
025 import java.util.Collection;
026 import java.util.Comparator;
027 import java.util.Set;
028 import java.util.SortedMap;
029 import java.util.SortedSet;
030 import java.util.TreeMap;
031 import java.util.concurrent.atomic.AtomicInteger;
032
033 import 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
053 public 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 public Comparator<? super E> comparator() {
153 return sortedMap().comparator();
154 }
155
156 public E first() {
157 return sortedMap().firstKey();
158 }
159
160 public E last() {
161 return sortedMap().lastKey();
162 }
163
164 public SortedSet<E> headSet(E toElement) {
165 return new SortedMapBasedElementSet(sortedMap().headMap(toElement));
166 }
167
168 public SortedSet<E> subSet(E fromElement, E toElement) {
169 return new SortedMapBasedElementSet(
170 sortedMap().subMap(fromElement, toElement));
171 }
172
173 public SortedSet<E> tailSet(E fromElement) {
174 return new SortedMapBasedElementSet(sortedMap().tailMap(fromElement));
175 }
176
177 @Override public boolean remove(Object element) {
178 try {
179 return super.remove(element);
180 } catch (NullPointerException e) {
181 return false;
182 } catch (ClassCastException e) {
183 return false;
184 }
185 }
186 }
187
188 /*
189 * TODO: Decide whether entrySet() should return entries with an equals()
190 * method that calls the comparator to compare the two keys. If that change
191 * is made, AbstractMultiset.equals() can simply check whether two multisets
192 * have equal entry sets.
193 */
194
195 /**
196 * @serialData the comparator, the number of distinct elements, the first
197 * element, its count, the second element, its count, and so on
198 */
199 @GwtIncompatible("java.io.ObjectOutputStream")
200 private void writeObject(ObjectOutputStream stream) throws IOException {
201 stream.defaultWriteObject();
202 stream.writeObject(elementSet().comparator());
203 Serialization.writeMultiset(this, stream);
204 }
205
206 @GwtIncompatible("java.io.ObjectInputStream")
207 private void readObject(ObjectInputStream stream)
208 throws IOException, ClassNotFoundException {
209 stream.defaultReadObject();
210 @SuppressWarnings("unchecked") // reading data stored by writeObject
211 Comparator<? super E> comparator
212 = (Comparator<? super E>) stream.readObject();
213 setBackingMap(new TreeMap<E, AtomicInteger>(comparator));
214 Serialization.populateMultiset(this, stream);
215 }
216
217 @GwtIncompatible("not needed in emulated source")
218 private static final long serialVersionUID = 0;
219 }