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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkNotNull;
020
021 import com.google.common.annotations.Beta;
022 import com.google.common.annotations.GwtCompatible;
023 import com.google.common.annotations.GwtIncompatible;
024 import com.google.common.base.Function;
025
026 import java.io.Serializable;
027 import java.util.Arrays;
028 import java.util.Collection;
029 import java.util.Collections;
030 import java.util.Comparator;
031 import java.util.Iterator;
032 import java.util.LinkedHashMap;
033 import java.util.List;
034 import java.util.Map;
035 import java.util.Map.Entry;
036 import java.util.Set;
037
038 import javax.annotation.Nullable;
039
040 /**
041 * An immutable {@link Multimap}. Does not permit null keys or values.
042 *
043 * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is
044 * a <i>view</i> of a separate multimap which can still change, an instance of
045 * {@code ImmutableMultimap} contains its own data and will <i>never</i>
046 * change. {@code ImmutableMultimap} is convenient for
047 * {@code public static final} multimaps ("constant multimaps") and also lets
048 * you easily make a "defensive copy" of a multimap provided to your class by
049 * a caller.
050 *
051 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
052 * it has no public or protected constructors. Thus, instances of this class
053 * are guaranteed to be immutable.
054 *
055 * <p>In addition to methods defined by {@link Multimap}, an {@link #inverse}
056 * method is also supported.
057 *
058 * <p>See the Guava User Guide article on <a href=
059 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
060 * immutable collections</a>.
061 *
062 * @author Jared Levy
063 * @since 2.0 (imported from Google Collections Library)
064 */
065 @GwtCompatible(emulated = true)
066 public abstract class ImmutableMultimap<K, V>
067 implements Multimap<K, V>, Serializable {
068
069 /** Returns an empty multimap. */
070 public static <K, V> ImmutableMultimap<K, V> of() {
071 return ImmutableListMultimap.of();
072 }
073
074 /**
075 * Returns an immutable multimap containing a single entry.
076 */
077 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) {
078 return ImmutableListMultimap.of(k1, v1);
079 }
080
081 /**
082 * Returns an immutable multimap containing the given entries, in order.
083 */
084 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) {
085 return ImmutableListMultimap.of(k1, v1, k2, v2);
086 }
087
088 /**
089 * Returns an immutable multimap containing the given entries, in order.
090 */
091 public static <K, V> ImmutableMultimap<K, V> of(
092 K k1, V v1, K k2, V v2, K k3, V v3) {
093 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3);
094 }
095
096 /**
097 * Returns an immutable multimap containing the given entries, in order.
098 */
099 public static <K, V> ImmutableMultimap<K, V> of(
100 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
101 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4);
102 }
103
104 /**
105 * Returns an immutable multimap containing the given entries, in order.
106 */
107 public static <K, V> ImmutableMultimap<K, V> of(
108 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
109 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
110 }
111
112 // looking for of() with > 5 entries? Use the builder instead.
113
114 /**
115 * Returns a new builder. The generated builder is equivalent to the builder
116 * created by the {@link Builder} constructor.
117 */
118 public static <K, V> Builder<K, V> builder() {
119 return new Builder<K, V>();
120 }
121
122 /**
123 * Multimap for {@link ImmutableMultimap.Builder} that maintains key and
124 * value orderings, allows duplicate values, and performs better than
125 * {@link LinkedListMultimap}.
126 */
127 private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> {
128 BuilderMultimap() {
129 super(new LinkedHashMap<K, Collection<V>>());
130 }
131 @Override Collection<V> createCollection() {
132 return Lists.newArrayList();
133 }
134 private static final long serialVersionUID = 0;
135 }
136
137 /**
138 * A builder for creating immutable multimap instances, especially
139 * {@code public static final} multimaps ("constant multimaps"). Example:
140 * <pre> {@code
141 *
142 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
143 * new ImmutableMultimap.Builder<String, Integer>()
144 * .put("one", 1)
145 * .putAll("several", 1, 2, 3)
146 * .putAll("many", 1, 2, 3, 4, 5)
147 * .build();}</pre>
148 *
149 * Builder instances can be reused; it is safe to call {@link #build} multiple
150 * times to build multiple multimaps in series. Each multimap contains the
151 * key-value mappings in the previously created multimaps.
152 *
153 * @since 2.0 (imported from Google Collections Library)
154 */
155 public static class Builder<K, V> {
156 Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>();
157 Comparator<? super K> keyComparator;
158 Comparator<? super V> valueComparator;
159
160 /**
161 * Creates a new builder. The returned builder is equivalent to the builder
162 * generated by {@link ImmutableMultimap#builder}.
163 */
164 public Builder() {}
165
166 /**
167 * Adds a key-value mapping to the built multimap.
168 */
169 public Builder<K, V> put(K key, V value) {
170 builderMultimap.put(checkNotNull(key), checkNotNull(value));
171 return this;
172 }
173
174 /**
175 * Adds an entry to the built multimap.
176 *
177 * @since 11.0
178 */
179 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
180 builderMultimap.put(
181 checkNotNull(entry.getKey()), checkNotNull(entry.getValue()));
182 return this;
183 }
184
185 /**
186 * Stores a collection of values with the same key in the built multimap.
187 *
188 * @throws NullPointerException if {@code key}, {@code values}, or any
189 * element in {@code values} is null. The builder is left in an invalid
190 * state.
191 */
192 public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
193 Collection<V> valueList = builderMultimap.get(checkNotNull(key));
194 for (V value : values) {
195 valueList.add(checkNotNull(value));
196 }
197 return this;
198 }
199
200 /**
201 * Stores an array of values with the same key in the built multimap.
202 *
203 * @throws NullPointerException if the key or any value is null. The builder
204 * is left in an invalid state.
205 */
206 public Builder<K, V> putAll(K key, V... values) {
207 return putAll(key, Arrays.asList(values));
208 }
209
210 /**
211 * Stores another multimap's entries in the built multimap. The generated
212 * multimap's key and value orderings correspond to the iteration ordering
213 * of the {@code multimap.asMap()} view, with new keys and values following
214 * any existing keys and values.
215 *
216 * @throws NullPointerException if any key or value in {@code multimap} is
217 * null. The builder is left in an invalid state.
218 */
219 public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
220 for (Entry<? extends K, ? extends Collection<? extends V>> entry
221 : multimap.asMap().entrySet()) {
222 putAll(entry.getKey(), entry.getValue());
223 }
224 return this;
225 }
226
227 /**
228 * Specifies the ordering of the generated multimap's keys.
229 *
230 * @since 8.0
231 */
232 @Beta
233 public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
234 this.keyComparator = checkNotNull(keyComparator);
235 return this;
236 }
237
238 /**
239 * Specifies the ordering of the generated multimap's values for each key.
240 *
241 * @since 8.0
242 */
243 @Beta
244 public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
245 this.valueComparator = checkNotNull(valueComparator);
246 return this;
247 }
248
249 /**
250 * Returns a newly-created immutable multimap.
251 */
252 public ImmutableMultimap<K, V> build() {
253 if (valueComparator != null) {
254 for (Collection<V> values : builderMultimap.asMap().values()) {
255 List<V> list = (List <V>) values;
256 Collections.sort(list, valueComparator);
257 }
258 }
259 if (keyComparator != null) {
260 Multimap<K, V> sortedCopy = new BuilderMultimap<K, V>();
261 List<Map.Entry<K, Collection<V>>> entries = Lists.newArrayList(
262 builderMultimap.asMap().entrySet());
263 Collections.sort(
264 entries,
265 Ordering.from(keyComparator).onResultOf(new Function<Entry<K, Collection<V>>, K>() {
266 @Override
267 public K apply(Entry<K, Collection<V>> entry) {
268 return entry.getKey();
269 }
270 }));
271 for (Map.Entry<K, Collection<V>> entry : entries) {
272 sortedCopy.putAll(entry.getKey(), entry.getValue());
273 }
274 builderMultimap = sortedCopy;
275 }
276 return copyOf(builderMultimap);
277 }
278 }
279
280 /**
281 * Returns an immutable multimap containing the same mappings as {@code
282 * multimap}. The generated multimap's key and value orderings correspond to
283 * the iteration ordering of the {@code multimap.asMap()} view.
284 *
285 * <p>Despite the method name, this method attempts to avoid actually copying
286 * the data when it is safe to do so. The exact circumstances under which a
287 * copy will or will not be performed are undocumented and subject to change.
288 *
289 * @throws NullPointerException if any key or value in {@code multimap} is
290 * null
291 */
292 public static <K, V> ImmutableMultimap<K, V> copyOf(
293 Multimap<? extends K, ? extends V> multimap) {
294 if (multimap instanceof ImmutableMultimap) {
295 @SuppressWarnings("unchecked") // safe since multimap is not writable
296 ImmutableMultimap<K, V> kvMultimap
297 = (ImmutableMultimap<K, V>) multimap;
298 if (!kvMultimap.isPartialView()) {
299 return kvMultimap;
300 }
301 }
302 return ImmutableListMultimap.copyOf(multimap);
303 }
304
305 final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map;
306 final transient int size;
307
308 // These constants allow the deserialization code to set final fields. This
309 // holder class makes sure they are not initialized unless an instance is
310 // deserialized.
311 @GwtIncompatible("java serialization is not supported")
312 static class FieldSettersHolder {
313 static final Serialization.FieldSetter<ImmutableMultimap>
314 MAP_FIELD_SETTER = Serialization.getFieldSetter(
315 ImmutableMultimap.class, "map");
316 static final Serialization.FieldSetter<ImmutableMultimap>
317 SIZE_FIELD_SETTER = Serialization.getFieldSetter(
318 ImmutableMultimap.class, "size");
319 }
320
321 ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map,
322 int size) {
323 this.map = map;
324 this.size = size;
325 }
326
327 // mutators (not supported)
328
329 /**
330 * Guaranteed to throw an exception and leave the multimap unmodified.
331 *
332 * @throws UnsupportedOperationException always
333 */
334 @Override
335 public ImmutableCollection<V> removeAll(Object key) {
336 throw new UnsupportedOperationException();
337 }
338
339 /**
340 * Guaranteed to throw an exception and leave the multimap unmodified.
341 *
342 * @throws UnsupportedOperationException always
343 */
344 @Override
345 public ImmutableCollection<V> replaceValues(K key,
346 Iterable<? extends V> values) {
347 throw new UnsupportedOperationException();
348 }
349
350 /**
351 * Guaranteed to throw an exception and leave the multimap unmodified.
352 *
353 * @throws UnsupportedOperationException always
354 */
355 @Override
356 public void clear() {
357 throw new UnsupportedOperationException();
358 }
359
360 /**
361 * Returns an immutable collection of the values for the given key. If no
362 * mappings in the multimap have the provided key, an empty immutable
363 * collection is returned. The values are in the same order as the parameters
364 * used to build this multimap.
365 */
366 @Override
367 public abstract ImmutableCollection<V> get(K key);
368
369 /**
370 * Returns an immutable multimap which is the inverse of this one. For every
371 * key-value mapping in the original, the result will have a mapping with
372 * key and value reversed.
373 *
374 * @since 11.0
375 */
376 @Beta
377 public abstract ImmutableMultimap<V, K> inverse();
378
379 /**
380 * Guaranteed to throw an exception and leave the multimap unmodified.
381 *
382 * @throws UnsupportedOperationException always
383 */
384 @Override
385 public boolean put(K key, V value) {
386 throw new UnsupportedOperationException();
387 }
388
389 /**
390 * Guaranteed to throw an exception and leave the multimap unmodified.
391 *
392 * @throws UnsupportedOperationException always
393 */
394 @Override
395 public boolean putAll(K key, Iterable<? extends V> values) {
396 throw new UnsupportedOperationException();
397 }
398
399 /**
400 * Guaranteed to throw an exception and leave the multimap unmodified.
401 *
402 * @throws UnsupportedOperationException always
403 */
404 @Override
405 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
406 throw new UnsupportedOperationException();
407 }
408
409 /**
410 * Guaranteed to throw an exception and leave the multimap unmodified.
411 *
412 * @throws UnsupportedOperationException always
413 */
414 @Override
415 public boolean remove(Object key, Object value) {
416 throw new UnsupportedOperationException();
417 }
418
419 boolean isPartialView() {
420 return map.isPartialView();
421 }
422
423 // accessors
424
425 @Override
426 public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
427 Collection<V> values = map.get(key);
428 return values != null && values.contains(value);
429 }
430
431 @Override
432 public boolean containsKey(@Nullable Object key) {
433 return map.containsKey(key);
434 }
435
436 @Override
437 public boolean containsValue(@Nullable Object value) {
438 for (Collection<V> valueCollection : map.values()) {
439 if (valueCollection.contains(value)) {
440 return true;
441 }
442 }
443 return false;
444 }
445
446 @Override
447 public boolean isEmpty() {
448 return size == 0;
449 }
450
451 @Override
452 public int size() {
453 return size;
454 }
455
456 @Override public boolean equals(@Nullable Object object) {
457 if (object instanceof Multimap) {
458 Multimap<?, ?> that = (Multimap<?, ?>) object;
459 return this.map.equals(that.asMap());
460 }
461 return false;
462 }
463
464 @Override public int hashCode() {
465 return map.hashCode();
466 }
467
468 @Override public String toString() {
469 return map.toString();
470 }
471
472 // views
473
474 /**
475 * Returns an immutable set of the distinct keys in this multimap. These keys
476 * are ordered according to when they first appeared during the construction
477 * of this multimap.
478 */
479 @Override
480 public ImmutableSet<K> keySet() {
481 return map.keySet();
482 }
483
484 /**
485 * Returns an immutable map that associates each key with its corresponding
486 * values in the multimap.
487 */
488 @Override
489 @SuppressWarnings("unchecked") // a widening cast
490 public ImmutableMap<K, Collection<V>> asMap() {
491 return (ImmutableMap) map;
492 }
493
494 private transient ImmutableCollection<Entry<K, V>> entries;
495
496 /**
497 * Returns an immutable collection of all key-value pairs in the multimap. Its
498 * iterator traverses the values for the first key, the values for the second
499 * key, and so on.
500 */
501 @Override
502 public ImmutableCollection<Entry<K, V>> entries() {
503 ImmutableCollection<Entry<K, V>> result = entries;
504 return (result == null)
505 ? (entries = new EntryCollection<K, V>(this)) : result;
506 }
507
508 private static class EntryCollection<K, V>
509 extends ImmutableCollection<Entry<K, V>> {
510 final ImmutableMultimap<K, V> multimap;
511
512 EntryCollection(ImmutableMultimap<K, V> multimap) {
513 this.multimap = multimap;
514 }
515
516 @Override public UnmodifiableIterator<Entry<K, V>> iterator() {
517 final Iterator<? extends Entry<K, ? extends ImmutableCollection<V>>>
518 mapIterator = this.multimap.map.entrySet().iterator();
519
520 return new UnmodifiableIterator<Entry<K, V>>() {
521 K key;
522 Iterator<V> valueIterator;
523
524 @Override
525 public boolean hasNext() {
526 return (key != null && valueIterator.hasNext())
527 || mapIterator.hasNext();
528 }
529
530 @Override
531 public Entry<K, V> next() {
532 if (key == null || !valueIterator.hasNext()) {
533 Entry<K, ? extends ImmutableCollection<V>> entry
534 = mapIterator.next();
535 key = entry.getKey();
536 valueIterator = entry.getValue().iterator();
537 }
538 return Maps.immutableEntry(key, valueIterator.next());
539 }
540 };
541 }
542
543 @Override boolean isPartialView() {
544 return multimap.isPartialView();
545 }
546
547 @Override
548 public int size() {
549 return multimap.size();
550 }
551
552 @Override public boolean contains(Object object) {
553 if (object instanceof Entry) {
554 Entry<?, ?> entry = (Entry<?, ?>) object;
555 return multimap.containsEntry(entry.getKey(), entry.getValue());
556 }
557 return false;
558 }
559
560 private static final long serialVersionUID = 0;
561 }
562
563 private transient ImmutableMultiset<K> keys;
564
565 /**
566 * Returns a collection, which may contain duplicates, of all keys. The number
567 * of times a key appears in the returned multiset equals the number of
568 * mappings the key has in the multimap. Duplicate keys appear consecutively
569 * in the multiset's iteration order.
570 */
571 @Override
572 public ImmutableMultiset<K> keys() {
573 ImmutableMultiset<K> result = keys;
574 return (result == null) ? (keys = createKeys()) : result;
575 }
576
577 private ImmutableMultiset<K> createKeys() {
578 return new Keys();
579 }
580
581 @SuppressWarnings("serial") // Uses writeReplace, not default serialization
582 class Keys extends ImmutableMultiset<K> {
583 @Override
584 public boolean contains(@Nullable Object object) {
585 return containsKey(object);
586 }
587
588 @Override
589 public int count(@Nullable Object element) {
590 Collection<V> values = map.get(element);
591 return (values == null) ? 0 : values.size();
592 }
593
594 @Override
595 public Set<K> elementSet() {
596 return keySet();
597 }
598
599 @Override
600 public int size() {
601 return ImmutableMultimap.this.size();
602 }
603
604 @Override
605 ImmutableSet<Entry<K>> createEntrySet() {
606 return new KeysEntrySet();
607 }
608
609 private class KeysEntrySet extends ImmutableMultiset<K>.EntrySet {
610 @Override
611 public int size() {
612 return keySet().size();
613 }
614
615 @Override
616 public UnmodifiableIterator<Entry<K>> iterator() {
617 return asList().iterator();
618 }
619
620 @Override
621 ImmutableList<Entry<K>> createAsList() {
622 final ImmutableList<? extends Map.Entry<K, ? extends Collection<V>>> mapEntries =
623 map.entrySet().asList();
624 return new ImmutableAsList<Entry<K>>() {
625 @Override
626 public Entry<K> get(int index) {
627 Map.Entry<K, ? extends Collection<V>> entry = mapEntries.get(index);
628 return Multisets.immutableEntry(entry.getKey(), entry.getValue().size());
629 }
630
631 @Override
632 ImmutableCollection<Entry<K>> delegateCollection() {
633 return KeysEntrySet.this;
634 }
635 };
636 }
637 }
638
639 @Override
640 boolean isPartialView() {
641 return true;
642 }
643 }
644
645 private transient ImmutableCollection<V> values;
646
647 /**
648 * Returns an immutable collection of the values in this multimap. Its
649 * iterator traverses the values for the first key, the values for the second
650 * key, and so on.
651 */
652 @Override
653 public ImmutableCollection<V> values() {
654 ImmutableCollection<V> result = values;
655 return (result == null) ? (values = new Values<V>(this)) : result;
656 }
657
658 private static class Values<V> extends ImmutableCollection<V> {
659 final ImmutableMultimap<?, V> multimap;
660
661 Values(ImmutableMultimap<?, V> multimap) {
662 this.multimap = multimap;
663 }
664
665 @Override public UnmodifiableIterator<V> iterator() {
666 return Maps.valueIterator(multimap.entries().iterator());
667 }
668
669 @Override
670 public int size() {
671 return multimap.size();
672 }
673
674 @Override boolean isPartialView() {
675 return true;
676 }
677
678 private static final long serialVersionUID = 0;
679 }
680
681 private static final long serialVersionUID = 0;
682 }