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.errorprone.annotations.CanIgnoreReturnValue;
23  import com.google.errorprone.annotations.CompatibleWith;
24  import java.util.Collection;
25  import java.util.List;
26  import java.util.Map;
27  import java.util.Set;
28  import java.util.function.BiConsumer;
29  import javax.annotation.Nullable;
30  
31  /**
32   * A collection that maps keys to values, similar to {@link Map}, but in which
33   * each key may be associated with <i>multiple</i> values. You can visualize the
34   * contents of a multimap either as a map from keys to <i>nonempty</i>
35   * collections of values:
36   *
37   * <ul>
38   * <li>a → 1, 2
39   * <li>b → 3
40   * </ul>
41   *
42   * ... or as a single "flattened" collection of key-value pairs:
43   *
44   * <ul>
45   * <li>a → 1
46   * <li>a → 2
47   * <li>b → 3
48   * </ul>
49   *
50   * <p><b>Important:</b> although the first interpretation resembles how most
51   * multimaps are <i>implemented</i>, the design of the {@code Multimap} API is
52   * based on the <i>second</i> form. So, using the multimap shown above as an
53   * example, the {@link #size} is {@code 3}, not {@code 2}, and the {@link
54   * #values} collection is {@code [1, 2, 3]}, not {@code [[1, 2], [3]]}. For
55   * those times when the first style is more useful, use the multimap's {@link
56   * #asMap} view (or create a {@code Map<K, Collection<V>>} in the first place).
57   *
58   * <h3>Example</h3>
59   *
60   * <p>The following code: <pre>   {@code
61   *
62   *   ListMultimap<String, String> multimap = ArrayListMultimap.create();
63   *   for (President pres : US_PRESIDENTS_IN_ORDER) {
64   *     multimap.put(pres.firstName(), pres.lastName());
65   *   }
66   *   for (String firstName : multimap.keySet()) {
67   *     List<String> lastNames = multimap.get(firstName);
68   *     out.println(firstName + ": " + lastNames);
69   *   }}</pre>
70   *
71   * ... produces output such as: <pre>   {@code
72   *
73   *   Zachary: [Taylor]
74   *   John: [Adams, Adams, Tyler, Kennedy]  // Remember, Quincy!
75   *   George: [Washington, Bush, Bush]
76   *   Grover: [Cleveland, Cleveland]        // Two, non-consecutive terms, rep'ing NJ!
77   *   ...}</pre>
78   *
79   * <h3>Views</h3>
80   *
81   * <p>Much of the power of the multimap API comes from the <i>view
82   * collections</i> it provides. These always reflect the latest state of the
83   * multimap itself. When they support modification, the changes are
84   * <i>write-through</i> (they automatically update the backing multimap). These
85   * view collections are:
86   *
87   * <ul>
88   * <li>{@link #asMap}, mentioned above</li>
89   * <li>{@link #keys}, {@link #keySet}, {@link #values}, {@link #entries}, which
90   *     are similar to the corresponding view collections of {@link Map}
91   * <li>and, notably, even the collection returned by {@link #get get(key)} is an
92   *     active view of the values corresponding to {@code key}
93   * </ul>
94   *
95   * <p>The collections returned by the {@link #replaceValues replaceValues} and
96   * {@link #removeAll removeAll} methods, which contain values that have just
97   * been removed from the multimap, are naturally <i>not</i> views.
98   *
99   * <h3>Subinterfaces</h3>
100  *
101  * <p>Instead of using the {@code Multimap} interface directly, prefer the
102  * subinterfaces {@link ListMultimap} and {@link SetMultimap}. These take their
103  * names from the fact that the collections they return from {@code get} behave
104  * like (and, of course, implement) {@link List} and {@link Set}, respectively.
105  *
106  * <p>For example, the "presidents" code snippet above used a {@code
107  * ListMultimap}; if it had used a {@code SetMultimap} instead, two presidents
108  * would have vanished, and last names might or might not appear in
109  * chronological order.
110  *
111  * <p><b>Warning:</b> instances of type {@code Multimap} may not implement
112  * {@link Object#equals} in the way you expect.  Multimaps containing the same
113  * key-value pairs, even in the same order, may or may not be equal and may or
114  * may not have the same {@code hashCode}. The recommended subinterfaces
115  * provide much stronger guarantees.
116  *
117  * <h3>Comparison to a map of collections</h3>
118  *
119  * <p>Multimaps are commonly used in places where a {@code Map<K,
120  * Collection<V>>} would otherwise have appeared. The differences include:
121  *
122  * <ul>
123  * <li>There is no need to populate an empty collection before adding an entry
124  *     with {@link #put put}.
125  * <li>{@code get} never returns {@code null}, only an empty collection.
126  * <li>A key is contained in the multimap if and only if it maps to at least
127  *     one value. Any operation that causes a key to have zero associated
128  *     values has the effect of <i>removing</i> that key from the multimap.
129  * <li>The total entry count is available as {@link #size}.
130  * <li>Many complex operations become easier; for example, {@code
131  *     Collections.min(multimap.values())} finds the smallest value across all
132  *     keys.
133  * </ul>
134  *
135  * <h3>Implementations</h3>
136  *
137  * <p>As always, prefer the immutable implementations, {@link
138  * ImmutableListMultimap} and {@link ImmutableSetMultimap}. General-purpose
139  * mutable implementations are listed above under "All Known Implementing
140  * Classes". You can also create a <i>custom</i> multimap, backed by any {@code
141  * Map} and {@link Collection} types, using the {@link Multimaps#newMultimap
142  * Multimaps.newMultimap} family of methods. Finally, another popular way to
143  * obtain a multimap is using {@link Multimaps#index Multimaps.index}. See
144  * the {@link Multimaps} class for these and other static utilities related
145  * to multimaps.
146  *
147  * <h3>Other Notes</h3>
148  *
149  * <p>As with {@code Map}, the behavior of a {@code Multimap} is not specified
150  * if key objects already present in the multimap change in a manner that
151  * affects {@code equals} comparisons.  Use caution if mutable objects are used
152  * as keys in a {@code Multimap}.
153  *
154  * <p>All methods that modify the multimap are optional. The view collections
155  * returned by the multimap may or may not be modifiable. Any modification
156  * method that is not supported will throw {@link
157  * UnsupportedOperationException}.
158  *
159  * <p>See the Guava User Guide article on <a href=
160  * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">
161  * {@code Multimap}</a>.
162  *
163  * @author Jared Levy
164  * @since 2.0
165  */
166 @GwtCompatible
167 public interface Multimap<K, V> {
168   // Query Operations
169 
170   /**
171    * Returns the number of key-value pairs in this multimap.
172    *
173    * <p><b>Note:</b> this method does not return the number of <i>distinct
174    * keys</i> in the multimap, which is given by {@code keySet().size()} or
175    * {@code asMap().size()}. See the opening section of the {@link Multimap}
176    * class documentation for clarification.
177    */
178   int size();
179 
180   /**
181    * Returns {@code true} if this multimap contains no key-value pairs.
182    * Equivalent to {@code size() == 0}, but can in some cases be more efficient.
183    */
184   boolean isEmpty();
185 
186   /**
187    * Returns {@code true} if this multimap contains at least one key-value pair
188    * with the key {@code key}.
189    */
190   boolean containsKey(@CompatibleWith("K") @Nullable Object key);
191 
192   /**
193    * Returns {@code true} if this multimap contains at least one key-value pair
194    * with the value {@code value}.
195    */
196   boolean containsValue(@CompatibleWith("V") @Nullable Object value);
197 
198   /**
199    * Returns {@code true} if this multimap contains at least one key-value pair
200    * with the key {@code key} and the value {@code value}.
201    */
202   boolean containsEntry(
203       @CompatibleWith("K") @Nullable Object key,
204       @CompatibleWith("V") @Nullable Object value);
205 
206   // Modification Operations
207 
208   /**
209    * Stores a key-value pair in this multimap.
210    *
211    * <p>Some multimap implementations allow duplicate key-value pairs, in which
212    * case {@code put} always adds a new key-value pair and increases the
213    * multimap size by 1. Other implementations prohibit duplicates, and storing
214    * a key-value pair that's already in the multimap has no effect.
215    *
216    * @return {@code true} if the method increased the size of the multimap, or
217    *     {@code false} if the multimap already contained the key-value pair and
218    *     doesn't allow duplicates
219    */
220   @CanIgnoreReturnValue
221   boolean put(@Nullable K key, @Nullable V value);
222 
223   /**
224    * Removes a single key-value pair with the key {@code key} and the value
225    * {@code value} from this multimap, if such exists. If multiple key-value
226    * pairs in the multimap fit this description, which one is removed is
227    * unspecified.
228    *
229    * @return {@code true} if the multimap changed
230    */
231   @CanIgnoreReturnValue
232   boolean remove(
233       @CompatibleWith("K") @Nullable Object key,
234       @CompatibleWith("V") @Nullable Object value);
235 
236   // Bulk Operations
237 
238   /**
239    * Stores a key-value pair in this multimap for each of {@code values}, all
240    * using the same key, {@code key}. Equivalent to (but expected to be more
241    * efficient than): <pre>   {@code
242    *
243    *   for (V value : values) {
244    *     put(key, value);
245    *   }}</pre>
246    *
247    * <p>In particular, this is a no-op if {@code values} is empty.
248    *
249    * @return {@code true} if the multimap changed
250    */
251   @CanIgnoreReturnValue
252   boolean putAll(@Nullable K key, Iterable<? extends V> values);
253 
254   /**
255    * Stores all key-value pairs of {@code multimap} in this multimap, in the
256    * order returned by {@code multimap.entries()}.
257    *
258    * @return {@code true} if the multimap changed
259    */
260   @CanIgnoreReturnValue
261   boolean putAll(Multimap<? extends K, ? extends V> multimap);
262 
263   /**
264    * Stores a collection of values with the same key, replacing any existing
265    * values for that key.
266    *
267    * <p>If {@code values} is empty, this is equivalent to
268    * {@link #removeAll(Object) removeAll(key)}.
269    *
270    * @return the collection of replaced values, or an empty collection if no
271    *     values were previously associated with the key. The collection
272    *     <i>may</i> be modifiable, but updating it will have no effect on the
273    *     multimap.
274    */
275   @CanIgnoreReturnValue
276   Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values);
277 
278   /**
279    * Removes all values associated with the key {@code key}.
280    *
281    * <p>Once this method returns, {@code key} will not be mapped to any values,
282    * so it will not appear in {@link #keySet()}, {@link #asMap()}, or any other
283    * views.
284    *
285    * @return the values that were removed (possibly empty). The returned
286    *     collection <i>may</i> be modifiable, but updating it will have no
287    *     effect on the multimap.
288    */
289   @CanIgnoreReturnValue
290   Collection<V> removeAll(@CompatibleWith("K") @Nullable Object key);
291 
292   /**
293    * Removes all key-value pairs from the multimap, leaving it {@linkplain
294    * #isEmpty empty}.
295    */
296   void clear();
297 
298   // Views
299 
300   /**
301    * Returns a view collection of the values associated with {@code key} in this
302    * multimap, if any. Note that when {@code containsKey(key)} is false, this
303    * returns an empty collection, not {@code null}.
304    *
305    * <p>Changes to the returned collection will update the underlying multimap,
306    * and vice versa.
307    */
308   Collection<V> get(@Nullable K key);
309 
310   /**
311    * Returns a view collection of all <i>distinct</i> keys contained in this
312    * multimap. Note that the key set contains a key if and only if this multimap
313    * maps that key to at least one value.
314    *
315    * <p>Changes to the returned set will update the underlying multimap, and
316    * vice versa. However, <i>adding</i> to the returned set is not possible.
317    */
318   Set<K> keySet();
319 
320   /**
321    * Returns a view collection containing the key from each key-value pair in
322    * this multimap, <i>without</i> collapsing duplicates. This collection has
323    * the same size as this multimap, and {@code keys().count(k) ==
324    * get(k).size()} for all {@code k}.
325    *
326    * <p>Changes to the returned multiset will update the underlying multimap,
327    * and vice versa. However, <i>adding</i> to the returned collection is not
328    * possible.
329    */
330   Multiset<K> keys();
331 
332   /**
333    * Returns a view collection containing the <i>value</i> from each key-value
334    * pair contained in this multimap, without collapsing duplicates (so {@code
335    * values().size() == size()}).
336    *
337    * <p>Changes to the returned collection will update the underlying multimap,
338    * and vice versa. However, <i>adding</i> to the returned collection is not
339    * possible.
340    */
341   Collection<V> values();
342 
343   /**
344    * Returns a view collection of all key-value pairs contained in this
345    * multimap, as {@link Map.Entry} instances.
346    *
347    * <p>Changes to the returned collection or the entries it contains will
348    * update the underlying multimap, and vice versa. However, <i>adding</i> to
349    * the returned collection is not possible.
350    */
351   Collection<Map.Entry<K, V>> entries();
352 
353   /**
354    * Performs the given action for all key-value pairs contained in this multimap. If an ordering is
355    * specified by the {@code Multimap} implementation, actions will be performed in the order of
356    * iteration of {@link #entries()}. Exceptions thrown by the action are relayed to the caller.
357    *
358    * <p>To loop over all keys and their associated value collections, write
359    * {@code Multimaps.asMap(multimap).forEach((key, valueCollection) -> action())}.
360    *
361    * @since 21.0
362    */
363   default void forEach(BiConsumer<? super K, ? super V> action) {
364     checkNotNull(action);
365     entries().forEach(entry -> action.accept(entry.getKey(), entry.getValue()));
366   }
367 
368   /**
369    * Returns a view of this multimap as a {@code Map} from each distinct key
370    * to the nonempty collection of that key's associated values. Note that
371    * {@code this.asMap().get(k)} is equivalent to {@code this.get(k)} only when
372    * {@code k} is a key contained in the multimap; otherwise it returns {@code
373    * null} as opposed to an empty collection.
374    *
375    * <p>Changes to the returned map or the collections that serve as its values
376    * will update the underlying multimap, and vice versa. The map does not
377    * support {@code put} or {@code putAll}, nor do its entries support {@link
378    * Map.Entry#setValue setValue}.
379    */
380   Map<K, Collection<V>> asMap();
381 
382   // Comparison and hashing
383 
384   /**
385    * Compares the specified object with this multimap for equality. Two
386    * multimaps are equal when their map views, as returned by {@link #asMap},
387    * are also equal.
388    *
389    * <p>In general, two multimaps with identical key-value mappings may or may
390    * not be equal, depending on the implementation. For example, two
391    * {@link SetMultimap} instances with the same key-value mappings are equal,
392    * but equality of two {@link ListMultimap} instances depends on the ordering
393    * of the values for each key.
394    *
395    * <p>A non-empty {@link SetMultimap} cannot be equal to a non-empty
396    * {@link ListMultimap}, since their {@link #asMap} views contain unequal
397    * collections as values. However, any two empty multimaps are equal, because
398    * they both have empty {@link #asMap} views.
399    */
400   @Override
401   boolean equals(@Nullable Object obj);
402 
403   /**
404    * Returns the hash code for this multimap.
405    *
406    * <p>The hash code of a multimap is defined as the hash code of the map view,
407    * as returned by {@link Multimap#asMap}.
408    *
409    * <p>In general, two multimaps with identical key-value mappings may or may
410    * not have the same hash codes, depending on the implementation. For
411    * example, two {@link SetMultimap} instances with the same key-value
412    * mappings will have the same {@code hashCode}, but the {@code hashCode}
413    * of {@link ListMultimap} instances depends on the ordering of the values
414    * for each key.
415    */
416   @Override
417   int hashCode();
418 }