001 /* AbstractMap.java -- Abstract implementation of most of Map
002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005
003 Free Software Foundation, Inc.
004
005 This file is part of GNU Classpath.
006
007 GNU Classpath is free software; you can redistribute it and/or modify
008 it under the terms of the GNU General Public License as published by
009 the Free Software Foundation; either version 2, or (at your option)
010 any later version.
011
012 GNU Classpath is distributed in the hope that it will be useful, but
013 WITHOUT ANY WARRANTY; without even the implied warranty of
014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 General Public License for more details.
016
017 You should have received a copy of the GNU General Public License
018 along with GNU Classpath; see the file COPYING. If not, write to the
019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020 02110-1301 USA.
021
022 Linking this library statically or dynamically with other modules is
023 making a combined work based on this library. Thus, the terms and
024 conditions of the GNU General Public License cover the whole
025 combination.
026
027 As a special exception, the copyright holders of this library give you
028 permission to link this library with independent modules to produce an
029 executable, regardless of the license terms of these independent
030 modules, and to copy and distribute the resulting executable under
031 terms of your choice, provided that you also meet, for each linked
032 independent module, the terms and conditions of the license of that
033 module. An independent module is a module which is not derived from
034 or based on this library. If you modify this library, you may extend
035 this exception to your version of the library, but you are not
036 obligated to do so. If you do not wish to do so, delete this
037 exception statement from your version. */
038
039
040 package java.util;
041
042 import java.io.Serializable;
043
044 /**
045 * An abstract implementation of Map to make it easier to create your own
046 * implementations. In order to create an unmodifiable Map, subclass
047 * AbstractMap and implement the <code>entrySet</code> (usually via an
048 * AbstractSet). To make it modifiable, also implement <code>put</code>,
049 * and have <code>entrySet().iterator()</code> support <code>remove</code>.
050 * <p>
051 *
052 * It is recommended that classes which extend this support at least the
053 * no-argument constructor, and a constructor which accepts another Map.
054 * Further methods in this class may be overridden if you have a more
055 * efficient implementation.
056 *
057 * @author Original author unknown
058 * @author Bryce McKinlay
059 * @author Eric Blake (ebb9@email.byu.edu)
060 * @see Map
061 * @see Collection
062 * @see HashMap
063 * @see LinkedHashMap
064 * @see TreeMap
065 * @see WeakHashMap
066 * @see IdentityHashMap
067 * @since 1.2
068 * @status updated to 1.4
069 */
070 public abstract class AbstractMap<K, V> implements Map<K, V>
071 {
072 /**
073 * A class containing an immutable key and value. The
074 * implementation of {@link Entry#setValue(V)} for this class
075 * simply throws an {@link UnsupportedOperationException},
076 * thus preventing changes being made. This is useful when
077 * a static thread-safe view of a map is required.
078 *
079 * @since 1.6
080 */
081 public static class SimpleImmutableEntry<K, V>
082 implements Entry<K, V>, Serializable
083 {
084 /**
085 * Compatible with JDK 1.6
086 */
087 private static final long serialVersionUID = 7138329143949025153L;
088
089 K key;
090 V value;
091
092 public SimpleImmutableEntry(K key, V value)
093 {
094 this.key = key;
095 this.value = value;
096 }
097
098 public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry)
099 {
100 this(entry.getKey(), entry.getValue());
101 }
102
103 public K getKey()
104 {
105 return key;
106 }
107
108 public V getValue()
109 {
110 return value;
111 }
112
113 public V setValue(V value)
114 {
115 throw new UnsupportedOperationException("setValue not supported on immutable entry");
116 }
117 }
118
119 /** An "enum" of iterator types. */
120 // Package visible for use by subclasses.
121 static final int KEYS = 0,
122 VALUES = 1,
123 ENTRIES = 2;
124
125 /**
126 * The cache for {@link #keySet()}.
127 */
128 // Package visible for use by subclasses.
129 Set<K> keys;
130
131 /**
132 * The cache for {@link #values()}.
133 */
134 // Package visible for use by subclasses.
135 Collection<V> values;
136
137 /**
138 * The main constructor, for use by subclasses.
139 */
140 protected AbstractMap()
141 {
142 }
143
144 /**
145 * Returns a set view of the mappings in this Map. Each element in the
146 * set must be an implementation of Map.Entry. The set is backed by
147 * the map, so that changes in one show up in the other. Modifications
148 * made while an iterator is in progress cause undefined behavior. If
149 * the set supports removal, these methods must be valid:
150 * <code>Iterator.remove</code>, <code>Set.remove</code>,
151 * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>.
152 * Element addition is not supported via this set.
153 *
154 * @return the entry set
155 * @see Map.Entry
156 */
157 public abstract Set<Map.Entry<K, V>> entrySet();
158
159 /**
160 * Remove all entries from this Map (optional operation). This default
161 * implementation calls entrySet().clear(). NOTE: If the entry set does
162 * not permit clearing, then this will fail, too. Subclasses often
163 * override this for efficiency. Your implementation of entrySet() should
164 * not call <code>AbstractMap.clear</code> unless you want an infinite loop.
165 *
166 * @throws UnsupportedOperationException if <code>entrySet().clear()</code>
167 * does not support clearing.
168 * @see Set#clear()
169 */
170 public void clear()
171 {
172 entrySet().clear();
173 }
174
175 /**
176 * Create a shallow copy of this Map, no keys or values are copied. The
177 * default implementation simply calls <code>super.clone()</code>.
178 *
179 * @return the shallow clone
180 * @throws CloneNotSupportedException if a subclass is not Cloneable
181 * @see Cloneable
182 * @see Object#clone()
183 */
184 protected Object clone() throws CloneNotSupportedException
185 {
186 AbstractMap<K, V> copy = (AbstractMap<K, V>) super.clone();
187 // Clear out the caches; they are stale.
188 copy.keys = null;
189 copy.values = null;
190 return copy;
191 }
192
193 /**
194 * Returns true if this contains a mapping for the given key. This
195 * implementation does a linear search, O(n), over the
196 * <code>entrySet()</code>, returning <code>true</code> if a match
197 * is found, <code>false</code> if the iteration ends. Many subclasses
198 * can implement this more efficiently.
199 *
200 * @param key the key to search for
201 * @return true if the map contains the key
202 * @throws NullPointerException if key is <code>null</code> but the map
203 * does not permit null keys
204 * @see #containsValue(Object)
205 */
206 public boolean containsKey(Object key)
207 {
208 Iterator<Map.Entry<K, V>> entries = entrySet().iterator();
209 int pos = size();
210 while (--pos >= 0)
211 if (equals(key, entries.next().getKey()))
212 return true;
213 return false;
214 }
215
216 /**
217 * Returns true if this contains at least one mapping with the given value.
218 * This implementation does a linear search, O(n), over the
219 * <code>entrySet()</code>, returning <code>true</code> if a match
220 * is found, <code>false</code> if the iteration ends. A match is
221 * defined as a value, v, where <code>(value == null ? v == null :
222 * value.equals(v))</code>. Subclasses are unlikely to implement
223 * this more efficiently.
224 *
225 * @param value the value to search for
226 * @return true if the map contains the value
227 * @see #containsKey(Object)
228 */
229 public boolean containsValue(Object value)
230 {
231 Iterator<Map.Entry<K, V>> entries = entrySet().iterator();
232 int pos = size();
233 while (--pos >= 0)
234 if (equals(value, entries.next().getValue()))
235 return true;
236 return false;
237 }
238
239 /**
240 * Compares the specified object with this map for equality. Returns
241 * <code>true</code> if the other object is a Map with the same mappings,
242 * that is,<br>
243 * <code>o instanceof Map && entrySet().equals(((Map) o).entrySet();</code>
244 *
245 * @param o the object to be compared
246 * @return true if the object equals this map
247 * @see Set#equals(Object)
248 */
249 public boolean equals(Object o)
250 {
251 return (o == this
252 || (o instanceof Map
253 && entrySet().equals(((Map<K, V>) o).entrySet())));
254 }
255
256 /**
257 * Returns the value mapped by the given key. Returns <code>null</code> if
258 * there is no mapping. However, in Maps that accept null values, you
259 * must rely on <code>containsKey</code> to determine if a mapping exists.
260 * This iteration takes linear time, searching entrySet().iterator() of
261 * the key. Many implementations override this method.
262 *
263 * @param key the key to look up
264 * @return the value associated with the key, or null if key not in map
265 * @throws NullPointerException if this map does not accept null keys
266 * @see #containsKey(Object)
267 */
268 public V get(Object key)
269 {
270 Iterator<Map.Entry<K, V>> entries = entrySet().iterator();
271 int pos = size();
272 while (--pos >= 0)
273 {
274 Map.Entry<K, V> entry = entries.next();
275 if (equals(key, entry.getKey()))
276 return entry.getValue();
277 }
278 return null;
279 }
280
281 /**
282 * Returns the hash code for this map. As defined in Map, this is the sum
283 * of all hashcodes for each Map.Entry object in entrySet, or basically
284 * entrySet().hashCode().
285 *
286 * @return the hash code
287 * @see Map.Entry#hashCode()
288 * @see Set#hashCode()
289 */
290 public int hashCode()
291 {
292 return entrySet().hashCode();
293 }
294
295 /**
296 * Returns true if the map contains no mappings. This is implemented by
297 * <code>size() == 0</code>.
298 *
299 * @return true if the map is empty
300 * @see #size()
301 */
302 public boolean isEmpty()
303 {
304 return size() == 0;
305 }
306
307 /**
308 * Returns a set view of this map's keys. The set is backed by the map,
309 * so changes in one show up in the other. Modifications while an iteration
310 * is in progress produce undefined behavior. The set supports removal
311 * if entrySet() does, but does not support element addition.
312 * <p>
313 *
314 * This implementation creates an AbstractSet, where the iterator wraps
315 * the entrySet iterator, size defers to the Map's size, and contains
316 * defers to the Map's containsKey. The set is created on first use, and
317 * returned on subsequent uses, although since no synchronization occurs,
318 * there is a slight possibility of creating two sets.
319 *
320 * @return a Set view of the keys
321 * @see Set#iterator()
322 * @see #size()
323 * @see #containsKey(Object)
324 * @see #values()
325 */
326 public Set<K> keySet()
327 {
328 if (keys == null)
329 keys = new AbstractSet<K>()
330 {
331 /**
332 * Retrieves the number of keys in the backing map.
333 *
334 * @return The number of keys.
335 */
336 public int size()
337 {
338 return AbstractMap.this.size();
339 }
340
341 /**
342 * Returns true if the backing map contains the
343 * supplied key.
344 *
345 * @param key The key to search for.
346 * @return True if the key was found, false otherwise.
347 */
348 public boolean contains(Object key)
349 {
350 return containsKey(key);
351 }
352
353 /**
354 * Returns an iterator which iterates over the keys
355 * in the backing map, using a wrapper around the
356 * iterator returned by <code>entrySet()</code>.
357 *
358 * @return An iterator over the keys.
359 */
360 public Iterator<K> iterator()
361 {
362 return new Iterator<K>()
363 {
364 /**
365 * The iterator returned by <code>entrySet()</code>.
366 */
367 private final Iterator<Map.Entry<K, V>> map_iterator
368 = entrySet().iterator();
369
370 /**
371 * Returns true if a call to <code>next()</code> will
372 * return another key.
373 *
374 * @return True if the iterator has not yet reached
375 * the last key.
376 */
377 public boolean hasNext()
378 {
379 return map_iterator.hasNext();
380 }
381
382 /**
383 * Returns the key from the next entry retrieved
384 * by the underlying <code>entrySet()</code> iterator.
385 *
386 * @return The next key.
387 */
388 public K next()
389 {
390 return map_iterator.next().getKey();
391 }
392
393 /**
394 * Removes the map entry which has a key equal
395 * to that returned by the last call to
396 * <code>next()</code>.
397 *
398 * @throws UnsupportedOperationException if the
399 * map doesn't support removal.
400 */
401 public void remove()
402 {
403 map_iterator.remove();
404 }
405 };
406 }
407 };
408 return keys;
409 }
410
411 /**
412 * Associates the given key to the given value (optional operation). If the
413 * map already contains the key, its value is replaced. This implementation
414 * simply throws an UnsupportedOperationException. Be aware that in a map
415 * that permits <code>null</code> values, a null return does not always
416 * imply that the mapping was created.
417 *
418 * @param key the key to map
419 * @param value the value to be mapped
420 * @return the previous value of the key, or null if there was no mapping
421 * @throws UnsupportedOperationException if the operation is not supported
422 * @throws ClassCastException if the key or value is of the wrong type
423 * @throws IllegalArgumentException if something about this key or value
424 * prevents it from existing in this map
425 * @throws NullPointerException if the map forbids null keys or values
426 * @see #containsKey(Object)
427 */
428 public V put(K key, V value)
429 {
430 throw new UnsupportedOperationException();
431 }
432
433 /**
434 * Copies all entries of the given map to this one (optional operation). If
435 * the map already contains a key, its value is replaced. This implementation
436 * simply iterates over the map's entrySet(), calling <code>put</code>,
437 * so it is not supported if puts are not.
438 *
439 * @param m the mapping to load into this map
440 * @throws UnsupportedOperationException if the operation is not supported
441 * by this map.
442 * @throws ClassCastException if a key or value is of the wrong type for
443 * adding to this map.
444 * @throws IllegalArgumentException if something about a key or value
445 * prevents it from existing in this map.
446 * @throws NullPointerException if the map forbids null keys or values.
447 * @throws NullPointerException if <code>m</code> is null.
448 * @see #put(Object, Object)
449 */
450 public void putAll(Map<? extends K, ? extends V> m)
451 {
452 // FIXME: bogus circumlocution.
453 Iterator entries2 = m.entrySet().iterator();
454 Iterator<Map.Entry<? extends K, ? extends V>> entries
455 = (Iterator<Map.Entry<? extends K, ? extends V>>) entries2;
456 int pos = m.size();
457 while (--pos >= 0)
458 {
459 Map.Entry<? extends K, ? extends V> entry = entries.next();
460 put(entry.getKey(), entry.getValue());
461 }
462 }
463
464 /**
465 * Removes the mapping for this key if present (optional operation). This
466 * implementation iterates over the entrySet searching for a matching
467 * key, at which point it calls the iterator's <code>remove</code> method.
468 * It returns the result of <code>getValue()</code> on the entry, if found,
469 * or null if no entry is found. Note that maps which permit null values
470 * may also return null if the key was removed. If the entrySet does not
471 * support removal, this will also fail. This is O(n), so many
472 * implementations override it for efficiency.
473 *
474 * @param key the key to remove
475 * @return the value the key mapped to, or null if not present.
476 * Null may also be returned if null values are allowed
477 * in the map and the value of this mapping is null.
478 * @throws UnsupportedOperationException if deletion is unsupported
479 * @see Iterator#remove()
480 */
481 public V remove(Object key)
482 {
483 Iterator<Map.Entry<K, V>> entries = entrySet().iterator();
484 int pos = size();
485 while (--pos >= 0)
486 {
487 Map.Entry<K, V> entry = entries.next();
488 if (equals(key, entry.getKey()))
489 {
490 // Must get the value before we remove it from iterator.
491 V r = entry.getValue();
492 entries.remove();
493 return r;
494 }
495 }
496 return null;
497 }
498
499 /**
500 * Returns the number of key-value mappings in the map. If there are more
501 * than Integer.MAX_VALUE mappings, return Integer.MAX_VALUE. This is
502 * implemented as <code>entrySet().size()</code>.
503 *
504 * @return the number of mappings
505 * @see Set#size()
506 */
507 public int size()
508 {
509 return entrySet().size();
510 }
511
512 /**
513 * Returns a String representation of this map. This is a listing of the
514 * map entries (which are specified in Map.Entry as being
515 * <code>getKey() + "=" + getValue()</code>), separated by a comma and
516 * space (", "), and surrounded by braces ('{' and '}'). This implementation
517 * uses a StringBuffer and iterates over the entrySet to build the String.
518 * Note that this can fail with an exception if underlying keys or
519 * values complete abruptly in toString().
520 *
521 * @return a String representation
522 * @see Map.Entry#toString()
523 */
524 public String toString()
525 {
526 Iterator<Map.Entry<K, V>> entries = entrySet().iterator();
527 StringBuffer r = new StringBuffer("{");
528 for (int pos = size(); pos > 0; pos--)
529 {
530 Map.Entry<K, V> entry = entries.next();
531 r.append(entry.getKey());
532 r.append('=');
533 r.append(entry.getValue());
534 if (pos > 1)
535 r.append(", ");
536 }
537 r.append("}");
538 return r.toString();
539 }
540
541 /**
542 * Returns a collection or bag view of this map's values. The collection
543 * is backed by the map, so changes in one show up in the other.
544 * Modifications while an iteration is in progress produce undefined
545 * behavior. The collection supports removal if entrySet() does, but
546 * does not support element addition.
547 * <p>
548 *
549 * This implementation creates an AbstractCollection, where the iterator
550 * wraps the entrySet iterator, size defers to the Map's size, and contains
551 * defers to the Map's containsValue. The collection is created on first
552 * use, and returned on subsequent uses, although since no synchronization
553 * occurs, there is a slight possibility of creating two collections.
554 *
555 * @return a Collection view of the values
556 * @see Collection#iterator()
557 * @see #size()
558 * @see #containsValue(Object)
559 * @see #keySet()
560 */
561 public Collection<V> values()
562 {
563 if (values == null)
564 values = new AbstractCollection<V>()
565 {
566 /**
567 * Returns the number of values stored in
568 * the backing map.
569 *
570 * @return The number of values.
571 */
572 public int size()
573 {
574 return AbstractMap.this.size();
575 }
576
577 /**
578 * Returns true if the backing map contains
579 * the supplied value.
580 *
581 * @param value The value to search for.
582 * @return True if the value was found, false otherwise.
583 */
584 public boolean contains(Object value)
585 {
586 return containsValue(value);
587 }
588
589 /**
590 * Returns an iterator which iterates over the
591 * values in the backing map, by using a wrapper
592 * around the iterator returned by <code>entrySet()</code>.
593 *
594 * @return An iterator over the values.
595 */
596 public Iterator<V> iterator()
597 {
598 return new Iterator<V>()
599 {
600 /**
601 * The iterator returned by <code>entrySet()</code>.
602 */
603 private final Iterator<Map.Entry<K, V>> map_iterator
604 = entrySet().iterator();
605
606 /**
607 * Returns true if a call to <code>next()</call> will
608 * return another value.
609 *
610 * @return True if the iterator has not yet reached
611 * the last value.
612 */
613 public boolean hasNext()
614 {
615 return map_iterator.hasNext();
616 }
617
618 /**
619 * Returns the value from the next entry retrieved
620 * by the underlying <code>entrySet()</code> iterator.
621 *
622 * @return The next value.
623 */
624 public V next()
625 {
626 return map_iterator.next().getValue();
627 }
628
629 /**
630 * Removes the map entry which has a key equal
631 * to that returned by the last call to
632 * <code>next()</code>.
633 *
634 * @throws UnsupportedOperationException if the
635 * map doesn't support removal.
636 */
637 public void remove()
638 {
639 map_iterator.remove();
640 }
641 };
642 }
643 };
644 return values;
645 }
646
647 /**
648 * Compare two objects according to Collection semantics.
649 *
650 * @param o1 the first object
651 * @param o2 the second object
652 * @return o1 == o2 || (o1 != null && o1.equals(o2))
653 */
654 // Package visible for use throughout java.util.
655 // It may be inlined since it is final.
656 static final boolean equals(Object o1, Object o2)
657 {
658 return o1 == o2 || (o1 != null && o1.equals(o2));
659 }
660
661 /**
662 * Hash an object according to Collection semantics.
663 *
664 * @param o the object to hash
665 * @return o1 == null ? 0 : o1.hashCode()
666 */
667 // Package visible for use throughout java.util.
668 // It may be inlined since it is final.
669 static final int hashCode(Object o)
670 {
671 return o == null ? 0 : o.hashCode();
672 }
673
674 /**
675 * A class which implements Map.Entry. It is shared by HashMap, TreeMap,
676 * Hashtable, and Collections. It is not specified by the JDK, but makes
677 * life much easier.
678 *
679 * @author Jon Zeppieri
680 * @author Eric Blake (ebb9@email.byu.edu)
681 *
682 * @since 1.6
683 */
684 public static class SimpleEntry<K, V> implements Entry<K, V>, Serializable
685 {
686
687 /**
688 * Compatible with JDK 1.6
689 */
690 private static final long serialVersionUID = -8499721149061103585L;
691
692 /**
693 * The key. Package visible for direct manipulation.
694 */
695 K key;
696
697 /**
698 * The value. Package visible for direct manipulation.
699 */
700 V value;
701
702 /**
703 * Basic constructor initializes the fields.
704 * @param newKey the key
705 * @param newValue the value
706 */
707 public SimpleEntry(K newKey, V newValue)
708 {
709 key = newKey;
710 value = newValue;
711 }
712
713 public SimpleEntry(Entry<? extends K, ? extends V> entry)
714 {
715 this(entry.getKey(), entry.getValue());
716 }
717
718 /**
719 * Compares the specified object with this entry. Returns true only if
720 * the object is a mapping of identical key and value. In other words,
721 * this must be:<br>
722 * <pre>(o instanceof Map.Entry)
723 * && (getKey() == null ? ((HashMap) o).getKey() == null
724 * : getKey().equals(((HashMap) o).getKey()))
725 * && (getValue() == null ? ((HashMap) o).getValue() == null
726 * : getValue().equals(((HashMap) o).getValue()))</pre>
727 *
728 * @param o the object to compare
729 * @return <code>true</code> if it is equal
730 */
731 public boolean equals(Object o)
732 {
733 if (! (o instanceof Map.Entry))
734 return false;
735 // Optimize for our own entries.
736 if (o instanceof SimpleEntry)
737 {
738 SimpleEntry e = (SimpleEntry) o;
739 return (AbstractMap.equals(key, e.key)
740 && AbstractMap.equals(value, e.value));
741 }
742 Map.Entry e = (Map.Entry) o;
743 return (AbstractMap.equals(key, e.getKey())
744 && AbstractMap.equals(value, e.getValue()));
745 }
746
747 /**
748 * Get the key corresponding to this entry.
749 *
750 * @return the key
751 */
752 public K getKey()
753 {
754 return key;
755 }
756
757 /**
758 * Get the value corresponding to this entry. If you already called
759 * Iterator.remove(), the behavior undefined, but in this case it works.
760 *
761 * @return the value
762 */
763 public V getValue()
764 {
765 return value;
766 }
767
768 /**
769 * Returns the hash code of the entry. This is defined as the exclusive-or
770 * of the hashcodes of the key and value (using 0 for null). In other
771 * words, this must be:<br>
772 * <pre>(getKey() == null ? 0 : getKey().hashCode())
773 * ^ (getValue() == null ? 0 : getValue().hashCode())</pre>
774 *
775 * @return the hash code
776 */
777 public int hashCode()
778 {
779 return (AbstractMap.hashCode(key) ^ AbstractMap.hashCode(value));
780 }
781
782 /**
783 * Replaces the value with the specified object. This writes through
784 * to the map, unless you have already called Iterator.remove(). It
785 * may be overridden to restrict a null value.
786 *
787 * @param newVal the new value to store
788 * @return the old value
789 * @throws NullPointerException if the map forbids null values.
790 * @throws UnsupportedOperationException if the map doesn't support
791 * <code>put()</code>.
792 * @throws ClassCastException if the value is of a type unsupported
793 * by the map.
794 * @throws IllegalArgumentException if something else about this
795 * value prevents it being stored in the map.
796 */
797 public V setValue(V newVal)
798 {
799 V r = value;
800 value = newVal;
801 return r;
802 }
803
804 /**
805 * This provides a string representation of the entry. It is of the form
806 * "key=value", where string concatenation is used on key and value.
807 *
808 * @return the string representation
809 */
810 public String toString()
811 {
812 return key + "=" + value;
813 }
814 } // class SimpleEntry
815
816
817 }