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