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.13 by dl, Wed May 11 11:16:08 2005 UTC vs.
Revision 1.21 by jsr166, Fri Jun 24 00:26:57 2005 UTC

#	Line 6 | Line 6
6		*/
7
8		package java.util;
9	<
9	>	import java.util.*; // for javadoc (till 6280605 is fixed)
10
11		/**
12	<	* Red-Black tree based implementation of the <tt>NavigableMap</tt> interface.
13	<	* This class guarantees that the map will be in ascending key order, sorted
14	<	* according to the <i>natural order</i> for the keys' class (see
15	<	* <tt>Comparable</tt>), or by the comparator provided at creation time,
16	<	* depending on which constructor is used.<p>
12	>	* A Red-Black tree based {@link NavigableMap} implementation.
13	>	* The map is sorted according to the {@linkplain Comparable natural
14	>	* ordering} of its keys, or by a {@link Comparator} provided at map
15	>	* creation time, depending on which constructor is used.
16		*
17	<	* This implementation provides guaranteed log(n) time cost for the
17	>	* <p>This implementation provides guaranteed log(n) time cost for the
18		* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
19		* operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
20	<	* Rivest's <I>Introduction to Algorithms</I>.<p>
20	>	* Rivest's <I>Introduction to Algorithms</I>.
21		*
22	<	* Note that the ordering maintained by a sorted map (whether or not an
22	>	* <p>Note that the ordering maintained by a sorted map (whether or not an
23		* explicit comparator is provided) must be <i>consistent with equals</i> if
24		* this sorted map is to correctly implement the <tt>Map</tt> interface.  (See
25		* <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
#	Line 30 | Line 29 | package java.util;
29		* method, so two keys that are deemed equal by this method are, from the
30		* standpoint of the sorted map, equal.  The behavior of a sorted map
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.<p>
32	>	* just fails to obey the general contract of the <tt>Map</tt> interface.
33		*
34	<	* <b>Note that this implementation is not synchronized.</b> If multiple
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
#	Line 44 | Line 43 | package java.util;
43		* time, to prevent accidental unsynchronized access to the map:
44		* <pre>
45		*     Map m = Collections.synchronizedMap(new TreeMap(...));
46	<	* </pre><p>
46	>	* </pre>
47		*
48	<	* The iterators returned by all of this class's "collection view methods" are
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
50		* <i>fail-fast</i>: if the map is structurally modified at any time after the
51		* iterator is created, in any way except through the iterator's own
52	<	* <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
53	<	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of concurrent
52	>	* <tt>remove</tt> method, the iterator will throw a {@link
53	>	* ConcurrentModificationException}.  Thus, in the face of concurrent
54		* modification, the iterator fails quickly and cleanly, rather than risking
55	<	* arbitrary, non-deterministic behavior at an undetermined time in the
56	<	* future.
55	>	* arbitrary, non-deterministic behavior at an undetermined time in the future.
56		*
57		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
58		* as it is, generally speaking, impossible to make any hard guarantees in the
#	Line 73 | Line 72 | package java.util;
72		* <a href="{@docRoot}/../guide/collections/index.html">
73		* Java Collections Framework</a>.
74		*
75	+	* @param <K> the type of keys maintained by this map
76	+	* @param <V> the type of mapped values
77	+	*
78		* @author  Josh Bloch and Doug Lea
79		* @version %I%, %G%
80		* @see Map
#	Line 90 | Line 92 | public class TreeMap<K,V>
92		implements NavigableMap<K,V>, Cloneable, java.io.Serializable
93		{
94		/**
95	<	* The Comparator used to maintain order in this TreeMap, or
96	<	* null if this TreeMap uses its elements natural ordering.
95	>	* The comparator used to maintain order in this tree map, or
96	>	* null if it uses the natural ordering of its keys.
97		*
98		* @serial
99		*/
#	Line 113 | Line 115 | public class TreeMap<K,V>
115		private void decrementSize()   { modCount++; size--; }
116
117		/**
118	<	* Constructs a new, empty map, sorted according to the keys' natural
119	<	* order.  All keys inserted into the map must implement the
120	<	* <tt>Comparable</tt> interface.  Furthermore, all such keys must be
121	<	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
122	<	* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
123	<	* map.  If the user attempts to put a key into the map that violates this
124	<	* constraint (for example, the user attempts to put a string key into a
125	<	* map whose keys are integers), the <tt>put(Object key, Object
126	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
127	<	*
126	<	* @see Comparable
118	>	* Constructs a new, empty tree map, using the natural ordering of its
119	>	* keys.  All keys inserted into the map must implement the {@link
120	>	* Comparable} interface.  Furthermore, all such keys must be
121	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
122	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
123	>	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
124	>	* map that violates this constraint (for example, the user attempts to
125	>	* put a string key into a map whose keys are integers), the
126	>	* <tt>put(Object key, Object value)</tt> call will throw a
127	>	* <tt>ClassCastException</tt>.
128		*/
129		public TreeMap() {
130		}
131
132		/**
133	<	* Constructs a new, empty map, sorted according to the given comparator.
134	<	* All keys inserted into the map must be <i>mutually comparable</i> by
135	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
136	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
137	<	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
138	<	* map that violates this constraint, the <tt>put(Object key, Object
139	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
140	<	*
141	<	* @param c the comparator that will be used to sort this map.  A
142	<	*        <tt>null</tt> value indicates that the keys' <i>natural
143	<	*        ordering</i> should be used.
144	<	*/
145	<	public TreeMap(Comparator<? super K> c) {
146	<	this.comparator = c;
133	>	* Constructs a new, empty tree map, ordered according to the given
134	>	* comparator.  All keys inserted into the map must be <i>mutually
135	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
136	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
137	>	* <tt>k1</tt> and <tt>k2</tt> in the map.  If the user attempts to put
138	>	* a key into the map that violates this constraint, the <tt>put(Object
139	>	* key, Object value)</tt> call will throw a
140	>	* <tt>ClassCastException</tt>.
141	>	*
142	>	* @param comparator the comparator that will be used to order this map.
143	>	*        If <tt>null</tt>, the {@linkplain Comparable natural
144	>	*        ordering} of the keys will be used.
145	>	*/
146	>	public TreeMap(Comparator<? super K> comparator) {
147	>	this.comparator = comparator;
148		}
149
150		/**
151	<	* Constructs a new map containing the same mappings as the given map,
152	<	* sorted according to the keys' <i>natural order</i>.  All keys inserted
153	<	* into the new map must implement the <tt>Comparable</tt> interface.
154	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
155	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
156	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
157	<	* runs in n*log(n) time.
158	<	*
159	<	* @param  m the map whose mappings are to be placed in this map.
160	<	* @throws ClassCastException the keys in t are not Comparable, or
161	<	*         are not mutually comparable.
162	<	* @throws NullPointerException if the specified map is null.
151	>	* Constructs a new tree map containing the same mappings as the given
152	>	* map, ordered according to the <i>natural ordering</i> of its keys.
153	>	* All keys inserted into the new map must implement the {@link
154	>	* Comparable} interface.  Furthermore, all such keys must be
155	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
156	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
157	>	* <tt>k2</tt> in the map.  This method runs in n*log(n) time.
158	>	*
159	>	* @param  m the map whose mappings are to be placed in this map
160	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
161	>	*         or are not mutually comparable
162	>	* @throws NullPointerException if the specified map is null
163		*/
164		public TreeMap(Map<? extends K, ? extends V> m) {
165		putAll(m);
166		}
167
168		/**
169	<	* Constructs a new map containing the same mappings as the given
170	<	* <tt>SortedMap</tt>, sorted according to the same ordering.  This method
171	<	* runs in linear time.
169	>	* Constructs a new tree map containing the same mappings and
170	>	* using the same ordering as the specified sorted map.  This
171	>	* method runs in linear time.
172		*
173		* @param  m the sorted map whose mappings are to be placed in this map,
174	<	*         and whose comparator is to be used to sort this map.
175	<	* @throws NullPointerException if the specified sorted map is null.
174	>	*         and whose comparator is to be used to sort this map
175	>	* @throws NullPointerException if the specified map is null
176		*/
177		public TreeMap(SortedMap<K, ? extends V> m) {
178		comparator = m.comparator();
#	Line 187 | Line 189 | public class TreeMap<K,V>
189		/**
190		* Returns the number of key-value mappings in this map.
191		*
192	<	* @return the number of key-value mappings in this map.
192	>	* @return the number of key-value mappings in this map
193		*/
194		public int size() {
195		return size;
#	Line 197 | Line 199 | public class TreeMap<K,V>
199		* Returns <tt>true</tt> if this map contains a mapping for the specified
200		* key.
201		*
202	<	* @param key key whose presence in this map is to be tested.
201	<	*
202	>	* @param key key whose presence in this map is to be tested
203		* @return <tt>true</tt> if this map contains a mapping for the
204	<	*            specified key.
205	<	* @throws ClassCastException if the key cannot be compared with the keys
206	<	*                  currently in the map.
207	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
208	<	*                  natural ordering, or its comparator does not tolerate
209	<	*            <tt>null</tt> keys.
204	>	*         specified key
205	>	* @throws ClassCastException if the specified key cannot be compared
206	>	*         with the keys currently in the map
207	>	* @throws NullPointerException if the specified key is null
208	>	*         and this map uses natural ordering, or its comparator
209	>	*         does not permit null keys
210		*/
211		public boolean containsKey(Object key) {
212		return getEntry(key) != null;
#	Line 216 | Line 217 | public class TreeMap<K,V>
217		* specified value.  More formally, returns <tt>true</tt> if and only if
218		* this map contains at least one mapping to a value <tt>v</tt> such
219		* that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
220	<	* operation will probably require time linear in the Map size for most
221	<	* implementations of Map.
220	>	* operation will probably require time linear in the map size for
221	>	* most implementations.
222		*
223	<	* @param value value whose presence in this Map is to be tested.
224	<	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
225	<	*          <tt>false</tt> otherwise.
223	>	* @param value value whose presence in this map is to be tested
224	>	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
225	>	*         <tt>false</tt> otherwise
226		* @since 1.2
227		*/
228		public boolean containsValue(Object value) {
#	Line 250 | Line 251 | public class TreeMap<K,V>
251		}
252
253		/**
254	<	* Returns the value to which this map maps the specified key.  Returns
255	<	* <tt>null</tt> if the map contains no mapping for this key.  A return
254	>	* Returns the value to which this map maps the specified key, or
255	>	* <tt>null</tt> if the map contains no mapping for the key.  A return
256		* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
257		* map contains no mapping for the key; it's also possible that the map
258	<	* explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
259	<	* operation may be used to distinguish these two cases.
258	>	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey
259	>	* containsKey} operation may be used to distinguish these two cases.
260		*
261	<	* @param key key whose associated value is to be returned.
261	>	* @param key key whose associated value is to be returned
262		* @return the value to which this map maps the specified key, or
263	<	*               <tt>null</tt> if the map contains no mapping for the key.
264	<	* @throws    ClassCastException if key cannot be compared with the keys
265	<	*                  currently in the map.
266	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
267	<	*                  natural ordering, or its comparator does not tolerate
268	<	*                  <tt>null</tt> keys.
268	<	*
269	<	* @see #containsKey(Object)
263	>	*         <tt>null</tt> if the map contains no mapping for the key
264	>	* @throws ClassCastException if the specified key cannot be compared
265	>	*         with the keys currently in the map
266	>	* @throws NullPointerException if the specified key is null
267	>	*         and this map uses natural ordering, or its comparator
268	>	*         does not permit null keys
269		*/
270		public V get(Object key) {
271		Entry<K,V> p = getEntry(key);
272		return (p==null ? null : p.value);
273		}
274
276	–	/**
277	–	* Returns the comparator used to order this map, or <tt>null</tt> if this
278	–	* map uses its keys' natural order.
279	–	*
280	–	* @return the comparator associated with this sorted map, or
281	–	*                <tt>null</tt> if it uses its keys' natural sort method.
282	–	*/
275		public Comparator<? super K> comparator() {
276		return comparator;
277		}
278
279		/**
280	<	* Returns the first (lowest) key currently in this sorted map.
289	<	*
290	<	* @return the first (lowest) key currently in this sorted map.
291	<	* @throws    NoSuchElementException Map is empty.
280	>	* @throws NoSuchElementException {@inheritDoc}
281		*/
282		public K firstKey() {
283		return key(getFirstEntry());
284		}
285
286		/**
287	<	* Returns the last (highest) key currently in this sorted map.
299	<	*
300	<	* @return the last (highest) key currently in this sorted map.
301	<	* @throws    NoSuchElementException Map is empty.
287	>	* @throws NoSuchElementException {@inheritDoc}
288		*/
289		public K lastKey() {
290		return key(getLastEntry());
291		}
292
293		/**
294	<	* Copies all of the mappings from the specified map to this map.  These
295	<	* mappings replace any mappings that this map had for any of the keys
296	<	* currently in the specified map.
297	<	*
298	<	* @param     map mappings to be stored in this map.
299	<	* @throws    ClassCastException class of a key or value in the specified
300	<	*                   map prevents it from being stored in this map.
301	<	*
302	<	* @throws NullPointerException if the given map is <tt>null</tt> or
303	<	*         this map does not permit <tt>null</tt> keys and a
318	<	*         key in the specified map is <tt>null</tt>.
294	>	* Copies all of the mappings from the specified map to this map.
295	>	* These mappings replace any mappings that this map had for any
296	>	* of the keys currently in the specified map.
297	>	*
298	>	* @param  map mappings to be stored in this map
299	>	* @throws ClassCastException if the class of a key or value in
300	>	*         the specified map prevents it from being stored in this map
301	>	* @throws NullPointerException if the specified map is null or
302	>	*         the specified map contains a null key and this map does not
303	>	*         permit null keys
304		*/
305		public void putAll(Map<? extends K, ? extends V> map) {
306		int mapSize = map.size();
#	Line 340 | Line 325 | public class TreeMap<K,V>
325		* does not contain an entry for the key.
326		*
327		* @return this map's entry for the given key, or <tt>null</tt> if the map
328	<	*                does not contain an entry for the key.
329	<	* @throws ClassCastException if the key cannot be compared with the keys
330	<	*                  currently in the map.
331	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
332	<	*                  natural order, or its comparator does not tolerate *
333	<	*                  <tt>null</tt> keys.
328	>	*         does not contain an entry for the key
329	>	* @throws ClassCastException if the specified key cannot be compared
330	>	*         with the keys currently in the map
331	>	* @throws NullPointerException if the specified key is null
332	>	*         and this map uses natural ordering, or its comparator
333	>	*         does not permit null keys
334		*/
335		private Entry<K,V> getEntry(Object key) {
336		// Offload comparator-based version for sake of performance
#	Line 525 | Line 510 | public class TreeMap<K,V>
510		}
511
512		/**
513	<	* Returns the key corresponding to the specified Entry.  Throw
514	<	* NoSuchElementException if the Entry is <tt>null</tt>.
513	>	* Returns the key corresponding to the specified Entry.
514	>	* @throws NoSuchElementException if the Entry is null
515		*/
516		private static <K> K key(Entry<K,?> e) {
517		if (e==null)
#	Line 536 | Line 521 | public class TreeMap<K,V>
521
522		/**
523		* Associates the specified value with the specified key in this map.
524	<	* If the map previously contained a mapping for this key, the old
524	>	* If the map previously contained a mapping for the key, the old
525		* value is replaced.
526		*
527	<	* @param key key with which the specified value is to be associated.
528	<	* @param value value to be associated with the specified key.
527	>	* @param key key with which the specified value is to be associated
528	>	* @param value value to be associated with the specified key
529		*
530	<	* @return the previous value associated with specified key, or <tt>null</tt>
531	<	*         if there was no mapping for key.  A <tt>null</tt> return can
532	<	*         also indicate that the map previously associated <tt>null</tt>
533	<	*         with the specified key.
534	<	* @throws    ClassCastException if key cannot be compared with the keys
535	<	*            currently in the map.
536	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
537	<	*         natural order, or its comparator does not tolerate
538	<	*         <tt>null</tt> keys.
530	>	* @return the previous value associated with <tt>key</tt>, or
531	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
532	>	*         (A <tt>null</tt> return can also indicate that the map
533	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
534	>	* @throws ClassCastException if the specified key cannot be compared
535	>	*         with the keys currently in the map
536	>	* @throws NullPointerException if the specified key is null
537	>	*         and this map uses natural ordering, or its comparator
538	>	*         does not permit null keys
539		*/
540		public V put(K key, V value) {
541		Entry<K,V> t = root;
#	Line 596 | Line 581 | public class TreeMap<K,V>
581		* Removes the mapping for this key from this TreeMap if present.
582		*
583		* @param  key key for which mapping should be removed
584	<	* @return the previous value associated with specified key, or <tt>null</tt>
585	<	*         if there was no mapping for key.  A <tt>null</tt> return can
586	<	*         also indicate that the map previously associated
587	<	*         <tt>null</tt> with the specified key.
588	<	*
589	<	* @throws    ClassCastException if key cannot be compared with the keys
590	<	*            currently in the map.
591	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
592	<	*         natural order, or its comparator does not tolerate
608	<	*         <tt>null</tt> keys.
584	>	* @return the previous value associated with <tt>key</tt>, or
585	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
586	>	*         (A <tt>null</tt> return can also indicate that the map
587	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
588	>	* @throws ClassCastException if the specified key cannot be compared
589	>	*         with the keys currently in the map
590	>	* @throws NullPointerException if the specified key is null
591	>	*         and this map uses natural ordering, or its comparator
592	>	*         does not permit null keys
593		*/
594		public V remove(Object key) {
595		Entry<K,V> p = getEntry(key);
#	Line 618 | Line 602 | public class TreeMap<K,V>
602		}
603
604		/**
605	<	* Removes all mappings from this TreeMap.
605	>	* Removes all of the mappings from this map.
606	>	* The map will be empty after this call returns.
607		*/
608		public void clear() {
609		modCount++;
#	Line 630 | Line 615 | public class TreeMap<K,V>
615		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
616		* values themselves are not cloned.)
617		*
618	<	* @return a shallow copy of this Map.
618	>	* @return a shallow copy of this map
619		*/
620		public Object clone() {
621		TreeMap<K,V> clone = null;
#	Line 660 | Line 645 | public class TreeMap<K,V>
645
646		// NavigableMap API methods
647
663	–	/**
664	–	* Returns a key-value mapping associated with the least
665	–	* key in this map, or <tt>null</tt> if the map is empty.
666	–	*
667	–	* @return an Entry with least key, or <tt>null</tt>
668	–	* if the map is empty.
669	–	*/
648		public Map.Entry<K,V> firstEntry() {
649		Entry<K,V> e = getFirstEntry();
650	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
650	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
651		}
652
675	–	/**
676	–	* Returns a key-value mapping associated with the greatest
677	–	* key in this map, or <tt>null</tt> if the map is empty.
678	–	*
679	–	* @return an Entry with greatest key, or <tt>null</tt>
680	–	* if the map is empty.
681	–	*/
653		public Map.Entry<K,V> lastEntry() {
654		Entry<K,V> e = getLastEntry();
655	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
655	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
656		}
657
687	–	/**
688	–	* Removes and returns a key-value mapping associated with
689	–	* the least key in this map, or <tt>null</tt> if the map is empty.
690	–	*
691	–	* @return the removed first entry of this map, or <tt>null</tt>
692	–	* if the map is empty.
693	–	*/
658		public Map.Entry<K,V> pollFirstEntry() {
659		Entry<K,V> p = getFirstEntry();
660		if (p == null)
661		return null;
662	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
662	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
663		deleteEntry(p);
664		return result;
665		}
666
703	–	/**
704	–	* Removes and returns a key-value mapping associated with
705	–	* the greatest key in this map, or <tt>null</tt> if the map is empty.
706	–	*
707	–	* @return the removed last entry of this map, or <tt>null</tt>
708	–	* if the map is empty.
709	–	*/
667		public Map.Entry<K,V> pollLastEntry() {
668		Entry<K,V> p = getLastEntry();
669		if (p == null)
670		return null;
671	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
671	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
672		deleteEntry(p);
673		return result;
674		}
675
676		/**
677	<	* Returns a key-value mapping associated with the least key
678	<	* greater than or equal to the given key, or <tt>null</tt> if
679	<	* there is no such entry.
680	<	*
724	<	* @param key the key.
725	<	* @return an Entry associated with ceiling of given key, or
726	<	* <tt>null</tt> if there is no such Entry.
727	<	* @throws ClassCastException if key cannot be compared with the
728	<	* keys currently in the map.
729	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
730	<	*         natural order, or its comparator does not tolerate
731	<	*         <tt>null</tt> keys.
677	>	* @throws ClassCastException {@inheritDoc}
678	>	* @throws NullPointerException if the specified key is null
679	>	*         and this map uses natural ordering, or its comparator
680	>	*         does not permit null keys
681		*/
682	<	public Map.Entry<K,V> ceilingEntry(K key) {
683	<	Entry<K,V> e = getCeilingEntry(key);
684	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
682	>	public Map.Entry<K,V> lowerEntry(K key) {
683	>	Entry<K,V> e =  getLowerEntry(key);
684	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
685		}
686
738	–
687		/**
688	<	* Returns least key greater than or equal to the given key, or
689	<	* <tt>null</tt> if there is no such key.
690	<	*
691	<	* @param key the key.
744	<	* @return the ceiling key, or <tt>null</tt>
745	<	* if there is no such key.
746	<	* @throws ClassCastException if key cannot be compared with the keys
747	<	*            currently in the map.
748	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
749	<	*         natural order, or its comparator does not tolerate
750	<	*         <tt>null</tt> keys.
688	>	* @throws ClassCastException {@inheritDoc}
689	>	* @throws NullPointerException if the specified key is null
690	>	*         and this map uses natural ordering, or its comparator
691	>	*         does not permit null keys
692		*/
693	<	public K ceilingKey(K key) {
694	<	Entry<K,V> e = getCeilingEntry(key);
693	>	public K lowerKey(K key) {
694	>	Entry<K,V> e =  getLowerEntry(key);
695		return (e == null)? null : e.key;
696		}
697
757	–
758	–
698		/**
699	<	* Returns a key-value mapping associated with the greatest key
700	<	* less than or equal to the given key, or <tt>null</tt> if there
701	<	* is no such entry.
702	<	*
764	<	* @param key the key.
765	<	* @return an Entry associated with floor of given key, or <tt>null</tt>
766	<	* if there is no such Entry.
767	<	* @throws ClassCastException if key cannot be compared with the keys
768	<	*            currently in the map.
769	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
770	<	*         natural order, or its comparator does not tolerate
771	<	*         <tt>null</tt> keys.
699	>	* @throws ClassCastException {@inheritDoc}
700	>	* @throws NullPointerException if the specified key is null
701	>	*         and this map uses natural ordering, or its comparator
702	>	*         does not permit null keys
703		*/
704		public Map.Entry<K,V> floorEntry(K key) {
705		Entry<K,V> e = getFloorEntry(key);
706	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
706	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
707		}
708
709		/**
710	<	* Returns the greatest key
711	<	* less than or equal to the given key, or <tt>null</tt> if there
712	<	* is no such key.
713	<	*
783	<	* @param key the key.
784	<	* @return the floor of given key, or <tt>null</tt> if there is no
785	<	* such key.
786	<	* @throws ClassCastException if key cannot be compared with the keys
787	<	*            currently in the map.
788	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
789	<	*         natural order, or its comparator does not tolerate
790	<	*         <tt>null</tt> keys.
710	>	* @throws ClassCastException {@inheritDoc}
711	>	* @throws NullPointerException if the specified key is null
712	>	*         and this map uses natural ordering, or its comparator
713	>	*         does not permit null keys
714		*/
715		public K floorKey(K key) {
716		Entry<K,V> e = getFloorEntry(key);
#	Line 795 | Line 718 | public class TreeMap<K,V>
718		}
719
720		/**
721	<	* Returns a key-value mapping associated with the least key
722	<	* strictly greater than the given key, or <tt>null</tt> if there
723	<	* is no such entry.
724	<	*
802	<	* @param key the key.
803	<	* @return an Entry with least key greater than the given key, or
804	<	* <tt>null</tt> if there is no such Entry.
805	<	* @throws ClassCastException if key cannot be compared with the keys
806	<	*            currently in the map.
807	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
808	<	*         natural order, or its comparator does not tolerate
809	<	*         <tt>null</tt> keys.
721	>	* @throws ClassCastException {@inheritDoc}
722	>	* @throws NullPointerException if the specified key is null
723	>	*         and this map uses natural ordering, or its comparator
724	>	*         does not permit null keys
725		*/
726	<	public Map.Entry<K,V> higherEntry(K key) {
727	<	Entry<K,V> e = getHigherEntry(key);
728	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
726	>	public Map.Entry<K,V> ceilingEntry(K key) {
727	>	Entry<K,V> e = getCeilingEntry(key);
728	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
729		}
730
731		/**
732	<	* Returns the least key strictly greater than the given key, or
733	<	* <tt>null</tt> if there is no such key.
734	<	*
735	<	* @param key the key.
821	<	* @return the least key greater than the given key, or
822	<	* <tt>null</tt> if there is no such key.
823	<	* @throws ClassCastException if key cannot be compared with the keys
824	<	*            currently in the map.
825	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
826	<	*         natural order, or its comparator does not tolerate
827	<	*         <tt>null</tt> keys.
732	>	* @throws ClassCastException {@inheritDoc}
733	>	* @throws NullPointerException if the specified key is null
734	>	*         and this map uses natural ordering, or its comparator
735	>	*         does not permit null keys
736		*/
737	<	public K higherKey(K key) {
738	<	Entry<K,V> e = getHigherEntry(key);
737	>	public K ceilingKey(K key) {
738	>	Entry<K,V> e = getCeilingEntry(key);
739		return (e == null)? null : e.key;
740		}
741
742		/**
743	<	* Returns a key-value mapping associated with the greatest
744	<	* key strictly less than the given key, or <tt>null</tt> if there is no
745	<	* such entry.
746	<	*
839	<	* @param key the key.
840	<	* @return an Entry with greatest key less than the given
841	<	* key, or <tt>null</tt> if there is no such Entry.
842	<	* @throws ClassCastException if key cannot be compared with the keys
843	<	*            currently in the map.
844	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
845	<	*         natural order, or its comparator does not tolerate
846	<	*         <tt>null</tt> keys.
743	>	* @throws ClassCastException {@inheritDoc}
744	>	* @throws NullPointerException if the specified key is null
745	>	*         and this map uses natural ordering, or its comparator
746	>	*         does not permit null keys
747		*/
748	<	public Map.Entry<K,V> lowerEntry(K key) {
749	<	Entry<K,V> e =  getLowerEntry(key);
750	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
748	>	public Map.Entry<K,V> higherEntry(K key) {
749	>	Entry<K,V> e = getHigherEntry(key);
750	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
751		}
752
753		/**
754	<	* Returns the greatest key strictly less than the given key, or
755	<	* <tt>null</tt> if there is no such key.
756	<	*
757	<	* @param key the key.
858	<	* @return the greatest key less than the given
859	<	* key, or <tt>null</tt> if there is no such key.
860	<	* @throws ClassCastException if key cannot be compared with the keys
861	<	*            currently in the map.
862	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
863	<	*         natural order, or its comparator does not tolerate
864	<	*         <tt>null</tt> keys.
754	>	* @throws ClassCastException {@inheritDoc}
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		*/
759	<	public K lowerKey(K key) {
760	<	Entry<K,V> e =  getLowerEntry(key);
759	>	public K higherKey(K key) {
760	>	Entry<K,V> e = getHigherEntry(key);
761		return (e == null)? null : e.key;
762		}
763
#	Line 880 | Line 773 | public class TreeMap<K,V>
773		private transient Set<K> descendingKeySet = null;
774
775		/**
776	<	* Returns a Set view of the keys contained in this map.  The set's
777	<	* iterator will return the keys in ascending order.  The set is backed by
778	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
779	<	* the Set, and vice-versa.  The Set supports element removal, which
780	<	* removes the corresponding mapping from the map, via the
781	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
782	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
783	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
784	<	*
785	<	* @return a set view of the keys contained in this TreeMap.
776	>	* Returns a {@link Set} view of the keys contained in this map.
777	>	* The set's iterator returns the keys in ascending order.
778	>	* The set is backed by the map, so changes to the map are
779	>	* reflected in the set, and vice-versa.  If the map is modified
780	>	* while an iteration over the set is in progress (except through
781	>	* the iterator's own <tt>remove</tt> operation), the results of
782	>	* the iteration are undefined.  The set supports element removal,
783	>	* which removes the corresponding mapping from the map, via the
784	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
785	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
786	>	* operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
787	>	* operations.
788		*/
789		public Set<K> keySet() {
790		Set<K> ks = keySet;
#	Line 921 | Line 816 | public class TreeMap<K,V>
816		}
817
818		/**
819	<	* Returns a collection view of the values contained in this map.  The
820	<	* collection's iterator will return the values in the order that their
821	<	* corresponding keys appear in the tree.  The collection is backed by
822	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
823	<	* the collection, and vice-versa.  The collection supports element
824	<	* removal, which removes the corresponding mapping from the map through
825	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
826	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
827	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
828	<	*
829	<	* @return a collection view of the values contained in this map.
819	>	* Returns a {@link Collection} view of the values contained in this map.
820	>	* The collection's iterator returns the values in ascending order
821	>	* of the corresponding keys.
822	>	* The collection is backed by the map, so changes to the map are
823	>	* reflected in the collection, and vice-versa.  If the map is
824	>	* modified while an iteration over the collection is in progress
825	>	* (except through the iterator's own <tt>remove</tt> operation),
826	>	* the results of the iteration are undefined.  The collection
827	>	* supports element removal, which removes the corresponding
828	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
829	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
830	>	* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
831	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
832		*/
833		public Collection<V> values() {
834		Collection<V> vs = values;
#	Line 970 | Line 867 | public class TreeMap<K,V>
867		}
868
869		/**
870	<	* Returns a set view of the mappings contained in this map.  The set's
871	<	* iterator returns the mappings in ascending key order.  Each element in
872	<	* the returned set is a <tt>Map.Entry</tt>.  The set is backed by this
873	<	* map, so changes to this map are reflected in the set, and vice-versa.
874	<	* The set supports element removal, which removes the corresponding
875	<	* mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
870	>	* Returns a {@link Set} view of the mappings contained in this map.
871	>	* The set's iterator returns the entries in ascending key order.
872	>	* The set is backed by the map, so changes to the map are
873	>	* reflected in the set, and vice-versa.  If the map is modified
874	>	* while an iteration over the set is in progress (except through
875	>	* the iterator's own <tt>remove</tt> operation, or through the
876	>	* <tt>setValue</tt> operation on a map entry returned by the
877	>	* iterator) the results of the iteration are undefined.  The set
878	>	* supports element removal, which removes the corresponding
879	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
880		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
881	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
882	<	* <tt>addAll</tt> operations.
982	<	*
983	<	* @return a set view of the mappings contained in this map.
984	<	* @see Map.Entry
881	>	* <tt>clear</tt> operations.  It does not support the
882	>	* <tt>add</tt> or <tt>addAll</tt> operations.
883		*/
884		public Set<Map.Entry<K,V>> entrySet() {
885		Set<Map.Entry<K,V>> es = entrySet;
#	Line 1024 | Line 922 | public class TreeMap<K,V>
922		}
923		}
924
1027	–	/**
1028	–	* Returns a set view of the mappings contained in this map.  The
1029	–	* set's iterator returns the mappings in descending key order.
1030	–	* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1031	–	* set is backed by this map, so changes to this map are reflected
1032	–	* in the set, and vice-versa.  The set supports element removal,
1033	–	* which removes the corresponding mapping from the TreeMap,
1034	–	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1035	–	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1036	–	* operations.  It does not support the <tt>add</tt> or
1037	–	* <tt>addAll</tt> operations.
1038	–	*
1039	–	* @return a set view of the mappings contained in this map, in
1040	–	* descending key order
1041	–	* @see Map.Entry
1042	–	*/
925		public Set<Map.Entry<K,V>> descendingEntrySet() {
926		Set<Map.Entry<K,V>> es = descendingEntrySet;
927		return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
#	Line 1051 | Line 933 | public class TreeMap<K,V>
933		}
934		}
935
1054	–	/**
1055	–	* Returns a Set view of the keys contained in this map.  The
1056	–	* set's iterator will return the keys in descending order.  The
1057	–	* map is backed by this <tt>TreeMap</tt> instance, so changes to
1058	–	* this map are reflected in the Set, and vice-versa.  The Set
1059	–	* supports element removal, which removes the corresponding
1060	–	* mapping from the map, via the <tt>Iterator.remove</tt>,
1061	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1062	–	* and <tt>clear</tt> operations.  It does not support the
1063	–	* <tt>add</tt> or <tt>addAll</tt> operations.
1064	–	*
1065	–	* @return a set view of the keys contained in this TreeMap.
1066	–	*/
936		public Set<K> descendingKeySet() {
937		Set<K> ks = descendingKeySet;
938		return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
#	Line 1076 | Line 945 | public class TreeMap<K,V>
945		}
946
947		/**
948	<	* Returns a view of the portion of this map whose keys range from
1080	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1081	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1082	<	* navigable map is empty.)  The returned navigable map is backed
1083	<	* by this map, so changes in the returned navigable map are
1084	<	* reflected in this map, and vice-versa.  The returned navigable
1085	<	* map supports all optional map operations.<p>
1086	<	*
1087	<	* The navigable map returned by this method will throw an
1088	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1089	<	* less than <tt>fromKey</tt> or greater than or equal to
1090	<	* <tt>toKey</tt>.<p>
1091	<	*
1092	<	* Note: this method always returns a <i>half-open range</i> (which
1093	<	* includes its low endpoint but not its high endpoint).  If you need a
1094	<	* <i>closed range</i> (which includes both endpoints), and the key type
1095	<	* allows for calculation of the successor of a given key, merely request the
1096	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1097	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1098	<	* strings.  The following idiom obtains a view containing all of the
1099	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1100	<	* and <tt>high</tt>, inclusive:
1101	<	* <pre>  NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1102	<	* A similar technique can be used to generate an <i>open range</i> (which
1103	<	* contains neither endpoint).  The following idiom obtains a view
1104	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1105	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1106	<	* <pre>  NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1107	<	*
1108	<	* @param fromKey low endpoint (inclusive) of the subMap.
1109	<	* @param toKey high endpoint (exclusive) of the subMap.
1110	<	*
1111	<	* @return a view of the portion of this map whose keys range from
1112	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1113	<	*
1114	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1115	<	*         cannot be compared to one another using this map's comparator
1116	<	*         (or, if the map has no comparator, using natural ordering).
1117	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1118	<	*         <tt>toKey</tt>.
948	>	* @throws ClassCastException       {@inheritDoc}
949		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
950	<	*               <tt>null</tt> and this map uses natural order, or its
951	<	*               comparator does not tolerate <tt>null</tt> keys.
950	>	*         null and this map uses natural ordering, or its comparator
951	>	*         does not permit null keys
952	>	* @throws IllegalArgumentException {@inheritDoc}
953		*/
954		public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
955		return new SubMap(fromKey, toKey);
956		}
957
1127	–
958		/**
959	<	* Returns a view of the portion of this map whose keys are strictly less
960	<	* than <tt>toKey</tt>.  The returned navigable map is backed by this map, so
961	<	* changes in the returned navigable map are reflected in this map, and
962	<	* vice-versa.  The returned navigable map supports all optional map
963	<	* operations.<p>
1134	<	*
1135	<	* The navigable map returned by this method will throw an
1136	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1137	<	* greater than or equal to <tt>toKey</tt>.<p>
1138	<	*
1139	<	* Note: this method always returns a view that does not contain its
1140	<	* (high) endpoint.  If you need a view that does contain this endpoint,
1141	<	* and the key type allows for calculation of the successor of a given key,
1142	<	* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1143	<	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1144	<	* keys are strings.  The following idiom obtains a view containing all of
1145	<	* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1146	<	* to <tt>high</tt>:
1147	<	* <pre>
1148	<	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1149	<	* </pre>
1150	<	*
1151	<	* @param toKey high endpoint (exclusive) of the headMap.
1152	<	* @return a view of the portion of this map whose keys are strictly
1153	<	*                less than <tt>toKey</tt>.
1154	<	*
1155	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1156	<	*         with this map's comparator (or, if the map has no comparator,
1157	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1158	<	* @throws IllegalArgumentException if this map is itself a subMap,
1159	<	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1160	<	*         specified range of the subMap, headMap, or tailMap.
1161	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1162	<	*               this map uses natural order, or its comparator does not
1163	<	*               tolerate <tt>null</tt> keys.
959	>	* @throws ClassCastException       {@inheritDoc}
960	>	* @throws NullPointerException if <tt>toKey</tt> is null
961	>	*         and this map uses natural ordering, or its comparator
962	>	*         does not permit null keys
963	>	* @throws IllegalArgumentException {@inheritDoc}
964		*/
965		public NavigableMap<K,V> navigableHeadMap(K toKey) {
966		return new SubMap(toKey, true);
967		}
968
969		/**
970	<	* Returns a view of the portion of this map whose keys are greater than
971	<	* or equal to <tt>fromKey</tt>.  The returned navigable map is backed by
972	<	* this map, so changes in the returned navigable map are reflected in this
973	<	* map, and vice-versa.  The returned navigable map supports all optional map
974	<	* operations.<p>
1175	<	*
1176	<	* The navigable map returned by this method will throw an
1177	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1178	<	* less than <tt>fromKey</tt>.<p>
1179	<	*
1180	<	* Note: this method always returns a view that contains its (low)
1181	<	* endpoint.  If you need a view that does not contain this endpoint, and
1182	<	* the element type allows for calculation of the successor of a given value,
1183	<	* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1184	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1185	<	* are strings.  The following idiom obtains a view containing
1186	<	* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1187	<	* greater than <tt>low</tt>: <pre>
1188	<	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1189	<	* </pre>
1190	<	*
1191	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1192	<	* @return a view of the portion of this map whose keys are greater
1193	<	*                than or equal to <tt>fromKey</tt>.
1194	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1195	<	*         with this map's comparator (or, if the map has no comparator,
1196	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1197	<	* @throws IllegalArgumentException if this map is itself a subMap,
1198	<	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1199	<	*         specified range of the subMap, headMap, or tailMap.
1200	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1201	<	*               this map uses natural order, or its comparator does not
1202	<	*               tolerate <tt>null</tt> keys.
970	>	* @throws ClassCastException       {@inheritDoc}
971	>	* @throws NullPointerException if <tt>fromKey</tt> is null
972	>	*         and this map uses natural ordering, or its comparator
973	>	*         does not permit null keys
974	>	* @throws IllegalArgumentException {@inheritDoc}
975		*/
976		public NavigableMap<K,V> navigableTailMap(K fromKey) {
977		return new SubMap(fromKey, false);
978		}
979
980		/**
981	<	* Equivalent to <tt>navigableSubMap</tt> but with a return
982	<	* type conforming to the <tt>SortedMap</tt> interface.
983	<	* @param fromKey low endpoint (inclusive) of the subMap.
984	<	* @param toKey high endpoint (exclusive) of the subMap.
985	<	*
986	<	* @return a view of the portion of this map whose keys range from
1215	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1216	<	*
1217	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1218	<	*         cannot be compared to one another using this map's comparator
1219	<	*         (or, if the map has no comparator, using natural ordering).
1220	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1221	<	*         <tt>toKey</tt>.
981	>	* Equivalent to {@link #navigableSubMap} but with a return type
982	>	* conforming to the <tt>SortedMap</tt> interface.
983	>	*
984	>	* <p>{@inheritDoc}
985	>	*
986	>	* @throws ClassCastException       {@inheritDoc}
987		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
988	<	*               <tt>null</tt> and this map uses natural order, or its
989	<	*               comparator does not tolerate <tt>null</tt> keys.
988	>	*         null and this map uses natural ordering, or its comparator
989	>	*         does not permit null keys
990	>	* @throws IllegalArgumentException {@inheritDoc}
991		*/
992		public SortedMap<K,V> subMap(K fromKey, K toKey) {
993		return new SubMap(fromKey, toKey);
994		}
995
1230	–
996		/**
997	<	* Equivalent to <tt>navigableHeadMap</tt> but with a return
998	<	* type conforming to the <tt>SortedMap</tt> interface.
997	>	* Equivalent to {@link #navigableHeadMap} but with a return type
998	>	* conforming to the <tt>SortedMap</tt> interface.
999	>	*
1000	>	* <p>{@inheritDoc}
1001		*
1002	<	* @param toKey high endpoint (exclusive) of the headMap.
1003	<	* @return a view of the portion of this map whose keys are strictly
1004	<	*                less than <tt>toKey</tt>.
1005	<	*
1006	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1240	<	*         with this map's comparator (or, if the map has no comparator,
1241	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1242	<	* @throws IllegalArgumentException if this map is itself a subMap,
1243	<	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1244	<	*         specified range of the subMap, headMap, or tailMap.
1245	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1246	<	*               this map uses natural order, or its comparator does not
1247	<	*               tolerate <tt>null</tt> keys.
1002	>	* @throws ClassCastException       {@inheritDoc}
1003	>	* @throws NullPointerException if <tt>toKey</tt> is null
1004	>	*         and this map uses natural ordering, or its comparator
1005	>	*         does not permit null keys
1006	>	* @throws IllegalArgumentException {@inheritDoc}
1007		*/
1008		public SortedMap<K,V> headMap(K toKey) {
1009		return new SubMap(toKey, true);
1010		}
1011
1012		/**
1013	<	* Equivalent to <tt>navigableTailMap</tt> but with a return
1014	<	* type conforming to the <tt>SortedMap</tt> interface.
1013	>	* Equivalent to {@link #navigableTailMap} but with a return type
1014	>	* conforming to the <tt>SortedMap</tt> interface.
1015		*
1016	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1017	<	* @return a view of the portion of this map whose keys are greater
1018	<	*                than or equal to <tt>fromKey</tt>.
1019	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1020	<	*         with this map's comparator (or, if the map has no comparator,
1021	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1022	<	* @throws IllegalArgumentException if this map is itself a subMap,
1264	<	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1265	<	*         specified range of the subMap, headMap, or tailMap.
1266	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1267	<	*               this map uses natural order, or its comparator does not
1268	<	*               tolerate <tt>null</tt> keys.
1016	>	* <p>{@inheritDoc}
1017	>	*
1018	>	* @throws ClassCastException       {@inheritDoc}
1019	>	* @throws NullPointerException if <tt>fromKey</tt> is null
1020	>	*         and this map uses natural ordering, or its comparator
1021	>	*         does not permit null keys
1022	>	* @throws IllegalArgumentException {@inheritDoc}
1023		*/
1024		public SortedMap<K,V> tailMap(K fromKey) {
1025		return new SubMap(fromKey, false);
#	Line 1314 | Line 1068 | public class TreeMap<K,V>
1068		}
1069
1070		public boolean containsKey(Object key) {
1071	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1071	>	return inRange(key) && TreeMap.this.containsKey(key);
1072		}
1073
1074		public V get(Object key) {
1075	<	if (!inRange((K) key))
1075	>	if (!inRange(key))
1076		return null;
1077		return TreeMap.this.get(key);
1078		}
#	Line 1330 | Line 1084 | public class TreeMap<K,V>
1084		}
1085
1086		public V remove(Object key) {
1087	<	if (!inRange((K) key))
1087	>	if (!inRange(key))
1088		return null;
1089		return TreeMap.this.remove(key);
1090		}
#	Line 1376 | Line 1130 | public class TreeMap<K,V>
1130		getFirstEntry() : getCeilingEntry(fromKey);
1131		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1132		return null;
1133	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1133	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1134		deleteEntry(e);
1135		return result;
1136		}
#	Line 1386 | Line 1140 | public class TreeMap<K,V>
1140		getLastEntry() : getLowerEntry(toKey);
1141		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1142		return null;
1143	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1143	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1144		deleteEntry(e);
1145		return result;
1146		}
#	Line 1401 | Line 1155 | public class TreeMap<K,V>
1155
1156		public Map.Entry<K,V> ceilingEntry(K key) {
1157		TreeMap.Entry<K,V> e = subceiling(key);
1158	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1158	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1159		}
1160
1161		public K ceilingKey(K key) {
#	Line 1420 | Line 1174 | public class TreeMap<K,V>
1174
1175		public Map.Entry<K,V> higherEntry(K key) {
1176		TreeMap.Entry<K,V> e = subhigher(key);
1177	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1177	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1178		}
1179
1180		public K higherKey(K key) {
#	Line 1438 | Line 1192 | public class TreeMap<K,V>
1192
1193		public Map.Entry<K,V> floorEntry(K key) {
1194		TreeMap.Entry<K,V> e = subfloor(key);
1195	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1195	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1196		}
1197
1198		public K floorKey(K key) {
#	Line 1456 | Line 1210 | public class TreeMap<K,V>
1210
1211		public Map.Entry<K,V> lowerEntry(K key) {
1212		TreeMap.Entry<K,V> e = sublower(key);
1213	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1213	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1214		}
1215
1216		public K lowerKey(K key) {
#	Line 1529 | Line 1283 | public class TreeMap<K,V>
1283
1284		public Set<Map.Entry<K,V>> descendingEntrySet() {
1285		Set<Map.Entry<K,V>> es = descendingEntrySetView;
1286	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1286	>	return (es != null) ? es :
1287	>	(descendingEntrySetView = new DescendingEntrySetView());
1288		}
1289
1290		public Set<K> descendingKeySet() {
1291		Set<K> ks = descendingKeySetView;
1292	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1292	>	return (ks != null) ? ks :
1293	>	(descendingKeySetView = new DescendingKeySetView());
1294		}
1295
1296		private class DescendingEntrySetView extends EntrySetView {
#	Line 1565 | Line 1321 | public class TreeMap<K,V>
1321		}
1322		}
1323
1568	–
1324		public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1325		if (!inRange2(fromKey))
1326		throw new IllegalArgumentException("fromKey out of range");
#	Line 1586 | Line 1341 | public class TreeMap<K,V>
1341		return new SubMap(false, fromKey, toEnd, toKey);
1342		}
1343
1589	–
1344		public SortedMap<K,V> subMap(K fromKey, K toKey) {
1345		return navigableSubMap(fromKey, toKey);
1346		}
#	Line 1599 | Line 1353 | public class TreeMap<K,V>
1353		return navigableTailMap(fromKey);
1354		}
1355
1356	<	private boolean inRange(K key) {
1356	>	private boolean inRange(Object key) {
1357		return (fromStart || compare(key, fromKey) >= 0) &&
1358		(toEnd     || compare(key, toKey)   <  0);
1359		}
1360
1361		// This form allows the high endpoint (as well as all legit keys)
1362	<	private boolean inRange2(K key) {
1362	>	private boolean inRange2(Object key) {
1363		return (fromStart || compare(key, fromKey) >= 0) &&
1364		(toEnd     || compare(key, toKey)   <= 0);
1365		}
#	Line 1627 | Line 1381 | public class TreeMap<K,V>
1381		return next != null;
1382		}
1383
1384	<	Entry<K,V> nextEntry() {
1384	>	Entry<K,V> nextEntry() {
1385		if (next == null)
1386		throw new NoSuchElementException();
1387		if (modCount != expectedModCount)
#	Line 1654 | Line 1408 | public class TreeMap<K,V>
1408		EntryIterator(Entry<K,V> first) {
1409		super(first);
1410		}
1657	–
1411		public Map.Entry<K,V> next() {
1412		return nextEntry();
1413		}
#	Line 1699 | Line 1452 | public class TreeMap<K,V>
1452		}
1453		}
1454
1702	–
1455		/**
1456		* Base for Descending Iterators.
1457		*/
#	Line 1760 | Line 1512 | public class TreeMap<K,V>
1512
1513		}
1514
1763	–
1515		/**
1516		* Compares two keys using the correct comparison method for this TreeMap.
1517		*/
1518	<	private int compare(K k1, K k2) {
1519	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1520	<	: comparator.compare(k1, k2);
1518	>	private int compare(Object k1, Object k2) {
1519	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1520	>	: comparator.compare((K)k1, (K)k2);
1521		}
1522
1523		/**
1524	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1524	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1525		* that it copes with <tt>null</tt> o1 properly.
1526		*/
1527		private static boolean valEquals(Object o1, Object o2) {
#	Line 1806 | Line 1557 | public class TreeMap<K,V>
1557		/**
1558		* Returns the key.
1559		*
1560	<	* @return the key.
1560	>	* @return the key
1561		*/
1562		public K getKey() {
1563		return key;
#	Line 1815 | Line 1566 | public class TreeMap<K,V>
1566		/**
1567		* Returns the value associated with the key.
1568		*
1569	<	* @return the value associated with the key.
1569	>	* @return the value associated with the key
1570		*/
1571		public V getValue() {
1572		return value;
#	Line 1826 | Line 1577 | public class TreeMap<K,V>
1577		* value.
1578		*
1579		* @return the value associated with the key before this method was
1580	<	*           called.
1580	>	*         called
1581		*/
1582		public V setValue(V value) {
1583		V oldValue = this.value;
#	Line 2165 | Line 1916 | public class TreeMap<K,V>
1916		// Write out size (number of Mappings)
1917		s.writeInt(size);
1918
2168	–	Set<Map.Entry<K,V>> es = entrySet();
1919		// Write out keys and values (alternating)
1920	<	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
1920	>	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
1921		Map.Entry<K,V> e = i.next();
1922		s.writeObject(e.getKey());
1923		s.writeObject(e.getValue());
#	Line 2223 | Line 1973 | public class TreeMap<K,V>
1973		* to calling this method.
1974		*
1975		* @param size the number of keys (or key-value pairs) to be read from
1976	<	*        the iterator or stream.
1976	>	*        the iterator or stream
1977		* @param it If non-null, new entries are created from entries
1978		*        or keys read from this iterator.
1979		* @param str If non-null, new entries are created from keys and
#	Line 2258 | Line 2008 | public class TreeMap<K,V>
2008		* @param level the current level of tree. Initial call should be 0.
2009		* @param lo the first element index of this subtree. Initial should be 0.
2010		* @param hi the last element index of this subtree.  Initial should be
2011	<	*              size-1.
2011	>	*        size-1.
2012		* @param redLevel the level at which nodes should be red.
2013		*        Must be equal to computeRedLevel for tree of this size.
2014		*/
#	Line 2342 | Line 2092 | public class TreeMap<K,V>
2092		level++;
2093		return level;
2094		}
2345	–
2095		}

Diff Legend

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