001 /*
002 * Copyright 2003-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package java.util;
027
028 import java.util.Map.Entry;
029 import sun.misc.SharedSecrets;
030
031 /**
032 * A specialized {@link Map} implementation for use with enum type keys. All
033 * of the keys in an enum map must come from a single enum type that is
034 * specified, explicitly or implicitly, when the map is created. Enum maps
035 * are represented internally as arrays. This representation is extremely
036 * compact and efficient.
037 *
038 * <p>Enum maps are maintained in the <i>natural order</i> of their keys
039 * (the order in which the enum constants are declared). This is reflected
040 * in the iterators returned by the collections views ({@link #keySet()},
041 * {@link #entrySet()}, and {@link #values()}).
042 *
043 * <p>Iterators returned by the collection views are <i>weakly consistent</i>:
044 * they will never throw {@link ConcurrentModificationException} and they may
045 * or may not show the effects of any modifications to the map that occur while
046 * the iteration is in progress.
047 *
048 * <p>Null keys are not permitted. Attempts to insert a null key will
049 * throw {@link NullPointerException}. Attempts to test for the
050 * presence of a null key or to remove one will, however, function properly.
051 * Null values are permitted.
052
053 * <P>Like most collection implementations <tt>EnumMap</tt> is not
054 * synchronized. If multiple threads access an enum map concurrently, and at
055 * least one of the threads modifies the map, it should be synchronized
056 * externally. This is typically accomplished by synchronizing on some
057 * object that naturally encapsulates the enum map. If no such object exists,
058 * the map should be "wrapped" using the {@link Collections#synchronizedMap}
059 * method. This is best done at creation time, to prevent accidental
060 * unsynchronized access:
061 *
062 * <pre>
063 * Map<EnumKey, V> m
064 * = Collections.synchronizedMap(new EnumMap<EnumKey, V>(...));
065 * </pre>
066 *
067 * <p>Implementation note: All basic operations execute in constant time.
068 * They are likely (though not guaranteed) to be faster than their
069 * {@link HashMap} counterparts.
070 *
071 * <p>This class is a member of the
072 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
073 * Java Collections Framework</a>.
074 *
075 * @author Josh Bloch
076 * @version 1.22, 05/05/07
077 * @see EnumSet
078 * @since 1.5
079 */
080 public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
081 implements java.io.Serializable, Cloneable {
082 /**
083 * The <tt>Class</tt> object for the enum type of all the keys of this map.
084 *
085 * @serial
086 */
087 private final Class<K> keyType;
088
089 /**
090 * All of the values comprising K. (Cached for performance.)
091 */
092 private transient K[] keyUniverse;
093
094 /**
095 * Array representation of this map. The ith element is the value
096 * to which universe[i] is currently mapped, or null if it isn't
097 * mapped to anything, or NULL if it's mapped to null.
098 */
099 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 Object();
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 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 = (Object[]) 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 = (Object[]) em.vals.clone();
165 size = em.size;
166 } else {
167 if (m.isEmpty())
168 throw new IllegalArgumentException(
169 "Specified map is empty");
170 keyType = m.keySet().iterator().next().getDeclaringClass();
171 keyUniverse = getKeyUniverse(keyType);
172 vals = new Object[keyUniverse.length];
173 putAll(m);
174 }
175 }
176
177 // Query Operations
178
179 /**
180 * Returns the number of key-value mappings in this map.
181 *
182 * @return the number of key-value mappings in this map
183 */
184 public int size() {
185 return size;
186 }
187
188 /**
189 * Returns <tt>true</tt> if this map maps one or more keys to the
190 * specified value.
191 *
192 * @param value the value whose presence in this map is to be tested
193 * @return <tt>true</tt> if this map maps one or more keys to this value
194 */
195 public boolean containsValue(Object value) {
196 value = maskNull(value);
197
198 for (Object val : vals)
199 if (value.equals(val))
200 return true;
201
202 return false;
203 }
204
205 /**
206 * Returns <tt>true</tt> if this map contains a mapping for the specified
207 * key.
208 *
209 * @param key the key whose presence in this map is to be tested
210 * @return <tt>true</tt> if this map contains a mapping for the specified
211 * key
212 */
213 public boolean containsKey(Object key) {
214 return isValidKey(key) && vals[((Enum) key).ordinal()] != null;
215 }
216
217 private boolean containsMapping(Object key, Object value) {
218 return isValidKey(key)
219 && maskNull(value).equals(vals[((Enum) key).ordinal()]);
220 }
221
222 /**
223 * Returns the value to which the specified key is mapped,
224 * or {@code null} if this map contains no mapping for the key.
225 *
226 * <p>More formally, if this map contains a mapping from a key
227 * {@code k} to a value {@code v} such that {@code (key == k)},
228 * then this method returns {@code v}; otherwise it returns
229 * {@code null}. (There can be at most one such mapping.)
230 *
231 * <p>A return value of {@code null} does not <i>necessarily</i>
232 * indicate that the map contains no mapping for the key; it's also
233 * possible that the map explicitly maps the key to {@code null}.
234 * The {@link #containsKey containsKey} operation may be used to
235 * distinguish these two cases.
236 */
237 public V get(Object key) {
238 return (isValidKey(key) ? unmaskNull(vals[((Enum) key)
239 .ordinal()]) : null);
240 }
241
242 // Modification Operations
243
244 /**
245 * Associates the specified value with the specified key in this map.
246 * If the map previously contained a mapping for this key, the old
247 * value is replaced.
248 *
249 * @param key the key with which the specified value is to be associated
250 * @param value the value to be associated with the specified key
251 *
252 * @return the previous value associated with specified key, or
253 * <tt>null</tt> if there was no mapping for key. (A <tt>null</tt>
254 * return can also indicate that the map previously associated
255 * <tt>null</tt> with the specified key.)
256 * @throws NullPointerException if the specified key is null
257 */
258 public V put(K key, V value) {
259 typeCheck(key);
260
261 int index = ((Enum) key).ordinal();
262 Object oldValue = vals[index];
263 vals[index] = maskNull(value);
264 if (oldValue == null)
265 size++;
266 return unmaskNull(oldValue);
267 }
268
269 /**
270 * Removes the mapping for this key from this map if present.
271 *
272 * @param key the key whose mapping is to be removed from the map
273 * @return the previous value associated with specified key, or
274 * <tt>null</tt> if there was no entry for key. (A <tt>null</tt>
275 * return can also indicate that the map previously associated
276 * <tt>null</tt> with the specified key.)
277 */
278 public V remove(Object key) {
279 if (!isValidKey(key))
280 return null;
281 int index = ((Enum) key).ordinal();
282 Object oldValue = vals[index];
283 vals[index] = null;
284 if (oldValue != null)
285 size--;
286 return unmaskNull(oldValue);
287 }
288
289 private boolean removeMapping(Object key, Object value) {
290 if (!isValidKey(key))
291 return false;
292 int index = ((Enum) key).ordinal();
293 if (maskNull(value).equals(vals[index])) {
294 vals[index] = null;
295 size--;
296 return true;
297 }
298 return false;
299 }
300
301 /**
302 * Returns true if key is of the proper type to be a key in this
303 * enum map.
304 */
305 private boolean isValidKey(Object key) {
306 if (key == null)
307 return false;
308
309 // Cheaper than instanceof Enum followed by getDeclaringClass
310 Class keyClass = key.getClass();
311 return keyClass == keyType
312 || keyClass.getSuperclass() == keyType;
313 }
314
315 // Bulk Operations
316
317 /**
318 * Copies all of the mappings from the specified map to this map.
319 * These mappings will replace any mappings that this map had for
320 * any of the keys currently in the specified map.
321 *
322 * @param m the mappings to be stored in this map
323 * @throws NullPointerException the specified map is null, or if
324 * one or more keys in the specified map are null
325 */
326 public void putAll(Map<? extends K, ? extends V> m) {
327 if (m instanceof EnumMap) {
328 EnumMap<? extends K, ? extends V> em = (EnumMap<? extends K, ? extends V>) m;
329 if (em.keyType != keyType) {
330 if (em.isEmpty())
331 return;
332 throw new ClassCastException(em.keyType + " != "
333 + keyType);
334 }
335
336 for (int i = 0; i < keyUniverse.length; i++) {
337 Object emValue = em.vals[i];
338 if (emValue != null) {
339 if (vals[i] == null)
340 size++;
341 vals[i] = emValue;
342 }
343 }
344 } else {
345 super .putAll(m);
346 }
347 }
348
349 /**
350 * Removes all mappings from this map.
351 */
352 public void clear() {
353 Arrays.fill(vals, null);
354 size = 0;
355 }
356
357 // Views
358
359 /**
360 * This field is initialized to contain an instance of the entry set
361 * view the first time this view is requested. The view is stateless,
362 * so there's no reason to create more than one.
363 */
364 private transient Set<Map.Entry<K, V>> entrySet = null;
365
366 /**
367 * Returns a {@link Set} view of the keys contained in this map.
368 * The returned set obeys the general contract outlined in
369 * {@link Map#keySet()}. The set's iterator will return the keys
370 * in their natural order (the order in which the enum constants
371 * are declared).
372 *
373 * @return a set view of the keys contained in this enum map
374 */
375 public Set<K> keySet() {
376 Set<K> ks = keySet;
377 if (ks != null)
378 return ks;
379 else
380 return keySet = new KeySet();
381 }
382
383 private class KeySet extends AbstractSet<K> {
384 public Iterator<K> iterator() {
385 return new KeyIterator();
386 }
387
388 public int size() {
389 return size;
390 }
391
392 public boolean contains(Object o) {
393 return containsKey(o);
394 }
395
396 public boolean remove(Object o) {
397 int oldSize = size;
398 EnumMap.this .remove(o);
399 return size != oldSize;
400 }
401
402 public void clear() {
403 EnumMap.this .clear();
404 }
405 }
406
407 /**
408 * Returns a {@link Collection} view of the values contained in this map.
409 * The returned collection obeys the general contract outlined in
410 * {@link Map#values()}. The collection's iterator will return the
411 * values in the order their corresponding keys appear in map,
412 * which is their natural order (the order in which the enum constants
413 * are declared).
414 *
415 * @return a collection view of the values contained in this map
416 */
417 public Collection<V> values() {
418 Collection<V> vs = values;
419 if (vs != null)
420 return vs;
421 else
422 return values = new Values();
423 }
424
425 private class Values extends AbstractCollection<V> {
426 public Iterator<V> iterator() {
427 return new ValueIterator();
428 }
429
430 public int size() {
431 return size;
432 }
433
434 public boolean contains(Object o) {
435 return containsValue(o);
436 }
437
438 public boolean remove(Object o) {
439 o = maskNull(o);
440
441 for (int i = 0; i < vals.length; i++) {
442 if (o.equals(vals[i])) {
443 vals[i] = null;
444 size--;
445 return true;
446 }
447 }
448 return false;
449 }
450
451 public void clear() {
452 EnumMap.this .clear();
453 }
454 }
455
456 /**
457 * Returns a {@link Set} view of the mappings contained in this map.
458 * The returned set obeys the general contract outlined in
459 * {@link Map#keySet()}. The set's iterator will return the
460 * mappings in the order their keys appear in map, which is their
461 * natural order (the order in which the enum constants are declared).
462 *
463 * @return a set view of the mappings contained in this enum map
464 */
465 public Set<Map.Entry<K, V>> entrySet() {
466 Set<Map.Entry<K, V>> es = entrySet;
467 if (es != null)
468 return es;
469 else
470 return entrySet = new EntrySet();
471 }
472
473 private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
474 public Iterator<Map.Entry<K, V>> iterator() {
475 return new EntryIterator();
476 }
477
478 public boolean contains(Object o) {
479 if (!(o instanceof Map.Entry))
480 return false;
481 Map.Entry entry = (Map.Entry) o;
482 return containsMapping(entry.getKey(), entry.getValue());
483 }
484
485 public boolean remove(Object o) {
486 if (!(o instanceof Map.Entry))
487 return false;
488 Map.Entry entry = (Map.Entry) o;
489 return removeMapping(entry.getKey(), entry.getValue());
490 }
491
492 public int size() {
493 return size;
494 }
495
496 public void clear() {
497 EnumMap.this .clear();
498 }
499
500 public Object[] toArray() {
501 return fillEntryArray(new Object[size]);
502 }
503
504 @SuppressWarnings("unchecked")
505 public <T> T[] toArray(T[] a) {
506 int size = size();
507 if (a.length < size)
508 a = (T[]) java.lang.reflect.Array.newInstance(a
509 .getClass().getComponentType(), size);
510 if (a.length > size)
511 a[size] = null;
512 return (T[]) fillEntryArray(a);
513 }
514
515 private Object[] fillEntryArray(Object[] a) {
516 int j = 0;
517 for (int i = 0; i < vals.length; i++)
518 if (vals[i] != null)
519 a[j++] = new AbstractMap.SimpleEntry<K, V>(
520 keyUniverse[i], unmaskNull(vals[i]));
521 return a;
522 }
523 }
524
525 private abstract class EnumMapIterator<T> implements Iterator<T> {
526 // Lower bound on index of next element to return
527 int index = 0;
528
529 // Index of last returned element, or -1 if none
530 int lastReturnedIndex = -1;
531
532 public boolean hasNext() {
533 while (index < vals.length && vals[index] == null)
534 index++;
535 return index != vals.length;
536 }
537
538 public void remove() {
539 checkLastReturnedIndex();
540
541 if (vals[lastReturnedIndex] != null) {
542 vals[lastReturnedIndex] = null;
543 size--;
544 }
545 lastReturnedIndex = -1;
546 }
547
548 private void checkLastReturnedIndex() {
549 if (lastReturnedIndex < 0)
550 throw new IllegalStateException();
551 }
552 }
553
554 private class KeyIterator extends EnumMapIterator<K> {
555 public K next() {
556 if (!hasNext())
557 throw new NoSuchElementException();
558 lastReturnedIndex = index++;
559 return keyUniverse[lastReturnedIndex];
560 }
561 }
562
563 private class ValueIterator extends EnumMapIterator<V> {
564 public V next() {
565 if (!hasNext())
566 throw new NoSuchElementException();
567 lastReturnedIndex = index++;
568 return unmaskNull(vals[lastReturnedIndex]);
569 }
570 }
571
572 /**
573 * Since we don't use Entry objects, we use the Iterator itself as entry.
574 */
575 private class EntryIterator extends
576 EnumMapIterator<Map.Entry<K, V>> implements Map.Entry<K, V> {
577 public Map.Entry<K, V> next() {
578 if (!hasNext())
579 throw new NoSuchElementException();
580 lastReturnedIndex = index++;
581 return this ;
582 }
583
584 public K getKey() {
585 checkLastReturnedIndexForEntryUse();
586 return keyUniverse[lastReturnedIndex];
587 }
588
589 public V getValue() {
590 checkLastReturnedIndexForEntryUse();
591 return unmaskNull(vals[lastReturnedIndex]);
592 }
593
594 public V setValue(V value) {
595 checkLastReturnedIndexForEntryUse();
596 V oldValue = unmaskNull(vals[lastReturnedIndex]);
597 vals[lastReturnedIndex] = maskNull(value);
598 return oldValue;
599 }
600
601 public boolean equals(Object o) {
602 if (lastReturnedIndex < 0)
603 return o == this ;
604
605 if (!(o instanceof Map.Entry))
606 return false;
607 Map.Entry e = (Map.Entry) o;
608 V ourValue = unmaskNull(vals[lastReturnedIndex]);
609 Object hisValue = e.getValue();
610 return e.getKey() == keyUniverse[lastReturnedIndex]
611 && (ourValue == hisValue || (ourValue != null && ourValue
612 .equals(hisValue)));
613 }
614
615 public int hashCode() {
616 if (lastReturnedIndex < 0)
617 return super .hashCode();
618
619 Object value = vals[lastReturnedIndex];
620 return keyUniverse[lastReturnedIndex].hashCode()
621 ^ (value == NULL ? 0 : value.hashCode());
622 }
623
624 public String toString() {
625 if (lastReturnedIndex < 0)
626 return super .toString();
627
628 return keyUniverse[lastReturnedIndex] + "="
629 + unmaskNull(vals[lastReturnedIndex]);
630 }
631
632 private void checkLastReturnedIndexForEntryUse() {
633 if (lastReturnedIndex < 0)
634 throw new IllegalStateException("Entry was removed");
635 }
636 }
637
638 // Comparison and hashing
639
640 /**
641 * Compares the specified object with this map for equality. Returns
642 * <tt>true</tt> if the given object is also a map and the two maps
643 * represent the same mappings, as specified in the {@link
644 * Map#equals(Object)} contract.
645 *
646 * @param o the object to be compared for equality with this map
647 * @return <tt>true</tt> if the specified object is equal to this map
648 */
649 public boolean equals(Object o) {
650 if (!(o instanceof EnumMap))
651 return super .equals(o);
652
653 EnumMap em = (EnumMap) o;
654 if (em.keyType != keyType)
655 return size == 0 && em.size == 0;
656
657 // Key types match, compare each value
658 for (int i = 0; i < keyUniverse.length; i++) {
659 Object ourValue = vals[i];
660 Object hisValue = em.vals[i];
661 if (hisValue != ourValue
662 && (hisValue == null || !hisValue.equals(ourValue)))
663 return false;
664 }
665 return true;
666 }
667
668 /**
669 * Returns a shallow copy of this enum map. (The values themselves
670 * are not cloned.
671 *
672 * @return a shallow copy of this enum map
673 */
674 public EnumMap<K, V> clone() {
675 EnumMap<K, V> result = null;
676 try {
677 result = (EnumMap<K, V>) super .clone();
678 } catch (CloneNotSupportedException e) {
679 throw new AssertionError();
680 }
681 result.vals = (Object[]) result.vals.clone();
682 return result;
683 }
684
685 /**
686 * Throws an exception if e is not of the correct type for this enum set.
687 */
688 private void typeCheck(K key) {
689 Class keyClass = key.getClass();
690 if (keyClass != keyType && keyClass.getSuperclass() != keyType)
691 throw new ClassCastException(keyClass + " != " + keyType);
692 }
693
694 /**
695 * Returns all of the values comprising K.
696 * The result is uncloned, cached, and shared by all callers.
697 */
698 private static <K extends Enum<K>> K[] getKeyUniverse(
699 Class<K> keyType) {
700 return SharedSecrets.getJavaLangAccess()
701 .getEnumConstantsShared(keyType);
702 }
703
704 private static final long serialVersionUID = 458661240069192865L;
705
706 /**
707 * Save the state of the <tt>EnumMap</tt> instance to a stream (i.e.,
708 * serialize it).
709 *
710 * @serialData The <i>size</i> of the enum map (the number of key-value
711 * mappings) is emitted (int), followed by the key (Object)
712 * and value (Object) for each key-value mapping represented
713 * by the enum map.
714 */
715 private void writeObject(java.io.ObjectOutputStream s)
716 throws java.io.IOException {
717 // Write out the key type and any hidden stuff
718 s.defaultWriteObject();
719
720 // Write out size (number of Mappings)
721 s.writeInt(size);
722
723 // Write out keys and values (alternating)
724 for (Map.Entry<K, V> e : entrySet()) {
725 s.writeObject(e.getKey());
726 s.writeObject(e.getValue());
727 }
728 }
729
730 /**
731 * Reconstitute the <tt>EnumMap</tt> instance from a stream (i.e.,
732 * deserialize it).
733 */
734 private void readObject(java.io.ObjectInputStream s)
735 throws java.io.IOException, ClassNotFoundException {
736 // Read in the key type and any hidden stuff
737 s.defaultReadObject();
738
739 keyUniverse = getKeyUniverse(keyType);
740 vals = new Object[keyUniverse.length];
741
742 // Read in size (number of Mappings)
743 int size = s.readInt();
744
745 // Read the keys and values, and put the mappings in the HashMap
746 for (int i = 0; i < size; i++) {
747 K key = (K) s.readObject();
748 V value = (V) s.readObject();
749 put(key, value);
750 }
751 }
752 }
|