001/* 002 * Copyright (C) 2008 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 java.util.Objects.requireNonNull; 020 021import com.google.common.annotations.GwtCompatible; 022import com.google.common.annotations.GwtIncompatible; 023import com.google.common.annotations.J2ktIncompatible; 024import com.google.errorprone.annotations.CanIgnoreReturnValue; 025import com.google.errorprone.annotations.DoNotCall; 026import com.google.errorprone.annotations.concurrent.LazyInit; 027import com.google.j2objc.annotations.RetainedWith; 028import java.io.IOException; 029import java.io.InvalidObjectException; 030import java.io.ObjectInputStream; 031import java.io.ObjectOutputStream; 032import java.util.Collection; 033import java.util.Comparator; 034import java.util.Map; 035import java.util.Map.Entry; 036import java.util.function.Function; 037import java.util.stream.Collector; 038import java.util.stream.Stream; 039import javax.annotation.CheckForNull; 040import org.checkerframework.checker.nullness.qual.Nullable; 041 042/** 043 * A {@link ListMultimap} whose contents will never change, with many other important properties 044 * detailed at {@link ImmutableCollection}. 045 * 046 * <p>See the Guava User Guide article on <a href= 047 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 048 * 049 * @author Jared Levy 050 * @since 2.0 051 */ 052@GwtCompatible(serializable = true, emulated = true) 053@ElementTypesAreNonnullByDefault 054public class ImmutableListMultimap<K, V> extends ImmutableMultimap<K, V> 055 implements ListMultimap<K, V> { 056 /** 057 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableListMultimap} 058 * whose keys and values are the result of applying the provided mapping functions to the input 059 * elements. 060 * 061 * <p>For streams with defined encounter order (as defined in the Ordering section of the {@link 062 * java.util.stream} Javadoc), that order is preserved, but entries are <a 063 * href="ImmutableMultimap.html#iteration">grouped by key</a>. 064 * 065 * <p>Example: 066 * 067 * <pre>{@code 068 * static final Multimap<Character, String> FIRST_LETTER_MULTIMAP = 069 * Stream.of("banana", "apple", "carrot", "asparagus", "cherry") 070 * .collect(toImmutableListMultimap(str -> str.charAt(0), str -> str.substring(1))); 071 * 072 * // is equivalent to 073 * 074 * static final Multimap<Character, String> FIRST_LETTER_MULTIMAP = 075 * new ImmutableListMultimap.Builder<Character, String>() 076 * .put('b', "anana") 077 * .putAll('a', "pple", "sparagus") 078 * .putAll('c', "arrot", "herry") 079 * .build(); 080 * }</pre> 081 * 082 * @since 21.0 083 */ 084 public static <T extends @Nullable Object, K, V> 085 Collector<T, ?, ImmutableListMultimap<K, V>> toImmutableListMultimap( 086 Function<? super T, ? extends K> keyFunction, 087 Function<? super T, ? extends V> valueFunction) { 088 return CollectCollectors.toImmutableListMultimap(keyFunction, valueFunction); 089 } 090 091 /** 092 * Returns a {@code Collector} accumulating entries into an {@code ImmutableListMultimap}. Each 093 * input element is mapped to a key and a stream of values, each of which are put into the 094 * resulting {@code Multimap}, in the encounter order of the stream and the encounter order of the 095 * streams of values. 096 * 097 * <p>Example: 098 * 099 * <pre>{@code 100 * static final ImmutableListMultimap<Character, Character> FIRST_LETTER_MULTIMAP = 101 * Stream.of("banana", "apple", "carrot", "asparagus", "cherry") 102 * .collect( 103 * flatteningToImmutableListMultimap( 104 * str -> str.charAt(0), 105 * str -> str.substring(1).chars().mapToObj(c -> (char) c)); 106 * 107 * // is equivalent to 108 * 109 * static final ImmutableListMultimap<Character, Character> FIRST_LETTER_MULTIMAP = 110 * ImmutableListMultimap.<Character, Character>builder() 111 * .putAll('b', Arrays.asList('a', 'n', 'a', 'n', 'a')) 112 * .putAll('a', Arrays.asList('p', 'p', 'l', 'e')) 113 * .putAll('c', Arrays.asList('a', 'r', 'r', 'o', 't')) 114 * .putAll('a', Arrays.asList('s', 'p', 'a', 'r', 'a', 'g', 'u', 's')) 115 * .putAll('c', Arrays.asList('h', 'e', 'r', 'r', 'y')) 116 * .build(); 117 * } 118 * }</pre> 119 * 120 * @since 21.0 121 */ 122 public static <T extends @Nullable Object, K, V> 123 Collector<T, ?, ImmutableListMultimap<K, V>> flatteningToImmutableListMultimap( 124 Function<? super T, ? extends K> keyFunction, 125 Function<? super T, ? extends Stream<? extends V>> valuesFunction) { 126 return CollectCollectors.flatteningToImmutableListMultimap(keyFunction, valuesFunction); 127 } 128 129 /** 130 * Returns the empty multimap. 131 * 132 * <p><b>Performance note:</b> the instance returned is a singleton. 133 */ 134 // Casting is safe because the multimap will never hold any elements. 135 @SuppressWarnings("unchecked") 136 public static <K, V> ImmutableListMultimap<K, V> of() { 137 return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE; 138 } 139 140 /** Returns an immutable multimap containing a single entry. */ 141 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) { 142 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 143 builder.put(k1, v1); 144 return builder.build(); 145 } 146 147 /** Returns an immutable multimap containing the given entries, in order. */ 148 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) { 149 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 150 builder.put(k1, v1); 151 builder.put(k2, v2); 152 return builder.build(); 153 } 154 155 /** Returns an immutable multimap containing the given entries, in order. */ 156 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) { 157 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 158 builder.put(k1, v1); 159 builder.put(k2, v2); 160 builder.put(k3, v3); 161 return builder.build(); 162 } 163 164 /** Returns an immutable multimap containing the given entries, in order. */ 165 public static <K, V> ImmutableListMultimap<K, V> of( 166 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 167 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 168 builder.put(k1, v1); 169 builder.put(k2, v2); 170 builder.put(k3, v3); 171 builder.put(k4, v4); 172 return builder.build(); 173 } 174 175 /** Returns an immutable multimap containing the given entries, in order. */ 176 public static <K, V> ImmutableListMultimap<K, V> of( 177 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 178 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 179 builder.put(k1, v1); 180 builder.put(k2, v2); 181 builder.put(k3, v3); 182 builder.put(k4, v4); 183 builder.put(k5, v5); 184 return builder.build(); 185 } 186 187 // looking for of() with > 5 entries? Use the builder instead. 188 189 /** 190 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 191 * Builder} constructor. 192 */ 193 public static <K, V> Builder<K, V> builder() { 194 return new Builder<>(); 195 } 196 197 /** 198 * A builder for creating immutable {@code ListMultimap} instances, especially {@code public 199 * static final} multimaps ("constant multimaps"). Example: 200 * 201 * <pre>{@code 202 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP = 203 * new ImmutableListMultimap.Builder<String, Integer>() 204 * .put("one", 1) 205 * .putAll("several", 1, 2, 3) 206 * .putAll("many", 1, 2, 3, 4, 5) 207 * .build(); 208 * }</pre> 209 * 210 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 211 * multiple multimaps in series. Each multimap contains the key-value mappings in the previously 212 * created multimaps. 213 * 214 * @since 2.0 215 */ 216 public static final class Builder<K, V> extends ImmutableMultimap.Builder<K, V> { 217 /** 218 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 219 * ImmutableListMultimap#builder}. 220 */ 221 public Builder() {} 222 223 @CanIgnoreReturnValue 224 @Override 225 public Builder<K, V> put(K key, V value) { 226 super.put(key, value); 227 return this; 228 } 229 230 /** 231 * {@inheritDoc} 232 * 233 * @since 11.0 234 */ 235 @CanIgnoreReturnValue 236 @Override 237 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 238 super.put(entry); 239 return this; 240 } 241 242 /** 243 * {@inheritDoc} 244 * 245 * @since 19.0 246 */ 247 @CanIgnoreReturnValue 248 @Override 249 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 250 super.putAll(entries); 251 return this; 252 } 253 254 @CanIgnoreReturnValue 255 @Override 256 public Builder<K, V> putAll(K key, Iterable<? extends V> values) { 257 super.putAll(key, values); 258 return this; 259 } 260 261 @CanIgnoreReturnValue 262 @Override 263 public Builder<K, V> putAll(K key, V... values) { 264 super.putAll(key, values); 265 return this; 266 } 267 268 @CanIgnoreReturnValue 269 @Override 270 public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) { 271 super.putAll(multimap); 272 return this; 273 } 274 275 @CanIgnoreReturnValue 276 @Override 277 Builder<K, V> combine(ImmutableMultimap.Builder<K, V> other) { 278 super.combine(other); 279 return this; 280 } 281 282 /** 283 * {@inheritDoc} 284 * 285 * @since 8.0 286 */ 287 @CanIgnoreReturnValue 288 @Override 289 public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) { 290 super.orderKeysBy(keyComparator); 291 return this; 292 } 293 294 /** 295 * {@inheritDoc} 296 * 297 * @since 8.0 298 */ 299 @CanIgnoreReturnValue 300 @Override 301 public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) { 302 super.orderValuesBy(valueComparator); 303 return this; 304 } 305 306 /** Returns a newly-created immutable list multimap. */ 307 @Override 308 public ImmutableListMultimap<K, V> build() { 309 return (ImmutableListMultimap<K, V>) super.build(); 310 } 311 } 312 313 /** 314 * Returns an immutable multimap containing the same mappings as {@code multimap}. The generated 315 * multimap's key and value orderings correspond to the iteration ordering of the {@code 316 * multimap.asMap()} view. 317 * 318 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 319 * safe to do so. The exact circumstances under which a copy will or will not be performed are 320 * undocumented and subject to change. 321 * 322 * @throws NullPointerException if any key or value in {@code multimap} is null 323 */ 324 public static <K, V> ImmutableListMultimap<K, V> copyOf( 325 Multimap<? extends K, ? extends V> multimap) { 326 if (multimap.isEmpty()) { 327 return of(); 328 } 329 330 // TODO(lowasser): copy ImmutableSetMultimap by using asList() on the sets 331 if (multimap instanceof ImmutableListMultimap) { 332 @SuppressWarnings("unchecked") // safe since multimap is not writable 333 ImmutableListMultimap<K, V> kvMultimap = (ImmutableListMultimap<K, V>) multimap; 334 if (!kvMultimap.isPartialView()) { 335 return kvMultimap; 336 } 337 } 338 339 return fromMapEntries(multimap.asMap().entrySet(), null); 340 } 341 342 /** 343 * Returns an immutable multimap containing the specified entries. The returned multimap iterates 344 * over keys in the order they were first encountered in the input, and the values for each key 345 * are iterated in the order they were encountered. 346 * 347 * @throws NullPointerException if any key, value, or entry is null 348 * @since 19.0 349 */ 350 public static <K, V> ImmutableListMultimap<K, V> copyOf( 351 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 352 return new Builder<K, V>().putAll(entries).build(); 353 } 354 355 /** Creates an ImmutableListMultimap from an asMap.entrySet. */ 356 static <K, V> ImmutableListMultimap<K, V> fromMapEntries( 357 Collection<? extends Map.Entry<? extends K, ? extends Collection<? extends V>>> mapEntries, 358 @CheckForNull Comparator<? super V> valueComparator) { 359 if (mapEntries.isEmpty()) { 360 return of(); 361 } 362 ImmutableMap.Builder<K, ImmutableList<V>> builder = 363 new ImmutableMap.Builder<>(mapEntries.size()); 364 int size = 0; 365 366 for (Entry<? extends K, ? extends Collection<? extends V>> entry : mapEntries) { 367 K key = entry.getKey(); 368 Collection<? extends V> values = entry.getValue(); 369 ImmutableList<V> list = 370 (valueComparator == null) 371 ? ImmutableList.copyOf(values) 372 : ImmutableList.sortedCopyOf(valueComparator, values); 373 if (!list.isEmpty()) { 374 builder.put(key, list); 375 size += list.size(); 376 } 377 } 378 379 return new ImmutableListMultimap<>(builder.buildOrThrow(), size); 380 } 381 382 ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) { 383 super(map, size); 384 } 385 386 // views 387 388 /** 389 * Returns an immutable list of the values for the given key. If no mappings in the multimap have 390 * the provided key, an empty immutable list is returned. The values are in the same order as the 391 * parameters used to build this multimap. 392 */ 393 @Override 394 public ImmutableList<V> get(K key) { 395 // This cast is safe as its type is known in constructor. 396 ImmutableList<V> list = (ImmutableList<V>) map.get(key); 397 return (list == null) ? ImmutableList.<V>of() : list; 398 } 399 400 @LazyInit @RetainedWith @CheckForNull private transient ImmutableListMultimap<V, K> inverse; 401 402 /** 403 * {@inheritDoc} 404 * 405 * <p>Because an inverse of a list multimap can contain multiple pairs with the same key and 406 * value, this method returns an {@code ImmutableListMultimap} rather than the {@code 407 * ImmutableMultimap} specified in the {@code ImmutableMultimap} class. 408 * 409 * @since 11.0 410 */ 411 @Override 412 public ImmutableListMultimap<V, K> inverse() { 413 ImmutableListMultimap<V, K> result = inverse; 414 return (result == null) ? (inverse = invert()) : result; 415 } 416 417 private ImmutableListMultimap<V, K> invert() { 418 Builder<V, K> builder = builder(); 419 for (Entry<K, V> entry : entries()) { 420 builder.put(entry.getValue(), entry.getKey()); 421 } 422 ImmutableListMultimap<V, K> invertedMultimap = builder.build(); 423 invertedMultimap.inverse = this; 424 return invertedMultimap; 425 } 426 427 /** 428 * Guaranteed to throw an exception and leave the multimap unmodified. 429 * 430 * @throws UnsupportedOperationException always 431 * @deprecated Unsupported operation. 432 */ 433 @CanIgnoreReturnValue 434 @Deprecated 435 @Override 436 @DoNotCall("Always throws UnsupportedOperationException") 437 public final ImmutableList<V> removeAll(@CheckForNull Object key) { 438 throw new UnsupportedOperationException(); 439 } 440 441 /** 442 * Guaranteed to throw an exception and leave the multimap unmodified. 443 * 444 * @throws UnsupportedOperationException always 445 * @deprecated Unsupported operation. 446 */ 447 @CanIgnoreReturnValue 448 @Deprecated 449 @Override 450 @DoNotCall("Always throws UnsupportedOperationException") 451 public final ImmutableList<V> replaceValues(K key, Iterable<? extends V> values) { 452 throw new UnsupportedOperationException(); 453 } 454 455 /** 456 * @serialData number of distinct keys, and then for each distinct key: the key, the number of 457 * values for that key, and the key's values 458 */ 459 @GwtIncompatible // java.io.ObjectOutputStream 460 @J2ktIncompatible 461 private void writeObject(ObjectOutputStream stream) throws IOException { 462 stream.defaultWriteObject(); 463 Serialization.writeMultimap(this, stream); 464 } 465 466 @GwtIncompatible // java.io.ObjectInputStream 467 @J2ktIncompatible 468 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 469 stream.defaultReadObject(); 470 int keyCount = stream.readInt(); 471 if (keyCount < 0) { 472 throw new InvalidObjectException("Invalid key count " + keyCount); 473 } 474 ImmutableMap.Builder<Object, ImmutableList<Object>> builder = ImmutableMap.builder(); 475 int tmpSize = 0; 476 477 for (int i = 0; i < keyCount; i++) { 478 Object key = requireNonNull(stream.readObject()); 479 int valueCount = stream.readInt(); 480 if (valueCount <= 0) { 481 throw new InvalidObjectException("Invalid value count " + valueCount); 482 } 483 484 ImmutableList.Builder<Object> valuesBuilder = ImmutableList.builder(); 485 for (int j = 0; j < valueCount; j++) { 486 valuesBuilder.add(requireNonNull(stream.readObject())); 487 } 488 builder.put(key, valuesBuilder.build()); 489 tmpSize += valueCount; 490 } 491 492 ImmutableMap<Object, ImmutableList<Object>> tmpMap; 493 try { 494 tmpMap = builder.buildOrThrow(); 495 } catch (IllegalArgumentException e) { 496 throw (InvalidObjectException) new InvalidObjectException(e.getMessage()).initCause(e); 497 } 498 499 FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap); 500 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize); 501 } 502 503 @GwtIncompatible // Not needed in emulated source 504 @J2ktIncompatible 505 private static final long serialVersionUID = 0; 506}