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.31 by dl, Fri Apr 21 13:42:57 2006 UTC vs.
Revision 1.45 by jsr166, Sun May 18 23:47:56 2008 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
#	Line 68 | Line 86 | package java.util;
86		* associated map using <tt>put</tt>.)
87		*
88		* <p>This class is a member of the
89	<	* <a href="{@docRoot}/../guide/collections/index.html">
89	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
90		* Java Collections Framework</a>.
91		*
92		* @param <K> the type of keys maintained by this map
#	Line 109 | Line 127 | public class TreeMap<K,V>
127		*/
128		private transient int modCount = 0;
129
112	–	private void incrementSize()   { modCount++; size++; }
113	–	private void decrementSize()   { modCount++; size--; }
114	–
130		/**
131		* Constructs a new, empty tree map, using the natural ordering of its
132		* keys.  All keys inserted into the map must implement the {@link
#	Line 222 | Line 237 | public class TreeMap<K,V>
237		*
238		* @param value value whose presence in this map is to be tested
239		* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
240	<	*         <tt>false</tt> otherwise
240	>	*         <tt>false</tt> otherwise
241		* @since 1.2
242		*/
243		public boolean containsValue(Object value) {
244	<	return (root==null ? false :
245	<	(value==null ? valueSearchNull(root)
246	<	: valueSearchNonNull(root, value)));
247	<	}
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));
244	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
245	>	if (valEquals(value, e.value))
246	>	return true;
247	>	return false;
248		}
249
250		/**
#	Line 312 | Line 309 | public class TreeMap<K,V>
309		if (size==0 && mapSize!=0 && map instanceof SortedMap) {
310		Comparator c = ((SortedMap)map).comparator();
311		if (c == comparator || (c != null && c.equals(comparator))) {
312	<	++modCount;
313	<	try {
314	<	buildFromSorted(mapSize, map.entrySet().iterator(),
315	<	null, null);
316	<	} catch (java.io.IOException cannotHappen) {
317	<	} catch (ClassNotFoundException cannotHappen) {
318	<	}
319	<	return;
312	>	++modCount;
313	>	try {
314	>	buildFromSorted(mapSize, map.entrySet().iterator(),
315	>	null, null);
316	>	} catch (java.io.IOException cannotHappen) {
317	>	} catch (ClassNotFoundException cannotHappen) {
318	>	}
319	>	return;
320		}
321		}
322		super.putAll(map);
#	Line 343 | Line 340 | public class TreeMap<K,V>
340		return getEntryUsingComparator(key);
341		if (key == null)
342		throw new NullPointerException();
343	<	Comparable<? super K> k = (Comparable<? super K>) key;
343	>	Comparable<? super K> k = (Comparable<? super K>) key;
344		Entry<K,V> p = root;
345		while (p != null) {
346		int cmp = k.compareTo(p.key);
#	Line 361 | Line 358 | public class TreeMap<K,V>
358		* Version of getEntry using comparator. Split off from getEntry
359		* for performance. (This is not worth doing for most methods,
360		* that are less dependent on comparator performance, but is
361	<	* worthwhile for get and put.)
361	>	* worthwhile here.)
362		*/
363		final Entry<K,V> getEntryUsingComparator(Object key) {
364	<	K k = (K) key;
364	>	K k = (K) key;
365		Comparator<? super K> cpr = comparator;
366	<	Entry<K,V> p = root;
367	<	while (p != null) {
368	<	int cmp = cpr.compare(k, p.key);
369	<	if (cmp < 0)
370	<	p = p.left;
371	<	else if (cmp > 0)
372	<	p = p.right;
373	<	else
374	<	return p;
366	>	if (cpr != null) {
367	>	Entry<K,V> p = root;
368	>	while (p != null) {
369	>	int cmp = cpr.compare(k, p.key);
370	>	if (cmp < 0)
371	>	p = p.left;
372	>	else if (cmp > 0)
373	>	p = p.right;
374	>	else
375	>	return p;
376	>	}
377		}
378		return null;
379		}
#	Line 509 | Line 508 | public class TreeMap<K,V>
508		}
509
510		/**
512	–	* Returns the key corresponding to the specified Entry.
513	–	* @throws NoSuchElementException if the Entry is null
514	–	*/
515	–	static <K> K key(Entry<K,?> e) {
516	–	if (e==null)
517	–	throw new NoSuchElementException();
518	–	return e.key;
519	–	}
520	–
521	–	/**
511		* Associates the specified value with the specified key in this map.
512		* If the map previously contained a mapping for the key, the old
513		* value is replaced.
#	Line 537 | Line 526 | public class TreeMap<K,V>
526		*         does not permit null keys
527		*/
528		public V put(K key, V value) {
540	–	// Offload comparator-based version for sake of performance
541	–	if (comparator != null)
542	–	return putUsingComparator(key, value);
543	–	if (key == null)
544	–	throw new NullPointerException();
545	–	Comparable<? super K> k = (Comparable<? super K>) key;
546	–
529		Entry<K,V> t = root;
530	<	while (t != null) {
531	<	int cmp = k.compareTo(t.key);
532	<	if (cmp == 0) {
533	<	return t.setValue(value);
534	<	} else if (cmp < 0) {
535	<	if (t.left != null) {
530	>	if (t == null) {
531	>	// TBD:
532	>	// 5045147: (coll) Adding null to an empty TreeSet should
533	>	// throw NullPointerException
534	>	//
535	>	// compare(key, key); // type check
536	>	root = new Entry<K,V>(key, value, null);
537	>	size = 1;
538	>	modCount++;
539	>	return null;
540	>	}
541	>	int cmp;
542	>	Entry<K,V> parent;
543	>	// split comparator and comparable paths
544	>	Comparator<? super K> cpr = comparator;
545	>	if (cpr != null) {
546	>	do {
547	>	parent = t;
548	>	cmp = cpr.compare(key, t.key);
549	>	if (cmp < 0)
550		t = t.left;
551	<	} else {
556	<	incrementSize();
557	<	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
558	<	return null;
559	<	}
560	<	} else { // cmp > 0
561	<	if (t.right != null) {
551	>	else if (cmp > 0)
552		t = t.right;
553	<	} else {
554	<	incrementSize();
555	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	<	return null;
567	<	}
568	<	}
553	>	else
554	>	return t.setValue(value);
555	>	} while (t != null);
556		}
557	<	incrementSize();
558	<	root = new Entry<K,V>(key, value, null);
559	<	return null;
560	<	}
561	<
562	<	/**
563	<	* Version of put using comparator. Split off from put for
564	<	* performance.
578	<	*/
579	<	final V putUsingComparator(K key, V value) {
580	<	Comparator<? super K> cpr = comparator;
581	<	Entry<K,V> t = root;
582	<	while (t != null) {
583	<	int cmp = cpr.compare(key, t.key);
584	<	if (cmp == 0) {
585	<	return t.setValue(value);
586	<	} else if (cmp < 0) {
587	<	if (t.left != null) {
557	>	else {
558	>	if (key == null)
559	>	throw new NullPointerException();
560	>	Comparable<? super K> k = (Comparable<? super K>) key;
561	>	do {
562	>	parent = t;
563	>	cmp = k.compareTo(t.key);
564	>	if (cmp < 0)
565		t = t.left;
566	<	} else {
590	<	incrementSize();
591	<	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592	<	return null;
593	<	}
594	<	} else { // cmp > 0
595	<	if (t.right != null) {
566	>	else if (cmp > 0)
567		t = t.right;
568	<	} else {
569	<	incrementSize();
570	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600	<	return null;
601	<	}
602	<	}
568	>	else
569	>	return t.setValue(value);
570	>	} while (t != null);
571		}
572	<	cpr.compare(key, key); // type check
573	<	incrementSize();
574	<	root = new Entry<K,V>(key, value, null);
572	>	Entry<K,V> e = new Entry<K,V>(key, value, parent);
573	>	if (cmp < 0)
574	>	parent.left = e;
575	>	else
576	>	parent.right = e;
577	>	fixAfterInsertion(e);
578	>	size++;
579	>	modCount++;
580		return null;
581		}
582
#	Line 679 | Line 652 | public class TreeMap<K,V>
652		* @since 1.6
653		*/
654		public Map.Entry<K,V> firstEntry() {
655	<	Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
655	>	return exportEntry(getFirstEntry());
656		}
657
658		/**
659		* @since 1.6
660		*/
661		public Map.Entry<K,V> lastEntry() {
662	<	Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
662	>	return exportEntry(getLastEntry());
663		}
664
665		/**
#	Line 696 | Line 667 | public class TreeMap<K,V>
667		*/
668		public Map.Entry<K,V> pollFirstEntry() {
669		Entry<K,V> p = getFirstEntry();
670	<	if (p == null)
671	<	return null;
672	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702	<	deleteEntry(p);
670	>	Map.Entry<K,V> result = exportEntry(p);
671	>	if (p != null)
672	>	deleteEntry(p);
673		return result;
674		}
675
#	Line 708 | Line 678 | public class TreeMap<K,V>
678		*/
679		public Map.Entry<K,V> pollLastEntry() {
680		Entry<K,V> p = getLastEntry();
681	<	if (p == null)
682	<	return null;
683	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714	<	deleteEntry(p);
681	>	Map.Entry<K,V> result = exportEntry(p);
682	>	if (p != null)
683	>	deleteEntry(p);
684		return result;
685		}
686
#	Line 723 | Line 692 | public class TreeMap<K,V>
692		* @since 1.6
693		*/
694		public Map.Entry<K,V> lowerEntry(K key) {
695	<	Entry<K,V> e =  getLowerEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
695	>	return exportEntry(getLowerEntry(key));
696		}
697
698		/**
#	Line 735 | Line 703 | public class TreeMap<K,V>
703		* @since 1.6
704		*/
705		public K lowerKey(K key) {
706	<	Entry<K,V> e =  getLowerEntry(key);
739	<	return (e == null)? null : e.key;
706	>	return keyOrNull(getLowerEntry(key));
707		}
708
709		/**
#	Line 747 | Line 714 | public class TreeMap<K,V>
714		* @since 1.6
715		*/
716		public Map.Entry<K,V> floorEntry(K key) {
717	<	Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
717	>	return exportEntry(getFloorEntry(key));
718		}
719
720		/**
#	Line 759 | Line 725 | public class TreeMap<K,V>
725		* @since 1.6
726		*/
727		public K floorKey(K key) {
728	<	Entry<K,V> e = getFloorEntry(key);
763	<	return (e == null)? null : e.key;
728	>	return keyOrNull(getFloorEntry(key));
729		}
730
731		/**
#	Line 771 | Line 736 | public class TreeMap<K,V>
736		* @since 1.6
737		*/
738		public Map.Entry<K,V> ceilingEntry(K key) {
739	<	Entry<K,V> e = getCeilingEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
739	>	return exportEntry(getCeilingEntry(key));
740		}
741
742		/**
#	Line 783 | Line 747 | public class TreeMap<K,V>
747		* @since 1.6
748		*/
749		public K ceilingKey(K key) {
750	<	Entry<K,V> e = getCeilingEntry(key);
787	<	return (e == null)? null : e.key;
750	>	return keyOrNull(getCeilingEntry(key));
751		}
752
753		/**
#	Line 795 | Line 758 | public class TreeMap<K,V>
758		* @since 1.6
759		*/
760		public Map.Entry<K,V> higherEntry(K key) {
761	<	Entry<K,V> e = getHigherEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
761	>	return exportEntry(getHigherEntry(key));
762		}
763
764		/**
#	Line 807 | Line 769 | public class TreeMap<K,V>
769		* @since 1.6
770		*/
771		public K higherKey(K key) {
772	<	Entry<K,V> e = getHigherEntry(key);
811	<	return (e == null)? null : e.key;
772	>	return keyOrNull(getHigherEntry(key));
773		}
774
775		// Views
#	Line 902 | Line 863 | public class TreeMap<K,V>
863		NavigableMap<K, V> km = descendingMap;
864		return (km != null) ? km :
865		(descendingMap = new DescendingSubMap(this,
866	<	true, null, 0,
867	<	true, null, 0));
866	>	true, null, true,
867	>	true, null, true));
868		}
869
870		/**
#	Line 917 | Line 878 | public class TreeMap<K,V>
878		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
879		K toKey,   boolean toInclusive) {
880		return new AscendingSubMap(this,
881	<	false, fromKey, excluded(fromInclusive),
882	<	false, toKey,   excluded(toInclusive));
881	>	false, fromKey, fromInclusive,
882	>	false, toKey,   toInclusive);
883		}
884
885		/**
#	Line 931 | Line 892 | public class TreeMap<K,V>
892		*/
893		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
894		return new AscendingSubMap(this,
895	<	true,  null,  0,
896	<	false, toKey, excluded(inclusive));
895	>	true,  null,  true,
896	>	false, toKey, inclusive);
897		}
898
899		/**
#	Line 945 | Line 906 | public class TreeMap<K,V>
906		*/
907		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
908		return new AscendingSubMap(this,
909	<	false, fromKey, excluded(inclusive),
910	<	true,  null,    0);
950	<	}
951	<
952	<	/**
953	<	* Translates a boolean "inclusive" value to the correct int value
954	<	* for the loExcluded or hiExcluded field.
955	<	*/
956	<	static int excluded(boolean inclusive) {
957	<	return inclusive ? 0 : 1;
909	>	false, fromKey, inclusive,
910	>	true,  null,    true);
911		}
912
913		/**
#	Line 1002 | Line 955 | public class TreeMap<K,V>
955		}
956
957		public boolean contains(Object o) {
958	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
1006	<	if (valEquals(e.getValue(), o))
1007	<	return true;
1008	<	return false;
958	>	return TreeMap.this.containsValue(o);
959		}
960
961		public boolean remove(Object o) {
#	Line 1118 | Line 1068 | public class TreeMap<K,V>
1068		return size() != oldSize;
1069		}
1070		public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071	<	E toElement, boolean toInclusive) {
1071	>	E toElement,   boolean toInclusive) {
1072		return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1073		toElement,   toInclusive));
1074		}
#	Line 1160 | Line 1110 | public class TreeMap<K,V>
1110		return next != null;
1111		}
1112
1113	<	final Entry<K,V> nextEntry() {
1114	<	Entry<K,V> e = lastReturned = next;
1113	>	final Entry<K,V> nextEntry() {
1114	>	Entry<K,V> e = next;
1115		if (e == null)
1116		throw new NoSuchElementException();
1117		if (modCount != expectedModCount)
1118		throw new ConcurrentModificationException();
1119		next = successor(e);
1120	+	lastReturned = e;
1121		return e;
1122		}
1123
1124		final Entry<K,V> prevEntry() {
1125	<	Entry<K,V> e = lastReturned= next;
1125	>	Entry<K,V> e = next;
1126		if (e == null)
1127		throw new NoSuchElementException();
1128		if (modCount != expectedModCount)
1129		throw new ConcurrentModificationException();
1130		next = predecessor(e);
1131	+	lastReturned = e;
1132		return e;
1133		}
1134
#	Line 1185 | Line 1137 | public class TreeMap<K,V>
1137		throw new IllegalStateException();
1138		if (modCount != expectedModCount)
1139		throw new ConcurrentModificationException();
1140	+	// deleted entries are replaced by their successors
1141		if (lastReturned.left != null && lastReturned.right != null)
1142		next = lastReturned;
1143		deleteEntry(lastReturned);
1144	<	expectedModCount++;
1144	>	expectedModCount = modCount;
1145		lastReturned = null;
1146		}
1147		}
#	Line 1229 | Line 1182 | public class TreeMap<K,V>
1182		}
1183		}
1184
1185	+	// Little utilities
1186	+
1187	+	/**
1188	+	* Compares two keys using the correct comparison method for this TreeMap.
1189	+	*/
1190	+	final int compare(Object k1, Object k2) {
1191	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1192	+	: comparator.compare((K)k1, (K)k2);
1193	+	}
1194	+
1195	+	/**
1196	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1197	+	* that it copes with <tt>null</tt> o1 properly.
1198	+	*/
1199	+	final static boolean valEquals(Object o1, Object o2) {
1200	+	return (o1==null ? o2==null : o1.equals(o2));
1201	+	}
1202	+
1203	+	/**
1204	+	* Return SimpleImmutableEntry for entry, or null if null
1205	+	*/
1206	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1207	+	return e == null? null :
1208	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1209	+	}
1210	+
1211	+	/**
1212	+	* Return key for entry, or null if null
1213	+	*/
1214	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1215	+	return e == null? null : e.key;
1216	+	}
1217	+
1218	+	/**
1219	+	* Returns the key corresponding to the specified Entry.
1220	+	* @throws NoSuchElementException if the Entry is null
1221	+	*/
1222	+	static <K> K key(Entry<K,?> e) {
1223	+	if (e==null)
1224	+	throw new NoSuchElementException();
1225	+	return e.key;
1226	+	}
1227	+
1228	+
1229		// SubMaps
1230
1231	+	/**
1232	+	* Dummy value serving as unmatchable fence key for unbounded
1233	+	* SubMapIterators
1234	+	*/
1235	+	private static final Object UNBOUNDED = new Object();
1236	+
1237	+	/**
1238	+	* @serial include
1239	+	*/
1240		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241		implements NavigableMap<K,V>, java.io.Serializable {
1242	<
1237	<	/*
1242	>	/**
1243		* The backing map.
1244		*/
1245		final TreeMap<K,V> m;
1246
1247	<	/*
1248	<	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1249	<	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1250	<	* the low (absolute) bound is the start of the backing map, and the
1251	<	* other values are ignored. Otherwise, if loExcluded is
1252	<	* zero, lo is the inclusive bound, else loExcluded is one,
1253	<	* and lo is the exclusive bound. Similarly for the upper bound.
1247	>	/**
1248	>	* Endpoints are represented as triples (fromStart, lo,
1249	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250	>	* true, then the low (absolute) bound is the start of the
1251	>	* backing map, and the other values are ignored. Otherwise,
1252	>	* if loInclusive is true, lo is the inclusive bound, else lo
1253	>	* is the exclusive bound. Similarly for the upper bound.
1254		*/
1250	–
1255		final K lo, hi;
1256		final boolean fromStart, toEnd;
1257	<	final int loExcluded, hiExcluded;
1257	>	final boolean loInclusive, hiInclusive;
1258
1259		NavigableSubMap(TreeMap<K,V> m,
1260	<	boolean fromStart, K lo, int loExcluded,
1261	<	boolean toEnd,     K hi, int hiExcluded) {
1260	>	boolean fromStart, K lo, boolean loInclusive,
1261	>	boolean toEnd,     K hi, boolean hiInclusive) {
1262		if (!fromStart && !toEnd) {
1263		if (m.compare(lo, hi) > 0)
1264		throw new IllegalArgumentException("fromKey > toKey");
1265	+	} else {
1266	+	if (!fromStart) // type check
1267	+	m.compare(lo, lo);
1268	+	if (!toEnd)
1269	+	m.compare(hi, hi);
1270		}
1262	–	else if (!fromStart) // type check
1263	–	m.compare(lo, lo);
1264	–	else if (!toEnd)
1265	–	m.compare(hi, hi);
1271
1272		this.m = m;
1273		this.fromStart = fromStart;
1274		this.lo = lo;
1275	<	this.loExcluded = loExcluded;
1275	>	this.loInclusive = loInclusive;
1276		this.toEnd = toEnd;
1277		this.hi = hi;
1278	<	this.hiExcluded = hiExcluded;
1278	>	this.hiInclusive = hiInclusive;
1279		}
1280
1281		// internal utilities
1282
1283	+	final boolean tooLow(Object key) {
1284	+	if (!fromStart) {
1285	+	int c = m.compare(key, lo);
1286	+	if (c < 0 || (c == 0 && !loInclusive))
1287	+	return true;
1288	+	}
1289	+	return false;
1290	+	}
1291	+
1292	+	final boolean tooHigh(Object key) {
1293	+	if (!toEnd) {
1294	+	int c = m.compare(key, hi);
1295	+	if (c > 0 || (c == 0 && !hiInclusive))
1296	+	return true;
1297	+	}
1298	+	return false;
1299	+	}
1300	+
1301		final boolean inRange(Object key) {
1302	<	return (fromStart || m.compare(key, lo) >= loExcluded)
1280	<	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1302	>	return !tooLow(key) && !tooHigh(key);
1303		}
1304
1305		final boolean inClosedRange(Object key) {
#	Line 1289 | Line 1311 | public class TreeMap<K,V>
1311		return inclusive ? inRange(key) : inClosedRange(key);
1312		}
1313
1314	<	final boolean tooLow(K key) {
1315	<	return !fromStart && m.compare(key, lo) < loExcluded;
1316	<	}
1317	<
1318	<	final boolean tooHigh(K key) {
1297	<	return !toEnd && m.compare(hi, key) < hiExcluded;
1298	<	}
1314	>	/*
1315	>	* Absolute versions of relation operations.
1316	>	* Subclasses map to these using like-named "sub"
1317	>	* versions that invert senses for descending maps
1318	>	*/
1319
1320	<	/** Returns the lowest entry in this submap (absolute ordering) */
1321	<	final TreeMap.Entry<K,V> loEntry() {
1302	<	TreeMap.Entry<K,V> result =
1320	>	final TreeMap.Entry<K,V> absLowest() {
1321	>	TreeMap.Entry<K,V> e =
1322		(fromStart ?  m.getFirstEntry() :
1323	<	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1324	<	m.getHigherEntry(lo)));
1325	<	return (result == null || tooHigh(result.key)) ? null : result;
1323	>	(loInclusive ? m.getCeilingEntry(lo) :
1324	>	m.getHigherEntry(lo)));
1325	>	return (e == null || tooHigh(e.key)) ? null : e;
1326		}
1327
1328	<	/** Returns the highest key in this submap (absolute ordering) */
1329	<	final TreeMap.Entry<K,V> hiEntry() {
1311	<	TreeMap.Entry<K,V> result =
1328	>	final TreeMap.Entry<K,V> absHighest() {
1329	>	TreeMap.Entry<K,V> e =
1330		(toEnd ?  m.getLastEntry() :
1331	<	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1332	<	m.getLowerEntry(hi)));
1333	<	return (result == null || tooLow(result.key)) ? null : result;
1331	>	(hiInclusive ?  m.getFloorEntry(hi) :
1332	>	m.getLowerEntry(hi)));
1333	>	return (e == null || tooLow(e.key)) ? null : e;
1334		}
1335
1336	<	/** Polls the lowest entry in this submap (absolute ordering) */
1337	<	final Map.Entry<K,V> pollLoEntry() {
1338	<	TreeMap.Entry<K,V> e = loEntry();
1339	<	if (e == null)
1340	<	return null;
1323	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1324	<	m.deleteEntry(e);
1325	<	return result;
1336	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1337	>	if (tooLow(key))
1338	>	return absLowest();
1339	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1340	>	return (e == null || tooHigh(e.key)) ? null : e;
1341		}
1342
1343	<	/** Polls the highest key in this submap (absolute ordering) */
1344	<	final Map.Entry<K,V> pollHiEntry() {
1345	<	TreeMap.Entry<K,V> e = hiEntry();
1346	<	if (e == null)
1347	<	return null;
1333	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1334	<	m.deleteEntry(e);
1335	<	return result;
1343	>	final TreeMap.Entry<K,V> absHigher(K key) {
1344	>	if (tooLow(key))
1345	>	return absLowest();
1346	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1347	>	return (e == null || tooHigh(e.key)) ? null : e;
1348		}
1349
1350	<	/**
1351	<	* Return the absolute high fence for ascending traversal
1352	<	*/
1353	<	final TreeMap.Entry<K,V> hiFence() {
1354	<	if (toEnd)
1343	<	return null;
1344	<	else if (hiExcluded == 0)
1345	<	return m.getHigherEntry(hi);
1346	<	else
1347	<	return m.getCeilingEntry(hi);
1350	>	final TreeMap.Entry<K,V> absFloor(K key) {
1351	>	if (tooHigh(key))
1352	>	return absHighest();
1353	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1354	>	return (e == null || tooLow(e.key)) ? null : e;
1355		}
1356
1357	<	/**
1358	<	* Return the absolute low fence for descending traversal
1359	<	*/
1360	<	final TreeMap.Entry<K,V> loFence() {
1361	<	if (fromStart)
1355	<	return null;
1356	<	else if (loExcluded == 0)
1357	<	return m.getLowerEntry(lo);
1358	<	else
1359	<	return m.getFloorEntry(lo);
1357	>	final TreeMap.Entry<K,V> absLower(K key) {
1358	>	if (tooHigh(key))
1359	>	return absHighest();
1360	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1361	>	return (e == null || tooLow(e.key)) ? null : e;
1362		}
1363
1364	+	/** Returns the absolute high fence for ascending traversal */
1365	+	final TreeMap.Entry<K,V> absHighFence() {
1366	+	return (toEnd ? null : (hiInclusive ?
1367	+	m.getHigherEntry(hi) :
1368	+	m.getCeilingEntry(hi)));
1369	+	}
1370	+
1371	+	/** Return the absolute low fence for descending traversal  */
1372	+	final TreeMap.Entry<K,V> absLowFence() {
1373	+	return (fromStart ? null : (loInclusive ?
1374	+	m.getLowerEntry(lo) :
1375	+	m.getFloorEntry(lo)));
1376	+	}
1377	+
1378	+	// Abstract methods defined in ascending vs descending classes
1379	+	// These relay to the appropriate absolute versions
1380	+
1381	+	abstract TreeMap.Entry<K,V> subLowest();
1382	+	abstract TreeMap.Entry<K,V> subHighest();
1383	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1384	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1385	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1386	+	abstract TreeMap.Entry<K,V> subLower(K key);
1387	+
1388	+	/** Returns ascending iterator from the perspective of this submap */
1389	+	abstract Iterator<K> keyIterator();
1390	+
1391	+	/** Returns descending iterator from the perspective of this submap */
1392	+	abstract Iterator<K> descendingKeyIterator();
1393	+
1394	+	// public methods
1395
1396		public boolean isEmpty() {
1397	<	return entrySet().isEmpty();
1397	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1398		}
1399
1400	<	public boolean containsKey(Object key) {
1401	<	return inRange(key) && m.containsKey(key);
1400	>	public int size() {
1401	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1402		}
1403
1404	<	public V get(Object key) {
1405	<	if (!inRange(key))
1373	<	return null;
1374	<	return m.get(key);
1404	>	public final boolean containsKey(Object key) {
1405	>	return inRange(key) && m.containsKey(key);
1406		}
1407
1408	<	public V put(K key, V value) {
1408	>	public final V put(K key, V value) {
1409		if (!inRange(key))
1410		throw new IllegalArgumentException("key out of range");
1411		return m.put(key, value);
1412		}
1413
1414	<	public V remove(Object key) {
1415	<	if (!inRange(key))
1385	<	return null;
1386	<	return m.remove(key);
1414	>	public final V get(Object key) {
1415	>	return !inRange(key)? null :  m.get(key);
1416		}
1417
1418	<	public Map.Entry<K,V> ceilingEntry(K key) {
1419	<	TreeMap.Entry<K,V> e = subCeiling(key);
1391	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1418	>	public final V remove(Object key) {
1419	>	return !inRange(key)? null  : m.remove(key);
1420		}
1421
1422	<	public K ceilingKey(K key) {
1423	<	TreeMap.Entry<K,V> e = subCeiling(key);
1396	<	return e == null? null : e.key;
1422	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1423	>	return exportEntry(subCeiling(key));
1424		}
1425
1426	<	public Map.Entry<K,V> higherEntry(K key) {
1427	<	TreeMap.Entry<K,V> e = subHigher(key);
1401	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1426	>	public final K ceilingKey(K key) {
1427	>	return keyOrNull(subCeiling(key));
1428		}
1429
1430	<	public K higherKey(K key) {
1431	<	TreeMap.Entry<K,V> e = subHigher(key);
1406	<	return e == null? null : e.key;
1430	>	public final Map.Entry<K,V> higherEntry(K key) {
1431	>	return exportEntry(subHigher(key));
1432		}
1433
1434	<	public Map.Entry<K,V> floorEntry(K key) {
1435	<	TreeMap.Entry<K,V> e = subFloor(key);
1411	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1434	>	public final K higherKey(K key) {
1435	>	return keyOrNull(subHigher(key));
1436		}
1437
1438	<	public K floorKey(K key) {
1439	<	TreeMap.Entry<K,V> e = subFloor(key);
1416	<	return e == null? null : e.key;
1438	>	public final Map.Entry<K,V> floorEntry(K key) {
1439	>	return exportEntry(subFloor(key));
1440		}
1441
1442	<	public Map.Entry<K,V> lowerEntry(K key) {
1443	<	TreeMap.Entry<K,V> e = subLower(key);
1421	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1442	>	public final K floorKey(K key) {
1443	>	return keyOrNull(subFloor(key));
1444		}
1445
1446	<	public K lowerKey(K key) {
1447	<	TreeMap.Entry<K,V> e = subLower(key);
1426	<	return e == null? null : e.key;
1446	>	public final Map.Entry<K,V> lowerEntry(K key) {
1447	>	return exportEntry(subLower(key));
1448		}
1449
1450	<	abstract Iterator<K> keyIterator();
1451	<	abstract Iterator<K> descendingKeyIterator();
1450	>	public final K lowerKey(K key) {
1451	>	return keyOrNull(subLower(key));
1452	>	}
1453
1454	<	public NavigableSet<K> descendingKeySet() {
1455	<	return descendingMap().navigableKeySet();
1454	>	public final K firstKey() {
1455	>	return key(subLowest());
1456	>	}
1457	>
1458	>	public final K lastKey() {
1459	>	return key(subHighest());
1460	>	}
1461	>
1462	>	public final Map.Entry<K,V> firstEntry() {
1463	>	return exportEntry(subLowest());
1464	>	}
1465	>
1466	>	public final Map.Entry<K,V> lastEntry() {
1467	>	return exportEntry(subHighest());
1468	>	}
1469	>
1470	>	public final Map.Entry<K,V> pollFirstEntry() {
1471	>	TreeMap.Entry<K,V> e = subLowest();
1472	>	Map.Entry<K,V> result = exportEntry(e);
1473	>	if (e != null)
1474	>	m.deleteEntry(e);
1475	>	return result;
1476	>	}
1477	>
1478	>	public final Map.Entry<K,V> pollLastEntry() {
1479	>	TreeMap.Entry<K,V> e = subHighest();
1480	>	Map.Entry<K,V> result = exportEntry(e);
1481	>	if (e != null)
1482	>	m.deleteEntry(e);
1483	>	return result;
1484		}
1485
1486		// Views
#	Line 1438 | Line 1488 | public class TreeMap<K,V>
1488		transient EntrySetView entrySetView = null;
1489		transient KeySet<K> navigableKeySetView = null;
1490
1491	+	public final NavigableSet<K> navigableKeySet() {
1492	+	KeySet<K> nksv = navigableKeySetView;
1493	+	return (nksv != null) ? nksv :
1494	+	(navigableKeySetView = new TreeMap.KeySet(this));
1495	+	}
1496	+
1497	+	public final Set<K> keySet() {
1498	+	return navigableKeySet();
1499	+	}
1500	+
1501	+	public NavigableSet<K> descendingKeySet() {
1502	+	return descendingMap().navigableKeySet();
1503	+	}
1504	+
1505	+	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1506	+	return subMap(fromKey, true, toKey, false);
1507	+	}
1508	+
1509	+	public final SortedMap<K,V> headMap(K toKey) {
1510	+	return headMap(toKey, false);
1511	+	}
1512	+
1513	+	public final SortedMap<K,V> tailMap(K fromKey) {
1514	+	return tailMap(fromKey, true);
1515	+	}
1516	+
1517	+	// View classes
1518	+
1519		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1520		private transient int size = -1, sizeModCount;
1521
#	Line 1457 | Line 1535 | public class TreeMap<K,V>
1535		}
1536
1537		public boolean isEmpty() {
1538	<	TreeMap.Entry<K,V> n = loEntry();
1538	>	TreeMap.Entry<K,V> n = absLowest();
1539		return n == null || tooHigh(n.key);
1540		}
1541
#	Line 1489 | Line 1567 | public class TreeMap<K,V>
1567		}
1568		}
1569
1492	–	public NavigableSet<K> navigableKeySet() {
1493	–	KeySet<K> nksv = navigableKeySetView;
1494	–	return (nksv != null) ? nksv :
1495	–	(navigableKeySetView = new TreeMap.KeySet(this));
1496	–	}
1497	–
1498	–	public Set<K> keySet() {
1499	–	return navigableKeySet();
1500	–	}
1501	–
1502	–	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1503	–	return subMap(fromKey, true, toKey, false);
1504	–	}
1505	–
1506	–	public SortedMap<K,V> headMap(K toKey) {
1507	–	return headMap(toKey, false);
1508	–	}
1509	–
1510	–	public SortedMap<K,V> tailMap(K fromKey) {
1511	–	return tailMap(fromKey, true);
1512	–	}
1513	–
1514	–	// The following four definitions are correct only for
1515	–	// ascending submaps. They are overridden in DescendingSubMap.
1516	–	// They are defined in the base class because the definitions
1517	–	// in DescendingSubMap rely on those for AscendingSubMap.
1518	–
1519	–	/**
1520	–	* Returns the entry corresponding to the ceiling of the specified
1521	–	* key from the perspective of this submap, or null if the submap
1522	–	* contains no such entry.
1523	–	*/
1524	–	TreeMap.Entry<K,V> subCeiling(K key) {
1525	–	if (tooLow(key))
1526	–	return loEntry();
1527	–	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1528	–	return (e == null || tooHigh(e.key)) ? null : e;
1529	–	}
1530	–
1531	–	/**
1532	–	* Returns the entry corresponding to the higher of the specified
1533	–	* key from the perspective of this submap, or null if the submap
1534	–	* contains no such entry.
1535	–	*/
1536	–	TreeMap.Entry<K,V> subHigher(K key) {
1537	–	if (tooLow(key))
1538	–	return loEntry();
1539	–	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1540	–	return (e == null || tooHigh(e.key)) ? null : e;
1541	–	}
1542	–
1543	–	/**
1544	–	* Returns the entry corresponding to the floor of the specified
1545	–	* key from the perspective of this submap, or null if the submap
1546	–	* contains no such entry.
1547	–	*/
1548	–	TreeMap.Entry<K,V> subFloor(K key) {
1549	–	if (tooHigh(key))
1550	–	return hiEntry();
1551	–	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1552	–	return (e == null || tooLow(e.key)) ? null : e;
1553	–	}
1554	–
1555	–	/**
1556	–	* Returns the entry corresponding to the lower of the specified
1557	–	* key from the perspective of this submap, or null if the submap
1558	–	* contains no such entry.
1559	–	*/
1560	–	TreeMap.Entry<K,V> subLower(K key) {
1561	–	if (tooHigh(key))
1562	–	return hiEntry();
1563	–	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1564	–	return (e == null || tooLow(e.key)) ? null : e;
1565	–	}
1566	–
1570		/**
1571		* Iterators for SubMaps
1572		*/
1573		abstract class SubMapIterator<T> implements Iterator<T> {
1574		TreeMap.Entry<K,V> lastReturned;
1575		TreeMap.Entry<K,V> next;
1576	<	final K fenceKey;
1576	>	final Object fenceKey;
1577		int expectedModCount;
1578
1579		SubMapIterator(TreeMap.Entry<K,V> first,
#	Line 1578 | Line 1581 | public class TreeMap<K,V>
1581		expectedModCount = m.modCount;
1582		lastReturned = null;
1583		next = first;
1584	<	fenceKey = fence == null ? null : fence.key;
1584	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1585		}
1586
1587		public final boolean hasNext() {
#	Line 1586 | Line 1589 | public class TreeMap<K,V>
1589		}
1590
1591		final TreeMap.Entry<K,V> nextEntry() {
1592	<	TreeMap.Entry<K,V> e = lastReturned = next;
1592	>	TreeMap.Entry<K,V> e = next;
1593		if (e == null || e.key == fenceKey)
1594		throw new NoSuchElementException();
1595		if (m.modCount != expectedModCount)
1596		throw new ConcurrentModificationException();
1597		next = successor(e);
1598	+	lastReturned = e;
1599		return e;
1600		}
1601
1602		final TreeMap.Entry<K,V> prevEntry() {
1603	<	TreeMap.Entry<K,V> e = lastReturned = next;
1603	>	TreeMap.Entry<K,V> e = next;
1604		if (e == null || e.key == fenceKey)
1605		throw new NoSuchElementException();
1606		if (m.modCount != expectedModCount)
1607		throw new ConcurrentModificationException();
1608		next = predecessor(e);
1609	+	lastReturned = e;
1610		return e;
1611		}
1612
1613	<	public void remove() {
1613	>	final void removeAscending() {
1614		if (lastReturned == null)
1615		throw new IllegalStateException();
1616		if (m.modCount != expectedModCount)
1617		throw new ConcurrentModificationException();
1618	+	// deleted entries are replaced by their successors
1619		if (lastReturned.left != null && lastReturned.right != null)
1620		next = lastReturned;
1621		m.deleteEntry(lastReturned);
1616	–	expectedModCount++;
1622		lastReturned = null;
1623	+	expectedModCount = m.modCount;
1624	+	}
1625	+
1626	+	final void removeDescending() {
1627	+	if (lastReturned == null)
1628	+	throw new IllegalStateException();
1629	+	if (m.modCount != expectedModCount)
1630	+	throw new ConcurrentModificationException();
1631	+	m.deleteEntry(lastReturned);
1632	+	lastReturned = null;
1633	+	expectedModCount = m.modCount;
1634		}
1635	+
1636		}
1637
1638		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1626 | Line 1643 | public class TreeMap<K,V>
1643		public Map.Entry<K,V> next() {
1644		return nextEntry();
1645		}
1646	+	public void remove() {
1647	+	removeAscending();
1648	+	}
1649		}
1650
1651		final class SubMapKeyIterator extends SubMapIterator<K> {
#	Line 1636 | Line 1656 | public class TreeMap<K,V>
1656		public K next() {
1657		return nextEntry().key;
1658		}
1659	+	public void remove() {
1660	+	removeAscending();
1661	+	}
1662		}
1663
1664		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1665		DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1666	<	TreeMap.Entry<K,V> lastExcluded) {
1667	<	super(last, lastExcluded);
1666	>	TreeMap.Entry<K,V> fence) {
1667	>	super(last, fence);
1668		}
1669
1670		public Map.Entry<K,V> next() {
1671		return prevEntry();
1672		}
1673	+	public void remove() {
1674	+	removeDescending();
1675	+	}
1676		}
1677
1678		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1679		DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1680	<	TreeMap.Entry<K,V> lastExcluded) {
1681	<	super(last, lastExcluded);
1680	>	TreeMap.Entry<K,V> fence) {
1681	>	super(last, fence);
1682		}
1683		public K next() {
1684		return prevEntry().key;
1685		}
1686	+	public void remove() {
1687	+	removeDescending();
1688	+	}
1689		}
1690		}
1691
1692	<	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1692	>	/**
1693	>	* @serial include
1694	>	*/
1695	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1696		private static final long serialVersionUID = 912986545866124060L;
1697
1698		AscendingSubMap(TreeMap<K,V> m,
1699	<	boolean fromStart, K lo, int loExcluded,
1700	<	boolean toEnd, K hi, int hiExcluded) {
1701	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1699	>	boolean fromStart, K lo, boolean loInclusive,
1700	>	boolean toEnd,     K hi, boolean hiInclusive) {
1701	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1702		}
1703
1704		public Comparator<? super K> comparator() {
#	Line 1674 | Line 1706 | public class TreeMap<K,V>
1706		}
1707
1708		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1709	<	K toKey, boolean toInclusive) {
1709	>	K toKey,   boolean toInclusive) {
1710		if (!inRange(fromKey, fromInclusive))
1711		throw new IllegalArgumentException("fromKey out of range");
1712		if (!inRange(toKey, toInclusive))
1713		throw new IllegalArgumentException("toKey out of range");
1714		return new AscendingSubMap(m,
1715	<	false, fromKey, excluded(fromInclusive),
1716	<	false, toKey,   excluded(toInclusive));
1715	>	false, fromKey, fromInclusive,
1716	>	false, toKey,   toInclusive);
1717		}
1718
1719		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1720	<	if (!inClosedRange(toKey))
1720	>	if (!inRange(toKey, inclusive))
1721		throw new IllegalArgumentException("toKey out of range");
1722		return new AscendingSubMap(m,
1723	<	fromStart, lo,    loExcluded,
1724	<	false,     toKey, excluded(inclusive));
1723	>	fromStart, lo,    loInclusive,
1724	>	false,     toKey, inclusive);
1725		}
1726
1727		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1728		if (!inRange(fromKey, inclusive))
1729		throw new IllegalArgumentException("fromKey out of range");
1730		return new AscendingSubMap(m,
1731	<	false, fromKey, excluded(inclusive),
1732	<	toEnd, hi,      hiExcluded);
1731	>	false, fromKey, inclusive,
1732	>	toEnd, hi,      hiInclusive);
1733	>	}
1734	>
1735	>	public NavigableMap<K,V> descendingMap() {
1736	>	NavigableMap<K,V> mv = descendingMapView;
1737	>	return (mv != null) ? mv :
1738	>	(descendingMapView =
1739	>	new DescendingSubMap(m,
1740	>	fromStart, lo, loInclusive,
1741	>	toEnd,     hi, hiInclusive));
1742		}
1743
1744		Iterator<K> keyIterator() {
1745	<	return new SubMapKeyIterator(loEntry(), hiFence());
1745	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1746		}
1747
1748		Iterator<K> descendingKeyIterator() {
1749	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1749	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1750		}
1751
1752	<	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1752	>	final class AscendingEntrySetView extends EntrySetView {
1753		public Iterator<Map.Entry<K,V>> iterator() {
1754	<	return new SubMapEntryIterator(loEntry(), hiFence());
1754	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1755		}
1756		}
1757
#	Line 1719 | Line 1760 | public class TreeMap<K,V>
1760		return (es != null) ? es : new AscendingEntrySetView();
1761		}
1762
1763	<	public K firstKey() {
1764	<	return key(loEntry());
1765	<	}
1766	<
1767	<	public K lastKey() {
1768	<	return key(hiEntry());
1728	<	}
1729	<
1730	<	public Map.Entry<K,V> firstEntry() {
1731	<	return loEntry();
1732	<	}
1733	<
1734	<	public Map.Entry<K,V> lastEntry() {
1735	<	return hiEntry();
1736	<	}
1737	<
1738	<	public Map.Entry<K,V> pollFirstEntry() {
1739	<	return pollLoEntry();
1740	<	}
1741	<
1742	<	public Map.Entry<K,V> pollLastEntry() {
1743	<	return pollHiEntry();
1744	<	}
1745	<
1746	<	public NavigableMap<K,V> descendingMap() {
1747	<	NavigableMap<K,V> mv = descendingMapView;
1748	<	return (mv != null) ? mv :
1749	<	(descendingMapView =
1750	<	new DescendingSubMap(m,
1751	<	fromStart, lo, loExcluded,
1752	<	toEnd,     hi, hiExcluded));
1753	<	}
1763	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1764	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1765	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1766	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1767	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1768	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1769		}
1770
1771	<	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1771	>	/**
1772	>	* @serial include
1773	>	*/
1774	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1775		private static final long serialVersionUID = 912986545866120460L;
1776		DescendingSubMap(TreeMap<K,V> m,
1777	<	boolean fromStart, K lo, int loExcluded,
1778	<	boolean toEnd, K hi, int hiExcluded) {
1779	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1777	>	boolean fromStart, K lo, boolean loInclusive,
1778	>	boolean toEnd,     K hi, boolean hiInclusive) {
1779	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1780		}
1781
1782		private final Comparator<? super K> reverseComparator =
#	Line 1769 | Line 1787 | public class TreeMap<K,V>
1787		}
1788
1789		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1790	<	K toKey, boolean toInclusive) {
1790	>	K toKey,   boolean toInclusive) {
1791		if (!inRange(fromKey, fromInclusive))
1792		throw new IllegalArgumentException("fromKey out of range");
1793		if (!inRange(toKey, toInclusive))
1794		throw new IllegalArgumentException("toKey out of range");
1795		return new DescendingSubMap(m,
1796	<	false, toKey,   excluded(toInclusive),
1797	<	false, fromKey, excluded(fromInclusive));
1796	>	false, toKey,   toInclusive,
1797	>	false, fromKey, fromInclusive);
1798		}
1799
1800		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1801		if (!inRange(toKey, inclusive))
1802		throw new IllegalArgumentException("toKey out of range");
1803		return new DescendingSubMap(m,
1804	<	false, toKey, excluded(inclusive),
1805	<	toEnd, hi,    hiExcluded);
1804	>	false, toKey, inclusive,
1805	>	toEnd, hi,    hiInclusive);
1806		}
1807
1808		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1809		if (!inRange(fromKey, inclusive))
1810		throw new IllegalArgumentException("fromKey out of range");
1811		return new DescendingSubMap(m,
1812	<	fromStart, lo, loExcluded,
1813	<	false, fromKey, excluded(inclusive));
1796	<	}
1797	<
1798	<	Iterator<K> keyIterator() {
1799	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1800	<	}
1801	<
1802	<	Iterator<K> descendingKeyIterator() {
1803	<	return new SubMapKeyIterator(loEntry(), hiFence());
1804	<	}
1805	<
1806	<	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1807	<	public Iterator<Map.Entry<K,V>> iterator() {
1808	<	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1809	<	}
1810	<	}
1811	<
1812	<	public Set<Map.Entry<K,V>> entrySet() {
1813	<	EntrySetView es = entrySetView;
1814	<	return (es != null) ? es : new DescendingEntrySetView();
1815	<	}
1816	<
1817	<	public K firstKey() {
1818	<	return key(hiEntry());
1819	<	}
1820	<
1821	<	public K lastKey() {
1822	<	return key(loEntry());
1823	<	}
1824	<
1825	<	public Map.Entry<K,V> firstEntry() {
1826	<	return hiEntry();
1827	<	}
1828	<
1829	<	public Map.Entry<K,V> lastEntry() {
1830	<	return loEntry();
1831	<	}
1832	<
1833	<	public Map.Entry<K,V> pollFirstEntry() {
1834	<	return pollHiEntry();
1835	<	}
1836	<
1837	<	public Map.Entry<K,V> pollLastEntry() {
1838	<	return pollLoEntry();
1812	>	fromStart, lo, loInclusive,
1813	>	false, fromKey, inclusive);
1814		}
1815
1816		public NavigableMap<K,V> descendingMap() {
#	Line 1843 | Line 1818 | public class TreeMap<K,V>
1818		return (mv != null) ? mv :
1819		(descendingMapView =
1820		new AscendingSubMap(m,
1821	<	fromStart, lo, loExcluded,
1822	<	toEnd, hi, hiExcluded));
1821	>	fromStart, lo, loInclusive,
1822	>	toEnd,     hi, hiInclusive));
1823		}
1824
1825	<	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1826	<	return super.subFloor(key);
1825	>	Iterator<K> keyIterator() {
1826	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1827		}
1828
1829	<	@Override TreeMap.Entry<K,V> subHigher(K key) {
1830	<	return super.subLower(key);
1829	>	Iterator<K> descendingKeyIterator() {
1830	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1831		}
1832
1833	<	@Override TreeMap.Entry<K,V> subFloor(K key) {
1834	<	return super.subCeiling(key);
1833	>	final class DescendingEntrySetView extends EntrySetView {
1834	>	public Iterator<Map.Entry<K,V>> iterator() {
1835	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1836	>	}
1837		}
1838
1839	<	@Override TreeMap.Entry<K,V> subLower(K key) {
1840	<	return super.subHigher(key);
1839	>	public Set<Map.Entry<K,V>> entrySet() {
1840	>	EntrySetView es = entrySetView;
1841	>	return (es != null) ? es : new DescendingEntrySetView();
1842		}
1865	–	}
1866	–
1867	–	/**
1868	–	* Compares two keys using the correct comparison method for this TreeMap.
1869	–	*/
1870	–	final int compare(Object k1, Object k2) {
1871	–	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1872	–	: comparator.compare((K)k1, (K)k2);
1873	–	}
1843
1844	<	/**
1845	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1846	<	* that it copes with <tt>null</tt> o1 properly.
1847	<	*/
1848	<	final static boolean valEquals(Object o1, Object o2) {
1849	<	return (o1==null ? o2==null : o1.equals(o2));
1844	>	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1845	>	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1846	>	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1847	>	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1848	>	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1849	>	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1850		}
1851
1852		/**
#	Line 1886 | Line 1855 | public class TreeMap<K,V>
1855		* support NavigableMap.  It translates an old-version SubMap into
1856		* a new-version AscendingSubMap. This class is never otherwise
1857		* used.
1858	+	*
1859	+	* @serial include
1860		*/
1861		private class SubMap extends AbstractMap<K,V>
1862	<	implements SortedMap<K,V>, java.io.Serializable {
1862	>	implements SortedMap<K,V>, java.io.Serializable {
1863		private static final long serialVersionUID = -6520786458950516097L;
1864		private boolean fromStart = false, toEnd = false;
1865		private K fromKey, toKey;
1866		private Object readResolve() {
1867		return new AscendingSubMap(TreeMap.this,
1868	<	fromStart, fromKey, 0,
1869	<	toEnd, toKey, 1);
1868	>	fromStart, fromKey, true,
1869	>	toEnd, toKey, false);
1870		}
1871		public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1872		public K lastKey() { throw new InternalError(); }
#	Line 1907 | Line 1878 | public class TreeMap<K,V>
1878		}
1879
1880
1881	+	// Red-black mechanics
1882	+
1883		private static final boolean RED   = false;
1884		private static final boolean BLACK = true;
1885
#	Line 1916 | Line 1889 | public class TreeMap<K,V>
1889		*/
1890
1891		static final class Entry<K,V> implements Map.Entry<K,V> {
1892	<	K key;
1892	>	K key;
1893		V value;
1894		Entry<K,V> left = null;
1895		Entry<K,V> right = null;
#	Line 1967 | Line 1940 | public class TreeMap<K,V>
1940		public boolean equals(Object o) {
1941		if (!(o instanceof Map.Entry))
1942		return false;
1943	<	Map.Entry e = (Map.Entry)o;
1943	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1944
1945		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1946		}
#	Line 2071 | Line 2044 | public class TreeMap<K,V>
2044
2045		private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2046		if (p != null)
2047	<	p.color = c;
2047	>	p.color = c;
2048		}
2049
2050		private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
#	Line 2082 | Line 2055 | public class TreeMap<K,V>
2055		return (p == null) ? null: p.right;
2056		}
2057
2058	<	/** From CLR **/
2058	>	/** From CLR */
2059		private void rotateLeft(Entry<K,V> p) {
2060	<	Entry<K,V> r = p.right;
2061	<	p.right = r.left;
2062	<	if (r.left != null)
2063	<	r.left.parent = p;
2064	<	r.parent = p.parent;
2065	<	if (p.parent == null)
2066	<	root = r;
2067	<	else if (p.parent.left == p)
2068	<	p.parent.left = r;
2069	<	else
2070	<	p.parent.right = r;
2071	<	r.left = p;
2072	<	p.parent = r;
2060	>	if (p != null) {
2061	>	Entry<K,V> r = p.right;
2062	>	p.right = r.left;
2063	>	if (r.left != null)
2064	>	r.left.parent = p;
2065	>	r.parent = p.parent;
2066	>	if (p.parent == null)
2067	>	root = r;
2068	>	else if (p.parent.left == p)
2069	>	p.parent.left = r;
2070	>	else
2071	>	p.parent.right = r;
2072	>	r.left = p;
2073	>	p.parent = r;
2074	>	}
2075		}
2076
2077	<	/** From CLR **/
2077	>	/** From CLR */
2078		private void rotateRight(Entry<K,V> p) {
2079	<	Entry<K,V> l = p.left;
2080	<	p.left = l.right;
2081	<	if (l.right != null) l.right.parent = p;
2082	<	l.parent = p.parent;
2083	<	if (p.parent == null)
2084	<	root = l;
2085	<	else if (p.parent.right == p)
2086	<	p.parent.right = l;
2087	<	else p.parent.left = l;
2088	<	l.right = p;
2089	<	p.parent = l;
2079	>	if (p != null) {
2080	>	Entry<K,V> l = p.left;
2081	>	p.left = l.right;
2082	>	if (l.right != null) l.right.parent = p;
2083	>	l.parent = p.parent;
2084	>	if (p.parent == null)
2085	>	root = l;
2086	>	else if (p.parent.right == p)
2087	>	p.parent.right = l;
2088	>	else p.parent.left = l;
2089	>	l.right = p;
2090	>	p.parent = l;
2091	>	}
2092		}
2093
2094	<
2118	<	/** From CLR **/
2094	>	/** From CLR */
2095		private void fixAfterInsertion(Entry<K,V> x) {
2096		x.color = RED;
2097
#	Line 2134 | Line 2110 | public class TreeMap<K,V>
2110		}
2111		setColor(parentOf(x), BLACK);
2112		setColor(parentOf(parentOf(x)), RED);
2113	<	if (parentOf(parentOf(x)) != null)
2138	<	rotateRight(parentOf(parentOf(x)));
2113	>	rotateRight(parentOf(parentOf(x)));
2114		}
2115		} else {
2116		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2151 | Line 2126 | public class TreeMap<K,V>
2126		}
2127		setColor(parentOf(x), BLACK);
2128		setColor(parentOf(parentOf(x)), RED);
2129	<	if (parentOf(parentOf(x)) != null)
2155	<	rotateLeft(parentOf(parentOf(x)));
2129	>	rotateLeft(parentOf(parentOf(x)));
2130		}
2131		}
2132		}
#	Line 2162 | Line 2136 | public class TreeMap<K,V>
2136		/**
2137		* Delete node p, and then rebalance the tree.
2138		*/
2165	–
2139		private void deleteEntry(Entry<K,V> p) {
2140	<	decrementSize();
2140	>	modCount++;
2141	>	size--;
2142
2143		// If strictly internal, copy successor's element to p and then make p
2144		// point to successor.
#	Line 2210 | Line 2184 | public class TreeMap<K,V>
2184		}
2185		}
2186
2187	<	/** From CLR **/
2187	>	/** From CLR */
2188		private void fixAfterDeletion(Entry<K,V> x) {
2189		while (x != root && colorOf(x) == BLACK) {
2190		if (x == leftOf(parentOf(x))) {
#	Line 2318 | Line 2292 | public class TreeMap<K,V>
2292		buildFromSorted(size, null, s, null);
2293		}
2294
2295	<	/** Intended to be called only from TreeSet.readObject **/
2295	>	/** Intended to be called only from TreeSet.readObject */
2296		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2297		throws java.io.IOException, ClassNotFoundException {
2298		buildFromSorted(size, null, s, defaultVal);
2299		}
2300
2301	<	/** Intended to be called only from TreeSet.addAll **/
2301	>	/** Intended to be called only from TreeSet.addAll */
2302		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2303	<	try {
2304	<	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2305	<	} catch (java.io.IOException cannotHappen) {
2306	<	} catch (ClassNotFoundException cannotHappen) {
2307	<	}
2303	>	try {
2304	>	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2305	>	} catch (java.io.IOException cannotHappen) {
2306	>	} catch (ClassNotFoundException cannotHappen) {
2307	>	}
2308		}
2309
2310
#	Line 2365 | Line 2339 | public class TreeMap<K,V>
2339		*         This cannot occur if str is null.
2340		*/
2341		private void buildFromSorted(int size, Iterator it,
2342	<	java.io.ObjectInputStream str,
2343	<	V defaultVal)
2342	>	java.io.ObjectInputStream str,
2343	>	V defaultVal)
2344		throws  java.io.IOException, ClassNotFoundException {
2345		this.size = size;
2346		root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2347	<	it, str, defaultVal);
2347	>	it, str, defaultVal);
2348		}
2349
2350		/**
#	Line 2388 | Line 2362 | public class TreeMap<K,V>
2362		*        Must be equal to computeRedLevel for tree of this size.
2363		*/
2364		private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2365	<	int redLevel,
2366	<	Iterator it,
2367	<	java.io.ObjectInputStream str,
2368	<	V defaultVal)
2365	>	int redLevel,
2366	>	Iterator it,
2367	>	java.io.ObjectInputStream str,
2368	>	V defaultVal)
2369		throws  java.io.IOException, ClassNotFoundException {
2370		/*
2371		* Strategy: The root is the middlemost element. To get to it, we
#	Line 2407 | Line 2381 | public class TreeMap<K,V>
2381
2382		if (hi < lo) return null;
2383
2384	<	int mid = (lo + hi) / 2;
2384	>	int mid = (lo + hi) >>> 1;
2385
2386		Entry<K,V> left  = null;
2387		if (lo < mid)
2388		left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2389	<	it, str, defaultVal);
2389	>	it, str, defaultVal);
2390
2391		// extract key and/or value from iterator or stream
2392		K key;
#	Line 2444 | Line 2418 | public class TreeMap<K,V>
2418
2419		if (mid < hi) {
2420		Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2421	<	it, str, defaultVal);
2421	>	it, str, defaultVal);
2422		middle.right = right;
2423		right.parent = middle;
2424		}

Diff Legend

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