1. /*
  2. * @(#)EnumMap.java 1.10 04/07/15
  3. *
  4. * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util;
  8. import java.util.Map.Entry;
  9. /**
  10. * A specialized {@link Map} implementation for use with enum type keys. All
  11. * of the keys in an enum map must come from a single enum type that is
  12. * specified, explicitly or implicitly, when the map is created. Enum maps
  13. * are represented internally as arrays. This representation is extremely
  14. * compact and efficient.
  15. *
  16. * <p>Enum maps are maintained in the <i>natural order</i> of their keys
  17. * (the order in which the enum constants are declared). This is reflected
  18. * in the iterators returned by the collections views ({@link #keySet()},
  19. * {@link #entrySet()}, and {@link #values()}).
  20. *
  21. * <p>Iterators returned by the collection views are <i>weakly consistent</i>:
  22. * they will never throw {@link ConcurrentModificationException} and they may
  23. * or may not show the effects of any modifications to the map that occur while
  24. * the iteration is in progress.
  25. *
  26. * <p>Null keys are not permitted. Attempts to insert a null key will
  27. * throw {@link NullPointerException}. Attempts to test for the
  28. * presence of a null key or to remove one will, however, function properly.
  29. * Null values are permitted.
  30. * <P>Like most collection implementations <tt>EnumMap</tt> is not
  31. * synchronized. If multiple threads access an enum map concurrently, and at
  32. * least one of the threads modifies the map, it should be synchronized
  33. * externally. This is typically accomplished by synchronizing on some
  34. * object that naturally encapsulates the enum map. If no such object exists,
  35. * the map should be "wrapped" using the {@link Collections#synchronizedMap}
  36. * method. This is best done at creation time, to prevent accidental
  37. * unsynchronized access:
  38. *
  39. * <pre>
  40. * Map<EnumKey, V> m = Collections.synchronizedMap(new EnumMap(...));
  41. * </pre>
  42. *
  43. * <p>Implementation note: All basic operations execute in constant time.
  44. * They are likely (though not guaranteed) to be faster than their
  45. * {@link HashMap} counterparts.
  46. *
  47. * <p>This class is a member of the
  48. * <a href="{@docRoot}/../guide/collections/index.html">
  49. * Java Collections Framework</a>.
  50. *
  51. * @author Josh Bloch
  52. * @version 1.10, 07/15/04
  53. * @see EnumSet
  54. * @since 1.5
  55. */
  56. public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
  57. implements java.io.Serializable, Cloneable
  58. {
  59. /**
  60. * The <tt>Class</tt> object for the enum type of all the keys of this map.
  61. *
  62. * @serial
  63. */
  64. private final Class<K> keyType;
  65. /**
  66. * All of the values comprising K. (Cached for performance.)
  67. */
  68. private transient K[] keyUniverse;
  69. /**
  70. * Array representation of this map. The ith element is the value
  71. * to which universe[i] is currently mapped, or null if it isn't
  72. * mapped to anything, or NULL if it's mapped to null.
  73. */
  74. private transient Object[] vals;
  75. /**
  76. * The number of mappings in this map.
  77. */
  78. private transient int size = 0;
  79. /**
  80. * Distinguished non-null value for representing null values.
  81. */
  82. private static final Object NULL = new Object();
  83. private Object maskNull(Object value) {
  84. return (value == null ? NULL : value);
  85. }
  86. private V unmaskNull(Object value) {
  87. return (V) (value == NULL ? null : value);
  88. }
  89. private static Enum[] ZERO_LENGTH_ENUM_ARRAY = new Enum[0];
  90. /**
  91. * Creates an empty enum map with the specified key type.
  92. *
  93. * @param keyType the class object of the key type for this enum map
  94. * @throws NullPointerException if <tt>keyType</tt> is null
  95. */
  96. public EnumMap(Class<K> keyType) {
  97. this.keyType = keyType;
  98. keyUniverse = keyType.getEnumConstants();
  99. vals = new Object[keyUniverse.length];
  100. }
  101. /**
  102. * Creates an enum map with the same key type as the specified enum
  103. * map, initially containing the same mappings (if any).
  104. *
  105. * @param m the enum map from which to initialize this enum map
  106. * @throws NullPointerException if <tt>m</tt> is null
  107. */
  108. public EnumMap(EnumMap<K, ? extends V> m) {
  109. keyType = m.keyType;
  110. keyUniverse = m.keyUniverse;
  111. vals = (Object[]) m.vals.clone();
  112. size = m.size;
  113. }
  114. /**
  115. * Creates an enum map initialized from the specified map. If the
  116. * specified map is an <tt>EnumMap</tt> instance, this constructor behaves
  117. * identically to {@link #EnumMap(EnumMap)}. Otherwise, the specified map
  118. * must contain at least one mapping (in order to determine the new
  119. * enum map's key type).
  120. *
  121. * @param m the map from which to initialize this enum map
  122. * @throws IllegalArgumentException if <tt>m</tt> is not an
  123. * <tt>EnumMap</tt> instance and contains no mappings
  124. * @throws NullPointerException if <tt>m</tt> is null
  125. */
  126. public EnumMap(Map<K, ? extends V> m) {
  127. if (m instanceof EnumMap) {
  128. EnumMap<K, ? extends V> em = (EnumMap<K, ? extends V>) m;
  129. keyType = em.keyType;
  130. keyUniverse = em.keyUniverse;
  131. vals = (Object[]) em.vals.clone();
  132. size = em.size;
  133. } else {
  134. if (m.isEmpty())
  135. throw new IllegalArgumentException("Specified map is empty");
  136. keyType = m.keySet().iterator().next().getDeclaringClass();
  137. keyUniverse = keyType.getEnumConstants();
  138. vals = new Object[keyUniverse.length];
  139. putAll(m);
  140. }
  141. }
  142. // Query Operations
  143. /**
  144. * Returns the number of key-value mappings in this map.
  145. *
  146. * @return the number of key-value mappings in this map
  147. */
  148. public int size() {
  149. return size;
  150. }
  151. /**
  152. * Returns <tt>true</tt> if this map maps one or more keys to the
  153. * specified value.
  154. *
  155. * @param value the value whose presence in this map is to be tested
  156. * @return <tt>true</tt> if this map maps one or more keys to this value
  157. */
  158. public boolean containsValue(Object value) {
  159. value = maskNull(value);
  160. for (Object val : vals)
  161. if (value.equals(val))
  162. return true;
  163. return false;
  164. }
  165. /**
  166. * Returns <tt>true</tt> if this map contains a mapping for the specified
  167. * key.
  168. *
  169. * @param key the key whose presence in this map is to be tested
  170. * @return <tt>true</tt> if this map contains a mapping for the specified
  171. * key
  172. */
  173. public boolean containsKey(Object key) {
  174. return isValidKey(key) && vals[((Enum)key).ordinal()] != null;
  175. }
  176. private boolean containsMapping(Object key, Object value) {
  177. return isValidKey(key) &&
  178. maskNull(value).equals(vals[((Enum)key).ordinal()]);
  179. }
  180. /**
  181. * Returns the value to which this map maps the specified key, or null
  182. * if this map contains no mapping for the specified key.
  183. *
  184. * @param key the key whose associated value is to be returned
  185. * @return the value to which this map maps the specified key, or null
  186. * if this map contains no mapping for the specified key
  187. */
  188. public V get(Object key) {
  189. return (isValidKey(key) ?
  190. unmaskNull(vals[((Enum)key).ordinal()]) : null);
  191. }
  192. // Modification Operations
  193. /**
  194. * Associates the specified value with the specified key in this map.
  195. * If the map previously contained a mapping for this key, the old
  196. * value is replaced.
  197. *
  198. * @param key the key with which the specified value is to be associated
  199. * @param value the value to be associated with the specified key
  200. *
  201. * @return the previous value associated with specified key, or
  202. * <tt>null</tt> if there was no mapping for key. (A <tt>null</tt>
  203. * return can also indicate that the map previously associated
  204. * <tt>null</tt> with the specified key.)
  205. * @throws NullPointerException if the specified key is null
  206. */
  207. public V put(K key, V value) {
  208. typeCheck(key);
  209. int index = ((Enum)key).ordinal();
  210. Object oldValue = vals[index];
  211. vals[index] = maskNull(value);
  212. if (oldValue == null)
  213. size++;
  214. return unmaskNull(oldValue);
  215. }
  216. /**
  217. * Removes the mapping for this key from this map if present.
  218. *
  219. * @param key the key whose mapping is to be removed from the map
  220. * @return the previous value associated with specified key, or
  221. * <tt>null</tt> if there was no entry for key. (A <tt>null</tt>
  222. * return can also indicate that the map previously associated
  223. * <tt>null</tt> with the specified key.)
  224. */
  225. public V remove(Object key) {
  226. if (!isValidKey(key))
  227. return null;
  228. int index = ((Enum)key).ordinal();
  229. Object oldValue = vals[index];
  230. vals[index] = null;
  231. if (oldValue != null)
  232. size--;
  233. return unmaskNull(oldValue);
  234. }
  235. private boolean removeMapping(Object key, Object value) {
  236. if (!isValidKey(key))
  237. return false;
  238. int index = ((Enum)key).ordinal();
  239. if (maskNull(value).equals(vals[index])) {
  240. vals[index] = null;
  241. size--;
  242. return true;
  243. }
  244. return false;
  245. }
  246. /**
  247. * Returns true if key is of the proper type to be a key in this
  248. * enum map.
  249. */
  250. private boolean isValidKey(Object key) {
  251. if (key == null)
  252. return false;
  253. // Cheaper than instanceof Enum followed by getDeclaringClass
  254. Class keyClass = key.getClass();
  255. return keyClass == keyType || keyClass.getSuperclass() == keyType;
  256. }
  257. // Bulk Operations
  258. /**
  259. * Copies all of the mappings from the specified map to this map.
  260. * These mappings will replace any mappings that this map had for
  261. * any of the keys currently in the specified map.
  262. *
  263. * @param m the mappings to be stored in this map
  264. * @throws NullPointerException the specified map is null, or if
  265. * one or more keys in the specified map are null
  266. */
  267. public void putAll(Map<? extends K, ? extends V> m) {
  268. if (m instanceof EnumMap) {
  269. EnumMap<? extends K, ? extends V> em =
  270. (EnumMap<? extends K, ? extends V>)m;
  271. if (em.keyType != keyType) {
  272. if (em.isEmpty())
  273. return;
  274. throw new ClassCastException(em.keyType + " != " + keyType);
  275. }
  276. for (int i = 0; i < keyUniverse.length; i++) {
  277. Object emValue = em.vals[i];
  278. if (emValue != null) {
  279. if (vals[i] == null)
  280. size++;
  281. vals[i] = emValue;
  282. }
  283. }
  284. } else {
  285. super.putAll(m);
  286. }
  287. }
  288. /**
  289. * Removes all mappings from this map.
  290. */
  291. public void clear() {
  292. Arrays.fill(vals, null);
  293. size = 0;
  294. }
  295. // Views
  296. /**
  297. * This field is initialized to contain an instance of the entry set
  298. * view the first time this view is requested. The view is stateless,
  299. * so there's no reason to create more than one.
  300. */
  301. private transient Set<Map.Entry<K,V>> entrySet = null;
  302. /**
  303. * Returns a {@link Set} view of the keys contained in this map.
  304. * The returned set obeys the general contract outlined in
  305. * {@link Map#keySet()}. The set's iterator will return the keys
  306. * in their natural order (the order in which the enum constants
  307. * are declared).
  308. *
  309. * @return a set view of the keys contained in this enum map
  310. */
  311. public Set<K> keySet() {
  312. Set<K> ks = keySet;
  313. if (ks != null)
  314. return ks;
  315. else
  316. return keySet = new KeySet();
  317. }
  318. private class KeySet extends AbstractSet<K> {
  319. public Iterator<K> iterator() {
  320. return new KeyIterator();
  321. }
  322. public int size() {
  323. return size;
  324. }
  325. public boolean contains(Object o) {
  326. return containsKey(o);
  327. }
  328. public boolean remove(Object o) {
  329. int oldSize = size;
  330. EnumMap.this.remove(o);
  331. return size != oldSize;
  332. }
  333. public void clear() {
  334. EnumMap.this.clear();
  335. }
  336. }
  337. /**
  338. * Returns a {@link Collection} view of the values contained in this map.
  339. * The returned collection obeys the general contract outlined in
  340. * {@link Map#values()}. The collection's iterator will return the
  341. * values in the order their corresponding keys appear in map,
  342. * which is their natural order (the order in which the enum constants
  343. * are declared).
  344. *
  345. * @return a collection view of the values contained in this map
  346. */
  347. public Collection<V> values() {
  348. Collection<V> vs = values;
  349. if (vs != null)
  350. return vs;
  351. else
  352. return values = new Values();
  353. }
  354. private class Values extends AbstractCollection<V> {
  355. public Iterator<V> iterator() {
  356. return new ValueIterator();
  357. }
  358. public int size() {
  359. return size;
  360. }
  361. public boolean contains(Object o) {
  362. return containsValue(o);
  363. }
  364. public boolean remove(Object o) {
  365. o = maskNull(o);
  366. for (int i = 0; i < vals.length; i++) {
  367. if (o.equals(vals[i])) {
  368. vals[i] = null;
  369. size--;
  370. return true;
  371. }
  372. }
  373. return false;
  374. }
  375. public void clear() {
  376. EnumMap.this.clear();
  377. }
  378. }
  379. /**
  380. * Returns a {@link Set} view of the mappings contained in this map.
  381. * The returned set obeys the general contract outlined in
  382. * {@link Map#keySet()}. The set's iterator will return the
  383. * mappings in the order their keys appear in map, which is their
  384. * natural order (the order in which the enum constants are declared).
  385. *
  386. * @return a set view of the mappings contained in this enum map
  387. */
  388. public Set<Map.Entry<K,V>> entrySet() {
  389. Set<Map.Entry<K,V>> es = entrySet;
  390. if (es != null)
  391. return es;
  392. else
  393. return entrySet = new EntrySet();
  394. }
  395. private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
  396. public Iterator<Map.Entry<K,V>> iterator() {
  397. return new EntryIterator();
  398. }
  399. public boolean contains(Object o) {
  400. if (!(o instanceof Map.Entry))
  401. return false;
  402. Map.Entry entry = (Map.Entry)o;
  403. return containsMapping(entry.getKey(), entry.getValue());
  404. }
  405. public boolean remove(Object o) {
  406. if (!(o instanceof Map.Entry))
  407. return false;
  408. Map.Entry entry = (Map.Entry)o;
  409. return removeMapping(entry.getKey(), entry.getValue());
  410. }
  411. public int size() {
  412. return size;
  413. }
  414. public void clear() {
  415. EnumMap.this.clear();
  416. }
  417. public Object[] toArray() {
  418. return fillEntryArray(new Object[size]);
  419. }
  420. public <T> T[] toArray(T[] a) {
  421. Object[] result = (Object[]) java.lang.reflect.Array.newInstance(
  422. a.getClass().getComponentType(), size);
  423. return (T[]) fillEntryArray(result);
  424. }
  425. private Object[] fillEntryArray(Object[] a) {
  426. int j = 0;
  427. for (int i = 0; i < vals.length; i++)
  428. if (vals[i] != null)
  429. a[j++] = new AbstractMap.SimpleEntry<K,V>(
  430. keyUniverse[i], unmaskNull(vals[i]));
  431. return a;
  432. }
  433. }
  434. private abstract class EnumMapIterator<T> implements Iterator<T> {
  435. // Lower bound on index of next element to return
  436. int index = 0;
  437. // Index of last returned element, or -1 if none
  438. int lastReturnedIndex = -1;
  439. public boolean hasNext() {
  440. while (index < vals.length && vals[index] == null)
  441. index++;
  442. return index != vals.length;
  443. }
  444. public void remove() {
  445. checkLastReturnedIndex();
  446. if (vals[lastReturnedIndex] != null) {
  447. vals[lastReturnedIndex] = null;
  448. size--;
  449. }
  450. lastReturnedIndex = -1;
  451. }
  452. private void checkLastReturnedIndex() {
  453. if (lastReturnedIndex < 0)
  454. throw new IllegalStateException();
  455. }
  456. }
  457. private class KeyIterator extends EnumMapIterator<K> {
  458. public K next() {
  459. if (!hasNext())
  460. throw new NoSuchElementException();
  461. lastReturnedIndex = index++;
  462. return keyUniverse[lastReturnedIndex];
  463. }
  464. }
  465. private class ValueIterator extends EnumMapIterator<V> {
  466. public V next() {
  467. if (!hasNext())
  468. throw new NoSuchElementException();
  469. lastReturnedIndex = index++;
  470. return unmaskNull(vals[lastReturnedIndex]);
  471. }
  472. }
  473. /**
  474. * Since we don't use Entry objects, we use the Iterator itself as entry.
  475. */
  476. private class EntryIterator extends EnumMapIterator<Map.Entry<K,V>>
  477. implements Map.Entry<K,V>
  478. {
  479. public Map.Entry<K,V> next() {
  480. if (!hasNext())
  481. throw new NoSuchElementException();
  482. lastReturnedIndex = index++;
  483. return this;
  484. }
  485. public K getKey() {
  486. checkLastReturnedIndexForEntryUse();
  487. return keyUniverse[lastReturnedIndex];
  488. }
  489. public V getValue() {
  490. checkLastReturnedIndexForEntryUse();
  491. return unmaskNull(vals[lastReturnedIndex]);
  492. }
  493. public V setValue(V value) {
  494. checkLastReturnedIndexForEntryUse();
  495. V oldValue = unmaskNull(vals[lastReturnedIndex]);
  496. vals[lastReturnedIndex] = maskNull(value);
  497. return oldValue;
  498. }
  499. public boolean equals(Object o) {
  500. if (lastReturnedIndex < 0)
  501. return o == this;
  502. if (!(o instanceof Map.Entry))
  503. return false;
  504. Map.Entry e = (Map.Entry)o;
  505. V ourValue = unmaskNull(vals[lastReturnedIndex]);
  506. Object hisValue = e.getValue();
  507. return e.getKey() == keyUniverse[lastReturnedIndex] &&
  508. (ourValue == hisValue ||
  509. (ourValue != null && ourValue.equals(hisValue)));
  510. }
  511. public int hashCode() {
  512. if (lastReturnedIndex < 0)
  513. return super.hashCode();
  514. Object value = vals[lastReturnedIndex];
  515. return keyUniverse[lastReturnedIndex].hashCode()
  516. ^ (value == NULL ? 0 : value.hashCode());
  517. }
  518. public String toString() {
  519. if (lastReturnedIndex < 0)
  520. return super.toString();
  521. return keyUniverse[lastReturnedIndex] + "="
  522. + unmaskNull(vals[lastReturnedIndex]);
  523. }
  524. private void checkLastReturnedIndexForEntryUse() {
  525. if (lastReturnedIndex < 0)
  526. throw new IllegalStateException("Entry was removed");
  527. }
  528. }
  529. // Comparison and hashing
  530. /**
  531. * Compares the specified object with this map for equality. Returns
  532. * <tt>true</tt> if the given object is also a map and the two maps
  533. * represent the same mappings, as specified in the {@link
  534. * Map#equals(Object)} contract.
  535. *
  536. * @param o the object to be compared for equality with this map
  537. * @return <tt>true</tt> if the specified object is equal to this map
  538. */
  539. public boolean equals(Object o) {
  540. if (!(o instanceof EnumMap))
  541. return super.equals(o);
  542. EnumMap em = (EnumMap)o;
  543. if (em.keyType != keyType)
  544. return size == 0 && em.size == 0;
  545. // Key types match, compare each value
  546. for (int i = 0; i < keyUniverse.length; i++) {
  547. Object ourValue = vals[i];
  548. Object hisValue = em.vals[i];
  549. if (hisValue != ourValue &&
  550. (hisValue == null || !hisValue.equals(ourValue)))
  551. return false;
  552. }
  553. return true;
  554. }
  555. /**
  556. * Returns a shallow copy of this enum map. (The values themselves
  557. * are not cloned.
  558. *
  559. * @return a shallow copy of this enum map
  560. */
  561. public EnumMap<K, V> clone() {
  562. EnumMap<K, V> result = null;
  563. try {
  564. result = (EnumMap<K, V>) super.clone();
  565. } catch(CloneNotSupportedException e) {
  566. throw new AssertionError();
  567. }
  568. result.vals = (Object[]) result.vals.clone();
  569. return result;
  570. }
  571. /**
  572. * Throws an exception if e is not of the correct type for this enum set.
  573. */
  574. private void typeCheck(K key) {
  575. Class keyClass = key.getClass();
  576. if (keyClass != keyType && keyClass.getSuperclass() != keyType)
  577. throw new ClassCastException(keyClass + " != " + keyType);
  578. }
  579. private static final long serialVersionUID = 458661240069192865L;
  580. /**
  581. * Save the state of the <tt>EnumMap</tt> instance to a stream (i.e.,
  582. * serialize it).
  583. *
  584. * @serialData The <i>size</i> of the enum map (the number of key-value
  585. * mappings) is emitted (int), followed by the key (Object)
  586. * and value (Object) for each key-value mapping represented
  587. * by the enum map.
  588. */
  589. private void writeObject(java.io.ObjectOutputStream s)
  590. throws java.io.IOException
  591. {
  592. // Write out the key type and any hidden stuff
  593. s.defaultWriteObject();
  594. // Write out size (number of Mappings)
  595. s.writeInt(size);
  596. // Write out keys and values (alternating)
  597. for (Map.Entry<K,V> e : entrySet()) {
  598. s.writeObject(e.getKey());
  599. s.writeObject(e.getValue());
  600. }
  601. }
  602. /**
  603. * Reconstitute the <tt>EnumMap</tt> instance from a stream (i.e.,
  604. * deserialize it).
  605. */
  606. private void readObject(java.io.ObjectInputStream s)
  607. throws java.io.IOException, ClassNotFoundException
  608. {
  609. // Read in the key type and any hidden stuff
  610. s.defaultReadObject();
  611. keyUniverse = keyType.getEnumConstants();
  612. vals = new Object[keyUniverse.length];
  613. // Read in size (number of Mappings)
  614. int size = s.readInt();
  615. // Read the keys and values, and put the mappings in the HashMap
  616. for (int i = 0; i < size; i++) {
  617. K key = (K) s.readObject();
  618. V value = (V) s.readObject();
  619. put(key, value);
  620. }
  621. }
  622. }