ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/TreeMap.java

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

Diff Legend

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