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