libjava/java/util/AbstractMap.java

   1 /* AbstractMap.java -- Abstract implementation of most of Map
   2    Copyright (C) 1998, 1999, 2000, 2001, 2002 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    * Remove all entries from this Map (optional operation). This default
  96    * implementation calls entrySet().clear(). NOTE: If the entry set does
  97    * not permit clearing, then this will fail, too. Subclasses often
  98    * override this for efficiency.  Your implementation of entrySet() should
  99    * not call <code>AbstractMap.clear</code> unless you want an infinite loop.
 100    *
 101    * @throws UnsupportedOperationException if <code>entrySet().clear()</code>
 102    *         does not support clearing.
 103    * @see Set#clear()
 104    */
 105   public void clear()
 106   {
 107     entrySet().clear();
 108   }
 109
 110   /**
 111    * Create a shallow copy of this Map, no keys or values are copied. The
 112    * default implementation simply calls <code>super.clone()</code>.
 113    *
 114    * @return the shallow clone
 115    * @throws CloneNotSupportedException if a subclass is not Cloneable
 116    * @see Cloneable
 117    * @see Object#clone()
 118    */
 119   protected Object clone() throws CloneNotSupportedException
 120   {
 121     AbstractMap copy = (AbstractMap) super.clone();
 122     // Clear out the caches; they are stale.
 123     copy.keys = null;
 124     copy.values = null;
 125     return copy;
 126   }
 127
 128   /**
 129    * Returns true if this contains a mapping for the given key. This
 130    * implementation does a linear search, O(n), over the
 131    * <code>entrySet()</code>, returning <code>true</code> if a match
 132    * is found, <code>false</code> if the iteration ends. Many subclasses
 133    * can implement this more efficiently.
 134    *
 135    * @param key the key to search for
 136    * @return true if the map contains the key
 137    * @throws NullPointerException if key is <code>null</code> but the map
 138    *         does not permit null keys
 139    * @see #containsValue(Object)
 140    */
 141   public boolean containsKey(Object key)
 142   {
 143     Iterator entries = entrySet().iterator();
 144     int pos = size();
 145     while (--pos >= 0)
 146       if (equals(key, ((Map.Entry) entries.next()).getKey()))
 147         return true;
 148     return false;
 149   }
 150
 151   /**
 152    * Returns true if this contains at least one mapping with the given value.
 153    * This implementation does a linear search, O(n), over the
 154    * <code>entrySet()</code>, returning <code>true</code> if a match
 155    * is found, <code>false</code> if the iteration ends. A match is
 156    * defined as <code>(value == null ? v == null : value.equals(v))</code>
 157    * Subclasses are unlikely to implement this more efficiently.
 158    *
 159    * @param value the value to search for
 160    * @return true if the map contains the value
 161    * @see #containsKey(Object)
 162    */
 163   public boolean containsValue(Object value)
 164   {
 165     Iterator entries = entrySet().iterator();
 166     int pos = size();
 167     while (--pos >= 0)
 168       if (equals(value, ((Map.Entry) entries.next()).getValue()))
 169         return true;
 170     return false;
 171   }
 172
 173   /**
 174    * Returns a set view of the mappings in this Map.  Each element in the
 175    * set must be an implementation of Map.Entry.  The set is backed by
 176    * the map, so that changes in one show up in the other.  Modifications
 177    * made while an iterator is in progress cause undefined behavior.  If
 178    * the set supports removal, these methods must be valid:
 179    * <code>Iterator.remove</code>, <code>Set.remove</code>,
 180    * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>.
 181    * Element addition is not supported via this set.
 182    *
 183    * @return the entry set
 184    * @see Map.Entry
 185    */
 186   public abstract Set entrySet();
 187
 188   /**
 189    * Compares the specified object with this map for equality. Returns
 190    * <code>true</code> if the other object is a Map with the same mappings,
 191    * that is,<br>
 192    * <code>o instanceof Map && entrySet().equals(((Map) o).entrySet();</code>
 193    *
 194    * @param o the object to be compared
 195    * @return true if the object equals this map
 196    * @see Set#equals(Object)
 197    */
 198   public boolean equals(Object o)
 199   {
 200     return (o == this ||
 201             (o instanceof Map &&
 202              entrySet().equals(((Map) o).entrySet())));
 203   }
 204
 205   /**
 206    * Returns the value mapped by the given key. Returns <code>null</code> if
 207    * there is no mapping.  However, in Maps that accept null values, you
 208    * must rely on <code>containsKey</code> to determine if a mapping exists.
 209    * This iteration takes linear time, searching entrySet().iterator() of
 210    * the key.  Many implementations override this method.
 211    *
 212    * @param key the key to look up
 213    * @return the value associated with the key, or null if key not in map
 214    * @throws NullPointerException if this map does not accept null keys
 215    * @see #containsKey(Object)
 216    */
 217   public Object get(Object key)
 218   {
 219     Iterator entries = entrySet().iterator();
 220     int pos = size();
 221     while (--pos >= 0)
 222       {
 223         Map.Entry entry = (Map.Entry) entries.next();
 224         if (equals(key, entry.getKey()))
 225           return entry.getValue();
 226       }
 227     return null;
 228   }
 229
 230   /**
 231    * Returns the hash code for this map. As defined in Map, this is the sum
 232    * of all hashcodes for each Map.Entry object in entrySet, or basically
 233    * entrySet().hashCode().
 234    *
 235    * @return the hash code
 236    * @see Map.Entry#hashCode()
 237    * @see Set#hashCode()
 238    */
 239   public int hashCode()
 240   {
 241     return entrySet().hashCode();
 242   }
 243
 244   /**
 245    * Returns true if the map contains no mappings. This is implemented by
 246    * <code>size() == 0</code>.
 247    *
 248    * @return true if the map is empty
 249    * @see #size()
 250    */
 251   public boolean isEmpty()
 252   {
 253     return size() == 0;
 254   }
 255
 256   /**
 257    * Returns a set view of this map's keys. The set is backed by the map,
 258    * so changes in one show up in the other. Modifications while an iteration
 259    * is in progress produce undefined behavior. The set supports removal
 260    * if entrySet() does, but does not support element addition.
 261    * <p>
 262    *
 263    * This implementation creates an AbstractSet, where the iterator wraps
 264    * the entrySet iterator, size defers to the Map's size, and contains
 265    * defers to the Map's containsKey. The set is created on first use, and
 266    * returned on subsequent uses, although since no synchronization occurs,
 267    * there is a slight possibility of creating two sets.
 268    *
 269    * @return a Set view of the keys
 270    * @see Set#iterator()
 271    * @see #size()
 272    * @see #containsKey(Object)
 273    * @see #values()
 274    */
 275   public Set keySet()
 276   {
 277     if (keys == null)
 278       keys = new AbstractSet()
 279       {
 280         public int size()
 281         {
 282           return AbstractMap.this.size();
 283         }
 284
 285         public boolean contains(Object key)
 286         {
 287           return containsKey(key);
 288         }
 289
 290         public Iterator iterator()
 291         {
 292           return new Iterator()
 293           {
 294             private final Iterator map_iterator = entrySet().iterator();
 295
 296             public boolean hasNext()
 297             {
 298               return map_iterator.hasNext();
 299             }
 300
 301             public Object next()
 302             {
 303               return ((Map.Entry) map_iterator.next()).getKey();
 304             }
 305
 306             public void remove()
 307             {
 308               map_iterator.remove();
 309             }
 310           };
 311         }
 312       };
 313     return keys;
 314   }
 315
 316   /**
 317    * Associates the given key to the given value (optional operation). If the
 318    * map already contains the key, its value is replaced. This implementation
 319    * simply throws an UnsupportedOperationException. Be aware that in a map
 320    * that permits <code>null</code> values, a null return does not always
 321    * imply that the mapping was created.
 322    *
 323    * @param key the key to map
 324    * @param value the value to be mapped
 325    * @return the previous value of the key, or null if there was no mapping
 326    * @throws UnsupportedOperationException if the operation is not supported
 327    * @throws ClassCastException if the key or value is of the wrong type
 328    * @throws IllegalArgumentException if something about this key or value
 329    *         prevents it from existing in this map
 330    * @throws NullPointerException if the map forbids null keys or values
 331    * @see #containsKey(Object)
 332    */
 333   public Object put(Object key, Object value)
 334   {
 335     throw new UnsupportedOperationException();
 336   }
 337
 338   /**
 339    * Copies all entries of the given map to this one (optional operation). If
 340    * the map already contains a key, its value is replaced. This implementation
 341    * simply iterates over the map's entrySet(), calling <code>put</code>,
 342    * so it is not supported if puts are not.
 343    *
 344    * @param m the mapping to load into this map
 345    * @throws UnsupportedOperationException if the operation is not supported
 346    * @throws ClassCastException if a key or value is of the wrong type
 347    * @throws IllegalArgumentException if something about a key or value
 348    *         prevents it from existing in this map
 349    * @throws NullPointerException if the map forbids null keys or values, or
 350    *         if <code>m</code> is null.
 351    * @see #put(Object, Object)
 352    */
 353   public void putAll(Map m)
 354   {
 355     Iterator entries = m.entrySet().iterator();
 356     int pos = m.size();
 357     while (--pos >= 0)
 358       {
 359         Map.Entry entry = (Map.Entry) entries.next();
 360         put(entry.getKey(), entry.getValue());
 361       }
 362   }
 363
 364   /**
 365    * Removes the mapping for this key if present (optional operation). This
 366    * implementation iterates over the entrySet searching for a matching
 367    * key, at which point it calls the iterator's <code>remove</code> method.
 368    * It returns the result of <code>getValue()</code> on the entry, if found,
 369    * or null if no entry is found. Note that maps which permit null values
 370    * may also return null if the key was removed.  If the entrySet does not
 371    * support removal, this will also fail. This is O(n), so many
 372    * implementations override it for efficiency.
 373    *
 374    * @param key the key to remove
 375    * @return the value the key mapped to, or null if not present
 376    * @throws UnsupportedOperationException if deletion is unsupported
 377    * @see Iterator#remove()
 378    */
 379   public Object remove(Object key)
 380   {
 381     Iterator entries = entrySet().iterator();
 382     int pos = size();
 383     while (--pos >= 0)
 384       {
 385         Map.Entry entry = (Map.Entry) entries.next();
 386         if (equals(key, entry.getKey()))
 387           {
 388             // Must get the value before we remove it from iterator.
 389             Object r = entry.getValue();
 390             entries.remove();
 391             return r;
 392           }
 393       }
 394     return null;
 395   }
 396
 397   /**
 398    * Returns the number of key-value mappings in the map. If there are more
 399    * than Integer.MAX_VALUE mappings, return Integer.MAX_VALUE. This is
 400    * implemented as <code>entrySet().size()</code>.
 401    *
 402    * @return the number of mappings
 403    * @see Set#size()
 404    */
 405   public int size()
 406   {
 407     return entrySet().size();
 408   }
 409
 410   /**
 411    * Returns a String representation of this map. This is a listing of the
 412    * map entries (which are specified in Map.Entry as being
 413    * <code>getKey() + "=" + getValue()</code>), separated by a comma and
 414    * space (", "), and surrounded by braces ('{' and '}'). This implementation
 415    * uses a StringBuffer and iterates over the entrySet to build the String.
 416    * Note that this can fail with an exception if underlying keys or
 417    * values complete abruptly in toString().
 418    *
 419    * @return a String representation
 420    * @see Map.Entry#toString()
 421    */
 422   public String toString()
 423   {
 424     Iterator entries = entrySet().iterator();
 425     StringBuffer r = new StringBuffer("{");
 426     for (int pos = size(); pos > 0; pos--)
 427       {
 428         Map.Entry entry = (Map.Entry) entries.next();
 429         r.append(entry.getKey());
 430         r.append('=');
 431         r.append(entry.getValue());
 432         if (pos > 1)
 433           r.append(", ");
 434       }
 435     r.append("}");
 436     return r.toString();
 437   }
 438
 439   /**
 440    * Returns a collection or bag view of this map's values. The collection
 441    * is backed by the map, so changes in one show up in the other.
 442    * Modifications while an iteration is in progress produce undefined
 443    * behavior. The collection supports removal if entrySet() does, but
 444    * does not support element addition.
 445    * <p>
 446    *
 447    * This implementation creates an AbstractCollection, where the iterator
 448    * wraps the entrySet iterator, size defers to the Map's size, and contains
 449    * defers to the Map's containsValue. The collection is created on first
 450    * use, and returned on subsequent uses, although since no synchronization
 451    * occurs, there is a slight possibility of creating two collections.
 452    *
 453    * @return a Collection view of the values
 454    * @see Collection#iterator()
 455    * @see #size()
 456    * @see #containsValue(Object)
 457    * @see #keySet()
 458    */
 459   public Collection values()
 460   {
 461     if (values == null)
 462       values = new AbstractCollection()
 463       {
 464         public int size()
 465         {
 466           return AbstractMap.this.size();
 467         }
 468
 469         public boolean contains(Object value)
 470         {
 471           return containsValue(value);
 472         }
 473
 474         public Iterator iterator()
 475         {
 476           return new Iterator()
 477           {
 478             private final Iterator map_iterator = entrySet().iterator();
 479
 480             public boolean hasNext()
 481             {
 482               return map_iterator.hasNext();
 483             }
 484
 485             public Object next()
 486             {
 487               return ((Map.Entry) map_iterator.next()).getValue();
 488             }
 489
 490             public void remove()
 491             {
 492               map_iterator.remove();
 493             }
 494           };
 495         }
 496       };
 497     return values;
 498   }
 499
 500   /**
 501    * Compare two objects according to Collection semantics.
 502    *
 503    * @param o1 the first object
 504    * @param o2 the second object
 505    * @return o1 == null ? o2 == null : o1.equals(o2)
 506    */
 507   // Package visible for use throughout java.util.
 508   // It may be inlined since it is final.
 509   static final boolean equals(Object o1, Object o2)
 510   {
 511     return o1 == null ? o2 == null : o1.equals(o2);
 512   }
 513
 514   /**
 515    * Hash an object according to Collection semantics.
 516    *
 517    * @param o the object to hash
 518    * @return o1 == null ? 0 : o1.hashCode()
 519    */
 520   // Package visible for use throughout java.util.
 521   // It may be inlined since it is final.
 522   static final int hashCode(Object o)
 523   {
 524     return o == null ? 0 : o.hashCode();
 525   }
 526
 527   /**
 528    * A class which implements Map.Entry. It is shared by HashMap, TreeMap,
 529    * Hashtable, and Collections. It is not specified by the JDK, but makes
 530    * life much easier.
 531    *
 532    * @author Jon Zeppieri
 533    * @author Eric Blake <ebb9@email.byu.edu>
 534    */
 535   // XXX - FIXME Use fully qualified implements as gcj 3.1 workaround.
 536   static class BasicMapEntry implements Map.Entry
 537   {
 538     /**
 539      * The key. Package visible for direct manipulation.
 540      */
 541     Object key;
 542
 543     /**
 544      * The value. Package visible for direct manipulation.
 545      */
 546     Object value;
 547
 548     /**
 549      * Basic constructor initializes the fields.
 550      * @param newKey the key
 551      * @param newValue the value
 552      */
 553     BasicMapEntry(Object newKey, Object newValue)
 554     {
 555       key = newKey;
 556       value = newValue;
 557     }
 558
 559     /**
 560      * Compares the specified object with this entry. Returns true only if
 561      * the object is a mapping of identical key and value. In other words,
 562      * this must be:<br>
 563      * <pre>(o instanceof Map.Entry)
 564      *       && (getKey() == null ? ((HashMap) o).getKey() == null
 565      *           : getKey().equals(((HashMap) o).getKey()))
 566      *       && (getValue() == null ? ((HashMap) o).getValue() == null
 567      *           : getValue().equals(((HashMap) o).getValue()))</pre>
 568      *
 569      * @param o the object to compare
 570      * @return <code>true</code> if it is equal
 571      */
 572     public final boolean equals(Object o)
 573     {
 574       if (! (o instanceof Map.Entry))
 575         return false;
 576       // Optimize for our own entries.
 577       if (o instanceof BasicMapEntry)
 578         {
 579           BasicMapEntry e = (BasicMapEntry) o;
 580           return (AbstractMap.equals(key, e.key)
 581                   && AbstractMap.equals(value, e.value));
 582         }
 583       Map.Entry e = (Map.Entry) o;
 584       return (AbstractMap.equals(key, e.getKey())
 585               && AbstractMap.equals(value, e.getValue()));
 586     }
 587
 588     /**
 589      * Get the key corresponding to this entry.
 590      *
 591      * @return the key
 592      */
 593     public final Object getKey()
 594     {
 595       return key;
 596     }
 597
 598     /**
 599      * Get the value corresponding to this entry. If you already called
 600      * Iterator.remove(), the behavior undefined, but in this case it works.
 601      *
 602      * @return the value
 603      */
 604     public final Object getValue()
 605     {
 606       return value;
 607     }
 608
 609     /**
 610      * Returns the hash code of the entry.  This is defined as the exclusive-or
 611      * of the hashcodes of the key and value (using 0 for null). In other
 612      * words, this must be:<br>
 613      * <pre>(getKey() == null ? 0 : getKey().hashCode())
 614      *       ^ (getValue() == null ? 0 : getValue().hashCode())</pre>
 615      *
 616      * @return the hash code
 617      */
 618     public final int hashCode()
 619     {
 620       return (AbstractMap.hashCode(key) ^ AbstractMap.hashCode(value));
 621     }
 622
 623     /**
 624      * Replaces the value with the specified object. This writes through
 625      * to the map, unless you have already called Iterator.remove(). It
 626      * may be overridden to restrict a null value.
 627      *
 628      * @param newVal the new value to store
 629      * @return the old value
 630      * @throws NullPointerException if the map forbids null values
 631      */
 632     public Object setValue(Object newVal)
 633     {
 634       Object r = value;
 635       value = newVal;
 636       return r;
 637     }
 638
 639     /**
 640      * This provides a string representation of the entry. It is of the form
 641      * "key=value", where string concatenation is used on key and value.
 642      *
 643      * @return the string representation
 644      */
 645     public final String toString()
 646     {
 647       return key + "=" + value;
 648     }
 649   } // class BasicMapEntry
 650 }