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.3 by dl, Sun Mar 6 12:06:17 2005 UTC vs.
Revision 1.32 by dl, Sat Apr 22 16:38:01 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	<
8	>	package java.util;
9
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 key's 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 61 | Line 59 | package java.util;
59		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
60		* Therefore, it would be wrong to write a program that depended on this
61		* exception for its correctness:   <i>the fail-fast behavior of iterators
62	<	* should be used only to detect bugs.</i><p>
62	>	* should be used only to detect bugs.</i>
63		*
64		* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
65		* and its views represent snapshots of mappings at the time they were
#	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		*/
98	<	private Comparator<? super K> comparator = null;
98	>	private final Comparator<? super K> comparator;
99
100		private transient Entry<K,V> root = null;
101
#	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	+	comparator = null;
129		}
130
131		/**
132	<	* Constructs a new, empty map, sorted according to the given comparator.
133	<	* All keys inserted into the map must be <i>mutually comparable</i> by
134	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
135	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
136	<	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
137	<	* map that violates this constraint, the <tt>put(Object key, Object
138	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
132	>	* Constructs a new, empty tree map, ordered according to the given
133	>	* comparator.  All keys inserted into the map must be <i>mutually
134	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
135	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
136	>	* <tt>k1</tt> and <tt>k2</tt> in the map.  If the user attempts to put
137	>	* a key into the map that violates this constraint, the <tt>put(Object
138	>	* key, Object value)</tt> call will throw a
139	>	* <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;
141	>	* @param comparator the comparator that will be used to order this map.
142	>	*        If <tt>null</tt>, the {@linkplain Comparable natural
143	>	*        ordering} of the keys will be used.
144	>	*/
145	>	public TreeMap(Comparator<? super K> comparator) {
146	>	this.comparator = comparator;
147		}
148
149		/**
150	<	* Constructs a new map containing the same mappings as the given map,
151	<	* sorted according to the keys' <i>natural order</i>.  All keys inserted
152	<	* into the new map must implement the <tt>Comparable</tt> interface.
153	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
154	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
155	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
156	<	* runs in n*log(n) time.
157	<	*
158	<	* @param  m the map whose mappings are to be placed in this map.
159	<	* @throws ClassCastException the keys in t are not Comparable, or
160	<	*         are not mutually comparable.
161	<	* @throws NullPointerException if the specified map is null.
150	>	* Constructs a new tree map containing the same mappings as the given
151	>	* map, ordered according to the <i>natural ordering</i> of its keys.
152	>	* All keys inserted into the new map must implement the {@link
153	>	* Comparable} interface.  Furthermore, all such keys must be
154	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
155	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
156	>	* <tt>k2</tt> in the map.  This method runs in n*log(n) time.
157	>	*
158	>	* @param  m the map whose mappings are to be placed in this map
159	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
160	>	*         or are not mutually comparable
161	>	* @throws NullPointerException if the specified map is null
162		*/
163		public TreeMap(Map<? extends K, ? extends V> m) {
164	+	comparator = null;
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) {
229		return (root==null ? false :
230		(value==null ? valueSearchNull(root)
231	<	: valueSearchNonNull(root, value)));
231	>	: valueSearchNonNull(root, value)));
232		}
233
234		private boolean valueSearchNull(Entry n) {
#	Line 236 | Line 237 | public class TreeMap<K,V>
237
238		// Check left and right subtrees for value
239		return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
240	>	(n.right != null && valueSearchNull(n.right));
241		}
242
243		private boolean valueSearchNonNull(Entry n, Object value) {
#	Line 246 | Line 247 | public class TreeMap<K,V>
247
248		// Check left and right subtrees for value
249		return (n.left  != null && valueSearchNonNull(n.left, value)) ||
250	<	(n.right != null && valueSearchNonNull(n.right, value));
250	>	(n.right != null && valueSearchNonNull(n.right, value));
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
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.
254	>	* Returns the value to which the specified key is mapped,
255	>	* or {@code null} if this map contains no mapping for the key.
256		*
257	<	* @see #containsKey(Object)
257	>	* <p>More formally, if this map contains a mapping from a key
258	>	* {@code k} to a value {@code v} such that {@code key} compares
259	>	* equal to {@code k} according to the map's ordering, then this
260	>	* method returns {@code v}; otherwise it returns {@code null}.
261	>	* (There can be at most one such mapping.)
262	>	*
263	>	* <p>A return value of {@code null} does not <i>necessarily</i>
264	>	* indicate that the map contains no mapping for the key; it's also
265	>	* possible that the map explicitly maps the key to {@code null}.
266	>	* The {@link #containsKey containsKey} operation may be used to
267	>	* distinguish these two cases.
268	>	*
269	>	* @throws ClassCastException if the specified key cannot be compared
270	>	*         with the keys currently in the map
271	>	* @throws NullPointerException if the specified key is null
272	>	*         and this map uses natural ordering, or its comparator
273	>	*         does not permit null keys
274		*/
275		public V get(Object key) {
276		Entry<K,V> p = getEntry(key);
277		return (p==null ? null : p.value);
278		}
279
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	–	*/
280		public Comparator<? super K> comparator() {
281		return comparator;
282		}
283
284		/**
285	<	* 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.
285	>	* @throws NoSuchElementException {@inheritDoc}
286		*/
287		public K firstKey() {
288		return key(getFirstEntry());
289		}
290
291		/**
292	<	* 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.
292	>	* @throws NoSuchElementException {@inheritDoc}
293		*/
294		public K lastKey() {
295		return key(getLastEntry());
296		}
297
298		/**
299	<	* Copies all of the mappings from the specified map to this map.  These
300	<	* mappings replace any mappings that this map had for any of the keys
301	<	* currently in the specified map.
302	<	*
303	<	* @param     map mappings to be stored in this map.
304	<	* @throws    ClassCastException class of a key or value in the specified
305	<	*                   map prevents it from being stored in this map.
306	<	*
307	<	* @throws NullPointerException if the given map is <tt>null</tt> or
308	<	*         this map does not permit <tt>null</tt> keys and a
318	<	*         key in the specified map is <tt>null</tt>.
299	>	* Copies all of the mappings from the specified map to this map.
300	>	* These mappings replace any mappings that this map had for any
301	>	* of the keys currently in the specified map.
302	>	*
303	>	* @param  map mappings to be stored in this map
304	>	* @throws ClassCastException if the class of a key or value in
305	>	*         the specified map prevents it from being stored in this map
306	>	* @throws NullPointerException if the specified map is null or
307	>	*         the specified map contains a null key and this map does not
308	>	*         permit null keys
309		*/
310		public void putAll(Map<? extends K, ? extends V> map) {
311		int mapSize = map.size();
#	Line 340 | Line 330 | public class TreeMap<K,V>
330		* does not contain an entry for the key.
331		*
332		* @return this map's entry for the given key, or <tt>null</tt> if the map
333	<	*                does not contain an entry for the key.
334	<	* @throws ClassCastException if the key cannot be compared with the keys
335	<	*                  currently in the map.
336	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
337	<	*                  natural order, or its comparator does not tolerate *
338	<	*                  <tt>null</tt> keys.
333	>	*         does not contain an entry for the key
334	>	* @throws ClassCastException if the specified key cannot be compared
335	>	*         with the keys currently in the map
336	>	* @throws NullPointerException if the specified key is null
337	>	*         and this map uses natural ordering, or its comparator
338	>	*         does not permit null keys
339		*/
340	<	private Entry<K,V> getEntry(Object key) {
340	>	final Entry<K,V> getEntry(Object key) {
341		// Offload comparator-based version for sake of performance
342		if (comparator != null)
343		return getEntryUsingComparator(key);
344	<	Comparable<K> k = (Comparable<K>) key;
344	>	if (key == null)
345	>	throw new NullPointerException();
346	>	Comparable<? super K> k = (Comparable<? super K>) key;
347		Entry<K,V> p = root;
348		while (p != null) {
349		int cmp = k.compareTo(p.key);
#	Line 369 | Line 361 | public class TreeMap<K,V>
361		* Version of getEntry using comparator. Split off from getEntry
362		* for performance. (This is not worth doing for most methods,
363		* that are less dependent on comparator performance, but is
364	<	* worthwhile here.)
364	>	* worthwhile for get and put.)
365		*/
366	<	private Entry<K,V> getEntryUsingComparator(Object key) {
366	>	final Entry<K,V> getEntryUsingComparator(Object key) {
367		K k = (K) key;
368		Comparator<? super K> cpr = comparator;
369		Entry<K,V> p = root;
#	Line 393 | Line 385 | public class TreeMap<K,V>
385		* key; if no such entry exists (i.e., the greatest key in the Tree is less
386		* than the specified key), returns <tt>null</tt>.
387		*/
388	<	private Entry<K,V> getCeilingEntry(K key) {
388	>	final Entry<K,V> getCeilingEntry(K key) {
389		Entry<K,V> p = root;
390	<	if (p==null)
399	<	return null;
400	<
401	<	while (true) {
390	>	while (p != null) {
391		int cmp = compare(key, p.key);
392		if (cmp < 0) {
393		if (p.left != null)
#	Line 420 | Line 409 | public class TreeMap<K,V>
409		} else
410		return p;
411		}
412	+	return null;
413		}
414
415		/**
#	Line 427 | Line 417 | public class TreeMap<K,V>
417		* exists, returns the entry for the greatest key less than the specified
418		* key; if no such entry exists, returns <tt>null</tt>.
419		*/
420	<	private Entry<K,V> getFloorEntry(K key) {
420	>	final Entry<K,V> getFloorEntry(K key) {
421		Entry<K,V> p = root;
422	<	if (p==null)
433	<	return null;
434	<
435	<	while (true) {
422	>	while (p != null) {
423		int cmp = compare(key, p.key);
424		if (cmp > 0) {
425		if (p.right != null)
#	Line 455 | Line 442 | public class TreeMap<K,V>
442		return p;
443
444		}
445	+	return null;
446		}
447
448		/**
#	Line 463 | Line 451 | public class TreeMap<K,V>
451		* key greater than the specified key; if no such entry exists
452		* returns <tt>null</tt>.
453		*/
454	<	private Entry<K,V> getHigherEntry(K key) {
454	>	final Entry<K,V> getHigherEntry(K key) {
455		Entry<K,V> p = root;
456	<	if (p==null)
469	<	return null;
470	<
471	<	while (true) {
456	>	while (p != null) {
457		int cmp = compare(key, p.key);
458		if (cmp < 0) {
459		if (p.left != null)
#	Line 489 | Line 474 | public class TreeMap<K,V>
474		}
475		}
476		}
477	+	return null;
478		}
479
480		/**
#	Line 496 | Line 482 | public class TreeMap<K,V>
482		* no such entry exists (i.e., the least key in the Tree is greater than
483		* the specified key), returns <tt>null</tt>.
484		*/
485	<	private Entry<K,V> getLowerEntry(K key) {
485	>	final Entry<K,V> getLowerEntry(K key) {
486		Entry<K,V> p = root;
487	<	if (p==null)
502	<	return null;
503	<
504	<	while (true) {
487	>	while (p != null) {
488		int cmp = compare(key, p.key);
489		if (cmp > 0) {
490		if (p.right != null)
#	Line 522 | Line 505 | public class TreeMap<K,V>
505		}
506		}
507		}
508	+	return null;
509		}
510
511		/**
512	<	* Returns the key corresponding to the specified Entry.  Throw
513	<	* NoSuchElementException if the Entry is <tt>null</tt>.
512	>	* Returns the key corresponding to the specified Entry.
513	>	* @throws NoSuchElementException if the Entry is null
514		*/
515	<	private static <K> K key(Entry<K,?> e) {
515	>	static <K> K key(Entry<K,?> e) {
516		if (e==null)
517		throw new NoSuchElementException();
518		return e.key;
#	Line 536 | Line 520 | public class TreeMap<K,V>
520
521		/**
522		* Associates the specified value with the specified key in this map.
523	<	* If the map previously contained a mapping for this key, the old
523	>	* If the map previously contained a mapping for the key, the old
524		* value is replaced.
525		*
526	<	* @param key key with which the specified value is to be associated.
527	<	* @param value value to be associated with the specified key.
526	>	* @param key key with which the specified value is to be associated
527	>	* @param value value to be associated with the specified key
528		*
529	<	* @return previous value associated with specified key, or <tt>null</tt>
530	<	*         if there was no mapping for key.  A <tt>null</tt> return can
531	<	*         also indicate that the map previously associated <tt>null</tt>
532	<	*         with the specified key.
533	<	* @throws    ClassCastException if key cannot be compared with the keys
534	<	*            currently in the map.
535	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
536	<	*         natural order, or its comparator does not tolerate
537	<	*         <tt>null</tt> keys.
529	>	* @return the previous value associated with <tt>key</tt>, or
530	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
531	>	*         (A <tt>null</tt> return can also indicate that the map
532	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
533	>	* @throws ClassCastException if the specified key cannot be compared
534	>	*         with the keys currently in the map
535	>	* @throws NullPointerException if the specified key is null
536	>	*         and this map uses natural ordering, or its comparator
537	>	*         does not permit null keys
538		*/
539		public V put(K key, V value) {
540	<	Entry<K,V> t = root;
540	>	// Offload comparator-based version for sake of performance
541	>	if (comparator != null)
542	>	return putUsingComparator(key, value);
543	>	if (key == null)
544	>	throw new NullPointerException();
545	>	Comparable<? super K> k = (Comparable<? super K>) key;
546
547	<	if (t == null) {
548	<	incrementSize();
549	<	root = new Entry<K,V>(key, value, null);
550	<	return null;
551	<	}
547	>	Entry<K,V> t = root;
548	>	while (t != null) {
549	>	int cmp = k.compareTo(t.key);
550	>	if (cmp == 0) {
551	>	return t.setValue(value);
552	>	} else if (cmp < 0) {
553	>	if (t.left != null) {
554	>	t = t.left;
555	>	} else {
556	>	incrementSize();
557	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
558	>	return null;
559	>	}
560	>	} else { // cmp > 0
561	>	if (t.right != null) {
562	>	t = t.right;
563	>	} else {
564	>	incrementSize();
565	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	>	return null;
567	>	}
568	>	}
569	>	}
570	>	incrementSize();
571	>	root = new Entry<K,V>(key, value, null);
572	>	return null;
573	>	}
574
575	<	while (true) {
576	<	int cmp = compare(key, t.key);
575	>	/**
576	>	* Version of put using comparator. Split off from put for
577	>	* performance.
578	>	*/
579	>	final V putUsingComparator(K key, V value) {
580	>	Comparator<? super K> cpr = comparator;
581	>	Entry<K,V> t = root;
582	>	while (t != null) {
583	>	int cmp = cpr.compare(key, t.key);
584		if (cmp == 0) {
585		return t.setValue(value);
586		} else if (cmp < 0) {
#	Line 570 | Line 588 | public class TreeMap<K,V>
588		t = t.left;
589		} else {
590		incrementSize();
591	<	t.left = new Entry<K,V>(key, value, t);
574	<	fixAfterInsertion(t.left);
591	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592		return null;
593		}
594		} else { // cmp > 0
#	Line 579 | Line 596 | public class TreeMap<K,V>
596		t = t.right;
597		} else {
598		incrementSize();
599	<	t.right = new Entry<K,V>(key, value, t);
583	<	fixAfterInsertion(t.right);
599	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600		return null;
601		}
602		}
603		}
604	+	cpr.compare(key, key); // type check
605	+	incrementSize();
606	+	root = new Entry<K,V>(key, value, null);
607	+	return null;
608		}
609
610		/**
611		* Removes the mapping for this key from this TreeMap if present.
612		*
613		* @param  key key for which mapping should be removed
614	<	* @return previous value associated with specified key, or <tt>null</tt>
615	<	*         if there was no mapping for key.  A <tt>null</tt> return can
616	<	*         also indicate that the map previously associated
617	<	*         <tt>null</tt> with the specified key.
618	<	*
619	<	* @throws    ClassCastException if key cannot be compared with the keys
620	<	*            currently in the map.
621	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
622	<	*         natural order, or its comparator does not tolerate
603	<	*         <tt>null</tt> keys.
614	>	* @return the previous value associated with <tt>key</tt>, or
615	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
616	>	*         (A <tt>null</tt> return can also indicate that the map
617	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
618	>	* @throws ClassCastException if the specified key cannot be compared
619	>	*         with the keys currently in the map
620	>	* @throws NullPointerException if the specified key is null
621	>	*         and this map uses natural ordering, or its comparator
622	>	*         does not permit null keys
623		*/
624		public V remove(Object key) {
625		Entry<K,V> p = getEntry(key);
#	Line 613 | Line 632 | public class TreeMap<K,V>
632		}
633
634		/**
635	<	* Removes all mappings from this TreeMap.
635	>	* Removes all of the mappings from this map.
636	>	* The map will be empty after this call returns.
637		*/
638		public void clear() {
639		modCount++;
#	Line 625 | Line 645 | public class TreeMap<K,V>
645		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
646		* values themselves are not cloned.)
647		*
648	<	* @return a shallow copy of this Map.
648	>	* @return a shallow copy of this map
649		*/
650		public Object clone() {
651		TreeMap<K,V> clone = null;
#	Line 640 | Line 660 | public class TreeMap<K,V>
660		clone.size = 0;
661		clone.modCount = 0;
662		clone.entrySet = null;
663	<	clone.descendingEntrySet = null;
664	<	clone.descendingKeySet = null;
663	>	clone.navigableKeySet = null;
664	>	clone.descendingMap = null;
665
666		// Initialize clone with our mappings
667		try {
#	Line 656 | Line 676 | public class TreeMap<K,V>
676		// NavigableMap API methods
677
678		/**
679	<	* 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.
679	>	* @since 1.6
680		*/
681		public Map.Entry<K,V> firstEntry() {
682		Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
683	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
684		}
685
686		/**
687	<	* Returns a key-value mapping associated with the greatest
672	<	* key in this map, or <tt>null</tt> if the map is empty.
673	<	* The returned entry does <em>not</em> support
674	<	* the <tt>Entry.setValue</tt> method.
675	<	*
676	<	* @return an Entry with greatest key, or <tt>null</tt>
677	<	* if the map is empty.
687	>	* @since 1.6
688		*/
689		public Map.Entry<K,V> lastEntry() {
690		Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
691	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
692		}
693
694		/**
695	<	* Removes and returns a key-value mapping associated with
686	<	* the least key in this map, or <tt>null</tt> if the map is empty.
687	<	*
688	<	* @return the removed first entry of this map, or <tt>null</tt>
689	<	* if the map is empty.
695	>	* @since 1.6
696		*/
697		public Map.Entry<K,V> pollFirstEntry() {
698		Entry<K,V> p = getFirstEntry();
699	<	if (p == null)
699	>	if (p == null)
700		return null;
701	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
701	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702		deleteEntry(p);
703		return result;
704		}
705
706		/**
707	<	* Removes and returns a key-value mapping associated with
702	<	* the greatest key in this map, or <tt>null</tt> if the map is empty.
703	<	*
704	<	* @return the removed last entry of this map, or <tt>null</tt>
705	<	* if the map is empty.
707	>	* @since 1.6
708		*/
709		public Map.Entry<K,V> pollLastEntry() {
710		Entry<K,V> p = getLastEntry();
711	<	if (p == null)
711	>	if (p == null)
712		return null;
713	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
713	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714		deleteEntry(p);
715		return result;
716		}
717
718		/**
719	<	* Returns a key-value mapping associated with the least key
720	<	* greater than or equal to the given key, or <tt>null</tt> if
721	<	* there is no such entry.
722	<	*
723	<	* @param key the key.
722	<	* @return an Entry associated with ceiling of given key, or
723	<	* <tt>null</tt> if there is no such Entry.
724	<	* @throws ClassCastException if key cannot be compared with the
725	<	* keys currently in the map.
726	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
727	<	*         natural order, or its comparator does not tolerate
728	<	*         <tt>null</tt> keys.
719	>	* @throws ClassCastException {@inheritDoc}
720	>	* @throws NullPointerException if the specified key is null
721	>	*         and this map uses natural ordering, or its comparator
722	>	*         does not permit null keys
723	>	* @since 1.6
724		*/
725	<	public Map.Entry<K,V> ceilingEntry(K key) {
726	<	Entry<K,V> e = getCeilingEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
725	>	public Map.Entry<K,V> lowerEntry(K key) {
726	>	Entry<K,V> e =  getLowerEntry(key);
727	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
728		}
729
735	–
730		/**
731	<	* Returns least key greater than or equal to the given key, or
732	<	* <tt>null</tt> if there is no such key.
733	<	*
734	<	* @param key the key.
735	<	* @return the ceiling key, or <tt>null</tt>
742	<	* if there is no such key.
743	<	* @throws ClassCastException if key cannot be compared with the keys
744	<	*            currently in the map.
745	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
746	<	*         natural order, or its comparator does not tolerate
747	<	*         <tt>null</tt> keys.
731	>	* @throws ClassCastException {@inheritDoc}
732	>	* @throws NullPointerException if the specified key is null
733	>	*         and this map uses natural ordering, or its comparator
734	>	*         does not permit null keys
735	>	* @since 1.6
736		*/
737	<	public K ceilingKey(K key) {
738	<	Entry<K,V> e = getCeilingEntry(key);
737	>	public K lowerKey(K key) {
738	>	Entry<K,V> e =  getLowerEntry(key);
739		return (e == null)? null : e.key;
740		}
741
754	–
755	–
742		/**
743	<	* Returns a key-value mapping associated with the greatest key
744	<	* less than or equal to the given key, or <tt>null</tt> if there
745	<	* is no such entry.
746	<	*
747	<	* @param key the key.
762	<	* @return an Entry associated with floor of given key, or <tt>null</tt>
763	<	* if there is no such Entry.
764	<	* @throws ClassCastException if key cannot be compared with the keys
765	<	*            currently in the map.
766	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
767	<	*         natural order, or its comparator does not tolerate
768	<	*         <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	>	* @since 1.6
748		*/
749		public Map.Entry<K,V> floorEntry(K key) {
750		Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
751	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
752		}
753
754		/**
755	<	* Returns the greatest key
756	<	* less than or equal to the given key, or <tt>null</tt> if there
757	<	* is no such key.
758	<	*
759	<	* @param key the key.
781	<	* @return the floor of given key, or <tt>null</tt> if there is no
782	<	* such key.
783	<	* @throws ClassCastException if key cannot be compared with the keys
784	<	*            currently in the map.
785	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
786	<	*         natural order, or its comparator does not tolerate
787	<	*         <tt>null</tt> keys.
755	>	* @throws ClassCastException {@inheritDoc}
756	>	* @throws NullPointerException if the specified key is null
757	>	*         and this map uses natural ordering, or its comparator
758	>	*         does not permit null keys
759	>	* @since 1.6
760		*/
761		public K floorKey(K key) {
762		Entry<K,V> e = getFloorEntry(key);
#	Line 792 | Line 764 | public class TreeMap<K,V>
764		}
765
766		/**
767	<	* Returns a key-value mapping associated with the least key
768	<	* strictly greater than the given key, or <tt>null</tt> if there
769	<	* is no such entry.
770	<	*
771	<	* @param key the key.
800	<	* @return an Entry with least key greater than the given key, or
801	<	* <tt>null</tt> if there is no such Entry.
802	<	* @throws ClassCastException if key cannot be compared with the keys
803	<	*            currently in the map.
804	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
805	<	*         natural order, or its comparator does not tolerate
806	<	*         <tt>null</tt> keys.
767	>	* @throws ClassCastException {@inheritDoc}
768	>	* @throws NullPointerException if the specified key is null
769	>	*         and this map uses natural ordering, or its comparator
770	>	*         does not permit null keys
771	>	* @since 1.6
772		*/
773	<	public Map.Entry<K,V> higherEntry(K key) {
774	<	Entry<K,V> e = getHigherEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
773	>	public Map.Entry<K,V> ceilingEntry(K key) {
774	>	Entry<K,V> e = getCeilingEntry(key);
775	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
776		}
777
778		/**
779	<	* Returns the least key strictly greater than the given key, or
780	<	* <tt>null</tt> if there is no such key.
781	<	*
782	<	* @param key the key.
783	<	* @return the least key greater than the given key, or
819	<	* <tt>null</tt> if there is no such key.
820	<	* @throws ClassCastException if key cannot be compared with the keys
821	<	*            currently in the map.
822	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
823	<	*         natural order, or its comparator does not tolerate
824	<	*         <tt>null</tt> keys.
779	>	* @throws ClassCastException {@inheritDoc}
780	>	* @throws NullPointerException if the specified key is null
781	>	*         and this map uses natural ordering, or its comparator
782	>	*         does not permit null keys
783	>	* @since 1.6
784		*/
785	<	public K higherKey(K key) {
786	<	Entry<K,V> e = getHigherEntry(key);
785	>	public K ceilingKey(K key) {
786	>	Entry<K,V> e = getCeilingEntry(key);
787		return (e == null)? null : e.key;
788		}
789
790		/**
791	<	* Returns a key-value mapping associated with the greatest
792	<	* key strictly less than the given key, or <tt>null</tt> if there is no
793	<	* such entry.
794	<	*
795	<	* @param key the key.
837	<	* @return an Entry with greatest key less than the given
838	<	* key, or <tt>null</tt> if there is no such Entry.
839	<	* @throws ClassCastException if key cannot be compared with the keys
840	<	*            currently in the map.
841	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
842	<	*         natural order, or its comparator does not tolerate
843	<	*         <tt>null</tt> keys.
791	>	* @throws ClassCastException {@inheritDoc}
792	>	* @throws NullPointerException if the specified key is null
793	>	*         and this map uses natural ordering, or its comparator
794	>	*         does not permit null keys
795	>	* @since 1.6
796		*/
797	<	public Map.Entry<K,V> lowerEntry(K key) {
798	<	Entry<K,V> e =  getLowerEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
797	>	public Map.Entry<K,V> higherEntry(K key) {
798	>	Entry<K,V> e = getHigherEntry(key);
799	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
800		}
801
802		/**
803	<	* Returns the greatest key strictly less than the given key, or
804	<	* <tt>null</tt> if there is no such key.
805	<	*
806	<	* @param key the key.
807	<	* @return the greatest key less than the given
856	<	* key, or <tt>null</tt> if there is no such key.
857	<	* @throws ClassCastException if key cannot be compared with the keys
858	<	*            currently in the map.
859	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
860	<	*         natural order, or its comparator does not tolerate
861	<	*         <tt>null</tt> keys.
803	>	* @throws ClassCastException {@inheritDoc}
804	>	* @throws NullPointerException if the specified key is null
805	>	*         and this map uses natural ordering, or its comparator
806	>	*         does not permit null keys
807	>	* @since 1.6
808		*/
809	<	public K lowerKey(K key) {
810	<	Entry<K,V> e =  getLowerEntry(key);
809	>	public K higherKey(K key) {
810	>	Entry<K,V> e = getHigherEntry(key);
811		return (e == null)? null : e.key;
812		}
813
#	Line 872 | Line 818 | public class TreeMap<K,V>
818		* the first time this view is requested.  Views are stateless, so
819		* there's no reason to create more than one.
820		*/
821	<	private transient Set<Map.Entry<K,V>> entrySet = null;
822	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
823	<	private transient Set<K> descendingKeySet = null;
824	<
825	<	transient Set<K> keySet = null;        // XXX remove when integrated
826	<	transient Collection<V> values = null; // XXX remove when integrated
827	<
828	<	/**
829	<	* Returns a Set view of the keys contained in this map.  The set's
830	<	* iterator will return the keys in ascending order.  The set is backed by
831	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
832	<	* the Set, and vice-versa.  The Set supports element removal, which
833	<	* removes the corresponding mapping from the map, via the
834	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
835	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
836	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
837	<	*
892	<	* @return a set view of the keys contained in this TreeMap.
821	>	private transient EntrySet entrySet = null;
822	>	private transient KeySet<K> navigableKeySet = null;
823	>	private transient NavigableMap<K,V> descendingMap = null;
824	>
825	>	/**
826	>	* Returns a {@link Set} view of the keys contained in this map.
827	>	* The set's iterator returns the keys in ascending order.
828	>	* The set is backed by the map, so changes to the map are
829	>	* reflected in the set, and vice-versa.  If the map is modified
830	>	* while an iteration over the set is in progress (except through
831	>	* the iterator's own <tt>remove</tt> operation), the results of
832	>	* the iteration are undefined.  The set supports element removal,
833	>	* which removes the corresponding mapping from the map, via the
834	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
835	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
836	>	* operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
837	>	* operations.
838		*/
839		public Set<K> keySet() {
840	<	Set<K> ks = keySet;
896	<	return (ks != null) ? ks : (keySet = new KeySet());
840	>	return navigableKeySet();
841		}
842
843	<	class KeySet extends AbstractSet<K> {
844	<	public Iterator<K> iterator() {
845	<	return new KeyIterator(getFirstEntry());
846	<	}
847	<
848	<	public int size() {
905	<	return TreeMap.this.size();
906	<	}
907	<
908	<	public boolean contains(Object o) {
909	<	return containsKey(o);
910	<	}
911	<
912	<	public boolean remove(Object o) {
913	<	int oldSize = size;
914	<	TreeMap.this.remove(o);
915	<	return size != oldSize;
916	<	}
917	<
918	<	public void clear() {
919	<	TreeMap.this.clear();
920	<	}
843	>	/**
844	>	* @since 1.6
845	>	*/
846	>	public NavigableSet<K> navigableKeySet() {
847	>	KeySet<K> nks = navigableKeySet;
848	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
849		}
850
851		/**
852	<	* Returns a collection view of the values contained in this map.  The
853	<	* collection's iterator will return the values in the order that their
854	<	* corresponding keys appear in the tree.  The collection is backed by
855	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
856	<	* the collection, and vice-versa.  The collection supports element
857	<	* removal, which removes the corresponding mapping from the map through
858	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
859	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
860	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
861	<	*
862	<	* @return a collection view of the values contained in this map.
852	>	* @since 1.6
853	>	*/
854	>	public NavigableSet<K> descendingKeySet() {
855	>	return descendingMap().navigableKeySet();
856	>	}
857	>
858	>	/**
859	>	* Returns a {@link Collection} view of the values contained in this map.
860	>	* The collection's iterator returns the values in ascending order
861	>	* of the corresponding keys.
862	>	* The collection is backed by the map, so changes to the map are
863	>	* reflected in the collection, and vice-versa.  If the map is
864	>	* modified while an iteration over the collection is in progress
865	>	* (except through the iterator's own <tt>remove</tt> operation),
866	>	* the results of the iteration are undefined.  The collection
867	>	* supports element removal, which removes the corresponding
868	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
869	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
870	>	* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
871	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
872		*/
873		public Collection<V> values() {
874		Collection<V> vs = values;
875		return (vs != null) ? vs : (values = new Values());
876		}
877
878	+	/**
879	+	* Returns a {@link Set} view of the mappings contained in this map.
880	+	* The set's iterator returns the entries in ascending key order.
881	+	* The set is backed by the map, so changes to the map are
882	+	* reflected in the set, and vice-versa.  If the map is modified
883	+	* while an iteration over the set is in progress (except through
884	+	* the iterator's own <tt>remove</tt> operation, or through the
885	+	* <tt>setValue</tt> operation on a map entry returned by the
886	+	* iterator) the results of the iteration are undefined.  The set
887	+	* supports element removal, which removes the corresponding
888	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
889	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
890	+	* <tt>clear</tt> operations.  It does not support the
891	+	* <tt>add</tt> or <tt>addAll</tt> operations.
892	+	*/
893	+	public Set<Map.Entry<K,V>> entrySet() {
894	+	EntrySet es = entrySet;
895	+	return (es != null) ? es : (entrySet = new EntrySet());
896	+	}
897	+
898	+	/**
899	+	* @since 1.6
900	+	*/
901	+	public NavigableMap<K, V> descendingMap() {
902	+	NavigableMap<K, V> km = descendingMap;
903	+	return (km != null) ? km :
904	+	(descendingMap = new DescendingSubMap(this,
905	+	true, null, true,
906	+	true, null, true));
907	+	}
908	+
909	+	/**
910	+	* @throws ClassCastException       {@inheritDoc}
911	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
912	+	*         null and this map uses natural ordering, or its comparator
913	+	*         does not permit null keys
914	+	* @throws IllegalArgumentException {@inheritDoc}
915	+	* @since 1.6
916	+	*/
917	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
918	+	K toKey,   boolean toInclusive) {
919	+	return new AscendingSubMap(this,
920	+	false, fromKey, fromInclusive,
921	+	false, toKey,   toInclusive);
922	+	}
923	+
924	+	/**
925	+	* @throws ClassCastException       {@inheritDoc}
926	+	* @throws NullPointerException if <tt>toKey</tt> is null
927	+	*         and this map uses natural ordering, or its comparator
928	+	*         does not permit null keys
929	+	* @throws IllegalArgumentException {@inheritDoc}
930	+	* @since 1.6
931	+	*/
932	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
933	+	return new AscendingSubMap(this,
934	+	true,  null,  true,
935	+	false, toKey, inclusive);
936	+	}
937	+
938	+	/**
939	+	* @throws ClassCastException       {@inheritDoc}
940	+	* @throws NullPointerException if <tt>fromKey</tt> is null
941	+	*         and this map uses natural ordering, or its comparator
942	+	*         does not permit null keys
943	+	* @throws IllegalArgumentException {@inheritDoc}
944	+	* @since 1.6
945	+	*/
946	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
947	+	return new AscendingSubMap(this,
948	+	false, fromKey, inclusive,
949	+	true,  null,    true);
950	+	}
951	+
952	+	/**
953	+	* @throws ClassCastException       {@inheritDoc}
954	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
955	+	*         null and this map uses natural ordering, or its comparator
956	+	*         does not permit null keys
957	+	* @throws IllegalArgumentException {@inheritDoc}
958	+	*/
959	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
960	+	return subMap(fromKey, true, toKey, false);
961	+	}
962	+
963	+	/**
964	+	* @throws ClassCastException       {@inheritDoc}
965	+	* @throws NullPointerException if <tt>toKey</tt> is null
966	+	*         and this map uses natural ordering, or its comparator
967	+	*         does not permit null keys
968	+	* @throws IllegalArgumentException {@inheritDoc}
969	+	*/
970	+	public SortedMap<K,V> headMap(K toKey) {
971	+	return headMap(toKey, false);
972	+	}
973	+
974	+	/**
975	+	* @throws ClassCastException       {@inheritDoc}
976	+	* @throws NullPointerException if <tt>fromKey</tt> is null
977	+	*         and this map uses natural ordering, or its comparator
978	+	*         does not permit null keys
979	+	* @throws IllegalArgumentException {@inheritDoc}
980	+	*/
981	+	public SortedMap<K,V> tailMap(K fromKey) {
982	+	return tailMap(fromKey, true);
983	+	}
984	+
985	+	// View class support
986	+
987		class Values extends AbstractCollection<V> {
988		public Iterator<V> iterator() {
989		return new ValueIterator(getFirstEntry());
990		}
991	<
991	>
992		public int size() {
993		return TreeMap.this.size();
994		}
995	<
995	>
996		public boolean contains(Object o) {
997		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
998		if (valEquals(e.getValue(), o))
999		return true;
1000		return false;
1001		}
1002	<
1002	>
1003		public boolean remove(Object o) {
1004		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
1005		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 1009 | public class TreeMap<K,V>
1009		}
1010		return false;
1011		}
1012	<
1012	>
1013		public void clear() {
1014		TreeMap.this.clear();
1015		}
1016		}
1017
972	–	/**
973	–	* Returns a set view of the mappings contained in this map.  The set's
974	–	* iterator returns the mappings in ascending key order.  Each element in
975	–	* the returned set is a <tt>Map.Entry</tt>.  The set is backed by this
976	–	* map, so changes to this map are reflected in the set, and vice-versa.
977	–	* The set supports element removal, which removes the corresponding
978	–	* mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
979	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
980	–	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
981	–	* <tt>addAll</tt> operations.
982	–	*
983	–	* @return a set view of the mappings contained in this map.
984	–	* @see Map.Entry
985	–	*/
986	–	public Set<Map.Entry<K,V>> entrySet() {
987	–	Set<Map.Entry<K,V>> es = entrySet;
988	–	return (es != null) ? es : (entrySet = new EntrySet());
989	–	}
990	–
1018		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1019		public Iterator<Map.Entry<K,V>> iterator() {
1020		return new EntryIterator(getFirstEntry());
1021		}
1022	<
1022	>
1023		public boolean contains(Object o) {
1024		if (!(o instanceof Map.Entry))
1025		return false;
#	Line 1001 | Line 1028 | public class TreeMap<K,V>
1028		Entry<K,V> p = getEntry(entry.getKey());
1029		return p != null && valEquals(p.getValue(), value);
1030		}
1031	<
1031	>
1032		public boolean remove(Object o) {
1033		if (!(o instanceof Map.Entry))
1034		return false;
#	Line 1014 | Line 1041 | public class TreeMap<K,V>
1041		}
1042		return false;
1043		}
1044	<
1044	>
1045		public int size() {
1046		return TreeMap.this.size();
1047		}
1048	<
1048	>
1049		public void clear() {
1050		TreeMap.this.clear();
1051		}
1052		}
1053
1054	<	/**
1055	<	* Returns a set view of the mappings contained in this map.  The
1056	<	* set's iterator returns the mappings in descending key order.
1057	<	* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1058	<	* set is backed by this map, so changes to this map are reflected
1059	<	* in the set, and vice-versa.  The set supports element removal,
1060	<	* which removes the corresponding mapping from the TreeMap,
1061	<	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1062	<	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1063	<	* 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	<	*/
1043	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1044	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
1045	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1054	>	/*
1055	>	* Unlike Values and EntrySet, the KeySet class is static,
1056	>	* delegating to a NavigableMap to allow use by SubMaps, which
1057	>	* outweighs the ugliness of needing type-tests for the following
1058	>	* Iterator methods that are defined appropriately in main versus
1059	>	* submap classes.
1060	>	*/
1061	>
1062	>	Iterator<K> keyIterator() {
1063	>	return new KeyIterator(getFirstEntry());
1064		}
1065
1066	<	class DescendingEntrySet extends EntrySet {
1067	<	public Iterator<Map.Entry<K,V>> iterator() {
1068	<	return new DescendingEntryIterator(getLastEntry());
1066	>	Iterator<K> descendingKeyIterator() {
1067	>	return new DescendingKeyIterator(getFirstEntry());
1068	>	}
1069	>
1070	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1071	>	private final NavigableMap<E, Object> m;
1072	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1073	>
1074	>	public Iterator<E> iterator() {
1075	>	if (m instanceof TreeMap)
1076	>	return ((TreeMap<E,Object>)m).keyIterator();
1077	>	else
1078	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1079	>	}
1080	>
1081	>	public Iterator<E> descendingIterator() {
1082	>	if (m instanceof TreeMap)
1083	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1084	>	else
1085	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1086	>	}
1087	>
1088	>	public int size() { return m.size(); }
1089	>	public boolean isEmpty() { return m.isEmpty(); }
1090	>	public boolean contains(Object o) { return m.containsKey(o); }
1091	>	public void clear() { m.clear(); }
1092	>	public E lower(E e) { return m.lowerKey(e); }
1093	>	public E floor(E e) { return m.floorKey(e); }
1094	>	public E ceiling(E e) { return m.ceilingKey(e); }
1095	>	public E higher(E e) { return m.higherKey(e); }
1096	>	public E first() { return m.firstKey(); }
1097	>	public E last() { return m.lastKey(); }
1098	>	public Comparator<? super E> comparator() { return m.comparator(); }
1099	>	public E pollFirst() {
1100	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1101	>	return e == null? null : e.getKey();
1102	>	}
1103	>	public E pollLast() {
1104	>	Map.Entry<E,Object> e = m.pollLastEntry();
1105	>	return e == null? null : e.getKey();
1106	>	}
1107	>	public boolean remove(Object o) {
1108	>	int oldSize = size();
1109	>	m.remove(o);
1110	>	return size() != oldSize;
1111	>	}
1112	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1113	>	E toElement, boolean toInclusive) {
1114	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1115	>	toElement,   toInclusive));
1116	>	}
1117	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1118	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1119	>	}
1120	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1121	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1122	>	}
1123	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1124	>	return subSet(fromElement, true, toElement, false);
1125	>	}
1126	>	public SortedSet<E> headSet(E toElement) {
1127	>	return headSet(toElement, false);
1128	>	}
1129	>	public SortedSet<E> tailSet(E fromElement) {
1130	>	return tailSet(fromElement, true);
1131	>	}
1132	>	public NavigableSet<E> descendingSet() {
1133	>	return new TreeSet(m.descendingMap());
1134		}
1135		}
1136
1137		/**
1138	<	* 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.
1138	>	* Base class for TreeMap Iterators
1139		*/
1140	<	public Set<K> descendingKeySet() {
1141	<	Set<K> ks = descendingKeySet;
1142	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1143	<	}
1144	<
1145	<	class DescendingKeySet extends KeySet {
1146	<	public Iterator<K> iterator() {
1147	<	return new DescendingKeyIterator(getLastEntry());
1140	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1141	>	Entry<K,V> next;
1142	>	Entry<K,V> lastReturned;
1143	>	int expectedModCount;
1144	>
1145	>	PrivateEntryIterator(Entry<K,V> first) {
1146	>	expectedModCount = modCount;
1147	>	lastReturned = null;
1148	>	next = first;
1149	>	}
1150	>
1151	>	public final boolean hasNext() {
1152	>	return next != null;
1153	>	}
1154	>
1155	>	final Entry<K,V> nextEntry() {
1156	>	Entry<K,V> e = lastReturned = next;
1157	>	if (e == null)
1158	>	throw new NoSuchElementException();
1159	>	if (modCount != expectedModCount)
1160	>	throw new ConcurrentModificationException();
1161	>	next = successor(e);
1162	>	return e;
1163	>	}
1164	>
1165	>	final Entry<K,V> prevEntry() {
1166	>	Entry<K,V> e = lastReturned= next;
1167	>	if (e == null)
1168	>	throw new NoSuchElementException();
1169	>	if (modCount != expectedModCount)
1170	>	throw new ConcurrentModificationException();
1171	>	next = predecessor(e);
1172	>	return e;
1173	>	}
1174	>
1175	>	public void remove() {
1176	>	if (lastReturned == null)
1177	>	throw new IllegalStateException();
1178	>	if (modCount != expectedModCount)
1179	>	throw new ConcurrentModificationException();
1180	>	if (lastReturned.left != null && lastReturned.right != null)
1181	>	next = lastReturned;
1182	>	deleteEntry(lastReturned);
1183	>	expectedModCount++;
1184	>	lastReturned = null;
1185		}
1186		}
1187
1188	<	/**
1189	<	* Returns a view of the portion of this map whose keys range from
1190	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1191	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
1192	<	* is empty.)  The returned sorted map is backed by this map, so changes
1193	<	* in the returned sorted map are reflected in this map, and vice-versa.
1194	<	* The returned sorted map supports all optional map operations.<p>
1085	<	*
1086	<	* The sorted map returned by this method will throw an
1087	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1088	<	* less than <tt>fromKey</tt> or greater than or equal to
1089	<	* <tt>toKey</tt>.<p>
1090	<	*
1091	<	* Note: this method always returns a <i>half-open range</i> (which
1092	<	* includes its low endpoint but not its high endpoint).  If you need a
1093	<	* <i>closed range</i> (which includes both endpoints), and the key type
1094	<	* allows for calculation of the successor a given key, merely request the
1095	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1096	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys are
1097	<	* strings.  The following idiom obtains a view containing all of the
1098	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1099	<	* and <tt>high</tt>, inclusive:
1100	<	*             <pre>    NavigableMap sub = m.submap(low, high+"\0");</pre>
1101	<	* A similar technique can be used to generate an <i>open range</i> (which
1102	<	* contains neither endpoint).  The following idiom obtains a view
1103	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1104	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1105	<	*             <pre>    NavigableMap sub = m.subMap(low+"\0", high);</pre>
1106	<	*
1107	<	* @param fromKey low endpoint (inclusive) of the subMap.
1108	<	* @param toKey high endpoint (exclusive) of the subMap.
1109	<	*
1110	<	* @return a view of the portion of this map whose keys range from
1111	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1112	<	*
1113	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1114	<	*         cannot be compared to one another using this map's comparator
1115	<	*         (or, if the map has no comparator, using natural ordering).
1116	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1117	<	*         <tt>toKey</tt>.
1118	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1119	<	*               <tt>null</tt> and this map uses natural order, or its
1120	<	*               comparator does not tolerate <tt>null</tt> keys.
1121	<	*/
1122	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1123	<	return new SubMap(fromKey, toKey);
1188	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1189	>	EntryIterator(Entry<K,V> first) {
1190	>	super(first);
1191	>	}
1192	>	public Map.Entry<K,V> next() {
1193	>	return nextEntry();
1194	>	}
1195		}
1196
1197	<	/**
1198	<	* Returns a view of the portion of this map whose keys are strictly less
1199	<	* than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
1200	<	* changes in the returned sorted map are reflected in this map, and
1201	<	* vice-versa.  The returned sorted map supports all optional map
1202	<	* operations.<p>
1203	<	*
1204	<	* The sorted 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 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 sorted 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.headMap(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.
1162	<	*/
1163	<	public NavigableMap<K,V> headMap(K toKey) {
1164	<	return new SubMap(toKey, true);
1165	<	}
1166	<
1167	<	/**
1168	<	* Returns a view of the portion of this map whose keys are greater than
1169	<	* or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
1170	<	* this map, so changes in the returned sorted map are reflected in this
1171	<	* map, and vice-versa.  The returned sorted map supports all optional map
1172	<	* operations.<p>
1173	<	*
1174	<	* The sorted 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 a given value,
1181	<	* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1182	<	* For example, suppose that <tt>m</tt> is a sorted 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.tailMap(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.
1201	<	*/
1202	<	public NavigableMap<K,V> tailMap(K fromKey) {
1203	<	return new SubMap(fromKey, false);
1204	<	}
1205	<
1206	<	private class SubMap
1207	<	extends AbstractMap<K,V>
1208	<	implements NavigableMap<K,V>, java.io.Serializable {
1209	<	private static final long serialVersionUID = -6520786458950516097L;
1197	>	final class ValueIterator extends PrivateEntryIterator<V> {
1198	>	ValueIterator(Entry<K,V> first) {
1199	>	super(first);
1200	>	}
1201	>	public V next() {
1202	>	return nextEntry().value;
1203	>	}
1204	>	}
1205
1206	<	/**
1207	<	* fromKey is significant only if fromStart is false.  Similarly,
1208	<	* toKey is significant only if toStart is false.
1209	<	*/
1210	<	private boolean fromStart = false, toEnd = false;
1211	<	private K fromKey, toKey;
1206	>	final class KeyIterator extends PrivateEntryIterator<K> {
1207	>	KeyIterator(Entry<K,V> first) {
1208	>	super(first);
1209	>	}
1210	>	public K next() {
1211	>	return nextEntry().key;
1212	>	}
1213	>	}
1214
1215	<	SubMap(K fromKey, K toKey) {
1216	<	if (compare(fromKey, toKey) > 0)
1217	<	throw new IllegalArgumentException("fromKey > toKey");
1218	<	this.fromKey = fromKey;
1219	<	this.toKey = toKey;
1215	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1216	>	DescendingKeyIterator(Entry<K,V> first) {
1217	>	super(first);
1218	>	}
1219	>	public K next() {
1220	>	return prevEntry().key;
1221		}
1222	+	}
1223	+
1224	+	// SubMaps
1225	+
1226	+	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1227	+	implements NavigableMap<K,V>, java.io.Serializable {
1228	+	/*
1229	+	* The backing map.
1230	+	*/
1231	+	final TreeMap<K,V> m;
1232
1233	<	SubMap(K key, boolean headMap) {
1234	<	compare(key, key); // Type-check key
1235	<
1236	<	if (headMap) {
1237	<	fromStart = true;
1238	<	toKey = key;
1233	>	/*
1234	>	* Endpoints are represented as triples (fromStart, lo,
1235	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1236	>	* true, then the low (absolute) bound is the start of the
1237	>	* backing map, and the other values are ignored. Otherwise,
1238	>	* if loInclusive is true, lo is the inclusive bound, else lo
1239	>	* is the exclusive bound. Similarly for the upper bound.
1240	>	*/
1241	>
1242	>	final K lo, hi;
1243	>	final boolean fromStart, toEnd;
1244	>	final boolean loInclusive, hiInclusive;
1245	>
1246	>	NavigableSubMap(TreeMap<K,V> m,
1247	>	boolean fromStart, K lo, boolean loInclusive,
1248	>	boolean toEnd,     K hi, boolean hiInclusive) {
1249	>	if (!fromStart && !toEnd) {
1250	>	if (m.compare(lo, hi) > 0)
1251	>	throw new IllegalArgumentException("fromKey > toKey");
1252		} else {
1253	<	toEnd = true;
1254	<	fromKey = key;
1253	>	if (!fromStart) // type check
1254	>	m.compare(lo, lo);
1255	>	if (!toEnd)
1256	>	m.compare(hi, hi);
1257		}
1235	–	}
1258
1259	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1259	>	this.m = m;
1260		this.fromStart = fromStart;
1261	<	this.fromKey= fromKey;
1261	>	this.lo = lo;
1262	>	this.loInclusive = loInclusive;
1263		this.toEnd = toEnd;
1264	<	this.toKey = toKey;
1264	>	this.hi = hi;
1265	>	this.hiInclusive = hiInclusive;
1266	>	}
1267	>
1268	>	// internal utilities
1269	>
1270	>	final boolean tooLow(Object key) {
1271	>	if (!fromStart) {
1272	>	int c = m.compare(key, lo);
1273	>	if (c < 0 || (c == 0 && !loInclusive))
1274	>	return true;
1275	>	}
1276	>	return false;
1277	>	}
1278	>
1279	>	final boolean tooHigh(Object key) {
1280	>	if (!toEnd) {
1281	>	int c = m.compare(key, hi);
1282	>	if (c > 0 || (c == 0 && !hiInclusive))
1283	>	return true;
1284	>	}
1285	>	return false;
1286	>	}
1287	>
1288	>	final boolean inRange(Object key) {
1289	>	return !tooLow(key) && !tooHigh(key);
1290	>	}
1291	>
1292	>	final boolean inClosedRange(Object key) {
1293	>	return (fromStart || m.compare(key, lo) >= 0)
1294	>	&& (toEnd || m.compare(hi, key) >= 0);
1295	>	}
1296	>
1297	>	final boolean inRange(Object key, boolean inclusive) {
1298	>	return inclusive ? inRange(key) : inClosedRange(key);
1299	>	}
1300	>
1301	>	/**
1302	>	* Return SimpleImmutableEntry for entry, or null if null
1303	>	*/
1304	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1305	>	return e == null? null :
1306	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1307	>	}
1308	>
1309	>	/**
1310	>	* Return key for entry, or null if null
1311	>	*/
1312	>	static <K,V> K exportKey(TreeMap.Entry<K,V> e) {
1313	>	return e == null? null : e.key;
1314	>	}
1315	>
1316	>	/*
1317	>	* Absolute versions of relation operations.
1318	>	* Subclasses map to these using like-named "sub"
1319	>	* versions that invert senses for descending maps
1320	>	*/
1321	>
1322	>	final TreeMap.Entry<K,V> absLowest() {
1323	>	TreeMap.Entry<K,V> e =
1324	>	(fromStart ?  m.getFirstEntry() :
1325	>	(loInclusive ? m.getCeilingEntry(lo) :
1326	>	m.getHigherEntry(lo)));
1327	>	return (e == null || tooHigh(e.key)) ? null : e;
1328	>	}
1329	>
1330	>	final TreeMap.Entry<K,V> absHighest() {
1331	>	TreeMap.Entry<K,V> e =
1332	>	(toEnd ?  m.getLastEntry() :
1333	>	(hiInclusive ?  m.getFloorEntry(hi) :
1334	>	m.getLowerEntry(hi)));
1335	>	return (e == null || tooLow(e.key)) ? null : e;
1336	>	}
1337	>
1338	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1339	>	if (tooLow(key))
1340	>	return absLowest();
1341	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1342	>	return (e == null || tooHigh(e.key)) ? null : e;
1343		}
1344
1345	+	final TreeMap.Entry<K,V> absHigher(K key) {
1346	+	if (tooLow(key))
1347	+	return absLowest();
1348	+	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1349	+	return (e == null || tooHigh(e.key)) ? null : e;
1350	+	}
1351	+
1352	+	final TreeMap.Entry<K,V> absFloor(K key) {
1353	+	if (tooHigh(key))
1354	+	return absHighest();
1355	+	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1356	+	return (e == null || tooLow(e.key)) ? null : e;
1357	+	}
1358	+
1359	+	final TreeMap.Entry<K,V> absLower(K key) {
1360	+	if (tooHigh(key))
1361	+	return absHighest();
1362	+	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1363	+	return (e == null || tooLow(e.key)) ? null : e;
1364	+	}
1365	+
1366	+	/** Returns the absolute high fence for ascending traversal */
1367	+	final TreeMap.Entry<K,V> absHighFence() {
1368	+	return (toEnd ? null : (hiInclusive ?
1369	+	m.getHigherEntry(hi) :
1370	+	m.getCeilingEntry(hi)));
1371	+	}
1372	+
1373	+	/** Return the absolute low fence for descending traversal  */
1374	+	final TreeMap.Entry<K,V> absLowFence() {
1375	+	return (fromStart ? null : (loInclusive ?
1376	+	m.getLowerEntry(lo) :
1377	+	m.getFloorEntry(lo)));
1378	+	}
1379	+
1380	+	// Abstract methods defined in ascending vs descending classes
1381	+	// These relay to the appropriate  absolute versions
1382	+
1383	+	abstract TreeMap.Entry<K,V> subLowest();
1384	+	abstract TreeMap.Entry<K,V> subHighest();
1385	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1386	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1387	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1388	+	abstract TreeMap.Entry<K,V> subLower(K key);
1389	+
1390	+	/** Returns ascending iterator from the perspective of this submap */
1391	+	abstract Iterator<K> keyIterator();
1392	+
1393	+	/** Returns descending iterator from the perspective of this submap */
1394	+	abstract Iterator<K> descendingKeyIterator();
1395	+
1396	+	// public methods
1397	+
1398		public boolean isEmpty() {
1399	<	return entrySet.isEmpty();
1399	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1400		}
1401
1402	<	public boolean containsKey(Object key) {
1403	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1402	>	public int size() {
1403	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1404		}
1405
1406	<	public V get(Object key) {
1407	<	if (!inRange((K) key))
1254	<	return null;
1255	<	return TreeMap.this.get(key);
1406	>	public final boolean containsKey(Object key) {
1407	>	return inRange(key) && m.containsKey(key);
1408		}
1409
1410	<	public V put(K key, V value) {
1410	>	public final V put(K key, V value) {
1411		if (!inRange(key))
1412		throw new IllegalArgumentException("key out of range");
1413	<	return TreeMap.this.put(key, value);
1413	>	return m.put(key, value);
1414		}
1415
1416	<	public V remove(Object key) {
1417	<	if (!inRange((K) key))
1266	<	return null;
1267	<	return TreeMap.this.remove(key);
1416	>	public final V get(Object key) {
1417	>	return !inRange(key)? null :  m.get(key);
1418		}
1419
1420	<	public Comparator<? super K> comparator() {
1421	<	return comparator;
1420	>	public final V remove(Object key) {
1421	>	return !inRange(key)? null  : m.remove(key);
1422		}
1423
1424	<	public K firstKey() {
1425	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1276	<	K first = key(e);
1277	<	if (!toEnd && compare(first, toKey) >= 0)
1278	<	throw(new NoSuchElementException());
1279	<	return first;
1280	<	}
1281	<
1282	<	public K lastKey() {
1283	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1284	<	K last = key(e);
1285	<	if (!fromStart && compare(last, fromKey) < 0)
1286	<	throw(new NoSuchElementException());
1287	<	return last;
1288	<	}
1289	<
1290	<	public Map.Entry<K,V> firstEntry() {
1291	<	TreeMap.Entry<K,V> e = fromStart ?
1292	<	getFirstEntry() : getCeilingEntry(fromKey);
1293	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1294	<	return null;
1295	<	return e;
1424	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1425	>	return exportEntry(subCeiling(key));
1426		}
1427
1428	<	public Map.Entry<K,V> lastEntry() {
1429	<	TreeMap.Entry<K,V> e = toEnd ?
1300	<	getLastEntry() : getLowerEntry(toKey);
1301	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1302	<	return null;
1303	<	return e;
1428	>	public final K ceilingKey(K key) {
1429	>	return exportKey(subCeiling(key));
1430		}
1431
1432	<	public Map.Entry<K,V> pollFirstEntry() {
1433	<	TreeMap.Entry<K,V> e = fromStart ?
1308	<	getFirstEntry() : getCeilingEntry(fromKey);
1309	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1310	<	return null;
1311	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1312	<	deleteEntry(e);
1313	<	return result;
1432	>	public final Map.Entry<K,V> higherEntry(K key) {
1433	>	return exportEntry(subHigher(key));
1434		}
1435
1436	<	public Map.Entry<K,V> pollLastEntry() {
1437	<	TreeMap.Entry<K,V> e = toEnd ?
1318	<	getLastEntry() : getLowerEntry(toKey);
1319	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1320	<	return null;
1321	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1322	<	deleteEntry(e);
1323	<	return result;
1436	>	public final K higherKey(K key) {
1437	>	return exportKey(subHigher(key));
1438		}
1439
1440	<	private TreeMap.Entry<K,V> subceiling(K key) {
1441	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1328	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1329	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1330	<	return null;
1331	<	return e;
1440	>	public final Map.Entry<K,V> floorEntry(K key) {
1441	>	return exportEntry(subFloor(key));
1442		}
1443
1444	<	public Map.Entry<K,V> ceilingEntry(K key) {
1445	<	TreeMap.Entry<K,V> e = subceiling(key);
1336	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1444	>	public final K floorKey(K key) {
1445	>	return exportKey(subFloor(key));
1446		}
1447
1448	<	public K ceilingKey(K key) {
1449	<	TreeMap.Entry<K,V> e = subceiling(key);
1341	<	return e == null? null : e.key;
1448	>	public final Map.Entry<K,V> lowerEntry(K key) {
1449	>	return exportEntry(subLower(key));
1450		}
1451
1452	+	public final K lowerKey(K key) {
1453	+	return exportKey(subLower(key));
1454	+	}
1455
1456	<	private TreeMap.Entry<K,V> subhigher(K key) {
1457	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1347	<	getCeilingEntry(fromKey) : getHigherEntry(key);
1348	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1349	<	return null;
1350	<	return e;
1456	>	public final K firstKey() {
1457	>	return key(subLowest());
1458		}
1459
1460	<	public Map.Entry<K,V> higherEntry(K key) {
1461	<	TreeMap.Entry<K,V> e = subhigher(key);
1355	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1460	>	public final K lastKey() {
1461	>	return key(subHighest());
1462		}
1463
1464	<	public K higherKey(K key) {
1465	<	TreeMap.Entry<K,V> e = subhigher(key);
1360	<	return e == null? null : e.key;
1464	>	public final Map.Entry<K,V> firstEntry() {
1465	>	return exportEntry(subLowest());
1466		}
1467
1468	<	private TreeMap.Entry<K,V> subfloor(K key) {
1469	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1365	<	getLowerEntry(toKey) : getFloorEntry(key);
1366	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1367	<	return null;
1368	<	return e;
1468	>	public final Map.Entry<K,V> lastEntry() {
1469	>	return exportEntry(subHighest());
1470		}
1471
1472	<	public Map.Entry<K,V> floorEntry(K key) {
1473	<	TreeMap.Entry<K,V> e = subfloor(key);
1474	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1472	>	public final Map.Entry<K,V> pollFirstEntry() {
1473	>	TreeMap.Entry<K,V> e = subLowest();
1474	>	Map.Entry<K,V> result = exportEntry(e);
1475	>	if (e != null)
1476	>	m.deleteEntry(e);
1477	>	return result;
1478		}
1479
1480	<	public K floorKey(K key) {
1481	<	TreeMap.Entry<K,V> e = subfloor(key);
1482	<	return e == null? null : e.key;
1480	>	public final Map.Entry<K,V> pollLastEntry() {
1481	>	TreeMap.Entry<K,V> e = subHighest();
1482	>	Map.Entry<K,V> result = exportEntry(e);
1483	>	if (e != null)
1484	>	m.deleteEntry(e);
1485	>	return result;
1486		}
1487
1488	<	private TreeMap.Entry<K,V> sublower(K key) {
1489	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1490	<	getLowerEntry(toKey) :  getLowerEntry(key);
1491	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1492	<	return null;
1493	<	return e;
1488	>	// Views
1489	>	transient NavigableMap<K,V> descendingMapView = null;
1490	>	transient EntrySetView entrySetView = null;
1491	>	transient KeySet<K> navigableKeySetView = null;
1492	>
1493	>	public final NavigableSet<K> navigableKeySet() {
1494	>	KeySet<K> nksv = navigableKeySetView;
1495	>	return (nksv != null) ? nksv :
1496	>	(navigableKeySetView = new TreeMap.KeySet(this));
1497		}
1498
1499	<	public Map.Entry<K,V> lowerEntry(K key) {
1500	<	TreeMap.Entry<K,V> e = sublower(key);
1391	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1499	>	public final Set<K> keySet() {
1500	>	return navigableKeySet();
1501		}
1502
1503	<	public K lowerKey(K key) {
1504	<	TreeMap.Entry<K,V> e = sublower(key);
1505	<	return e == null? null : e.key;
1503	>	public NavigableSet<K> descendingKeySet() {
1504	>	return descendingMap().navigableKeySet();
1505	>	}
1506	>
1507	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1508	>	return subMap(fromKey, true, toKey, false);
1509		}
1510
1511	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1511	>	public final SortedMap<K,V> headMap(K toKey) {
1512	>	return headMap(toKey, false);
1513	>	}
1514
1515	<	public Set<Map.Entry<K,V>> entrySet() {
1516	<	return entrySet;
1515	>	public final SortedMap<K,V> tailMap(K fromKey) {
1516	>	return tailMap(fromKey, true);
1517		}
1518
1519	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1519	>	// View classes
1520	>
1521	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1522		private transient int size = -1, sizeModCount;
1523
1524		public int size() {
1525	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1526	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1525	>	if (fromStart && toEnd)
1526	>	return m.size();
1527	>	if (size == -1 || sizeModCount != m.modCount) {
1528	>	sizeModCount = m.modCount;
1529	>	size = 0;
1530		Iterator i = iterator();
1531		while (i.hasNext()) {
1532		size++;
#	Line 1418 | Line 1537 | public class TreeMap<K,V>
1537		}
1538
1539		public boolean isEmpty() {
1540	<	return !iterator().hasNext();
1540	>	TreeMap.Entry<K,V> n = absLowest();
1541	>	return n == null || tooHigh(n.key);
1542		}
1543
1544		public boolean contains(Object o) {
#	Line 1428 | Line 1548 | public class TreeMap<K,V>
1548		K key = entry.getKey();
1549		if (!inRange(key))
1550		return false;
1551	<	TreeMap.Entry node = getEntry(key);
1551	>	TreeMap.Entry node = m.getEntry(key);
1552		return node != null &&
1553	<	valEquals(node.getValue(), entry.getValue());
1553	>	valEquals(node.getValue(), entry.getValue());
1554		}
1555
1556		public boolean remove(Object o) {
#	Line 1440 | Line 1560 | public class TreeMap<K,V>
1560		K key = entry.getKey();
1561		if (!inRange(key))
1562		return false;
1563	<	TreeMap.Entry<K,V> node = getEntry(key);
1563	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1564		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1565	<	deleteEntry(node);
1565	>	m.deleteEntry(node);
1566		return true;
1567		}
1568		return false;
1569		}
1450	–
1451	–	public Iterator<Map.Entry<K,V>> iterator() {
1452	–	return new SubMapEntryIterator(
1453	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1454	–	(toEnd     ? null            : getCeilingEntry(toKey)));
1455	–	}
1570		}
1571
1572	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1573	<	private transient Set<K> descendingKeySetView = null;
1574	<
1575	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1576	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1577	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1578	<	}
1572	>	/**
1573	>	* Iterators for SubMaps
1574	>	*/
1575	>	abstract class SubMapIterator<T> implements Iterator<T> {
1576	>	TreeMap.Entry<K,V> lastReturned;
1577	>	TreeMap.Entry<K,V> next;
1578	>	final K fenceKey;
1579	>	int expectedModCount;
1580
1581	<	public Set<K> descendingKeySet() {
1582	<	Set<K> ks = descendingKeySetView;
1583	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1584	<	}
1581	>	SubMapIterator(TreeMap.Entry<K,V> first,
1582	>	TreeMap.Entry<K,V> fence) {
1583	>	expectedModCount = m.modCount;
1584	>	lastReturned = null;
1585	>	next = first;
1586	>	fenceKey = fence == null ? null : fence.key;
1587	>	}
1588
1589	<	private class DescendingEntrySetView extends EntrySetView {
1590	<	public Iterator<Map.Entry<K,V>> iterator() {
1473	<	return new DescendingSubMapEntryIterator
1474	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1475	<	(fromStart ? null            : getLowerEntry(fromKey)));
1589	>	public final boolean hasNext() {
1590	>	return next != null && next.key != fenceKey;
1591		}
1477	–	}
1592
1593	<	private class DescendingKeySetView extends AbstractSet<K> {
1594	<	public Iterator<K> iterator() {
1595	<	return new Iterator<K>() {
1596	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1597	<
1598	<	public boolean hasNext() { return i.hasNext(); }
1599	<	public K next() { return i.next().getKey(); }
1600	<	public void remove() { i.remove(); }
1487	<	};
1593	>	final TreeMap.Entry<K,V> nextEntry() {
1594	>	TreeMap.Entry<K,V> e = lastReturned = next;
1595	>	if (e == null || e.key == fenceKey)
1596	>	throw new NoSuchElementException();
1597	>	if (m.modCount != expectedModCount)
1598	>	throw new ConcurrentModificationException();
1599	>	next = successor(e);
1600	>	return e;
1601		}
1602	<
1603	<	public int size() {
1604	<	return SubMap.this.size();
1602	>
1603	>	final TreeMap.Entry<K,V> prevEntry() {
1604	>	TreeMap.Entry<K,V> e = lastReturned = next;
1605	>	if (e == null || e.key == fenceKey)
1606	>	throw new NoSuchElementException();
1607	>	if (m.modCount != expectedModCount)
1608	>	throw new ConcurrentModificationException();
1609	>	next = predecessor(e);
1610	>	return e;
1611		}
1612	<
1613	<	public boolean contains(Object k) {
1614	<	return SubMap.this.containsKey(k);
1612	>
1613	>	public void remove() {
1614	>	if (lastReturned == null)
1615	>	throw new IllegalStateException();
1616	>	if (m.modCount != expectedModCount)
1617	>	throw new ConcurrentModificationException();
1618	>	if (lastReturned.left != null && lastReturned.right != null)
1619	>	next = lastReturned;
1620	>	m.deleteEntry(lastReturned);
1621	>	expectedModCount++;
1622	>	lastReturned = null;
1623		}
1624		}
1625
1626	<
1627	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1628	<	if (!inRange2(fromKey))
1629	<	throw new IllegalArgumentException("fromKey out of range");
1630	<	if (!inRange2(toKey))
1631	<	throw new IllegalArgumentException("toKey out of range");
1632	<	return new SubMap(fromKey, toKey);
1626	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1627	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1628	>	TreeMap.Entry<K,V> fence) {
1629	>	super(first, fence);
1630	>	}
1631	>	public Map.Entry<K,V> next() {
1632	>	return nextEntry();
1633	>	}
1634		}
1635
1636	<	public NavigableMap<K,V> headMap(K toKey) {
1637	<	if (!inRange2(toKey))
1638	<	throw new IllegalArgumentException("toKey out of range");
1639	<	return new SubMap(fromStart, fromKey, false, toKey);
1636	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1637	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1638	>	TreeMap.Entry<K,V> fence) {
1639	>	super(first, fence);
1640	>	}
1641	>	public K next() {
1642	>	return nextEntry().key;
1643	>	}
1644		}
1645
1646	<	public NavigableMap<K,V> tailMap(K fromKey) {
1647	<	if (!inRange2(fromKey))
1648	<	throw new IllegalArgumentException("fromKey out of range");
1649	<	return new SubMap(false, fromKey, toEnd, toKey);
1650	<	}
1646	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1647	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1648	>	TreeMap.Entry<K,V> fence) {
1649	>	super(last, fence);
1650	>	}
1651
1652	<	private boolean inRange(K key) {
1653	<	return (fromStart || compare(key, fromKey) >= 0) &&
1654	<	(toEnd     || compare(key, toKey)   <  0);
1652	>	public Map.Entry<K,V> next() {
1653	>	return prevEntry();
1654	>	}
1655		}
1656
1657	<	// This form allows the high endpoint (as well as all legit keys)
1658	<	private boolean inRange2(K key) {
1659	<	return (fromStart || compare(key, fromKey) >= 0) &&
1660	<	(toEnd     || compare(key, toKey)   <= 0);
1657	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1658	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1659	>	TreeMap.Entry<K,V> fence) {
1660	>	super(last, fence);
1661	>	}
1662	>	public K next() {
1663	>	return prevEntry().key;
1664	>	}
1665		}
1666		}
1667
1668	<	/**
1669	<	* TreeMap Iterator.
1534	<	*/
1535	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1536	<	int expectedModCount = TreeMap.this.modCount;
1537	<	Entry<K,V> lastReturned = null;
1538	<	Entry<K,V> next;
1668	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1669	>	private static final long serialVersionUID = 912986545866124060L;
1670
1671	<	PrivateEntryIterator(Entry<K,V> first) {
1672	<	next = first;
1671	>	AscendingSubMap(TreeMap<K,V> m,
1672	>	boolean fromStart, K lo, boolean loInclusive,
1673	>	boolean toEnd, K hi, boolean hiInclusive) {
1674	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1675		}
1676
1677	<	public boolean hasNext() {
1678	<	return next != null;
1677	>	public Comparator<? super K> comparator() {
1678	>	return m.comparator();
1679		}
1680
1681	<	Entry<K,V> nextEntry() {
1682	<	if (next == null)
1683	<	throw new NoSuchElementException();
1684	<	if (modCount != expectedModCount)
1685	<	throw new ConcurrentModificationException();
1686	<	lastReturned = next;
1687	<	next = successor(next);
1688	<	return lastReturned;
1681	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1682	>	K toKey, boolean toInclusive) {
1683	>	if (!inRange(fromKey, fromInclusive))
1684	>	throw new IllegalArgumentException("fromKey out of range");
1685	>	if (!inRange(toKey, toInclusive))
1686	>	throw new IllegalArgumentException("toKey out of range");
1687	>	return new AscendingSubMap(m,
1688	>	false, fromKey, fromInclusive,
1689	>	false, toKey,   toInclusive);
1690		}
1691
1692	<	public void remove() {
1693	<	if (lastReturned == null)
1694	<	throw new IllegalStateException();
1695	<	if (modCount != expectedModCount)
1696	<	throw new ConcurrentModificationException();
1697	<	if (lastReturned.left != null && lastReturned.right != null)
1564	<	next = lastReturned;
1565	<	deleteEntry(lastReturned);
1566	<	expectedModCount++;
1567	<	lastReturned = null;
1692	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1693	>	if (!inClosedRange(toKey))
1694	>	throw new IllegalArgumentException("toKey out of range");
1695	>	return new AscendingSubMap(m,
1696	>	fromStart, lo,    loInclusive,
1697	>	false,     toKey, inclusive);
1698		}
1569	–	}
1699
1700	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1701	<	EntryIterator(Entry<K,V> first) {
1702	<	super(first);
1700	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1701	>	if (!inRange(fromKey, inclusive))
1702	>	throw new IllegalArgumentException("fromKey out of range");
1703	>	return new AscendingSubMap(m,
1704	>	false, fromKey, inclusive,
1705	>	toEnd, hi,      hiInclusive);
1706		}
1707
1708	<	public Map.Entry<K,V> next() {
1709	<	return nextEntry();
1708	>	public NavigableMap<K,V> descendingMap() {
1709	>	NavigableMap<K,V> mv = descendingMapView;
1710	>	return (mv != null) ? mv :
1711	>	(descendingMapView =
1712	>	new DescendingSubMap(m,
1713	>	fromStart, lo, loInclusive,
1714	>	toEnd,     hi, hiInclusive));
1715		}
1579	–	}
1716
1717	<	class KeyIterator extends PrivateEntryIterator<K> {
1718	<	KeyIterator(Entry<K,V> first) {
1583	<	super(first);
1584	<	}
1585	<	public K next() {
1586	<	return nextEntry().key;
1717	>	Iterator<K> keyIterator() {
1718	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1719		}
1588	–	}
1720
1721	<	class ValueIterator extends PrivateEntryIterator<V> {
1722	<	ValueIterator(Entry<K,V> first) {
1592	<	super(first);
1721	>	Iterator<K> descendingKeyIterator() {
1722	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1723		}
1594	–	public V next() {
1595	–	return nextEntry().value;
1596	–	}
1597	–	}
1724
1725	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1726	<	private final K firstExcludedKey;
1727	<
1728	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1603	<	super(first);
1604	<	firstExcludedKey = (firstExcluded == null
1605	<	? null
1606	<	: firstExcluded.key);
1725	>	final class AscendingEntrySetView extends EntrySetView {
1726	>	public Iterator<Map.Entry<K,V>> iterator() {
1727	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1728	>	}
1729		}
1730
1731	<	public boolean hasNext() {
1732	<	return next != null && next.key != firstExcludedKey;
1731	>	public Set<Map.Entry<K,V>> entrySet() {
1732	>	EntrySetView es = entrySetView;
1733	>	return (es != null) ? es : new AscendingEntrySetView();
1734		}
1735
1736	<	public Map.Entry<K,V> next() {
1737	<	if (next == null || next.key == firstExcludedKey)
1738	<	throw new NoSuchElementException();
1739	<	return nextEntry();
1740	<	}
1736	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1737	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1738	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1739	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1740	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1741	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1742		}
1743
1744	<
1745	<	/**
1746	<	* Base for Descending Iterators.
1747	<	*/
1748	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1749	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1626	<	super(first);
1744	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1745	>	private static final long serialVersionUID = 912986545866120460L;
1746	>	DescendingSubMap(TreeMap<K,V> m,
1747	>	boolean fromStart, K lo, boolean loInclusive,
1748	>	boolean toEnd, K hi, boolean hiInclusive) {
1749	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1750		}
1751
1752	<	Entry<K,V> nextEntry() {
1753	<	if (next == null)
1631	<	throw new NoSuchElementException();
1632	<	if (modCount != expectedModCount)
1633	<	throw new ConcurrentModificationException();
1634	<	lastReturned = next;
1635	<	next = predecessor(next);
1636	<	return lastReturned;
1637	<	}
1638	<	}
1752	>	private final Comparator<? super K> reverseComparator =
1753	>	Collections.reverseOrder(m.comparator);
1754
1755	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1756	<	DescendingEntryIterator(Entry<K,V> first) {
1642	<	super(first);
1755	>	public Comparator<? super K> comparator() {
1756	>	return reverseComparator;
1757		}
1758	<	public Map.Entry<K,V> next() {
1759	<	return nextEntry();
1758	>
1759	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1760	>	K toKey, boolean toInclusive) {
1761	>	if (!inRange(fromKey, fromInclusive))
1762	>	throw new IllegalArgumentException("fromKey out of range");
1763	>	if (!inRange(toKey, toInclusive))
1764	>	throw new IllegalArgumentException("toKey out of range");
1765	>	return new DescendingSubMap(m,
1766	>	false, toKey,   toInclusive,
1767	>	false, fromKey, fromInclusive);
1768		}
1647	–	}
1769
1770	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1771	<	DescendingKeyIterator(Entry<K,V> first) {
1772	<	super(first);
1770	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1771	>	if (!inRange(toKey, inclusive))
1772	>	throw new IllegalArgumentException("toKey out of range");
1773	>	return new DescendingSubMap(m,
1774	>	false, toKey, inclusive,
1775	>	toEnd, hi,    hiInclusive);
1776		}
1777	<	public K next() {
1778	<	return nextEntry().key;
1777	>
1778	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1779	>	if (!inRange(fromKey, inclusive))
1780	>	throw new IllegalArgumentException("fromKey out of range");
1781	>	return new DescendingSubMap(m,
1782	>	fromStart, lo, loInclusive,
1783	>	false, fromKey, inclusive);
1784		}
1656	–	}
1785
1786	+	public NavigableMap<K,V> descendingMap() {
1787	+	NavigableMap<K,V> mv = descendingMapView;
1788	+	return (mv != null) ? mv :
1789	+	(descendingMapView =
1790	+	new AscendingSubMap(m,
1791	+	fromStart, lo, loInclusive,
1792	+	toEnd,     hi, hiInclusive));
1793	+	}
1794
1795	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1796	<	private final K lastExcludedKey;
1795	>	Iterator<K> keyIterator() {
1796	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1797	>	}
1798
1799	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1800	<	super(last);
1664	<	lastExcludedKey = (lastExcluded == null
1665	<	? null
1666	<	: lastExcluded.key);
1799	>	Iterator<K> descendingKeyIterator() {
1800	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1801		}
1802
1803	<	public boolean hasNext() {
1804	<	return next != null && next.key != lastExcludedKey;
1803	>	final class DescendingEntrySetView extends EntrySetView {
1804	>	public Iterator<Map.Entry<K,V>> iterator() {
1805	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1806	>	}
1807		}
1808
1809	<	public Map.Entry<K,V> next() {
1810	<	if (next == null || next.key == lastExcludedKey)
1811	<	throw new NoSuchElementException();
1676	<	return nextEntry();
1809	>	public Set<Map.Entry<K,V>> entrySet() {
1810	>	EntrySetView es = entrySetView;
1811	>	return (es != null) ? es : new DescendingEntrySetView();
1812		}
1813
1814	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1815	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1816	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1817	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1818	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1819	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1820		}
1821
1681	–
1822		/**
1823		* Compares two keys using the correct comparison method for this TreeMap.
1824		*/
1825	<	private int compare(K k1, K k2) {
1826	<	return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
1827	<	: comparator.compare((K)k1, (K)k2));
1825	>	final int compare(Object k1, Object k2) {
1826	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1827	>	: comparator.compare((K)k1, (K)k2);
1828		}
1829
1830		/**
1831	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1831	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1832		* that it copes with <tt>null</tt> o1 properly.
1833		*/
1834	<	private static boolean valEquals(Object o1, Object o2) {
1834	>	final static boolean valEquals(Object o1, Object o2) {
1835		return (o1==null ? o2==null : o1.equals(o2));
1836		}
1837
1838	+	/**
1839	+	* This class exists solely for the sake of serialization
1840	+	* compatibility with previous releases of TreeMap that did not
1841	+	* support NavigableMap.  It translates an old-version SubMap into
1842	+	* a new-version AscendingSubMap. This class is never otherwise
1843	+	* used.
1844	+	*/
1845	+	private class SubMap extends AbstractMap<K,V>
1846	+	implements SortedMap<K,V>, java.io.Serializable {
1847	+	private static final long serialVersionUID = -6520786458950516097L;
1848	+	private boolean fromStart = false, toEnd = false;
1849	+	private K fromKey, toKey;
1850	+	private Object readResolve() {
1851	+	return new AscendingSubMap(TreeMap.this,
1852	+	fromStart, fromKey, true,
1853	+	toEnd, toKey, false);
1854	+	}
1855	+	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1856	+	public K lastKey() { throw new InternalError(); }
1857	+	public K firstKey() { throw new InternalError(); }
1858	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1859	+	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1860	+	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1861	+	public Comparator<? super K> comparator() { throw new InternalError(); }
1862	+	}
1863	+
1864	+
1865		private static final boolean RED   = false;
1866		private static final boolean BLACK = true;
1867
#	Line 1703 | Line 1870 | public class TreeMap<K,V>
1870		* user (see Map.Entry).
1871		*/
1872
1873	<	static class Entry<K,V> implements Map.Entry<K,V> {
1873	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1874		K key;
1875		V value;
1876		Entry<K,V> left = null;
#	Line 1724 | Line 1891 | public class TreeMap<K,V>
1891		/**
1892		* Returns the key.
1893		*
1894	<	* @return the key.
1894	>	* @return the key
1895		*/
1896		public K getKey() {
1897		return key;
#	Line 1733 | Line 1900 | public class TreeMap<K,V>
1900		/**
1901		* Returns the value associated with the key.
1902		*
1903	<	* @return the value associated with the key.
1903	>	* @return the value associated with the key
1904		*/
1905		public V getValue() {
1906		return value;
#	Line 1744 | Line 1911 | public class TreeMap<K,V>
1911		* value.
1912		*
1913		* @return the value associated with the key before this method was
1914	<	*           called.
1914	>	*         called
1915		*/
1916		public V setValue(V value) {
1917		V oldValue = this.value;
#	Line 1775 | Line 1942 | public class TreeMap<K,V>
1942		* Returns the first Entry in the TreeMap (according to the TreeMap's
1943		* key-sort function).  Returns null if the TreeMap is empty.
1944		*/
1945	<	private Entry<K,V> getFirstEntry() {
1945	>	final Entry<K,V> getFirstEntry() {
1946		Entry<K,V> p = root;
1947		if (p != null)
1948		while (p.left != null)
#	Line 1787 | Line 1954 | public class TreeMap<K,V>
1954		* Returns the last Entry in the TreeMap (according to the TreeMap's
1955		* key-sort function).  Returns null if the TreeMap is empty.
1956		*/
1957	<	private Entry<K,V> getLastEntry() {
1957	>	final Entry<K,V> getLastEntry() {
1958		Entry<K,V> p = root;
1959		if (p != null)
1960		while (p.right != null)
#	Line 1798 | Line 1965 | public class TreeMap<K,V>
1965		/**
1966		* Returns the successor of the specified Entry, or null if no such.
1967		*/
1968	<	private Entry<K,V> successor(Entry<K,V> t) {
1968	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1969		if (t == null)
1970		return null;
1971		else if (t.right != null) {
#	Line 1820 | Line 1987 | public class TreeMap<K,V>
1987		/**
1988		* Returns the predecessor of the specified Entry, or null if no such.
1989		*/
1990	<	private Entry<K,V> predecessor(Entry<K,V> t) {
1990	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1991		if (t == null)
1992		return null;
1993		else if (t.left != null) {
#	Line 1937 | Line 2104 | public class TreeMap<K,V>
2104		x = parentOf(x);
2105		rotateRight(x);
2106		}
2107	<	setColor(parentOf(x),  BLACK);
2107	>	setColor(parentOf(x), BLACK);
2108		setColor(parentOf(parentOf(x)), RED);
2109		if (parentOf(parentOf(x)) != null)
2110		rotateLeft(parentOf(parentOf(x)));
#	Line 2013 | Line 2180 | public class TreeMap<K,V>
2180
2181		if (colorOf(leftOf(sib))  == BLACK &&
2182		colorOf(rightOf(sib)) == BLACK) {
2183	<	setColor(sib,  RED);
2183	>	setColor(sib, RED);
2184		x = parentOf(x);
2185		} else {
2186		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2040 | Line 2207 | public class TreeMap<K,V>
2207
2208		if (colorOf(rightOf(sib)) == BLACK &&
2209		colorOf(leftOf(sib)) == BLACK) {
2210	<	setColor(sib,  RED);
2210	>	setColor(sib, RED);
2211		x = parentOf(x);
2212		} else {
2213		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 2091 | Line 2258 | public class TreeMap<K,V>
2258		}
2259		}
2260
2094	–
2095	–
2261		/**
2262		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2263		* deserialize it).
#	Line 2115 | Line 2280 | public class TreeMap<K,V>
2280		}
2281
2282		/** Intended to be called only from TreeSet.addAll **/
2283	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
2283	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2284		try {
2285		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2286		} catch (java.io.IOException cannotHappen) {
#	Line 2140 | Line 2305 | public class TreeMap<K,V>
2305		* to calling this method.
2306		*
2307		* @param size the number of keys (or key-value pairs) to be read from
2308	<	*        the iterator or stream.
2308	>	*        the iterator or stream
2309		* @param it If non-null, new entries are created from entries
2310		*        or keys read from this iterator.
2311		* @param str If non-null, new entries are created from keys and
#	Line 2154 | Line 2319 | public class TreeMap<K,V>
2319		* @throws ClassNotFoundException propagated from readObject.
2320		*         This cannot occur if str is null.
2321		*/
2322	<	private
2323	<	void buildFromSorted(int size, Iterator it,
2324	<	java.io.ObjectInputStream str,
2160	<	V defaultVal)
2322	>	private void buildFromSorted(int size, Iterator it,
2323	>	java.io.ObjectInputStream str,
2324	>	V defaultVal)
2325		throws  java.io.IOException, ClassNotFoundException {
2326		this.size = size;
2327	<	root =
2328	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
2165	<	it, str, defaultVal);
2327	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2328	>	it, str, defaultVal);
2329		}
2330
2331		/**
2332		* Recursive "helper method" that does the real work of the
2333	<	* of the previous method.  Identically named parameters have
2333	>	* previous method.  Identically named parameters have
2334		* identical definitions.  Additional parameters are documented below.
2335		* It is assumed that the comparator and size fields of the TreeMap are
2336		* already set prior to calling this method.  (It ignores both fields.)
#	Line 2175 | Line 2338 | public class TreeMap<K,V>
2338		* @param level the current level of tree. Initial call should be 0.
2339		* @param lo the first element index of this subtree. Initial should be 0.
2340		* @param hi the last element index of this subtree.  Initial should be
2341	<	*              size-1.
2341	>	*        size-1.
2342		* @param redLevel the level at which nodes should be red.
2343		*        Must be equal to computeRedLevel for tree of this size.
2344		*/
#	Line 2259 | Line 2422 | public class TreeMap<K,V>
2422		level++;
2423		return level;
2424		}
2262	–
2425		}

Diff Legend

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