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