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.28 by dl, Wed Apr 19 15:07:14 2006 UTC vs.
Revision 1.42 by jsr166, Tue Jan 30 03:54:29 2007 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
#	Line 68 | Line 68 | package java.util;
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 95 | 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 110 | Line 110 | public class TreeMap<K,V>
110		private transient int modCount = 0;
111
112		/**
113	–	* A sentinel to indicate that an endpoint of a submap is not bounded.
114	–	* It is used to generate head maps, tail maps, and descending views
115	–	* of the entire backing map. The sentinel must be serializable,
116	–	* requiring a little class to express.
117	–	*/
118	–	private static class Unbounded implements java.io.Serializable {}
119	–	private static final Unbounded UNBOUNDED = new Unbounded();
120	–
121	–	private void incrementSize()   { modCount++; size++; }
122	–	private void decrementSize()   { modCount++; size--; }
123	–
124	–	/**
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
115		* Comparable} interface.  Furthermore, all such keys must be
#	Line 134 | Line 122 | public class TreeMap<K,V>
122		* <tt>ClassCastException</tt>.
123		*/
124		public TreeMap() {
125	+	comparator = null;
126		}
127
128		/**
#	Line 169 | 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 233 | 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	<	}
240	<
241	<	private boolean valueSearchNull(Entry n) {
242	<	if (n.value == null)
243	<	return true;
244	<
245	<	// Check left and right subtrees for value
246	<	return (n.left  != null && valueSearchNull(n.left)) ||
247	<	(n.right != null && valueSearchNull(n.right));
248	<	}
249	<
250	<	private boolean valueSearchNonNull(Entry n, Object value) {
251	<	// Check this node for the value
252	<	if (value.equals(n.value))
253	<	return true;
254	<
255	<	// Check left and right subtrees for value
256	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
257	<	(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		/**
#	Line 344 | 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);
#	Line 370 | 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 392 | 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)
398	<	return null;
399	<
400	<	while (true) {
371	>	while (p != null) {
372		int cmp = compare(key, p.key);
373		if (cmp < 0) {
374		if (p.left != null)
#	Line 419 | Line 390 | public class TreeMap<K,V>
390		} else
391		return p;
392		}
393	+	return null;
394		}
395
396		/**
#	Line 426 | 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)
432	<	return null;
433	<
434	<	while (true) {
403	>	while (p != null) {
404		int cmp = compare(key, p.key);
405		if (cmp > 0) {
406		if (p.right != null)
#	Line 454 | Line 423 | public class TreeMap<K,V>
423		return p;
424
425		}
426	+	return null;
427		}
428
429		/**
#	Line 462 | 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)
468	<	return null;
469	<
470	<	while (true) {
437	>	while (p != null) {
438		int cmp = compare(key, p.key);
439		if (cmp < 0) {
440		if (p.left != null)
#	Line 488 | Line 455 | public class TreeMap<K,V>
455		}
456		}
457		}
458	+	return null;
459		}
460
461		/**
#	Line 495 | 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)
501	<	return null;
502	<
503	<	while (true) {
468	>	while (p != null) {
469		int cmp = compare(key, p.key);
470		if (cmp > 0) {
471		if (p.right != null)
#	Line 521 | Line 486 | public class TreeMap<K,V>
486		}
487		}
488		}
489	<	}
525	<
526	<	/**
527	<	* Returns the key corresponding to the specified Entry.
528	<	* @throws NoSuchElementException if the Entry is null
529	<	*/
530	<	private static <K> K key(Entry<K,?> e) {
531	<	if (e==null)
532	<	throw new NoSuchElementException();
533	<	return e.key;
489	>	return null;
490		}
491
492		/**
#	Line 553 | Line 509 | public class TreeMap<K,V>
509		*/
510		public V put(K key, V value) {
511		Entry<K,V> t = root;
556	–
512		if (t == null) {
513	<	// TBD
514	<	//             if (key == null) {
515	<	//                 if (comparator == null)
516	<	//                     throw new NullPointerException();
517	<	//                 comparator.compare(key, key);
563	<	//             }
564	<	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 {
577	<	incrementSize();
578	<	t.left = new Entry<K,V>(key, value, t);
579	<	fixAfterInsertion(t.left);
580	<	return null;
581	<	}
582	<	} else { // cmp > 0
583	<	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);
588	<	fixAfterInsertion(t.right);
589	<	return null;
590	<	}
591	<	}
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 664 | Line 634 | public class TreeMap<K,V>
634		* @since 1.6
635		*/
636		public Map.Entry<K,V> firstEntry() {
637	<	Entry<K,V> e = getFirstEntry();
668	<	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();
676	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
644	>	return exportEntry(getLastEntry());
645		}
646
647		/**
#	Line 681 | Line 649 | public class TreeMap<K,V>
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);
687	<	deleteEntry(p);
652	>	Map.Entry<K,V> result = exportEntry(p);
653	>	if (p != null)
654	>	deleteEntry(p);
655		return result;
656		}
657
#	Line 693 | Line 660 | public class TreeMap<K,V>
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);
699	<	deleteEntry(p);
663	>	Map.Entry<K,V> result = exportEntry(p);
664	>	if (p != null)
665	>	deleteEntry(p);
666		return result;
667		}
668
#	Line 708 | Line 674 | public class TreeMap<K,V>
674		* @since 1.6
675		*/
676		public Map.Entry<K,V> lowerEntry(K key) {
677	<	Entry<K,V> e =  getLowerEntry(key);
712	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
677	>	return exportEntry(getLowerEntry(key));
678		}
679
680		/**
#	Line 720 | Line 685 | public class TreeMap<K,V>
685		* @since 1.6
686		*/
687		public K lowerKey(K key) {
688	<	Entry<K,V> e =  getLowerEntry(key);
724	<	return (e == null)? null : e.key;
688	>	return keyOrNull(getLowerEntry(key));
689		}
690
691		/**
#	Line 732 | Line 696 | public class TreeMap<K,V>
696		* @since 1.6
697		*/
698		public Map.Entry<K,V> floorEntry(K key) {
699	<	Entry<K,V> e = getFloorEntry(key);
736	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
699	>	return exportEntry(getFloorEntry(key));
700		}
701
702		/**
#	Line 744 | Line 707 | public class TreeMap<K,V>
707		* @since 1.6
708		*/
709		public K floorKey(K key) {
710	<	Entry<K,V> e = getFloorEntry(key);
748	<	return (e == null)? null : e.key;
710	>	return keyOrNull(getFloorEntry(key));
711		}
712
713		/**
#	Line 756 | Line 718 | public class TreeMap<K,V>
718		* @since 1.6
719		*/
720		public Map.Entry<K,V> ceilingEntry(K key) {
721	<	Entry<K,V> e = getCeilingEntry(key);
760	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
721	>	return exportEntry(getCeilingEntry(key));
722		}
723
724		/**
#	Line 768 | Line 729 | public class TreeMap<K,V>
729		* @since 1.6
730		*/
731		public K ceilingKey(K key) {
732	<	Entry<K,V> e = getCeilingEntry(key);
772	<	return (e == null)? null : e.key;
732	>	return keyOrNull(getCeilingEntry(key));
733		}
734
735		/**
#	Line 780 | Line 740 | public class TreeMap<K,V>
740		* @since 1.6
741		*/
742		public Map.Entry<K,V> higherEntry(K key) {
743	<	Entry<K,V> e = getHigherEntry(key);
784	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
743	>	return exportEntry(getHigherEntry(key));
744		}
745
746		/**
#	Line 792 | Line 751 | public class TreeMap<K,V>
751		* @since 1.6
752		*/
753		public K higherKey(K key) {
754	<	Entry<K,V> e = getHigherEntry(key);
796	<	return (e == null)? null : e.key;
754	>	return keyOrNull(getHigherEntry(key));
755		}
756
757		// Views
#	Line 803 | 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;
764	>	private transient EntrySet entrySet = null;
765		private transient KeySet<K> navigableKeySet = null;
766		private transient NavigableMap<K,V> descendingMap = null;
767
#	Line 829 | Line 787 | public class TreeMap<K,V>
787		* @since 1.6
788		*/
789		public NavigableSet<K> navigableKeySet() {
790	<	NavigableSet<K> nks = navigableKeySet;
790	>	KeySet<K> nks = navigableKeySet;
791		return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
792		}
793
#	Line 876 | Line 834 | public class TreeMap<K,V>
834		* <tt>add</tt> or <tt>addAll</tt> operations.
835		*/
836		public Set<Map.Entry<K,V>> entrySet() {
837	<	Set<Map.Entry<K,V>> es = entrySet;
837	>	EntrySet es = entrySet;
838		return (es != null) ? es : (entrySet = new EntrySet());
839		}
840
#	Line 886 | Line 844 | public class TreeMap<K,V>
844		public NavigableMap<K, V> descendingMap() {
845		NavigableMap<K, V> km = descendingMap;
846		return (km != null) ? km :
847	<	(descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
848	<	(K)UNBOUNDED, 0));
847	>	(descendingMap = new DescendingSubMap(this,
848	>	true, null, true,
849	>	true, null, true));
850		}
851
852		/**
#	Line 898 | Line 857 | public class TreeMap<K,V>
857		* @throws IllegalArgumentException {@inheritDoc}
858		* @since 1.6
859		*/
860	<	public NavigableMap<K,V> navigableSubMap(K fromKey, boolean fromInclusive,
861	<	K toKey,   boolean toInclusive) {
862	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
863	<	toKey,   excluded(toInclusive));
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		/**
#	Line 912 | Line 872 | public class TreeMap<K,V>
872		* @throws IllegalArgumentException {@inheritDoc}
873		* @since 1.6
874		*/
875	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
876	<	return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
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		/**
#	Line 924 | Line 886 | public class TreeMap<K,V>
886		* @throws IllegalArgumentException {@inheritDoc}
887		* @since 1.6
888		*/
889	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive) {
890	<	return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 0);
891	<	}
892	<
931	<	/**
932	<	* Translates a boolean "inclusive" value to the correct int value
933	<	* for the loExcluded or hiExcluded field.
934	<	*/
935	<	static int excluded(boolean inclusive) {
936	<	return inclusive ? 0 : 1;
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		/**
#	Line 944 | Line 900 | public class TreeMap<K,V>
900		* @throws IllegalArgumentException {@inheritDoc}
901		*/
902		public SortedMap<K,V> subMap(K fromKey, K toKey) {
903	<	return navigableSubMap(fromKey, true, toKey, false);
903	>	return subMap(fromKey, true, toKey, false);
904		}
905
906		/**
#	Line 955 | Line 911 | public class TreeMap<K,V>
911		* @throws IllegalArgumentException {@inheritDoc}
912		*/
913		public SortedMap<K,V> headMap(K toKey) {
914	<	return navigableHeadMap(toKey, false);
914	>	return headMap(toKey, false);
915		}
916
917		/**
#	Line 966 | Line 922 | public class TreeMap<K,V>
922		* @throws IllegalArgumentException {@inheritDoc}
923		*/
924		public SortedMap<K,V> tailMap(K fromKey) {
925	<	return navigableTailMap(fromKey, true);
925	>	return tailMap(fromKey, true);
926		}
927
928		// View class support
#	Line 981 | 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))
985	<	if (valEquals(e.getValue(), o))
986	<	return true;
987	<	return false;
940	>	return TreeMap.this.containsValue(o);
941		}
942
943		public boolean remove(Object o) {
#	Line 1096 | Line 1049 | public class TreeMap<K,V>
1049		m.remove(o);
1050		return size() != oldSize;
1051		}
1052	<	public NavigableSet<E> navigableSubSet(E fromElement,
1053	<	boolean fromInclusive,
1054	<	E toElement,
1055	<	boolean toInclusive) {
1103	<	return new TreeSet<E>
1104	<	(m.navigableSubMap(fromElement, fromInclusive,
1105	<	toElement,   toInclusive));
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> navigableHeadSet(E toElement, boolean inclusive) {
1058	<	return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
1057	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1058	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1059		}
1060	<	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
1061	<	return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
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 navigableSubSet(fromElement, true, toElement, false);
1064	>	return subSet(fromElement, true, toElement, false);
1065		}
1066		public SortedSet<E> headSet(E toElement) {
1067	<	return navigableHeadSet(toElement, false);
1067	>	return headSet(toElement, false);
1068		}
1069		public SortedSet<E> tailSet(E fromElement) {
1070	<	return navigableTailSet(fromElement, true);
1070	>	return tailSet(fromElement, true);
1071		}
1072		public NavigableSet<E> descendingSet() {
1073		return new TreeSet(m.descendingMap());
1074		}
1075		}
1076
1077	<	// SubMaps
1078	<
1079	<	abstract class NavigableSubMap extends AbstractMap<K,V>
1080	<	implements NavigableMap<K,V>, java.io.Serializable {
1081	<
1082	<	/**
1083	<	* The low endpoint of this submap in absolute terms.  For ascending
1134	<	* submaps this will be the "first" endpoint; for descending submaps,
1135	<	* the last.  If there is no bound, this field is set to UNBOUNDED.
1136	<	*/
1137	<	K lo;
1138	<
1139	<	/**
1140	<	* Zero if the low endpoint is excluded from this submap, one if
1141	<	* it's included.  This field is unused if lo is UNBOUNDED.
1142	<	*/
1143	<	int loExcluded;
1144	<
1145	<	/**
1146	<	* The high endpoint of this submap in absolute terms.  For ascending
1147	<	* submaps this will be the "last" endpoint; for descending submaps,
1148	<	* the first.  If there is no bound, this field is set to UNBOUNDED.
1149	<	*/
1150	<	K hi;
1151	<
1152	<	/**
1153	<	* Zero if the high endpoint is excluded from this submap, one if
1154	<	* it's included.  This field is unused if hi is UNBOUNDED.
1155	<	*/
1156	<	int hiExcluded;
1077	>	/**
1078	>	* Base class for TreeMap Iterators
1079	>	*/
1080	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1081	>	Entry<K,V> next;
1082	>	Entry<K,V> lastReturned;
1083	>	int expectedModCount;
1084
1085	<	NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1086	<	if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
1087	<	throw new IllegalArgumentException("fromKey > toKey");
1088	<	this.lo = lo;
1162	<	this.loExcluded = loExcluded;
1163	<	this.hi = hi;
1164	<	this.hiExcluded = hiExcluded;
1085	>	PrivateEntryIterator(Entry<K,V> first) {
1086	>	expectedModCount = modCount;
1087	>	lastReturned = null;
1088	>	next = first;
1089		}
1090
1091	<	public boolean isEmpty() {
1092	<	return entrySet().isEmpty();
1091	>	public final boolean hasNext() {
1092	>	return next != null;
1093		}
1094
1095	<	public boolean containsKey(Object key) {
1096	<	return inRange(key) && TreeMap.this.containsKey(key);
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	<	public V get(Object key) {
1106	<	if (!inRange(key))
1107	<	return null;
1108	<	return TreeMap.this.get(key);
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 V put(K key, V value) {
1116	<	if (!inRange(key))
1117	<	throw new IllegalArgumentException("key out of range");
1118	<	return TreeMap.this.put(key, value);
1115	>	public void remove() {
1116	>	if (lastReturned == null)
1117	>	throw new IllegalStateException();
1118	>	if (modCount != expectedModCount)
1119	>	throw new ConcurrentModificationException();
1120	>	// deleted entries are replaced by their successors
1121	>	if (lastReturned.left != null && lastReturned.right != null)
1122	>	next = lastReturned;
1123	>	deleteEntry(lastReturned);
1124	>	expectedModCount = modCount;
1125	>	lastReturned = null;
1126		}
1127	+	}
1128
1129	<	public V remove(Object key) {
1130	<	if (!inRange(key))
1131	<	return null;
1190	<	return TreeMap.this.remove(key);
1129	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1130	>	EntryIterator(Entry<K,V> first) {
1131	>	super(first);
1132		}
1133	<
1134	<	public Map.Entry<K,V> ceilingEntry(K key) {
1194	<	TreeMap.Entry<K,V> e = subCeiling(key);
1195	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1133	>	public Map.Entry<K,V> next() {
1134	>	return nextEntry();
1135		}
1136	+	}
1137
1138	<	public K ceilingKey(K key) {
1139	<	TreeMap.Entry<K,V> e = subCeiling(key);
1140	<	return e == null? null : e.key;
1138	>	final class ValueIterator extends PrivateEntryIterator<V> {
1139	>	ValueIterator(Entry<K,V> first) {
1140	>	super(first);
1141		}
1142	<
1143	<	public Map.Entry<K,V> higherEntry(K key) {
1204	<	TreeMap.Entry<K,V> e = subHigher(key);
1205	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1142	>	public V next() {
1143	>	return nextEntry().value;
1144		}
1145	+	}
1146
1147	<	public K higherKey(K key) {
1148	<	TreeMap.Entry<K,V> e = subHigher(key);
1149	<	return e == null? null : e.key;
1147	>	final class KeyIterator extends PrivateEntryIterator<K> {
1148	>	KeyIterator(Entry<K,V> first) {
1149	>	super(first);
1150		}
1151	<
1152	<	public Map.Entry<K,V> floorEntry(K key) {
1214	<	TreeMap.Entry<K,V> e = subFloor(key);
1215	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1151	>	public K next() {
1152	>	return nextEntry().key;
1153		}
1154	+	}
1155
1156	<	public K floorKey(K key) {
1157	<	TreeMap.Entry<K,V> e = subFloor(key);
1158	<	return e == null? null : e.key;
1156	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1157	>	DescendingKeyIterator(Entry<K,V> first) {
1158	>	super(first);
1159		}
1160	<
1161	<	public Map.Entry<K,V> lowerEntry(K key) {
1224	<	TreeMap.Entry<K,V> e = subLower(key);
1225	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1160	>	public K next() {
1161	>	return prevEntry().key;
1162		}
1163	+	}
1164
1165	<	public K lowerKey(K key) {
1229	<	TreeMap.Entry<K,V> e = subLower(key);
1230	<	return e == null? null : e.key;
1231	<	}
1165	>	// Little utilities
1166
1167	<	abstract Iterator<K> keyIterator();
1168	<	abstract Iterator<K> descendingKeyIterator();
1167	>	/**
1168	>	* Compares two keys using the correct comparison method for this TreeMap.
1169	>	*/
1170	>	final int compare(Object k1, Object k2) {
1171	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1172	>	: comparator.compare((K)k1, (K)k2);
1173	>	}
1174
1175	<	public NavigableSet<K> descendingKeySet() {
1176	<	return descendingMap().navigableKeySet();
1177	<	}
1175	>	/**
1176	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1177	>	* that it copes with <tt>null</tt> o1 properly.
1178	>	*/
1179	>	final static boolean valEquals(Object o1, Object o2) {
1180	>	return (o1==null ? o2==null : o1.equals(o2));
1181	>	}
1182
1183	<	// Views
1184	<	transient NavigableMap<K,V> descendingMapView = null;
1185	<	transient Set<Map.Entry<K,V>> entrySetView = null;
1186	<	private transient NavigableSet<K> navigableKeySetView = null;
1183	>	/**
1184	>	* Return SimpleImmutableEntry for entry, or null if null
1185	>	*/
1186	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1187	>	return e == null? null :
1188	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1189	>	}
1190
1191	<	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1192	<	private transient int size = -1, sizeModCount;
1191	>	/**
1192	>	* Return key for entry, or null if null
1193	>	*/
1194	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1195	>	return e == null? null : e.key;
1196	>	}
1197
1198	<	public int size() {
1199	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1200	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1201	<	Iterator i = iterator();
1202	<	while (i.hasNext()) {
1203	<	size++;
1204	<	i.next();
1205	<	}
1206	<	}
1257	<	return size;
1258	<	}
1198	>	/**
1199	>	* Returns the key corresponding to the specified Entry.
1200	>	* @throws NoSuchElementException if the Entry is null
1201	>	*/
1202	>	static <K> K key(Entry<K,?> e) {
1203	>	if (e==null)
1204	>	throw new NoSuchElementException();
1205	>	return e.key;
1206	>	}
1207
1260	–	public boolean isEmpty() {
1261	–	return !iterator().hasNext();
1262	–	}
1208
1209	<	public boolean contains(Object o) {
1265	<	if (!(o instanceof Map.Entry))
1266	<	return false;
1267	<	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1268	<	K key = entry.getKey();
1269	<	if (!inRange(key))
1270	<	return false;
1271	<	TreeMap.Entry node = getEntry(key);
1272	<	return node != null &&
1273	<	valEquals(node.getValue(), entry.getValue());
1274	<	}
1209	>	// SubMaps
1210
1211	<	public boolean remove(Object o) {
1212	<	if (!(o instanceof Map.Entry))
1213	<	return false;
1214	<	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1215	<	K key = entry.getKey();
1216	<	if (!inRange(key))
1217	<	return false;
1218	<	TreeMap.Entry<K,V> node = getEntry(key);
1219	<	if (node!=null && valEquals(node.getValue(),entry.getValue())){
1220	<	deleteEntry(node);
1221	<	return true;
1222	<	}
1223	<	return false;
1211	>	/**
1212	>	* Dummy value serving as unmatchable fence key for unbounded
1213	>	* SubMapIterators
1214	>	*/
1215	>	private static final Object UNBOUNDED = new Object();
1216	>
1217	>	/**
1218	>	* @serial include
1219	>	*/
1220	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1221	>	implements NavigableMap<K,V>, java.io.Serializable {
1222	>	/**
1223	>	* The backing map.
1224	>	*/
1225	>	final TreeMap<K,V> m;
1226	>
1227	>	/**
1228	>	* Endpoints are represented as triples (fromStart, lo,
1229	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1230	>	* true, then the low (absolute) bound is the start of the
1231	>	* backing map, and the other values are ignored. Otherwise,
1232	>	* if loInclusive is true, lo is the inclusive bound, else lo
1233	>	* is the exclusive bound. Similarly for the upper bound.
1234	>	*/
1235	>	final K lo, hi;
1236	>	final boolean fromStart, toEnd;
1237	>	final boolean loInclusive, hiInclusive;
1238	>
1239	>	NavigableSubMap(TreeMap<K,V> m,
1240	>	boolean fromStart, K lo, boolean loInclusive,
1241	>	boolean toEnd,     K hi, boolean hiInclusive) {
1242	>	if (!fromStart && !toEnd) {
1243	>	if (m.compare(lo, hi) > 0)
1244	>	throw new IllegalArgumentException("fromKey > toKey");
1245	>	} else {
1246	>	if (!fromStart) // type check
1247	>	m.compare(lo, lo);
1248	>	if (!toEnd)
1249	>	m.compare(hi, hi);
1250		}
1290	–	}
1251
1252	<	public NavigableSet<K> navigableKeySet() {
1253	<	NavigableSet<K> nksv = navigableKeySetView;
1254	<	return (nksv != null) ? nksv :
1255	<	(navigableKeySetView = new TreeMap.KeySet(this));
1252	>	this.m = m;
1253	>	this.fromStart = fromStart;
1254	>	this.lo = lo;
1255	>	this.loInclusive = loInclusive;
1256	>	this.toEnd = toEnd;
1257	>	this.hi = hi;
1258	>	this.hiInclusive = hiInclusive;
1259		}
1260
1261	<	public Set<K> keySet() {
1299	<	return navigableKeySet();
1300	<	}
1261	>	// internal utilities
1262
1263	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1264	<	return navigableSubMap(fromKey, true, toKey, false);
1263	>	final boolean tooLow(Object key) {
1264	>	if (!fromStart) {
1265	>	int c = m.compare(key, lo);
1266	>	if (c < 0 || (c == 0 && !loInclusive))
1267	>	return true;
1268	>	}
1269	>	return false;
1270		}
1271
1272	<	public SortedMap<K,V> headMap(K toKey) {
1273	<	return navigableHeadMap(toKey, false);
1272	>	final boolean tooHigh(Object key) {
1273	>	if (!toEnd) {
1274	>	int c = m.compare(key, hi);
1275	>	if (c > 0 || (c == 0 && !hiInclusive))
1276	>	return true;
1277	>	}
1278	>	return false;
1279		}
1280
1281	<	public SortedMap<K,V> tailMap(K fromKey) {
1282	<	return navigableTailMap(fromKey, true);
1281	>	final boolean inRange(Object key) {
1282	>	return !tooLow(key) && !tooHigh(key);
1283		}
1284
1285	<	/** Returns the lowest entry in this submap (absolute ordering) */
1286	<	TreeMap.Entry<K,V> loEntry() {
1287	<	TreeMap.Entry<K,V> result =
1317	<	((lo == UNBOUNDED) ? getFirstEntry() :
1318	<	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1319	<	return (result == null || tooHigh(result.key)) ? null : result;
1285	>	final boolean inClosedRange(Object key) {
1286	>	return (fromStart || m.compare(key, lo) >= 0)
1287	>	&& (toEnd || m.compare(hi, key) >= 0);
1288		}
1289
1290	<	/** Returns the highest key in this submap (absolute ordering) */
1291	<	TreeMap.Entry<K,V> hiEntry() {
1324	<	TreeMap.Entry<K,V> result =
1325	<	((hi == UNBOUNDED) ? getLastEntry() :
1326	<	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1327	<	return (result == null || tooLow(result.key)) ? null : result;
1290	>	final boolean inRange(Object key, boolean inclusive) {
1291	>	return inclusive ? inRange(key) : inClosedRange(key);
1292		}
1293
1294	<	/** Polls the lowest entry in this submap (absolute ordering) */
1295	<	Map.Entry<K,V> pollLoEntry() {
1294	>	/*
1295	>	* Absolute versions of relation operations.
1296	>	* Subclasses map to these using like-named "sub"
1297	>	* versions that invert senses for descending maps
1298	>	*/
1299	>
1300	>	final TreeMap.Entry<K,V> absLowest() {
1301		TreeMap.Entry<K,V> e =
1302	<	((lo == UNBOUNDED) ? getFirstEntry() :
1303	<	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1304	<	if (e == null || tooHigh(e.key))
1305	<	return null;
1337	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1338	<	deleteEntry(e);
1339	<	return result;
1302	>	(fromStart ?  m.getFirstEntry() :
1303	>	(loInclusive ? m.getCeilingEntry(lo) :
1304	>	m.getHigherEntry(lo)));
1305	>	return (e == null || tooHigh(e.key)) ? null : e;
1306		}
1307
1308	<	/** Polls the highest key in this submap (absolute ordering) */
1343	<	Map.Entry<K,V> pollHiEntry() {
1308	>	final TreeMap.Entry<K,V> absHighest() {
1309		TreeMap.Entry<K,V> e =
1310	<	((hi == UNBOUNDED) ? getLastEntry() :
1311	<	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1312	<	if (e == null || tooLow(e.key))
1313	<	return null;
1349	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1350	<	deleteEntry(e);
1351	<	return result;
1310	>	(toEnd ?  m.getLastEntry() :
1311	>	(hiInclusive ?  m.getFloorEntry(hi) :
1312	>	m.getLowerEntry(hi)));
1313	>	return (e == null || tooLow(e.key)) ? null : e;
1314		}
1315
1316	<	// The following four definitions are correct only for
1355	<	// ascending submaps. They are overridden in DescendingSubMap.
1356	<	// They are defined in the base class because the definitions
1357	<	// in DescendingSubMap rely on those for AscendingSubMap.
1358	<
1359	<	/**
1360	<	* Returns the entry corresponding to the ceiling of the specified
1361	<	* key from the perspective of this submap, or null if the submap
1362	<	* contains no such entry.
1363	<	*/
1364	<	TreeMap.Entry<K,V> subCeiling(K key) {
1316	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1317		if (tooLow(key))
1318	<	return loEntry();
1319	<	TreeMap.Entry<K,V> e = getCeilingEntry(key);
1318	>	return absLowest();
1319	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1320		return (e == null || tooHigh(e.key)) ? null : e;
1321		}
1322
1323	<	/**
1372	<	* Returns the entry corresponding to the higher of the specified
1373	<	* key from the perspective of this submap, or null if the submap
1374	<	* contains no such entry.
1375	<	*/
1376	<	TreeMap.Entry<K,V> subHigher(K key) {
1323	>	final TreeMap.Entry<K,V> absHigher(K key) {
1324		if (tooLow(key))
1325	<	return loEntry();
1326	<	TreeMap.Entry<K,V> e = getHigherEntry(key);
1325	>	return absLowest();
1326	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1327		return (e == null || tooHigh(e.key)) ? null : e;
1328		}
1329
1330	<	/**
1384	<	* Returns the entry corresponding to the floor of the specified
1385	<	* key from the perspective of this submap, or null if the submap
1386	<	* contains no such entry.
1387	<	*/
1388	<	TreeMap.Entry<K,V> subFloor(K key) {
1330	>	final TreeMap.Entry<K,V> absFloor(K key) {
1331		if (tooHigh(key))
1332	<	return hiEntry();
1333	<	TreeMap.Entry<K,V> e = getFloorEntry(key);
1332	>	return absHighest();
1333	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1334		return (e == null || tooLow(e.key)) ? null : e;
1335		}
1336
1337	<	/**
1396	<	* Returns the entry corresponding to the lower of the specified
1397	<	* key from the perspective of this submap, or null if the submap
1398	<	* contains no such entry.
1399	<	*/
1400	<	TreeMap.Entry<K,V> subLower(K key) {
1337	>	final TreeMap.Entry<K,V> absLower(K key) {
1338		if (tooHigh(key))
1339	<	return hiEntry();
1340	<	TreeMap.Entry<K,V> e = getLowerEntry(key);
1339	>	return absHighest();
1340	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1341		return (e == null || tooLow(e.key)) ? null : e;
1342		}
1343
1344	<	boolean inRange(Object key) {
1345	<	return (lo == UNBOUNDED || compare(key, lo) >= loExcluded)
1346	<	&& (hi == UNBOUNDED || compare(hi, key) >= hiExcluded);
1347	<	}
1344	>	/** Returns the absolute high fence for ascending traversal */
1345	>	final TreeMap.Entry<K,V> absHighFence() {
1346	>	return (toEnd ? null : (hiInclusive ?
1347	>	m.getHigherEntry(hi) :
1348	>	m.getCeilingEntry(hi)));
1349	>	}
1350	>
1351	>	/** Return the absolute low fence for descending traversal  */
1352	>	final TreeMap.Entry<K,V> absLowFence() {
1353	>	return (fromStart ? null : (loInclusive ?
1354	>	m.getLowerEntry(lo) :
1355	>	m.getFloorEntry(lo)));
1356	>	}
1357	>
1358	>	// Abstract methods defined in ascending vs descending classes
1359	>	// These relay to the appropriate absolute versions
1360	>
1361	>	abstract TreeMap.Entry<K,V> subLowest();
1362	>	abstract TreeMap.Entry<K,V> subHighest();
1363	>	abstract TreeMap.Entry<K,V> subCeiling(K key);
1364	>	abstract TreeMap.Entry<K,V> subHigher(K key);
1365	>	abstract TreeMap.Entry<K,V> subFloor(K key);
1366	>	abstract TreeMap.Entry<K,V> subLower(K key);
1367
1368	<	boolean inClosedRange(Object key) {
1369	<	return (lo == UNBOUNDED || compare(key, lo) >= 0)
1414	<	&& (hi == UNBOUNDED || compare(hi, key) >= 0);
1415	<	}
1368	>	/** Returns ascending iterator from the perspective of this submap */
1369	>	abstract Iterator<K> keyIterator();
1370
1371	<	boolean inRange(Object key, boolean inclusive) {
1372	<	return inclusive ? inRange(key) : inClosedRange(key);
1371	>	/** Returns descending iterator from the perspective of this submap */
1372	>	abstract Iterator<K> descendingKeyIterator();
1373	>
1374	>	// public methods
1375	>
1376	>	public boolean isEmpty() {
1377	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1378		}
1379
1380	<	boolean tooLow(K key) {
1381	<	return lo != UNBOUNDED && compare(key, lo) < loExcluded;
1380	>	public int size() {
1381	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1382		}
1383
1384	<	boolean tooHigh(K key) {
1385	<	return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
1384	>	public final boolean containsKey(Object key) {
1385	>	return inRange(key) && m.containsKey(key);
1386		}
1428	–	}
1387
1388	<	class AscendingSubMap extends NavigableSubMap {
1389	<	private static final long serialVersionUID = 912986545866124060L;
1388	>	public final V put(K key, V value) {
1389	>	if (!inRange(key))
1390	>	throw new IllegalArgumentException("key out of range");
1391	>	return m.put(key, value);
1392	>	}
1393
1394	<	AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1395	<	super(lo, loExcluded, hi, hiExcluded);
1394	>	public final V get(Object key) {
1395	>	return !inRange(key)? null :  m.get(key);
1396		}
1397
1398	<	public Comparator<? super K> comparator() {
1399	<	return comparator;
1398	>	public final V remove(Object key) {
1399	>	return !inRange(key)? null  : m.remove(key);
1400		}
1401
1402	<	public NavigableMap<K,V> navigableSubMap(
1403	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1443	<	if (!inRange(fromKey, fromInclusive))
1444	<	throw new IllegalArgumentException("fromKey out of range");
1445	<	if (!inRange(toKey, toInclusive))
1446	<	throw new IllegalArgumentException("toKey out of range");
1447	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
1448	<	toKey,   excluded(toInclusive));
1402	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1403	>	return exportEntry(subCeiling(key));
1404		}
1405
1406	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1407	<	if (!inClosedRange(toKey))
1453	<	throw new IllegalArgumentException("toKey out of range");
1454	<	return new AscendingSubMap(lo,    loExcluded,
1455	<	toKey, excluded(inclusive));
1406	>	public final K ceilingKey(K key) {
1407	>	return keyOrNull(subCeiling(key));
1408		}
1409
1410	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1411	<	if (!inRange(fromKey, inclusive))
1460	<	throw new IllegalArgumentException("fromKey out of range");
1461	<	return new AscendingSubMap(fromKey, excluded(inclusive),
1462	<	hi,      hiExcluded);
1410	>	public final Map.Entry<K,V> higherEntry(K key) {
1411	>	return exportEntry(subHigher(key));
1412		}
1413
1414	<	Iterator<K> keyIterator() {
1415	<	return new SubMapKeyIterator
1467	<	(loEntry(),
1468	<	hi == UNBOUNDED ? null :
1469	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1470	<	getHigherEntry(hi));
1414	>	public final K higherKey(K key) {
1415	>	return keyOrNull(subHigher(key));
1416		}
1417
1418	<	Iterator<K> descendingKeyIterator() {
1419	<	return new DescendingSubMapKeyIterator
1475	<	(hiEntry(),
1476	<	lo == UNBOUNDED ? null :
1477	<	loExcluded == 1 ? getFloorEntry(lo) :
1478	<	getLowerEntry(lo));
1418	>	public final Map.Entry<K,V> floorEntry(K key) {
1419	>	return exportEntry(subFloor(key));
1420		}
1421
1422	<	public Set<Map.Entry<K,V>> entrySet() {
1423	<	Set<Map.Entry<K,V>> es = entrySetView;
1483	<	if  (es != null)
1484	<	return es;
1485	<	return entrySetView = new NavigableSubMap.EntrySetView() {
1486	<	public Iterator<Map.Entry<K,V>> iterator() {
1487	<	return new SubMapEntryIterator(loEntry(),
1488	<	hi == UNBOUNDED ? null :
1489	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1490	<	getHigherEntry(hi));
1491	<	}
1492	<	};
1422	>	public final K floorKey(K key) {
1423	>	return keyOrNull(subFloor(key));
1424		}
1425
1426	<	public K firstKey() {
1427	<	return key(loEntry());
1426	>	public final Map.Entry<K,V> lowerEntry(K key) {
1427	>	return exportEntry(subLower(key));
1428		}
1429
1430	<	public K lastKey() {
1431	<	return key(hiEntry());
1430	>	public final K lowerKey(K key) {
1431	>	return keyOrNull(subLower(key));
1432		}
1433
1434	<	public Map.Entry<K,V> firstEntry() {
1435	<	return loEntry();
1434	>	public final K firstKey() {
1435	>	return key(subLowest());
1436		}
1437
1438	<	public Map.Entry<K,V> lastEntry() {
1439	<	return hiEntry();
1438	>	public final K lastKey() {
1439	>	return key(subHighest());
1440		}
1441
1442	<	public Map.Entry<K,V> pollFirstEntry() {
1443	<	return pollLoEntry();
1442	>	public final Map.Entry<K,V> firstEntry() {
1443	>	return exportEntry(subLowest());
1444		}
1445
1446	<	public Map.Entry<K,V> pollLastEntry() {
1447	<	return pollHiEntry();
1446	>	public final Map.Entry<K,V> lastEntry() {
1447	>	return exportEntry(subHighest());
1448		}
1449
1450	<	public NavigableMap<K,V> descendingMap() {
1451	<	NavigableMap<K,V> m = descendingMapView;
1452	<	return (m != null) ? m :
1453	<	(descendingMapView =
1454	<	new DescendingSubMap(lo, loExcluded, hi, hiExcluded));
1450	>	public final Map.Entry<K,V> pollFirstEntry() {
1451	>	TreeMap.Entry<K,V> e = subLowest();
1452	>	Map.Entry<K,V> result = exportEntry(e);
1453	>	if (e != null)
1454	>	m.deleteEntry(e);
1455	>	return result;
1456		}
1525	–	}
1457
1458	<	class DescendingSubMap extends NavigableSubMap {
1459	<	private static final long serialVersionUID = 912986545866120460L;
1460	<	DescendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1461	<	super(lo, loExcluded, hi, hiExcluded);
1458	>	public final Map.Entry<K,V> pollLastEntry() {
1459	>	TreeMap.Entry<K,V> e = subHighest();
1460	>	Map.Entry<K,V> result = exportEntry(e);
1461	>	if (e != null)
1462	>	m.deleteEntry(e);
1463	>	return result;
1464		}
1465
1466	<	private final Comparator<? super K> reverseComparator =
1467	<	Collections.reverseOrder(comparator);
1466	>	// Views
1467	>	transient NavigableMap<K,V> descendingMapView = null;
1468	>	transient EntrySetView entrySetView = null;
1469	>	transient KeySet<K> navigableKeySetView = null;
1470
1471	<	public Comparator<? super K> comparator() {
1472	<	return reverseComparator;
1471	>	public final NavigableSet<K> navigableKeySet() {
1472	>	KeySet<K> nksv = navigableKeySetView;
1473	>	return (nksv != null) ? nksv :
1474	>	(navigableKeySetView = new TreeMap.KeySet(this));
1475		}
1476
1477	<	public NavigableMap<K,V> navigableSubMap(
1478	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1542	<	if (!inRange(fromKey, fromInclusive))
1543	<	throw new IllegalArgumentException("fromKey out of range");
1544	<	if (!inRange(toKey, toInclusive))
1545	<	throw new IllegalArgumentException("toKey out of range");
1546	<	return new DescendingSubMap(toKey,   excluded(toInclusive),
1547	<	fromKey, excluded(fromInclusive));
1477	>	public final Set<K> keySet() {
1478	>	return navigableKeySet();
1479		}
1480
1481	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1482	<	if (!inRange(toKey, inclusive))
1552	<	throw new IllegalArgumentException("toKey out of range");
1553	<	return new DescendingSubMap(toKey, inclusive ? 0:1, hi, hiExcluded);
1481	>	public NavigableSet<K> descendingKeySet() {
1482	>	return descendingMap().navigableKeySet();
1483		}
1484
1485	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1486	<	if (!inRange(fromKey, inclusive))
1558	<	throw new IllegalArgumentException("fromKey out of range");
1559	<	return new DescendingSubMap(lo,      loExcluded,
1560	<	fromKey, excluded(inclusive));
1485	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1486	>	return subMap(fromKey, true, toKey, false);
1487		}
1488
1489	<	Iterator<K> keyIterator() {
1490	<	return new DescendingSubMapKeyIterator
1565	<	(hiEntry(),
1566	<	lo == UNBOUNDED ? null :
1567	<	loExcluded == 1 ? getFloorEntry(lo) :
1568	<	getLowerEntry(lo));
1489	>	public final SortedMap<K,V> headMap(K toKey) {
1490	>	return headMap(toKey, false);
1491		}
1492
1493	<	Iterator<K> descendingKeyIterator() {
1494	<	return new SubMapKeyIterator
1573	<	(loEntry(),
1574	<	hi == UNBOUNDED ? null :
1575	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1576	<	getHigherEntry(hi));
1493	>	public final SortedMap<K,V> tailMap(K fromKey) {
1494	>	return tailMap(fromKey, true);
1495		}
1496
1497	<	public Set<Map.Entry<K,V>> entrySet() {
1498	<	Set<Map.Entry<K,V>> es = entrySetView;
1499	<	if  (es != null)
1500	<	return es;
1501	<	return entrySetView = new NavigableSubMap.EntrySetView() {
1502	<	public Iterator<Map.Entry<K,V>> iterator() {
1503	<	return new DescendingSubMapEntryIterator(hiEntry(),
1504	<	lo == UNBOUNDED ? null :
1505	<	loExcluded == 1 ? getFloorEntry(lo) :
1506	<	getLowerEntry(lo));
1497	>	// View classes
1498	>
1499	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1500	>	private transient int size = -1, sizeModCount;
1501	>
1502	>	public int size() {
1503	>	if (fromStart && toEnd)
1504	>	return m.size();
1505	>	if (size == -1 || sizeModCount != m.modCount) {
1506	>	sizeModCount = m.modCount;
1507	>	size = 0;
1508	>	Iterator i = iterator();
1509	>	while (i.hasNext()) {
1510	>	size++;
1511	>	i.next();
1512	>	}
1513		}
1514	<	};
1515	<	}
1514	>	return size;
1515	>	}
1516
1517	<	public K firstKey() {
1518	<	return key(hiEntry());
1519	<	}
1517	>	public boolean isEmpty() {
1518	>	TreeMap.Entry<K,V> n = absLowest();
1519	>	return n == null || tooHigh(n.key);
1520	>	}
1521
1522	<	public K lastKey() {
1523	<	return key(loEntry());
1524	<	}
1522	>	public boolean contains(Object o) {
1523	>	if (!(o instanceof Map.Entry))
1524	>	return false;
1525	>	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1526	>	K key = entry.getKey();
1527	>	if (!inRange(key))
1528	>	return false;
1529	>	TreeMap.Entry node = m.getEntry(key);
1530	>	return node != null &&
1531	>	valEquals(node.getValue(), entry.getValue());
1532	>	}
1533
1534	<	public Map.Entry<K,V> firstEntry() {
1535	<	return hiEntry();
1534	>	public boolean remove(Object o) {
1535	>	if (!(o instanceof Map.Entry))
1536	>	return false;
1537	>	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1538	>	K key = entry.getKey();
1539	>	if (!inRange(key))
1540	>	return false;
1541	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1542	>	if (node!=null && valEquals(node.getValue(),entry.getValue())){
1543	>	m.deleteEntry(node);
1544	>	return true;
1545	>	}
1546	>	return false;
1547	>	}
1548		}
1549
1550	<	public Map.Entry<K,V> lastEntry() {
1551	<	return loEntry();
1552	<	}
1550	>	/**
1551	>	* Iterators for SubMaps
1552	>	*/
1553	>	abstract class SubMapIterator<T> implements Iterator<T> {
1554	>	TreeMap.Entry<K,V> lastReturned;
1555	>	TreeMap.Entry<K,V> next;
1556	>	final Object fenceKey;
1557	>	int expectedModCount;
1558	>
1559	>	SubMapIterator(TreeMap.Entry<K,V> first,
1560	>	TreeMap.Entry<K,V> fence) {
1561	>	expectedModCount = m.modCount;
1562	>	lastReturned = null;
1563	>	next = first;
1564	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1565	>	}
1566
1567	<	public Map.Entry<K,V> pollFirstEntry() {
1568	<	return pollHiEntry();
1569	<	}
1567	>	public final boolean hasNext() {
1568	>	return next != null && next.key != fenceKey;
1569	>	}
1570
1571	<	public Map.Entry<K,V> pollLastEntry() {
1572	<	return pollLoEntry();
1573	<	}
1571	>	final TreeMap.Entry<K,V> nextEntry() {
1572	>	TreeMap.Entry<K,V> e = lastReturned = next;
1573	>	if (e == null || e.key == fenceKey)
1574	>	throw new NoSuchElementException();
1575	>	if (m.modCount != expectedModCount)
1576	>	throw new ConcurrentModificationException();
1577	>	next = successor(e);
1578	>	return e;
1579	>	}
1580
1581	<	public NavigableMap<K,V> descendingMap() {
1582	<	NavigableMap<K,V> m = descendingMapView;
1583	<	return (m != null) ? m :
1584	<	(descendingMapView =
1585	<	new AscendingSubMap(lo, loExcluded, hi, hiExcluded));
1586	<	}
1581	>	final TreeMap.Entry<K,V> prevEntry() {
1582	>	TreeMap.Entry<K,V> e = lastReturned = next;
1583	>	if (e == null || e.key == fenceKey)
1584	>	throw new NoSuchElementException();
1585	>	if (m.modCount != expectedModCount)
1586	>	throw new ConcurrentModificationException();
1587	>	next = predecessor(e);
1588	>	return e;
1589	>	}
1590	>
1591	>	final void removeAscending() {
1592	>	if (lastReturned == null)
1593	>	throw new IllegalStateException();
1594	>	if (m.modCount != expectedModCount)
1595	>	throw new ConcurrentModificationException();
1596	>	// deleted entries are replaced by their successors
1597	>	if (lastReturned.left != null && lastReturned.right != null)
1598	>	next = lastReturned;
1599	>	m.deleteEntry(lastReturned);
1600	>	lastReturned = null;
1601	>	expectedModCount = m.modCount;
1602	>	}
1603	>
1604	>	final void removeDescending() {
1605	>	if (lastReturned == null)
1606	>	throw new IllegalStateException();
1607	>	if (m.modCount != expectedModCount)
1608	>	throw new ConcurrentModificationException();
1609	>	m.deleteEntry(lastReturned);
1610	>	lastReturned = null;
1611	>	expectedModCount = m.modCount;
1612	>	}
1613
1624	–	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1625	–	return super.subFloor(key);
1614		}
1615
1616	<	@Override TreeMap.Entry<K,V> subHigher(K key) {
1617	<	return super.subLower(key);
1616	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1617	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1618	>	TreeMap.Entry<K,V> fence) {
1619	>	super(first, fence);
1620	>	}
1621	>	public Map.Entry<K,V> next() {
1622	>	return nextEntry();
1623	>	}
1624	>	public void remove() {
1625	>	removeAscending();
1626	>	}
1627		}
1628
1629	<	@Override TreeMap.Entry<K,V> subFloor(K key) {
1630	<	return super.subCeiling(key);
1629	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1630	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1631	>	TreeMap.Entry<K,V> fence) {
1632	>	super(first, fence);
1633	>	}
1634	>	public K next() {
1635	>	return nextEntry().key;
1636	>	}
1637	>	public void remove() {
1638	>	removeAscending();
1639	>	}
1640		}
1641
1642	<	@Override TreeMap.Entry<K,V> subLower(K key) {
1643	<	return super.subHigher(key);
1642	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1643	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1644	>	TreeMap.Entry<K,V> fence) {
1645	>	super(last, fence);
1646	>	}
1647	>
1648	>	public Map.Entry<K,V> next() {
1649	>	return prevEntry();
1650	>	}
1651	>	public void remove() {
1652	>	removeDescending();
1653	>	}
1654		}
1639	–	}
1655
1656	<	/**
1657	<	* This class exists solely for the sake of serialization
1658	<	* compatibility with previous releases of TreeMap that did not
1659	<	* support NavigableMap.  It translates an old-version SubMap into
1660	<	* a new-version AscendingSubMap. This class is never otherwise
1661	<	* used.
1662	<	*/
1663	<	private class SubMap extends AbstractMap<K,V>
1664	<	implements SortedMap<K,V>, java.io.Serializable {
1665	<	private static final long serialVersionUID = -6520786458950516097L;
1666	<	private boolean fromStart = false, toEnd = false;
1652	<	private K fromKey, toKey;
1653	<	private Object readResolve() {
1654	<	return new AscendingSubMap
1655	<	(fromStart? ((K)UNBOUNDED) : fromKey, 0,
1656	<	toEnd? ((K)UNBOUNDED) : toKey, 1);
1656	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1657	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1658	>	TreeMap.Entry<K,V> fence) {
1659	>	super(last, fence);
1660	>	}
1661	>	public K next() {
1662	>	return prevEntry().key;
1663	>	}
1664	>	public void remove() {
1665	>	removeDescending();
1666	>	}
1667		}
1658	–	public Set<Map.Entry<K,V>> entrySet() { throw new UnsupportedOperationException(); }
1659	–	public K lastKey() { throw new UnsupportedOperationException(); }
1660	–	public K firstKey() { throw new UnsupportedOperationException(); }
1661	–	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new UnsupportedOperationException(); }
1662	–	public SortedMap<K,V> headMap(K toKey) { throw new UnsupportedOperationException(); }
1663	–	public SortedMap<K,V> tailMap(K fromKey) { throw new UnsupportedOperationException(); }
1664	–	public Comparator<? super K> comparator() { throw new UnsupportedOperationException(); }
1668		}
1669
1670		/**
1671	<	* TreeMap Iterator.
1671	>	* @serial include
1672		*/
1673	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1674	<	int expectedModCount = TreeMap.this.modCount;
1672	<	Entry<K,V> lastReturned = null;
1673	<	Entry<K,V> next;
1673	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1674	>	private static final long serialVersionUID = 912986545866124060L;
1675
1676	<	PrivateEntryIterator(Entry<K,V> first) {
1677	<	next = first;
1676	>	AscendingSubMap(TreeMap<K,V> m,
1677	>	boolean fromStart, K lo, boolean loInclusive,
1678	>	boolean toEnd,     K hi, boolean hiInclusive) {
1679	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1680		}
1681
1682	<	public final boolean hasNext() {
1683	<	return next != null;
1682	>	public Comparator<? super K> comparator() {
1683	>	return m.comparator();
1684		}
1685
1686	<	final Entry<K,V> nextEntry() {
1687	<	if (next == null)
1688	<	throw new NoSuchElementException();
1689	<	if (modCount != expectedModCount)
1690	<	throw new ConcurrentModificationException();
1691	<	lastReturned = next;
1692	<	next = successor(next);
1693	<	return lastReturned;
1686	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1687	>	K toKey,   boolean toInclusive) {
1688	>	if (!inRange(fromKey, fromInclusive))
1689	>	throw new IllegalArgumentException("fromKey out of range");
1690	>	if (!inRange(toKey, toInclusive))
1691	>	throw new IllegalArgumentException("toKey out of range");
1692	>	return new AscendingSubMap(m,
1693	>	false, fromKey, fromInclusive,
1694	>	false, toKey,   toInclusive);
1695		}
1696
1697	<	final Entry<K,V> prevEntry() {
1698	<	if (next == null)
1699	<	throw new NoSuchElementException();
1700	<	if (modCount != expectedModCount)
1701	<	throw new ConcurrentModificationException();
1702	<	lastReturned = next;
1699	<	next = predecessor(next);
1700	<	return lastReturned;
1697	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1698	>	if (!inRange(toKey, inclusive))
1699	>	throw new IllegalArgumentException("toKey out of range");
1700	>	return new AscendingSubMap(m,
1701	>	fromStart, lo,    loInclusive,
1702	>	false,     toKey, inclusive);
1703		}
1704
1705	<	public void remove() {
1706	<	if (lastReturned == null)
1707	<	throw new IllegalStateException();
1708	<	if (modCount != expectedModCount)
1709	<	throw new ConcurrentModificationException();
1710	<	if (lastReturned.left != null && lastReturned.right != null)
1709	<	next = lastReturned;
1710	<	deleteEntry(lastReturned);
1711	<	expectedModCount++;
1712	<	lastReturned = null;
1705	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1706	>	if (!inRange(fromKey, inclusive))
1707	>	throw new IllegalArgumentException("fromKey out of range");
1708	>	return new AscendingSubMap(m,
1709	>	false, fromKey, inclusive,
1710	>	toEnd, hi,      hiInclusive);
1711		}
1714	–	}
1712
1713	<	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1714	<	EntryIterator(Entry<K,V> first) {
1715	<	super(first);
1716	<	}
1717	<	public Map.Entry<K,V> next() {
1718	<	return nextEntry();
1713	>	public NavigableMap<K,V> descendingMap() {
1714	>	NavigableMap<K,V> mv = descendingMapView;
1715	>	return (mv != null) ? mv :
1716	>	(descendingMapView =
1717	>	new DescendingSubMap(m,
1718	>	fromStart, lo, loInclusive,
1719	>	toEnd,     hi, hiInclusive));
1720		}
1723	–	}
1721
1722	<	final class ValueIterator extends PrivateEntryIterator<V> {
1723	<	ValueIterator(Entry<K,V> first) {
1727	<	super(first);
1728	<	}
1729	<	public V next() {
1730	<	return nextEntry().value;
1722	>	Iterator<K> keyIterator() {
1723	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1724		}
1732	–	}
1725
1726	<	final class KeyIterator extends PrivateEntryIterator<K> {
1727	<	KeyIterator(Entry<K,V> first) {
1736	<	super(first);
1737	<	}
1738	<	public K next() {
1739	<	return nextEntry().key;
1726	>	Iterator<K> descendingKeyIterator() {
1727	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1728		}
1741	–	}
1729
1730	<	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1731	<	DescendingKeyIterator(Entry<K,V> first) {
1732	<	super(first);
1730	>	final class AscendingEntrySetView extends EntrySetView {
1731	>	public Iterator<Map.Entry<K,V>> iterator() {
1732	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1733	>	}
1734		}
1735	<	public K next() {
1736	<	return prevEntry().key;
1735	>
1736	>	public Set<Map.Entry<K,V>> entrySet() {
1737	>	EntrySetView es = entrySetView;
1738	>	return (es != null) ? es : new AscendingEntrySetView();
1739		}
1740	+
1741	+	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1742	+	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1743	+	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1744	+	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1745	+	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1746	+	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1747		}
1748
1749	<	/**
1750	<	* Iterators for SubMaps
1749	>	/**
1750	>	* @serial include
1751		*/
1752	<	abstract class SubMapIterator<T> implements Iterator<T> {
1753	<	int expectedModCount = TreeMap.this.modCount;
1754	<	Entry<K,V> lastReturned = null;
1755	<	Entry<K,V> next;
1756	<	final K firstExcludedKey;
1757	<
1761	<	SubMapIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	<	next = first;
1763	<	firstExcludedKey = (firstExcluded == null ? null
1764	<	: firstExcluded.key);
1752	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1753	>	private static final long serialVersionUID = 912986545866120460L;
1754	>	DescendingSubMap(TreeMap<K,V> m,
1755	>	boolean fromStart, K lo, boolean loInclusive,
1756	>	boolean toEnd,     K hi, boolean hiInclusive) {
1757	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1758		}
1759
1760	<	public final boolean hasNext() {
1761	<	return next != null && next.key != firstExcludedKey;
1769	<	}
1760	>	private final Comparator<? super K> reverseComparator =
1761	>	Collections.reverseOrder(m.comparator);
1762
1763	<	final Entry<K,V> nextEntry() {
1764	<	if (next == null || next.key == firstExcludedKey)
1773	<	throw new NoSuchElementException();
1774	<	if (modCount != expectedModCount)
1775	<	throw new ConcurrentModificationException();
1776	<	lastReturned = next;
1777	<	next = successor(next);
1778	<	return lastReturned;
1763	>	public Comparator<? super K> comparator() {
1764	>	return reverseComparator;
1765		}
1766
1767	<	final Entry<K,V> prevEntry() {
1768	<	if (next == null || next.key == firstExcludedKey)
1769	<	throw new NoSuchElementException();
1770	<	if (modCount != expectedModCount)
1771	<	throw new ConcurrentModificationException();
1772	<	lastReturned = next;
1773	<	next = predecessor(next);
1774	<	return lastReturned;
1767	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1768	>	K toKey,   boolean toInclusive) {
1769	>	if (!inRange(fromKey, fromInclusive))
1770	>	throw new IllegalArgumentException("fromKey out of range");
1771	>	if (!inRange(toKey, toInclusive))
1772	>	throw new IllegalArgumentException("toKey out of range");
1773	>	return new DescendingSubMap(m,
1774	>	false, toKey,   toInclusive,
1775	>	false, fromKey, fromInclusive);
1776		}
1777
1778	<	public void remove() {
1779	<	if (lastReturned == null)
1780	<	throw new IllegalStateException();
1781	<	if (modCount != expectedModCount)
1782	<	throw new ConcurrentModificationException();
1783	<	if (lastReturned.left != null && lastReturned.right != null)
1797	<	next = lastReturned;
1798	<	deleteEntry(lastReturned);
1799	<	expectedModCount++;
1800	<	lastReturned = null;
1778	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1779	>	if (!inRange(toKey, inclusive))
1780	>	throw new IllegalArgumentException("toKey out of range");
1781	>	return new DescendingSubMap(m,
1782	>	false, toKey, inclusive,
1783	>	toEnd, hi,    hiInclusive);
1784		}
1802	–	}
1785
1786	<	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1787	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1788	<	super(first, firstExcluded);
1789	<	}
1790	<	public Map.Entry<K,V> next() {
1791	<	return nextEntry();
1786	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1787	>	if (!inRange(fromKey, inclusive))
1788	>	throw new IllegalArgumentException("fromKey out of range");
1789	>	return new DescendingSubMap(m,
1790	>	fromStart, lo, loInclusive,
1791	>	false, fromKey, inclusive);
1792		}
1811	–	}
1793
1794	<	final class SubMapKeyIterator extends SubMapIterator<K> {
1795	<	SubMapKeyIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1796	<	super(first, firstExcluded);
1797	<	}
1798	<	public K next() {
1799	<	return nextEntry().key;
1794	>	public NavigableMap<K,V> descendingMap() {
1795	>	NavigableMap<K,V> mv = descendingMapView;
1796	>	return (mv != null) ? mv :
1797	>	(descendingMapView =
1798	>	new AscendingSubMap(m,
1799	>	fromStart, lo, loInclusive,
1800	>	toEnd,     hi, hiInclusive));
1801		}
1820	–	}
1802
1803	<	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1804	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1824	<	super(last, lastExcluded);
1803	>	Iterator<K> keyIterator() {
1804	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1805		}
1806
1807	<	public Map.Entry<K,V> next() {
1808	<	return prevEntry();
1807	>	Iterator<K> descendingKeyIterator() {
1808	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1809		}
1830	–	}
1810
1811	<	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1812	<	DescendingSubMapKeyIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1813	<	super(last, lastExcluded);
1811	>	final class DescendingEntrySetView extends EntrySetView {
1812	>	public Iterator<Map.Entry<K,V>> iterator() {
1813	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1814	>	}
1815		}
1816	<	public K next() {
1817	<	return prevEntry().key;
1816	>
1817	>	public Set<Map.Entry<K,V>> entrySet() {
1818	>	EntrySetView es = entrySetView;
1819	>	return (es != null) ? es : new DescendingEntrySetView();
1820		}
1839	–	}
1821
1822	<	/**
1823	<	* Compares two keys using the correct comparison method for this TreeMap.
1824	<	*/
1825	<	private int compare(Object k1, Object k2) {
1826	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1827	<	: comparator.compare((K)k1, (K)k2);
1822	>	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1823	>	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1824	>	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1825	>	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1826	>	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1827	>	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1828		}
1829
1830		/**
1831	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1832	<	* that it copes with <tt>null</tt> o1 properly.
1831	>	* This class exists solely for the sake of serialization
1832	>	* compatibility with previous releases of TreeMap that did not
1833	>	* support NavigableMap.  It translates an old-version SubMap into
1834	>	* a new-version AscendingSubMap. This class is never otherwise
1835	>	* used.
1836	>	*
1837	>	* @serial include
1838		*/
1839	<	private static boolean valEquals(Object o1, Object o2) {
1840	<	return (o1==null ? o2==null : o1.equals(o2));
1839	>	private class SubMap extends AbstractMap<K,V>
1840	>	implements SortedMap<K,V>, java.io.Serializable {
1841	>	private static final long serialVersionUID = -6520786458950516097L;
1842	>	private boolean fromStart = false, toEnd = false;
1843	>	private K fromKey, toKey;
1844	>	private Object readResolve() {
1845	>	return new AscendingSubMap(TreeMap.this,
1846	>	fromStart, fromKey, true,
1847	>	toEnd, toKey, false);
1848	>	}
1849	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1850	>	public K lastKey() { throw new InternalError(); }
1851	>	public K firstKey() { throw new InternalError(); }
1852	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1853	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1854	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1855	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1856		}
1857
1858	+
1859	+	// Red-black mechanics
1860	+
1861		private static final boolean RED   = false;
1862		private static final boolean BLACK = true;
1863
#	Line 1862 | Line 1866 | public class TreeMap<K,V>
1866		* user (see Map.Entry).
1867		*/
1868
1869	<	static class Entry<K,V> implements Map.Entry<K,V> {
1869	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1870		K key;
1871		V value;
1872		Entry<K,V> left = null;
#	Line 1914 | Line 1918 | public class TreeMap<K,V>
1918		public boolean equals(Object o) {
1919		if (!(o instanceof Map.Entry))
1920		return false;
1921	<	Map.Entry e = (Map.Entry)o;
1921	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1922
1923		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1924		}
#	Line 1934 | Line 1938 | public class TreeMap<K,V>
1938		* Returns the first Entry in the TreeMap (according to the TreeMap's
1939		* key-sort function).  Returns null if the TreeMap is empty.
1940		*/
1941	<	private Entry<K,V> getFirstEntry() {
1941	>	final Entry<K,V> getFirstEntry() {
1942		Entry<K,V> p = root;
1943		if (p != null)
1944		while (p.left != null)
#	Line 1946 | Line 1950 | public class TreeMap<K,V>
1950		* Returns the last Entry in the TreeMap (according to the TreeMap's
1951		* key-sort function).  Returns null if the TreeMap is empty.
1952		*/
1953	<	private Entry<K,V> getLastEntry() {
1953	>	final Entry<K,V> getLastEntry() {
1954		Entry<K,V> p = root;
1955		if (p != null)
1956		while (p.right != null)
#	Line 1957 | Line 1961 | public class TreeMap<K,V>
1961		/**
1962		* Returns the successor of the specified Entry, or null if no such.
1963		*/
1964	<	private Entry<K,V> successor(Entry<K,V> t) {
1964	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1965		if (t == null)
1966		return null;
1967		else if (t.right != null) {
#	Line 1979 | Line 1983 | public class TreeMap<K,V>
1983		/**
1984		* Returns the predecessor of the specified Entry, or null if no such.
1985		*/
1986	<	private Entry<K,V> predecessor(Entry<K,V> t) {
1986	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1987		if (t == null)
1988		return null;
1989		else if (t.left != null) {
#	Line 2029 | Line 2033 | public class TreeMap<K,V>
2033		return (p == null) ? null: p.right;
2034		}
2035
2036	<	/** From CLR **/
2036	>	/** From CLR */
2037		private void rotateLeft(Entry<K,V> p) {
2038	<	Entry<K,V> r = p.right;
2039	<	p.right = r.left;
2040	<	if (r.left != null)
2041	<	r.left.parent = p;
2042	<	r.parent = p.parent;
2043	<	if (p.parent == null)
2044	<	root = r;
2045	<	else if (p.parent.left == p)
2046	<	p.parent.left = r;
2047	<	else
2048	<	p.parent.right = r;
2049	<	r.left = p;
2050	<	p.parent = r;
2038	>	if (p != null) {
2039	>	Entry<K,V> r = p.right;
2040	>	p.right = r.left;
2041	>	if (r.left != null)
2042	>	r.left.parent = p;
2043	>	r.parent = p.parent;
2044	>	if (p.parent == null)
2045	>	root = r;
2046	>	else if (p.parent.left == p)
2047	>	p.parent.left = r;
2048	>	else
2049	>	p.parent.right = r;
2050	>	r.left = p;
2051	>	p.parent = r;
2052	>	}
2053		}
2054
2055	<	/** From CLR **/
2055	>	/** From CLR */
2056		private void rotateRight(Entry<K,V> p) {
2057	<	Entry<K,V> l = p.left;
2058	<	p.left = l.right;
2059	<	if (l.right != null) l.right.parent = p;
2060	<	l.parent = p.parent;
2061	<	if (p.parent == null)
2062	<	root = l;
2063	<	else if (p.parent.right == p)
2064	<	p.parent.right = l;
2065	<	else p.parent.left = l;
2066	<	l.right = p;
2067	<	p.parent = l;
2057	>	if (p != null) {
2058	>	Entry<K,V> l = p.left;
2059	>	p.left = l.right;
2060	>	if (l.right != null) l.right.parent = p;
2061	>	l.parent = p.parent;
2062	>	if (p.parent == null)
2063	>	root = l;
2064	>	else if (p.parent.right == p)
2065	>	p.parent.right = l;
2066	>	else p.parent.left = l;
2067	>	l.right = p;
2068	>	p.parent = l;
2069	>	}
2070		}
2071
2072	<
2065	<	/** From CLR **/
2072	>	/** From CLR */
2073		private void fixAfterInsertion(Entry<K,V> x) {
2074		x.color = RED;
2075
#	Line 2081 | Line 2088 | public class TreeMap<K,V>
2088		}
2089		setColor(parentOf(x), BLACK);
2090		setColor(parentOf(parentOf(x)), RED);
2091	<	if (parentOf(parentOf(x)) != null)
2085	<	rotateRight(parentOf(parentOf(x)));
2091	>	rotateRight(parentOf(parentOf(x)));
2092		}
2093		} else {
2094		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2096 | Line 2102 | public class TreeMap<K,V>
2102		x = parentOf(x);
2103		rotateRight(x);
2104		}
2105	<	setColor(parentOf(x),  BLACK);
2105	>	setColor(parentOf(x), BLACK);
2106		setColor(parentOf(parentOf(x)), RED);
2107	<	if (parentOf(parentOf(x)) != null)
2102	<	rotateLeft(parentOf(parentOf(x)));
2107	>	rotateLeft(parentOf(parentOf(x)));
2108		}
2109		}
2110		}
#	Line 2109 | Line 2114 | public class TreeMap<K,V>
2114		/**
2115		* Delete node p, and then rebalance the tree.
2116		*/
2112	–
2117		private void deleteEntry(Entry<K,V> p) {
2118	<	decrementSize();
2118	>	modCount++;
2119	>	size--;
2120
2121		// If strictly internal, copy successor's element to p and then make p
2122		// point to successor.
#	Line 2157 | Line 2162 | public class TreeMap<K,V>
2162		}
2163		}
2164
2165	<	/** From CLR **/
2165	>	/** From CLR */
2166		private void fixAfterDeletion(Entry<K,V> x) {
2167		while (x != root && colorOf(x) == BLACK) {
2168		if (x == leftOf(parentOf(x))) {
#	Line 2172 | Line 2177 | public class TreeMap<K,V>
2177
2178		if (colorOf(leftOf(sib))  == BLACK &&
2179		colorOf(rightOf(sib)) == BLACK) {
2180	<	setColor(sib,  RED);
2180	>	setColor(sib, RED);
2181		x = parentOf(x);
2182		} else {
2183		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2199 | Line 2204 | public class TreeMap<K,V>
2204
2205		if (colorOf(rightOf(sib)) == BLACK &&
2206		colorOf(leftOf(sib)) == BLACK) {
2207	<	setColor(sib,  RED);
2207	>	setColor(sib, RED);
2208		x = parentOf(x);
2209		} else {
2210		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 2265 | Line 2270 | public class TreeMap<K,V>
2270		buildFromSorted(size, null, s, null);
2271		}
2272
2273	<	/** Intended to be called only from TreeSet.readObject **/
2273	>	/** Intended to be called only from TreeSet.readObject */
2274		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2275		throws java.io.IOException, ClassNotFoundException {
2276		buildFromSorted(size, null, s, defaultVal);
2277		}
2278
2279	<	/** Intended to be called only from TreeSet.addAll **/
2279	>	/** Intended to be called only from TreeSet.addAll */
2280		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2281		try {
2282		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
#	Line 2354 | Line 2359 | public class TreeMap<K,V>
2359
2360		if (hi < lo) return null;
2361
2362	<	int mid = (lo + hi) / 2;
2362	>	int mid = (lo + hi) >>> 1;
2363
2364		Entry<K,V> left  = null;
2365		if (lo < mid)

Diff Legend

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