1: /* AbstractMap.java -- Abstract implementation of most of Map 2: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 3: Free Software Foundation, Inc. 4: 5: This file is part of GNU Classpath. 6: 7: GNU Classpath is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU Classpath is distributed in the hope that it will be useful, but 13: WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15: General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU Classpath; see the file COPYING. If not, write to the 19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20: 02110-1301 USA. 21: 22: Linking this library statically or dynamically with other modules is 23: making a combined work based on this library. Thus, the terms and 24: conditions of the GNU General Public License cover the whole 25: combination. 26: 27: As a special exception, the copyright holders of this library give you 28: permission to link this library with independent modules to produce an 29: executable, regardless of the license terms of these independent 30: modules, and to copy and distribute the resulting executable under 31: terms of your choice, provided that you also meet, for each linked 32: independent module, the terms and conditions of the license of that 33: module. An independent module is a module which is not derived from 34: or based on this library. If you modify this library, you may extend 35: this exception to your version of the library, but you are not 36: obligated to do so. If you do not wish to do so, delete this 37: exception statement from your version. */ 38: 39: 40: package java.util; 41: 42: import java.io.Serializable; 43: 44: /** 45: * An abstract implementation of Map to make it easier to create your own 46: * implementations. In order to create an unmodifiable Map, subclass 47: * AbstractMap and implement the <code>entrySet</code> (usually via an 48: * AbstractSet). To make it modifiable, also implement <code>put</code>, 49: * and have <code>entrySet().iterator()</code> support <code>remove</code>. 50: * <p> 51: * 52: * It is recommended that classes which extend this support at least the 53: * no-argument constructor, and a constructor which accepts another Map. 54: * Further methods in this class may be overridden if you have a more 55: * efficient implementation. 56: * 57: * @author Original author unknown 58: * @author Bryce McKinlay 59: * @author Eric Blake (ebb9@email.byu.edu) 60: * @see Map 61: * @see Collection 62: * @see HashMap 63: * @see LinkedHashMap 64: * @see TreeMap 65: * @see WeakHashMap 66: * @see IdentityHashMap 67: * @since 1.2 68: * @status updated to 1.4 69: */ 70: public abstract class AbstractMap<K, V> implements Map<K, V> 71: { 72: /** 73: * A class containing an immutable key and value. The 74: * implementation of {@link Entry#setValue(V)} for this class 75: * simply throws an {@link UnsupportedOperationException}, 76: * thus preventing changes being made. This is useful when 77: * a static thread-safe view of a map is required. 78: * 79: * @since 1.6 80: */ 81: public static class SimpleImmutableEntry<K, V> 82: implements Entry<K, V>, Serializable 83: { 84: /** 85: * Compatible with JDK 1.6 86: */ 87: private static final long serialVersionUID = 7138329143949025153L; 88: 89: K key; 90: V value; 91: 92: public SimpleImmutableEntry(K key, V value) 93: { 94: this.key = key; 95: this.value = value; 96: } 97: 98: public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) 99: { 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: }