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