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.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(e);
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(e);
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)
674		return null;
675	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
675	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
676		deleteEntry(p);
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)
686		return null;
687	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
687	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
688		deleteEntry(p);
689		return result;
690		}
#	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);
701	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
701	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
702		}
703
704		/**
#	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);
725	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
725	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
726		}
727
728		/**
#	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);
749	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
749	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
750		}
751
752		/**
#	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);
773	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
773	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
774		}
775
776		/**
#	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 1128 | Line 1163 | public class TreeMap<K,V>
1163		getFirstEntry() : getCeilingEntry(fromKey);
1164		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1165		return null;
1166	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1166	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1167		deleteEntry(e);
1168		return result;
1169		}
#	Line 1138 | Line 1173 | public class TreeMap<K,V>
1173		getLastEntry() : getLowerEntry(toKey);
1174		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1175		return null;
1176	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1176	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1177		deleteEntry(e);
1178		return result;
1179		}
#	Line 1153 | Line 1188 | public class TreeMap<K,V>
1188
1189		public Map.Entry<K,V> ceilingEntry(K key) {
1190		TreeMap.Entry<K,V> e = subceiling(key);
1191	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1191	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1192		}
1193
1194		public K ceilingKey(K key) {
#	Line 1172 | Line 1207 | public class TreeMap<K,V>
1207
1208		public Map.Entry<K,V> higherEntry(K key) {
1209		TreeMap.Entry<K,V> e = subhigher(key);
1210	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1210	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1211		}
1212
1213		public K higherKey(K key) {
#	Line 1190 | Line 1225 | public class TreeMap<K,V>
1225
1226		public Map.Entry<K,V> floorEntry(K key) {
1227		TreeMap.Entry<K,V> e = subfloor(key);
1228	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1228	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1229		}
1230
1231		public K floorKey(K key) {
#	Line 1208 | Line 1243 | public class TreeMap<K,V>
1243
1244		public Map.Entry<K,V> lowerEntry(K key) {
1245		TreeMap.Entry<K,V> e = sublower(key);
1246	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1246	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1247		}
1248
1249		public K lowerKey(K key) {
#	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 1513 | Line 1548 | public class TreeMap<K,V>
1548		/**
1549		* Compares two keys using the correct comparison method for this TreeMap.
1550		*/
1551	<	private int compare(K k1, K k2) {
1552	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1553	<	: comparator.compare(k1, k2);
1551	>	private int compare(Object k1, Object k2) {
1552	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1553	>	: comparator.compare((K)k1, (K)k2);
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