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.31 by dl, Fri Apr 21 13:42:57 2006 UTC

#	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 109 | Line 109 | public class TreeMap<K,V>
109		*/
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	–
112		private void incrementSize()   { modCount++; size++; }
113		private void decrementSize()   { modCount++; size--; }
114
#	Line 134 | Line 125 | public class TreeMap<K,V>
125		* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128	+	comparator = null;
129		}
130
131		/**
#	Line 169 | Line 161 | public class TreeMap<K,V>
161		* @throws NullPointerException if the specified map is null
162		*/
163		public TreeMap(Map<? extends K, ? extends V> m) {
164	+	comparator = null;
165		putAll(m);
166		}
167
#	Line 235 | Line 228 | public class TreeMap<K,V>
228		public boolean containsValue(Object value) {
229		return (root==null ? false :
230		(value==null ? valueSearchNull(root)
231	<	: valueSearchNonNull(root, value)));
231	>	: valueSearchNonNull(root, value)));
232		}
233
234		private boolean valueSearchNull(Entry n) {
#	Line 244 | Line 237 | public class TreeMap<K,V>
237
238		// Check left and right subtrees for value
239		return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
240	>	(n.right != null && valueSearchNull(n.right));
241		}
242
243		private boolean valueSearchNonNull(Entry n, Object value) {
#	Line 254 | Line 247 | public class TreeMap<K,V>
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));
250	>	(n.right != null && valueSearchNonNull(n.right, value));
251		}
252
253		/**
#	Line 344 | Line 337 | public class TreeMap<K,V>
337		*         and this map uses natural ordering, or its comparator
338		*         does not permit null keys
339		*/
340	<	private Entry<K,V> getEntry(Object key) {
340	>	final Entry<K,V> getEntry(Object key) {
341		// Offload comparator-based version for sake of performance
342		if (comparator != null)
343		return getEntryUsingComparator(key);
#	Line 368 | Line 361 | public class TreeMap<K,V>
361		* Version of getEntry using comparator. Split off from getEntry
362		* for performance. (This is not worth doing for most methods,
363		* that are less dependent on comparator performance, but is
364	<	* worthwhile here.)
364	>	* worthwhile for get and put.)
365		*/
366	<	private Entry<K,V> getEntryUsingComparator(Object key) {
366	>	final Entry<K,V> getEntryUsingComparator(Object key) {
367		K k = (K) key;
368		Comparator<? super K> cpr = comparator;
369		Entry<K,V> p = root;
#	Line 392 | Line 385 | public class TreeMap<K,V>
385		* key; if no such entry exists (i.e., the greatest key in the Tree is less
386		* than the specified key), returns <tt>null</tt>.
387		*/
388	<	private Entry<K,V> getCeilingEntry(K key) {
388	>	final Entry<K,V> getCeilingEntry(K key) {
389		Entry<K,V> p = root;
390	<	if (p==null)
398	<	return null;
399	<
400	<	while (true) {
390	>	while (p != null) {
391		int cmp = compare(key, p.key);
392		if (cmp < 0) {
393		if (p.left != null)
#	Line 419 | Line 409 | public class TreeMap<K,V>
409		} else
410		return p;
411		}
412	+	return null;
413		}
414
415		/**
#	Line 426 | Line 417 | public class TreeMap<K,V>
417		* exists, returns the entry for the greatest key less than the specified
418		* key; if no such entry exists, returns <tt>null</tt>.
419		*/
420	<	private Entry<K,V> getFloorEntry(K key) {
420	>	final Entry<K,V> getFloorEntry(K key) {
421		Entry<K,V> p = root;
422	<	if (p==null)
432	<	return null;
433	<
434	<	while (true) {
422	>	while (p != null) {
423		int cmp = compare(key, p.key);
424		if (cmp > 0) {
425		if (p.right != null)
#	Line 454 | Line 442 | public class TreeMap<K,V>
442		return p;
443
444		}
445	+	return null;
446		}
447
448		/**
#	Line 462 | Line 451 | public class TreeMap<K,V>
451		* key greater than the specified key; if no such entry exists
452		* returns <tt>null</tt>.
453		*/
454	<	private Entry<K,V> getHigherEntry(K key) {
454	>	final Entry<K,V> getHigherEntry(K key) {
455		Entry<K,V> p = root;
456	<	if (p==null)
468	<	return null;
469	<
470	<	while (true) {
456	>	while (p != null) {
457		int cmp = compare(key, p.key);
458		if (cmp < 0) {
459		if (p.left != null)
#	Line 488 | Line 474 | public class TreeMap<K,V>
474		}
475		}
476		}
477	+	return null;
478		}
479
480		/**
#	Line 495 | Line 482 | public class TreeMap<K,V>
482		* no such entry exists (i.e., the least key in the Tree is greater than
483		* the specified key), returns <tt>null</tt>.
484		*/
485	<	private Entry<K,V> getLowerEntry(K key) {
485	>	final Entry<K,V> getLowerEntry(K key) {
486		Entry<K,V> p = root;
487	<	if (p==null)
501	<	return null;
502	<
503	<	while (true) {
487	>	while (p != null) {
488		int cmp = compare(key, p.key);
489		if (cmp > 0) {
490		if (p.right != null)
#	Line 521 | Line 505 | public class TreeMap<K,V>
505		}
506		}
507		}
508	+	return null;
509		}
510
511		/**
512		* Returns the key corresponding to the specified Entry.
513		* @throws NoSuchElementException if the Entry is null
514		*/
515	<	private static <K> K key(Entry<K,?> e) {
515	>	static <K> K key(Entry<K,?> e) {
516		if (e==null)
517		throw new NoSuchElementException();
518		return e.key;
#	Line 552 | Line 537 | public class TreeMap<K,V>
537		*         does not permit null keys
538		*/
539		public V put(K key, V value) {
540	<	Entry<K,V> t = root;
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
547	<	if (t == null) {
548	<	// TBD
549	<	//             if (key == null) {
550	<	//                 if (comparator == null)
551	<	//                     throw new NullPointerException();
552	<	//                 comparator.compare(key, key);
553	<	//             }
554	<	incrementSize();
555	<	root = new Entry<K,V>(key, value, null);
556	<	return null;
547	>	Entry<K,V> t = root;
548	>	while (t != null) {
549	>	int cmp = k.compareTo(t.key);
550	>	if (cmp == 0) {
551	>	return t.setValue(value);
552	>	} else if (cmp < 0) {
553	>	if (t.left != null) {
554	>	t = t.left;
555	>	} 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) {
562	>	t = t.right;
563	>	} else {
564	>	incrementSize();
565	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	>	return null;
567	>	}
568	>	}
569		}
570	+	incrementSize();
571	+	root = new Entry<K,V>(key, value, null);
572	+	return null;
573	+	}
574
575	<	while (true) {
576	<	int cmp = compare(key, t.key);
575	>	/**
576	>	* Version of put using comparator. Split off from put for
577	>	* 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) {
#	Line 575 | Line 588 | public class TreeMap<K,V>
588		t = t.left;
589		} else {
590		incrementSize();
591	<	t.left = new Entry<K,V>(key, value, t);
579	<	fixAfterInsertion(t.left);
591	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592		return null;
593		}
594		} else { // cmp > 0
#	Line 584 | Line 596 | public class TreeMap<K,V>
596		t = t.right;
597		} else {
598		incrementSize();
599	<	t.right = new Entry<K,V>(key, value, t);
588	<	fixAfterInsertion(t.right);
599	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600		return null;
601		}
602		}
603		}
604	+	cpr.compare(key, key); // type check
605	+	incrementSize();
606	+	root = new Entry<K,V>(key, value, null);
607	+	return null;
608		}
609
610		/**
#	Line 803 | Line 818 | public class TreeMap<K,V>
818		* the first time this view is requested.  Views are stateless, so
819		* there's no reason to create more than one.
820		*/
821	<	private transient Set<Map.Entry<K,V>> entrySet = null;
821	>	private transient EntrySet entrySet = null;
822		private transient KeySet<K> navigableKeySet = null;
823		private transient NavigableMap<K,V> descendingMap = null;
824
#	Line 829 | Line 844 | public class TreeMap<K,V>
844		* @since 1.6
845		*/
846		public NavigableSet<K> navigableKeySet() {
847	<	NavigableSet<K> nks = navigableKeySet;
847	>	KeySet<K> nks = navigableKeySet;
848		return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
849		}
850
#	Line 876 | Line 891 | public class TreeMap<K,V>
891		* <tt>add</tt> or <tt>addAll</tt> operations.
892		*/
893		public Set<Map.Entry<K,V>> entrySet() {
894	<	Set<Map.Entry<K,V>> es = entrySet;
894	>	EntrySet es = entrySet;
895		return (es != null) ? es : (entrySet = new EntrySet());
896		}
897
#	Line 886 | Line 901 | public class TreeMap<K,V>
901		public NavigableMap<K, V> descendingMap() {
902		NavigableMap<K, V> km = descendingMap;
903		return (km != null) ? km :
904	<	(descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
905	<	(K)UNBOUNDED, 0));
904	>	(descendingMap = new DescendingSubMap(this,
905	>	true, null, 0,
906	>	true, null, 0));
907		}
908
909		/**
#	Line 898 | Line 914 | public class TreeMap<K,V>
914		* @throws IllegalArgumentException {@inheritDoc}
915		* @since 1.6
916		*/
917	<	public NavigableMap<K,V> navigableSubMap(K fromKey, boolean fromInclusive,
918	<	K toKey,   boolean toInclusive) {
919	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
920	<	toKey,   excluded(toInclusive));
917	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
918	>	K toKey,   boolean toInclusive) {
919	>	return new AscendingSubMap(this,
920	>	false, fromKey, excluded(fromInclusive),
921	>	false, toKey,   excluded(toInclusive));
922		}
923
924		/**
#	Line 912 | Line 929 | public class TreeMap<K,V>
929		* @throws IllegalArgumentException {@inheritDoc}
930		* @since 1.6
931		*/
932	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
933	<	return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
932	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
933	>	return new AscendingSubMap(this,
934	>	true,  null,  0,
935	>	false, toKey, excluded(inclusive));
936		}
937
938		/**
#	Line 924 | Line 943 | public class TreeMap<K,V>
943		* @throws IllegalArgumentException {@inheritDoc}
944		* @since 1.6
945		*/
946	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive) {
947	<	return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 0);
946	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
947	>	return new AscendingSubMap(this,
948	>	false, fromKey, excluded(inclusive),
949	>	true,  null,    0);
950		}
951
952		/**
#	Line 944 | Line 965 | public class TreeMap<K,V>
965		* @throws IllegalArgumentException {@inheritDoc}
966		*/
967		public SortedMap<K,V> subMap(K fromKey, K toKey) {
968	<	return navigableSubMap(fromKey, true, toKey, false);
968	>	return subMap(fromKey, true, toKey, false);
969		}
970
971		/**
#	Line 955 | Line 976 | public class TreeMap<K,V>
976		* @throws IllegalArgumentException {@inheritDoc}
977		*/
978		public SortedMap<K,V> headMap(K toKey) {
979	<	return navigableHeadMap(toKey, false);
979	>	return headMap(toKey, false);
980		}
981
982		/**
#	Line 966 | Line 987 | public class TreeMap<K,V>
987		* @throws IllegalArgumentException {@inheritDoc}
988		*/
989		public SortedMap<K,V> tailMap(K fromKey) {
990	<	return navigableTailMap(fromKey, true);
990	>	return tailMap(fromKey, true);
991		}
992
993		// View class support
#	Line 1096 | Line 1117 | public class TreeMap<K,V>
1117		m.remove(o);
1118		return size() != oldSize;
1119		}
1120	<	public NavigableSet<E> navigableSubSet(E fromElement,
1121	<	boolean fromInclusive,
1122	<	E toElement,
1123	<	boolean toInclusive) {
1103	<	return new TreeSet<E>
1104	<	(m.navigableSubMap(fromElement, fromInclusive,
1105	<	toElement,   toInclusive));
1120	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1121	>	E toElement, boolean toInclusive) {
1122	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1123	>	toElement,   toInclusive));
1124		}
1125	<	public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
1126	<	return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
1125	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1126	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1127		}
1128	<	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
1129	<	return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
1128	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1129	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1130		}
1131		public SortedSet<E> subSet(E fromElement, E toElement) {
1132	<	return navigableSubSet(fromElement, true, toElement, false);
1132	>	return subSet(fromElement, true, toElement, false);
1133		}
1134		public SortedSet<E> headSet(E toElement) {
1135	<	return navigableHeadSet(toElement, false);
1135	>	return headSet(toElement, false);
1136		}
1137		public SortedSet<E> tailSet(E fromElement) {
1138	<	return navigableTailSet(fromElement, true);
1138	>	return tailSet(fromElement, true);
1139		}
1140		public NavigableSet<E> descendingSet() {
1141		return new TreeSet(m.descendingMap());
1142		}
1143		}
1144
1145	+	/**
1146	+	* Base class for TreeMap Iterators
1147	+	*/
1148	+	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1149	+	Entry<K,V> next;
1150	+	Entry<K,V> lastReturned;
1151	+	int expectedModCount;
1152	+
1153	+	PrivateEntryIterator(Entry<K,V> first) {
1154	+	expectedModCount = modCount;
1155	+	lastReturned = null;
1156	+	next = first;
1157	+	}
1158	+
1159	+	public final boolean hasNext() {
1160	+	return next != null;
1161	+	}
1162	+
1163	+	final Entry<K,V> nextEntry() {
1164	+	Entry<K,V> e = lastReturned = next;
1165	+	if (e == null)
1166	+	throw new NoSuchElementException();
1167	+	if (modCount != expectedModCount)
1168	+	throw new ConcurrentModificationException();
1169	+	next = successor(e);
1170	+	return e;
1171	+	}
1172	+
1173	+	final Entry<K,V> prevEntry() {
1174	+	Entry<K,V> e = lastReturned= next;
1175	+	if (e == null)
1176	+	throw new NoSuchElementException();
1177	+	if (modCount != expectedModCount)
1178	+	throw new ConcurrentModificationException();
1179	+	next = predecessor(e);
1180	+	return e;
1181	+	}
1182	+
1183	+	public void remove() {
1184	+	if (lastReturned == null)
1185	+	throw new IllegalStateException();
1186	+	if (modCount != expectedModCount)
1187	+	throw new ConcurrentModificationException();
1188	+	if (lastReturned.left != null && lastReturned.right != null)
1189	+	next = lastReturned;
1190	+	deleteEntry(lastReturned);
1191	+	expectedModCount++;
1192	+	lastReturned = null;
1193	+	}
1194	+	}
1195	+
1196	+	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1197	+	EntryIterator(Entry<K,V> first) {
1198	+	super(first);
1199	+	}
1200	+	public Map.Entry<K,V> next() {
1201	+	return nextEntry();
1202	+	}
1203	+	}
1204	+
1205	+	final class ValueIterator extends PrivateEntryIterator<V> {
1206	+	ValueIterator(Entry<K,V> first) {
1207	+	super(first);
1208	+	}
1209	+	public V next() {
1210	+	return nextEntry().value;
1211	+	}
1212	+	}
1213	+
1214	+	final class KeyIterator extends PrivateEntryIterator<K> {
1215	+	KeyIterator(Entry<K,V> first) {
1216	+	super(first);
1217	+	}
1218	+	public K next() {
1219	+	return nextEntry().key;
1220	+	}
1221	+	}
1222	+
1223	+	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1224	+	DescendingKeyIterator(Entry<K,V> first) {
1225	+	super(first);
1226	+	}
1227	+	public K next() {
1228	+	return prevEntry().key;
1229	+	}
1230	+	}
1231	+
1232		// SubMaps
1233
1234	<	abstract class NavigableSubMap extends AbstractMap<K,V>
1234	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1235		implements NavigableMap<K,V>, java.io.Serializable {
1236
1237	<	/**
1238	<	* 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.
1237	>	/*
1238	>	* The backing map.
1239		*/
1240	<	int loExcluded;
1240	>	final TreeMap<K,V> m;
1241
1242	<	/**
1243	<	* The high endpoint of this submap in absolute terms.  For ascending
1244	<	* submaps this will be the "last" endpoint; for descending submaps,
1245	<	* the first.  If there is no bound, this field is set to UNBOUNDED.
1242	>	/*
1243	>	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1244	>	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1245	>	* the low (absolute) bound is the start of the backing map, and the
1246	>	* other values are ignored. Otherwise, if loExcluded is
1247	>	* zero, lo is the inclusive bound, else loExcluded is one,
1248	>	* and lo is the exclusive bound. Similarly for the upper bound.
1249		*/
1150	–	K hi;
1250
1251	<	/**
1252	<	* Zero if the high endpoint is excluded from this submap, one if
1253	<	* it's included.  This field is unused if hi is UNBOUNDED.
1254	<	*/
1255	<	int hiExcluded;
1251	>	final K lo, hi;
1252	>	final boolean fromStart, toEnd;
1253	>	final int loExcluded, hiExcluded;
1254	>
1255	>	NavigableSubMap(TreeMap<K,V> m,
1256	>	boolean fromStart, K lo, int loExcluded,
1257	>	boolean toEnd,     K hi, int hiExcluded) {
1258	>	if (!fromStart && !toEnd) {
1259	>	if (m.compare(lo, hi) > 0)
1260	>	throw new IllegalArgumentException("fromKey > toKey");
1261	>	}
1262	>	else if (!fromStart) // type check
1263	>	m.compare(lo, lo);
1264	>	else if (!toEnd)
1265	>	m.compare(hi, hi);
1266
1267	<	NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1268	<	if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
1160	<	throw new IllegalArgumentException("fromKey > toKey");
1267	>	this.m = m;
1268	>	this.fromStart = fromStart;
1269		this.lo = lo;
1270		this.loExcluded = loExcluded;
1271	+	this.toEnd = toEnd;
1272		this.hi = hi;
1273		this.hiExcluded = hiExcluded;
1274		}
1275
1276	+	// internal utilities
1277	+
1278	+	final boolean inRange(Object key) {
1279	+	return (fromStart || m.compare(key, lo) >= loExcluded)
1280	+	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1281	+	}
1282	+
1283	+	final boolean inClosedRange(Object key) {
1284	+	return (fromStart || m.compare(key, lo) >= 0)
1285	+	&& (toEnd || m.compare(hi, key) >= 0);
1286	+	}
1287	+
1288	+	final boolean inRange(Object key, boolean inclusive) {
1289	+	return inclusive ? inRange(key) : inClosedRange(key);
1290	+	}
1291	+
1292	+	final boolean tooLow(K key) {
1293	+	return !fromStart && m.compare(key, lo) < loExcluded;
1294	+	}
1295	+
1296	+	final boolean tooHigh(K key) {
1297	+	return !toEnd && m.compare(hi, key) < hiExcluded;
1298	+	}
1299	+
1300	+	/** Returns the lowest entry in this submap (absolute ordering) */
1301	+	final TreeMap.Entry<K,V> loEntry() {
1302	+	TreeMap.Entry<K,V> result =
1303	+	(fromStart ?  m.getFirstEntry() :
1304	+	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1305	+	m.getHigherEntry(lo)));
1306	+	return (result == null || tooHigh(result.key)) ? null : result;
1307	+	}
1308	+
1309	+	/** Returns the highest key in this submap (absolute ordering) */
1310	+	final TreeMap.Entry<K,V> hiEntry() {
1311	+	TreeMap.Entry<K,V> result =
1312	+	(toEnd ?  m.getLastEntry() :
1313	+	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1314	+	m.getLowerEntry(hi)));
1315	+	return (result == null || tooLow(result.key)) ? null : result;
1316	+	}
1317	+
1318	+	/** Polls the lowest entry in this submap (absolute ordering) */
1319	+	final Map.Entry<K,V> pollLoEntry() {
1320	+	TreeMap.Entry<K,V> e = loEntry();
1321	+	if (e == null)
1322	+	return null;
1323	+	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1324	+	m.deleteEntry(e);
1325	+	return result;
1326	+	}
1327	+
1328	+	/** Polls the highest key in this submap (absolute ordering) */
1329	+	final Map.Entry<K,V> pollHiEntry() {
1330	+	TreeMap.Entry<K,V> e = hiEntry();
1331	+	if (e == null)
1332	+	return null;
1333	+	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1334	+	m.deleteEntry(e);
1335	+	return result;
1336	+	}
1337	+
1338	+	/**
1339	+	* Return the absolute high fence for ascending traversal
1340	+	*/
1341	+	final TreeMap.Entry<K,V> hiFence() {
1342	+	if (toEnd)
1343	+	return null;
1344	+	else if (hiExcluded == 0)
1345	+	return m.getHigherEntry(hi);
1346	+	else
1347	+	return m.getCeilingEntry(hi);
1348	+	}
1349	+
1350	+	/**
1351	+	* Return the absolute low fence for descending traversal
1352	+	*/
1353	+	final TreeMap.Entry<K,V> loFence() {
1354	+	if (fromStart)
1355	+	return null;
1356	+	else if (loExcluded == 0)
1357	+	return m.getLowerEntry(lo);
1358	+	else
1359	+	return m.getFloorEntry(lo);
1360	+	}
1361	+
1362	+
1363		public boolean isEmpty() {
1364		return entrySet().isEmpty();
1365		}
1366
1367		public boolean containsKey(Object key) {
1368	<	return inRange(key) && TreeMap.this.containsKey(key);
1368	>	return inRange(key) && m.containsKey(key);
1369		}
1370
1371		public V get(Object key) {
1372		if (!inRange(key))
1373		return null;
1374	<	return TreeMap.this.get(key);
1374	>	return m.get(key);
1375		}
1376
1377		public V put(K key, V value) {
1378		if (!inRange(key))
1379		throw new IllegalArgumentException("key out of range");
1380	<	return TreeMap.this.put(key, value);
1380	>	return m.put(key, value);
1381		}
1382
1383		public V remove(Object key) {
1384		if (!inRange(key))
1385		return null;
1386	<	return TreeMap.this.remove(key);
1386	>	return m.remove(key);
1387		}
1388
1389		public Map.Entry<K,V> ceilingEntry(K key) {
#	Line 1239 | Line 1435 | public class TreeMap<K,V>
1435
1436		// Views
1437		transient NavigableMap<K,V> descendingMapView = null;
1438	<	transient Set<Map.Entry<K,V>> entrySetView = null;
1439	<	private transient NavigableSet<K> navigableKeySetView = null;
1438	>	transient EntrySetView entrySetView = null;
1439	>	transient KeySet<K> navigableKeySetView = null;
1440
1441		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1442		private transient int size = -1, sizeModCount;
1443
1444		public int size() {
1445	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1446	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1445	>	if (fromStart && toEnd)
1446	>	return m.size();
1447	>	if (size == -1 || sizeModCount != m.modCount) {
1448	>	sizeModCount = m.modCount;
1449	>	size = 0;
1450		Iterator i = iterator();
1451		while (i.hasNext()) {
1452		size++;
#	Line 1258 | Line 1457 | public class TreeMap<K,V>
1457		}
1458
1459		public boolean isEmpty() {
1460	<	return !iterator().hasNext();
1460	>	TreeMap.Entry<K,V> n = loEntry();
1461	>	return n == null || tooHigh(n.key);
1462		}
1463
1464		public boolean contains(Object o) {
#	Line 1268 | Line 1468 | public class TreeMap<K,V>
1468		K key = entry.getKey();
1469		if (!inRange(key))
1470		return false;
1471	<	TreeMap.Entry node = getEntry(key);
1471	>	TreeMap.Entry node = m.getEntry(key);
1472		return node != null &&
1473	<	valEquals(node.getValue(), entry.getValue());
1473	>	valEquals(node.getValue(), entry.getValue());
1474		}
1475
1476		public boolean remove(Object o) {
#	Line 1280 | Line 1480 | public class TreeMap<K,V>
1480		K key = entry.getKey();
1481		if (!inRange(key))
1482		return false;
1483	<	TreeMap.Entry<K,V> node = getEntry(key);
1483	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1484		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1485	<	deleteEntry(node);
1485	>	m.deleteEntry(node);
1486		return true;
1487		}
1488		return false;
#	Line 1290 | Line 1490 | public class TreeMap<K,V>
1490		}
1491
1492		public NavigableSet<K> navigableKeySet() {
1493	<	NavigableSet<K> nksv = navigableKeySetView;
1493	>	KeySet<K> nksv = navigableKeySetView;
1494		return (nksv != null) ? nksv :
1495		(navigableKeySetView = new TreeMap.KeySet(this));
1496		}
#	Line 1300 | Line 1500 | public class TreeMap<K,V>
1500		}
1501
1502		public SortedMap<K,V> subMap(K fromKey, K toKey) {
1503	<	return navigableSubMap(fromKey, true, toKey, false);
1503	>	return subMap(fromKey, true, toKey, false);
1504		}
1505
1506		public SortedMap<K,V> headMap(K toKey) {
1507	<	return navigableHeadMap(toKey, false);
1507	>	return headMap(toKey, false);
1508		}
1509
1510		public SortedMap<K,V> tailMap(K fromKey) {
1511	<	return navigableTailMap(fromKey, true);
1312	<	}
1313	<
1314	<	/** Returns the lowest entry in this submap (absolute ordering) */
1315	<	TreeMap.Entry<K,V> loEntry() {
1316	<	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;
1320	<	}
1321	<
1322	<	/** Returns the highest key in this submap (absolute ordering) */
1323	<	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;
1328	<	}
1329	<
1330	<	/** Polls the lowest entry in this submap (absolute ordering) */
1331	<	Map.Entry<K,V> pollLoEntry() {
1332	<	TreeMap.Entry<K,V> e =
1333	<	((lo == UNBOUNDED) ? getFirstEntry() :
1334	<	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1335	<	if (e == null || tooHigh(e.key))
1336	<	return null;
1337	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1338	<	deleteEntry(e);
1339	<	return result;
1340	<	}
1341	<
1342	<	/** Polls the highest key in this submap (absolute ordering) */
1343	<	Map.Entry<K,V> pollHiEntry() {
1344	<	TreeMap.Entry<K,V> e =
1345	<	((hi == UNBOUNDED) ? getLastEntry() :
1346	<	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1347	<	if (e == null || tooLow(e.key))
1348	<	return null;
1349	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1350	<	deleteEntry(e);
1351	<	return result;
1511	>	return tailMap(fromKey, true);
1512		}
1513
1514		// The following four definitions are correct only for
#	Line 1364 | Line 1524 | public class TreeMap<K,V>
1524		TreeMap.Entry<K,V> subCeiling(K key) {
1525		if (tooLow(key))
1526		return loEntry();
1527	<	TreeMap.Entry<K,V> e = getCeilingEntry(key);
1527	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1528		return (e == null || tooHigh(e.key)) ? null : e;
1529		}
1530
#	Line 1376 | Line 1536 | public class TreeMap<K,V>
1536		TreeMap.Entry<K,V> subHigher(K key) {
1537		if (tooLow(key))
1538		return loEntry();
1539	<	TreeMap.Entry<K,V> e = getHigherEntry(key);
1539	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1540		return (e == null || tooHigh(e.key)) ? null : e;
1541		}
1542
#	Line 1388 | Line 1548 | public class TreeMap<K,V>
1548		TreeMap.Entry<K,V> subFloor(K key) {
1549		if (tooHigh(key))
1550		return hiEntry();
1551	<	TreeMap.Entry<K,V> e = getFloorEntry(key);
1551	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1552		return (e == null || tooLow(e.key)) ? null : e;
1553		}
1554
#	Line 1400 | Line 1560 | public class TreeMap<K,V>
1560		TreeMap.Entry<K,V> subLower(K key) {
1561		if (tooHigh(key))
1562		return hiEntry();
1563	<	TreeMap.Entry<K,V> e = getLowerEntry(key);
1563	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1564		return (e == null || tooLow(e.key)) ? null : e;
1565		}
1566
1567	<	boolean inRange(Object key) {
1568	<	return (lo == UNBOUNDED || compare(key, lo) >= loExcluded)
1569	<	&& (hi == UNBOUNDED || compare(hi, key) >= hiExcluded);
1567	>	/**
1568	>	* Iterators for SubMaps
1569	>	*/
1570	>	abstract class SubMapIterator<T> implements Iterator<T> {
1571	>	TreeMap.Entry<K,V> lastReturned;
1572	>	TreeMap.Entry<K,V> next;
1573	>	final K fenceKey;
1574	>	int expectedModCount;
1575	>
1576	>	SubMapIterator(TreeMap.Entry<K,V> first,
1577	>	TreeMap.Entry<K,V> fence) {
1578	>	expectedModCount = m.modCount;
1579	>	lastReturned = null;
1580	>	next = first;
1581	>	fenceKey = fence == null ? null : fence.key;
1582	>	}
1583	>
1584	>	public final boolean hasNext() {
1585	>	return next != null && next.key != fenceKey;
1586	>	}
1587	>
1588	>	final TreeMap.Entry<K,V> nextEntry() {
1589	>	TreeMap.Entry<K,V> e = lastReturned = next;
1590	>	if (e == null || e.key == fenceKey)
1591	>	throw new NoSuchElementException();
1592	>	if (m.modCount != expectedModCount)
1593	>	throw new ConcurrentModificationException();
1594	>	next = successor(e);
1595	>	return e;
1596	>	}
1597	>
1598	>	final TreeMap.Entry<K,V> prevEntry() {
1599	>	TreeMap.Entry<K,V> e = lastReturned = next;
1600	>	if (e == null || e.key == fenceKey)
1601	>	throw new NoSuchElementException();
1602	>	if (m.modCount != expectedModCount)
1603	>	throw new ConcurrentModificationException();
1604	>	next = predecessor(e);
1605	>	return e;
1606	>	}
1607	>
1608	>	public void remove() {
1609	>	if (lastReturned == null)
1610	>	throw new IllegalStateException();
1611	>	if (m.modCount != expectedModCount)
1612	>	throw new ConcurrentModificationException();
1613	>	if (lastReturned.left != null && lastReturned.right != null)
1614	>	next = lastReturned;
1615	>	m.deleteEntry(lastReturned);
1616	>	expectedModCount++;
1617	>	lastReturned = null;
1618	>	}
1619		}
1620
1621	<	boolean inClosedRange(Object key) {
1622	<	return (lo == UNBOUNDED || compare(key, lo) >= 0)
1623	<	&& (hi == UNBOUNDED || compare(hi, key) >= 0);
1621	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1622	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1623	>	TreeMap.Entry<K,V> fence) {
1624	>	super(first, fence);
1625	>	}
1626	>	public Map.Entry<K,V> next() {
1627	>	return nextEntry();
1628	>	}
1629		}
1630
1631	<	boolean inRange(Object key, boolean inclusive) {
1632	<	return inclusive ? inRange(key) : inClosedRange(key);
1631	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1632	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1633	>	TreeMap.Entry<K,V> fence) {
1634	>	super(first, fence);
1635	>	}
1636	>	public K next() {
1637	>	return nextEntry().key;
1638	>	}
1639		}
1640
1641	<	boolean tooLow(K key) {
1642	<	return lo != UNBOUNDED && compare(key, lo) < loExcluded;
1641	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1642	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1643	>	TreeMap.Entry<K,V> lastExcluded) {
1644	>	super(last, lastExcluded);
1645	>	}
1646	>
1647	>	public Map.Entry<K,V> next() {
1648	>	return prevEntry();
1649	>	}
1650		}
1651
1652	<	boolean tooHigh(K key) {
1653	<	return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
1652	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1653	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1654	>	TreeMap.Entry<K,V> lastExcluded) {
1655	>	super(last, lastExcluded);
1656	>	}
1657	>	public K next() {
1658	>	return prevEntry().key;
1659	>	}
1660		}
1661		}
1662
1663	<	class AscendingSubMap extends NavigableSubMap {
1663	>	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1664		private static final long serialVersionUID = 912986545866124060L;
1665
1666	<	AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1667	<	super(lo, loExcluded, hi, hiExcluded);
1666	>	AscendingSubMap(TreeMap<K,V> m,
1667	>	boolean fromStart, K lo, int loExcluded,
1668	>	boolean toEnd, K hi, int hiExcluded) {
1669	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1670		}
1671
1672		public Comparator<? super K> comparator() {
1673	<	return comparator;
1673	>	return m.comparator();
1674		}
1675
1676	<	public NavigableMap<K,V> navigableSubMap(
1677	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1676	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1677	>	K toKey, boolean toInclusive) {
1678		if (!inRange(fromKey, fromInclusive))
1679		throw new IllegalArgumentException("fromKey out of range");
1680		if (!inRange(toKey, toInclusive))
1681		throw new IllegalArgumentException("toKey out of range");
1682	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
1683	<	toKey,   excluded(toInclusive));
1682	>	return new AscendingSubMap(m,
1683	>	false, fromKey, excluded(fromInclusive),
1684	>	false, toKey,   excluded(toInclusive));
1685		}
1686
1687	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1687	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1688		if (!inClosedRange(toKey))
1689		throw new IllegalArgumentException("toKey out of range");
1690	<	return new AscendingSubMap(lo,    loExcluded,
1691	<	toKey, excluded(inclusive));
1690	>	return new AscendingSubMap(m,
1691	>	fromStart, lo,    loExcluded,
1692	>	false,     toKey, excluded(inclusive));
1693		}
1694
1695	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1695	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1696		if (!inRange(fromKey, inclusive))
1697		throw new IllegalArgumentException("fromKey out of range");
1698	<	return new AscendingSubMap(fromKey, excluded(inclusive),
1699	<	hi,      hiExcluded);
1698	>	return new AscendingSubMap(m,
1699	>	false, fromKey, excluded(inclusive),
1700	>	toEnd, hi,      hiExcluded);
1701		}
1702
1703		Iterator<K> keyIterator() {
1704	<	return new SubMapKeyIterator
1467	<	(loEntry(),
1468	<	hi == UNBOUNDED ? null :
1469	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1470	<	getHigherEntry(hi));
1704	>	return new SubMapKeyIterator(loEntry(), hiFence());
1705		}
1706
1707		Iterator<K> descendingKeyIterator() {
1708	<	return new DescendingSubMapKeyIterator
1709	<	(hiEntry(),
1710	<	lo == UNBOUNDED ? null :
1711	<	loExcluded == 1 ? getFloorEntry(lo) :
1712	<	getLowerEntry(lo));
1708	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1709	>	}
1710	>
1711	>	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1712	>	public Iterator<Map.Entry<K,V>> iterator() {
1713	>	return new SubMapEntryIterator(loEntry(), hiFence());
1714	>	}
1715		}
1716
1717		public Set<Map.Entry<K,V>> entrySet() {
1718	<	Set<Map.Entry<K,V>> es = entrySetView;
1719	<	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	<	};
1718	>	EntrySetView es = entrySetView;
1719	>	return (es != null) ? es : new AscendingEntrySetView();
1720		}
1721
1722		public K firstKey() {
#	Line 1517 | Line 1744 | public class TreeMap<K,V>
1744		}
1745
1746		public NavigableMap<K,V> descendingMap() {
1747	<	NavigableMap<K,V> m = descendingMapView;
1748	<	return (m != null) ? m :
1747	>	NavigableMap<K,V> mv = descendingMapView;
1748	>	return (mv != null) ? mv :
1749		(descendingMapView =
1750	<	new DescendingSubMap(lo, loExcluded, hi, hiExcluded));
1750	>	new DescendingSubMap(m,
1751	>	fromStart, lo, loExcluded,
1752	>	toEnd,     hi, hiExcluded));
1753		}
1754		}
1755
1756	<	class DescendingSubMap extends NavigableSubMap {
1756	>	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1757		private static final long serialVersionUID = 912986545866120460L;
1758	<	DescendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1759	<	super(lo, loExcluded, hi, hiExcluded);
1758	>	DescendingSubMap(TreeMap<K,V> m,
1759	>	boolean fromStart, K lo, int loExcluded,
1760	>	boolean toEnd, K hi, int hiExcluded) {
1761	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1762		}
1763
1764		private final Comparator<? super K> reverseComparator =
1765	<	Collections.reverseOrder(comparator);
1765	>	Collections.reverseOrder(m.comparator);
1766
1767		public Comparator<? super K> comparator() {
1768		return reverseComparator;
1769		}
1770
1771	<	public NavigableMap<K,V> navigableSubMap(
1772	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1771	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1772	>	K toKey, boolean toInclusive) {
1773		if (!inRange(fromKey, fromInclusive))
1774		throw new IllegalArgumentException("fromKey out of range");
1775		if (!inRange(toKey, toInclusive))
1776		throw new IllegalArgumentException("toKey out of range");
1777	<	return new DescendingSubMap(toKey,   excluded(toInclusive),
1778	<	fromKey, excluded(fromInclusive));
1777	>	return new DescendingSubMap(m,
1778	>	false, toKey,   excluded(toInclusive),
1779	>	false, fromKey, excluded(fromInclusive));
1780		}
1781
1782	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1782	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1783		if (!inRange(toKey, inclusive))
1784		throw new IllegalArgumentException("toKey out of range");
1785	<	return new DescendingSubMap(toKey, inclusive ? 0:1, hi, hiExcluded);
1785	>	return new DescendingSubMap(m,
1786	>	false, toKey, excluded(inclusive),
1787	>	toEnd, hi,    hiExcluded);
1788		}
1789
1790	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1790	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1791		if (!inRange(fromKey, inclusive))
1792		throw new IllegalArgumentException("fromKey out of range");
1793	<	return new DescendingSubMap(lo,      loExcluded,
1794	<	fromKey, excluded(inclusive));
1793	>	return new DescendingSubMap(m,
1794	>	fromStart, lo, loExcluded,
1795	>	false, fromKey, excluded(inclusive));
1796		}
1797
1798		Iterator<K> keyIterator() {
1799	<	return new DescendingSubMapKeyIterator
1565	<	(hiEntry(),
1566	<	lo == UNBOUNDED ? null :
1567	<	loExcluded == 1 ? getFloorEntry(lo) :
1568	<	getLowerEntry(lo));
1799	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1800		}
1801
1802		Iterator<K> descendingKeyIterator() {
1803	<	return new SubMapKeyIterator
1804	<	(loEntry(),
1805	<	hi == UNBOUNDED ? null :
1806	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1807	<	getHigherEntry(hi));
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	<	Set<Map.Entry<K,V>> es = entrySetView;
1814	<	if  (es != null)
1582	<	return es;
1583	<	return entrySetView = new NavigableSubMap.EntrySetView() {
1584	<	public Iterator<Map.Entry<K,V>> iterator() {
1585	<	return new DescendingSubMapEntryIterator(hiEntry(),
1586	<	lo == UNBOUNDED ? null :
1587	<	loExcluded == 1 ? getFloorEntry(lo) :
1588	<	getLowerEntry(lo));
1589	<	}
1590	<	};
1813	>	EntrySetView es = entrySetView;
1814	>	return (es != null) ? es : new DescendingEntrySetView();
1815		}
1816
1817		public K firstKey() {
#	Line 1615 | Line 1839 | public class TreeMap<K,V>
1839		}
1840
1841		public NavigableMap<K,V> descendingMap() {
1842	<	NavigableMap<K,V> m = descendingMapView;
1843	<	return (m != null) ? m :
1842	>	NavigableMap<K,V> mv = descendingMapView;
1843	>	return (mv != null) ? mv :
1844		(descendingMapView =
1845	<	new AscendingSubMap(lo, loExcluded, hi, hiExcluded));
1845	>	new AscendingSubMap(m,
1846	>	fromStart, lo, loExcluded,
1847	>	toEnd, hi, hiExcluded));
1848		}
1849
1850		@Override TreeMap.Entry<K,V> subCeiling(K key) {
#	Line 1639 | Line 1865 | public class TreeMap<K,V>
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	+	}
1874	+
1875	+	/**
1876	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1877	+	* that it copes with <tt>null</tt> o1 properly.
1878	+	*/
1879	+	final static boolean valEquals(Object o1, Object o2) {
1880	+	return (o1==null ? o2==null : o1.equals(o2));
1881	+	}
1882	+
1883	+	/**
1884		* This class exists solely for the sake of serialization
1885		* compatibility with previous releases of TreeMap that did not
1886		* support NavigableMap.  It translates an old-version SubMap into
#	Line 1651 | Line 1893 | public class TreeMap<K,V>
1893		private boolean fromStart = false, toEnd = false;
1894		private K fromKey, toKey;
1895		private Object readResolve() {
1896	<	return new AscendingSubMap
1897	<	(fromStart? ((K)UNBOUNDED) : fromKey, 0,
1898	<	toEnd? ((K)UNBOUNDED) : toKey, 1);
1899	<	}
1900	<	public Set<Map.Entry<K,V>> entrySet() { throw new UnsupportedOperationException(); }
1901	<	public K lastKey() { throw new UnsupportedOperationException(); }
1902	<	public K firstKey() { throw new UnsupportedOperationException(); }
1903	<	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new UnsupportedOperationException(); }
1904	<	public SortedMap<K,V> headMap(K toKey) { throw new UnsupportedOperationException(); }
1905	<	public SortedMap<K,V> tailMap(K fromKey) { throw new UnsupportedOperationException(); }
1906	<	public Comparator<? super K> comparator() { throw new UnsupportedOperationException(); }
1896	>	return new AscendingSubMap(TreeMap.this,
1897	>	fromStart, fromKey, 0,
1898	>	toEnd, toKey, 1);
1899	>	}
1900	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1901	>	public K lastKey() { throw new InternalError(); }
1902	>	public K firstKey() { throw new InternalError(); }
1903	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1904	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1905	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1906	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1907		}
1908
1667	–	/**
1668	–	* TreeMap Iterator.
1669	–	*/
1670	–	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1671	–	int expectedModCount = TreeMap.this.modCount;
1672	–	Entry<K,V> lastReturned = null;
1673	–	Entry<K,V> next;
1674	–
1675	–	PrivateEntryIterator(Entry<K,V> first) {
1676	–	next = first;
1677	–	}
1678	–
1679	–	public final boolean hasNext() {
1680	–	return next != null;
1681	–	}
1682	–
1683	–	final Entry<K,V> nextEntry() {
1684	–	if (next == null)
1685	–	throw new NoSuchElementException();
1686	–	if (modCount != expectedModCount)
1687	–	throw new ConcurrentModificationException();
1688	–	lastReturned = next;
1689	–	next = successor(next);
1690	–	return lastReturned;
1691	–	}
1692	–
1693	–	final Entry<K,V> prevEntry() {
1694	–	if (next == null)
1695	–	throw new NoSuchElementException();
1696	–	if (modCount != expectedModCount)
1697	–	throw new ConcurrentModificationException();
1698	–	lastReturned = next;
1699	–	next = predecessor(next);
1700	–	return lastReturned;
1701	–	}
1702	–
1703	–	public void remove() {
1704	–	if (lastReturned == null)
1705	–	throw new IllegalStateException();
1706	–	if (modCount != expectedModCount)
1707	–	throw new ConcurrentModificationException();
1708	–	if (lastReturned.left != null && lastReturned.right != null)
1709	–	next = lastReturned;
1710	–	deleteEntry(lastReturned);
1711	–	expectedModCount++;
1712	–	lastReturned = null;
1713	–	}
1714	–	}
1715	–
1716	–	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1717	–	EntryIterator(Entry<K,V> first) {
1718	–	super(first);
1719	–	}
1720	–	public Map.Entry<K,V> next() {
1721	–	return nextEntry();
1722	–	}
1723	–	}
1724	–
1725	–	final class ValueIterator extends PrivateEntryIterator<V> {
1726	–	ValueIterator(Entry<K,V> first) {
1727	–	super(first);
1728	–	}
1729	–	public V next() {
1730	–	return nextEntry().value;
1731	–	}
1732	–	}
1733	–
1734	–	final class KeyIterator extends PrivateEntryIterator<K> {
1735	–	KeyIterator(Entry<K,V> first) {
1736	–	super(first);
1737	–	}
1738	–	public K next() {
1739	–	return nextEntry().key;
1740	–	}
1741	–	}
1742	–
1743	–	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1744	–	DescendingKeyIterator(Entry<K,V> first) {
1745	–	super(first);
1746	–	}
1747	–	public K next() {
1748	–	return prevEntry().key;
1749	–	}
1750	–	}
1751	–
1752	–	/**
1753	–	* Iterators for SubMaps
1754	–	*/
1755	–	abstract class SubMapIterator<T> implements Iterator<T> {
1756	–	int expectedModCount = TreeMap.this.modCount;
1757	–	Entry<K,V> lastReturned = null;
1758	–	Entry<K,V> next;
1759	–	final K firstExcludedKey;
1760	–
1761	–	SubMapIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	–	next = first;
1763	–	firstExcludedKey = (firstExcluded == null ? null
1764	–	: firstExcluded.key);
1765	–	}
1766	–
1767	–	public final boolean hasNext() {
1768	–	return next != null && next.key != firstExcludedKey;
1769	–	}
1770	–
1771	–	final Entry<K,V> nextEntry() {
1772	–	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;
1779	–	}
1780	–
1781	–	final Entry<K,V> prevEntry() {
1782	–	if (next == null || next.key == firstExcludedKey)
1783	–	throw new NoSuchElementException();
1784	–	if (modCount != expectedModCount)
1785	–	throw new ConcurrentModificationException();
1786	–	lastReturned = next;
1787	–	next = predecessor(next);
1788	–	return lastReturned;
1789	–	}
1790	–
1791	–	public void remove() {
1792	–	if (lastReturned == null)
1793	–	throw new IllegalStateException();
1794	–	if (modCount != expectedModCount)
1795	–	throw new ConcurrentModificationException();
1796	–	if (lastReturned.left != null && lastReturned.right != null)
1797	–	next = lastReturned;
1798	–	deleteEntry(lastReturned);
1799	–	expectedModCount++;
1800	–	lastReturned = null;
1801	–	}
1802	–	}
1803	–
1804	–	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1805	–	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1806	–	super(first, firstExcluded);
1807	–	}
1808	–	public Map.Entry<K,V> next() {
1809	–	return nextEntry();
1810	–	}
1811	–	}
1812	–
1813	–	final class SubMapKeyIterator extends SubMapIterator<K> {
1814	–	SubMapKeyIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1815	–	super(first, firstExcluded);
1816	–	}
1817	–	public K next() {
1818	–	return nextEntry().key;
1819	–	}
1820	–	}
1821	–
1822	–	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1823	–	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1824	–	super(last, lastExcluded);
1825	–	}
1826	–
1827	–	public Map.Entry<K,V> next() {
1828	–	return prevEntry();
1829	–	}
1830	–	}
1831	–
1832	–	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1833	–	DescendingSubMapKeyIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1834	–	super(last, lastExcluded);
1835	–	}
1836	–	public K next() {
1837	–	return prevEntry().key;
1838	–	}
1839	–	}
1840	–
1841	–	/**
1842	–	* Compares two keys using the correct comparison method for this TreeMap.
1843	–	*/
1844	–	private int compare(Object k1, Object k2) {
1845	–	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1846	–	: comparator.compare((K)k1, (K)k2);
1847	–	}
1848	–
1849	–	/**
1850	–	* Test two values for equality.  Differs from o1.equals(o2) only in
1851	–	* that it copes with <tt>null</tt> o1 properly.
1852	–	*/
1853	–	private static boolean valEquals(Object o1, Object o2) {
1854	–	return (o1==null ? o2==null : o1.equals(o2));
1855	–	}
1909
1910		private static final boolean RED   = false;
1911		private static final boolean BLACK = true;
#	Line 1862 | Line 1915 | public class TreeMap<K,V>
1915		* user (see Map.Entry).
1916		*/
1917
1918	<	static class Entry<K,V> implements Map.Entry<K,V> {
1918	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1919		K key;
1920		V value;
1921		Entry<K,V> left = null;
#	Line 1934 | Line 1987 | public class TreeMap<K,V>
1987		* Returns the first Entry in the TreeMap (according to the TreeMap's
1988		* key-sort function).  Returns null if the TreeMap is empty.
1989		*/
1990	<	private Entry<K,V> getFirstEntry() {
1990	>	final Entry<K,V> getFirstEntry() {
1991		Entry<K,V> p = root;
1992		if (p != null)
1993		while (p.left != null)
#	Line 1946 | Line 1999 | public class TreeMap<K,V>
1999		* Returns the last Entry in the TreeMap (according to the TreeMap's
2000		* key-sort function).  Returns null if the TreeMap is empty.
2001		*/
2002	<	private Entry<K,V> getLastEntry() {
2002	>	final Entry<K,V> getLastEntry() {
2003		Entry<K,V> p = root;
2004		if (p != null)
2005		while (p.right != null)
#	Line 1957 | Line 2010 | public class TreeMap<K,V>
2010		/**
2011		* Returns the successor of the specified Entry, or null if no such.
2012		*/
2013	<	private Entry<K,V> successor(Entry<K,V> t) {
2013	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2014		if (t == null)
2015		return null;
2016		else if (t.right != null) {
#	Line 1979 | Line 2032 | public class TreeMap<K,V>
2032		/**
2033		* Returns the predecessor of the specified Entry, or null if no such.
2034		*/
2035	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2035	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2036		if (t == null)
2037		return null;
2038		else if (t.left != null) {
#	Line 2096 | Line 2149 | public class TreeMap<K,V>
2149		x = parentOf(x);
2150		rotateRight(x);
2151		}
2152	<	setColor(parentOf(x),  BLACK);
2152	>	setColor(parentOf(x), BLACK);
2153		setColor(parentOf(parentOf(x)), RED);
2154		if (parentOf(parentOf(x)) != null)
2155		rotateLeft(parentOf(parentOf(x)));
#	Line 2172 | Line 2225 | public class TreeMap<K,V>
2225
2226		if (colorOf(leftOf(sib))  == BLACK &&
2227		colorOf(rightOf(sib)) == BLACK) {
2228	<	setColor(sib,  RED);
2228	>	setColor(sib, RED);
2229		x = parentOf(x);
2230		} else {
2231		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2199 | Line 2252 | public class TreeMap<K,V>
2252
2253		if (colorOf(rightOf(sib)) == BLACK &&
2254		colorOf(leftOf(sib)) == BLACK) {
2255	<	setColor(sib,  RED);
2255	>	setColor(sib, RED);
2256		x = parentOf(x);
2257		} else {
2258		if (colorOf(leftOf(sib)) == BLACK) {

Diff Legend

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