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