KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > AbstractMap


1 /*
2  * @(#)AbstractMap.java 1.42 04/02/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util;
9 import java.util.Map.Entry;
10
11 /**
12  * This class provides a skeletal implementation of the <tt>Map</tt>
13  * interface, to minimize the effort required to implement this interface. <p>
14  *
15  * To implement an unmodifiable map, the programmer needs only to extend this
16  * class and provide an implementation for the <tt>entrySet</tt> method, which
17  * returns a set-view of the map's mappings. Typically, the returned set
18  * will, in turn, be implemented atop <tt>AbstractSet</tt>. This set should
19  * not support the <tt>add</tt> or <tt>remove</tt> methods, and its iterator
20  * should not support the <tt>remove</tt> method.<p>
21  *
22  * To implement a modifiable map, the programmer must additionally override
23  * this class's <tt>put</tt> method (which otherwise throws an
24  * <tt>UnsupportedOperationException</tt>), and the iterator returned by
25  * <tt>entrySet().iterator()</tt> must additionally implement its
26  * <tt>remove</tt> method.<p>
27  *
28  * The programmer should generally provide a void (no argument) and map
29  * constructor, as per the recommendation in the <tt>Map</tt> interface
30  * specification.<p>
31  *
32  * The documentation for each non-abstract methods in this class describes its
33  * implementation in detail. Each of these methods may be overridden if the
34  * map being implemented admits a more efficient implementation.<p>
35  *
36  * This class is a member of the
37  * <a HREF="{@docRoot}/../guide/collections/index.html">
38  * Java Collections Framework</a>.
39  *
40  * @author Josh Bloch
41  * @author Neal Gafter
42  * @version 1.42, 02/19/04
43  * @see Map
44  * @see Collection
45  * @since 1.2
46  */

