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 import static com.google.common.collect.Iterables.getOnlyElement;
021
022 import com.google.common.annotations.GwtCompatible;
023 import com.google.common.collect.ImmutableSet.TransformedImmutableSet;
024
025 import java.io.Serializable;
026 import java.util.ArrayList;
027 import java.util.Collections;
028 import java.util.HashMap;
029 import java.util.List;
030 import java.util.Map;
031
032 import javax.annotation.Nullable;
033
034 /**
035 * An immutable, hash-based {@link Map} with reliable user-specified iteration
036 * order. Does not permit null keys or values.
037 *
038 * <p>Unlike {@link Collections#unmodifiableMap}, which is a <i>view</i> of a
039 * separate map which can still change, an instance of {@code ImmutableMap}
040 * contains its own data and will <i>never</i> change. {@code ImmutableMap} is
041 * convenient for {@code public static final} maps ("constant maps") and also
042 * lets you easily make a "defensive copy" of a map provided to your class by a
043 * caller.
044 *
045 * <p><i>Performance notes:</i> unlike {@link HashMap}, {@code ImmutableMap} is
046 * not optimized for element types that have slow {@link Object#equals} or
047 * {@link Object#hashCode} implementations. You can get better performance by
048 * having your element type cache its own hash codes, and by making use of the
049 * cached values to short-circuit a slow {@code equals} algorithm.
050 *
051 * <p>See the Guava User Guide article on <a href=
052 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
053 * immutable collections</a>.
054 *
055 * @author Jesse Wilson
056 * @author Kevin Bourrillion
057 * @since 2.0 (imported from Google Collections Library)
058 */
059 @GwtCompatible(serializable = true, emulated = true)
060 @SuppressWarnings("serial") // we're overriding default serialization
061 public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
062 /**
063 * Returns the empty map. This map behaves and performs comparably to
064 * {@link Collections#emptyMap}, and is preferable mainly for consistency
065 * and maintainability of your code.
066 */
067 // Casting to any type is safe because the set will never hold any elements.
068 @SuppressWarnings("unchecked")
069 public static <K, V> ImmutableMap<K, V> of() {
070 return (ImmutableMap<K, V>) EmptyImmutableMap.INSTANCE;
071 }
072
073 /**
074 * Returns an immutable map containing a single entry. This map behaves and
075 * performs comparably to {@link Collections#singletonMap} but will not accept
076 * a null key or value. It is preferable mainly for consistency and
077 * maintainability of your code.
078 */
079 public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
080 return new SingletonImmutableMap<K, V>(
081 checkNotNull(k1), checkNotNull(v1));
082 }
083
084 /**
085 * Returns an immutable map containing the given entries, in order.
086 *
087 * @throws IllegalArgumentException if duplicate keys are provided
088 */
089 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
090 return new RegularImmutableMap<K, V>(entryOf(k1, v1), entryOf(k2, v2));
091 }
092
093 /**
094 * Returns an immutable map containing the given entries, in order.
095 *
096 * @throws IllegalArgumentException if duplicate keys are provided
097 */
098 public static <K, V> ImmutableMap<K, V> of(
099 K k1, V v1, K k2, V v2, K k3, V v3) {
100 return new RegularImmutableMap<K, V>(
101 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
102 }
103
104 /**
105 * Returns an immutable map containing the given entries, in order.
106 *
107 * @throws IllegalArgumentException if duplicate keys are provided
108 */
109 public static <K, V> ImmutableMap<K, V> of(
110 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
111 return new RegularImmutableMap<K, V>(
112 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
113 }
114
115 /**
116 * Returns an immutable map containing the given entries, in order.
117 *
118 * @throws IllegalArgumentException if duplicate keys are provided
119 */
120 public static <K, V> ImmutableMap<K, V> of(
121 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
122 return new RegularImmutableMap<K, V>(entryOf(k1, v1),
123 entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
124 }
125
126 // looking for of() with > 5 entries? Use the builder instead.
127
128 /**
129 * Returns a new builder. The generated builder is equivalent to the builder
130 * created by the {@link Builder} constructor.
131 */
132 public static <K, V> Builder<K, V> builder() {
133 return new Builder<K, V>();
134 }
135
136 /**
137 * Verifies that {@code key} and {@code value} are non-null, and returns a new
138 * immutable entry with those values.
139 *
140 * <p>A call to {@link Map.Entry#setValue} on the returned entry will always
141 * throw {@link UnsupportedOperationException}.
142 */
143 static <K, V> Entry<K, V> entryOf(K key, V value) {
144 return Maps.immutableEntry(
145 checkNotNull(key, "null key"),
146 checkNotNull(value, "null value"));
147 }
148
149 /**
150 * A builder for creating immutable map instances, especially {@code public
151 * static final} maps ("constant maps"). Example: <pre> {@code
152 *
153 * static final ImmutableMap<String, Integer> WORD_TO_INT =
154 * new ImmutableMap.Builder<String, Integer>()
155 * .put("one", 1)
156 * .put("two", 2)
157 * .put("three", 3)
158 * .build();}</pre>
159 *
160 * For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are
161 * even more convenient.
162 *
163 * <p>Builder instances can be reused - it is safe to call {@link #build}
164 * multiple times to build multiple maps in series. Each map is a superset of
165 * the maps created before it.
166 *
167 * @since 2.0 (imported from Google Collections Library)
168 */
169 public static class Builder<K, V> {
170 final ArrayList<Entry<K, V>> entries = Lists.newArrayList();
171
172 /**
173 * Creates a new builder. The returned builder is equivalent to the builder
174 * generated by {@link ImmutableMap#builder}.
175 */
176 public Builder() {}
177
178 /**
179 * Associates {@code key} with {@code value} in the built map. Duplicate
180 * keys are not allowed, and will cause {@link #build} to fail.
181 */
182 public Builder<K, V> put(K key, V value) {
183 entries.add(entryOf(key, value));
184 return this;
185 }
186
187 /**
188 * Adds the given {@code entry} to the map, making it immutable if
189 * necessary. Duplicate keys are not allowed, and will cause {@link #build}
190 * to fail.
191 *
192 * @since 11.0
193 */
194 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
195 K key = entry.getKey();
196 V value = entry.getValue();
197 if (entry instanceof ImmutableEntry<?, ?>) {
198 checkNotNull(key);
199 checkNotNull(value);
200 @SuppressWarnings("unchecked") // all supported methods are covariant
201 Entry<K, V> immutableEntry = (Entry<K, V>) entry;
202 entries.add(immutableEntry);
203 } else {
204 // Directly calling entryOf(entry.getKey(), entry.getValue()) can cause
205 // compilation error in Eclipse.
206 entries.add(entryOf(key, value));
207 }
208 return this;
209 }
210
211 /**
212 * Associates all of the given map's keys and values in the built map.
213 * Duplicate keys are not allowed, and will cause {@link #build} to fail.
214 *
215 * @throws NullPointerException if any key or value in {@code map} is null
216 */
217 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
218 entries.ensureCapacity(entries.size() + map.size());
219 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
220 put(entry.getKey(), entry.getValue());
221 }
222 return this;
223 }
224
225 /*
226 * TODO(kevinb): Should build() and the ImmutableBiMap & ImmutableSortedMap
227 * versions throw an IllegalStateException instead?
228 */
229
230 /**
231 * Returns a newly-created immutable map.
232 *
233 * @throws IllegalArgumentException if duplicate keys were added
234 */
235 public ImmutableMap<K, V> build() {
236 return fromEntryList(entries);
237 }
238
239 private static <K, V> ImmutableMap<K, V> fromEntryList(
240 List<Entry<K, V>> entries) {
241 int size = entries.size();
242 switch (size) {
243 case 0:
244 return of();
245 case 1:
246 return new SingletonImmutableMap<K, V>(getOnlyElement(entries));
247 default:
248 Entry<?, ?>[] entryArray
249 = entries.toArray(new Entry<?, ?>[entries.size()]);
250 return new RegularImmutableMap<K, V>(entryArray);
251 }
252 }
253 }
254
255 /**
256 * Returns an immutable map containing the same entries as {@code map}. If
257 * {@code map} somehow contains entries with duplicate keys (for example, if
258 * it is a {@code SortedMap} whose comparator is not <i>consistent with
259 * equals</i>), the results of this method are undefined.
260 *
261 * <p>Despite the method name, this method attempts to avoid actually copying
262 * the data when it is safe to do so. The exact circumstances under which a
263 * copy will or will not be performed are undocumented and subject to change.
264 *
265 * @throws NullPointerException if any key or value in {@code map} is null
266 */
267 public static <K, V> ImmutableMap<K, V> copyOf(
268 Map<? extends K, ? extends V> map) {
269 if ((map instanceof ImmutableMap) && !(map instanceof ImmutableSortedMap)) {
270 // TODO(user): Make ImmutableMap.copyOf(immutableBiMap) call copyOf()
271 // on the ImmutableMap delegate(), rather than the bimap itself
272
273 @SuppressWarnings("unchecked") // safe since map is not writable
274 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
275 if (!kvMap.isPartialView()) {
276 return kvMap;
277 }
278 }
279
280 @SuppressWarnings("unchecked") // we won't write to this array
281 Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]);
282 switch (entries.length) {
283 case 0:
284 return of();
285 case 1:
286 return new SingletonImmutableMap<K, V>(entryOf(
287 entries[0].getKey(), entries[0].getValue()));
288 default:
289 for (int i = 0; i < entries.length; i++) {
290 K k = entries[i].getKey();
291 V v = entries[i].getValue();
292 entries[i] = entryOf(k, v);
293 }
294 return new RegularImmutableMap<K, V>(entries);
295 }
296 }
297
298 ImmutableMap() {}
299
300 /**
301 * Guaranteed to throw an exception and leave the map unmodified.
302 *
303 * @throws UnsupportedOperationException always
304 */
305 @Override
306 public final V put(K k, V v) {
307 throw new UnsupportedOperationException();
308 }
309
310 /**
311 * Guaranteed to throw an exception and leave the map unmodified.
312 *
313 * @throws UnsupportedOperationException always
314 */
315 @Override
316 public final V remove(Object o) {
317 throw new UnsupportedOperationException();
318 }
319
320 /**
321 * Guaranteed to throw an exception and leave the map unmodified.
322 *
323 * @throws UnsupportedOperationException always
324 */
325 @Override
326 public final void putAll(Map<? extends K, ? extends V> map) {
327 throw new UnsupportedOperationException();
328 }
329
330 /**
331 * Guaranteed to throw an exception and leave the map unmodified.
332 *
333 * @throws UnsupportedOperationException always
334 */
335 @Override
336 public final void clear() {
337 throw new UnsupportedOperationException();
338 }
339
340 @Override
341 public boolean isEmpty() {
342 return size() == 0;
343 }
344
345 @Override
346 public boolean containsKey(@Nullable Object key) {
347 return get(key) != null;
348 }
349
350 // Overriding to mark it Nullable
351 @Override
352 public abstract boolean containsValue(@Nullable Object value);
353
354 // Overriding to mark it Nullable
355 @Override
356 public abstract V get(@Nullable Object key);
357
358 private transient ImmutableSet<Entry<K, V>> entrySet;
359
360 /**
361 * Returns an immutable set of the mappings in this map. The entries are in
362 * the same order as the parameters used to build this map.
363 */
364 @Override
365 public ImmutableSet<Entry<K, V>> entrySet() {
366 ImmutableSet<Entry<K, V>> result = entrySet;
367 return (result == null) ? entrySet = createEntrySet() : result;
368 }
369
370 abstract ImmutableSet<Entry<K, V>> createEntrySet();
371
372 abstract class EntrySet extends ImmutableSet<Entry<K, V>> {
373 @Override
374 public int size() {
375 return ImmutableMap.this.size();
376 }
377
378 @Override
379 public boolean contains(@Nullable Object object) {
380 if (object instanceof Entry) {
381 Entry<?, ?> entry = (Entry<?, ?>) object;
382 V value = get(entry.getKey());
383 return value != null && value.equals(entry.getValue());
384 }
385 return false;
386 }
387
388 @Override
389 boolean isPartialView() {
390 return ImmutableMap.this.isPartialView();
391 }
392
393 @Override
394 Object writeReplace() {
395 return new EntrySetSerializedForm<K, V>(ImmutableMap.this);
396 }
397 }
398
399 private static class EntrySetSerializedForm<K, V> implements Serializable {
400 final ImmutableMap<K, V> map;
401 EntrySetSerializedForm(ImmutableMap<K, V> map) {
402 this.map = map;
403 }
404 Object readResolve() {
405 return map.entrySet();
406 }
407 private static final long serialVersionUID = 0;
408 }
409
410 private transient ImmutableSet<K> keySet;
411
412 /**
413 * Returns an immutable set of the keys in this map. These keys are in
414 * the same order as the parameters used to build this map.
415 */
416 @Override
417 public ImmutableSet<K> keySet() {
418 ImmutableSet<K> result = keySet;
419 return (result == null) ? keySet = createKeySet() : result;
420 }
421
422 ImmutableSet<K> createKeySet() {
423 return new KeySet();
424 }
425
426 class KeySet extends TransformedImmutableSet<Entry<K, V>, K> {
427 KeySet() {
428 super(entrySet());
429 }
430
431 KeySet(int hashCode) {
432 super(entrySet(), hashCode);
433 }
434
435 @Override
436 K transform(Entry<K, V> entry) {
437 return entry.getKey();
438 }
439
440 @Override
441 public boolean contains(@Nullable Object object) {
442 return containsKey(object);
443 }
444
445 @Override
446 boolean isPartialView() {
447 return true;
448 }
449
450 @Override
451 ImmutableList<K> createAsList() {
452 // TODO(user): rewrite to delegate contains() calls to the KeySet
453 return new TransformedImmutableList<Entry<K, V>, K>(entrySet().asList()) {
454 @Override
455 K transform(Entry<K, V> entry) {
456 return entry.getKey();
457 }
458 };
459 }
460
461 @Override Object writeReplace() {
462 return new KeySetSerializedForm<K>(ImmutableMap.this);
463 }
464 }
465
466 private static class KeySetSerializedForm<K> implements Serializable {
467 final ImmutableMap<K, ?> map;
468 KeySetSerializedForm(ImmutableMap<K, ?> map) {
469 this.map = map;
470 }
471 Object readResolve() {
472 return map.keySet();
473 }
474 private static final long serialVersionUID = 0;
475 }
476
477 private transient ImmutableCollection<V> values;
478
479 /**
480 * Returns an immutable collection of the values in this map. The values are
481 * in the same order as the parameters used to build this map.
482 */
483 @Override
484 public ImmutableCollection<V> values() {
485 ImmutableCollection<V> result = values;
486 return (result == null) ? values = createValues() : result;
487 }
488
489 ImmutableCollection<V> createValues() {
490 return new Values();
491 }
492
493 class Values extends ImmutableCollection<V> {
494 @Override
495 public int size() {
496 return ImmutableMap.this.size();
497 }
498
499 @Override
500 public UnmodifiableIterator<V> iterator() {
501 return Maps.valueIterator(entrySet().iterator());
502 }
503
504 @Override
505 public boolean contains(Object object) {
506 return containsValue(object);
507 }
508
509 @Override
510 boolean isPartialView() {
511 return true;
512 }
513
514 @Override
515 ImmutableList<V> createAsList() {
516 // TODO(user): rewrite to delegate contains() calls to the Values
517 return new TransformedImmutableList<Entry<K, V>, V>(entrySet().asList()) {
518 @Override
519 V transform(Entry<K, V> entry) {
520 return entry.getValue();
521 }
522 };
523 }
524
525 @Override Object writeReplace() {
526 return new ValuesSerializedForm<V>(ImmutableMap.this);
527 }
528 }
529
530 private static class ValuesSerializedForm<V> implements Serializable {
531 final ImmutableMap<?, V> map;
532 ValuesSerializedForm(ImmutableMap<?, V> map) {
533 this.map = map;
534 }
535 Object readResolve() {
536 return map.values();
537 }
538 private static final long serialVersionUID = 0;
539 }
540
541 @Override public boolean equals(@Nullable Object object) {
542 if (object == this) {
543 return true;
544 }
545 if (object instanceof Map) {
546 Map<?, ?> that = (Map<?, ?>) object;
547 return this.entrySet().equals(that.entrySet());
548 }
549 return false;
550 }
551
552 abstract boolean isPartialView();
553
554 @Override public int hashCode() {
555 // not caching hash code since it could change if map values are mutable
556 // in a way that modifies their hash codes
557 return entrySet().hashCode();
558 }
559
560 @Override public String toString() {
561 return Maps.toStringImpl(this);
562 }
563
564 /**
565 * Serialized type for all ImmutableMap instances. It captures the logical
566 * contents and they are reconstructed using public factory methods. This
567 * ensures that the implementation types remain as implementation details.
568 */
569 static class SerializedForm implements Serializable {
570 private final Object[] keys;
571 private final Object[] values;
572 SerializedForm(ImmutableMap<?, ?> map) {
573 keys = new Object[map.size()];
574 values = new Object[map.size()];
575 int i = 0;
576 for (Entry<?, ?> entry : map.entrySet()) {
577 keys[i] = entry.getKey();
578 values[i] = entry.getValue();
579 i++;
580 }
581 }
582 Object readResolve() {
583 Builder<Object, Object> builder = new Builder<Object, Object>();
584 return createMap(builder);
585 }
586 Object createMap(Builder<Object, Object> builder) {
587 for (int i = 0; i < keys.length; i++) {
588 builder.put(keys[i], values[i]);
589 }
590 return builder.build();
591 }
592 private static final long serialVersionUID = 0;
593 }
594
595 Object writeReplace() {
596 return new SerializedForm(this);
597 }
598 }