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