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.4 by dl, Tue Mar 22 01:30:10 2005 UTC vs.
Revision 1.29 by dl, Thu Apr 20 20:34:37 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		*/
#	Line 113 | Line 113 | public class TreeMap<K,V>
113		private void decrementSize()   { modCount++; size--; }
114
115		/**
116	<	* Constructs a new, empty map, sorted according to the keys' natural
117	<	* order.  All keys inserted into the map must implement the
118	<	* <tt>Comparable</tt> interface.  Furthermore, all such keys must be
119	<	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
120	<	* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
121	<	* map.  If the user attempts to put a key into the map that violates this
122	<	* constraint (for example, the user attempts to put a string key into a
123	<	* map whose keys are integers), the <tt>put(Object key, Object
124	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
125	<	*
126	<	* @see Comparable
116	>	* Constructs a new, empty tree map, using the natural ordering of its
117	>	* keys.  All keys inserted into the map must implement the {@link
118	>	* Comparable} interface.  Furthermore, all such keys must be
119	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
120	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
121	>	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
122	>	* map that violates this constraint (for example, the user attempts to
123	>	* put a string key into a map whose keys are integers), the
124	>	* <tt>put(Object key, Object value)</tt> call will throw a
125	>	* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128		}
129
130		/**
131	<	* Constructs a new, empty map, sorted according to the given comparator.
132	<	* All keys inserted into the map must be <i>mutually comparable</i> by
133	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
134	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
135	<	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
136	<	* map that violates this constraint, the <tt>put(Object key, Object
137	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
138	<	*
139	<	* @param c the comparator that will be used to sort this map.  A
140	<	*        <tt>null</tt> value indicates that the keys' <i>natural
141	<	*        ordering</i> should be used.
142	<	*/
143	<	public TreeMap(Comparator<? super K> c) {
144	<	this.comparator = c;
131	>	* Constructs a new, empty tree map, ordered according to the given
132	>	* comparator.  All keys inserted into the map must be <i>mutually
133	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
134	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
135	>	* <tt>k1</tt> and <tt>k2</tt> in the map.  If the user attempts to put
136	>	* a key into the map that violates this constraint, the <tt>put(Object
137	>	* key, Object value)</tt> call will throw a
138	>	* <tt>ClassCastException</tt>.
139	>	*
140	>	* @param comparator the comparator that will be used to order this map.
141	>	*        If <tt>null</tt>, the {@linkplain Comparable natural
142	>	*        ordering} of the keys will be used.
143	>	*/
144	>	public TreeMap(Comparator<? super K> comparator) {
145	>	this.comparator = comparator;
146		}
147
148		/**
149	<	* Constructs a new map containing the same mappings as the given map,
150	<	* sorted according to the keys' <i>natural order</i>.  All keys inserted
151	<	* into the new map must implement the <tt>Comparable</tt> interface.
152	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
153	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
154	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
155	<	* runs in n*log(n) time.
156	<	*
157	<	* @param  m the map whose mappings are to be placed in this map.
158	<	* @throws ClassCastException the keys in t are not Comparable, or
159	<	*         are not mutually comparable.
160	<	* @throws NullPointerException if the specified map is null.
149	>	* Constructs a new tree map containing the same mappings as the given
150	>	* map, ordered according to the <i>natural ordering</i> of its keys.
151	>	* All keys inserted into the new map must implement the {@link
152	>	* Comparable} interface.  Furthermore, all such keys must be
153	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
154	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
155	>	* <tt>k2</tt> in the map.  This method runs in n*log(n) time.
156	>	*
157	>	* @param  m the map whose mappings are to be placed in this map
158	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
159	>	*         or are not mutually comparable
160	>	* @throws NullPointerException if the specified map is null
161		*/
162		public TreeMap(Map<? extends K, ? extends V> m) {
163		putAll(m);
164		}
165
166		/**
167	<	* Constructs a new map containing the same mappings as the given
168	<	* <tt>SortedMap</tt>, sorted according to the same ordering.  This method
169	<	* runs in linear time.
167	>	* Constructs a new tree map containing the same mappings and
168	>	* using the same ordering as the specified sorted map.  This
169	>	* method runs in linear time.
170		*
171		* @param  m the sorted map whose mappings are to be placed in this map,
172	<	*         and whose comparator is to be used to sort this map.
173	<	* @throws NullPointerException if the specified sorted map is null.
172	>	*         and whose comparator is to be used to sort this map
173	>	* @throws NullPointerException if the specified map is null
174		*/
175		public TreeMap(SortedMap<K, ? extends V> m) {
176		comparator = m.comparator();
#	Line 187 | Line 187 | public class TreeMap<K,V>
187		/**
188		* Returns the number of key-value mappings in this map.
189		*
190	<	* @return the number of key-value mappings in this map.
190	>	* @return the number of key-value mappings in this map
191		*/
192		public int size() {
193		return size;
#	Line 197 | Line 197 | public class TreeMap<K,V>
197		* Returns <tt>true</tt> if this map contains a mapping for the specified
198		* key.
199		*
200	<	* @param key key whose presence in this map is to be tested.
201	<	*
200	>	* @param key key whose presence in this map is to be tested
201		* @return <tt>true</tt> if this map contains a mapping for the
202	<	*            specified key.
203	<	* @throws ClassCastException if the key cannot be compared with the keys
204	<	*                  currently in the map.
205	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
206	<	*                  natural ordering, or its comparator does not tolerate
207	<	*            <tt>null</tt> keys.
202	>	*         specified key
203	>	* @throws ClassCastException if the specified key cannot be compared
204	>	*         with the keys currently in the map
205	>	* @throws NullPointerException if the specified key is null
206	>	*         and this map uses natural ordering, or its comparator
207	>	*         does not permit null keys
208		*/
209		public boolean containsKey(Object key) {
210		return getEntry(key) != null;
#	Line 216 | Line 215 | public class TreeMap<K,V>
215		* specified value.  More formally, returns <tt>true</tt> if and only if
216		* this map contains at least one mapping to a value <tt>v</tt> such
217		* that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
218	<	* operation will probably require time linear in the Map size for most
219	<	* implementations of Map.
218	>	* operation will probably require time linear in the map size for
219	>	* most implementations.
220		*
221	<	* @param value value whose presence in this Map is to be tested.
222	<	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
223	<	*          <tt>false</tt> otherwise.
221	>	* @param value value whose presence in this map is to be tested
222	>	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
223	>	*         <tt>false</tt> otherwise
224		* @since 1.2
225		*/
226		public boolean containsValue(Object value) {
227		return (root==null ? false :
228		(value==null ? valueSearchNull(root)
229	<	: valueSearchNonNull(root, value)));
229	>	: valueSearchNonNull(root, value)));
230		}
231
232		private boolean valueSearchNull(Entry n) {
#	Line 236 | Line 235 | public class TreeMap<K,V>
235
236		// Check left and right subtrees for value
237		return (n.left  != null && valueSearchNull(n.left)) ||
238	<	(n.right != null && valueSearchNull(n.right));
238	>	(n.right != null && valueSearchNull(n.right));
239		}
240
241		private boolean valueSearchNonNull(Entry n, Object value) {
#	Line 246 | Line 245 | public class TreeMap<K,V>
245
246		// Check left and right subtrees for value
247		return (n.left  != null && valueSearchNonNull(n.left, value)) ||
248	<	(n.right != null && valueSearchNonNull(n.right, value));
248	>	(n.right != null && valueSearchNonNull(n.right, value));
249		}
250
251		/**
252	<	* Returns the value to which this map maps the specified key.  Returns
253	<	* <tt>null</tt> if the map contains no mapping for this key.  A return
255	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
256	<	* map contains no mapping for the key; it's also possible that the map
257	<	* explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
258	<	* operation may be used to distinguish these two cases.
259	<	*
260	<	* @param key key whose associated value is to be returned.
261	<	* @return the value to which this map maps the specified key, or
262	<	*               <tt>null</tt> if the map contains no mapping for the key.
263	<	* @throws    ClassCastException if key cannot be compared with the keys
264	<	*                  currently in the map.
265	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
266	<	*                  natural ordering, or its comparator does not tolerate
267	<	*                  <tt>null</tt> keys.
252	>	* Returns the value to which the specified key is mapped,
253	>	* or {@code null} if this map contains no mapping for the key.
254		*
255	<	* @see #containsKey(Object)
255	>	* <p>More formally, if this map contains a mapping from a key
256	>	* {@code k} to a value {@code v} such that {@code key} compares
257	>	* equal to {@code k} according to the map's ordering, then this
258	>	* method returns {@code v}; otherwise it returns {@code null}.
259	>	* (There can be at most one such mapping.)
260	>	*
261	>	* <p>A return value of {@code null} does not <i>necessarily</i>
262	>	* indicate that the map contains no mapping for the key; it's also
263	>	* possible that the map explicitly maps the key to {@code null}.
264	>	* The {@link #containsKey containsKey} operation may be used to
265	>	* distinguish these two cases.
266	>	*
267	>	* @throws ClassCastException if the specified key cannot be compared
268	>	*         with the keys currently in the map
269	>	* @throws NullPointerException if the specified key is null
270	>	*         and this map uses natural ordering, or its comparator
271	>	*         does not permit null keys
272		*/
273		public V get(Object key) {
274		Entry<K,V> p = getEntry(key);
275		return (p==null ? null : p.value);
276		}
277
276	–	/**
277	–	* Returns the comparator used to order this map, or <tt>null</tt> if this
278	–	* map uses its keys' natural order.
279	–	*
280	–	* @return the comparator associated with this sorted map, or
281	–	*                <tt>null</tt> if it uses its keys' natural sort method.
282	–	*/
278		public Comparator<? super K> comparator() {
279		return comparator;
280		}
281
282		/**
283	<	* Returns the first (lowest) key currently in this sorted map.
289	<	*
290	<	* @return the first (lowest) key currently in this sorted map.
291	<	* @throws    NoSuchElementException Map is empty.
283	>	* @throws NoSuchElementException {@inheritDoc}
284		*/
285		public K firstKey() {
286		return key(getFirstEntry());
287		}
288
289		/**
290	<	* Returns the last (highest) key currently in this sorted map.
299	<	*
300	<	* @return the last (highest) key currently in this sorted map.
301	<	* @throws    NoSuchElementException Map is empty.
290	>	* @throws NoSuchElementException {@inheritDoc}
291		*/
292		public K lastKey() {
293		return key(getLastEntry());
294		}
295
296		/**
297	<	* Copies all of the mappings from the specified map to this map.  These
298	<	* mappings replace any mappings that this map had for any of the keys
299	<	* currently in the specified map.
300	<	*
301	<	* @param     map mappings to be stored in this map.
302	<	* @throws    ClassCastException class of a key or value in the specified
303	<	*                   map prevents it from being stored in this map.
304	<	*
305	<	* @throws NullPointerException if the given map is <tt>null</tt> or
306	<	*         this map does not permit <tt>null</tt> keys and a
318	<	*         key in the specified map is <tt>null</tt>.
297	>	* Copies all of the mappings from the specified map to this map.
298	>	* These mappings replace any mappings that this map had for any
299	>	* of the keys currently in the specified map.
300	>	*
301	>	* @param  map mappings to be stored in this map
302	>	* @throws ClassCastException if the class of a key or value in
303	>	*         the specified map prevents it from being stored in this map
304	>	* @throws NullPointerException if the specified map is null or
305	>	*         the specified map contains a null key and this map does not
306	>	*         permit null keys
307		*/
308		public void putAll(Map<? extends K, ? extends V> map) {
309		int mapSize = map.size();
#	Line 340 | Line 328 | public class TreeMap<K,V>
328		* does not contain an entry for the key.
329		*
330		* @return this map's entry for the given key, or <tt>null</tt> if the map
331	<	*                does not contain an entry for the key.
332	<	* @throws ClassCastException if the key cannot be compared with the keys
333	<	*                  currently in the map.
334	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
335	<	*                  natural order, or its comparator does not tolerate *
336	<	*                  <tt>null</tt> keys.
331	>	*         does not contain an entry for the key
332	>	* @throws ClassCastException if the specified key cannot be compared
333	>	*         with the keys currently in the map
334	>	* @throws NullPointerException if the specified key is null
335	>	*         and this map uses natural ordering, or its comparator
336	>	*         does not permit null keys
337		*/
338	<	private Entry<K,V> getEntry(Object key) {
338	>	final Entry<K,V> getEntry(Object key) {
339		// Offload comparator-based version for sake of performance
340		if (comparator != null)
341		return getEntryUsingComparator(key);
342	<	Comparable<K> k = (Comparable<K>) key;
342	>	if (key == null)
343	>	throw new NullPointerException();
344	>	Comparable<? super K> k = (Comparable<? super K>) key;
345		Entry<K,V> p = root;
346		while (p != null) {
347		int cmp = k.compareTo(p.key);
#	Line 371 | Line 361 | public class TreeMap<K,V>
361		* that are less dependent on comparator performance, but is
362		* worthwhile here.)
363		*/
364	<	private Entry<K,V> getEntryUsingComparator(Object key) {
364	>	final Entry<K,V> getEntryUsingComparator(Object key) {
365		K k = (K) key;
366		Comparator<? super K> cpr = comparator;
367		Entry<K,V> p = root;
#	Line 393 | Line 383 | public class TreeMap<K,V>
383		* key; if no such entry exists (i.e., the greatest key in the Tree is less
384		* than the specified key), returns <tt>null</tt>.
385		*/
386	<	private Entry<K,V> getCeilingEntry(K key) {
386	>	final Entry<K,V> getCeilingEntry(K key) {
387		Entry<K,V> p = root;
388		if (p==null)
389		return null;
#	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)
423		return null;
#	Line 463 | Line 453 | public class TreeMap<K,V>
453		* key greater than the specified key; if no such entry exists
454		* returns <tt>null</tt>.
455		*/
456	<	private Entry<K,V> getHigherEntry(K key) {
456	>	final Entry<K,V> getHigherEntry(K key) {
457		Entry<K,V> p = root;
458		if (p==null)
459		return null;
#	Line 496 | Line 486 | public class TreeMap<K,V>
486		* no such entry exists (i.e., the least key in the Tree is greater than
487		* the specified key), returns <tt>null</tt>.
488		*/
489	<	private Entry<K,V> getLowerEntry(K key) {
489	>	final Entry<K,V> getLowerEntry(K key) {
490		Entry<K,V> p = root;
491		if (p==null)
492		return null;
#	Line 525 | Line 515 | public class TreeMap<K,V>
515		}
516
517		/**
518	<	* Returns the key corresponding to the specified Entry.  Throw
519	<	* NoSuchElementException if the Entry is <tt>null</tt>.
518	>	* Returns the key corresponding to the specified Entry.
519	>	* @throws NoSuchElementException if the Entry is null
520		*/
521	<	private static <K> K key(Entry<K,?> e) {
521	>	static <K> K key(Entry<K,?> e) {
522		if (e==null)
523		throw new NoSuchElementException();
524		return e.key;
#	Line 536 | Line 526 | public class TreeMap<K,V>
526
527		/**
528		* Associates the specified value with the specified key in this map.
529	<	* If the map previously contained a mapping for this key, the old
529	>	* If the map previously contained a mapping for the key, the old
530		* value is replaced.
531		*
532	<	* @param key key with which the specified value is to be associated.
533	<	* @param value value to be associated with the specified key.
532	>	* @param key key with which the specified value is to be associated
533	>	* @param value value to be associated with the specified key
534		*
535	<	* @return previous value associated with specified key, or <tt>null</tt>
536	<	*         if there was no mapping for key.  A <tt>null</tt> return can
537	<	*         also indicate that the map previously associated <tt>null</tt>
538	<	*         with the specified key.
539	<	* @throws    ClassCastException if key cannot be compared with the keys
540	<	*            currently in the map.
541	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
542	<	*         natural order, or its comparator does not tolerate
543	<	*         <tt>null</tt> keys.
535	>	* @return the previous value associated with <tt>key</tt>, or
536	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
537	>	*         (A <tt>null</tt> return can also indicate that the map
538	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
539	>	* @throws ClassCastException if the specified key cannot be compared
540	>	*         with the keys currently in the map
541	>	* @throws NullPointerException if the specified key is null
542	>	*         and this map uses natural ordering, or its comparator
543	>	*         does not permit null keys
544		*/
545		public V put(K key, V value) {
546		Entry<K,V> t = root;
547
548		if (t == null) {
549	+	// TBD
550	+	//             if (key == null) {
551	+	//                 if (comparator == null)
552	+	//                     throw new NullPointerException();
553	+	//                 comparator.compare(key, key);
554	+	//             }
555		incrementSize();
556		root = new Entry<K,V>(key, value, null);
557		return null;
558	<	}
558	>	}
559
560		while (true) {
561		int cmp = compare(key, t.key);
#	Line 591 | Line 587 | public class TreeMap<K,V>
587		* Removes the mapping for this key from this TreeMap if present.
588		*
589		* @param  key key for which mapping should be removed
590	<	* @return previous value associated with specified key, or <tt>null</tt>
591	<	*         if there was no mapping for key.  A <tt>null</tt> return can
592	<	*         also indicate that the map previously associated
593	<	*         <tt>null</tt> with the specified key.
594	<	*
595	<	* @throws    ClassCastException if key cannot be compared with the keys
596	<	*            currently in the map.
597	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
598	<	*         natural order, or its comparator does not tolerate
603	<	*         <tt>null</tt> keys.
590	>	* @return the previous value associated with <tt>key</tt>, or
591	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
592	>	*         (A <tt>null</tt> return can also indicate that the map
593	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
594	>	* @throws ClassCastException if the specified key cannot be compared
595	>	*         with the keys currently in the map
596	>	* @throws NullPointerException if the specified key is null
597	>	*         and this map uses natural ordering, or its comparator
598	>	*         does not permit null keys
599		*/
600		public V remove(Object key) {
601		Entry<K,V> p = getEntry(key);
#	Line 613 | Line 608 | public class TreeMap<K,V>
608		}
609
610		/**
611	<	* Removes all mappings from this TreeMap.
611	>	* Removes all of the mappings from this map.
612	>	* The map will be empty after this call returns.
613		*/
614		public void clear() {
615		modCount++;
#	Line 625 | Line 621 | public class TreeMap<K,V>
621		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
622		* values themselves are not cloned.)
623		*
624	<	* @return a shallow copy of this Map.
624	>	* @return a shallow copy of this map
625		*/
626		public Object clone() {
627		TreeMap<K,V> clone = null;
#	Line 640 | Line 636 | public class TreeMap<K,V>
636		clone.size = 0;
637		clone.modCount = 0;
638		clone.entrySet = null;
639	<	clone.descendingEntrySet = null;
640	<	clone.descendingKeySet = null;
639	>	clone.navigableKeySet = null;
640	>	clone.descendingMap = null;
641
642		// Initialize clone with our mappings
643		try {
#	Line 656 | Line 652 | public class TreeMap<K,V>
652		// NavigableMap API methods
653
654		/**
655	<	* 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.
655	>	* @since 1.6
656		*/
657		public Map.Entry<K,V> firstEntry() {
658		Entry<K,V> e = getFirstEntry();
659	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
659	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
660		}
661
662		/**
663	<	* 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.
663	>	* @since 1.6
664		*/
665		public Map.Entry<K,V> lastEntry() {
666		Entry<K,V> e = getLastEntry();
667	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
667	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
668		}
669
670		/**
671	<	* 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.
671	>	* @since 1.6
672		*/
673		public Map.Entry<K,V> pollFirstEntry() {
674		Entry<K,V> p = getFirstEntry();
675	<	if (p == null)
675	>	if (p == null)
676		return null;
677	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
677	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
678		deleteEntry(p);
679		return result;
680		}
681
682		/**
683	<	* 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.
683	>	* @since 1.6
684		*/
685		public Map.Entry<K,V> pollLastEntry() {
686		Entry<K,V> p = getLastEntry();
687	<	if (p == null)
687	>	if (p == null)
688		return null;
689	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
689	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
690		deleteEntry(p);
691		return result;
692		}
693
694		/**
695	<	* Returns a key-value mapping associated with the least key
696	<	* greater than or equal to the given key, or <tt>null</tt> if
697	<	* there is no such entry.
698	<	*
699	<	* @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.
695	>	* @throws ClassCastException {@inheritDoc}
696	>	* @throws NullPointerException if the specified key is null
697	>	*         and this map uses natural ordering, or its comparator
698	>	*         does not permit null keys
699	>	* @since 1.6
700		*/
701	<	public Map.Entry<K,V> ceilingEntry(K key) {
702	<	Entry<K,V> e = getCeilingEntry(key);
703	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
701	>	public Map.Entry<K,V> lowerEntry(K key) {
702	>	Entry<K,V> e =  getLowerEntry(key);
703	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
704		}
705
735	–
706		/**
707	<	* Returns least key greater than or equal to the given key, or
708	<	* <tt>null</tt> if there is no such key.
709	<	*
710	<	* @param key the key.
711	<	* @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.
707	>	* @throws ClassCastException {@inheritDoc}
708	>	* @throws NullPointerException if the specified key is null
709	>	*         and this map uses natural ordering, or its comparator
710	>	*         does not permit null keys
711	>	* @since 1.6
712		*/
713	<	public K ceilingKey(K key) {
714	<	Entry<K,V> e = getCeilingEntry(key);
713	>	public K lowerKey(K key) {
714	>	Entry<K,V> e =  getLowerEntry(key);
715		return (e == null)? null : e.key;
716		}
717
754	–
755	–
718		/**
719	<	* Returns a key-value mapping associated with the greatest key
720	<	* less than or equal to the given key, or <tt>null</tt> if there
721	<	* is no such entry.
722	<	*
723	<	* @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.
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> floorEntry(K key) {
726		Entry<K,V> e = getFloorEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
727	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
728		}
729
730		/**
731	<	* Returns the greatest key
732	<	* less than or equal to the given key, or <tt>null</tt> if there
733	<	* is no such key.
734	<	*
735	<	* @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.
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 floorKey(K key) {
738		Entry<K,V> e = getFloorEntry(key);
#	Line 792 | Line 740 | public class TreeMap<K,V>
740		}
741
742		/**
743	<	* Returns a key-value mapping associated with the least key
744	<	* strictly greater than the given key, or <tt>null</tt> if there
745	<	* is no such entry.
746	<	*
747	<	* @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.
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> higherEntry(K key) {
750	<	Entry<K,V> e = getHigherEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
749	>	public Map.Entry<K,V> ceilingEntry(K key) {
750	>	Entry<K,V> e = getCeilingEntry(key);
751	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
752		}
753
754		/**
755	<	* Returns the least key strictly greater than the given key, or
756	<	* <tt>null</tt> if there is no such key.
757	<	*
758	<	* @param key the key.
759	<	* @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.
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 higherKey(K key) {
762	<	Entry<K,V> e = getHigherEntry(key);
761	>	public K ceilingKey(K key) {
762	>	Entry<K,V> e = getCeilingEntry(key);
763		return (e == null)? null : e.key;
764		}
765
766		/**
767	<	* Returns a key-value mapping associated with the greatest
768	<	* key strictly less than the given key, or <tt>null</tt> if there is no
769	<	* such entry.
770	<	*
771	<	* @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.
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> lowerEntry(K key) {
774	<	Entry<K,V> e =  getLowerEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
773	>	public Map.Entry<K,V> higherEntry(K key) {
774	>	Entry<K,V> e = getHigherEntry(key);
775	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
776		}
777
778		/**
779	<	* Returns the greatest key strictly less than the given key, or
780	<	* <tt>null</tt> if there is no such key.
781	<	*
782	<	* @param key the key.
783	<	* @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.
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 lowerKey(K key) {
786	<	Entry<K,V> e =  getLowerEntry(key);
785	>	public K higherKey(K key) {
786	>	Entry<K,V> e = getHigherEntry(key);
787		return (e == null)? null : e.key;
788		}
789
#	Line 872 | Line 794 | public class TreeMap<K,V>
794		* the first time this view is requested.  Views are stateless, so
795		* there's no reason to create more than one.
796		*/
797	<	private transient Set<Map.Entry<K,V>> entrySet = null;
798	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
799	<	private transient Set<K> descendingKeySet = null;
800	<
801	<	transient Set<K> keySet = null;        // XXX remove when integrated
802	<	transient Collection<V> values = null; // XXX remove when integrated
803	<
804	<	/**
805	<	* Returns a Set view of the keys contained in this map.  The set's
806	<	* iterator will return the keys in ascending order.  The set is backed by
807	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
808	<	* the Set, and vice-versa.  The Set supports element removal, which
809	<	* removes the corresponding mapping from the map, via the
810	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
811	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
812	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
813	<	*
892	<	* @return a set view of the keys contained in this TreeMap.
797	>	private transient EntrySet entrySet = null;
798	>	private transient KeySet<K> navigableKeySet = null;
799	>	private transient NavigableMap<K,V> descendingMap = null;
800	>
801	>	/**
802	>	* Returns a {@link Set} view of the keys contained in this map.
803	>	* The set's iterator returns the keys in ascending order.
804	>	* The set is backed by the map, so changes to the map are
805	>	* reflected in the set, and vice-versa.  If the map is modified
806	>	* while an iteration over the set is in progress (except through
807	>	* the iterator's own <tt>remove</tt> operation), the results of
808	>	* the iteration are undefined.  The set supports element removal,
809	>	* which removes the corresponding mapping from the map, via the
810	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
811	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
812	>	* operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
813	>	* operations.
814		*/
815		public Set<K> keySet() {
816	<	Set<K> ks = keySet;
896	<	return (ks != null) ? ks : (keySet = new KeySet());
816	>	return navigableKeySet();
817		}
818
819	<	class KeySet extends AbstractSet<K> {
820	<	public Iterator<K> iterator() {
821	<	return new KeyIterator(getFirstEntry());
822	<	}
823	<
824	<	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	<	}
819	>	/**
820	>	* @since 1.6
821	>	*/
822	>	public NavigableSet<K> navigableKeySet() {
823	>	KeySet<K> nks = navigableKeySet;
824	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
825		}
826
827		/**
828	<	* Returns a collection view of the values contained in this map.  The
829	<	* collection's iterator will return the values in the order that their
830	<	* corresponding keys appear in the tree.  The collection is backed by
831	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
832	<	* the collection, and vice-versa.  The collection supports element
833	<	* removal, which removes the corresponding mapping from the map through
834	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
835	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
836	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
837	<	*
838	<	* @return a collection view of the values contained in this map.
828	>	* @since 1.6
829	>	*/
830	>	public NavigableSet<K> descendingKeySet() {
831	>	return descendingMap().navigableKeySet();
832	>	}
833	>
834	>	/**
835	>	* Returns a {@link Collection} view of the values contained in this map.
836	>	* The collection's iterator returns the values in ascending order
837	>	* of the corresponding keys.
838	>	* The collection is backed by the map, so changes to the map are
839	>	* reflected in the collection, and vice-versa.  If the map is
840	>	* modified while an iteration over the collection is in progress
841	>	* (except through the iterator's own <tt>remove</tt> operation),
842	>	* the results of the iteration are undefined.  The collection
843	>	* supports element removal, which removes the corresponding
844	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
845	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
846	>	* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
847	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
848		*/
849		public Collection<V> values() {
850		Collection<V> vs = values;
851		return (vs != null) ? vs : (values = new Values());
852		}
853
854	+	/**
855	+	* Returns a {@link Set} view of the mappings contained in this map.
856	+	* The set's iterator returns the entries in ascending key order.
857	+	* The set is backed by the map, so changes to the map are
858	+	* reflected in the set, and vice-versa.  If the map is modified
859	+	* while an iteration over the set is in progress (except through
860	+	* the iterator's own <tt>remove</tt> operation, or through the
861	+	* <tt>setValue</tt> operation on a map entry returned by the
862	+	* iterator) the results of the iteration are undefined.  The set
863	+	* supports element removal, which removes the corresponding
864	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
865	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
866	+	* <tt>clear</tt> operations.  It does not support the
867	+	* <tt>add</tt> or <tt>addAll</tt> operations.
868	+	*/
869	+	public Set<Map.Entry<K,V>> entrySet() {
870	+	EntrySet es = entrySet;
871	+	return (es != null) ? es : (entrySet = new EntrySet());
872	+	}
873	+
874	+	/**
875	+	* @since 1.6
876	+	*/
877	+	public NavigableMap<K, V> descendingMap() {
878	+	NavigableMap<K, V> km = descendingMap;
879	+	return (km != null) ? km :
880	+	(descendingMap = new DescendingSubMap(this,
881	+	true, null, 0,
882	+	true, null, 0));
883	+	}
884	+
885	+	/**
886	+	* @throws ClassCastException       {@inheritDoc}
887	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
888	+	*         null and this map uses natural ordering, or its comparator
889	+	*         does not permit null keys
890	+	* @throws IllegalArgumentException {@inheritDoc}
891	+	* @since 1.6
892	+	*/
893	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
894	+	K toKey,   boolean toInclusive) {
895	+	return new AscendingSubMap(this,
896	+	false, fromKey, excluded(fromInclusive),
897	+	false, toKey,   excluded(toInclusive));
898	+	}
899	+
900	+	/**
901	+	* @throws ClassCastException       {@inheritDoc}
902	+	* @throws NullPointerException if <tt>toKey</tt> is null
903	+	*         and this map uses natural ordering, or its comparator
904	+	*         does not permit null keys
905	+	* @throws IllegalArgumentException {@inheritDoc}
906	+	* @since 1.6
907	+	*/
908	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
909	+	return new AscendingSubMap(this,
910	+	true, null, 0,
911	+	false, toKey, excluded(inclusive));
912	+	}
913	+
914	+	/**
915	+	* @throws ClassCastException       {@inheritDoc}
916	+	* @throws NullPointerException if <tt>fromKey</tt> is null
917	+	*         and this map uses natural ordering, or its comparator
918	+	*         does not permit null keys
919	+	* @throws IllegalArgumentException {@inheritDoc}
920	+	* @since 1.6
921	+	*/
922	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
923	+	return new AscendingSubMap(this,
924	+	false, fromKey, excluded(inclusive),
925	+	true, null, 0);
926	+	}
927	+
928	+	/**
929	+	* Translates a boolean "inclusive" value to the correct int value
930	+	* for the loExcluded or hiExcluded field.
931	+	*/
932	+	static int excluded(boolean inclusive) {
933	+	return inclusive ? 0 : 1;
934	+	}
935	+
936	+	/**
937	+	* @throws ClassCastException       {@inheritDoc}
938	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
939	+	*         null and this map uses natural ordering, or its comparator
940	+	*         does not permit null keys
941	+	* @throws IllegalArgumentException {@inheritDoc}
942	+	*/
943	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
944	+	return subMap(fromKey, true, toKey, false);
945	+	}
946	+
947	+	/**
948	+	* @throws ClassCastException       {@inheritDoc}
949	+	* @throws NullPointerException if <tt>toKey</tt> is null
950	+	*         and this map uses natural ordering, or its comparator
951	+	*         does not permit null keys
952	+	* @throws IllegalArgumentException {@inheritDoc}
953	+	*/
954	+	public SortedMap<K,V> headMap(K toKey) {
955	+	return headMap(toKey, false);
956	+	}
957	+
958	+	/**
959	+	* @throws ClassCastException       {@inheritDoc}
960	+	* @throws NullPointerException if <tt>fromKey</tt> is null
961	+	*         and this map uses natural ordering, or its comparator
962	+	*         does not permit null keys
963	+	* @throws IllegalArgumentException {@inheritDoc}
964	+	*/
965	+	public SortedMap<K,V> tailMap(K fromKey) {
966	+	return tailMap(fromKey, true);
967	+	}
968	+
969	+	// View class support
970	+
971		class Values extends AbstractCollection<V> {
972		public Iterator<V> iterator() {
973		return new ValueIterator(getFirstEntry());
974		}
975	<
975	>
976		public int size() {
977		return TreeMap.this.size();
978		}
979	<
979	>
980		public boolean contains(Object o) {
981		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
982		if (valEquals(e.getValue(), o))
983		return true;
984		return false;
985		}
986	<
986	>
987		public boolean remove(Object o) {
988		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
989		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 993 | public class TreeMap<K,V>
993		}
994		return false;
995		}
996	<
996	>
997		public void clear() {
998		TreeMap.this.clear();
999		}
1000		}
1001
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	–
1002		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1003		public Iterator<Map.Entry<K,V>> iterator() {
1004		return new EntryIterator(getFirstEntry());
1005		}
1006	<
1006	>
1007		public boolean contains(Object o) {
1008		if (!(o instanceof Map.Entry))
1009		return false;
#	Line 1001 | Line 1012 | public class TreeMap<K,V>
1012		Entry<K,V> p = getEntry(entry.getKey());
1013		return p != null && valEquals(p.getValue(), value);
1014		}
1015	<
1015	>
1016		public boolean remove(Object o) {
1017		if (!(o instanceof Map.Entry))
1018		return false;
#	Line 1014 | Line 1025 | public class TreeMap<K,V>
1025		}
1026		return false;
1027		}
1028	<
1028	>
1029		public int size() {
1030		return TreeMap.this.size();
1031		}
1032	<
1032	>
1033		public void clear() {
1034		TreeMap.this.clear();
1035		}
1036		}
1037
1038	<	/**
1039	<	* Returns a set view of the mappings contained in this map.  The
1040	<	* set's iterator returns the mappings in descending key order.
1041	<	* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1042	<	* set is backed by this map, so changes to this map are reflected
1043	<	* in the set, and vice-versa.  The set supports element removal,
1044	<	* which removes the corresponding mapping from the TreeMap,
1045	<	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1046	<	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1047	<	* 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());
1038	>	/*
1039	>	* Unlike Values and EntrySet, the KeySet class is static,
1040	>	* delegating to a NavigableMap to allow use by SubMaps, which
1041	>	* outweighs the ugliness of needing type-tests for the following
1042	>	* Iterator methods that are defined appropriately in main versus
1043	>	* submap classes.
1044	>	*/
1045	>
1046	>	Iterator<K> keyIterator() {
1047	>	return new KeyIterator(getFirstEntry());
1048		}
1049
1050	<	class DescendingEntrySet extends EntrySet {
1051	<	public Iterator<Map.Entry<K,V>> iterator() {
1050	<	return new DescendingEntryIterator(getLastEntry());
1051	<	}
1050	>	Iterator<K> descendingKeyIterator() {
1051	>	return new DescendingKeyIterator(getFirstEntry());
1052		}
1053
1054	<	/**
1055	<	* Returns a Set view of the keys contained in this map.  The
1056	<	* set's iterator will return the keys in descending order.  The
1057	<	* map is backed by this <tt>TreeMap</tt> instance, so changes to
1058	<	* this map are reflected in the Set, and vice-versa.  The Set
1059	<	* supports element removal, which removes the corresponding
1060	<	* mapping from the map, via the <tt>Iterator.remove</tt>,
1061	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1062	<	* and <tt>clear</tt> operations.  It does not support the
1063	<	* <tt>add</tt> or <tt>addAll</tt> operations.
1064	<	*
1065	<	* @return a set view of the keys contained in this TreeMap.
1066	<	*/
1067	<	public Set<K> descendingKeySet() {
1068	<	Set<K> ks = descendingKeySet;
1069	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1070	<	}
1071	<
1072	<	class DescendingKeySet extends KeySet {
1073	<	public Iterator<K> iterator() {
1074	<	return new DescendingKeyIterator(getLastEntry());
1054	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1055	>	private final NavigableMap<E, Object> m;
1056	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1057	>
1058	>	public Iterator<E> iterator() {
1059	>	if (m instanceof TreeMap)
1060	>	return ((TreeMap<E,Object>)m).keyIterator();
1061	>	else
1062	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1063	>	}
1064	>
1065	>	public Iterator<E> descendingIterator() {
1066	>	if (m instanceof TreeMap)
1067	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1068	>	else
1069	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1070	>	}
1071	>
1072	>	public int size() { return m.size(); }
1073	>	public boolean isEmpty() { return m.isEmpty(); }
1074	>	public boolean contains(Object o) { return m.containsKey(o); }
1075	>	public void clear() { m.clear(); }
1076	>	public E lower(E e) { return m.lowerKey(e); }
1077	>	public E floor(E e) { return m.floorKey(e); }
1078	>	public E ceiling(E e) { return m.ceilingKey(e); }
1079	>	public E higher(E e) { return m.higherKey(e); }
1080	>	public E first() { return m.firstKey(); }
1081	>	public E last() { return m.lastKey(); }
1082	>	public Comparator<? super E> comparator() { return m.comparator(); }
1083	>	public E pollFirst() {
1084	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1085	>	return e == null? null : e.getKey();
1086	>	}
1087	>	public E pollLast() {
1088	>	Map.Entry<E,Object> e = m.pollLastEntry();
1089	>	return e == null? null : e.getKey();
1090	>	}
1091	>	public boolean remove(Object o) {
1092	>	int oldSize = size();
1093	>	m.remove(o);
1094	>	return size() != oldSize;
1095	>	}
1096	>	public NavigableSet<E> subSet(E fromElement,
1097	>	boolean fromInclusive,
1098	>	E toElement,
1099	>	boolean toInclusive) {
1100	>	return new TreeSet<E>
1101	>	(m.subMap(fromElement, fromInclusive,
1102	>	toElement,   toInclusive));
1103	>	}
1104	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1105	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1106	>	}
1107	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1108	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1109	>	}
1110	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1111	>	return subSet(fromElement, true, toElement, false);
1112	>	}
1113	>	public SortedSet<E> headSet(E toElement) {
1114	>	return headSet(toElement, false);
1115	>	}
1116	>	public SortedSet<E> tailSet(E fromElement) {
1117	>	return tailSet(fromElement, true);
1118	>	}
1119	>	public NavigableSet<E> descendingSet() {
1120	>	return new TreeSet(m.descendingMap());
1121		}
1122		}
1123
1124		/**
1125	<	* Returns a view of the portion of this map whose keys range from
1080	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1081	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1082	<	* navigable map is empty.)  The returned navigable map is backed
1083	<	* by this map, so changes in the returned navigable map are
1084	<	* reflected in this map, and vice-versa.  The returned navigable
1085	<	* map supports all optional map operations.<p>
1086	<	*
1087	<	* The navigable map returned by this method will throw an
1088	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1089	<	* less than <tt>fromKey</tt> or greater than or equal to
1090	<	* <tt>toKey</tt>.<p>
1091	<	*
1092	<	* Note: this method always returns a <i>half-open range</i> (which
1093	<	* includes its low endpoint but not its high endpoint).  If you need a
1094	<	* <i>closed range</i> (which includes both endpoints), and the key type
1095	<	* allows for calculation of the successor of a given key, merely request the
1096	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1097	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1098	<	* strings.  The following idiom obtains a view containing all of the
1099	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1100	<	* and <tt>high</tt>, inclusive:
1101	<	* <pre>  NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1102	<	* A similar technique can be used to generate an <i>open range</i> (which
1103	<	* contains neither endpoint).  The following idiom obtains a view
1104	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1105	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1106	<	* <pre>  NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1107	<	*
1108	<	* @param fromKey low endpoint (inclusive) of the subMap.
1109	<	* @param toKey high endpoint (exclusive) of the subMap.
1110	<	*
1111	<	* @return a view of the portion of this map whose keys range from
1112	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1113	<	*
1114	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1115	<	*         cannot be compared to one another using this map's comparator
1116	<	*         (or, if the map has no comparator, using natural ordering).
1117	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1118	<	*         <tt>toKey</tt>.
1119	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1120	<	*               <tt>null</tt> and this map uses natural order, or its
1121	<	*               comparator does not tolerate <tt>null</tt> keys.
1125	>	* Base class for TreeMap Iterators
1126		*/
1127	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1128	<	return new SubMap(fromKey, toKey);
1129	<	}
1127	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1128	>	int expectedModCount = TreeMap.this.modCount;
1129	>	Entry<K,V> lastReturned = null;
1130	>	Entry<K,V> next;
1131
1132	+	PrivateEntryIterator(Entry<K,V> first) {
1133	+	next = first;
1134	+	}
1135
1136	<	/**
1137	<	* Returns a view of the portion of this map whose keys are strictly less
1138	<	* than <tt>toKey</tt>.  The returned navigable map is backed by this map, so
1139	<	* changes in the returned navigable map are reflected in this map, and
1140	<	* vice-versa.  The returned navigable map supports all optional map
1141	<	* operations.<p>
1142	<	*
1143	<	* The navigable map returned by this method will throw an
1144	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1145	<	* greater than or equal to <tt>toKey</tt>.<p>
1146	<	*
1147	<	* Note: this method always returns a view that does not contain its
1148	<	* (high) endpoint.  If you need a view that does contain this endpoint,
1149	<	* and the key type allows for calculation of the successor of a given key,
1150	<	* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1151	<	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1152	<	* keys are strings.  The following idiom obtains a view containing all of
1153	<	* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1154	<	* to <tt>high</tt>:
1155	<	* <pre>
1156	<	*     NavigableMap head = m.headMap(high+"\0");
1157	<	* </pre>
1158	<	*
1159	<	* @param toKey high endpoint (exclusive) of the headMap.
1160	<	* @return a view of the portion of this map whose keys are strictly
1161	<	*                less than <tt>toKey</tt>.
1162	<	*
1163	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1164	<	*         with this map's comparator (or, if the map has no comparator,
1165	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1166	<	* @throws IllegalArgumentException if this map is itself a subMap,
1167	<	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1168	<	*         specified range of the subMap, headMap, or tailMap.
1169	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1170	<	*               this map uses natural order, or its comparator does not
1163	<	*               tolerate <tt>null</tt> keys.
1164	<	*/
1165	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1166	<	return new SubMap(toKey, true);
1167	<	}
1168	<
1169	<	/**
1170	<	* Returns a view of the portion of this map whose keys are greater than
1171	<	* or equal to <tt>fromKey</tt>.  The returned navigable map is backed by
1172	<	* this map, so changes in the returned navigable map are reflected in this
1173	<	* map, and vice-versa.  The returned navigable map supports all optional map
1174	<	* operations.<p>
1175	<	*
1176	<	* The navigable map returned by this method will throw an
1177	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1178	<	* less than <tt>fromKey</tt>.<p>
1179	<	*
1180	<	* Note: this method always returns a view that contains its (low)
1181	<	* endpoint.  If you need a view that does not contain this endpoint, and
1182	<	* the element type allows for calculation of the successor of a given value,
1183	<	* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1184	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1185	<	* are strings.  The following idiom obtains a view containing
1186	<	* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1187	<	* greater than <tt>low</tt>: <pre>
1188	<	*     NavigableMap tail = m.tailMap(low+"\0");
1189	<	* </pre>
1190	<	*
1191	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1192	<	* @return a view of the portion of this map whose keys are greater
1193	<	*                than or equal to <tt>fromKey</tt>.
1194	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1195	<	*         with this map's comparator (or, if the map has no comparator,
1196	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1197	<	* @throws IllegalArgumentException if this map is itself a subMap,
1198	<	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1199	<	*         specified range of the subMap, headMap, or tailMap.
1200	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1201	<	*               this map uses natural order, or its comparator does not
1202	<	*               tolerate <tt>null</tt> keys.
1203	<	*/
1204	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1205	<	return new SubMap(fromKey, false);
1206	<	}
1207	<
1208	<	/**
1209	<	* Equivalent to <tt>navigableSubMap</tt> but with a return
1210	<	* type conforming to the <tt>SortedMap</tt> interface.
1211	<	* @param fromKey low endpoint (inclusive) of the subMap.
1212	<	* @param toKey high endpoint (exclusive) of the subMap.
1213	<	*
1214	<	* @return a view of the portion of this map whose keys range from
1215	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1216	<	*
1217	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1218	<	*         cannot be compared to one another using this map's comparator
1219	<	*         (or, if the map has no comparator, using natural ordering).
1220	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1221	<	*         <tt>toKey</tt>.
1222	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1223	<	*               <tt>null</tt> and this map uses natural order, or its
1224	<	*               comparator does not tolerate <tt>null</tt> keys.
1225	<	*/
1226	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1227	<	return new SubMap(fromKey, toKey);
1136	>	public final boolean hasNext() {
1137	>	return next != null;
1138	>	}
1139	>
1140	>	final Entry<K,V> nextEntry() {
1141	>	if (next == null)
1142	>	throw new NoSuchElementException();
1143	>	if (modCount != expectedModCount)
1144	>	throw new ConcurrentModificationException();
1145	>	lastReturned = next;
1146	>	next = successor(next);
1147	>	return lastReturned;
1148	>	}
1149	>
1150	>	final Entry<K,V> prevEntry() {
1151	>	if (next == null)
1152	>	throw new NoSuchElementException();
1153	>	if (modCount != expectedModCount)
1154	>	throw new ConcurrentModificationException();
1155	>	lastReturned = next;
1156	>	next = predecessor(next);
1157	>	return lastReturned;
1158	>	}
1159	>
1160	>	public void remove() {
1161	>	if (lastReturned == null)
1162	>	throw new IllegalStateException();
1163	>	if (modCount != expectedModCount)
1164	>	throw new ConcurrentModificationException();
1165	>	if (lastReturned.left != null && lastReturned.right != null)
1166	>	next = lastReturned;
1167	>	deleteEntry(lastReturned);
1168	>	expectedModCount++;
1169	>	lastReturned = null;
1170	>	}
1171		}
1172
1173	+	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1174	+	EntryIterator(Entry<K,V> first) {
1175	+	super(first);
1176	+	}
1177	+	public Map.Entry<K,V> next() {
1178	+	return nextEntry();
1179	+	}
1180	+	}
1181
1182	<	/**
1183	<	* Equivalent to <tt>navigableHeadMap</tt> but with a return
1184	<	* type conforming to the <tt>SortedMap</tt> interface.
1185	<	*
1186	<	* @param toKey high endpoint (exclusive) of the headMap.
1187	<	* @return a view of the portion of this map whose keys are strictly
1188	<	*                less than <tt>toKey</tt>.
1238	<	*
1239	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1240	<	*         with this map's comparator (or, if the map has no comparator,
1241	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1242	<	* @throws IllegalArgumentException if this map is itself a subMap,
1243	<	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1244	<	*         specified range of the subMap, headMap, or tailMap.
1245	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1246	<	*               this map uses natural order, or its comparator does not
1247	<	*               tolerate <tt>null</tt> keys.
1248	<	*/
1249	<	public SortedMap<K,V> headMap(K toKey) {
1250	<	return new SubMap(toKey, true);
1182	>	final class ValueIterator extends PrivateEntryIterator<V> {
1183	>	ValueIterator(Entry<K,V> first) {
1184	>	super(first);
1185	>	}
1186	>	public V next() {
1187	>	return nextEntry().value;
1188	>	}
1189		}
1190
1191	<	/**
1192	<	* Equivalent to <tt>navigableTailMap</tt> but with a return
1193	<	* type conforming to the <tt>SortedMap</tt> interface.
1194	<	*
1195	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1196	<	* @return a view of the portion of this map whose keys are greater
1197	<	*                than or equal to <tt>fromKey</tt>.
1260	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1261	<	*         with this map's comparator (or, if the map has no comparator,
1262	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1263	<	* @throws IllegalArgumentException if this map is itself a subMap,
1264	<	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1265	<	*         specified range of the subMap, headMap, or tailMap.
1266	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1267	<	*               this map uses natural order, or its comparator does not
1268	<	*               tolerate <tt>null</tt> keys.
1269	<	*/
1270	<	public SortedMap<K,V> tailMap(K fromKey) {
1271	<	return new SubMap(fromKey, false);
1191	>	final class KeyIterator extends PrivateEntryIterator<K> {
1192	>	KeyIterator(Entry<K,V> first) {
1193	>	super(first);
1194	>	}
1195	>	public K next() {
1196	>	return nextEntry().key;
1197	>	}
1198		}
1199
1200	<	private class SubMap
1201	<	extends AbstractMap<K,V>
1202	<	implements NavigableMap<K,V>, java.io.Serializable {
1203	<	private static final long serialVersionUID = -6520786458950516097L;
1200	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1201	>	DescendingKeyIterator(Entry<K,V> first) {
1202	>	super(first);
1203	>	}
1204	>	public K next() {
1205	>	return prevEntry().key;
1206	>	}
1207	>	}
1208	>
1209	>	// SubMaps
1210	>
1211	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1212	>	implements NavigableMap<K,V>, java.io.Serializable {
1213	>
1214	>	/*
1215	>	* The backing map.
1216	>	*/
1217	>	final TreeMap<K,V> m;
1218	>
1219	>	/** True if low point is from start of backing map */
1220	>	boolean fromStart;
1221	>
1222	>	/**
1223	>	* The low endpoint of this submap in absolute terms, or null
1224	>	* if fromStart.
1225	>	*/
1226	>	K lo;
1227
1228		/**
1229	<	* fromKey is significant only if fromStart is false.  Similarly,
1230	<	* toKey is significant only if toStart is false.
1229	>	* Zero if the low endpoint is excluded from this submap, one if
1230	>	* it's included.  This field is unused if fromStart.
1231		*/
1232	<	private boolean fromStart = false, toEnd = false;
1284	<	private K fromKey, toKey;
1232	>	int loExcluded;
1233
1234	<	SubMap(K fromKey, K toKey) {
1235	<	if (compare(fromKey, toKey) > 0)
1288	<	throw new IllegalArgumentException("fromKey > toKey");
1289	<	this.fromKey = fromKey;
1290	<	this.toKey = toKey;
1291	<	}
1234	>	/** True if high point is to End of backing map */
1235	>	boolean toEnd;
1236
1237	<	SubMap(K key, boolean headMap) {
1238	<	compare(key, key); // Type-check key
1237	>	/**
1238	>	* The high endpoint of this submap in absolute terms, or null
1239	>	* if toEnd.
1240	>	*/
1241	>	K hi;
1242
1243	<	if (headMap) {
1244	<	fromStart = true;
1245	<	toKey = key;
1246	<	} else {
1247	<	toEnd = true;
1301	<	fromKey = key;
1302	<	}
1303	<	}
1243	>	/**
1244	>	* Zero if the high endpoint is excluded from this submap, one if
1245	>	* it's included.  This field is unused if toEnd.
1246	>	*/
1247	>	int hiExcluded;
1248
1249	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1249	>	NavigableSubMap(TreeMap<K,V> m,
1250	>	boolean fromStart, K lo, int loExcluded,
1251	>	boolean toEnd, K hi, int hiExcluded) {
1252	>	if (!fromStart && !toEnd && m.compare(lo, hi) > 0)
1253	>	throw new IllegalArgumentException("fromKey > toKey");
1254	>	this.m = m;
1255		this.fromStart = fromStart;
1256	<	this.fromKey= fromKey;
1256	>	this.lo = lo;
1257	>	this.loExcluded = loExcluded;
1258		this.toEnd = toEnd;
1259	<	this.toKey = toKey;
1259	>	this.hi = hi;
1260	>	this.hiExcluded = hiExcluded;
1261		}
1262
1263	<	public boolean isEmpty() {
1264	<	return entrySet.isEmpty();
1263	>	// internal utilities
1264	>
1265	>	final boolean inRange(Object key) {
1266	>	return (fromStart || m.compare(key, lo) >= loExcluded)
1267	>	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1268		}
1269
1270	<	public boolean containsKey(Object key) {
1271	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1270	>	final boolean inClosedRange(Object key) {
1271	>	return (fromStart || m.compare(key, lo) >= 0)
1272	>	&& (toEnd || m.compare(hi, key) >= 0);
1273		}
1274
1275	<	public V get(Object key) {
1276	<	if (!inRange((K) key))
1322	<	return null;
1323	<	return TreeMap.this.get(key);
1275	>	final boolean inRange(Object key, boolean inclusive) {
1276	>	return inclusive ? inRange(key) : inClosedRange(key);
1277		}
1278
1279	<	public V put(K key, V value) {
1280	<	if (!inRange(key))
1328	<	throw new IllegalArgumentException("key out of range");
1329	<	return TreeMap.this.put(key, value);
1279	>	final boolean tooLow(K key) {
1280	>	return !fromStart && m.compare(key, lo) < loExcluded;
1281		}
1282
1283	<	public V remove(Object key) {
1284	<	if (!inRange((K) key))
1334	<	return null;
1335	<	return TreeMap.this.remove(key);
1283	>	final boolean tooHigh(K key) {
1284	>	return !toEnd && m.compare(hi, key) < hiExcluded;
1285		}
1286
1287	<	public Comparator<? super K> comparator() {
1288	<	return comparator;
1287	>
1288	>	/** Returns the lowest entry in this submap (absolute ordering) */
1289	>	final TreeMap.Entry<K,V> loEntry() {
1290	>	TreeMap.Entry<K,V> result =
1291	>	(fromStart ?  m.getFirstEntry() :
1292	>	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1293	>	m.getHigherEntry(lo)));
1294	>	return (result == null || tooHigh(result.key)) ? null : result;
1295		}
1296
1297	<	public K firstKey() {
1298	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1299	<	K first = key(e);
1300	<	if (!toEnd && compare(first, toKey) >= 0)
1301	<	throw(new NoSuchElementException());
1302	<	return first;
1297	>	/** Returns the highest key in this submap (absolute ordering) */
1298	>	final TreeMap.Entry<K,V> hiEntry() {
1299	>	TreeMap.Entry<K,V> result =
1300	>	(toEnd ?  m.getLastEntry() :
1301	>	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1302	>	m.getLowerEntry(hi)));
1303	>	return (result == null || tooLow(result.key)) ? null : result;
1304		}
1305
1306	<	public K lastKey() {
1307	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1308	<	K last = key(e);
1309	<	if (!fromStart && compare(last, fromKey) < 0)
1310	<	throw(new NoSuchElementException());
1311	<	return last;
1306	>	/** Polls the lowest entry in this submap (absolute ordering) */
1307	>	final Map.Entry<K,V> pollLoEntry() {
1308	>	TreeMap.Entry<K,V> e = loEntry();
1309	>	if (e == null)
1310	>	return null;
1311	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1312	>	m.deleteEntry(e);
1313	>	return result;
1314		}
1315
1316	<	public Map.Entry<K,V> firstEntry() {
1317	<	TreeMap.Entry<K,V> e = fromStart ?
1318	<	getFirstEntry() : getCeilingEntry(fromKey);
1319	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1316	>	/** Polls the highest key in this submap (absolute ordering) */
1317	>	final Map.Entry<K,V> pollHiEntry() {
1318	>	TreeMap.Entry<K,V> e = hiEntry();
1319	>	if (e == null)
1320		return null;
1321	<	return e;
1321	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1322	>	m.deleteEntry(e);
1323	>	return result;
1324		}
1325
1326	<	public Map.Entry<K,V> lastEntry() {
1327	<	TreeMap.Entry<K,V> e = toEnd ?
1328	<	getLastEntry() : getLowerEntry(toKey);
1329	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1326	>	/**
1327	>	* Return the absolute high fence for ascending traversal
1328	>	*/
1329	>	final TreeMap.Entry<K,V> hiFence() {
1330	>	if (toEnd)
1331		return null;
1332	<	return e;
1332	>	else if (hiExcluded == 0)
1333	>	return m.getHigherEntry(hi);
1334	>	else
1335	>	return m.getCeilingEntry(hi);
1336		}
1337
1338	<	public Map.Entry<K,V> pollFirstEntry() {
1339	<	TreeMap.Entry<K,V> e = fromStart ?
1340	<	getFirstEntry() : getCeilingEntry(fromKey);
1341	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1338	>	/**
1339	>	* Return the absolute low fence for descending traversal
1340	>	*/
1341	>	final TreeMap.Entry<K,V> loFence() {
1342	>	if (fromStart)
1343		return null;
1344	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1345	<	deleteEntry(e);
1346	<	return result;
1344	>	else if (loExcluded == 0)
1345	>	return m.getLowerEntry(lo);
1346	>	else
1347	>	return m.getFloorEntry(lo);
1348		}
1349
1350	<	public Map.Entry<K,V> pollLastEntry() {
1351	<	TreeMap.Entry<K,V> e = toEnd ?
1352	<	getLastEntry() : getLowerEntry(toKey);
1353	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1350	>
1351	>	public boolean isEmpty() {
1352	>	return entrySet().isEmpty();
1353	>	}
1354	>
1355	>	public boolean containsKey(Object key) {
1356	>	return inRange(key) && m.containsKey(key);
1357	>	}
1358	>
1359	>	public V get(Object key) {
1360	>	if (!inRange(key))
1361		return null;
1362	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1363	<	deleteEntry(e);
1364	<	return result;
1362	>	return m.get(key);
1363	>	}
1364	>
1365	>	public V put(K key, V value) {
1366	>	if (!inRange(key))
1367	>	throw new IllegalArgumentException("key out of range");
1368	>	return m.put(key, value);
1369		}
1370
1371	<	private TreeMap.Entry<K,V> subceiling(K key) {
1372	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1396	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1397	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1371	>	public V remove(Object key) {
1372	>	if (!inRange(key))
1373		return null;
1374	<	return e;
1374	>	return m.remove(key);
1375		}
1376
1377		public Map.Entry<K,V> ceilingEntry(K key) {
1378	<	TreeMap.Entry<K,V> e = subceiling(key);
1379	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1378	>	TreeMap.Entry<K,V> e = subCeiling(key);
1379	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1380		}
1381
1382		public K ceilingKey(K key) {
1383	<	TreeMap.Entry<K,V> e = subceiling(key);
1383	>	TreeMap.Entry<K,V> e = subCeiling(key);
1384		return e == null? null : e.key;
1385		}
1386
1412	–
1413	–	private TreeMap.Entry<K,V> subhigher(K key) {
1414	–	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1415	–	getCeilingEntry(fromKey) : getHigherEntry(key);
1416	–	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1417	–	return null;
1418	–	return e;
1419	–	}
1420	–
1387		public Map.Entry<K,V> higherEntry(K key) {
1388	<	TreeMap.Entry<K,V> e = subhigher(key);
1389	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1388	>	TreeMap.Entry<K,V> e = subHigher(key);
1389	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1390		}
1391
1392		public K higherKey(K key) {
1393	<	TreeMap.Entry<K,V> e = subhigher(key);
1393	>	TreeMap.Entry<K,V> e = subHigher(key);
1394		return e == null? null : e.key;
1395		}
1396
1431	–	private TreeMap.Entry<K,V> subfloor(K key) {
1432	–	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1433	–	getLowerEntry(toKey) : getFloorEntry(key);
1434	–	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1435	–	return null;
1436	–	return e;
1437	–	}
1438	–
1397		public Map.Entry<K,V> floorEntry(K key) {
1398	<	TreeMap.Entry<K,V> e = subfloor(key);
1399	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1398	>	TreeMap.Entry<K,V> e = subFloor(key);
1399	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1400		}
1401
1402		public K floorKey(K key) {
1403	<	TreeMap.Entry<K,V> e = subfloor(key);
1403	>	TreeMap.Entry<K,V> e = subFloor(key);
1404		return e == null? null : e.key;
1405		}
1406
1449	–	private TreeMap.Entry<K,V> sublower(K key) {
1450	–	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1451	–	getLowerEntry(toKey) :  getLowerEntry(key);
1452	–	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1453	–	return null;
1454	–	return e;
1455	–	}
1456	–
1407		public Map.Entry<K,V> lowerEntry(K key) {
1408	<	TreeMap.Entry<K,V> e = sublower(key);
1409	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1408	>	TreeMap.Entry<K,V> e = subLower(key);
1409	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1410		}
1411
1412		public K lowerKey(K key) {
1413	<	TreeMap.Entry<K,V> e = sublower(key);
1413	>	TreeMap.Entry<K,V> e = subLower(key);
1414		return e == null? null : e.key;
1415		}
1416
1417	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1417	>	abstract Iterator<K> keyIterator();
1418	>	abstract Iterator<K> descendingKeyIterator();
1419
1420	<	public Set<Map.Entry<K,V>> entrySet() {
1421	<	return entrySet;
1420	>	public NavigableSet<K> descendingKeySet() {
1421	>	return descendingMap().navigableKeySet();
1422		}
1423
1424	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1424	>	// Views
1425	>	transient NavigableMap<K,V> descendingMapView = null;
1426	>	transient EntrySetView entrySetView = null;
1427	>	transient KeySet<K> navigableKeySetView = null;
1428	>
1429	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1430		private transient int size = -1, sizeModCount;
1431
1432		public int size() {
1433	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1434	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1433	>	if (fromStart && toEnd)
1434	>	return m.size();
1435	>	if (size == -1 || sizeModCount != m.modCount) {
1436	>	sizeModCount = m.modCount;
1437	>	size = 0;
1438		Iterator i = iterator();
1439		while (i.hasNext()) {
1440		size++;
#	Line 1486 | Line 1445 | public class TreeMap<K,V>
1445		}
1446
1447		public boolean isEmpty() {
1448	<	return !iterator().hasNext();
1448	>	TreeMap.Entry<K,V> n = loEntry();
1449	>	return n == null || tooHigh(n.key);
1450		}
1451
1452		public boolean contains(Object o) {
#	Line 1496 | Line 1456 | public class TreeMap<K,V>
1456		K key = entry.getKey();
1457		if (!inRange(key))
1458		return false;
1459	<	TreeMap.Entry node = getEntry(key);
1459	>	TreeMap.Entry node = m.getEntry(key);
1460		return node != null &&
1461	<	valEquals(node.getValue(), entry.getValue());
1461	>	valEquals(node.getValue(), entry.getValue());
1462		}
1463
1464		public boolean remove(Object o) {
#	Line 1508 | Line 1468 | public class TreeMap<K,V>
1468		K key = entry.getKey();
1469		if (!inRange(key))
1470		return false;
1471	<	TreeMap.Entry<K,V> node = getEntry(key);
1471	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1472		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1473	<	deleteEntry(node);
1473	>	m.deleteEntry(node);
1474		return true;
1475		}
1476		return false;
1477		}
1478	+	}
1479
1480	<	public Iterator<Map.Entry<K,V>> iterator() {
1481	<	return new SubMapEntryIterator(
1482	<	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1483	<	(toEnd     ? null            : getCeilingEntry(toKey)));
1523	<	}
1480	>	public NavigableSet<K> navigableKeySet() {
1481	>	KeySet<K> nksv = navigableKeySetView;
1482	>	return (nksv != null) ? nksv :
1483	>	(navigableKeySetView = new TreeMap.KeySet(this));
1484		}
1485
1486	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1487	<	private transient Set<K> descendingKeySetView = null;
1486	>	public Set<K> keySet() {
1487	>	return navigableKeySet();
1488	>	}
1489
1490	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1491	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1531	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1490	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1491	>	return subMap(fromKey, true, toKey, false);
1492		}
1493
1494	<	public Set<K> descendingKeySet() {
1495	<	Set<K> ks = descendingKeySetView;
1536	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1494	>	public SortedMap<K,V> headMap(K toKey) {
1495	>	return headMap(toKey, false);
1496		}
1497
1498	<	private class DescendingEntrySetView extends EntrySetView {
1499	<	public Iterator<Map.Entry<K,V>> iterator() {
1500	<	return new DescendingSubMapEntryIterator
1501	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1502	<	(fromStart ? null            : getLowerEntry(fromKey)));
1498	>	public SortedMap<K,V> tailMap(K fromKey) {
1499	>	return tailMap(fromKey, true);
1500	>	}
1501	>
1502	>
1503	>	// The following four definitions are correct only for
1504	>	// ascending submaps. They are overridden in DescendingSubMap.
1505	>	// They are defined in the base class because the definitions
1506	>	// in DescendingSubMap rely on those for AscendingSubMap.
1507	>
1508	>	/**
1509	>	* Returns the entry corresponding to the ceiling of the specified
1510	>	* key from the perspective of this submap, or null if the submap
1511	>	* contains no such entry.
1512	>	*/
1513	>	TreeMap.Entry<K,V> subCeiling(K key) {
1514	>	if (tooLow(key))
1515	>	return loEntry();
1516	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1517	>	return (e == null || tooHigh(e.key)) ? null : e;
1518	>	}
1519	>
1520	>	/**
1521	>	* Returns the entry corresponding to the higher of the specified
1522	>	* key from the perspective of this submap, or null if the submap
1523	>	* contains no such entry.
1524	>	*/
1525	>	TreeMap.Entry<K,V> subHigher(K key) {
1526	>	if (tooLow(key))
1527	>	return loEntry();
1528	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1529	>	return (e == null || tooHigh(e.key)) ? null : e;
1530	>	}
1531	>
1532	>	/**
1533	>	* Returns the entry corresponding to the floor of the specified
1534	>	* key from the perspective of this submap, or null if the submap
1535	>	* contains no such entry.
1536	>	*/
1537	>	TreeMap.Entry<K,V> subFloor(K key) {
1538	>	if (tooHigh(key))
1539	>	return hiEntry();
1540	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1541	>	return (e == null || tooLow(e.key)) ? null : e;
1542	>	}
1543	>
1544	>	/**
1545	>	* Returns the entry corresponding to the lower of the specified
1546	>	* key from the perspective of this submap, or null if the submap
1547	>	* contains no such entry.
1548	>	*/
1549	>	TreeMap.Entry<K,V> subLower(K key) {
1550	>	if (tooHigh(key))
1551	>	return hiEntry();
1552	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1553	>	return (e == null || tooLow(e.key)) ? null : e;
1554	>	}
1555	>
1556	>	/**
1557	>	* Iterators for SubMaps
1558	>	*/
1559	>	abstract class SubMapIterator<T> implements Iterator<T> {
1560	>	int expectedModCount = m.modCount;
1561	>	TreeMap.Entry<K,V> lastReturned = null;
1562	>	TreeMap.Entry<K,V> next;
1563	>	final K firstExcludedKey;
1564	>
1565	>	SubMapIterator(TreeMap.Entry<K,V> first,
1566	>	TreeMap.Entry<K,V> firstExcluded) {
1567	>	next = first;
1568	>	firstExcludedKey = (firstExcluded == null ? null
1569	>	: firstExcluded.key);
1570	>	}
1571	>
1572	>	public final boolean hasNext() {
1573	>	return next != null && next.key != firstExcludedKey;
1574	>	}
1575	>
1576	>	final TreeMap.Entry<K,V> nextEntry() {
1577	>	if (next == null || next.key == firstExcludedKey)
1578	>	throw new NoSuchElementException();
1579	>	if (m.modCount != expectedModCount)
1580	>	throw new ConcurrentModificationException();
1581	>	lastReturned = next;
1582	>	next = m.successor(next);
1583	>	return lastReturned;
1584	>	}
1585	>
1586	>	final TreeMap.Entry<K,V> prevEntry() {
1587	>	if (next == null || next.key == firstExcludedKey)
1588	>	throw new NoSuchElementException();
1589	>	if (m.modCount != expectedModCount)
1590	>	throw new ConcurrentModificationException();
1591	>	lastReturned = next;
1592	>	next = m.predecessor(next);
1593	>	return lastReturned;
1594	>	}
1595	>
1596	>	public void remove() {
1597	>	if (lastReturned == null)
1598	>	throw new IllegalStateException();
1599	>	if (m.modCount != expectedModCount)
1600	>	throw new ConcurrentModificationException();
1601	>	if (lastReturned.left != null && lastReturned.right != null)
1602	>	next = lastReturned;
1603	>	m.deleteEntry(lastReturned);
1604	>	expectedModCount++;
1605	>	lastReturned = null;
1606		}
1607		}
1608
1609	<	private class DescendingKeySetView extends AbstractSet<K> {
1610	<	public Iterator<K> iterator() {
1611	<	return new Iterator<K>() {
1612	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1551	<
1552	<	public boolean hasNext() { return i.hasNext(); }
1553	<	public K next() { return i.next().getKey(); }
1554	<	public void remove() { i.remove(); }
1555	<	};
1609	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1610	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1611	>	TreeMap.Entry<K,V> firstExcluded) {
1612	>	super(first, firstExcluded);
1613		}
1614	<
1615	<	public int size() {
1616	<	return SubMap.this.size();
1614	>	public Map.Entry<K,V> next() {
1615	>	return nextEntry();
1616	>	}
1617	>	}
1618	>
1619	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1620	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1621	>	TreeMap.Entry<K,V> firstExcluded) {
1622	>	super(first, firstExcluded);
1623		}
1624	<
1625	<	public boolean contains(Object k) {
1563	<	return SubMap.this.containsKey(k);
1624	>	public K next() {
1625	>	return nextEntry().key;
1626		}
1627		}
1628
1629	+	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1630	+	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1631	+	TreeMap.Entry<K,V> lastExcluded) {
1632	+	super(last, lastExcluded);
1633	+	}
1634	+
1635	+	public Map.Entry<K,V> next() {
1636	+	return prevEntry();
1637	+	}
1638	+	}
1639
1640	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1641	<	if (!inRange2(fromKey))
1640	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1641	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1642	>	TreeMap.Entry<K,V> lastExcluded) {
1643	>	super(last, lastExcluded);
1644	>	}
1645	>	public K next() {
1646	>	return prevEntry().key;
1647	>	}
1648	>	}
1649	>	}
1650	>
1651	>	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1652	>	private static final long serialVersionUID = 912986545866124060L;
1653	>
1654	>	AscendingSubMap(TreeMap<K,V> m,
1655	>	boolean fromStart, K lo, int loExcluded,
1656	>	boolean toEnd, K hi, int hiExcluded) {
1657	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1658	>	}
1659	>
1660	>	public Comparator<? super K> comparator() {
1661	>	return m.comparator();
1662	>	}
1663	>
1664	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1665	>	K toKey, boolean toInclusive) {
1666	>	if (!inRange(fromKey, fromInclusive))
1667		throw new IllegalArgumentException("fromKey out of range");
1668	<	if (!inRange2(toKey))
1668	>	if (!inRange(toKey, toInclusive))
1669		throw new IllegalArgumentException("toKey out of range");
1670	<	return new SubMap(fromKey, toKey);
1670	>	return new AscendingSubMap(m,
1671	>	false, fromKey, excluded(fromInclusive),
1672	>	false, toKey,   excluded(toInclusive));
1673		}
1674
1675	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1676	<	if (!inRange2(toKey))
1675	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1676	>	if (!inClosedRange(toKey))
1677		throw new IllegalArgumentException("toKey out of range");
1678	<	return new SubMap(fromStart, fromKey, false, toKey);
1678	>	return new AscendingSubMap(m,
1679	>	fromStart, lo,    loExcluded,
1680	>	false, toKey, excluded(inclusive));
1681		}
1682
1683	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1684	<	if (!inRange2(fromKey))
1683	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1684	>	if (!inRange(fromKey, inclusive))
1685		throw new IllegalArgumentException("fromKey out of range");
1686	<	return new SubMap(false, fromKey, toEnd, toKey);
1686	>	return new AscendingSubMap(m,
1687	>	false, fromKey, excluded(inclusive),
1688	>	toEnd, hi,      hiExcluded);
1689		}
1690
1691	<
1692	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1590	<	return navigableSubMap(fromKey, toKey);
1691	>	Iterator<K> keyIterator() {
1692	>	return new SubMapKeyIterator(loEntry(), hiFence());
1693		}
1694
1695	<	public SortedMap<K,V> headMap(K toKey) {
1696	<	return navigableHeadMap(toKey);
1695	>	Iterator<K> descendingKeyIterator() {
1696	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1697		}
1698
1699	<	public SortedMap<K,V> tailMap(K fromKey) {
1700	<	return navigableTailMap(fromKey);
1699	>	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1700	>	public Iterator<Map.Entry<K,V>> iterator() {
1701	>	return new SubMapEntryIterator(loEntry(), hiFence());
1702	>	}
1703		}
1704
1705	<	private boolean inRange(K key) {
1706	<	return (fromStart || compare(key, fromKey) >= 0) &&
1707	<	(toEnd     || compare(key, toKey)   <  0);
1705	>	public Set<Map.Entry<K,V>> entrySet() {
1706	>	EntrySetView es = entrySetView;
1707	>	return (es != null) ? es : new AscendingEntrySetView();
1708		}
1709
1710	<	// This form allows the high endpoint (as well as all legit keys)
1711	<	private boolean inRange2(K key) {
1608	<	return (fromStart || compare(key, fromKey) >= 0) &&
1609	<	(toEnd     || compare(key, toKey)   <= 0);
1710	>	public K firstKey() {
1711	>	return key(loEntry());
1712		}
1611	–	}
1713
1714	<	/**
1715	<	* TreeMap Iterator.
1615	<	*/
1616	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1617	<	int expectedModCount = TreeMap.this.modCount;
1618	<	Entry<K,V> lastReturned = null;
1619	<	Entry<K,V> next;
1620	<
1621	<	PrivateEntryIterator(Entry<K,V> first) {
1622	<	next = first;
1714	>	public K lastKey() {
1715	>	return key(hiEntry());
1716		}
1717
1718	<	public boolean hasNext() {
1719	<	return next != null;
1718	>	public Map.Entry<K,V> firstEntry() {
1719	>	return loEntry();
1720		}
1721
1722	<	Entry<K,V> nextEntry() {
1723	<	if (next == null)
1631	<	throw new NoSuchElementException();
1632	<	if (modCount != expectedModCount)
1633	<	throw new ConcurrentModificationException();
1634	<	lastReturned = next;
1635	<	next = successor(next);
1636	<	return lastReturned;
1722	>	public Map.Entry<K,V> lastEntry() {
1723	>	return hiEntry();
1724		}
1725
1726	<	public void remove() {
1727	<	if (lastReturned == null)
1641	<	throw new IllegalStateException();
1642	<	if (modCount != expectedModCount)
1643	<	throw new ConcurrentModificationException();
1644	<	if (lastReturned.left != null && lastReturned.right != null)
1645	<	next = lastReturned;
1646	<	deleteEntry(lastReturned);
1647	<	expectedModCount++;
1648	<	lastReturned = null;
1726	>	public Map.Entry<K,V> pollFirstEntry() {
1727	>	return pollLoEntry();
1728		}
1650	–	}
1729
1730	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1731	<	EntryIterator(Entry<K,V> first) {
1654	<	super(first);
1730	>	public Map.Entry<K,V> pollLastEntry() {
1731	>	return pollHiEntry();
1732		}
1733
1734	<	public Map.Entry<K,V> next() {
1735	<	return nextEntry();
1734	>	public NavigableMap<K,V> descendingMap() {
1735	>	NavigableMap<K,V> mv = descendingMapView;
1736	>	return (mv != null) ? mv :
1737	>	(descendingMapView =
1738	>	new DescendingSubMap(m,
1739	>	fromStart, lo, loExcluded,
1740	>	toEnd, hi, hiExcluded));
1741		}
1742		}
1743
1744	<	class KeyIterator extends PrivateEntryIterator<K> {
1745	<	KeyIterator(Entry<K,V> first) {
1746	<	super(first);
1747	<	}
1748	<	public K next() {
1749	<	return nextEntry().key;
1744	>	static 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, int loExcluded,
1748	>	boolean toEnd, K hi, int hiExcluded) {
1749	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1750		}
1669	–	}
1751
1752	<	class ValueIterator extends PrivateEntryIterator<V> {
1753	<	ValueIterator(Entry<K,V> first) {
1754	<	super(first);
1752	>	private final Comparator<? super K> reverseComparator =
1753	>	Collections.reverseOrder(m.comparator);
1754	>
1755	>	public Comparator<? super K> comparator() {
1756	>	return reverseComparator;
1757		}
1758	<	public V next() {
1759	<	return nextEntry().value;
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,   excluded(toInclusive),
1767	>	false, fromKey, excluded(fromInclusive));
1768		}
1678	–	}
1769
1770	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1771	<	private final K firstExcludedKey;
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, excluded(inclusive),
1775	>	toEnd, hi, hiExcluded);
1776	>	}
1777
1778	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1779	<	super(first);
1780	<	firstExcludedKey = (firstExcluded == null
1781	<	? null
1782	<	: firstExcluded.key);
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,      loExcluded,
1783	>	false, fromKey, excluded(inclusive));
1784		}
1785
1786	<	public boolean hasNext() {
1787	<	return next != null && next.key != firstExcludedKey;
1786	>	Iterator<K> keyIterator() {
1787	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1788		}
1789
1790	<	public Map.Entry<K,V> next() {
1791	<	if (next == null || next.key == firstExcludedKey)
1696	<	throw new NoSuchElementException();
1697	<	return nextEntry();
1790	>	Iterator<K> descendingKeyIterator() {
1791	>	return new SubMapKeyIterator(loEntry(), hiFence());
1792		}
1699	–	}
1793
1794	+	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1795	+	public Iterator<Map.Entry<K,V>> iterator() {
1796	+	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1797	+	}
1798	+	}
1799
1800	<	/**
1801	<	* Base for Descending Iterators.
1802	<	*/
1705	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1706	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1707	<	super(first);
1800	>	public Set<Map.Entry<K,V>> entrySet() {
1801	>	EntrySetView es = entrySetView;
1802	>	return (es != null) ? es : new DescendingEntrySetView();
1803		}
1804
1805	<	Entry<K,V> nextEntry() {
1806	<	if (next == null)
1712	<	throw new NoSuchElementException();
1713	<	if (modCount != expectedModCount)
1714	<	throw new ConcurrentModificationException();
1715	<	lastReturned = next;
1716	<	next = predecessor(next);
1717	<	return lastReturned;
1805	>	public K firstKey() {
1806	>	return key(hiEntry());
1807		}
1719	–	}
1808
1809	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1810	<	DescendingEntryIterator(Entry<K,V> first) {
1723	<	super(first);
1809	>	public K lastKey() {
1810	>	return key(loEntry());
1811		}
1812	<	public Map.Entry<K,V> next() {
1813	<	return nextEntry();
1812	>
1813	>	public Map.Entry<K,V> firstEntry() {
1814	>	return hiEntry();
1815		}
1728	–	}
1816
1817	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1818	<	DescendingKeyIterator(Entry<K,V> first) {
1732	<	super(first);
1817	>	public Map.Entry<K,V> lastEntry() {
1818	>	return loEntry();
1819		}
1820	<	public K next() {
1821	<	return nextEntry().key;
1820	>
1821	>	public Map.Entry<K,V> pollFirstEntry() {
1822	>	return pollHiEntry();
1823		}
1737	–	}
1824
1825	+	public Map.Entry<K,V> pollLastEntry() {
1826	+	return pollLoEntry();
1827	+	}
1828
1829	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1830	<	private final K lastExcludedKey;
1829	>	public NavigableMap<K,V> descendingMap() {
1830	>	NavigableMap<K,V> mv = descendingMapView;
1831	>	return (mv != null) ? mv :
1832	>	(descendingMapView =
1833	>	new AscendingSubMap(m,
1834	>	fromStart, lo, loExcluded,
1835	>	toEnd, hi, hiExcluded));
1836	>	}
1837
1838	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1839	<	super(last);
1745	<	lastExcludedKey = (lastExcluded == null
1746	<	? null
1747	<	: lastExcluded.key);
1838	>	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1839	>	return super.subFloor(key);
1840		}
1841
1842	<	public boolean hasNext() {
1843	<	return next != null && next.key != lastExcludedKey;
1842	>	@Override TreeMap.Entry<K,V> subHigher(K key) {
1843	>	return super.subLower(key);
1844		}
1845
1846	<	public Map.Entry<K,V> next() {
1847	<	if (next == null || next.key == lastExcludedKey)
1756	<	throw new NoSuchElementException();
1757	<	return nextEntry();
1846	>	@Override TreeMap.Entry<K,V> subFloor(K key) {
1847	>	return super.subCeiling(key);
1848		}
1849
1850	+	@Override TreeMap.Entry<K,V> subLower(K key) {
1851	+	return super.subHigher(key);
1852	+	}
1853		}
1854
1762	–
1855		/**
1856		* Compares two keys using the correct comparison method for this TreeMap.
1857		*/
1858	<	private int compare(K k1, K k2) {
1859	<	return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
1860	<	: comparator.compare((K)k1, (K)k2));
1858	>	final int compare(Object k1, Object k2) {
1859	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1860	>	: comparator.compare((K)k1, (K)k2);
1861		}
1862
1863		/**
1864	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1864	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1865		* that it copes with <tt>null</tt> o1 properly.
1866		*/
1867	<	private static boolean valEquals(Object o1, Object o2) {
1867	>	final static boolean valEquals(Object o1, Object o2) {
1868		return (o1==null ? o2==null : o1.equals(o2));
1869		}
1870
1871	+	/**
1872	+	* This class exists solely for the sake of serialization
1873	+	* compatibility with previous releases of TreeMap that did not
1874	+	* support NavigableMap.  It translates an old-version SubMap into
1875	+	* a new-version AscendingSubMap. This class is never otherwise
1876	+	* used.
1877	+	*/
1878	+	private class SubMap extends AbstractMap<K,V>
1879	+	implements SortedMap<K,V>, java.io.Serializable {
1880	+	private static final long serialVersionUID = -6520786458950516097L;
1881	+	private boolean fromStart = false, toEnd = false;
1882	+	private K fromKey, toKey;
1883	+	private Object readResolve() {
1884	+	return new AscendingSubMap(TreeMap.this,
1885	+	fromStart, fromKey, 0,
1886	+	toEnd, toKey, 1);
1887	+	}
1888	+	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1889	+	public K lastKey() { throw new InternalError(); }
1890	+	public K firstKey() { throw new InternalError(); }
1891	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1892	+	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1893	+	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1894	+	public Comparator<? super K> comparator() { throw new InternalError(); }
1895	+	}
1896	+
1897	+
1898		private static final boolean RED   = false;
1899		private static final boolean BLACK = true;
1900
#	Line 1784 | Line 1903 | public class TreeMap<K,V>
1903		* user (see Map.Entry).
1904		*/
1905
1906	<	static class Entry<K,V> implements Map.Entry<K,V> {
1906	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1907		K key;
1908		V value;
1909		Entry<K,V> left = null;
#	Line 1805 | Line 1924 | public class TreeMap<K,V>
1924		/**
1925		* Returns the key.
1926		*
1927	<	* @return the key.
1927	>	* @return the key
1928		*/
1929		public K getKey() {
1930		return key;
#	Line 1814 | Line 1933 | public class TreeMap<K,V>
1933		/**
1934		* Returns the value associated with the key.
1935		*
1936	<	* @return the value associated with the key.
1936	>	* @return the value associated with the key
1937		*/
1938		public V getValue() {
1939		return value;
#	Line 1825 | Line 1944 | public class TreeMap<K,V>
1944		* value.
1945		*
1946		* @return the value associated with the key before this method was
1947	<	*           called.
1947	>	*         called
1948		*/
1949		public V setValue(V value) {
1950		V oldValue = this.value;
#	Line 1856 | Line 1975 | public class TreeMap<K,V>
1975		* Returns the first Entry in the TreeMap (according to the TreeMap's
1976		* key-sort function).  Returns null if the TreeMap is empty.
1977		*/
1978	<	private Entry<K,V> getFirstEntry() {
1978	>	final Entry<K,V> getFirstEntry() {
1979		Entry<K,V> p = root;
1980		if (p != null)
1981		while (p.left != null)
#	Line 1868 | Line 1987 | public class TreeMap<K,V>
1987		* Returns the last Entry in the TreeMap (according to the TreeMap's
1988		* key-sort function).  Returns null if the TreeMap is empty.
1989		*/
1990	<	private Entry<K,V> getLastEntry() {
1990	>	final Entry<K,V> getLastEntry() {
1991		Entry<K,V> p = root;
1992		if (p != null)
1993		while (p.right != null)
#	Line 1879 | Line 1998 | public class TreeMap<K,V>
1998		/**
1999		* Returns the successor of the specified Entry, or null if no such.
2000		*/
2001	<	private Entry<K,V> successor(Entry<K,V> t) {
2001	>	final Entry<K,V> successor(Entry<K,V> t) {
2002		if (t == null)
2003		return null;
2004		else if (t.right != null) {
#	Line 1901 | Line 2020 | public class TreeMap<K,V>
2020		/**
2021		* Returns the predecessor of the specified Entry, or null if no such.
2022		*/
2023	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2023	>	final Entry<K,V> predecessor(Entry<K,V> t) {
2024		if (t == null)
2025		return null;
2026		else if (t.left != null) {
#	Line 2172 | Line 2291 | public class TreeMap<K,V>
2291		}
2292		}
2293
2175	–
2176	–
2294		/**
2295		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2296		* deserialize it).
#	Line 2196 | Line 2313 | public class TreeMap<K,V>
2313		}
2314
2315		/** Intended to be called only from TreeSet.addAll **/
2316	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
2316	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2317		try {
2318		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2319		} catch (java.io.IOException cannotHappen) {
#	Line 2221 | Line 2338 | public class TreeMap<K,V>
2338		* to calling this method.
2339		*
2340		* @param size the number of keys (or key-value pairs) to be read from
2341	<	*        the iterator or stream.
2341	>	*        the iterator or stream
2342		* @param it If non-null, new entries are created from entries
2343		*        or keys read from this iterator.
2344		* @param str If non-null, new entries are created from keys and
#	Line 2235 | Line 2352 | public class TreeMap<K,V>
2352		* @throws ClassNotFoundException propagated from readObject.
2353		*         This cannot occur if str is null.
2354		*/
2355	<	private
2356	<	void buildFromSorted(int size, Iterator it,
2357	<	java.io.ObjectInputStream str,
2241	<	V defaultVal)
2355	>	private void buildFromSorted(int size, Iterator it,
2356	>	java.io.ObjectInputStream str,
2357	>	V defaultVal)
2358		throws  java.io.IOException, ClassNotFoundException {
2359		this.size = size;
2360	<	root =
2361	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
2246	<	it, str, defaultVal);
2360	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2361	>	it, str, defaultVal);
2362		}
2363
2364		/**
2365		* Recursive "helper method" that does the real work of the
2366	<	* of the previous method.  Identically named parameters have
2366	>	* previous method.  Identically named parameters have
2367		* identical definitions.  Additional parameters are documented below.
2368		* It is assumed that the comparator and size fields of the TreeMap are
2369		* already set prior to calling this method.  (It ignores both fields.)
#	Line 2256 | Line 2371 | public class TreeMap<K,V>
2371		* @param level the current level of tree. Initial call should be 0.
2372		* @param lo the first element index of this subtree. Initial should be 0.
2373		* @param hi the last element index of this subtree.  Initial should be
2374	<	*              size-1.
2374	>	*        size-1.
2375		* @param redLevel the level at which nodes should be red.
2376		*        Must be equal to computeRedLevel for tree of this size.
2377		*/
#	Line 2340 | Line 2455 | public class TreeMap<K,V>
2455		level++;
2456		return level;
2457		}
2343	–
2458		}

Diff Legend

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