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.29 by dl, Thu Apr 20 20:34:37 2006 UTC

#	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 235 | Line 226 | public class TreeMap<K,V>
226		public boolean containsValue(Object value) {
227		return (root==null ? false :
228		(value==null ? valueSearchNull(root)
229	<	: valueSearchNonNull(root, value)));
229	>	: valueSearchNonNull(root, value)));
230		}
231
232		private boolean valueSearchNull(Entry n) {
#	Line 244 | Line 235 | public class TreeMap<K,V>
235
236		// Check left and right subtrees for value
237		return (n.left  != null && valueSearchNull(n.left)) ||
238	<	(n.right != null && valueSearchNull(n.right));
238	>	(n.right != null && valueSearchNull(n.right));
239		}
240
241		private boolean valueSearchNonNull(Entry n, Object value) {
#	Line 254 | Line 245 | public class TreeMap<K,V>
245
246		// Check left and right subtrees for value
247		return (n.left  != null && valueSearchNonNull(n.left, value)) ||
248	<	(n.right != null && valueSearchNonNull(n.right, value));
248	>	(n.right != null && valueSearchNonNull(n.right, value));
249		}
250
251		/**
#	Line 344 | Line 335 | public class TreeMap<K,V>
335		*         and this map uses natural ordering, or its comparator
336		*         does not permit null keys
337		*/
338	<	private Entry<K,V> getEntry(Object key) {
338	>	final Entry<K,V> getEntry(Object key) {
339		// Offload comparator-based version for sake of performance
340		if (comparator != null)
341		return getEntryUsingComparator(key);
#	Line 370 | Line 361 | public class TreeMap<K,V>
361		* that are less dependent on comparator performance, but is
362		* worthwhile here.)
363		*/
364	<	private Entry<K,V> getEntryUsingComparator(Object key) {
364	>	final Entry<K,V> getEntryUsingComparator(Object key) {
365		K k = (K) key;
366		Comparator<? super K> cpr = comparator;
367		Entry<K,V> p = root;
#	Line 392 | Line 383 | public class TreeMap<K,V>
383		* key; if no such entry exists (i.e., the greatest key in the Tree is less
384		* than the specified key), returns <tt>null</tt>.
385		*/
386	<	private Entry<K,V> getCeilingEntry(K key) {
386	>	final Entry<K,V> getCeilingEntry(K key) {
387		Entry<K,V> p = root;
388		if (p==null)
389		return null;
#	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)
423		return null;
#	Line 462 | Line 453 | public class TreeMap<K,V>
453		* key greater than the specified key; if no such entry exists
454		* returns <tt>null</tt>.
455		*/
456	<	private Entry<K,V> getHigherEntry(K key) {
456	>	final Entry<K,V> getHigherEntry(K key) {
457		Entry<K,V> p = root;
458		if (p==null)
459		return null;
#	Line 495 | Line 486 | public class TreeMap<K,V>
486		* no such entry exists (i.e., the least key in the Tree is greater than
487		* the specified key), returns <tt>null</tt>.
488		*/
489	<	private Entry<K,V> getLowerEntry(K key) {
489	>	final Entry<K,V> getLowerEntry(K key) {
490		Entry<K,V> p = root;
491		if (p==null)
492		return null;
#	Line 527 | Line 518 | public class TreeMap<K,V>
518		* Returns the key corresponding to the specified Entry.
519		* @throws NoSuchElementException if the Entry is null
520		*/
521	<	private static <K> K key(Entry<K,?> e) {
521	>	static <K> K key(Entry<K,?> e) {
522		if (e==null)
523		throw new NoSuchElementException();
524		return e.key;
#	Line 556 | Line 547 | public class TreeMap<K,V>
547
548		if (t == null) {
549		// TBD
550	<	//             if (key == null) {
551	<	//                 if (comparator == null)
552	<	//                     throw new NullPointerException();
553	<	//                 comparator.compare(key, key);
554	<	//             }
550	>	//             if (key == null) {
551	>	//                 if (comparator == null)
552	>	//                     throw new NullPointerException();
553	>	//                 comparator.compare(key, key);
554	>	//             }
555		incrementSize();
556		root = new Entry<K,V>(key, value, null);
557		return null;
#	Line 803 | Line 794 | public class TreeMap<K,V>
794		* the first time this view is requested.  Views are stateless, so
795		* there's no reason to create more than one.
796		*/
797	<	private transient Set<Map.Entry<K,V>> entrySet = null;
797	>	private transient EntrySet entrySet = null;
798		private transient KeySet<K> navigableKeySet = null;
799		private transient NavigableMap<K,V> descendingMap = null;
800
#	Line 829 | Line 820 | public class TreeMap<K,V>
820		* @since 1.6
821		*/
822		public NavigableSet<K> navigableKeySet() {
823	<	NavigableSet<K> nks = navigableKeySet;
823	>	KeySet<K> nks = navigableKeySet;
824		return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
825		}
826
#	Line 876 | Line 867 | public class TreeMap<K,V>
867		* <tt>add</tt> or <tt>addAll</tt> operations.
868		*/
869		public Set<Map.Entry<K,V>> entrySet() {
870	<	Set<Map.Entry<K,V>> es = entrySet;
870	>	EntrySet es = entrySet;
871		return (es != null) ? es : (entrySet = new EntrySet());
872		}
873
#	Line 886 | Line 877 | public class TreeMap<K,V>
877		public NavigableMap<K, V> descendingMap() {
878		NavigableMap<K, V> km = descendingMap;
879		return (km != null) ? km :
880	<	(descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
881	<	(K)UNBOUNDED, 0));
880	>	(descendingMap = new DescendingSubMap(this,
881	>	true, null, 0,
882	>	true, null, 0));
883		}
884
885		/**
#	Line 898 | Line 890 | public class TreeMap<K,V>
890		* @throws IllegalArgumentException {@inheritDoc}
891		* @since 1.6
892		*/
893	<	public NavigableMap<K,V> navigableSubMap(K fromKey, boolean fromInclusive,
894	<	K toKey,   boolean toInclusive) {
895	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
896	<	toKey,   excluded(toInclusive));
893	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
894	>	K toKey,   boolean toInclusive) {
895	>	return new AscendingSubMap(this,
896	>	false, fromKey, excluded(fromInclusive),
897	>	false, toKey,   excluded(toInclusive));
898		}
899
900		/**
#	Line 912 | Line 905 | public class TreeMap<K,V>
905		* @throws IllegalArgumentException {@inheritDoc}
906		* @since 1.6
907		*/
908	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
909	<	return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
908	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
909	>	return new AscendingSubMap(this,
910	>	true, null, 0,
911	>	false, toKey, excluded(inclusive));
912		}
913
914		/**
#	Line 924 | Line 919 | public class TreeMap<K,V>
919		* @throws IllegalArgumentException {@inheritDoc}
920		* @since 1.6
921		*/
922	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive) {
923	<	return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 0);
922	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
923	>	return new AscendingSubMap(this,
924	>	false, fromKey, excluded(inclusive),
925	>	true, null, 0);
926		}
927
928		/**
#	Line 944 | Line 941 | public class TreeMap<K,V>
941		* @throws IllegalArgumentException {@inheritDoc}
942		*/
943		public SortedMap<K,V> subMap(K fromKey, K toKey) {
944	<	return navigableSubMap(fromKey, true, toKey, false);
944	>	return subMap(fromKey, true, toKey, false);
945		}
946
947		/**
#	Line 955 | Line 952 | public class TreeMap<K,V>
952		* @throws IllegalArgumentException {@inheritDoc}
953		*/
954		public SortedMap<K,V> headMap(K toKey) {
955	<	return navigableHeadMap(toKey, false);
955	>	return headMap(toKey, false);
956		}
957
958		/**
#	Line 966 | Line 963 | public class TreeMap<K,V>
963		* @throws IllegalArgumentException {@inheritDoc}
964		*/
965		public SortedMap<K,V> tailMap(K fromKey) {
966	<	return navigableTailMap(fromKey, true);
966	>	return tailMap(fromKey, true);
967		}
968
969		// View class support
#	Line 1096 | Line 1093 | public class TreeMap<K,V>
1093		m.remove(o);
1094		return size() != oldSize;
1095		}
1096	<	public NavigableSet<E> navigableSubSet(E fromElement,
1097	<	boolean fromInclusive,
1098	<	E toElement,
1099	<	boolean toInclusive) {
1096	>	public NavigableSet<E> subSet(E fromElement,
1097	>	boolean fromInclusive,
1098	>	E toElement,
1099	>	boolean toInclusive) {
1100		return new TreeSet<E>
1101	<	(m.navigableSubMap(fromElement, fromInclusive,
1102	<	toElement,   toInclusive));
1101	>	(m.subMap(fromElement, fromInclusive,
1102	>	toElement,   toInclusive));
1103		}
1104	<	public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
1105	<	return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
1104	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1105	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1106		}
1107	<	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
1108	<	return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
1107	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1108	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1109		}
1110		public SortedSet<E> subSet(E fromElement, E toElement) {
1111	<	return navigableSubSet(fromElement, true, toElement, false);
1111	>	return subSet(fromElement, true, toElement, false);
1112		}
1113		public SortedSet<E> headSet(E toElement) {
1114	<	return navigableHeadSet(toElement, false);
1114	>	return headSet(toElement, false);
1115		}
1116		public SortedSet<E> tailSet(E fromElement) {
1117	<	return navigableTailSet(fromElement, true);
1117	>	return tailSet(fromElement, true);
1118		}
1119		public NavigableSet<E> descendingSet() {
1120		return new TreeSet(m.descendingMap());
1121		}
1122		}
1123
1124	+	/**
1125	+	* Base class for TreeMap Iterators
1126	+	*/
1127	+	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1128	+	int expectedModCount = TreeMap.this.modCount;
1129	+	Entry<K,V> lastReturned = null;
1130	+	Entry<K,V> next;
1131	+
1132	+	PrivateEntryIterator(Entry<K,V> first) {
1133	+	next = first;
1134	+	}
1135	+
1136	+	public final boolean hasNext() {
1137	+	return next != null;
1138	+	}
1139	+
1140	+	final Entry<K,V> nextEntry() {
1141	+	if (next == null)
1142	+	throw new NoSuchElementException();
1143	+	if (modCount != expectedModCount)
1144	+	throw new ConcurrentModificationException();
1145	+	lastReturned = next;
1146	+	next = successor(next);
1147	+	return lastReturned;
1148	+	}
1149	+
1150	+	final Entry<K,V> prevEntry() {
1151	+	if (next == null)
1152	+	throw new NoSuchElementException();
1153	+	if (modCount != expectedModCount)
1154	+	throw new ConcurrentModificationException();
1155	+	lastReturned = next;
1156	+	next = predecessor(next);
1157	+	return lastReturned;
1158	+	}
1159	+
1160	+	public void remove() {
1161	+	if (lastReturned == null)
1162	+	throw new IllegalStateException();
1163	+	if (modCount != expectedModCount)
1164	+	throw new ConcurrentModificationException();
1165	+	if (lastReturned.left != null && lastReturned.right != null)
1166	+	next = lastReturned;
1167	+	deleteEntry(lastReturned);
1168	+	expectedModCount++;
1169	+	lastReturned = null;
1170	+	}
1171	+	}
1172	+
1173	+	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1174	+	EntryIterator(Entry<K,V> first) {
1175	+	super(first);
1176	+	}
1177	+	public Map.Entry<K,V> next() {
1178	+	return nextEntry();
1179	+	}
1180	+	}
1181	+
1182	+	final class ValueIterator extends PrivateEntryIterator<V> {
1183	+	ValueIterator(Entry<K,V> first) {
1184	+	super(first);
1185	+	}
1186	+	public V next() {
1187	+	return nextEntry().value;
1188	+	}
1189	+	}
1190	+
1191	+	final class KeyIterator extends PrivateEntryIterator<K> {
1192	+	KeyIterator(Entry<K,V> first) {
1193	+	super(first);
1194	+	}
1195	+	public K next() {
1196	+	return nextEntry().key;
1197	+	}
1198	+	}
1199	+
1200	+	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1201	+	DescendingKeyIterator(Entry<K,V> first) {
1202	+	super(first);
1203	+	}
1204	+	public K next() {
1205	+	return prevEntry().key;
1206	+	}
1207	+	}
1208	+
1209		// SubMaps
1210
1211	<	abstract class NavigableSubMap extends AbstractMap<K,V>
1211	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1212		implements NavigableMap<K,V>, java.io.Serializable {
1213
1214	<	/**
1215	<	* The low endpoint of this submap in absolute terms.  For ascending
1216	<	* submaps this will be the "first" endpoint; for descending submaps,
1217	<	* the last.  If there is no bound, this field is set to UNBOUNDED.
1214	>	/*
1215	>	* The backing map.
1216	>	*/
1217	>	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;
1227
1228		/**
1229		* Zero if the low endpoint is excluded from this submap, one if
1230	<	* it's included.  This field is unused if lo is UNBOUNDED.
1230	>	* it's included.  This field is unused if fromStart.
1231		*/
1232		int loExcluded;
1233
1234	<	/**
1235	<	* The high endpoint of this submap in absolute terms.  For ascending
1236	<	* submaps this will be the "last" endpoint; for descending submaps,
1237	<	* the first.  If there is no bound, this field is set to UNBOUNDED.
1234	>	/** 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.
1240		*/
1241		K hi;
1242
1243		/**
1244		* Zero if the high endpoint is excluded from this submap, one if
1245	<	* it's included.  This field is unused if hi is UNBOUNDED.
1245	>	* it's included.  This field is unused if toEnd.
1246		*/
1247		int hiExcluded;
1248
1249	<	NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1250	<	if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
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");
1254	+	this.m = m;
1255	+	this.fromStart = fromStart;
1256		this.lo = lo;
1257		this.loExcluded = loExcluded;
1258	+	this.toEnd = toEnd;
1259		this.hi = hi;
1260		this.hiExcluded = hiExcluded;
1261		}
1262
1263	+	// internal utilities
1264	+
1265	+	final boolean inRange(Object key) {
1266	+	return (fromStart || m.compare(key, lo) >= loExcluded)
1267	+	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1268	+	}
1269	+
1270	+	final boolean inClosedRange(Object key) {
1271	+	return (fromStart || m.compare(key, lo) >= 0)
1272	+	&& (toEnd || m.compare(hi, key) >= 0);
1273	+	}
1274	+
1275	+	final boolean inRange(Object key, boolean inclusive) {
1276	+	return inclusive ? inRange(key) : inClosedRange(key);
1277	+	}
1278	+
1279	+	final boolean tooLow(K key) {
1280	+	return !fromStart && m.compare(key, lo) < loExcluded;
1281	+	}
1282	+
1283	+	final boolean tooHigh(K key) {
1284	+	return !toEnd && m.compare(hi, key) < hiExcluded;
1285	+	}
1286	+
1287	+
1288	+	/** Returns the lowest entry in this submap (absolute ordering) */
1289	+	final TreeMap.Entry<K,V> loEntry() {
1290	+	TreeMap.Entry<K,V> result =
1291	+	(fromStart ?  m.getFirstEntry() :
1292	+	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1293	+	m.getHigherEntry(lo)));
1294	+	return (result == null || tooHigh(result.key)) ? null : result;
1295	+	}
1296	+
1297	+	/** Returns the highest key in this submap (absolute ordering) */
1298	+	final TreeMap.Entry<K,V> hiEntry() {
1299	+	TreeMap.Entry<K,V> result =
1300	+	(toEnd ?  m.getLastEntry() :
1301	+	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1302	+	m.getLowerEntry(hi)));
1303	+	return (result == null || tooLow(result.key)) ? null : result;
1304	+	}
1305	+
1306	+	/** Polls the lowest entry in this submap (absolute ordering) */
1307	+	final Map.Entry<K,V> pollLoEntry() {
1308	+	TreeMap.Entry<K,V> e = loEntry();
1309	+	if (e == null)
1310	+	return null;
1311	+	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1312	+	m.deleteEntry(e);
1313	+	return result;
1314	+	}
1315	+
1316	+	/** Polls the highest key in this submap (absolute ordering) */
1317	+	final Map.Entry<K,V> pollHiEntry() {
1318	+	TreeMap.Entry<K,V> e = hiEntry();
1319	+	if (e == null)
1320	+	return null;
1321	+	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1322	+	m.deleteEntry(e);
1323	+	return result;
1324	+	}
1325	+
1326	+	/**
1327	+	* Return the absolute high fence for ascending traversal
1328	+	*/
1329	+	final TreeMap.Entry<K,V> hiFence() {
1330	+	if (toEnd)
1331	+	return null;
1332	+	else if (hiExcluded == 0)
1333	+	return m.getHigherEntry(hi);
1334	+	else
1335	+	return m.getCeilingEntry(hi);
1336	+	}
1337	+
1338	+	/**
1339	+	* Return the absolute low fence for descending traversal
1340	+	*/
1341	+	final TreeMap.Entry<K,V> loFence() {
1342	+	if (fromStart)
1343	+	return null;
1344	+	else if (loExcluded == 0)
1345	+	return m.getLowerEntry(lo);
1346	+	else
1347	+	return m.getFloorEntry(lo);
1348	+	}
1349	+
1350	+
1351		public boolean isEmpty() {
1352		return entrySet().isEmpty();
1353		}
1354
1355		public boolean containsKey(Object key) {
1356	<	return inRange(key) && TreeMap.this.containsKey(key);
1356	>	return inRange(key) && m.containsKey(key);
1357		}
1358
1359		public V get(Object key) {
1360		if (!inRange(key))
1361		return null;
1362	<	return TreeMap.this.get(key);
1362	>	return m.get(key);
1363		}
1364
1365		public V put(K key, V value) {
1366		if (!inRange(key))
1367		throw new IllegalArgumentException("key out of range");
1368	<	return TreeMap.this.put(key, value);
1368	>	return m.put(key, value);
1369		}
1370
1371		public V remove(Object key) {
1372		if (!inRange(key))
1373		return null;
1374	<	return TreeMap.this.remove(key);
1374	>	return m.remove(key);
1375		}
1376
1377		public Map.Entry<K,V> ceilingEntry(K key) {
#	Line 1239 | Line 1423 | public class TreeMap<K,V>
1423
1424		// Views
1425		transient NavigableMap<K,V> descendingMapView = null;
1426	<	transient Set<Map.Entry<K,V>> entrySetView = null;
1427	<	private transient NavigableSet<K> navigableKeySetView = null;
1426	>	transient EntrySetView entrySetView = null;
1427	>	transient KeySet<K> navigableKeySetView = null;
1428
1429		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1430		private transient int size = -1, sizeModCount;
1431
1432		public int size() {
1433	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1434	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1433	>	if (fromStart && toEnd)
1434	>	return m.size();
1435	>	if (size == -1 || sizeModCount != m.modCount) {
1436	>	sizeModCount = m.modCount;
1437	>	size = 0;
1438		Iterator i = iterator();
1439		while (i.hasNext()) {
1440		size++;
#	Line 1258 | Line 1445 | public class TreeMap<K,V>
1445		}
1446
1447		public boolean isEmpty() {
1448	<	return !iterator().hasNext();
1448	>	TreeMap.Entry<K,V> n = loEntry();
1449	>	return n == null || tooHigh(n.key);
1450		}
1451
1452		public boolean contains(Object o) {
#	Line 1268 | Line 1456 | public class TreeMap<K,V>
1456		K key = entry.getKey();
1457		if (!inRange(key))
1458		return false;
1459	<	TreeMap.Entry node = getEntry(key);
1459	>	TreeMap.Entry node = m.getEntry(key);
1460		return node != null &&
1461	<	valEquals(node.getValue(), entry.getValue());
1461	>	valEquals(node.getValue(), entry.getValue());
1462		}
1463
1464		public boolean remove(Object o) {
#	Line 1280 | Line 1468 | public class TreeMap<K,V>
1468		K key = entry.getKey();
1469		if (!inRange(key))
1470		return false;
1471	<	TreeMap.Entry<K,V> node = getEntry(key);
1471	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1472		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1473	<	deleteEntry(node);
1473	>	m.deleteEntry(node);
1474		return true;
1475		}
1476		return false;
#	Line 1290 | Line 1478 | public class TreeMap<K,V>
1478		}
1479
1480		public NavigableSet<K> navigableKeySet() {
1481	<	NavigableSet<K> nksv = navigableKeySetView;
1481	>	KeySet<K> nksv = navigableKeySetView;
1482		return (nksv != null) ? nksv :
1483		(navigableKeySetView = new TreeMap.KeySet(this));
1484		}
#	Line 1300 | Line 1488 | public class TreeMap<K,V>
1488		}
1489
1490		public SortedMap<K,V> subMap(K fromKey, K toKey) {
1491	<	return navigableSubMap(fromKey, true, toKey, false);
1491	>	return subMap(fromKey, true, toKey, false);
1492		}
1493
1494		public SortedMap<K,V> headMap(K toKey) {
1495	<	return navigableHeadMap(toKey, false);
1495	>	return headMap(toKey, false);
1496		}
1497
1498		public SortedMap<K,V> tailMap(K fromKey) {
1499	<	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;
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
#	Line 1364 | Line 1513 | public class TreeMap<K,V>
1513		TreeMap.Entry<K,V> subCeiling(K key) {
1514		if (tooLow(key))
1515		return loEntry();
1516	<	TreeMap.Entry<K,V> e = getCeilingEntry(key);
1516	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1517		return (e == null || tooHigh(e.key)) ? null : e;
1518		}
1519
#	Line 1376 | Line 1525 | public class TreeMap<K,V>
1525		TreeMap.Entry<K,V> subHigher(K key) {
1526		if (tooLow(key))
1527		return loEntry();
1528	<	TreeMap.Entry<K,V> e = getHigherEntry(key);
1528	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1529		return (e == null || tooHigh(e.key)) ? null : e;
1530		}
1531
#	Line 1388 | Line 1537 | public class TreeMap<K,V>
1537		TreeMap.Entry<K,V> subFloor(K key) {
1538		if (tooHigh(key))
1539		return hiEntry();
1540	<	TreeMap.Entry<K,V> e = getFloorEntry(key);
1540	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1541		return (e == null || tooLow(e.key)) ? null : e;
1542		}
1543
#	Line 1400 | Line 1549 | public class TreeMap<K,V>
1549		TreeMap.Entry<K,V> subLower(K key) {
1550		if (tooHigh(key))
1551		return hiEntry();
1552	<	TreeMap.Entry<K,V> e = getLowerEntry(key);
1552	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1553		return (e == null || tooLow(e.key)) ? null : e;
1554		}
1555
1556	<	boolean inRange(Object key) {
1557	<	return (lo == UNBOUNDED || compare(key, lo) >= loExcluded)
1558	<	&& (hi == UNBOUNDED || compare(hi, key) >= hiExcluded);
1556	>	/**
1557	>	* Iterators for SubMaps
1558	>	*/
1559	>	abstract class SubMapIterator<T> implements Iterator<T> {
1560	>	int expectedModCount = m.modCount;
1561	>	TreeMap.Entry<K,V> lastReturned = null;
1562	>	TreeMap.Entry<K,V> next;
1563	>	final K firstExcludedKey;
1564	>
1565	>	SubMapIterator(TreeMap.Entry<K,V> first,
1566	>	TreeMap.Entry<K,V> firstExcluded) {
1567	>	next = first;
1568	>	firstExcludedKey = (firstExcluded == null ? null
1569	>	: firstExcluded.key);
1570	>	}
1571	>
1572	>	public final boolean hasNext() {
1573	>	return next != null && next.key != firstExcludedKey;
1574	>	}
1575	>
1576	>	final TreeMap.Entry<K,V> nextEntry() {
1577	>	if (next == null || next.key == firstExcludedKey)
1578	>	throw new NoSuchElementException();
1579	>	if (m.modCount != expectedModCount)
1580	>	throw new ConcurrentModificationException();
1581	>	lastReturned = next;
1582	>	next = m.successor(next);
1583	>	return lastReturned;
1584	>	}
1585	>
1586	>	final TreeMap.Entry<K,V> prevEntry() {
1587	>	if (next == null || next.key == firstExcludedKey)
1588	>	throw new NoSuchElementException();
1589	>	if (m.modCount != expectedModCount)
1590	>	throw new ConcurrentModificationException();
1591	>	lastReturned = next;
1592	>	next = m.predecessor(next);
1593	>	return lastReturned;
1594	>	}
1595	>
1596	>	public void remove() {
1597	>	if (lastReturned == null)
1598	>	throw new IllegalStateException();
1599	>	if (m.modCount != expectedModCount)
1600	>	throw new ConcurrentModificationException();
1601	>	if (lastReturned.left != null && lastReturned.right != null)
1602	>	next = lastReturned;
1603	>	m.deleteEntry(lastReturned);
1604	>	expectedModCount++;
1605	>	lastReturned = null;
1606	>	}
1607		}
1608
1609	<	boolean inClosedRange(Object key) {
1610	<	return (lo == UNBOUNDED || compare(key, lo) >= 0)
1611	<	&& (hi == UNBOUNDED || compare(hi, key) >= 0);
1609	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1610	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1611	>	TreeMap.Entry<K,V> firstExcluded) {
1612	>	super(first, firstExcluded);
1613	>	}
1614	>	public Map.Entry<K,V> next() {
1615	>	return nextEntry();
1616	>	}
1617		}
1618
1619	<	boolean inRange(Object key, boolean inclusive) {
1620	<	return inclusive ? inRange(key) : inClosedRange(key);
1619	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1620	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1621	>	TreeMap.Entry<K,V> firstExcluded) {
1622	>	super(first, firstExcluded);
1623	>	}
1624	>	public K next() {
1625	>	return nextEntry().key;
1626	>	}
1627		}
1628
1629	<	boolean tooLow(K key) {
1630	<	return lo != UNBOUNDED && compare(key, lo) < loExcluded;
1629	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1630	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1631	>	TreeMap.Entry<K,V> lastExcluded) {
1632	>	super(last, lastExcluded);
1633	>	}
1634	>
1635	>	public Map.Entry<K,V> next() {
1636	>	return prevEntry();
1637	>	}
1638		}
1639
1640	<	boolean tooHigh(K key) {
1641	<	return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
1640	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1641	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1642	>	TreeMap.Entry<K,V> lastExcluded) {
1643	>	super(last, lastExcluded);
1644	>	}
1645	>	public K next() {
1646	>	return prevEntry().key;
1647	>	}
1648		}
1649		}
1650
1651	<	class AscendingSubMap extends NavigableSubMap {
1651	>	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1652		private static final long serialVersionUID = 912986545866124060L;
1653
1654	<	AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1655	<	super(lo, loExcluded, hi, hiExcluded);
1654	>	AscendingSubMap(TreeMap<K,V> m,
1655	>	boolean fromStart, K lo, int loExcluded,
1656	>	boolean toEnd, K hi, int hiExcluded) {
1657	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1658		}
1659
1660		public Comparator<? super K> comparator() {
1661	<	return comparator;
1661	>	return m.comparator();
1662		}
1663
1664	<	public NavigableMap<K,V> navigableSubMap(
1665	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1664	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1665	>	K toKey, boolean toInclusive) {
1666		if (!inRange(fromKey, fromInclusive))
1667		throw new IllegalArgumentException("fromKey out of range");
1668		if (!inRange(toKey, toInclusive))
1669		throw new IllegalArgumentException("toKey out of range");
1670	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
1671	<	toKey,   excluded(toInclusive));
1670	>	return new AscendingSubMap(m,
1671	>	false, fromKey, excluded(fromInclusive),
1672	>	false, toKey,   excluded(toInclusive));
1673		}
1674
1675	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1675	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1676		if (!inClosedRange(toKey))
1677		throw new IllegalArgumentException("toKey out of range");
1678	<	return new AscendingSubMap(lo,    loExcluded,
1679	<	toKey, excluded(inclusive));
1678	>	return new AscendingSubMap(m,
1679	>	fromStart, lo,    loExcluded,
1680	>	false, toKey, excluded(inclusive));
1681		}
1682
1683	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1683	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1684		if (!inRange(fromKey, inclusive))
1685		throw new IllegalArgumentException("fromKey out of range");
1686	<	return new AscendingSubMap(fromKey, excluded(inclusive),
1687	<	hi,      hiExcluded);
1686	>	return new AscendingSubMap(m,
1687	>	false, fromKey, excluded(inclusive),
1688	>	toEnd, hi,      hiExcluded);
1689		}
1690
1691		Iterator<K> keyIterator() {
1692	<	return new SubMapKeyIterator
1467	<	(loEntry(),
1468	<	hi == UNBOUNDED ? null :
1469	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1470	<	getHigherEntry(hi));
1692	>	return new SubMapKeyIterator(loEntry(), hiFence());
1693		}
1694
1695		Iterator<K> descendingKeyIterator() {
1696	<	return new DescendingSubMapKeyIterator
1697	<	(hiEntry(),
1698	<	lo == UNBOUNDED ? null :
1699	<	loExcluded == 1 ? getFloorEntry(lo) :
1700	<	getLowerEntry(lo));
1696	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1697	>	}
1698	>
1699	>	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1700	>	public Iterator<Map.Entry<K,V>> iterator() {
1701	>	return new SubMapEntryIterator(loEntry(), hiFence());
1702	>	}
1703		}
1704
1705		public Set<Map.Entry<K,V>> entrySet() {
1706	<	Set<Map.Entry<K,V>> es = entrySetView;
1707	<	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	<	};
1706	>	EntrySetView es = entrySetView;
1707	>	return (es != null) ? es : new AscendingEntrySetView();
1708		}
1709
1710		public K firstKey() {
#	Line 1517 | Line 1732 | public class TreeMap<K,V>
1732		}
1733
1734		public NavigableMap<K,V> descendingMap() {
1735	<	NavigableMap<K,V> m = descendingMapView;
1736	<	return (m != null) ? m :
1735	>	NavigableMap<K,V> mv = descendingMapView;
1736	>	return (mv != null) ? mv :
1737		(descendingMapView =
1738	<	new DescendingSubMap(lo, loExcluded, hi, hiExcluded));
1738	>	new DescendingSubMap(m,
1739	>	fromStart, lo, loExcluded,
1740	>	toEnd, hi, hiExcluded));
1741		}
1742		}
1743
1744	<	class DescendingSubMap extends NavigableSubMap {
1744	>	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1745		private static final long serialVersionUID = 912986545866120460L;
1746	<	DescendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1747	<	super(lo, loExcluded, hi, hiExcluded);
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);
1750		}
1751
1752		private final Comparator<? super K> reverseComparator =
1753	<	Collections.reverseOrder(comparator);
1753	>	Collections.reverseOrder(m.comparator);
1754
1755		public Comparator<? super K> comparator() {
1756		return reverseComparator;
1757		}
1758
1759	<	public NavigableMap<K,V> navigableSubMap(
1760	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
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(toKey,   excluded(toInclusive),
1766	<	fromKey, excluded(fromInclusive));
1765	>	return new DescendingSubMap(m,
1766	>	false, toKey,   excluded(toInclusive),
1767	>	false, fromKey, excluded(fromInclusive));
1768		}
1769
1770	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
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(toKey, inclusive ? 0:1, hi, hiExcluded);
1773	>	return new DescendingSubMap(m,
1774	>	false, toKey, excluded(inclusive),
1775	>	toEnd, hi, hiExcluded);
1776		}
1777
1778	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
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(lo,      loExcluded,
1782	<	fromKey, excluded(inclusive));
1781	>	return new DescendingSubMap(m,
1782	>	fromStart, lo,      loExcluded,
1783	>	false, fromKey, excluded(inclusive));
1784		}
1785
1786		Iterator<K> keyIterator() {
1787	<	return new DescendingSubMapKeyIterator
1565	<	(hiEntry(),
1566	<	lo == UNBOUNDED ? null :
1567	<	loExcluded == 1 ? getFloorEntry(lo) :
1568	<	getLowerEntry(lo));
1787	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1788		}
1789
1790		Iterator<K> descendingKeyIterator() {
1791	<	return new SubMapKeyIterator
1792	<	(loEntry(),
1793	<	hi == UNBOUNDED ? null :
1794	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1795	<	getHigherEntry(hi));
1791	>	return new SubMapKeyIterator(loEntry(), hiFence());
1792	>	}
1793	>
1794	>	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1795	>	public Iterator<Map.Entry<K,V>> iterator() {
1796	>	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1797	>	}
1798		}
1799
1800		public Set<Map.Entry<K,V>> entrySet() {
1801	<	Set<Map.Entry<K,V>> es = entrySetView;
1802	<	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	<	};
1801	>	EntrySetView es = entrySetView;
1802	>	return (es != null) ? es : new DescendingEntrySetView();
1803		}
1804
1805		public K firstKey() {
#	Line 1615 | Line 1827 | public class TreeMap<K,V>
1827		}
1828
1829		public NavigableMap<K,V> descendingMap() {
1830	<	NavigableMap<K,V> m = descendingMapView;
1831	<	return (m != null) ? m :
1830	>	NavigableMap<K,V> mv = descendingMapView;
1831	>	return (mv != null) ? mv :
1832		(descendingMapView =
1833	<	new AscendingSubMap(lo, loExcluded, hi, hiExcluded));
1833	>	new AscendingSubMap(m,
1834	>	fromStart, lo, loExcluded,
1835	>	toEnd, hi, hiExcluded));
1836		}
1837
1838		@Override TreeMap.Entry<K,V> subCeiling(K key) {
#	Line 1639 | Line 1853 | public class TreeMap<K,V>
1853		}
1854
1855		/**
1856	+	* Compares two keys using the correct comparison method for this TreeMap.
1857	+	*/
1858	+	final int compare(Object k1, Object k2) {
1859	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1860	+	: comparator.compare((K)k1, (K)k2);
1861	+	}
1862	+
1863	+	/**
1864	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1865	+	* that it copes with <tt>null</tt> o1 properly.
1866	+	*/
1867	+	final static boolean valEquals(Object o1, Object o2) {
1868	+	return (o1==null ? o2==null : o1.equals(o2));
1869	+	}
1870	+
1871	+	/**
1872		* This class exists solely for the sake of serialization
1873		* compatibility with previous releases of TreeMap that did not
1874		* support NavigableMap.  It translates an old-version SubMap into
#	Line 1651 | Line 1881 | public class TreeMap<K,V>
1881		private boolean fromStart = false, toEnd = false;
1882		private K fromKey, toKey;
1883		private Object readResolve() {
1884	<	return new AscendingSubMap
1885	<	(fromStart? ((K)UNBOUNDED) : fromKey, 0,
1886	<	toEnd? ((K)UNBOUNDED) : toKey, 1);
1887	<	}
1888	<	public Set<Map.Entry<K,V>> entrySet() { throw new UnsupportedOperationException(); }
1889	<	public K lastKey() { throw new UnsupportedOperationException(); }
1890	<	public K firstKey() { throw new UnsupportedOperationException(); }
1891	<	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new UnsupportedOperationException(); }
1892	<	public SortedMap<K,V> headMap(K toKey) { throw new UnsupportedOperationException(); }
1893	<	public SortedMap<K,V> tailMap(K fromKey) { throw new UnsupportedOperationException(); }
1894	<	public Comparator<? super K> comparator() { throw new UnsupportedOperationException(); }
1884	>	return new AscendingSubMap(TreeMap.this,
1885	>	fromStart, fromKey, 0,
1886	>	toEnd, toKey, 1);
1887	>	}
1888	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1889	>	public K lastKey() { throw new InternalError(); }
1890	>	public K firstKey() { throw new InternalError(); }
1891	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1892	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1893	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1894	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1895		}
1896
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	–	}
1897
1898		private static final boolean RED   = false;
1899		private static final boolean BLACK = true;
#	Line 1862 | Line 1903 | public class TreeMap<K,V>
1903		* user (see Map.Entry).
1904		*/
1905
1906	<	static class Entry<K,V> implements Map.Entry<K,V> {
1906	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1907		K key;
1908		V value;
1909		Entry<K,V> left = null;
#	Line 1934 | Line 1975 | public class TreeMap<K,V>
1975		* Returns the first Entry in the TreeMap (according to the TreeMap's
1976		* key-sort function).  Returns null if the TreeMap is empty.
1977		*/
1978	<	private Entry<K,V> getFirstEntry() {
1978	>	final Entry<K,V> getFirstEntry() {
1979		Entry<K,V> p = root;
1980		if (p != null)
1981		while (p.left != null)
#	Line 1946 | Line 1987 | public class TreeMap<K,V>
1987		* Returns the last 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> getLastEntry() {
1990	>	final Entry<K,V> getLastEntry() {
1991		Entry<K,V> p = root;
1992		if (p != null)
1993		while (p.right != null)
#	Line 1957 | Line 1998 | public class TreeMap<K,V>
1998		/**
1999		* Returns the successor of the specified Entry, or null if no such.
2000		*/
2001	<	private Entry<K,V> successor(Entry<K,V> t) {
2001	>	final Entry<K,V> successor(Entry<K,V> t) {
2002		if (t == null)
2003		return null;
2004		else if (t.right != null) {
#	Line 1979 | Line 2020 | public class TreeMap<K,V>
2020		/**
2021		* Returns the predecessor of the specified Entry, or null if no such.
2022		*/
2023	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2023	>	final Entry<K,V> predecessor(Entry<K,V> t) {
2024		if (t == null)
2025		return null;
2026		else if (t.left != null) {

Diff Legend

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