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.0 (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.0 (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.0
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.0
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 static final Serialization.FieldSetter<ImmutableMultimap>
294 MAP_FIELD_SETTER = Serialization.getFieldSetter(
295 ImmutableMultimap.class, "map");
296 static final Serialization.FieldSetter<ImmutableMultimap>
297 SIZE_FIELD_SETTER = Serialization.getFieldSetter(
298 ImmutableMultimap.class, "size");
299 }
300
301 ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map,
302 int size) {
303 this.map = map;
304 this.size = size;
305 }
306
307 // mutators (not supported)
308
309 /**
310 * Guaranteed to throw an exception and leave the multimap unmodified.
311 *
312 * @throws UnsupportedOperationException always
313 */
314 @Override
315 public ImmutableCollection<V> removeAll(Object key) {
316 throw new UnsupportedOperationException();
317 }
318
319 /**
320 * Guaranteed to throw an exception and leave the multimap unmodified.
321 *
322 * @throws UnsupportedOperationException always
323 */
324 @Override
325 public ImmutableCollection<V> replaceValues(K key,
326 Iterable<? extends V> values) {
327 throw new UnsupportedOperationException();
328 }
329
330 /**
331 * Guaranteed to throw an exception and leave the multimap unmodified.
332 *
333 * @throws UnsupportedOperationException always
334 */
335 @Override
336 public void clear() {
337 throw new UnsupportedOperationException();
338 }
339
340 /**
341 * Returns an immutable collection of the values for the given key. If no
342 * mappings in the multimap have the provided key, an empty immutable
343 * collection is returned. The values are in the same order as the parameters
344 * used to build this multimap.
345 */
346 @Override
347 public abstract ImmutableCollection<V> get(K key);
348
349 /**
350 * Guaranteed to throw an exception and leave the multimap unmodified.
351 *
352 * @throws UnsupportedOperationException always
353 */
354 @Override
355 public boolean put(K key, V value) {
356 throw new UnsupportedOperationException();
357 }
358
359 /**
360 * Guaranteed to throw an exception and leave the multimap unmodified.
361 *
362 * @throws UnsupportedOperationException always
363 */
364 @Override
365 public boolean putAll(K key, Iterable<? extends V> values) {
366 throw new UnsupportedOperationException();
367 }
368
369 /**
370 * Guaranteed to throw an exception and leave the multimap unmodified.
371 *
372 * @throws UnsupportedOperationException always
373 */
374 @Override
375 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
376 throw new UnsupportedOperationException();
377 }
378
379 /**
380 * Guaranteed to throw an exception and leave the multimap unmodified.
381 *
382 * @throws UnsupportedOperationException always
383 */
384 @Override
385 public boolean remove(Object key, Object value) {
386 throw new UnsupportedOperationException();
387 }
388
389 boolean isPartialView(){
390 return map.isPartialView();
391 }
392
393 // accessors
394
395 @Override
396 public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
397 Collection<V> values = map.get(key);
398 return values != null && values.contains(value);
399 }
400
401 @Override
402 public boolean containsKey(@Nullable Object key) {
403 return map.containsKey(key);
404 }
405
406 @Override
407 public boolean containsValue(@Nullable Object value) {
408 for (Collection<V> valueCollection : map.values()) {
409 if (valueCollection.contains(value)) {
410 return true;
411 }
412 }
413 return false;
414 }
415
416 @Override
417 public boolean isEmpty() {
418 return size == 0;
419 }
420
421 @Override
422 public int size() {
423 return size;
424 }
425
426 @Override public boolean equals(@Nullable Object object) {
427 if (object instanceof Multimap) {
428 Multimap<?, ?> that = (Multimap<?, ?>) object;
429 return this.map.equals(that.asMap());
430 }
431 return false;
432 }
433
434 @Override public int hashCode() {
435 return map.hashCode();
436 }
437
438 @Override public String toString() {
439 return map.toString();
440 }
441
442 // views
443
444 /**
445 * Returns an immutable set of the distinct keys in this multimap. These keys
446 * are ordered according to when they first appeared during the construction
447 * of this multimap.
448 */
449 @Override
450 public ImmutableSet<K> keySet() {
451 return map.keySet();
452 }
453
454 /**
455 * Returns an immutable map that associates each key with its corresponding
456 * values in the multimap.
457 */
458 @Override
459 @SuppressWarnings("unchecked") // a widening cast
460 public ImmutableMap<K, Collection<V>> asMap() {
461 return (ImmutableMap) map;
462 }
463
464 private transient ImmutableCollection<Map.Entry<K, V>> entries;
465
466 /**
467 * Returns an immutable collection of all key-value pairs in the multimap. Its
468 * iterator traverses the values for the first key, the values for the second
469 * key, and so on.
470 */
471 @Override
472 public ImmutableCollection<Map.Entry<K, V>> entries() {
473 ImmutableCollection<Map.Entry<K, V>> result = entries;
474 return (result == null)
475 ? (entries = new EntryCollection<K, V>(this)) : result;
476 }
477
478 private static class EntryCollection<K, V>
479 extends ImmutableCollection<Map.Entry<K, V>> {
480 final ImmutableMultimap<K, V> multimap;
481
482 EntryCollection(ImmutableMultimap<K, V> multimap) {
483 this.multimap = multimap;
484 }
485
486 @Override public UnmodifiableIterator<Map.Entry<K, V>> iterator() {
487 final Iterator<? extends Map.Entry<K, ? extends ImmutableCollection<V>>>
488 mapIterator = this.multimap.map.entrySet().iterator();
489
490 return new UnmodifiableIterator<Map.Entry<K, V>>() {
491 K key;
492 Iterator<V> valueIterator;
493
494 @Override
495 public boolean hasNext() {
496 return (key != null && valueIterator.hasNext())
497 || mapIterator.hasNext();
498 }
499
500 @Override
501 public Map.Entry<K, V> next() {
502 if (key == null || !valueIterator.hasNext()) {
503 Map.Entry<K, ? extends ImmutableCollection<V>> entry
504 = mapIterator.next();
505 key = entry.getKey();
506 valueIterator = entry.getValue().iterator();
507 }
508 return Maps.immutableEntry(key, valueIterator.next());
509 }
510 };
511 }
512
513 @Override boolean isPartialView() {
514 return multimap.isPartialView();
515 }
516
517 @Override
518 public int size() {
519 return multimap.size();
520 }
521
522 @Override public boolean contains(Object object) {
523 if (object instanceof Map.Entry) {
524 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
525 return multimap.containsEntry(entry.getKey(), entry.getValue());
526 }
527 return false;
528 }
529
530 private static final long serialVersionUID = 0;
531 }
532
533 private transient ImmutableMultiset<K> keys;
534
535 /**
536 * Returns a collection, which may contain duplicates, of all keys. The number
537 * of times a key appears in the returned multiset equals the number of
538 * mappings the key has in the multimap. Duplicate keys appear consecutively
539 * in the multiset's iteration order.
540 */
541 @Override
542 public ImmutableMultiset<K> keys() {
543 ImmutableMultiset<K> result = keys;
544 return (result == null) ? (keys = createKeys()) : result;
545 }
546
547 private ImmutableMultiset<K> createKeys() {
548 ImmutableMultiset.Builder<K> builder = ImmutableMultiset.builder();
549 for (Map.Entry<K, ? extends ImmutableCollection<V>> entry
550 : map.entrySet()) {
551 builder.addCopies(entry.getKey(), entry.getValue().size());
552 }
553 return builder.build();
554 }
555
556 private transient ImmutableCollection<V> values;
557
558 /**
559 * Returns an immutable collection of the values in this multimap. Its
560 * iterator traverses the values for the first key, the values for the second
561 * key, and so on.
562 */
563 @Override
564 public ImmutableCollection<V> values() {
565 ImmutableCollection<V> result = values;
566 return (result == null) ? (values = new Values<V>(this)) : result;
567 }
568
569 private static class Values<V> extends ImmutableCollection<V> {
570 final ImmutableMultimap<?, V> multimap;
571
572 Values(ImmutableMultimap<?, V> multimap) {
573 this.multimap = multimap;
574 }
575
576 @Override public UnmodifiableIterator<V> iterator() {
577 final Iterator<? extends Map.Entry<?, V>> entryIterator
578 = multimap.entries().iterator();
579 return new UnmodifiableIterator<V>() {
580 @Override
581 public boolean hasNext() {
582 return entryIterator.hasNext();
583 }
584 @Override
585 public V next() {
586 return entryIterator.next().getValue();
587 }
588 };
589 }
590
591 @Override
592 public int size() {
593 return multimap.size();
594 }
595
596 @Override boolean isPartialView() {
597 return true;
598 }
599
600 private static final long serialVersionUID = 0;
601 }
602
603 private static final long serialVersionUID = 0;
604 }