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.8 by dl, Sat Apr 2 11:29:42 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 2004 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
10	–
10		/**
11	<	* Red-Black tree based implementation of the <tt>NavigableMap</tt> interface.
12	<	* This class guarantees that the map will be in ascending key order, sorted
13	<	* according to the <i>natural order</i> for the keys' class (see
14	<	* <tt>Comparable</tt>), or by the comparator provided at creation time,
16	<	* depending on which constructor is used.<p>
11	>	* A Red-Black tree based {@link NavigableMap} implementation.
12	>	* The map is sorted according to the {@linkplain Comparable natural
13	>	* ordering} of its keys, or by a {@link Comparator} provided at map
14	>	* creation time, depending on which constructor is used.
15		*
16	<	* This implementation provides guaranteed log(n) time cost for the
16	>	* <p>This implementation provides guaranteed log(n) time cost for the
17		* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
18		* operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
19	<	* Rivest's <I>Introduction to Algorithms</I>.<p>
19	>	* Rivest's <I>Introduction to Algorithms</I>.
20		*
21	<	* Note that the ordering maintained by a sorted map (whether or not an
21	>	* <p>Note that the ordering maintained by a sorted map (whether or not an
22		* explicit comparator is provided) must be <i>consistent with equals</i> if
23		* this sorted map is to correctly implement the <tt>Map</tt> interface.  (See
24		* <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
#	Line 30 | Line 28 | package java.util;
28		* method, so two keys that are deemed equal by this method are, from the
29		* standpoint of the sorted map, equal.  The behavior of a sorted map
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.<p>
31	>	* just fails to obey the general contract of the <tt>Map</tt> interface.
32		*
33	<	* <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><p>
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	<	* The iterators returned by all of this class's "collection view methods" are
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
49		* <i>fail-fast</i>: if the map is structurally modified at any time after the
50		* iterator is created, in any way except through the iterator's own
51	<	* <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
52	<	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of concurrent
51	>	* <tt>remove</tt> method, the iterator will throw a {@link
52	>	* ConcurrentModificationException}.  Thus, in the face of concurrent
53		* modification, the iterator fails quickly and cleanly, rather than risking
54	<	* arbitrary, non-deterministic behavior at an undetermined time in the
56	<	* future.
54	>	* arbitrary, non-deterministic behavior at an undetermined time in the future.
55		*
56		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
57		* as it is, generally speaking, impossible to make any hard guarantees in the
#	Line 73 | Line 71 | package java.util;
71		* <a href="{@docRoot}/../guide/collections/index.html">
72		* Java Collections Framework</a>.
73		*
74	+	* @param <K> the type of keys maintained by this map
75	+	* @param <V> the type of mapped values
76	+	*
77		* @author  Josh Bloch and Doug Lea
78		* @version %I%, %G%
79		* @see Map
#	Line 81 | Line 82 | package java.util;
82		* @see Comparable
83		* @see Comparator
84		* @see Collection
84	–	* @see Collections#synchronizedMap(Map)
85		* @since 1.2
86		*/
87
#	Line 90 | Line 90 | public class TreeMap<K,V>
90		implements NavigableMap<K,V>, Cloneable, java.io.Serializable
91		{
92		/**
93	<	* The Comparator used to maintain order in this TreeMap, or
94	<	* null if this TreeMap uses its elements natural ordering.
93	>	* The comparator used to maintain order in this tree map, or
94	>	* null if it uses the natural ordering of its keys.
95		*
96		* @serial
97		*/
#	Line 113 | Line 113 | public class TreeMap<K,V>
113		private void decrementSize()   { modCount++; size--; }
114
115		/**
116	<	* Constructs a new, empty map, sorted according to the keys' natural
117	<	* order.  All keys inserted into the map must implement the
118	<	* <tt>Comparable</tt> interface.  Furthermore, all such keys must be
119	<	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
120	<	* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
121	<	* map.  If the user attempts to put a key into the map that violates this
122	<	* constraint (for example, the user attempts to put a string key into a
123	<	* map whose keys are integers), the <tt>put(Object key, Object
124	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
125	<	*
126	<	* @see Comparable
116	>	* Constructs a new, empty tree map, using the natural ordering of its
117	>	* keys.  All keys inserted into the map must implement the {@link
118	>	* Comparable} interface.  Furthermore, all such keys must be
119	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
120	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
121	>	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
122	>	* map that violates this constraint (for example, the user attempts to
123	>	* put a string key into a map whose keys are integers), the
124	>	* <tt>put(Object key, Object value)</tt> call will throw a
125	>	* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128		}
129
130		/**
131	<	* Constructs a new, empty map, sorted according to the given comparator.
132	<	* All keys inserted into the map must be <i>mutually comparable</i> by
133	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
134	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
135	<	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
136	<	* map that violates this constraint, the <tt>put(Object key, Object
137	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
138	<	*
139	<	* @param c the comparator that will be used to sort this map.  A
140	<	*        <tt>null</tt> value indicates that the keys' <i>natural
141	<	*        ordering</i> should be used.
142	<	*/
143	<	public TreeMap(Comparator<? super K> c) {
144	<	this.comparator = c;
131	>	* Constructs a new, empty tree map, ordered according to the given
132	>	* comparator.  All keys inserted into the map must be <i>mutually
133	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
134	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
135	>	* <tt>k1</tt> and <tt>k2</tt> in the map.  If the user attempts to put
136	>	* a key into the map that violates this constraint, the <tt>put(Object
137	>	* key, Object value)</tt> call will throw a
138	>	* <tt>ClassCastException</tt>.
139	>	*
140	>	* @param comparator the comparator that will be used to order this map.
141	>	*        If <tt>null</tt>, the {@linkplain Comparable natural
142	>	*        ordering} of the keys will be used.
143	>	*/
144	>	public TreeMap(Comparator<? super K> comparator) {
145	>	this.comparator = comparator;
146		}
147
148		/**
149	<	* Constructs a new map containing the same mappings as the given map,
150	<	* sorted according to the keys' <i>natural order</i>.  All keys inserted
151	<	* into the new map must implement the <tt>Comparable</tt> interface.
152	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
153	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
154	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
155	<	* runs in n*log(n) time.
156	<	*
157	<	* @param  m the map whose mappings are to be placed in this map.
158	<	* @throws ClassCastException the keys in t are not Comparable, or
159	<	*         are not mutually comparable.
160	<	* @throws NullPointerException if the specified map is null.
149	>	* Constructs a new tree map containing the same mappings as the given
150	>	* map, ordered according to the <i>natural ordering</i> of its keys.
151	>	* All keys inserted into the new map must implement the {@link
152	>	* Comparable} interface.  Furthermore, all such keys must be
153	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
154	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
155	>	* <tt>k2</tt> in the map.  This method runs in n*log(n) time.
156	>	*
157	>	* @param  m the map whose mappings are to be placed in this map
158	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
159	>	*         or are not mutually comparable
160	>	* @throws NullPointerException if the specified map is null
161		*/
162		public TreeMap(Map<? extends K, ? extends V> m) {
163		putAll(m);
164		}
165
166		/**
167	<	* Constructs a new map containing the same mappings as the given
168	<	* <tt>SortedMap</tt>, sorted according to the same ordering.  This method
169	<	* runs in linear time.
167	>	* Constructs a new tree map containing the same mappings and
168	>	* using the same ordering as the specified sorted map.  This
169	>	* method runs in linear time.
170		*
171		* @param  m the sorted map whose mappings are to be placed in this map,
172	<	*         and whose comparator is to be used to sort this map.
173	<	* @throws NullPointerException if the specified sorted map is null.
172	>	*         and whose comparator is to be used to sort this map
173	>	* @throws NullPointerException if the specified map is null
174		*/
175		public TreeMap(SortedMap<K, ? extends V> m) {
176		comparator = m.comparator();
#	Line 187 | Line 187 | public class TreeMap<K,V>
187		/**
188		* Returns the number of key-value mappings in this map.
189		*
190	<	* @return the number of key-value mappings in this map.
190	>	* @return the number of key-value mappings in this map
191		*/
192		public int size() {
193		return size;
#	Line 197 | Line 197 | public class TreeMap<K,V>
197		* Returns <tt>true</tt> if this map contains a mapping for the specified
198		* key.
199		*
200	<	* @param key key whose presence in this map is to be tested.
201	<	*
200	>	* @param key key whose presence in this map is to be tested
201		* @return <tt>true</tt> if this map contains a mapping for the
202	<	*            specified key.
203	<	* @throws ClassCastException if the key cannot be compared with the keys
204	<	*                  currently in the map.
205	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
206	<	*                  natural ordering, or its comparator does not tolerate
207	<	*            <tt>null</tt> keys.
202	>	*         specified key
203	>	* @throws ClassCastException if the specified key cannot be compared
204	>	*         with the keys currently in the map
205	>	* @throws NullPointerException if the specified key is null
206	>	*         and this map uses natural ordering, or its comparator
207	>	*         does not permit null keys
208		*/
209		public boolean containsKey(Object key) {
210		return getEntry(key) != null;
#	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 will probably require time linear in the Map size for most
219	<	* implementations of Map.
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;
223	<	*          <tt>false</tt> otherwise.
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;
223	>	*         <tt>false</tt> otherwise
224		* @since 1.2
225		*/
226		public boolean containsValue(Object value) {
#	Line 250 | Line 249 | public class TreeMap<K,V>
249		}
250
251		/**
252	<	* Returns the value to which this map maps the specified key.  Returns
253	<	* <tt>null</tt> if the map contains no mapping for this 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 <tt>containsKey</tt>
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.
263	<	* @throws    ClassCastException if key cannot be compared with the keys
264	<	*                  currently in the map.
265	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
266	<	*                  natural ordering, or its comparator does not tolerate
267	<	*                  <tt>null</tt> keys.
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	<	* @see #containsKey(Object)
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
270	>	*         and this map uses natural ordering, or its comparator
271	>	*         does not permit null keys
272		*/
273		public V get(Object key) {
274		Entry<K,V> p = getEntry(key);
275		return (p==null ? null : p.value);
276		}
277
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	–	*/
278		public Comparator<? super K> comparator() {
279		return comparator;
280		}
281
282		/**
283	<	* 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.
283	>	* @throws NoSuchElementException {@inheritDoc}
284		*/
285		public K firstKey() {
286		return key(getFirstEntry());
287		}
288
289		/**
290	<	* 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.
290	>	* @throws NoSuchElementException {@inheritDoc}
291		*/
292		public K lastKey() {
293		return key(getLastEntry());
294		}
295
296		/**
297	<	* Copies all of the mappings from the specified map to this map.  These
298	<	* mappings replace any mappings that this map had for any of the keys
299	<	* currently in the specified map.
300	<	*
301	<	* @param     map mappings to be stored in this map.
302	<	* @throws    ClassCastException class of a key or value in the specified
303	<	*                   map prevents it from being stored in this map.
304	<	*
305	<	* @throws NullPointerException if the given map is <tt>null</tt> or
306	<	*         this map does not permit <tt>null</tt> keys and a
318	<	*         key in the specified map is <tt>null</tt>.
297	>	* Copies all of the mappings from the specified map to this map.
298	>	* These mappings replace any mappings that this map had for any
299	>	* of the keys currently in the specified map.
300	>	*
301	>	* @param  map mappings to be stored in this map
302	>	* @throws ClassCastException if the class of a key or value in
303	>	*         the specified map prevents it from being stored in this map
304	>	* @throws NullPointerException if the specified map is null or
305	>	*         the specified map contains a null key and this map does not
306	>	*         permit null keys
307		*/
308		public void putAll(Map<? extends K, ? extends V> map) {
309		int mapSize = map.size();
#	Line 340 | Line 328 | public class TreeMap<K,V>
328		* does not contain an entry for the key.
329		*
330		* @return this map's entry for the given key, or <tt>null</tt> if the map
331	<	*                does not contain an entry for the key.
332	<	* @throws ClassCastException if the key cannot be compared with the keys
333	<	*                  currently in the map.
334	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
335	<	*                  natural order, or its comparator does not tolerate *
336	<	*                  <tt>null</tt> keys.
331	>	*         does not contain an entry for the key
332	>	* @throws ClassCastException if the specified key cannot be compared
333	>	*         with the keys currently in the map
334	>	* @throws NullPointerException if the specified key is null
335	>	*         and this map uses natural ordering, or its comparator
336	>	*         does not permit null keys
337		*/
338		private Entry<K,V> getEntry(Object key) {
339		// Offload comparator-based version for sake of performance
340		if (comparator != null)
341		return getEntryUsingComparator(key);
342	<	Comparable<K> k = (Comparable<K>) key;
342	>	Comparable<? super K> k = (Comparable<? super K>) key;
343		Entry<K,V> p = root;
344		while (p != null) {
345		int cmp = k.compareTo(p.key);
#	Line 525 | Line 513 | public class TreeMap<K,V>
513		}
514
515		/**
516	<	* Returns the key corresponding to the specified Entry.  Throw
517	<	* NoSuchElementException if the Entry is <tt>null</tt>.
516	>	* Returns the key corresponding to the specified Entry.
517	>	* @throws NoSuchElementException if the Entry is null
518		*/
519		private static <K> K key(Entry<K,?> e) {
520		if (e==null)
#	Line 536 | 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.
531	<	* @param value value to be associated with the specified key.
530	>	* @param key key with which the specified value is to be associated
531	>	* @param value value to be associated with the specified key
532		*
533	<	* @return the previous value associated with specified key, or <tt>null</tt>
534	<	*         if there was no mapping for key.  A <tt>null</tt> return can
535	<	*         also indicate that the map previously associated <tt>null</tt>
536	<	*         with the specified key.
537	<	* @throws    ClassCastException if key cannot be compared with the keys
538	<	*            currently in the map.
539	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
540	<	*         natural order, or its comparator does not tolerate
541	<	*         <tt>null</tt> keys.
533	>	* @return the previous value associated with <tt>key</tt>, or
534	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
535	>	*         (A <tt>null</tt> return can also indicate that the map
536	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
537	>	* @throws ClassCastException if the specified key cannot be compared
538	>	*         with the keys currently in the map
539	>	* @throws NullPointerException if the specified key is null
540	>	*         and this map uses natural ordering, or its comparator
541	>	*         does not permit null keys
542		*/
543		public V put(K key, V value) {
544		Entry<K,V> t = root;
545
546		if (t == null) {
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 591 | Line 585 | public class TreeMap<K,V>
585		* Removes the mapping for this key from this TreeMap if present.
586		*
587		* @param  key key for which mapping should be removed
588	<	* @return the previous value associated with specified key, or <tt>null</tt>
589	<	*         if there was no mapping for key.  A <tt>null</tt> return can
590	<	*         also indicate that the map previously associated
591	<	*         <tt>null</tt> with the specified key.
592	<	*
593	<	* @throws    ClassCastException if key cannot be compared with the keys
594	<	*            currently in the map.
595	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
596	<	*         natural order, or its comparator does not tolerate
603	<	*         <tt>null</tt> keys.
588	>	* @return the previous value associated with <tt>key</tt>, or
589	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
590	>	*         (A <tt>null</tt> return can also indicate that the map
591	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
592	>	* @throws ClassCastException if the specified key cannot be compared
593	>	*         with the keys currently in the map
594	>	* @throws NullPointerException if the specified key is null
595	>	*         and this map uses natural ordering, or its comparator
596	>	*         does not permit null keys
597		*/
598		public V remove(Object key) {
599		Entry<K,V> p = getEntry(key);
#	Line 613 | Line 606 | public class TreeMap<K,V>
606		}
607
608		/**
609	<	* Removes all mappings from this TreeMap.
609	>	* Removes all of the mappings from this map.
610	>	* The map will be empty after this call returns.
611		*/
612		public void clear() {
613		modCount++;
#	Line 625 | Line 619 | public class TreeMap<K,V>
619		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
620		* values themselves are not cloned.)
621		*
622	<	* @return a shallow copy of this Map.
622	>	* @return a shallow copy of this map
623		*/
624		public Object clone() {
625		TreeMap<K,V> clone = null;
#	Line 656 | Line 650 | public class TreeMap<K,V>
650		// NavigableMap API methods
651
652		/**
653	<	* Returns a key-value mapping associated with the least
660	<	* key in this map, or <tt>null</tt> if the map is empty.
661	<	*
662	<	* @return an Entry with least key, or <tt>null</tt>
663	<	* if the map is empty.
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	<	* Returns a key-value mapping associated with the greatest
672	<	* key in this map, or <tt>null</tt> if the map is empty.
673	<	*
674	<	* @return an Entry with greatest key, or <tt>null</tt>
675	<	* if the map is empty.
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	<	* Removes and returns a key-value mapping associated with
684	<	* the least key in this map, or <tt>null</tt> if the map is empty.
685	<	*
686	<	* @return the removed first entry of this map, or <tt>null</tt>
687	<	* if the map is empty.
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	<	* Removes and returns a key-value mapping associated with
700	<	* the greatest key in this map, or <tt>null</tt> if the map is empty.
701	<	*
702	<	* @return the removed last entry of this map, or <tt>null</tt>
703	<	* if the map is empty.
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		}
691
692		/**
693	<	* Returns a key-value mapping associated with the least key
694	<	* greater than or equal to the given key, or <tt>null</tt> if
695	<	* there is no such entry.
696	<	*
697	<	* @param key the key.
720	<	* @return an Entry associated with ceiling of given key, or
721	<	* <tt>null</tt> if there is no such Entry.
722	<	* @throws ClassCastException if key cannot be compared with the
723	<	* keys currently in the map.
724	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
725	<	*         natural order, or its comparator does not tolerate
726	<	*         <tt>null</tt> keys.
693	>	* @throws ClassCastException {@inheritDoc}
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> ceilingEntry(K key) {
700	<	Entry<K,V> e = getCeilingEntry(key);
701	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
699	>	public Map.Entry<K,V> lowerEntry(K key) {
700	>	Entry<K,V> e =  getLowerEntry(key);
701	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
702		}
703
733	–
704		/**
705	<	* Returns least key greater than or equal to the given key, or
706	<	* <tt>null</tt> if there is no such key.
707	<	*
708	<	* @param key the key.
709	<	* @return the ceiling key, or <tt>null</tt>
740	<	* if there is no such key.
741	<	* @throws ClassCastException if key cannot be compared with the keys
742	<	*            currently in the map.
743	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
744	<	*         natural order, or its comparator does not tolerate
745	<	*         <tt>null</tt> keys.
705	>	* @throws ClassCastException {@inheritDoc}
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 ceilingKey(K key) {
712	<	Entry<K,V> e = getCeilingEntry(key);
711	>	public K lowerKey(K key) {
712	>	Entry<K,V> e =  getLowerEntry(key);
713		return (e == null)? null : e.key;
714		}
715
752	–
753	–
716		/**
717	<	* Returns a key-value mapping associated with the greatest key
718	<	* less than or equal to the given key, or <tt>null</tt> if there
719	<	* is no such entry.
720	<	*
721	<	* @param key the key.
760	<	* @return an Entry associated with floor of given key, or <tt>null</tt>
761	<	* if there is no such Entry.
762	<	* @throws ClassCastException if key cannot be compared with the keys
763	<	*            currently in the map.
764	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
765	<	*         natural order, or its comparator does not tolerate
766	<	*         <tt>null</tt> keys.
717	>	* @throws ClassCastException {@inheritDoc}
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		/**
729	<	* Returns the greatest key
730	<	* less than or equal to the given key, or <tt>null</tt> if there
731	<	* is no such key.
732	<	*
733	<	* @param key the key.
779	<	* @return the floor of given key, or <tt>null</tt> if there is no
780	<	* such key.
781	<	* @throws ClassCastException if key cannot be compared with the keys
782	<	*            currently in the map.
783	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
784	<	*         natural order, or its comparator does not tolerate
785	<	*         <tt>null</tt> keys.
729	>	* @throws ClassCastException {@inheritDoc}
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 790 | Line 738 | public class TreeMap<K,V>
738		}
739
740		/**
741	<	* Returns a key-value mapping associated with the least key
742	<	* strictly greater than the given key, or <tt>null</tt> if there
743	<	* is no such entry.
744	<	*
745	<	* @param key the key.
798	<	* @return an Entry with least key greater than the given key, or
799	<	* <tt>null</tt> if there is no such Entry.
800	<	* @throws ClassCastException if key cannot be compared with the keys
801	<	*            currently in the map.
802	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
803	<	*         natural order, or its comparator does not tolerate
804	<	*         <tt>null</tt> keys.
741	>	* @throws ClassCastException {@inheritDoc}
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> higherEntry(K key) {
748	<	Entry<K,V> e = getHigherEntry(key);
749	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
747	>	public Map.Entry<K,V> ceilingEntry(K key) {
748	>	Entry<K,V> e = getCeilingEntry(key);
749	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
750		}
751
752		/**
753	<	* Returns the least key strictly greater than the given key, or
754	<	* <tt>null</tt> if there is no such key.
755	<	*
756	<	* @param key the key.
757	<	* @return the least key greater than the given key, or
817	<	* <tt>null</tt> if there is no such key.
818	<	* @throws ClassCastException if key cannot be compared with the keys
819	<	*            currently in the map.
820	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
821	<	*         natural order, or its comparator does not tolerate
822	<	*         <tt>null</tt> keys.
753	>	* @throws ClassCastException {@inheritDoc}
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 higherKey(K key) {
760	<	Entry<K,V> e = getHigherEntry(key);
759	>	public K ceilingKey(K key) {
760	>	Entry<K,V> e = getCeilingEntry(key);
761		return (e == null)? null : e.key;
762		}
763
764		/**
765	<	* Returns a key-value mapping associated with the greatest
766	<	* key strictly less than the given key, or <tt>null</tt> if there is no
767	<	* such entry.
768	<	*
769	<	* @param key the key.
835	<	* @return an Entry with greatest key less than the given
836	<	* key, or <tt>null</tt> if there is no such Entry.
837	<	* @throws ClassCastException if key cannot be compared with the keys
838	<	*            currently in the map.
839	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
840	<	*         natural order, or its comparator does not tolerate
841	<	*         <tt>null</tt> keys.
765	>	* @throws ClassCastException {@inheritDoc}
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> lowerEntry(K key) {
772	<	Entry<K,V> e =  getLowerEntry(key);
773	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
771	>	public Map.Entry<K,V> higherEntry(K key) {
772	>	Entry<K,V> e = getHigherEntry(key);
773	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
774		}
775
776		/**
777	<	* Returns the greatest key strictly less than the given key, or
778	<	* <tt>null</tt> if there is no such key.
779	<	*
780	<	* @param key the key.
781	<	* @return the greatest key less than the given
854	<	* key, or <tt>null</tt> if there is no such key.
855	<	* @throws ClassCastException if key cannot be compared with the keys
856	<	*            currently in the map.
857	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
858	<	*         natural order, or its comparator does not tolerate
859	<	*         <tt>null</tt> keys.
777	>	* @throws ClassCastException {@inheritDoc}
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 lowerKey(K key) {
784	<	Entry<K,V> e =  getLowerEntry(key);
783	>	public K higherKey(K key) {
784	>	Entry<K,V> e = getHigherEntry(key);
785		return (e == null)? null : e.key;
786		}
787
#	Line 874 | Line 796 | public class TreeMap<K,V>
796		private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
797		private transient Set<K> descendingKeySet = null;
798
877	–	transient Set<K> keySet = null;        // XXX remove when integrated
878	–	transient Collection<V> values = null; // XXX remove when integrated
879	–
799		/**
800	<	* Returns a Set view of the keys contained in this map.  The set's
801	<	* iterator will return the keys in ascending order.  The set is backed by
802	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
803	<	* the Set, and vice-versa.  The Set supports element removal, which
804	<	* removes the corresponding mapping from the map, via the
805	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
806	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
807	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
808	<	*
809	<	* @return a set view of the keys contained in this TreeMap.
800	>	* Returns a {@link Set} view of the keys contained in this map.
801	>	* The set's iterator returns the keys in ascending order.
802	>	* The set is backed by the map, so changes to the map are
803	>	* reflected in the set, and vice-versa.  If the map is modified
804	>	* while an iteration over the set is in progress (except through
805	>	* the iterator's own <tt>remove</tt> operation), the results of
806	>	* the iteration are undefined.  The set supports element removal,
807	>	* which removes the corresponding mapping from the map, via the
808	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
809	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
810	>	* operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
811	>	* operations.
812		*/
813		public Set<K> keySet() {
814		Set<K> ks = keySet;
#	Line 919 | Line 840 | public class TreeMap<K,V>
840		}
841
842		/**
843	<	* Returns a collection view of the values contained in this map.  The
844	<	* collection's iterator will return the values in the order that their
845	<	* corresponding keys appear in the tree.  The collection is backed by
846	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
847	<	* the collection, and vice-versa.  The collection supports element
848	<	* removal, which removes the corresponding mapping from the map through
849	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
850	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
851	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
852	<	*
853	<	* @return a collection view of the values contained in this map.
843	>	* Returns a {@link Collection} view of the values contained in this map.
844	>	* The collection's iterator returns the values in ascending order
845	>	* of the corresponding keys.
846	>	* The collection is backed by the map, so changes to the map are
847	>	* reflected in the collection, and vice-versa.  If the map is
848	>	* modified while an iteration over the collection is in progress
849	>	* (except through the iterator's own <tt>remove</tt> operation),
850	>	* the results of the iteration are undefined.  The collection
851	>	* supports element removal, which removes the corresponding
852	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
853	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
854	>	* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
855	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
856		*/
857		public Collection<V> values() {
858		Collection<V> vs = values;
#	Line 968 | Line 891 | public class TreeMap<K,V>
891		}
892
893		/**
894	<	* Returns a set view of the mappings contained in this map.  The set's
895	<	* iterator returns the mappings in ascending key order.  Each element in
896	<	* the returned set is a <tt>Map.Entry</tt>.  The set is backed by this
897	<	* map, so changes to this map are reflected in the set, and vice-versa.
898	<	* The set supports element removal, which removes the corresponding
899	<	* mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
894	>	* Returns a {@link Set} view of the mappings contained in this map.
895	>	* The set's iterator returns the entries in ascending key order.
896	>	* The set is backed by the map, so changes to the map are
897	>	* reflected in the set, and vice-versa.  If the map is modified
898	>	* while an iteration over the set is in progress (except through
899	>	* the iterator's own <tt>remove</tt> operation, or through the
900	>	* <tt>setValue</tt> operation on a map entry returned by the
901	>	* iterator) the results of the iteration are undefined.  The set
902	>	* supports element removal, which removes the corresponding
903	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
904		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
905	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
906	<	* <tt>addAll</tt> operations.
980	<	*
981	<	* @return a set view of the mappings contained in this map.
982	<	* @see Map.Entry
905	>	* <tt>clear</tt> operations.  It does not support the
906	>	* <tt>add</tt> or <tt>addAll</tt> operations.
907		*/
908		public Set<Map.Entry<K,V>> entrySet() {
909		Set<Map.Entry<K,V>> es = entrySet;
#	Line 1023 | Line 947 | public class TreeMap<K,V>
947		}
948
949		/**
950	<	* Returns a set view of the mappings contained in this map.  The
1027	<	* set's iterator returns the mappings in descending key order.
1028	<	* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1029	<	* set is backed by this map, so changes to this map are reflected
1030	<	* in the set, and vice-versa.  The set supports element removal,
1031	<	* which removes the corresponding mapping from the TreeMap,
1032	<	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1033	<	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1034	<	* operations.  It does not support the <tt>add</tt> or
1035	<	* <tt>addAll</tt> operations.
1036	<	*
1037	<	* @return a set view of the mappings contained in this map, in
1038	<	* descending key order
1039	<	* @see Map.Entry
950	>	* @since 1.6
951		*/
952		public Set<Map.Entry<K,V>> descendingEntrySet() {
953		Set<Map.Entry<K,V>> es = descendingEntrySet;
#	Line 1050 | Line 961 | public class TreeMap<K,V>
961		}
962
963		/**
964	<	* Returns a Set view of the keys contained in this map.  The
1054	<	* set's iterator will return the keys in descending order.  The
1055	<	* map is backed by this <tt>TreeMap</tt> instance, so changes to
1056	<	* this map are reflected in the Set, and vice-versa.  The Set
1057	<	* supports element removal, which removes the corresponding
1058	<	* mapping from the map, via the <tt>Iterator.remove</tt>,
1059	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1060	<	* and <tt>clear</tt> operations.  It does not support the
1061	<	* <tt>add</tt> or <tt>addAll</tt> operations.
1062	<	*
1063	<	* @return a set view of the keys contained in this TreeMap.
964	>	* @since 1.6
965		*/
966		public Set<K> descendingKeySet() {
967		Set<K> ks = descendingKeySet;
#	Line 1074 | Line 975 | public class TreeMap<K,V>
975		}
976
977		/**
978	<	* Returns a view of the portion of this map whose keys range from
1078	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1079	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1080	<	* navigable map is empty.)  The returned navigable map is backed
1081	<	* by this map, so changes in the returned navigable map are
1082	<	* reflected in this map, and vice-versa.  The returned navigable
1083	<	* map supports all optional map operations.<p>
1084	<	*
1085	<	* The navigable map returned by this method will throw an
1086	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1087	<	* less than <tt>fromKey</tt> or greater than or equal to
1088	<	* <tt>toKey</tt>.<p>
1089	<	*
1090	<	* Note: this method always returns a <i>half-open range</i> (which
1091	<	* includes its low endpoint but not its high endpoint).  If you need a
1092	<	* <i>closed range</i> (which includes both endpoints), and the key type
1093	<	* allows for calculation of the successor of a given key, merely request the
1094	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1095	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1096	<	* strings.  The following idiom obtains a view containing all of the
1097	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1098	<	* and <tt>high</tt>, inclusive:
1099	<	* <pre>  NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1100	<	* A similar technique can be used to generate an <i>open range</i> (which
1101	<	* contains neither endpoint).  The following idiom obtains a view
1102	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1103	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1104	<	* <pre>  NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1105	<	*
1106	<	* @param fromKey low endpoint (inclusive) of the subMap.
1107	<	* @param toKey high endpoint (exclusive) of the subMap.
1108	<	*
1109	<	* @return a view of the portion of this map whose keys range from
1110	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1111	<	*
1112	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1113	<	*         cannot be compared to one another using this map's comparator
1114	<	*         (or, if the map has no comparator, using natural ordering).
1115	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1116	<	*         <tt>toKey</tt>.
978	>	* @throws ClassCastException       {@inheritDoc}
979		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
980	<	*               <tt>null</tt> and this map uses natural order, or its
981	<	*               comparator does not tolerate <tt>null</tt> keys.
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);
987		}
988
1125	–
989		/**
990	<	* Returns a view of the portion of this map whose keys are strictly less
991	<	* than <tt>toKey</tt>.  The returned navigable map is backed by this map, so
992	<	* changes in the returned navigable map are reflected in this map, and
993	<	* vice-versa.  The returned navigable map supports all optional map
994	<	* operations.<p>
995	<	*
1133	<	* The navigable map returned by this method will throw an
1134	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1135	<	* greater than or equal to <tt>toKey</tt>.<p>
1136	<	*
1137	<	* Note: this method always returns a view that does not contain its
1138	<	* (high) endpoint.  If you need a view that does contain this endpoint,
1139	<	* and the key type allows for calculation of the successor of a given key,
1140	<	* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1141	<	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1142	<	* keys are strings.  The following idiom obtains a view containing all of
1143	<	* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1144	<	* to <tt>high</tt>:
1145	<	* <pre>
1146	<	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1147	<	* </pre>
1148	<	*
1149	<	* @param toKey high endpoint (exclusive) of the headMap.
1150	<	* @return a view of the portion of this map whose keys are strictly
1151	<	*                less than <tt>toKey</tt>.
1152	<	*
1153	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1154	<	*         with this map's comparator (or, if the map has no comparator,
1155	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1156	<	* @throws IllegalArgumentException if this map is itself a subMap,
1157	<	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1158	<	*         specified range of the subMap, headMap, or tailMap.
1159	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1160	<	*               this map uses natural order, or its comparator does not
1161	<	*               tolerate <tt>null</tt> keys.
990	>	* @throws ClassCastException       {@inheritDoc}
991	>	* @throws NullPointerException if <tt>toKey</tt> is null
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);
999		}
1000
1001		/**
1002	<	* Returns a view of the portion of this map whose keys are greater than
1003	<	* or equal to <tt>fromKey</tt>.  The returned navigable map is backed by
1004	<	* this map, so changes in the returned navigable map are reflected in this
1005	<	* map, and vice-versa.  The returned navigable map supports all optional map
1006	<	* operations.<p>
1007	<	*
1174	<	* The navigable map returned by this method will throw an
1175	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1176	<	* less than <tt>fromKey</tt>.<p>
1177	<	*
1178	<	* Note: this method always returns a view that contains its (low)
1179	<	* endpoint.  If you need a view that does not contain this endpoint, and
1180	<	* the element type allows for calculation of the successor of a given value,
1181	<	* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1182	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1183	<	* are strings.  The following idiom obtains a view containing
1184	<	* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1185	<	* greater than <tt>low</tt>: <pre>
1186	<	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1187	<	* </pre>
1188	<	*
1189	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1190	<	* @return a view of the portion of this map whose keys are greater
1191	<	*                than or equal to <tt>fromKey</tt>.
1192	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1193	<	*         with this map's comparator (or, if the map has no comparator,
1194	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1195	<	* @throws IllegalArgumentException if this map is itself a subMap,
1196	<	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1197	<	*         specified range of the subMap, headMap, or tailMap.
1198	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1199	<	*               this map uses natural order, or its comparator does not
1200	<	*               tolerate <tt>null</tt> keys.
1002	>	* @throws ClassCastException       {@inheritDoc}
1003	>	* @throws NullPointerException if <tt>fromKey</tt> is null
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);
1011		}
1012
1013		/**
1014	<	* Equivalent to <tt>navigableSubMap</tt> but with a return
1015	<	* type conforming to the <tt>SortedMap</tt> interface.
1016	<	* @param fromKey low endpoint (inclusive) of the subMap.
1017	<	* @param toKey high endpoint (exclusive) of the subMap.
1018	<	*
1019	<	* @return a view of the portion of this map whose keys range from
1213	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1214	<	*
1215	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1216	<	*         cannot be compared to one another using this map's comparator
1217	<	*         (or, if the map has no comparator, using natural ordering).
1218	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1219	<	*         <tt>toKey</tt>.
1014	>	* Equivalent to {@link #navigableSubMap} but with a return type
1015	>	* conforming to the <tt>SortedMap</tt> interface.
1016	>	*
1017	>	* <p>{@inheritDoc}
1018	>	*
1019	>	* @throws ClassCastException       {@inheritDoc}
1020		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1021	<	*               <tt>null</tt> and this map uses natural order, or its
1022	<	*               comparator does not tolerate <tt>null</tt> keys.
1021	>	*         null and this map uses natural ordering, or its comparator
1022	>	*         does not permit null keys
1023	>	* @throws IllegalArgumentException {@inheritDoc}
1024		*/
1025		public SortedMap<K,V> subMap(K fromKey, K toKey) {
1026		return new SubMap(fromKey, toKey);
1027		}
1028
1228	–
1029		/**
1030	<	* Equivalent to <tt>navigableHeadMap</tt> but with a return
1031	<	* type conforming to the <tt>SortedMap</tt> interface.
1030	>	* Equivalent to {@link #navigableHeadMap} but with a return type
1031	>	* conforming to the <tt>SortedMap</tt> interface.
1032	>	*
1033	>	* <p>{@inheritDoc}
1034		*
1035	<	* @param toKey high endpoint (exclusive) of the headMap.
1036	<	* @return a view of the portion of this map whose keys are strictly
1037	<	*                less than <tt>toKey</tt>.
1038	<	*
1039	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1238	<	*         with this map's comparator (or, if the map has no comparator,
1239	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1240	<	* @throws IllegalArgumentException if this map is itself a subMap,
1241	<	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1242	<	*         specified range of the subMap, headMap, or tailMap.
1243	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1244	<	*               this map uses natural order, or its comparator does not
1245	<	*               tolerate <tt>null</tt> keys.
1035	>	* @throws ClassCastException       {@inheritDoc}
1036	>	* @throws NullPointerException if <tt>toKey</tt> is null
1037	>	*         and this map uses natural ordering, or its comparator
1038	>	*         does not permit null keys
1039	>	* @throws IllegalArgumentException {@inheritDoc}
1040		*/
1041		public SortedMap<K,V> headMap(K toKey) {
1042		return new SubMap(toKey, true);
1043		}
1044
1045		/**
1046	<	* Equivalent to <tt>navigableTailMap</tt> but with a return
1047	<	* type conforming to the <tt>SortedMap</tt> interface.
1046	>	* Equivalent to {@link #navigableTailMap} but with a return type
1047	>	* conforming to the <tt>SortedMap</tt> interface.
1048	>	*
1049	>	* <p>{@inheritDoc}
1050		*
1051	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1052	<	* @return a view of the portion of this map whose keys are greater
1053	<	*                than or equal to <tt>fromKey</tt>.
1054	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1055	<	*         with this map's comparator (or, if the map has no comparator,
1260	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1261	<	* @throws IllegalArgumentException if this map is itself a subMap,
1262	<	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1263	<	*         specified range of the subMap, headMap, or tailMap.
1264	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1265	<	*               this map uses natural order, or its comparator does not
1266	<	*               tolerate <tt>null</tt> keys.
1051	>	* @throws ClassCastException       {@inheritDoc}
1052	>	* @throws NullPointerException if <tt>fromKey</tt> is null
1053	>	*         and this map uses natural ordering, or its comparator
1054	>	*         does not permit null keys
1055	>	* @throws IllegalArgumentException {@inheritDoc}
1056		*/
1057		public SortedMap<K,V> tailMap(K fromKey) {
1058		return new SubMap(fromKey, false);
#	Line 1312 | 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 1328 | 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 1341 | Line 1130 | public class TreeMap<K,V>
1130		TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1131		K first = key(e);
1132		if (!toEnd && compare(first, toKey) >= 0)
1133	<	throw(new NoSuchElementException());
1133	>	throw new NoSuchElementException();
1134		return first;
1135		}
1136
#	Line 1349 | Line 1138 | public class TreeMap<K,V>
1138		TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1139		K last = key(e);
1140		if (!fromStart && compare(last, fromKey) < 0)
1141	<	throw(new NoSuchElementException());
1141	>	throw new NoSuchElementException();
1142		return last;
1143		}
1144
#	Line 1374 | 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 1384 | 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 1399 | 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 1418 | 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 1436 | 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 1454 | 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 1527 | Line 1316 | public class TreeMap<K,V>
1316
1317		public Set<Map.Entry<K,V>> descendingEntrySet() {
1318		Set<Map.Entry<K,V>> es = descendingEntrySetView;
1319	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1319	>	return (es != null) ? es :
1320	>	(descendingEntrySetView = new DescendingEntrySetView());
1321		}
1322
1323		public Set<K> descendingKeySet() {
1324		Set<K> ks = descendingKeySetView;
1325	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1325	>	return (ks != null) ? ks :
1326	>	(descendingKeySetView = new DescendingKeySetView());
1327		}
1328
1329		private class DescendingEntrySetView extends EntrySetView {
#	Line 1563 | Line 1354 | public class TreeMap<K,V>
1354		}
1355		}
1356
1566	–
1357		public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1358		if (!inRange2(fromKey))
1359		throw new IllegalArgumentException("fromKey out of range");
#	Line 1584 | Line 1374 | public class TreeMap<K,V>
1374		return new SubMap(false, fromKey, toEnd, toKey);
1375		}
1376
1587	–
1377		public SortedMap<K,V> subMap(K fromKey, K toKey) {
1378		return navigableSubMap(fromKey, toKey);
1379		}
#	Line 1597 | 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 1625 | Line 1414 | public class TreeMap<K,V>
1414		return next != null;
1415		}
1416
1417	<	Entry<K,V> nextEntry() {
1417	>	Entry<K,V> nextEntry() {
1418		if (next == null)
1419		throw new NoSuchElementException();
1420		if (modCount != expectedModCount)
#	Line 1652 | Line 1441 | public class TreeMap<K,V>
1441		EntryIterator(Entry<K,V> first) {
1442		super(first);
1443		}
1655	–
1444		public Map.Entry<K,V> next() {
1445		return nextEntry();
1446		}
#	Line 1697 | Line 1485 | public class TreeMap<K,V>
1485		}
1486		}
1487
1700	–
1488		/**
1489		* Base for Descending Iterators.
1490		*/
#	Line 1758 | Line 1545 | public class TreeMap<K,V>
1545
1546		}
1547
1761	–
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</*-*/K>)k1).compareTo(k2)
1553	<	: comparator.compare((K)k1, (K)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 1804 | Line 1590 | public class TreeMap<K,V>
1590		/**
1591		* Returns the key.
1592		*
1593	<	* @return the key.
1593	>	* @return the key
1594		*/
1595		public K getKey() {
1596		return key;
#	Line 1813 | Line 1599 | public class TreeMap<K,V>
1599		/**
1600		* Returns the value associated with the key.
1601		*
1602	<	* @return the value associated with the key.
1602	>	* @return the value associated with the key
1603		*/
1604		public V getValue() {
1605		return value;
#	Line 1824 | Line 1610 | public class TreeMap<K,V>
1610		* value.
1611		*
1612		* @return the value associated with the key before this method was
1613	<	*           called.
1613	>	*         called
1614		*/
1615		public V setValue(V value) {
1616		V oldValue = this.value;
#	Line 2163 | Line 1949 | public class TreeMap<K,V>
1949		// Write out size (number of Mappings)
1950		s.writeInt(size);
1951
2166	–	Set<Map.Entry<K,V>> es = entrySet();
1952		// Write out keys and values (alternating)
1953	<	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
1953	>	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
1954		Map.Entry<K,V> e = i.next();
1955		s.writeObject(e.getKey());
1956		s.writeObject(e.getValue());
#	Line 2196 | Line 1981 | public class TreeMap<K,V>
1981		}
1982
1983		/** Intended to be called only from TreeSet.addAll **/
1984	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
1984	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
1985		try {
1986		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
1987		} catch (java.io.IOException cannotHappen) {
#	Line 2221 | Line 2006 | public class TreeMap<K,V>
2006		* to calling this method.
2007		*
2008		* @param size the number of keys (or key-value pairs) to be read from
2009	<	*        the iterator or stream.
2009	>	*        the iterator or stream
2010		* @param it If non-null, new entries are created from entries
2011		*        or keys read from this iterator.
2012		* @param str If non-null, new entries are created from keys and
#	Line 2235 | 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,
2241	<	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),
2246	<	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.)
#	Line 2256 | Line 2039 | public class TreeMap<K,V>
2039		* @param level the current level of tree. Initial call should be 0.
2040		* @param lo the first element index of this subtree. Initial should be 0.
2041		* @param hi the last element index of this subtree.  Initial should be
2042	<	*              size-1.
2042	>	*        size-1.
2043		* @param redLevel the level at which nodes should be red.
2044		*        Must be equal to computeRedLevel for tree of this size.
2045		*/
#	Line 2340 | Line 2123 | public class TreeMap<K,V>
2123		level++;
2124		return level;
2125		}
2343	–
2126		}

Diff Legend

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