[ViewVC] Diff of: 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.28 by dl, Wed Apr 19 15:07:14 2006 UTC

#	Line 1 \| Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
8	<	package java.util;
9	<
8	>	package java.util;
9
10		/**
11	<	* Red-Black tree based implementation of the <tt>NavigableMap</tt> interface.
12	<	* This class guarantees that the map will be in ascending key order, sorted
13	<	* according to the <i>natural order</i> for the key's class (see
14	<	* <tt>Comparable</tt>), or by the comparator provided at creation time,
16	<	* depending on which constructor is used.<p>
11	>	* A Red-Black tree based {@link NavigableMap} implementation.
12	>	* The map is sorted according to the {@linkplain Comparable natural
13	>	* ordering} of its keys, or by a {@link Comparator} provided at map
14	>	* creation time, depending on which constructor is used.
15		*
16	<	* This implementation provides guaranteed log(n) time cost for the
16	>	* <p>This implementation provides guaranteed log(n) time cost for the
17		* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
18		* operations. Algorithms are adaptations of those in Cormen, Leiserson, and
19	<	* Rivest's <I>Introduction to Algorithms</I>.<p>
19	>	* Rivest's <I>Introduction to Algorithms</I>.
20		*
21	<	* Note that the ordering maintained by a sorted map (whether or not an
21	>	* <p>Note that the ordering maintained by a sorted map (whether or not an
22		* explicit comparator is provided) must be <i>consistent with equals</i> if
23		* this sorted map is to correctly implement the <tt>Map</tt> interface. (See
24		* <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
#	Line 30 \| Line 28 \| package java.util;
28		* method, so two keys that are deemed equal by this method are, from the
29		* standpoint of the sorted map, equal. The behavior of a sorted map
30		* <i>is</i> well-defined even if its ordering is inconsistent with equals; it
31	<	* just fails to obey the general contract of the <tt>Map</tt> interface.<p>
31	>	* just fails to obey the general contract of the <tt>Map</tt> interface.
32		*
33	<	* <b>Note that this implementation is not synchronized.</b> If multiple
34	<	* threads access a map concurrently, and at least one of the threads modifies
35	<	* the map structurally, it <i>must</i> be synchronized externally. (A
36	<	* structural modification is any operation that adds or deletes one or more
37	<	* mappings; merely changing the value associated with an existing key is not
38	<	* a structural modification.) This is typically accomplished by
39	<	* synchronizing on some object that naturally encapsulates the map. If no
40	<	* such object exists, the map should be "wrapped" using the
41	<	* <tt>Collections.synchronizedMap</tt> method. This is best done at creation
42	<	* time, to prevent accidental unsynchronized access to the map:
43	<	* <pre>
44	<	* Map m = Collections.synchronizedMap(new TreeMap(...));
45	<	* </pre><p>
33	>	* <p><strong>Note that this implementation is not synchronized.</strong>
34	>	* If multiple threads access a map concurrently, and at least one of the
35	>	* threads modifies the map structurally, it <i>must</i> be synchronized
36	>	* externally. (A structural modification is any operation that adds or
37	>	* deletes one or more mappings; merely changing the value associated
38	>	* with an existing key is not a structural modification.) This is
39	>	* typically accomplished by synchronizing on some object that naturally
40	>	* encapsulates the map.
41	>	* If no such object exists, the map should be "wrapped" using the
42	>	* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
43	>	* method. This is best done at creation time, to prevent accidental
44	>	* unsynchronized access to the map: <pre>
45	>	* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
46		*
47	<	* The iterators returned by all of this class's "collection view methods" are
47	>	* <p>The iterators returned by the <tt>iterator</tt> method of the collections
48	>	* returned by all of this class's "collection view methods" are
49		* <i>fail-fast</i>: if the map is structurally modified at any time after the
50		* iterator is created, in any way except through the iterator's own
51	<	* <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
52	<	* <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
51	>	* <tt>remove</tt> method, the iterator will throw a {@link
52	>	* ConcurrentModificationException}. Thus, in the face of concurrent
53		* modification, the iterator fails quickly and cleanly, rather than risking
54	<	* arbitrary, non-deterministic behavior at an undetermined time in the
56	<	* future.
54	>	* arbitrary, non-deterministic behavior at an undetermined time in the future.
55		*
56		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
57		* as it is, generally speaking, impossible to make any hard guarantees in the
#	Line 61 \| Line 59 \| package java.util;
59		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
60		* Therefore, it would be wrong to write a program that depended on this
61		* exception for its correctness: <i>the fail-fast behavior of iterators
62	<	* should be used only to detect bugs.</i><p>
62	>	* should be used only to detect bugs.</i>
63		*
64		* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
65		* and its views represent snapshots of mappings at the time they were
#	Line 73 \| Line 71 \| package java.util;
71		* <a href="{@docRoot}/../guide/collections/index.html">
72		* Java Collections Framework</a>.
73		*
74	+	* @param <K> the type of keys maintained by this map
75	+	* @param <V> the type of mapped values
76	+	*
77		* @author Josh Bloch and Doug Lea
78		* @version %I%, %G%
79		* @see Map
#	Line 81 \| Line 82 \| package java.util;
82		* @see Comparable
83		* @see Comparator
84		* @see Collection
84	–	* @see Collections#synchronizedMap(Map)
85		* @since 1.2
86		*/
87
#	Line 90 \| Line 90 \| public class TreeMap<K,V>
90		implements NavigableMap<K,V>, Cloneable, java.io.Serializable
91		{
92		/**
93	<	* The Comparator used to maintain order in this TreeMap, or
94	<	* null if this TreeMap uses its elements natural ordering.
93	>	* The comparator used to maintain order in this tree map, or
94	>	* null if it uses the natural ordering of its keys.
95		*
96		* @serial
97		*/
#	Line 109 \| Line 109 \| public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
112	+	/**
113	+	* A sentinel to indicate that an endpoint of a submap is not bounded.
114	+	* It is used to generate head maps, tail maps, and descending views
115	+	* of the entire backing map. The sentinel must be serializable,
116	+	* requiring a little class to express.
117	+	*/
118	+	private static class Unbounded implements java.io.Serializable {}
119	+	private static final Unbounded UNBOUNDED = new Unbounded();
120	+
121		private void incrementSize() { modCount++; size++; }
122		private void decrementSize() { modCount++; size--; }
123
124		/**
125	<	* Constructs a new, empty map, sorted according to the keys' natural
126	<	* order. All keys inserted into the map must implement the
127	<	* <tt>Comparable</tt> interface. Furthermore, all such keys must be
128	<	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
129	<	* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
130	<	* map. If the user attempts to put a key into the map that violates this
131	<	* constraint (for example, the user attempts to put a string key into a
132	<	* map whose keys are integers), the <tt>put(Object key, Object
133	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
134	<	*
126	<	* @see Comparable
125	>	* Constructs a new, empty tree map, using the natural ordering of its
126	>	* keys. All keys inserted into the map must implement the {@link
127	>	* Comparable} interface. Furthermore, all such keys must be
128	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
129	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
130	>	* <tt>k2</tt> in the map. If the user attempts to put a key into the
131	>	* map that violates this constraint (for example, the user attempts to
132	>	* put a string key into a map whose keys are integers), the
133	>	* <tt>put(Object key, Object value)</tt> call will throw a
134	>	* <tt>ClassCastException</tt>.
135		*/
136		public TreeMap() {
137		}
138
139		/**
140	<	* Constructs a new, empty map, sorted according to the given comparator.
141	<	* All keys inserted into the map must be <i>mutually comparable</i> by
142	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
143	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
144	<	* <tt>k2</tt> in the map. If the user attempts to put a key into the
145	<	* map that violates this constraint, the <tt>put(Object key, Object
146	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
147	<	*
148	<	* @param c the comparator that will be used to sort this map. A
149	<	* <tt>null</tt> value indicates that the keys' <i>natural
150	<	* ordering</i> should be used.
151	<	*/
152	<	public TreeMap(Comparator<? super K> c) {
153	<	this.comparator = c;
140	>	* Constructs a new, empty tree map, ordered according to the given
141	>	* comparator. All keys inserted into the map must be <i>mutually
142	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
143	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
144	>	* <tt>k1</tt> and <tt>k2</tt> in the map. If the user attempts to put
145	>	* a key into the map that violates this constraint, the <tt>put(Object
146	>	* key, Object value)</tt> call will throw a
147	>	* <tt>ClassCastException</tt>.
148	>	*
149	>	* @param comparator the comparator that will be used to order this map.
150	>	* If <tt>null</tt>, the {@linkplain Comparable natural
151	>	* ordering} of the keys will be used.
152	>	*/
153	>	public TreeMap(Comparator<? super K> comparator) {
154	>	this.comparator = comparator;
155		}
156
157		/**
158	<	* Constructs a new map containing the same mappings as the given map,
159	<	* sorted according to the keys' <i>natural order</i>. All keys inserted
160	<	* into the new map must implement the <tt>Comparable</tt> interface.
161	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
162	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
163	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map. This method
164	<	* runs in n*log(n) time.
165	<	*
166	<	* @param m the map whose mappings are to be placed in this map.
167	<	* @throws ClassCastException the keys in t are not Comparable, or
168	<	* are not mutually comparable.
169	<	* @throws NullPointerException if the specified map is null.
158	>	* Constructs a new tree map containing the same mappings as the given
159	>	* map, ordered according to the <i>natural ordering</i> of its keys.
160	>	* All keys inserted into the new map must implement the {@link
161	>	* Comparable} interface. Furthermore, all such keys must be
162	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
163	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
164	>	* <tt>k2</tt> in the map. This method runs in n*log(n) time.
165	>	*
166	>	* @param m the map whose mappings are to be placed in this map
167	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
168	>	* or are not mutually comparable
169	>	* @throws NullPointerException if the specified map is null
170		*/
171		public TreeMap(Map<? extends K, ? extends V> m) {
172		putAll(m);
173		}
174
175		/**
176	<	* Constructs a new map containing the same mappings as the given
177	<	* <tt>SortedMap</tt>, sorted according to the same ordering. This method
178	<	* runs in linear time.
176	>	* Constructs a new tree map containing the same mappings and
177	>	* using the same ordering as the specified sorted map. This
178	>	* method runs in linear time.
179		*
180		* @param m the sorted map whose mappings are to be placed in this map,
181	<	* and whose comparator is to be used to sort this map.
182	<	* @throws NullPointerException if the specified sorted map is null.
181	>	* and whose comparator is to be used to sort this map
182	>	* @throws NullPointerException if the specified map is null
183		*/
184		public TreeMap(SortedMap<K, ? extends V> m) {
185		comparator = m.comparator();
#	Line 187 \| Line 196 \| public class TreeMap<K,V>
196		/**
197		* Returns the number of key-value mappings in this map.
198		*
199	<	* @return the number of key-value mappings in this map.
199	>	* @return the number of key-value mappings in this map
200		*/
201		public int size() {
202		return size;
#	Line 197 \| Line 206 \| public class TreeMap<K,V>
206		* Returns <tt>true</tt> if this map contains a mapping for the specified
207		* key.
208		*
209	<	* @param key key whose presence in this map is to be tested.
201	<	*
209	>	* @param key key whose presence in this map is to be tested
210		* @return <tt>true</tt> if this map contains a mapping for the
211	<	* specified key.
212	<	* @throws ClassCastException if the key cannot be compared with the keys
213	<	* currently in the map.
214	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
215	<	* natural ordering, or its comparator does not tolerate
216	<	* <tt>null</tt> keys.
211	>	* specified key
212	>	* @throws ClassCastException if the specified key cannot be compared
213	>	* with the keys currently in the map
214	>	* @throws NullPointerException if the specified key is null
215	>	* and this map uses natural ordering, or its comparator
216	>	* does not permit null keys
217		*/
218		public boolean containsKey(Object key) {
219		return getEntry(key) != null;
#	Line 216 \| Line 224 \| public class TreeMap<K,V>
224		* specified value. More formally, returns <tt>true</tt> if and only if
225		* this map contains at least one mapping to a value <tt>v</tt> such
226		* that <tt>(value==null ? v==null : value.equals(v))</tt>. This
227	<	* operation will probably require time linear in the Map size for most
228	<	* implementations of Map.
227	>	* operation will probably require time linear in the map size for
228	>	* most implementations.
229		*
230	<	* @param value value whose presence in this Map is to be tested.
231	<	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
232	<	* <tt>false</tt> otherwise.
230	>	* @param value value whose presence in this map is to be tested
231	>	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
232	>	* <tt>false</tt> otherwise
233		* @since 1.2
234		*/
235		public boolean containsValue(Object value) {
#	Line 250 \| Line 258 \| public class TreeMap<K,V>
258		}
259
260		/**
261	<	* Returns the value to which this map maps the specified key. Returns
262	<	* <tt>null</tt> if the map contains no mapping for this key. A return
255	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
256	<	* map contains no mapping for the key; it's also possible that the map
257	<	* explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
258	<	* operation may be used to distinguish these two cases.
259	<	*
260	<	* @param key key whose associated value is to be returned.
261	<	* @return the value to which this map maps the specified key, or
262	<	* <tt>null</tt> if the map contains no mapping for the key.
263	<	* @throws ClassCastException key cannot be compared with the keys
264	<	* currently in the map.
265	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
266	<	* natural ordering, or its comparator does not tolerate
267	<	* <tt>null</tt> keys.
261	>	* Returns the value to which the specified key is mapped,
262	>	* or {@code null} if this map contains no mapping for the key.
263		*
264	<	* @see #containsKey(Object)
264	>	* <p>More formally, if this map contains a mapping from a key
265	>	* {@code k} to a value {@code v} such that {@code key} compares
266	>	* equal to {@code k} according to the map's ordering, then this
267	>	* method returns {@code v}; otherwise it returns {@code null}.
268	>	* (There can be at most one such mapping.)
269	>	*
270	>	* <p>A return value of {@code null} does not <i>necessarily</i>
271	>	* indicate that the map contains no mapping for the key; it's also
272	>	* possible that the map explicitly maps the key to {@code null}.
273	>	* The {@link #containsKey containsKey} operation may be used to
274	>	* distinguish these two cases.
275	>	*
276	>	* @throws ClassCastException if the specified key cannot be compared
277	>	* with the keys currently in the map
278	>	* @throws NullPointerException if the specified key is null
279	>	* and this map uses natural ordering, or its comparator
280	>	* does not permit null keys
281		*/
282		public V get(Object key) {
283		Entry<K,V> p = getEntry(key);
284		return (p==null ? null : p.value);
285		}
286
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	–	*/
287		public Comparator<? super K> comparator() {
288		return comparator;
289		}
290
291		/**
292	<	* 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.
292	>	* @throws NoSuchElementException {@inheritDoc}
293		*/
294		public K firstKey() {
295		return key(getFirstEntry());
296		}
297
298		/**
299	<	* 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.
299	>	* @throws NoSuchElementException {@inheritDoc}
300		*/
301		public K lastKey() {
302		return key(getLastEntry());
303		}
304
305		/**
306	<	* Copies all of the mappings from the specified map to this map. These
307	<	* mappings replace any mappings that this map had for any of the keys
308	<	* currently in the specified map.
309	<	*
310	<	* @param map mappings to be stored in this map.
311	<	* @throws ClassCastException class of a key or value in the specified
312	<	* map prevents it from being stored in this map.
313	<	*
314	<	* @throws NullPointerException if the given map is <tt>null</tt> or
315	<	* this map does not permit <tt>null</tt> keys and a
318	<	* key in the specified map is <tt>null</tt>.
306	>	* Copies all of the mappings from the specified map to this map.
307	>	* These mappings replace any mappings that this map had for any
308	>	* of the keys currently in the specified map.
309	>	*
310	>	* @param map mappings to be stored in this map
311	>	* @throws ClassCastException if the class of a key or value in
312	>	* the specified map prevents it from being stored in this map
313	>	* @throws NullPointerException if the specified map is null or
314	>	* the specified map contains a null key and this map does not
315	>	* permit null keys
316		*/
317		public void putAll(Map<? extends K, ? extends V> map) {
318		int mapSize = map.size();
#	Line 340 \| Line 337 \| public class TreeMap<K,V>
337		* does not contain an entry for the key.
338		*
339		* @return this map's entry for the given key, or <tt>null</tt> if the map
340	<	* does not contain an entry for the key.
341	<	* @throws ClassCastException if the key cannot be compared with the keys
342	<	* currently in the map.
343	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
344	<	* natural order, or its comparator does not tolerate *
345	<	* <tt>null</tt> keys.
340	>	* does not contain an entry for the key
341	>	* @throws ClassCastException if the specified key cannot be compared
342	>	* with the keys currently in the map
343	>	* @throws NullPointerException if the specified key is null
344	>	* and this map uses natural ordering, or its comparator
345	>	* does not permit null keys
346		*/
347		private Entry<K,V> getEntry(Object key) {
348		// Offload comparator-based version for sake of performance
349		if (comparator != null)
350		return getEntryUsingComparator(key);
351	<	Comparable<K> k = (Comparable<K>) key;
351	>	if (key == null)
352	>	throw new NullPointerException();
353	>	Comparable<? super K> k = (Comparable<? super K>) key;
354		Entry<K,V> p = root;
355		while (p != null) {
356		int cmp = k.compareTo(p.key);
#	Line 525 \| Line 524 \| public class TreeMap<K,V>
524		}
525
526		/**
527	<	* Returns the key corresponding to the specified Entry. Throw
528	<	* NoSuchElementException if the Entry is <tt>null</tt>.
527	>	* Returns the key corresponding to the specified Entry.
528	>	* @throws NoSuchElementException if the Entry is null
529		*/
530		private static <K> K key(Entry<K,?> e) {
531		if (e==null)
#	Line 536 \| Line 535 \| public class TreeMap<K,V>
535
536		/**
537		* Associates the specified value with the specified key in this map.
538	<	* If the map previously contained a mapping for this key, the old
538	>	* If the map previously contained a mapping for the key, the old
539		* value is replaced.
540		*
541	<	* @param key key with which the specified value is to be associated.
542	<	* @param value value to be associated with the specified key.
541	>	* @param key key with which the specified value is to be associated
542	>	* @param value value to be associated with the specified key
543		*
544	<	* @return previous value associated with specified key, or <tt>null</tt>
545	<	* if there was no mapping for key. A <tt>null</tt> return can
546	<	* also indicate that the map previously associated <tt>null</tt>
547	<	* with the specified key.
548	<	* @throws ClassCastException key cannot be compared with the keys
549	<	* currently in the map.
550	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
551	<	* natural order, or its comparator does not tolerate
552	<	* <tt>null</tt> keys.
544	>	* @return the previous value associated with <tt>key</tt>, or
545	>	* <tt>null</tt> if there was no mapping for <tt>key</tt>.
546	>	* (A <tt>null</tt> return can also indicate that the map
547	>	* previously associated <tt>null</tt> with <tt>key</tt>.)
548	>	* @throws ClassCastException if the specified key cannot be compared
549	>	* with the keys currently in the map
550	>	* @throws NullPointerException if the specified key is null
551	>	* and this map uses natural ordering, or its comparator
552	>	* does not permit null keys
553		*/
554		public V put(K key, V value) {
555		Entry<K,V> t = root;
556
557		if (t == null) {
558	+	// TBD
559	+	// if (key == null) {
560	+	// if (comparator == null)
561	+	// throw new NullPointerException();
562	+	// comparator.compare(key, key);
563	+	// }
564		incrementSize();
565		root = new Entry<K,V>(key, value, null);
566		return null;
567	<	}
567	>	}
568
569		while (true) {
570		int cmp = compare(key, t.key);
#	Line 591 \| Line 596 \| public class TreeMap<K,V>
596		* Removes the mapping for this key from this TreeMap if present.
597		*
598		* @param key key for which mapping should be removed
599	<	* @return previous value associated with specified key, or <tt>null</tt>
600	<	* if there was no mapping for key. A <tt>null</tt> return can
601	<	* also indicate that the map previously associated
602	<	* <tt>null</tt> with the specified key.
603	<	*
604	<	* @throws ClassCastException key cannot be compared with the keys
605	<	* currently in the map.
606	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
607	<	* natural order, or its comparator does not tolerate
603	<	* <tt>null</tt> keys.
599	>	* @return the previous value associated with <tt>key</tt>, or
600	>	* <tt>null</tt> if there was no mapping for <tt>key</tt>.
601	>	* (A <tt>null</tt> return can also indicate that the map
602	>	* previously associated <tt>null</tt> with <tt>key</tt>.)
603	>	* @throws ClassCastException if the specified key cannot be compared
604	>	* with the keys currently in the map
605	>	* @throws NullPointerException if the specified key is null
606	>	* and this map uses natural ordering, or its comparator
607	>	* does not permit null keys
608		*/
609		public V remove(Object key) {
610		Entry<K,V> p = getEntry(key);
#	Line 613 \| Line 617 \| public class TreeMap<K,V>
617		}
618
619		/**
620	<	* Removes all mappings from this TreeMap.
620	>	* Removes all of the mappings from this map.
621	>	* The map will be empty after this call returns.
622		*/
623		public void clear() {
624		modCount++;
#	Line 625 \| Line 630 \| public class TreeMap<K,V>
630		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
631		* values themselves are not cloned.)
632		*
633	<	* @return a shallow copy of this Map.
633	>	* @return a shallow copy of this map
634		*/
635		public Object clone() {
636		TreeMap<K,V> clone = null;
#	Line 640 \| Line 645 \| public class TreeMap<K,V>
645		clone.size = 0;
646		clone.modCount = 0;
647		clone.entrySet = null;
648	<	clone.descendingEntrySet = null;
649	<	clone.descendingKeySet = null;
648	>	clone.navigableKeySet = null;
649	>	clone.descendingMap = null;
650
651		// Initialize clone with our mappings
652		try {
#	Line 656 \| Line 661 \| public class TreeMap<K,V>
661		// NavigableMap API methods
662
663		/**
664	<	* 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.
664	>	* @since 1.6
665		*/
666		public Map.Entry<K,V> firstEntry() {
667		Entry<K,V> e = getFirstEntry();
668	<	return (e == null)? null : new SnapshotEntry(e);
668	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
669		}
670
671		/**
672	<	* 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.
672	>	* @since 1.6
673		*/
674		public Map.Entry<K,V> lastEntry() {
675		Entry<K,V> e = getLastEntry();
676	<	return (e == null)? null : new SnapshotEntry(e);
676	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
677		}
678
679		/**
680	<	* 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.
680	>	* @since 1.6
681		*/
682		public Map.Entry<K,V> pollFirstEntry() {
683		Entry<K,V> p = getFirstEntry();
684	<	if (p == null)
684	>	if (p == null)
685		return null;
686	<	Map.Entry result = new SnapshotEntry(p);
686	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
687		deleteEntry(p);
688		return result;
689		}
690
691		/**
692	<	* 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.
692	>	* @since 1.6
693		*/
694		public Map.Entry<K,V> pollLastEntry() {
695		Entry<K,V> p = getLastEntry();
696	<	if (p == null)
696	>	if (p == null)
697		return null;
698	<	Map.Entry result = new SnapshotEntry(p);
698	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
699		deleteEntry(p);
700		return result;
701		}
702
703		/**
704	<	* Returns a key-value mapping associated with the least key
705	<	* greater than or equal to the given key, or <tt>null</tt> if
706	<	* there is no such entry.
707	<	*
708	<	* @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.
704	>	* @throws ClassCastException {@inheritDoc}
705	>	* @throws NullPointerException if the specified key is null
706	>	* and this map uses natural ordering, or its comparator
707	>	* does not permit null keys
708	>	* @since 1.6
709		*/
710	<	public Map.Entry<K,V> ceilingEntry(K key) {
711	<	Entry<K,V> e = getCeilingEntry(key);
712	<	return (e == null)? null : new SnapshotEntry(e);
710	>	public Map.Entry<K,V> lowerEntry(K key) {
711	>	Entry<K,V> e = getLowerEntry(key);
712	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
713		}
714
735	–
715		/**
716	<	* Returns least key greater than or equal to the given key, or
717	<	* <tt>null</tt> if there is no such key.
718	<	*
719	<	* @param key the key.
720	<	* @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.
716	>	* @throws ClassCastException {@inheritDoc}
717	>	* @throws NullPointerException if the specified key is null
718	>	* and this map uses natural ordering, or its comparator
719	>	* does not permit null keys
720	>	* @since 1.6
721		*/
722	<	public K ceilingKey(K key) {
723	<	Entry<K,V> e = getCeilingEntry(key);
722	>	public K lowerKey(K key) {
723	>	Entry<K,V> e = getLowerEntry(key);
724		return (e == null)? null : e.key;
725		}
726
754	–
755	–
727		/**
728	<	* Returns a key-value mapping associated with the greatest key
729	<	* less than or equal to the given key, or <tt>null</tt> if there
730	<	* is no such entry.
731	<	*
732	<	* @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.
728	>	* @throws ClassCastException {@inheritDoc}
729	>	* @throws NullPointerException if the specified key is null
730	>	* and this map uses natural ordering, or its comparator
731	>	* does not permit null keys
732	>	* @since 1.6
733		*/
734		public Map.Entry<K,V> floorEntry(K key) {
735		Entry<K,V> e = getFloorEntry(key);
736	<	return (e == null)? null : new SnapshotEntry(e);
736	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
737		}
738
739		/**
740	<	* Returns the greatest key
741	<	* less than or equal to the given key, or <tt>null</tt> if there
742	<	* is no such key.
743	<	*
744	<	* @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.
740	>	* @throws ClassCastException {@inheritDoc}
741	>	* @throws NullPointerException if the specified key is null
742	>	* and this map uses natural ordering, or its comparator
743	>	* does not permit null keys
744	>	* @since 1.6
745		*/
746		public K floorKey(K key) {
747		Entry<K,V> e = getFloorEntry(key);
#	Line 792 \| Line 749 \| public class TreeMap<K,V>
749		}
750
751		/**
752	<	* Returns a key-value mapping associated with the least key
753	<	* strictly greater than the given key, or <tt>null</tt> if there
754	<	* is no such entry.
755	<	*
756	<	* @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.
752	>	* @throws ClassCastException {@inheritDoc}
753	>	* @throws NullPointerException if the specified key is null
754	>	* and this map uses natural ordering, or its comparator
755	>	* does not permit null keys
756	>	* @since 1.6
757		*/
758	<	public Map.Entry<K,V> higherEntry(K key) {
759	<	Entry<K,V> e = getHigherEntry(key);
760	<	return (e == null)? null : new SnapshotEntry(e);
758	>	public Map.Entry<K,V> ceilingEntry(K key) {
759	>	Entry<K,V> e = getCeilingEntry(key);
760	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
761		}
762
763		/**
764	<	* Returns the least key strictly greater than the given key, or
765	<	* <tt>null</tt> if there is no such key.
766	<	*
767	<	* @param key the key.
768	<	* @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.
764	>	* @throws ClassCastException {@inheritDoc}
765	>	* @throws NullPointerException if the specified key is null
766	>	* and this map uses natural ordering, or its comparator
767	>	* does not permit null keys
768	>	* @since 1.6
769		*/
770	<	public K higherKey(K key) {
771	<	Entry<K,V> e = getHigherEntry(key);
770	>	public K ceilingKey(K key) {
771	>	Entry<K,V> e = getCeilingEntry(key);
772		return (e == null)? null : e.key;
773		}
774
775		/**
776	<	* Returns a key-value mapping associated with the greatest
777	<	* key strictly less than the given key, or <tt>null</tt> if there is no
778	<	* such entry.
779	<	*
780	<	* @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.
776	>	* @throws ClassCastException {@inheritDoc}
777	>	* @throws NullPointerException if the specified key is null
778	>	* and this map uses natural ordering, or its comparator
779	>	* does not permit null keys
780	>	* @since 1.6
781		*/
782	<	public Map.Entry<K,V> lowerEntry(K key) {
783	<	Entry<K,V> e = getLowerEntry(key);
784	<	return (e == null)? null : new SnapshotEntry(e);
782	>	public Map.Entry<K,V> higherEntry(K key) {
783	>	Entry<K,V> e = getHigherEntry(key);
784	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
785		}
786
787		/**
788	<	* Returns the greatest key strictly less than the given key, or
789	<	* <tt>null</tt> if there is no such key.
790	<	*
791	<	* @param key the key.
792	<	* @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.
788	>	* @throws ClassCastException {@inheritDoc}
789	>	* @throws NullPointerException if the specified key is null
790	>	* and this map uses natural ordering, or its comparator
791	>	* does not permit null keys
792	>	* @since 1.6
793		*/
794	<	public K lowerKey(K key) {
795	<	Entry<K,V> e = getLowerEntry(key);
794	>	public K higherKey(K key) {
795	>	Entry<K,V> e = getHigherEntry(key);
796		return (e == null)? null : e.key;
797		}
798
#	Line 873 \| Line 804 \| public class TreeMap<K,V>
804		* there's no reason to create more than one.
805		*/
806		private transient Set<Map.Entry<K,V>> entrySet = null;
807	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
808	<	private transient Set<K> descendingKeySet = null;
878	<
879	<	transient Set<K> keySet = null; // XXX remove when integrated
880	<	transient Collection<V> values = null; // XXX remove when integrated
807	>	private transient KeySet<K> navigableKeySet = null;
808	>	private transient NavigableMap<K,V> descendingMap = null;
809
810		/**
811	<	* Returns a Set view of the keys contained in this map. The set's
812	<	* iterator will return the keys in ascending order. The set is backed by
813	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
814	<	* the Set, and vice-versa. The Set supports element removal, which
815	<	* removes the corresponding mapping from the map, via the
816	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
817	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
818	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
819	<	*
820	<	* @return a set view of the keys contained in this TreeMap.
811	>	* Returns a {@link Set} view of the keys contained in this map.
812	>	* The set's iterator returns the keys in ascending order.
813	>	* The set is backed by the map, so changes to the map are
814	>	* reflected in the set, and vice-versa. If the map is modified
815	>	* while an iteration over the set is in progress (except through
816	>	* the iterator's own <tt>remove</tt> operation), the results of
817	>	* the iteration are undefined. The set supports element removal,
818	>	* which removes the corresponding mapping from the map, via the
819	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
820	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
821	>	* operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
822	>	* operations.
823		*/
824		public Set<K> keySet() {
825	<	Set<K> ks = keySet;
896	<	return (ks != null) ? ks : (keySet = new KeySet());
825	>	return navigableKeySet();
826		}
827
828	<	class KeySet extends AbstractSet<K> {
829	<	public Iterator<K> iterator() {
830	<	return new KeyIterator(getFirstEntry());
831	<	}
832	<
833	<	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	<	}
828	>	/**
829	>	* @since 1.6
830	>	*/
831	>	public NavigableSet<K> navigableKeySet() {
832	>	NavigableSet<K> nks = navigableKeySet;
833	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
834		}
835
836		/**
837	<	* Returns a collection view of the values contained in this map. The
838	<	* collection's iterator will return the values in the order that their
839	<	* corresponding keys appear in the tree. The collection is backed by
840	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
841	<	* the collection, and vice-versa. The collection supports element
842	<	* removal, which removes the corresponding mapping from the map through
843	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
844	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
845	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
846	<	*
847	<	* @return a collection view of the values contained in this map.
837	>	* @since 1.6
838	>	*/
839	>	public NavigableSet<K> descendingKeySet() {
840	>	return descendingMap().navigableKeySet();
841	>	}
842	>
843	>	/**
844	>	* Returns a {@link Collection} view of the values contained in this map.
845	>	* The collection's iterator returns the values in ascending order
846	>	* of the corresponding keys.
847	>	* The collection is backed by the map, so changes to the map are
848	>	* reflected in the collection, and vice-versa. If the map is
849	>	* modified while an iteration over the collection is in progress
850	>	* (except through the iterator's own <tt>remove</tt> operation),
851	>	* the results of the iteration are undefined. The collection
852	>	* supports element removal, which removes the corresponding
853	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
854	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
855	>	* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
856	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
857		*/
858		public Collection<V> values() {
859		Collection<V> vs = values;
860		return (vs != null) ? vs : (values = new Values());
861		}
862
863	+	/**
864	+	* Returns a {@link Set} view of the mappings contained in this map.
865	+	* The set's iterator returns the entries in ascending key order.
866	+	* The set is backed by the map, so changes to the map are
867	+	* reflected in the set, and vice-versa. If the map is modified
868	+	* while an iteration over the set is in progress (except through
869	+	* the iterator's own <tt>remove</tt> operation, or through the
870	+	* <tt>setValue</tt> operation on a map entry returned by the
871	+	* iterator) the results of the iteration are undefined. The set
872	+	* supports element removal, which removes the corresponding
873	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
874	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
875	+	* <tt>clear</tt> operations. It does not support the
876	+	* <tt>add</tt> or <tt>addAll</tt> operations.
877	+	*/
878	+	public Set<Map.Entry<K,V>> entrySet() {
879	+	Set<Map.Entry<K,V>> es = entrySet;
880	+	return (es != null) ? es : (entrySet = new EntrySet());
881	+	}
882	+
883	+	/**
884	+	* @since 1.6
885	+	*/
886	+	public NavigableMap<K, V> descendingMap() {
887	+	NavigableMap<K, V> km = descendingMap;
888	+	return (km != null) ? km :
889	+	(descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
890	+	(K)UNBOUNDED, 0));
891	+	}
892	+
893	+	/**
894	+	* @throws ClassCastException {@inheritDoc}
895	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
896	+	* null and this map uses natural ordering, or its comparator
897	+	* does not permit null keys
898	+	* @throws IllegalArgumentException {@inheritDoc}
899	+	* @since 1.6
900	+	*/
901	+	public NavigableMap<K,V> navigableSubMap(K fromKey, boolean fromInclusive,
902	+	K toKey, boolean toInclusive) {
903	+	return new AscendingSubMap(fromKey, excluded(fromInclusive),
904	+	toKey, excluded(toInclusive));
905	+	}
906	+
907	+	/**
908	+	* @throws ClassCastException {@inheritDoc}
909	+	* @throws NullPointerException if <tt>toKey</tt> is null
910	+	* and this map uses natural ordering, or its comparator
911	+	* does not permit null keys
912	+	* @throws IllegalArgumentException {@inheritDoc}
913	+	* @since 1.6
914	+	*/
915	+	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
916	+	return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
917	+	}
918	+
919	+	/**
920	+	* @throws ClassCastException {@inheritDoc}
921	+	* @throws NullPointerException if <tt>fromKey</tt> is null
922	+	* and this map uses natural ordering, or its comparator
923	+	* does not permit null keys
924	+	* @throws IllegalArgumentException {@inheritDoc}
925	+	* @since 1.6
926	+	*/
927	+	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive) {
928	+	return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 0);
929	+	}
930	+
931	+	/**
932	+	* Translates a boolean "inclusive" value to the correct int value
933	+	* for the loExcluded or hiExcluded field.
934	+	*/
935	+	static int excluded(boolean inclusive) {
936	+	return inclusive ? 0 : 1;
937	+	}
938	+
939	+	/**
940	+	* @throws ClassCastException {@inheritDoc}
941	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
942	+	* null and this map uses natural ordering, or its comparator
943	+	* does not permit null keys
944	+	* @throws IllegalArgumentException {@inheritDoc}
945	+	*/
946	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
947	+	return navigableSubMap(fromKey, true, toKey, false);
948	+	}
949	+
950	+	/**
951	+	* @throws ClassCastException {@inheritDoc}
952	+	* @throws NullPointerException if <tt>toKey</tt> is null
953	+	* and this map uses natural ordering, or its comparator
954	+	* does not permit null keys
955	+	* @throws IllegalArgumentException {@inheritDoc}
956	+	*/
957	+	public SortedMap<K,V> headMap(K toKey) {
958	+	return navigableHeadMap(toKey, false);
959	+	}
960	+
961	+	/**
962	+	* @throws ClassCastException {@inheritDoc}
963	+	* @throws NullPointerException if <tt>fromKey</tt> is null
964	+	* and this map uses natural ordering, or its comparator
965	+	* does not permit null keys
966	+	* @throws IllegalArgumentException {@inheritDoc}
967	+	*/
968	+	public SortedMap<K,V> tailMap(K fromKey) {
969	+	return navigableTailMap(fromKey, true);
970	+	}
971	+
972	+	// View class support
973	+
974		class Values extends AbstractCollection<V> {
975		public Iterator<V> iterator() {
976		return new ValueIterator(getFirstEntry());
977		}
978	<
978	>
979		public int size() {
980		return TreeMap.this.size();
981		}
982	<
982	>
983		public boolean contains(Object o) {
984		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
985		if (valEquals(e.getValue(), o))
986		return true;
987		return false;
988		}
989	<
989	>
990		public boolean remove(Object o) {
991		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
992		if (valEquals(e.getValue(), o)) {
#	Line 963 \| Line 996 \| public class TreeMap<K,V>
996		}
997		return false;
998		}
999	<
999	>
1000		public void clear() {
1001		TreeMap.this.clear();
1002		}
1003		}
1004
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	–
1005		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1006		public Iterator<Map.Entry<K,V>> iterator() {
1007		return new EntryIterator(getFirstEntry());
1008		}
1009	<
1009	>
1010		public boolean contains(Object o) {
1011		if (!(o instanceof Map.Entry))
1012		return false;
#	Line 1001 \| Line 1015 \| public class TreeMap<K,V>
1015		Entry<K,V> p = getEntry(entry.getKey());
1016		return p != null && valEquals(p.getValue(), value);
1017		}
1018	<
1018	>
1019		public boolean remove(Object o) {
1020		if (!(o instanceof Map.Entry))
1021		return false;
#	Line 1014 \| Line 1028 \| public class TreeMap<K,V>
1028		}
1029		return false;
1030		}
1031	<
1031	>
1032		public int size() {
1033		return TreeMap.this.size();
1034		}
1035	<
1035	>
1036		public void clear() {
1037		TreeMap.this.clear();
1038		}
1039		}
1040
1041	<	/**
1042	<	* Returns a set view of the mappings contained in this map. The
1043	<	* set's iterator returns the mappings in descrending key order.
1044	<	* Each element in the returned set is a <tt>Map.Entry</tt>. The
1045	<	* set is backed by this map, so changes to this map are reflected
1046	<	* in the set, and vice-versa. The set supports element removal,
1047	<	* which removes the corresponding mapping from the TreeMap,
1048	<	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1049	<	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1050	<	* 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());
1041	>	/*
1042	>	* Unlike Values and EntrySet, the KeySet class is static,
1043	>	* delegating to a NavigableMap to allow use by SubMaps, which
1044	>	* outweighs the ugliness of needing type-tests for the following
1045	>	* Iterator methods that are defined appropriately in main versus
1046	>	* submap classes.
1047	>	*/
1048	>
1049	>	Iterator<K> keyIterator() {
1050	>	return new KeyIterator(getFirstEntry());
1051		}
1052
1053	<	class DescendingEntrySet extends EntrySet {
1054	<	public Iterator<Map.Entry<K,V>> iterator() {
1050	<	return new DescendingEntryIterator(getLastEntry());
1051	<	}
1053	>	Iterator<K> descendingKeyIterator() {
1054	>	return new DescendingKeyIterator(getFirstEntry());
1055		}
1056
1057	<	/**
1058	<	* Returns a Set view of the keys contained in this map. The
1059	<	* set's iterator will return the keys in descending order. The
1060	<	* map is backed by this <tt>TreeMap</tt> instance, so changes to
1061	<	* this map are reflected in the Set, and vice-versa. The Set
1062	<	* supports element removal, which removes the corresponding
1063	<	* mapping from the map, via the <tt>Iterator.remove</tt>,
1064	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1065	<	* and <tt>clear</tt> operations. It does not support the
1063	<	* <tt>add</tt> or <tt>addAll</tt> operations.
1064	<	*
1065	<	* @return a set view of the keys contained in this TreeMap.
1066	<	*/
1067	<	public Set<K> descendingKeySet() {
1068	<	Set<K> ks = descendingKeySet;
1069	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1070	<	}
1071	<
1072	<	class DescendingKeySet extends KeySet {
1073	<	public Iterator<K> iterator() {
1074	<	return new DescendingKeyIterator(getLastEntry());
1057	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1058	>	private final NavigableMap<E, Object> m;
1059	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1060	>
1061	>	public Iterator<E> iterator() {
1062	>	if (m instanceof TreeMap)
1063	>	return ((TreeMap<E,Object>)m).keyIterator();
1064	>	else
1065	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1066		}
1076	–	}
1067
1068	<	/**
1069	<	* Returns a view of the portion of this map whose keys range from
1070	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
1071	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
1072	<	* is empty.) The returned sorted map is backed by this map, so changes
1073	<	* in the returned sorted map are reflected in this map, and vice-versa.
1074	<	* The returned sorted map supports all optional map operations.<p>
1075	<	*
1076	<	* The sorted map returned by this method will throw an
1077	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1078	<	* less than <tt>fromKey</tt> or greater than or equal to
1079	<	* <tt>toKey</tt>.<p>
1080	<	*
1081	<	* Note: this method always returns a <i>half-open range</i> (which
1082	<	* includes its low endpoint but not its high endpoint). If you need a
1083	<	* <i>closed range</i> (which includes both endpoints), and the key type
1084	<	* allows for calculation of the successor a given key, merely request the
1085	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1086	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys are
1087	<	* strings. The following idiom obtains a view containing all of the
1088	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1089	<	* and <tt>high</tt>, inclusive:
1090	<	* <pre> NavigableMap sub = m.submap(low, high+"\0");</pre>
1091	<	* A similar technique can be used to generate an <i>open range</i> (which
1092	<	* contains neither endpoint). The following idiom obtains a view
1093	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1094	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1095	<	* <pre> NavigableMap sub = m.subMap(low+"\0", high);</pre>
1096	<	*
1097	<	* @param fromKey low endpoint (inclusive) of the subMap.
1098	<	* @param toKey high endpoint (exclusive) of the subMap.
1099	<	*
1100	<	* @return a view of the portion of this map whose keys range from
1101	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1102	<	*
1103	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1104	<	* cannot be compared to one another using this map's comparator
1105	<	* (or, if the map has no comparator, using natural ordering).
1106	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1107	<	* <tt>toKey</tt>.
1108	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1109	<	* <tt>null</tt> and this map uses natural order, or its
1110	<	* comparator does not tolerate <tt>null</tt> keys.
1111	<	*/
1112	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1113	<	return new SubMap(fromKey, toKey);
1068	>	public Iterator<E> descendingIterator() {
1069	>	if (m instanceof TreeMap)
1070	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1071	>	else
1072	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1073	>	}
1074	>
1075	>	public int size() { return m.size(); }
1076	>	public boolean isEmpty() { return m.isEmpty(); }
1077	>	public boolean contains(Object o) { return m.containsKey(o); }
1078	>	public void clear() { m.clear(); }
1079	>	public E lower(E e) { return m.lowerKey(e); }
1080	>	public E floor(E e) { return m.floorKey(e); }
1081	>	public E ceiling(E e) { return m.ceilingKey(e); }
1082	>	public E higher(E e) { return m.higherKey(e); }
1083	>	public E first() { return m.firstKey(); }
1084	>	public E last() { return m.lastKey(); }
1085	>	public Comparator<? super E> comparator() { return m.comparator(); }
1086	>	public E pollFirst() {
1087	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1088	>	return e == null? null : e.getKey();
1089	>	}
1090	>	public E pollLast() {
1091	>	Map.Entry<E,Object> e = m.pollLastEntry();
1092	>	return e == null? null : e.getKey();
1093	>	}
1094	>	public boolean remove(Object o) {
1095	>	int oldSize = size();
1096	>	m.remove(o);
1097	>	return size() != oldSize;
1098	>	}
1099	>	public NavigableSet<E> navigableSubSet(E fromElement,
1100	>	boolean fromInclusive,
1101	>	E toElement,
1102	>	boolean toInclusive) {
1103	>	return new TreeSet<E>
1104	>	(m.navigableSubMap(fromElement, fromInclusive,
1105	>	toElement, toInclusive));
1106	>	}
1107	>	public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
1108	>	return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
1109	>	}
1110	>	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
1111	>	return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
1112	>	}
1113	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1114	>	return navigableSubSet(fromElement, true, toElement, false);
1115	>	}
1116	>	public SortedSet<E> headSet(E toElement) {
1117	>	return navigableHeadSet(toElement, false);
1118	>	}
1119	>	public SortedSet<E> tailSet(E fromElement) {
1120	>	return navigableTailSet(fromElement, true);
1121	>	}
1122	>	public NavigableSet<E> descendingSet() {
1123	>	return new TreeSet(m.descendingMap());
1124	>	}
1125		}
1126
1127	<	/**
1128	<	* Returns a view of the portion of this map whose keys are strictly less
1129	<	* than <tt>toKey</tt>. The returned sorted map is backed by this map, so
1130	<	* changes in the returned sorted map are reflected in this map, and
1130	<	* vice-versa. The returned sorted map supports all optional map
1131	<	* operations.<p>
1132	<	*
1133	<	* The sorted map returned by this method will throw an
1134	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1135	<	* greater than or equal to <tt>toKey</tt>.<p>
1136	<	*
1137	<	* Note: this method always returns a view that does not contain its
1138	<	* (high) endpoint. If you need a view that does contain this endpoint,
1139	<	* and the key type allows for calculation of the successor a given key,
1140	<	* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1141	<	* For example, suppose that suppose that <tt>m</tt> is a sorted map whose
1142	<	* keys are strings. The following idiom obtains a view containing all of
1143	<	* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1144	<	* to <tt>high</tt>:
1145	<	* <pre>
1146	<	* NavigableMap head = m.headMap(high+"\0");
1147	<	* </pre>
1148	<	*
1149	<	* @param toKey high endpoint (exclusive) of the headMap.
1150	<	* @return a view of the portion of this map whose keys are strictly
1151	<	* less than <tt>toKey</tt>.
1152	<	*
1153	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1154	<	* with this map's comparator (or, if the map has no comparator,
1155	<	* if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1156	<	* @throws IllegalArgumentException if this map is itself a subMap,
1157	<	* headMap, or tailMap, and <tt>toKey</tt> is not within the
1158	<	* specified range of the subMap, headMap, or tailMap.
1159	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1160	<	* this map uses natural order, or its comparator does not
1161	<	* tolerate <tt>null</tt> keys.
1162	<	*/
1163	<	public NavigableMap<K,V> headMap(K toKey) {
1164	<	return new SubMap(toKey, true);
1165	<	}
1166	<
1167	<	/**
1168	<	* Returns a view of the portion of this map whose keys are greater than
1169	<	* or equal to <tt>fromKey</tt>. The returned sorted map is backed by
1170	<	* this map, so changes in the returned sorted map are reflected in this
1171	<	* map, and vice-versa. The returned sorted map supports all optional map
1172	<	* operations.<p>
1173	<	*
1174	<	* The sorted map returned by this method will throw an
1175	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1176	<	* less than <tt>fromKey</tt>.<p>
1177	<	*
1178	<	* Note: this method always returns a view that contains its (low)
1179	<	* endpoint. If you need a view that does not contain this endpoint, and
1180	<	* the element type allows for calculation of the successor a given value,
1181	<	* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1182	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys
1183	<	* are strings. The following idiom obtains a view containing
1184	<	* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1185	<	* greater than <tt>low</tt>: <pre>
1186	<	* NavigableMap tail = m.tailMap(low+"\0");
1187	<	* </pre>
1188	<	*
1189	<	* @param fromKey low endpoint (inclusive) of the tailMap.
1190	<	* @return a view of the portion of this map whose keys are greater
1191	<	* than or equal to <tt>fromKey</tt>.
1192	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1193	<	* with this map's comparator (or, if the map has no comparator,
1194	<	* if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1195	<	* @throws IllegalArgumentException if this map is itself a subMap,
1196	<	* headMap, or tailMap, and <tt>fromKey</tt> is not within the
1197	<	* specified range of the subMap, headMap, or tailMap.
1198	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1199	<	* this map uses natural order, or its comparator does not
1200	<	* tolerate <tt>null</tt> keys.
1201	<	*/
1202	<	public NavigableMap<K,V> tailMap(K fromKey) {
1203	<	return new SubMap(fromKey, false);
1204	<	}
1205	<
1206	<	private class SubMap
1207	<	extends AbstractMap<K,V>
1208	<	implements NavigableMap<K,V>, java.io.Serializable {
1209	<	private static final long serialVersionUID = -6520786458950516097L;
1127	>	// SubMaps
1128	>
1129	>	abstract class NavigableSubMap extends AbstractMap<K,V>
1130	>	implements NavigableMap<K,V>, java.io.Serializable {
1131
1132		/**
1133	<	* fromKey is significant only if fromStart is false. Similarly,
1134	<	* toKey is significant only if toStart is false.
1133	>	* The low endpoint of this submap in absolute terms. For ascending
1134	>	* submaps this will be the "first" endpoint; for descending submaps,
1135	>	* the last. If there is no bound, this field is set to UNBOUNDED.
1136		*/
1137	<	private boolean fromStart = false, toEnd = false;
1216	<	private K fromKey, toKey;
1137	>	K lo;
1138
1139	<	SubMap(K fromKey, K toKey) {
1140	<	if (compare(fromKey, toKey) > 0)
1141	<	throw new IllegalArgumentException("fromKey > toKey");
1142	<	this.fromKey = fromKey;
1143	<	this.toKey = toKey;
1223	<	}
1139	>	/**
1140	>	* Zero if the low endpoint is excluded from this submap, one if
1141	>	* it's included. This field is unused if lo is UNBOUNDED.
1142	>	*/
1143	>	int loExcluded;
1144
1145	<	SubMap(K key, boolean headMap) {
1146	<	compare(key, key); // Type-check key
1145	>	/**
1146	>	* The high endpoint of this submap in absolute terms. For ascending
1147	>	* submaps this will be the "last" endpoint; for descending submaps,
1148	>	* the first. If there is no bound, this field is set to UNBOUNDED.
1149	>	*/
1150	>	K hi;
1151
1152	<	if (headMap) {
1153	<	fromStart = true;
1154	<	toKey = key;
1155	<	} else {
1156	<	toEnd = true;
1233	<	fromKey = key;
1234	<	}
1235	<	}
1152	>	/**
1153	>	* Zero if the high endpoint is excluded from this submap, one if
1154	>	* it's included. This field is unused if hi is UNBOUNDED.
1155	>	*/
1156	>	int hiExcluded;
1157
1158	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1159	<	this.fromStart = fromStart;
1160	<	this.fromKey= fromKey;
1161	<	this.toEnd = toEnd;
1162	<	this.toKey = toKey;
1158	>	NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1159	>	if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
1160	>	throw new IllegalArgumentException("fromKey > toKey");
1161	>	this.lo = lo;
1162	>	this.loExcluded = loExcluded;
1163	>	this.hi = hi;
1164	>	this.hiExcluded = hiExcluded;
1165		}
1166
1167		public boolean isEmpty() {
1168	<	return entrySet.isEmpty();
1168	>	return entrySet().isEmpty();
1169		}
1170
1171		public boolean containsKey(Object key) {
1172	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1172	>	return inRange(key) && TreeMap.this.containsKey(key);
1173		}
1174
1175		public V get(Object key) {
1176	<	if (!inRange((K) key))
1176	>	if (!inRange(key))
1177		return null;
1178		return TreeMap.this.get(key);
1179		}
#	Line 1262 \| Line 1185 \| public class TreeMap<K,V>
1185		}
1186
1187		public V remove(Object key) {
1188	<	if (!inRange((K) key))
1188	>	if (!inRange(key))
1189		return null;
1190		return TreeMap.this.remove(key);
1191		}
1192
1270	–	public Comparator<? super K> comparator() {
1271	–	return comparator;
1272	–	}
1273	–
1274	–	public K firstKey() {
1275	–	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;
1296	–	}
1297	–
1298	–	public Map.Entry<K,V> lastEntry() {
1299	–	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;
1304	–	}
1305	–
1306	–	public Map.Entry<K,V> pollFirstEntry() {
1307	–	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;
1314	–	}
1315	–
1316	–	public Map.Entry<K,V> pollLastEntry() {
1317	–	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;
1324	–	}
1325	–
1326	–	private TreeMap.Entry<K,V> subceiling(K key) {
1327	–	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;
1332	–	}
1333	–
1193		public Map.Entry<K,V> ceilingEntry(K key) {
1194	<	TreeMap.Entry<K,V> e = subceiling(key);
1195	<	return e == null? null : new SnapshotEntry(e);
1194	>	TreeMap.Entry<K,V> e = subCeiling(key);
1195	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1196		}
1197
1198		public K ceilingKey(K key) {
1199	<	TreeMap.Entry<K,V> e = subceiling(key);
1199	>	TreeMap.Entry<K,V> e = subCeiling(key);
1200		return e == null? null : e.key;
1201		}
1202
1344	–
1345	–	private TreeMap.Entry<K,V> subhigher(K key) {
1346	–	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;
1351	–	}
1352	–
1203		public Map.Entry<K,V> higherEntry(K key) {
1204	<	TreeMap.Entry<K,V> e = subhigher(key);
1205	<	return e == null? null : new SnapshotEntry(e);
1204	>	TreeMap.Entry<K,V> e = subHigher(key);
1205	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1206		}
1207
1208		public K higherKey(K key) {
1209	<	TreeMap.Entry<K,V> e = subhigher(key);
1209	>	TreeMap.Entry<K,V> e = subHigher(key);
1210		return e == null? null : e.key;
1211		}
1212
1363	–	private TreeMap.Entry<K,V> subfloor(K key) {
1364	–	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;
1369	–	}
1370	–
1213		public Map.Entry<K,V> floorEntry(K key) {
1214	<	TreeMap.Entry<K,V> e = subfloor(key);
1215	<	return e == null? null : new SnapshotEntry(e);
1214	>	TreeMap.Entry<K,V> e = subFloor(key);
1215	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1216		}
1217
1218		public K floorKey(K key) {
1219	<	TreeMap.Entry<K,V> e = subfloor(key);
1219	>	TreeMap.Entry<K,V> e = subFloor(key);
1220		return e == null? null : e.key;
1221		}
1222
1381	–	private TreeMap.Entry<K,V> sublower(K key) {
1382	–	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1383	–	getLowerEntry(toKey) : getLowerEntry(key);
1384	–	if (e == null \|\| (!fromStart && compare(e.key, fromKey) < 0))
1385	–	return null;
1386	–	return e;
1387	–	}
1388	–
1223		public Map.Entry<K,V> lowerEntry(K key) {
1224	<	TreeMap.Entry<K,V> e = sublower(key);
1225	<	return e == null? null : new SnapshotEntry(e);
1224	>	TreeMap.Entry<K,V> e = subLower(key);
1225	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1226		}
1227
1228		public K lowerKey(K key) {
1229	<	TreeMap.Entry<K,V> e = sublower(key);
1229	>	TreeMap.Entry<K,V> e = subLower(key);
1230		return e == null? null : e.key;
1231		}
1232
1233	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1233	>	abstract Iterator<K> keyIterator();
1234	>	abstract Iterator<K> descendingKeyIterator();
1235
1236	<	public Set<Map.Entry<K,V>> entrySet() {
1237	<	return entrySet;
1236	>	public NavigableSet<K> descendingKeySet() {
1237	>	return descendingMap().navigableKeySet();
1238		}
1239
1240	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1240	>	// Views
1241	>	transient NavigableMap<K,V> descendingMapView = null;
1242	>	transient Set<Map.Entry<K,V>> entrySetView = null;
1243	>	private transient NavigableSet<K> navigableKeySetView = null;
1244	>
1245	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1246		private transient int size = -1, sizeModCount;
1247
1248		public int size() {
#	Line 1447 \| Line 1287 \| public class TreeMap<K,V>
1287		}
1288		return false;
1289		}
1290	+	}
1291
1292	<	public Iterator<Map.Entry<K,V>> iterator() {
1293	<	return new SubMapEntryIterator(
1294	<	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1295	<	(toEnd ? null : getCeilingEntry(toKey)));
1455	<	}
1292	>	public NavigableSet<K> navigableKeySet() {
1293	>	NavigableSet<K> nksv = navigableKeySetView;
1294	>	return (nksv != null) ? nksv :
1295	>	(navigableKeySetView = new TreeMap.KeySet(this));
1296		}
1297
1298	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1299	<	private transient Set<K> descendingKeySetView = null;
1298	>	public Set<K> keySet() {
1299	>	return navigableKeySet();
1300	>	}
1301
1302	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1303	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1463	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1302	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1303	>	return navigableSubMap(fromKey, true, toKey, false);
1304		}
1305
1306	<	public Set<K> descendingKeySet() {
1307	<	Set<K> ks = descendingKeySetView;
1468	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1306	>	public SortedMap<K,V> headMap(K toKey) {
1307	>	return navigableHeadMap(toKey, false);
1308		}
1309
1310	<	private class DescendingEntrySetView extends EntrySetView {
1311	<	public Iterator<Map.Entry<K,V>> iterator() {
1473	<	return new DescendingSubMapEntryIterator
1474	<	((toEnd ? getLastEntry() : getLowerEntry(toKey)),
1475	<	(fromStart ? null : getLowerEntry(fromKey)));
1476	<	}
1310	>	public SortedMap<K,V> tailMap(K fromKey) {
1311	>	return navigableTailMap(fromKey, true);
1312		}
1313
1314	<	private class DescendingKeySetView extends AbstractSet<K> {
1315	<	public Iterator<K> iterator() {
1316	<	return new Iterator<K>() {
1317	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1318	<
1319	<	public boolean hasNext() { return i.hasNext(); }
1485	<	public K next() { return i.next().getKey(); }
1486	<	public void remove() { i.remove(); }
1487	<	};
1488	<	}
1489	<
1490	<	public int size() {
1491	<	return SubMap.this.size();
1492	<	}
1493	<
1494	<	public boolean contains(Object k) {
1495	<	return SubMap.this.containsKey(k);
1496	<	}
1314	>	/** Returns the lowest entry in this submap (absolute ordering) */
1315	>	TreeMap.Entry<K,V> loEntry() {
1316	>	TreeMap.Entry<K,V> result =
1317	>	((lo == UNBOUNDED) ? getFirstEntry() :
1318	>	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1319	>	return (result == null \|\| tooHigh(result.key)) ? null : result;
1320		}
1321
1322	+	/** Returns the highest key in this submap (absolute ordering) */
1323	+	TreeMap.Entry<K,V> hiEntry() {
1324	+	TreeMap.Entry<K,V> result =
1325	+	((hi == UNBOUNDED) ? getLastEntry() :
1326	+	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1327	+	return (result == null \|\| tooLow(result.key)) ? null : result;
1328	+	}
1329
1330	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1331	<	if (!inRange2(fromKey))
1330	>	/** Polls the lowest entry in this submap (absolute ordering) */
1331	>	Map.Entry<K,V> pollLoEntry() {
1332	>	TreeMap.Entry<K,V> e =
1333	>	((lo == UNBOUNDED) ? getFirstEntry() :
1334	>	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1335	>	if (e == null \|\| tooHigh(e.key))
1336	>	return null;
1337	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1338	>	deleteEntry(e);
1339	>	return result;
1340	>	}
1341	>
1342	>	/** Polls the highest key in this submap (absolute ordering) */
1343	>	Map.Entry<K,V> pollHiEntry() {
1344	>	TreeMap.Entry<K,V> e =
1345	>	((hi == UNBOUNDED) ? getLastEntry() :
1346	>	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1347	>	if (e == null \|\| tooLow(e.key))
1348	>	return null;
1349	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1350	>	deleteEntry(e);
1351	>	return result;
1352	>	}
1353	>
1354	>	// The following four definitions are correct only for
1355	>	// ascending submaps. They are overridden in DescendingSubMap.
1356	>	// They are defined in the base class because the definitions
1357	>	// in DescendingSubMap rely on those for AscendingSubMap.
1358	>
1359	>	/**
1360	>	* Returns the entry corresponding to the ceiling of the specified
1361	>	* key from the perspective of this submap, or null if the submap
1362	>	* contains no such entry.
1363	>	*/
1364	>	TreeMap.Entry<K,V> subCeiling(K key) {
1365	>	if (tooLow(key))
1366	>	return loEntry();
1367	>	TreeMap.Entry<K,V> e = getCeilingEntry(key);
1368	>	return (e == null \|\| tooHigh(e.key)) ? null : e;
1369	>	}
1370	>
1371	>	/**
1372	>	* Returns the entry corresponding to the higher of the specified
1373	>	* key from the perspective of this submap, or null if the submap
1374	>	* contains no such entry.
1375	>	*/
1376	>	TreeMap.Entry<K,V> subHigher(K key) {
1377	>	if (tooLow(key))
1378	>	return loEntry();
1379	>	TreeMap.Entry<K,V> e = getHigherEntry(key);
1380	>	return (e == null \|\| tooHigh(e.key)) ? null : e;
1381	>	}
1382	>
1383	>	/**
1384	>	* Returns the entry corresponding to the floor of the specified
1385	>	* key from the perspective of this submap, or null if the submap
1386	>	* contains no such entry.
1387	>	*/
1388	>	TreeMap.Entry<K,V> subFloor(K key) {
1389	>	if (tooHigh(key))
1390	>	return hiEntry();
1391	>	TreeMap.Entry<K,V> e = getFloorEntry(key);
1392	>	return (e == null \|\| tooLow(e.key)) ? null : e;
1393	>	}
1394	>
1395	>	/**
1396	>	* Returns the entry corresponding to the lower of the specified
1397	>	* key from the perspective of this submap, or null if the submap
1398	>	* contains no such entry.
1399	>	*/
1400	>	TreeMap.Entry<K,V> subLower(K key) {
1401	>	if (tooHigh(key))
1402	>	return hiEntry();
1403	>	TreeMap.Entry<K,V> e = getLowerEntry(key);
1404	>	return (e == null \|\| tooLow(e.key)) ? null : e;
1405	>	}
1406	>
1407	>	boolean inRange(Object key) {
1408	>	return (lo == UNBOUNDED \|\| compare(key, lo) >= loExcluded)
1409	>	&& (hi == UNBOUNDED \|\| compare(hi, key) >= hiExcluded);
1410	>	}
1411	>
1412	>	boolean inClosedRange(Object key) {
1413	>	return (lo == UNBOUNDED \|\| compare(key, lo) >= 0)
1414	>	&& (hi == UNBOUNDED \|\| compare(hi, key) >= 0);
1415	>	}
1416	>
1417	>	boolean inRange(Object key, boolean inclusive) {
1418	>	return inclusive ? inRange(key) : inClosedRange(key);
1419	>	}
1420	>
1421	>	boolean tooLow(K key) {
1422	>	return lo != UNBOUNDED && compare(key, lo) < loExcluded;
1423	>	}
1424	>
1425	>	boolean tooHigh(K key) {
1426	>	return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
1427	>	}
1428	>	}
1429	>
1430	>	class AscendingSubMap extends NavigableSubMap {
1431	>	private static final long serialVersionUID = 912986545866124060L;
1432	>
1433	>	AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1434	>	super(lo, loExcluded, hi, hiExcluded);
1435	>	}
1436	>
1437	>	public Comparator<? super K> comparator() {
1438	>	return comparator;
1439	>	}
1440	>
1441	>	public NavigableMap<K,V> navigableSubMap(
1442	>	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1443	>	if (!inRange(fromKey, fromInclusive))
1444		throw new IllegalArgumentException("fromKey out of range");
1445	<	if (!inRange2(toKey))
1445	>	if (!inRange(toKey, toInclusive))
1446		throw new IllegalArgumentException("toKey out of range");
1447	<	return new SubMap(fromKey, toKey);
1447	>	return new AscendingSubMap(fromKey, excluded(fromInclusive),
1448	>	toKey, excluded(toInclusive));
1449		}
1450
1451	<	public NavigableMap<K,V> headMap(K toKey) {
1452	<	if (!inRange2(toKey))
1451	>	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1452	>	if (!inClosedRange(toKey))
1453		throw new IllegalArgumentException("toKey out of range");
1454	<	return new SubMap(fromStart, fromKey, false, toKey);
1454	>	return new AscendingSubMap(lo, loExcluded,
1455	>	toKey, excluded(inclusive));
1456		}
1457
1458	<	public NavigableMap<K,V> tailMap(K fromKey) {
1459	<	if (!inRange2(fromKey))
1458	>	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1459	>	if (!inRange(fromKey, inclusive))
1460		throw new IllegalArgumentException("fromKey out of range");
1461	<	return new SubMap(false, fromKey, toEnd, toKey);
1461	>	return new AscendingSubMap(fromKey, excluded(inclusive),
1462	>	hi, hiExcluded);
1463	>	}
1464	>
1465	>	Iterator<K> keyIterator() {
1466	>	return new SubMapKeyIterator
1467	>	(loEntry(),
1468	>	hi == UNBOUNDED ? null :
1469	>	hiExcluded == 1 ? getCeilingEntry(hi) :
1470	>	getHigherEntry(hi));
1471	>	}
1472	>
1473	>	Iterator<K> descendingKeyIterator() {
1474	>	return new DescendingSubMapKeyIterator
1475	>	(hiEntry(),
1476	>	lo == UNBOUNDED ? null :
1477	>	loExcluded == 1 ? getFloorEntry(lo) :
1478	>	getLowerEntry(lo));
1479	>	}
1480	>
1481	>	public Set<Map.Entry<K,V>> entrySet() {
1482	>	Set<Map.Entry<K,V>> es = entrySetView;
1483	>	if (es != null)
1484	>	return es;
1485	>	return entrySetView = new NavigableSubMap.EntrySetView() {
1486	>	public Iterator<Map.Entry<K,V>> iterator() {
1487	>	return new SubMapEntryIterator(loEntry(),
1488	>	hi == UNBOUNDED ? null :
1489	>	hiExcluded == 1 ? getCeilingEntry(hi) :
1490	>	getHigherEntry(hi));
1491	>	}
1492	>	};
1493	>	}
1494	>
1495	>	public K firstKey() {
1496	>	return key(loEntry());
1497	>	}
1498	>
1499	>	public K lastKey() {
1500	>	return key(hiEntry());
1501	>	}
1502	>
1503	>	public Map.Entry<K,V> firstEntry() {
1504	>	return loEntry();
1505	>	}
1506	>
1507	>	public Map.Entry<K,V> lastEntry() {
1508	>	return hiEntry();
1509	>	}
1510	>
1511	>	public Map.Entry<K,V> pollFirstEntry() {
1512	>	return pollLoEntry();
1513	>	}
1514	>
1515	>	public Map.Entry<K,V> pollLastEntry() {
1516	>	return pollHiEntry();
1517	>	}
1518	>
1519	>	public NavigableMap<K,V> descendingMap() {
1520	>	NavigableMap<K,V> m = descendingMapView;
1521	>	return (m != null) ? m :
1522	>	(descendingMapView =
1523	>	new DescendingSubMap(lo, loExcluded, hi, hiExcluded));
1524	>	}
1525	>	}
1526	>
1527	>	class DescendingSubMap extends NavigableSubMap {
1528	>	private static final long serialVersionUID = 912986545866120460L;
1529	>	DescendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1530	>	super(lo, loExcluded, hi, hiExcluded);
1531	>	}
1532	>
1533	>	private final Comparator<? super K> reverseComparator =
1534	>	Collections.reverseOrder(comparator);
1535	>
1536	>	public Comparator<? super K> comparator() {
1537	>	return reverseComparator;
1538	>	}
1539	>
1540	>	public NavigableMap<K,V> navigableSubMap(
1541	>	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1542	>	if (!inRange(fromKey, fromInclusive))
1543	>	throw new IllegalArgumentException("fromKey out of range");
1544	>	if (!inRange(toKey, toInclusive))
1545	>	throw new IllegalArgumentException("toKey out of range");
1546	>	return new DescendingSubMap(toKey, excluded(toInclusive),
1547	>	fromKey, excluded(fromInclusive));
1548	>	}
1549	>
1550	>	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1551	>	if (!inRange(toKey, inclusive))
1552	>	throw new IllegalArgumentException("toKey out of range");
1553	>	return new DescendingSubMap(toKey, inclusive ? 0:1, hi, hiExcluded);
1554	>	}
1555	>
1556	>	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1557	>	if (!inRange(fromKey, inclusive))
1558	>	throw new IllegalArgumentException("fromKey out of range");
1559	>	return new DescendingSubMap(lo, loExcluded,
1560	>	fromKey, excluded(inclusive));
1561	>	}
1562	>
1563	>	Iterator<K> keyIterator() {
1564	>	return new DescendingSubMapKeyIterator
1565	>	(hiEntry(),
1566	>	lo == UNBOUNDED ? null :
1567	>	loExcluded == 1 ? getFloorEntry(lo) :
1568	>	getLowerEntry(lo));
1569	>	}
1570	>
1571	>	Iterator<K> descendingKeyIterator() {
1572	>	return new SubMapKeyIterator
1573	>	(loEntry(),
1574	>	hi == UNBOUNDED ? null :
1575	>	hiExcluded == 1 ? getCeilingEntry(hi) :
1576	>	getHigherEntry(hi));
1577	>	}
1578	>
1579	>	public Set<Map.Entry<K,V>> entrySet() {
1580	>	Set<Map.Entry<K,V>> es = entrySetView;
1581	>	if (es != null)
1582	>	return es;
1583	>	return entrySetView = new NavigableSubMap.EntrySetView() {
1584	>	public Iterator<Map.Entry<K,V>> iterator() {
1585	>	return new DescendingSubMapEntryIterator(hiEntry(),
1586	>	lo == UNBOUNDED ? null :
1587	>	loExcluded == 1 ? getFloorEntry(lo) :
1588	>	getLowerEntry(lo));
1589	>	}
1590	>	};
1591	>	}
1592	>
1593	>	public K firstKey() {
1594	>	return key(hiEntry());
1595	>	}
1596	>
1597	>	public K lastKey() {
1598	>	return key(loEntry());
1599	>	}
1600	>
1601	>	public Map.Entry<K,V> firstEntry() {
1602	>	return hiEntry();
1603	>	}
1604	>
1605	>	public Map.Entry<K,V> lastEntry() {
1606	>	return loEntry();
1607	>	}
1608	>
1609	>	public Map.Entry<K,V> pollFirstEntry() {
1610	>	return pollHiEntry();
1611	>	}
1612	>
1613	>	public Map.Entry<K,V> pollLastEntry() {
1614	>	return pollLoEntry();
1615	>	}
1616	>
1617	>	public NavigableMap<K,V> descendingMap() {
1618	>	NavigableMap<K,V> m = descendingMapView;
1619	>	return (m != null) ? m :
1620	>	(descendingMapView =
1621	>	new AscendingSubMap(lo, loExcluded, hi, hiExcluded));
1622	>	}
1623	>
1624	>	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1625	>	return super.subFloor(key);
1626	>	}
1627	>
1628	>	@Override TreeMap.Entry<K,V> subHigher(K key) {
1629	>	return super.subLower(key);
1630		}
1631
1632	<	private boolean inRange(K key) {
1633	<	return (fromStart \|\| compare(key, fromKey) >= 0) &&
1522	<	(toEnd \|\| compare(key, toKey) < 0);
1632	>	@Override TreeMap.Entry<K,V> subFloor(K key) {
1633	>	return super.subCeiling(key);
1634		}
1635
1636	<	// This form allows the high endpoint (as well as all legit keys)
1637	<	private boolean inRange2(K key) {
1527	<	return (fromStart \|\| compare(key, fromKey) >= 0) &&
1528	<	(toEnd \|\| compare(key, toKey) <= 0);
1636	>	@Override TreeMap.Entry<K,V> subLower(K key) {
1637	>	return super.subHigher(key);
1638		}
1639		}
1640
1641		/**
1642	+	* This class exists solely for the sake of serialization
1643	+	* compatibility with previous releases of TreeMap that did not
1644	+	* support NavigableMap. It translates an old-version SubMap into
1645	+	* a new-version AscendingSubMap. This class is never otherwise
1646	+	* used.
1647	+	*/
1648	+	private class SubMap extends AbstractMap<K,V>
1649	+	implements SortedMap<K,V>, java.io.Serializable {
1650	+	private static final long serialVersionUID = -6520786458950516097L;
1651	+	private boolean fromStart = false, toEnd = false;
1652	+	private K fromKey, toKey;
1653	+	private Object readResolve() {
1654	+	return new AscendingSubMap
1655	+	(fromStart? ((K)UNBOUNDED) : fromKey, 0,
1656	+	toEnd? ((K)UNBOUNDED) : toKey, 1);
1657	+	}
1658	+	public Set<Map.Entry<K,V>> entrySet() { throw new UnsupportedOperationException(); }
1659	+	public K lastKey() { throw new UnsupportedOperationException(); }
1660	+	public K firstKey() { throw new UnsupportedOperationException(); }
1661	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new UnsupportedOperationException(); }
1662	+	public SortedMap<K,V> headMap(K toKey) { throw new UnsupportedOperationException(); }
1663	+	public SortedMap<K,V> tailMap(K fromKey) { throw new UnsupportedOperationException(); }
1664	+	public Comparator<? super K> comparator() { throw new UnsupportedOperationException(); }
1665	+	}
1666	+
1667	+	/**
1668		* TreeMap Iterator.
1669		*/
1670		abstract class PrivateEntryIterator<T> implements Iterator<T> {
#	Line 1541 \| Line 1676 \| public class TreeMap<K,V>
1676		next = first;
1677		}
1678
1679	<	public boolean hasNext() {
1679	>	public final boolean hasNext() {
1680		return next != null;
1681		}
1682
1683	<	Entry<K,V> nextEntry() {
1683	>	final Entry<K,V> nextEntry() {
1684		if (next == null)
1685		throw new NoSuchElementException();
1686		if (modCount != expectedModCount)
#	Line 1555 \| Line 1690 \| public class TreeMap<K,V>
1690		return lastReturned;
1691		}
1692
1693	+	final Entry<K,V> prevEntry() {
1694	+	if (next == null)
1695	+	throw new NoSuchElementException();
1696	+	if (modCount != expectedModCount)
1697	+	throw new ConcurrentModificationException();
1698	+	lastReturned = next;
1699	+	next = predecessor(next);
1700	+	return lastReturned;
1701	+	}
1702	+
1703		public void remove() {
1704		if (lastReturned == null)
1705		throw new IllegalStateException();
#	Line 1568 \| Line 1713 \| public class TreeMap<K,V>
1713		}
1714		}
1715
1716	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1716	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1717		EntryIterator(Entry<K,V> first) {
1718		super(first);
1719		}
1575	–
1720		public Map.Entry<K,V> next() {
1721		return nextEntry();
1722		}
1723		}
1724
1725	<	class KeyIterator extends PrivateEntryIterator<K> {
1725	>	final class ValueIterator extends PrivateEntryIterator<V> {
1726	>	ValueIterator(Entry<K,V> first) {
1727	>	super(first);
1728	>	}
1729	>	public V next() {
1730	>	return nextEntry().value;
1731	>	}
1732	>	}
1733	>
1734	>	final class KeyIterator extends PrivateEntryIterator<K> {
1735		KeyIterator(Entry<K,V> first) {
1736		super(first);
1737		}
#	Line 1587 \| Line 1740 \| public class TreeMap<K,V>
1740		}
1741		}
1742
1743	<	class ValueIterator extends PrivateEntryIterator<V> {
1744	<	ValueIterator(Entry<K,V> first) {
1743	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1744	>	DescendingKeyIterator(Entry<K,V> first) {
1745		super(first);
1746		}
1747	<	public V next() {
1748	<	return nextEntry().value;
1747	>	public K next() {
1748	>	return prevEntry().key;
1749		}
1750		}
1751
1752	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1753	<	private final K firstExcludedKey;
1752	>	/**
1753	>	* Iterators for SubMaps
1754	>	*/
1755	>	abstract class SubMapIterator<T> implements Iterator<T> {
1756	>	int expectedModCount = TreeMap.this.modCount;
1757	>	Entry<K,V> lastReturned = null;
1758	>	Entry<K,V> next;
1759	>	final K firstExcludedKey;
1760
1761	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	<	super(first);
1763	<	firstExcludedKey = (firstExcluded == null
1605	<	? null
1761	>	SubMapIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	>	next = first;
1763	>	firstExcludedKey = (firstExcluded == null ? null
1764		: firstExcluded.key);
1765		}
1766
1767	<	public boolean hasNext() {
1767	>	public final boolean hasNext() {
1768		return next != null && next.key != firstExcludedKey;
1769		}
1770
1771	<	public Map.Entry<K,V> next() {
1771	>	final Entry<K,V> nextEntry() {
1772		if (next == null \|\| next.key == firstExcludedKey)
1773		throw new NoSuchElementException();
1774	<	return nextEntry();
1775	<	}
1776	<	}
1777	<
1778	<
1621	<	/**
1622	<	* Base for Descending Iterators.
1623	<	*/
1624	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1625	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1626	<	super(first);
1774	>	if (modCount != expectedModCount)
1775	>	throw new ConcurrentModificationException();
1776	>	lastReturned = next;
1777	>	next = successor(next);
1778	>	return lastReturned;
1779		}
1780
1781	<	Entry<K,V> nextEntry() {
1782	<	if (next == null)
1781	>	final Entry<K,V> prevEntry() {
1782	>	if (next == null \|\| next.key == firstExcludedKey)
1783		throw new NoSuchElementException();
1784		if (modCount != expectedModCount)
1785		throw new ConcurrentModificationException();
#	Line 1635 \| Line 1787 \| public class TreeMap<K,V>
1787		next = predecessor(next);
1788		return lastReturned;
1789		}
1790	+
1791	+	public void remove() {
1792	+	if (lastReturned == null)
1793	+	throw new IllegalStateException();
1794	+	if (modCount != expectedModCount)
1795	+	throw new ConcurrentModificationException();
1796	+	if (lastReturned.left != null && lastReturned.right != null)
1797	+	next = lastReturned;
1798	+	deleteEntry(lastReturned);
1799	+	expectedModCount++;
1800	+	lastReturned = null;
1801	+	}
1802		}
1803
1804	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1805	<	DescendingEntryIterator(Entry<K,V> first) {
1806	<	super(first);
1804	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1805	>	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1806	>	super(first, firstExcluded);
1807		}
1808		public Map.Entry<K,V> next() {
1809		return nextEntry();
1810		}
1811		}
1812
1813	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1814	<	DescendingKeyIterator(Entry<K,V> first) {
1815	<	super(first);
1813	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1814	>	SubMapKeyIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1815	>	super(first, firstExcluded);
1816		}
1817		public K next() {
1818		return nextEntry().key;
1819		}
1820		}
1821
1822	<
1659	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1660	<	private final K lastExcludedKey;
1661	<
1822	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1823		DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1824	<	super(last);
1664	<	lastExcludedKey = (lastExcluded == null
1665	<	? null
1666	<	: lastExcluded.key);
1667	<	}
1668	<
1669	<	public boolean hasNext() {
1670	<	return next != null && next.key != lastExcludedKey;
1824	>	super(last, lastExcluded);
1825		}
1826
1827		public Map.Entry<K,V> next() {
1828	<	if (next == null \|\| next.key == lastExcludedKey)
1675	<	throw new NoSuchElementException();
1676	<	return nextEntry();
1828	>	return prevEntry();
1829		}
1678	–
1830		}
1831
1832	+	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1833	+	DescendingSubMapKeyIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1834	+	super(last, lastExcluded);
1835	+	}
1836	+	public K next() {
1837	+	return prevEntry().key;
1838	+	}
1839	+	}
1840
1841		/**
1842		* Compares two keys using the correct comparison method for this TreeMap.
1843		*/
1844	<	private int compare(K k1, K k2) {
1845	<	return (comparator==null ? ((Comparable</-/K>)k1).compareTo(k2)
1846	<	: comparator.compare((K)k1, (K)k2));
1844	>	private int compare(Object k1, Object k2) {
1845	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1846	>	: comparator.compare((K)k1, (K)k2);
1847		}
1848
1849		/**
1850	<	* Test two values for equality. Differs from o1.equals(o2) only in
1850	>	* Test two values for equality. Differs from o1.equals(o2) only in
1851		* that it copes with <tt>null</tt> o1 properly.
1852		*/
1853		private static boolean valEquals(Object o1, Object o2) {
#	Line 1724 \| Line 1883 \| public class TreeMap<K,V>
1883		/**
1884		* Returns the key.
1885		*
1886	<	* @return the key.
1886	>	* @return the key
1887		*/
1888		public K getKey() {
1889		return key;
#	Line 1733 \| Line 1892 \| public class TreeMap<K,V>
1892		/**
1893		* Returns the value associated with the key.
1894		*
1895	<	* @return the value associated with the key.
1895	>	* @return the value associated with the key
1896		*/
1897		public V getValue() {
1898		return value;
#	Line 1744 \| Line 1903 \| public class TreeMap<K,V>
1903		* value.
1904		*
1905		* @return the value associated with the key before this method was
1906	<	* called.
1906	>	* called
1907		*/
1908		public V setValue(V value) {
1909		V oldValue = this.value;
#	Line 2091 \| Line 2250 \| public class TreeMap<K,V>
2250		}
2251		}
2252
2094	–
2095	–
2253		/**
2254		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2255		* deserialize it).
#	Line 2115 \| Line 2272 \| public class TreeMap<K,V>
2272		}
2273
2274		/ Intended to be called only from TreeSet.addAll /
2275	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
2275	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2276		try {
2277		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2278		} catch (java.io.IOException cannotHappen) {
#	Line 2140 \| Line 2297 \| public class TreeMap<K,V>
2297		* to calling this method.
2298		*
2299		* @param size the number of keys (or key-value pairs) to be read from
2300	<	* the iterator or stream.
2300	>	* the iterator or stream
2301		* @param it If non-null, new entries are created from entries
2302		* or keys read from this iterator.
2303		* @param str If non-null, new entries are created from keys and
#	Line 2154 \| Line 2311 \| public class TreeMap<K,V>
2311		* @throws ClassNotFoundException propagated from readObject.
2312		* This cannot occur if str is null.
2313		*/
2314	<	private
2315	<	void buildFromSorted(int size, Iterator it,
2316	<	java.io.ObjectInputStream str,
2160	<	V defaultVal)
2314	>	private void buildFromSorted(int size, Iterator it,
2315	>	java.io.ObjectInputStream str,
2316	>	V defaultVal)
2317		throws java.io.IOException, ClassNotFoundException {
2318		this.size = size;
2319	<	root =
2320	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
2165	<	it, str, defaultVal);
2319	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2320	>	it, str, defaultVal);
2321		}
2322
2323		/**
2324		* Recursive "helper method" that does the real work of the
2325	<	* of the previous method. Identically named parameters have
2325	>	* previous method. Identically named parameters have
2326		* identical definitions. Additional parameters are documented below.
2327		* It is assumed that the comparator and size fields of the TreeMap are
2328		* already set prior to calling this method. (It ignores both fields.)
#	Line 2175 \| Line 2330 \| public class TreeMap<K,V>
2330		* @param level the current level of tree. Initial call should be 0.
2331		* @param lo the first element index of this subtree. Initial should be 0.
2332		* @param hi the last element index of this subtree. Initial should be
2333	<	* size-1.
2333	>	* size-1.
2334		* @param redLevel the level at which nodes should be red.
2335		* Must be equal to computeRedLevel for tree of this size.
2336		*/
#	Line 2259 \| Line 2414 \| public class TreeMap<K,V>
2414		level++;
2415		return level;
2416		}
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	–
2417		}

Diff Legend

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

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.28 by dl, Wed Apr 19 15:07:14 2006 UTC

Diff Legend

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.28 by dl, Wed Apr 19 15:07:14 2006 UTC