25 |
25 |
26 package java.util; |
26 package java.util; |
27 import java.util.Map.Entry; |
27 import java.util.Map.Entry; |
28 |
28 |
29 /** |
29 /** |
30 * This class provides a skeletal implementation of the <tt>Map</tt> |
30 * This class provides a skeletal implementation of the {@code Map} |
31 * interface, to minimize the effort required to implement this interface. |
31 * interface, to minimize the effort required to implement this interface. |
32 * |
32 * |
33 * <p>To implement an unmodifiable map, the programmer needs only to extend this |
33 * <p>To implement an unmodifiable map, the programmer needs only to extend this |
34 * class and provide an implementation for the <tt>entrySet</tt> method, which |
34 * class and provide an implementation for the {@code entrySet} method, which |
35 * returns a set-view of the map's mappings. Typically, the returned set |
35 * returns a set-view of the map's mappings. Typically, the returned set |
36 * will, in turn, be implemented atop <tt>AbstractSet</tt>. This set should |
36 * will, in turn, be implemented atop {@code AbstractSet}. This set should |
37 * not support the <tt>add</tt> or <tt>remove</tt> methods, and its iterator |
37 * not support the {@code add} or {@code remove} methods, and its iterator |
38 * should not support the <tt>remove</tt> method. |
38 * should not support the {@code remove} method. |
39 * |
39 * |
40 * <p>To implement a modifiable map, the programmer must additionally override |
40 * <p>To implement a modifiable map, the programmer must additionally override |
41 * this class's <tt>put</tt> method (which otherwise throws an |
41 * this class's {@code put} method (which otherwise throws an |
42 * <tt>UnsupportedOperationException</tt>), and the iterator returned by |
42 * {@code UnsupportedOperationException}), and the iterator returned by |
43 * <tt>entrySet().iterator()</tt> must additionally implement its |
43 * {@code entrySet().iterator()} must additionally implement its |
44 * <tt>remove</tt> method. |
44 * {@code remove} method. |
45 * |
45 * |
46 * <p>The programmer should generally provide a void (no argument) and map |
46 * <p>The programmer should generally provide a void (no argument) and map |
47 * constructor, as per the recommendation in the <tt>Map</tt> interface |
47 * constructor, as per the recommendation in the {@code Map} interface |
48 * specification. |
48 * specification. |
49 * |
49 * |
50 * <p>The documentation for each non-abstract method in this class describes its |
50 * <p>The documentation for each non-abstract method in this class describes its |
51 * implementation in detail. Each of these methods may be overridden if the |
51 * implementation in detail. Each of these methods may be overridden if the |
52 * map being implemented admits a more efficient implementation. |
52 * map being implemented admits a more efficient implementation. |
77 |
77 |
78 /** |
78 /** |
79 * {@inheritDoc} |
79 * {@inheritDoc} |
80 * |
80 * |
81 * @implSpec |
81 * @implSpec |
82 * This implementation returns <tt>entrySet().size()</tt>. |
82 * This implementation returns {@code entrySet().size()}. |
83 */ |
83 */ |
84 public int size() { |
84 public int size() { |
85 return entrySet().size(); |
85 return entrySet().size(); |
86 } |
86 } |
87 |
87 |
88 /** |
88 /** |
89 * {@inheritDoc} |
89 * {@inheritDoc} |
90 * |
90 * |
91 * @implSpec |
91 * @implSpec |
92 * This implementation returns <tt>size() == 0</tt>. |
92 * This implementation returns {@code size() == 0}. |
93 */ |
93 */ |
94 public boolean isEmpty() { |
94 public boolean isEmpty() { |
95 return size() == 0; |
95 return size() == 0; |
96 } |
96 } |
97 |
97 |
98 /** |
98 /** |
99 * {@inheritDoc} |
99 * {@inheritDoc} |
100 * |
100 * |
101 * @implSpec |
101 * @implSpec |
102 * This implementation iterates over <tt>entrySet()</tt> searching |
102 * This implementation iterates over {@code entrySet()} searching |
103 * for an entry with the specified value. If such an entry is found, |
103 * for an entry with the specified value. If such an entry is found, |
104 * <tt>true</tt> is returned. If the iteration terminates without |
104 * {@code true} is returned. If the iteration terminates without |
105 * finding such an entry, <tt>false</tt> is returned. Note that this |
105 * finding such an entry, {@code false} is returned. Note that this |
106 * implementation requires linear time in the size of the map. |
106 * implementation requires linear time in the size of the map. |
107 * |
107 * |
108 * @throws ClassCastException {@inheritDoc} |
108 * @throws ClassCastException {@inheritDoc} |
109 * @throws NullPointerException {@inheritDoc} |
109 * @throws NullPointerException {@inheritDoc} |
110 */ |
110 */ |
128 |
128 |
129 /** |
129 /** |
130 * {@inheritDoc} |
130 * {@inheritDoc} |
131 * |
131 * |
132 * @implSpec |
132 * @implSpec |
133 * This implementation iterates over <tt>entrySet()</tt> searching |
133 * This implementation iterates over {@code entrySet()} searching |
134 * for an entry with the specified key. If such an entry is found, |
134 * for an entry with the specified key. If such an entry is found, |
135 * <tt>true</tt> is returned. If the iteration terminates without |
135 * {@code true} is returned. If the iteration terminates without |
136 * finding such an entry, <tt>false</tt> is returned. Note that this |
136 * finding such an entry, {@code false} is returned. Note that this |
137 * implementation requires linear time in the size of the map; many |
137 * implementation requires linear time in the size of the map; many |
138 * implementations will override this method. |
138 * implementations will override this method. |
139 * |
139 * |
140 * @throws ClassCastException {@inheritDoc} |
140 * @throws ClassCastException {@inheritDoc} |
141 * @throws NullPointerException {@inheritDoc} |
141 * @throws NullPointerException {@inheritDoc} |
160 |
160 |
161 /** |
161 /** |
162 * {@inheritDoc} |
162 * {@inheritDoc} |
163 * |
163 * |
164 * @implSpec |
164 * @implSpec |
165 * This implementation iterates over <tt>entrySet()</tt> searching |
165 * This implementation iterates over {@code entrySet()} searching |
166 * for an entry with the specified key. If such an entry is found, |
166 * for an entry with the specified key. If such an entry is found, |
167 * the entry's value is returned. If the iteration terminates without |
167 * the entry's value is returned. If the iteration terminates without |
168 * finding such an entry, <tt>null</tt> is returned. Note that this |
168 * finding such an entry, {@code null} is returned. Note that this |
169 * implementation requires linear time in the size of the map; many |
169 * implementation requires linear time in the size of the map; many |
170 * implementations will override this method. |
170 * implementations will override this method. |
171 * |
171 * |
172 * @throws ClassCastException {@inheritDoc} |
172 * @throws ClassCastException {@inheritDoc} |
173 * @throws NullPointerException {@inheritDoc} |
173 * @throws NullPointerException {@inheritDoc} |
196 /** |
196 /** |
197 * {@inheritDoc} |
197 * {@inheritDoc} |
198 * |
198 * |
199 * @implSpec |
199 * @implSpec |
200 * This implementation always throws an |
200 * This implementation always throws an |
201 * <tt>UnsupportedOperationException</tt>. |
201 * {@code UnsupportedOperationException}. |
202 * |
202 * |
203 * @throws UnsupportedOperationException {@inheritDoc} |
203 * @throws UnsupportedOperationException {@inheritDoc} |
204 * @throws ClassCastException {@inheritDoc} |
204 * @throws ClassCastException {@inheritDoc} |
205 * @throws NullPointerException {@inheritDoc} |
205 * @throws NullPointerException {@inheritDoc} |
206 * @throws IllegalArgumentException {@inheritDoc} |
206 * @throws IllegalArgumentException {@inheritDoc} |
211 |
211 |
212 /** |
212 /** |
213 * {@inheritDoc} |
213 * {@inheritDoc} |
214 * |
214 * |
215 * @implSpec |
215 * @implSpec |
216 * This implementation iterates over <tt>entrySet()</tt> searching for an |
216 * This implementation iterates over {@code entrySet()} searching for an |
217 * entry with the specified key. If such an entry is found, its value is |
217 * entry with the specified key. If such an entry is found, its value is |
218 * obtained with its <tt>getValue</tt> operation, the entry is removed |
218 * obtained with its {@code getValue} operation, the entry is removed |
219 * from the collection (and the backing map) with the iterator's |
219 * from the collection (and the backing map) with the iterator's |
220 * <tt>remove</tt> operation, and the saved value is returned. If the |
220 * {@code remove} operation, and the saved value is returned. If the |
221 * iteration terminates without finding such an entry, <tt>null</tt> is |
221 * iteration terminates without finding such an entry, {@code null} is |
222 * returned. Note that this implementation requires linear time in the |
222 * returned. Note that this implementation requires linear time in the |
223 * size of the map; many implementations will override this method. |
223 * size of the map; many implementations will override this method. |
224 * |
224 * |
225 * <p>Note that this implementation throws an |
225 * <p>Note that this implementation throws an |
226 * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt> |
226 * {@code UnsupportedOperationException} if the {@code entrySet} |
227 * iterator does not support the <tt>remove</tt> method and this map |
227 * iterator does not support the {@code remove} method and this map |
228 * contains a mapping for the specified key. |
228 * contains a mapping for the specified key. |
229 * |
229 * |
230 * @throws UnsupportedOperationException {@inheritDoc} |
230 * @throws UnsupportedOperationException {@inheritDoc} |
231 * @throws ClassCastException {@inheritDoc} |
231 * @throws ClassCastException {@inheritDoc} |
232 * @throws NullPointerException {@inheritDoc} |
232 * @throws NullPointerException {@inheritDoc} |
262 /** |
262 /** |
263 * {@inheritDoc} |
263 * {@inheritDoc} |
264 * |
264 * |
265 * @implSpec |
265 * @implSpec |
266 * This implementation iterates over the specified map's |
266 * This implementation iterates over the specified map's |
267 * <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt> |
267 * {@code entrySet()} collection, and calls this map's {@code put} |
268 * operation once for each entry returned by the iteration. |
268 * operation once for each entry returned by the iteration. |
269 * |
269 * |
270 * <p>Note that this implementation throws an |
270 * <p>Note that this implementation throws an |
271 * <tt>UnsupportedOperationException</tt> if this map does not support |
271 * {@code UnsupportedOperationException} if this map does not support |
272 * the <tt>put</tt> operation and the specified map is nonempty. |
272 * the {@code put} operation and the specified map is nonempty. |
273 * |
273 * |
274 * @throws UnsupportedOperationException {@inheritDoc} |
274 * @throws UnsupportedOperationException {@inheritDoc} |
275 * @throws ClassCastException {@inheritDoc} |
275 * @throws ClassCastException {@inheritDoc} |
276 * @throws NullPointerException {@inheritDoc} |
276 * @throws NullPointerException {@inheritDoc} |
277 * @throws IllegalArgumentException {@inheritDoc} |
277 * @throws IllegalArgumentException {@inheritDoc} |
283 |
283 |
284 /** |
284 /** |
285 * {@inheritDoc} |
285 * {@inheritDoc} |
286 * |
286 * |
287 * @implSpec |
287 * @implSpec |
288 * This implementation calls <tt>entrySet().clear()</tt>. |
288 * This implementation calls {@code entrySet().clear()}. |
289 * |
289 * |
290 * <p>Note that this implementation throws an |
290 * <p>Note that this implementation throws an |
291 * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt> |
291 * {@code UnsupportedOperationException} if the {@code entrySet} |
292 * does not support the <tt>clear</tt> operation. |
292 * does not support the {@code clear} operation. |
293 * |
293 * |
294 * @throws UnsupportedOperationException {@inheritDoc} |
294 * @throws UnsupportedOperationException {@inheritDoc} |
295 */ |
295 */ |
296 public void clear() { |
296 public void clear() { |
297 entrySet().clear(); |
297 entrySet().clear(); |
312 * {@inheritDoc} |
312 * {@inheritDoc} |
313 * |
313 * |
314 * @implSpec |
314 * @implSpec |
315 * This implementation returns a set that subclasses {@link AbstractSet}. |
315 * This implementation returns a set that subclasses {@link AbstractSet}. |
316 * The subclass's iterator method returns a "wrapper object" over this |
316 * The subclass's iterator method returns a "wrapper object" over this |
317 * map's <tt>entrySet()</tt> iterator. The <tt>size</tt> method |
317 * map's {@code entrySet()} iterator. The {@code size} method |
318 * delegates to this map's <tt>size</tt> method and the |
318 * delegates to this map's {@code size} method and the |
319 * <tt>contains</tt> method delegates to this map's |
319 * {@code contains} method delegates to this map's |
320 * <tt>containsKey</tt> method. |
320 * {@code containsKey} method. |
321 * |
321 * |
322 * <p>The set is created the first time this method is called, |
322 * <p>The set is created the first time this method is called, |
323 * and returned in response to all subsequent calls. No synchronization |
323 * and returned in response to all subsequent calls. No synchronization |
324 * is performed, so there is a slight chance that multiple calls to this |
324 * is performed, so there is a slight chance that multiple calls to this |
325 * method will not all return the same set. |
325 * method will not all return the same set. |
369 * {@inheritDoc} |
369 * {@inheritDoc} |
370 * |
370 * |
371 * @implSpec |
371 * @implSpec |
372 * This implementation returns a collection that subclasses {@link |
372 * This implementation returns a collection that subclasses {@link |
373 * AbstractCollection}. The subclass's iterator method returns a |
373 * AbstractCollection}. The subclass's iterator method returns a |
374 * "wrapper object" over this map's <tt>entrySet()</tt> iterator. |
374 * "wrapper object" over this map's {@code entrySet()} iterator. |
375 * The <tt>size</tt> method delegates to this map's <tt>size</tt> |
375 * The {@code size} method delegates to this map's {@code size} |
376 * method and the <tt>contains</tt> method delegates to this map's |
376 * method and the {@code contains} method delegates to this map's |
377 * <tt>containsValue</tt> method. |
377 * {@code containsValue} method. |
378 * |
378 * |
379 * <p>The collection is created the first time this method is called, and |
379 * <p>The collection is created the first time this method is called, and |
380 * returned in response to all subsequent calls. No synchronization is |
380 * returned in response to all subsequent calls. No synchronization is |
381 * performed, so there is a slight chance that multiple calls to this |
381 * performed, so there is a slight chance that multiple calls to this |
382 * method will not all return the same collection. |
382 * method will not all return the same collection. |
427 |
427 |
428 // Comparison and hashing |
428 // Comparison and hashing |
429 |
429 |
430 /** |
430 /** |
431 * Compares the specified object with this map for equality. Returns |
431 * Compares the specified object with this map for equality. Returns |
432 * <tt>true</tt> if the given object is also a map and the two maps |
432 * {@code true} if the given object is also a map and the two maps |
433 * represent the same mappings. More formally, two maps <tt>m1</tt> and |
433 * represent the same mappings. More formally, two maps {@code m1} and |
434 * <tt>m2</tt> represent the same mappings if |
434 * {@code m2} represent the same mappings if |
435 * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This ensures that the |
435 * {@code m1.entrySet().equals(m2.entrySet())}. This ensures that the |
436 * <tt>equals</tt> method works properly across different implementations |
436 * {@code equals} method works properly across different implementations |
437 * of the <tt>Map</tt> interface. |
437 * of the {@code Map} interface. |
438 * |
438 * |
439 * @implSpec |
439 * @implSpec |
440 * This implementation first checks if the specified object is this map; |
440 * This implementation first checks if the specified object is this map; |
441 * if so it returns <tt>true</tt>. Then, it checks if the specified |
441 * if so it returns {@code true}. Then, it checks if the specified |
442 * object is a map whose size is identical to the size of this map; if |
442 * object is a map whose size is identical to the size of this map; if |
443 * not, it returns <tt>false</tt>. If so, it iterates over this map's |
443 * not, it returns {@code false}. If so, it iterates over this map's |
444 * <tt>entrySet</tt> collection, and checks that the specified map |
444 * {@code entrySet} collection, and checks that the specified map |
445 * contains each mapping that this map contains. If the specified map |
445 * contains each mapping that this map contains. If the specified map |
446 * fails to contain such a mapping, <tt>false</tt> is returned. If the |
446 * fails to contain such a mapping, {@code false} is returned. If the |
447 * iteration completes, <tt>true</tt> is returned. |
447 * iteration completes, {@code true} is returned. |
448 * |
448 * |
449 * @param o object to be compared for equality with this map |
449 * @param o object to be compared for equality with this map |
450 * @return <tt>true</tt> if the specified object is equal to this map |
450 * @return {@code true} if the specified object is equal to this map |
451 */ |
451 */ |
452 public boolean equals(Object o) { |
452 public boolean equals(Object o) { |
453 if (o == this) |
453 if (o == this) |
454 return true; |
454 return true; |
455 |
455 |
481 } |
481 } |
482 |
482 |
483 /** |
483 /** |
484 * Returns the hash code value for this map. The hash code of a map is |
484 * Returns the hash code value for this map. The hash code of a map is |
485 * defined to be the sum of the hash codes of each entry in the map's |
485 * defined to be the sum of the hash codes of each entry in the map's |
486 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt> |
486 * {@code entrySet()} view. This ensures that {@code m1.equals(m2)} |
487 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps |
487 * implies that {@code m1.hashCode()==m2.hashCode()} for any two maps |
488 * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of |
488 * {@code m1} and {@code m2}, as required by the general contract of |
489 * {@link Object#hashCode}. |
489 * {@link Object#hashCode}. |
490 * |
490 * |
491 * @implSpec |
491 * @implSpec |
492 * This implementation iterates over <tt>entrySet()</tt>, calling |
492 * This implementation iterates over {@code entrySet()}, calling |
493 * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the |
493 * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the |
494 * set, and adding up the results. |
494 * set, and adding up the results. |
495 * |
495 * |
496 * @return the hash code value for this map |
496 * @return the hash code value for this map |
497 * @see Map.Entry#hashCode() |
497 * @see Map.Entry#hashCode() |
506 } |
506 } |
507 |
507 |
508 /** |
508 /** |
509 * Returns a string representation of this map. The string representation |
509 * Returns a string representation of this map. The string representation |
510 * consists of a list of key-value mappings in the order returned by the |
510 * consists of a list of key-value mappings in the order returned by the |
511 * map's <tt>entrySet</tt> view's iterator, enclosed in braces |
511 * map's {@code entrySet} view's iterator, enclosed in braces |
512 * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters |
512 * ({@code "{}"}). Adjacent mappings are separated by the characters |
513 * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as |
513 * {@code ", "} (comma and space). Each key-value mapping is rendered as |
514 * the key followed by an equals sign (<tt>"="</tt>) followed by the |
514 * the key followed by an equals sign ({@code "="}) followed by the |
515 * associated value. Keys and values are converted to strings as by |
515 * associated value. Keys and values are converted to strings as by |
516 * {@link String#valueOf(Object)}. |
516 * {@link String#valueOf(Object)}. |
517 * |
517 * |
518 * @return a string representation of this map |
518 * @return a string representation of this map |
519 */ |
519 */ |
536 sb.append(',').append(' '); |
536 sb.append(',').append(' '); |
537 } |
537 } |
538 } |
538 } |
539 |
539 |
540 /** |
540 /** |
541 * Returns a shallow copy of this <tt>AbstractMap</tt> instance: the keys |
541 * Returns a shallow copy of this {@code AbstractMap} instance: the keys |
542 * and values themselves are not cloned. |
542 * and values themselves are not cloned. |
543 * |
543 * |
544 * @return a shallow copy of this map |
544 * @return a shallow copy of this map |
545 */ |
545 */ |
546 protected Object clone() throws CloneNotSupportedException { |
546 protected Object clone() throws CloneNotSupportedException { |
568 // exposing a common abstract class. |
568 // exposing a common abstract class. |
569 |
569 |
570 |
570 |
571 /** |
571 /** |
572 * An Entry maintaining a key and a value. The value may be |
572 * An Entry maintaining a key and a value. The value may be |
573 * changed using the <tt>setValue</tt> method. This class |
573 * changed using the {@code setValue} method. This class |
574 * facilitates the process of building custom map |
574 * facilitates the process of building custom map |
575 * implementations. For example, it may be convenient to return |
575 * implementations. For example, it may be convenient to return |
576 * arrays of <tt>SimpleEntry</tt> instances in method |
576 * arrays of {@code SimpleEntry} instances in method |
577 * <tt>Map.entrySet().toArray</tt>. |
577 * {@code Map.entrySet().toArray}. |
578 * |
578 * |
579 * @since 1.6 |
579 * @since 1.6 |
580 */ |
580 */ |
581 public static class SimpleEntry<K,V> |
581 public static class SimpleEntry<K,V> |
582 implements Entry<K,V>, java.io.Serializable |
582 implements Entry<K,V>, java.io.Serializable |
687 } |
687 } |
688 |
688 |
689 /** |
689 /** |
690 * Returns a String representation of this map entry. This |
690 * Returns a String representation of this map entry. This |
691 * implementation returns the string representation of this |
691 * implementation returns the string representation of this |
692 * entry's key followed by the equals character ("<tt>=</tt>") |
692 * entry's key followed by the equals character ("{@code =}") |
693 * followed by the string representation of this entry's value. |
693 * followed by the string representation of this entry's value. |
694 * |
694 * |
695 * @return a String representation of this map entry |
695 * @return a String representation of this map entry |
696 */ |
696 */ |
697 public String toString() { |
697 public String toString() { |
758 } |
758 } |
759 |
759 |
760 /** |
760 /** |
761 * Replaces the value corresponding to this entry with the specified |
761 * Replaces the value corresponding to this entry with the specified |
762 * value (optional operation). This implementation simply throws |
762 * value (optional operation). This implementation simply throws |
763 * <tt>UnsupportedOperationException</tt>, as this class implements |
763 * {@code UnsupportedOperationException}, as this class implements |
764 * an <i>immutable</i> map entry. |
764 * an <i>immutable</i> map entry. |
765 * |
765 * |
766 * @param value new value to be stored in this entry |
766 * @param value new value to be stored in this entry |
767 * @return (Does not return) |
767 * @return (Does not return) |
768 * @throws UnsupportedOperationException always |
768 * @throws UnsupportedOperationException always |
818 } |
818 } |
819 |
819 |
820 /** |
820 /** |
821 * Returns a String representation of this map entry. This |
821 * Returns a String representation of this map entry. This |
822 * implementation returns the string representation of this |
822 * implementation returns the string representation of this |
823 * entry's key followed by the equals character ("<tt>=</tt>") |
823 * entry's key followed by the equals character ("{@code =}") |
824 * followed by the string representation of this entry's value. |
824 * followed by the string representation of this entry's value. |
825 * |
825 * |
826 * @return a String representation of this map entry |
826 * @return a String representation of this map entry |
827 */ |
827 */ |
828 public String toString() { |
828 public String toString() { |