[ViewVC] Diff of: jsr166/jsr166/src/main/java/util/TreeMap.java

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.11 by jsr166, Mon May 2 16:35:52 2005 UTC vs.
Revision 1.46 by jsr166, Sun May 18 23:59:57 2008 UTC

#	Line 1 \| Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation. Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
27
10	–
28		/**
29	<	* Red-Black tree based implementation of the <tt>NavigableMap</tt> interface.
30	<	* This class guarantees that the map will be in ascending key order, sorted
31	<	* according to the <i>natural order</i> for the keys' class (see
32	<	* <tt>Comparable</tt>), or by the comparator provided at creation time,
16	<	* depending on which constructor is used.<p>
29	>	* A Red-Black tree based {@link NavigableMap} implementation.
30	>	* The map is sorted according to the {@linkplain Comparable natural
31	>	* ordering} of its keys, or by a {@link Comparator} provided at map
32	>	* creation time, depending on which constructor is used.
33		*
34	<	* This implementation provides guaranteed log(n) time cost for the
34	>	* <p>This implementation provides guaranteed log(n) time cost for the
35		* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
36		* operations. Algorithms are adaptations of those in Cormen, Leiserson, and
37	<	* Rivest's <I>Introduction to Algorithms</I>.<p>
37	>	* Rivest's <I>Introduction to Algorithms</I>.
38		*
39	<	* Note that the ordering maintained by a sorted map (whether or not an
39	>	* <p>Note that the ordering maintained by a sorted map (whether or not an
40		* explicit comparator is provided) must be <i>consistent with equals</i> if
41		* this sorted map is to correctly implement the <tt>Map</tt> interface. (See
42		* <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
#	Line 30 \| Line 46 \| package java.util;
46		* method, so two keys that are deemed equal by this method are, from the
47		* standpoint of the sorted map, equal. The behavior of a sorted map
48		* <i>is</i> well-defined even if its ordering is inconsistent with equals; it
49	<	* just fails to obey the general contract of the <tt>Map</tt> interface.<p>
49	>	* just fails to obey the general contract of the <tt>Map</tt> interface.
50		*
51	<	* <b>Note that this implementation is not synchronized.</b> If multiple
52	<	* threads access a map concurrently, and at least one of the threads modifies
53	<	* the map structurally, it <i>must</i> be synchronized externally. (A
54	<	* structural modification is any operation that adds or deletes one or more
55	<	* mappings; merely changing the value associated with an existing key is not
56	<	* a structural modification.) This is typically accomplished by
57	<	* synchronizing on some object that naturally encapsulates the map. If no
58	<	* such object exists, the map should be "wrapped" using the
59	<	* <tt>Collections.synchronizedMap</tt> method. This is best done at creation
60	<	* time, to prevent accidental unsynchronized access to the map:
61	<	* <pre>
62	<	* Map m = Collections.synchronizedMap(new TreeMap(...));
63	<	* </pre><p>
51	>	* <p><strong>Note that this implementation is not synchronized.</strong>
52	>	* If multiple threads access a map concurrently, and at least one of the
53	>	* threads modifies the map structurally, it <i>must</i> be synchronized
54	>	* externally. (A structural modification is any operation that adds or
55	>	* deletes one or more mappings; merely changing the value associated
56	>	* with an existing key is not a structural modification.) This is
57	>	* typically accomplished by synchronizing on some object that naturally
58	>	* encapsulates the map.
59	>	* If no such object exists, the map should be "wrapped" using the
60	>	* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
61	>	* method. This is best done at creation time, to prevent accidental
62	>	* unsynchronized access to the map: <pre>
63	>	* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
64		*
65	<	* The iterators returned by all of this class's "collection view methods" are
65	>	* <p>The iterators returned by the <tt>iterator</tt> method of the collections
66	>	* returned by all of this class's "collection view methods" are
67		* <i>fail-fast</i>: if the map is structurally modified at any time after the
68		* iterator is created, in any way except through the iterator's own
69	<	* <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
70	<	* <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
69	>	* <tt>remove</tt> method, the iterator will throw a {@link
70	>	* ConcurrentModificationException}. Thus, in the face of concurrent
71		* modification, the iterator fails quickly and cleanly, rather than risking
72	<	* arbitrary, non-deterministic behavior at an undetermined time in the
56	<	* future.
72	>	* arbitrary, non-deterministic behavior at an undetermined time in the future.
73		*
74		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
75		* as it is, generally speaking, impossible to make any hard guarantees in the
#	Line 70 \| Line 86 \| package java.util;
86		* associated map using <tt>put</tt>.)
87		*
88		* <p>This class is a member of the
89	<	* <a href="{@docRoot}/../guide/collections/index.html">
89	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
90		* Java Collections Framework</a>.
91		*
92	+	* @param <K> the type of keys maintained by this map
93	+	* @param <V> the type of mapped values
94	+	*
95		* @author Josh Bloch and Doug Lea
77	–	* @version %I%, %G%
96		* @see Map
97		* @see HashMap
98		* @see Hashtable
99		* @see Comparable
100		* @see Comparator
101		* @see Collection
84	–	* @see Collections#synchronizedMap(Map)
102		* @since 1.2
103		*/
104
#	Line 90 \| Line 107 \| public class TreeMap<K,V>
107		implements NavigableMap<K,V>, Cloneable, java.io.Serializable
108		{
109		/**
110	<	* The Comparator used to maintain order in this TreeMap, or
111	<	* null if this TreeMap uses its elements natural ordering.
110	>	* The comparator used to maintain order in this tree map, or
111	>	* null if it uses the natural ordering of its keys.
112		*
113		* @serial
114		*/
115	<	private Comparator<? super K> comparator = null;
115	>	private final Comparator<? super K> comparator;
116
117		private transient Entry<K,V> root = null;
118
#	Line 109 \| Line 126 \| public class TreeMap<K,V>
126		*/
127		private transient int modCount = 0;
128
112	–	private void incrementSize() { modCount++; size++; }
113	–	private void decrementSize() { modCount++; size--; }
114	–
129		/**
130	<	* Constructs a new, empty map, sorted according to the keys' natural
131	<	* order. All keys inserted into the map must implement the
132	<	* <tt>Comparable</tt> interface. Furthermore, all such keys must be
133	<	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
134	<	* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
135	<	* map. If the user attempts to put a key into the map that violates this
136	<	* constraint (for example, the user attempts to put a string key into a
137	<	* map whose keys are integers), the <tt>put(Object key, Object
138	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
139	<	*
126	<	* @see Comparable
130	>	* Constructs a new, empty tree map, using the natural ordering of its
131	>	* keys. All keys inserted into the map must implement the {@link
132	>	* Comparable} interface. Furthermore, all such keys must be
133	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
134	>	* 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 (for example, the user attempts to
137	>	* put a string key into a map whose keys are integers), the
138	>	* <tt>put(Object key, Object value)</tt> call will throw a
139	>	* <tt>ClassCastException</tt>.
140		*/
141		public TreeMap() {
142	+	comparator = null;
143		}
144
145		/**
146	<	* Constructs a new, empty map, sorted according to the given comparator.
147	<	* All keys inserted into the map must be <i>mutually comparable</i> by
148	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
149	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
150	<	* <tt>k2</tt> in the map. If the user attempts to put a key into the
151	<	* map that violates this constraint, the <tt>put(Object key, Object
152	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
146	>	* Constructs a new, empty tree map, ordered according to the given
147	>	* comparator. All keys inserted into the map must be <i>mutually
148	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
149	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
150	>	* <tt>k1</tt> and <tt>k2</tt> in the map. If the user attempts to put
151	>	* a key into the map that violates this constraint, the <tt>put(Object
152	>	* key, Object value)</tt> call will throw a
153	>	* <tt>ClassCastException</tt>.
154		*
155	<	* @param c the comparator that will be used to sort this map. A
156	<	* <tt>null</tt> value indicates that the keys' <i>natural
157	<	* ordering</i> should be used.
158	<	*/
159	<	public TreeMap(Comparator<? super K> c) {
160	<	this.comparator = c;
155	>	* @param comparator the comparator that will be used to order this map.
156	>	* If <tt>null</tt>, the {@linkplain Comparable natural
157	>	* ordering} of the keys will be used.
158	>	*/
159	>	public TreeMap(Comparator<? super K> comparator) {
160	>	this.comparator = comparator;
161		}
162
163		/**
164	<	* Constructs a new map containing the same mappings as the given map,
165	<	* sorted according to the keys' <i>natural order</i>. All keys inserted
166	<	* into the new map must implement the <tt>Comparable</tt> interface.
167	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
168	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
169	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map. This method
170	<	* runs in n*log(n) time.
171	<	*
172	<	* @param m the map whose mappings are to be placed in this map.
173	<	* @throws ClassCastException the keys in t are not Comparable, or
174	<	* are not mutually comparable.
175	<	* @throws NullPointerException if the specified map is null.
164	>	* Constructs a new tree map containing the same mappings as the given
165	>	* map, ordered according to the <i>natural ordering</i> of its keys.
166	>	* All keys inserted into the new map must implement the {@link
167	>	* Comparable} interface. Furthermore, all such keys must be
168	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
169	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
170	>	* <tt>k2</tt> in the map. This method runs in n*log(n) time.
171	>	*
172	>	* @param m the map whose mappings are to be placed in this map
173	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
174	>	* or are not mutually comparable
175	>	* @throws NullPointerException if the specified map is null
176		*/
177		public TreeMap(Map<? extends K, ? extends V> m) {
178	+	comparator = null;
179		putAll(m);
180		}
181
182		/**
183	<	* Constructs a new map containing the same mappings as the given
184	<	* <tt>SortedMap</tt>, sorted according to the same ordering. This method
185	<	* runs in linear time.
183	>	* Constructs a new tree map containing the same mappings and
184	>	* using the same ordering as the specified sorted map. This
185	>	* method runs in linear time.
186		*
187		* @param m the sorted map whose mappings are to be placed in this map,
188	<	* and whose comparator is to be used to sort this map.
189	<	* @throws NullPointerException if the specified sorted map is null.
188	>	* and whose comparator is to be used to sort this map
189	>	* @throws NullPointerException if the specified map is null
190		*/
191		public TreeMap(SortedMap<K, ? extends V> m) {
192		comparator = m.comparator();
#	Line 187 \| Line 203 \| public class TreeMap<K,V>
203		/**
204		* Returns the number of key-value mappings in this map.
205		*
206	<	* @return the number of key-value mappings in this map.
206	>	* @return the number of key-value mappings in this map
207		*/
208		public int size() {
209		return size;
#	Line 197 \| Line 213 \| public class TreeMap<K,V>
213		* Returns <tt>true</tt> if this map contains a mapping for the specified
214		* key.
215		*
216	<	* @param key key whose presence in this map is to be tested.
201	<	*
216	>	* @param key key whose presence in this map is to be tested
217		* @return <tt>true</tt> if this map contains a mapping for the
218	<	* specified key.
219	<	* @throws ClassCastException if the key cannot be compared with the keys
220	<	* currently in the map.
221	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
222	<	* natural ordering, or its comparator does not tolerate
223	<	* <tt>null</tt> keys.
218	>	* specified key
219	>	* @throws ClassCastException if the specified key cannot be compared
220	>	* with the keys currently in the map
221	>	* @throws NullPointerException if the specified key is null
222	>	* and this map uses natural ordering, or its comparator
223	>	* does not permit null keys
224		*/
225		public boolean containsKey(Object key) {
226		return getEntry(key) != null;
#	Line 216 \| Line 231 \| public class TreeMap<K,V>
231		* specified value. More formally, returns <tt>true</tt> if and only if
232		* this map contains at least one mapping to a value <tt>v</tt> such
233		* that <tt>(value==null ? v==null : value.equals(v))</tt>. This
234	<	* operation will probably require time linear in the Map size for most
235	<	* implementations of Map.
234	>	* operation will probably require time linear in the map size for
235	>	* most implementations.
236		*
237	<	* @param value value whose presence in this Map is to be tested.
238	<	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
239	<	* <tt>false</tt> otherwise.
237	>	* @param value value whose presence in this map is to be tested
238	>	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
239	>	* <tt>false</tt> otherwise
240		* @since 1.2
241		*/
242		public boolean containsValue(Object value) {
243	<	return (root==null ? false :
244	<	(value==null ? valueSearchNull(root)
245	<	: valueSearchNonNull(root, value)));
246	<	}
232	<
233	<	private boolean valueSearchNull(Entry n) {
234	<	if (n.value == null)
235	<	return true;
236	<
237	<	// Check left and right subtrees for value
238	<	return (n.left != null && valueSearchNull(n.left)) \|\|
239	<	(n.right != null && valueSearchNull(n.right));
240	<	}
241	<
242	<	private boolean valueSearchNonNull(Entry n, Object value) {
243	<	// Check this node for the value
244	<	if (value.equals(n.value))
245	<	return true;
246	<
247	<	// Check left and right subtrees for value
248	<	return (n.left != null && valueSearchNonNull(n.left, value)) \|\|
249	<	(n.right != null && valueSearchNonNull(n.right, value));
243	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
244	>	if (valEquals(value, e.value))
245	>	return true;
246	>	return false;
247		}
248
249		/**
250	<	* Returns the value to which this map maps the specified key. Returns
251	<	* <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.
250	>	* Returns the value to which the specified key is mapped,
251	>	* or {@code null} if this map contains no mapping for the key.
252		*
253	<	* @param key key whose associated value is to be returned.
254	<	* @return the value to which this map maps the specified key, or
255	<	* <tt>null</tt> if the map contains no mapping for the key.
256	<	* @throws ClassCastException if key cannot be compared with the keys
257	<	* currently in the map.
258	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
259	<	* natural ordering, or its comparator does not tolerate
260	<	* <tt>null</tt> keys.
261	<	*
262	<	* @see #containsKey(Object)
253	>	* <p>More formally, if this map contains a mapping from a key
254	>	* {@code k} to a value {@code v} such that {@code key} compares
255	>	* equal to {@code k} according to the map's ordering, then this
256	>	* method returns {@code v}; otherwise it returns {@code null}.
257	>	* (There can be at most one such mapping.)
258	>	*
259	>	* <p>A return value of {@code null} does not <i>necessarily</i>
260	>	* indicate that the map contains no mapping for the key; it's also
261	>	* possible that the map explicitly maps the key to {@code null}.
262	>	* The {@link #containsKey containsKey} operation may be used to
263	>	* distinguish these two cases.
264	>	*
265	>	* @throws ClassCastException if the specified key cannot be compared
266	>	* with the keys currently in the map
267	>	* @throws NullPointerException if the specified key is null
268	>	* and this map uses natural ordering, or its comparator
269	>	* does not permit null keys
270		*/
271		public V get(Object key) {
272		Entry<K,V> p = getEntry(key);
273		return (p==null ? null : p.value);
274		}
275
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	–	*/
276		public Comparator<? super K> comparator() {
277		return comparator;
278		}
279
280		/**
281	<	* 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.
281	>	* @throws NoSuchElementException {@inheritDoc}
282		*/
283		public K firstKey() {
284		return key(getFirstEntry());
285		}
286
287		/**
288	<	* 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.
288	>	* @throws NoSuchElementException {@inheritDoc}
289		*/
290		public K lastKey() {
291		return key(getLastEntry());
292		}
293
294		/**
295	<	* Copies all of the mappings from the specified map to this map. These
296	<	* mappings replace any mappings that this map had for any of the keys
297	<	* currently in the specified map.
298	<	*
299	<	* @param map mappings to be stored in this map.
300	<	* @throws ClassCastException class of a key or value in the specified
301	<	* map prevents it from being stored in this map.
302	<	*
303	<	* @throws NullPointerException if the given map is <tt>null</tt> or
304	<	* this map does not permit <tt>null</tt> keys and a
318	<	* key in the specified map is <tt>null</tt>.
295	>	* Copies all of the mappings from the specified map to this map.
296	>	* These mappings replace any mappings that this map had for any
297	>	* of the keys currently in the specified map.
298	>	*
299	>	* @param map mappings to be stored in this map
300	>	* @throws ClassCastException if the class of a key or value in
301	>	* the specified map prevents it from being stored in this map
302	>	* @throws NullPointerException if the specified map is null or
303	>	* the specified map contains a null key and this map does not
304	>	* permit null keys
305		*/
306		public void putAll(Map<? extends K, ? extends V> map) {
307		int mapSize = map.size();
308		if (size==0 && mapSize!=0 && map instanceof SortedMap) {
309		Comparator c = ((SortedMap)map).comparator();
310		if (c == comparator \|\| (c != null && c.equals(comparator))) {
311	<	++modCount;
312	<	try {
313	<	buildFromSorted(mapSize, map.entrySet().iterator(),
314	<	null, null);
315	<	} catch (java.io.IOException cannotHappen) {
316	<	} catch (ClassNotFoundException cannotHappen) {
317	<	}
318	<	return;
311	>	++modCount;
312	>	try {
313	>	buildFromSorted(mapSize, map.entrySet().iterator(),
314	>	null, null);
315	>	} catch (java.io.IOException cannotHappen) {
316	>	} catch (ClassNotFoundException cannotHappen) {
317	>	}
318	>	return;
319		}
320		}
321		super.putAll(map);
#	Line 340 \| Line 326 \| public class TreeMap<K,V>
326		* does not contain an entry for the key.
327		*
328		* @return this map's entry for the given key, or <tt>null</tt> if the map
329	<	* does not contain an entry for the key.
330	<	* @throws ClassCastException if the key cannot be compared with the keys
331	<	* currently in the map.
332	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
333	<	* natural order, or its comparator does not tolerate *
334	<	* <tt>null</tt> keys.
329	>	* does not contain an entry for the key
330	>	* @throws ClassCastException if the specified key cannot be compared
331	>	* with the keys currently in the map
332	>	* @throws NullPointerException if the specified key is null
333	>	* and this map uses natural ordering, or its comparator
334	>	* does not permit null keys
335		*/
336	<	private Entry<K,V> getEntry(Object key) {
336	>	final Entry<K,V> getEntry(Object key) {
337		// Offload comparator-based version for sake of performance
338		if (comparator != null)
339		return getEntryUsingComparator(key);
340	<	Comparable<K> k = (Comparable<K>) key;
340	>	if (key == null)
341	>	throw new NullPointerException();
342	>	Comparable<? super K> k = (Comparable<? super K>) key;
343		Entry<K,V> p = root;
344		while (p != null) {
345		int cmp = k.compareTo(p.key);
#	Line 371 \| Line 359 \| public class TreeMap<K,V>
359		* that are less dependent on comparator performance, but is
360		* worthwhile here.)
361		*/
362	<	private Entry<K,V> getEntryUsingComparator(Object key) {
363	<	K k = (K) key;
362	>	final Entry<K,V> getEntryUsingComparator(Object key) {
363	>	K k = (K) key;
364		Comparator<? super K> cpr = comparator;
365	<	Entry<K,V> p = root;
366	<	while (p != null) {
367	<	int cmp = cpr.compare(k, p.key);
368	<	if (cmp < 0)
369	<	p = p.left;
370	<	else if (cmp > 0)
371	<	p = p.right;
372	<	else
373	<	return p;
365	>	if (cpr != null) {
366	>	Entry<K,V> p = root;
367	>	while (p != null) {
368	>	int cmp = cpr.compare(k, p.key);
369	>	if (cmp < 0)
370	>	p = p.left;
371	>	else if (cmp > 0)
372	>	p = p.right;
373	>	else
374	>	return p;
375	>	}
376		}
377		return null;
378		}
#	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)
399	<	return null;
400	<
401	<	while (true) {
388	>	while (p != null) {
389		int cmp = compare(key, p.key);
390		if (cmp < 0) {
391		if (p.left != null)
#	Line 420 \| Line 407 \| public class TreeMap<K,V>
407		} else
408		return p;
409		}
410	+	return null;
411		}
412
413		/**
#	Line 427 \| Line 415 \| public class TreeMap<K,V>
415		* exists, returns the entry for the greatest key less than the specified
416		* key; if no such entry exists, returns <tt>null</tt>.
417		*/
418	<	private Entry<K,V> getFloorEntry(K key) {
418	>	final Entry<K,V> getFloorEntry(K key) {
419		Entry<K,V> p = root;
420	<	if (p==null)
433	<	return null;
434	<
435	<	while (true) {
420	>	while (p != null) {
421		int cmp = compare(key, p.key);
422		if (cmp > 0) {
423		if (p.right != null)
#	Line 455 \| Line 440 \| public class TreeMap<K,V>
440		return p;
441
442		}
443	+	return null;
444		}
445
446		/**
#	Line 463 \| Line 449 \| public class TreeMap<K,V>
449		* key greater than the specified key; if no such entry exists
450		* returns <tt>null</tt>.
451		*/
452	<	private Entry<K,V> getHigherEntry(K key) {
452	>	final Entry<K,V> getHigherEntry(K key) {
453		Entry<K,V> p = root;
454	<	if (p==null)
469	<	return null;
470	<
471	<	while (true) {
454	>	while (p != null) {
455		int cmp = compare(key, p.key);
456		if (cmp < 0) {
457		if (p.left != null)
#	Line 489 \| Line 472 \| public class TreeMap<K,V>
472		}
473		}
474		}
475	+	return null;
476		}
477
478		/**
#	Line 496 \| Line 480 \| public class TreeMap<K,V>
480		* no such entry exists (i.e., the least key in the Tree is greater than
481		* the specified key), returns <tt>null</tt>.
482		*/
483	<	private Entry<K,V> getLowerEntry(K key) {
483	>	final Entry<K,V> getLowerEntry(K key) {
484		Entry<K,V> p = root;
485	<	if (p==null)
502	<	return null;
503	<
504	<	while (true) {
485	>	while (p != null) {
486		int cmp = compare(key, p.key);
487		if (cmp > 0) {
488		if (p.right != null)
#	Line 522 \| Line 503 \| public class TreeMap<K,V>
503		}
504		}
505		}
506	<	}
526	<
527	<	/**
528	<	* Returns the key corresponding to the specified Entry. Throw
529	<	* NoSuchElementException if the Entry is <tt>null</tt>.
530	<	*/
531	<	private static <K> K key(Entry<K,?> e) {
532	<	if (e==null)
533	<	throw new NoSuchElementException();
534	<	return e.key;
506	>	return null;
507		}
508
509		/**
510		* Associates the specified value with the specified key in this map.
511	<	* If the map previously contained a mapping for this key, the old
511	>	* If the map previously contained a mapping for the key, the old
512		* value is replaced.
513		*
514	<	* @param key key with which the specified value is to be associated.
515	<	* @param value value to be associated with the specified key.
514	>	* @param key key with which the specified value is to be associated
515	>	* @param value value to be associated with the specified key
516		*
517	<	* @return the previous value associated with specified key, or <tt>null</tt>
518	<	* if there was no mapping for key. A <tt>null</tt> return can
519	<	* also indicate that the map previously associated <tt>null</tt>
520	<	* with the specified key.
521	<	* @throws ClassCastException if key cannot be compared with the keys
522	<	* currently in the map.
523	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
524	<	* natural order, or its comparator does not tolerate
525	<	* <tt>null</tt> keys.
517	>	* @return the previous value associated with <tt>key</tt>, or
518	>	* <tt>null</tt> if there was no mapping for <tt>key</tt>.
519	>	* (A <tt>null</tt> return can also indicate that the map
520	>	* previously associated <tt>null</tt> with <tt>key</tt>.)
521	>	* @throws ClassCastException if the specified key cannot be compared
522	>	* with the keys currently in the map
523	>	* @throws NullPointerException if the specified key is null
524	>	* and this map uses natural ordering, or its comparator
525	>	* does not permit null keys
526		*/
527		public V put(K key, V value) {
528		Entry<K,V> t = root;
557	–
529		if (t == null) {
530	<	incrementSize();
530	>	// TBD:
531	>	// 5045147: (coll) Adding null to an empty TreeSet should
532	>	// throw NullPointerException
533	>	//
534	>	// compare(key, key); // type check
535		root = new Entry<K,V>(key, value, null);
536	+	size = 1;
537	+	modCount++;
538		return null;
539		}
540	<
541	<	while (true) {
542	<	int cmp = compare(key, t.key);
543	<	if (cmp == 0) {
544	<	return t.setValue(value);
545	<	} else if (cmp < 0) {
546	<	if (t.left != null) {
540	>	int cmp;
541	>	Entry<K,V> parent;
542	>	// split comparator and comparable paths
543	>	Comparator<? super K> cpr = comparator;
544	>	if (cpr != null) {
545	>	do {
546	>	parent = t;
547	>	cmp = cpr.compare(key, t.key);
548	>	if (cmp < 0)
549		t = t.left;
550	<	} else {
572	<	incrementSize();
573	<	t.left = new Entry<K,V>(key, value, t);
574	<	fixAfterInsertion(t.left);
575	<	return null;
576	<	}
577	<	} else { // cmp > 0
578	<	if (t.right != null) {
550	>	else if (cmp > 0)
551		t = t.right;
552	<	} else {
553	<	incrementSize();
554	<	t.right = new Entry<K,V>(key, value, t);
583	<	fixAfterInsertion(t.right);
584	<	return null;
585	<	}
586	<	}
552	>	else
553	>	return t.setValue(value);
554	>	} while (t != null);
555		}
556	+	else {
557	+	if (key == null)
558	+	throw new NullPointerException();
559	+	Comparable<? super K> k = (Comparable<? super K>) key;
560	+	do {
561	+	parent = t;
562	+	cmp = k.compareTo(t.key);
563	+	if (cmp < 0)
564	+	t = t.left;
565	+	else if (cmp > 0)
566	+	t = t.right;
567	+	else
568	+	return t.setValue(value);
569	+	} while (t != null);
570	+	}
571	+	Entry<K,V> e = new Entry<K,V>(key, value, parent);
572	+	if (cmp < 0)
573	+	parent.left = e;
574	+	else
575	+	parent.right = e;
576	+	fixAfterInsertion(e);
577	+	size++;
578	+	modCount++;
579	+	return null;
580		}
581
582		/**
583		* Removes the mapping for this key from this TreeMap if present.
584		*
585		* @param key key for which mapping should be removed
586	<	* @return the previous value associated with specified key, or <tt>null</tt>
587	<	* if there was no mapping for key. A <tt>null</tt> return can
588	<	* also indicate that the map previously associated
589	<	* <tt>null</tt> with the specified key.
590	<	*
591	<	* @throws ClassCastException if key cannot be compared with the keys
592	<	* currently in the map.
593	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
594	<	* natural order, or its comparator does not tolerate
603	<	* <tt>null</tt> keys.
586	>	* @return the previous value associated with <tt>key</tt>, or
587	>	* <tt>null</tt> if there was no mapping for <tt>key</tt>.
588	>	* (A <tt>null</tt> return can also indicate that the map
589	>	* previously associated <tt>null</tt> with <tt>key</tt>.)
590	>	* @throws ClassCastException if the specified key cannot be compared
591	>	* with the keys currently in the map
592	>	* @throws NullPointerException if the specified key is null
593	>	* and this map uses natural ordering, or its comparator
594	>	* does not permit null keys
595		*/
596		public V remove(Object key) {
597		Entry<K,V> p = getEntry(key);
#	Line 613 \| Line 604 \| public class TreeMap<K,V>
604		}
605
606		/**
607	<	* Removes all mappings from this TreeMap.
607	>	* Removes all of the mappings from this map.
608	>	* The map will be empty after this call returns.
609		*/
610		public void clear() {
611		modCount++;
#	Line 625 \| Line 617 \| public class TreeMap<K,V>
617		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
618		* values themselves are not cloned.)
619		*
620	<	* @return a shallow copy of this Map.
620	>	* @return a shallow copy of this map
621		*/
622		public Object clone() {
623		TreeMap<K,V> clone = null;
#	Line 640 \| Line 632 \| public class TreeMap<K,V>
632		clone.size = 0;
633		clone.modCount = 0;
634		clone.entrySet = null;
635	<	clone.descendingEntrySet = null;
636	<	clone.descendingKeySet = null;
635	>	clone.navigableKeySet = null;
636	>	clone.descendingMap = null;
637
638		// Initialize clone with our mappings
639		try {
#	Line 656 \| Line 648 \| public class TreeMap<K,V>
648		// NavigableMap API methods
649
650		/**
651	<	* 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.
651	>	* @since 1.6
652		*/
653		public Map.Entry<K,V> firstEntry() {
654	<	Entry<K,V> e = getFirstEntry();
667	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
654	>	return exportEntry(getFirstEntry());
655		}
656
657		/**
658	<	* Returns a key-value mapping associated with the greatest
672	<	* key in this map, or <tt>null</tt> if the map is empty.
673	<	*
674	<	* @return an Entry with greatest key, or <tt>null</tt>
675	<	* if the map is empty.
658	>	* @since 1.6
659		*/
660		public Map.Entry<K,V> lastEntry() {
661	<	Entry<K,V> e = getLastEntry();
679	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
661	>	return exportEntry(getLastEntry());
662		}
663
664		/**
665	<	* Removes and returns a key-value mapping associated with
684	<	* the least key in this map, or <tt>null</tt> if the map is empty.
685	<	*
686	<	* @return the removed first entry of this map, or <tt>null</tt>
687	<	* if the map is empty.
665	>	* @since 1.6
666		*/
667		public Map.Entry<K,V> pollFirstEntry() {
668		Entry<K,V> p = getFirstEntry();
669	<	if (p == null)
670	<	return null;
671	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
694	<	deleteEntry(p);
669	>	Map.Entry<K,V> result = exportEntry(p);
670	>	if (p != null)
671	>	deleteEntry(p);
672		return result;
673		}
674
675		/**
676	<	* Removes and returns a key-value mapping associated with
700	<	* the greatest key in this map, or <tt>null</tt> if the map is empty.
701	<	*
702	<	* @return the removed last entry of this map, or <tt>null</tt>
703	<	* if the map is empty.
676	>	* @since 1.6
677		*/
678		public Map.Entry<K,V> pollLastEntry() {
679		Entry<K,V> p = getLastEntry();
680	<	if (p == null)
681	<	return null;
682	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
710	<	deleteEntry(p);
680	>	Map.Entry<K,V> result = exportEntry(p);
681	>	if (p != null)
682	>	deleteEntry(p);
683		return result;
684		}
685
686		/**
687	<	* Returns a key-value mapping associated with the least key
688	<	* greater than or equal to the given key, or <tt>null</tt> if
689	<	* there is no such entry.
690	<	*
691	<	* @param key the key.
720	<	* @return an Entry associated with ceiling of given key, or
721	<	* <tt>null</tt> if there is no such Entry.
722	<	* @throws ClassCastException if key cannot be compared with the
723	<	* keys currently in the map.
724	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
725	<	* natural order, or its comparator does not tolerate
726	<	* <tt>null</tt> keys.
687	>	* @throws ClassCastException {@inheritDoc}
688	>	* @throws NullPointerException if the specified key is null
689	>	* and this map uses natural ordering, or its comparator
690	>	* does not permit null keys
691	>	* @since 1.6
692		*/
693	<	public Map.Entry<K,V> ceilingEntry(K key) {
694	<	Entry<K,V> e = getCeilingEntry(key);
730	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
693	>	public Map.Entry<K,V> lowerEntry(K key) {
694	>	return exportEntry(getLowerEntry(key));
695		}
696
733	–
697		/**
698	<	* Returns least key greater than or equal to the given key, or
699	<	* <tt>null</tt> if there is no such key.
700	<	*
701	<	* @param key the key.
702	<	* @return the ceiling key, or <tt>null</tt>
740	<	* if there is no such key.
741	<	* @throws ClassCastException if key cannot be compared with the keys
742	<	* currently in the map.
743	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
744	<	* natural order, or its comparator does not tolerate
745	<	* <tt>null</tt> keys.
698	>	* @throws ClassCastException {@inheritDoc}
699	>	* @throws NullPointerException if the specified key is null
700	>	* and this map uses natural ordering, or its comparator
701	>	* does not permit null keys
702	>	* @since 1.6
703		*/
704	<	public K ceilingKey(K key) {
705	<	Entry<K,V> e = getCeilingEntry(key);
749	<	return (e == null)? null : e.key;
704	>	public K lowerKey(K key) {
705	>	return keyOrNull(getLowerEntry(key));
706		}
707
752	–
753	–
708		/**
709	<	* Returns a key-value mapping associated with the greatest key
710	<	* less than or equal to the given key, or <tt>null</tt> if there
711	<	* is no such entry.
712	<	*
713	<	* @param key the key.
760	<	* @return an Entry associated with floor of given key, or <tt>null</tt>
761	<	* if there is no such Entry.
762	<	* @throws ClassCastException if key cannot be compared with the keys
763	<	* currently in the map.
764	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
765	<	* natural order, or its comparator does not tolerate
766	<	* <tt>null</tt> keys.
709	>	* @throws ClassCastException {@inheritDoc}
710	>	* @throws NullPointerException if the specified key is null
711	>	* and this map uses natural ordering, or its comparator
712	>	* does not permit null keys
713	>	* @since 1.6
714		*/
715		public Map.Entry<K,V> floorEntry(K key) {
716	<	Entry<K,V> e = getFloorEntry(key);
770	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
716	>	return exportEntry(getFloorEntry(key));
717		}
718
719		/**
720	<	* Returns the greatest key
721	<	* less than or equal to the given key, or <tt>null</tt> if there
722	<	* is no such key.
723	<	*
724	<	* @param key the key.
779	<	* @return the floor of given key, or <tt>null</tt> if there is no
780	<	* such key.
781	<	* @throws ClassCastException if key cannot be compared with the keys
782	<	* currently in the map.
783	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
784	<	* natural order, or its comparator does not tolerate
785	<	* <tt>null</tt> keys.
720	>	* @throws ClassCastException {@inheritDoc}
721	>	* @throws NullPointerException if the specified key is null
722	>	* and this map uses natural ordering, or its comparator
723	>	* does not permit null keys
724	>	* @since 1.6
725		*/
726		public K floorKey(K key) {
727	<	Entry<K,V> e = getFloorEntry(key);
789	<	return (e == null)? null : e.key;
727	>	return keyOrNull(getFloorEntry(key));
728		}
729
730		/**
731	<	* Returns a key-value mapping associated with the least key
732	<	* strictly greater than the given key, or <tt>null</tt> if there
733	<	* is no such entry.
734	<	*
735	<	* @param key the key.
798	<	* @return an Entry with least key greater than the given key, or
799	<	* <tt>null</tt> if there is no such Entry.
800	<	* @throws ClassCastException if key cannot be compared with the keys
801	<	* currently in the map.
802	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
803	<	* natural order, or its comparator does not tolerate
804	<	* <tt>null</tt> keys.
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 Map.Entry<K,V> higherEntry(K key) {
738	<	Entry<K,V> e = getHigherEntry(key);
808	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
737	>	public Map.Entry<K,V> ceilingEntry(K key) {
738	>	return exportEntry(getCeilingEntry(key));
739		}
740
741		/**
742	<	* Returns the least key strictly greater than the given key, or
743	<	* <tt>null</tt> if there is no such key.
744	<	*
745	<	* @param key the key.
746	<	* @return the least key greater than the given key, or
817	<	* <tt>null</tt> if there is no such key.
818	<	* @throws ClassCastException if key cannot be compared with the keys
819	<	* currently in the map.
820	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
821	<	* natural order, or its comparator does not tolerate
822	<	* <tt>null</tt> keys.
742	>	* @throws ClassCastException {@inheritDoc}
743	>	* @throws NullPointerException if the specified key is null
744	>	* and this map uses natural ordering, or its comparator
745	>	* does not permit null keys
746	>	* @since 1.6
747		*/
748	<	public K higherKey(K key) {
749	<	Entry<K,V> e = getHigherEntry(key);
826	<	return (e == null)? null : e.key;
748	>	public K ceilingKey(K key) {
749	>	return keyOrNull(getCeilingEntry(key));
750		}
751
752		/**
753	<	* Returns a key-value mapping associated with the greatest
754	<	* key strictly less than the given key, or <tt>null</tt> if there is no
755	<	* such entry.
756	<	*
757	<	* @param key the key.
835	<	* @return an Entry with greatest key less than the given
836	<	* key, or <tt>null</tt> if there is no such Entry.
837	<	* @throws ClassCastException if key cannot be compared with the keys
838	<	* currently in the map.
839	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
840	<	* natural order, or its comparator does not tolerate
841	<	* <tt>null</tt> keys.
753	>	* @throws ClassCastException {@inheritDoc}
754	>	* @throws NullPointerException if the specified key is null
755	>	* and this map uses natural ordering, or its comparator
756	>	* does not permit null keys
757	>	* @since 1.6
758		*/
759	<	public Map.Entry<K,V> lowerEntry(K key) {
760	<	Entry<K,V> e = getLowerEntry(key);
845	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
759	>	public Map.Entry<K,V> higherEntry(K key) {
760	>	return exportEntry(getHigherEntry(key));
761		}
762
763		/**
764	<	* Returns the greatest key strictly less than the given key, or
765	<	* <tt>null</tt> if there is no such key.
766	<	*
767	<	* @param key the key.
768	<	* @return the greatest key less than the given
854	<	* key, or <tt>null</tt> if there is no such key.
855	<	* @throws ClassCastException if key cannot be compared with the keys
856	<	* currently in the map.
857	<	* @throws NullPointerException if key is <tt>null</tt> and this map uses
858	<	* natural order, or its comparator does not tolerate
859	<	* <tt>null</tt> keys.
764	>	* @throws ClassCastException {@inheritDoc}
765	>	* @throws NullPointerException if the specified key is null
766	>	* and this map uses natural ordering, or its comparator
767	>	* does not permit null keys
768	>	* @since 1.6
769		*/
770	<	public K lowerKey(K key) {
771	<	Entry<K,V> e = getLowerEntry(key);
863	<	return (e == null)? null : e.key;
770	>	public K higherKey(K key) {
771	>	return keyOrNull(getHigherEntry(key));
772		}
773
774		// Views
#	Line 870 \| Line 778 \| public class TreeMap<K,V>
778		* the first time this view is requested. Views are stateless, so
779		* there's no reason to create more than one.
780		*/
781	<	private transient Set<Map.Entry<K,V>> entrySet = null;
782	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
783	<	private transient Set<K> descendingKeySet = null;
781	>	private transient EntrySet entrySet = null;
782	>	private transient KeySet<K> navigableKeySet = null;
783	>	private transient NavigableMap<K,V> descendingMap = null;
784	>
785	>	/**
786	>	* Returns a {@link Set} view of the keys contained in this map.
787	>	* The set's iterator returns the keys in ascending order.
788	>	* The set is backed by the map, so changes to the map are
789	>	* reflected in the set, and vice-versa. If the map is modified
790	>	* while an iteration over the set is in progress (except through
791	>	* the iterator's own <tt>remove</tt> operation), the results of
792	>	* the iteration are undefined. The set supports element removal,
793	>	* which removes the corresponding mapping from the map, via the
794	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
795	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
796	>	* operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
797	>	* operations.
798	>	*/
799	>	public Set<K> keySet() {
800	>	return navigableKeySet();
801	>	}
802
803		/**
804	<	* Returns a Set view of the keys contained in this map. The set's
879	<	* iterator will return the keys in ascending order. The set is backed by
880	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
881	<	* the Set, and vice-versa. The Set supports element removal, which
882	<	* removes the corresponding mapping from the map, via the
883	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
884	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
885	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
886	<	*
887	<	* @return a set view of the keys contained in this TreeMap.
804	>	* @since 1.6
805		*/
806	<	public Set<K> keySet() {
807	<	Set<K> ks = keySet;
808	<	return (ks != null) ? ks : (keySet = new KeySet());
806	>	public NavigableSet<K> navigableKeySet() {
807	>	KeySet<K> nks = navigableKeySet;
808	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
809		}
810
811	<	class KeySet extends AbstractSet<K> {
812	<	public Iterator<K> iterator() {
813	<	return new KeyIterator(getFirstEntry());
814	<	}
811	>	/**
812	>	* @since 1.6
813	>	*/
814	>	public NavigableSet<K> descendingKeySet() {
815	>	return descendingMap().navigableKeySet();
816	>	}
817
818	<	public int size() {
819	<	return TreeMap.this.size();
820	<	}
818	>	/**
819	>	* Returns a {@link Collection} view of the values contained in this map.
820	>	* The collection's iterator returns the values in ascending order
821	>	* of the corresponding keys.
822	>	* The collection is backed by the map, so changes to the map are
823	>	* reflected in the collection, and vice-versa. If the map is
824	>	* modified while an iteration over the collection is in progress
825	>	* (except through the iterator's own <tt>remove</tt> operation),
826	>	* the results of the iteration are undefined. The collection
827	>	* supports element removal, which removes the corresponding
828	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
829	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
830	>	* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
831	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
832	>	*/
833	>	public Collection<V> values() {
834	>	Collection<V> vs = values;
835	>	return (vs != null) ? vs : (values = new Values());
836	>	}
837
838	<	public boolean contains(Object o) {
839	<	return containsKey(o);
840	<	}
838	>	/**
839	>	* Returns a {@link Set} view of the mappings contained in this map.
840	>	* The set's iterator returns the entries in ascending key order.
841	>	* The set is backed by the map, so changes to the map are
842	>	* reflected in the set, and vice-versa. If the map is modified
843	>	* while an iteration over the set is in progress (except through
844	>	* the iterator's own <tt>remove</tt> operation, or through the
845	>	* <tt>setValue</tt> operation on a map entry returned by the
846	>	* iterator) the results of the iteration are undefined. The set
847	>	* supports element removal, which removes the corresponding
848	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
849	>	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
850	>	* <tt>clear</tt> operations. It does not support the
851	>	* <tt>add</tt> or <tt>addAll</tt> operations.
852	>	*/
853	>	public Set<Map.Entry<K,V>> entrySet() {
854	>	EntrySet es = entrySet;
855	>	return (es != null) ? es : (entrySet = new EntrySet());
856	>	}
857
858	<	public boolean remove(Object o) {
859	<	int oldSize = size;
860	<	TreeMap.this.remove(o);
861	<	return size != oldSize;
862	<	}
858	>	/**
859	>	* @since 1.6
860	>	*/
861	>	public NavigableMap<K, V> descendingMap() {
862	>	NavigableMap<K, V> km = descendingMap;
863	>	return (km != null) ? km :
864	>	(descendingMap = new DescendingSubMap(this,
865	>	true, null, true,
866	>	true, null, true));
867	>	}
868
869	<	public void clear() {
870	<	TreeMap.this.clear();
871	<	}
869	>	/**
870	>	* @throws ClassCastException {@inheritDoc}
871	>	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
872	>	* null and this map uses natural ordering, or its comparator
873	>	* does not permit null keys
874	>	* @throws IllegalArgumentException {@inheritDoc}
875	>	* @since 1.6
876	>	*/
877	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
878	>	K toKey, boolean toInclusive) {
879	>	return new AscendingSubMap(this,
880	>	false, fromKey, fromInclusive,
881	>	false, toKey, toInclusive);
882		}
883
884		/**
885	<	* Returns a collection view of the values contained in this map. The
886	<	* collection's iterator will return the values in the order that their
887	<	* corresponding keys appear in the tree. The collection is backed by
888	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
889	<	* the collection, and vice-versa. The collection supports element
890	<	* removal, which removes the corresponding mapping from the map through
925	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
926	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
927	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
928	<	*
929	<	* @return a collection view of the values contained in this map.
885	>	* @throws ClassCastException {@inheritDoc}
886	>	* @throws NullPointerException if <tt>toKey</tt> is null
887	>	* and this map uses natural ordering, or its comparator
888	>	* does not permit null keys
889	>	* @throws IllegalArgumentException {@inheritDoc}
890	>	* @since 1.6
891		*/
892	<	public Collection<V> values() {
893	<	Collection<V> vs = values;
894	<	return (vs != null) ? vs : (values = new Values());
892	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
893	>	return new AscendingSubMap(this,
894	>	true, null, true,
895	>	false, toKey, inclusive);
896	>	}
897	>
898	>	/**
899	>	* @throws ClassCastException {@inheritDoc}
900	>	* @throws NullPointerException if <tt>fromKey</tt> is null
901	>	* and this map uses natural ordering, or its comparator
902	>	* does not permit null keys
903	>	* @throws IllegalArgumentException {@inheritDoc}
904	>	* @since 1.6
905	>	*/
906	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
907	>	return new AscendingSubMap(this,
908	>	false, fromKey, inclusive,
909	>	true, null, true);
910		}
911
912	+	/**
913	+	* @throws ClassCastException {@inheritDoc}
914	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
915	+	* null and this map uses natural ordering, or its comparator
916	+	* does not permit null keys
917	+	* @throws IllegalArgumentException {@inheritDoc}
918	+	*/
919	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
920	+	return subMap(fromKey, true, toKey, false);
921	+	}
922	+
923	+	/**
924	+	* @throws ClassCastException {@inheritDoc}
925	+	* @throws NullPointerException if <tt>toKey</tt> is null
926	+	* and this map uses natural ordering, or its comparator
927	+	* does not permit null keys
928	+	* @throws IllegalArgumentException {@inheritDoc}
929	+	*/
930	+	public SortedMap<K,V> headMap(K toKey) {
931	+	return headMap(toKey, false);
932	+	}
933	+
934	+	/**
935	+	* @throws ClassCastException {@inheritDoc}
936	+	* @throws NullPointerException if <tt>fromKey</tt> is null
937	+	* and this map uses natural ordering, or its comparator
938	+	* does not permit null keys
939	+	* @throws IllegalArgumentException {@inheritDoc}
940	+	*/
941	+	public SortedMap<K,V> tailMap(K fromKey) {
942	+	return tailMap(fromKey, true);
943	+	}
944	+
945	+	// View class support
946	+
947		class Values extends AbstractCollection<V> {
948		public Iterator<V> iterator() {
949		return new ValueIterator(getFirstEntry());
#	Line 943 \| Line 954 \| public class TreeMap<K,V>
954		}
955
956		public boolean contains(Object o) {
957	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
947	<	if (valEquals(e.getValue(), o))
948	<	return true;
949	<	return false;
957	>	return TreeMap.this.containsValue(o);
958		}
959
960		public boolean remove(Object o) {
#	Line 964 \| Line 972 \| public class TreeMap<K,V>
972		}
973		}
974
967	–	/**
968	–	* Returns a set view of the mappings contained in this map. The set's
969	–	* iterator returns the mappings in ascending key order. Each element in
970	–	* the returned set is a <tt>Map.Entry</tt>. The set is backed by this
971	–	* map, so changes to this map are reflected in the set, and vice-versa.
972	–	* The set supports element removal, which removes the corresponding
973	–	* mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
974	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
975	–	* <tt>clear</tt> operations. It does not support the <tt>add</tt> or
976	–	* <tt>addAll</tt> operations.
977	–	*
978	–	* @return a set view of the mappings contained in this map.
979	–	* @see Map.Entry
980	–	*/
981	–	public Set<Map.Entry<K,V>> entrySet() {
982	–	Set<Map.Entry<K,V>> es = entrySet;
983	–	return (es != null) ? es : (entrySet = new EntrySet());
984	–	}
985	–
975		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
976		public Iterator<Map.Entry<K,V>> iterator() {
977		return new EntryIterator(getFirstEntry());
#	Line 1019 \| Line 1008 \| public class TreeMap<K,V>
1008		}
1009		}
1010
1011	<	/**
1012	<	* Returns a set view of the mappings contained in this map. The
1013	<	* set's iterator returns the mappings in descending key order.
1014	<	* Each element in the returned set is a <tt>Map.Entry</tt>. The
1015	<	* set is backed by this map, so changes to this map are reflected
1016	<	* in the set, and vice-versa. The set supports element removal,
1017	<	* which removes the corresponding mapping from the TreeMap,
1018	<	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1019	<	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1020	<	* operations. It does not support the <tt>add</tt> or
1032	<	* <tt>addAll</tt> operations.
1033	<	*
1034	<	* @return a set view of the mappings contained in this map, in
1035	<	* descending key order
1036	<	* @see Map.Entry
1037	<	*/
1038	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1039	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
1040	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1011	>	/*
1012	>	* Unlike Values and EntrySet, the KeySet class is static,
1013	>	* delegating to a NavigableMap to allow use by SubMaps, which
1014	>	* outweighs the ugliness of needing type-tests for the following
1015	>	* Iterator methods that are defined appropriately in main versus
1016	>	* submap classes.
1017	>	*/
1018	>
1019	>	Iterator<K> keyIterator() {
1020	>	return new KeyIterator(getFirstEntry());
1021		}
1022
1023	<	class DescendingEntrySet extends EntrySet {
1024	<	public Iterator<Map.Entry<K,V>> iterator() {
1025	<	return new DescendingEntryIterator(getLastEntry());
1023	>	Iterator<K> descendingKeyIterator() {
1024	>	return new DescendingKeyIterator(getFirstEntry());
1025	>	}
1026	>
1027	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1028	>	private final NavigableMap<E, Object> m;
1029	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1030	>
1031	>	public Iterator<E> iterator() {
1032	>	if (m instanceof TreeMap)
1033	>	return ((TreeMap<E,Object>)m).keyIterator();
1034	>	else
1035	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1036	>	}
1037	>
1038	>	public Iterator<E> descendingIterator() {
1039	>	if (m instanceof TreeMap)
1040	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1041	>	else
1042	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1043	>	}
1044	>
1045	>	public int size() { return m.size(); }
1046	>	public boolean isEmpty() { return m.isEmpty(); }
1047	>	public boolean contains(Object o) { return m.containsKey(o); }
1048	>	public void clear() { m.clear(); }
1049	>	public E lower(E e) { return m.lowerKey(e); }
1050	>	public E floor(E e) { return m.floorKey(e); }
1051	>	public E ceiling(E e) { return m.ceilingKey(e); }
1052	>	public E higher(E e) { return m.higherKey(e); }
1053	>	public E first() { return m.firstKey(); }
1054	>	public E last() { return m.lastKey(); }
1055	>	public Comparator<? super E> comparator() { return m.comparator(); }
1056	>	public E pollFirst() {
1057	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1058	>	return e == null? null : e.getKey();
1059	>	}
1060	>	public E pollLast() {
1061	>	Map.Entry<E,Object> e = m.pollLastEntry();
1062	>	return e == null? null : e.getKey();
1063	>	}
1064	>	public boolean remove(Object o) {
1065	>	int oldSize = size();
1066	>	m.remove(o);
1067	>	return size() != oldSize;
1068	>	}
1069	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1070	>	E toElement, boolean toInclusive) {
1071	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1072	>	toElement, toInclusive));
1073	>	}
1074	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1075	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1076	>	}
1077	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1078	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1079	>	}
1080	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1081	>	return subSet(fromElement, true, toElement, false);
1082	>	}
1083	>	public SortedSet<E> headSet(E toElement) {
1084	>	return headSet(toElement, false);
1085	>	}
1086	>	public SortedSet<E> tailSet(E fromElement) {
1087	>	return tailSet(fromElement, true);
1088	>	}
1089	>	public NavigableSet<E> descendingSet() {
1090	>	return new TreeSet(m.descendingMap());
1091		}
1092		}
1093
1094		/**
1095	<	* Returns a Set view of the keys contained in this map. The
1051	<	* set's iterator will return the keys in descending order. The
1052	<	* map is backed by this <tt>TreeMap</tt> instance, so changes to
1053	<	* this map are reflected in the Set, and vice-versa. The Set
1054	<	* supports element removal, which removes the corresponding
1055	<	* mapping from the map, via the <tt>Iterator.remove</tt>,
1056	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1057	<	* and <tt>clear</tt> operations. It does not support the
1058	<	* <tt>add</tt> or <tt>addAll</tt> operations.
1059	<	*
1060	<	* @return a set view of the keys contained in this TreeMap.
1095	>	* Base class for TreeMap Iterators
1096		*/
1097	<	public Set<K> descendingKeySet() {
1098	<	Set<K> ks = descendingKeySet;
1099	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1100	<	}
1101	<
1102	<	class DescendingKeySet extends KeySet {
1103	<	public Iterator<K> iterator() {
1104	<	return new DescendingKeyIterator(getLastEntry());
1097	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1098	>	Entry<K,V> next;
1099	>	Entry<K,V> lastReturned;
1100	>	int expectedModCount;
1101	>
1102	>	PrivateEntryIterator(Entry<K,V> first) {
1103	>	expectedModCount = modCount;
1104	>	lastReturned = null;
1105	>	next = first;
1106	>	}
1107	>
1108	>	public final boolean hasNext() {
1109	>	return next != null;
1110	>	}
1111	>
1112	>	final Entry<K,V> nextEntry() {
1113	>	Entry<K,V> e = next;
1114	>	if (e == null)
1115	>	throw new NoSuchElementException();
1116	>	if (modCount != expectedModCount)
1117	>	throw new ConcurrentModificationException();
1118	>	next = successor(e);
1119	>	lastReturned = e;
1120	>	return e;
1121	>	}
1122	>
1123	>	final Entry<K,V> prevEntry() {
1124	>	Entry<K,V> e = next;
1125	>	if (e == null)
1126	>	throw new NoSuchElementException();
1127	>	if (modCount != expectedModCount)
1128	>	throw new ConcurrentModificationException();
1129	>	next = predecessor(e);
1130	>	lastReturned = e;
1131	>	return e;
1132	>	}
1133	>
1134	>	public void remove() {
1135	>	if (lastReturned == null)
1136	>	throw new IllegalStateException();
1137	>	if (modCount != expectedModCount)
1138	>	throw new ConcurrentModificationException();
1139	>	// deleted entries are replaced by their successors
1140	>	if (lastReturned.left != null && lastReturned.right != null)
1141	>	next = lastReturned;
1142	>	deleteEntry(lastReturned);
1143	>	expectedModCount = modCount;
1144	>	lastReturned = null;
1145	>	}
1146	>	}
1147	>
1148	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1149	>	EntryIterator(Entry<K,V> first) {
1150	>	super(first);
1151	>	}
1152	>	public Map.Entry<K,V> next() {
1153	>	return nextEntry();
1154		}
1155		}
1156
1157	+	final class ValueIterator extends PrivateEntryIterator<V> {
1158	+	ValueIterator(Entry<K,V> first) {
1159	+	super(first);
1160	+	}
1161	+	public V next() {
1162	+	return nextEntry().value;
1163	+	}
1164	+	}
1165	+
1166	+	final class KeyIterator extends PrivateEntryIterator<K> {
1167	+	KeyIterator(Entry<K,V> first) {
1168	+	super(first);
1169	+	}
1170	+	public K next() {
1171	+	return nextEntry().key;
1172	+	}
1173	+	}
1174	+
1175	+	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1176	+	DescendingKeyIterator(Entry<K,V> first) {
1177	+	super(first);
1178	+	}
1179	+	public K next() {
1180	+	return prevEntry().key;
1181	+	}
1182	+	}
1183	+
1184	+	// Little utilities
1185	+
1186		/**
1187	<	* Returns a view of the portion of this map whose keys range from
1075	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
1076	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1077	<	* navigable map is empty.) The returned navigable map is backed
1078	<	* by this map, so changes in the returned navigable map are
1079	<	* reflected in this map, and vice-versa. The returned navigable
1080	<	* map supports all optional map operations.<p>
1081	<	*
1082	<	* The navigable map returned by this method will throw an
1083	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1084	<	* less than <tt>fromKey</tt> or greater than or equal to
1085	<	* <tt>toKey</tt>.<p>
1086	<	*
1087	<	* Note: this method always returns a <i>half-open range</i> (which
1088	<	* includes its low endpoint but not its high endpoint). If you need a
1089	<	* <i>closed range</i> (which includes both endpoints), and the key type
1090	<	* allows for calculation of the successor of a given key, merely request the
1091	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1092	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1093	<	* strings. The following idiom obtains a view containing all of the
1094	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1095	<	* and <tt>high</tt>, inclusive:
1096	<	* <pre> NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1097	<	* A similar technique can be used to generate an <i>open range</i> (which
1098	<	* contains neither endpoint). The following idiom obtains a view
1099	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1100	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1101	<	* <pre> NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1102	<	*
1103	<	* @param fromKey low endpoint (inclusive) of the subMap.
1104	<	* @param toKey high endpoint (exclusive) of the subMap.
1105	<	*
1106	<	* @return a view of the portion of this map whose keys range from
1107	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1108	<	*
1109	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1110	<	* cannot be compared to one another using this map's comparator
1111	<	* (or, if the map has no comparator, using natural ordering).
1112	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1113	<	* <tt>toKey</tt>.
1114	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1115	<	* <tt>null</tt> and this map uses natural order, or its
1116	<	* comparator does not tolerate <tt>null</tt> keys.
1187	>	* Compares two keys using the correct comparison method for this TreeMap.
1188		*/
1189	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1190	<	return new SubMap(fromKey, toKey);
1189	>	final int compare(Object k1, Object k2) {
1190	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1191	>	: comparator.compare((K)k1, (K)k2);
1192		}
1193
1122	–
1194		/**
1195	<	* Returns a view of the portion of this map whose keys are strictly less
1196	<	* than <tt>toKey</tt>. The returned navigable map is backed by this map, so
1126	<	* changes in the returned navigable map are reflected in this map, and
1127	<	* vice-versa. The returned navigable map supports all optional map
1128	<	* operations.<p>
1129	<	*
1130	<	* The navigable map returned by this method will throw an
1131	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1132	<	* greater than or equal to <tt>toKey</tt>.<p>
1133	<	*
1134	<	* Note: this method always returns a view that does not contain its
1135	<	* (high) endpoint. If you need a view that does contain this endpoint,
1136	<	* and the key type allows for calculation of the successor of a given key,
1137	<	* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1138	<	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1139	<	* keys are strings. The following idiom obtains a view containing all of
1140	<	* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1141	<	* to <tt>high</tt>:
1142	<	* <pre>
1143	<	* NavigableMap head = m.navigableHeadMap(high+"\0");
1144	<	* </pre>
1145	<	*
1146	<	* @param toKey high endpoint (exclusive) of the headMap.
1147	<	* @return a view of the portion of this map whose keys are strictly
1148	<	* less than <tt>toKey</tt>.
1149	<	*
1150	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1151	<	* with this map's comparator (or, if the map has no comparator,
1152	<	* if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1153	<	* @throws IllegalArgumentException if this map is itself a subMap,
1154	<	* headMap, or tailMap, and <tt>toKey</tt> is not within the
1155	<	* specified range of the subMap, headMap, or tailMap.
1156	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1157	<	* this map uses natural order, or its comparator does not
1158	<	* tolerate <tt>null</tt> keys.
1159	<	*/
1160	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1161	<	return new SubMap(toKey, true);
1162	<	}
1163	<
1164	<	/**
1165	<	* Returns a view of the portion of this map whose keys are greater than
1166	<	* or equal to <tt>fromKey</tt>. The returned navigable map is backed by
1167	<	* this map, so changes in the returned navigable map are reflected in this
1168	<	* map, and vice-versa. The returned navigable map supports all optional map
1169	<	* operations.<p>
1170	<	*
1171	<	* The navigable map returned by this method will throw an
1172	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1173	<	* less than <tt>fromKey</tt>.<p>
1174	<	*
1175	<	* Note: this method always returns a view that contains its (low)
1176	<	* endpoint. If you need a view that does not contain this endpoint, and
1177	<	* the element type allows for calculation of the successor of a given value,
1178	<	* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1179	<	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1180	<	* are strings. The following idiom obtains a view containing
1181	<	* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1182	<	* greater than <tt>low</tt>: <pre>
1183	<	* NavigableMap tail = m.navigableTailMap(low+"\0");
1184	<	* </pre>
1185	<	*
1186	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1187	<	* @return a view of the portion of this map whose keys are greater
1188	<	* than or equal to <tt>fromKey</tt>.
1189	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1190	<	* with this map's comparator (or, if the map has no comparator,
1191	<	* if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1192	<	* @throws IllegalArgumentException if this map is itself a subMap,
1193	<	* headMap, or tailMap, and <tt>fromKey</tt> is not within the
1194	<	* specified range of the subMap, headMap, or tailMap.
1195	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1196	<	* this map uses natural order, or its comparator does not
1197	<	* tolerate <tt>null</tt> keys.
1198	<	*/
1199	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1200	<	return new SubMap(fromKey, false);
1201	<	}
1202	<
1203	<	/**
1204	<	* Equivalent to <tt>navigableSubMap</tt> but with a return
1205	<	* type conforming to the <tt>SortedMap</tt> interface.
1206	<	* @param fromKey low endpoint (inclusive) of the subMap.
1207	<	* @param toKey high endpoint (exclusive) of the subMap.
1208	<	*
1209	<	* @return a view of the portion of this map whose keys range from
1210	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1211	<	*
1212	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1213	<	* cannot be compared to one another using this map's comparator
1214	<	* (or, if the map has no comparator, using natural ordering).
1215	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1216	<	* <tt>toKey</tt>.
1217	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1218	<	* <tt>null</tt> and this map uses natural order, or its
1219	<	* comparator does not tolerate <tt>null</tt> keys.
1195	>	* Test two values for equality. Differs from o1.equals(o2) only in
1196	>	* that it copes with <tt>null</tt> o1 properly.
1197		*/
1198	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1199	<	return new SubMap(fromKey, toKey);
1198	>	final static boolean valEquals(Object o1, Object o2) {
1199	>	return (o1==null ? o2==null : o1.equals(o2));
1200		}
1201
1202	+	/**
1203	+	* Return SimpleImmutableEntry for entry, or null if null
1204	+	*/
1205	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1206	+	return e == null? null :
1207	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1208	+	}
1209
1210		/**
1211	<	* Equivalent to <tt>navigableHeadMap</tt> but with a return
1228	<	* type conforming to the <tt>SortedMap</tt> interface.
1229	<	*
1230	<	* @param toKey high endpoint (exclusive) of the headMap.
1231	<	* @return a view of the portion of this map whose keys are strictly
1232	<	* less than <tt>toKey</tt>.
1233	<	*
1234	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1235	<	* with this map's comparator (or, if the map has no comparator,
1236	<	* if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1237	<	* @throws IllegalArgumentException if this map is itself a subMap,
1238	<	* headMap, or tailMap, and <tt>toKey</tt> is not within the
1239	<	* specified range of the subMap, headMap, or tailMap.
1240	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1241	<	* this map uses natural order, or its comparator does not
1242	<	* tolerate <tt>null</tt> keys.
1211	>	* Return key for entry, or null if null
1212		*/
1213	<	public SortedMap<K,V> headMap(K toKey) {
1214	<	return new SubMap(toKey, true);
1213	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1214	>	return e == null? null : e.key;
1215		}
1216
1217		/**
1218	<	* Equivalent to <tt>navigableTailMap</tt> but with a return
1219	<	* type conforming to the <tt>SortedMap</tt> interface.
1251	<	*
1252	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1253	<	* @return a view of the portion of this map whose keys are greater
1254	<	* than or equal to <tt>fromKey</tt>.
1255	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1256	<	* with this map's comparator (or, if the map has no comparator,
1257	<	* if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1258	<	* @throws IllegalArgumentException if this map is itself a subMap,
1259	<	* headMap, or tailMap, and <tt>fromKey</tt> is not within the
1260	<	* specified range of the subMap, headMap, or tailMap.
1261	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1262	<	* this map uses natural order, or its comparator does not
1263	<	* tolerate <tt>null</tt> keys.
1218	>	* Returns the key corresponding to the specified Entry.
1219	>	* @throws NoSuchElementException if the Entry is null
1220		*/
1221	<	public SortedMap<K,V> tailMap(K fromKey) {
1222	<	return new SubMap(fromKey, false);
1221	>	static <K> K key(Entry<K,?> e) {
1222	>	if (e==null)
1223	>	throw new NoSuchElementException();
1224	>	return e.key;
1225		}
1226
1269	–	private class SubMap
1270	–	extends AbstractMap<K,V>
1271	–	implements NavigableMap<K,V>, java.io.Serializable {
1272	–	private static final long serialVersionUID = -6520786458950516097L;
1227
1228	+	// SubMaps
1229	+
1230	+	/**
1231	+	* Dummy value serving as unmatchable fence key for unbounded
1232	+	* SubMapIterators
1233	+	*/
1234	+	private static final Object UNBOUNDED = new Object();
1235	+
1236	+	/**
1237	+	* @serial include
1238	+	*/
1239	+	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1240	+	implements NavigableMap<K,V>, java.io.Serializable {
1241		/**
1242	<	* fromKey is significant only if fromStart is false. Similarly,
1276	<	* toKey is significant only if toStart is false.
1242	>	* The backing map.
1243		*/
1244	<	private boolean fromStart = false, toEnd = false;
1279	<	private K fromKey, toKey;
1280	<
1281	<	SubMap(K fromKey, K toKey) {
1282	<	if (compare(fromKey, toKey) > 0)
1283	<	throw new IllegalArgumentException("fromKey > toKey");
1284	<	this.fromKey = fromKey;
1285	<	this.toKey = toKey;
1286	<	}
1244	>	final TreeMap<K,V> m;
1245
1246	<	SubMap(K key, boolean headMap) {
1247	<	compare(key, key); // Type-check key
1248	<
1249	<	if (headMap) {
1250	<	fromStart = true;
1251	<	toKey = key;
1246	>	/**
1247	>	* Endpoints are represented as triples (fromStart, lo,
1248	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1249	>	* true, then the low (absolute) bound is the start of the
1250	>	* backing map, and the other values are ignored. Otherwise,
1251	>	* if loInclusive is true, lo is the inclusive bound, else lo
1252	>	* is the exclusive bound. Similarly for the upper bound.
1253	>	*/
1254	>	final K lo, hi;
1255	>	final boolean fromStart, toEnd;
1256	>	final boolean loInclusive, hiInclusive;
1257	>
1258	>	NavigableSubMap(TreeMap<K,V> m,
1259	>	boolean fromStart, K lo, boolean loInclusive,
1260	>	boolean toEnd, K hi, boolean hiInclusive) {
1261	>	if (!fromStart && !toEnd) {
1262	>	if (m.compare(lo, hi) > 0)
1263	>	throw new IllegalArgumentException("fromKey > toKey");
1264		} else {
1265	<	toEnd = true;
1266	<	fromKey = key;
1265	>	if (!fromStart) // type check
1266	>	m.compare(lo, lo);
1267	>	if (!toEnd)
1268	>	m.compare(hi, hi);
1269		}
1298	–	}
1270
1271	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1271	>	this.m = m;
1272		this.fromStart = fromStart;
1273	<	this.fromKey= fromKey;
1273	>	this.lo = lo;
1274	>	this.loInclusive = loInclusive;
1275		this.toEnd = toEnd;
1276	<	this.toKey = toKey;
1276	>	this.hi = hi;
1277	>	this.hiInclusive = hiInclusive;
1278	>	}
1279	>
1280	>	// internal utilities
1281	>
1282	>	final boolean tooLow(Object key) {
1283	>	if (!fromStart) {
1284	>	int c = m.compare(key, lo);
1285	>	if (c < 0 \|\| (c == 0 && !loInclusive))
1286	>	return true;
1287	>	}
1288	>	return false;
1289		}
1290
1291	+	final boolean tooHigh(Object key) {
1292	+	if (!toEnd) {
1293	+	int c = m.compare(key, hi);
1294	+	if (c > 0 \|\| (c == 0 && !hiInclusive))
1295	+	return true;
1296	+	}
1297	+	return false;
1298	+	}
1299	+
1300	+	final boolean inRange(Object key) {
1301	+	return !tooLow(key) && !tooHigh(key);
1302	+	}
1303	+
1304	+	final boolean inClosedRange(Object key) {
1305	+	return (fromStart \|\| m.compare(key, lo) >= 0)
1306	+	&& (toEnd \|\| m.compare(hi, key) >= 0);
1307	+	}
1308	+
1309	+	final boolean inRange(Object key, boolean inclusive) {
1310	+	return inclusive ? inRange(key) : inClosedRange(key);
1311	+	}
1312	+
1313	+	/*
1314	+	* Absolute versions of relation operations.
1315	+	* Subclasses map to these using like-named "sub"
1316	+	* versions that invert senses for descending maps
1317	+	*/
1318	+
1319	+	final TreeMap.Entry<K,V> absLowest() {
1320	+	TreeMap.Entry<K,V> e =
1321	+	(fromStart ? m.getFirstEntry() :
1322	+	(loInclusive ? m.getCeilingEntry(lo) :
1323	+	m.getHigherEntry(lo)));
1324	+	return (e == null \|\| tooHigh(e.key)) ? null : e;
1325	+	}
1326	+
1327	+	final TreeMap.Entry<K,V> absHighest() {
1328	+	TreeMap.Entry<K,V> e =
1329	+	(toEnd ? m.getLastEntry() :
1330	+	(hiInclusive ? m.getFloorEntry(hi) :
1331	+	m.getLowerEntry(hi)));
1332	+	return (e == null \|\| tooLow(e.key)) ? null : e;
1333	+	}
1334	+
1335	+	final TreeMap.Entry<K,V> absCeiling(K key) {
1336	+	if (tooLow(key))
1337	+	return absLowest();
1338	+	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1339	+	return (e == null \|\| tooHigh(e.key)) ? null : e;
1340	+	}
1341	+
1342	+	final TreeMap.Entry<K,V> absHigher(K key) {
1343	+	if (tooLow(key))
1344	+	return absLowest();
1345	+	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1346	+	return (e == null \|\| tooHigh(e.key)) ? null : e;
1347	+	}
1348	+
1349	+	final TreeMap.Entry<K,V> absFloor(K key) {
1350	+	if (tooHigh(key))
1351	+	return absHighest();
1352	+	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1353	+	return (e == null \|\| tooLow(e.key)) ? null : e;
1354	+	}
1355	+
1356	+	final TreeMap.Entry<K,V> absLower(K key) {
1357	+	if (tooHigh(key))
1358	+	return absHighest();
1359	+	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1360	+	return (e == null \|\| tooLow(e.key)) ? null : e;
1361	+	}
1362	+
1363	+	/** Returns the absolute high fence for ascending traversal */
1364	+	final TreeMap.Entry<K,V> absHighFence() {
1365	+	return (toEnd ? null : (hiInclusive ?
1366	+	m.getHigherEntry(hi) :
1367	+	m.getCeilingEntry(hi)));
1368	+	}
1369	+
1370	+	/** Return the absolute low fence for descending traversal */
1371	+	final TreeMap.Entry<K,V> absLowFence() {
1372	+	return (fromStart ? null : (loInclusive ?
1373	+	m.getLowerEntry(lo) :
1374	+	m.getFloorEntry(lo)));
1375	+	}
1376	+
1377	+	// Abstract methods defined in ascending vs descending classes
1378	+	// These relay to the appropriate absolute versions
1379	+
1380	+	abstract TreeMap.Entry<K,V> subLowest();
1381	+	abstract TreeMap.Entry<K,V> subHighest();
1382	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1383	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1384	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1385	+	abstract TreeMap.Entry<K,V> subLower(K key);
1386	+
1387	+	/** Returns ascending iterator from the perspective of this submap */
1388	+	abstract Iterator<K> keyIterator();
1389	+
1390	+	/** Returns descending iterator from the perspective of this submap */
1391	+	abstract Iterator<K> descendingKeyIterator();
1392	+
1393	+	// public methods
1394	+
1395		public boolean isEmpty() {
1396	<	return entrySet().isEmpty();
1396	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1397		}
1398
1399	<	public boolean containsKey(Object key) {
1400	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1399	>	public int size() {
1400	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1401		}
1402
1403	<	public V get(Object key) {
1404	<	if (!inRange((K) key))
1317	<	return null;
1318	<	return TreeMap.this.get(key);
1403	>	public final boolean containsKey(Object key) {
1404	>	return inRange(key) && m.containsKey(key);
1405		}
1406
1407	<	public V put(K key, V value) {
1407	>	public final V put(K key, V value) {
1408		if (!inRange(key))
1409		throw new IllegalArgumentException("key out of range");
1410	<	return TreeMap.this.put(key, value);
1410	>	return m.put(key, value);
1411		}
1412
1413	<	public V remove(Object key) {
1414	<	if (!inRange((K) key))
1329	<	return null;
1330	<	return TreeMap.this.remove(key);
1413	>	public final V get(Object key) {
1414	>	return !inRange(key)? null : m.get(key);
1415		}
1416
1417	<	public Comparator<? super K> comparator() {
1418	<	return comparator;
1417	>	public final V remove(Object key) {
1418	>	return !inRange(key)? null : m.remove(key);
1419		}
1420
1421	<	public K firstKey() {
1422	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1339	<	K first = key(e);
1340	<	if (!toEnd && compare(first, toKey) >= 0)
1341	<	throw new NoSuchElementException();
1342	<	return first;
1421	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1422	>	return exportEntry(subCeiling(key));
1423		}
1424
1425	<	public K lastKey() {
1426	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1347	<	K last = key(e);
1348	<	if (!fromStart && compare(last, fromKey) < 0)
1349	<	throw new NoSuchElementException();
1350	<	return last;
1425	>	public final K ceilingKey(K key) {
1426	>	return keyOrNull(subCeiling(key));
1427		}
1428
1429	<	public Map.Entry<K,V> firstEntry() {
1430	<	TreeMap.Entry<K,V> e = fromStart ?
1355	<	getFirstEntry() : getCeilingEntry(fromKey);
1356	<	if (e == null \|\| (!toEnd && compare(e.key, toKey) >= 0))
1357	<	return null;
1358	<	return e;
1429	>	public final Map.Entry<K,V> higherEntry(K key) {
1430	>	return exportEntry(subHigher(key));
1431		}
1432
1433	<	public Map.Entry<K,V> lastEntry() {
1434	<	TreeMap.Entry<K,V> e = toEnd ?
1363	<	getLastEntry() : getLowerEntry(toKey);
1364	<	if (e == null \|\| (!fromStart && compare(e.key, fromKey) < 0))
1365	<	return null;
1366	<	return e;
1433	>	public final K higherKey(K key) {
1434	>	return keyOrNull(subHigher(key));
1435		}
1436
1437	<	public Map.Entry<K,V> pollFirstEntry() {
1438	<	TreeMap.Entry<K,V> e = fromStart ?
1371	<	getFirstEntry() : getCeilingEntry(fromKey);
1372	<	if (e == null \|\| (!toEnd && compare(e.key, toKey) >= 0))
1373	<	return null;
1374	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1375	<	deleteEntry(e);
1376	<	return result;
1437	>	public final Map.Entry<K,V> floorEntry(K key) {
1438	>	return exportEntry(subFloor(key));
1439		}
1440
1441	<	public Map.Entry<K,V> pollLastEntry() {
1442	<	TreeMap.Entry<K,V> e = toEnd ?
1381	<	getLastEntry() : getLowerEntry(toKey);
1382	<	if (e == null \|\| (!fromStart && compare(e.key, fromKey) < 0))
1383	<	return null;
1384	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1385	<	deleteEntry(e);
1386	<	return result;
1441	>	public final K floorKey(K key) {
1442	>	return keyOrNull(subFloor(key));
1443		}
1444
1445	<	private TreeMap.Entry<K,V> subceiling(K key) {
1446	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1391	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1392	<	if (e == null \|\| (!toEnd && compare(e.key, toKey) >= 0))
1393	<	return null;
1394	<	return e;
1445	>	public final Map.Entry<K,V> lowerEntry(K key) {
1446	>	return exportEntry(subLower(key));
1447		}
1448
1449	<	public Map.Entry<K,V> ceilingEntry(K key) {
1450	<	TreeMap.Entry<K,V> e = subceiling(key);
1399	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1449	>	public final K lowerKey(K key) {
1450	>	return keyOrNull(subLower(key));
1451		}
1452
1453	<	public K ceilingKey(K key) {
1454	<	TreeMap.Entry<K,V> e = subceiling(key);
1404	<	return e == null? null : e.key;
1453	>	public final K firstKey() {
1454	>	return key(subLowest());
1455		}
1456
1457	<
1458	<	private TreeMap.Entry<K,V> subhigher(K key) {
1409	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1410	<	getCeilingEntry(fromKey) : getHigherEntry(key);
1411	<	if (e == null \|\| (!toEnd && compare(e.key, toKey) >= 0))
1412	<	return null;
1413	<	return e;
1457	>	public final K lastKey() {
1458	>	return key(subHighest());
1459		}
1460
1461	<	public Map.Entry<K,V> higherEntry(K key) {
1462	<	TreeMap.Entry<K,V> e = subhigher(key);
1418	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1461	>	public final Map.Entry<K,V> firstEntry() {
1462	>	return exportEntry(subLowest());
1463		}
1464
1465	<	public K higherKey(K key) {
1466	<	TreeMap.Entry<K,V> e = subhigher(key);
1423	<	return e == null? null : e.key;
1465	>	public final Map.Entry<K,V> lastEntry() {
1466	>	return exportEntry(subHighest());
1467		}
1468
1469	<	private TreeMap.Entry<K,V> subfloor(K key) {
1470	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1471	<	getLowerEntry(toKey) : getFloorEntry(key);
1472	<	if (e == null \|\| (!fromStart && compare(e.key, fromKey) < 0))
1473	<	return null;
1474	<	return e;
1469	>	public final Map.Entry<K,V> pollFirstEntry() {
1470	>	TreeMap.Entry<K,V> e = subLowest();
1471	>	Map.Entry<K,V> result = exportEntry(e);
1472	>	if (e != null)
1473	>	m.deleteEntry(e);
1474	>	return result;
1475		}
1476
1477	<	public Map.Entry<K,V> floorEntry(K key) {
1478	<	TreeMap.Entry<K,V> e = subfloor(key);
1479	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1477	>	public final Map.Entry<K,V> pollLastEntry() {
1478	>	TreeMap.Entry<K,V> e = subHighest();
1479	>	Map.Entry<K,V> result = exportEntry(e);
1480	>	if (e != null)
1481	>	m.deleteEntry(e);
1482	>	return result;
1483		}
1484
1485	<	public K floorKey(K key) {
1486	<	TreeMap.Entry<K,V> e = subfloor(key);
1487	<	return e == null? null : e.key;
1485	>	// Views
1486	>	transient NavigableMap<K,V> descendingMapView = null;
1487	>	transient EntrySetView entrySetView = null;
1488	>	transient KeySet<K> navigableKeySetView = null;
1489	>
1490	>	public final NavigableSet<K> navigableKeySet() {
1491	>	KeySet<K> nksv = navigableKeySetView;
1492	>	return (nksv != null) ? nksv :
1493	>	(navigableKeySetView = new TreeMap.KeySet(this));
1494		}
1495
1496	<	private TreeMap.Entry<K,V> sublower(K key) {
1497	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1446	<	getLowerEntry(toKey) : getLowerEntry(key);
1447	<	if (e == null \|\| (!fromStart && compare(e.key, fromKey) < 0))
1448	<	return null;
1449	<	return e;
1496	>	public final Set<K> keySet() {
1497	>	return navigableKeySet();
1498		}
1499
1500	<	public Map.Entry<K,V> lowerEntry(K key) {
1501	<	TreeMap.Entry<K,V> e = sublower(key);
1454	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1500	>	public NavigableSet<K> descendingKeySet() {
1501	>	return descendingMap().navigableKeySet();
1502		}
1503
1504	<	public K lowerKey(K key) {
1505	<	TreeMap.Entry<K,V> e = sublower(key);
1459	<	return e == null? null : e.key;
1504	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1505	>	return subMap(fromKey, true, toKey, false);
1506		}
1507
1508	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1508	>	public final SortedMap<K,V> headMap(K toKey) {
1509	>	return headMap(toKey, false);
1510	>	}
1511
1512	<	public Set<Map.Entry<K,V>> entrySet() {
1513	<	Set<Map.Entry<K,V>> es = entrySet;
1466	<	return (es != null)? es : (entrySet = new EntrySetView());
1512	>	public final SortedMap<K,V> tailMap(K fromKey) {
1513	>	return tailMap(fromKey, true);
1514		}
1515
1516	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1516	>	// View classes
1517	>
1518	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1519		private transient int size = -1, sizeModCount;
1520
1521		public int size() {
1522	<	if (size == -1 \|\| sizeModCount != TreeMap.this.modCount) {
1523	<	size = 0; sizeModCount = TreeMap.this.modCount;
1522	>	if (fromStart && toEnd)
1523	>	return m.size();
1524	>	if (size == -1 \|\| sizeModCount != m.modCount) {
1525	>	sizeModCount = m.modCount;
1526	>	size = 0;
1527		Iterator i = iterator();
1528		while (i.hasNext()) {
1529		size++;
#	Line 1482 \| Line 1534 \| public class TreeMap<K,V>
1534		}
1535
1536		public boolean isEmpty() {
1537	<	return !iterator().hasNext();
1537	>	TreeMap.Entry<K,V> n = absLowest();
1538	>	return n == null \|\| tooHigh(n.key);
1539		}
1540
1541		public boolean contains(Object o) {
#	Line 1492 \| Line 1545 \| public class TreeMap<K,V>
1545		K key = entry.getKey();
1546		if (!inRange(key))
1547		return false;
1548	<	TreeMap.Entry node = getEntry(key);
1548	>	TreeMap.Entry node = m.getEntry(key);
1549		return node != null &&
1550	<	valEquals(node.getValue(), entry.getValue());
1550	>	valEquals(node.getValue(), entry.getValue());
1551		}
1552
1553		public boolean remove(Object o) {
#	Line 1504 \| Line 1557 \| public class TreeMap<K,V>
1557		K key = entry.getKey();
1558		if (!inRange(key))
1559		return false;
1560	<	TreeMap.Entry<K,V> node = getEntry(key);
1560	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1561		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1562	<	deleteEntry(node);
1562	>	m.deleteEntry(node);
1563		return true;
1564		}
1565		return false;
1566		}
1514	–
1515	–	public Iterator<Map.Entry<K,V>> iterator() {
1516	–	return new SubMapEntryIterator(
1517	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1518	–	(toEnd ? null : getCeilingEntry(toKey)));
1519	–	}
1520	–	}
1521	–
1522	–	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1523	–	private transient Set<K> descendingKeySetView = null;
1524	–
1525	–	public Set<Map.Entry<K,V>> descendingEntrySet() {
1526	–	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1527	–	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1567		}
1568
1569	<	public Set<K> descendingKeySet() {
1570	<	Set<K> ks = descendingKeySetView;
1571	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1572	<	}
1569	>	/**
1570	>	* Iterators for SubMaps
1571	>	*/
1572	>	abstract class SubMapIterator<T> implements Iterator<T> {
1573	>	TreeMap.Entry<K,V> lastReturned;
1574	>	TreeMap.Entry<K,V> next;
1575	>	final Object fenceKey;
1576	>	int expectedModCount;
1577
1578	<	private class DescendingEntrySetView extends EntrySetView {
1579	<	public Iterator<Map.Entry<K,V>> iterator() {
1580	<	return new DescendingSubMapEntryIterator
1581	<	((toEnd ? getLastEntry() : getLowerEntry(toKey)),
1582	<	(fromStart ? null : getLowerEntry(fromKey)));
1578	>	SubMapIterator(TreeMap.Entry<K,V> first,
1579	>	TreeMap.Entry<K,V> fence) {
1580	>	expectedModCount = m.modCount;
1581	>	lastReturned = null;
1582	>	next = first;
1583	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1584		}
1541	–	}
1542	–
1543	–	private class DescendingKeySetView extends AbstractSet<K> {
1544	–	public Iterator<K> iterator() {
1545	–	return new Iterator<K>() {
1546	–	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1585
1586	<	public boolean hasNext() { return i.hasNext(); }
1587	<	public K next() { return i.next().getKey(); }
1550	<	public void remove() { i.remove(); }
1551	<	};
1586	>	public final boolean hasNext() {
1587	>	return next != null && next.key != fenceKey;
1588		}
1589
1590	<	public int size() {
1591	<	return SubMap.this.size();
1590	>	final TreeMap.Entry<K,V> nextEntry() {
1591	>	TreeMap.Entry<K,V> e = next;
1592	>	if (e == null \|\| e.key == fenceKey)
1593	>	throw new NoSuchElementException();
1594	>	if (m.modCount != expectedModCount)
1595	>	throw new ConcurrentModificationException();
1596	>	next = successor(e);
1597	>	lastReturned = e;
1598	>	return e;
1599		}
1600
1601	<	public boolean contains(Object k) {
1602	<	return SubMap.this.containsKey(k);
1601	>	final TreeMap.Entry<K,V> prevEntry() {
1602	>	TreeMap.Entry<K,V> e = next;
1603	>	if (e == null \|\| e.key == fenceKey)
1604	>	throw new NoSuchElementException();
1605	>	if (m.modCount != expectedModCount)
1606	>	throw new ConcurrentModificationException();
1607	>	next = predecessor(e);
1608	>	lastReturned = e;
1609	>	return e;
1610		}
1561	–	}
1611
1612	+	final void removeAscending() {
1613	+	if (lastReturned == null)
1614	+	throw new IllegalStateException();
1615	+	if (m.modCount != expectedModCount)
1616	+	throw new ConcurrentModificationException();
1617	+	// deleted entries are replaced by their successors
1618	+	if (lastReturned.left != null && lastReturned.right != null)
1619	+	next = lastReturned;
1620	+	m.deleteEntry(lastReturned);
1621	+	lastReturned = null;
1622	+	expectedModCount = m.modCount;
1623	+	}
1624
1625	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1626	<	if (!inRange2(fromKey))
1627	<	throw new IllegalArgumentException("fromKey out of range");
1628	<	if (!inRange2(toKey))
1629	<	throw new IllegalArgumentException("toKey out of range");
1630	<	return new SubMap(fromKey, toKey);
1631	<	}
1632	<
1633	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1573	<	if (!inRange2(toKey))
1574	<	throw new IllegalArgumentException("toKey out of range");
1575	<	return new SubMap(fromStart, fromKey, false, toKey);
1576	<	}
1625	>	final void removeDescending() {
1626	>	if (lastReturned == null)
1627	>	throw new IllegalStateException();
1628	>	if (m.modCount != expectedModCount)
1629	>	throw new ConcurrentModificationException();
1630	>	m.deleteEntry(lastReturned);
1631	>	lastReturned = null;
1632	>	expectedModCount = m.modCount;
1633	>	}
1634
1578	–	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1579	–	if (!inRange2(fromKey))
1580	–	throw new IllegalArgumentException("fromKey out of range");
1581	–	return new SubMap(false, fromKey, toEnd, toKey);
1635		}
1636
1637	<
1638	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1639	<	return navigableSubMap(fromKey, toKey);
1637	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1638	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1639	>	TreeMap.Entry<K,V> fence) {
1640	>	super(first, fence);
1641	>	}
1642	>	public Map.Entry<K,V> next() {
1643	>	return nextEntry();
1644	>	}
1645	>	public void remove() {
1646	>	removeAscending();
1647	>	}
1648		}
1649
1650	<	public SortedMap<K,V> headMap(K toKey) {
1651	<	return navigableHeadMap(toKey);
1650	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1651	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1652	>	TreeMap.Entry<K,V> fence) {
1653	>	super(first, fence);
1654	>	}
1655	>	public K next() {
1656	>	return nextEntry().key;
1657	>	}
1658	>	public void remove() {
1659	>	removeAscending();
1660	>	}
1661		}
1662
1663	<	public SortedMap<K,V> tailMap(K fromKey) {
1664	<	return navigableTailMap(fromKey);
1665	<	}
1663	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1664	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1665	>	TreeMap.Entry<K,V> fence) {
1666	>	super(last, fence);
1667	>	}
1668
1669	<	private boolean inRange(K key) {
1670	<	return (fromStart \|\| compare(key, fromKey) >= 0) &&
1671	<	(toEnd \|\| compare(key, toKey) < 0);
1669	>	public Map.Entry<K,V> next() {
1670	>	return prevEntry();
1671	>	}
1672	>	public void remove() {
1673	>	removeDescending();
1674	>	}
1675		}
1676
1677	<	// This form allows the high endpoint (as well as all legit keys)
1678	<	private boolean inRange2(K key) {
1679	<	return (fromStart \|\| compare(key, fromKey) >= 0) &&
1680	<	(toEnd \|\| compare(key, toKey) <= 0);
1677	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1678	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1679	>	TreeMap.Entry<K,V> fence) {
1680	>	super(last, fence);
1681	>	}
1682	>	public K next() {
1683	>	return prevEntry().key;
1684	>	}
1685	>	public void remove() {
1686	>	removeDescending();
1687	>	}
1688		}
1689		}
1690
1691		/**
1692	<	* TreeMap Iterator.
1692	>	* @serial include
1693		*/
1694	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1695	<	int expectedModCount = TreeMap.this.modCount;
1614	<	Entry<K,V> lastReturned = null;
1615	<	Entry<K,V> next;
1694	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1695	>	private static final long serialVersionUID = 912986545866124060L;
1696
1697	<	PrivateEntryIterator(Entry<K,V> first) {
1698	<	next = first;
1697	>	AscendingSubMap(TreeMap<K,V> m,
1698	>	boolean fromStart, K lo, boolean loInclusive,
1699	>	boolean toEnd, K hi, boolean hiInclusive) {
1700	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1701		}
1702
1703	<	public boolean hasNext() {
1704	<	return next != null;
1703	>	public Comparator<? super K> comparator() {
1704	>	return m.comparator();
1705		}
1706
1707	<	Entry<K,V> nextEntry() {
1708	<	if (next == null)
1709	<	throw new NoSuchElementException();
1710	<	if (modCount != expectedModCount)
1711	<	throw new ConcurrentModificationException();
1712	<	lastReturned = next;
1713	<	next = successor(next);
1714	<	return lastReturned;
1707	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1708	>	K toKey, boolean toInclusive) {
1709	>	if (!inRange(fromKey, fromInclusive))
1710	>	throw new IllegalArgumentException("fromKey out of range");
1711	>	if (!inRange(toKey, toInclusive))
1712	>	throw new IllegalArgumentException("toKey out of range");
1713	>	return new AscendingSubMap(m,
1714	>	false, fromKey, fromInclusive,
1715	>	false, toKey, toInclusive);
1716		}
1717
1718	<	public void remove() {
1719	<	if (lastReturned == null)
1720	<	throw new IllegalStateException();
1721	<	if (modCount != expectedModCount)
1722	<	throw new ConcurrentModificationException();
1723	<	if (lastReturned.left != null && lastReturned.right != null)
1641	<	next = lastReturned;
1642	<	deleteEntry(lastReturned);
1643	<	expectedModCount++;
1644	<	lastReturned = null;
1718	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1719	>	if (!inRange(toKey, inclusive))
1720	>	throw new IllegalArgumentException("toKey out of range");
1721	>	return new AscendingSubMap(m,
1722	>	fromStart, lo, loInclusive,
1723	>	false, toKey, inclusive);
1724		}
1646	–	}
1725
1726	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1727	<	EntryIterator(Entry<K,V> first) {
1728	<	super(first);
1726	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1727	>	if (!inRange(fromKey, inclusive))
1728	>	throw new IllegalArgumentException("fromKey out of range");
1729	>	return new AscendingSubMap(m,
1730	>	false, fromKey, inclusive,
1731	>	toEnd, hi, hiInclusive);
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, loInclusive,
1740	>	toEnd, hi, hiInclusive));
1741		}
1656	–	}
1742
1743	<	class KeyIterator extends PrivateEntryIterator<K> {
1744	<	KeyIterator(Entry<K,V> first) {
1660	<	super(first);
1743	>	Iterator<K> keyIterator() {
1744	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1745		}
1662	–	public K next() {
1663	–	return nextEntry().key;
1664	–	}
1665	–	}
1746
1747	<	class ValueIterator extends PrivateEntryIterator<V> {
1748	<	ValueIterator(Entry<K,V> first) {
1669	<	super(first);
1670	<	}
1671	<	public V next() {
1672	<	return nextEntry().value;
1747	>	Iterator<K> descendingKeyIterator() {
1748	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1749		}
1674	–	}
1750
1751	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1752	<	private final K firstExcludedKey;
1753	<
1754	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1680	<	super(first);
1681	<	firstExcludedKey = (firstExcluded == null
1682	<	? null
1683	<	: firstExcluded.key);
1751	>	final class AscendingEntrySetView extends EntrySetView {
1752	>	public Iterator<Map.Entry<K,V>> iterator() {
1753	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1754	>	}
1755		}
1756
1757	<	public boolean hasNext() {
1758	<	return next != null && next.key != firstExcludedKey;
1757	>	public Set<Map.Entry<K,V>> entrySet() {
1758	>	EntrySetView es = entrySetView;
1759	>	return (es != null) ? es : new AscendingEntrySetView();
1760		}
1761
1762	<	public Map.Entry<K,V> next() {
1763	<	if (next == null \|\| next.key == firstExcludedKey)
1764	<	throw new NoSuchElementException();
1765	<	return nextEntry();
1766	<	}
1762	>	TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1763	>	TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1764	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1765	>	TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1766	>	TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1767	>	TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1768		}
1769
1697	–
1770		/**
1771	<	* Base for Descending Iterators.
1771	>	* @serial include
1772		*/
1773	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1774	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1775	<	super(first);
1773	>	static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1774	>	private static final long serialVersionUID = 912986545866120460L;
1775	>	DescendingSubMap(TreeMap<K,V> m,
1776	>	boolean fromStart, K lo, boolean loInclusive,
1777	>	boolean toEnd, K hi, boolean hiInclusive) {
1778	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1779		}
1780
1781	<	Entry<K,V> nextEntry() {
1782	<	if (next == null)
1708	<	throw new NoSuchElementException();
1709	<	if (modCount != expectedModCount)
1710	<	throw new ConcurrentModificationException();
1711	<	lastReturned = next;
1712	<	next = predecessor(next);
1713	<	return lastReturned;
1714	<	}
1715	<	}
1781	>	private final Comparator<? super K> reverseComparator =
1782	>	Collections.reverseOrder(m.comparator);
1783
1784	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1785	<	DescendingEntryIterator(Entry<K,V> first) {
1719	<	super(first);
1784	>	public Comparator<? super K> comparator() {
1785	>	return reverseComparator;
1786		}
1787	<	public Map.Entry<K,V> next() {
1788	<	return nextEntry();
1787	>
1788	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1789	>	K toKey, boolean toInclusive) {
1790	>	if (!inRange(fromKey, fromInclusive))
1791	>	throw new IllegalArgumentException("fromKey out of range");
1792	>	if (!inRange(toKey, toInclusive))
1793	>	throw new IllegalArgumentException("toKey out of range");
1794	>	return new DescendingSubMap(m,
1795	>	false, toKey, toInclusive,
1796	>	false, fromKey, fromInclusive);
1797		}
1724	–	}
1798
1799	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1800	<	DescendingKeyIterator(Entry<K,V> first) {
1801	<	super(first);
1799	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1800	>	if (!inRange(toKey, inclusive))
1801	>	throw new IllegalArgumentException("toKey out of range");
1802	>	return new DescendingSubMap(m,
1803	>	false, toKey, inclusive,
1804	>	toEnd, hi, hiInclusive);
1805		}
1806	<	public K next() {
1807	<	return nextEntry().key;
1806	>
1807	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1808	>	if (!inRange(fromKey, inclusive))
1809	>	throw new IllegalArgumentException("fromKey out of range");
1810	>	return new DescendingSubMap(m,
1811	>	fromStart, lo, loInclusive,
1812	>	false, fromKey, inclusive);
1813		}
1733	–	}
1814
1815	+	public NavigableMap<K,V> descendingMap() {
1816	+	NavigableMap<K,V> mv = descendingMapView;
1817	+	return (mv != null) ? mv :
1818	+	(descendingMapView =
1819	+	new AscendingSubMap(m,
1820	+	fromStart, lo, loInclusive,
1821	+	toEnd, hi, hiInclusive));
1822	+	}
1823
1824	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1825	<	private final K lastExcludedKey;
1824	>	Iterator<K> keyIterator() {
1825	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1826	>	}
1827
1828	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1829	<	super(last);
1741	<	lastExcludedKey = (lastExcluded == null
1742	<	? null
1743	<	: lastExcluded.key);
1828	>	Iterator<K> descendingKeyIterator() {
1829	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1830		}
1831
1832	<	public boolean hasNext() {
1833	<	return next != null && next.key != lastExcludedKey;
1832	>	final class DescendingEntrySetView extends EntrySetView {
1833	>	public Iterator<Map.Entry<K,V>> iterator() {
1834	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1835	>	}
1836		}
1837
1838	<	public Map.Entry<K,V> next() {
1839	<	if (next == null \|\| next.key == lastExcludedKey)
1840	<	throw new NoSuchElementException();
1753	<	return nextEntry();
1838	>	public Set<Map.Entry<K,V>> entrySet() {
1839	>	EntrySetView es = entrySetView;
1840	>	return (es != null) ? es : new DescendingEntrySetView();
1841		}
1842
1843	+	TreeMap.Entry<K,V> subLowest() { return absHighest(); }
1844	+	TreeMap.Entry<K,V> subHighest() { return absLowest(); }
1845	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1846	+	TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
1847	+	TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
1848	+	TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
1849		}
1850
1758	–
1851		/**
1852	<	* Compares two keys using the correct comparison method for this TreeMap.
1852	>	* This class exists solely for the sake of serialization
1853	>	* compatibility with previous releases of TreeMap that did not
1854	>	* support NavigableMap. It translates an old-version SubMap into
1855	>	* a new-version AscendingSubMap. This class is never otherwise
1856	>	* used.
1857	>	*
1858	>	* @serial include
1859		*/
1860	<	private int compare(K k1, K k2) {
1861	<	return (comparator==null ? ((Comparable</-/K>)k1).compareTo(k2)
1862	<	: comparator.compare((K)k1, (K)k2));
1860	>	private class SubMap extends AbstractMap<K,V>
1861	>	implements SortedMap<K,V>, java.io.Serializable {
1862	>	private static final long serialVersionUID = -6520786458950516097L;
1863	>	private boolean fromStart = false, toEnd = false;
1864	>	private K fromKey, toKey;
1865	>	private Object readResolve() {
1866	>	return new AscendingSubMap(TreeMap.this,
1867	>	fromStart, fromKey, true,
1868	>	toEnd, toKey, false);
1869	>	}
1870	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1871	>	public K lastKey() { throw new InternalError(); }
1872	>	public K firstKey() { throw new InternalError(); }
1873	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1874	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1875	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1876	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1877		}
1878
1879	<	/**
1880	<	* Test two values for equality. Differs from o1.equals(o2) only in
1769	<	* that it copes with <tt>null</tt> o1 properly.
1770	<	*/
1771	<	private static boolean valEquals(Object o1, Object o2) {
1772	<	return (o1==null ? o2==null : o1.equals(o2));
1773	<	}
1879	>
1880	>	// Red-black mechanics
1881
1882		private static final boolean RED = false;
1883		private static final boolean BLACK = true;
#	Line 1780 \| Line 1887 \| public class TreeMap<K,V>
1887		* user (see Map.Entry).
1888		*/
1889
1890	<	static class Entry<K,V> implements Map.Entry<K,V> {
1891	<	K key;
1890	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1891	>	K key;
1892		V value;
1893		Entry<K,V> left = null;
1894		Entry<K,V> right = null;
#	Line 1801 \| Line 1908 \| public class TreeMap<K,V>
1908		/**
1909		* Returns the key.
1910		*
1911	<	* @return the key.
1911	>	* @return the key
1912		*/
1913		public K getKey() {
1914		return key;
#	Line 1810 \| Line 1917 \| public class TreeMap<K,V>
1917		/**
1918		* Returns the value associated with the key.
1919		*
1920	<	* @return the value associated with the key.
1920	>	* @return the value associated with the key
1921		*/
1922		public V getValue() {
1923		return value;
#	Line 1821 \| Line 1928 \| public class TreeMap<K,V>
1928		* value.
1929		*
1930		* @return the value associated with the key before this method was
1931	<	* called.
1931	>	* called
1932		*/
1933		public V setValue(V value) {
1934		V oldValue = this.value;
#	Line 1832 \| Line 1939 \| public class TreeMap<K,V>
1939		public boolean equals(Object o) {
1940		if (!(o instanceof Map.Entry))
1941		return false;
1942	<	Map.Entry e = (Map.Entry)o;
1942	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1943
1944		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1945		}
#	Line 1852 \| Line 1959 \| public class TreeMap<K,V>
1959		* Returns the first Entry in the TreeMap (according to the TreeMap's
1960		* key-sort function). Returns null if the TreeMap is empty.
1961		*/
1962	<	private Entry<K,V> getFirstEntry() {
1962	>	final Entry<K,V> getFirstEntry() {
1963		Entry<K,V> p = root;
1964		if (p != null)
1965		while (p.left != null)
#	Line 1864 \| Line 1971 \| public class TreeMap<K,V>
1971		* Returns the last Entry in the TreeMap (according to the TreeMap's
1972		* key-sort function). Returns null if the TreeMap is empty.
1973		*/
1974	<	private Entry<K,V> getLastEntry() {
1974	>	final Entry<K,V> getLastEntry() {
1975		Entry<K,V> p = root;
1976		if (p != null)
1977		while (p.right != null)
#	Line 1875 \| Line 1982 \| public class TreeMap<K,V>
1982		/**
1983		* Returns the successor of the specified Entry, or null if no such.
1984		*/
1985	<	private Entry<K,V> successor(Entry<K,V> t) {
1985	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1986		if (t == null)
1987		return null;
1988		else if (t.right != null) {
#	Line 1897 \| Line 2004 \| public class TreeMap<K,V>
2004		/**
2005		* Returns the predecessor of the specified Entry, or null if no such.
2006		*/
2007	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2007	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2008		if (t == null)
2009		return null;
2010		else if (t.left != null) {
#	Line 1936 \| Line 2043 \| public class TreeMap<K,V>
2043
2044		private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2045		if (p != null)
2046	<	p.color = c;
2046	>	p.color = c;
2047		}
2048
2049		private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
#	Line 1947 \| Line 2054 \| public class TreeMap<K,V>
2054		return (p == null) ? null: p.right;
2055		}
2056
2057	<	/ From CLR /
2057	>	/** From CLR */
2058		private void rotateLeft(Entry<K,V> p) {
2059	<	Entry<K,V> r = p.right;
2060	<	p.right = r.left;
2061	<	if (r.left != null)
2062	<	r.left.parent = p;
2063	<	r.parent = p.parent;
2064	<	if (p.parent == null)
2065	<	root = r;
2066	<	else if (p.parent.left == p)
2067	<	p.parent.left = r;
2068	<	else
2069	<	p.parent.right = r;
2070	<	r.left = p;
2071	<	p.parent = r;
2059	>	if (p != null) {
2060	>	Entry<K,V> r = p.right;
2061	>	p.right = r.left;
2062	>	if (r.left != null)
2063	>	r.left.parent = p;
2064	>	r.parent = p.parent;
2065	>	if (p.parent == null)
2066	>	root = r;
2067	>	else if (p.parent.left == p)
2068	>	p.parent.left = r;
2069	>	else
2070	>	p.parent.right = r;
2071	>	r.left = p;
2072	>	p.parent = r;
2073	>	}
2074		}
2075
2076	<	/ From CLR /
2076	>	/** From CLR */
2077		private void rotateRight(Entry<K,V> p) {
2078	<	Entry<K,V> l = p.left;
2079	<	p.left = l.right;
2080	<	if (l.right != null) l.right.parent = p;
2081	<	l.parent = p.parent;
2082	<	if (p.parent == null)
2083	<	root = l;
2084	<	else if (p.parent.right == p)
2085	<	p.parent.right = l;
2086	<	else p.parent.left = l;
2087	<	l.right = p;
2088	<	p.parent = l;
2078	>	if (p != null) {
2079	>	Entry<K,V> l = p.left;
2080	>	p.left = l.right;
2081	>	if (l.right != null) l.right.parent = p;
2082	>	l.parent = p.parent;
2083	>	if (p.parent == null)
2084	>	root = l;
2085	>	else if (p.parent.right == p)
2086	>	p.parent.right = l;
2087	>	else p.parent.left = l;
2088	>	l.right = p;
2089	>	p.parent = l;
2090	>	}
2091		}
2092
2093	<
1983	<	/ From CLR /
2093	>	/** From CLR */
2094		private void fixAfterInsertion(Entry<K,V> x) {
2095		x.color = RED;
2096
#	Line 1999 \| Line 2109 \| public class TreeMap<K,V>
2109		}
2110		setColor(parentOf(x), BLACK);
2111		setColor(parentOf(parentOf(x)), RED);
2112	<	if (parentOf(parentOf(x)) != null)
2003	<	rotateRight(parentOf(parentOf(x)));
2112	>	rotateRight(parentOf(parentOf(x)));
2113		}
2114		} else {
2115		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2014 \| Line 2123 \| public class TreeMap<K,V>
2123		x = parentOf(x);
2124		rotateRight(x);
2125		}
2126	<	setColor(parentOf(x), BLACK);
2126	>	setColor(parentOf(x), BLACK);
2127		setColor(parentOf(parentOf(x)), RED);
2128	<	if (parentOf(parentOf(x)) != null)
2020	<	rotateLeft(parentOf(parentOf(x)));
2128	>	rotateLeft(parentOf(parentOf(x)));
2129		}
2130		}
2131		}
#	Line 2027 \| Line 2135 \| public class TreeMap<K,V>
2135		/**
2136		* Delete node p, and then rebalance the tree.
2137		*/
2030	–
2138		private void deleteEntry(Entry<K,V> p) {
2139	<	decrementSize();
2139	>	modCount++;
2140	>	size--;
2141
2142		// If strictly internal, copy successor's element to p and then make p
2143		// point to successor.
#	Line 2075 \| Line 2183 \| public class TreeMap<K,V>
2183		}
2184		}
2185
2186	<	/ From CLR /
2186	>	/** From CLR */
2187		private void fixAfterDeletion(Entry<K,V> x) {
2188		while (x != root && colorOf(x) == BLACK) {
2189		if (x == leftOf(parentOf(x))) {
#	Line 2090 \| Line 2198 \| public class TreeMap<K,V>
2198
2199		if (colorOf(leftOf(sib)) == BLACK &&
2200		colorOf(rightOf(sib)) == BLACK) {
2201	<	setColor(sib, RED);
2201	>	setColor(sib, RED);
2202		x = parentOf(x);
2203		} else {
2204		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2117 \| Line 2225 \| public class TreeMap<K,V>
2225
2226		if (colorOf(rightOf(sib)) == BLACK &&
2227		colorOf(leftOf(sib)) == BLACK) {
2228	<	setColor(sib, RED);
2228	>	setColor(sib, RED);
2229		x = parentOf(x);
2230		} else {
2231		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 2160 \| Line 2268 \| public class TreeMap<K,V>
2268		// Write out size (number of Mappings)
2269		s.writeInt(size);
2270
2163	–	Set<Map.Entry<K,V>> es = entrySet();
2271		// Write out keys and values (alternating)
2272	<	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
2272	>	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2273		Map.Entry<K,V> e = i.next();
2274		s.writeObject(e.getKey());
2275		s.writeObject(e.getValue());
2276		}
2277		}
2278
2172	–
2173	–
2279		/**
2280		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2281		* deserialize it).
#	Line 2186 \| Line 2291 \| public class TreeMap<K,V>
2291		buildFromSorted(size, null, s, null);
2292		}
2293
2294	<	/ Intended to be called only from TreeSet.readObject /
2294	>	/** Intended to be called only from TreeSet.readObject */
2295		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2296		throws java.io.IOException, ClassNotFoundException {
2297		buildFromSorted(size, null, s, defaultVal);
2298		}
2299
2300	<	/ Intended to be called only from TreeSet.addAll /
2301	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
2302	<	try {
2303	<	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304	<	} catch (java.io.IOException cannotHappen) {
2305	<	} catch (ClassNotFoundException cannotHappen) {
2306	<	}
2300	>	/** Intended to be called only from TreeSet.addAll */
2301	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2302	>	try {
2303	>	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304	>	} catch (java.io.IOException cannotHappen) {
2305	>	} catch (ClassNotFoundException cannotHappen) {
2306	>	}
2307		}
2308
2309
#	Line 2218 \| Line 2323 \| public class TreeMap<K,V>
2323		* to calling this method.
2324		*
2325		* @param size the number of keys (or key-value pairs) to be read from
2326	<	* the iterator or stream.
2326	>	* the iterator or stream
2327		* @param it If non-null, new entries are created from entries
2328		* or keys read from this iterator.
2329		* @param str If non-null, new entries are created from keys and
#	Line 2232 \| Line 2337 \| public class TreeMap<K,V>
2337		* @throws ClassNotFoundException propagated from readObject.
2338		* This cannot occur if str is null.
2339		*/
2340	<	private
2341	<	void buildFromSorted(int size, Iterator it,
2342	<	java.io.ObjectInputStream str,
2238	<	V defaultVal)
2340	>	private void buildFromSorted(int size, Iterator it,
2341	>	java.io.ObjectInputStream str,
2342	>	V defaultVal)
2343		throws java.io.IOException, ClassNotFoundException {
2344		this.size = size;
2345	<	root =
2346	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
2243	<	it, str, defaultVal);
2345	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2346	>	it, str, defaultVal);
2347		}
2348
2349		/**
2350		* Recursive "helper method" that does the real work of the
2351	<	* of the previous method. Identically named parameters have
2351	>	* previous method. Identically named parameters have
2352		* identical definitions. Additional parameters are documented below.
2353		* It is assumed that the comparator and size fields of the TreeMap are
2354		* already set prior to calling this method. (It ignores both fields.)
#	Line 2253 \| Line 2356 \| public class TreeMap<K,V>
2356		* @param level the current level of tree. Initial call should be 0.
2357		* @param lo the first element index of this subtree. Initial should be 0.
2358		* @param hi the last element index of this subtree. Initial should be
2359	<	* size-1.
2359	>	* size-1.
2360		* @param redLevel the level at which nodes should be red.
2361		* Must be equal to computeRedLevel for tree of this size.
2362		*/
2363		private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2364	<	int redLevel,
2365	<	Iterator it,
2366	<	java.io.ObjectInputStream str,
2367	<	V defaultVal)
2364	>	int redLevel,
2365	>	Iterator it,
2366	>	java.io.ObjectInputStream str,
2367	>	V defaultVal)
2368		throws java.io.IOException, ClassNotFoundException {
2369		/*
2370		* Strategy: The root is the middlemost element. To get to it, we
#	Line 2277 \| Line 2380 \| public class TreeMap<K,V>
2380
2381		if (hi < lo) return null;
2382
2383	<	int mid = (lo + hi) / 2;
2383	>	int mid = (lo + hi) >>> 1;
2384
2385		Entry<K,V> left = null;
2386		if (lo < mid)
2387		left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2388	<	it, str, defaultVal);
2388	>	it, str, defaultVal);
2389
2390		// extract key and/or value from iterator or stream
2391		K key;
#	Line 2314 \| Line 2417 \| public class TreeMap<K,V>
2417
2418		if (mid < hi) {
2419		Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2420	<	it, str, defaultVal);
2420	>	it, str, defaultVal);
2421		middle.right = right;
2422		right.parent = middle;
2423		}
#	Line 2337 \| Line 2440 \| public class TreeMap<K,V>
2440		level++;
2441		return level;
2442		}
2340	–
2443		}

Diff Legend

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

Comparing jsr166/src/main/java/util/TreeMap.java (file contents): Revision 1.11 by jsr166, Mon May 2 16:35:52 2005 UTC vs. Revision 1.46 by jsr166, Sun May 18 23:59:57 2008 UTC

Diff Legend

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.11 by jsr166, Mon May 2 16:35:52 2005 UTC vs.
Revision 1.46 by jsr166, Sun May 18 23:59:57 2008 UTC