libjava/java/util/AbstractMap.java

   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., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 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 == null ? o2 == 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 == null ? o2 == 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 }