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    
017    package com.google.common.collect;
018    
019    import com.google.common.annotations.GwtCompatible;
020    
021    import java.util.Collection;
022    import java.util.List;
023    import java.util.Map;
024    import java.util.Set;
025    
026    import 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
152    public 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    }