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