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.Collection;
028 import java.util.Comparator;
029 import java.util.SortedMap;
030 import java.util.SortedSet;
031 import java.util.TreeMap;
032 import java.util.TreeSet;
033
034 /**
035 * Implementation of {@code Multimap} whose keys and values are ordered by
036 * their natural ordering or by supplied comparators. In all cases, this
037 * implementation uses {@link Comparable#compareTo} or {@link
038 * Comparator#compare} instead of {@link Object#equals} to determine
039 * equivalence of instances.
040 *
041 * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent
042 * with equals</i> as explained by the {@link Comparable} class specification.
043 * Otherwise, the resulting multiset will violate the general contract of {@link
044 * SetMultimap}, which it is specified in terms of {@link Object#equals}.
045 *
046 * <p>The collections returned by {@code keySet} and {@code asMap} iterate
047 * through the keys according to the key comparator ordering or the natural
048 * ordering of the keys. Similarly, {@code get}, {@code removeAll}, and {@code
049 * replaceValues} return collections that iterate through the values according
050 * to the value comparator ordering or the natural ordering of the values. The
051 * collections generated by {@code entries}, {@code keys}, and {@code values}
052 * iterate across the keys according to the above key ordering, and for each
053 * key they iterate across the values according to the value ordering.
054 *
055 * <p>The multimap does not store duplicate key-value pairs. Adding a new
056 * key-value pair equal to an existing key-value pair has no effect.
057 *
058 * <p>Null keys and values are permitted (provided, of course, that the
059 * respective comparators support them). All optional multimap methods are
060 * supported, and all returned views are modifiable.
061 *
062 * <p>This class is not threadsafe when any concurrent operations update the
063 * multimap. Concurrent read operations will work correctly. To allow concurrent
064 * update operations, wrap your multimap with a call to {@link
065 * Multimaps#synchronizedSortedSetMultimap}.
066 *
067 * @author Jared Levy
068 * @since 2.0 (imported from Google Collections Library)
069 */
070 @GwtCompatible(serializable = true, emulated = true)
071 public class TreeMultimap<K, V> extends AbstractSortedSetMultimap<K, V> {
072 private transient Comparator<? super K> keyComparator;
073 private transient Comparator<? super V> valueComparator;
074
075 /**
076 * Creates an empty {@code TreeMultimap} ordered by the natural ordering of
077 * its keys and values.
078 */
079 public static <K extends Comparable, V extends Comparable>
080 TreeMultimap<K, V> create() {
081 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural());
082 }
083
084 /**
085 * Creates an empty {@code TreeMultimap} instance using explicit comparators.
086 * Neither comparator may be null; use {@link Ordering#natural()} to specify
087 * natural order.
088 *
089 * @param keyComparator the comparator that determines the key ordering
090 * @param valueComparator the comparator that determines the value ordering
091 */
092 public static <K, V> TreeMultimap<K, V> create(
093 Comparator<? super K> keyComparator,
094 Comparator<? super V> valueComparator) {
095 return new TreeMultimap<K, V>(checkNotNull(keyComparator),
096 checkNotNull(valueComparator));
097 }
098
099 /**
100 * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its
101 * keys and values, with the same mappings as the specified multimap.
102 *
103 * @param multimap the multimap whose contents are copied to this multimap
104 */
105 public static <K extends Comparable, V extends Comparable>
106 TreeMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
107 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural(),
108 multimap);
109 }
110
111 TreeMultimap(Comparator<? super K> keyComparator,
112 Comparator<? super V> valueComparator) {
113 super(new TreeMap<K, Collection<V>>(keyComparator));
114 this.keyComparator = keyComparator;
115 this.valueComparator = valueComparator;
116 }
117
118 private TreeMultimap(Comparator<? super K> keyComparator,
119 Comparator<? super V> valueComparator,
120 Multimap<? extends K, ? extends V> multimap) {
121 this(keyComparator, valueComparator);
122 putAll(multimap);
123 }
124
125 /**
126 * {@inheritDoc}
127 *
128 * <p>Creates an empty {@code TreeSet} for a collection of values for one key.
129 *
130 * @return a new {@code TreeSet} containing a collection of values for one
131 * key
132 */
133 @Override SortedSet<V> createCollection() {
134 return new TreeSet<V>(valueComparator);
135 }
136
137 /**
138 * Returns the comparator that orders the multimap keys.
139 */
140 public Comparator<? super K> keyComparator() {
141 return keyComparator;
142 }
143
144 @Override
145 public Comparator<? super V> valueComparator() {
146 return valueComparator;
147 }
148
149 /**
150 * {@inheritDoc}
151 *
152 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method
153 * returns a {@link SortedSet}, instead of the {@link java.util.Set} specified
154 * in the {@link Multimap} interface.
155 */
156 @Override public SortedSet<K> keySet() {
157 return (SortedSet<K>) super.keySet();
158 }
159
160 /**
161 * {@inheritDoc}
162 *
163 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method
164 * returns a {@link SortedMap}, instead of the {@link java.util.Map} specified
165 * in the {@link Multimap} interface.
166 */
167 @Override public SortedMap<K, Collection<V>> asMap() {
168 return (SortedMap<K, Collection<V>>) super.asMap();
169 }
170
171 /**
172 * @serialData key comparator, value comparator, number of distinct keys, and
173 * then for each distinct key: the key, number of values for that key, and
174 * key values
175 */
176 @GwtIncompatible("java.io.ObjectOutputStream")
177 private void writeObject(ObjectOutputStream stream) throws IOException {
178 stream.defaultWriteObject();
179 stream.writeObject(keyComparator());
180 stream.writeObject(valueComparator());
181 Serialization.writeMultimap(this, stream);
182 }
183
184 @GwtIncompatible("java.io.ObjectInputStream")
185 @SuppressWarnings("unchecked") // reading data stored by writeObject
186 private void readObject(ObjectInputStream stream)
187 throws IOException, ClassNotFoundException {
188 stream.defaultReadObject();
189 keyComparator = checkNotNull((Comparator<? super K>) stream.readObject());
190 valueComparator = checkNotNull((Comparator<? super V>) stream.readObject());
191 setMap(new TreeMap<K, Collection<V>>(keyComparator));
192 Serialization.populateMultimap(this, stream);
193 }
194
195 @GwtIncompatible("not needed in emulated source")
196 private static final long serialVersionUID = 0;
197 }