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 }