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 * <ul> 136 * <li>{@link ImmutableListMultimap} 137 * <li>{@link ImmutableSetMultimap} 138 * <li>Configure your own mutable multimap with {@link MultimapBuilder} 139 * <li>{@link LinkedListMultimap} (for one unusual kind of mutable {@code Multimap}) 140 * </ul> 141 * 142 * Guava contains a number of other multimap implementations, such as {@link ArrayListMultimap}. In 143 * new code, we recommend using {@link MultimapBuilder} instead: It provides better control of how 144 * keys and values are stored. 145 * 146 * <h3>Other Notes</h3> 147 * 148 * <p>As with {@code Map}, the behavior of a {@code Multimap} is not specified if key objects 149 * already present in the multimap change in a manner that affects {@code equals} comparisons. Use 150 * caution if mutable objects are used as keys in a {@code Multimap}. 151 * 152 * <p>All methods that modify the multimap are optional. The view collections returned by the 153 * multimap may or may not be modifiable. Any modification method that is not supported will throw 154 * {@link UnsupportedOperationException}. 155 * 156 * <p>See the Guava User Guide article on <a href= 157 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>. 158 * 159 * @author Jared Levy 160 * @since 2.0 161 */ 162@DoNotMock("Use ImmutableMultimap, HashMultimap, or another implementation") 163@GwtCompatible 164@ElementTypesAreNonnullByDefault 165public interface Multimap<K extends @Nullable Object, V extends @Nullable Object> { 166 // Query Operations 167 168 /** 169 * Returns the number of key-value pairs in this multimap. 170 * 171 * <p><b>Note:</b> this method does not return the number of <i>distinct keys</i> in the multimap, 172 * which is given by {@code keySet().size()} or {@code asMap().size()}. See the opening section of 173 * the {@link Multimap} class documentation for clarification. 174 */ 175 int size(); 176 177 /** 178 * Returns {@code true} if this multimap contains no key-value pairs. Equivalent to {@code size() 179 * == 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 with the key {@code 185 * key}. 186 */ 187 boolean containsKey(@CompatibleWith("K") @CheckForNull Object key); 188 189 /** 190 * Returns {@code true} if this multimap contains at least one key-value pair with the value 191 * {@code value}. 192 */ 193 boolean containsValue(@CompatibleWith("V") @CheckForNull Object value); 194 195 /** 196 * Returns {@code true} if this multimap contains at least one key-value pair with the key {@code 197 * key} and the value {@code value}. 198 */ 199 boolean containsEntry( 200 @CompatibleWith("K") @CheckForNull Object key, 201 @CompatibleWith("V") @CheckForNull Object value); 202 203 // Modification Operations 204 205 /** 206 * Stores a key-value pair in this multimap. 207 * 208 * <p>Some multimap implementations allow duplicate key-value pairs, in which case {@code put} 209 * always adds a new key-value pair and increases the multimap size by 1. Other implementations 210 * prohibit duplicates, and storing a key-value pair that's already in the multimap has no effect. 211 * 212 * @return {@code true} if the method increased the size of the multimap, or {@code false} if the 213 * multimap already contained the key-value pair and doesn't allow duplicates 214 */ 215 @CanIgnoreReturnValue 216 boolean put(@ParametricNullness K key, @ParametricNullness V value); 217 218 /** 219 * Removes a single key-value pair with the key {@code key} and the value {@code value} from this 220 * multimap, if such exists. If multiple key-value pairs in the multimap fit this description, 221 * which one is removed is unspecified. 222 * 223 * @return {@code true} if the multimap changed 224 */ 225 @CanIgnoreReturnValue 226 boolean remove( 227 @CompatibleWith("K") @CheckForNull Object key, 228 @CompatibleWith("V") @CheckForNull Object value); 229 230 // Bulk Operations 231 232 /** 233 * Stores a key-value pair in this multimap for each of {@code values}, all using the same key, 234 * {@code key}. Equivalent to (but expected to be more efficient than): 235 * 236 * <pre>{@code 237 * for (V value : values) { 238 * put(key, value); 239 * } 240 * }</pre> 241 * 242 * <p>In particular, this is a no-op if {@code values} is empty. 243 * 244 * @return {@code true} if the multimap changed 245 */ 246 @CanIgnoreReturnValue 247 boolean putAll(@ParametricNullness K key, Iterable<? extends V> values); 248 249 /** 250 * Stores all key-value pairs of {@code multimap} in this multimap, in the order returned by 251 * {@code multimap.entries()}. 252 * 253 * @return {@code true} if the multimap changed 254 */ 255 @CanIgnoreReturnValue 256 boolean putAll(Multimap<? extends K, ? extends V> multimap); 257 258 /** 259 * Stores a collection of values with the same key, replacing any existing values for that key. 260 * 261 * <p>If {@code values} is empty, this is equivalent to {@link #removeAll(Object) removeAll(key)}. 262 * 263 * @return the collection of replaced values, or an empty collection if no values were previously 264 * associated with the key. The collection <i>may</i> be modifiable, but updating it will have 265 * no effect on the multimap. 266 */ 267 @CanIgnoreReturnValue 268 Collection<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values); 269 270 /** 271 * Removes all values associated with the key {@code key}. 272 * 273 * <p>Once this method returns, {@code key} will not be mapped to any values, so it will not 274 * appear in {@link #keySet()}, {@link #asMap()}, or any other views. 275 * 276 * @return the values that were removed (possibly empty). The returned collection <i>may</i> be 277 * modifiable, but updating it will have no effect on the multimap. 278 */ 279 @CanIgnoreReturnValue 280 Collection<V> removeAll(@CompatibleWith("K") @CheckForNull Object key); 281 282 /** Removes all key-value pairs from the multimap, leaving it {@linkplain #isEmpty empty}. */ 283 void clear(); 284 285 // Views 286 287 /** 288 * Returns a view collection of the values associated with {@code key} in this multimap, if any. 289 * Note that when {@code containsKey(key)} is false, this returns an empty collection, not {@code 290 * null}. 291 * 292 * <p>Changes to the returned collection will update the underlying multimap, and vice versa. 293 */ 294 Collection<V> get(@ParametricNullness K key); 295 296 /** 297 * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the 298 * key set contains a key if and only if this multimap maps that key to at least one value. 299 * 300 * <p>Changes to the returned set will update the underlying multimap, and vice versa. However, 301 * <i>adding</i> to the returned set is not possible. 302 */ 303 Set<K> keySet(); 304 305 /** 306 * Returns a view collection containing the key from each key-value pair in this multimap, 307 * <i>without</i> collapsing duplicates. This collection has the same size as this multimap, and 308 * {@code keys().count(k) == get(k).size()} for all {@code k}. 309 * 310 * <p>Changes to the returned multiset will update the underlying multimap, and vice versa. 311 * However, <i>adding</i> to the returned collection is not possible. 312 */ 313 Multiset<K> keys(); 314 315 /** 316 * Returns a view collection containing the <i>value</i> from each key-value pair contained in 317 * this multimap, without collapsing duplicates (so {@code values().size() == size()}). 318 * 319 * <p>Changes to the returned collection will update the underlying multimap, and vice versa. 320 * However, <i>adding</i> to the returned collection is not possible. 321 */ 322 Collection<V> values(); 323 324 /** 325 * Returns a view collection of all key-value pairs contained in this multimap, as {@link Entry} 326 * instances. 327 * 328 * <p>Changes to the returned collection or the entries it contains will update the underlying 329 * multimap, and vice versa. However, <i>adding</i> to the returned collection is not possible. 330 */ 331 Collection<Entry<K, V>> entries(); 332 333 /** 334 * Returns a view of this multimap as a {@code Map} from each distinct key to the nonempty 335 * collection of that key's associated values. Note that {@code this.asMap().get(k)} is equivalent 336 * to {@code this.get(k)} only when {@code k} is a key contained in the multimap; otherwise it 337 * returns {@code null} as opposed to an empty collection. 338 * 339 * <p>Changes to the returned map or the collections that serve as its values will update the 340 * underlying multimap, and vice versa. The map does not support {@code put} or {@code putAll}, 341 * nor do its entries support {@link Entry#setValue setValue}. 342 */ 343 Map<K, Collection<V>> asMap(); 344 345 // Comparison and hashing 346 347 /** 348 * Compares the specified object with this multimap for equality. Two multimaps are equal when 349 * their map views, as returned by {@link #asMap}, are also equal. 350 * 351 * <p>In general, two multimaps with identical key-value mappings may or may not be equal, 352 * depending on the implementation. For example, two {@link SetMultimap} instances with the same 353 * key-value mappings are equal, but equality of two {@link ListMultimap} instances depends on the 354 * ordering of the values for each key. 355 * 356 * <p>A non-empty {@link SetMultimap} cannot be equal to a non-empty {@link ListMultimap}, since 357 * their {@link #asMap} views contain unequal collections as values. However, any two empty 358 * multimaps are equal, because they both have empty {@link #asMap} views. 359 */ 360 @Override 361 boolean equals(@CheckForNull Object obj); 362 363 /** 364 * Returns the hash code for this multimap. 365 * 366 * <p>The hash code of a multimap is defined as the hash code of the map view, as returned by 367 * {@link Multimap#asMap}. 368 * 369 * <p>In general, two multimaps with identical key-value mappings may or may not have the same 370 * hash codes, depending on the implementation. For example, two {@link SetMultimap} instances 371 * with the same key-value mappings will have the same {@code hashCode}, but the {@code hashCode} 372 * of {@link ListMultimap} instances depends on the ordering of the values for each key. 373 */ 374 @Override 375 int hashCode(); 376}