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.35 by jsr166, Tue May 2 19:42:46 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 69 | Line 68 | import java.util.*; // for javadoc (till
68		* associated map using <tt>put</tt>.)
69		*
70		* <p>This class is a member of the
71	<	* <a href="{@docRoot}/../guide/collections/index.html">
71	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
72		* Java Collections Framework</a>.
73		*
74		* @param <K> the type of keys maintained by this map
#	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 226 | Line 223 | public class TreeMap<K,V>
223		* @since 1.2
224		*/
225		public boolean containsValue(Object value) {
226	<	return (root==null ? false :
227	<	(value==null ? valueSearchNull(root)
228	<	: valueSearchNonNull(root, value)));
229	<	}
233	<
234	<	private boolean valueSearchNull(Entry n) {
235	<	if (n.value == null)
236	<	return true;
237	<
238	<	// Check left and right subtrees for value
239	<	return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
241	<	}
242	<
243	<	private boolean valueSearchNonNull(Entry n, Object value) {
244	<	// Check this node for the value
245	<	if (value.equals(n.value))
246	<	return true;
247	<
248	<	// Check left and right subtrees for value
249	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
250	<	(n.right != null && valueSearchNonNull(n.right, value));
226	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
227	>	if (valEquals(value, e.value))
228	>	return true;
229	>	return false;
230		}
231
232		/**
233	<	* Returns the value to which this map maps the specified key, or
234	<	* <tt>null</tt> if the map contains no mapping for the key.  A return
235	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
236	<	* map contains no mapping for the key; it's also possible that the map
237	<	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey
238	<	* containsKey} operation may be used to distinguish these two cases.
233	>	* Returns the value to which the specified key is mapped,
234	>	* or {@code null} if this map contains no mapping for the key.
235	>	*
236	>	* <p>More formally, if this map contains a mapping from a key
237	>	* {@code k} to a value {@code v} such that {@code key} compares
238	>	* equal to {@code k} according to the map's ordering, then this
239	>	* method returns {@code v}; otherwise it returns {@code null}.
240	>	* (There can be at most one such mapping.)
241	>	*
242	>	* <p>A return value of {@code null} does not <i>necessarily</i>
243	>	* indicate that the map contains no mapping for the key; it's also
244	>	* possible that the map explicitly maps the key to {@code null}.
245	>	* The {@link #containsKey containsKey} operation may be used to
246	>	* distinguish these two cases.
247		*
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
248		* @throws ClassCastException if the specified key cannot be compared
249		*         with the keys currently in the map
250		* @throws NullPointerException if the specified key is null
#	Line 332 | Line 316 | public class TreeMap<K,V>
316		*         and this map uses natural ordering, or its comparator
317		*         does not permit null keys
318		*/
319	<	private Entry<K,V> getEntry(Object key) {
319	>	final Entry<K,V> getEntry(Object key) {
320		// Offload comparator-based version for sake of performance
321		if (comparator != null)
322		return getEntryUsingComparator(key);
323	+	if (key == null)
324	+	throw new NullPointerException();
325		Comparable<? super K> k = (Comparable<? super K>) key;
326		Entry<K,V> p = root;
327		while (p != null) {
#	Line 356 | Line 342 | public class TreeMap<K,V>
342		* that are less dependent on comparator performance, but is
343		* worthwhile here.)
344		*/
345	<	private Entry<K,V> getEntryUsingComparator(Object key) {
345	>	final Entry<K,V> getEntryUsingComparator(Object key) {
346		K k = (K) key;
347		Comparator<? super K> cpr = comparator;
348	<	Entry<K,V> p = root;
349	<	while (p != null) {
350	<	int cmp = cpr.compare(k, p.key);
351	<	if (cmp < 0)
352	<	p = p.left;
353	<	else if (cmp > 0)
354	<	p = p.right;
355	<	else
356	<	return p;
348	>	if (cpr != null) {
349	>	Entry<K,V> p = root;
350	>	while (p != null) {
351	>	int cmp = cpr.compare(k, p.key);
352	>	if (cmp < 0)
353	>	p = p.left;
354	>	else if (cmp > 0)
355	>	p = p.right;
356	>	else
357	>	return p;
358	>	}
359		}
360		return null;
361		}
#	Line 378 | Line 366 | public class TreeMap<K,V>
366		* key; if no such entry exists (i.e., the greatest key in the Tree is less
367		* than the specified key), returns <tt>null</tt>.
368		*/
369	<	private Entry<K,V> getCeilingEntry(K key) {
369	>	final Entry<K,V> getCeilingEntry(K key) {
370		Entry<K,V> p = root;
371	<	if (p==null)
384	<	return null;
385	<
386	<	while (true) {
371	>	while (p != null) {
372		int cmp = compare(key, p.key);
373		if (cmp < 0) {
374		if (p.left != null)
#	Line 405 | Line 390 | public class TreeMap<K,V>
390		} else
391		return p;
392		}
393	+	return null;
394		}
395
396		/**
#	Line 412 | Line 398 | public class TreeMap<K,V>
398		* exists, returns the entry for the greatest key less than the specified
399		* key; if no such entry exists, returns <tt>null</tt>.
400		*/
401	<	private Entry<K,V> getFloorEntry(K key) {
401	>	final Entry<K,V> getFloorEntry(K key) {
402		Entry<K,V> p = root;
403	<	if (p==null)
418	<	return null;
419	<
420	<	while (true) {
403	>	while (p != null) {
404		int cmp = compare(key, p.key);
405		if (cmp > 0) {
406		if (p.right != null)
#	Line 440 | Line 423 | public class TreeMap<K,V>
423		return p;
424
425		}
426	+	return null;
427		}
428
429		/**
#	Line 448 | Line 432 | public class TreeMap<K,V>
432		* key greater than the specified key; if no such entry exists
433		* returns <tt>null</tt>.
434		*/
435	<	private Entry<K,V> getHigherEntry(K key) {
435	>	final Entry<K,V> getHigherEntry(K key) {
436		Entry<K,V> p = root;
437	<	if (p==null)
454	<	return null;
455	<
456	<	while (true) {
437	>	while (p != null) {
438		int cmp = compare(key, p.key);
439		if (cmp < 0) {
440		if (p.left != null)
#	Line 474 | Line 455 | public class TreeMap<K,V>
455		}
456		}
457		}
458	+	return null;
459		}
460
461		/**
#	Line 481 | Line 463 | public class TreeMap<K,V>
463		* no such entry exists (i.e., the least key in the Tree is greater than
464		* the specified key), returns <tt>null</tt>.
465		*/
466	<	private Entry<K,V> getLowerEntry(K key) {
466	>	final Entry<K,V> getLowerEntry(K key) {
467		Entry<K,V> p = root;
468	<	if (p==null)
487	<	return null;
488	<
489	<	while (true) {
468	>	while (p != null) {
469		int cmp = compare(key, p.key);
470		if (cmp > 0) {
471		if (p.right != null)
#	Line 507 | Line 486 | public class TreeMap<K,V>
486		}
487		}
488		}
489	<	}
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;
489	>	return null;
490		}
491
492		/**
#	Line 539 | Line 509 | public class TreeMap<K,V>
509		*/
510		public V put(K key, V value) {
511		Entry<K,V> t = root;
542	–
512		if (t == null) {
513	<	if (key == null) {
514	<	if (comparator == null)
515	<	throw new NullPointerException();
516	<	comparator.compare(key, key);
517	<	}
549	<	incrementSize();
513	>	// TBD:
514	>	// 5045147: (coll) Adding null to an empty TreeSet should
515	>	// throw NullPointerException
516	>	//
517	>	// compare(key, key); // type check
518		root = new Entry<K,V>(key, value, null);
519	+	size = 1;
520	+	modCount++;
521		return null;
522		}
523	<
524	<	while (true) {
525	<	int cmp = compare(key, t.key);
526	<	if (cmp == 0) {
527	<	return t.setValue(value);
528	<	} else if (cmp < 0) {
529	<	if (t.left != null) {
523	>	int cmp;
524	>	Entry<K,V> parent;
525	>	// split comparator and comparable paths
526	>	Comparator<? super K> cpr = comparator;
527	>	if (cpr != null) {
528	>	do {
529	>	parent = t;
530	>	cmp = cpr.compare(key, t.key);
531	>	if (cmp < 0)
532		t = t.left;
533	<	} 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) {
533	>	else if (cmp > 0)
534		t = t.right;
535	<	} else {
536	<	incrementSize();
537	<	t.right = new Entry<K,V>(key, value, t);
573	<	fixAfterInsertion(t.right);
574	<	return null;
575	<	}
576	<	}
535	>	else
536	>	return t.setValue(value);
537	>	} while (t != null);
538		}
539	+	else {
540	+	if (key == null)
541	+	throw new NullPointerException();
542	+	Comparable<? super K> k = (Comparable<? super K>) key;
543	+	do {
544	+	parent = t;
545	+	cmp = k.compareTo(t.key);
546	+	if (cmp < 0)
547	+	t = t.left;
548	+	else if (cmp > 0)
549	+	t = t.right;
550	+	else
551	+	return t.setValue(value);
552	+	} while (t != null);
553	+	}
554	+	Entry<K,V> e = new Entry<K,V>(key, value, parent);
555	+	if (cmp < 0)
556	+	parent.left = e;
557	+	else
558	+	parent.right = e;
559	+	fixAfterInsertion(e);
560	+	size++;
561	+	modCount++;
562	+	return null;
563		}
564
565		/**
#	Line 630 | Line 615 | public class TreeMap<K,V>
615		clone.size = 0;
616		clone.modCount = 0;
617		clone.entrySet = null;
618	<	clone.descendingEntrySet = null;
619	<	clone.descendingKeySet = null;
618	>	clone.navigableKeySet = null;
619	>	clone.descendingMap = null;
620
621		// Initialize clone with our mappings
622		try {
#	Line 645 | Line 630 | public class TreeMap<K,V>
630
631		// NavigableMap API methods
632
633	+	/**
634	+	* @since 1.6
635	+	*/
636		public Map.Entry<K,V> firstEntry() {
637	<	Entry<K,V> e = getFirstEntry();
650	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
637	>	return exportEntry(getFirstEntry());
638		}
639
640	+	/**
641	+	* @since 1.6
642	+	*/
643		public Map.Entry<K,V> lastEntry() {
644	<	Entry<K,V> e = getLastEntry();
655	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
644	>	return exportEntry(getLastEntry());
645		}
646
647	+	/**
648	+	* @since 1.6
649	+	*/
650		public Map.Entry<K,V> pollFirstEntry() {
651		Entry<K,V> p = getFirstEntry();
652	<	if (p == null)
653	<	return null;
654	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
663	<	deleteEntry(p);
652	>	Map.Entry<K,V> result = exportEntry(p);
653	>	if (p != null)
654	>	deleteEntry(p);
655		return result;
656		}
657
658	+	/**
659	+	* @since 1.6
660	+	*/
661		public Map.Entry<K,V> pollLastEntry() {
662		Entry<K,V> p = getLastEntry();
663	<	if (p == null)
664	<	return null;
665	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
672	<	deleteEntry(p);
663	>	Map.Entry<K,V> result = exportEntry(p);
664	>	if (p != null)
665	>	deleteEntry(p);
666		return result;
667		}
668
#	Line 678 | Line 671 | public class TreeMap<K,V>
671		* @throws NullPointerException if the specified key is null
672		*         and this map uses natural ordering, or its comparator
673		*         does not permit null keys
674	+	* @since 1.6
675		*/
676		public Map.Entry<K,V> lowerEntry(K key) {
677	<	Entry<K,V> e =  getLowerEntry(key);
684	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
677	>	return exportEntry(getLowerEntry(key));
678		}
679
680		/**
#	Line 689 | Line 682 | public class TreeMap<K,V>
682		* @throws NullPointerException if the specified key is null
683		*         and this map uses natural ordering, or its comparator
684		*         does not permit null keys
685	+	* @since 1.6
686		*/
687		public K lowerKey(K key) {
688	<	Entry<K,V> e =  getLowerEntry(key);
695	<	return (e == null)? null : e.key;
688	>	return keyOrNull(getLowerEntry(key));
689		}
690
691		/**
#	Line 700 | Line 693 | public class TreeMap<K,V>
693		* @throws NullPointerException if the specified key is null
694		*         and this map uses natural ordering, or its comparator
695		*         does not permit null keys
696	+	* @since 1.6
697		*/
698		public Map.Entry<K,V> floorEntry(K key) {
699	<	Entry<K,V> e = getFloorEntry(key);
706	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
699	>	return exportEntry(getFloorEntry(key));
700		}
701
702		/**
#	Line 711 | Line 704 | public class TreeMap<K,V>
704		* @throws NullPointerException if the specified key is null
705		*         and this map uses natural ordering, or its comparator
706		*         does not permit null keys
707	+	* @since 1.6
708		*/
709		public K floorKey(K key) {
710	<	Entry<K,V> e = getFloorEntry(key);
717	<	return (e == null)? null : e.key;
710	>	return keyOrNull(getFloorEntry(key));
711		}
712
713		/**
#	Line 722 | Line 715 | public class TreeMap<K,V>
715		* @throws NullPointerException if the specified key is null
716		*         and this map uses natural ordering, or its comparator
717		*         does not permit null keys
718	+	* @since 1.6
719		*/
720		public Map.Entry<K,V> ceilingEntry(K key) {
721	<	Entry<K,V> e = getCeilingEntry(key);
728	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
721	>	return exportEntry(getCeilingEntry(key));
722		}
723
724		/**
#	Line 733 | Line 726 | public class TreeMap<K,V>
726		* @throws NullPointerException if the specified key is null
727		*         and this map uses natural ordering, or its comparator
728		*         does not permit null keys
729	+	* @since 1.6
730		*/
731		public K ceilingKey(K key) {
732	<	Entry<K,V> e = getCeilingEntry(key);
739	<	return (e == null)? null : e.key;
732	>	return keyOrNull(getCeilingEntry(key));
733		}
734
735		/**
#	Line 744 | Line 737 | public class TreeMap<K,V>
737		* @throws NullPointerException if the specified key is null
738		*         and this map uses natural ordering, or its comparator
739		*         does not permit null keys
740	+	* @since 1.6
741		*/
742		public Map.Entry<K,V> higherEntry(K key) {
743	<	Entry<K,V> e = getHigherEntry(key);
750	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
743	>	return exportEntry(getHigherEntry(key));
744		}
745
746		/**
#	Line 755 | Line 748 | public class TreeMap<K,V>
748		* @throws NullPointerException if the specified key is null
749		*         and this map uses natural ordering, or its comparator
750		*         does not permit null keys
751	+	* @since 1.6
752		*/
753		public K higherKey(K key) {
754	<	Entry<K,V> e = getHigherEntry(key);
761	<	return (e == null)? null : e.key;
754	>	return keyOrNull(getHigherEntry(key));
755		}
756
757		// Views
#	Line 768 | Line 761 | public class TreeMap<K,V>
761		* the first time this view is requested.  Views are stateless, so
762		* there's no reason to create more than one.
763		*/
764	<	private transient Set<Map.Entry<K,V>> entrySet = null;
765	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
766	<	private transient Set<K> descendingKeySet = null;
764	>	private transient EntrySet entrySet = null;
765	>	private transient KeySet<K> navigableKeySet = null;
766	>	private transient NavigableMap<K,V> descendingMap = null;
767
768		/**
769		* Returns a {@link Set} view of the keys contained in this map.
#	Line 787 | Line 780 | public class TreeMap<K,V>
780		* operations.
781		*/
782		public Set<K> keySet() {
783	<	Set<K> ks = keySet;
791	<	return (ks != null) ? ks : (keySet = new KeySet());
783	>	return navigableKeySet();
784		}
785
786	<	class KeySet extends AbstractSet<K> {
787	<	public Iterator<K> iterator() {
788	<	return new KeyIterator(getFirstEntry());
789	<	}
790	<
791	<	public int size() {
792	<	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	<	}
786	>	/**
787	>	* @since 1.6
788	>	*/
789	>	public NavigableSet<K> navigableKeySet() {
790	>	KeySet<K> nks = navigableKeySet;
791	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
792	>	}
793
794	<	public void clear() {
795	<	TreeMap.this.clear();
796	<	}
794	>	/**
795	>	* @since 1.6
796	>	*/
797	>	public NavigableSet<K> descendingKeySet() {
798	>	return descendingMap().navigableKeySet();
799		}
800
801		/**
#	Line 835 | Line 818 | public class TreeMap<K,V>
818		return (vs != null) ? vs : (values = new Values());
819		}
820
821	+	/**
822	+	* Returns a {@link Set} view of the mappings contained in this map.
823	+	* The set's iterator returns the entries in ascending key order.
824	+	* The set is backed by the map, so changes to the map are
825	+	* reflected in the set, and vice-versa.  If the map is modified
826	+	* while an iteration over the set is in progress (except through
827	+	* the iterator's own <tt>remove</tt> operation, or through the
828	+	* <tt>setValue</tt> operation on a map entry returned by the
829	+	* iterator) the results of the iteration are undefined.  The set
830	+	* supports element removal, which removes the corresponding
831	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
832	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
833	+	* <tt>clear</tt> operations.  It does not support the
834	+	* <tt>add</tt> or <tt>addAll</tt> operations.
835	+	*/
836	+	public Set<Map.Entry<K,V>> entrySet() {
837	+	EntrySet es = entrySet;
838	+	return (es != null) ? es : (entrySet = new EntrySet());
839	+	}
840	+
841	+	/**
842	+	* @since 1.6
843	+	*/
844	+	public NavigableMap<K, V> descendingMap() {
845	+	NavigableMap<K, V> km = descendingMap;
846	+	return (km != null) ? km :
847	+	(descendingMap = new DescendingSubMap(this,
848	+	true, null, true,
849	+	true, null, true));
850	+	}
851	+
852	+	/**
853	+	* @throws ClassCastException       {@inheritDoc}
854	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
855	+	*         null and this map uses natural ordering, or its comparator
856	+	*         does not permit null keys
857	+	* @throws IllegalArgumentException {@inheritDoc}
858	+	* @since 1.6
859	+	*/
860	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
861	+	K toKey,   boolean toInclusive) {
862	+	return new AscendingSubMap(this,
863	+	false, fromKey, fromInclusive,
864	+	false, toKey,   toInclusive);
865	+	}
866	+
867	+	/**
868	+	* @throws ClassCastException       {@inheritDoc}
869	+	* @throws NullPointerException if <tt>toKey</tt> is null
870	+	*         and this map uses natural ordering, or its comparator
871	+	*         does not permit null keys
872	+	* @throws IllegalArgumentException {@inheritDoc}
873	+	* @since 1.6
874	+	*/
875	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
876	+	return new AscendingSubMap(this,
877	+	true,  null,  true,
878	+	false, toKey, inclusive);
879	+	}
880	+
881	+	/**
882	+	* @throws ClassCastException       {@inheritDoc}
883	+	* @throws NullPointerException if <tt>fromKey</tt> is null
884	+	*         and this map uses natural ordering, or its comparator
885	+	*         does not permit null keys
886	+	* @throws IllegalArgumentException {@inheritDoc}
887	+	* @since 1.6
888	+	*/
889	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
890	+	return new AscendingSubMap(this,
891	+	false, fromKey, inclusive,
892	+	true,  null,    true);
893	+	}
894	+
895	+	/**
896	+	* @throws ClassCastException       {@inheritDoc}
897	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
898	+	*         null and this map uses natural ordering, or its comparator
899	+	*         does not permit null keys
900	+	* @throws IllegalArgumentException {@inheritDoc}
901	+	*/
902	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
903	+	return subMap(fromKey, true, toKey, false);
904	+	}
905	+
906	+	/**
907	+	* @throws ClassCastException       {@inheritDoc}
908	+	* @throws NullPointerException if <tt>toKey</tt> is null
909	+	*         and this map uses natural ordering, or its comparator
910	+	*         does not permit null keys
911	+	* @throws IllegalArgumentException {@inheritDoc}
912	+	*/
913	+	public SortedMap<K,V> headMap(K toKey) {
914	+	return headMap(toKey, false);
915	+	}
916	+
917	+	/**
918	+	* @throws ClassCastException       {@inheritDoc}
919	+	* @throws NullPointerException if <tt>fromKey</tt> is null
920	+	*         and this map uses natural ordering, or its comparator
921	+	*         does not permit null keys
922	+	* @throws IllegalArgumentException {@inheritDoc}
923	+	*/
924	+	public SortedMap<K,V> tailMap(K fromKey) {
925	+	return tailMap(fromKey, true);
926	+	}
927	+
928	+	// View class support
929	+
930		class Values extends AbstractCollection<V> {
931		public Iterator<V> iterator() {
932		return new ValueIterator(getFirstEntry());
#	Line 845 | Line 937 | public class TreeMap<K,V>
937		}
938
939		public boolean contains(Object o) {
940	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
849	<	if (valEquals(e.getValue(), o))
850	<	return true;
851	<	return false;
940	>	return TreeMap.this.containsValue(o);
941		}
942
943		public boolean remove(Object o) {
#	Line 866 | Line 955 | public class TreeMap<K,V>
955		}
956		}
957
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	–
958		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
959		public Iterator<Map.Entry<K,V>> iterator() {
960		return new EntryIterator(getFirstEntry());
#	Line 922 | Line 991 | public class TreeMap<K,V>
991		}
992		}
993
994	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
995	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
996	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
997	<	}
994	>	/*
995	>	* Unlike Values and EntrySet, the KeySet class is static,
996	>	* delegating to a NavigableMap to allow use by SubMaps, which
997	>	* outweighs the ugliness of needing type-tests for the following
998	>	* Iterator methods that are defined appropriately in main versus
999	>	* submap classes.
1000	>	*/
1001
1002	<	class DescendingEntrySet extends EntrySet {
1003	<	public Iterator<Map.Entry<K,V>> iterator() {
932	<	return new DescendingEntryIterator(getLastEntry());
933	<	}
1002	>	Iterator<K> keyIterator() {
1003	>	return new KeyIterator(getFirstEntry());
1004		}
1005
1006	<	public Set<K> descendingKeySet() {
1007	<	Set<K> ks = descendingKeySet;
938	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1006	>	Iterator<K> descendingKeyIterator() {
1007	>	return new DescendingKeyIterator(getFirstEntry());
1008		}
1009
1010	<	class DescendingKeySet extends KeySet {
1011	<	public Iterator<K> iterator() {
1012	<	return new DescendingKeyIterator(getLastEntry());
1010	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1011	>	private final NavigableMap<E, Object> m;
1012	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1013	>
1014	>	public Iterator<E> iterator() {
1015	>	if (m instanceof TreeMap)
1016	>	return ((TreeMap<E,Object>)m).keyIterator();
1017	>	else
1018	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1019	>	}
1020	>
1021	>	public Iterator<E> descendingIterator() {
1022	>	if (m instanceof TreeMap)
1023	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1024	>	else
1025	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1026	>	}
1027	>
1028	>	public int size() { return m.size(); }
1029	>	public boolean isEmpty() { return m.isEmpty(); }
1030	>	public boolean contains(Object o) { return m.containsKey(o); }
1031	>	public void clear() { m.clear(); }
1032	>	public E lower(E e) { return m.lowerKey(e); }
1033	>	public E floor(E e) { return m.floorKey(e); }
1034	>	public E ceiling(E e) { return m.ceilingKey(e); }
1035	>	public E higher(E e) { return m.higherKey(e); }
1036	>	public E first() { return m.firstKey(); }
1037	>	public E last() { return m.lastKey(); }
1038	>	public Comparator<? super E> comparator() { return m.comparator(); }
1039	>	public E pollFirst() {
1040	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1041	>	return e == null? null : e.getKey();
1042	>	}
1043	>	public E pollLast() {
1044	>	Map.Entry<E,Object> e = m.pollLastEntry();
1045	>	return e == null? null : e.getKey();
1046	>	}
1047	>	public boolean remove(Object o) {
1048	>	int oldSize = size();
1049	>	m.remove(o);
1050	>	return size() != oldSize;
1051	>	}
1052	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1053	>	E toElement, boolean toInclusive) {
1054	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1055	>	toElement,   toInclusive));
1056	>	}
1057	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1058	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1059	>	}
1060	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1061	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1062	>	}
1063	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1064	>	return subSet(fromElement, true, toElement, false);
1065	>	}
1066	>	public SortedSet<E> headSet(E toElement) {
1067	>	return headSet(toElement, false);
1068	>	}
1069	>	public SortedSet<E> tailSet(E fromElement) {
1070	>	return tailSet(fromElement, true);
1071	>	}
1072	>	public NavigableSet<E> descendingSet() {
1073	>	return new TreeSet(m.descendingMap());
1074		}
1075		}
1076
1077		/**
1078	<	* @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}
1078	>	* Base class for TreeMap Iterators
1079		*/
1080	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1081	<	return new SubMap(fromKey, toKey);
1080	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1081	>	Entry<K,V> next;
1082	>	Entry<K,V> lastReturned;
1083	>	int expectedModCount;
1084	>
1085	>	PrivateEntryIterator(Entry<K,V> first) {
1086	>	expectedModCount = modCount;
1087	>	lastReturned = null;
1088	>	next = first;
1089	>	}
1090	>
1091	>	public final boolean hasNext() {
1092	>	return next != null;
1093	>	}
1094	>
1095	>	final Entry<K,V> nextEntry() {
1096	>	Entry<K,V> e = lastReturned = next;
1097	>	if (e == null)
1098	>	throw new NoSuchElementException();
1099	>	if (modCount != expectedModCount)
1100	>	throw new ConcurrentModificationException();
1101	>	next = successor(e);
1102	>	return e;
1103	>	}
1104	>
1105	>	final Entry<K,V> prevEntry() {
1106	>	Entry<K,V> e = lastReturned= next;
1107	>	if (e == null)
1108	>	throw new NoSuchElementException();
1109	>	if (modCount != expectedModCount)
1110	>	throw new ConcurrentModificationException();
1111	>	next = predecessor(e);
1112	>	return e;
1113	>	}
1114	>
1115	>	public void remove() {
1116	>	if (lastReturned == null)
1117	>	throw new IllegalStateException();
1118	>	if (modCount != expectedModCount)
1119	>	throw new ConcurrentModificationException();
1120	>	if (lastReturned.left != null && lastReturned.right != null)
1121	>	next = lastReturned;
1122	>	deleteEntry(lastReturned);
1123	>	expectedModCount++;
1124	>	lastReturned = null;
1125	>	}
1126		}
1127
1128	+	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1129	+	EntryIterator(Entry<K,V> first) {
1130	+	super(first);
1131	+	}
1132	+	public Map.Entry<K,V> next() {
1133	+	return nextEntry();
1134	+	}
1135	+	}
1136	+
1137	+	final class ValueIterator extends PrivateEntryIterator<V> {
1138	+	ValueIterator(Entry<K,V> first) {
1139	+	super(first);
1140	+	}
1141	+	public V next() {
1142	+	return nextEntry().value;
1143	+	}
1144	+	}
1145	+
1146	+	final class KeyIterator extends PrivateEntryIterator<K> {
1147	+	KeyIterator(Entry<K,V> first) {
1148	+	super(first);
1149	+	}
1150	+	public K next() {
1151	+	return nextEntry().key;
1152	+	}
1153	+	}
1154	+
1155	+	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1156	+	DescendingKeyIterator(Entry<K,V> first) {
1157	+	super(first);
1158	+	}
1159	+	public K next() {
1160	+	return prevEntry().key;
1161	+	}
1162	+	}
1163	+
1164	+	// Little utilities
1165	+
1166		/**
1167	<	* @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}
1167	>	* Compares two keys using the correct comparison method for this TreeMap.
1168		*/
1169	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1170	<	return new SubMap(toKey, true);
1169	>	final int compare(Object k1, Object k2) {
1170	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1171	>	: comparator.compare((K)k1, (K)k2);
1172		}
1173
1174		/**
1175	<	* @throws ClassCastException       {@inheritDoc}
1176	<	* @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}
1175	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1176	>	* that it copes with <tt>null</tt> o1 properly.
1177		*/
1178	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1179	<	return new SubMap(fromKey, false);
1178	>	final static boolean valEquals(Object o1, Object o2) {
1179	>	return (o1==null ? o2==null : o1.equals(o2));
1180		}
1181
1182		/**
1183	<	* 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}
1183	>	* Return SimpleImmutableEntry for entry, or null if null
1184		*/
1185	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1186	<	return new SubMap(fromKey, toKey);
1185	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1186	>	return e == null? null :
1187	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1188		}
1189
1190		/**
1191	<	* 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}
1191	>	* Return key for entry, or null if null
1192		*/
1193	<	public SortedMap<K,V> headMap(K toKey) {
1194	<	return new SubMap(toKey, true);
1193	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1194	>	return e == null? null : e.key;
1195		}
1196
1197		/**
1198	<	* Equivalent to {@link #navigableTailMap} but with a return type
1199	<	* 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}
1198	>	* Returns the key corresponding to the specified Entry.
1199	>	* @throws NoSuchElementException if the Entry is null
1200		*/
1201	<	public SortedMap<K,V> tailMap(K fromKey) {
1202	<	return new SubMap(fromKey, false);
1201	>	static <K> K key(Entry<K,?> e) {
1202	>	if (e==null)
1203	>	throw new NoSuchElementException();
1204	>	return e.key;
1205		}
1206
1028	–	private class SubMap
1029	–	extends AbstractMap<K,V>
1030	–	implements NavigableMap<K,V>, java.io.Serializable {
1031	–	private static final long serialVersionUID = -6520786458950516097L;
1207
1208	<	/**
1209	<	* fromKey is significant only if fromStart is false.  Similarly,
1210	<	* toKey is significant only if toStart is false.
1208	>	// SubMaps
1209	>
1210	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1211	>	implements NavigableMap<K,V>, java.io.Serializable {
1212	>	/*
1213	>	* The backing map.
1214		*/
1215	<	private boolean fromStart = false, toEnd = false;
1038	<	private K fromKey, toKey;
1215	>	final TreeMap<K,V> m;
1216
1217	<	SubMap(K fromKey, K toKey) {
1218	<	if (compare(fromKey, toKey) > 0)
1219	<	throw new IllegalArgumentException("fromKey > toKey");
1220	<	this.fromKey = fromKey;
1221	<	this.toKey = toKey;
1222	<	}
1217	>	/*
1218	>	* Endpoints are represented as triples (fromStart, lo,
1219	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1220	>	* true, then the low (absolute) bound is the start of the
1221	>	* backing map, and the other values are ignored. Otherwise,
1222	>	* if loInclusive is true, lo is the inclusive bound, else lo
1223	>	* is the exclusive bound. Similarly for the upper bound.
1224	>	*/
1225
1226	<	SubMap(K key, boolean headMap) {
1227	<	compare(key, key); // Type-check key
1228	<
1229	<	if (headMap) {
1230	<	fromStart = true;
1231	<	toKey = key;
1226	>	final K lo, hi;
1227	>	final boolean fromStart, toEnd;
1228	>	final boolean loInclusive, hiInclusive;
1229	>
1230	>	NavigableSubMap(TreeMap<K,V> m,
1231	>	boolean fromStart, K lo, boolean loInclusive,
1232	>	boolean toEnd,     K hi, boolean hiInclusive) {
1233	>	if (!fromStart && !toEnd) {
1234	>	if (m.compare(lo, hi) > 0)
1235	>	throw new IllegalArgumentException("fromKey > toKey");
1236		} else {
1237	<	toEnd = true;
1238	<	fromKey = key;
1237	>	if (!fromStart) // type check
1238	>	m.compare(lo, lo);
1239	>	if (!toEnd)
1240	>	m.compare(hi, hi);
1241		}
1057	–	}
1242
1243	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1243	>	this.m = m;
1244		this.fromStart = fromStart;
1245	<	this.fromKey= fromKey;
1245	>	this.lo = lo;
1246	>	this.loInclusive = loInclusive;
1247		this.toEnd = toEnd;
1248	<	this.toKey = toKey;
1248	>	this.hi = hi;
1249	>	this.hiInclusive = hiInclusive;
1250	>	}
1251	>
1252	>	// internal utilities
1253	>
1254	>	final boolean tooLow(Object key) {
1255	>	if (!fromStart) {
1256	>	int c = m.compare(key, lo);
1257	>	if (c < 0 || (c == 0 && !loInclusive))
1258	>	return true;
1259	>	}
1260	>	return false;
1261	>	}
1262	>
1263	>	final boolean tooHigh(Object key) {
1264	>	if (!toEnd) {
1265	>	int c = m.compare(key, hi);
1266	>	if (c > 0 || (c == 0 && !hiInclusive))
1267	>	return true;
1268	>	}
1269	>	return false;
1270	>	}
1271	>
1272	>	final boolean inRange(Object key) {
1273	>	return !tooLow(key) && !tooHigh(key);
1274	>	}
1275	>
1276	>	final boolean inClosedRange(Object key) {
1277	>	return (fromStart || m.compare(key, lo) >= 0)
1278	>	&& (toEnd || m.compare(hi, key) >= 0);
1279	>	}
1280	>
1281	>	final boolean inRange(Object key, boolean inclusive) {
1282	>	return inclusive ? inRange(key) : inClosedRange(key);
1283	>	}
1284	>
1285	>	/*
1286	>	* Absolute versions of relation operations.
1287	>	* Subclasses map to these using like-named "sub"
1288	>	* versions that invert senses for descending maps
1289	>	*/
1290	>
1291	>	final TreeMap.Entry<K,V> absLowest() {
1292	>	TreeMap.Entry<K,V> e =
1293	>	(fromStart ?  m.getFirstEntry() :
1294	>	(loInclusive ? m.getCeilingEntry(lo) :
1295	>	m.getHigherEntry(lo)));
1296	>	return (e == null || tooHigh(e.key)) ? null : e;
1297	>	}
1298	>
1299	>	final TreeMap.Entry<K,V> absHighest() {
1300	>	TreeMap.Entry<K,V> e =
1301	>	(toEnd ?  m.getLastEntry() :
1302	>	(hiInclusive ?  m.getFloorEntry(hi) :
1303	>	m.getLowerEntry(hi)));
1304	>	return (e == null || tooLow(e.key)) ? null : e;
1305	>	}
1306	>
1307	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1308	>	if (tooLow(key))
1309	>	return absLowest();
1310	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1311	>	return (e == null || tooHigh(e.key)) ? null : e;
1312	>	}
1313	>
1314	>	final TreeMap.Entry<K,V> absHigher(K key) {
1315	>	if (tooLow(key))
1316	>	return absLowest();
1317	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1318	>	return (e == null || tooHigh(e.key)) ? null : e;
1319	>	}
1320	>
1321	>	final TreeMap.Entry<K,V> absFloor(K key) {
1322	>	if (tooHigh(key))
1323	>	return absHighest();
1324	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1325	>	return (e == null || tooLow(e.key)) ? null : e;
1326	>	}
1327	>
1328	>	final TreeMap.Entry<K,V> absLower(K key) {
1329	>	if (tooHigh(key))
1330	>	return absHighest();
1331	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1332	>	return (e == null || tooLow(e.key)) ? null : e;
1333	>	}
1334	>
1335	>	/** Returns the absolute high fence for ascending traversal */
1336	>	final TreeMap.Entry<K,V> absHighFence() {
1337	>	return (toEnd ? null : (hiInclusive ?
1338	>	m.getHigherEntry(hi) :
1339	>	m.getCeilingEntry(hi)));
1340	>	}
1341	>
1342	>	/** Return the absolute low fence for descending traversal  */
1343	>	final TreeMap.Entry<K,V> absLowFence() {
1344	>	return (fromStart ? null : (loInclusive ?
1345	>	m.getLowerEntry(lo) :
1346	>	m.getFloorEntry(lo)));
1347		}
1348
1349	+	// Abstract methods defined in ascending vs descending classes
1350	+	// These relay to the appropriate  absolute versions
1351	+
1352	+	abstract TreeMap.Entry<K,V> subLowest();
1353	+	abstract TreeMap.Entry<K,V> subHighest();
1354	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1355	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1356	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1357	+	abstract TreeMap.Entry<K,V> subLower(K key);
1358	+
1359	+	/** Returns ascending iterator from the perspective of this submap */
1360	+	abstract Iterator<K> keyIterator();
1361	+
1362	+	/** Returns descending iterator from the perspective of this submap */
1363	+	abstract Iterator<K> descendingKeyIterator();
1364	+
1365	+	// public methods
1366	+
1367		public boolean isEmpty() {
1368	<	return entrySet().isEmpty();
1368	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1369		}
1370
1371	<	public boolean containsKey(Object key) {
1372	<	return inRange(key) && TreeMap.this.containsKey(key);
1371	>	public int size() {
1372	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1373		}
1374
1375	<	public V get(Object key) {
1376	<	if (!inRange(key))
1076	<	return null;
1077	<	return TreeMap.this.get(key);
1375	>	public final boolean containsKey(Object key) {
1376	>	return inRange(key) && m.containsKey(key);
1377		}
1378
1379	<	public V put(K key, V value) {
1379	>	public final V put(K key, V value) {
1380		if (!inRange(key))
1381		throw new IllegalArgumentException("key out of range");
1382	<	return TreeMap.this.put(key, value);
1382	>	return m.put(key, value);
1383		}
1384
1385	<	public V remove(Object key) {
1386	<	if (!inRange(key))
1088	<	return null;
1089	<	return TreeMap.this.remove(key);
1385	>	public final V get(Object key) {
1386	>	return !inRange(key)? null :  m.get(key);
1387		}
1388
1389	<	public Comparator<? super K> comparator() {
1390	<	return comparator;
1389	>	public final V remove(Object key) {
1390	>	return !inRange(key)? null  : m.remove(key);
1391		}
1392
1393	<	public K firstKey() {
1394	<	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;
1393	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1394	>	return exportEntry(subCeiling(key));
1395		}
1396
1397	<	public K lastKey() {
1398	<	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;
1397	>	public final K ceilingKey(K key) {
1398	>	return keyOrNull(subCeiling(key));
1399		}
1400
1401	<	public Map.Entry<K,V> firstEntry() {
1402	<	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;
1401	>	public final Map.Entry<K,V> higherEntry(K key) {
1402	>	return exportEntry(subHigher(key));
1403		}
1404
1405	<	public Map.Entry<K,V> lastEntry() {
1406	<	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;
1405	>	public final K higherKey(K key) {
1406	>	return keyOrNull(subHigher(key));
1407		}
1408
1409	<	public Map.Entry<K,V> pollFirstEntry() {
1410	<	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;
1409	>	public final Map.Entry<K,V> floorEntry(K key) {
1410	>	return exportEntry(subFloor(key));
1411		}
1412
1413	<	public Map.Entry<K,V> pollLastEntry() {
1414	<	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;
1413	>	public final K floorKey(K key) {
1414	>	return keyOrNull(subFloor(key));
1415		}
1416
1417	<	private TreeMap.Entry<K,V> subceiling(K key) {
1418	<	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;
1417	>	public final Map.Entry<K,V> lowerEntry(K key) {
1418	>	return exportEntry(subLower(key));
1419		}
1420
1421	<	public Map.Entry<K,V> ceilingEntry(K key) {
1422	<	TreeMap.Entry<K,V> e = subceiling(key);
1158	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1421	>	public final K lowerKey(K key) {
1422	>	return keyOrNull(subLower(key));
1423		}
1424
1425	<	public K ceilingKey(K key) {
1426	<	TreeMap.Entry<K,V> e = subceiling(key);
1163	<	return e == null? null : e.key;
1425	>	public final K firstKey() {
1426	>	return key(subLowest());
1427		}
1428
1429	<
1430	<	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;
1429	>	public final K lastKey() {
1430	>	return key(subHighest());
1431		}
1432
1433	<	public Map.Entry<K,V> higherEntry(K key) {
1434	<	TreeMap.Entry<K,V> e = subhigher(key);
1177	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1433	>	public final Map.Entry<K,V> firstEntry() {
1434	>	return exportEntry(subLowest());
1435		}
1436
1437	<	public K higherKey(K key) {
1438	<	TreeMap.Entry<K,V> e = subhigher(key);
1182	<	return e == null? null : e.key;
1437	>	public final Map.Entry<K,V> lastEntry() {
1438	>	return exportEntry(subHighest());
1439		}
1440
1441	<	private TreeMap.Entry<K,V> subfloor(K key) {
1442	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1443	<	getLowerEntry(toKey) : getFloorEntry(key);
1444	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1445	<	return null;
1446	<	return e;
1441	>	public final Map.Entry<K,V> pollFirstEntry() {
1442	>	TreeMap.Entry<K,V> e = subLowest();
1443	>	Map.Entry<K,V> result = exportEntry(e);
1444	>	if (e != null)
1445	>	m.deleteEntry(e);
1446	>	return result;
1447		}
1448
1449	<	public Map.Entry<K,V> floorEntry(K key) {
1450	<	TreeMap.Entry<K,V> e = subfloor(key);
1451	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1449	>	public final Map.Entry<K,V> pollLastEntry() {
1450	>	TreeMap.Entry<K,V> e = subHighest();
1451	>	Map.Entry<K,V> result = exportEntry(e);
1452	>	if (e != null)
1453	>	m.deleteEntry(e);
1454	>	return result;
1455		}
1456
1457	<	public K floorKey(K key) {
1458	<	TreeMap.Entry<K,V> e = subfloor(key);
1459	<	return e == null? null : e.key;
1457	>	// Views
1458	>	transient NavigableMap<K,V> descendingMapView = null;
1459	>	transient EntrySetView entrySetView = null;
1460	>	transient KeySet<K> navigableKeySetView = null;
1461	>
1462	>	public final NavigableSet<K> navigableKeySet() {
1463	>	KeySet<K> nksv = navigableKeySetView;
1464	>	return (nksv != null) ? nksv :
1465	>	(navigableKeySetView = new TreeMap.KeySet(this));
1466		}
1467
1468	<	private TreeMap.Entry<K,V> sublower(K key) {
1469	<	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;
1468	>	public final Set<K> keySet() {
1469	>	return navigableKeySet();
1470		}
1471
1472	<	public Map.Entry<K,V> lowerEntry(K key) {
1473	<	TreeMap.Entry<K,V> e = sublower(key);
1213	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1472	>	public NavigableSet<K> descendingKeySet() {
1473	>	return descendingMap().navigableKeySet();
1474		}
1475
1476	<	public K lowerKey(K key) {
1477	<	TreeMap.Entry<K,V> e = sublower(key);
1218	<	return e == null? null : e.key;
1476	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1477	>	return subMap(fromKey, true, toKey, false);
1478		}
1479
1480	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1480	>	public final SortedMap<K,V> headMap(K toKey) {
1481	>	return headMap(toKey, false);
1482	>	}
1483
1484	<	public Set<Map.Entry<K,V>> entrySet() {
1485	<	Set<Map.Entry<K,V>> es = entrySet;
1225	<	return (es != null)? es : (entrySet = new EntrySetView());
1484	>	public final SortedMap<K,V> tailMap(K fromKey) {
1485	>	return tailMap(fromKey, true);
1486		}
1487
1488	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1488	>	// View classes
1489	>
1490	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1491		private transient int size = -1, sizeModCount;
1492
1493		public int size() {
1494	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1495	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1494	>	if (fromStart && toEnd)
1495	>	return m.size();
1496	>	if (size == -1 || sizeModCount != m.modCount) {
1497	>	sizeModCount = m.modCount;
1498	>	size = 0;
1499		Iterator i = iterator();
1500		while (i.hasNext()) {
1501		size++;
#	Line 1241 | Line 1506 | public class TreeMap<K,V>
1506		}
1507
1508		public boolean isEmpty() {
1509	<	return !iterator().hasNext();
1509	>	TreeMap.Entry<K,V> n = absLowest();
1510	>	return n == null || tooHigh(n.key);
1511		}
1512
1513		public boolean contains(Object o) {
#	Line 1251 | Line 1517 | public class TreeMap<K,V>
1517		K key = entry.getKey();
1518		if (!inRange(key))
1519		return false;
1520	<	TreeMap.Entry node = getEntry(key);
1520	>	TreeMap.Entry node = m.getEntry(key);
1521		return node != null &&
1522	<	valEquals(node.getValue(), entry.getValue());
1522	>	valEquals(node.getValue(), entry.getValue());
1523		}
1524
1525		public boolean remove(Object o) {
#	Line 1263 | Line 1529 | public class TreeMap<K,V>
1529		K key = entry.getKey();
1530		if (!inRange(key))
1531		return false;
1532	<	TreeMap.Entry<K,V> node = getEntry(key);
1532	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1533		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1534	<	deleteEntry(node);
1534	>	m.deleteEntry(node);
1535		return true;
1536		}
1537		return false;
1538		}
1273	–
1274	–	public Iterator<Map.Entry<K,V>> iterator() {
1275	–	return new SubMapEntryIterator(
1276	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1277	–	(toEnd     ? null            : getCeilingEntry(toKey)));
1278	–	}
1539		}
1540
1541	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1542	<	private transient Set<K> descendingKeySetView = null;
1543	<
1544	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1545	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1546	<	return (es != null) ? es :
1547	<	(descendingEntrySetView = new DescendingEntrySetView());
1548	<	}
1289	<
1290	<	public Set<K> descendingKeySet() {
1291	<	Set<K> ks = descendingKeySetView;
1292	<	return (ks != null) ? ks :
1293	<	(descendingKeySetView = new DescendingKeySetView());
1294	<	}
1541	>	/**
1542	>	* Iterators for SubMaps
1543	>	*/
1544	>	abstract class SubMapIterator<T> implements Iterator<T> {
1545	>	TreeMap.Entry<K,V> lastReturned;
1546	>	TreeMap.Entry<K,V> next;
1547	>	final K fenceKey;
1548	>	int expectedModCount;
1549
1550	<	private class DescendingEntrySetView extends EntrySetView {
1551	<	public Iterator<Map.Entry<K,V>> iterator() {
1552	<	return new DescendingSubMapEntryIterator
1553	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1554	<	(fromStart ? null            : getLowerEntry(fromKey)));
1550	>	SubMapIterator(TreeMap.Entry<K,V> first,
1551	>	TreeMap.Entry<K,V> fence) {
1552	>	expectedModCount = m.modCount;
1553	>	lastReturned = null;
1554	>	next = first;
1555	>	fenceKey = fence == null ? null : fence.key;
1556		}
1302	–	}
1557
1558	<	private class DescendingKeySetView extends AbstractSet<K> {
1559	<	public Iterator<K> iterator() {
1560	<	return new Iterator<K>() {
1307	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1558	>	public final boolean hasNext() {
1559	>	return next != null && next.key != fenceKey;
1560	>	}
1561
1562	<	public boolean hasNext() { return i.hasNext(); }
1563	<	public K next() { return i.next().getKey(); }
1564	<	public void remove() { i.remove(); }
1565	<	};
1562	>	final TreeMap.Entry<K,V> nextEntry() {
1563	>	TreeMap.Entry<K,V> e = lastReturned = next;
1564	>	if (e == null || e.key == fenceKey)
1565	>	throw new NoSuchElementException();
1566	>	if (m.modCount != expectedModCount)
1567	>	throw new ConcurrentModificationException();
1568	>	next = successor(e);
1569	>	return e;
1570		}
1571
1572	<	public int size() {
1573	<	return SubMap.this.size();
1572	>	final TreeMap.Entry<K,V> prevEntry() {
1573	>	TreeMap.Entry<K,V> e = lastReturned = next;
1574	>	if (e == null || e.key == fenceKey)
1575	>	throw new NoSuchElementException();
1576	>	if (m.modCount != expectedModCount)
1577	>	throw new ConcurrentModificationException();
1578	>	next = predecessor(e);
1579	>	return e;
1580		}
1581
1582	<	public boolean contains(Object k) {
1583	<	return SubMap.this.containsKey(k);
1582	>	public void remove() {
1583	>	if (lastReturned == null)
1584	>	throw new IllegalStateException();
1585	>	if (m.modCount != expectedModCount)
1586	>	throw new ConcurrentModificationException();
1587	>	if (lastReturned.left != null && lastReturned.right != null)
1588	>	next = lastReturned;
1589	>	m.deleteEntry(lastReturned);
1590	>	expectedModCount++;
1591	>	lastReturned = null;
1592		}
1593		}
1594
1595	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1596	<	if (!inRange2(fromKey))
1597	<	throw new IllegalArgumentException("fromKey out of range");
1598	<	if (!inRange2(toKey))
1599	<	throw new IllegalArgumentException("toKey out of range");
1600	<	return new SubMap(fromKey, toKey);
1595	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1596	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1597	>	TreeMap.Entry<K,V> fence) {
1598	>	super(first, fence);
1599	>	}
1600	>	public Map.Entry<K,V> next() {
1601	>	return nextEntry();
1602	>	}
1603		}
1604
1605	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1606	<	if (!inRange2(toKey))
1607	<	throw new IllegalArgumentException("toKey out of range");
1608	<	return new SubMap(fromStart, fromKey, false, toKey);
1605	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1606	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1607	>	TreeMap.Entry<K,V> fence) {
1608	>	super(first, fence);
1609	>	}
1610	>	public K next() {
1611	>	return nextEntry().key;
1612	>	}
1613		}
1614
1615	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1616	<	if (!inRange2(fromKey))
1617	<	throw new IllegalArgumentException("fromKey out of range");
1618	<	return new SubMap(false, fromKey, toEnd, toKey);
1619	<	}
1615	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1616	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1617	>	TreeMap.Entry<K,V> fence) {
1618	>	super(last, fence);
1619	>	}
1620
1621	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1622	<	return navigableSubMap(fromKey, toKey);
1621	>	public Map.Entry<K,V> next() {
1622	>	return prevEntry();
1623	>	}
1624		}
1625
1626	<	public SortedMap<K,V> headMap(K toKey) {
1627	<	return navigableHeadMap(toKey);
1626	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1627	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1628	>	TreeMap.Entry<K,V> fence) {
1629	>	super(last, fence);
1630	>	}
1631	>	public K next() {
1632	>	return prevEntry().key;
1633	>	}
1634		}
1635	+	}
1636
1637	<	public SortedMap<K,V> tailMap(K fromKey) {
1638	<	return navigableTailMap(fromKey);
1354	<	}
1637	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1638	>	private static final long serialVersionUID = 912986545866124060L;
1639
1640	<	private boolean inRange(Object key) {
1641	<	return (fromStart || compare(key, fromKey) >= 0) &&
1642	<	(toEnd     || compare(key, toKey)   <  0);
1640	>	AscendingSubMap(TreeMap<K,V> m,
1641	>	boolean fromStart, K lo, boolean loInclusive,
1642	>	boolean toEnd, K hi, boolean hiInclusive) {
1643	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1644		}
1645
1646	<	// This form allows the high endpoint (as well as all legit keys)
1647	<	private boolean inRange2(Object key) {
1363	<	return (fromStart || compare(key, fromKey) >= 0) &&
1364	<	(toEnd     || compare(key, toKey)   <= 0);
1646	>	public Comparator<? super K> comparator() {
1647	>	return m.comparator();
1648		}
1366	–	}
1367	–
1368	–	/**
1369	–	* TreeMap Iterator.
1370	–	*/
1371	–	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1372	–	int expectedModCount = TreeMap.this.modCount;
1373	–	Entry<K,V> lastReturned = null;
1374	–	Entry<K,V> next;
1649
1650	<	PrivateEntryIterator(Entry<K,V> first) {
1651	<	next = first;
1650	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1651	>	K toKey, boolean toInclusive) {
1652	>	if (!inRange(fromKey, fromInclusive))
1653	>	throw new IllegalArgumentException("fromKey out of range");
1654	>	if (!inRange(toKey, toInclusive))
1655	>	throw new IllegalArgumentException("toKey out of range");
1656	>	return new AscendingSubMap(m,
1657	>	false, fromKey, fromInclusive,
1658	>	false, toKey,   toInclusive);
1659		}
1660
1661	<	public boolean hasNext() {
1662	<	return next != null;
1661	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1662	>	if (!inClosedRange(toKey))
1663	>	throw new IllegalArgumentException("toKey out of range");
1664	>	return new AscendingSubMap(m,
1665	>	fromStart, lo,    loInclusive,
1666	>	false,     toKey, inclusive);
1667		}
1668
1669	<	Entry<K,V> nextEntry() {
1670	<	if (next == null)
1671	<	throw new NoSuchElementException();
1672	<	if (modCount != expectedModCount)
1673	<	throw new ConcurrentModificationException();
1674	<	lastReturned = next;
1390	<	next = successor(next);
1391	<	return lastReturned;
1669	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1670	>	if (!inRange(fromKey, inclusive))
1671	>	throw new IllegalArgumentException("fromKey out of range");
1672	>	return new AscendingSubMap(m,
1673	>	false, fromKey, inclusive,
1674	>	toEnd, hi,      hiInclusive);
1675		}
1676
1677	<	public void remove() {
1678	<	if (lastReturned == null)
1679	<	throw new IllegalStateException();
1680	<	if (modCount != expectedModCount)
1681	<	throw new ConcurrentModificationException();
1682	<	if (lastReturned.left != null && lastReturned.right != null)
1683	<	next = lastReturned;
1401	<	deleteEntry(lastReturned);
1402	<	expectedModCount++;
1403	<	lastReturned = null;
1677	>	public NavigableMap<K,V> descendingMap() {
1678	>	NavigableMap<K,V> mv = descendingMapView;
1679	>	return (mv != null) ? mv :
1680	>	(descendingMapView =
1681	>	new DescendingSubMap(m,
1682	>	fromStart, lo, loInclusive,
1683	>	toEnd,     hi, hiInclusive));
1684		}
1405	–	}
1685
1686	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1687	<	EntryIterator(Entry<K,V> first) {
1409	<	super(first);
1686	>	Iterator<K> keyIterator() {
1687	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1688		}
1411	–	public Map.Entry<K,V> next() {
1412	–	return nextEntry();
1413	–	}
1414	–	}
1689
1690	<	class KeyIterator extends PrivateEntryIterator<K> {
1691	<	KeyIterator(Entry<K,V> first) {
1418	<	super(first);
1419	<	}
1420	<	public K next() {
1421	<	return nextEntry().key;
1690	>	Iterator<K> descendingKeyIterator() {
1691	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1692		}
1423	–	}
1693
1694	<	class ValueIterator extends PrivateEntryIterator<V> {
1695	<	ValueIterator(Entry<K,V> first) {
1696	<	super(first);
1694	>	final class AscendingEntrySetView extends EntrySetView {
1695	>	public Iterator<Map.Entry<K,V>> iterator() {
1696	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1697	>	}
1698		}
1699	<	public V next() {
1700	<	return nextEntry().value;
1699	>
1700	>	public Set<Map.Entry<K,V>> entrySet() {
1701	>	EntrySetView es = entrySetView;
1702	>	return (es != null) ? es : new AscendingEntrySetView();
1703		}
1432	–	}
1704
1705	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1706	<	private final K firstExcludedKey;
1705	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1706	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1707	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1708	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1709	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1710	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1711	>	}
1712
1713	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1714	<	super(first);
1715	<	firstExcludedKey = (firstExcluded == null
1716	<	? null
1717	<	: firstExcluded.key);
1713	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1714	>	private static final long serialVersionUID = 912986545866120460L;
1715	>	DescendingSubMap(TreeMap<K,V> m,
1716	>	boolean fromStart, K lo, boolean loInclusive,
1717	>	boolean toEnd, K hi, boolean hiInclusive) {
1718	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1719		}
1720
1721	<	public boolean hasNext() {
1722	<	return next != null && next.key != firstExcludedKey;
1446	<	}
1721	>	private final Comparator<? super K> reverseComparator =
1722	>	Collections.reverseOrder(m.comparator);
1723
1724	<	public Map.Entry<K,V> next() {
1725	<	if (next == null || next.key == firstExcludedKey)
1450	<	throw new NoSuchElementException();
1451	<	return nextEntry();
1724	>	public Comparator<? super K> comparator() {
1725	>	return reverseComparator;
1726		}
1453	–	}
1727
1728	<	/**
1729	<	* Base for Descending Iterators.
1730	<	*/
1731	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1732	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1733	<	super(first);
1728	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1729	>	K toKey, boolean toInclusive) {
1730	>	if (!inRange(fromKey, fromInclusive))
1731	>	throw new IllegalArgumentException("fromKey out of range");
1732	>	if (!inRange(toKey, toInclusive))
1733	>	throw new IllegalArgumentException("toKey out of range");
1734	>	return new DescendingSubMap(m,
1735	>	false, toKey,   toInclusive,
1736	>	false, fromKey, fromInclusive);
1737		}
1738
1739	<	Entry<K,V> nextEntry() {
1740	<	if (next == null)
1741	<	throw new NoSuchElementException();
1742	<	if (modCount != expectedModCount)
1743	<	throw new ConcurrentModificationException();
1744	<	lastReturned = next;
1469	<	next = predecessor(next);
1470	<	return lastReturned;
1739	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1740	>	if (!inRange(toKey, inclusive))
1741	>	throw new IllegalArgumentException("toKey out of range");
1742	>	return new DescendingSubMap(m,
1743	>	false, toKey, inclusive,
1744	>	toEnd, hi,    hiInclusive);
1745		}
1472	–	}
1746
1747	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1748	<	DescendingEntryIterator(Entry<K,V> first) {
1749	<	super(first);
1750	<	}
1751	<	public Map.Entry<K,V> next() {
1752	<	return nextEntry();
1747	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1748	>	if (!inRange(fromKey, inclusive))
1749	>	throw new IllegalArgumentException("fromKey out of range");
1750	>	return new DescendingSubMap(m,
1751	>	fromStart, lo, loInclusive,
1752	>	false, fromKey, inclusive);
1753		}
1481	–	}
1754
1755	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1756	<	DescendingKeyIterator(Entry<K,V> first) {
1757	<	super(first);
1758	<	}
1759	<	public K next() {
1760	<	return nextEntry().key;
1755	>	public NavigableMap<K,V> descendingMap() {
1756	>	NavigableMap<K,V> mv = descendingMapView;
1757	>	return (mv != null) ? mv :
1758	>	(descendingMapView =
1759	>	new AscendingSubMap(m,
1760	>	fromStart, lo, loInclusive,
1761	>	toEnd,     hi, hiInclusive));
1762		}
1490	–	}
1491	–
1763
1764	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1765	<	private final K lastExcludedKey;
1764	>	Iterator<K> keyIterator() {
1765	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1766	>	}
1767
1768	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1769	<	super(last);
1498	<	lastExcludedKey = (lastExcluded == null
1499	<	? null
1500	<	: lastExcluded.key);
1768	>	Iterator<K> descendingKeyIterator() {
1769	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1770		}
1771
1772	<	public boolean hasNext() {
1773	<	return next != null && next.key != lastExcludedKey;
1772	>	final class DescendingEntrySetView extends EntrySetView {
1773	>	public Iterator<Map.Entry<K,V>> iterator() {
1774	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1775	>	}
1776		}
1777
1778	<	public Map.Entry<K,V> next() {
1779	<	if (next == null || next.key == lastExcludedKey)
1780	<	throw new NoSuchElementException();
1510	<	return nextEntry();
1778	>	public Set<Map.Entry<K,V>> entrySet() {
1779	>	EntrySetView es = entrySetView;
1780	>	return (es != null) ? es : new DescendingEntrySetView();
1781		}
1782
1783	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1784	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1785	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1786	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1787	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1788	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1789		}
1790
1791		/**
1792	<	* Compares two keys using the correct comparison method for this TreeMap.
1792	>	* This class exists solely for the sake of serialization
1793	>	* compatibility with previous releases of TreeMap that did not
1794	>	* support NavigableMap.  It translates an old-version SubMap into
1795	>	* a new-version AscendingSubMap. This class is never otherwise
1796	>	* used.
1797		*/
1798	<	private int compare(Object k1, Object k2) {
1799	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1800	<	: comparator.compare((K)k1, (K)k2);
1798	>	private class SubMap extends AbstractMap<K,V>
1799	>	implements SortedMap<K,V>, java.io.Serializable {
1800	>	private static final long serialVersionUID = -6520786458950516097L;
1801	>	private boolean fromStart = false, toEnd = false;
1802	>	private K fromKey, toKey;
1803	>	private Object readResolve() {
1804	>	return new AscendingSubMap(TreeMap.this,
1805	>	fromStart, fromKey, true,
1806	>	toEnd, toKey, false);
1807	>	}
1808	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1809	>	public K lastKey() { throw new InternalError(); }
1810	>	public K firstKey() { throw new InternalError(); }
1811	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1812	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1813	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1814	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1815		}
1816
1817	<	/**
1818	<	* 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	<	}
1817	>
1818	>	// Red-black mechanics
1819
1820		private static final boolean RED   = false;
1821		private static final boolean BLACK = true;
#	Line 1536 | Line 1825 | public class TreeMap<K,V>
1825		* user (see Map.Entry).
1826		*/
1827
1828	<	static class Entry<K,V> implements Map.Entry<K,V> {
1828	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1829		K key;
1830		V value;
1831		Entry<K,V> left = null;
#	Line 1608 | Line 1897 | public class TreeMap<K,V>
1897		* Returns the first Entry in the TreeMap (according to the TreeMap's
1898		* key-sort function).  Returns null if the TreeMap is empty.
1899		*/
1900	<	private Entry<K,V> getFirstEntry() {
1900	>	final Entry<K,V> getFirstEntry() {
1901		Entry<K,V> p = root;
1902		if (p != null)
1903		while (p.left != null)
#	Line 1620 | Line 1909 | public class TreeMap<K,V>
1909		* Returns the last Entry in the TreeMap (according to the TreeMap's
1910		* key-sort function).  Returns null if the TreeMap is empty.
1911		*/
1912	<	private Entry<K,V> getLastEntry() {
1912	>	final Entry<K,V> getLastEntry() {
1913		Entry<K,V> p = root;
1914		if (p != null)
1915		while (p.right != null)
#	Line 1631 | Line 1920 | public class TreeMap<K,V>
1920		/**
1921		* Returns the successor of the specified Entry, or null if no such.
1922		*/
1923	<	private Entry<K,V> successor(Entry<K,V> t) {
1923	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1924		if (t == null)
1925		return null;
1926		else if (t.right != null) {
#	Line 1653 | Line 1942 | public class TreeMap<K,V>
1942		/**
1943		* Returns the predecessor of the specified Entry, or null if no such.
1944		*/
1945	<	private Entry<K,V> predecessor(Entry<K,V> t) {
1945	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1946		if (t == null)
1947		return null;
1948		else if (t.left != null) {
#	Line 1703 | Line 1992 | public class TreeMap<K,V>
1992		return (p == null) ? null: p.right;
1993		}
1994
1995	<	/** From CLR **/
1995	>	/** From CLR */
1996		private void rotateLeft(Entry<K,V> p) {
1997	<	Entry<K,V> r = p.right;
1998	<	p.right = r.left;
1999	<	if (r.left != null)
2000	<	r.left.parent = p;
2001	<	r.parent = p.parent;
2002	<	if (p.parent == null)
2003	<	root = r;
2004	<	else if (p.parent.left == p)
2005	<	p.parent.left = r;
2006	<	else
2007	<	p.parent.right = r;
2008	<	r.left = p;
2009	<	p.parent = r;
1997	>	if (p != null) {
1998	>	Entry<K,V> r = p.right;
1999	>	p.right = r.left;
2000	>	if (r.left != null)
2001	>	r.left.parent = p;
2002	>	r.parent = p.parent;
2003	>	if (p.parent == null)
2004	>	root = r;
2005	>	else if (p.parent.left == p)
2006	>	p.parent.left = r;
2007	>	else
2008	>	p.parent.right = r;
2009	>	r.left = p;
2010	>	p.parent = r;
2011	>	}
2012		}
2013
2014	<	/** From CLR **/
2014	>	/** From CLR */
2015		private void rotateRight(Entry<K,V> p) {
2016	<	Entry<K,V> l = p.left;
2017	<	p.left = l.right;
2018	<	if (l.right != null) l.right.parent = p;
2019	<	l.parent = p.parent;
2020	<	if (p.parent == null)
2021	<	root = l;
2022	<	else if (p.parent.right == p)
2023	<	p.parent.right = l;
2024	<	else p.parent.left = l;
2025	<	l.right = p;
2026	<	p.parent = l;
2016	>	if (p != null) {
2017	>	Entry<K,V> l = p.left;
2018	>	p.left = l.right;
2019	>	if (l.right != null) l.right.parent = p;
2020	>	l.parent = p.parent;
2021	>	if (p.parent == null)
2022	>	root = l;
2023	>	else if (p.parent.right == p)
2024	>	p.parent.right = l;
2025	>	else p.parent.left = l;
2026	>	l.right = p;
2027	>	p.parent = l;
2028	>	}
2029		}
2030
2031	<
1739	<	/** From CLR **/
2031	>	/** From CLR */
2032		private void fixAfterInsertion(Entry<K,V> x) {
2033		x.color = RED;
2034
#	Line 1755 | Line 2047 | public class TreeMap<K,V>
2047		}
2048		setColor(parentOf(x), BLACK);
2049		setColor(parentOf(parentOf(x)), RED);
2050	<	if (parentOf(parentOf(x)) != null)
1759	<	rotateRight(parentOf(parentOf(x)));
2050	>	rotateRight(parentOf(parentOf(x)));
2051		}
2052		} else {
2053		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 1770 | Line 2061 | public class TreeMap<K,V>
2061		x = parentOf(x);
2062		rotateRight(x);
2063		}
2064	<	setColor(parentOf(x),  BLACK);
2064	>	setColor(parentOf(x), BLACK);
2065		setColor(parentOf(parentOf(x)), RED);
2066	<	if (parentOf(parentOf(x)) != null)
1776	<	rotateLeft(parentOf(parentOf(x)));
2066	>	rotateLeft(parentOf(parentOf(x)));
2067		}
2068		}
2069		}
#	Line 1783 | Line 2073 | public class TreeMap<K,V>
2073		/**
2074		* Delete node p, and then rebalance the tree.
2075		*/
1786	–
2076		private void deleteEntry(Entry<K,V> p) {
2077	<	decrementSize();
2077	>	modCount++;
2078	>	size--;
2079
2080		// If strictly internal, copy successor's element to p and then make p
2081		// point to successor.
#	Line 1831 | Line 2121 | public class TreeMap<K,V>
2121		}
2122		}
2123
2124	<	/** From CLR **/
2124	>	/** From CLR */
2125		private void fixAfterDeletion(Entry<K,V> x) {
2126		while (x != root && colorOf(x) == BLACK) {
2127		if (x == leftOf(parentOf(x))) {
#	Line 1846 | Line 2136 | public class TreeMap<K,V>
2136
2137		if (colorOf(leftOf(sib))  == BLACK &&
2138		colorOf(rightOf(sib)) == BLACK) {
2139	<	setColor(sib,  RED);
2139	>	setColor(sib, RED);
2140		x = parentOf(x);
2141		} else {
2142		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 1873 | Line 2163 | public class TreeMap<K,V>
2163
2164		if (colorOf(rightOf(sib)) == BLACK &&
2165		colorOf(leftOf(sib)) == BLACK) {
2166	<	setColor(sib,  RED);
2166	>	setColor(sib, RED);
2167		x = parentOf(x);
2168		} else {
2169		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 1924 | Line 2214 | public class TreeMap<K,V>
2214		}
2215		}
2216
1927	–
1928	–
2217		/**
2218		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2219		* deserialize it).
#	Line 1941 | Line 2229 | public class TreeMap<K,V>
2229		buildFromSorted(size, null, s, null);
2230		}
2231
2232	<	/** Intended to be called only from TreeSet.readObject **/
2232	>	/** Intended to be called only from TreeSet.readObject */
2233		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2234		throws java.io.IOException, ClassNotFoundException {
2235		buildFromSorted(size, null, s, defaultVal);
2236		}
2237
2238	<	/** Intended to be called only from TreeSet.addAll **/
2238	>	/** Intended to be called only from TreeSet.addAll */
2239		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2240		try {
2241		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
#	Line 1987 | Line 2275 | public class TreeMap<K,V>
2275		* @throws ClassNotFoundException propagated from readObject.
2276		*         This cannot occur if str is null.
2277		*/
2278	<	private
2279	<	void buildFromSorted(int size, Iterator it,
2280	<	java.io.ObjectInputStream str,
1993	<	V defaultVal)
2278	>	private void buildFromSorted(int size, Iterator it,
2279	>	java.io.ObjectInputStream str,
2280	>	V defaultVal)
2281		throws  java.io.IOException, ClassNotFoundException {
2282		this.size = size;
2283	<	root =
2284	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
1998	<	it, str, defaultVal);
2283	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2284	>	it, str, defaultVal);
2285		}
2286
2287		/**
2288		* Recursive "helper method" that does the real work of the
2289	<	* of the previous method.  Identically named parameters have
2289	>	* previous method.  Identically named parameters have
2290		* identical definitions.  Additional parameters are documented below.
2291		* It is assumed that the comparator and size fields of the TreeMap are
2292		* already set prior to calling this method.  (It ignores both fields.)

Diff Legend

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