1 /* 2 * Copyright (C) 2008 The Guava Authors 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 static com.google.common.base.Preconditions.checkNotNull; 20 21 import com.google.common.annotations.Beta; 22 import com.google.common.annotations.GwtCompatible; 23 import com.google.common.annotations.GwtIncompatible; 24 25 import java.io.Serializable; 26 import java.util.Arrays; 27 import java.util.Collection; 28 import java.util.Collections; 29 import java.util.Comparator; 30 import java.util.Iterator; 31 import java.util.LinkedHashMap; 32 import java.util.List; 33 import java.util.Map.Entry; 34 import java.util.TreeMap; 35 36 import javax.annotation.Nullable; 37 38 /** 39 * An immutable {@link Multimap}. Does not permit null keys or values. 40 * 41 * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is 42 * a <i>view</i> of a separate multimap which can still change, an instance of 43 * {@code ImmutableMultimap} contains its own data and will <i>never</i> 44 * change. {@code ImmutableMultimap} is convenient for 45 * {@code public static final} multimaps ("constant multimaps") and also lets 46 * you easily make a "defensive copy" of a multimap provided to your class by 47 * a caller. 48 * 49 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as 50 * it has no public or protected constructors. Thus, instances of this class 51 * are guaranteed to be immutable. 52 * 53 * <p>In addition to methods defined by {@link Multimap}, an {@link #inverse} 54 * method is also supported. 55 * 56 * @author Jared Levy 57 * @since 2.0 (imported from Google Collections Library) 58 */ 59 @GwtCompatible(emulated = true) 60 // TODO(user): If BiMultimap graduates from labs, this class should implement it. 61 public abstract class ImmutableMultimap<K, V> 62 implements Multimap<K, V>, Serializable { 63 64 /** Returns an empty multimap. */ 65 public static <K, V> ImmutableMultimap<K, V> of() { 66 return ImmutableListMultimap.of(); 67 } 68 69 /** 70 * Returns an immutable multimap containing a single entry. 71 */ 72 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) { 73 return ImmutableListMultimap.of(k1, v1); 74 } 75 76 /** 77 * Returns an immutable multimap containing the given entries, in order. 78 */ 79 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) { 80 return ImmutableListMultimap.of(k1, v1, k2, v2); 81 } 82 83 /** 84 * Returns an immutable multimap containing the given entries, in order. 85 */ 86 public static <K, V> ImmutableMultimap<K, V> of( 87 K k1, V v1, K k2, V v2, K k3, V v3) { 88 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3); 89 } 90 91 /** 92 * Returns an immutable multimap containing the given entries, in order. 93 */ 94 public static <K, V> ImmutableMultimap<K, V> of( 95 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 96 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4); 97 } 98 99 /** 100 * Returns an immutable multimap containing the given entries, in order. 101 */ 102 public static <K, V> ImmutableMultimap<K, V> of( 103 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 104 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5); 105 } 106 107 // looking for of() with > 5 entries? Use the builder instead. 108 109 /** 110 * Returns a new builder. The generated builder is equivalent to the builder 111 * created by the {@link Builder} constructor. 112 */ 113 public static <K, V> Builder<K, V> builder() { 114 return new Builder<K, V>(); 115 } 116 117 /** 118 * Multimap for {@link ImmutableMultimap.Builder} that maintains key and 119 * value orderings, allows duplicate values, and performs better than 120 * {@link LinkedListMultimap}. 121 */ 122 private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> { 123 BuilderMultimap() { 124 super(new LinkedHashMap<K, Collection<V>>()); 125 } 126 @Override Collection<V> createCollection() { 127 return Lists.newArrayList(); 128 } 129 private static final long serialVersionUID = 0; 130 } 131 132 /** 133 * Multimap for {@link ImmutableMultimap.Builder} that sorts key and allows 134 * duplicate values, 135 */ 136 private static class SortedKeyBuilderMultimap<K, V> 137 extends AbstractMultimap<K, V> { 138 SortedKeyBuilderMultimap( 139 Comparator<? super K> keyComparator, Multimap<K, V> multimap) { 140 super(new TreeMap<K, Collection<V>>(keyComparator)); 141 putAll(multimap); 142 } 143 @Override Collection<V> createCollection() { 144 return Lists.newArrayList(); 145 } 146 private static final long serialVersionUID = 0; 147 } 148 149 /** 150 * A builder for creating immutable multimap instances, especially 151 * {@code public static final} multimaps ("constant multimaps"). Example: 152 * <pre> {@code 153 * 154 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP = 155 * new ImmutableMultimap.Builder<String, Integer>() 156 * .put("one", 1) 157 * .putAll("several", 1, 2, 3) 158 * .putAll("many", 1, 2, 3, 4, 5) 159 * .build();}</pre> 160 * 161 * Builder instances can be reused; it is safe to call {@link #build} multiple 162 * times to build multiple multimaps in series. Each multimap contains the 163 * key-value mappings in the previously created multimaps. 164 * 165 * @since 2.0 (imported from Google Collections Library) 166 */ 167 public static class Builder<K, V> { 168 Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>(); 169 Comparator<? super V> valueComparator; 170 171 /** 172 * Creates a new builder. The returned builder is equivalent to the builder 173 * generated by {@link ImmutableMultimap#builder}. 174 */ 175 public Builder() {} 176 177 /** 178 * Adds a key-value mapping to the built multimap. 179 */ 180 public Builder<K, V> put(K key, V value) { 181 builderMultimap.put(checkNotNull(key), checkNotNull(value)); 182 return this; 183 } 184 185 /** 186 * Adds an entry to the built multimap. 187 * 188 * @since 11.0 189 */ 190 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 191 builderMultimap.put( 192 checkNotNull(entry.getKey()), checkNotNull(entry.getValue())); 193 return this; 194 } 195 196 /** 197 * Stores a collection of values with the same key in the built multimap. 198 * 199 * @throws NullPointerException if {@code key}, {@code values}, or any 200 * element in {@code values} is null. The builder is left in an invalid 201 * state. 202 */ 203 public Builder<K, V> putAll(K key, Iterable<? extends V> values) { 204 Collection<V> valueList = builderMultimap.get(checkNotNull(key)); 205 for (V value : values) { 206 valueList.add(checkNotNull(value)); 207 } 208 return this; 209 } 210 211 /** 212 * Stores an array of values with the same key in the built multimap. 213 * 214 * @throws NullPointerException if the key or any value is null. The builder 215 * is left in an invalid state. 216 */ 217 public Builder<K, V> putAll(K key, V... values) { 218 return putAll(key, Arrays.asList(values)); 219 } 220 221 /** 222 * Stores another multimap's entries in the built multimap. The generated 223 * multimap's key and value orderings correspond to the iteration ordering 224 * of the {@code multimap.asMap()} view, with new keys and values following 225 * any existing keys and values. 226 * 227 * @throws NullPointerException if any key or value in {@code multimap} is 228 * null. The builder is left in an invalid state. 229 */ 230 public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) { 231 for (Entry<? extends K, ? extends Collection<? extends V>> entry 232 : multimap.asMap().entrySet()) { 233 putAll(entry.getKey(), entry.getValue()); 234 } 235 return this; 236 } 237 238 /** 239 * Specifies the ordering of the generated multimap's keys. 240 * 241 * @since 8.0 242 */ 243 @Beta 244 public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) { 245 builderMultimap = new SortedKeyBuilderMultimap<K, V>( 246 checkNotNull(keyComparator), builderMultimap); 247 return this; 248 } 249 250 /** 251 * Specifies the ordering of the generated multimap's values for each key. 252 * 253 * @since 8.0 254 */ 255 @Beta 256 public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) { 257 this.valueComparator = checkNotNull(valueComparator); 258 return this; 259 } 260 261 /** 262 * Returns a newly-created immutable multimap. 263 */ 264 public ImmutableMultimap<K, V> build() { 265 if (valueComparator != null) { 266 for (Collection<V> values : builderMultimap.asMap().values()) { 267 List<V> list = (List <V>) values; 268 Collections.sort(list, valueComparator); 269 } 270 } 271 return copyOf(builderMultimap); 272 } 273 } 274 275 /** 276 * Returns an immutable multimap containing the same mappings as {@code 277 * multimap}. The generated multimap's key and value orderings correspond to 278 * the iteration ordering of the {@code multimap.asMap()} view. 279 * 280 * <p>Despite the method name, this method attempts to avoid actually copying 281 * the data when it is safe to do so. The exact circumstances under which a 282 * copy will or will not be performed are undocumented and subject to change. 283 * 284 * @throws NullPointerException if any key or value in {@code multimap} is 285 * null 286 */ 287 public static <K, V> ImmutableMultimap<K, V> copyOf( 288 Multimap<? extends K, ? extends V> multimap) { 289 if (multimap instanceof ImmutableMultimap) { 290 @SuppressWarnings("unchecked") // safe since multimap is not writable 291 ImmutableMultimap<K, V> kvMultimap 292 = (ImmutableMultimap<K, V>) multimap; 293 if (!kvMultimap.isPartialView()) { 294 return kvMultimap; 295 } 296 } 297 return ImmutableListMultimap.copyOf(multimap); 298 } 299 300 final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map; 301 final transient int size; 302 303 // These constants allow the deserialization code to set final fields. This 304 // holder class makes sure they are not initialized unless an instance is 305 // deserialized. 306 @GwtIncompatible("java serialization is not supported") 307 static class FieldSettersHolder { 308 static final Serialization.FieldSetter<ImmutableMultimap> 309 MAP_FIELD_SETTER = Serialization.getFieldSetter( 310 ImmutableMultimap.class, "map"); 311 static final Serialization.FieldSetter<ImmutableMultimap> 312 SIZE_FIELD_SETTER = Serialization.getFieldSetter( 313 ImmutableMultimap.class, "size"); 314 } 315 316 ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, 317 int size) { 318 this.map = map; 319 this.size = size; 320 } 321 322 // mutators (not supported) 323 324 /** 325 * Guaranteed to throw an exception and leave the multimap unmodified. 326 * 327 * @throws UnsupportedOperationException always 328 */ 329 @Override 330 public ImmutableCollection<V> removeAll(Object key) { 331 throw new UnsupportedOperationException(); 332 } 333 334 /** 335 * Guaranteed to throw an exception and leave the multimap unmodified. 336 * 337 * @throws UnsupportedOperationException always 338 */ 339 @Override 340 public ImmutableCollection<V> replaceValues(K key, 341 Iterable<? extends V> values) { 342 throw new UnsupportedOperationException(); 343 } 344 345 /** 346 * Guaranteed to throw an exception and leave the multimap unmodified. 347 * 348 * @throws UnsupportedOperationException always 349 */ 350 @Override 351 public void clear() { 352 throw new UnsupportedOperationException(); 353 } 354 355 /** 356 * Returns an immutable collection of the values for the given key. If no 357 * mappings in the multimap have the provided key, an empty immutable 358 * collection is returned. The values are in the same order as the parameters 359 * used to build this multimap. 360 */ 361 @Override 362 public abstract ImmutableCollection<V> get(K key); 363 364 /** 365 * Returns an immutable multimap which is the inverse of this one. For every 366 * key-value mapping in the original, the result will have a mapping with 367 * key and value reversed. 368 * 369 * @since 11 370 */ 371 @Beta 372 public abstract ImmutableMultimap<V, K> inverse(); 373 374 /** 375 * Guaranteed to throw an exception and leave the multimap unmodified. 376 * 377 * @throws UnsupportedOperationException always 378 */ 379 @Override 380 public boolean put(K key, V value) { 381 throw new UnsupportedOperationException(); 382 } 383 384 /** 385 * Guaranteed to throw an exception and leave the multimap unmodified. 386 * 387 * @throws UnsupportedOperationException always 388 */ 389 @Override 390 public boolean putAll(K key, Iterable<? extends V> values) { 391 throw new UnsupportedOperationException(); 392 } 393 394 /** 395 * Guaranteed to throw an exception and leave the multimap unmodified. 396 * 397 * @throws UnsupportedOperationException always 398 */ 399 @Override 400 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 401 throw new UnsupportedOperationException(); 402 } 403 404 /** 405 * Guaranteed to throw an exception and leave the multimap unmodified. 406 * 407 * @throws UnsupportedOperationException always 408 */ 409 @Override 410 public boolean remove(Object key, Object value) { 411 throw new UnsupportedOperationException(); 412 } 413 414 boolean isPartialView(){ 415 return map.isPartialView(); 416 } 417 418 // accessors 419 420 @Override 421 public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 422 Collection<V> values = map.get(key); 423 return values != null && values.contains(value); 424 } 425 426 @Override 427 public boolean containsKey(@Nullable Object key) { 428 return map.containsKey(key); 429 } 430 431 @Override 432 public boolean containsValue(@Nullable Object value) { 433 for (Collection<V> valueCollection : map.values()) { 434 if (valueCollection.contains(value)) { 435 return true; 436 } 437 } 438 return false; 439 } 440 441 @Override 442 public boolean isEmpty() { 443 return size == 0; 444 } 445 446 @Override 447 public int size() { 448 return size; 449 } 450 451 @Override public boolean equals(@Nullable Object object) { 452 if (object instanceof Multimap) { 453 Multimap<?, ?> that = (Multimap<?, ?>) object; 454 return this.map.equals(that.asMap()); 455 } 456 return false; 457 } 458 459 @Override public int hashCode() { 460 return map.hashCode(); 461 } 462 463 @Override public String toString() { 464 return map.toString(); 465 } 466 467 // views 468 469 /** 470 * Returns an immutable set of the distinct keys in this multimap. These keys 471 * are ordered according to when they first appeared during the construction 472 * of this multimap. 473 */ 474 @Override 475 public ImmutableSet<K> keySet() { 476 return map.keySet(); 477 } 478 479 /** 480 * Returns an immutable map that associates each key with its corresponding 481 * values in the multimap. 482 */ 483 @Override 484 @SuppressWarnings("unchecked") // a widening cast 485 public ImmutableMap<K, Collection<V>> asMap() { 486 return (ImmutableMap) map; 487 } 488 489 private transient ImmutableCollection<Entry<K, V>> entries; 490 491 /** 492 * Returns an immutable collection of all key-value pairs in the multimap. Its 493 * iterator traverses the values for the first key, the values for the second 494 * key, and so on. 495 */ 496 @Override 497 public ImmutableCollection<Entry<K, V>> entries() { 498 ImmutableCollection<Entry<K, V>> result = entries; 499 return (result == null) 500 ? (entries = new EntryCollection<K, V>(this)) : result; 501 } 502 503 private static class EntryCollection<K, V> 504 extends ImmutableCollection<Entry<K, V>> { 505 final ImmutableMultimap<K, V> multimap; 506 507 EntryCollection(ImmutableMultimap<K, V> multimap) { 508 this.multimap = multimap; 509 } 510 511 @Override public UnmodifiableIterator<Entry<K, V>> iterator() { 512 final Iterator<? extends Entry<K, ? extends ImmutableCollection<V>>> 513 mapIterator = this.multimap.map.entrySet().iterator(); 514 515 return new UnmodifiableIterator<Entry<K, V>>() { 516 K key; 517 Iterator<V> valueIterator; 518 519 @Override 520 public boolean hasNext() { 521 return (key != null && valueIterator.hasNext()) 522 || mapIterator.hasNext(); 523 } 524 525 @Override 526 public Entry<K, V> next() { 527 if (key == null || !valueIterator.hasNext()) { 528 Entry<K, ? extends ImmutableCollection<V>> entry 529 = mapIterator.next(); 530 key = entry.getKey(); 531 valueIterator = entry.getValue().iterator(); 532 } 533 return Maps.immutableEntry(key, valueIterator.next()); 534 } 535 }; 536 } 537 538 @Override boolean isPartialView() { 539 return multimap.isPartialView(); 540 } 541 542 @Override 543 public int size() { 544 return multimap.size(); 545 } 546 547 @Override public boolean contains(Object object) { 548 if (object instanceof Entry) { 549 Entry<?, ?> entry = (Entry<?, ?>) object; 550 return multimap.containsEntry(entry.getKey(), entry.getValue()); 551 } 552 return false; 553 } 554 555 private static final long serialVersionUID = 0; 556 } 557 558 private transient ImmutableMultiset<K> keys; 559 560 /** 561 * Returns a collection, which may contain duplicates, of all keys. The number 562 * of times a key appears in the returned multiset equals the number of 563 * mappings the key has in the multimap. Duplicate keys appear consecutively 564 * in the multiset's iteration order. 565 */ 566 @Override 567 public ImmutableMultiset<K> keys() { 568 ImmutableMultiset<K> result = keys; 569 return (result == null) ? (keys = createKeys()) : result; 570 } 571 572 private ImmutableMultiset<K> createKeys() { 573 ImmutableMultiset.Builder<K> builder = ImmutableMultiset.builder(); 574 for (Entry<K, ? extends ImmutableCollection<V>> entry 575 : map.entrySet()) { 576 builder.addCopies(entry.getKey(), entry.getValue().size()); 577 } 578 return builder.build(); 579 } 580 581 private transient ImmutableCollection<V> values; 582 583 /** 584 * Returns an immutable collection of the values in this multimap. Its 585 * iterator traverses the values for the first key, the values for the second 586 * key, and so on. 587 */ 588 @Override 589 public ImmutableCollection<V> values() { 590 ImmutableCollection<V> result = values; 591 return (result == null) ? (values = new Values<V>(this)) : result; 592 } 593 594 private static class Values<V> extends ImmutableCollection<V> { 595 final ImmutableMultimap<?, V> multimap; 596 597 Values(ImmutableMultimap<?, V> multimap) { 598 this.multimap = multimap; 599 } 600 601 @Override public UnmodifiableIterator<V> iterator() { 602 final Iterator<? extends Entry<?, V>> entryIterator 603 = multimap.entries().iterator(); 604 return new UnmodifiableIterator<V>() { 605 @Override 606 public boolean hasNext() { 607 return entryIterator.hasNext(); 608 } 609 @Override 610 public V next() { 611 return entryIterator.next().getValue(); 612 } 613 }; 614 } 615 616 @Override 617 public int size() { 618 return multimap.size(); 619 } 620 621 @Override boolean isPartialView() { 622 return true; 623 } 624 625 private static final long serialVersionUID = 0; 626 } 627 628 private static final long serialVersionUID = 0; 629 } 630