ViewVC Help

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

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

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.1 by dl, Tue Dec 28 12:14:07 2004 UTC vs.
Revision 1.14 by jsr166, Mon May 16 08:13:36 2005 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2005 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
33	>	* <p><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
#	Line 44 | Line 42 | package java.util;
42		* time, to prevent accidental unsynchronized access to the map:
43		* <pre>
44		*     Map m = Collections.synchronizedMap(new TreeMap(...));
45	<	* </pre><p>
45	>	* </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 90 | Line 91 | public class TreeMap<K,V>
91		implements NavigableMap<K,V>, Cloneable, java.io.Serializable
92		{
93		/**
94	<	* The Comparator used to maintain order in this TreeMap, or
95	<	* null if this TreeMap uses its elements natural ordering.
94	>	* The comparator used to maintain order in this tree map, or
95	>	* null if it uses the natural ordering of its keys.
96		*
97		* @serial
98		*/
#	Line 113 | Line 114 | public class TreeMap<K,V>
114		private void decrementSize()   { modCount++; size--; }
115
116		/**
117	<	* Constructs a new, empty map, sorted according to the keys' natural
118	<	* order.  All keys inserted into the map must implement the
119	<	* <tt>Comparable</tt> interface.  Furthermore, all such keys must be
120	<	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
121	<	* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
122	<	* map.  If the user attempts to put a key into the map that violates this
123	<	* constraint (for example, the user attempts to put a string key into a
124	<	* map whose keys are integers), the <tt>put(Object key, Object
125	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
126	<	*
126	<	* @see Comparable
117	>	* Constructs a new, empty tree map, using the natural ordering of its
118	>	* keys.  All keys inserted into the map must implement the {@link
119	>	* Comparable} interface.  Furthermore, all such keys must be
120	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
121	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
122	>	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
123	>	* map that violates this constraint (for example, the user attempts to
124	>	* put a string key into a map whose keys are integers), the
125	>	* <tt>put(Object key, Object value)</tt> call will throw a
126	>	* <tt>ClassCastException</tt>.
127		*/
128		public TreeMap() {
129		}
130
131		/**
132	<	* Constructs a new, empty map, sorted according to the given comparator.
133	<	* All keys inserted into the map must be <i>mutually comparable</i> by
134	<	* the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
135	<	* throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
136	<	* <tt>k2</tt> in the map.  If the user attempts to put a key into the
137	<	* map that violates this constraint, the <tt>put(Object key, Object
138	<	* value)</tt> call will throw a <tt>ClassCastException</tt>.
139	<	*
140	<	* @param c the comparator that will be used to sort this map.  A
141	<	*        <tt>null</tt> value indicates that the keys' <i>natural
142	<	*        ordering</i> should be used.
143	<	*/
144	<	public TreeMap(Comparator<? super K> c) {
145	<	this.comparator = c;
132	>	* Constructs a new, empty tree map, ordered according to the given
133	>	* comparator.  All keys inserted into the map must be <i>mutually
134	>	* comparable</i> by the given comparator: <tt>comparator.compare(k1,
135	>	* k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
136	>	* <tt>k1</tt> and <tt>k2</tt> in the map.  If the user attempts to put
137	>	* a key into the map that violates this constraint, the <tt>put(Object
138	>	* key, Object value)</tt> call will throw a
139	>	* <tt>ClassCastException</tt>.
140	>	*
141	>	* @param comparator the comparator that will be used to order this map.
142	>	*        If <tt>null</tt>, the {@linkplain Comparable natural
143	>	*        ordering} of the keys will be used.
144	>	*/
145	>	public TreeMap(Comparator<? super K> comparator) {
146	>	this.comparator = comparator;
147		}
148
149		/**
150	<	* Constructs a new map containing the same mappings as the given map,
151	<	* sorted according to the keys' <i>natural order</i>.  All keys inserted
152	<	* into the new map must implement the <tt>Comparable</tt> interface.
153	<	* Furthermore, all such keys must be <i>mutually comparable</i>:
154	<	* <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
155	<	* for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
156	<	* runs in n*log(n) time.
157	<	*
158	<	* @param  m the map whose mappings are to be placed in this map.
159	<	* @throws ClassCastException the keys in t are not Comparable, or
160	<	*         are not mutually comparable.
161	<	* @throws NullPointerException if the specified map is null.
150	>	* Constructs a new tree map containing the same mappings as the given
151	>	* map, ordered according to the <i>natural ordering</i> of its keys.
152	>	* All keys inserted into the new map must implement the {@link
153	>	* Comparable} interface.  Furthermore, all such keys must be
154	>	* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
155	>	* a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
156	>	* <tt>k2</tt> in the map.  This method runs in n*log(n) time.
157	>	*
158	>	* @param  m the map whose mappings are to be placed in this map
159	>	* @throws ClassCastException if the keys in m are not {@link Comparable},
160	>	*         or are not mutually comparable
161	>	* @throws NullPointerException if the specified map is null
162		*/
163		public TreeMap(Map<? extends K, ? extends V> m) {
164		putAll(m);
165		}
166
167		/**
168	<	* Constructs a new map containing the same mappings as the given
169	<	* <tt>SortedMap</tt>, sorted according to the same ordering.  This method
170	<	* runs in linear time.
168	>	* Constructs a new tree map containing the same mappings and
169	>	* using the same ordering as the specified sorted map.  This
170	>	* method runs in linear time.
171		*
172		* @param  m the sorted map whose mappings are to be placed in this map,
173	<	*         and whose comparator is to be used to sort this map.
174	<	* @throws NullPointerException if the specified sorted map is null.
173	>	*         and whose comparator is to be used to sort this map
174	>	* @throws NullPointerException if the specified map is null
175		*/
176		public TreeMap(SortedMap<K, ? extends V> m) {
177		comparator = m.comparator();
#	Line 187 | Line 188 | public class TreeMap<K,V>
188		/**
189		* Returns the number of key-value mappings in this map.
190		*
191	<	* @return the number of key-value mappings in this map.
191	>	* @return the number of key-value mappings in this map
192		*/
193		public int size() {
194		return size;
#	Line 197 | Line 198 | public class TreeMap<K,V>
198		* Returns <tt>true</tt> if this map contains a mapping for the specified
199		* key.
200		*
201	<	* @param key key whose presence in this map is to be tested.
201	<	*
201	>	* @param key key whose presence in this map is to be tested
202		* @return <tt>true</tt> if this map contains a mapping for the
203	<	*            specified key.
204	<	* @throws ClassCastException if the key cannot be compared with the keys
205	<	*                  currently in the map.
206	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
207	<	*                  natural ordering, or its comparator does not tolerate
208	<	*            <tt>null</tt> keys.
203	>	*         specified key
204	>	* @throws ClassCastException if the specified key cannot be compared
205	>	*         with the keys currently in the map
206	>	* @throws NullPointerException if the specified key is null
207	>	*         and this map uses natural ordering, or its comparator
208	>	*         does not permit null keys
209		*/
210		public boolean containsKey(Object key) {
211		return getEntry(key) != null;
#	Line 216 | Line 216 | public class TreeMap<K,V>
216		* specified value.  More formally, returns <tt>true</tt> if and only if
217		* this map contains at least one mapping to a value <tt>v</tt> such
218		* that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
219	<	* operation will probably require time linear in the Map size for most
220	<	* implementations of Map.
219	>	* operation requires time linear in the map size.
220		*
221	<	* @param value value whose presence in this Map is to be tested.
222	<	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
223	<	*          <tt>false</tt> otherwise.
221	>	* @param value value whose presence in this map is to be tested
222	>	* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
223	>	*         <tt>false</tt> otherwise
224		* @since 1.2
225		*/
226		public boolean containsValue(Object value) {
#	Line 250 | Line 249 | public class TreeMap<K,V>
249		}
250
251		/**
252	<	* Returns the value to which this map maps the specified key.  Returns
253	<	* <tt>null</tt> if the map contains no mapping for this key.  A return
252	>	* Returns the value to which this map maps the specified key, or
253	>	* <tt>null</tt> if the map contains no mapping for the key.  A return
254		* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
255		* map contains no mapping for the key; it's also possible that the map
256	<	* explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
256	>	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey}
257		* operation may be used to distinguish these two cases.
258		*
259	<	* @param key key whose associated value is to be returned.
259	>	* @param key key whose associated value is to be returned
260		* @return the value to which this map maps the specified key, or
261	<	*               <tt>null</tt> if the map contains no mapping for the key.
262	<	* @throws    ClassCastException key cannot be compared with the keys
263	<	*                  currently in the map.
264	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
265	<	*                  natural ordering, or its comparator does not tolerate
266	<	*                  <tt>null</tt> keys.
268	<	*
269	<	* @see #containsKey(Object)
261	>	*         <tt>null</tt> if the map contains no mapping for the key
262	>	* @throws ClassCastException if the specified key cannot be compared
263	>	*         with the keys currently in the map
264	>	* @throws NullPointerException if the specified key is null
265	>	*         and this map uses natural ordering, or its comparator
266	>	*         does not permit null keys
267		*/
268		public V get(Object key) {
269		Entry<K,V> p = getEntry(key);
270		return (p==null ? null : p.value);
271		}
272
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	–	*/
273		public Comparator<? super K> comparator() {
274		return comparator;
275		}
276
277		/**
278	<	* 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.
278	>	* @throws NoSuchElementException {@inheritDoc}
279		*/
280		public K firstKey() {
281		return key(getFirstEntry());
282		}
283
284		/**
285	<	* 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.
285	>	* @throws NoSuchElementException {@inheritDoc}
286		*/
287		public K lastKey() {
288		return key(getLastEntry());
289		}
290
291		/**
292	<	* Copies all of the mappings from the specified map to this map.  These
293	<	* mappings replace any mappings that this map had for any of the keys
294	<	* currently in the specified map.
295	<	*
296	<	* @param     map mappings to be stored in this map.
297	<	* @throws    ClassCastException class of a key or value in the specified
298	<	*                   map prevents it from being stored in this map.
299	<	*
300	<	* @throws NullPointerException if the given map is <tt>null</tt> or
301	<	*         this map does not permit <tt>null</tt> keys and a
318	<	*         key in the specified map is <tt>null</tt>.
292	>	* Copies all of the mappings from the specified map to this map.
293	>	* These mappings replace any mappings that this map had for any
294	>	* of the keys currently in the specified map.
295	>	*
296	>	* @param  map mappings to be stored in this map
297	>	* @throws ClassCastException if the class of a key or value in
298	>	*         the specified map prevents it from being stored in this map
299	>	* @throws NullPointerException if the specified map is null or
300	>	*         the specified map contains a null key and this map does not
301	>	*         permit null keys
302		*/
303		public void putAll(Map<? extends K, ? extends V> map) {
304		int mapSize = map.size();
#	Line 340 | Line 323 | public class TreeMap<K,V>
323		* does not contain an entry for the key.
324		*
325		* @return this map's entry for the given key, or <tt>null</tt> if the map
326	<	*                does not contain an entry for the key.
327	<	* @throws ClassCastException if the key cannot be compared with the keys
328	<	*                  currently in the map.
329	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
330	<	*                  natural order, or its comparator does not tolerate *
331	<	*                  <tt>null</tt> keys.
326	>	*         does not contain an entry for the key
327	>	* @throws ClassCastException if the specified key cannot be compared
328	>	*         with the keys currently in the map
329	>	* @throws NullPointerException if the specified key is null
330	>	*         and this map uses natural ordering, or its comparator
331	>	*         does not permit null keys
332		*/
333		private Entry<K,V> getEntry(Object key) {
334		// Offload comparator-based version for sake of performance
335		if (comparator != null)
336		return getEntryUsingComparator(key);
337	<	Comparable<K> k = (Comparable<K>) key;
337	>	Comparable<? super K> k = (Comparable<? super K>) key;
338		Entry<K,V> p = root;
339		while (p != null) {
340		int cmp = k.compareTo(p.key);
#	Line 525 | Line 508 | public class TreeMap<K,V>
508		}
509
510		/**
511	<	* Returns the key corresponding to the specified Entry.  Throw
512	<	* NoSuchElementException if the Entry is <tt>null</tt>.
511	>	* Returns the key corresponding to the specified Entry.
512	>	* @throws NoSuchElementException if the Entry is null
513		*/
514		private static <K> K key(Entry<K,?> e) {
515		if (e==null)
#	Line 539 | Line 522 | public class TreeMap<K,V>
522		* If the map previously contained a mapping for this key, the old
523		* value is replaced.
524		*
525	<	* @param key key with which the specified value is to be associated.
526	<	* @param value value to be associated with the specified key.
525	>	* @param key key with which the specified value is to be associated
526	>	* @param value value to be associated with the specified key
527		*
528	<	* @return previous value associated with specified key, or <tt>null</tt>
529	<	*         if there was no mapping for key.  A <tt>null</tt> return can
530	<	*         also indicate that the map previously associated <tt>null</tt>
531	<	*         with the specified key.
532	<	* @throws    ClassCastException key cannot be compared with the keys
533	<	*            currently in the map.
534	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
535	<	*         natural order, or its comparator does not tolerate
536	<	*         <tt>null</tt> keys.
528	>	* @return the previous value associated with <tt>key</tt>, or
529	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
530	>	*         (A <tt>null</tt> return can also indicate that the map
531	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
532	>	* @throws ClassCastException if the specified key cannot be compared
533	>	*         with the keys currently in the map
534	>	* @throws NullPointerException if the specified key is null
535	>	*         and this map uses natural ordering, or its comparator
536	>	*         does not permit null keys
537		*/
538		public V put(K key, V value) {
539		Entry<K,V> t = root;
540
541		if (t == null) {
542	+	if (key == null) {
543	+	if (comparator == null)
544	+	throw new NullPointerException();
545	+	comparator.compare(key, key);
546	+	}
547		incrementSize();
548		root = new Entry<K,V>(key, value, null);
549		return null;
550	<	}
550	>	}
551
552		while (true) {
553		int cmp = compare(key, t.key);
#	Line 591 | Line 579 | public class TreeMap<K,V>
579		* Removes the mapping for this key from this TreeMap if present.
580		*
581		* @param  key key for which mapping should be removed
582	<	* @return previous value associated with specified key, or <tt>null</tt>
583	<	*         if there was no mapping for key.  A <tt>null</tt> return can
584	<	*         also indicate that the map previously associated
585	<	*         <tt>null</tt> with the specified key.
586	<	*
587	<	* @throws    ClassCastException key cannot be compared with the keys
588	<	*            currently in the map.
589	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
590	<	*         natural order, or its comparator does not tolerate
603	<	*         <tt>null</tt> keys.
582	>	* @return the previous value associated with <tt>key</tt>, or
583	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
584	>	*         (A <tt>null</tt> return can also indicate that the map
585	>	*         previously associated <tt>null</tt> with <tt>key</tt>.)
586	>	* @throws ClassCastException if the specified key cannot be compared
587	>	*         with the keys currently in the map
588	>	* @throws NullPointerException if the specified key is null
589	>	*         and this map uses natural ordering, or its comparator
590	>	*         does not permit null keys
591		*/
592		public V remove(Object key) {
593		Entry<K,V> p = getEntry(key);
#	Line 613 | Line 600 | public class TreeMap<K,V>
600		}
601
602		/**
603	<	* Removes all mappings from this TreeMap.
603	>	* Removes all of the mappings from this map.
604	>	* The map will be empty after this call returns.
605		*/
606		public void clear() {
607		modCount++;
#	Line 625 | Line 613 | public class TreeMap<K,V>
613		* Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
614		* values themselves are not cloned.)
615		*
616	<	* @return a shallow copy of this Map.
616	>	* @return a shallow copy of this map
617		*/
618		public Object clone() {
619		TreeMap<K,V> clone = null;
#	Line 655 | Line 643 | public class TreeMap<K,V>
643
644		// NavigableMap API methods
645
658	–	/**
659	–	* 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	–	*/
646		public Map.Entry<K,V> firstEntry() {
647		Entry<K,V> e = getFirstEntry();
648	<	return (e == null)? null : new SnapshotEntry(e);
648	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
649		}
650
670	–	/**
671	–	* 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.
678	–	*/
651		public Map.Entry<K,V> lastEntry() {
652		Entry<K,V> e = getLastEntry();
653	<	return (e == null)? null : new SnapshotEntry(e);
653	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
654		}
655
684	–	/**
685	–	* 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.
690	–	*/
656		public Map.Entry<K,V> pollFirstEntry() {
657		Entry<K,V> p = getFirstEntry();
658	<	if (p == null)
658	>	if (p == null)
659		return null;
660	<	Map.Entry result = new SnapshotEntry(p);
660	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
661		deleteEntry(p);
662		return result;
663		}
664
700	–	/**
701	–	* 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.
706	–	*/
665		public Map.Entry<K,V> pollLastEntry() {
666		Entry<K,V> p = getLastEntry();
667	<	if (p == null)
667	>	if (p == null)
668		return null;
669	<	Map.Entry result = new SnapshotEntry(p);
669	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
670		deleteEntry(p);
671		return result;
672		}
673
674		/**
675	<	* Returns a key-value mapping associated with the least key
676	<	* greater than or equal to the given key, or <tt>null</tt> if
677	<	* there is no such entry.
678	<	*
721	<	* @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.
675	>	* @throws ClassCastException {@inheritDoc}
676	>	* @throws NullPointerException if the specified key is null
677	>	*         and this map uses natural ordering, or its comparator
678	>	*         does not permit null keys
679		*/
680	<	public Map.Entry<K,V> ceilingEntry(K key) {
681	<	Entry<K,V> e = getCeilingEntry(key);
682	<	return (e == null)? null : new SnapshotEntry(e);
680	>	public Map.Entry<K,V> lowerEntry(K key) {
681	>	Entry<K,V> e =  getLowerEntry(key);
682	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
683		}
684
735	–
685		/**
686	<	* Returns least key greater than or equal to the given key, or
687	<	* <tt>null</tt> if there is no such key.
688	<	*
689	<	* @param key the key.
741	<	* @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.
686	>	* @throws ClassCastException {@inheritDoc}
687	>	* @throws NullPointerException if the specified key is null
688	>	*         and this map uses natural ordering, or its comparator
689	>	*         does not permit null keys
690		*/
691	<	public K ceilingKey(K key) {
692	<	Entry<K,V> e = getCeilingEntry(key);
691	>	public K lowerKey(K key) {
692	>	Entry<K,V> e =  getLowerEntry(key);
693		return (e == null)? null : e.key;
694		}
695
754	–
755	–
696		/**
697	<	* Returns a key-value mapping associated with the greatest key
698	<	* less than or equal to the given key, or <tt>null</tt> if there
699	<	* is no such entry.
700	<	*
761	<	* @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.
697	>	* @throws ClassCastException {@inheritDoc}
698	>	* @throws NullPointerException if the specified key is null
699	>	*         and this map uses natural ordering, or its comparator
700	>	*         does not permit null keys
701		*/
702		public Map.Entry<K,V> floorEntry(K key) {
703		Entry<K,V> e = getFloorEntry(key);
704	<	return (e == null)? null : new SnapshotEntry(e);
704	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
705		}
706
707		/**
708	<	* Returns the greatest key
709	<	* less than or equal to the given key, or <tt>null</tt> if there
710	<	* is no such key.
711	<	*
780	<	* @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.
708	>	* @throws ClassCastException {@inheritDoc}
709	>	* @throws NullPointerException if the specified key is null
710	>	*         and this map uses natural ordering, or its comparator
711	>	*         does not permit null keys
712		*/
713		public K floorKey(K key) {
714		Entry<K,V> e = getFloorEntry(key);
#	Line 792 | Line 716 | public class TreeMap<K,V>
716		}
717
718		/**
719	<	* Returns a key-value mapping associated with the least key
720	<	* strictly greater than the given key, or <tt>null</tt> if there
721	<	* is no such entry.
722	<	*
799	<	* @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.
719	>	* @throws ClassCastException {@inheritDoc}
720	>	* @throws NullPointerException if the specified key is null
721	>	*         and this map uses natural ordering, or its comparator
722	>	*         does not permit null keys
723		*/
724	<	public Map.Entry<K,V> higherEntry(K key) {
725	<	Entry<K,V> e = getHigherEntry(key);
726	<	return (e == null)? null : new SnapshotEntry(e);
724	>	public Map.Entry<K,V> ceilingEntry(K key) {
725	>	Entry<K,V> e = getCeilingEntry(key);
726	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
727		}
728
729		/**
730	<	* Returns the least key strictly greater than the given key, or
731	<	* <tt>null</tt> if there is no such key.
732	<	*
733	<	* @param key the key.
818	<	* @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.
730	>	* @throws ClassCastException {@inheritDoc}
731	>	* @throws NullPointerException if the specified key is null
732	>	*         and this map uses natural ordering, or its comparator
733	>	*         does not permit null keys
734		*/
735	<	public K higherKey(K key) {
736	<	Entry<K,V> e = getHigherEntry(key);
735	>	public K ceilingKey(K key) {
736	>	Entry<K,V> e = getCeilingEntry(key);
737		return (e == null)? null : e.key;
738		}
739
740		/**
741	<	* Returns a key-value mapping associated with the greatest
742	<	* key strictly less than the given key, or <tt>null</tt> if there is no
743	<	* such entry.
744	<	*
836	<	* @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.
741	>	* @throws ClassCastException {@inheritDoc}
742	>	* @throws NullPointerException if the specified key is null
743	>	*         and this map uses natural ordering, or its comparator
744	>	*         does not permit null keys
745		*/
746	<	public Map.Entry<K,V> lowerEntry(K key) {
747	<	Entry<K,V> e =  getLowerEntry(key);
748	<	return (e == null)? null : new SnapshotEntry(e);
746	>	public Map.Entry<K,V> higherEntry(K key) {
747	>	Entry<K,V> e = getHigherEntry(key);
748	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
749		}
750
751		/**
752	<	* Returns the greatest key strictly less than the given key, or
753	<	* <tt>null</tt> if there is no such key.
754	<	*
755	<	* @param key the key.
855	<	* @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.
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		*/
757	<	public K lowerKey(K key) {
758	<	Entry<K,V> e =  getLowerEntry(key);
757	>	public K higherKey(K key) {
758	>	Entry<K,V> e = getHigherEntry(key);
759		return (e == null)? null : e.key;
760		}
761
#	Line 874 | Line 768 | public class TreeMap<K,V>
768		*/
769		private transient Set<Map.Entry<K,V>> entrySet = null;
770		private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
771	<	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
771	>	private transient Set<K> descendingKeySet = null;
772
773		/**
774	<	* Returns a Set view of the keys contained in this map.  The set's
775	<	* iterator will return the keys in ascending order.  The set is backed by
776	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
777	<	* the Set, and vice-versa.  The Set supports element removal, which
778	<	* removes the corresponding mapping from the map, via the
779	<	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
780	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
781	<	* the <tt>add</tt> or <tt>addAll</tt> operations.
782	<	*
783	<	* @return a set view of the keys contained in this TreeMap.
774	>	* Returns a {@link Set} view of the keys contained in this map.
775	>	* The set's iterator returns the keys in ascending order.
776	>	* The set is backed by the map, so changes to the map are
777	>	* reflected in the set, and vice-versa.  If the map is modified
778	>	* while an iteration over the set is in progress (except through
779	>	* the iterator's own <tt>remove</tt> operation), the results of
780	>	* the iteration are undefined.  The set supports element removal,
781	>	* which removes the corresponding mapping from the map, via the
782	>	* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
783	>	* <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt>
784	>	* operations.  It does not support the add or <tt>addAll</tt>
785	>	* operations.
786		*/
787		public Set<K> keySet() {
788		Set<K> ks = keySet;
#	Line 900 | Line 793 | public class TreeMap<K,V>
793		public Iterator<K> iterator() {
794		return new KeyIterator(getFirstEntry());
795		}
796	<
796	>
797		public int size() {
798		return TreeMap.this.size();
799		}
800	<
800	>
801		public boolean contains(Object o) {
802		return containsKey(o);
803		}
804	<
804	>
805		public boolean remove(Object o) {
806		int oldSize = size;
807		TreeMap.this.remove(o);
808		return size != oldSize;
809		}
810	<
810	>
811		public void clear() {
812		TreeMap.this.clear();
813		}
814		}
815
816		/**
817	<	* Returns a collection view of the values contained in this map.  The
818	<	* collection's iterator will return the values in the order that their
819	<	* corresponding keys appear in the tree.  The collection is backed by
820	<	* this <tt>TreeMap</tt> instance, so changes to this map are reflected in
821	<	* the collection, and vice-versa.  The collection supports element
822	<	* removal, which removes the corresponding mapping from the map through
823	<	* the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
824	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
825	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
826	<	*
827	<	* @return a collection view of the values contained in this map.
817	>	* Returns a {@link Collection} view of the values contained in this map.
818	>	* The collection's iterator returns the values in ascending order
819	>	* of the corresponding keys.
820	>	* The collection is backed by the map, so changes to the map are
821	>	* reflected in the collection, and vice-versa.  If the map is
822	>	* modified while an iteration over the collection is in progress
823	>	* (except through the iterator's own <tt>remove</tt> operation),
824	>	* the results of the iteration are undefined.  The collection
825	>	* supports element removal, which removes the corresponding
826	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
827	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
828	>	* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
829	>	* support the add or <tt>addAll</tt> operations.
830		*/
831		public Collection<V> values() {
832		Collection<V> vs = values;
#	Line 942 | Line 837 | public class TreeMap<K,V>
837		public Iterator<V> iterator() {
838		return new ValueIterator(getFirstEntry());
839		}
840	<
840	>
841		public int size() {
842		return TreeMap.this.size();
843		}
844	<
844	>
845		public boolean contains(Object o) {
846		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
847		if (valEquals(e.getValue(), o))
848		return true;
849		return false;
850		}
851	<
851	>
852		public boolean remove(Object o) {
853		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
854		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 858 | public class TreeMap<K,V>
858		}
859		return false;
860		}
861	<
861	>
862		public void clear() {
863		TreeMap.this.clear();
864		}
865		}
866
867		/**
868	<	* Returns a set view of the mappings contained in this map.  The set's
869	<	* iterator returns the mappings in ascending key order.  Each element in
870	<	* the returned set is a <tt>Map.Entry</tt>.  The set is backed by this
871	<	* map, so changes to this map are reflected in the set, and vice-versa.
872	<	* The set supports element removal, which removes the corresponding
873	<	* mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
868	>	* Returns a {@link Set} view of the mappings contained in this map.
869	>	* The set's iterator returns the entries in ascending key order.
870	>	* The set is backed by the map, so changes to the map are
871	>	* reflected in the set, and vice-versa.  If the map is modified
872	>	* while an iteration over the set is in progress (except through
873	>	* the iterator's own <tt>remove</tt> operation, or through the
874	>	* <tt>setValue</tt> operation on a map entry returned by the
875	>	* iterator) the results of the iteration are undefined.  The set
876	>	* supports element removal, which removes the corresponding
877	>	* mapping from the map, via the <tt>Iterator.remove</tt>,
878		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
879	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
880	<	* <tt>addAll</tt> operations.
982	<	*
983	<	* @return a set view of the mappings contained in this map.
984	<	* @see Map.Entry
879	>	* <tt>clear</tt> operations.  It does not support the
880	>	* <tt>add</tt> or <tt>addAll</tt> operations.
881		*/
882		public Set<Map.Entry<K,V>> entrySet() {
883		Set<Map.Entry<K,V>> es = entrySet;
#	Line 992 | Line 888 | public class TreeMap<K,V>
888		public Iterator<Map.Entry<K,V>> iterator() {
889		return new EntryIterator(getFirstEntry());
890		}
891	<
891	>
892		public boolean contains(Object o) {
893		if (!(o instanceof Map.Entry))
894		return false;
#	Line 1001 | Line 897 | public class TreeMap<K,V>
897		Entry<K,V> p = getEntry(entry.getKey());
898		return p != null && valEquals(p.getValue(), value);
899		}
900	<
900	>
901		public boolean remove(Object o) {
902		if (!(o instanceof Map.Entry))
903		return false;
#	Line 1014 | Line 910 | public class TreeMap<K,V>
910		}
911		return false;
912		}
913	<
913	>
914		public int size() {
915		return TreeMap.this.size();
916		}
917	<
917	>
918		public void clear() {
919		TreeMap.this.clear();
920		}
921		}
922
1027	–	/**
1028	–	* Returns a set view of the mappings contained in this map.  The
1029	–	* set's iterator returns the mappings in descrending key order.
1030	–	* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1031	–	* set is backed by this map, so changes to this map are reflected
1032	–	* in the set, and vice-versa.  The set supports element removal,
1033	–	* which removes the corresponding mapping from the TreeMap,
1034	–	* through the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1035	–	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1036	–	* 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	–	*/
923		public Set<Map.Entry<K,V>> descendingEntrySet() {
924		Set<Map.Entry<K,V>> es = descendingEntrySet;
925		return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
#	Line 1051 | Line 931 | public class TreeMap<K,V>
931		}
932		}
933
1054	–	/**
1055	–	* Returns a Set view of the keys contained in this map.  The
1056	–	* set's iterator will return the keys in descending order.  The
1057	–	* map is backed by this <tt>TreeMap</tt> instance, so changes to
1058	–	* this map are reflected in the Set, and vice-versa.  The Set
1059	–	* supports element removal, which removes the corresponding
1060	–	* mapping from the map, via the <tt>Iterator.remove</tt>,
1061	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1062	–	* and <tt>clear</tt> operations.  It does not support the
1063	–	* <tt>add</tt> or <tt>addAll</tt> operations.
1064	–	*
1065	–	* @return a set view of the keys contained in this TreeMap.
1066	–	*/
934		public Set<K> descendingKeySet() {
935		Set<K> ks = descendingKeySet;
936		return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
#	Line 1076 | Line 943 | public class TreeMap<K,V>
943		}
944
945		/**
946	<	* Returns a view of the portion of this map whose keys range from
1080	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1081	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
1082	<	* is empty.)  The returned sorted map is backed by this map, so changes
1083	<	* in the returned sorted map are reflected in this map, and vice-versa.
1084	<	* The returned sorted map supports all optional map operations.<p>
1085	<	*
1086	<	* The sorted map returned by this method will throw an
1087	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1088	<	* less than <tt>fromKey</tt> or greater than or equal to
1089	<	* <tt>toKey</tt>.<p>
1090	<	*
1091	<	* Note: this method always returns a <i>half-open range</i> (which
1092	<	* includes its low endpoint but not its high endpoint).  If you need a
1093	<	* <i>closed range</i> (which includes both endpoints), and the key type
1094	<	* allows for calculation of the successor a given key, merely request the
1095	<	* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1096	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys are
1097	<	* strings.  The following idiom obtains a view containing all of the
1098	<	* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1099	<	* and <tt>high</tt>, inclusive:
1100	<	*             <pre>    NavigableMap sub = m.submap(low, high+"\0");</pre>
1101	<	* A similar technique can be used to generate an <i>open range</i> (which
1102	<	* contains neither endpoint).  The following idiom obtains a view
1103	<	* containing all of the key-value mappings in <tt>m</tt> whose keys are
1104	<	* between <tt>low</tt> and <tt>high</tt>, exclusive:
1105	<	*             <pre>    NavigableMap sub = m.subMap(low+"\0", high);</pre>
1106	<	*
1107	<	* @param fromKey low endpoint (inclusive) of the subMap.
1108	<	* @param toKey high endpoint (exclusive) of the subMap.
1109	<	*
1110	<	* @return a view of the portion of this map whose keys range from
1111	<	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1112	<	*
1113	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1114	<	*         cannot be compared to one another using this map's comparator
1115	<	*         (or, if the map has no comparator, using natural ordering).
1116	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1117	<	*         <tt>toKey</tt>.
946	>	* @throws ClassCastException       {@inheritDoc}
947		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
948	<	*               <tt>null</tt> and this map uses natural order, or its
949	<	*               comparator does not tolerate <tt>null</tt> keys.
948	>	*         null and this map uses natural ordering, or its comparator
949	>	*         does not permit null keys
950	>	* @throws IllegalArgumentException {@inheritDoc}
951		*/
952	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
952	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
953		return new SubMap(fromKey, toKey);
954		}
955
956		/**
957	<	* Returns a view of the portion of this map whose keys are strictly less
958	<	* than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
959	<	* changes in the returned sorted map are reflected in this map, and
960	<	* vice-versa.  The returned sorted map supports all optional map
961	<	* 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.
957	>	* @throws ClassCastException       {@inheritDoc}
958	>	* @throws NullPointerException if <tt>toKey</tt> is null
959	>	*         and this map uses natural ordering, or its comparator
960	>	*         does not permit null keys
961	>	* @throws IllegalArgumentException {@inheritDoc}
962		*/
963	<	public NavigableMap<K,V> headMap(K toKey) {
963	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
964		return new SubMap(toKey, true);
965		}
966
967		/**
968	<	* Returns a view of the portion of this map whose keys are greater than
969	<	* or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
970	<	* this map, so changes in the returned sorted map are reflected in this
971	<	* map, and vice-versa.  The returned sorted map supports all optional map
972	<	* 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.
968	>	* @throws ClassCastException       {@inheritDoc}
969	>	* @throws NullPointerException if <tt>fromKey</tt> is null
970	>	*         and this map uses natural ordering, or its comparator
971	>	*         does not permit null keys
972	>	* @throws IllegalArgumentException {@inheritDoc}
973		*/
974	<	public NavigableMap<K,V> tailMap(K fromKey) {
974	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
975	>	return new SubMap(fromKey, false);
976	>	}
977	>
978	>	/**
979	>	* Equivalent to {@link #navigableSubMap} but with a return type
980	>	* conforming to the <tt>SortedMap</tt> interface.
981	>	*
982	>	* <p>{@inheritDoc}
983	>	*
984	>	* @throws ClassCastException       {@inheritDoc}
985	>	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
986	>	*         null and this map uses natural ordering, or its comparator
987	>	*         does not permit null keys
988	>	* @throws IllegalArgumentException {@inheritDoc}
989	>	*/
990	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
991	>	return new SubMap(fromKey, toKey);
992	>	}
993	>
994	>	/**
995	>	* Equivalent to {@link #navigableHeadMap} but with a return type
996	>	* conforming to the <tt>SortedMap</tt> interface.
997	>	*
998	>	* <p>{@inheritDoc}
999	>	*
1000	>	* @throws ClassCastException       {@inheritDoc}
1001	>	* @throws NullPointerException if <tt>toKey</tt> is null
1002	>	*         and this map uses natural ordering, or its comparator
1003	>	*         does not permit null keys
1004	>	* @throws IllegalArgumentException {@inheritDoc}
1005	>	*/
1006	>	public SortedMap<K,V> headMap(K toKey) {
1007	>	return new SubMap(toKey, true);
1008	>	}
1009	>
1010	>	/**
1011	>	* Equivalent to {@link #navigableTailMap} but with a return type
1012	>	* conforming to the <tt>SortedMap</tt> interface.
1013	>	*
1014	>	* <p>{@inheritDoc}
1015	>	*
1016	>	* @throws ClassCastException       {@inheritDoc}
1017	>	* @throws NullPointerException if <tt>fromKey</tt> is null
1018	>	*         and this map uses natural ordering, or its comparator
1019	>	*         does not permit null keys
1020	>	* @throws IllegalArgumentException {@inheritDoc}
1021	>	*/
1022	>	public SortedMap<K,V> tailMap(K fromKey) {
1023		return new SubMap(fromKey, false);
1024		}
1025
#	Line 1242 | Line 1062 | public class TreeMap<K,V>
1062		}
1063
1064		public boolean isEmpty() {
1065	<	return entrySet.isEmpty();
1065	>	return entrySet().isEmpty();
1066		}
1067
1068		public boolean containsKey(Object key) {
#	Line 1275 | Line 1095 | public class TreeMap<K,V>
1095		TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1096		K first = key(e);
1097		if (!toEnd && compare(first, toKey) >= 0)
1098	<	throw(new NoSuchElementException());
1098	>	throw new NoSuchElementException();
1099		return first;
1100		}
1101
#	Line 1283 | Line 1103 | public class TreeMap<K,V>
1103		TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1104		K last = key(e);
1105		if (!fromStart && compare(last, fromKey) < 0)
1106	<	throw(new NoSuchElementException());
1106	>	throw new NoSuchElementException();
1107		return last;
1108		}
1109
1110		public Map.Entry<K,V> firstEntry() {
1111	<	TreeMap.Entry<K,V> e = fromStart ?
1111	>	TreeMap.Entry<K,V> e = fromStart ?
1112		getFirstEntry() : getCeilingEntry(fromKey);
1113		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1114		return null;
#	Line 1296 | Line 1116 | public class TreeMap<K,V>
1116		}
1117
1118		public Map.Entry<K,V> lastEntry() {
1119	<	TreeMap.Entry<K,V> e = toEnd ?
1119	>	TreeMap.Entry<K,V> e = toEnd ?
1120		getLastEntry() : getLowerEntry(toKey);
1121		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1122		return null;
#	Line 1304 | Line 1124 | public class TreeMap<K,V>
1124		}
1125
1126		public Map.Entry<K,V> pollFirstEntry() {
1127	<	TreeMap.Entry<K,V> e = fromStart ?
1127	>	TreeMap.Entry<K,V> e = fromStart ?
1128		getFirstEntry() : getCeilingEntry(fromKey);
1129	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1129	>	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1130		return null;
1131	<	Map.Entry result = new SnapshotEntry(e);
1131	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1132		deleteEntry(e);
1133		return result;
1134		}
1135
1136		public Map.Entry<K,V> pollLastEntry() {
1137	<	TreeMap.Entry<K,V> e = toEnd ?
1137	>	TreeMap.Entry<K,V> e = toEnd ?
1138		getLastEntry() : getLowerEntry(toKey);
1139	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1139	>	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1140		return null;
1141	<	Map.Entry result = new SnapshotEntry(e);
1141	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1142		deleteEntry(e);
1143		return result;
1144		}
#	Line 1333 | Line 1153 | public class TreeMap<K,V>
1153
1154		public Map.Entry<K,V> ceilingEntry(K key) {
1155		TreeMap.Entry<K,V> e = subceiling(key);
1156	<	return e == null? null : new SnapshotEntry(e);
1156	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1157		}
1158
1159		public K ceilingKey(K key) {
#	Line 1352 | Line 1172 | public class TreeMap<K,V>
1172
1173		public Map.Entry<K,V> higherEntry(K key) {
1174		TreeMap.Entry<K,V> e = subhigher(key);
1175	<	return e == null? null : new SnapshotEntry(e);
1175	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1176		}
1177
1178		public K higherKey(K key) {
#	Line 1370 | Line 1190 | public class TreeMap<K,V>
1190
1191		public Map.Entry<K,V> floorEntry(K key) {
1192		TreeMap.Entry<K,V> e = subfloor(key);
1193	<	return e == null? null : new SnapshotEntry(e);
1193	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1194		}
1195
1196		public K floorKey(K key) {
#	Line 1388 | Line 1208 | public class TreeMap<K,V>
1208
1209		public Map.Entry<K,V> lowerEntry(K key) {
1210		TreeMap.Entry<K,V> e = sublower(key);
1211	<	return e == null? null : new SnapshotEntry(e);
1211	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1212		}
1213
1214		public K lowerKey(K key) {
#	Line 1396 | Line 1216 | public class TreeMap<K,V>
1216		return e == null? null : e.key;
1217		}
1218
1219	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1219	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1220
1221		public Set<Map.Entry<K,V>> entrySet() {
1222	<	return entrySet;
1222	>	Set<Map.Entry<K,V>> es = entrySet;
1223	>	return (es != null)? es : (entrySet = new EntrySetView());
1224		}
1225
1226		private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
#	Line 1456 | Line 1277 | public class TreeMap<K,V>
1277		}
1278
1279		private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1280	<	private transient Set<K> descendingKeySetView = null;
1280	>	private transient Set<K> descendingKeySetView = null;
1281
1282		public Set<Map.Entry<K,V>> descendingEntrySet() {
1283		Set<Map.Entry<K,V>> es = descendingEntrySetView;
1284	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
1284	>	return (es != null) ? es :
1285	>	(descendingEntrySetView = new DescendingEntrySetView());
1286		}
1287
1288		public Set<K> descendingKeySet() {
1289		Set<K> ks = descendingKeySetView;
1290	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
1290	>	return (ks != null) ? ks :
1291	>	(descendingKeySetView = new DescendingKeySetView());
1292		}
1293
1294		private class DescendingEntrySetView extends EntrySetView {
#	Line 1480 | Line 1303 | public class TreeMap<K,V>
1303		public Iterator<K> iterator() {
1304		return new Iterator<K>() {
1305		private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1306	<
1306	>
1307		public boolean hasNext() { return i.hasNext(); }
1308		public K next() { return i.next().getKey(); }
1309		public void remove() { i.remove(); }
1310		};
1311		}
1312	<
1312	>
1313		public int size() {
1314		return SubMap.this.size();
1315		}
1316	<
1316	>
1317		public boolean contains(Object k) {
1318		return SubMap.this.containsKey(k);
1319		}
1320		}
1321
1322	<
1500	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1322	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1323		if (!inRange2(fromKey))
1324		throw new IllegalArgumentException("fromKey out of range");
1325		if (!inRange2(toKey))
#	Line 1505 | Line 1327 | public class TreeMap<K,V>
1327		return new SubMap(fromKey, toKey);
1328		}
1329
1330	<	public NavigableMap<K,V> headMap(K toKey) {
1330	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1331		if (!inRange2(toKey))
1332		throw new IllegalArgumentException("toKey out of range");
1333		return new SubMap(fromStart, fromKey, false, toKey);
1334		}
1335
1336	<	public NavigableMap<K,V> tailMap(K fromKey) {
1336	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1337		if (!inRange2(fromKey))
1338		throw new IllegalArgumentException("fromKey out of range");
1339		return new SubMap(false, fromKey, toEnd, toKey);
1340		}
1341
1342	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1343	+	return navigableSubMap(fromKey, toKey);
1344	+	}
1345	+
1346	+	public SortedMap<K,V> headMap(K toKey) {
1347	+	return navigableHeadMap(toKey);
1348	+	}
1349	+
1350	+	public SortedMap<K,V> tailMap(K fromKey) {
1351	+	return navigableTailMap(fromKey);
1352	+	}
1353	+
1354		private boolean inRange(K key) {
1355		return (fromStart || compare(key, fromKey) >= 0) &&
1356		(toEnd     || compare(key, toKey)   <  0);
#	Line 1545 | Line 1379 | public class TreeMap<K,V>
1379		return next != null;
1380		}
1381
1382	<	Entry<K,V> nextEntry() {
1382	>	Entry<K,V> nextEntry() {
1383		if (next == null)
1384		throw new NoSuchElementException();
1385		if (modCount != expectedModCount)
#	Line 1572 | Line 1406 | public class TreeMap<K,V>
1406		EntryIterator(Entry<K,V> first) {
1407		super(first);
1408		}
1575	–
1409		public Map.Entry<K,V> next() {
1410		return nextEntry();
1411		}
#	Line 1617 | Line 1450 | public class TreeMap<K,V>
1450		}
1451		}
1452
1620	–
1453		/**
1454		* Base for Descending Iterators.
1455		*/
#	Line 1678 | Line 1510 | public class TreeMap<K,V>
1510
1511		}
1512
1681	–
1513		/**
1514		* Compares two keys using the correct comparison method for this TreeMap.
1515		*/
1516		private int compare(K k1, K k2) {
1517	<	return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
1518	<	: comparator.compare((K)k1, (K)k2));
1517	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1518	>	: comparator.compare(k1, k2);
1519		}
1520
1521		/**
#	Line 1724 | Line 1555 | public class TreeMap<K,V>
1555		/**
1556		* Returns the key.
1557		*
1558	<	* @return the key.
1558	>	* @return the key
1559		*/
1560		public K getKey() {
1561		return key;
#	Line 1733 | Line 1564 | public class TreeMap<K,V>
1564		/**
1565		* Returns the value associated with the key.
1566		*
1567	<	* @return the value associated with the key.
1567	>	* @return the value associated with the key
1568		*/
1569		public V getValue() {
1570		return value;
#	Line 1744 | Line 1575 | public class TreeMap<K,V>
1575		* value.
1576		*
1577		* @return the value associated with the key before this method was
1578	<	*           called.
1578	>	*         called
1579		*/
1580		public V setValue(V value) {
1581		V oldValue = this.value;
#	Line 2115 | Line 1946 | public class TreeMap<K,V>
1946		}
1947
1948		/** Intended to be called only from TreeSet.addAll **/
1949	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
1949	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
1950		try {
1951		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
1952		} catch (java.io.IOException cannotHappen) {
#	Line 2140 | Line 1971 | public class TreeMap<K,V>
1971		* to calling this method.
1972		*
1973		* @param size the number of keys (or key-value pairs) to be read from
1974	<	*        the iterator or stream.
1974	>	*        the iterator or stream
1975		* @param it If non-null, new entries are created from entries
1976		*        or keys read from this iterator.
1977		* @param str If non-null, new entries are created from keys and
#	Line 2175 | Line 2006 | public class TreeMap<K,V>
2006		* @param level the current level of tree. Initial call should be 0.
2007		* @param lo the first element index of this subtree. Initial should be 0.
2008		* @param hi the last element index of this subtree.  Initial should be
2009	<	*              size-1.
2009	>	*        size-1.
2010		* @param redLevel the level at which nodes should be red.
2011		*        Must be equal to computeRedLevel for tree of this size.
2012		*/
#	Line 2259 | Line 2090 | public class TreeMap<K,V>
2090		level++;
2091		return level;
2092		}
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	–
2093		}

Diff Legend

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