001: /*
002: * @(#)AbstractMap.java 1.28 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: import java.util.Map.Entry;
031:
032: /**
033: * This class provides a skeletal implementation of the <tt>Map</tt>
034: * interface, to minimize the effort required to implement this interface. <p>
035: *
036: * To implement an unmodifiable map, the programmer needs only to extend this
037: * class and provide an implementation for the <tt>entrySet</tt> method, which
038: * returns a set-view of the map's mappings. Typically, the returned set
039: * will, in turn, be implemented atop <tt>AbstractSet</tt>. This set should
040: * not support the <tt>add</tt> or <tt>remove</tt> methods, and its iterator
041: * should not support the <tt>remove</tt> method.<p>
042: *
043: * To implement a modifiable map, the programmer must additionally override
044: * this class's <tt>put</tt> method (which otherwise throws an
045: * <tt>UnsupportedOperationException</tt>), and the iterator returned by
046: * <tt>entrySet().iterator()</tt> must additionally implement its
047: * <tt>remove</tt> method.<p>
048: *
049: * The programmer should generally provide a void (no argument) and map
050: * constructor, as per the recommendation in the <tt>Map</tt> interface
051: * specification.<p>
052: *
053: * The documentation for each non-abstract methods in this class describes its
054: * implementation in detail. Each of these methods may be overridden if the
055: * map being implemented admits a more efficient implementation.<p>
056: *
057: * This class is a member of the
058: * <a href="{@docRoot}/../guide/collections/index.html">
059: * Java Collections Framework</a>.
060: *
061: * @author Josh Bloch
062: * @version 1.21, 02/02/00
063: * @see Map
064: * @see Collection
065: * @since 1.2
066: */
067:
068: public abstract class AbstractMap implements Map {
069: /**
070: * Sole constructor. (For invocation by subclass constructors, typically
071: * implicit.)
072: */
073: protected AbstractMap() {
074: }
075:
076: // Query Operations
077:
078: /**
079: * Returns the number of key-value mappings in this map. If the map
080: * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
081: * <tt>Integer.MAX_VALUE</tt>.<p>
082: *
083: * This implementation returns <tt>entrySet().size()</tt>.
084: *
085: * @return the number of key-value mappings in this map.
086: */
087: public int size() {
088: return entrySet().size();
089: }
090:
091: /**
092: * Returns <tt>true</tt> if this map contains no key-value mappings. <p>
093: *
094: * This implementation returns <tt>size() == 0</tt>.
095: *
096: * @return <tt>true</tt> if this map contains no key-value mappings.
097: */
098: public boolean isEmpty() {
099: return size() == 0;
100: }
101:
102: /**
103: * Returns <tt>true</tt> if this map maps one or more keys to this value.
104: * More formally, returns <tt>true</tt> if and only if this map contains
105: * at least one mapping to a value <tt>v</tt> such that <tt>(value==null ?
106: * v==null : value.equals(v))</tt>. This operation will probably require
107: * time linear in the map size for most implementations of map.<p>
108: *
109: * This implementation iterates over entrySet() searching for an entry
110: * with the specified value. If such an entry is found, <tt>true</tt> is
111: * returned. If the iteration terminates without finding such an entry,
112: * <tt>false</tt> is returned. Note that this implementation requires
113: * linear time in the size of the map.
114: *
115: * @param value value whose presence in this map is to be tested.
116: *
117: * @return <tt>true</tt> if this map maps one or more keys to this value.
118: */
119: public boolean containsValue(Object value) {
120: Iterator i = entrySet().iterator();
121: if (value == null) {
122: while (i.hasNext()) {
123: Entry e = (Entry) i.next();
124: if (e.getValue() == null)
125: return true;
126: }
127: } else {
128: while (i.hasNext()) {
129: Entry e = (Entry) i.next();
130: if (value.equals(e.getValue()))
131: return true;
132: }
133: }
134: return false;
135: }
136:
137: /**
138: * Returns <tt>true</tt> if this map contains a mapping for the specified
139: * key. <p>
140: *
141: * This implementation iterates over <tt>entrySet()</tt> searching for an
142: * entry with the specified key. If such an entry is found, <tt>true</tt>
143: * is returned. If the iteration terminates without finding such an
144: * entry, <tt>false</tt> is returned. Note that this implementation
145: * requires linear time in the size of the map; many implementations will
146: * override this method.
147: *
148: * @param key key whose presence in this map is to be tested.
149: * @return <tt>true</tt> if this map contains a mapping for the specified
150: * key.
151: *
152: * @throws NullPointerException key is <tt>null</tt> and this map does not
153: * not permit <tt>null</tt> keys.
154: */
155: public boolean containsKey(Object key) {
156: Iterator i = entrySet().iterator();
157: if (key == null) {
158: while (i.hasNext()) {
159: Entry e = (Entry) i.next();
160: if (e.getKey() == null)
161: return true;
162: }
163: } else {
164: while (i.hasNext()) {
165: Entry e = (Entry) i.next();
166: if (key.equals(e.getKey()))
167: return true;
168: }
169: }
170: return false;
171: }
172:
173: /**
174: * Returns the value to which this map maps the specified key. Returns
175: * <tt>null</tt> if the map contains no mapping for this key. A return
176: * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
177: * map contains no mapping for the key; it's also possible that the map
178: * explicitly maps the key to <tt>null</tt>. The containsKey operation
179: * may be used to distinguish these two cases. <p>
180: *
181: * This implementation iterates over <tt>entrySet()</tt> searching for an
182: * entry with the specified key. If such an entry is found, the entry's
183: * value is returned. If the iteration terminates without finding such an
184: * entry, <tt>null</tt> is returned. Note that this implementation
185: * requires linear time in the size of the map; many implementations will
186: * override this method.
187: *
188: * @param key key whose associated value is to be returned.
189: * @return the value to which this map maps the specified key.
190: *
191: * @throws NullPointerException if the key is <tt>null</tt> and this map
192: * does not not permit <tt>null</tt> keys.
193: *
194: * @see #containsKey(Object)
195: */
196: public Object get(Object key) {
197: Iterator i = entrySet().iterator();
198: if (key == null) {
199: while (i.hasNext()) {
200: Entry e = (Entry) i.next();
201: if (e.getKey() == null)
202: return e.getValue();
203: }
204: } else {
205: while (i.hasNext()) {
206: Entry e = (Entry) i.next();
207: if (key.equals(e.getKey()))
208: return e.getValue();
209: }
210: }
211: return null;
212: }
213:
214: // Modification Operations
215:
216: /**
217: * Associates the specified value with the specified key in this map
218: * (optional operation). If the map previously contained a mapping for
219: * this key, the old value is replaced.<p>
220: *
221: * This implementation always throws an
222: * <tt>UnsupportedOperationException</tt>.
223: *
224: * @param key key with which the specified value is to be associated.
225: * @param value value to be associated with the specified key.
226: *
227: * @return previous value associated with specified key, or <tt>null</tt>
228: * if there was no mapping for key. (A <tt>null</tt> return can
229: * also indicate that the map previously associated <tt>null</tt>
230: * with the specified key, if the implementation supports
231: * <tt>null</tt> values.)
232: *
233: * @throws UnsupportedOperationException if the <tt>put</tt> operation is
234: * not supported by this map.
235: *
236: * @throws ClassCastException if the class of the specified key or value
237: * prevents it from being stored in this map.
238: *
239: * @throws IllegalArgumentException if some aspect of this key or value *
240: * prevents it from being stored in this map.
241: *
242: * @throws NullPointerException this map does not permit <tt>null</tt>
243: * keys or values, and the specified key or value is
244: * <tt>null</tt>.
245: */
246: public Object put(Object key, Object value) {
247: throw new UnsupportedOperationException();
248: }
249:
250: /**
251: * Removes the mapping for this key from this map if present (optional
252: * operation). <p>
253: *
254: * This implementation iterates over <tt>entrySet()</tt> searching for an
255: * entry with the specified key. If such an entry is found, its value is
256: * obtained with its <tt>getValue</tt> operation, the entry is is removed
257: * from the Collection (and the backing map) with the iterator's
258: * <tt>remove</tt> operation, and the saved value is returned. If the
259: * iteration terminates without finding such an entry, <tt>null</tt> is
260: * returned. Note that this implementation requires linear time in the
261: * size of the map; many implementations will override this method.<p>
262: *
263: * Note that this implementation throws an
264: * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt> iterator
265: * does not support the <tt>remove</tt> method and this map contains a
266: * mapping for the specified key.
267: *
268: * @param key key whose mapping is to be removed from the map.
269: * @return previous value associated with specified key, or <tt>null</tt>
270: * if there was no entry for key. (A <tt>null</tt> return can
271: * also indicate that the map previously associated <tt>null</tt>
272: * with the specified key, if the implementation supports
273: * <tt>null</tt> values.)
274: * @throws UnsupportedOperationException if the <tt>remove</tt> operation
275: * is not supported by this map.
276: */
277: public Object remove(Object key) {
278: Iterator i = entrySet().iterator();
279: Entry correctEntry = null;
280: if (key == null) {
281: while (correctEntry == null && i.hasNext()) {
282: Entry e = (Entry) i.next();
283: if (e.getKey() == null)
284: correctEntry = e;
285: }
286: } else {
287: while (correctEntry == null && i.hasNext()) {
288: Entry e = (Entry) i.next();
289: if (key.equals(e.getKey()))
290: correctEntry = e;
291: }
292: }
293:
294: Object oldValue = null;
295: if (correctEntry != null) {
296: oldValue = correctEntry.getValue();
297: i.remove();
298: }
299: return oldValue;
300: }
301:
302: // Bulk Operations
303:
304: /**
305: * Copies all of the mappings from the specified map to this map
306: * (optional operation). These mappings will replace any mappings that
307: * this map had for any of the keys currently in the specified map.<p>
308: *
309: * This implementation iterates over the specified map's
310: * <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt>
311: * operation once for each entry returned by the iteration.<p>
312: *
313: * Note that this implementation throws an
314: * <tt>UnsupportedOperationException</tt> if this map does not support
315: * the <tt>put</tt> operation and the specified map is nonempty.
316: *
317: * @param t mappings to be stored in this map.
318: *
319: * @throws UnsupportedOperationException if the <tt>putAll</tt> operation
320: * is not supported by this map.
321: *
322: * @throws ClassCastException if the class of a key or value in the
323: * specified map prevents it from being stored in this map.
324: *
325: * @throws IllegalArgumentException if some aspect of a key or value in
326: * the specified map prevents it from being stored in this map.
327: * @throws NullPointerException the specified map is <tt>null</tt>, or if
328: * this map does not permit <tt>null</tt> keys or values, and the
329: * specified map contains <tt>null</tt> keys or values.
330: */
331: public void putAll(Map t) {
332: Iterator i = t.entrySet().iterator();
333: while (i.hasNext()) {
334: Entry e = (Entry) i.next();
335: put(e.getKey(), e.getValue());
336: }
337: }
338:
339: /**
340: * Removes all mappings from this map (optional operation). <p>
341: *
342: * This implementation calls <tt>entrySet().clear()</tt>.
343: *
344: * Note that this implementation throws an
345: * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt>
346: * does not support the <tt>clear</tt> operation.
347: *
348: * @throws UnsupportedOperationException clear is not supported
349: * by this map.
350: */
351: public void clear() {
352: entrySet().clear();
353: }
354:
355: // Views
356:
357: /**
358: * Each of these fields are initialized to contain an instance of the
359: * appropriate view the first time this view is requested. The views are
360: * stateless, so there's no reason to create more than one of each.
361: */
362: transient volatile Set keySet = null;
363: transient volatile Collection values = null;
364:
365: /**
366: * Returns a Set view of the keys contained in this map. The Set is
367: * backed by the map, so changes to the map are reflected in the Set,
368: * and vice-versa. (If the map is modified while an iteration over
369: * the Set is in progress, the results of the iteration are undefined.)
370: * The Set supports element removal, which removes the corresponding entry
371: * from the map, via the Iterator.remove, Set.remove, removeAll
372: * retainAll, and clear operations. It does not support the add or
373: * addAll operations.<p>
374: *
375: * This implementation returns a Set that subclasses
376: * AbstractSet. The subclass's iterator method returns a "wrapper
377: * object" over this map's entrySet() iterator. The size method delegates
378: * to this map's size method and the contains method delegates to this
379: * map's containsKey method.<p>
380: *
381: * The Set is created the first time this method is called,
382: * and returned in response to all subsequent calls. No synchronization
383: * is performed, so there is a slight chance that multiple calls to this
384: * method will not all return the same Set.
385: *
386: * @return a Set view of the keys contained in this map.
387: */
388: public Set keySet() {
389: if (keySet == null) {
390: keySet = new AbstractSet() {
391: public Iterator iterator() {
392: return new Iterator() {
393: private Iterator i = entrySet().iterator();
394:
395: public boolean hasNext() {
396: return i.hasNext();
397: }
398:
399: public Object next() {
400: return ((Entry) i.next()).getKey();
401: }
402:
403: public void remove() {
404: i.remove();
405: }
406: };
407: }
408:
409: public int size() {
410: return AbstractMap.this .size();
411: }
412:
413: public boolean contains(Object k) {
414: return AbstractMap.this .containsKey(k);
415: }
416: };
417: }
418: return keySet;
419: }
420:
421: /**
422: * Returns a collection view of the values contained in this map. The
423: * collection is backed by the map, so changes to the map are reflected in
424: * the collection, and vice-versa. (If the map is modified while an
425: * iteration over the collection is in progress, the results of the
426: * iteration are undefined.) The collection supports element removal,
427: * which removes the corresponding entry from the map, via the
428: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
429: * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> operations.
430: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.<p>
431: *
432: * This implementation returns a collection that subclasses abstract
433: * collection. The subclass's iterator method returns a "wrapper object"
434: * over this map's <tt>entrySet()</tt> iterator. The size method
435: * delegates to this map's size method and the contains method delegates
436: * to this map's containsValue method.<p>
437: *
438: * The collection is created the first time this method is called, and
439: * returned in response to all subsequent calls. No synchronization is
440: * performed, so there is a slight chance that multiple calls to this
441: * method will not all return the same Collection.
442: *
443: * @return a collection view of the values contained in this map.
444: */
445: public Collection values() {
446: if (values == null) {
447: values = new AbstractCollection() {
448: public Iterator iterator() {
449: return new Iterator() {
450: private Iterator i = entrySet().iterator();
451:
452: public boolean hasNext() {
453: return i.hasNext();
454: }
455:
456: public Object next() {
457: return ((Entry) i.next()).getValue();
458: }
459:
460: public void remove() {
461: i.remove();
462: }
463: };
464: }
465:
466: public int size() {
467: return AbstractMap.this .size();
468: }
469:
470: public boolean contains(Object v) {
471: return AbstractMap.this .containsValue(v);
472: }
473: };
474: }
475: return values;
476: }
477:
478: /**
479: * Returns a set view of the mappings contained in this map. Each element
480: * in this set is a Map.Entry. The set is backed by the map, so changes
481: * to the map are reflected in the set, and vice-versa. (If the map is
482: * modified while an iteration over the set is in progress, the results of
483: * the iteration are undefined.) The set supports element removal, which
484: * removes the corresponding entry from the map, via the
485: * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
486: * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not support
487: * the <tt>add</tt> or <tt>addAll</tt> operations.
488: *
489: * @return a set view of the mappings contained in this map.
490: */
491: public abstract Set entrySet();
492:
493: // Comparison and hashing
494:
495: /**
496: * Compares the specified object with this map for equality. Returns
497: * <tt>true</tt> if the given object is also a map and the two maps
498: * represent the same mappings. More formally, two maps <tt>t1</tt> and
499: * <tt>t2</tt> represent the same mappings if
500: * <tt>t1.keySet().equals(t2.keySet())</tt> and for every key <tt>k</tt>
501: * in <tt>t1.keySet()</tt>, <tt> (t1.get(k)==null ? t2.get(k)==null :
502: * t1.get(k).equals(t2.get(k))) </tt>. This ensures that the
503: * <tt>equals</tt> method works properly across different implementations
504: * of the map interface.<p>
505: *
506: * This implementation first checks if the specified object is this map;
507: * if so it returns <tt>true</tt>. Then, it checks if the specified
508: * object is a map whose size is identical to the size of this set; if
509: * not, it it returns <tt>false</tt>. If so, it iterates over this map's
510: * <tt>entrySet</tt> collection, and checks that the specified map
511: * contains each mapping that this map contains. If the specified map
512: * fails to contain such a mapping, <tt>false</tt> is returned. If the
513: * iteration completes, <tt>true</tt> is returned.
514: *
515: * @param o object to be compared for equality with this map.
516: * @return <tt>true</tt> if the specified object is equal to this map.
517: */
518: public boolean equals(Object o) {
519: if (o == this )
520: return true;
521:
522: if (!(o instanceof Map))
523: return false;
524: Map t = (Map) o;
525: if (t.size() != size())
526: return false;
527:
528: try {
529: Iterator i = entrySet().iterator();
530: while (i.hasNext()) {
531: Entry e = (Entry) i.next();
532: Object key = e.getKey();
533: Object value = e.getValue();
534: if (value == null) {
535: if (!(t.get(key) == null && t.containsKey(key)))
536: return false;
537: } else {
538: if (!value.equals(t.get(key)))
539: return false;
540: }
541: }
542: } catch (ClassCastException unused) {
543: return false;
544: } catch (NullPointerException unused) {
545: return false;
546: }
547:
548: return true;
549: }
550:
551: /**
552: * Returns the hash code value for this map. The hash code of a map is
553: * defined to be the sum of the hash codes of each entry in the map's
554: * <tt>entrySet()</tt> view. This ensures that <tt>t1.equals(t2)</tt>
555: * implies that <tt>t1.hashCode()==t2.hashCode()</tt> for any two maps
556: * <tt>t1</tt> and <tt>t2</tt>, as required by the general contract of
557: * Object.hashCode.<p>
558: *
559: * This implementation iterates over <tt>entrySet()</tt>, calling
560: * <tt>hashCode</tt> on each element (entry) in the Collection, and adding
561: * up the results.
562: *
563: * @return the hash code value for this map.
564: * @see Map.Entry#hashCode()
565: * @see Object#hashCode()
566: * @see Object#equals(Object)
567: * @see Set#equals(Object)
568: */
569: public int hashCode() {
570: int h = 0;
571: Iterator i = entrySet().iterator();
572: while (i.hasNext())
573: h += i.next().hashCode();
574: return h;
575: }
576:
577: /**
578: * Returns a string representation of this map. The string representation
579: * consists of a list of key-value mappings in the order returned by the
580: * map's <tt>entrySet</tt> view's iterator, enclosed in braces
581: * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters
582: * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as
583: * the key followed by an equals sign (<tt>"="</tt>) followed by the
584: * associated value. Keys and values are converted to strings as by
585: * <tt>String.valueOf(Object)</tt>.<p>
586: *
587: * This implementation creates an empty string buffer, appends a left
588: * brace, and iterates over the map's <tt>entrySet</tt> view, appending
589: * the string representation of each <tt>map.entry</tt> in turn. After
590: * appending each entry except the last, the string <tt>", "</tt> is
591: * appended. Finally a right brace is appended. A string is obtained
592: * from the stringbuffer, and returned.
593: *
594: * @return a String representation of this map.
595: */
596: public String toString() {
597: StringBuffer buf = new StringBuffer();
598: buf.append("{");
599:
600: Iterator i = entrySet().iterator();
601: boolean hasNext = i.hasNext();
602: while (hasNext) {
603: Entry e = (Entry) (i.next());
604: Object key = e.getKey();
605: Object value = e.getValue();
606: buf.append((key == this ? "(this Map)" : key) + "="
607: + (value == this ? "(this Map)" : value));
608:
609: hasNext = i.hasNext();
610: if (hasNext)
611: buf.append(", ");
612: }
613:
614: buf.append("}");
615: return buf.toString();
616: }
617:
618: /**
619: * Returns a shallow copy of this <tt>AbstractMap</tt> instance: the keys
620: * and values themselves are not cloned.
621: *
622: * @return a shallow copy of this map.
623: */
624: protected Object clone() throws CloneNotSupportedException {
625: AbstractMap result = (AbstractMap) super .clone();
626: result.keySet = null;
627: result.values = null;
628: return result;
629: }
630:
631: /**
632: * This should be made public as soon as possible. It greately simplifies
633: * the task of implementing Map.
634: */
635: static class SimpleEntry implements Entry {
636: Object key;
637: Object value;
638:
639: public SimpleEntry(Object key, Object value) {
640: this .key = key;
641: this .value = value;
642: }
643:
644: public SimpleEntry(Map.Entry e) {
645: this .key = e.getKey();
646: this .value = e.getValue();
647: }
648:
649: public Object getKey() {
650: return key;
651: }
652:
653: public Object getValue() {
654: return value;
655: }
656:
657: public Object setValue(Object value) {
658: Object oldValue = this .value;
659: this .value = value;
660: return oldValue;
661: }
662:
663: public boolean equals(Object o) {
664: if (!(o instanceof Map.Entry))
665: return false;
666: Map.Entry e = (Map.Entry) o;
667: return eq(key, e.getKey()) && eq(value, e.getValue());
668: }
669:
670: public int hashCode() {
671: Object v;
672: return ((key == null) ? 0 : key.hashCode())
673: ^ ((value == null) ? 0 : value.hashCode());
674: }
675:
676: public String toString() {
677: return key + "=" + value;
678: }
679:
680: private static boolean eq(Object o1, Object o2) {
681: return (o1 == null ? o2 == null : o1.equals(o2));
682: }
683: }
684: }
|