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    }