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 import static com.google.common.collect.Iterables.getOnlyElement;
021
022 import com.google.common.annotations.GwtCompatible;
023
024 import java.io.Serializable;
025 import java.util.Collections;
026 import java.util.List;
027 import java.util.Map;
028
029 import javax.annotation.Nullable;
030
031 /**
032 * An immutable, hash-based {@link Map} with reliable user-specified iteration
033 * order. Does not permit null keys or values.
034 *
035 * <p>Unlike {@link Collections#unmodifiableMap}, which is a <i>view</i> of a
036 * separate map which can still change, an instance of {@code ImmutableMap}
037 * contains its own data and will <i>never</i> change. {@code ImmutableMap} is
038 * convenient for {@code public static final} maps ("constant maps") and also
039 * lets you easily make a "defensive copy" of a map provided to your class by a
040 * caller.
041 *
042 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
043 * it has no public or protected constructors. Thus, instances of this class are
044 * guaranteed to be immutable.
045 *
046 * @see ImmutableList
047 * @see ImmutableSet
048 * @author Jesse Wilson
049 * @author Kevin Bourrillion
050 * @since 2 (imported from Google Collections Library)
051 */
052 @GwtCompatible(serializable = true, emulated = true)
053 @SuppressWarnings("serial") // we're overriding default serialization
054 public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
055 /**
056 * Returns the empty map. This map behaves and performs comparably to
057 * {@link Collections#emptyMap}, and is preferable mainly for consistency
058 * and maintainability of your code.
059 */
060 // Casting to any type is safe because the set will never hold any elements.
061 @SuppressWarnings("unchecked")
062 public static <K, V> ImmutableMap<K, V> of() {
063 return (ImmutableMap<K, V>) EmptyImmutableMap.INSTANCE;
064 }
065
066 /**
067 * Returns an immutable map containing a single entry. This map behaves and
068 * performs comparably to {@link Collections#singletonMap} but will not accept
069 * a null key or value. It is preferable mainly for consistency and
070 * maintainability of your code.
071 */
072 public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
073 return new SingletonImmutableMap<K, V>(
074 checkNotNull(k1), checkNotNull(v1));
075 }
076
077 /**
078 * Returns an immutable map containing the given entries, in order.
079 *
080 * @throws IllegalArgumentException if duplicate keys are provided
081 */
082 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
083 return new RegularImmutableMap<K, V>(entryOf(k1, v1), entryOf(k2, v2));
084 }
085
086 /**
087 * Returns an immutable map containing the given entries, in order.
088 *
089 * @throws IllegalArgumentException if duplicate keys are provided
090 */
091 public static <K, V> ImmutableMap<K, V> of(
092 K k1, V v1, K k2, V v2, K k3, V v3) {
093 return new RegularImmutableMap<K, V>(
094 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
095 }
096
097 /**
098 * Returns an immutable map containing the given entries, in order.
099 *
100 * @throws IllegalArgumentException if duplicate keys are provided
101 */
102 public static <K, V> ImmutableMap<K, V> of(
103 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
104 return new RegularImmutableMap<K, V>(
105 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
106 }
107
108 /**
109 * Returns an immutable map containing the given entries, in order.
110 *
111 * @throws IllegalArgumentException if duplicate keys are provided
112 */
113 public static <K, V> ImmutableMap<K, V> of(
114 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
115 return new RegularImmutableMap<K, V>(entryOf(k1, v1),
116 entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
117 }
118
119 // looking for of() with > 5 entries? Use the builder instead.
120
121 /**
122 * Returns a new builder. The generated builder is equivalent to the builder
123 * created by the {@link Builder} constructor.
124 */
125 public static <K, V> Builder<K, V> builder() {
126 return new Builder<K, V>();
127 }
128
129 /**
130 * Verifies that {@code key} and {@code value} are non-null, and returns a new
131 * immutable entry with those values.
132 *
133 * <p>A call to {@link Map.Entry#setValue} on the returned entry will always
134 * throw {@link UnsupportedOperationException}.
135 */
136 static <K, V> Entry<K, V> entryOf(K key, V value) {
137 return Maps.immutableEntry(checkNotNull(key), checkNotNull(value));
138 }
139
140 /**
141 * A builder for creating immutable map instances, especially {@code public
142 * static final} maps ("constant maps"). Example: <pre> {@code
143 *
144 * static final ImmutableMap<String, Integer> WORD_TO_INT =
145 * new ImmutableMap.Builder<String, Integer>()
146 * .put("one", 1)
147 * .put("two", 2)
148 * .put("three", 3)
149 * .build();}</pre>
150 *
151 * For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are
152 * even more convenient.
153 *
154 * <p>Builder instances can be reused - it is safe to call {@link #build}
155 * multiple times to build multiple maps in series. Each map is a superset of
156 * the maps created before it.
157 */
158 public static class Builder<K, V> {
159 final List<Entry<K, V>> entries = Lists.newArrayList();
160
161 /**
162 * Creates a new builder. The returned builder is equivalent to the builder
163 * generated by {@link ImmutableMap#builder}.
164 */
165 public Builder() {}
166
167 /**
168 * Associates {@code key} with {@code value} in the built map. Duplicate
169 * keys are not allowed, and will cause {@link #build} to fail.
170 */
171 public Builder<K, V> put(K key, V value) {
172 entries.add(entryOf(key, value));
173 return this;
174 }
175
176 /**
177 * Associates all of the given map's keys and values in the built map.
178 * Duplicate keys are not allowed, and will cause {@link #build} to fail.
179 *
180 * @throws NullPointerException if any key or value in {@code map} is null
181 */
182 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
183 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
184 put(entry.getKey(), entry.getValue());
185 }
186 return this;
187 }
188
189 // TODO: Should build() and the ImmutableBiMap & ImmutableSortedMap versions
190 // throw an IllegalStateException instead?
191
192 /**
193 * Returns a newly-created immutable map.
194 *
195 * @throws IllegalArgumentException if duplicate keys were added
196 */
197 public ImmutableMap<K, V> build() {
198 return fromEntryList(entries);
199 }
200
201 private static <K, V> ImmutableMap<K, V> fromEntryList(
202 List<Entry<K, V>> entries) {
203 int size = entries.size();
204 switch (size) {
205 case 0:
206 return of();
207 case 1:
208 return new SingletonImmutableMap<K, V>(getOnlyElement(entries));
209 default:
210 Entry<?, ?>[] entryArray
211 = entries.toArray(new Entry<?, ?>[entries.size()]);
212 return new RegularImmutableMap<K, V>(entryArray);
213 }
214 }
215 }
216
217 /**
218 * Returns an immutable map containing the same entries as {@code map}. If
219 * {@code map} somehow contains entries with duplicate keys (for example, if
220 * it is a {@code SortedMap} whose comparator is not <i>consistent with
221 * equals</i>), the results of this method are undefined.
222 *
223 * <p><b>Note:</b> Despite what the method name suggests, if {@code map} is an
224 * {@code ImmutableMap}, no copy will actually be performed, and the given map
225 * itself will be returned.
226 *
227 * @throws NullPointerException if any key or value in {@code map} is null
228 */
229 public static <K, V> ImmutableMap<K, V> copyOf(
230 Map<? extends K, ? extends V> map) {
231 if ((map instanceof ImmutableMap) && !(map instanceof ImmutableSortedMap)) {
232 @SuppressWarnings("unchecked") // safe since map is not writable
233 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
234 return kvMap;
235 }
236
237 @SuppressWarnings("unchecked") // we won't write to this array
238 Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]);
239 switch (entries.length) {
240 case 0:
241 return of();
242 case 1:
243 return new SingletonImmutableMap<K, V>(entryOf(
244 entries[0].getKey(), entries[0].getValue()));
245 default:
246 for (int i = 0; i < entries.length; i++) {
247 K k = entries[i].getKey();
248 V v = entries[i].getValue();
249 entries[i] = entryOf(k, v);
250 }
251 return new RegularImmutableMap<K, V>(entries);
252 }
253 }
254
255 ImmutableMap() {}
256
257 /**
258 * Guaranteed to throw an exception and leave the map unmodified.
259 *
260 * @throws UnsupportedOperationException always
261 */
262 public final V put(K k, V v) {
263 throw new UnsupportedOperationException();
264 }
265
266 /**
267 * Guaranteed to throw an exception and leave the map unmodified.
268 *
269 * @throws UnsupportedOperationException always
270 */
271 public final V remove(Object o) {
272 throw new UnsupportedOperationException();
273 }
274
275 /**
276 * Guaranteed to throw an exception and leave the map unmodified.
277 *
278 * @throws UnsupportedOperationException always
279 */
280 public final void putAll(Map<? extends K, ? extends V> map) {
281 throw new UnsupportedOperationException();
282 }
283
284 /**
285 * Guaranteed to throw an exception and leave the map unmodified.
286 *
287 * @throws UnsupportedOperationException always
288 */
289 public final void clear() {
290 throw new UnsupportedOperationException();
291 }
292
293 public boolean isEmpty() {
294 return size() == 0;
295 }
296
297 public boolean containsKey(@Nullable Object key) {
298 return get(key) != null;
299 }
300
301 // Overriding to mark it Nullable
302 public abstract boolean containsValue(@Nullable Object value);
303
304 // Overriding to mark it Nullable
305 public abstract V get(@Nullable Object key);
306
307 /**
308 * Returns an immutable set of the mappings in this map. The entries are in
309 * the same order as the parameters used to build this map.
310 */
311 public abstract ImmutableSet<Entry<K, V>> entrySet();
312
313 /**
314 * Returns an immutable set of the keys in this map. These keys are in
315 * the same order as the parameters used to build this map.
316 */
317 public abstract ImmutableSet<K> keySet();
318
319 /**
320 * Returns an immutable collection of the values in this map. The values are
321 * in the same order as the parameters used to build this map.
322 */
323 public abstract ImmutableCollection<V> values();
324
325 @Override public boolean equals(@Nullable Object object) {
326 if (object == this) {
327 return true;
328 }
329 if (object instanceof Map) {
330 Map<?, ?> that = (Map<?, ?>) object;
331 return this.entrySet().equals(that.entrySet());
332 }
333 return false;
334 }
335
336 @Override public int hashCode() {
337 // not caching hash code since it could change if map values are mutable
338 // in a way that modifies their hash codes
339 return entrySet().hashCode();
340 }
341
342 @Override public String toString() {
343 StringBuilder result = new StringBuilder(size() * 16).append('{');
344 Maps.standardJoiner.appendTo(result, this);
345 return result.append('}').toString();
346 }
347
348 /**
349 * Serialized type for all ImmutableMap instances. It captures the logical
350 * contents and they are reconstructed using public factory methods. This
351 * ensures that the implementation types remain as implementation details.
352 */
353 static class SerializedForm implements Serializable {
354 private final Object[] keys;
355 private final Object[] values;
356 SerializedForm(ImmutableMap<?, ?> map) {
357 keys = new Object[map.size()];
358 values = new Object[map.size()];
359 int i = 0;
360 for (Entry<?, ?> entry : map.entrySet()) {
361 keys[i] = entry.getKey();
362 values[i] = entry.getValue();
363 i++;
364 }
365 }
366 Object readResolve() {
367 Builder<Object, Object> builder = new Builder<Object, Object>();
368 return createMap(builder);
369 }
370 Object createMap(Builder<Object, Object> builder) {
371 for (int i = 0; i < keys.length; i++) {
372 builder.put(keys[i], values[i]);
373 }
374 return builder.build();
375 }
376 private static final long serialVersionUID = 0;
377 }
378
379 Object writeReplace() {
380 return new SerializedForm(this);
381 }
382 }