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 com.google.common.annotations.Beta; 020import com.google.common.annotations.GwtCompatible; 021import com.google.common.annotations.GwtIncompatible; 022import com.google.errorprone.annotations.CanIgnoreReturnValue; 023import com.google.errorprone.annotations.DoNotCall; 024import com.google.errorprone.annotations.concurrent.LazyInit; 025import com.google.j2objc.annotations.RetainedWith; 026import java.io.IOException; 027import java.io.InvalidObjectException; 028import java.io.ObjectInputStream; 029import java.io.ObjectOutputStream; 030import java.util.Collection; 031import java.util.Comparator; 032import java.util.Map; 033import java.util.Map.Entry; 034import javax.annotation.CheckForNull; 035import org.checkerframework.checker.nullness.qual.Nullable; 036 037/** 038 * A {@link ListMultimap} whose contents will never change, with many other important properties 039 * detailed at {@link ImmutableCollection}. 040 * 041 * <p>See the Guava User Guide article on <a href= 042 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>. 043 * 044 * @author Jared Levy 045 * @since 2.0 046 */ 047@GwtCompatible(serializable = true, emulated = true) 048@ElementTypesAreNonnullByDefault 049public class ImmutableListMultimap<K, V> extends ImmutableMultimap<K, V> 050 implements ListMultimap<K, V> { 051 052 /** 053 * Returns the empty multimap. 054 * 055 * <p><b>Performance note:</b> the instance returned is a singleton. 056 */ 057 // Casting is safe because the multimap will never hold any elements. 058 @SuppressWarnings("unchecked") 059 public static <K, V> ImmutableListMultimap<K, V> of() { 060 return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE; 061 } 062 063 /** Returns an immutable multimap containing a single entry. */ 064 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) { 065 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 066 builder.put(k1, v1); 067 return builder.build(); 068 } 069 070 /** Returns an immutable multimap containing the given entries, in order. */ 071 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) { 072 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 073 builder.put(k1, v1); 074 builder.put(k2, v2); 075 return builder.build(); 076 } 077 078 /** Returns an immutable multimap containing the given entries, in order. */ 079 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) { 080 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 081 builder.put(k1, v1); 082 builder.put(k2, v2); 083 builder.put(k3, v3); 084 return builder.build(); 085 } 086 087 /** Returns an immutable multimap containing the given entries, in order. */ 088 public static <K, V> ImmutableListMultimap<K, V> of( 089 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 090 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 091 builder.put(k1, v1); 092 builder.put(k2, v2); 093 builder.put(k3, v3); 094 builder.put(k4, v4); 095 return builder.build(); 096 } 097 098 /** Returns an immutable multimap containing the given entries, in order. */ 099 public static <K, V> ImmutableListMultimap<K, V> of( 100 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 101 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder(); 102 builder.put(k1, v1); 103 builder.put(k2, v2); 104 builder.put(k3, v3); 105 builder.put(k4, v4); 106 builder.put(k5, v5); 107 return builder.build(); 108 } 109 110 // looking for of() with > 5 entries? Use the builder instead. 111 112 /** 113 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 114 * Builder} constructor. 115 */ 116 public static <K, V> Builder<K, V> builder() { 117 return new Builder<>(); 118 } 119 120 /** 121 * A builder for creating immutable {@code ListMultimap} instances, especially {@code public 122 * static final} multimaps ("constant multimaps"). Example: 123 * 124 * <pre>{@code 125 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP = 126 * new ImmutableListMultimap.Builder<String, Integer>() 127 * .put("one", 1) 128 * .putAll("several", 1, 2, 3) 129 * .putAll("many", 1, 2, 3, 4, 5) 130 * .build(); 131 * }</pre> 132 * 133 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 134 * multiple multimaps in series. Each multimap contains the key-value mappings in the previously 135 * created multimaps. 136 * 137 * @since 2.0 138 */ 139 public static final class Builder<K, V> extends ImmutableMultimap.Builder<K, V> { 140 /** 141 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 142 * ImmutableListMultimap#builder}. 143 */ 144 public Builder() {} 145 146 @CanIgnoreReturnValue 147 @Override 148 public Builder<K, V> put(K key, V value) { 149 super.put(key, value); 150 return this; 151 } 152 153 /** 154 * {@inheritDoc} 155 * 156 * @since 11.0 157 */ 158 @CanIgnoreReturnValue 159 @Override 160 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 161 super.put(entry); 162 return this; 163 } 164 165 /** 166 * {@inheritDoc} 167 * 168 * @since 19.0 169 */ 170 @CanIgnoreReturnValue 171 @Beta 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 @Beta 275 public static <K, V> ImmutableListMultimap<K, V> copyOf( 276 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 277 return new Builder<K, V>().putAll(entries).build(); 278 } 279 280 /** Creates an ImmutableListMultimap from an asMap.entrySet. */ 281 static <K, V> ImmutableListMultimap<K, V> fromMapEntries( 282 Collection<? extends Map.Entry<? extends K, ? extends Collection<? extends V>>> mapEntries, 283 @Nullable Comparator<? super V> valueComparator) { 284 if (mapEntries.isEmpty()) { 285 return of(); 286 } 287 ImmutableMap.Builder<K, ImmutableList<V>> builder = 288 new ImmutableMap.Builder<>(mapEntries.size()); 289 int size = 0; 290 291 for (Entry<? extends K, ? extends Collection<? extends V>> entry : mapEntries) { 292 K key = entry.getKey(); 293 Collection<? extends V> values = entry.getValue(); 294 ImmutableList<V> list = 295 (valueComparator == null) 296 ? ImmutableList.copyOf(values) 297 : ImmutableList.sortedCopyOf(valueComparator, values); 298 if (!list.isEmpty()) { 299 builder.put(key, list); 300 size += list.size(); 301 } 302 } 303 304 return new ImmutableListMultimap<>(builder.build(), size); 305 } 306 307 ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) { 308 super(map, size); 309 } 310 311 // views 312 313 /** 314 * Returns an immutable list of the values for the given key. If no mappings in the multimap have 315 * the provided key, an empty immutable list is returned. The values are in the same order as the 316 * parameters used to build this multimap. 317 */ 318 @Override 319 public ImmutableList<V> get(K key) { 320 // This cast is safe as its type is known in constructor. 321 ImmutableList<V> list = (ImmutableList<V>) map.get(key); 322 return (list == null) ? ImmutableList.<V>of() : list; 323 } 324 325 @LazyInit @RetainedWith @CheckForNull private transient ImmutableListMultimap<V, K> inverse; 326 327 /** 328 * {@inheritDoc} 329 * 330 * <p>Because an inverse of a list multimap can contain multiple pairs with the same key and 331 * value, this method returns an {@code ImmutableListMultimap} rather than the {@code 332 * ImmutableMultimap} specified in the {@code ImmutableMultimap} class. 333 * 334 * @since 11.0 335 */ 336 @Override 337 public ImmutableListMultimap<V, K> inverse() { 338 ImmutableListMultimap<V, K> result = inverse; 339 return (result == null) ? (inverse = invert()) : result; 340 } 341 342 private ImmutableListMultimap<V, K> invert() { 343 Builder<V, K> builder = builder(); 344 for (Entry<K, V> entry : entries()) { 345 builder.put(entry.getValue(), entry.getKey()); 346 } 347 ImmutableListMultimap<V, K> invertedMultimap = builder.build(); 348 invertedMultimap.inverse = this; 349 return invertedMultimap; 350 } 351 352 /** 353 * Guaranteed to throw an exception and leave the multimap unmodified. 354 * 355 * @throws UnsupportedOperationException always 356 * @deprecated Unsupported operation. 357 */ 358 @CanIgnoreReturnValue 359 @Deprecated 360 @Override 361 @DoNotCall("Always throws UnsupportedOperationException") 362 public final ImmutableList<V> removeAll(@CheckForNull Object key) { 363 throw new UnsupportedOperationException(); 364 } 365 366 /** 367 * Guaranteed to throw an exception and leave the multimap unmodified. 368 * 369 * @throws UnsupportedOperationException always 370 * @deprecated Unsupported operation. 371 */ 372 @CanIgnoreReturnValue 373 @Deprecated 374 @Override 375 @DoNotCall("Always throws UnsupportedOperationException") 376 public final ImmutableList<V> replaceValues(K key, Iterable<? extends V> values) { 377 throw new UnsupportedOperationException(); 378 } 379 380 /** 381 * @serialData number of distinct keys, and then for each distinct key: the key, the number of 382 * values for that key, and the key's values 383 */ 384 @GwtIncompatible // java.io.ObjectOutputStream 385 private void writeObject(ObjectOutputStream stream) throws IOException { 386 stream.defaultWriteObject(); 387 Serialization.writeMultimap(this, stream); 388 } 389 390 @GwtIncompatible // java.io.ObjectInputStream 391 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 392 stream.defaultReadObject(); 393 int keyCount = stream.readInt(); 394 if (keyCount < 0) { 395 throw new InvalidObjectException("Invalid key count " + keyCount); 396 } 397 ImmutableMap.Builder<Object, ImmutableList<Object>> builder = ImmutableMap.builder(); 398 int tmpSize = 0; 399 400 for (int i = 0; i < keyCount; i++) { 401 Object key = stream.readObject(); 402 int valueCount = stream.readInt(); 403 if (valueCount <= 0) { 404 throw new InvalidObjectException("Invalid value count " + valueCount); 405 } 406 407 ImmutableList.Builder<Object> valuesBuilder = ImmutableList.builder(); 408 for (int j = 0; j < valueCount; j++) { 409 valuesBuilder.add(stream.readObject()); 410 } 411 builder.put(key, valuesBuilder.build()); 412 tmpSize += valueCount; 413 } 414 415 ImmutableMap<Object, ImmutableList<Object>> tmpMap; 416 try { 417 tmpMap = builder.build(); 418 } catch (IllegalArgumentException e) { 419 throw (InvalidObjectException) new InvalidObjectException(e.getMessage()).initCause(e); 420 } 421 422 FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap); 423 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize); 424 } 425 426 @GwtIncompatible // Not needed in emulated source 427 private static final long serialVersionUID = 0; 428}