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.18 by jsr166, Thu Jun 16 02:11:13 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  
8   package java.util;
9 – import java.util.*; // for javadoc
9  
10   /**
11   * A Red-Black tree based {@link NavigableMap} implementation.
# Line 31 | Line 30 | import java.util.*; // for javadoc
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 83 | Line 82 | import java.util.*; // for javadoc
82   * @see Comparable
83   * @see Comparator
84   * @see Collection
86 – * @see Collections#synchronizedMap(Map)
85   * @since 1.2
86   */
87  
# Line 217 | 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 250 | 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 520 | 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 540 | 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 644 | 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 663 | 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 677 | 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 688 | 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 699 | 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 710 | 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 721 | 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 732 | 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 743 | 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 754 | 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 921 | 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 932 | 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 949 | 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 960 | 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 971 | 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 1986 | 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,
1992 <                         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),
1997 <                            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