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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.errorprone.annotations.CanIgnoreReturnValue;
023import com.google.errorprone.annotations.CompatibleWith;
024import com.google.errorprone.annotations.DoNotMock;
025import java.util.Collection;
026import java.util.List;
027import java.util.Map;
028import java.util.Map.Entry;
029import java.util.Set;
030import java.util.function.BiConsumer;
031import javax.annotation.CheckForNull;
032import org.checkerframework.checker.nullness.qual.Nullable;
033
034/**
035 * A collection that maps keys to values, similar to {@link Map}, but in which each key may be
036 * associated with <i>multiple</i> values. You can visualize the contents of a multimap either as a
037 * map from keys to <i>nonempty</i> collections of values:
038 *
039 * <ul>
040 *   <li>a → 1, 2
041 *   <li>b → 3
042 * </ul>
043 *
044 * ... or as a single "flattened" collection of key-value pairs:
045 *
046 * <ul>
047 *   <li>a → 1
048 *   <li>a → 2
049 *   <li>b → 3
050 * </ul>
051 *
052 * <p><b>Important:</b> although the first interpretation resembles how most multimaps are
053 * <i>implemented</i>, the design of the {@code Multimap} API is based on the <i>second</i> form.
054 * So, using the multimap shown above as an example, the {@link #size} is {@code 3}, not {@code 2},
055 * and the {@link #values} collection is {@code [1, 2, 3]}, not {@code [[1, 2], [3]]}. For those
056 * times when the first style is more useful, use the multimap's {@link #asMap} view (or create a
057 * {@code Map<K, Collection<V>>} in the first place).
058 *
059 * <h3>Example</h3>
060 *
061 * <p>The following code:
062 *
063 * <pre>{@code
064 * ListMultimap<String, String> multimap = ArrayListMultimap.create();
065 * for (President pres : US_PRESIDENTS_IN_ORDER) {
066 *   multimap.put(pres.firstName(), pres.lastName());
067 * }
068 * for (String firstName : multimap.keySet()) {
069 *   List<String> lastNames = multimap.get(firstName);
070 *   out.println(firstName + ": " + lastNames);
071 * }
072 * }</pre>
073 *
074 * ... produces output such as:
075 *
076 * <pre>{@code
077 * Zachary: [Taylor]
078 * John: [Adams, Adams, Tyler, Kennedy]  // Remember, Quincy!
079 * George: [Washington, Bush, Bush]
080 * Grover: [Cleveland, Cleveland]        // Two, non-consecutive terms, rep'ing NJ!
081 * ...
082 * }</pre>
083 *
084 * <h3>Views</h3>
085 *
086 * <p>Much of the power of the multimap API comes from the <i>view collections</i> it provides.
087 * These always reflect the latest state of the multimap itself. When they support modification, the
088 * changes are <i>write-through</i> (they automatically update the backing multimap). These view
089 * collections are:
090 *
091 * <ul>
092 *   <li>{@link #asMap}, mentioned above
093 *   <li>{@link #keys}, {@link #keySet}, {@link #values}, {@link #entries}, which are similar to the
094 *       corresponding view collections of {@link Map}
095 *   <li>and, notably, even the collection returned by {@link #get get(key)} is an active view of
096 *       the values corresponding to {@code key}
097 * </ul>
098 *
099 * <p>The collections returned by the {@link #replaceValues replaceValues} and {@link #removeAll
100 * removeAll} methods, which contain values that have just been removed from the multimap, are
101 * naturally <i>not</i> views.
102 *
103 * <h3>Subinterfaces</h3>
104 *
105 * <p>Instead of using the {@code Multimap} interface directly, prefer the subinterfaces {@link
106 * ListMultimap} and {@link SetMultimap}. These take their names from the fact that the collections
107 * they return from {@code get} behave like (and, of course, implement) {@link List} and {@link
108 * Set}, respectively.
109 *
110 * <p>For example, the "presidents" code snippet above used a {@code ListMultimap}; if it had used a
111 * {@code SetMultimap} instead, two presidents would have vanished, and last names might or might
112 * not appear in chronological order.
113 *
114 * <p><b>Warning:</b> instances of type {@code Multimap} may not implement {@link Object#equals} in
115 * the way you expect. Multimaps containing the same key-value pairs, even in the same order, may or
116 * may not be equal and may or may not have the same {@code hashCode}. The recommended subinterfaces
117 * provide much stronger guarantees.
118 *
119 * <h3>Comparison to a map of collections</h3>
120 *
121 * <p>Multimaps are commonly used in places where a {@code Map<K, Collection<V>>} would otherwise
122 * have appeared. The differences include:
123 *
124 * <ul>
125 *   <li>There is no need to populate an empty collection before adding an entry with {@link #put
126 *       put}.
127 *   <li>{@code get} never returns {@code null}, only an empty collection.
128 *   <li>A key is contained in the multimap if and only if it maps to at least one value. Any
129 *       operation that causes a key to have zero associated values has the effect of
130 *       <i>removing</i> that key from the multimap.
131 *   <li>The total entry count is available as {@link #size}.
132 *   <li>Many complex operations become easier; for example, {@code
133 *       Collections.min(multimap.values())} finds the smallest value across all keys.
134 * </ul>
135 *
136 * <h3>Implementations</h3>
137 *
138 * <ul>
139 *   <li>{@link ImmutableListMultimap}
140 *   <li>{@link ImmutableSetMultimap}
141 *   <li>Configure your own mutable multimap with {@link MultimapBuilder}
142 *   <li>{@link LinkedListMultimap} (for one unusual kind of mutable {@code Multimap})
143 * </ul>
144 *
145 * Guava contains a number of other multimap implementations, such as {@link ArrayListMultimap}. In
146 * new code, we recommend using {@link MultimapBuilder} instead: It provides better control of how
147 * keys and values are stored.
148 *
149 * <h3>Other Notes</h3>
150 *
151 * <p>As with {@code Map}, the behavior of a {@code Multimap} is not specified if key objects
152 * already present in the multimap change in a manner that affects {@code equals} comparisons. Use
153 * caution if mutable objects are used as keys in a {@code Multimap}.
154 *
155 * <p>All methods that modify the multimap are optional. The view collections returned by the
156 * multimap may or may not be modifiable. Any modification method that is not supported will throw
157 * {@link UnsupportedOperationException}.
158 *
159 * <p>See the Guava User Guide article on <a href=
160 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>.
161 *
162 * @author Jared Levy
163 * @since 2.0
164 */
165@DoNotMock("Use ImmutableMultimap, HashMultimap, or another implementation")
166@GwtCompatible
167@ElementTypesAreNonnullByDefault
168public interface Multimap<K extends @Nullable Object, V extends @Nullable Object> {
169  // Query Operations
170
171  /**
172   * Returns the number of key-value pairs in this multimap.
173   *
174   * <p><b>Note:</b> this method does not return the number of <i>distinct keys</i> in the multimap,
175   * which is given by {@code keySet().size()} or {@code asMap().size()}. See the opening section of
176   * the {@link Multimap} class documentation for clarification.
177   */
178  int size();
179
180  /**
181   * Returns {@code true} if this multimap contains no key-value pairs. Equivalent to {@code size()
182   * == 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 with the key {@code
188   * key}.
189   */
190  boolean containsKey(@CompatibleWith("K") @CheckForNull Object key);
191
192  /**
193   * Returns {@code true} if this multimap contains at least one key-value pair with the value
194   * {@code value}.
195   */
196  boolean containsValue(@CompatibleWith("V") @CheckForNull Object value);
197
198  /**
199   * Returns {@code true} if this multimap contains at least one key-value pair with the key {@code
200   * key} and the value {@code value}.
201   */
202  boolean containsEntry(
203      @CompatibleWith("K") @CheckForNull Object key,
204      @CompatibleWith("V") @CheckForNull 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 case {@code put}
212   * always adds a new key-value pair and increases the multimap size by 1. Other implementations
213   * prohibit duplicates, and storing a key-value pair that's already in the multimap has no effect.
214   *
215   * @return {@code true} if the method increased the size of the multimap, or {@code false} if the
216   *     multimap already contained the key-value pair and doesn't allow duplicates
217   */
218  @CanIgnoreReturnValue
219  boolean put(@ParametricNullness K key, @ParametricNullness V value);
220
221  /**
222   * Removes a single key-value pair with the key {@code key} and the value {@code value} from this
223   * multimap, if such exists. If multiple key-value pairs in the multimap fit this description,
224   * which one is removed is unspecified.
225   *
226   * @return {@code true} if the multimap changed
227   */
228  @CanIgnoreReturnValue
229  boolean remove(
230      @CompatibleWith("K") @CheckForNull Object key,
231      @CompatibleWith("V") @CheckForNull Object value);
232
233  // Bulk Operations
234
235  /**
236   * Stores a key-value pair in this multimap for each of {@code values}, all using the same key,
237   * {@code key}. Equivalent to (but expected to be more efficient than):
238   *
239   * <pre>{@code
240   * for (V value : values) {
241   *   put(key, value);
242   * }
243   * }</pre>
244   *
245   * <p>In particular, this is a no-op if {@code values} is empty.
246   *
247   * @return {@code true} if the multimap changed
248   */
249  @CanIgnoreReturnValue
250  boolean putAll(@ParametricNullness K key, Iterable<? extends V> values);
251
252  /**
253   * Stores all key-value pairs of {@code multimap} in this multimap, in the order returned by
254   * {@code multimap.entries()}.
255   *
256   * @return {@code true} if the multimap changed
257   */
258  @CanIgnoreReturnValue
259  boolean putAll(Multimap<? extends K, ? extends V> multimap);
260
261  /**
262   * Stores a collection of values with the same key, replacing any existing values for that key.
263   *
264   * <p>If {@code values} is empty, this is equivalent to {@link #removeAll(Object) removeAll(key)}.
265   *
266   * @return the collection of replaced values, or an empty collection if no values were previously
267   *     associated with the key. The collection <i>may</i> be modifiable, but updating it will have
268   *     no effect on the multimap.
269   */
270  @CanIgnoreReturnValue
271  Collection<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values);
272
273  /**
274   * Removes all values associated with the key {@code key}.
275   *
276   * <p>Once this method returns, {@code key} will not be mapped to any values, so it will not
277   * appear in {@link #keySet()}, {@link #asMap()}, or any other views.
278   *
279   * @return the values that were removed (possibly empty). The returned collection <i>may</i> be
280   *     modifiable, but updating it will have no effect on the multimap.
281   */
282  @CanIgnoreReturnValue
283  Collection<V> removeAll(@CompatibleWith("K") @CheckForNull Object key);
284
285  /** Removes all key-value pairs from the multimap, leaving it {@linkplain #isEmpty empty}. */
286  void clear();
287
288  // Views
289
290  /**
291   * Returns a view collection of the values associated with {@code key} in this multimap, if any.
292   * Note that when {@code containsKey(key)} is false, this returns an empty collection, not {@code
293   * null}.
294   *
295   * <p>Changes to the returned collection will update the underlying multimap, and vice versa.
296   */
297  Collection<V> get(@ParametricNullness K key);
298
299  /**
300   * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
301   * key set contains a key if and only if this multimap maps that key to at least one value.
302   *
303   * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
304   * <i>adding</i> to the returned set is not possible.
305   */
306  Set<K> keySet();
307
308  /**
309   * Returns a view collection containing the key from each key-value pair in this multimap,
310   * <i>without</i> collapsing duplicates. This collection has the same size as this multimap, and
311   * {@code keys().count(k) == get(k).size()} for all {@code k}.
312   *
313   * <p>Changes to the returned multiset will update the underlying multimap, and vice versa.
314   * However, <i>adding</i> to the returned collection is not possible.
315   */
316  Multiset<K> keys();
317
318  /**
319   * Returns a view collection containing the <i>value</i> from each key-value pair contained in
320   * this multimap, without collapsing duplicates (so {@code values().size() == size()}).
321   *
322   * <p>Changes to the returned collection will update the underlying multimap, and vice versa.
323   * However, <i>adding</i> to the returned collection is not possible.
324   */
325  Collection<V> values();
326
327  /**
328   * Returns a view collection of all key-value pairs contained in this multimap, as {@link Entry}
329   * instances.
330   *
331   * <p>Changes to the returned collection or the entries it contains will update the underlying
332   * multimap, and vice versa. However, <i>adding</i> to the returned collection is not possible.
333   */
334  Collection<Entry<K, V>> entries();
335
336  /**
337   * Performs the given action for all key-value pairs contained in this multimap. If an ordering is
338   * specified by the {@code Multimap} implementation, actions will be performed in the order of
339   * iteration of {@link #entries()}. Exceptions thrown by the action are relayed to the caller.
340   *
341   * <p>To loop over all keys and their associated value collections, write {@code
342   * Multimaps.asMap(multimap).forEach((key, valueCollection) -> action())}.
343   *
344   * @since 21.0
345   */
346  default void forEach(BiConsumer<? super K, ? super V> action) {
347    checkNotNull(action);
348    entries().forEach(entry -> action.accept(entry.getKey(), entry.getValue()));
349  }
350
351  /**
352   * Returns a view of this multimap as a {@code Map} from each distinct key to the nonempty
353   * collection of that key's associated values. Note that {@code this.asMap().get(k)} is equivalent
354   * to {@code this.get(k)} only when {@code k} is a key contained in the multimap; otherwise it
355   * returns {@code null} as opposed to an empty collection.
356   *
357   * <p>Changes to the returned map or the collections that serve as its values will update the
358   * underlying multimap, and vice versa. The map does not support {@code put} or {@code putAll},
359   * nor do its entries support {@link Entry#setValue setValue}.
360   */
361  Map<K, Collection<V>> asMap();
362
363  // Comparison and hashing
364
365  /**
366   * Compares the specified object with this multimap for equality. Two multimaps are equal when
367   * their map views, as returned by {@link #asMap}, are also equal.
368   *
369   * <p>In general, two multimaps with identical key-value mappings may or may not be equal,
370   * depending on the implementation. For example, two {@link SetMultimap} instances with the same
371   * key-value mappings are equal, but equality of two {@link ListMultimap} instances depends on the
372   * ordering of the values for each key.
373   *
374   * <p>A non-empty {@link SetMultimap} cannot be equal to a non-empty {@link ListMultimap}, since
375   * their {@link #asMap} views contain unequal collections as values. However, any two empty
376   * multimaps are equal, because they both have empty {@link #asMap} views.
377   */
378  @Override
379  boolean equals(@CheckForNull Object obj);
380
381  /**
382   * Returns the hash code for this multimap.
383   *
384   * <p>The hash code of a multimap is defined as the hash code of the map view, as returned by
385   * {@link Multimap#asMap}.
386   *
387   * <p>In general, two multimaps with identical key-value mappings may or may not have the same
388   * hash codes, depending on the implementation. For example, two {@link SetMultimap} instances
389   * with the same key-value mappings will have the same {@code hashCode}, but the {@code hashCode}
390   * of {@link ListMultimap} instances depends on the ordering of the values for each key.
391   */
392  @Override
393  int hashCode();
394}