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 com.google.common.annotations.GwtCompatible;
020
021import java.util.Collection;
022import java.util.List;
023import java.util.Map;
024import java.util.Set;
025
026import javax.annotation.Nullable;
027
028/**
029 * A collection that maps keys to values, similar to {@link Map}, but in which
030 * each key may be associated with <i>multiple</i> values. You can visualize the
031 * contents of a multimap either as a map from keys to collections of values:
032 *
033 * <ul>
034 * <li>a → 1, 2
035 * <li>b → 3
036 * </ul>
037 *
038 * ... or as a single "flattened" collection of key-value pairs:
039 *
040 * <ul>
041 * <li>a → 1
042 * <li>a → 2
043 * <li>b → 3
044 * </ul>
045 *
046 * <p><b>Important:</b> although the first interpretation resembles how most
047 * multimaps are <i>implemented</i>, the design of the {@code Multimap} API is
048 * based on the <i>second</i> form. So, using the multimap shown above as an
049 * example, the {@link #size} is {@code 3}, not {@code 2}, and the {@link
050 * #values} collection is {@code [1, 2, 3]}, not {@code [[1, 2], [3]]}. For
051 * those times when the first style is more useful, use the multimap's {@link
052 * #asMap} view.
053 *
054 * <h3>Example</h3>
055 *
056 * <p>The following code: <pre>   {@code
057 *
058 *   ListMultimap<String, String> multimap = ArrayListMultimap.create();
059 *   for (President pres : US_PRESIDENTS_IN_ORDER) {
060 *     multimap.put(pres.firstName(), pres.lastName());
061 *   }
062 *   for (String firstName : multimap.keySet()) {
063 *     List<String> lastNames = multimap.get(firstName);
064 *     out.println(firstName + ": " + lastNames);
065 *   }}</pre>
066 *
067 * ... produces output such as: <pre>   {@code
068 *
069 *   Zachary: [Taylor]
070 *   John: [Adams, Adams, Tyler, Kennedy]
071 *   George: [Washington, Bush, Bush]
072 *   Grover: [Cleveland]
073 *   ...}</pre>
074 *
075 * <h3>Views</h3>
076 *
077 * <p>Much of the power of the multimap API comes from the <i>view
078 * collections</i> it provides. These always reflect the latest state of the
079 * multimap itself. When they support modification, the changes are
080 * <i>write-through</i> (they automatically update the backing multimap). These
081 * view collections are:
082 *
083 * <ul>
084 * <li>{@link #asMap}, mentioned above</li>
085 * <li>{@link #keys}, {@link #keySet}, {@link #values}, {@link #entries}, which
086 *     are similar to the corresponding view collections of {@link Map}
087 * <li>and, notably, even the collection returned by {@link #get get(key)} is an
088 *     active view of the values corresponding to {@code key}
089 * </ul>
090 *
091 * <p>The collections returned by the {@link #replaceValues replaceValues} and
092 * {@link #removeAll removeAll} methods, which contain values that have just
093 * been removed from the multimap, are naturally <i>not</i> views.
094 *
095 * <h3>Subinterfaces</h3>
096 *
097 * <p>Instead of using the {@code Multimap} interface directly, prefer the
098 * subinterfaces {@link ListMultimap} and {@link SetMultimap}. These take their
099 * names from the fact that the collections they return from {@code get} behave
100 * like (and, of course, implement) {@link List} and {@link Set}, respectively.
101 *
102 * <p>For example, the "presidents" code snippet above used a {@code
103 * ListMultimap}; if it had used a {@code SetMultimap} instead, two presidents
104 * would have vanished, and last names might or might not appear in
105 * chronological order.
106 *
107 * <h3>Uses</h3>
108 *
109 * <p>Multimaps are commonly used anywhere a {@code Map<K, Collection<V>>} would
110 * otherwise have appeared. The advantages include:
111 *
112 * <ul>
113 * <li>There is no need to populate an empty collection before adding an entry
114 *     with {@link #put put}.
115 * <li>{@code get} never returns {@code null}, only an empty collection.
116 * <li>It will not retain empty collections after the last value for a key is
117 *     removed. As a result, {@link #containsKey} behaves logically, and the
118 *     multimap won't leak memory.
119 * <li>The total entry count is available as {@link #size}.
120 * <li>Many complex operations become easier; for example, {@code
121 *     Collections.min(multimap.values())} finds the smallest value across all
122 *     keys.
123 * </ul>
124 *
125 * <h3>Implementations</h3>
126 *
127 * <p>As always, prefer the immutable implementations, {@link
128 * ImmutableListMultimap} and {@link ImmutableSetMultimap}. General-purpose
129 * mutable implementations are listed above under "All Known Implementing
130 * Classes". You can also create a <i>custom</i> multimap, backed by any {@code
131 * Map} and {@link Collection} types, using the {@link Multimaps#newMultimap
132 * Multimaps.newMultimap} family of methods. Finally, another popular way to
133 * obtain a multimap is using {@link Multimaps#index Multimaps.index}. See
134 * the {@link Multimaps} class for these and other static utilities related
135 * to multimaps.
136 *
137 * <h3>Other Notes</h3>
138 *
139 * <p>All methods that modify the multimap are optional. The view collections
140 * returned by the multimap may or may not be modifiable. Any modification
141 * method that is not supported will throw {@link
142 * UnsupportedOperationException}.
143 *
144 * <p>See the Guava User Guide article on <a href=
145 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
146 * {@code Multimap}</a>.
147 *
148 * @author Jared Levy
149 * @since 2.0 (imported from Google Collections Library)
150 */
151@GwtCompatible
152public interface Multimap<K, V> {
153  // Query Operations
154
155  /** Returns the number of key-value pairs in the multimap. */
156  int size();
157
158  /** Returns {@code true} if the multimap contains no key-value pairs. */
159  boolean isEmpty();
160
161  /**
162   * Returns {@code true} if the multimap contains any values for the specified
163   * key.
164   *
165   * @param key key to search for in multimap
166   */
167  boolean containsKey(@Nullable Object key);
168
169  /**
170   * Returns {@code true} if the multimap contains the specified value for any
171   * key.
172   *
173   * @param value value to search for in multimap
174   */
175  boolean containsValue(@Nullable Object value);
176
177  /**
178   * Returns {@code true} if the multimap contains the specified key-value pair.
179   *
180   * @param key key to search for in multimap
181   * @param value value to search for in multimap
182   */
183  boolean containsEntry(@Nullable Object key, @Nullable Object value);
184
185  // Modification Operations
186
187  /**
188   * Stores a key-value pair in the multimap.
189   *
190   * <p>Some multimap implementations allow duplicate key-value pairs, in which
191   * case {@code put} always adds a new key-value pair and increases the
192   * multimap size by 1. Other implementations prohibit duplicates, and storing
193   * a key-value pair that's already in the multimap has no effect.
194   *
195   * @param key key to store in the multimap
196   * @param value value to store in the multimap
197   * @return {@code true} if the method increased the size of the multimap, or
198   *     {@code false} if the multimap already contained the key-value pair and
199   *     doesn't allow duplicates
200   */
201  boolean put(@Nullable K key, @Nullable V value);
202
203  /**
204   * Removes a single key-value pair from the multimap.
205   *
206   * @param key key of entry to remove from the multimap
207   * @param value value of entry to remove the multimap
208   * @return {@code true} if the multimap changed
209   */
210  boolean remove(@Nullable Object key, @Nullable Object value);
211
212  // Bulk Operations
213
214  /**
215   * Stores a collection of values with the same key.
216   *
217   * @param key key to store in the multimap
218   * @param values values to store in the multimap
219   * @return {@code true} if the multimap changed
220   */
221  boolean putAll(@Nullable K key, Iterable<? extends V> values);
222
223  /**
224   * Copies all of another multimap's key-value pairs into this multimap. The
225   * order in which the mappings are added is determined by
226   * {@code multimap.entries()}.
227   *
228   * @param multimap mappings to store in this multimap
229   * @return {@code true} if the multimap changed
230   */
231  boolean putAll(Multimap<? extends K, ? extends V> multimap);
232
233  /**
234   * Stores a collection of values with the same key, replacing any existing
235   * values for that key.
236   *
237   * @param key key to store in the multimap
238   * @param values values to store in the multimap
239   * @return the collection of replaced values, or an empty collection if no
240   *     values were previously associated with the key. The collection
241   *     <i>may</i> be modifiable, but updating it will have no effect on the
242   *     multimap.
243   */
244  Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values);
245
246  /**
247   * Removes all values associated with a given key.
248   *
249   * @param key key of entries to remove from the multimap
250   * @return the collection of removed values, or an empty collection if no
251   *     values were associated with the provided key. The collection
252   *     <i>may</i> be modifiable, but updating it will have no effect on the
253   *     multimap.
254   */
255  Collection<V> removeAll(@Nullable Object key);
256
257  /**
258   * Removes all key-value pairs from the multimap.
259   */
260  void clear();
261
262  // Views
263
264  /**
265   * Returns a collection view of all values associated with a key. If no
266   * mappings in the multimap have the provided key, an empty collection is
267   * returned.
268   *
269   * <p>Changes to the returned collection will update the underlying multimap,
270   * and vice versa.
271   *
272   * @param key key to search for in multimap
273   * @return the collection of values that the key maps to
274   */
275  Collection<V> get(@Nullable K key);
276
277  /**
278   * Returns the set of all keys, each appearing once in the returned set.
279   * Changes to the returned set will update the underlying multimap, and vice
280   * versa.
281   *
282   * @return the collection of distinct keys
283   */
284  Set<K> keySet();
285
286  /**
287   * Returns a collection, which may contain duplicates, of all keys. The number
288   * of times of key appears in the returned multiset equals the number of
289   * mappings the key has in the multimap. Changes to the returned multiset will
290   * update the underlying multimap, and vice versa.
291   *
292   * @return a multiset with keys corresponding to the distinct keys of the
293   *     multimap and frequencies corresponding to the number of values that
294   *     each key maps to
295   */
296  Multiset<K> keys();
297
298  /**
299   * Returns a collection of all values in the multimap. Changes to the returned
300   * collection will update the underlying multimap, and vice versa.
301   *
302   * @return collection of values, which may include the same value multiple
303   *     times if it occurs in multiple mappings
304   */
305  Collection<V> values();
306
307  /**
308   * Returns a collection of all key-value pairs. Changes to the returned
309   * collection will update the underlying multimap, and vice versa. The entries
310   * collection does not support the {@code add} or {@code addAll} operations.
311   *
312   * @return collection of map entries consisting of key-value pairs
313   */
314  Collection<Map.Entry<K, V>> entries();
315
316  /**
317   * Returns a map view that associates each key with the corresponding values
318   * in the multimap. Changes to the returned map, such as element removal, will
319   * update the underlying multimap. The map does not support {@code setValue()}
320   * on its entries, {@code put}, or {@code putAll}.
321   *
322   * <p>When passed a key that is present in the map, {@code
323   * asMap().get(Object)} has the same behavior as {@link #get}, returning a
324   * live collection. When passed a key that is not present, however, {@code
325   * asMap().get(Object)} returns {@code null} instead of an empty collection.
326   *
327   * @return a map view from a key to its collection of values
328   */
329  Map<K, Collection<V>> asMap();
330
331  // Comparison and hashing
332
333  /**
334   * Compares the specified object with this multimap for equality. Two
335   * multimaps are equal when their map views, as returned by {@link #asMap},
336   * are also equal.
337   *
338   * <p>In general, two multimaps with identical key-value mappings may or may
339   * not be equal, depending on the implementation. For example, two
340   * {@link SetMultimap} instances with the same key-value mappings are equal,
341   * but equality of two {@link ListMultimap} instances depends on the ordering
342   * of the values for each key.
343   *
344   * <p>A non-empty {@link SetMultimap} cannot be equal to a non-empty
345   * {@link ListMultimap}, since their {@link #asMap} views contain unequal
346   * collections as values. However, any two empty multimaps are equal, because
347   * they both have empty {@link #asMap} views.
348   */
349  @Override
350  boolean equals(@Nullable Object obj);
351
352  /**
353   * Returns the hash code for this multimap.
354   *
355   * <p>The hash code of a multimap is defined as the hash code of the map view,
356   * as returned by {@link Multimap#asMap}.
357   */
358  @Override
359  int hashCode();
360}