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