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.GwtCompatible;
022 import com.google.common.annotations.GwtIncompatible;
023
024 import java.io.Serializable;
025 import java.util.Arrays;
026 import java.util.Collection;
027 import java.util.Iterator;
028 import java.util.LinkedHashMap;
029 import java.util.Map;
030
031 import javax.annotation.Nullable;
032
033 /**
034 * An immutable {@link Multimap}. Does not permit null keys or values.
035 *
036 * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is
037 * a <i>view</i> of a separate multimap which can still change, an instance of
038 * {@code ImmutableMultimap} contains its own data and will <i>never</i>
039 * change. {@code ImmutableMultimap} is convenient for
040 * {@code public static final} multimaps ("constant multimaps") and also lets
041 * you easily make a "defensive copy" of a multimap provided to your class by
042 * a caller.
043 *
044 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
045 * it has no public or protected constructors. Thus, instances of this class
046 * are guaranteed to be immutable.
047 *
048 * @author Jared Levy
049 * @since 2 (imported from Google Collections Library)
050 */
051 @GwtCompatible(emulated = true)
052 public abstract class ImmutableMultimap<K, V>
053 implements Multimap<K, V>, Serializable {
054
055 /** Returns an empty multimap. */
056 public static <K, V> ImmutableMultimap<K, V> of() {
057 return ImmutableListMultimap.of();
058 }
059
060 /**
061 * Returns an immutable multimap containing a single entry.
062 */
063 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) {
064 return ImmutableListMultimap.of(k1, v1);
065 }
066
067 /**
068 * Returns an immutable multimap containing the given entries, in order.
069 */
070 public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) {
071 return ImmutableListMultimap.of(k1, v1, k2, v2);
072 }
073
074 /**
075 * Returns an immutable multimap containing the given entries, in order.
076 */
077 public static <K, V> ImmutableMultimap<K, V> of(
078 K k1, V v1, K k2, V v2, K k3, V v3) {
079 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3);
080 }
081
082 /**
083 * Returns an immutable multimap containing the given entries, in order.
084 */
085 public static <K, V> ImmutableMultimap<K, V> of(
086 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
087 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4);
088 }
089
090 /**
091 * Returns an immutable multimap containing the given entries, in order.
092 */
093 public static <K, V> ImmutableMultimap<K, V> of(
094 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
095 return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
096 }
097
098 // looking for of() with > 5 entries? Use the builder instead.
099
100 /**
101 * Returns a new builder. The generated builder is equivalent to the builder
102 * created by the {@link Builder} constructor.
103 */
104 public static <K, V> Builder<K, V> builder() {
105 return new Builder<K, V>();
106 }
107
108 /**
109 * Multimap for {@link ImmutableMultimap.Builder} that maintains key and
110 * value orderings, allows duplicate values, and performs better than
111 * {@link LinkedListMultimap}.
112 */
113 private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> {
114 BuilderMultimap() {
115 super(new LinkedHashMap<K, Collection<V>>());
116 }
117 @Override Collection<V> createCollection() {
118 return Lists.newArrayList();
119 }
120 private static final long serialVersionUID = 0;
121 }
122
123 /**
124 * A builder for creating immutable multimap instances, especially
125 * {@code public static final} multimaps ("constant multimaps"). Example:
126 * <pre> {@code
127 *
128 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
129 * new ImmutableMultimap.Builder<String, Integer>()
130 * .put("one", 1)
131 * .putAll("several", 1, 2, 3)
132 * .putAll("many", 1, 2, 3, 4, 5)
133 * .build();}</pre>
134 *
135 * <p>Builder instances can be reused - it is safe to call {@link #build}
136 * multiple times to build multiple multimaps in series. Each multimap
137 * contains the key-value mappings in the previously created multimaps.
138 */
139 public static class Builder<K, V> {
140 private final Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>();
141
142 /**
143 * Creates a new builder. The returned builder is equivalent to the builder
144 * generated by {@link ImmutableMultimap#builder}.
145 */
146 public Builder() {}
147
148 /**
149 * Adds a key-value mapping to the built multimap.
150 */
151 public Builder<K, V> put(K key, V value) {
152 builderMultimap.put(checkNotNull(key), checkNotNull(value));
153 return this;
154 }
155
156 /**
157 * Stores a collection of values with the same key in the built multimap.
158 *
159 * @throws NullPointerException if {@code key}, {@code values}, or any
160 * element in {@code values} is null. The builder is left in an invalid
161 * state.
162 */
163 public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
164 Collection<V> valueList = builderMultimap.get(checkNotNull(key));
165 for (V value : values) {
166 valueList.add(checkNotNull(value));
167 }
168 return this;
169 }
170
171 /**
172 * Stores an array of values with the same key in the built multimap.
173 *
174 * @throws NullPointerException if the key or any value is null. The builder
175 * is left in an invalid state.
176 */
177 public Builder<K, V> putAll(K key, V... values) {
178 return putAll(key, Arrays.asList(values));
179 }
180
181 /**
182 * Stores another multimap's entries in the built multimap. The generated
183 * multimap's key and value orderings correspond to the iteration ordering
184 * of the {@code multimap.asMap()} view, with new keys and values following
185 * any existing keys and values.
186 *
187 * @throws NullPointerException if any key or value in {@code multimap} is
188 * null. The builder is left in an invalid state.
189 */
190 public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
191 for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry
192 : multimap.asMap().entrySet()) {
193 putAll(entry.getKey(), entry.getValue());
194 }
195 return this;
196 }
197
198 /**
199 * Returns a newly-created immutable multimap.
200 */
201 public ImmutableMultimap<K, V> build() {
202 return copyOf(builderMultimap);
203 }
204 }
205
206 /**
207 * Returns an immutable multimap containing the same mappings as
208 * {@code multimap}. The generated multimap's key and value orderings
209 * correspond to the iteration ordering of the {@code multimap.asMap()} view.
210 *
211 * <p><b>Note:</b> Despite what the method name suggests, if
212 * {@code multimap} is an {@code ImmutableMultimap}, no copy will actually be
213 * performed, and the given multimap itself will be returned.
214 *
215 * @throws NullPointerException if any key or value in {@code multimap} is
216 * null
217 */
218 public static <K, V> ImmutableMultimap<K, V> copyOf(
219 Multimap<? extends K, ? extends V> multimap) {
220 if (multimap instanceof ImmutableMultimap) {
221 @SuppressWarnings("unchecked") // safe since multimap is not writable
222 ImmutableMultimap<K, V> kvMultimap
223 = (ImmutableMultimap<K, V>) multimap;
224 return kvMultimap;
225 } else {
226 return ImmutableListMultimap.copyOf(multimap);
227 }
228 }
229
230 final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map;
231 final transient int size;
232
233 // These constants allow the deserialization code to set final fields. This
234 // holder class makes sure they are not initialized unless an instance is
235 // deserialized.
236 @GwtIncompatible("java serialization is not supported")
237 static class FieldSettersHolder {
238 // Eclipse doesn't like the raw ImmutableMultimap
239 @SuppressWarnings("unchecked")
240 static final Serialization.FieldSetter<ImmutableMultimap>
241 MAP_FIELD_SETTER = Serialization.getFieldSetter(
242 ImmutableMultimap.class, "map");
243 // Eclipse doesn't like the raw ImmutableMultimap
244 @SuppressWarnings("unchecked")
245 static final Serialization.FieldSetter<ImmutableMultimap>
246 SIZE_FIELD_SETTER = Serialization.getFieldSetter(
247 ImmutableMultimap.class, "size");
248 }
249
250 ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map,
251 int size) {
252 this.map = map;
253 this.size = size;
254 }
255
256 // mutators (not supported)
257
258 /**
259 * Guaranteed to throw an exception and leave the multimap unmodified.
260 *
261 * @throws UnsupportedOperationException always
262 */
263 public ImmutableCollection<V> removeAll(Object key) {
264 throw new UnsupportedOperationException();
265 }
266
267 /**
268 * Guaranteed to throw an exception and leave the multimap unmodified.
269 *
270 * @throws UnsupportedOperationException always
271 */
272 public ImmutableCollection<V> replaceValues(K key,
273 Iterable<? extends V> values) {
274 throw new UnsupportedOperationException();
275 }
276
277 /**
278 * Guaranteed to throw an exception and leave the multimap unmodified.
279 *
280 * @throws UnsupportedOperationException always
281 */
282 public void clear() {
283 throw new UnsupportedOperationException();
284 }
285
286 /**
287 * Returns an immutable collection of the values for the given key. If no
288 * mappings in the multimap have the provided key, an empty immutable
289 * collection is returned. The values are in the same order as the parameters
290 * used to build this multimap.
291 */
292 public abstract ImmutableCollection<V> get(K key);
293
294 /**
295 * Guaranteed to throw an exception and leave the multimap unmodified.
296 *
297 * @throws UnsupportedOperationException always
298 */
299 public boolean put(K key, V value) {
300 throw new UnsupportedOperationException();
301 }
302
303 /**
304 * Guaranteed to throw an exception and leave the multimap unmodified.
305 *
306 * @throws UnsupportedOperationException always
307 */
308 public boolean putAll(K key, Iterable<? extends V> values) {
309 throw new UnsupportedOperationException();
310 }
311
312 /**
313 * Guaranteed to throw an exception and leave the multimap unmodified.
314 *
315 * @throws UnsupportedOperationException always
316 */
317 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
318 throw new UnsupportedOperationException();
319 }
320
321 /**
322 * Guaranteed to throw an exception and leave the multimap unmodified.
323 *
324 * @throws UnsupportedOperationException always
325 */
326 public boolean remove(Object key, Object value) {
327 throw new UnsupportedOperationException();
328 }
329
330 // accessors
331
332 public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
333 Collection<V> values = map.get(key);
334 return values != null && values.contains(value);
335 }
336
337 public boolean containsKey(@Nullable Object key) {
338 return map.containsKey(key);
339 }
340
341 public boolean containsValue(@Nullable Object value) {
342 for (Collection<V> valueCollection : map.values()) {
343 if (valueCollection.contains(value)) {
344 return true;
345 }
346 }
347 return false;
348 }
349
350 public boolean isEmpty() {
351 return size == 0;
352 }
353
354 public int size() {
355 return size;
356 }
357
358 @Override public boolean equals(@Nullable Object object) {
359 if (object instanceof Multimap) {
360 Multimap<?, ?> that = (Multimap<?, ?>) object;
361 return this.map.equals(that.asMap());
362 }
363 return false;
364 }
365
366 @Override public int hashCode() {
367 return map.hashCode();
368 }
369
370 @Override public String toString() {
371 return map.toString();
372 }
373
374 // views
375
376 /**
377 * Returns an immutable set of the distinct keys in this multimap. These keys
378 * are ordered according to when they first appeared during the construction
379 * of this multimap.
380 */
381 public ImmutableSet<K> keySet() {
382 return map.keySet();
383 }
384
385 /**
386 * Returns an immutable map that associates each key with its corresponding
387 * values in the multimap.
388 */
389 @SuppressWarnings("unchecked") // a widening cast
390 public ImmutableMap<K, Collection<V>> asMap() {
391 return (ImmutableMap) map;
392 }
393
394 private transient ImmutableCollection<Map.Entry<K, V>> entries;
395
396 /**
397 * Returns an immutable collection of all key-value pairs in the multimap. Its
398 * iterator traverses the values for the first key, the values for the second
399 * key, and so on.
400 */
401 public ImmutableCollection<Map.Entry<K, V>> entries() {
402 ImmutableCollection<Map.Entry<K, V>> result = entries;
403 return (result == null)
404 ? (entries = new EntryCollection<K, V>(this)) : result;
405 }
406
407 private static class EntryCollection<K, V>
408 extends ImmutableCollection<Map.Entry<K, V>> {
409 final ImmutableMultimap<K, V> multimap;
410
411 EntryCollection(ImmutableMultimap<K, V> multimap) {
412 this.multimap = multimap;
413 }
414
415 @Override public UnmodifiableIterator<Map.Entry<K, V>> iterator() {
416 final Iterator<? extends Map.Entry<K, ? extends ImmutableCollection<V>>>
417 mapIterator = this.multimap.map.entrySet().iterator();
418
419 return new UnmodifiableIterator<Map.Entry<K, V>>() {
420 K key;
421 Iterator<V> valueIterator;
422
423 public boolean hasNext() {
424 return (key != null && valueIterator.hasNext())
425 || mapIterator.hasNext();
426 }
427
428 public Map.Entry<K, V> next() {
429 if (key == null || !valueIterator.hasNext()) {
430 Map.Entry<K, ? extends ImmutableCollection<V>> entry
431 = mapIterator.next();
432 key = entry.getKey();
433 valueIterator = entry.getValue().iterator();
434 }
435 return Maps.immutableEntry(key, valueIterator.next());
436 }
437 };
438 }
439
440 public int size() {
441 return multimap.size();
442 }
443
444 @Override public boolean contains(Object object) {
445 if (object instanceof Map.Entry) {
446 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
447 return multimap.containsEntry(entry.getKey(), entry.getValue());
448 }
449 return false;
450 }
451
452 private static final long serialVersionUID = 0;
453 }
454
455 private transient ImmutableMultiset<K> keys;
456
457 /**
458 * Returns a collection, which may contain duplicates, of all keys. The number
459 * of times a key appears in the returned multiset equals the number of
460 * mappings the key has in the multimap. Duplicate keys appear consecutively
461 * in the multiset's iteration order.
462 */
463 public ImmutableMultiset<K> keys() {
464 ImmutableMultiset<K> result = keys;
465 return (result == null) ? (keys = createKeys()) : result;
466 }
467
468 private ImmutableMultiset<K> createKeys() {
469 ImmutableMultiset.Builder<K> builder = ImmutableMultiset.builder();
470 for (Map.Entry<K, ? extends ImmutableCollection<V>> entry
471 : map.entrySet()) {
472 builder.addCopies(entry.getKey(), entry.getValue().size());
473 }
474 return builder.build();
475 }
476
477 private transient ImmutableCollection<V> values;
478
479 /**
480 * Returns an immutable collection of the values in this multimap. Its
481 * iterator traverses the values for the first key, the values for the second
482 * key, and so on.
483 */
484 public ImmutableCollection<V> values() {
485 ImmutableCollection<V> result = values;
486 return (result == null) ? (values = new Values<V>(this)) : result;
487 }
488
489 private static class Values<V> extends ImmutableCollection<V> {
490 final Multimap<?, V> multimap;
491
492 Values(Multimap<?, V> multimap) {
493 this.multimap = multimap;
494 }
495
496 @Override public UnmodifiableIterator<V> iterator() {
497 final Iterator<? extends Map.Entry<?, V>> entryIterator
498 = multimap.entries().iterator();
499 return new UnmodifiableIterator<V>() {
500 public boolean hasNext() {
501 return entryIterator.hasNext();
502 }
503 public V next() {
504 return entryIterator.next().getValue();
505 }
506 };
507 }
508
509 public int size() {
510 return multimap.size();
511 }
512
513 private static final long serialVersionUID = 0;
514 }
515
516 private static final long serialVersionUID = 0;
517 }