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