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