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.29 by dl, Thu Apr 20 20:34:37 2006 UTC vs.
Revision 1.32 by dl, Sat Apr 22 16:38:01 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 125 | Line 125 | public class TreeMap<K,V>
125		* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128	+	comparator = null;
129		}
130
131		/**
#	Line 160 | 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 359 | 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		final Entry<K,V> getEntryUsingComparator(Object key) {
367		K k = (K) key;
#	Line 385 | Line 387 | public class TreeMap<K,V>
387		*/
388		final Entry<K,V> getCeilingEntry(K key) {
389		Entry<K,V> p = root;
390	<	if (p==null)
389	<	return null;
390	<
391	<	while (true) {
390	>	while (p != null) {
391		int cmp = compare(key, p.key);
392		if (cmp < 0) {
393		if (p.left != null)
#	Line 410 | Line 409 | public class TreeMap<K,V>
409		} else
410		return p;
411		}
412	+	return null;
413		}
414
415		/**
#	Line 419 | Line 419 | public class TreeMap<K,V>
419		*/
420		final Entry<K,V> getFloorEntry(K key) {
421		Entry<K,V> p = root;
422	<	if (p==null)
423	<	return null;
424	<
425	<	while (true) {
422	>	while (p != null) {
423		int cmp = compare(key, p.key);
424		if (cmp > 0) {
425		if (p.right != null)
#	Line 445 | Line 442 | public class TreeMap<K,V>
442		return p;
443
444		}
445	+	return null;
446		}
447
448		/**
#	Line 455 | Line 453 | public class TreeMap<K,V>
453		*/
454		final Entry<K,V> getHigherEntry(K key) {
455		Entry<K,V> p = root;
456	<	if (p==null)
459	<	return null;
460	<
461	<	while (true) {
456	>	while (p != null) {
457		int cmp = compare(key, p.key);
458		if (cmp < 0) {
459		if (p.left != null)
#	Line 479 | Line 474 | public class TreeMap<K,V>
474		}
475		}
476		}
477	+	return null;
478		}
479
480		/**
#	Line 488 | Line 484 | public class TreeMap<K,V>
484		*/
485		final Entry<K,V> getLowerEntry(K key) {
486		Entry<K,V> p = root;
487	<	if (p==null)
492	<	return null;
493	<
494	<	while (true) {
487	>	while (p != null) {
488		int cmp = compare(key, p.key);
489		if (cmp > 0) {
490		if (p.right != null)
#	Line 512 | Line 505 | public class TreeMap<K,V>
505		}
506		}
507		}
508	+	return null;
509		}
510
511		/**
#	Line 543 | 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 566 | 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);
570	<	fixAfterInsertion(t.left);
591	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592		return null;
593		}
594		} else { // cmp > 0
#	Line 575 | 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);
579	<	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 877 | 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(this,
905	<	true, null, 0,
906	<	true, null, 0));
904	>	(descendingMap = new DescendingSubMap(this,
905	>	true, null, true,
906	>	true, null, true));
907		}
908
909		/**
#	Line 892 | Line 916 | public class TreeMap<K,V>
916		*/
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));
919	>	return new AscendingSubMap(this,
920	>	false, fromKey, fromInclusive,
921	>	false, toKey,   toInclusive);
922		}
923
924		/**
#	Line 906 | Line 930 | public class TreeMap<K,V>
930		* @since 1.6
931		*/
932		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
933	<	return new AscendingSubMap(this,
934	<	true, null, 0,
935	<	false, toKey, excluded(inclusive));
933	>	return new AscendingSubMap(this,
934	>	true,  null,  true,
935	>	false, toKey, inclusive);
936		}
937
938		/**
#	Line 920 | Line 944 | public class TreeMap<K,V>
944		* @since 1.6
945		*/
946		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
947	<	return new AscendingSubMap(this,
948	<	false, fromKey, excluded(inclusive),
949	<	true, null, 0);
926	<	}
927	<
928	<	/**
929	<	* Translates a boolean "inclusive" value to the correct int value
930	<	* for the loExcluded or hiExcluded field.
931	<	*/
932	<	static int excluded(boolean inclusive) {
933	<	return inclusive ? 0 : 1;
947	>	return new AscendingSubMap(this,
948	>	false, fromKey, inclusive,
949	>	true,  null,    true);
950		}
951
952		/**
#	Line 1093 | Line 1109 | public class TreeMap<K,V>
1109		m.remove(o);
1110		return size() != oldSize;
1111		}
1112	<	public NavigableSet<E> subSet(E fromElement,
1113	<	boolean fromInclusive,
1114	<	E toElement,
1115	<	boolean toInclusive) {
1100	<	return new TreeSet<E>
1101	<	(m.subMap(fromElement, fromInclusive,
1102	<	toElement,   toInclusive));
1112	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1113	>	E toElement, boolean toInclusive) {
1114	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1115	>	toElement,   toInclusive));
1116		}
1117		public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1118		return new TreeSet<E>(m.headMap(toElement, inclusive));
#	Line 1125 | Line 1138 | public class TreeMap<K,V>
1138		* Base class for TreeMap Iterators
1139		*/
1140		abstract class PrivateEntryIterator<T> implements Iterator<T> {
1128	–	int expectedModCount = TreeMap.this.modCount;
1129	–	Entry<K,V> lastReturned = null;
1141		Entry<K,V> next;
1142	+	Entry<K,V> lastReturned;
1143	+	int expectedModCount;
1144
1145		PrivateEntryIterator(Entry<K,V> first) {
1146	+	expectedModCount = modCount;
1147	+	lastReturned = null;
1148		next = first;
1149		}
1150
#	Line 1138 | Line 1153 | public class TreeMap<K,V>
1153		}
1154
1155		final Entry<K,V> nextEntry() {
1156	<	if (next == null)
1156	>	Entry<K,V> e = lastReturned = next;
1157	>	if (e == null)
1158		throw new NoSuchElementException();
1159		if (modCount != expectedModCount)
1160		throw new ConcurrentModificationException();
1161	<	lastReturned = next;
1162	<	next = successor(next);
1147	<	return lastReturned;
1161	>	next = successor(e);
1162	>	return e;
1163		}
1164
1165		final Entry<K,V> prevEntry() {
1166	<	if (next == null)
1166	>	Entry<K,V> e = lastReturned= next;
1167	>	if (e == null)
1168		throw new NoSuchElementException();
1169		if (modCount != expectedModCount)
1170		throw new ConcurrentModificationException();
1171	<	lastReturned = next;
1172	<	next = predecessor(next);
1157	<	return lastReturned;
1171	>	next = predecessor(e);
1172	>	return e;
1173		}
1174
1175		public void remove() {
#	Line 1210 | Line 1225 | public class TreeMap<K,V>
1225
1226		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1227		implements NavigableMap<K,V>, java.io.Serializable {
1213	–
1228		/*
1229		* The backing map.
1230		*/
1231	<	final TreeMap<K,V> m;
1218	<
1219	<	/** True if low point is from start of backing map */
1220	<	boolean fromStart;
1221	<
1222	<	/**
1223	<	* The low endpoint of this submap in absolute terms, or null
1224	<	* if fromStart.
1225	<	*/
1226	<	K lo;
1231	>	final TreeMap<K,V> m;
1232
1233	<	/**
1234	<	* Zero if the low endpoint is excluded from this submap, one if
1235	<	* it's included.  This field is unused if fromStart.
1236	<	*/
1237	<	int loExcluded;
1238	<
1239	<	/** True if high point is to End of backing map */
1235	<	boolean toEnd;
1236	<
1237	<	/**
1238	<	* The high endpoint of this submap in absolute terms, or null
1239	<	* if toEnd.
1233	>	/*
1234	>	* Endpoints are represented as triples (fromStart, lo,
1235	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1236	>	* true, then the low (absolute) bound is the start of the
1237	>	* backing map, and the other values are ignored. Otherwise,
1238	>	* if loInclusive is true, lo is the inclusive bound, else lo
1239	>	* is the exclusive bound. Similarly for the upper bound.
1240		*/
1241	–	K hi;
1241
1242	<	/**
1243	<	* Zero if the high endpoint is excluded from this submap, one if
1244	<	* it's included.  This field is unused if toEnd.
1245	<	*/
1246	<	int hiExcluded;
1242	>	final K lo, hi;
1243	>	final boolean fromStart, toEnd;
1244	>	final boolean loInclusive, hiInclusive;
1245	>
1246	>	NavigableSubMap(TreeMap<K,V> m,
1247	>	boolean fromStart, K lo, boolean loInclusive,
1248	>	boolean toEnd,     K hi, boolean hiInclusive) {
1249	>	if (!fromStart && !toEnd) {
1250	>	if (m.compare(lo, hi) > 0)
1251	>	throw new IllegalArgumentException("fromKey > toKey");
1252	>	} else {
1253	>	if (!fromStart) // type check
1254	>	m.compare(lo, lo);
1255	>	if (!toEnd)
1256	>	m.compare(hi, hi);
1257	>	}
1258
1249	–	NavigableSubMap(TreeMap<K,V> m,
1250	–	boolean fromStart, K lo, int loExcluded,
1251	–	boolean toEnd, K hi, int hiExcluded) {
1252	–	if (!fromStart && !toEnd && m.compare(lo, hi) > 0)
1253	–	throw new IllegalArgumentException("fromKey > toKey");
1259		this.m = m;
1260		this.fromStart = fromStart;
1261		this.lo = lo;
1262	<	this.loExcluded = loExcluded;
1262	>	this.loInclusive = loInclusive;
1263		this.toEnd = toEnd;
1264		this.hi = hi;
1265	<	this.hiExcluded = hiExcluded;
1265	>	this.hiInclusive = hiInclusive;
1266		}
1267
1268		// internal utilities
1269
1270	+	final boolean tooLow(Object key) {
1271	+	if (!fromStart) {
1272	+	int c = m.compare(key, lo);
1273	+	if (c < 0 || (c == 0 && !loInclusive))
1274	+	return true;
1275	+	}
1276	+	return false;
1277	+	}
1278	+
1279	+	final boolean tooHigh(Object key) {
1280	+	if (!toEnd) {
1281	+	int c = m.compare(key, hi);
1282	+	if (c > 0 || (c == 0 && !hiInclusive))
1283	+	return true;
1284	+	}
1285	+	return false;
1286	+	}
1287	+
1288		final boolean inRange(Object key) {
1289	<	return (fromStart || m.compare(key, lo) >= loExcluded)
1267	<	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1289	>	return !tooLow(key) && !tooHigh(key);
1290		}
1291
1292		final boolean inClosedRange(Object key) {
#	Line 1276 | Line 1298 | public class TreeMap<K,V>
1298		return inclusive ? inRange(key) : inClosedRange(key);
1299		}
1300
1301	<	final boolean tooLow(K key) {
1302	<	return !fromStart && m.compare(key, lo) < loExcluded;
1301	>	/**
1302	>	* Return SimpleImmutableEntry for entry, or null if null
1303	>	*/
1304	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1305	>	return e == null? null :
1306	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1307		}
1308
1309	<	final boolean tooHigh(K key) {
1310	<	return !toEnd && m.compare(hi, key) < hiExcluded;
1309	>	/**
1310	>	* Return key for entry, or null if null
1311	>	*/
1312	>	static <K,V> K exportKey(TreeMap.Entry<K,V> e) {
1313	>	return e == null? null : e.key;
1314		}
1315
1316	+	/*
1317	+	* Absolute versions of relation operations.
1318	+	* Subclasses map to these using like-named "sub"
1319	+	* versions that invert senses for descending maps
1320	+	*/
1321
1322	<	/** Returns the lowest entry in this submap (absolute ordering) */
1323	<	final TreeMap.Entry<K,V> loEntry() {
1290	<	TreeMap.Entry<K,V> result =
1322	>	final TreeMap.Entry<K,V> absLowest() {
1323	>	TreeMap.Entry<K,V> e =
1324		(fromStart ?  m.getFirstEntry() :
1325	<	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1326	<	m.getHigherEntry(lo)));
1327	<	return (result == null || tooHigh(result.key)) ? null : result;
1325	>	(loInclusive ? m.getCeilingEntry(lo) :
1326	>	m.getHigherEntry(lo)));
1327	>	return (e == null || tooHigh(e.key)) ? null : e;
1328		}
1329
1330	<	/** Returns the highest key in this submap (absolute ordering) */
1331	<	final TreeMap.Entry<K,V> hiEntry() {
1299	<	TreeMap.Entry<K,V> result =
1330	>	final TreeMap.Entry<K,V> absHighest() {
1331	>	TreeMap.Entry<K,V> e =
1332		(toEnd ?  m.getLastEntry() :
1333	<	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1334	<	m.getLowerEntry(hi)));
1335	<	return (result == null || tooLow(result.key)) ? null : result;
1333	>	(hiInclusive ?  m.getFloorEntry(hi) :
1334	>	m.getLowerEntry(hi)));
1335	>	return (e == null || tooLow(e.key)) ? null : e;
1336		}
1337	<
1338	<	/** Polls the lowest entry in this submap (absolute ordering) */
1339	<	final Map.Entry<K,V> pollLoEntry() {
1340	<	TreeMap.Entry<K,V> e = loEntry();
1341	<	if (e == null)
1342	<	return null;
1311	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1312	<	m.deleteEntry(e);
1313	<	return result;
1337	>
1338	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1339	>	if (tooLow(key))
1340	>	return absLowest();
1341	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1342	>	return (e == null || tooHigh(e.key)) ? null : e;
1343		}
1344
1345	<	/** Polls the highest key in this submap (absolute ordering) */
1346	<	final Map.Entry<K,V> pollHiEntry() {
1347	<	TreeMap.Entry<K,V> e = hiEntry();
1348	<	if (e == null)
1349	<	return null;
1321	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1322	<	m.deleteEntry(e);
1323	<	return result;
1345	>	final TreeMap.Entry<K,V> absHigher(K key) {
1346	>	if (tooLow(key))
1347	>	return absLowest();
1348	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1349	>	return (e == null || tooHigh(e.key)) ? null : e;
1350		}
1351
1352	<	/**
1353	<	* Return the absolute high fence for ascending traversal
1354	<	*/
1355	<	final TreeMap.Entry<K,V> hiFence() {
1356	<	if (toEnd)
1331	<	return null;
1332	<	else if (hiExcluded == 0)
1333	<	return m.getHigherEntry(hi);
1334	<	else
1335	<	return m.getCeilingEntry(hi);
1352	>	final TreeMap.Entry<K,V> absFloor(K key) {
1353	>	if (tooHigh(key))
1354	>	return absHighest();
1355	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1356	>	return (e == null || tooLow(e.key)) ? null : e;
1357		}
1358
1359	<	/**
1360	<	* Return the absolute low fence for descending traversal
1361	<	*/
1362	<	final TreeMap.Entry<K,V> loFence() {
1363	<	if (fromStart)
1343	<	return null;
1344	<	else if (loExcluded == 0)
1345	<	return m.getLowerEntry(lo);
1346	<	else
1347	<	return m.getFloorEntry(lo);
1359	>	final TreeMap.Entry<K,V> absLower(K key) {
1360	>	if (tooHigh(key))
1361	>	return absHighest();
1362	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1363	>	return (e == null || tooLow(e.key)) ? null : e;
1364		}
1365
1366	+	/** Returns the absolute high fence for ascending traversal */
1367	+	final TreeMap.Entry<K,V> absHighFence() {
1368	+	return (toEnd ? null : (hiInclusive ?
1369	+	m.getHigherEntry(hi) :
1370	+	m.getCeilingEntry(hi)));
1371	+	}
1372	+
1373	+	/** Return the absolute low fence for descending traversal  */
1374	+	final TreeMap.Entry<K,V> absLowFence() {
1375	+	return (fromStart ? null : (loInclusive ?
1376	+	m.getLowerEntry(lo) :
1377	+	m.getFloorEntry(lo)));
1378	+	}
1379	+
1380	+	// Abstract methods defined in ascending vs descending classes
1381	+	// These relay to the appropriate  absolute versions
1382	+
1383	+	abstract TreeMap.Entry<K,V> subLowest();
1384	+	abstract TreeMap.Entry<K,V> subHighest();
1385	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1386	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1387	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1388	+	abstract TreeMap.Entry<K,V> subLower(K key);
1389	+
1390	+	/** Returns ascending iterator from the perspective of this submap */
1391	+	abstract Iterator<K> keyIterator();
1392	+
1393	+	/** Returns descending iterator from the perspective of this submap */
1394	+	abstract Iterator<K> descendingKeyIterator();
1395	+
1396	+	// public methods
1397
1398		public boolean isEmpty() {
1399	<	return entrySet().isEmpty();
1399	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1400		}
1401
1402	<	public boolean containsKey(Object key) {
1403	<	return inRange(key) && m.containsKey(key);
1402	>	public int size() {
1403	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1404		}
1405
1406	<	public V get(Object key) {
1407	<	if (!inRange(key))
1361	<	return null;
1362	<	return m.get(key);
1406	>	public final boolean containsKey(Object key) {
1407	>	return inRange(key) && m.containsKey(key);
1408		}
1409
1410	<	public V put(K key, V value) {
1410	>	public final V put(K key, V value) {
1411		if (!inRange(key))
1412		throw new IllegalArgumentException("key out of range");
1413		return m.put(key, value);
1414		}
1415
1416	<	public V remove(Object key) {
1417	<	if (!inRange(key))
1373	<	return null;
1374	<	return m.remove(key);
1416	>	public final V get(Object key) {
1417	>	return !inRange(key)? null :  m.get(key);
1418		}
1419
1420	<	public Map.Entry<K,V> ceilingEntry(K key) {
1421	<	TreeMap.Entry<K,V> e = subCeiling(key);
1379	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1420	>	public final V remove(Object key) {
1421	>	return !inRange(key)? null  : m.remove(key);
1422		}
1423
1424	<	public K ceilingKey(K key) {
1425	<	TreeMap.Entry<K,V> e = subCeiling(key);
1384	<	return e == null? null : e.key;
1424	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1425	>	return exportEntry(subCeiling(key));
1426		}
1427
1428	<	public Map.Entry<K,V> higherEntry(K key) {
1429	<	TreeMap.Entry<K,V> e = subHigher(key);
1389	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1428	>	public final K ceilingKey(K key) {
1429	>	return exportKey(subCeiling(key));
1430		}
1431
1432	<	public K higherKey(K key) {
1433	<	TreeMap.Entry<K,V> e = subHigher(key);
1394	<	return e == null? null : e.key;
1432	>	public final Map.Entry<K,V> higherEntry(K key) {
1433	>	return exportEntry(subHigher(key));
1434		}
1435
1436	<	public Map.Entry<K,V> floorEntry(K key) {
1437	<	TreeMap.Entry<K,V> e = subFloor(key);
1399	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1436	>	public final K higherKey(K key) {
1437	>	return exportKey(subHigher(key));
1438		}
1439
1440	<	public K floorKey(K key) {
1441	<	TreeMap.Entry<K,V> e = subFloor(key);
1404	<	return e == null? null : e.key;
1440	>	public final Map.Entry<K,V> floorEntry(K key) {
1441	>	return exportEntry(subFloor(key));
1442		}
1443
1444	<	public Map.Entry<K,V> lowerEntry(K key) {
1445	<	TreeMap.Entry<K,V> e = subLower(key);
1409	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1444	>	public final K floorKey(K key) {
1445	>	return exportKey(subFloor(key));
1446		}
1447
1448	<	public K lowerKey(K key) {
1449	<	TreeMap.Entry<K,V> e = subLower(key);
1414	<	return e == null? null : e.key;
1448	>	public final Map.Entry<K,V> lowerEntry(K key) {
1449	>	return exportEntry(subLower(key));
1450		}
1451
1452	<	abstract Iterator<K> keyIterator();
1453	<	abstract Iterator<K> descendingKeyIterator();
1452	>	public final K lowerKey(K key) {
1453	>	return exportKey(subLower(key));
1454	>	}
1455
1456	<	public NavigableSet<K> descendingKeySet() {
1457	<	return descendingMap().navigableKeySet();
1456	>	public final K firstKey() {
1457	>	return key(subLowest());
1458	>	}
1459	>
1460	>	public final K lastKey() {
1461	>	return key(subHighest());
1462	>	}
1463	>
1464	>	public final Map.Entry<K,V> firstEntry() {
1465	>	return exportEntry(subLowest());
1466	>	}
1467	>
1468	>	public final Map.Entry<K,V> lastEntry() {
1469	>	return exportEntry(subHighest());
1470	>	}
1471	>
1472	>	public final Map.Entry<K,V> pollFirstEntry() {
1473	>	TreeMap.Entry<K,V> e = subLowest();
1474	>	Map.Entry<K,V> result = exportEntry(e);
1475	>	if (e != null)
1476	>	m.deleteEntry(e);
1477	>	return result;
1478	>	}
1479	>
1480	>	public final Map.Entry<K,V> pollLastEntry() {
1481	>	TreeMap.Entry<K,V> e = subHighest();
1482	>	Map.Entry<K,V> result = exportEntry(e);
1483	>	if (e != null)
1484	>	m.deleteEntry(e);
1485	>	return result;
1486		}
1487
1488		// Views
#	Line 1426 | Line 1490 | public class TreeMap<K,V>
1490		transient EntrySetView entrySetView = null;
1491		transient KeySet<K> navigableKeySetView = null;
1492
1493	+	public final NavigableSet<K> navigableKeySet() {
1494	+	KeySet<K> nksv = navigableKeySetView;
1495	+	return (nksv != null) ? nksv :
1496	+	(navigableKeySetView = new TreeMap.KeySet(this));
1497	+	}
1498	+
1499	+	public final Set<K> keySet() {
1500	+	return navigableKeySet();
1501	+	}
1502	+
1503	+	public NavigableSet<K> descendingKeySet() {
1504	+	return descendingMap().navigableKeySet();
1505	+	}
1506	+
1507	+	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1508	+	return subMap(fromKey, true, toKey, false);
1509	+	}
1510	+
1511	+	public final SortedMap<K,V> headMap(K toKey) {
1512	+	return headMap(toKey, false);
1513	+	}
1514	+
1515	+	public final SortedMap<K,V> tailMap(K fromKey) {
1516	+	return tailMap(fromKey, true);
1517	+	}
1518	+
1519	+	// View classes
1520	+
1521		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1522		private transient int size = -1, sizeModCount;
1523
#	Line 1434 | Line 1526 | public class TreeMap<K,V>
1526		return m.size();
1527		if (size == -1 || sizeModCount != m.modCount) {
1528		sizeModCount = m.modCount;
1529	<	size = 0;
1529	>	size = 0;
1530		Iterator i = iterator();
1531		while (i.hasNext()) {
1532		size++;
#	Line 1445 | Line 1537 | public class TreeMap<K,V>
1537		}
1538
1539		public boolean isEmpty() {
1540	<	TreeMap.Entry<K,V> n = loEntry();
1540	>	TreeMap.Entry<K,V> n = absLowest();
1541		return n == null || tooHigh(n.key);
1542		}
1543
#	Line 1477 | Line 1569 | public class TreeMap<K,V>
1569		}
1570		}
1571
1480	–	public NavigableSet<K> navigableKeySet() {
1481	–	KeySet<K> nksv = navigableKeySetView;
1482	–	return (nksv != null) ? nksv :
1483	–	(navigableKeySetView = new TreeMap.KeySet(this));
1484	–	}
1485	–
1486	–	public Set<K> keySet() {
1487	–	return navigableKeySet();
1488	–	}
1489	–
1490	–	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1491	–	return subMap(fromKey, true, toKey, false);
1492	–	}
1493	–
1494	–	public SortedMap<K,V> headMap(K toKey) {
1495	–	return headMap(toKey, false);
1496	–	}
1497	–
1498	–	public SortedMap<K,V> tailMap(K fromKey) {
1499	–	return tailMap(fromKey, true);
1500	–	}
1501	–
1502	–
1503	–	// The following four definitions are correct only for
1504	–	// ascending submaps. They are overridden in DescendingSubMap.
1505	–	// They are defined in the base class because the definitions
1506	–	// in DescendingSubMap rely on those for AscendingSubMap.
1507	–
1508	–	/**
1509	–	* Returns the entry corresponding to the ceiling of the specified
1510	–	* key from the perspective of this submap, or null if the submap
1511	–	* contains no such entry.
1512	–	*/
1513	–	TreeMap.Entry<K,V> subCeiling(K key) {
1514	–	if (tooLow(key))
1515	–	return loEntry();
1516	–	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1517	–	return (e == null || tooHigh(e.key)) ? null : e;
1518	–	}
1519	–
1520	–	/**
1521	–	* Returns the entry corresponding to the higher of the specified
1522	–	* key from the perspective of this submap, or null if the submap
1523	–	* contains no such entry.
1524	–	*/
1525	–	TreeMap.Entry<K,V> subHigher(K key) {
1526	–	if (tooLow(key))
1527	–	return loEntry();
1528	–	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1529	–	return (e == null || tooHigh(e.key)) ? null : e;
1530	–	}
1531	–
1532	–	/**
1533	–	* Returns the entry corresponding to the floor of the specified
1534	–	* key from the perspective of this submap, or null if the submap
1535	–	* contains no such entry.
1536	–	*/
1537	–	TreeMap.Entry<K,V> subFloor(K key) {
1538	–	if (tooHigh(key))
1539	–	return hiEntry();
1540	–	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1541	–	return (e == null || tooLow(e.key)) ? null : e;
1542	–	}
1543	–
1544	–	/**
1545	–	* Returns the entry corresponding to the lower of the specified
1546	–	* key from the perspective of this submap, or null if the submap
1547	–	* contains no such entry.
1548	–	*/
1549	–	TreeMap.Entry<K,V> subLower(K key) {
1550	–	if (tooHigh(key))
1551	–	return hiEntry();
1552	–	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1553	–	return (e == null || tooLow(e.key)) ? null : e;
1554	–	}
1555	–
1572		/**
1573		* Iterators for SubMaps
1574		*/
1575		abstract class SubMapIterator<T> implements Iterator<T> {
1576	<	int expectedModCount = m.modCount;
1561	<	TreeMap.Entry<K,V> lastReturned = null;
1576	>	TreeMap.Entry<K,V> lastReturned;
1577		TreeMap.Entry<K,V> next;
1578	<	final K firstExcludedKey;
1578	>	final K fenceKey;
1579	>	int expectedModCount;
1580
1581	<	SubMapIterator(TreeMap.Entry<K,V> first,
1582	<	TreeMap.Entry<K,V> firstExcluded) {
1581	>	SubMapIterator(TreeMap.Entry<K,V> first,
1582	>	TreeMap.Entry<K,V> fence) {
1583	>	expectedModCount = m.modCount;
1584	>	lastReturned = null;
1585		next = first;
1586	<	firstExcludedKey = (firstExcluded == null ? null
1569	<	: firstExcluded.key);
1586	>	fenceKey = fence == null ? null : fence.key;
1587		}
1588
1589		public final boolean hasNext() {
1590	<	return next != null && next.key != firstExcludedKey;
1590	>	return next != null && next.key != fenceKey;
1591		}
1592
1593		final TreeMap.Entry<K,V> nextEntry() {
1594	<	if (next == null || next.key == firstExcludedKey)
1594	>	TreeMap.Entry<K,V> e = lastReturned = next;
1595	>	if (e == null || e.key == fenceKey)
1596		throw new NoSuchElementException();
1597		if (m.modCount != expectedModCount)
1598		throw new ConcurrentModificationException();
1599	<	lastReturned = next;
1600	<	next = m.successor(next);
1583	<	return lastReturned;
1599	>	next = successor(e);
1600	>	return e;
1601		}
1602
1603		final TreeMap.Entry<K,V> prevEntry() {
1604	<	if (next == null || next.key == firstExcludedKey)
1604	>	TreeMap.Entry<K,V> e = lastReturned = next;
1605	>	if (e == null || e.key == fenceKey)
1606		throw new NoSuchElementException();
1607		if (m.modCount != expectedModCount)
1608		throw new ConcurrentModificationException();
1609	<	lastReturned = next;
1610	<	next = m.predecessor(next);
1593	<	return lastReturned;
1609	>	next = predecessor(e);
1610	>	return e;
1611		}
1612
1613		public void remove() {
#	Line 1607 | Line 1624 | public class TreeMap<K,V>
1624		}
1625
1626		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1627	<	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1628	<	TreeMap.Entry<K,V> firstExcluded) {
1629	<	super(first, firstExcluded);
1627	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1628	>	TreeMap.Entry<K,V> fence) {
1629	>	super(first, fence);
1630		}
1631		public Map.Entry<K,V> next() {
1632		return nextEntry();
#	Line 1617 | Line 1634 | public class TreeMap<K,V>
1634		}
1635
1636		final class SubMapKeyIterator extends SubMapIterator<K> {
1637	<	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1638	<	TreeMap.Entry<K,V> firstExcluded) {
1639	<	super(first, firstExcluded);
1637	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1638	>	TreeMap.Entry<K,V> fence) {
1639	>	super(first, fence);
1640		}
1641		public K next() {
1642		return nextEntry().key;
#	Line 1627 | Line 1644 | public class TreeMap<K,V>
1644		}
1645
1646		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1647	<	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1648	<	TreeMap.Entry<K,V> lastExcluded) {
1649	<	super(last, lastExcluded);
1647	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1648	>	TreeMap.Entry<K,V> fence) {
1649	>	super(last, fence);
1650		}
1651
1652		public Map.Entry<K,V> next() {
#	Line 1638 | Line 1655 | public class TreeMap<K,V>
1655		}
1656
1657		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1658	<	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1659	<	TreeMap.Entry<K,V> lastExcluded) {
1660	<	super(last, lastExcluded);
1658	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1659	>	TreeMap.Entry<K,V> fence) {
1660	>	super(last, fence);
1661		}
1662		public K next() {
1663		return prevEntry().key;
#	Line 1648 | Line 1665 | public class TreeMap<K,V>
1665		}
1666		}
1667
1668	<	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1668	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1669		private static final long serialVersionUID = 912986545866124060L;
1670
1671	<	AscendingSubMap(TreeMap<K,V> m,
1672	<	boolean fromStart, K lo, int loExcluded,
1673	<	boolean toEnd, K hi, int hiExcluded) {
1674	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1671	>	AscendingSubMap(TreeMap<K,V> m,
1672	>	boolean fromStart, K lo, boolean loInclusive,
1673	>	boolean toEnd, K hi, boolean hiInclusive) {
1674	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1675		}
1676
1677		public Comparator<? super K> comparator() {
1678		return m.comparator();
1679		}
1680
1681	<	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1681	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1682		K toKey, boolean toInclusive) {
1683		if (!inRange(fromKey, fromInclusive))
1684		throw new IllegalArgumentException("fromKey out of range");
1685		if (!inRange(toKey, toInclusive))
1686		throw new IllegalArgumentException("toKey out of range");
1687	<	return new AscendingSubMap(m,
1688	<	false, fromKey, excluded(fromInclusive),
1689	<	false, toKey,   excluded(toInclusive));
1687	>	return new AscendingSubMap(m,
1688	>	false, fromKey, fromInclusive,
1689	>	false, toKey,   toInclusive);
1690		}
1691
1692		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1693		if (!inClosedRange(toKey))
1694		throw new IllegalArgumentException("toKey out of range");
1695	<	return new AscendingSubMap(m,
1696	<	fromStart, lo,    loExcluded,
1697	<	false, toKey, excluded(inclusive));
1695	>	return new AscendingSubMap(m,
1696	>	fromStart, lo,    loInclusive,
1697	>	false,     toKey, inclusive);
1698		}
1699
1700		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1701		if (!inRange(fromKey, inclusive))
1702		throw new IllegalArgumentException("fromKey out of range");
1703	<	return new AscendingSubMap(m,
1704	<	false, fromKey, excluded(inclusive),
1705	<	toEnd, hi,      hiExcluded);
1703	>	return new AscendingSubMap(m,
1704	>	false, fromKey, inclusive,
1705	>	toEnd, hi,      hiInclusive);
1706	>	}
1707	>
1708	>	public NavigableMap<K,V> descendingMap() {
1709	>	NavigableMap<K,V> mv = descendingMapView;
1710	>	return (mv != null) ? mv :
1711	>	(descendingMapView =
1712	>	new DescendingSubMap(m,
1713	>	fromStart, lo, loInclusive,
1714	>	toEnd,     hi, hiInclusive));
1715		}
1716
1717		Iterator<K> keyIterator() {
1718	<	return new SubMapKeyIterator(loEntry(), hiFence());
1718	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1719		}
1720
1721		Iterator<K> descendingKeyIterator() {
1722	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1722	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1723		}
1724
1725	<	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1725	>	final class AscendingEntrySetView extends EntrySetView {
1726		public Iterator<Map.Entry<K,V>> iterator() {
1727	<	return new SubMapEntryIterator(loEntry(), hiFence());
1727	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1728		}
1729		}
1730
#	Line 1707 | Line 1733 | public class TreeMap<K,V>
1733		return (es != null) ? es : new AscendingEntrySetView();
1734		}
1735
1736	<	public K firstKey() {
1737	<	return key(loEntry());
1738	<	}
1739	<
1740	<	public K lastKey() {
1741	<	return key(hiEntry());
1716	<	}
1717	<
1718	<	public Map.Entry<K,V> firstEntry() {
1719	<	return loEntry();
1720	<	}
1721	<
1722	<	public Map.Entry<K,V> lastEntry() {
1723	<	return hiEntry();
1724	<	}
1725	<
1726	<	public Map.Entry<K,V> pollFirstEntry() {
1727	<	return pollLoEntry();
1728	<	}
1729	<
1730	<	public Map.Entry<K,V> pollLastEntry() {
1731	<	return pollHiEntry();
1732	<	}
1733	<
1734	<	public NavigableMap<K,V> descendingMap() {
1735	<	NavigableMap<K,V> mv = descendingMapView;
1736	<	return (mv != null) ? mv :
1737	<	(descendingMapView =
1738	<	new DescendingSubMap(m,
1739	<	fromStart, lo, loExcluded,
1740	<	toEnd, hi, hiExcluded));
1741	<	}
1736	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1737	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1738	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1739	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1740	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1741	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1742		}
1743
1744	<	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1744	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1745		private static final long serialVersionUID = 912986545866120460L;
1746	<	DescendingSubMap(TreeMap<K,V> m,
1747	<	boolean fromStart, K lo, int loExcluded,
1748	<	boolean toEnd, K hi, int hiExcluded) {
1749	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1746	>	DescendingSubMap(TreeMap<K,V> m,
1747	>	boolean fromStart, K lo, boolean loInclusive,
1748	>	boolean toEnd, K hi, boolean hiInclusive) {
1749	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1750		}
1751
1752		private final Comparator<? super K> reverseComparator =
#	Line 1756 | Line 1756 | public class TreeMap<K,V>
1756		return reverseComparator;
1757		}
1758
1759	<	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1759	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1760		K toKey, boolean toInclusive) {
1761		if (!inRange(fromKey, fromInclusive))
1762		throw new IllegalArgumentException("fromKey out of range");
1763		if (!inRange(toKey, toInclusive))
1764		throw new IllegalArgumentException("toKey out of range");
1765	<	return new DescendingSubMap(m,
1766	<	false, toKey,   excluded(toInclusive),
1767	<	false, fromKey, excluded(fromInclusive));
1765	>	return new DescendingSubMap(m,
1766	>	false, toKey,   toInclusive,
1767	>	false, fromKey, fromInclusive);
1768		}
1769
1770		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1771		if (!inRange(toKey, inclusive))
1772		throw new IllegalArgumentException("toKey out of range");
1773	<	return new DescendingSubMap(m,
1774	<	false, toKey, excluded(inclusive),
1775	<	toEnd, hi, hiExcluded);
1773	>	return new DescendingSubMap(m,
1774	>	false, toKey, inclusive,
1775	>	toEnd, hi,    hiInclusive);
1776		}
1777
1778		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1779		if (!inRange(fromKey, inclusive))
1780		throw new IllegalArgumentException("fromKey out of range");
1781	<	return new DescendingSubMap(m,
1782	<	fromStart, lo,      loExcluded,
1783	<	false, fromKey, excluded(inclusive));
1781	>	return new DescendingSubMap(m,
1782	>	fromStart, lo, loInclusive,
1783	>	false, fromKey, inclusive);
1784	>	}
1785	>
1786	>	public NavigableMap<K,V> descendingMap() {
1787	>	NavigableMap<K,V> mv = descendingMapView;
1788	>	return (mv != null) ? mv :
1789	>	(descendingMapView =
1790	>	new AscendingSubMap(m,
1791	>	fromStart, lo, loInclusive,
1792	>	toEnd,     hi, hiInclusive));
1793		}
1794
1795		Iterator<K> keyIterator() {
1796	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1796	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1797		}
1798
1799		Iterator<K> descendingKeyIterator() {
1800	<	return new SubMapKeyIterator(loEntry(), hiFence());
1800	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1801		}
1802
1803	<	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1803	>	final class DescendingEntrySetView extends EntrySetView {
1804		public Iterator<Map.Entry<K,V>> iterator() {
1805	<	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1805	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1806		}
1807		}
1808
#	Line 1802 | Line 1811 | public class TreeMap<K,V>
1811		return (es != null) ? es : new DescendingEntrySetView();
1812		}
1813
1814	<	public K firstKey() {
1815	<	return key(hiEntry());
1816	<	}
1817	<
1818	<	public K lastKey() {
1819	<	return key(loEntry());
1811	<	}
1812	<
1813	<	public Map.Entry<K,V> firstEntry() {
1814	<	return hiEntry();
1815	<	}
1816	<
1817	<	public Map.Entry<K,V> lastEntry() {
1818	<	return loEntry();
1819	<	}
1820	<
1821	<	public Map.Entry<K,V> pollFirstEntry() {
1822	<	return pollHiEntry();
1823	<	}
1824	<
1825	<	public Map.Entry<K,V> pollLastEntry() {
1826	<	return pollLoEntry();
1827	<	}
1828	<
1829	<	public NavigableMap<K,V> descendingMap() {
1830	<	NavigableMap<K,V> mv = descendingMapView;
1831	<	return (mv != null) ? mv :
1832	<	(descendingMapView =
1833	<	new AscendingSubMap(m,
1834	<	fromStart, lo, loExcluded,
1835	<	toEnd, hi, hiExcluded));
1836	<	}
1837	<
1838	<	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1839	<	return super.subFloor(key);
1840	<	}
1841	<
1842	<	@Override TreeMap.Entry<K,V> subHigher(K key) {
1843	<	return super.subLower(key);
1844	<	}
1845	<
1846	<	@Override TreeMap.Entry<K,V> subFloor(K key) {
1847	<	return super.subCeiling(key);
1848	<	}
1849	<
1850	<	@Override TreeMap.Entry<K,V> subLower(K key) {
1851	<	return super.subHigher(key);
1852	<	}
1814	>	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1815	>	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1816	>	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1817	>	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1818	>	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1819	>	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1820		}
1821
1822		/**
#	Line 1881 | Line 1848 | public class TreeMap<K,V>
1848		private boolean fromStart = false, toEnd = false;
1849		private K fromKey, toKey;
1850		private Object readResolve() {
1851	<	return new AscendingSubMap(TreeMap.this,
1852	<	fromStart, fromKey, 0,
1853	<	toEnd, toKey, 1);
1851	>	return new AscendingSubMap(TreeMap.this,
1852	>	fromStart, fromKey, true,
1853	>	toEnd, toKey, false);
1854		}
1855		public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1856		public K lastKey() { throw new InternalError(); }
#	Line 1998 | Line 1965 | public class TreeMap<K,V>
1965		/**
1966		* Returns the successor of the specified Entry, or null if no such.
1967		*/
1968	<	final Entry<K,V> successor(Entry<K,V> t) {
1968	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1969		if (t == null)
1970		return null;
1971		else if (t.right != null) {
#	Line 2020 | Line 1987 | public class TreeMap<K,V>
1987		/**
1988		* Returns the predecessor of the specified Entry, or null if no such.
1989		*/
1990	<	final Entry<K,V> predecessor(Entry<K,V> t) {
1990	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1991		if (t == null)
1992		return null;
1993		else if (t.left != null) {
#	Line 2137 | Line 2104 | public class TreeMap<K,V>
2104		x = parentOf(x);
2105		rotateRight(x);
2106		}
2107	<	setColor(parentOf(x),  BLACK);
2107	>	setColor(parentOf(x), BLACK);
2108		setColor(parentOf(parentOf(x)), RED);
2109		if (parentOf(parentOf(x)) != null)
2110		rotateLeft(parentOf(parentOf(x)));
#	Line 2213 | Line 2180 | public class TreeMap<K,V>
2180
2181		if (colorOf(leftOf(sib))  == BLACK &&
2182		colorOf(rightOf(sib)) == BLACK) {
2183	<	setColor(sib,  RED);
2183	>	setColor(sib, RED);
2184		x = parentOf(x);
2185		} else {
2186		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2240 | Line 2207 | public class TreeMap<K,V>
2207
2208		if (colorOf(rightOf(sib)) == BLACK &&
2209		colorOf(leftOf(sib)) == BLACK) {
2210	<	setColor(sib,  RED);
2210	>	setColor(sib, RED);
2211		x = parentOf(x);
2212		} else {
2213		if (colorOf(leftOf(sib)) == BLACK) {

Diff Legend

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