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.21 by jsr166, Fri Jun 24 00:26:57 2005 UTC vs.
Revision 1.33 by dl, Sat Apr 22 23:02:25 2006 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2005 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	–	import java.util.*; // for javadoc (till 6280605 is fixed)
9
10		/**
11		* A Red-Black tree based {@link NavigableMap} implementation.
#	Line 31 | Line 30 | import java.util.*; // for javadoc (till
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.
32		*
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
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>
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		* <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
#	Line 83 | Line 82 | import java.util.*; // for javadoc (till
82		* @see Comparable
83		* @see Comparator
84		* @see Collection
86	–	* @see Collections#synchronizedMap(Map)
85		* @since 1.2
86		*/
87
#	Line 97 | Line 95 | public class TreeMap<K,V>
95		*
96		* @serial
97		*/
98	<	private Comparator<? super K> comparator = null;
98	>	private final Comparator<? super K> comparator;
99
100		private transient Entry<K,V> root = null;
101
#	Line 111 | Line 109 | public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
114	–	private void incrementSize()   { modCount++; size++; }
115	–	private void decrementSize()   { modCount++; size--; }
116	–
112		/**
113		* Constructs a new, empty tree map, using the natural ordering of its
114		* keys.  All keys inserted into the map must implement the {@link
#	Line 127 | Line 122 | public class TreeMap<K,V>
122		* <tt>ClassCastException</tt>.
123		*/
124		public TreeMap() {
125	+	comparator = null;
126		}
127
128		/**
#	Line 162 | Line 158 | public class TreeMap<K,V>
158		* @throws NullPointerException if the specified map is null
159		*/
160		public TreeMap(Map<? extends K, ? extends V> m) {
161	+	comparator = null;
162		putAll(m);
163		}
164
#	Line 228 | Line 225 | public class TreeMap<K,V>
225		public boolean containsValue(Object value) {
226		return (root==null ? false :
227		(value==null ? valueSearchNull(root)
228	<	: valueSearchNonNull(root, value)));
228	>	: valueSearchNonNull(root, value)));
229		}
230
231		private boolean valueSearchNull(Entry n) {
#	Line 237 | Line 234 | public class TreeMap<K,V>
234
235		// Check left and right subtrees for value
236		return (n.left  != null && valueSearchNull(n.left)) ||
237	<	(n.right != null && valueSearchNull(n.right));
237	>	(n.right != null && valueSearchNull(n.right));
238		}
239
240		private boolean valueSearchNonNull(Entry n, Object value) {
#	Line 247 | Line 244 | public class TreeMap<K,V>
244
245		// Check left and right subtrees for value
246		return (n.left  != null && valueSearchNonNull(n.left, value)) ||
247	<	(n.right != null && valueSearchNonNull(n.right, value));
247	>	(n.right != null && valueSearchNonNull(n.right, value));
248		}
249
250		/**
251	<	* Returns the value to which this map maps the specified key, or
252	<	* <tt>null</tt> if the map contains no mapping for the key.  A return
253	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
254	<	* map contains no mapping for the key; it's also possible that the map
255	<	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey
256	<	* containsKey} operation may be used to distinguish these two cases.
251	>	* Returns the value to which the specified key is mapped,
252	>	* or {@code null} if this map contains no mapping for the key.
253	>	*
254	>	* <p>More formally, if this map contains a mapping from a key
255	>	* {@code k} to a value {@code v} such that {@code key} compares
256	>	* equal to {@code k} according to the map's ordering, then this
257	>	* method returns {@code v}; otherwise it returns {@code null}.
258	>	* (There can be at most one such mapping.)
259	>	*
260	>	* <p>A return value of {@code null} does not <i>necessarily</i>
261	>	* indicate that the map contains no mapping for the key; it's also
262	>	* possible that the map explicitly maps the key to {@code null}.
263	>	* The {@link #containsKey containsKey} operation may be used to
264	>	* distinguish these two cases.
265		*
261	–	* @param key key whose associated value is to be returned
262	–	* @return the value to which this map maps the specified key, or
263	–	*         <tt>null</tt> if the map contains no mapping for the key
266		* @throws ClassCastException if the specified key cannot be compared
267		*         with the keys currently in the map
268		* @throws NullPointerException if the specified key is null
#	Line 332 | Line 334 | public class TreeMap<K,V>
334		*         and this map uses natural ordering, or its comparator
335		*         does not permit null keys
336		*/
337	<	private Entry<K,V> getEntry(Object key) {
337	>	final Entry<K,V> getEntry(Object key) {
338		// Offload comparator-based version for sake of performance
339		if (comparator != null)
340		return getEntryUsingComparator(key);
341	+	if (key == null)
342	+	throw new NullPointerException();
343		Comparable<? super K> k = (Comparable<? super K>) key;
344		Entry<K,V> p = root;
345		while (p != null) {
#	Line 354 | Line 358 | public class TreeMap<K,V>
358		* Version of getEntry using comparator. Split off from getEntry
359		* for performance. (This is not worth doing for most methods,
360		* that are less dependent on comparator performance, but is
361	<	* worthwhile here.)
361	>	* worthwhile for get and put.)
362		*/
363	<	private Entry<K,V> getEntryUsingComparator(Object key) {
363	>	final Entry<K,V> getEntryUsingComparator(Object key) {
364		K k = (K) key;
365		Comparator<? super K> cpr = comparator;
366		Entry<K,V> p = root;
#	Line 378 | Line 382 | public class TreeMap<K,V>
382		* key; if no such entry exists (i.e., the greatest key in the Tree is less
383		* than the specified key), returns <tt>null</tt>.
384		*/
385	<	private Entry<K,V> getCeilingEntry(K key) {
385	>	final Entry<K,V> getCeilingEntry(K key) {
386		Entry<K,V> p = root;
387	<	if (p==null)
384	<	return null;
385	<
386	<	while (true) {
387	>	while (p != null) {
388		int cmp = compare(key, p.key);
389		if (cmp < 0) {
390		if (p.left != null)
#	Line 405 | Line 406 | public class TreeMap<K,V>
406		} else
407		return p;
408		}
409	+	return null;
410		}
411
412		/**
#	Line 412 | Line 414 | public class TreeMap<K,V>
414		* exists, returns the entry for the greatest key less than the specified
415		* key; if no such entry exists, returns <tt>null</tt>.
416		*/
417	<	private Entry<K,V> getFloorEntry(K key) {
417	>	final Entry<K,V> getFloorEntry(K key) {
418		Entry<K,V> p = root;
419	<	if (p==null)
418	<	return null;
419	<
420	<	while (true) {
419	>	while (p != null) {
420		int cmp = compare(key, p.key);
421		if (cmp > 0) {
422		if (p.right != null)
#	Line 440 | Line 439 | public class TreeMap<K,V>
439		return p;
440
441		}
442	+	return null;
443		}
444
445		/**
#	Line 448 | Line 448 | public class TreeMap<K,V>
448		* key greater than the specified key; if no such entry exists
449		* returns <tt>null</tt>.
450		*/
451	<	private Entry<K,V> getHigherEntry(K key) {
451	>	final Entry<K,V> getHigherEntry(K key) {
452		Entry<K,V> p = root;
453	<	if (p==null)
454	<	return null;
455	<
456	<	while (true) {
453	>	while (p != null) {
454		int cmp = compare(key, p.key);
455		if (cmp < 0) {
456		if (p.left != null)
#	Line 474 | Line 471 | public class TreeMap<K,V>
471		}
472		}
473		}
474	+	return null;
475		}
476
477		/**
#	Line 481 | Line 479 | public class TreeMap<K,V>
479		* no such entry exists (i.e., the least key in the Tree is greater than
480		* the specified key), returns <tt>null</tt>.
481		*/
482	<	private Entry<K,V> getLowerEntry(K key) {
482	>	final Entry<K,V> getLowerEntry(K key) {
483		Entry<K,V> p = root;
484	<	if (p==null)
487	<	return null;
488	<
489	<	while (true) {
484	>	while (p != null) {
485		int cmp = compare(key, p.key);
486		if (cmp > 0) {
487		if (p.right != null)
#	Line 507 | Line 502 | public class TreeMap<K,V>
502		}
503		}
504		}
505	<	}
511	<
512	<	/**
513	<	* Returns the key corresponding to the specified Entry.
514	<	* @throws NoSuchElementException if the Entry is null
515	<	*/
516	<	private static <K> K key(Entry<K,?> e) {
517	<	if (e==null)
518	<	throw new NoSuchElementException();
519	<	return e.key;
505	>	return null;
506		}
507
508		/**
#	Line 538 | Line 524 | public class TreeMap<K,V>
524		*         does not permit null keys
525		*/
526		public V put(K key, V value) {
527	+	// Offload comparator-based version for sake of performance
528	+	if (comparator != null)
529	+	return putUsingComparator(key, value);
530	+	if (key == null)
531	+	throw new NullPointerException();
532	+	Comparable<? super K> k = (Comparable<? super K>) key;
533	+	int cmp = 0;
534	+	Entry<K,V> parent = null;
535		Entry<K,V> t = root;
536	<
537	<	if (t == null) {
538	<	if (key == null) {
539	<	if (comparator == null)
540	<	throw new NullPointerException();
541	<	comparator.compare(key, key);
542	<	}
543	<	incrementSize();
544	<	root = new Entry<K,V>(key, value, null);
551	<	return null;
536	>	while (t != null) {
537	>	parent = t;
538	>	cmp = k.compareTo(t.key);
539	>	if (cmp < 0)
540	>	t = t.left;
541	>	else if (cmp > 0)
542	>	t = t.right;
543	>	else
544	>	return t.setValue(value);
545		}
546	+	Entry<K,V> e = new Entry<K,V>((K)k, value, parent);
547	+	size++;
548	+	modCount++;
549	+	if (parent != null) {
550	+	if (cmp < 0)
551	+	parent.left = e;
552	+	else
553	+	parent.right = e;
554	+	fixAfterInsertion(e);
555	+	}
556	+	else
557	+	root = e;
558	+	return null;
559	+	}
560
561	<	while (true) {
562	<	int cmp = compare(key, t.key);
563	<	if (cmp == 0) {
561	>	/**
562	>	* Version of put using comparator. Split off from put for
563	>	* performance.
564	>	*/
565	>	final V putUsingComparator(K key, V value) {
566	>	Comparator<? super K> cpr = comparator;
567	>	int cmp = 0;
568	>	Entry<K,V> parent = null;
569	>	Entry<K,V> t = root;
570	>	if (t == null)
571	>	cpr.compare(key, key); // type check
572	>	while (t != null) {
573	>	parent = t;
574	>	cmp = cpr.compare(key, t.key);
575	>	if (cmp < 0)
576	>	t = t.left;
577	>	else if (cmp > 0)
578	>	t = t.right;
579	>	else
580		return t.setValue(value);
558	–	} else if (cmp < 0) {
559	–	if (t.left != null) {
560	–	t = t.left;
561	–	} else {
562	–	incrementSize();
563	–	t.left = new Entry<K,V>(key, value, t);
564	–	fixAfterInsertion(t.left);
565	–	return null;
566	–	}
567	–	} else { // cmp > 0
568	–	if (t.right != null) {
569	–	t = t.right;
570	–	} else {
571	–	incrementSize();
572	–	t.right = new Entry<K,V>(key, value, t);
573	–	fixAfterInsertion(t.right);
574	–	return null;
575	–	}
576	–	}
581		}
582	+	Entry<K,V> e = new Entry<K,V>(key, value, parent);
583	+	size++;
584	+	modCount++;
585	+	if (parent != null) {
586	+	if (cmp < 0)
587	+	parent.left = e;
588	+	else
589	+	parent.right = e;
590	+	fixAfterInsertion(e);
591	+	}
592	+	else
593	+	root = e;
594	+	return null;
595		}
596
597		/**
#	Line 630 | Line 647 | public class TreeMap<K,V>
647		clone.size = 0;
648		clone.modCount = 0;
649		clone.entrySet = null;
650	<	clone.descendingEntrySet = null;
651	<	clone.descendingKeySet = null;
650	>	clone.navigableKeySet = null;
651	>	clone.descendingMap = null;
652
653		// Initialize clone with our mappings
654		try {
#	Line 645 | Line 662 | public class TreeMap<K,V>
662
663		// NavigableMap API methods
664
665	+	/**
666	+	* @since 1.6
667	+	*/
668		public Map.Entry<K,V> firstEntry() {
669	<	Entry<K,V> e = getFirstEntry();
650	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
669	>	return exportEntry(getFirstEntry());
670		}
671
672	+	/**
673	+	* @since 1.6
674	+	*/
675		public Map.Entry<K,V> lastEntry() {
676	<	Entry<K,V> e = getLastEntry();
655	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
676	>	return exportEntry(getLastEntry());
677		}
678
679	+	/**
680	+	* @since 1.6
681	+	*/
682		public Map.Entry<K,V> pollFirstEntry() {
683		Entry<K,V> p = getFirstEntry();
684	<	if (p == null)
685	<	return null;
686	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
663	<	deleteEntry(p);
684	>	Map.Entry<K,V> result = exportEntry(p);
685	>	if (p != null)
686	>	deleteEntry(p);
687		return result;
688		}
689
690	+	/**
691	+	* @since 1.6
692	+	*/
693		public Map.Entry<K,V> pollLastEntry() {
694		Entry<K,V> p = getLastEntry();
695	<	if (p == null)
696	<	return null;
697	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
672	<	deleteEntry(p);
695	>	Map.Entry<K,V> result = exportEntry(p);
696	>	if (p != null)
697	>	deleteEntry(p);
698		return result;
699		}
700
#	Line 678 | Line 703 | public class TreeMap<K,V>
703		* @throws NullPointerException if the specified key is null
704		*         and this map uses natural ordering, or its comparator
705		*         does not permit null keys
706	+	* @since 1.6
707		*/
708		public Map.Entry<K,V> lowerEntry(K key) {
709	<	Entry<K,V> e =  getLowerEntry(key);
684	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
709	>	return exportEntry(getLowerEntry(key));
710		}
711
712		/**
#	Line 689 | Line 714 | public class TreeMap<K,V>
714		* @throws NullPointerException if the specified key is null
715		*         and this map uses natural ordering, or its comparator
716		*         does not permit null keys
717	+	* @since 1.6
718		*/
719		public K lowerKey(K key) {
720	<	Entry<K,V> e =  getLowerEntry(key);
695	<	return (e == null)? null : e.key;
720	>	return keyOrNull(getLowerEntry(key));
721		}
722
723		/**
#	Line 700 | Line 725 | public class TreeMap<K,V>
725		* @throws NullPointerException if the specified key is null
726		*         and this map uses natural ordering, or its comparator
727		*         does not permit null keys
728	+	* @since 1.6
729		*/
730		public Map.Entry<K,V> floorEntry(K key) {
731	<	Entry<K,V> e = getFloorEntry(key);
706	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
731	>	return exportEntry(getFloorEntry(key));
732		}
733
734		/**
#	Line 711 | Line 736 | public class TreeMap<K,V>
736		* @throws NullPointerException if the specified key is null
737		*         and this map uses natural ordering, or its comparator
738		*         does not permit null keys
739	+	* @since 1.6
740		*/
741		public K floorKey(K key) {
742	<	Entry<K,V> e = getFloorEntry(key);
717	<	return (e == null)? null : e.key;
742	>	return keyOrNull(getFloorEntry(key));
743		}
744
745		/**
#	Line 722 | Line 747 | public class TreeMap<K,V>
747		* @throws NullPointerException if the specified key is null
748		*         and this map uses natural ordering, or its comparator
749		*         does not permit null keys
750	+	* @since 1.6
751		*/
752		public Map.Entry<K,V> ceilingEntry(K key) {
753	<	Entry<K,V> e = getCeilingEntry(key);
728	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
753	>	return exportEntry(getCeilingEntry(key));
754		}
755
756		/**
#	Line 733 | Line 758 | public class TreeMap<K,V>
758		* @throws NullPointerException if the specified key is null
759		*         and this map uses natural ordering, or its comparator
760		*         does not permit null keys
761	+	* @since 1.6
762		*/
763		public K ceilingKey(K key) {
764	<	Entry<K,V> e = getCeilingEntry(key);
739	<	return (e == null)? null : e.key;
764	>	return keyOrNull(getCeilingEntry(key));
765		}
766
767		/**
#	Line 744 | Line 769 | public class TreeMap<K,V>
769		* @throws NullPointerException if the specified key is null
770		*         and this map uses natural ordering, or its comparator
771		*         does not permit null keys
772	+	* @since 1.6
773		*/
774		public Map.Entry<K,V> higherEntry(K key) {
775	<	Entry<K,V> e = getHigherEntry(key);
750	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
775	>	return exportEntry(getHigherEntry(key));
776		}
777
778		/**
#	Line 755 | Line 780 | public class TreeMap<K,V>
780		* @throws NullPointerException if the specified key is null
781		*         and this map uses natural ordering, or its comparator
782		*         does not permit null keys
783	+	* @since 1.6
784		*/
785		public K higherKey(K key) {
786	<	Entry<K,V> e = getHigherEntry(key);
761	<	return (e == null)? null : e.key;
786	>	return keyOrNull(getHigherEntry(key));
787		}
788
789		// Views
#	Line 768 | Line 793 | public class TreeMap<K,V>
793		* the first time this view is requested.  Views are stateless, so
794		* there's no reason to create more than one.
795		*/
796	<	private transient Set<Map.Entry<K,V>> entrySet = null;
797	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
798	<	private transient Set<K> descendingKeySet = null;
796	>	private transient EntrySet entrySet = null;
797	>	private transient KeySet<K> navigableKeySet = null;
798	>	private transient NavigableMap<K,V> descendingMap = null;
799
800		/**
801		* Returns a {@link Set} view of the keys contained in this map.
#	Line 787 | Line 812 | public class TreeMap<K,V>
812		* operations.
813		*/
814		public Set<K> keySet() {
815	<	Set<K> ks = keySet;
791	<	return (ks != null) ? ks : (keySet = new KeySet());
815	>	return navigableKeySet();
816		}
817
818	<	class KeySet extends AbstractSet<K> {
819	<	public Iterator<K> iterator() {
820	<	return new KeyIterator(getFirstEntry());
821	<	}
822	<
823	<	public int size() {
824	<	return TreeMap.this.size();
801	<	}
802	<
803	<	public boolean contains(Object o) {
804	<	return containsKey(o);
805	<	}
806	<
807	<	public boolean remove(Object o) {
808	<	int oldSize = size;
809	<	TreeMap.this.remove(o);
810	<	return size != oldSize;
811	<	}
818	>	/**
819	>	* @since 1.6
820	>	*/
821	>	public NavigableSet<K> navigableKeySet() {
822	>	KeySet<K> nks = navigableKeySet;
823	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
824	>	}
825
826	<	public void clear() {
827	<	TreeMap.this.clear();
828	<	}
826	>	/**
827	>	* @since 1.6
828	>	*/
829	>	public NavigableSet<K> descendingKeySet() {
830	>	return descendingMap().navigableKeySet();
831		}
832
833		/**
#	Line 835 | Line 850 | public class TreeMap<K,V>
850		return (vs != null) ? vs : (values = new Values());
851		}
852
853	+	/**
854	+	* Returns a {@link Set} view of the mappings contained in this map.
855	+	* The set's iterator returns the entries in ascending key order.
856	+	* The set is backed by the map, so changes to the map are
857	+	* reflected in the set, and vice-versa.  If the map is modified
858	+	* while an iteration over the set is in progress (except through
859	+	* the iterator's own <tt>remove</tt> operation, or through the
860	+	* <tt>setValue</tt> operation on a map entry returned by the
861	+	* iterator) the results of the iteration are undefined.  The set
862	+	* supports element removal, which removes the corresponding
863	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
864	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
865	+	* <tt>clear</tt> operations.  It does not support the
866	+	* <tt>add</tt> or <tt>addAll</tt> operations.
867	+	*/
868	+	public Set<Map.Entry<K,V>> entrySet() {
869	+	EntrySet es = entrySet;
870	+	return (es != null) ? es : (entrySet = new EntrySet());
871	+	}
872	+
873	+	/**
874	+	* @since 1.6
875	+	*/
876	+	public NavigableMap<K, V> descendingMap() {
877	+	NavigableMap<K, V> km = descendingMap;
878	+	return (km != null) ? km :
879	+	(descendingMap = new DescendingSubMap(this,
880	+	true, null, true,
881	+	true, null, true));
882	+	}
883	+
884	+	/**
885	+	* @throws ClassCastException       {@inheritDoc}
886	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
887	+	*         null and this map uses natural ordering, or its comparator
888	+	*         does not permit null keys
889	+	* @throws IllegalArgumentException {@inheritDoc}
890	+	* @since 1.6
891	+	*/
892	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
893	+	K toKey,   boolean toInclusive) {
894	+	return new AscendingSubMap(this,
895	+	false, fromKey, fromInclusive,
896	+	false, toKey,   toInclusive);
897	+	}
898	+
899	+	/**
900	+	* @throws ClassCastException       {@inheritDoc}
901	+	* @throws NullPointerException if <tt>toKey</tt> is null
902	+	*         and this map uses natural ordering, or its comparator
903	+	*         does not permit null keys
904	+	* @throws IllegalArgumentException {@inheritDoc}
905	+	* @since 1.6
906	+	*/
907	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
908	+	return new AscendingSubMap(this,
909	+	true,  null,  true,
910	+	false, toKey, inclusive);
911	+	}
912	+
913	+	/**
914	+	* @throws ClassCastException       {@inheritDoc}
915	+	* @throws NullPointerException if <tt>fromKey</tt> is null
916	+	*         and this map uses natural ordering, or its comparator
917	+	*         does not permit null keys
918	+	* @throws IllegalArgumentException {@inheritDoc}
919	+	* @since 1.6
920	+	*/
921	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
922	+	return new AscendingSubMap(this,
923	+	false, fromKey, inclusive,
924	+	true,  null,    true);
925	+	}
926	+
927	+	/**
928	+	* @throws ClassCastException       {@inheritDoc}
929	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
930	+	*         null and this map uses natural ordering, or its comparator
931	+	*         does not permit null keys
932	+	* @throws IllegalArgumentException {@inheritDoc}
933	+	*/
934	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
935	+	return subMap(fromKey, true, toKey, false);
936	+	}
937	+
938	+	/**
939	+	* @throws ClassCastException       {@inheritDoc}
940	+	* @throws NullPointerException if <tt>toKey</tt> is null
941	+	*         and this map uses natural ordering, or its comparator
942	+	*         does not permit null keys
943	+	* @throws IllegalArgumentException {@inheritDoc}
944	+	*/
945	+	public SortedMap<K,V> headMap(K toKey) {
946	+	return headMap(toKey, false);
947	+	}
948	+
949	+	/**
950	+	* @throws ClassCastException       {@inheritDoc}
951	+	* @throws NullPointerException if <tt>fromKey</tt> is null
952	+	*         and this map uses natural ordering, or its comparator
953	+	*         does not permit null keys
954	+	* @throws IllegalArgumentException {@inheritDoc}
955	+	*/
956	+	public SortedMap<K,V> tailMap(K fromKey) {
957	+	return tailMap(fromKey, true);
958	+	}
959	+
960	+	// View class support
961	+
962		class Values extends AbstractCollection<V> {
963		public Iterator<V> iterator() {
964		return new ValueIterator(getFirstEntry());
#	Line 866 | Line 990 | public class TreeMap<K,V>
990		}
991		}
992
869	–	/**
870	–	* Returns a {@link Set} view of the mappings contained in this map.
871	–	* The set's iterator returns the entries in ascending key order.
872	–	* The set is backed by the map, so changes to the map are
873	–	* reflected in the set, and vice-versa.  If the map is modified
874	–	* while an iteration over the set is in progress (except through
875	–	* the iterator's own <tt>remove</tt> operation, or through the
876	–	* <tt>setValue</tt> operation on a map entry returned by the
877	–	* iterator) the results of the iteration are undefined.  The set
878	–	* supports element removal, which removes the corresponding
879	–	* mapping from the map, via the <tt>Iterator.remove</tt>,
880	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
881	–	* <tt>clear</tt> operations.  It does not support the
882	–	* <tt>add</tt> or <tt>addAll</tt> operations.
883	–	*/
884	–	public Set<Map.Entry<K,V>> entrySet() {
885	–	Set<Map.Entry<K,V>> es = entrySet;
886	–	return (es != null) ? es : (entrySet = new EntrySet());
887	–	}
888	–
993		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
994		public Iterator<Map.Entry<K,V>> iterator() {
995		return new EntryIterator(getFirstEntry());
#	Line 922 | Line 1026 | public class TreeMap<K,V>
1026		}
1027		}
1028
1029	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1030	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
1031	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1032	<	}
1029	>	/*
1030	>	* Unlike Values and EntrySet, the KeySet class is static,
1031	>	* delegating to a NavigableMap to allow use by SubMaps, which
1032	>	* outweighs the ugliness of needing type-tests for the following
1033	>	* Iterator methods that are defined appropriately in main versus
1034	>	* submap classes.
1035	>	*/
1036
1037	<	class DescendingEntrySet extends EntrySet {
1038	<	public Iterator<Map.Entry<K,V>> iterator() {
932	<	return new DescendingEntryIterator(getLastEntry());
933	<	}
1037	>	Iterator<K> keyIterator() {
1038	>	return new KeyIterator(getFirstEntry());
1039		}
1040
1041	<	public Set<K> descendingKeySet() {
1042	<	Set<K> ks = descendingKeySet;
938	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1041	>	Iterator<K> descendingKeyIterator() {
1042	>	return new DescendingKeyIterator(getFirstEntry());
1043		}
1044
1045	<	class DescendingKeySet extends KeySet {
1046	<	public Iterator<K> iterator() {
1047	<	return new DescendingKeyIterator(getLastEntry());
1045	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1046	>	private final NavigableMap<E, Object> m;
1047	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1048	>
1049	>	public Iterator<E> iterator() {
1050	>	if (m instanceof TreeMap)
1051	>	return ((TreeMap<E,Object>)m).keyIterator();
1052	>	else
1053	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1054	>	}
1055	>
1056	>	public Iterator<E> descendingIterator() {
1057	>	if (m instanceof TreeMap)
1058	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1059	>	else
1060	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1061	>	}
1062	>
1063	>	public int size() { return m.size(); }
1064	>	public boolean isEmpty() { return m.isEmpty(); }
1065	>	public boolean contains(Object o) { return m.containsKey(o); }
1066	>	public void clear() { m.clear(); }
1067	>	public E lower(E e) { return m.lowerKey(e); }
1068	>	public E floor(E e) { return m.floorKey(e); }
1069	>	public E ceiling(E e) { return m.ceilingKey(e); }
1070	>	public E higher(E e) { return m.higherKey(e); }
1071	>	public E first() { return m.firstKey(); }
1072	>	public E last() { return m.lastKey(); }
1073	>	public Comparator<? super E> comparator() { return m.comparator(); }
1074	>	public E pollFirst() {
1075	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1076	>	return e == null? null : e.getKey();
1077	>	}
1078	>	public E pollLast() {
1079	>	Map.Entry<E,Object> e = m.pollLastEntry();
1080	>	return e == null? null : e.getKey();
1081	>	}
1082	>	public boolean remove(Object o) {
1083	>	int oldSize = size();
1084	>	m.remove(o);
1085	>	return size() != oldSize;
1086	>	}
1087	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1088	>	E toElement, boolean toInclusive) {
1089	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1090	>	toElement,   toInclusive));
1091	>	}
1092	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1093	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1094	>	}
1095	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1096	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1097	>	}
1098	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1099	>	return subSet(fromElement, true, toElement, false);
1100	>	}
1101	>	public SortedSet<E> headSet(E toElement) {
1102	>	return headSet(toElement, false);
1103	>	}
1104	>	public SortedSet<E> tailSet(E fromElement) {
1105	>	return tailSet(fromElement, true);
1106	>	}
1107	>	public NavigableSet<E> descendingSet() {
1108	>	return new TreeSet(m.descendingMap());
1109		}
1110		}
1111
1112		/**
1113	<	* @throws ClassCastException       {@inheritDoc}
949	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
950	<	*         null and this map uses natural ordering, or its comparator
951	<	*         does not permit null keys
952	<	* @throws IllegalArgumentException {@inheritDoc}
1113	>	* Base class for TreeMap Iterators
1114		*/
1115	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1116	<	return new SubMap(fromKey, toKey);
1115	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1116	>	Entry<K,V> next;
1117	>	Entry<K,V> lastReturned;
1118	>	int expectedModCount;
1119	>
1120	>	PrivateEntryIterator(Entry<K,V> first) {
1121	>	expectedModCount = modCount;
1122	>	lastReturned = null;
1123	>	next = first;
1124	>	}
1125	>
1126	>	public final boolean hasNext() {
1127	>	return next != null;
1128	>	}
1129	>
1130	>	final Entry<K,V> nextEntry() {
1131	>	Entry<K,V> e = lastReturned = next;
1132	>	if (e == null)
1133	>	throw new NoSuchElementException();
1134	>	if (modCount != expectedModCount)
1135	>	throw new ConcurrentModificationException();
1136	>	next = successor(e);
1137	>	return e;
1138	>	}
1139	>
1140	>	final Entry<K,V> prevEntry() {
1141	>	Entry<K,V> e = lastReturned= next;
1142	>	if (e == null)
1143	>	throw new NoSuchElementException();
1144	>	if (modCount != expectedModCount)
1145	>	throw new ConcurrentModificationException();
1146	>	next = predecessor(e);
1147	>	return e;
1148	>	}
1149	>
1150	>	public void remove() {
1151	>	if (lastReturned == null)
1152	>	throw new IllegalStateException();
1153	>	if (modCount != expectedModCount)
1154	>	throw new ConcurrentModificationException();
1155	>	if (lastReturned.left != null && lastReturned.right != null)
1156	>	next = lastReturned;
1157	>	deleteEntry(lastReturned);
1158	>	expectedModCount++;
1159	>	lastReturned = null;
1160	>	}
1161	>	}
1162	>
1163	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1164	>	EntryIterator(Entry<K,V> first) {
1165	>	super(first);
1166	>	}
1167	>	public Map.Entry<K,V> next() {
1168	>	return nextEntry();
1169	>	}
1170		}
1171
1172	+	final class ValueIterator extends PrivateEntryIterator<V> {
1173	+	ValueIterator(Entry<K,V> first) {
1174	+	super(first);
1175	+	}
1176	+	public V next() {
1177	+	return nextEntry().value;
1178	+	}
1179	+	}
1180	+
1181	+	final class KeyIterator extends PrivateEntryIterator<K> {
1182	+	KeyIterator(Entry<K,V> first) {
1183	+	super(first);
1184	+	}
1185	+	public K next() {
1186	+	return nextEntry().key;
1187	+	}
1188	+	}
1189	+
1190	+	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1191	+	DescendingKeyIterator(Entry<K,V> first) {
1192	+	super(first);
1193	+	}
1194	+	public K next() {
1195	+	return prevEntry().key;
1196	+	}
1197	+	}
1198	+
1199	+	// Little utilities
1200	+
1201		/**
1202	<	* @throws ClassCastException       {@inheritDoc}
960	<	* @throws NullPointerException if <tt>toKey</tt> is null
961	<	*         and this map uses natural ordering, or its comparator
962	<	*         does not permit null keys
963	<	* @throws IllegalArgumentException {@inheritDoc}
1202	>	* Compares two keys using the correct comparison method for this TreeMap.
1203		*/
1204	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1205	<	return new SubMap(toKey, true);
1204	>	final int compare(Object k1, Object k2) {
1205	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1206	>	: comparator.compare((K)k1, (K)k2);
1207		}
1208
1209		/**
1210	<	* @throws ClassCastException       {@inheritDoc}
1211	<	* @throws NullPointerException if <tt>fromKey</tt> is null
972	<	*         and this map uses natural ordering, or its comparator
973	<	*         does not permit null keys
974	<	* @throws IllegalArgumentException {@inheritDoc}
1210	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1211	>	* that it copes with <tt>null</tt> o1 properly.
1212		*/
1213	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1214	<	return new SubMap(fromKey, false);
1213	>	final static boolean valEquals(Object o1, Object o2) {
1214	>	return (o1==null ? o2==null : o1.equals(o2));
1215		}
1216
1217		/**
1218	<	* Equivalent to {@link #navigableSubMap} but with a return type
982	<	* conforming to the <tt>SortedMap</tt> interface.
983	<	*
984	<	* <p>{@inheritDoc}
985	<	*
986	<	* @throws ClassCastException       {@inheritDoc}
987	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
988	<	*         null and this map uses natural ordering, or its comparator
989	<	*         does not permit null keys
990	<	* @throws IllegalArgumentException {@inheritDoc}
1218	>	* Return SimpleImmutableEntry for entry, or null if null
1219		*/
1220	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1221	<	return new SubMap(fromKey, toKey);
1220	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1221	>	return e == null? null :
1222	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1223		}
1224
1225		/**
1226	<	* Equivalent to {@link #navigableHeadMap} but with a return type
998	<	* conforming to the <tt>SortedMap</tt> interface.
999	<	*
1000	<	* <p>{@inheritDoc}
1001	<	*
1002	<	* @throws ClassCastException       {@inheritDoc}
1003	<	* @throws NullPointerException if <tt>toKey</tt> is null
1004	<	*         and this map uses natural ordering, or its comparator
1005	<	*         does not permit null keys
1006	<	* @throws IllegalArgumentException {@inheritDoc}
1226	>	* Return key for entry, or null if null
1227		*/
1228	<	public SortedMap<K,V> headMap(K toKey) {
1229	<	return new SubMap(toKey, true);
1228	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1229	>	return e == null? null : e.key;
1230		}
1231
1232		/**
1233	<	* Equivalent to {@link #navigableTailMap} but with a return type
1234	<	* conforming to the <tt>SortedMap</tt> interface.
1015	<	*
1016	<	* <p>{@inheritDoc}
1017	<	*
1018	<	* @throws ClassCastException       {@inheritDoc}
1019	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1020	<	*         and this map uses natural ordering, or its comparator
1021	<	*         does not permit null keys
1022	<	* @throws IllegalArgumentException {@inheritDoc}
1233	>	* Returns the key corresponding to the specified Entry.
1234	>	* @throws NoSuchElementException if the Entry is null
1235		*/
1236	<	public SortedMap<K,V> tailMap(K fromKey) {
1237	<	return new SubMap(fromKey, false);
1236	>	static <K> K key(Entry<K,?> e) {
1237	>	if (e==null)
1238	>	throw new NoSuchElementException();
1239	>	return e.key;
1240		}
1241
1028	–	private class SubMap
1029	–	extends AbstractMap<K,V>
1030	–	implements NavigableMap<K,V>, java.io.Serializable {
1031	–	private static final long serialVersionUID = -6520786458950516097L;
1242
1243	<	/**
1244	<	* fromKey is significant only if fromStart is false.  Similarly,
1245	<	* toKey is significant only if toStart is false.
1243	>	// SubMaps
1244	>
1245	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1246	>	implements NavigableMap<K,V>, java.io.Serializable {
1247	>	/*
1248	>	* The backing map.
1249		*/
1250	<	private boolean fromStart = false, toEnd = false;
1038	<	private K fromKey, toKey;
1250	>	final TreeMap<K,V> m;
1251
1252	<	SubMap(K fromKey, K toKey) {
1253	<	if (compare(fromKey, toKey) > 0)
1254	<	throw new IllegalArgumentException("fromKey > toKey");
1255	<	this.fromKey = fromKey;
1256	<	this.toKey = toKey;
1257	<	}
1252	>	/*
1253	>	* Endpoints are represented as triples (fromStart, lo,
1254	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1255	>	* true, then the low (absolute) bound is the start of the
1256	>	* backing map, and the other values are ignored. Otherwise,
1257	>	* if loInclusive is true, lo is the inclusive bound, else lo
1258	>	* is the exclusive bound. Similarly for the upper bound.
1259	>	*/
1260
1261	<	SubMap(K key, boolean headMap) {
1262	<	compare(key, key); // Type-check key
1263	<
1264	<	if (headMap) {
1265	<	fromStart = true;
1266	<	toKey = key;
1261	>	final K lo, hi;
1262	>	final boolean fromStart, toEnd;
1263	>	final boolean loInclusive, hiInclusive;
1264	>
1265	>	NavigableSubMap(TreeMap<K,V> m,
1266	>	boolean fromStart, K lo, boolean loInclusive,
1267	>	boolean toEnd,     K hi, boolean hiInclusive) {
1268	>	if (!fromStart && !toEnd) {
1269	>	if (m.compare(lo, hi) > 0)
1270	>	throw new IllegalArgumentException("fromKey > toKey");
1271		} else {
1272	<	toEnd = true;
1273	<	fromKey = key;
1272	>	if (!fromStart) // type check
1273	>	m.compare(lo, lo);
1274	>	if (!toEnd)
1275	>	m.compare(hi, hi);
1276		}
1057	–	}
1277
1278	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1278	>	this.m = m;
1279		this.fromStart = fromStart;
1280	<	this.fromKey= fromKey;
1280	>	this.lo = lo;
1281	>	this.loInclusive = loInclusive;
1282		this.toEnd = toEnd;
1283	<	this.toKey = toKey;
1283	>	this.hi = hi;
1284	>	this.hiInclusive = hiInclusive;
1285	>	}
1286	>
1287	>	// internal utilities
1288	>
1289	>	final boolean tooLow(Object key) {
1290	>	if (!fromStart) {
1291	>	int c = m.compare(key, lo);
1292	>	if (c < 0 || (c == 0 && !loInclusive))
1293	>	return true;
1294	>	}
1295	>	return false;
1296	>	}
1297	>
1298	>	final boolean tooHigh(Object key) {
1299	>	if (!toEnd) {
1300	>	int c = m.compare(key, hi);
1301	>	if (c > 0 || (c == 0 && !hiInclusive))
1302	>	return true;
1303	>	}
1304	>	return false;
1305		}
1306
1307	+	final boolean inRange(Object key) {
1308	+	return !tooLow(key) && !tooHigh(key);
1309	+	}
1310	+
1311	+	final boolean inClosedRange(Object key) {
1312	+	return (fromStart || m.compare(key, lo) >= 0)
1313	+	&& (toEnd || m.compare(hi, key) >= 0);
1314	+	}
1315	+
1316	+	final boolean inRange(Object key, boolean inclusive) {
1317	+	return inclusive ? inRange(key) : inClosedRange(key);
1318	+	}
1319	+
1320	+	/*
1321	+	* Absolute versions of relation operations.
1322	+	* Subclasses map to these using like-named "sub"
1323	+	* versions that invert senses for descending maps
1324	+	*/
1325	+
1326	+	final TreeMap.Entry<K,V> absLowest() {
1327	+	TreeMap.Entry<K,V> e =
1328	+	(fromStart ?  m.getFirstEntry() :
1329	+	(loInclusive ? m.getCeilingEntry(lo) :
1330	+	m.getHigherEntry(lo)));
1331	+	return (e == null || tooHigh(e.key)) ? null : e;
1332	+	}
1333	+
1334	+	final TreeMap.Entry<K,V> absHighest() {
1335	+	TreeMap.Entry<K,V> e =
1336	+	(toEnd ?  m.getLastEntry() :
1337	+	(hiInclusive ?  m.getFloorEntry(hi) :
1338	+	m.getLowerEntry(hi)));
1339	+	return (e == null || tooLow(e.key)) ? null : e;
1340	+	}
1341	+
1342	+	final TreeMap.Entry<K,V> absCeiling(K key) {
1343	+	if (tooLow(key))
1344	+	return absLowest();
1345	+	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1346	+	return (e == null || tooHigh(e.key)) ? null : e;
1347	+	}
1348	+
1349	+	final TreeMap.Entry<K,V> absHigher(K key) {
1350	+	if (tooLow(key))
1351	+	return absLowest();
1352	+	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1353	+	return (e == null || tooHigh(e.key)) ? null : e;
1354	+	}
1355	+
1356	+	final TreeMap.Entry<K,V> absFloor(K key) {
1357	+	if (tooHigh(key))
1358	+	return absHighest();
1359	+	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1360	+	return (e == null || tooLow(e.key)) ? null : e;
1361	+	}
1362	+
1363	+	final TreeMap.Entry<K,V> absLower(K key) {
1364	+	if (tooHigh(key))
1365	+	return absHighest();
1366	+	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1367	+	return (e == null || tooLow(e.key)) ? null : e;
1368	+	}
1369	+
1370	+	/** Returns the absolute high fence for ascending traversal */
1371	+	final TreeMap.Entry<K,V> absHighFence() {
1372	+	return (toEnd ? null : (hiInclusive ?
1373	+	m.getHigherEntry(hi) :
1374	+	m.getCeilingEntry(hi)));
1375	+	}
1376	+
1377	+	/** Return the absolute low fence for descending traversal  */
1378	+	final TreeMap.Entry<K,V> absLowFence() {
1379	+	return (fromStart ? null : (loInclusive ?
1380	+	m.getLowerEntry(lo) :
1381	+	m.getFloorEntry(lo)));
1382	+	}
1383	+
1384	+	// Abstract methods defined in ascending vs descending classes
1385	+	// These relay to the appropriate  absolute versions
1386	+
1387	+	abstract TreeMap.Entry<K,V> subLowest();
1388	+	abstract TreeMap.Entry<K,V> subHighest();
1389	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1390	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1391	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1392	+	abstract TreeMap.Entry<K,V> subLower(K key);
1393	+
1394	+	/** Returns ascending iterator from the perspective of this submap */
1395	+	abstract Iterator<K> keyIterator();
1396	+
1397	+	/** Returns descending iterator from the perspective of this submap */
1398	+	abstract Iterator<K> descendingKeyIterator();
1399	+
1400	+	// public methods
1401	+
1402		public boolean isEmpty() {
1403	<	return entrySet().isEmpty();
1403	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1404		}
1405
1406	<	public boolean containsKey(Object key) {
1407	<	return inRange(key) && TreeMap.this.containsKey(key);
1406	>	public int size() {
1407	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1408		}
1409
1410	<	public V get(Object key) {
1411	<	if (!inRange(key))
1076	<	return null;
1077	<	return TreeMap.this.get(key);
1410	>	public final boolean containsKey(Object key) {
1411	>	return inRange(key) && m.containsKey(key);
1412		}
1413
1414	<	public V put(K key, V value) {
1414	>	public final V put(K key, V value) {
1415		if (!inRange(key))
1416		throw new IllegalArgumentException("key out of range");
1417	<	return TreeMap.this.put(key, value);
1417	>	return m.put(key, value);
1418		}
1419
1420	<	public V remove(Object key) {
1421	<	if (!inRange(key))
1088	<	return null;
1089	<	return TreeMap.this.remove(key);
1420	>	public final V get(Object key) {
1421	>	return !inRange(key)? null :  m.get(key);
1422		}
1423
1424	<	public Comparator<? super K> comparator() {
1425	<	return comparator;
1424	>	public final V remove(Object key) {
1425	>	return !inRange(key)? null  : m.remove(key);
1426		}
1427
1428	<	public K firstKey() {
1429	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1098	<	K first = key(e);
1099	<	if (!toEnd && compare(first, toKey) >= 0)
1100	<	throw new NoSuchElementException();
1101	<	return first;
1428	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1429	>	return exportEntry(subCeiling(key));
1430		}
1431
1432	<	public K lastKey() {
1433	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1106	<	K last = key(e);
1107	<	if (!fromStart && compare(last, fromKey) < 0)
1108	<	throw new NoSuchElementException();
1109	<	return last;
1432	>	public final K ceilingKey(K key) {
1433	>	return keyOrNull(subCeiling(key));
1434		}
1435
1436	<	public Map.Entry<K,V> firstEntry() {
1437	<	TreeMap.Entry<K,V> e = fromStart ?
1114	<	getFirstEntry() : getCeilingEntry(fromKey);
1115	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1116	<	return null;
1117	<	return e;
1436	>	public final Map.Entry<K,V> higherEntry(K key) {
1437	>	return exportEntry(subHigher(key));
1438		}
1439
1440	<	public Map.Entry<K,V> lastEntry() {
1441	<	TreeMap.Entry<K,V> e = toEnd ?
1122	<	getLastEntry() : getLowerEntry(toKey);
1123	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1124	<	return null;
1125	<	return e;
1440	>	public final K higherKey(K key) {
1441	>	return keyOrNull(subHigher(key));
1442		}
1443
1444	<	public Map.Entry<K,V> pollFirstEntry() {
1445	<	TreeMap.Entry<K,V> e = fromStart ?
1130	<	getFirstEntry() : getCeilingEntry(fromKey);
1131	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1132	<	return null;
1133	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1134	<	deleteEntry(e);
1135	<	return result;
1444	>	public final Map.Entry<K,V> floorEntry(K key) {
1445	>	return exportEntry(subFloor(key));
1446		}
1447
1448	<	public Map.Entry<K,V> pollLastEntry() {
1449	<	TreeMap.Entry<K,V> e = toEnd ?
1140	<	getLastEntry() : getLowerEntry(toKey);
1141	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1142	<	return null;
1143	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1144	<	deleteEntry(e);
1145	<	return result;
1448	>	public final K floorKey(K key) {
1449	>	return keyOrNull(subFloor(key));
1450		}
1451
1452	<	private TreeMap.Entry<K,V> subceiling(K key) {
1453	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1150	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1151	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1152	<	return null;
1153	<	return e;
1452	>	public final Map.Entry<K,V> lowerEntry(K key) {
1453	>	return exportEntry(subLower(key));
1454		}
1455
1456	<	public Map.Entry<K,V> ceilingEntry(K key) {
1457	<	TreeMap.Entry<K,V> e = subceiling(key);
1158	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1456	>	public final K lowerKey(K key) {
1457	>	return keyOrNull(subLower(key));
1458		}
1459
1460	<	public K ceilingKey(K key) {
1461	<	TreeMap.Entry<K,V> e = subceiling(key);
1163	<	return e == null? null : e.key;
1460	>	public final K firstKey() {
1461	>	return key(subLowest());
1462		}
1463
1464	<
1465	<	private TreeMap.Entry<K,V> subhigher(K key) {
1168	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1169	<	getCeilingEntry(fromKey) : getHigherEntry(key);
1170	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1171	<	return null;
1172	<	return e;
1464	>	public final K lastKey() {
1465	>	return key(subHighest());
1466		}
1467
1468	<	public Map.Entry<K,V> higherEntry(K key) {
1469	<	TreeMap.Entry<K,V> e = subhigher(key);
1177	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1468	>	public final Map.Entry<K,V> firstEntry() {
1469	>	return exportEntry(subLowest());
1470		}
1471
1472	<	public K higherKey(K key) {
1473	<	TreeMap.Entry<K,V> e = subhigher(key);
1182	<	return e == null? null : e.key;
1472	>	public final Map.Entry<K,V> lastEntry() {
1473	>	return exportEntry(subHighest());
1474		}
1475
1476	<	private TreeMap.Entry<K,V> subfloor(K key) {
1477	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1478	<	getLowerEntry(toKey) : getFloorEntry(key);
1479	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1480	<	return null;
1481	<	return e;
1476	>	public final Map.Entry<K,V> pollFirstEntry() {
1477	>	TreeMap.Entry<K,V> e = subLowest();
1478	>	Map.Entry<K,V> result = exportEntry(e);
1479	>	if (e != null)
1480	>	m.deleteEntry(e);
1481	>	return result;
1482		}
1483
1484	<	public Map.Entry<K,V> floorEntry(K key) {
1485	<	TreeMap.Entry<K,V> e = subfloor(key);
1486	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1484	>	public final Map.Entry<K,V> pollLastEntry() {
1485	>	TreeMap.Entry<K,V> e = subHighest();
1486	>	Map.Entry<K,V> result = exportEntry(e);
1487	>	if (e != null)
1488	>	m.deleteEntry(e);
1489	>	return result;
1490		}
1491
1492	<	public K floorKey(K key) {
1493	<	TreeMap.Entry<K,V> e = subfloor(key);
1494	<	return e == null? null : e.key;
1492	>	// Views
1493	>	transient NavigableMap<K,V> descendingMapView = null;
1494	>	transient EntrySetView entrySetView = null;
1495	>	transient KeySet<K> navigableKeySetView = null;
1496	>
1497	>	public final NavigableSet<K> navigableKeySet() {
1498	>	KeySet<K> nksv = navigableKeySetView;
1499	>	return (nksv != null) ? nksv :
1500	>	(navigableKeySetView = new TreeMap.KeySet(this));
1501		}
1502
1503	<	private TreeMap.Entry<K,V> sublower(K key) {
1504	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1205	<	getLowerEntry(toKey) :  getLowerEntry(key);
1206	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1207	<	return null;
1208	<	return e;
1503	>	public final Set<K> keySet() {
1504	>	return navigableKeySet();
1505		}
1506
1507	<	public Map.Entry<K,V> lowerEntry(K key) {
1508	<	TreeMap.Entry<K,V> e = sublower(key);
1213	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1507	>	public NavigableSet<K> descendingKeySet() {
1508	>	return descendingMap().navigableKeySet();
1509		}
1510
1511	<	public K lowerKey(K key) {
1512	<	TreeMap.Entry<K,V> e = sublower(key);
1218	<	return e == null? null : e.key;
1511	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1512	>	return subMap(fromKey, true, toKey, false);
1513		}
1514
1515	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1515	>	public final SortedMap<K,V> headMap(K toKey) {
1516	>	return headMap(toKey, false);
1517	>	}
1518
1519	<	public Set<Map.Entry<K,V>> entrySet() {
1520	<	Set<Map.Entry<K,V>> es = entrySet;
1225	<	return (es != null)? es : (entrySet = new EntrySetView());
1519	>	public final SortedMap<K,V> tailMap(K fromKey) {
1520	>	return tailMap(fromKey, true);
1521		}
1522
1523	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1523	>	// View classes
1524	>
1525	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1526		private transient int size = -1, sizeModCount;
1527
1528		public int size() {
1529	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1530	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1529	>	if (fromStart && toEnd)
1530	>	return m.size();
1531	>	if (size == -1 || sizeModCount != m.modCount) {
1532	>	sizeModCount = m.modCount;
1533	>	size = 0;
1534		Iterator i = iterator();
1535		while (i.hasNext()) {
1536		size++;
#	Line 1241 | Line 1541 | public class TreeMap<K,V>
1541		}
1542
1543		public boolean isEmpty() {
1544	<	return !iterator().hasNext();
1544	>	TreeMap.Entry<K,V> n = absLowest();
1545	>	return n == null || tooHigh(n.key);
1546		}
1547
1548		public boolean contains(Object o) {
#	Line 1251 | Line 1552 | public class TreeMap<K,V>
1552		K key = entry.getKey();
1553		if (!inRange(key))
1554		return false;
1555	<	TreeMap.Entry node = getEntry(key);
1555	>	TreeMap.Entry node = m.getEntry(key);
1556		return node != null &&
1557	<	valEquals(node.getValue(), entry.getValue());
1557	>	valEquals(node.getValue(), entry.getValue());
1558		}
1559
1560		public boolean remove(Object o) {
#	Line 1263 | Line 1564 | public class TreeMap<K,V>
1564		K key = entry.getKey();
1565		if (!inRange(key))
1566		return false;
1567	<	TreeMap.Entry<K,V> node = getEntry(key);
1567	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1568		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1569	<	deleteEntry(node);
1569	>	m.deleteEntry(node);
1570		return true;
1571		}
1572		return false;
1573		}
1273	–
1274	–	public Iterator<Map.Entry<K,V>> iterator() {
1275	–	return new SubMapEntryIterator(
1276	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1277	–	(toEnd     ? null            : getCeilingEntry(toKey)));
1278	–	}
1574		}
1575
1576	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1577	<	private transient Set<K> descendingKeySetView = null;
1578	<
1579	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1580	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1581	<	return (es != null) ? es :
1582	<	(descendingEntrySetView = new DescendingEntrySetView());
1583	<	}
1289	<
1290	<	public Set<K> descendingKeySet() {
1291	<	Set<K> ks = descendingKeySetView;
1292	<	return (ks != null) ? ks :
1293	<	(descendingKeySetView = new DescendingKeySetView());
1294	<	}
1576	>	/**
1577	>	* Iterators for SubMaps
1578	>	*/
1579	>	abstract class SubMapIterator<T> implements Iterator<T> {
1580	>	TreeMap.Entry<K,V> lastReturned;
1581	>	TreeMap.Entry<K,V> next;
1582	>	final K fenceKey;
1583	>	int expectedModCount;
1584
1585	<	private class DescendingEntrySetView extends EntrySetView {
1586	<	public Iterator<Map.Entry<K,V>> iterator() {
1587	<	return new DescendingSubMapEntryIterator
1588	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1589	<	(fromStart ? null            : getLowerEntry(fromKey)));
1585	>	SubMapIterator(TreeMap.Entry<K,V> first,
1586	>	TreeMap.Entry<K,V> fence) {
1587	>	expectedModCount = m.modCount;
1588	>	lastReturned = null;
1589	>	next = first;
1590	>	fenceKey = fence == null ? null : fence.key;
1591		}
1302	–	}
1592
1593	<	private class DescendingKeySetView extends AbstractSet<K> {
1594	<	public Iterator<K> iterator() {
1595	<	return new Iterator<K>() {
1307	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1593	>	public final boolean hasNext() {
1594	>	return next != null && next.key != fenceKey;
1595	>	}
1596
1597	<	public boolean hasNext() { return i.hasNext(); }
1598	<	public K next() { return i.next().getKey(); }
1599	<	public void remove() { i.remove(); }
1600	<	};
1597	>	final TreeMap.Entry<K,V> nextEntry() {
1598	>	TreeMap.Entry<K,V> e = lastReturned = next;
1599	>	if (e == null || e.key == fenceKey)
1600	>	throw new NoSuchElementException();
1601	>	if (m.modCount != expectedModCount)
1602	>	throw new ConcurrentModificationException();
1603	>	next = successor(e);
1604	>	return e;
1605		}
1606
1607	<	public int size() {
1608	<	return SubMap.this.size();
1607	>	final TreeMap.Entry<K,V> prevEntry() {
1608	>	TreeMap.Entry<K,V> e = lastReturned = next;
1609	>	if (e == null || e.key == fenceKey)
1610	>	throw new NoSuchElementException();
1611	>	if (m.modCount != expectedModCount)
1612	>	throw new ConcurrentModificationException();
1613	>	next = predecessor(e);
1614	>	return e;
1615		}
1616
1617	<	public boolean contains(Object k) {
1618	<	return SubMap.this.containsKey(k);
1617	>	public void remove() {
1618	>	if (lastReturned == null)
1619	>	throw new IllegalStateException();
1620	>	if (m.modCount != expectedModCount)
1621	>	throw new ConcurrentModificationException();
1622	>	if (lastReturned.left != null && lastReturned.right != null)
1623	>	next = lastReturned;
1624	>	m.deleteEntry(lastReturned);
1625	>	expectedModCount++;
1626	>	lastReturned = null;
1627		}
1628		}
1629
1630	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1631	<	if (!inRange2(fromKey))
1632	<	throw new IllegalArgumentException("fromKey out of range");
1633	<	if (!inRange2(toKey))
1634	<	throw new IllegalArgumentException("toKey out of range");
1635	<	return new SubMap(fromKey, toKey);
1630	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1631	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1632	>	TreeMap.Entry<K,V> fence) {
1633	>	super(first, fence);
1634	>	}
1635	>	public Map.Entry<K,V> next() {
1636	>	return nextEntry();
1637	>	}
1638		}
1639
1640	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1641	<	if (!inRange2(toKey))
1642	<	throw new IllegalArgumentException("toKey out of range");
1643	<	return new SubMap(fromStart, fromKey, false, toKey);
1640	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1641	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1642	>	TreeMap.Entry<K,V> fence) {
1643	>	super(first, fence);
1644	>	}
1645	>	public K next() {
1646	>	return nextEntry().key;
1647	>	}
1648		}
1649
1650	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1651	<	if (!inRange2(fromKey))
1652	<	throw new IllegalArgumentException("fromKey out of range");
1653	<	return new SubMap(false, fromKey, toEnd, toKey);
1654	<	}
1650	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1651	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1652	>	TreeMap.Entry<K,V> fence) {
1653	>	super(last, fence);
1654	>	}
1655
1656	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1657	<	return navigableSubMap(fromKey, toKey);
1656	>	public Map.Entry<K,V> next() {
1657	>	return prevEntry();
1658	>	}
1659		}
1660
1661	<	public SortedMap<K,V> headMap(K toKey) {
1662	<	return navigableHeadMap(toKey);
1661	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1662	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1663	>	TreeMap.Entry<K,V> fence) {
1664	>	super(last, fence);
1665	>	}
1666	>	public K next() {
1667	>	return prevEntry().key;
1668	>	}
1669		}
1670	+	}
1671
1672	<	public SortedMap<K,V> tailMap(K fromKey) {
1673	<	return navigableTailMap(fromKey);
1354	<	}
1672	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1673	>	private static final long serialVersionUID = 912986545866124060L;
1674
1675	<	private boolean inRange(Object key) {
1676	<	return (fromStart || compare(key, fromKey) >= 0) &&
1677	<	(toEnd     || compare(key, toKey)   <  0);
1675	>	AscendingSubMap(TreeMap<K,V> m,
1676	>	boolean fromStart, K lo, boolean loInclusive,
1677	>	boolean toEnd, K hi, boolean hiInclusive) {
1678	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1679		}
1680
1681	<	// This form allows the high endpoint (as well as all legit keys)
1682	<	private boolean inRange2(Object key) {
1363	<	return (fromStart || compare(key, fromKey) >= 0) &&
1364	<	(toEnd     || compare(key, toKey)   <= 0);
1681	>	public Comparator<? super K> comparator() {
1682	>	return m.comparator();
1683		}
1366	–	}
1684
1685	<	/**
1686	<	* TreeMap Iterator.
1687	<	*/
1688	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1689	<	int expectedModCount = TreeMap.this.modCount;
1690	<	Entry<K,V> lastReturned = null;
1691	<	Entry<K,V> next;
1692	<
1693	<	PrivateEntryIterator(Entry<K,V> first) {
1377	<	next = first;
1685	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1686	>	K toKey, boolean toInclusive) {
1687	>	if (!inRange(fromKey, fromInclusive))
1688	>	throw new IllegalArgumentException("fromKey out of range");
1689	>	if (!inRange(toKey, toInclusive))
1690	>	throw new IllegalArgumentException("toKey out of range");
1691	>	return new AscendingSubMap(m,
1692	>	false, fromKey, fromInclusive,
1693	>	false, toKey,   toInclusive);
1694		}
1695
1696	<	public boolean hasNext() {
1697	<	return next != null;
1696	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1697	>	if (!inClosedRange(toKey))
1698	>	throw new IllegalArgumentException("toKey out of range");
1699	>	return new AscendingSubMap(m,
1700	>	fromStart, lo,    loInclusive,
1701	>	false,     toKey, inclusive);
1702		}
1703
1704	<	Entry<K,V> nextEntry() {
1705	<	if (next == null)
1706	<	throw new NoSuchElementException();
1707	<	if (modCount != expectedModCount)
1708	<	throw new ConcurrentModificationException();
1709	<	lastReturned = next;
1390	<	next = successor(next);
1391	<	return lastReturned;
1704	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1705	>	if (!inRange(fromKey, inclusive))
1706	>	throw new IllegalArgumentException("fromKey out of range");
1707	>	return new AscendingSubMap(m,
1708	>	false, fromKey, inclusive,
1709	>	toEnd, hi,      hiInclusive);
1710		}
1711
1712	<	public void remove() {
1713	<	if (lastReturned == null)
1714	<	throw new IllegalStateException();
1715	<	if (modCount != expectedModCount)
1716	<	throw new ConcurrentModificationException();
1717	<	if (lastReturned.left != null && lastReturned.right != null)
1718	<	next = lastReturned;
1401	<	deleteEntry(lastReturned);
1402	<	expectedModCount++;
1403	<	lastReturned = null;
1712	>	public NavigableMap<K,V> descendingMap() {
1713	>	NavigableMap<K,V> mv = descendingMapView;
1714	>	return (mv != null) ? mv :
1715	>	(descendingMapView =
1716	>	new DescendingSubMap(m,
1717	>	fromStart, lo, loInclusive,
1718	>	toEnd,     hi, hiInclusive));
1719		}
1405	–	}
1720
1721	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1722	<	EntryIterator(Entry<K,V> first) {
1409	<	super(first);
1410	<	}
1411	<	public Map.Entry<K,V> next() {
1412	<	return nextEntry();
1721	>	Iterator<K> keyIterator() {
1722	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1723		}
1414	–	}
1724
1725	<	class KeyIterator extends PrivateEntryIterator<K> {
1726	<	KeyIterator(Entry<K,V> first) {
1418	<	super(first);
1725	>	Iterator<K> descendingKeyIterator() {
1726	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1727		}
1420	–	public K next() {
1421	–	return nextEntry().key;
1422	–	}
1423	–	}
1728
1729	<	class ValueIterator extends PrivateEntryIterator<V> {
1730	<	ValueIterator(Entry<K,V> first) {
1731	<	super(first);
1729	>	final class AscendingEntrySetView extends EntrySetView {
1730	>	public Iterator<Map.Entry<K,V>> iterator() {
1731	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1732	>	}
1733		}
1734	<	public V next() {
1735	<	return nextEntry().value;
1734	>
1735	>	public Set<Map.Entry<K,V>> entrySet() {
1736	>	EntrySetView es = entrySetView;
1737	>	return (es != null) ? es : new AscendingEntrySetView();
1738		}
1432	–	}
1739
1740	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1741	<	private final K firstExcludedKey;
1740	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1741	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1742	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1743	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1744	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1745	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1746	>	}
1747
1748	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1749	<	super(first);
1750	<	firstExcludedKey = (firstExcluded == null
1751	<	? null
1752	<	: firstExcluded.key);
1748	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1749	>	private static final long serialVersionUID = 912986545866120460L;
1750	>	DescendingSubMap(TreeMap<K,V> m,
1751	>	boolean fromStart, K lo, boolean loInclusive,
1752	>	boolean toEnd, K hi, boolean hiInclusive) {
1753	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1754		}
1755
1756	<	public boolean hasNext() {
1757	<	return next != null && next.key != firstExcludedKey;
1446	<	}
1756	>	private final Comparator<? super K> reverseComparator =
1757	>	Collections.reverseOrder(m.comparator);
1758
1759	<	public Map.Entry<K,V> next() {
1760	<	if (next == null || next.key == firstExcludedKey)
1450	<	throw new NoSuchElementException();
1451	<	return nextEntry();
1759	>	public Comparator<? super K> comparator() {
1760	>	return reverseComparator;
1761		}
1453	–	}
1762
1763	<	/**
1764	<	* Base for Descending Iterators.
1765	<	*/
1766	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1767	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1768	<	super(first);
1763	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1764	>	K toKey, boolean toInclusive) {
1765	>	if (!inRange(fromKey, fromInclusive))
1766	>	throw new IllegalArgumentException("fromKey out of range");
1767	>	if (!inRange(toKey, toInclusive))
1768	>	throw new IllegalArgumentException("toKey out of range");
1769	>	return new DescendingSubMap(m,
1770	>	false, toKey,   toInclusive,
1771	>	false, fromKey, fromInclusive);
1772		}
1773
1774	<	Entry<K,V> nextEntry() {
1775	<	if (next == null)
1776	<	throw new NoSuchElementException();
1777	<	if (modCount != expectedModCount)
1778	<	throw new ConcurrentModificationException();
1779	<	lastReturned = next;
1469	<	next = predecessor(next);
1470	<	return lastReturned;
1774	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1775	>	if (!inRange(toKey, inclusive))
1776	>	throw new IllegalArgumentException("toKey out of range");
1777	>	return new DescendingSubMap(m,
1778	>	false, toKey, inclusive,
1779	>	toEnd, hi,    hiInclusive);
1780		}
1472	–	}
1781
1782	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1783	<	DescendingEntryIterator(Entry<K,V> first) {
1784	<	super(first);
1785	<	}
1786	<	public Map.Entry<K,V> next() {
1787	<	return nextEntry();
1782	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1783	>	if (!inRange(fromKey, inclusive))
1784	>	throw new IllegalArgumentException("fromKey out of range");
1785	>	return new DescendingSubMap(m,
1786	>	fromStart, lo, loInclusive,
1787	>	false, fromKey, inclusive);
1788		}
1481	–	}
1789
1790	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1791	<	DescendingKeyIterator(Entry<K,V> first) {
1792	<	super(first);
1790	>	public NavigableMap<K,V> descendingMap() {
1791	>	NavigableMap<K,V> mv = descendingMapView;
1792	>	return (mv != null) ? mv :
1793	>	(descendingMapView =
1794	>	new AscendingSubMap(m,
1795	>	fromStart, lo, loInclusive,
1796	>	toEnd,     hi, hiInclusive));
1797		}
1487	–	public K next() {
1488	–	return nextEntry().key;
1489	–	}
1490	–	}
1798
1799	+	Iterator<K> keyIterator() {
1800	+	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1801	+	}
1802
1803	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1804	<	private final K lastExcludedKey;
1495	<
1496	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1497	<	super(last);
1498	<	lastExcludedKey = (lastExcluded == null
1499	<	? null
1500	<	: lastExcluded.key);
1803	>	Iterator<K> descendingKeyIterator() {
1804	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1805		}
1806
1807	<	public boolean hasNext() {
1808	<	return next != null && next.key != lastExcludedKey;
1807	>	final class DescendingEntrySetView extends EntrySetView {
1808	>	public Iterator<Map.Entry<K,V>> iterator() {
1809	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1810	>	}
1811		}
1812
1813	<	public Map.Entry<K,V> next() {
1814	<	if (next == null || next.key == lastExcludedKey)
1815	<	throw new NoSuchElementException();
1510	<	return nextEntry();
1813	>	public Set<Map.Entry<K,V>> entrySet() {
1814	>	EntrySetView es = entrySetView;
1815	>	return (es != null) ? es : new DescendingEntrySetView();
1816		}
1817
1818	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1819	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1820	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1821	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1822	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1823	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1824		}
1825
1826		/**
1827	<	* Compares two keys using the correct comparison method for this TreeMap.
1827	>	* This class exists solely for the sake of serialization
1828	>	* compatibility with previous releases of TreeMap that did not
1829	>	* support NavigableMap.  It translates an old-version SubMap into
1830	>	* a new-version AscendingSubMap. This class is never otherwise
1831	>	* used.
1832		*/
1833	<	private int compare(Object k1, Object k2) {
1834	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1835	<	: comparator.compare((K)k1, (K)k2);
1833	>	private class SubMap extends AbstractMap<K,V>
1834	>	implements SortedMap<K,V>, java.io.Serializable {
1835	>	private static final long serialVersionUID = -6520786458950516097L;
1836	>	private boolean fromStart = false, toEnd = false;
1837	>	private K fromKey, toKey;
1838	>	private Object readResolve() {
1839	>	return new AscendingSubMap(TreeMap.this,
1840	>	fromStart, fromKey, true,
1841	>	toEnd, toKey, false);
1842	>	}
1843	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1844	>	public K lastKey() { throw new InternalError(); }
1845	>	public K firstKey() { throw new InternalError(); }
1846	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1847	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1848	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1849	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1850		}
1851
1852	<	/**
1853	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1525	<	* that it copes with <tt>null</tt> o1 properly.
1526	<	*/
1527	<	private static boolean valEquals(Object o1, Object o2) {
1528	<	return (o1==null ? o2==null : o1.equals(o2));
1529	<	}
1852	>
1853	>	// Red-black mechanics
1854
1855		private static final boolean RED   = false;
1856		private static final boolean BLACK = true;
#	Line 1536 | Line 1860 | public class TreeMap<K,V>
1860		* user (see Map.Entry).
1861		*/
1862
1863	<	static class Entry<K,V> implements Map.Entry<K,V> {
1863	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1864		K key;
1865		V value;
1866		Entry<K,V> left = null;
#	Line 1608 | Line 1932 | public class TreeMap<K,V>
1932		* Returns the first Entry in the TreeMap (according to the TreeMap's
1933		* key-sort function).  Returns null if the TreeMap is empty.
1934		*/
1935	<	private Entry<K,V> getFirstEntry() {
1935	>	final Entry<K,V> getFirstEntry() {
1936		Entry<K,V> p = root;
1937		if (p != null)
1938		while (p.left != null)
#	Line 1620 | Line 1944 | public class TreeMap<K,V>
1944		* Returns the last Entry in the TreeMap (according to the TreeMap's
1945		* key-sort function).  Returns null if the TreeMap is empty.
1946		*/
1947	<	private Entry<K,V> getLastEntry() {
1947	>	final Entry<K,V> getLastEntry() {
1948		Entry<K,V> p = root;
1949		if (p != null)
1950		while (p.right != null)
#	Line 1631 | Line 1955 | public class TreeMap<K,V>
1955		/**
1956		* Returns the successor of the specified Entry, or null if no such.
1957		*/
1958	<	private Entry<K,V> successor(Entry<K,V> t) {
1958	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1959		if (t == null)
1960		return null;
1961		else if (t.right != null) {
#	Line 1653 | Line 1977 | public class TreeMap<K,V>
1977		/**
1978		* Returns the predecessor of the specified Entry, or null if no such.
1979		*/
1980	<	private Entry<K,V> predecessor(Entry<K,V> t) {
1980	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1981		if (t == null)
1982		return null;
1983		else if (t.left != null) {
#	Line 1703 | Line 2027 | public class TreeMap<K,V>
2027		return (p == null) ? null: p.right;
2028		}
2029
2030	<	/** From CLR **/
2030	>	/** From CLR */
2031		private void rotateLeft(Entry<K,V> p) {
2032		Entry<K,V> r = p.right;
2033		p.right = r.left;
#	Line 1720 | Line 2044 | public class TreeMap<K,V>
2044		p.parent = r;
2045		}
2046
2047	<	/** From CLR **/
2047	>	/** From CLR */
2048		private void rotateRight(Entry<K,V> p) {
2049		Entry<K,V> l = p.left;
2050		p.left = l.right;
#	Line 1736 | Line 2060 | public class TreeMap<K,V>
2060		}
2061
2062
2063	<	/** From CLR **/
2063	>	/** From CLR */
2064		private void fixAfterInsertion(Entry<K,V> x) {
2065		x.color = RED;
2066
#	Line 1770 | Line 2094 | public class TreeMap<K,V>
2094		x = parentOf(x);
2095		rotateRight(x);
2096		}
2097	<	setColor(parentOf(x),  BLACK);
2097	>	setColor(parentOf(x), BLACK);
2098		setColor(parentOf(parentOf(x)), RED);
2099		if (parentOf(parentOf(x)) != null)
2100		rotateLeft(parentOf(parentOf(x)));
#	Line 1785 | Line 2109 | public class TreeMap<K,V>
2109		*/
2110
2111		private void deleteEntry(Entry<K,V> p) {
2112	<	decrementSize();
2112	>	modCount++;
2113	>	size--;
2114
2115		// If strictly internal, copy successor's element to p and then make p
2116		// point to successor.
#	Line 1831 | Line 2156 | public class TreeMap<K,V>
2156		}
2157		}
2158
2159	<	/** From CLR **/
2159	>	/** From CLR */
2160		private void fixAfterDeletion(Entry<K,V> x) {
2161		while (x != root && colorOf(x) == BLACK) {
2162		if (x == leftOf(parentOf(x))) {
#	Line 1846 | Line 2171 | public class TreeMap<K,V>
2171
2172		if (colorOf(leftOf(sib))  == BLACK &&
2173		colorOf(rightOf(sib)) == BLACK) {
2174	<	setColor(sib,  RED);
2174	>	setColor(sib, RED);
2175		x = parentOf(x);
2176		} else {
2177		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 1873 | Line 2198 | public class TreeMap<K,V>
2198
2199		if (colorOf(rightOf(sib)) == BLACK &&
2200		colorOf(leftOf(sib)) == BLACK) {
2201	<	setColor(sib,  RED);
2201	>	setColor(sib, RED);
2202		x = parentOf(x);
2203		} else {
2204		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 1924 | Line 2249 | public class TreeMap<K,V>
2249		}
2250		}
2251
1927	–
1928	–
2252		/**
2253		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2254		* deserialize it).
#	Line 1941 | Line 2264 | public class TreeMap<K,V>
2264		buildFromSorted(size, null, s, null);
2265		}
2266
2267	<	/** Intended to be called only from TreeSet.readObject **/
2267	>	/** Intended to be called only from TreeSet.readObject */
2268		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2269		throws java.io.IOException, ClassNotFoundException {
2270		buildFromSorted(size, null, s, defaultVal);
2271		}
2272
2273	<	/** Intended to be called only from TreeSet.addAll **/
2273	>	/** Intended to be called only from TreeSet.addAll */
2274		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2275		try {
2276		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
#	Line 1987 | Line 2310 | public class TreeMap<K,V>
2310		* @throws ClassNotFoundException propagated from readObject.
2311		*         This cannot occur if str is null.
2312		*/
2313	<	private
2314	<	void buildFromSorted(int size, Iterator it,
2315	<	java.io.ObjectInputStream str,
1993	<	V defaultVal)
2313	>	private void buildFromSorted(int size, Iterator it,
2314	>	java.io.ObjectInputStream str,
2315	>	V defaultVal)
2316		throws  java.io.IOException, ClassNotFoundException {
2317		this.size = size;
2318	<	root =
2319	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
1998	<	it, str, defaultVal);
2318	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2319	>	it, str, defaultVal);
2320		}
2321
2322		/**
2323		* Recursive "helper method" that does the real work of the
2324	<	* of the previous method.  Identically named parameters have
2324	>	* previous method.  Identically named parameters have
2325		* identical definitions.  Additional parameters are documented below.
2326		* It is assumed that the comparator and size fields of the TreeMap are
2327		* already set prior to calling this method.  (It ignores both fields.)

Diff Legend

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