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}