ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/TreeMap.java

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.15 by jsr166, Wed May 18 01:39:35 2005 UTC vs.
Revision 1.25 by jsr166, Mon Dec 5 02:56:59 2005 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 (till 6280605 is fixed)
10
11		/**
12		* A Red-Black tree based {@link NavigableMap} implementation.
#	Line 30 | Line 31 | package java.util;
31		* <i>is</i> well-defined even if its ordering is inconsistent with equals; it
32		* just fails to obey the general contract of the <tt>Map</tt> interface.
33		*
34	<	* <p><b>Note that this implementation is not synchronized.</b> If multiple
35	<	* threads access a map concurrently, and at least one of the threads modifies
36	<	* the map structurally, it <i>must</i> be synchronized externally.  (A
37	<	* structural modification is any operation that adds or deletes one or more
38	<	* mappings; merely changing the value associated with an existing key is not
39	<	* a structural modification.)  This is typically accomplished by
40	<	* synchronizing on some object that naturally encapsulates the map.  If no
41	<	* such object exists, the map should be "wrapped" using the
42	<	* <tt>Collections.synchronizedMap</tt> method.  This is best done at creation
43	<	* time, to prevent accidental unsynchronized access to the map:
44	<	* <pre>
45	<	*     Map m = Collections.synchronizedMap(new TreeMap(...));
46	<	* </pre>
34	>	* <p><strong>Note that this implementation is not synchronized.</strong>
35	>	* If multiple threads access a map concurrently, and at least one of the
36	>	* threads modifies the map structurally, it <i>must</i> be synchronized
37	>	* externally.  (A structural modification is any operation that adds or
38	>	* deletes one or more mappings; merely changing the value associated
39	>	* with an existing key is not a structural modification.)  This is
40	>	* typically accomplished by synchronizing on some object that naturally
41	>	* encapsulates the map.
42	>	* If no such object exists, the map should be "wrapped" using the
43	>	* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
44	>	* method.  This is best done at creation time, to prevent accidental
45	>	* unsynchronized access to the map: <pre>
46	>	*   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
47		*
48		* <p>The iterators returned by the <tt>iterator</tt> method of the collections
49		* returned by all of this class's "collection view methods" are
#	Line 82 | Line 83 | package java.util;
83		* @see Comparable
84		* @see Comparator
85		* @see Collection
85	–	* @see Collections#synchronizedMap(Map)
86		* @since 1.2
87		*/
88
#	Line 216 | Line 216 | public class TreeMap<K,V>
216		* specified value.  More formally, returns <tt>true</tt> if and only if
217		* this map contains at least one mapping to a value <tt>v</tt> such
218		* that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
219	<	* operation requires time linear in the map size.
219	>	* operation will probably require time linear in the map size for
220	>	* most implementations.
221		*
222		* @param value value whose presence in this map is to be tested
223		* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
#	Line 249 | Line 250 | public class TreeMap<K,V>
250		}
251
252		/**
253	<	* Returns the value to which this map maps the specified key, or
254	<	* <tt>null</tt> if the map contains no mapping for the key.  A return
255	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
256	<	* map contains no mapping for the key; it's also possible that the map
257	<	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey}
258	<	* operation may be used to distinguish these two cases.
259	<	*
260	<	* @param key key whose associated value is to be returned
261	<	* @return the value to which this map maps the specified key, or
262	<	*         <tt>null</tt> if the map contains no mapping for the key
253	>	* Returns the value to which the specified key is mapped,
254	>	* or {@code null} if this map contains no mapping for the key.
255	>	*
256	>	* <p>More formally, if this map contains a mapping from a key
257	>	* {@code k} to a value {@code v} such that {@code key} compares
258	>	* equal to {@code k} according to the map's ordering, then this
259	>	* method returns {@code v}; otherwise it returns {@code null}.
260	>	* (There can be at most one such mapping.)
261	>	*
262	>	* <p>A return value of {@code null} does not <i>necessarily</i>
263	>	* indicate that the map contains no mapping for the key; it's also
264	>	* possible that the map explicitly maps the key to {@code null}.
265	>	* The {@link #containsKey containsKey} operation may be used to
266	>	* distinguish these two cases.
267	>	*
268		* @throws ClassCastException if the specified key cannot be compared
269		*         with the keys currently in the map
270		* @throws NullPointerException if the specified key is null
#	Line 519 | Line 525 | public class TreeMap<K,V>
525
526		/**
527		* Associates the specified value with the specified key in this map.
528	<	* If the map previously contained a mapping for this key, the old
528	>	* If the map previously contained a mapping for the key, the old
529		* value is replaced.
530		*
531		* @param key key with which the specified value is to be associated
#	Line 539 | Line 545 | public class TreeMap<K,V>
545		Entry<K,V> t = root;
546
547		if (t == null) {
548	<	if (key == null) {
549	<	if (comparator == null)
550	<	throw new NullPointerException();
551	<	comparator.compare(key, key);
552	<	}
548	>	// TBD
549	>	//             if (key == null) {
550	>	//                 if (comparator == null)
551	>	//                     throw new NullPointerException();
552	>	//                 comparator.compare(key, key);
553	>	//             }
554		incrementSize();
555		root = new Entry<K,V>(key, value, null);
556		return null;
#	Line 643 | Line 650 | public class TreeMap<K,V>
650
651		// NavigableMap API methods
652
653	+	/**
654	+	* @since 1.6
655	+	*/
656		public Map.Entry<K,V> firstEntry() {
657		Entry<K,V> e = getFirstEntry();
658	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
658	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
659		}
660
661	+	/**
662	+	* @since 1.6
663	+	*/
664		public Map.Entry<K,V> lastEntry() {
665		Entry<K,V> e = getLastEntry();
666	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
666	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
667		}
668
669	+	/**
670	+	* @since 1.6
671	+	*/
672		public Map.Entry<K,V> pollFirstEntry() {
673		Entry<K,V> p = getFirstEntry();
674		if (p == null)
675		return null;
676	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
676	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
677		deleteEntry(p);
678		return result;
679		}
680
681	+	/**
682	+	* @since 1.6
683	+	*/
684		public Map.Entry<K,V> pollLastEntry() {
685		Entry<K,V> p = getLastEntry();
686		if (p == null)
687		return null;
688	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
688	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
689		deleteEntry(p);
690		return result;
691		}
#	Line 676 | Line 695 | public class TreeMap<K,V>
695		* @throws NullPointerException if the specified key is null
696		*         and this map uses natural ordering, or its comparator
697		*         does not permit null keys
698	+	* @since 1.6
699		*/
700		public Map.Entry<K,V> lowerEntry(K key) {
701		Entry<K,V> e =  getLowerEntry(key);
702	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
702	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
703		}
704
705		/**
#	Line 687 | Line 707 | public class TreeMap<K,V>
707		* @throws NullPointerException if the specified key is null
708		*         and this map uses natural ordering, or its comparator
709		*         does not permit null keys
710	+	* @since 1.6
711		*/
712		public K lowerKey(K key) {
713		Entry<K,V> e =  getLowerEntry(key);
#	Line 698 | Line 719 | public class TreeMap<K,V>
719		* @throws NullPointerException if the specified key is null
720		*         and this map uses natural ordering, or its comparator
721		*         does not permit null keys
722	+	* @since 1.6
723		*/
724		public Map.Entry<K,V> floorEntry(K key) {
725		Entry<K,V> e = getFloorEntry(key);
726	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
726	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
727		}
728
729		/**
#	Line 709 | Line 731 | public class TreeMap<K,V>
731		* @throws NullPointerException if the specified key is null
732		*         and this map uses natural ordering, or its comparator
733		*         does not permit null keys
734	+	* @since 1.6
735		*/
736		public K floorKey(K key) {
737		Entry<K,V> e = getFloorEntry(key);
#	Line 720 | Line 743 | public class TreeMap<K,V>
743		* @throws NullPointerException if the specified key is null
744		*         and this map uses natural ordering, or its comparator
745		*         does not permit null keys
746	+	* @since 1.6
747		*/
748		public Map.Entry<K,V> ceilingEntry(K key) {
749		Entry<K,V> e = getCeilingEntry(key);
750	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
750	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
751		}
752
753		/**
#	Line 731 | Line 755 | public class TreeMap<K,V>
755		* @throws NullPointerException if the specified key is null
756		*         and this map uses natural ordering, or its comparator
757		*         does not permit null keys
758	+	* @since 1.6
759		*/
760		public K ceilingKey(K key) {
761		Entry<K,V> e = getCeilingEntry(key);
#	Line 742 | Line 767 | public class TreeMap<K,V>
767		* @throws NullPointerException if the specified key is null
768		*         and this map uses natural ordering, or its comparator
769		*         does not permit null keys
770	+	* @since 1.6
771		*/
772		public Map.Entry<K,V> higherEntry(K key) {
773		Entry<K,V> e = getHigherEntry(key);
774	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
774	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
775		}
776
777		/**
#	Line 753 | Line 779 | public class TreeMap<K,V>
779		* @throws NullPointerException if the specified key is null
780		*         and this map uses natural ordering, or its comparator
781		*         does not permit null keys
782	+	* @since 1.6
783		*/
784		public K higherKey(K key) {
785		Entry<K,V> e = getHigherEntry(key);
#	Line 920 | Line 947 | public class TreeMap<K,V>
947		}
948		}
949
950	+	/**
951	+	* @since 1.6
952	+	*/
953		public Set<Map.Entry<K,V>> descendingEntrySet() {
954		Set<Map.Entry<K,V>> es = descendingEntrySet;
955		return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
#	Line 931 | Line 961 | public class TreeMap<K,V>
961		}
962		}
963
964	+	/**
965	+	* @since 1.6
966	+	*/
967		public Set<K> descendingKeySet() {
968		Set<K> ks = descendingKeySet;
969		return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
#	Line 948 | Line 981 | public class TreeMap<K,V>
981		*         null and this map uses natural ordering, or its comparator
982		*         does not permit null keys
983		* @throws IllegalArgumentException {@inheritDoc}
984	+	* @since 1.6
985		*/
986		public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
987		return new SubMap(fromKey, toKey);
#	Line 959 | Line 993 | public class TreeMap<K,V>
993		*         and this map uses natural ordering, or its comparator
994		*         does not permit null keys
995		* @throws IllegalArgumentException {@inheritDoc}
996	+	* @since 1.6
997		*/
998		public NavigableMap<K,V> navigableHeadMap(K toKey) {
999		return new SubMap(toKey, true);
#	Line 970 | Line 1005 | public class TreeMap<K,V>
1005		*         and this map uses natural ordering, or its comparator
1006		*         does not permit null keys
1007		* @throws IllegalArgumentException {@inheritDoc}
1008	+	* @since 1.6
1009		*/
1010		public NavigableMap<K,V> navigableTailMap(K fromKey) {
1011		return new SubMap(fromKey, false);
#	Line 1066 | Line 1102 | public class TreeMap<K,V>
1102		}
1103
1104		public boolean containsKey(Object key) {
1105	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1105	>	return inRange(key) && TreeMap.this.containsKey(key);
1106		}
1107
1108		public V get(Object key) {
1109	<	if (!inRange((K) key))
1109	>	if (!inRange(key))
1110		return null;
1111		return TreeMap.this.get(key);
1112		}
#	Line 1082 | Line 1118 | public class TreeMap<K,V>
1118		}
1119
1120		public V remove(Object key) {
1121	<	if (!inRange((K) key))
1121	>	if (!inRange(key))
1122		return null;
1123		return TreeMap.this.remove(key);
1124		}
#	Line 1128 | Line 1164 | public class TreeMap<K,V>
1164		getFirstEntry() : getCeilingEntry(fromKey);
1165		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1166		return null;
1167	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1167	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1168		deleteEntry(e);
1169		return result;
1170		}
#	Line 1138 | Line 1174 | public class TreeMap<K,V>
1174		getLastEntry() : getLowerEntry(toKey);
1175		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1176		return null;
1177	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1177	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1178		deleteEntry(e);
1179		return result;
1180		}
#	Line 1153 | Line 1189 | public class TreeMap<K,V>
1189
1190		public Map.Entry<K,V> ceilingEntry(K key) {
1191		TreeMap.Entry<K,V> e = subceiling(key);
1192	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1192	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1193		}
1194
1195		public K ceilingKey(K key) {
#	Line 1172 | Line 1208 | public class TreeMap<K,V>
1208
1209		public Map.Entry<K,V> higherEntry(K key) {
1210		TreeMap.Entry<K,V> e = subhigher(key);
1211	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1211	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1212		}
1213
1214		public K higherKey(K key) {
#	Line 1190 | Line 1226 | public class TreeMap<K,V>
1226
1227		public Map.Entry<K,V> floorEntry(K key) {
1228		TreeMap.Entry<K,V> e = subfloor(key);
1229	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1229	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1230		}
1231
1232		public K floorKey(K key) {
#	Line 1208 | Line 1244 | public class TreeMap<K,V>
1244
1245		public Map.Entry<K,V> lowerEntry(K key) {
1246		TreeMap.Entry<K,V> e = sublower(key);
1247	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1247	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1248		}
1249
1250		public K lowerKey(K key) {
#	Line 1351 | Line 1387 | public class TreeMap<K,V>
1387		return navigableTailMap(fromKey);
1388		}
1389
1390	<	private boolean inRange(K key) {
1390	>	private boolean inRange(Object key) {
1391		return (fromStart || compare(key, fromKey) >= 0) &&
1392		(toEnd     || compare(key, toKey)   <  0);
1393		}
1394
1395		// This form allows the high endpoint (as well as all legit keys)
1396	<	private boolean inRange2(K key) {
1396	>	private boolean inRange2(Object key) {
1397		return (fromStart || compare(key, fromKey) >= 0) &&
1398		(toEnd     || compare(key, toKey)   <= 0);
1399		}
#	Line 1513 | Line 1549 | public class TreeMap<K,V>
1549		/**
1550		* Compares two keys using the correct comparison method for this TreeMap.
1551		*/
1552	<	private int compare(K k1, K k2) {
1553	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1554	<	: comparator.compare(k1, k2);
1552	>	private int compare(Object k1, Object k2) {
1553	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1554	>	: comparator.compare((K)k1, (K)k2);
1555		}
1556
1557		/**
1558	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1558	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1559		* that it copes with <tt>null</tt> o1 properly.
1560		*/
1561		private static boolean valEquals(Object o1, Object o2) {

Diff Legend

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