1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import com.google.common.annotations.GwtCompatible; 20 21import java.util.Collection; 22import java.util.List; 23import java.util.Map; 24import java.util.Set; 25 26import javax.annotation.Nullable; 27 28/** 29 * A collection that maps keys to values, similar to {@link Map}, but in which 30 * each key may be associated with <i>multiple</i> values. You can visualize the 31 * contents of a multimap either as a map from keys to <i>nonempty</i> 32 * collections of values: 33 * 34 * <ul> 35 * <li>a → 1, 2 36 * <li>b → 3 37 * </ul> 38 * 39 * ... or as a single "flattened" collection of key-value pairs: 40 * 41 * <ul> 42 * <li>a → 1 43 * <li>a → 2 44 * <li>b → 3 45 * </ul> 46 * 47 * <p><b>Important:</b> although the first interpretation resembles how most 48 * multimaps are <i>implemented</i>, the design of the {@code Multimap} API is 49 * based on the <i>second</i> form. So, using the multimap shown above as an 50 * example, the {@link #size} is {@code 3}, not {@code 2}, and the {@link 51 * #values} collection is {@code [1, 2, 3]}, not {@code [[1, 2], [3]]}. For 52 * those times when the first style is more useful, use the multimap's {@link 53 * #asMap} view (or create a {@code Map<K, Collection<V>>} in the first place). 54 * 55 * <h3>Example</h3> 56 * 57 * <p>The following code: <pre> {@code 58 * 59 * ListMultimap<String, String> multimap = ArrayListMultimap.create(); 60 * for (President pres : US_PRESIDENTS_IN_ORDER) { 61 * multimap.put(pres.firstName(), pres.lastName()); 62 * } 63 * for (String firstName : multimap.keySet()) { 64 * List<String> lastNames = multimap.get(firstName); 65 * out.println(firstName + ": " + lastNames); 66 * }}</pre> 67 * 68 * ... produces output such as: <pre> {@code 69 * 70 * Zachary: [Taylor] 71 * John: [Adams, Adams, Tyler, Kennedy] // Remember, Quincy! 72 * George: [Washington, Bush, Bush] 73 * Grover: [Cleveland, Cleveland] // Two, non-consecutive terms, rep'ing NJ! 74 * ...}</pre> 75 * 76 * <h3>Views</h3> 77 * 78 * <p>Much of the power of the multimap API comes from the <i>view 79 * collections</i> it provides. These always reflect the latest state of the 80 * multimap itself. When they support modification, the changes are 81 * <i>write-through</i> (they automatically update the backing multimap). These 82 * view collections are: 83 * 84 * <ul> 85 * <li>{@link #asMap}, mentioned above</li> 86 * <li>{@link #keys}, {@link #keySet}, {@link #values}, {@link #entries}, which 87 * are similar to the corresponding view collections of {@link Map} 88 * <li>and, notably, even the collection returned by {@link #get get(key)} is an 89 * active view of the values corresponding to {@code key} 90 * </ul> 91 * 92 * <p>The collections returned by the {@link #replaceValues replaceValues} and 93 * {@link #removeAll removeAll} methods, which contain values that have just 94 * been removed from the multimap, are naturally <i>not</i> views. 95 * 96 * <h3>Subinterfaces</h3> 97 * 98 * <p>Instead of using the {@code Multimap} interface directly, prefer the 99 * 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 and may or 111 * may not have the same {@code hashCode}. The recommended subinterfaces 112 * provide much stronger guarantees. 113 * 114 * <h3>Comparison to a map of collections</h3> 115 * 116 * <p>Multimaps are commonly used in places where a {@code Map<K, 117 * Collection<V>>} would otherwise have appeared. The differences include: 118 * 119 * <ul> 120 * <li>There is no need to populate an empty collection before adding an entry 121 * with {@link #put put}. 122 * <li>{@code get} never returns {@code null}, only an empty collection. 123 * <li>A key is contained in the multimap if and only if it maps to at least 124 * one value. Any operation that causes a key to have zero associated 125 * values has the effect of <i>removing</i> that key from the multimap. 126 * <li>The total entry count is available as {@link #size}. 127 * <li>Many complex operations become easier; for example, {@code 128 * Collections.min(multimap.values())} finds the smallest value across all 129 * keys. 130 * </ul> 131 * 132 * <h3>Implementations</h3> 133 * 134 * <p>As always, prefer the immutable implementations, {@link 135 * ImmutableListMultimap} and {@link ImmutableSetMultimap}. General-purpose 136 * mutable implementations are listed above under "All Known Implementing 137 * Classes". You can also create a <i>custom</i> multimap, backed by any {@code 138 * Map} and {@link Collection} types, using the {@link Multimaps#newMultimap 139 * Multimaps.newMultimap} family of methods. Finally, another popular way to 140 * obtain a multimap is using {@link Multimaps#index Multimaps.index}. See 141 * the {@link Multimaps} class for these and other static utilities related 142 * to multimaps. 143 * 144 * <h3>Other Notes</h3> 145 * 146 * <p>As with {@code Map}, the behavior of a {@code Multimap} is not specified 147 * if key objects already present in the multimap change in a manner that 148 * affects {@code equals} comparisons. Use caution if mutable objects are used 149 * as keys in a {@code Multimap}. 150 * 151 * <p>All methods that modify the multimap are optional. The view collections 152 * returned by the multimap may or may not be modifiable. Any modification 153 * method that is not supported will throw {@link 154 * UnsupportedOperationException}. 155 * 156 * <p>See the Guava User Guide article on <a href= 157 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap"> 158 * {@code Multimap}</a>. 159 * 160 * @author Jared Levy 161 * @since 2.0 (imported from Google Collections Library) 162 */ 163@GwtCompatible 164public interface Multimap<K, V> { 165 // Query Operations 166 167 /** 168 * Returns the number of key-value pairs in this multimap. 169 * 170 * <p><b>Note:</b> this method does not return the number of <i>distinct 171 * keys</i> in the multimap, which is given by {@code keySet().size()} or 172 * {@code asMap().size()}. See the opening section of the {@link Multimap} 173 * class documentation for clarification. 174 */ 175 int size(); 176 177 /** 178 * Returns {@code true} if this multimap contains no key-value pairs. 179 * Equivalent to {@code size() == 0}, but can in some cases be more efficient. 180 */ 181 boolean isEmpty(); 182 183 /** 184 * Returns {@code true} if this multimap contains at least one key-value pair 185 * with the key {@code key}. 186 */ 187 boolean containsKey(@Nullable Object key); 188 189 /** 190 * Returns {@code true} if this multimap contains at least one key-value pair 191 * with the value {@code value}. 192 */ 193 boolean containsValue(@Nullable Object value); 194 195 /** 196 * Returns {@code true} if this multimap contains at least one key-value pair 197 * with the key {@code key} and the value {@code value}. 198 */ 199 boolean containsEntry(@Nullable Object key, @Nullable Object value); 200 201 // Modification Operations 202 203 /** 204 * Stores a key-value pair in this multimap. 205 * 206 * <p>Some multimap implementations allow duplicate key-value pairs, in which 207 * case {@code put} always adds a new key-value pair and increases the 208 * multimap size by 1. Other implementations prohibit duplicates, and storing 209 * a key-value pair that's already in the multimap has no effect. 210 * 211 * @return {@code true} if the method increased the size of the multimap, or 212 * {@code false} if the multimap already contained the key-value pair and 213 * doesn't allow duplicates 214 */ 215 boolean put(@Nullable K key, @Nullable V value); 216 217 /** 218 * Removes a single key-value pair with the key {@code key} and the value 219 * {@code value} from this multimap, if such exists. If multiple key-value 220 * pairs in the multimap fit this description, which one is removed is 221 * unspecified. 222 * 223 * @return {@code true} if the multimap changed 224 */ 225 boolean remove(@Nullable Object key, @Nullable Object value); 226 227 // Bulk Operations 228 229 /** 230 * Stores a key-value pair in this multimap for each of {@code values}, all 231 * using the same key, {@code key}. Equivalent to (but expected to be more 232 * efficient than): <pre> {@code 233 * 234 * for (V value : values) { 235 * put(key, value); 236 * }}</pre> 237 * 238 * <p>In particular, this is a no-op if {@code values} is empty. 239 * 240 * @return {@code true} if the multimap changed 241 */ 242 boolean putAll(@Nullable K key, Iterable<? extends V> values); 243 244 /** 245 * Stores all key-value pairs of {@code multimap} in this multimap, in the 246 * order returned by {@code multimap.entries()}. 247 * 248 * @return {@code true} if the multimap changed 249 */ 250 boolean putAll(Multimap<? extends K, ? extends V> multimap); 251 252 /** 253 * Stores a collection of values with the same key, replacing any existing 254 * values for that key. 255 * 256 * <p>If {@code values} is empty, this is equivalent to 257 * {@link #removeAll(Object) removeAll(key)}. 258 * 259 * @return the collection of replaced values, or an empty collection if no 260 * values were previously associated with the key. The collection 261 * <i>may</i> be modifiable, but updating it will have no effect on the 262 * multimap. 263 */ 264 Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values); 265 266 /** 267 * Removes all values associated with the key {@code key}. 268 * 269 * <p>Once this method returns, {@code key} will not be mapped to any values, 270 * so it will not appear in {@link #keySet()}, {@link #asMap()}, or any other 271 * views. 272 * 273 * @return the values that were removed (possibly empty). The returned 274 * collection <i>may</i> be modifiable, but updating it will have no 275 * effect on the multimap. 276 */ 277 Collection<V> removeAll(@Nullable Object key); 278 279 /** 280 * Removes all key-value pairs from the multimap, leaving it {@linkplain 281 * #isEmpty empty}. 282 */ 283 void clear(); 284 285 // Views 286 287 /** 288 * Returns a view collection of the values associated with {@code key} in this 289 * multimap, if any. Note that when {@code containsKey(key)} is false, this 290 * returns an empty collection, not {@code null}. 291 * 292 * <p>Changes to the returned collection will update the underlying multimap, 293 * and vice versa. 294 */ 295 Collection<V> get(@Nullable K key); 296 297 /** 298 * Returns a view collection of all <i>distinct</i> keys contained in this 299 * multimap. Note that the key set contains a key if and only if this multimap 300 * maps that key to at least one value. 301 * 302 * <p>Changes to the returned set will update the underlying multimap, and 303 * vice versa. However, <i>adding</i> to the returned set is not possible. 304 */ 305 Set<K> keySet(); 306 307 /** 308 * Returns a view collection containing the key from each key-value pair in 309 * this multimap, <i>without</i> collapsing duplicates. This collection has 310 * the same size as this multimap, and {@code keys().count(k) == 311 * get(k).size()} for all {@code k}. 312 * 313 * <p>Changes to the returned multiset will update the underlying multimap, 314 * and vice versa. However, <i>adding</i> to the returned collection is not 315 * possible. 316 */ 317 Multiset<K> keys(); 318 319 /** 320 * Returns a view collection containing the <i>value</i> from each key-value 321 * pair contained in this multimap, without collapsing duplicates (so {@code 322 * values().size() == size()}). 323 * 324 * <p>Changes to the returned collection will update the underlying multimap, 325 * and vice versa. However, <i>adding</i> to the returned collection is not 326 * possible. 327 */ 328 Collection<V> values(); 329 330 /** 331 * Returns a view collection of all key-value pairs contained in this 332 * multimap, as {@link Map.Entry} instances. 333 * 334 * <p>Changes to the returned collection or the entries it contains will 335 * update the underlying multimap, and vice versa. However, <i>adding</i> to 336 * the returned collection is not possible. 337 */ 338 Collection<Map.Entry<K, V>> entries(); 339 340 /** 341 * Returns a view of this multimap as a {@code Map} from each distinct key 342 * to the nonempty collection of that key's associated values. Note that 343 * {@code this.asMap().get(k)} is equivalent to {@code this.get(k)} only when 344 * {@code k} is a key contained in the multimap; otherwise it returns {@code 345 * null} as opposed to an empty collection. 346 * 347 * <p>Changes to the returned map or the collections that serve as its values 348 * will update the underlying multimap, and vice versa. The map does not 349 * support {@code put} or {@code putAll}, nor do its entries support {@link 350 * Map.Entry#setValue setValue}. 351 */ 352 Map<K, Collection<V>> asMap(); 353 354 // Comparison and hashing 355 356 /** 357 * Compares the specified object with this multimap for equality. Two 358 * multimaps are equal when their map views, as returned by {@link #asMap}, 359 * are also equal. 360 * 361 * <p>In general, two multimaps with identical key-value mappings may or may 362 * not be equal, depending on the implementation. For example, two 363 * {@link SetMultimap} instances with the same key-value mappings are equal, 364 * but equality of two {@link ListMultimap} instances depends on the ordering 365 * of the values for each key. 366 * 367 * <p>A non-empty {@link SetMultimap} cannot be equal to a non-empty 368 * {@link ListMultimap}, since their {@link #asMap} views contain unequal 369 * collections as values. However, any two empty multimaps are equal, because 370 * they both have empty {@link #asMap} views. 371 */ 372 @Override 373 boolean equals(@Nullable Object obj); 374 375 /** 376 * Returns the hash code for this multimap. 377 * 378 * <p>The hash code of a multimap is defined as the hash code of the map view, 379 * as returned by {@link Multimap#asMap}. 380 * 381 * <p>In general, two multimaps with identical key-value mappings may or may 382 * not have the same hash codes, depending on the implementation. For 383 * example, two {@link SetMultimap} instances with the same key-value 384 * mappings will have the same {@code hashCode}, but the {@code hashCode} 385 * of {@link ListMultimap} instances depends on the ordering of the values 386 * for each key. 387 */ 388 @Override 389 int hashCode(); 390} 391