View Javadoc
1   /*
2    * Copyright (C) 2007 The Guava Authors
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  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.GwtCompatible;
22  import com.google.common.annotations.GwtIncompatible;
23  import java.io.IOException;
24  import java.io.ObjectInputStream;
25  import java.io.ObjectOutputStream;
26  import java.util.Collection;
27  import java.util.Comparator;
28  import java.util.NavigableMap;
29  import java.util.NavigableSet;
30  import java.util.SortedSet;
31  import java.util.TreeMap;
32  import java.util.TreeSet;
33  import javax.annotation.Nullable;
34  
35  /**
36   * Implementation of {@code Multimap} whose keys and values are ordered by
37   * their natural ordering or by supplied comparators. In all cases, this
38   * implementation uses {@link Comparable#compareTo} or {@link
39   * Comparator#compare} instead of {@link Object#equals} to determine
40   * equivalence of instances.
41   *
42   * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent
43   * with equals</i> as explained by the {@link Comparable} class specification.
44   * Otherwise, the resulting multiset will violate the general contract of {@link
45   * SetMultimap}, which it is specified in terms of {@link Object#equals}.
46   *
47   * <p>The collections returned by {@code keySet} and {@code asMap} iterate
48   * through the keys according to the key comparator ordering or the natural
49   * ordering of the keys. Similarly, {@code get}, {@code removeAll}, and {@code
50   * replaceValues} return collections that iterate through the values according
51   * to the value comparator ordering or the natural ordering of the values. The
52   * collections generated by {@code entries}, {@code keys}, and {@code values}
53   * iterate across the keys according to the above key ordering, and for each
54   * key they iterate across the values according to the value ordering.
55   *
56   * <p>The multimap does not store duplicate key-value pairs. Adding a new
57   * key-value pair equal to an existing key-value pair has no effect.
58   *
59   * <p>Null keys and values are permitted (provided, of course, that the
60   * respective comparators support them). All optional multimap methods are
61   * supported, and all returned views are modifiable.
62   *
63   * <p>This class is not threadsafe when any concurrent operations update the
64   * multimap. Concurrent read operations will work correctly. To allow concurrent
65   * update operations, wrap your multimap with a call to {@link
66   * Multimaps#synchronizedSortedSetMultimap}.
67   *
68   * <p>See the Guava User Guide article on <a href=
69   * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">
70   * {@code Multimap}</a>.
71   *
72   * @author Jared Levy
73   * @author Louis Wasserman
74   * @since 2.0
75   */
76  @GwtCompatible(serializable = true, emulated = true)
77  public class TreeMultimap<K, V> extends AbstractSortedKeySortedSetMultimap<K, V> {
78    private transient Comparator<? super K> keyComparator;
79    private transient Comparator<? super V> valueComparator;
80  
81    /**
82     * Creates an empty {@code TreeMultimap} ordered by the natural ordering of
83     * its keys and values.
84     */
85    public static <K extends Comparable, V extends Comparable> TreeMultimap<K, V> create() {
86      return new TreeMultimap<>(Ordering.natural(), Ordering.natural());
87    }
88  
89    /**
90     * Creates an empty {@code TreeMultimap} instance using explicit comparators.
91     * Neither comparator may be null; use {@link Ordering#natural()} to specify
92     * natural order.
93     *
94     * @param keyComparator the comparator that determines the key ordering
95     * @param valueComparator the comparator that determines the value ordering
96     */
97    public static <K, V> TreeMultimap<K, V> create(
98        Comparator<? super K> keyComparator, Comparator<? super V> valueComparator) {
99      return new TreeMultimap<>(checkNotNull(keyComparator), checkNotNull(valueComparator));
100   }
101 
102   /**
103    * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its
104    * keys and values, with the same mappings as the specified multimap.
105    *
106    * @param multimap the multimap whose contents are copied to this multimap
107    */
108   public static <K extends Comparable, V extends Comparable> TreeMultimap<K, V> create(
109       Multimap<? extends K, ? extends V> multimap) {
110     return new TreeMultimap<>(Ordering.natural(), Ordering.natural(), multimap);
111   }
112 
113   TreeMultimap(Comparator<? super K> keyComparator, Comparator<? super V> valueComparator) {
114     super(new TreeMap<K, Collection<V>>(keyComparator));
115     this.keyComparator = keyComparator;
116     this.valueComparator = valueComparator;
117   }
118 
119   private TreeMultimap(
120       Comparator<? super K> keyComparator,
121       Comparator<? super V> valueComparator,
122       Multimap<? extends K, ? extends V> multimap) {
123     this(keyComparator, valueComparator);
124     putAll(multimap);
125   }
126 
127   /**
128    * {@inheritDoc}
129    *
130    * <p>Creates an empty {@code TreeSet} for a collection of values for one key.
131    *
132    * @return a new {@code TreeSet} containing a collection of values for one
133    *     key
134    */
135   @Override
136   SortedSet<V> createCollection() {
137     return new TreeSet<V>(valueComparator);
138   }
139 
140   @Override
141   Collection<V> createCollection(@Nullable K key) {
142     if (key == null) {
143       keyComparator().compare(key, key);
144     }
145     return super.createCollection(key);
146   }
147 
148   /**
149    * Returns the comparator that orders the multimap keys.
150    *
151    * @deprecated Use {@code ((NavigableSet<K>) multimap.keySet()).comparator()} instead.
152    */
153   @Deprecated
154   public Comparator<? super K> keyComparator() {
155     return keyComparator;
156   }
157 
158   @Override
159   public Comparator<? super V> valueComparator() {
160     return valueComparator;
161   }
162 
163   /**
164    * @since 14.0 (present with return type {@code SortedSet} since 2.0)
165    */
166   @Override
167   @GwtIncompatible // NavigableSet
168   public NavigableSet<V> get(@Nullable K key) {
169     return (NavigableSet<V>) super.get(key);
170   }
171 
172   /**
173    * {@inheritDoc}
174    *
175    * <p>Because a {@code TreeMultimap} has unique sorted keys, this method
176    * returns a {@link NavigableSet}, instead of the {@link java.util.Set} specified
177    * in the {@link Multimap} interface.
178    *
179    * @since 14.0 (present with return type {@code SortedSet} since 2.0)
180    */
181   @Override
182   public NavigableSet<K> keySet() {
183     return (NavigableSet<K>) super.keySet();
184   }
185 
186   /**
187    * {@inheritDoc}
188    *
189    * <p>Because a {@code TreeMultimap} has unique sorted keys, this method
190    * returns a {@link NavigableMap}, instead of the {@link java.util.Map} specified
191    * in the {@link Multimap} interface.
192    *
193    * @since 14.0 (present with return type {@code SortedMap} since 2.0)
194    */
195   @Override
196   public NavigableMap<K, Collection<V>> asMap() {
197     return (NavigableMap<K, Collection<V>>) super.asMap();
198   }
199 
200   /**
201    * @serialData key comparator, value comparator, number of distinct keys, and
202    *     then for each distinct key: the key, number of values for that key, and
203    *     key values
204    */
205   @GwtIncompatible // java.io.ObjectOutputStream
206   private void writeObject(ObjectOutputStream stream) throws IOException {
207     stream.defaultWriteObject();
208     stream.writeObject(keyComparator());
209     stream.writeObject(valueComparator());
210     Serialization.writeMultimap(this, stream);
211   }
212 
213   @GwtIncompatible // java.io.ObjectInputStream
214   @SuppressWarnings("unchecked") // reading data stored by writeObject
215   private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
216     stream.defaultReadObject();
217     keyComparator = checkNotNull((Comparator<? super K>) stream.readObject());
218     valueComparator = checkNotNull((Comparator<? super V>) stream.readObject());
219     setMap(new TreeMap<K, Collection<V>>(keyComparator));
220     Serialization.populateMultimap(this, stream);
221   }
222 
223   @GwtIncompatible // not needed in emulated source
224   private static final long serialVersionUID = 0;
225 }