47
48 public abstract class AbstractMap<K,V> implements Map JavaDoc<K,V> {
49     /**
50      * Sole constructor. (For invocation by subclass constructors, typically
51      * implicit.)
52      */

53     protected AbstractMap() {
54     }
55
56     // Query Operations
57

58     /**
59      * Returns the number of key-value mappings in this map. If the map
60      * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
61      * <tt>Integer.MAX_VALUE</tt>.<p>
62      *
63      * This implementation returns <tt>entrySet().size()</tt>.
64      *
65      * @return the number of key-value mappings in this map.
66      */

67     public int size() {
68     return entrySet().size();
69     }
70
71     /**
72      * Returns <tt>true</tt> if this map contains no key-value mappings. <p>
73      *
74      * This implementation returns <tt>size() == 0</tt>.
75      *
76      * @return <tt>true</tt> if this map contains no key-value mappings.
77      */

78     public boolean isEmpty() {
79     return size() == 0;
80     }
81
82     /**
83      * Returns <tt>true</tt> if this map maps one or more keys to this value.
84      * More formally, returns <tt>true</tt> if and only if this map contains
85      * at least one mapping to a value <tt>v</tt> such that <tt>(value==null ?
86      * v==null : value.equals(v))</tt>. This operation will probably require
87      * time linear in the map size for most implementations of map.<p>
88      *
89      * This implementation iterates over entrySet() searching for an entry
90      * with the specified value. If such an entry is found, <tt>true</tt> is
91      * returned. If the iteration terminates without finding such an entry,
92      * <tt>false</tt> is returned. Note that this implementation requires
93      * linear time in the size of the map.
94      *
95      * @param value value whose presence in this map is to be tested.
96      *
97      * @return <tt>true</tt> if this map maps one or more keys to this value.
98      */

99     public boolean containsValue(Object JavaDoc value) {
100     Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
101     if (value==null) {
102         while (i.hasNext()) {
103         Entry<K,V> e = i.next();
104         if (e.getValue()==null)
105             return true;
106         }
107     } else {
108         while (i.hasNext()) {
109         Entry<K,V> e = i.next();
110         if (value.equals(e.getValue()))
111             return true;
112         }
113     }
114     return false;
115     }
116
117     /**
118      * Returns <tt>true</tt> if this map contains a mapping for the specified
119      * key. <p>
120      *
121      * This implementation iterates over <tt>entrySet()</tt> searching for an
122      * entry with the specified key. If such an entry is found, <tt>true</tt>
123      * is returned. If the iteration terminates without finding such an
124      * entry, <tt>false</tt> is returned. Note that this implementation
125      * requires linear time in the size of the map; many implementations will
126      * override this method.
127      *
128      * @param key key whose presence in this map is to be tested.
129      * @return <tt>true</tt> if this map contains a mapping for the specified
130      * key.
131      *
132      * @throws NullPointerException if the key is <tt>null</tt> and this map
133      * does not permit <tt>null</tt> keys.
134      */

135     public boolean containsKey(Object JavaDoc key) {
136     Iterator JavaDoc<Map.Entry JavaDoc<K,V>> i = entrySet().iterator();
137     if (key==null) {
138         while (i.hasNext()) {
139         Entry<K,V> e = i.next();
140         if (e.getKey()==null)
141             return true;
142         }
143     } else {
144         while (i.hasNext()) {
145         Entry<K,V> e = i.next();
146         if (key.equals(e.getKey()))
147             return true;
148         }
149     }
150     return false;
151     }
152
153     /**
154      * Returns the value to which this map maps the specified key. Returns
155      * <tt>null</tt> if the map contains no mapping for this key. A return
156      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
157      * map contains no mapping for the key; it's also possible that the map
158      * explicitly maps the key to <tt>null</tt>. The containsKey operation
159      * may be used to distinguish these two cases. <p>
160      *
161      * This implementation iterates over <tt>entrySet()</tt> searching for an
162      * entry with the specified key. If such an entry is found, the entry's
163      * value is returned. If the iteration terminates without finding such an
164      * entry, <tt>null</tt> is returned. Note that this implementation
165      * requires linear time in the size of the map; many implementations will
166      * override this method.
167      *
168      * @param key key whose associated value is to be returned.
169      * @return the value to which this map maps the specified key.
170      *
171      * @throws NullPointerException if the key is <tt>null</tt> and this map
172      * does not permit <tt>null</tt> keys.
173      *
174      * @see #containsKey(Object)
175      */

176     public V get(Object JavaDoc key) {
177     Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
178     if (key==null) {
179         while (i.hasNext()) {
180         Entry<K,V> e = i.next();
181         if (e.getKey()==null)
182             return e.getValue();
183         }
184     } else {
185         while (i.hasNext()) {
186         Entry<K,V> e = i.next();
187         if (key.equals(e.getKey()))
188             return e.getValue();
189         }
190     }
191     return null;
192     }
193
194
195     // Modification Operations
196

197     /**
198      * Associates the specified value with the specified key in this map
199      * (optional operation). If the map previously contained a mapping for
200      * this key, the old value is replaced.<p>
201      *
202      * This implementation always throws an
203      * <tt>UnsupportedOperationException</tt>.
204      *
205      * @param key key with which the specified value is to be associated.
206      * @param value value to be associated with the specified key.
207      *
208      * @return previous value associated with specified key, or <tt>null</tt>
209      * if there was no mapping for key. (A <tt>null</tt> return can
210      * also indicate that the map previously associated <tt>null</tt>
211      * with the specified key, if the implementation supports
212      * <tt>null</tt> values.)
213      *
214      * @throws UnsupportedOperationException if the <tt>put</tt> operation is
215      * not supported by this map.
216      *
217      * @throws ClassCastException if the class of the specified key or value
218      * prevents it from being stored in this map.
219      *
220      * @throws IllegalArgumentException if some aspect of this key or value *
221      * prevents it from being stored in this map.
222      *
223      * @throws NullPointerException if this map does not permit <tt>null</tt>
224      * keys or values, and the specified key or value is
225      * <tt>null</tt>.
226      */

227     public V put(K key, V value) {
228     throw new UnsupportedOperationException JavaDoc();
229     }
230
231     /**
232      * Removes the mapping for this key from this map if present (optional
233      * operation). <p>
234      *
235      * This implementation iterates over <tt>entrySet()</tt> searching for an
236      * entry with the specified key. If such an entry is found, its value is
237      * obtained with its <tt>getValue</tt> operation, the entry is removed
238      * from the Collection (and the backing map) with the iterator's
239      * <tt>remove</tt> operation, and the saved value is returned. If the
240      * iteration terminates without finding such an entry, <tt>null</tt> is
241      * returned. Note that this implementation requires linear time in the
242      * size of the map; many implementations will override this method.<p>
243      *
244      * Note that this implementation throws an
245      * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt> iterator
246      * does not support the <tt>remove</tt> method and this map contains a
247      * mapping for the specified key.
248      *
249      * @param key key whose mapping is to be removed from the map.
250      * @return previous value associated with specified key, or <tt>null</tt>
251      * if there was no entry for key. (A <tt>null</tt> return can
252      * also indicate that the map previously associated <tt>null</tt>
253      * with the specified key, if the implementation supports
254      * <tt>null</tt> values.)
255      * @throws UnsupportedOperationException if the <tt>remove</tt> operation
256      * is not supported by this map.
257      */

258     public V remove(Object JavaDoc key) {
259     Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
260     Entry<K,V> correctEntry = null;
261     if (key==null) {
262         while (correctEntry==null && i.hasNext()) {
263         Entry<K,V> e = i.next();
264         if (e.getKey()==null)
265             correctEntry = e;
266         }
267     } else {
268         while (correctEntry==null && i.hasNext()) {
269         Entry<K,V> e = i.next();
270         if (key.equals(e.getKey()))
271             correctEntry = e;
272         }
273     }
274
275     V oldValue = null;
276     if (correctEntry !=null) {
277         oldValue = correctEntry.getValue();
278         i.remove();
279     }
280     return oldValue;
281     }
282
283
284     // Bulk Operations
285

286     /**
287      * Copies all of the mappings from the specified map to this map
288      * (optional operation). These mappings will replace any mappings that
289      * this map had for any of the keys currently in the specified map.<p>
290      *
291      * This implementation iterates over the specified map's
292      * <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt>
293      * operation once for each entry returned by the iteration.<p>
294      *
295      * Note that this implementation throws an
296      * <tt>UnsupportedOperationException</tt> if this map does not support
297      * the <tt>put</tt> operation and the specified map is nonempty.
298      *
299      * @param t mappings to be stored in this map.
300      *
301      * @throws UnsupportedOperationException if the <tt>putAll</tt> operation
302      * is not supported by this map.
303      *
304      * @throws ClassCastException if the class of a key or value in the
305      * specified map prevents it from being stored in this map.
306      *
307      * @throws IllegalArgumentException if some aspect of a key or value in
308      * the specified map prevents it from being stored in this map.
309      * @throws NullPointerException if the specified map is <tt>null</tt>, or if
310      * this map does not permit <tt>null</tt> keys or values, and the
311      * specified map contains <tt>null</tt> keys or values.
312      */

313     public void putAll(Map JavaDoc<? extends K, ? extends V> t) {
314     Iterator JavaDoc<? extends Entry<? extends K, ? extends V>> i = t.entrySet().iterator();
315     while (i.hasNext()) {
316         Entry<? extends K, ? extends V> e = i.next();
317         put(e.getKey(), e.getValue());
318     }
319     }
320
321     /**
322      * Removes all mappings from this map (optional operation). <p>
323      *
324      * This implementation calls <tt>entrySet().clear()</tt>.
325      *
326      * Note that this implementation throws an
327      * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt>
328      * does not support the <tt>clear</tt> operation.
329      *
330      * @throws UnsupportedOperationException clear is not supported
331      * by this map.
332      */

333     public void clear() {
334     entrySet().clear();
335     }
336
337
338     // Views
339

340     /**
341      * Each of these fields are initialized to contain an instance of the
342      * appropriate view the first time this view is requested. The views are
343      * stateless, so there's no reason to create more than one of each.
344      */

345     transient volatile Set JavaDoc<K> keySet = null;
346     transient volatile Collection JavaDoc<V> values = null;
347
348     /**
349      * Returns a Set view of the keys contained in this map. The Set is
350      * backed by the map, so changes to the map are reflected in the Set,
351      * and vice-versa. (If the map is modified while an iteration over
352      * the Set is in progress, the results of the iteration are undefined.)
353      * The Set supports element removal, which removes the corresponding entry
354      * from the map, via the Iterator.remove, Set.remove, removeAll
355      * retainAll, and clear operations. It does not support the add or
356      * addAll operations.<p>
357      *
358      * This implementation returns a Set that subclasses
359      * AbstractSet. The subclass's iterator method returns a "wrapper
360      * object" over this map's entrySet() iterator. The size method delegates
361      * to this map's size method and the contains method delegates to this
362      * map's containsKey method.<p>
363      *
364      * The Set is created the first time this method is called,
365      * and returned in response to all subsequent calls. No synchronization
366      * is performed, so there is a slight chance that multiple calls to this
367      * method will not all return the same Set.
368      *
369      * @return a Set view of the keys contained in this map.
370      */

371     public Set JavaDoc<K> keySet() {
372     if (keySet == null) {
373         keySet = new AbstractSet JavaDoc<K>() {
374         public Iterator JavaDoc<K> iterator() {
375             return new Iterator JavaDoc<K>() {
376             private Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
377
378             public boolean hasNext() {
379                 return i.hasNext();
380             }
381
382             public K next() {
383                 return i.next().getKey();
384             }
385
386             public void remove() {
387                 i.remove();
388             }
389                     };
390         }
391
392         public int size() {
393             return AbstractMap.this.size();
394         }
395
396         public boolean contains(Object JavaDoc k) {
397             return AbstractMap.this.containsKey(k);
398         }
399         };
400     }
401     return keySet;
402     }
403
404     /**
405      * Returns a collection view of the values contained in this map. The
406      * collection is backed by the map, so changes to the map are reflected in
407      * the collection, and vice-versa. (If the map is modified while an
408      * iteration over the collection is in progress, the results of the
409      * iteration are undefined.) The collection supports element removal,
410      * which removes the corresponding entry from the map, via the
411      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
412      * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> operations.
413      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.<p>
414      *
415      * This implementation returns a collection that subclasses abstract
416      * collection. The subclass's iterator method returns a "wrapper object"
417      * over this map's <tt>entrySet()</tt> iterator. The size method
418      * delegates to this map's size method and the contains method delegates
419      * to this map's containsValue method.<p>
420      *
421      * The collection is created the first time this method is called, and
422      * returned in response to all subsequent calls. No synchronization is
423      * performed, so there is a slight chance that multiple calls to this
424      * method will not all return the same Collection.
425      *
426      * @return a collection view of the values contained in this map.
427      */

428     public Collection JavaDoc<V> values() {
429     if (values == null) {
430         values = new AbstractCollection JavaDoc<V>() {
431         public Iterator JavaDoc<V> iterator() {
432             return new Iterator JavaDoc<V>() {
433             private Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
434
435             public boolean hasNext() {
436                 return i.hasNext();
437             }
438
439             public V next() {
440                 return i.next().getValue();
441             }
442
443             public void remove() {
444                 i.remove();
445             }
446                     };
447                 }
448
449         public int size() {
450             return AbstractMap.this.size();
451         }
452
453         public boolean contains(Object JavaDoc v) {
454             return AbstractMap.this.containsValue(v);
455         }
456         };
457     }
458     return values;
459     }
460
461     /**
462      * Returns a set view of the mappings contained in this map. Each element
463      * in this set is a Map.Entry. The set is backed by the map, so changes
464      * to the map are reflected in the set, and vice-versa. (If the map is
465      * modified while an iteration over the set is in progress, the results of
466      * the iteration are undefined.) The set supports element removal, which
467      * removes the corresponding entry from the map, via the
468      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
469      * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not support
470      * the <tt>add</tt> or <tt>addAll</tt> operations.
471      *
472      * @return a set view of the mappings contained in this map.
473      */

474     public abstract Set JavaDoc<Entry<K,V>> entrySet();
475
476
477     // Comparison and hashing
478

479     /**
480      * Compares the specified object with this map for equality. Returns
481      * <tt>true</tt> if the given object is also a map and the two maps
482      * represent the same mappings. More formally, two maps <tt>t1</tt> and
483      * <tt>t2</tt> represent the same mappings if
484      * <tt>t1.keySet().equals(t2.keySet())</tt> and for every key <tt>k</tt>
485      * in <tt>t1.keySet()</tt>, <tt> (t1.get(k)==null ? t2.get(k)==null :
486      * t1.get(k).equals(t2.get(k))) </tt>. This ensures that the
487      * <tt>equals</tt> method works properly across different implementations
488      * of the map interface.<p>
489      *
490      * This implementation first checks if the specified object is this map;
491      * if so it returns <tt>true</tt>. Then, it checks if the specified
492      * object is a map whose size is identical to the size of this set; if
493      * not, it returns <tt>false</tt>. If so, it iterates over this map's
494      * <tt>entrySet</tt> collection, and checks that the specified map
495      * contains each mapping that this map contains. If the specified map
496      * fails to contain such a mapping, <tt>false</tt> is returned. If the
497      * iteration completes, <tt>true</tt> is returned.
498      *
499      * @param o object to be compared for equality with this map.
500      * @return <tt>true</tt> if the specified object is equal to this map.
501      */

502     public boolean equals(Object JavaDoc o) {
503     if (o == this)
504         return true;
505
506     if (!(o instanceof Map JavaDoc))
507         return false;
508     Map JavaDoc<K,V> t = (Map JavaDoc<K,V>) o;
509     if (t.size() != size())
510         return false;
511
512         try {
513             Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
514             while (i.hasNext()) {
515                 Entry<K,V> e = i.next();
516         K key = e.getKey();
517                 V value = e.getValue();
518                 if (value == null) {
519                     if (!(t.get(key)==null && t.containsKey(key)))
520                         return false;
521                 } else {
522                     if (!value.equals(t.get(key)))
523                         return false;
524                 }
525             }
526         } catch(ClassCastException JavaDoc unused) {
527             return false;
528         } catch(NullPointerException JavaDoc unused) {
529             return false;
530         }
531
532     return true;
533     }
534
535     /**
536      * Returns the hash code value for this map. The hash code of a map is
537      * defined to be the sum of the hash codes of each entry in the map's
538      * <tt>entrySet()</tt> view. This ensures that <tt>t1.equals(t2)</tt>
539      * implies that <tt>t1.hashCode()==t2.hashCode()</tt> for any two maps
540      * <tt>t1</tt> and <tt>t2</tt>, as required by the general contract of
541      * Object.hashCode.<p>
542      *
543      * This implementation iterates over <tt>entrySet()</tt>, calling
544      * <tt>hashCode</tt> on each element (entry) in the Collection, and adding
545      * up the results.
546      *
547      * @return the hash code value for this map.
548      * @see Map.Entry#hashCode()
549      * @see Object#hashCode()
550      * @see Object#equals(Object)
551      * @see Set#equals(Object)
552      */

553     public int hashCode() {
554     int h = 0;
555     Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
556     while (i.hasNext())
557         h += i.next().hashCode();
558     return h;
559     }
560
561     /**
562      * Returns a string representation of this map. The string representation
563      * consists of a list of key-value mappings in the order returned by the
564      * map's <tt>entrySet</tt> view's iterator, enclosed in braces
565      * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters
566      * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as
567      * the key followed by an equals sign (<tt>"="</tt>) followed by the
568      * associated value. Keys and values are converted to strings as by
569      * <tt>String.valueOf(Object)</tt>.<p>
570      *
571      * This implementation creates an empty string buffer, appends a left
572      * brace, and iterates over the map's <tt>entrySet</tt> view, appending
573      * the string representation of each <tt>map.entry</tt> in turn. After
574      * appending each entry except the last, the string <tt>", "</tt> is
575      * appended. Finally a right brace is appended. A string is obtained
576      * from the stringbuffer, and returned.
577      *
578      * @return a String representation of this map.
579      */

580     public String JavaDoc toString() {
581     StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
582     buf.append("{");
583
584     Iterator JavaDoc<Entry<K,V>> i = entrySet().iterator();
585         boolean hasNext = i.hasNext();
586         while (hasNext) {
587         Entry<K,V> e = i.next();
588         K key = e.getKey();
589             V value = e.getValue();
590         if (key == this)
591         buf.append("(this Map)");
592         else
593         buf.append(key);
594         buf.append("=");
595         if (value == this)
596         buf.append("(this Map)");
597         else
598         buf.append(value);
599             hasNext = i.hasNext();
600             if (hasNext)
601                 buf.append(", ");
602         }
603
604     buf.append("}");
605     return buf.toString();
606     }
607     
608     /**
609      * Returns a shallow copy of this <tt>AbstractMap</tt> instance: the keys
610      * and values themselves are not cloned.
611      *
612      * @return a shallow copy of this map.
613      */

614     protected Object JavaDoc clone() throws CloneNotSupportedException JavaDoc {
615         AbstractMap JavaDoc<K,V> result = (AbstractMap JavaDoc<K,V>)super.clone();
616         result.keySet = null;
617         result.values = null;
618         return result;
619     }
620
621     /**
622      * This should be made public as soon as possible. It greatly simplifies
623      * the task of implementing Map.
624      */

625     static class SimpleEntry<K,V> implements Entry<K,V> {
626     K key;
627     V value;
628
629     public SimpleEntry(K key, V value) {
630         this.key = key;
631             this.value = value;
632     }
633
634     public SimpleEntry(Entry<K,V> e) {
635         this.key = e.getKey();
636             this.value = e.getValue();
637     }
638
639     public K getKey() {
640         return key;
641     }
642
643     public V getValue() {
644         return value;
645     }
646
647     public V setValue(V value) {
648         V oldValue = this.value;
649         this.value = value;
650         return oldValue;
651     }
652
653     public boolean equals(Object JavaDoc o) {
654         if (!(o instanceof Map.Entry JavaDoc))
655         return false;
656         Map.Entry JavaDoc e = (Map.Entry JavaDoc)o;
657         return eq(key, e.getKey()) && eq(value, e.getValue());
658     }
659
660     public int hashCode() {
661         return ((key == null) ? 0 : key.hashCode()) ^
662            ((value == null) ? 0 : value.hashCode());
663     }
664
665     public String JavaDoc toString() {
666         return key + "=" + value;
667     }
668
669         private static boolean eq(Object JavaDoc o1, Object JavaDoc o2) {
670             return (o1 == null ? o2 == null : o1.equals(o2));
671         }
672     }
673 }
674
Popular Tags