1 /*
2 * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.Map.Entry;
29 import sun.misc.SharedSecrets;
30
31 /**
32 * A specialized {@link Map} implementation for use with enum type keys. All
33 * of the keys in an enum map must come from a single enum type that is
34 * specified, explicitly or implicitly, when the map is created. Enum maps
35 * are represented internally as arrays. This representation is extremely
36 * compact and efficient.
37 *
38 * <p>Enum maps are maintained in the <i>natural order</i> of their keys
39 * (the order in which the enum constants are declared). This is reflected
40 * in the iterators returned by the collections views ({@link #keySet()},
41 * {@link #entrySet()}, and {@link #values()}).
42 *
43 * <p>Iterators returned by the collection views are <i>weakly consistent</i>:
44 * they will never throw {@link ConcurrentModificationException} and they may
45 * or may not show the effects of any modifications to the map that occur while
46 * the iteration is in progress.
47 *
48 * <p>Null keys are not permitted. Attempts to insert a null key will
49 * throw {@link NullPointerException}. Attempts to test for the
50 * presence of a null key or to remove one will, however, function properly.
51 * Null values are permitted.
52
53 * <P>Like most collection implementations <tt>EnumMap</tt> is not
54 * synchronized. If multiple threads access an enum map concurrently, and at
55 * least one of the threads modifies the map, it should be synchronized
56 * externally. This is typically accomplished by synchronizing on some
57 * object that naturally encapsulates the enum map. If no such object exists,
58 * the map should be "wrapped" using the {@link Collections#synchronizedMap}
59 * method. This is best done at creation time, to prevent accidental
60 * unsynchronized access:
61 *
62 * <pre>
63 * Map<EnumKey, V> m
64 * = Collections.synchronizedMap(new EnumMap<EnumKey, V>(...));
65 * </pre>
66 *
67 * <p>Implementation note: All basic operations execute in constant time.
68 * They are likely (though not guaranteed) to be faster than their
69 * {@link HashMap} counterparts.
70 *
71 * <p>This class is a member of the
72 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
73 * Java Collections Framework</a>.
74 *
75 * @author Josh Bloch
76 * @see EnumSet
77 * @since 1.5
78 */
79 public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
80 implements java.io.Serializable, Cloneable
81 {
82 /**
83 * The <tt>Class</tt> object for the enum type of all the keys of this map.
84 *
85 * @serial
86 */
87 private final Class<K> keyType;
88
89 /**
90 * All of the values comprising K. (Cached for performance.)
91 */
92 private transient K[] keyUniverse;
93
94 /**
95 * Array representation of this map. The ith element is the value
96 * to which universe[i] is currently mapped, or null if it isn't
97 * mapped to anything, or NULL if it's mapped to null.
98 */
99 private transient Object[] vals;
100
101 /**
102 * The number of mappings in this map.
103 */
104 private transient int size = 0;
105
106 /**
107 * Distinguished non-null value for representing null values.
108 */
109 private static final Object NULL = new Integer(0);
110
111 private Object maskNull(Object value) {
112 return (value == null ? NULL : value);
113 }
114
115 private V unmaskNull(Object value) {
116 return (V) (value == NULL ? null : value);
117 }
118
119 private static final Enum[] ZERO_LENGTH_ENUM_ARRAY = new Enum[0];
120
121 /**
122 * Creates an empty enum map with the specified key type.
123 *
124 * @param keyType the class object of the key type for this enum map
125 * @throws NullPointerException if <tt>keyType</tt> is null
126 */
127 public EnumMap(Class<K> keyType) {
128 this.keyType = keyType;
129 keyUniverse = getKeyUniverse(keyType);
130 vals = new Object[keyUniverse.length];
131 }
132
133 /**
134 * Creates an enum map with the same key type as the specified enum
135 * map, initially containing the same mappings (if any).
136 *
137 * @param m the enum map from which to initialize this enum map
138 * @throws NullPointerException if <tt>m</tt> is null
139 */
140 public EnumMap(EnumMap<K, ? extends V> m) {
141 keyType = m.keyType;
142 keyUniverse = m.keyUniverse;
143 vals = m.vals.clone();
144 size = m.size;
145 }
146
147 /**
148 * Creates an enum map initialized from the specified map. If the
149 * specified map is an <tt>EnumMap</tt> instance, this constructor behaves
150 * identically to {@link #EnumMap(EnumMap)}. Otherwise, the specified map
151 * must contain at least one mapping (in order to determine the new
152 * enum map's key type).
153 *
154 * @param m the map from which to initialize this enum map
155 * @throws IllegalArgumentException if <tt>m</tt> is not an
156 * <tt>EnumMap</tt> instance and contains no mappings
157 * @throws NullPointerException if <tt>m</tt> is null
158 */
159 public EnumMap(Map<K, ? extends V> m) {
160 if (m instanceof EnumMap) {
161 EnumMap<K, ? extends V> em = (EnumMap<K, ? extends V>) m;
162 keyType = em.keyType;
163 keyUniverse = em.keyUniverse;
164 vals = em.vals.clone();
165 size = em.size;
166 } else {
167 if (m.isEmpty())
168 throw new IllegalArgumentException("Specified map is empty");
169 keyType = m.keySet().iterator().next().getDeclaringClass();
170 keyUniverse = getKeyUniverse(keyType);
171 vals = new Object[keyUniverse.length];
172 putAll(m);
173 }
174 }
175
176 // Query Operations
177
178 /**
179 * Returns the number of key-value mappings in this map.
180 *
181 * @return the number of key-value mappings in this map
182 */
183 public int size() {
184 return size;
185 }
186
187 /**
188 * Returns <tt>true</tt> if this map maps one or more keys to the
189 * specified value.
190 *
191 * @param value the value whose presence in this map is to be tested
192 * @return <tt>true</tt> if this map maps one or more keys to this value
193 */
194 public boolean containsValue(Object value) {
195 value = maskNull(value);
196
197 for (Object val : vals)
198 if (value.equals(val))
199 return true;
200
201 return false;
202 }
203
204 /**
205 * Returns <tt>true</tt> if this map contains a mapping for the specified
206 * key.
207 *
208 * @param key the key whose presence in this map is to be tested
209 * @return <tt>true</tt> if this map contains a mapping for the specified
210 * key
211 */
212 public boolean containsKey(Object key) {
213 return isValidKey(key) && vals[((Enum)key).ordinal()] != null;
214 }
215
216 private boolean containsMapping(Object key, Object value) {
217 return isValidKey(key) &&
218 maskNull(value).equals(vals[((Enum)key).ordinal()]);
219 }
220
221 /**
222 * Returns the value to which the specified key is mapped,
223 * or {@code null} if this map contains no mapping for the key.
224 *
225 * <p>More formally, if this map contains a mapping from a key
226 * {@code k} to a value {@code v} such that {@code (key == k)},
227 * then this method returns {@code v}; otherwise it returns
228 * {@code null}. (There can be at most one such mapping.)
229 *
230 * <p>A return value of {@code null} does not <i>necessarily</i>
231 * indicate that the map contains no mapping for the key; it's also
232 * possible that the map explicitly maps the key to {@code null}.
233 * The {@link #containsKey containsKey} operation may be used to
234 * distinguish these two cases.
235 */
236 public V get(Object key) {
237 return (isValidKey(key) ?
238 unmaskNull(vals[((Enum)key).ordinal()]) : null);
239 }
240
241 // Modification Operations
242
243 /**
244 * Associates the specified value with the specified key in this map.
245 * If the map previously contained a mapping for this key, the old
246 * value is replaced.
247 *
248 * @param key the key with which the specified value is to be associated
249 * @param value the value to be associated with the specified key
250 *
251 * @return the previous value associated with specified key, or
252 * <tt>null</tt> if there was no mapping for key. (A <tt>null</tt>
253 * return can also indicate that the map previously associated
254 * <tt>null</tt> with the specified key.)
255 * @throws NullPointerException if the specified key is null
256 */
257 public V put(K key, V value) {
258 typeCheck(key);
259
260 int index = key.ordinal();
261 Object oldValue = vals[index];
262 vals[index] = maskNull(value);
263 if (oldValue == null)
264 size++;
265 return unmaskNull(oldValue);
266 }
267
268 /**
269 * Removes the mapping for this key from this map if present.
270 *
271 * @param key the key whose mapping is to be removed from the map
272 * @return the previous value associated with specified key, or
273 * <tt>null</tt> if there was no entry for key. (A <tt>null</tt>
274 * return can also indicate that the map previously associated
275 * <tt>null</tt> with the specified key.)
276 */
277 public V remove(Object key) {
278 if (!isValidKey(key))
279 return null;
280 int index = ((Enum)key).ordinal();
281 Object oldValue = vals[index];
282 vals[index] = null;
283 if (oldValue != null)
284 size--;
285 return unmaskNull(oldValue);
286 }
287
288 private boolean removeMapping(Object key, Object value) {
289 if (!isValidKey(key))
290 return false;
291 int index = ((Enum)key).ordinal();
292 if (maskNull(value).equals(vals[index])) {
293 vals[index] = null;
294 size--;
295 return true;
296 }
297 return false;
298 }
299
300 /**
301 * Returns true if key is of the proper type to be a key in this
302 * enum map.
303 */
304 private boolean isValidKey(Object key) {
305 if (key == null)
306 return false;
307
308 // Cheaper than instanceof Enum followed by getDeclaringClass
309 Class keyClass = key.getClass();
310 return keyClass == keyType || keyClass.getSuperclass() == keyType;
311 }
312
313 // Bulk Operations
314
315 /**
316 * Copies all of the mappings from the specified map to this map.
317 * These mappings will replace any mappings that this map had for
318 * any of the keys currently in the specified map.
319 *
320 * @param m the mappings to be stored in this map
321 * @throws NullPointerException the specified map is null, or if
322 * one or more keys in the specified map are null
323 */
324 public void putAll(Map<? extends K, ? extends V> m) {
325 if (m instanceof EnumMap) {
326 EnumMap<? extends K, ? extends V> em =
327 (EnumMap<? extends K, ? extends V>)m;
328 if (em.keyType != keyType) {
329 if (em.isEmpty())
330 return;
331 throw new ClassCastException(em.keyType + " != " + keyType);
332 }
333
334 for (int i = 0; i < keyUniverse.length; i++) {
335 Object emValue = em.vals[i];
336 if (emValue != null) {
337 if (vals[i] == null)
338 size++;
339 vals[i] = emValue;
340 }
341 }
342 } else {
343 super.putAll(m);
344 }
345 }
346
347 /**
348 * Removes all mappings from this map.
349 */
350 public void clear() {
351 Arrays.fill(vals, null);
352 size = 0;
353 }
354
355 // Views
356
357 /**
358 * This field is initialized to contain an instance of the entry set
359 * view the first time this view is requested. The view is stateless,
360 * so there's no reason to create more than one.
361 */
362 private transient Set<Map.Entry<K,V>> entrySet = null;
363
364 /**
365 * Returns a {@link Set} view of the keys contained in this map.
366 * The returned set obeys the general contract outlined in
367 * {@link Map#keySet()}. The set's iterator will return the keys
368 * in their natural order (the order in which the enum constants
369 * are declared).
370 *
371 * @return a set view of the keys contained in this enum map
372 */
373 public Set<K> keySet() {
374 Set<K> ks = keySet;
375 if (ks != null)
376 return ks;
377 else
378 return keySet = new KeySet();
379 }
380
381 private class KeySet extends AbstractSet<K> {
382 public Iterator<K> iterator() {
383 return new KeyIterator();
384 }
385 public int size() {
386 return size;
387 }
388 public boolean contains(Object o) {
389 return containsKey(o);
390 }
391 public boolean remove(Object o) {
392 int oldSize = size;
393 EnumMap.this.remove(o);
394 return size != oldSize;
395 }
396 public void clear() {
397 EnumMap.this.clear();
398 }
399 }
400
401 /**
402 * Returns a {@link Collection} view of the values contained in this map.
403 * The returned collection obeys the general contract outlined in
404 * {@link Map#values()}. The collection's iterator will return the
405 * values in the order their corresponding keys appear in map,
406 * which is their natural order (the order in which the enum constants
407 * are declared).
408 *
409 * @return a collection view of the values contained in this map
410 */
411 public Collection<V> values() {
412 Collection<V> vs = values;
413 if (vs != null)
414 return vs;
415 else
416 return values = new Values();
417 }
418
419 private class Values extends AbstractCollection<V> {
420 public Iterator<V> iterator() {
421 return new ValueIterator();
422 }
423 public int size() {
424 return size;
425 }
426 public boolean contains(Object o) {
427 return containsValue(o);
428 }
429 public boolean remove(Object o) {
430 o = maskNull(o);
431
432 for (int i = 0; i < vals.length; i++) {
433 if (o.equals(vals[i])) {
434 vals[i] = null;
435 size--;
436 return true;
437 }
438 }
439 return false;
440 }
441 public void clear() {
442 EnumMap.this.clear();
443 }
444 }
445
446 /**
447 * Returns a {@link Set} view of the mappings contained in this map.
448 * The returned set obeys the general contract outlined in
449 * {@link Map#keySet()}. The set's iterator will return the
450 * mappings in the order their keys appear in map, which is their
451 * natural order (the order in which the enum constants are declared).
452 *
453 * @return a set view of the mappings contained in this enum map
454 */
455 public Set<Map.Entry<K,V>> entrySet() {
456 Set<Map.Entry<K,V>> es = entrySet;
457 if (es != null)
458 return es;
459 else
460 return entrySet = new EntrySet();
461 }
462
463 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
464 public Iterator<Map.Entry<K,V>> iterator() {
465 return new EntryIterator();
466 }
467
468 public boolean contains(Object o) {
469 if (!(o instanceof Map.Entry))
470 return false;
471 Map.Entry entry = (Map.Entry)o;
472 return containsMapping(entry.getKey(), entry.getValue());
473 }
474 public boolean remove(Object o) {
475 if (!(o instanceof Map.Entry))
476 return false;
477 Map.Entry entry = (Map.Entry)o;
478 return removeMapping(entry.getKey(), entry.getValue());
479 }
480 public int size() {
481 return size;
482 }
483 public void clear() {
484 EnumMap.this.clear();
485 }
486 public Object[] toArray() {
487 return fillEntryArray(new Object[size]);
488 }
489 @SuppressWarnings("unchecked")
490 public <T> T[] toArray(T[] a) {
491 int size = size();
492 if (a.length < size)
493 a = (T[])java.lang.reflect.Array
494 .newInstance(a.getClass().getComponentType(), size);
495 if (a.length > size)
496 a[size] = null;
497 return (T[]) fillEntryArray(a);
498 }
499 private Object[] fillEntryArray(Object[] a) {
500 int j = 0;
501 for (int i = 0; i < vals.length; i++)
502 if (vals[i] != null)
503 a[j++] = new AbstractMap.SimpleEntry<>(
504 keyUniverse[i], unmaskNull(vals[i]));
505 return a;
506 }
507 }
508
509 private abstract class EnumMapIterator<T> implements Iterator<T> {
510 // Lower bound on index of next element to return
511 int index = 0;
512
513 // Index of last returned element, or -1 if none
514 int lastReturnedIndex = -1;
515
516 public boolean hasNext() {
517 while (index < vals.length && vals[index] == null)
518 index++;
519 return index != vals.length;
520 }
521
522 public void remove() {
523 checkLastReturnedIndex();
524
525 if (vals[lastReturnedIndex] != null) {
526 vals[lastReturnedIndex] = null;
527 size--;
528 }
529 lastReturnedIndex = -1;
530 }
531
532 private void checkLastReturnedIndex() {
533 if (lastReturnedIndex < 0)
534 throw new IllegalStateException();
535 }
536 }
537
538 private class KeyIterator extends EnumMapIterator<K> {
539 public K next() {
540 if (!hasNext())
541 throw new NoSuchElementException();
542 lastReturnedIndex = index++;
543 return keyUniverse[lastReturnedIndex];
544 }
545 }
546
547 private class ValueIterator extends EnumMapIterator<V> {
548 public V next() {
549 if (!hasNext())
550 throw new NoSuchElementException();
551 lastReturnedIndex = index++;
552 return unmaskNull(vals[lastReturnedIndex]);
553 }
554 }
555
556 private class EntryIterator extends EnumMapIterator<Map.Entry<K,V>> {
557 private Entry lastReturnedEntry = null;
558
559 public Map.Entry<K,V> next() {
560 if (!hasNext())
561 throw new NoSuchElementException();
562 lastReturnedEntry = new Entry(index++);
563 return lastReturnedEntry;
564 }
565
566 public void remove() {
567 lastReturnedIndex =
568 ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
569 super.remove();
570 lastReturnedEntry.index = lastReturnedIndex;
571 lastReturnedEntry = null;
572 }
573
574 private class Entry implements Map.Entry<K,V> {
575 private int index;
576
577 private Entry(int index) {
578 this.index = index;
579 }
580
581 public K getKey() {
582 checkIndexForEntryUse();
583 return keyUniverse[index];
584 }
585
586 public V getValue() {
587 checkIndexForEntryUse();
588 return unmaskNull(vals[index]);
589 }
590
591 public V setValue(V value) {
592 checkIndexForEntryUse();
593 V oldValue = unmaskNull(vals[index]);
594 vals[index] = maskNull(value);
595 return oldValue;
596 }
597
598 public boolean equals(Object o) {
599 if (index < 0)
600 return o == this;
601
602 if (!(o instanceof Map.Entry))
603 return false;
604
605 Map.Entry e = (Map.Entry)o;
606 V ourValue = unmaskNull(vals[index]);
607 Object hisValue = e.getValue();
608 return (e.getKey() == keyUniverse[index] &&
609 (ourValue == hisValue ||
610 (ourValue != null && ourValue.equals(hisValue))));
611 }
612
613 public int hashCode() {
614 if (index < 0)
615 return super.hashCode();
616
617 return entryHashCode(index);
618 }
619
620 public String toString() {
621 if (index < 0)
622 return super.toString();
623
624 return keyUniverse[index] + "="
625 + unmaskNull(vals[index]);
626 }
627
628 private void checkIndexForEntryUse() {
629 if (index < 0)
630 throw new IllegalStateException("Entry was removed");
631 }
632 }
633 }
634
635 // Comparison and hashing
636
637 /**
638 * Compares the specified object with this map for equality. Returns
639 * <tt>true</tt> if the given object is also a map and the two maps
640 * represent the same mappings, as specified in the {@link
641 * Map#equals(Object)} contract.
642 *
643 * @param o the object to be compared for equality with this map
644 * @return <tt>true</tt> if the specified object is equal to this map
645 */
646 public boolean equals(Object o) {
647 if (this == o)
648 return true;
649 if (o instanceof EnumMap)
650 return equals((EnumMap)o);
651 if (!(o instanceof Map))
652 return false;
653
654 Map<K,V> m = (Map<K,V>)o;
655 if (size != m.size())
656 return false;
657
658 for (int i = 0; i < keyUniverse.length; i++) {
659 if (null != vals[i]) {
660 K key = keyUniverse[i];
661 V value = unmaskNull(vals[i]);
662 if (null == value) {
663 if (!((null == m.get(key)) && m.containsKey(key)))
664 return false;
665 } else {
666 if (!value.equals(m.get(key)))
667 return false;
668 }
669 }
670 }
671
672 return true;
673 }
674
675 private boolean equals(EnumMap em) {
676 if (em.keyType != keyType)
677 return size == 0 && em.size == 0;
678
679 // Key types match, compare each value
680 for (int i = 0; i < keyUniverse.length; i++) {
681 Object ourValue = vals[i];
682 Object hisValue = em.vals[i];
683 if (hisValue != ourValue &&
684 (hisValue == null || !hisValue.equals(ourValue)))
685 return false;
686 }
687 return true;
688 }
689
690 /**
691 * Returns the hash code value for this map. The hash code of a map is
692 * defined to be the sum of the hash codes of each entry in the map.
693 */
694 public int hashCode() {
695 int h = 0;
696
697 for (int i = 0; i < keyUniverse.length; i++) {
698 if (null != vals[i]) {
699 h += entryHashCode(i);
700 }
701 }
702
703 return h;
704 }
705
706 private int entryHashCode(int index) {
707 return (keyUniverse[index].hashCode() ^ vals[index].hashCode());
708 }
709
710 /**
711 * Returns a shallow copy of this enum map. (The values themselves
712 * are not cloned.
713 *
714 * @return a shallow copy of this enum map
715 */
716 public EnumMap<K, V> clone() {
717 EnumMap<K, V> result = null;
718 try {
719 result = (EnumMap<K, V>) super.clone();
720 } catch(CloneNotSupportedException e) {
721 throw new AssertionError();
722 }
723 result.vals = result.vals.clone();
724 return result;
725 }
726
727 /**
728 * Throws an exception if e is not of the correct type for this enum set.
729 */
730 private void typeCheck(K key) {
731 Class keyClass = key.getClass();
732 if (keyClass != keyType && keyClass.getSuperclass() != keyType)
733 throw new ClassCastException(keyClass + " != " + keyType);
734 }
735
736 /**
737 * Returns all of the values comprising K.
738 * The result is uncloned, cached, and shared by all callers.
739 */
740 private static <K extends Enum<K>> K[] getKeyUniverse(Class<K> keyType) {
741 return SharedSecrets.getJavaLangAccess()
742 .getEnumConstantsShared(keyType);
743 }
744
745 private static final long serialVersionUID = 458661240069192865L;
746
747 /**
748 * Save the state of the <tt>EnumMap</tt> instance to a stream (i.e.,
749 * serialize it).
750 *
751 * @serialData The <i>size</i> of the enum map (the number of key-value
752 * mappings) is emitted (int), followed by the key (Object)
753 * and value (Object) for each key-value mapping represented
754 * by the enum map.
755 */
756 private void writeObject(java.io.ObjectOutputStream s)
757 throws java.io.IOException
758 {
759 // Write out the key type and any hidden stuff
760 s.defaultWriteObject();
761
762 // Write out size (number of Mappings)
763 s.writeInt(size);
764
765 // Write out keys and values (alternating)
766 int entriesToBeWritten = size;
767 for (int i = 0; entriesToBeWritten > 0; i++) {
768 if (null != vals[i]) {
769 s.writeObject(keyUniverse[i]);
770 s.writeObject(unmaskNull(vals[i]));
771 entriesToBeWritten--;
772 }
773 }
774 }
775
776 /**
777 * Reconstitute the <tt>EnumMap</tt> instance from a stream (i.e.,
778 * deserialize it).
779 */
780 private void readObject(java.io.ObjectInputStream s)
781 throws java.io.IOException, ClassNotFoundException
782 {
783 // Read in the key type and any hidden stuff
784 s.defaultReadObject();
785
786 keyUniverse = getKeyUniverse(keyType);
787 vals = new Object[keyUniverse.length];
788
789 // Read in size (number of Mappings)
790 int size = s.readInt();
791
792 // Read the keys and values, and put the mappings in the HashMap
793 for (int i = 0; i < size; i++) {
794 K key = (K) s.readObject();
795 V value = (V) s.readObject();
796 put(key, value);
797 }
798 }
799 }