ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/TreeMap.java

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.31 by dl, Fri Apr 21 13:42:57 2006 UTC vs.
Revision 1.35 by jsr166, Tue May 2 19:42:46 2006 UTC

#	Line 68 | Line 68 | package java.util;
68		* associated map using <tt>put</tt>.)
69		*
70		* <p>This class is a member of the
71	<	* <a href="{@docRoot}/../guide/collections/index.html">
71	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
72		* Java Collections Framework</a>.
73		*
74		* @param <K> the type of keys maintained by this map
#	Line 109 | Line 109 | public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
112	–	private void incrementSize()   { modCount++; size++; }
113	–	private void decrementSize()   { modCount++; size--; }
114	–
112		/**
113		* Constructs a new, empty tree map, using the natural ordering of its
114		* keys.  All keys inserted into the map must implement the {@link
#	Line 226 | Line 223 | public class TreeMap<K,V>
223		* @since 1.2
224		*/
225		public boolean containsValue(Object value) {
226	<	return (root==null ? false :
227	<	(value==null ? valueSearchNull(root)
228	<	: valueSearchNonNull(root, value)));
229	<	}
233	<
234	<	private boolean valueSearchNull(Entry n) {
235	<	if (n.value == null)
236	<	return true;
237	<
238	<	// Check left and right subtrees for value
239	<	return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
241	<	}
242	<
243	<	private boolean valueSearchNonNull(Entry n, Object value) {
244	<	// Check this node for the value
245	<	if (value.equals(n.value))
246	<	return true;
247	<
248	<	// Check left and right subtrees for value
249	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
250	<	(n.right != null && valueSearchNonNull(n.right, value));
226	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
227	>	if (valEquals(value, e.value))
228	>	return true;
229	>	return false;
230		}
231
232		/**
#	Line 361 | Line 340 | public class TreeMap<K,V>
340		* Version of getEntry using comparator. Split off from getEntry
341		* for performance. (This is not worth doing for most methods,
342		* that are less dependent on comparator performance, but is
343	<	* worthwhile for get and put.)
343	>	* worthwhile here.)
344		*/
345		final Entry<K,V> getEntryUsingComparator(Object key) {
346		K k = (K) key;
347		Comparator<? super K> cpr = comparator;
348	<	Entry<K,V> p = root;
349	<	while (p != null) {
350	<	int cmp = cpr.compare(k, p.key);
351	<	if (cmp < 0)
352	<	p = p.left;
353	<	else if (cmp > 0)
354	<	p = p.right;
355	<	else
356	<	return p;
348	>	if (cpr != null) {
349	>	Entry<K,V> p = root;
350	>	while (p != null) {
351	>	int cmp = cpr.compare(k, p.key);
352	>	if (cmp < 0)
353	>	p = p.left;
354	>	else if (cmp > 0)
355	>	p = p.right;
356	>	else
357	>	return p;
358	>	}
359		}
360		return null;
361		}
#	Line 509 | Line 490 | public class TreeMap<K,V>
490		}
491
492		/**
512	–	* Returns the key corresponding to the specified Entry.
513	–	* @throws NoSuchElementException if the Entry is null
514	–	*/
515	–	static <K> K key(Entry<K,?> e) {
516	–	if (e==null)
517	–	throw new NoSuchElementException();
518	–	return e.key;
519	–	}
520	–
521	–	/**
493		* Associates the specified value with the specified key in this map.
494		* If the map previously contained a mapping for the key, the old
495		* value is replaced.
#	Line 537 | Line 508 | public class TreeMap<K,V>
508		*         does not permit null keys
509		*/
510		public V put(K key, V value) {
540	–	// Offload comparator-based version for sake of performance
541	–	if (comparator != null)
542	–	return putUsingComparator(key, value);
543	–	if (key == null)
544	–	throw new NullPointerException();
545	–	Comparable<? super K> k = (Comparable<? super K>) key;
546	–
511		Entry<K,V> t = root;
512	<	while (t != null) {
513	<	int cmp = k.compareTo(t.key);
514	<	if (cmp == 0) {
515	<	return t.setValue(value);
516	<	} else if (cmp < 0) {
517	<	if (t.left != null) {
512	>	if (t == null) {
513	>	// TBD:
514	>	// 5045147: (coll) Adding null to an empty TreeSet should
515	>	// throw NullPointerException
516	>	//
517	>	// compare(key, key); // type check
518	>	root = new Entry<K,V>(key, value, null);
519	>	size = 1;
520	>	modCount++;
521	>	return null;
522	>	}
523	>	int cmp;
524	>	Entry<K,V> parent;
525	>	// split comparator and comparable paths
526	>	Comparator<? super K> cpr = comparator;
527	>	if (cpr != null) {
528	>	do {
529	>	parent = t;
530	>	cmp = cpr.compare(key, t.key);
531	>	if (cmp < 0)
532		t = t.left;
533	<	} else {
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) {
533	>	else if (cmp > 0)
534		t = t.right;
535	<	} else {
536	<	incrementSize();
537	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	<	return null;
567	<	}
568	<	}
535	>	else
536	>	return t.setValue(value);
537	>	} while (t != null);
538		}
539	<	incrementSize();
540	<	root = new Entry<K,V>(key, value, null);
541	<	return null;
542	<	}
543	<
544	<	/**
545	<	* Version of put using comparator. Split off from put for
546	<	* performance.
578	<	*/
579	<	final V putUsingComparator(K key, V value) {
580	<	Comparator<? super K> cpr = comparator;
581	<	Entry<K,V> t = root;
582	<	while (t != null) {
583	<	int cmp = cpr.compare(key, t.key);
584	<	if (cmp == 0) {
585	<	return t.setValue(value);
586	<	} else if (cmp < 0) {
587	<	if (t.left != null) {
539	>	else {
540	>	if (key == null)
541	>	throw new NullPointerException();
542	>	Comparable<? super K> k = (Comparable<? super K>) key;
543	>	do {
544	>	parent = t;
545	>	cmp = k.compareTo(t.key);
546	>	if (cmp < 0)
547		t = t.left;
548	<	} else {
590	<	incrementSize();
591	<	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592	<	return null;
593	<	}
594	<	} else { // cmp > 0
595	<	if (t.right != null) {
548	>	else if (cmp > 0)
549		t = t.right;
550	<	} else {
551	<	incrementSize();
552	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600	<	return null;
601	<	}
602	<	}
550	>	else
551	>	return t.setValue(value);
552	>	} while (t != null);
553		}
554	<	cpr.compare(key, key); // type check
555	<	incrementSize();
556	<	root = new Entry<K,V>(key, value, null);
554	>	Entry<K,V> e = new Entry<K,V>(key, value, parent);
555	>	if (cmp < 0)
556	>	parent.left = e;
557	>	else
558	>	parent.right = e;
559	>	fixAfterInsertion(e);
560	>	size++;
561	>	modCount++;
562		return null;
563		}
564
#	Line 679 | Line 634 | public class TreeMap<K,V>
634		* @since 1.6
635		*/
636		public Map.Entry<K,V> firstEntry() {
637	<	Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
637	>	return exportEntry(getFirstEntry());
638		}
639
640		/**
641		* @since 1.6
642		*/
643		public Map.Entry<K,V> lastEntry() {
644	<	Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
644	>	return exportEntry(getLastEntry());
645		}
646
647		/**
#	Line 696 | Line 649 | public class TreeMap<K,V>
649		*/
650		public Map.Entry<K,V> pollFirstEntry() {
651		Entry<K,V> p = getFirstEntry();
652	<	if (p == null)
653	<	return null;
654	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702	<	deleteEntry(p);
652	>	Map.Entry<K,V> result = exportEntry(p);
653	>	if (p != null)
654	>	deleteEntry(p);
655		return result;
656		}
657
#	Line 708 | Line 660 | public class TreeMap<K,V>
660		*/
661		public Map.Entry<K,V> pollLastEntry() {
662		Entry<K,V> p = getLastEntry();
663	<	if (p == null)
664	<	return null;
665	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714	<	deleteEntry(p);
663	>	Map.Entry<K,V> result = exportEntry(p);
664	>	if (p != null)
665	>	deleteEntry(p);
666		return result;
667		}
668
#	Line 723 | Line 674 | public class TreeMap<K,V>
674		* @since 1.6
675		*/
676		public Map.Entry<K,V> lowerEntry(K key) {
677	<	Entry<K,V> e =  getLowerEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
677	>	return exportEntry(getLowerEntry(key));
678		}
679
680		/**
#	Line 735 | Line 685 | public class TreeMap<K,V>
685		* @since 1.6
686		*/
687		public K lowerKey(K key) {
688	<	Entry<K,V> e =  getLowerEntry(key);
739	<	return (e == null)? null : e.key;
688	>	return keyOrNull(getLowerEntry(key));
689		}
690
691		/**
#	Line 747 | Line 696 | public class TreeMap<K,V>
696		* @since 1.6
697		*/
698		public Map.Entry<K,V> floorEntry(K key) {
699	<	Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
699	>	return exportEntry(getFloorEntry(key));
700		}
701
702		/**
#	Line 759 | Line 707 | public class TreeMap<K,V>
707		* @since 1.6
708		*/
709		public K floorKey(K key) {
710	<	Entry<K,V> e = getFloorEntry(key);
763	<	return (e == null)? null : e.key;
710	>	return keyOrNull(getFloorEntry(key));
711		}
712
713		/**
#	Line 771 | Line 718 | public class TreeMap<K,V>
718		* @since 1.6
719		*/
720		public Map.Entry<K,V> ceilingEntry(K key) {
721	<	Entry<K,V> e = getCeilingEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
721	>	return exportEntry(getCeilingEntry(key));
722		}
723
724		/**
#	Line 783 | Line 729 | public class TreeMap<K,V>
729		* @since 1.6
730		*/
731		public K ceilingKey(K key) {
732	<	Entry<K,V> e = getCeilingEntry(key);
787	<	return (e == null)? null : e.key;
732	>	return keyOrNull(getCeilingEntry(key));
733		}
734
735		/**
#	Line 795 | Line 740 | public class TreeMap<K,V>
740		* @since 1.6
741		*/
742		public Map.Entry<K,V> higherEntry(K key) {
743	<	Entry<K,V> e = getHigherEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
743	>	return exportEntry(getHigherEntry(key));
744		}
745
746		/**
#	Line 807 | Line 751 | public class TreeMap<K,V>
751		* @since 1.6
752		*/
753		public K higherKey(K key) {
754	<	Entry<K,V> e = getHigherEntry(key);
811	<	return (e == null)? null : e.key;
754	>	return keyOrNull(getHigherEntry(key));
755		}
756
757		// Views
#	Line 902 | Line 845 | public class TreeMap<K,V>
845		NavigableMap<K, V> km = descendingMap;
846		return (km != null) ? km :
847		(descendingMap = new DescendingSubMap(this,
848	<	true, null, 0,
849	<	true, null, 0));
848	>	true, null, true,
849	>	true, null, true));
850		}
851
852		/**
#	Line 917 | Line 860 | public class TreeMap<K,V>
860		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
861		K toKey,   boolean toInclusive) {
862		return new AscendingSubMap(this,
863	<	false, fromKey, excluded(fromInclusive),
864	<	false, toKey,   excluded(toInclusive));
863	>	false, fromKey, fromInclusive,
864	>	false, toKey,   toInclusive);
865		}
866
867		/**
#	Line 931 | Line 874 | public class TreeMap<K,V>
874		*/
875		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
876		return new AscendingSubMap(this,
877	<	true,  null,  0,
878	<	false, toKey, excluded(inclusive));
877	>	true,  null,  true,
878	>	false, toKey, inclusive);
879		}
880
881		/**
#	Line 945 | Line 888 | public class TreeMap<K,V>
888		*/
889		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
890		return new AscendingSubMap(this,
891	<	false, fromKey, excluded(inclusive),
892	<	true,  null,    0);
950	<	}
951	<
952	<	/**
953	<	* Translates a boolean "inclusive" value to the correct int value
954	<	* for the loExcluded or hiExcluded field.
955	<	*/
956	<	static int excluded(boolean inclusive) {
957	<	return inclusive ? 0 : 1;
891	>	false, fromKey, inclusive,
892	>	true,  null,    true);
893		}
894
895		/**
#	Line 1002 | Line 937 | public class TreeMap<K,V>
937		}
938
939		public boolean contains(Object o) {
940	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
1006	<	if (valEquals(e.getValue(), o))
1007	<	return true;
1008	<	return false;
940	>	return TreeMap.this.containsValue(o);
941		}
942
943		public boolean remove(Object o) {
#	Line 1229 | Line 1161 | public class TreeMap<K,V>
1161		}
1162		}
1163
1164	+	// Little utilities
1165	+
1166	+	/**
1167	+	* Compares two keys using the correct comparison method for this TreeMap.
1168	+	*/
1169	+	final int compare(Object k1, Object k2) {
1170	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1171	+	: comparator.compare((K)k1, (K)k2);
1172	+	}
1173	+
1174	+	/**
1175	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1176	+	* that it copes with <tt>null</tt> o1 properly.
1177	+	*/
1178	+	final static boolean valEquals(Object o1, Object o2) {
1179	+	return (o1==null ? o2==null : o1.equals(o2));
1180	+	}
1181	+
1182	+	/**
1183	+	* Return SimpleImmutableEntry for entry, or null if null
1184	+	*/
1185	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1186	+	return e == null? null :
1187	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1188	+	}
1189	+
1190	+	/**
1191	+	* Return key for entry, or null if null
1192	+	*/
1193	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1194	+	return e == null? null : e.key;
1195	+	}
1196	+
1197	+	/**
1198	+	* Returns the key corresponding to the specified Entry.
1199	+	* @throws NoSuchElementException if the Entry is null
1200	+	*/
1201	+	static <K> K key(Entry<K,?> e) {
1202	+	if (e==null)
1203	+	throw new NoSuchElementException();
1204	+	return e.key;
1205	+	}
1206	+
1207	+
1208		// SubMaps
1209
1210		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1211		implements NavigableMap<K,V>, java.io.Serializable {
1236	–
1212		/*
1213		* The backing map.
1214		*/
1215		final TreeMap<K,V> m;
1216
1217		/*
1218	<	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1219	<	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1220	<	* the low (absolute) bound is the start of the backing map, and the
1221	<	* other values are ignored. Otherwise, if loExcluded is
1222	<	* zero, lo is the inclusive bound, else loExcluded is one,
1223	<	* and lo is the exclusive bound. Similarly for the upper bound.
1218	>	* Endpoints are represented as triples (fromStart, lo,
1219	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1220	>	* true, then the low (absolute) bound is the start of the
1221	>	* backing map, and the other values are ignored. Otherwise,
1222	>	* if loInclusive is true, lo is the inclusive bound, else lo
1223	>	* is the exclusive bound. Similarly for the upper bound.
1224		*/
1225
1226		final K lo, hi;
1227		final boolean fromStart, toEnd;
1228	<	final int loExcluded, hiExcluded;
1228	>	final boolean loInclusive, hiInclusive;
1229
1230		NavigableSubMap(TreeMap<K,V> m,
1231	<	boolean fromStart, K lo, int loExcluded,
1232	<	boolean toEnd,     K hi, int hiExcluded) {
1231	>	boolean fromStart, K lo, boolean loInclusive,
1232	>	boolean toEnd,     K hi, boolean hiInclusive) {
1233		if (!fromStart && !toEnd) {
1234		if (m.compare(lo, hi) > 0)
1235		throw new IllegalArgumentException("fromKey > toKey");
1236	+	} else {
1237	+	if (!fromStart) // type check
1238	+	m.compare(lo, lo);
1239	+	if (!toEnd)
1240	+	m.compare(hi, hi);
1241		}
1262	–	else if (!fromStart) // type check
1263	–	m.compare(lo, lo);
1264	–	else if (!toEnd)
1265	–	m.compare(hi, hi);
1242
1243		this.m = m;
1244		this.fromStart = fromStart;
1245		this.lo = lo;
1246	<	this.loExcluded = loExcluded;
1246	>	this.loInclusive = loInclusive;
1247		this.toEnd = toEnd;
1248		this.hi = hi;
1249	<	this.hiExcluded = hiExcluded;
1249	>	this.hiInclusive = hiInclusive;
1250		}
1251
1252		// internal utilities
1253
1254	+	final boolean tooLow(Object key) {
1255	+	if (!fromStart) {
1256	+	int c = m.compare(key, lo);
1257	+	if (c < 0 || (c == 0 && !loInclusive))
1258	+	return true;
1259	+	}
1260	+	return false;
1261	+	}
1262	+
1263	+	final boolean tooHigh(Object key) {
1264	+	if (!toEnd) {
1265	+	int c = m.compare(key, hi);
1266	+	if (c > 0 || (c == 0 && !hiInclusive))
1267	+	return true;
1268	+	}
1269	+	return false;
1270	+	}
1271	+
1272		final boolean inRange(Object key) {
1273	<	return (fromStart || m.compare(key, lo) >= loExcluded)
1280	<	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1273	>	return !tooLow(key) && !tooHigh(key);
1274		}
1275
1276		final boolean inClosedRange(Object key) {
#	Line 1289 | Line 1282 | public class TreeMap<K,V>
1282		return inclusive ? inRange(key) : inClosedRange(key);
1283		}
1284
1285	<	final boolean tooLow(K key) {
1286	<	return !fromStart && m.compare(key, lo) < loExcluded;
1287	<	}
1288	<
1289	<	final boolean tooHigh(K key) {
1297	<	return !toEnd && m.compare(hi, key) < hiExcluded;
1298	<	}
1285	>	/*
1286	>	* Absolute versions of relation operations.
1287	>	* Subclasses map to these using like-named "sub"
1288	>	* versions that invert senses for descending maps
1289	>	*/
1290
1291	<	/** Returns the lowest entry in this submap (absolute ordering) */
1292	<	final TreeMap.Entry<K,V> loEntry() {
1302	<	TreeMap.Entry<K,V> result =
1291	>	final TreeMap.Entry<K,V> absLowest() {
1292	>	TreeMap.Entry<K,V> e =
1293		(fromStart ?  m.getFirstEntry() :
1294	<	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1295	<	m.getHigherEntry(lo)));
1296	<	return (result == null || tooHigh(result.key)) ? null : result;
1294	>	(loInclusive ? m.getCeilingEntry(lo) :
1295	>	m.getHigherEntry(lo)));
1296	>	return (e == null || tooHigh(e.key)) ? null : e;
1297		}
1298
1299	<	/** Returns the highest key in this submap (absolute ordering) */
1300	<	final TreeMap.Entry<K,V> hiEntry() {
1311	<	TreeMap.Entry<K,V> result =
1299	>	final TreeMap.Entry<K,V> absHighest() {
1300	>	TreeMap.Entry<K,V> e =
1301		(toEnd ?  m.getLastEntry() :
1302	<	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1303	<	m.getLowerEntry(hi)));
1304	<	return (result == null || tooLow(result.key)) ? null : result;
1302	>	(hiInclusive ?  m.getFloorEntry(hi) :
1303	>	m.getLowerEntry(hi)));
1304	>	return (e == null || tooLow(e.key)) ? null : e;
1305		}
1306
1307	<	/** Polls the lowest entry in this submap (absolute ordering) */
1308	<	final Map.Entry<K,V> pollLoEntry() {
1309	<	TreeMap.Entry<K,V> e = loEntry();
1310	<	if (e == null)
1311	<	return null;
1323	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1324	<	m.deleteEntry(e);
1325	<	return result;
1307	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1308	>	if (tooLow(key))
1309	>	return absLowest();
1310	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1311	>	return (e == null || tooHigh(e.key)) ? null : e;
1312		}
1313
1314	<	/** Polls the highest key in this submap (absolute ordering) */
1315	<	final Map.Entry<K,V> pollHiEntry() {
1316	<	TreeMap.Entry<K,V> e = hiEntry();
1317	<	if (e == null)
1318	<	return null;
1333	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1334	<	m.deleteEntry(e);
1335	<	return result;
1314	>	final TreeMap.Entry<K,V> absHigher(K key) {
1315	>	if (tooLow(key))
1316	>	return absLowest();
1317	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1318	>	return (e == null || tooHigh(e.key)) ? null : e;
1319		}
1320
1321	<	/**
1322	<	* Return the absolute high fence for ascending traversal
1323	<	*/
1324	<	final TreeMap.Entry<K,V> hiFence() {
1325	<	if (toEnd)
1343	<	return null;
1344	<	else if (hiExcluded == 0)
1345	<	return m.getHigherEntry(hi);
1346	<	else
1347	<	return m.getCeilingEntry(hi);
1321	>	final TreeMap.Entry<K,V> absFloor(K key) {
1322	>	if (tooHigh(key))
1323	>	return absHighest();
1324	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1325	>	return (e == null || tooLow(e.key)) ? null : e;
1326		}
1327
1328	<	/**
1329	<	* Return the absolute low fence for descending traversal
1330	<	*/
1331	<	final TreeMap.Entry<K,V> loFence() {
1332	<	if (fromStart)
1355	<	return null;
1356	<	else if (loExcluded == 0)
1357	<	return m.getLowerEntry(lo);
1358	<	else
1359	<	return m.getFloorEntry(lo);
1328	>	final TreeMap.Entry<K,V> absLower(K key) {
1329	>	if (tooHigh(key))
1330	>	return absHighest();
1331	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1332	>	return (e == null || tooLow(e.key)) ? null : e;
1333		}
1334
1335	+	/** Returns the absolute high fence for ascending traversal */
1336	+	final TreeMap.Entry<K,V> absHighFence() {
1337	+	return (toEnd ? null : (hiInclusive ?
1338	+	m.getHigherEntry(hi) :
1339	+	m.getCeilingEntry(hi)));
1340	+	}
1341	+
1342	+	/** Return the absolute low fence for descending traversal  */
1343	+	final TreeMap.Entry<K,V> absLowFence() {
1344	+	return (fromStart ? null : (loInclusive ?
1345	+	m.getLowerEntry(lo) :
1346	+	m.getFloorEntry(lo)));
1347	+	}
1348	+
1349	+	// Abstract methods defined in ascending vs descending classes
1350	+	// These relay to the appropriate  absolute versions
1351	+
1352	+	abstract TreeMap.Entry<K,V> subLowest();
1353	+	abstract TreeMap.Entry<K,V> subHighest();
1354	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1355	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1356	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1357	+	abstract TreeMap.Entry<K,V> subLower(K key);
1358	+
1359	+	/** Returns ascending iterator from the perspective of this submap */
1360	+	abstract Iterator<K> keyIterator();
1361	+
1362	+	/** Returns descending iterator from the perspective of this submap */
1363	+	abstract Iterator<K> descendingKeyIterator();
1364	+
1365	+	// public methods
1366
1367		public boolean isEmpty() {
1368	<	return entrySet().isEmpty();
1368	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1369		}
1370
1371	<	public boolean containsKey(Object key) {
1372	<	return inRange(key) && m.containsKey(key);
1371	>	public int size() {
1372	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1373		}
1374
1375	<	public V get(Object key) {
1376	<	if (!inRange(key))
1373	<	return null;
1374	<	return m.get(key);
1375	>	public final boolean containsKey(Object key) {
1376	>	return inRange(key) && m.containsKey(key);
1377		}
1378
1379	<	public V put(K key, V value) {
1379	>	public final V put(K key, V value) {
1380		if (!inRange(key))
1381		throw new IllegalArgumentException("key out of range");
1382		return m.put(key, value);
1383		}
1384
1385	<	public V remove(Object key) {
1386	<	if (!inRange(key))
1385	<	return null;
1386	<	return m.remove(key);
1385	>	public final V get(Object key) {
1386	>	return !inRange(key)? null :  m.get(key);
1387		}
1388
1389	<	public Map.Entry<K,V> ceilingEntry(K key) {
1390	<	TreeMap.Entry<K,V> e = subCeiling(key);
1391	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1389	>	public final V remove(Object key) {
1390	>	return !inRange(key)? null  : m.remove(key);
1391		}
1392
1393	<	public K ceilingKey(K key) {
1394	<	TreeMap.Entry<K,V> e = subCeiling(key);
1396	<	return e == null? null : e.key;
1393	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1394	>	return exportEntry(subCeiling(key));
1395		}
1396
1397	<	public Map.Entry<K,V> higherEntry(K key) {
1398	<	TreeMap.Entry<K,V> e = subHigher(key);
1401	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1397	>	public final K ceilingKey(K key) {
1398	>	return keyOrNull(subCeiling(key));
1399		}
1400
1401	<	public K higherKey(K key) {
1402	<	TreeMap.Entry<K,V> e = subHigher(key);
1406	<	return e == null? null : e.key;
1401	>	public final Map.Entry<K,V> higherEntry(K key) {
1402	>	return exportEntry(subHigher(key));
1403		}
1404
1405	<	public Map.Entry<K,V> floorEntry(K key) {
1406	<	TreeMap.Entry<K,V> e = subFloor(key);
1411	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1405	>	public final K higherKey(K key) {
1406	>	return keyOrNull(subHigher(key));
1407		}
1408
1409	<	public K floorKey(K key) {
1410	<	TreeMap.Entry<K,V> e = subFloor(key);
1416	<	return e == null? null : e.key;
1409	>	public final Map.Entry<K,V> floorEntry(K key) {
1410	>	return exportEntry(subFloor(key));
1411		}
1412
1413	<	public Map.Entry<K,V> lowerEntry(K key) {
1414	<	TreeMap.Entry<K,V> e = subLower(key);
1421	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1413	>	public final K floorKey(K key) {
1414	>	return keyOrNull(subFloor(key));
1415		}
1416
1417	<	public K lowerKey(K key) {
1418	<	TreeMap.Entry<K,V> e = subLower(key);
1426	<	return e == null? null : e.key;
1417	>	public final Map.Entry<K,V> lowerEntry(K key) {
1418	>	return exportEntry(subLower(key));
1419		}
1420
1421	<	abstract Iterator<K> keyIterator();
1422	<	abstract Iterator<K> descendingKeyIterator();
1421	>	public final K lowerKey(K key) {
1422	>	return keyOrNull(subLower(key));
1423	>	}
1424
1425	<	public NavigableSet<K> descendingKeySet() {
1426	<	return descendingMap().navigableKeySet();
1425	>	public final K firstKey() {
1426	>	return key(subLowest());
1427	>	}
1428	>
1429	>	public final K lastKey() {
1430	>	return key(subHighest());
1431	>	}
1432	>
1433	>	public final Map.Entry<K,V> firstEntry() {
1434	>	return exportEntry(subLowest());
1435	>	}
1436	>
1437	>	public final Map.Entry<K,V> lastEntry() {
1438	>	return exportEntry(subHighest());
1439	>	}
1440	>
1441	>	public final Map.Entry<K,V> pollFirstEntry() {
1442	>	TreeMap.Entry<K,V> e = subLowest();
1443	>	Map.Entry<K,V> result = exportEntry(e);
1444	>	if (e != null)
1445	>	m.deleteEntry(e);
1446	>	return result;
1447	>	}
1448	>
1449	>	public final Map.Entry<K,V> pollLastEntry() {
1450	>	TreeMap.Entry<K,V> e = subHighest();
1451	>	Map.Entry<K,V> result = exportEntry(e);
1452	>	if (e != null)
1453	>	m.deleteEntry(e);
1454	>	return result;
1455		}
1456
1457		// Views
#	Line 1438 | Line 1459 | public class TreeMap<K,V>
1459		transient EntrySetView entrySetView = null;
1460		transient KeySet<K> navigableKeySetView = null;
1461
1462	+	public final NavigableSet<K> navigableKeySet() {
1463	+	KeySet<K> nksv = navigableKeySetView;
1464	+	return (nksv != null) ? nksv :
1465	+	(navigableKeySetView = new TreeMap.KeySet(this));
1466	+	}
1467	+
1468	+	public final Set<K> keySet() {
1469	+	return navigableKeySet();
1470	+	}
1471	+
1472	+	public NavigableSet<K> descendingKeySet() {
1473	+	return descendingMap().navigableKeySet();
1474	+	}
1475	+
1476	+	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1477	+	return subMap(fromKey, true, toKey, false);
1478	+	}
1479	+
1480	+	public final SortedMap<K,V> headMap(K toKey) {
1481	+	return headMap(toKey, false);
1482	+	}
1483	+
1484	+	public final SortedMap<K,V> tailMap(K fromKey) {
1485	+	return tailMap(fromKey, true);
1486	+	}
1487	+
1488	+	// View classes
1489	+
1490		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1491		private transient int size = -1, sizeModCount;
1492
#	Line 1457 | Line 1506 | public class TreeMap<K,V>
1506		}
1507
1508		public boolean isEmpty() {
1509	<	TreeMap.Entry<K,V> n = loEntry();
1509	>	TreeMap.Entry<K,V> n = absLowest();
1510		return n == null || tooHigh(n.key);
1511		}
1512
#	Line 1489 | Line 1538 | public class TreeMap<K,V>
1538		}
1539		}
1540
1492	–	public NavigableSet<K> navigableKeySet() {
1493	–	KeySet<K> nksv = navigableKeySetView;
1494	–	return (nksv != null) ? nksv :
1495	–	(navigableKeySetView = new TreeMap.KeySet(this));
1496	–	}
1497	–
1498	–	public Set<K> keySet() {
1499	–	return navigableKeySet();
1500	–	}
1501	–
1502	–	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1503	–	return subMap(fromKey, true, toKey, false);
1504	–	}
1505	–
1506	–	public SortedMap<K,V> headMap(K toKey) {
1507	–	return headMap(toKey, false);
1508	–	}
1509	–
1510	–	public SortedMap<K,V> tailMap(K fromKey) {
1511	–	return tailMap(fromKey, true);
1512	–	}
1513	–
1514	–	// The following four definitions are correct only for
1515	–	// ascending submaps. They are overridden in DescendingSubMap.
1516	–	// They are defined in the base class because the definitions
1517	–	// in DescendingSubMap rely on those for AscendingSubMap.
1518	–
1519	–	/**
1520	–	* Returns the entry corresponding to the ceiling of the specified
1521	–	* key from the perspective of this submap, or null if the submap
1522	–	* contains no such entry.
1523	–	*/
1524	–	TreeMap.Entry<K,V> subCeiling(K key) {
1525	–	if (tooLow(key))
1526	–	return loEntry();
1527	–	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1528	–	return (e == null || tooHigh(e.key)) ? null : e;
1529	–	}
1530	–
1531	–	/**
1532	–	* Returns the entry corresponding to the higher of the specified
1533	–	* key from the perspective of this submap, or null if the submap
1534	–	* contains no such entry.
1535	–	*/
1536	–	TreeMap.Entry<K,V> subHigher(K key) {
1537	–	if (tooLow(key))
1538	–	return loEntry();
1539	–	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1540	–	return (e == null || tooHigh(e.key)) ? null : e;
1541	–	}
1542	–
1543	–	/**
1544	–	* Returns the entry corresponding to the floor of the specified
1545	–	* key from the perspective of this submap, or null if the submap
1546	–	* contains no such entry.
1547	–	*/
1548	–	TreeMap.Entry<K,V> subFloor(K key) {
1549	–	if (tooHigh(key))
1550	–	return hiEntry();
1551	–	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1552	–	return (e == null || tooLow(e.key)) ? null : e;
1553	–	}
1554	–
1555	–	/**
1556	–	* Returns the entry corresponding to the lower of the specified
1557	–	* key from the perspective of this submap, or null if the submap
1558	–	* contains no such entry.
1559	–	*/
1560	–	TreeMap.Entry<K,V> subLower(K key) {
1561	–	if (tooHigh(key))
1562	–	return hiEntry();
1563	–	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1564	–	return (e == null || tooLow(e.key)) ? null : e;
1565	–	}
1566	–
1541		/**
1542		* Iterators for SubMaps
1543		*/
#	Line 1640 | Line 1614 | public class TreeMap<K,V>
1614
1615		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1616		DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1617	<	TreeMap.Entry<K,V> lastExcluded) {
1618	<	super(last, lastExcluded);
1617	>	TreeMap.Entry<K,V> fence) {
1618	>	super(last, fence);
1619		}
1620
1621		public Map.Entry<K,V> next() {
#	Line 1651 | Line 1625 | public class TreeMap<K,V>
1625
1626		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1627		DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1628	<	TreeMap.Entry<K,V> lastExcluded) {
1629	<	super(last, lastExcluded);
1628	>	TreeMap.Entry<K,V> fence) {
1629	>	super(last, fence);
1630		}
1631		public K next() {
1632		return prevEntry().key;
#	Line 1660 | Line 1634 | public class TreeMap<K,V>
1634		}
1635		}
1636
1637	<	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1637	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1638		private static final long serialVersionUID = 912986545866124060L;
1639
1640		AscendingSubMap(TreeMap<K,V> m,
1641	<	boolean fromStart, K lo, int loExcluded,
1642	<	boolean toEnd, K hi, int hiExcluded) {
1643	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1641	>	boolean fromStart, K lo, boolean loInclusive,
1642	>	boolean toEnd, K hi, boolean hiInclusive) {
1643	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1644		}
1645
1646		public Comparator<? super K> comparator() {
#	Line 1680 | Line 1654 | public class TreeMap<K,V>
1654		if (!inRange(toKey, toInclusive))
1655		throw new IllegalArgumentException("toKey out of range");
1656		return new AscendingSubMap(m,
1657	<	false, fromKey, excluded(fromInclusive),
1658	<	false, toKey,   excluded(toInclusive));
1657	>	false, fromKey, fromInclusive,
1658	>	false, toKey,   toInclusive);
1659		}
1660
1661		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1662		if (!inClosedRange(toKey))
1663		throw new IllegalArgumentException("toKey out of range");
1664		return new AscendingSubMap(m,
1665	<	fromStart, lo,    loExcluded,
1666	<	false,     toKey, excluded(inclusive));
1665	>	fromStart, lo,    loInclusive,
1666	>	false,     toKey, inclusive);
1667		}
1668
1669		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1670		if (!inRange(fromKey, inclusive))
1671		throw new IllegalArgumentException("fromKey out of range");
1672		return new AscendingSubMap(m,
1673	<	false, fromKey, excluded(inclusive),
1674	<	toEnd, hi,      hiExcluded);
1673	>	false, fromKey, inclusive,
1674	>	toEnd, hi,      hiInclusive);
1675	>	}
1676	>
1677	>	public NavigableMap<K,V> descendingMap() {
1678	>	NavigableMap<K,V> mv = descendingMapView;
1679	>	return (mv != null) ? mv :
1680	>	(descendingMapView =
1681	>	new DescendingSubMap(m,
1682	>	fromStart, lo, loInclusive,
1683	>	toEnd,     hi, hiInclusive));
1684		}
1685
1686		Iterator<K> keyIterator() {
1687	<	return new SubMapKeyIterator(loEntry(), hiFence());
1687	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1688		}
1689
1690		Iterator<K> descendingKeyIterator() {
1691	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1691	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1692		}
1693
1694	<	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1694	>	final class AscendingEntrySetView extends EntrySetView {
1695		public Iterator<Map.Entry<K,V>> iterator() {
1696	<	return new SubMapEntryIterator(loEntry(), hiFence());
1696	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1697		}
1698		}
1699
#	Line 1719 | Line 1702 | public class TreeMap<K,V>
1702		return (es != null) ? es : new AscendingEntrySetView();
1703		}
1704
1705	<	public K firstKey() {
1706	<	return key(loEntry());
1707	<	}
1708	<
1709	<	public K lastKey() {
1710	<	return key(hiEntry());
1728	<	}
1729	<
1730	<	public Map.Entry<K,V> firstEntry() {
1731	<	return loEntry();
1732	<	}
1733	<
1734	<	public Map.Entry<K,V> lastEntry() {
1735	<	return hiEntry();
1736	<	}
1737	<
1738	<	public Map.Entry<K,V> pollFirstEntry() {
1739	<	return pollLoEntry();
1740	<	}
1741	<
1742	<	public Map.Entry<K,V> pollLastEntry() {
1743	<	return pollHiEntry();
1744	<	}
1745	<
1746	<	public NavigableMap<K,V> descendingMap() {
1747	<	NavigableMap<K,V> mv = descendingMapView;
1748	<	return (mv != null) ? mv :
1749	<	(descendingMapView =
1750	<	new DescendingSubMap(m,
1751	<	fromStart, lo, loExcluded,
1752	<	toEnd,     hi, hiExcluded));
1753	<	}
1705	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1706	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1707	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1708	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1709	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1710	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1711		}
1712
1713	<	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1713	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1714		private static final long serialVersionUID = 912986545866120460L;
1715		DescendingSubMap(TreeMap<K,V> m,
1716	<	boolean fromStart, K lo, int loExcluded,
1717	<	boolean toEnd, K hi, int hiExcluded) {
1718	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1716	>	boolean fromStart, K lo, boolean loInclusive,
1717	>	boolean toEnd, K hi, boolean hiInclusive) {
1718	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1719		}
1720
1721		private final Comparator<? super K> reverseComparator =
#	Line 1775 | Line 1732 | public class TreeMap<K,V>
1732		if (!inRange(toKey, toInclusive))
1733		throw new IllegalArgumentException("toKey out of range");
1734		return new DescendingSubMap(m,
1735	<	false, toKey,   excluded(toInclusive),
1736	<	false, fromKey, excluded(fromInclusive));
1735	>	false, toKey,   toInclusive,
1736	>	false, fromKey, fromInclusive);
1737		}
1738
1739		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1740		if (!inRange(toKey, inclusive))
1741		throw new IllegalArgumentException("toKey out of range");
1742		return new DescendingSubMap(m,
1743	<	false, toKey, excluded(inclusive),
1744	<	toEnd, hi,    hiExcluded);
1743	>	false, toKey, inclusive,
1744	>	toEnd, hi,    hiInclusive);
1745		}
1746
1747		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1748		if (!inRange(fromKey, inclusive))
1749		throw new IllegalArgumentException("fromKey out of range");
1750		return new DescendingSubMap(m,
1751	<	fromStart, lo, loExcluded,
1752	<	false, fromKey, excluded(inclusive));
1796	<	}
1797	<
1798	<	Iterator<K> keyIterator() {
1799	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1800	<	}
1801	<
1802	<	Iterator<K> descendingKeyIterator() {
1803	<	return new SubMapKeyIterator(loEntry(), hiFence());
1804	<	}
1805	<
1806	<	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1807	<	public Iterator<Map.Entry<K,V>> iterator() {
1808	<	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1809	<	}
1810	<	}
1811	<
1812	<	public Set<Map.Entry<K,V>> entrySet() {
1813	<	EntrySetView es = entrySetView;
1814	<	return (es != null) ? es : new DescendingEntrySetView();
1815	<	}
1816	<
1817	<	public K firstKey() {
1818	<	return key(hiEntry());
1819	<	}
1820	<
1821	<	public K lastKey() {
1822	<	return key(loEntry());
1823	<	}
1824	<
1825	<	public Map.Entry<K,V> firstEntry() {
1826	<	return hiEntry();
1827	<	}
1828	<
1829	<	public Map.Entry<K,V> lastEntry() {
1830	<	return loEntry();
1831	<	}
1832	<
1833	<	public Map.Entry<K,V> pollFirstEntry() {
1834	<	return pollHiEntry();
1835	<	}
1836	<
1837	<	public Map.Entry<K,V> pollLastEntry() {
1838	<	return pollLoEntry();
1751	>	fromStart, lo, loInclusive,
1752	>	false, fromKey, inclusive);
1753		}
1754
1755		public NavigableMap<K,V> descendingMap() {
#	Line 1843 | Line 1757 | public class TreeMap<K,V>
1757		return (mv != null) ? mv :
1758		(descendingMapView =
1759		new AscendingSubMap(m,
1760	<	fromStart, lo, loExcluded,
1761	<	toEnd, hi, hiExcluded));
1760	>	fromStart, lo, loInclusive,
1761	>	toEnd,     hi, hiInclusive));
1762		}
1763
1764	<	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1765	<	return super.subFloor(key);
1764	>	Iterator<K> keyIterator() {
1765	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1766		}
1767
1768	<	@Override TreeMap.Entry<K,V> subHigher(K key) {
1769	<	return super.subLower(key);
1768	>	Iterator<K> descendingKeyIterator() {
1769	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1770		}
1771
1772	<	@Override TreeMap.Entry<K,V> subFloor(K key) {
1773	<	return super.subCeiling(key);
1772	>	final class DescendingEntrySetView extends EntrySetView {
1773	>	public Iterator<Map.Entry<K,V>> iterator() {
1774	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1775	>	}
1776		}
1777
1778	<	@Override TreeMap.Entry<K,V> subLower(K key) {
1779	<	return super.subHigher(key);
1778	>	public Set<Map.Entry<K,V>> entrySet() {
1779	>	EntrySetView es = entrySetView;
1780	>	return (es != null) ? es : new DescendingEntrySetView();
1781		}
1865	–	}
1782
1783	<	/**
1784	<	* Compares two keys using the correct comparison method for this TreeMap.
1785	<	*/
1786	<	final int compare(Object k1, Object k2) {
1787	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1788	<	: 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));
1783	>	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1784	>	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1785	>	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1786	>	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1787	>	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1788	>	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1789		}
1790
1791		/**
#	Line 1894 | Line 1802 | public class TreeMap<K,V>
1802		private K fromKey, toKey;
1803		private Object readResolve() {
1804		return new AscendingSubMap(TreeMap.this,
1805	<	fromStart, fromKey, 0,
1806	<	toEnd, toKey, 1);
1805	>	fromStart, fromKey, true,
1806	>	toEnd, toKey, false);
1807		}
1808		public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1809		public K lastKey() { throw new InternalError(); }
#	Line 1907 | Line 1815 | public class TreeMap<K,V>
1815		}
1816
1817
1818	+	// Red-black mechanics
1819	+
1820		private static final boolean RED   = false;
1821		private static final boolean BLACK = true;
1822
#	Line 2082 | Line 1992 | public class TreeMap<K,V>
1992		return (p == null) ? null: p.right;
1993		}
1994
1995	<	/** From CLR **/
1995	>	/** From CLR */
1996		private void rotateLeft(Entry<K,V> p) {
1997	<	Entry<K,V> r = p.right;
1998	<	p.right = r.left;
1999	<	if (r.left != null)
2000	<	r.left.parent = p;
2001	<	r.parent = p.parent;
2002	<	if (p.parent == null)
2003	<	root = r;
2004	<	else if (p.parent.left == p)
2005	<	p.parent.left = r;
2006	<	else
2007	<	p.parent.right = r;
2008	<	r.left = p;
2009	<	p.parent = r;
1997	>	if (p != null) {
1998	>	Entry<K,V> r = p.right;
1999	>	p.right = r.left;
2000	>	if (r.left != null)
2001	>	r.left.parent = p;
2002	>	r.parent = p.parent;
2003	>	if (p.parent == null)
2004	>	root = r;
2005	>	else if (p.parent.left == p)
2006	>	p.parent.left = r;
2007	>	else
2008	>	p.parent.right = r;
2009	>	r.left = p;
2010	>	p.parent = r;
2011	>	}
2012		}
2013
2014	<	/** From CLR **/
2014	>	/** From CLR */
2015		private void rotateRight(Entry<K,V> p) {
2016	<	Entry<K,V> l = p.left;
2017	<	p.left = l.right;
2018	<	if (l.right != null) l.right.parent = p;
2019	<	l.parent = p.parent;
2020	<	if (p.parent == null)
2021	<	root = l;
2022	<	else if (p.parent.right == p)
2023	<	p.parent.right = l;
2024	<	else p.parent.left = l;
2025	<	l.right = p;
2026	<	p.parent = l;
2016	>	if (p != null) {
2017	>	Entry<K,V> l = p.left;
2018	>	p.left = l.right;
2019	>	if (l.right != null) l.right.parent = p;
2020	>	l.parent = p.parent;
2021	>	if (p.parent == null)
2022	>	root = l;
2023	>	else if (p.parent.right == p)
2024	>	p.parent.right = l;
2025	>	else p.parent.left = l;
2026	>	l.right = p;
2027	>	p.parent = l;
2028	>	}
2029		}
2030
2031	<
2118	<	/** From CLR **/
2031	>	/** From CLR */
2032		private void fixAfterInsertion(Entry<K,V> x) {
2033		x.color = RED;
2034
#	Line 2134 | Line 2047 | public class TreeMap<K,V>
2047		}
2048		setColor(parentOf(x), BLACK);
2049		setColor(parentOf(parentOf(x)), RED);
2050	<	if (parentOf(parentOf(x)) != null)
2138	<	rotateRight(parentOf(parentOf(x)));
2050	>	rotateRight(parentOf(parentOf(x)));
2051		}
2052		} else {
2053		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2151 | Line 2063 | public class TreeMap<K,V>
2063		}
2064		setColor(parentOf(x), BLACK);
2065		setColor(parentOf(parentOf(x)), RED);
2066	<	if (parentOf(parentOf(x)) != null)
2155	<	rotateLeft(parentOf(parentOf(x)));
2066	>	rotateLeft(parentOf(parentOf(x)));
2067		}
2068		}
2069		}
#	Line 2162 | Line 2073 | public class TreeMap<K,V>
2073		/**
2074		* Delete node p, and then rebalance the tree.
2075		*/
2165	–
2076		private void deleteEntry(Entry<K,V> p) {
2077	<	decrementSize();
2077	>	modCount++;
2078	>	size--;
2079
2080		// If strictly internal, copy successor's element to p and then make p
2081		// point to successor.
#	Line 2210 | Line 2121 | public class TreeMap<K,V>
2121		}
2122		}
2123
2124	<	/** From CLR **/
2124	>	/** From CLR */
2125		private void fixAfterDeletion(Entry<K,V> x) {
2126		while (x != root && colorOf(x) == BLACK) {
2127		if (x == leftOf(parentOf(x))) {
#	Line 2318 | Line 2229 | public class TreeMap<K,V>
2229		buildFromSorted(size, null, s, null);
2230		}
2231
2232	<	/** Intended to be called only from TreeSet.readObject **/
2232	>	/** Intended to be called only from TreeSet.readObject */
2233		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2234		throws java.io.IOException, ClassNotFoundException {
2235		buildFromSorted(size, null, s, defaultVal);
2236		}
2237
2238	<	/** Intended to be called only from TreeSet.addAll **/
2238	>	/** Intended to be called only from TreeSet.addAll */
2239		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2240		try {
2241		buildFromSorted(set.size(), set.iterator(), null, defaultVal);

Diff Legend

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