1 /* 2 * Copyright (C) 2008 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import com.google.common.annotations.GwtCompatible; 20 import static com.google.common.base.Preconditions.checkNotNull; 21 22 import java.io.Serializable; 23 import java.util.Arrays; 24 import java.util.Collection; 25 import java.util.Iterator; 26 import java.util.LinkedHashMap; 27 import java.util.Map; 28 29 import javax.annotation.Nullable; 30 31 /** 32 * An immutable {@link Multimap}. Does not permit null keys or values. 33 * 34 * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is 35 * a <i>view</i> of a separate multimap which can still change, an instance of 36 * {@code ImmutableMultimap} contains its own data and will <i>never</i> 37 * change. {@code ImmutableMultimap} is convenient for 38 * {@code public static final} multimaps ("constant multimaps") and also lets 39 * you easily make a "defensive copy" of a multimap provided to your class by 40 * a caller. 41 * 42 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as 43 * it has no public or protected constructors. Thus, instances of this class 44 * are guaranteed to be immutable. 45 * 46 * @author Jared Levy 47 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library) 48 */ 49 @GwtCompatible 50 public abstract class ImmutableMultimap<K, V> 51 implements Multimap<K, V>, Serializable { 52 53 /** Returns an empty multimap. */ 54 public static <K, V> ImmutableMultimap<K, V> of() { 55 return ImmutableListMultimap.of(); 56 } 57 58 /** 59 * Returns an immutable multimap containing a single entry. 60 */ 61 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) { 62 return ImmutableListMultimap.of(k1, v1); 63 } 64 65 /** 66 * Returns an immutable multimap containing the given entries, in order. 67 */ 68 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) { 69 return ImmutableListMultimap.of(k1, v1, k2, v2); 70 } 71 72 /** 73 * Returns an immutable multimap containing the given entries, in order. 74 */ 75 public static <K, V> ImmutableMultimap<K, V> of( 76 K k1, V v1, K k2, V v2, K k3, V v3) { 77 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3); 78 } 79 80 /** 81 * Returns an immutable multimap containing the given entries, in order. 82 */ 83 public static <K, V> ImmutableMultimap<K, V> of( 84 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 85 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4); 86 } 87 88 /** 89 * Returns an immutable multimap containing the given entries, in order. 90 */ 91 public static <K, V> ImmutableMultimap<K, V> of( 92 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 93 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5); 94 } 95 96 // looking for of() with > 5 entries? Use the builder instead. 97 98 /** 99 * Returns a new builder. The generated builder is equivalent to the builder 100 * created by the {@link Builder} constructor. 101 */ 102 public static <K, V> Builder<K, V> builder() { 103 return new Builder<K, V>(); 104 } 105 106 /** 107 * Multimap for {@link ImmutableMultimap.Builder} that maintains key and 108 * value orderings, allows duplicate values, and performs better than 109 * {@link LinkedListMultimap}. 110 */ 111 private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> { 112 BuilderMultimap() { 113 super(new LinkedHashMap<K, Collection<V>>()); 114 } 115 @Override Collection<V> createCollection() { 116 return Lists.newArrayList(); 117 } 118 private static final long serialVersionUID = 0; 119 } 120 121 /** 122 * A builder for creating immutable multimap instances, especially 123 * {@code public static final} multimaps ("constant multimaps"). Example: 124 * <pre> {@code 125 * 126 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP = 127 * new ImmutableMultimap.Builder<String, Integer>() 128 * .put("one", 1) 129 * .putAll("several", 1, 2, 3) 130 * .putAll("many", 1, 2, 3, 4, 5) 131 * .build();}</pre> 132 * 133 * <p>Builder instances can be reused - it is safe to call {@link #build} 134 * multiple times to build multiple multimaps in series. Each multimap 135 * contains the key-value mappings in the previously created multimaps. 136 */ 137 public static class Builder<K, V> { 138 private final Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>(); 139 140 /** 141 * Creates a new builder. The returned builder is equivalent to the builder 142 * generated by {@link ImmutableMultimap#builder}. 143 */ 144 public Builder() {} 145 146 /** 147 * Adds a key-value mapping to the built multimap. 148 */ 149 public Builder<K, V> put(K key, V value) { 150 builderMultimap.put(checkNotNull(key), checkNotNull(value)); 151 return this; 152 } 153 154 /** 155 * Stores a collection of values with the same key in the built multimap. 156 * 157 * @throws NullPointerException if {@code key}, {@code values}, or any 158 * element in {@code values} is null. The builder is left in an invalid 159 * state. 160 */ 161 public Builder<K, V> putAll(K key, Iterable<? extends V> values) { 162 Collection<V> valueList = builderMultimap.get(checkNotNull(key)); 163 for (V value : values) { 164 valueList.add(checkNotNull(value)); 165 } 166 return this; 167 } 168 169 /** 170 * Stores an array of values with the same key in the built multimap. 171 * 172 * @throws NullPointerException if the key or any value is null. The builder 173 * is left in an invalid state. 174 */ 175 public Builder<K, V> putAll(K key, V... values) { 176 return putAll(key, Arrays.asList(values)); 177 } 178 179 /** 180 * Stores another multimap's entries in the built multimap. The generated 181 * multimap's key and value orderings correspond to the iteration ordering 182 * of the {@code multimap.asMap()} view, with new keys and values following 183 * any existing keys and values. 184 * 185 * @throws NullPointerException if any key or value in {@code multimap} is 186 * null. The builder is left in an invalid state. 187 */ 188 public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) { 189 for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry 190 : multimap.asMap().entrySet()) { 191 putAll(entry.getKey(), entry.getValue()); 192 } 193 return this; 194 } 195 196 /** 197 * Returns a newly-created immutable multimap. 198 */ 199 public ImmutableMultimap<K, V> build() { 200 return copyOf(builderMultimap); 201 } 202 } 203 204 /** 205 * Returns an immutable multimap containing the same mappings as 206 * {@code multimap}. The generated multimap's key and value orderings 207 * correspond to the iteration ordering of the {@code multimap.asMap()} view. 208 * 209 * <p><b>Note:</b> Despite what the method name suggests, if 210 * {@code multimap} is an {@code ImmutableMultimap}, no copy will actually be 211 * performed, and the given multimap itself will be returned. 212 * 213 * @throws NullPointerException if any key or value in {@code multimap} is 214 * null 215 */ 216 public static <K, V> ImmutableMultimap<K, V> copyOf( 217 Multimap<? extends K, ? extends V> multimap) { 218 if (multimap instanceof ImmutableMultimap) { 219 @SuppressWarnings("unchecked") // safe since multimap is not writable 220 ImmutableMultimap<K, V> kvMultimap 221 = (ImmutableMultimap<K, V>) multimap; 222 return kvMultimap; 223 } else { 224 return ImmutableListMultimap.copyOf(multimap); 225 } 226 } 227 228 final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map; 229 final transient int size; 230 231 // These constants allow the deserialization code to set final fields. This 232 // holder class makes sure they are not initialized unless an instance is 233 // deserialized. 234 static class FieldSettersHolder { 235 // Eclipse doesn't like the raw ImmutableMultimap 236 @SuppressWarnings("unchecked") 237 static final Serialization.FieldSetter<ImmutableMultimap> 238 MAP_FIELD_SETTER = Serialization.getFieldSetter( 239 ImmutableMultimap.class, "map"); 240 // Eclipse doesn't like the raw ImmutableMultimap 241 @SuppressWarnings("unchecked") 242 static final Serialization.FieldSetter<ImmutableMultimap> 243 SIZE_FIELD_SETTER = Serialization.getFieldSetter( 244 ImmutableMultimap.class, "size"); 245 } 246 247 ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, 248 int size) { 249 this.map = map; 250 this.size = size; 251 } 252 253 // mutators (not supported) 254 255 /** 256 * Guaranteed to throw an exception and leave the multimap unmodified. 257 * 258 * @throws UnsupportedOperationException always 259 */ 260 public ImmutableCollection<V> removeAll(Object key) { 261 throw new UnsupportedOperationException(); 262 } 263 264 /** 265 * Guaranteed to throw an exception and leave the multimap unmodified. 266 * 267 * @throws UnsupportedOperationException always 268 */ 269 public ImmutableCollection<V> replaceValues(K key, 270 Iterable<? extends V> values) { 271 throw new UnsupportedOperationException(); 272 } 273 274 /** 275 * Guaranteed to throw an exception and leave the multimap unmodified. 276 * 277 * @throws UnsupportedOperationException always 278 */ 279 public void clear() { 280 throw new UnsupportedOperationException(); 281 } 282 283 /** 284 * Returns an immutable collection of the values for the given key. If no 285 * mappings in the multimap have the provided key, an empty immutable 286 * collection is returned. The values are in the same order as the parameters 287 * used to build this multimap. 288 */ 289 public abstract ImmutableCollection<V> get(K key); 290 291 /** 292 * Guaranteed to throw an exception and leave the multimap unmodified. 293 * 294 * @throws UnsupportedOperationException always 295 */ 296 public boolean put(K key, V value) { 297 throw new UnsupportedOperationException(); 298 } 299 300 /** 301 * Guaranteed to throw an exception and leave the multimap unmodified. 302 * 303 * @throws UnsupportedOperationException always 304 */ 305 public boolean putAll(K key, Iterable<? extends V> values) { 306 throw new UnsupportedOperationException(); 307 } 308 309 /** 310 * Guaranteed to throw an exception and leave the multimap unmodified. 311 * 312 * @throws UnsupportedOperationException always 313 */ 314 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 315 throw new UnsupportedOperationException(); 316 } 317 318 /** 319 * Guaranteed to throw an exception and leave the multimap unmodified. 320 * 321 * @throws UnsupportedOperationException always 322 */ 323 public boolean remove(Object key, Object value) { 324 throw new UnsupportedOperationException(); 325 } 326 327 // accessors 328 329 public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 330 Collection<V> values = map.get(key); 331 return values != null && values.contains(value); 332 } 333 334 public boolean containsKey(@Nullable Object key) { 335 return map.containsKey(key); 336 } 337 338 public boolean containsValue(@Nullable Object value) { 339 for (Collection<V> valueCollection : map.values()) { 340 if (valueCollection.contains(value)) { 341 return true; 342 } 343 } 344 return false; 345 } 346 347 public boolean isEmpty() { 348 return size == 0; 349 } 350 351 public int size() { 352 return size; 353 } 354 355 @Override public boolean equals(@Nullable Object object) { 356 if (object instanceof Multimap) { 357 Multimap<?, ?> that = (Multimap<?, ?>) object; 358 return this.map.equals(that.asMap()); 359 } 360 return false; 361 } 362 363 @Override public int hashCode() { 364 return map.hashCode(); 365 } 366 367 @Override public String toString() { 368 return map.toString(); 369 } 370 371 // views 372 373 /** 374 * Returns an immutable set of the distinct keys in this multimap. These keys 375 * are ordered according to when they first appeared during the construction 376 * of this multimap. 377 */ 378 public ImmutableSet<K> keySet() { 379 return map.keySet(); 380 } 381 382 /** 383 * Returns an immutable map that associates each key with its corresponding 384 * values in the multimap. 385 */ 386 @SuppressWarnings("unchecked") // a widening cast 387 public ImmutableMap<K, Collection<V>> asMap() { 388 return (ImmutableMap) map; 389 } 390 391 private transient ImmutableCollection<Map.Entry<K, V>> entries; 392 393 /** 394 * Returns an immutable collection of all key-value pairs in the multimap. Its 395 * iterator traverses the values for the first key, the values for the second 396 * key, and so on. 397 */ 398 public ImmutableCollection<Map.Entry<K, V>> entries() { 399 ImmutableCollection<Map.Entry<K, V>> result = entries; 400 return (result == null) 401 ? (entries = new EntryCollection<K, V>(this)) : result; 402 } 403 404 private static class EntryCollection<K, V> 405 extends ImmutableCollection<Map.Entry<K, V>> { 406 final ImmutableMultimap<K, V> multimap; 407 408 EntryCollection(ImmutableMultimap<K, V> multimap) { 409 this.multimap = multimap; 410 } 411 412 @Override public UnmodifiableIterator<Map.Entry<K, V>> iterator() { 413 final Iterator<? extends Map.Entry<K, ? extends ImmutableCollection<V>>> 414 mapIterator = this.multimap.map.entrySet().iterator(); 415 416 return new UnmodifiableIterator<Map.Entry<K, V>>() { 417 K key; 418 Iterator<V> valueIterator; 419 420 public boolean hasNext() { 421 return (key != null && valueIterator.hasNext()) 422 || mapIterator.hasNext(); 423 } 424 425 public Map.Entry<K, V> next() { 426 if (key == null || !valueIterator.hasNext()) { 427 Map.Entry<K, ? extends ImmutableCollection<V>> entry 428 = mapIterator.next(); 429 key = entry.getKey(); 430 valueIterator = entry.getValue().iterator(); 431 } 432 return Maps.immutableEntry(key, valueIterator.next()); 433 } 434 }; 435 } 436 437 public int size() { 438 return multimap.size(); 439 } 440 441 @Override public boolean contains(Object object) { 442 if (object instanceof Map.Entry) { 443 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object; 444 return multimap.containsEntry(entry.getKey(), entry.getValue()); 445 } 446 return false; 447 } 448 449 private static final long serialVersionUID = 0; 450 } 451 452 private transient ImmutableMultiset<K> keys; 453 454 /** 455 * Returns a collection, which may contain duplicates, of all keys. The number 456 * of times a key appears in the returned multiset equals the number of 457 * mappings the key has in the multimap. Duplicate keys appear consecutively 458 * in the multiset's iteration order. 459 */ 460 public ImmutableMultiset<K> keys() { 461 ImmutableMultiset<K> result = keys; 462 return (result == null) ? (keys = createKeys()) : result; 463 } 464 465 private ImmutableMultiset<K> createKeys() { 466 ImmutableMultiset.Builder<K> builder = ImmutableMultiset.builder(); 467 for (Map.Entry<K, ? extends ImmutableCollection<V>> entry 468 : map.entrySet()) { 469 builder.addCopies(entry.getKey(), entry.getValue().size()); 470 } 471 return builder.build(); 472 } 473 474 private transient ImmutableCollection<V> values; 475 476 /** 477 * Returns an immutable collection of the values in this multimap. Its 478 * iterator traverses the values for the first key, the values for the second 479 * key, and so on. 480 */ 481 public ImmutableCollection<V> values() { 482 ImmutableCollection<V> result = values; 483 return (result == null) ? (values = new Values<V>(this)) : result; 484 } 485 486 private static class Values<V> extends ImmutableCollection<V> { 487 final Multimap<?, V> multimap; 488 489 Values(Multimap<?, V> multimap) { 490 this.multimap = multimap; 491 } 492 493 @Override public UnmodifiableIterator<V> iterator() { 494 final Iterator<? extends Map.Entry<?, V>> entryIterator 495 = multimap.entries().iterator(); 496 return new UnmodifiableIterator<V>() { 497 public boolean hasNext() { 498 return entryIterator.hasNext(); 499 } 500 public V next() { 501 return entryIterator.next().getValue(); 502 } 503 }; 504 } 505 506 public int size() { 507 return multimap.size(); 508 } 509 510 private static final long serialVersionUID = 0; 511 } 512 513 private static final long serialVersionUID = 0; 514 } 515