ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/TreeMap.java
(Generate patch)

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.16 by dl, Wed May 25 14:05:06 2005 UTC vs.
Revision 1.27 by jsr166, Sun Mar 19 18:03:54 2006 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
# Line 30 | Line 30 | package java.util;
30   * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
31   * just fails to obey the general contract of the <tt>Map</tt> interface.
32   *
33 < * <p><b>Note that this implementation is not synchronized.</b> If multiple
34 < * threads access a map concurrently, and at least one of the threads modifies
35 < * the map structurally, it <i>must</i> be synchronized externally.  (A
36 < * structural modification is any operation that adds or deletes one or more
37 < * mappings; merely changing the value associated with an existing key is not
38 < * a structural modification.)  This is typically accomplished by
39 < * synchronizing on some object that naturally encapsulates the map.  If no
40 < * such object exists, the map should be "wrapped" using the
41 < * <tt>Collections.synchronizedMap</tt> method.  This is best done at creation
42 < * time, to prevent accidental unsynchronized access to the map:
43 < * <pre>
44 < *     Map m = Collections.synchronizedMap(new TreeMap(...));
45 < * </pre>
33 > * <p><strong>Note that this implementation is not synchronized.</strong>
34 > * If multiple threads access a map concurrently, and at least one of the
35 > * threads modifies the map structurally, it <i>must</i> be synchronized
36 > * externally.  (A structural modification is any operation that adds or
37 > * deletes one or more mappings; merely changing the value associated
38 > * with an existing key is not a structural modification.)  This is
39 > * typically accomplished by synchronizing on some object that naturally
40 > * encapsulates the map.
41 > * If no such object exists, the map should be "wrapped" using the
42 > * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
43 > * method.  This is best done at creation time, to prevent accidental
44 > * unsynchronized access to the map: <pre>
45 > *   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
46   *
47   * <p>The iterators returned by the <tt>iterator</tt> method of the collections
48   * returned by all of this class's "collection view methods" are
# Line 82 | Line 82 | package java.util;
82   * @see Comparable
83   * @see Comparator
84   * @see Collection
85 – * @see Collections#synchronizedMap(Map)
85   * @since 1.2
86   */
87  
# Line 216 | Line 215 | public class TreeMap<K,V>
215       * specified value.  More formally, returns <tt>true</tt> if and only if
216       * this map contains at least one mapping to a value <tt>v</tt> such
217       * that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
218 <     * operation requires time linear in the map size.
218 >     * operation will probably require time linear in the map size for
219 >     * most implementations.
220       *
221       * @param value value whose presence in this map is to be tested
222       * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
# Line 249 | Line 249 | public class TreeMap<K,V>
249      }
250  
251      /**
252 <     * Returns the value to which this map maps the specified key, or
253 <     * <tt>null</tt> if the map contains no mapping for the key.  A return
254 <     * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
255 <     * map contains no mapping for the key; it's also possible that the map
256 <     * explicitly maps the key to <tt>null</tt>.  The {@link #containsKey}
257 <     * operation may be used to distinguish these two cases.
258 <     *
259 <     * @param key key whose associated value is to be returned
260 <     * @return the value to which this map maps the specified key, or
261 <     *         <tt>null</tt> if the map contains no mapping for the key
252 >     * Returns the value to which the specified key is mapped,
253 >     * or {@code null} if this map contains no mapping for the key.
254 >     *
255 >     * <p>More formally, if this map contains a mapping from a key
256 >     * {@code k} to a value {@code v} such that {@code key} compares
257 >     * equal to {@code k} according to the map's ordering, then this
258 >     * method returns {@code v}; otherwise it returns {@code null}.
259 >     * (There can be at most one such mapping.)
260 >     *
261 >     * <p>A return value of {@code null} does not <i>necessarily</i>
262 >     * indicate that the map contains no mapping for the key; it's also
263 >     * possible that the map explicitly maps the key to {@code null}.
264 >     * The {@link #containsKey containsKey} operation may be used to
265 >     * distinguish these two cases.
266 >     *
267       * @throws ClassCastException if the specified key cannot be compared
268       *         with the keys currently in the map
269       * @throws NullPointerException if the specified key is null
# Line 519 | Line 524 | public class TreeMap<K,V>
524  
525      /**
526       * Associates the specified value with the specified key in this map.
527 <     * If the map previously contained a mapping for this key, the old
527 >     * If the map previously contained a mapping for the key, the old
528       * value is replaced.
529       *
530       * @param key key with which the specified value is to be associated
# Line 539 | Line 544 | public class TreeMap<K,V>
544          Entry<K,V> t = root;
545  
546          if (t == null) {
547 <            if (key == null) {
548 <                if (comparator == null)
549 <                    throw new NullPointerException();
550 <                comparator.compare(key, key);
551 <            }
547 >            // TBD
548 > //             if (key == null) {
549 > //                 if (comparator == null)
550 > //                     throw new NullPointerException();
551 > //                 comparator.compare(key, key);
552 > //             }
553              incrementSize();
554              root = new Entry<K,V>(key, value, null);
555              return null;
# Line 643 | Line 649 | public class TreeMap<K,V>
649  
650      // NavigableMap API methods
651  
652 +    /**
653 +     * @since 1.6
654 +     */
655      public Map.Entry<K,V> firstEntry() {
656          Entry<K,V> e = getFirstEntry();
657          return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
658      }
659  
660 +    /**
661 +     * @since 1.6
662 +     */
663      public Map.Entry<K,V> lastEntry() {
664          Entry<K,V> e = getLastEntry();
665          return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
666      }
667  
668 +    /**
669 +     * @since 1.6
670 +     */
671      public Map.Entry<K,V> pollFirstEntry() {
672          Entry<K,V> p = getFirstEntry();
673          if (p == null)
# Line 662 | Line 677 | public class TreeMap<K,V>
677          return result;
678      }
679  
680 +    /**
681 +     * @since 1.6
682 +     */
683      public Map.Entry<K,V> pollLastEntry() {
684          Entry<K,V> p = getLastEntry();
685          if (p == null)
# Line 676 | Line 694 | public class TreeMap<K,V>
694       * @throws NullPointerException if the specified key is null
695       *         and this map uses natural ordering, or its comparator
696       *         does not permit null keys
697 +     * @since 1.6
698       */
699      public Map.Entry<K,V> lowerEntry(K key) {
700          Entry<K,V> e =  getLowerEntry(key);
# Line 687 | Line 706 | public class TreeMap<K,V>
706       * @throws NullPointerException if the specified key is null
707       *         and this map uses natural ordering, or its comparator
708       *         does not permit null keys
709 +     * @since 1.6
710       */
711      public K lowerKey(K key) {
712          Entry<K,V> e =  getLowerEntry(key);
# Line 698 | Line 718 | public class TreeMap<K,V>
718       * @throws NullPointerException if the specified key is null
719       *         and this map uses natural ordering, or its comparator
720       *         does not permit null keys
721 +     * @since 1.6
722       */
723      public Map.Entry<K,V> floorEntry(K key) {
724          Entry<K,V> e = getFloorEntry(key);
# Line 709 | Line 730 | public class TreeMap<K,V>
730       * @throws NullPointerException if the specified key is null
731       *         and this map uses natural ordering, or its comparator
732       *         does not permit null keys
733 +     * @since 1.6
734       */
735      public K floorKey(K key) {
736          Entry<K,V> e = getFloorEntry(key);
# Line 720 | Line 742 | public class TreeMap<K,V>
742       * @throws NullPointerException if the specified key is null
743       *         and this map uses natural ordering, or its comparator
744       *         does not permit null keys
745 +     * @since 1.6
746       */
747      public Map.Entry<K,V> ceilingEntry(K key) {
748          Entry<K,V> e = getCeilingEntry(key);
# Line 731 | Line 754 | public class TreeMap<K,V>
754       * @throws NullPointerException if the specified key is null
755       *         and this map uses natural ordering, or its comparator
756       *         does not permit null keys
757 +     * @since 1.6
758       */
759      public K ceilingKey(K key) {
760          Entry<K,V> e = getCeilingEntry(key);
# Line 742 | Line 766 | public class TreeMap<K,V>
766       * @throws NullPointerException if the specified key is null
767       *         and this map uses natural ordering, or its comparator
768       *         does not permit null keys
769 +     * @since 1.6
770       */
771      public Map.Entry<K,V> higherEntry(K key) {
772          Entry<K,V> e = getHigherEntry(key);
# Line 753 | Line 778 | public class TreeMap<K,V>
778       * @throws NullPointerException if the specified key is null
779       *         and this map uses natural ordering, or its comparator
780       *         does not permit null keys
781 +     * @since 1.6
782       */
783      public K higherKey(K key) {
784          Entry<K,V> e = getHigherEntry(key);
# Line 920 | Line 946 | public class TreeMap<K,V>
946          }
947      }
948  
949 +    /**
950 +     * @since 1.6
951 +     */
952      public Set<Map.Entry<K,V>> descendingEntrySet() {
953          Set<Map.Entry<K,V>> es = descendingEntrySet;
954          return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
# Line 931 | Line 960 | public class TreeMap<K,V>
960          }
961      }
962  
963 +    /**
964 +     * @since 1.6
965 +     */
966      public Set<K> descendingKeySet() {
967          Set<K> ks = descendingKeySet;
968          return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
# Line 948 | Line 980 | public class TreeMap<K,V>
980       *         null and this map uses natural ordering, or its comparator
981       *         does not permit null keys
982       * @throws IllegalArgumentException {@inheritDoc}
983 +     * @since 1.6
984       */
985      public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
986          return new SubMap(fromKey, toKey);
# Line 959 | Line 992 | public class TreeMap<K,V>
992       *         and this map uses natural ordering, or its comparator
993       *         does not permit null keys
994       * @throws IllegalArgumentException {@inheritDoc}
995 +     * @since 1.6
996       */
997      public NavigableMap<K,V> navigableHeadMap(K toKey) {
998          return new SubMap(toKey, true);
# Line 970 | Line 1004 | public class TreeMap<K,V>
1004       *         and this map uses natural ordering, or its comparator
1005       *         does not permit null keys
1006       * @throws IllegalArgumentException {@inheritDoc}
1007 +     * @since 1.6
1008       */
1009      public NavigableMap<K,V> navigableTailMap(K fromKey) {
1010          return new SubMap(fromKey, false);
# Line 1066 | Line 1101 | public class TreeMap<K,V>
1101          }
1102  
1103          public boolean containsKey(Object key) {
1104 <            return inRange((K) key) && TreeMap.this.containsKey(key);
1104 >            return inRange(key) && TreeMap.this.containsKey(key);
1105          }
1106  
1107          public V get(Object key) {
1108 <            if (!inRange((K) key))
1108 >            if (!inRange(key))
1109                  return null;
1110              return TreeMap.this.get(key);
1111          }
# Line 1082 | Line 1117 | public class TreeMap<K,V>
1117          }
1118  
1119          public V remove(Object key) {
1120 <            if (!inRange((K) key))
1120 >            if (!inRange(key))
1121                  return null;
1122              return TreeMap.this.remove(key);
1123          }
# Line 1351 | Line 1386 | public class TreeMap<K,V>
1386              return navigableTailMap(fromKey);
1387          }
1388  
1389 <        private boolean inRange(K key) {
1389 >        private boolean inRange(Object key) {
1390              return (fromStart || compare(key, fromKey) >= 0) &&
1391                     (toEnd     || compare(key, toKey)   <  0);
1392          }
1393  
1394          // This form allows the high endpoint (as well as all legit keys)
1395 <        private boolean inRange2(K key) {
1395 >        private boolean inRange2(Object key) {
1396              return (fromStart || compare(key, fromKey) >= 0) &&
1397                     (toEnd     || compare(key, toKey)   <= 0);
1398          }
# Line 1519 | Line 1554 | public class TreeMap<K,V>
1554      }
1555  
1556      /**
1557 <     * Test two values  for equality.  Differs from o1.equals(o2) only in
1557 >     * Test two values for equality.  Differs from o1.equals(o2) only in
1558       * that it copes with <tt>null</tt> o1 properly.
1559       */
1560      private static boolean valEquals(Object o1, Object o2) {
# Line 1985 | Line 2020 | public class TreeMap<K,V>
2020       * @throws ClassNotFoundException propagated from readObject.
2021       *         This cannot occur if str is null.
2022       */
2023 <    private
2024 <    void buildFromSorted(int size, Iterator it,
2025 <                         java.io.ObjectInputStream str,
1991 <                         V defaultVal)
2023 >    private void buildFromSorted(int size, Iterator it,
2024 >                                 java.io.ObjectInputStream str,
2025 >                                 V defaultVal)
2026          throws  java.io.IOException, ClassNotFoundException {
2027          this.size = size;
2028 <        root =
2029 <            buildFromSorted(0, 0, size-1, computeRedLevel(size),
1996 <                            it, str, defaultVal);
2028 >        root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2029 >                               it, str, defaultVal);
2030      }
2031  
2032      /**
2033       * Recursive "helper method" that does the real work of the
2034 <     * of the previous method.  Identically named parameters have
2034 >     * previous method.  Identically named parameters have
2035       * identical definitions.  Additional parameters are documented below.
2036       * It is assumed that the comparator and size fields of the TreeMap are
2037       * already set prior to calling this method.  (It ignores both fields.)

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines