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
025 import java.io.Serializable;
026 import java.util.Arrays;
027 import java.util.Collection;
028 import java.util.Collections;
029 import java.util.Comparator;
030 import java.util.Iterator;
031 import java.util.LinkedHashMap;
032 import java.util.List;
033 import java.util.Map.Entry;
034 import java.util.TreeMap;
035
036 import javax.annotation.Nullable;
037
038 /**
039 * An immutable {@link Multimap}. Does not permit null keys or values.
040 *
041 * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is
042 * a <i>view</i> of a separate multimap which can still change, an instance of
043 * {@code ImmutableMultimap} contains its own data and will <i>never</i>
044 * change. {@code ImmutableMultimap} is convenient for
045 * {@code public static final} multimaps ("constant multimaps") and also lets
046 * you easily make a "defensive copy" of a multimap provided to your class by
047 * a caller.
048 *
049 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
050 * it has no public or protected constructors. Thus, instances of this class
051 * are guaranteed to be immutable.
052 *
053 * <p>In addition to methods defined by {@link Multimap}, an {@link #inverse}
054 * method is also supported.
055 *
056 * @author Jared Levy
057 * @since 2.0 (imported from Google Collections Library)
058 */
059 @GwtCompatible(emulated = true)
060 // TODO(user): If BiMultimap graduates from labs, this class should implement it.
061 public abstract class ImmutableMultimap<K, V>
062 implements Multimap<K, V>, Serializable {
063
064 /** Returns an empty multimap. */
065 public static <K, V> ImmutableMultimap<K, V> of() {
066 return ImmutableListMultimap.of();
067 }
068
069 /**
070 * Returns an immutable multimap containing a single entry.
071 */
072 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) {
073 return ImmutableListMultimap.of(k1, v1);
074 }
075
076 /**
077 * Returns an immutable multimap containing the given entries, in order.
078 */
079 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) {
080 return ImmutableListMultimap.of(k1, v1, k2, v2);
081 }
082
083 /**
084 * Returns an immutable multimap containing the given entries, in order.
085 */
086 public static <K, V> ImmutableMultimap<K, V> of(
087 K k1, V v1, K k2, V v2, K k3, V v3) {
088 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3);
089 }
090
091 /**
092 * Returns an immutable multimap containing the given entries, in order.
093 */
094 public static <K, V> ImmutableMultimap<K, V> of(
095 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
096 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4);
097 }
098
099 /**
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 }