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.39 by dl, Wed May 10 19:45:01 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 95 | Line 95 | public class TreeMap<K,V>
95		*
96		* @serial
97		*/
98	<	private Comparator<? super K> comparator = null;
98	>	private final Comparator<? super K> comparator;
99
100		private transient Entry<K,V> root = null;
101
#	Line 109 | Line 109 | public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
112	–	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 125 | Line 122 | public class TreeMap<K,V>
122		* <tt>ClassCastException</tt>.
123		*/
124		public TreeMap() {
125	+	comparator = null;
126		}
127
128		/**
#	Line 160 | Line 158 | public class TreeMap<K,V>
158		* @throws NullPointerException if the specified map is null
159		*/
160		public TreeMap(Map<? extends K, ? extends V> m) {
161	+	comparator = null;
162		putAll(m);
163		}
164
#	Line 224 | 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	<	}
231	<
232	<	private boolean valueSearchNull(Entry n) {
233	<	if (n.value == null)
234	<	return true;
235	<
236	<	// Check left and right subtrees for value
237	<	return (n.left  != null && valueSearchNull(n.left)) ||
238	<	(n.right != null && valueSearchNull(n.right));
239	<	}
240	<
241	<	private boolean valueSearchNonNull(Entry n, Object value) {
242	<	// Check this node for the value
243	<	if (value.equals(n.value))
244	<	return true;
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));
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 364 | Line 345 | public class TreeMap<K,V>
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 385 | Line 368 | public class TreeMap<K,V>
368		*/
369		final Entry<K,V> getCeilingEntry(K key) {
370		Entry<K,V> p = root;
371	<	if (p==null)
389	<	return null;
390	<
391	<	while (true) {
371	>	while (p != null) {
372		int cmp = compare(key, p.key);
373		if (cmp < 0) {
374		if (p.left != null)
#	Line 410 | Line 390 | public class TreeMap<K,V>
390		} else
391		return p;
392		}
393	+	return null;
394		}
395
396		/**
#	Line 419 | Line 400 | public class TreeMap<K,V>
400		*/
401		final Entry<K,V> getFloorEntry(K key) {
402		Entry<K,V> p = root;
403	<	if (p==null)
423	<	return null;
424	<
425	<	while (true) {
403	>	while (p != null) {
404		int cmp = compare(key, p.key);
405		if (cmp > 0) {
406		if (p.right != null)
#	Line 445 | Line 423 | public class TreeMap<K,V>
423		return p;
424
425		}
426	+	return null;
427		}
428
429		/**
#	Line 455 | Line 434 | public class TreeMap<K,V>
434		*/
435		final Entry<K,V> getHigherEntry(K key) {
436		Entry<K,V> p = root;
437	<	if (p==null)
459	<	return null;
460	<
461	<	while (true) {
437	>	while (p != null) {
438		int cmp = compare(key, p.key);
439		if (cmp < 0) {
440		if (p.left != null)
#	Line 479 | Line 455 | public class TreeMap<K,V>
455		}
456		}
457		}
458	+	return null;
459		}
460
461		/**
#	Line 488 | Line 465 | public class TreeMap<K,V>
465		*/
466		final Entry<K,V> getLowerEntry(K key) {
467		Entry<K,V> p = root;
468	<	if (p==null)
492	<	return null;
493	<
494	<	while (true) {
468	>	while (p != null) {
469		int cmp = compare(key, p.key);
470		if (cmp > 0) {
471		if (p.right != null)
#	Line 512 | Line 486 | public class TreeMap<K,V>
486		}
487		}
488		}
489	<	}
516	<
517	<	/**
518	<	* Returns the key corresponding to the specified Entry.
519	<	* @throws NoSuchElementException if the Entry is null
520	<	*/
521	<	static <K> K key(Entry<K,?> e) {
522	<	if (e==null)
523	<	throw new NoSuchElementException();
524	<	return e.key;
489	>	return null;
490		}
491
492		/**
#	Line 544 | Line 509 | public class TreeMap<K,V>
509		*/
510		public V put(K key, V value) {
511		Entry<K,V> t = root;
547	–
512		if (t == null) {
513	<	// TBD
514	<	//             if (key == null) {
515	<	//                 if (comparator == null)
516	<	//                     throw new NullPointerException();
517	<	//                 comparator.compare(key, key);
554	<	//             }
555	<	incrementSize();
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	<
524	<	while (true) {
525	<	int cmp = compare(key, t.key);
526	<	if (cmp == 0) {
527	<	return t.setValue(value);
528	<	} else if (cmp < 0) {
529	<	if (t.left != null) {
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 {
568	<	incrementSize();
569	<	t.left = new Entry<K,V>(key, value, t);
570	<	fixAfterInsertion(t.left);
571	<	return null;
572	<	}
573	<	} else { // cmp > 0
574	<	if (t.right != null) {
533	>	else if (cmp > 0)
534		t = t.right;
535	<	} else {
536	<	incrementSize();
537	<	t.right = new Entry<K,V>(key, value, t);
579	<	fixAfterInsertion(t.right);
580	<	return null;
581	<	}
582	<	}
535	>	else
536	>	return t.setValue(value);
537	>	} while (t != null);
538		}
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 if (cmp > 0)
549	+	t = t.right;
550	+	else
551	+	return t.setValue(value);
552	+	} while (t != null);
553	+	}
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
565		/**
#	Line 655 | 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();
659	<	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();
667	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
644	>	return exportEntry(getLastEntry());
645		}
646
647		/**
#	Line 672 | 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);
678	<	deleteEntry(p);
652	>	Map.Entry<K,V> result = exportEntry(p);
653	>	if (p != null)
654	>	deleteEntry(p);
655		return result;
656		}
657
#	Line 684 | 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);
690	<	deleteEntry(p);
663	>	Map.Entry<K,V> result = exportEntry(p);
664	>	if (p != null)
665	>	deleteEntry(p);
666		return result;
667		}
668
#	Line 699 | 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);
703	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
677	>	return exportEntry(getLowerEntry(key));
678		}
679
680		/**
#	Line 711 | 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);
715	<	return (e == null)? null : e.key;
688	>	return keyOrNull(getLowerEntry(key));
689		}
690
691		/**
#	Line 723 | 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);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
699	>	return exportEntry(getFloorEntry(key));
700		}
701
702		/**
#	Line 735 | 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);
739	<	return (e == null)? null : e.key;
710	>	return keyOrNull(getFloorEntry(key));
711		}
712
713		/**
#	Line 747 | 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);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
721	>	return exportEntry(getCeilingEntry(key));
722		}
723
724		/**
#	Line 759 | 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);
763	<	return (e == null)? null : e.key;
732	>	return keyOrNull(getCeilingEntry(key));
733		}
734
735		/**
#	Line 771 | 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);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
743	>	return exportEntry(getHigherEntry(key));
744		}
745
746		/**
#	Line 783 | 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);
787	<	return (e == null)? null : e.key;
754	>	return keyOrNull(getHigherEntry(key));
755		}
756
757		// Views
#	Line 877 | Line 844 | public class TreeMap<K,V>
844		public NavigableMap<K, V> descendingMap() {
845		NavigableMap<K, V> km = descendingMap;
846		return (km != null) ? km :
847	<	(descendingMap = new DescendingSubMap(this,
848	<	true, null, 0,
849	<	true, null, 0));
847	>	(descendingMap = new DescendingSubMap(this,
848	>	true, null, true,
849	>	true, null, true));
850		}
851
852		/**
#	Line 892 | Line 859 | public class TreeMap<K,V>
859		*/
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));
862	>	return new AscendingSubMap(this,
863	>	false, fromKey, fromInclusive,
864	>	false, toKey,   toInclusive);
865		}
866
867		/**
#	Line 906 | Line 873 | public class TreeMap<K,V>
873		* @since 1.6
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));
876	>	return new AscendingSubMap(this,
877	>	true,  null,  true,
878	>	false, toKey, inclusive);
879		}
880
881		/**
#	Line 920 | Line 887 | public class TreeMap<K,V>
887		* @since 1.6
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);
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;
890	>	return new AscendingSubMap(this,
891	>	false, fromKey, inclusive,
892	>	true,  null,    true);
893		}
894
895		/**
#	Line 978 | 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))
982	<	if (valEquals(e.getValue(), o))
983	<	return true;
984	<	return false;
940	>	return TreeMap.this.containsValue(o);
941		}
942
943		public boolean remove(Object o) {
#	Line 1093 | Line 1049 | public class TreeMap<K,V>
1049		m.remove(o);
1050		return size() != oldSize;
1051		}
1052	<	public NavigableSet<E> subSet(E fromElement,
1053	<	boolean fromInclusive,
1054	<	E toElement,
1055	<	boolean toInclusive) {
1100	<	return new TreeSet<E>
1101	<	(m.subMap(fromElement, fromInclusive,
1102	<	toElement,   toInclusive));
1052	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1053	>	E toElement,   boolean toInclusive) {
1054	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1055	>	toElement,   toInclusive));
1056		}
1057		public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1058		return new TreeSet<E>(m.headMap(toElement, inclusive));
#	Line 1125 | Line 1078 | public class TreeMap<K,V>
1078		* Base class for TreeMap Iterators
1079		*/
1080		abstract class PrivateEntryIterator<T> implements Iterator<T> {
1128	–	int expectedModCount = TreeMap.this.modCount;
1129	–	Entry<K,V> lastReturned = null;
1081		Entry<K,V> next;
1082	+	Entry<K,V> lastReturned;
1083	+	int expectedModCount;
1084
1085		PrivateEntryIterator(Entry<K,V> first) {
1086	+	expectedModCount = modCount;
1087	+	lastReturned = null;
1088		next = first;
1089		}
1090
#	Line 1138 | Line 1093 | public class TreeMap<K,V>
1093		}
1094
1095		final Entry<K,V> nextEntry() {
1096	<	if (next == null)
1096	>	Entry<K,V> e = lastReturned = next;
1097	>	if (e == null)
1098		throw new NoSuchElementException();
1099		if (modCount != expectedModCount)
1100		throw new ConcurrentModificationException();
1101	<	lastReturned = next;
1102	<	next = successor(next);
1147	<	return lastReturned;
1101	>	next = successor(e);
1102	>	return e;
1103		}
1104
1105		final Entry<K,V> prevEntry() {
1106	<	if (next == null)
1106	>	Entry<K,V> e = lastReturned= next;
1107	>	if (e == null)
1108		throw new NoSuchElementException();
1109		if (modCount != expectedModCount)
1110		throw new ConcurrentModificationException();
1111	<	lastReturned = next;
1112	<	next = predecessor(next);
1157	<	return lastReturned;
1111	>	next = predecessor(e);
1112	>	return e;
1113		}
1114
1115		public void remove() {
#	Line 1162 | Line 1117 | public class TreeMap<K,V>
1117		throw new IllegalStateException();
1118		if (modCount != expectedModCount)
1119		throw new ConcurrentModificationException();
1120	+	// deleted entries are replaced by their successors
1121		if (lastReturned.left != null && lastReturned.right != null)
1122		next = lastReturned;
1123		deleteEntry(lastReturned);
1124	<	expectedModCount++;
1124	>	expectedModCount = modCount;
1125		lastReturned = null;
1126		}
1127		}
#	Line 1206 | Line 1162 | public class TreeMap<K,V>
1162		}
1163		}
1164
1165	<	// SubMaps
1165	>	// Little utilities
1166
1167	<	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1168	<	implements NavigableMap<K,V>, java.io.Serializable {
1167	>	/**
1168	>	* Compares two keys using the correct comparison method for this TreeMap.
1169	>	*/
1170	>	final int compare(Object k1, Object k2) {
1171	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1172	>	: comparator.compare((K)k1, (K)k2);
1173	>	}
1174
1175	<	/*
1176	<	* The backing map.
1177	<	*/
1178	<	final TreeMap<K,V> m;
1175	>	/**
1176	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1177	>	* that it copes with <tt>null</tt> o1 properly.
1178	>	*/
1179	>	final static boolean valEquals(Object o1, Object o2) {
1180	>	return (o1==null ? o2==null : o1.equals(o2));
1181	>	}
1182
1183	<	/** True if low point is from start of backing map */
1184	<	boolean fromStart;
1183	>	/**
1184	>	* Return SimpleImmutableEntry for entry, or null if null
1185	>	*/
1186	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1187	>	return e == null? null :
1188	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1189	>	}
1190
1191	<	/**
1192	<	* The low endpoint of this submap in absolute terms, or null
1193	<	* if fromStart.
1194	<	*/
1195	<	K lo;
1191	>	/**
1192	>	* Return key for entry, or null if null
1193	>	*/
1194	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1195	>	return e == null? null : e.key;
1196	>	}
1197
1198	<	/**
1199	<	* Zero if the low endpoint is excluded from this submap, one if
1200	<	* it's included.  This field is unused if fromStart.
1201	<	*/
1202	<	int loExcluded;
1198	>	/**
1199	>	* Returns the key corresponding to the specified Entry.
1200	>	* @throws NoSuchElementException if the Entry is null
1201	>	*/
1202	>	static <K> K key(Entry<K,?> e) {
1203	>	if (e==null)
1204	>	throw new NoSuchElementException();
1205	>	return e.key;
1206	>	}
1207
1234	–	/** True if high point is to End of backing map */
1235	–	boolean toEnd;
1208
1209	<	/**
1210	<	* The high endpoint of this submap in absolute terms, or null
1211	<	* if toEnd.
1209	>	// SubMaps
1210	>
1211	>	/**
1212	>	* @serial include
1213	>	*/
1214	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1215	>	implements NavigableMap<K,V>, java.io.Serializable {
1216	>	/**
1217	>	* The backing map.
1218		*/
1219	<	K hi;
1219	>	final TreeMap<K,V> m;
1220
1221		/**
1222	<	* Zero if the high endpoint is excluded from this submap, one if
1223	<	* it's included.  This field is unused if toEnd.
1222	>	* Endpoints are represented as triples (fromStart, lo,
1223	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1224	>	* true, then the low (absolute) bound is the start of the
1225	>	* backing map, and the other values are ignored. Otherwise,
1226	>	* if loInclusive is true, lo is the inclusive bound, else lo
1227	>	* is the exclusive bound. Similarly for the upper bound.
1228		*/
1229	<	int hiExcluded;
1229	>	final K lo, hi;
1230	>	final boolean fromStart, toEnd;
1231	>	final boolean loInclusive, hiInclusive;
1232	>
1233	>	NavigableSubMap(TreeMap<K,V> m,
1234	>	boolean fromStart, K lo, boolean loInclusive,
1235	>	boolean toEnd,     K hi, boolean hiInclusive) {
1236	>	if (!fromStart && !toEnd) {
1237	>	if (m.compare(lo, hi) > 0)
1238	>	throw new IllegalArgumentException("fromKey > toKey");
1239	>	} else {
1240	>	if (!fromStart) // type check
1241	>	m.compare(lo, lo);
1242	>	if (!toEnd)
1243	>	m.compare(hi, hi);
1244	>	}
1245
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");
1246		this.m = m;
1247		this.fromStart = fromStart;
1248		this.lo = lo;
1249	<	this.loExcluded = loExcluded;
1249	>	this.loInclusive = loInclusive;
1250		this.toEnd = toEnd;
1251		this.hi = hi;
1252	<	this.hiExcluded = hiExcluded;
1252	>	this.hiInclusive = hiInclusive;
1253		}
1254
1255		// internal utilities
1256
1257	+	final boolean tooLow(Object key) {
1258	+	if (!fromStart) {
1259	+	int c = m.compare(key, lo);
1260	+	if (c < 0 || (c == 0 && !loInclusive))
1261	+	return true;
1262	+	}
1263	+	return false;
1264	+	}
1265	+
1266	+	final boolean tooHigh(Object key) {
1267	+	if (!toEnd) {
1268	+	int c = m.compare(key, hi);
1269	+	if (c > 0 || (c == 0 && !hiInclusive))
1270	+	return true;
1271	+	}
1272	+	return false;
1273	+	}
1274	+
1275		final boolean inRange(Object key) {
1276	<	return (fromStart || m.compare(key, lo) >= loExcluded)
1267	<	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1276	>	return !tooLow(key) && !tooHigh(key);
1277		}
1278
1279		final boolean inClosedRange(Object key) {
#	Line 1276 | Line 1285 | public class TreeMap<K,V>
1285		return inclusive ? inRange(key) : inClosedRange(key);
1286		}
1287
1288	<	final boolean tooLow(K key) {
1289	<	return !fromStart && m.compare(key, lo) < loExcluded;
1290	<	}
1291	<
1292	<	final boolean tooHigh(K key) {
1284	<	return !toEnd && m.compare(hi, key) < hiExcluded;
1285	<	}
1286	<
1288	>	/*
1289	>	* Absolute versions of relation operations.
1290	>	* Subclasses map to these using like-named "sub"
1291	>	* versions that invert senses for descending maps
1292	>	*/
1293
1294	<	/** Returns the lowest entry in this submap (absolute ordering) */
1295	<	final TreeMap.Entry<K,V> loEntry() {
1290	<	TreeMap.Entry<K,V> result =
1294	>	final TreeMap.Entry<K,V> absLowest() {
1295	>	TreeMap.Entry<K,V> e =
1296		(fromStart ?  m.getFirstEntry() :
1297	<	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1298	<	m.getHigherEntry(lo)));
1299	<	return (result == null || tooHigh(result.key)) ? null : result;
1297	>	(loInclusive ? m.getCeilingEntry(lo) :
1298	>	m.getHigherEntry(lo)));
1299	>	return (e == null || tooHigh(e.key)) ? null : e;
1300		}
1301
1302	<	/** Returns the highest key in this submap (absolute ordering) */
1303	<	final TreeMap.Entry<K,V> hiEntry() {
1299	<	TreeMap.Entry<K,V> result =
1302	>	final TreeMap.Entry<K,V> absHighest() {
1303	>	TreeMap.Entry<K,V> e =
1304		(toEnd ?  m.getLastEntry() :
1305	<	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1306	<	m.getLowerEntry(hi)));
1307	<	return (result == null || tooLow(result.key)) ? null : result;
1305	>	(hiInclusive ?  m.getFloorEntry(hi) :
1306	>	m.getLowerEntry(hi)));
1307	>	return (e == null || tooLow(e.key)) ? null : e;
1308		}
1309
1310	<	/** Polls the lowest entry in this submap (absolute ordering) */
1311	<	final Map.Entry<K,V> pollLoEntry() {
1312	<	TreeMap.Entry<K,V> e = loEntry();
1313	<	if (e == null)
1314	<	return null;
1311	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1312	<	m.deleteEntry(e);
1313	<	return result;
1310	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1311	>	if (tooLow(key))
1312	>	return absLowest();
1313	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1314	>	return (e == null || tooHigh(e.key)) ? null : e;
1315		}
1316
1317	<	/** Polls the highest key in this submap (absolute ordering) */
1318	<	final Map.Entry<K,V> pollHiEntry() {
1319	<	TreeMap.Entry<K,V> e = hiEntry();
1320	<	if (e == null)
1321	<	return null;
1321	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1322	<	m.deleteEntry(e);
1323	<	return result;
1317	>	final TreeMap.Entry<K,V> absHigher(K key) {
1318	>	if (tooLow(key))
1319	>	return absLowest();
1320	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1321	>	return (e == null || tooHigh(e.key)) ? null : e;
1322		}
1323
1324	<	/**
1325	<	* Return the absolute high fence for ascending traversal
1326	<	*/
1327	<	final TreeMap.Entry<K,V> hiFence() {
1328	<	if (toEnd)
1331	<	return null;
1332	<	else if (hiExcluded == 0)
1333	<	return m.getHigherEntry(hi);
1334	<	else
1335	<	return m.getCeilingEntry(hi);
1324	>	final TreeMap.Entry<K,V> absFloor(K key) {
1325	>	if (tooHigh(key))
1326	>	return absHighest();
1327	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1328	>	return (e == null || tooLow(e.key)) ? null : e;
1329		}
1330
1331	<	/**
1332	<	* Return the absolute low fence for descending traversal
1333	<	*/
1334	<	final TreeMap.Entry<K,V> loFence() {
1335	<	if (fromStart)
1343	<	return null;
1344	<	else if (loExcluded == 0)
1345	<	return m.getLowerEntry(lo);
1346	<	else
1347	<	return m.getFloorEntry(lo);
1331	>	final TreeMap.Entry<K,V> absLower(K key) {
1332	>	if (tooHigh(key))
1333	>	return absHighest();
1334	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1335	>	return (e == null || tooLow(e.key)) ? null : e;
1336		}
1337
1338	+	/** Returns the absolute high fence for ascending traversal */
1339	+	final TreeMap.Entry<K,V> absHighFence() {
1340	+	return (toEnd ? null : (hiInclusive ?
1341	+	m.getHigherEntry(hi) :
1342	+	m.getCeilingEntry(hi)));
1343	+	}
1344	+
1345	+	/** Return the absolute low fence for descending traversal  */
1346	+	final TreeMap.Entry<K,V> absLowFence() {
1347	+	return (fromStart ? null : (loInclusive ?
1348	+	m.getLowerEntry(lo) :
1349	+	m.getFloorEntry(lo)));
1350	+	}
1351	+
1352	+	// Abstract methods defined in ascending vs descending classes
1353	+	// These relay to the appropriate absolute versions
1354	+
1355	+	abstract TreeMap.Entry<K,V> subLowest();
1356	+	abstract TreeMap.Entry<K,V> subHighest();
1357	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1358	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1359	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1360	+	abstract TreeMap.Entry<K,V> subLower(K key);
1361	+
1362	+	/** Returns ascending iterator from the perspective of this submap */
1363	+	abstract Iterator<K> keyIterator();
1364	+
1365	+	/** Returns descending iterator from the perspective of this submap */
1366	+	abstract Iterator<K> descendingKeyIterator();
1367	+
1368	+	// public methods
1369
1370		public boolean isEmpty() {
1371	<	return entrySet().isEmpty();
1371	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1372		}
1373
1374	<	public boolean containsKey(Object key) {
1375	<	return inRange(key) && m.containsKey(key);
1374	>	public int size() {
1375	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1376		}
1377
1378	<	public V get(Object key) {
1379	<	if (!inRange(key))
1361	<	return null;
1362	<	return m.get(key);
1378	>	public final boolean containsKey(Object key) {
1379	>	return inRange(key) && m.containsKey(key);
1380		}
1381
1382	<	public V put(K key, V value) {
1382	>	public final V put(K key, V value) {
1383		if (!inRange(key))
1384		throw new IllegalArgumentException("key out of range");
1385		return m.put(key, value);
1386		}
1387
1388	<	public V remove(Object key) {
1389	<	if (!inRange(key))
1373	<	return null;
1374	<	return m.remove(key);
1388	>	public final V get(Object key) {
1389	>	return !inRange(key)? null :  m.get(key);
1390		}
1391
1392	<	public Map.Entry<K,V> ceilingEntry(K key) {
1393	<	TreeMap.Entry<K,V> e = subCeiling(key);
1379	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1392	>	public final V remove(Object key) {
1393	>	return !inRange(key)? null  : m.remove(key);
1394		}
1395
1396	<	public K ceilingKey(K key) {
1397	<	TreeMap.Entry<K,V> e = subCeiling(key);
1384	<	return e == null? null : e.key;
1396	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1397	>	return exportEntry(subCeiling(key));
1398		}
1399
1400	<	public Map.Entry<K,V> higherEntry(K key) {
1401	<	TreeMap.Entry<K,V> e = subHigher(key);
1389	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1400	>	public final K ceilingKey(K key) {
1401	>	return keyOrNull(subCeiling(key));
1402		}
1403
1404	<	public K higherKey(K key) {
1405	<	TreeMap.Entry<K,V> e = subHigher(key);
1394	<	return e == null? null : e.key;
1404	>	public final Map.Entry<K,V> higherEntry(K key) {
1405	>	return exportEntry(subHigher(key));
1406		}
1407
1408	<	public Map.Entry<K,V> floorEntry(K key) {
1409	<	TreeMap.Entry<K,V> e = subFloor(key);
1399	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1408	>	public final K higherKey(K key) {
1409	>	return keyOrNull(subHigher(key));
1410		}
1411
1412	<	public K floorKey(K key) {
1413	<	TreeMap.Entry<K,V> e = subFloor(key);
1404	<	return e == null? null : e.key;
1412	>	public final Map.Entry<K,V> floorEntry(K key) {
1413	>	return exportEntry(subFloor(key));
1414		}
1415
1416	<	public Map.Entry<K,V> lowerEntry(K key) {
1417	<	TreeMap.Entry<K,V> e = subLower(key);
1409	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1416	>	public final K floorKey(K key) {
1417	>	return keyOrNull(subFloor(key));
1418		}
1419
1420	<	public K lowerKey(K key) {
1421	<	TreeMap.Entry<K,V> e = subLower(key);
1414	<	return e == null? null : e.key;
1420	>	public final Map.Entry<K,V> lowerEntry(K key) {
1421	>	return exportEntry(subLower(key));
1422		}
1423
1424	<	abstract Iterator<K> keyIterator();
1425	<	abstract Iterator<K> descendingKeyIterator();
1424	>	public final K lowerKey(K key) {
1425	>	return keyOrNull(subLower(key));
1426	>	}
1427
1428	<	public NavigableSet<K> descendingKeySet() {
1429	<	return descendingMap().navigableKeySet();
1428	>	public final K firstKey() {
1429	>	return key(subLowest());
1430	>	}
1431	>
1432	>	public final K lastKey() {
1433	>	return key(subHighest());
1434	>	}
1435	>
1436	>	public final Map.Entry<K,V> firstEntry() {
1437	>	return exportEntry(subLowest());
1438	>	}
1439	>
1440	>	public final Map.Entry<K,V> lastEntry() {
1441	>	return exportEntry(subHighest());
1442	>	}
1443	>
1444	>	public final Map.Entry<K,V> pollFirstEntry() {
1445	>	TreeMap.Entry<K,V> e = subLowest();
1446	>	Map.Entry<K,V> result = exportEntry(e);
1447	>	if (e != null)
1448	>	m.deleteEntry(e);
1449	>	return result;
1450	>	}
1451	>
1452	>	public final Map.Entry<K,V> pollLastEntry() {
1453	>	TreeMap.Entry<K,V> e = subHighest();
1454	>	Map.Entry<K,V> result = exportEntry(e);
1455	>	if (e != null)
1456	>	m.deleteEntry(e);
1457	>	return result;
1458		}
1459
1460		// Views
#	Line 1426 | Line 1462 | public class TreeMap<K,V>
1462		transient EntrySetView entrySetView = null;
1463		transient KeySet<K> navigableKeySetView = null;
1464
1465	+	public final NavigableSet<K> navigableKeySet() {
1466	+	KeySet<K> nksv = navigableKeySetView;
1467	+	return (nksv != null) ? nksv :
1468	+	(navigableKeySetView = new TreeMap.KeySet(this));
1469	+	}
1470	+
1471	+	public final Set<K> keySet() {
1472	+	return navigableKeySet();
1473	+	}
1474	+
1475	+	public NavigableSet<K> descendingKeySet() {
1476	+	return descendingMap().navigableKeySet();
1477	+	}
1478	+
1479	+	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1480	+	return subMap(fromKey, true, toKey, false);
1481	+	}
1482	+
1483	+	public final SortedMap<K,V> headMap(K toKey) {
1484	+	return headMap(toKey, false);
1485	+	}
1486	+
1487	+	public final SortedMap<K,V> tailMap(K fromKey) {
1488	+	return tailMap(fromKey, true);
1489	+	}
1490	+
1491	+	// View classes
1492	+
1493		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1494		private transient int size = -1, sizeModCount;
1495
#	Line 1434 | Line 1498 | public class TreeMap<K,V>
1498		return m.size();
1499		if (size == -1 || sizeModCount != m.modCount) {
1500		sizeModCount = m.modCount;
1501	<	size = 0;
1501	>	size = 0;
1502		Iterator i = iterator();
1503		while (i.hasNext()) {
1504		size++;
#	Line 1445 | Line 1509 | public class TreeMap<K,V>
1509		}
1510
1511		public boolean isEmpty() {
1512	<	TreeMap.Entry<K,V> n = loEntry();
1512	>	TreeMap.Entry<K,V> n = absLowest();
1513		return n == null || tooHigh(n.key);
1514		}
1515
#	Line 1477 | Line 1541 | public class TreeMap<K,V>
1541		}
1542		}
1543
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	–
1544		/**
1545		* Iterators for SubMaps
1546		*/
1547		abstract class SubMapIterator<T> implements Iterator<T> {
1548	<	int expectedModCount = m.modCount;
1561	<	TreeMap.Entry<K,V> lastReturned = null;
1548	>	TreeMap.Entry<K,V> lastReturned;
1549		TreeMap.Entry<K,V> next;
1550	<	final K firstExcludedKey;
1550	>	final K fenceKey;
1551	>	int expectedModCount;
1552
1553	<	SubMapIterator(TreeMap.Entry<K,V> first,
1554	<	TreeMap.Entry<K,V> firstExcluded) {
1553	>	SubMapIterator(TreeMap.Entry<K,V> first,
1554	>	TreeMap.Entry<K,V> fence) {
1555	>	expectedModCount = m.modCount;
1556	>	lastReturned = null;
1557		next = first;
1558	<	firstExcludedKey = (firstExcluded == null ? null
1569	<	: firstExcluded.key);
1558	>	fenceKey = fence == null ? null : fence.key;
1559		}
1560
1561		public final boolean hasNext() {
1562	<	return next != null && next.key != firstExcludedKey;
1562	>	return next != null && next.key != fenceKey;
1563		}
1564
1565		final TreeMap.Entry<K,V> nextEntry() {
1566	<	if (next == null || next.key == firstExcludedKey)
1566	>	TreeMap.Entry<K,V> e = lastReturned = next;
1567	>	if (e == null || e.key == fenceKey)
1568		throw new NoSuchElementException();
1569		if (m.modCount != expectedModCount)
1570		throw new ConcurrentModificationException();
1571	<	lastReturned = next;
1572	<	next = m.successor(next);
1583	<	return lastReturned;
1571	>	next = successor(e);
1572	>	return e;
1573		}
1574
1575		final TreeMap.Entry<K,V> prevEntry() {
1576	<	if (next == null || next.key == firstExcludedKey)
1576	>	TreeMap.Entry<K,V> e = lastReturned = next;
1577	>	if (e == null || e.key == fenceKey)
1578		throw new NoSuchElementException();
1579		if (m.modCount != expectedModCount)
1580		throw new ConcurrentModificationException();
1581	<	lastReturned = next;
1582	<	next = m.predecessor(next);
1593	<	return lastReturned;
1581	>	next = predecessor(e);
1582	>	return e;
1583		}
1584
1585	<	public void remove() {
1585	>	final void removeAscending() {
1586		if (lastReturned == null)
1587		throw new IllegalStateException();
1588		if (m.modCount != expectedModCount)
1589		throw new ConcurrentModificationException();
1590	+	// deleted entries are replaced by their successors
1591		if (lastReturned.left != null && lastReturned.right != null)
1592		next = lastReturned;
1593		m.deleteEntry(lastReturned);
1604	–	expectedModCount++;
1594		lastReturned = null;
1595	+	expectedModCount = m.modCount;
1596		}
1597	+
1598	+	final void removeDescending() {
1599	+	if (lastReturned == null)
1600	+	throw new IllegalStateException();
1601	+	if (m.modCount != expectedModCount)
1602	+	throw new ConcurrentModificationException();
1603	+	m.deleteEntry(lastReturned);
1604	+	lastReturned = null;
1605	+	expectedModCount = m.modCount;
1606	+	}
1607	+
1608		}
1609
1610		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1611	<	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1612	<	TreeMap.Entry<K,V> firstExcluded) {
1613	<	super(first, firstExcluded);
1611	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1612	>	TreeMap.Entry<K,V> fence) {
1613	>	super(first, fence);
1614		}
1615		public Map.Entry<K,V> next() {
1616		return nextEntry();
1617		}
1618	+	public void remove() {
1619	+	removeAscending();
1620	+	}
1621		}
1622
1623		final class SubMapKeyIterator extends SubMapIterator<K> {
1624	<	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1625	<	TreeMap.Entry<K,V> firstExcluded) {
1626	<	super(first, firstExcluded);
1624	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1625	>	TreeMap.Entry<K,V> fence) {
1626	>	super(first, fence);
1627		}
1628		public K next() {
1629		return nextEntry().key;
1630		}
1631	+	public void remove() {
1632	+	removeAscending();
1633	+	}
1634		}
1635
1636		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1637	<	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1638	<	TreeMap.Entry<K,V> lastExcluded) {
1639	<	super(last, lastExcluded);
1637	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1638	>	TreeMap.Entry<K,V> fence) {
1639	>	super(last, fence);
1640		}
1641
1642		public Map.Entry<K,V> next() {
1643		return prevEntry();
1644		}
1645	+	public void remove() {
1646	+	removeDescending();
1647	+	}
1648		}
1649
1650		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1651	<	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1652	<	TreeMap.Entry<K,V> lastExcluded) {
1653	<	super(last, lastExcluded);
1651	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1652	>	TreeMap.Entry<K,V> fence) {
1653	>	super(last, fence);
1654		}
1655		public K next() {
1656		return prevEntry().key;
1657		}
1658	+	public void remove() {
1659	+	removeDescending();
1660	+	}
1661		}
1662		}
1663
1664	<	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1664	>	/**
1665	>	* @serial include
1666	>	*/
1667	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1668		private static final long serialVersionUID = 912986545866124060L;
1669
1670	<	AscendingSubMap(TreeMap<K,V> m,
1671	<	boolean fromStart, K lo, int loExcluded,
1672	<	boolean toEnd, K hi, int hiExcluded) {
1673	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1670	>	AscendingSubMap(TreeMap<K,V> m,
1671	>	boolean fromStart, K lo, boolean loInclusive,
1672	>	boolean toEnd,     K hi, boolean hiInclusive) {
1673	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1674		}
1675
1676		public Comparator<? super K> comparator() {
1677		return m.comparator();
1678		}
1679
1680	<	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1681	<	K toKey, boolean toInclusive) {
1680	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1681	>	K toKey,   boolean toInclusive) {
1682		if (!inRange(fromKey, fromInclusive))
1683		throw new IllegalArgumentException("fromKey out of range");
1684		if (!inRange(toKey, toInclusive))
1685		throw new IllegalArgumentException("toKey out of range");
1686	<	return new AscendingSubMap(m,
1687	<	false, fromKey, excluded(fromInclusive),
1688	<	false, toKey,   excluded(toInclusive));
1686	>	return new AscendingSubMap(m,
1687	>	false, fromKey, fromInclusive,
1688	>	false, toKey,   toInclusive);
1689		}
1690
1691		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1692	<	if (!inClosedRange(toKey))
1692	>	if (!inRange(toKey, inclusive))
1693		throw new IllegalArgumentException("toKey out of range");
1694	<	return new AscendingSubMap(m,
1695	<	fromStart, lo,    loExcluded,
1696	<	false, toKey, excluded(inclusive));
1694	>	return new AscendingSubMap(m,
1695	>	fromStart, lo,    loInclusive,
1696	>	false,     toKey, inclusive);
1697		}
1698
1699		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1700		if (!inRange(fromKey, inclusive))
1701		throw new IllegalArgumentException("fromKey out of range");
1702	<	return new AscendingSubMap(m,
1703	<	false, fromKey, excluded(inclusive),
1704	<	toEnd, hi,      hiExcluded);
1702	>	return new AscendingSubMap(m,
1703	>	false, fromKey, inclusive,
1704	>	toEnd, hi,      hiInclusive);
1705	>	}
1706	>
1707	>	public NavigableMap<K,V> descendingMap() {
1708	>	NavigableMap<K,V> mv = descendingMapView;
1709	>	return (mv != null) ? mv :
1710	>	(descendingMapView =
1711	>	new DescendingSubMap(m,
1712	>	fromStart, lo, loInclusive,
1713	>	toEnd,     hi, hiInclusive));
1714		}
1715
1716		Iterator<K> keyIterator() {
1717	<	return new SubMapKeyIterator(loEntry(), hiFence());
1717	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1718		}
1719
1720		Iterator<K> descendingKeyIterator() {
1721	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1721	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1722		}
1723
1724	<	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1724	>	final class AscendingEntrySetView extends EntrySetView {
1725		public Iterator<Map.Entry<K,V>> iterator() {
1726	<	return new SubMapEntryIterator(loEntry(), hiFence());
1726	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1727		}
1728		}
1729
#	Line 1707 | Line 1732 | public class TreeMap<K,V>
1732		return (es != null) ? es : new AscendingEntrySetView();
1733		}
1734
1735	<	public K firstKey() {
1736	<	return key(loEntry());
1737	<	}
1738	<
1739	<	public K lastKey() {
1740	<	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	<	}
1735	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1736	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1737	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1738	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1739	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1740	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1741		}
1742
1743	<	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1743	>	/**
1744	>	* @serial include
1745	>	*/
1746	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1747		private static final long serialVersionUID = 912986545866120460L;
1748	<	DescendingSubMap(TreeMap<K,V> m,
1749	<	boolean fromStart, K lo, int loExcluded,
1750	<	boolean toEnd, K hi, int hiExcluded) {
1751	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1748	>	DescendingSubMap(TreeMap<K,V> m,
1749	>	boolean fromStart, K lo, boolean loInclusive,
1750	>	boolean toEnd,     K hi, boolean hiInclusive) {
1751	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1752		}
1753
1754		private final Comparator<? super K> reverseComparator =
#	Line 1756 | Line 1758 | public class TreeMap<K,V>
1758		return reverseComparator;
1759		}
1760
1761	<	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1762	<	K toKey, boolean toInclusive) {
1761	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1762	>	K toKey,   boolean toInclusive) {
1763		if (!inRange(fromKey, fromInclusive))
1764		throw new IllegalArgumentException("fromKey out of range");
1765		if (!inRange(toKey, toInclusive))
1766		throw new IllegalArgumentException("toKey out of range");
1767	<	return new DescendingSubMap(m,
1768	<	false, toKey,   excluded(toInclusive),
1769	<	false, fromKey, excluded(fromInclusive));
1767	>	return new DescendingSubMap(m,
1768	>	false, toKey,   toInclusive,
1769	>	false, fromKey, fromInclusive);
1770		}
1771
1772		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1773		if (!inRange(toKey, inclusive))
1774		throw new IllegalArgumentException("toKey out of range");
1775	<	return new DescendingSubMap(m,
1776	<	false, toKey, excluded(inclusive),
1777	<	toEnd, hi, hiExcluded);
1775	>	return new DescendingSubMap(m,
1776	>	false, toKey, inclusive,
1777	>	toEnd, hi,    hiInclusive);
1778		}
1779
1780		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1781		if (!inRange(fromKey, inclusive))
1782		throw new IllegalArgumentException("fromKey out of range");
1783	<	return new DescendingSubMap(m,
1784	<	fromStart, lo,      loExcluded,
1785	<	false, fromKey, excluded(inclusive));
1783	>	return new DescendingSubMap(m,
1784	>	fromStart, lo, loInclusive,
1785	>	false, fromKey, inclusive);
1786	>	}
1787	>
1788	>	public NavigableMap<K,V> descendingMap() {
1789	>	NavigableMap<K,V> mv = descendingMapView;
1790	>	return (mv != null) ? mv :
1791	>	(descendingMapView =
1792	>	new AscendingSubMap(m,
1793	>	fromStart, lo, loInclusive,
1794	>	toEnd,     hi, hiInclusive));
1795		}
1796
1797		Iterator<K> keyIterator() {
1798	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1798	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1799		}
1800
1801		Iterator<K> descendingKeyIterator() {
1802	<	return new SubMapKeyIterator(loEntry(), hiFence());
1802	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1803		}
1804
1805	<	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1805	>	final class DescendingEntrySetView extends EntrySetView {
1806		public Iterator<Map.Entry<K,V>> iterator() {
1807	<	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1807	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1808		}
1809		}
1810
#	Line 1802 | Line 1813 | public class TreeMap<K,V>
1813		return (es != null) ? es : new DescendingEntrySetView();
1814		}
1815
1816	<	public K firstKey() {
1817	<	return key(hiEntry());
1818	<	}
1819	<
1820	<	public K lastKey() {
1821	<	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	<	}
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));
1816	>	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1817	>	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1818	>	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1819	>	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1820	>	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1821	>	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1822		}
1823
1824		/**
#	Line 1874 | Line 1827 | public class TreeMap<K,V>
1827		* support NavigableMap.  It translates an old-version SubMap into
1828		* a new-version AscendingSubMap. This class is never otherwise
1829		* used.
1830	+	*
1831	+	* @serial include
1832		*/
1833		private class SubMap extends AbstractMap<K,V>
1834		implements SortedMap<K,V>, java.io.Serializable {
#	Line 1881 | Line 1836 | public class TreeMap<K,V>
1836		private boolean fromStart = false, toEnd = false;
1837		private K fromKey, toKey;
1838		private Object readResolve() {
1839	<	return new AscendingSubMap(TreeMap.this,
1840	<	fromStart, fromKey, 0,
1841	<	toEnd, toKey, 1);
1839	>	return new AscendingSubMap(TreeMap.this,
1840	>	fromStart, fromKey, true,
1841	>	toEnd, toKey, false);
1842		}
1843		public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1844		public K lastKey() { throw new InternalError(); }
#	Line 1895 | Line 1850 | public class TreeMap<K,V>
1850		}
1851
1852
1853	+	// Red-black mechanics
1854	+
1855		private static final boolean RED   = false;
1856		private static final boolean BLACK = true;
1857
#	Line 1955 | Line 1912 | public class TreeMap<K,V>
1912		public boolean equals(Object o) {
1913		if (!(o instanceof Map.Entry))
1914		return false;
1915	<	Map.Entry e = (Map.Entry)o;
1915	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1916
1917		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1918		}
#	Line 1998 | Line 1955 | public class TreeMap<K,V>
1955		/**
1956		* Returns the successor of the specified Entry, or null if no such.
1957		*/
1958	<	final Entry<K,V> successor(Entry<K,V> t) {
1958	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1959		if (t == null)
1960		return null;
1961		else if (t.right != null) {
#	Line 2020 | Line 1977 | public class TreeMap<K,V>
1977		/**
1978		* Returns the predecessor of the specified Entry, or null if no such.
1979		*/
1980	<	final Entry<K,V> predecessor(Entry<K,V> t) {
1980	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1981		if (t == null)
1982		return null;
1983		else if (t.left != null) {
#	Line 2070 | Line 2027 | public class TreeMap<K,V>
2027		return (p == null) ? null: p.right;
2028		}
2029
2030	<	/** From CLR **/
2030	>	/** From CLR */
2031		private void rotateLeft(Entry<K,V> p) {
2032	<	Entry<K,V> r = p.right;
2033	<	p.right = r.left;
2034	<	if (r.left != null)
2035	<	r.left.parent = p;
2036	<	r.parent = p.parent;
2037	<	if (p.parent == null)
2038	<	root = r;
2039	<	else if (p.parent.left == p)
2040	<	p.parent.left = r;
2041	<	else
2042	<	p.parent.right = r;
2043	<	r.left = p;
2044	<	p.parent = r;
2032	>	if (p != null) {
2033	>	Entry<K,V> r = p.right;
2034	>	p.right = r.left;
2035	>	if (r.left != null)
2036	>	r.left.parent = p;
2037	>	r.parent = p.parent;
2038	>	if (p.parent == null)
2039	>	root = r;
2040	>	else if (p.parent.left == p)
2041	>	p.parent.left = r;
2042	>	else
2043	>	p.parent.right = r;
2044	>	r.left = p;
2045	>	p.parent = r;
2046	>	}
2047		}
2048
2049	<	/** From CLR **/
2049	>	/** From CLR */
2050		private void rotateRight(Entry<K,V> p) {
2051	<	Entry<K,V> l = p.left;
2052	<	p.left = l.right;
2053	<	if (l.right != null) l.right.parent = p;
2054	<	l.parent = p.parent;
2055	<	if (p.parent == null)
2056	<	root = l;
2057	<	else if (p.parent.right == p)
2058	<	p.parent.right = l;
2059	<	else p.parent.left = l;
2060	<	l.right = p;
2061	<	p.parent = l;
2051	>	if (p != null) {
2052	>	Entry<K,V> l = p.left;
2053	>	p.left = l.right;
2054	>	if (l.right != null) l.right.parent = p;
2055	>	l.parent = p.parent;
2056	>	if (p.parent == null)
2057	>	root = l;
2058	>	else if (p.parent.right == p)
2059	>	p.parent.right = l;
2060	>	else p.parent.left = l;
2061	>	l.right = p;
2062	>	p.parent = l;
2063	>	}
2064		}
2065
2066	<
2106	<	/** From CLR **/
2066	>	/** From CLR */
2067		private void fixAfterInsertion(Entry<K,V> x) {
2068		x.color = RED;
2069
#	Line 2122 | Line 2082 | public class TreeMap<K,V>
2082		}
2083		setColor(parentOf(x), BLACK);
2084		setColor(parentOf(parentOf(x)), RED);
2085	<	if (parentOf(parentOf(x)) != null)
2126	<	rotateRight(parentOf(parentOf(x)));
2085	>	rotateRight(parentOf(parentOf(x)));
2086		}
2087		} else {
2088		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2137 | Line 2096 | public class TreeMap<K,V>
2096		x = parentOf(x);
2097		rotateRight(x);
2098		}
2099	<	setColor(parentOf(x),  BLACK);
2099	>	setColor(parentOf(x), BLACK);
2100		setColor(parentOf(parentOf(x)), RED);
2101	<	if (parentOf(parentOf(x)) != null)
2143	<	rotateLeft(parentOf(parentOf(x)));
2101	>	rotateLeft(parentOf(parentOf(x)));
2102		}
2103		}
2104		}
#	Line 2150 | Line 2108 | public class TreeMap<K,V>
2108		/**
2109		* Delete node p, and then rebalance the tree.
2110		*/
2153	–
2111		private void deleteEntry(Entry<K,V> p) {
2112	<	decrementSize();
2112	>	modCount++;
2113	>	size--;
2114
2115		// If strictly internal, copy successor's element to p and then make p
2116		// point to successor.
#	Line 2198 | Line 2156 | public class TreeMap<K,V>
2156		}
2157		}
2158
2159	<	/** From CLR **/
2159	>	/** From CLR */
2160		private void fixAfterDeletion(Entry<K,V> x) {
2161		while (x != root && colorOf(x) == BLACK) {
2162		if (x == leftOf(parentOf(x))) {
#	Line 2213 | Line 2171 | public class TreeMap<K,V>
2171
2172		if (colorOf(leftOf(sib))  == BLACK &&
2173		colorOf(rightOf(sib)) == BLACK) {
2174	<	setColor(sib,  RED);
2174	>	setColor(sib, RED);
2175		x = parentOf(x);
2176		} else {
2177		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2240 | Line 2198 | public class TreeMap<K,V>
2198
2199		if (colorOf(rightOf(sib)) == BLACK &&
2200		colorOf(leftOf(sib)) == BLACK) {
2201	<	setColor(sib,  RED);
2201	>	setColor(sib, RED);
2202		x = parentOf(x);
2203		} else {
2204		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 2306 | Line 2264 | public class TreeMap<K,V>
2264		buildFromSorted(size, null, s, null);
2265		}
2266
2267	<	/** Intended to be called only from TreeSet.readObject **/
2267	>	/** Intended to be called only from TreeSet.readObject */
2268		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2269		throws java.io.IOException, ClassNotFoundException {
2270		buildFromSorted(size, null, s, defaultVal);
2271		}
2272
2273	<	/** Intended to be called only from TreeSet.addAll **/
2273	>	/** Intended to be called only from TreeSet.addAll */
2274		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2275		try {
2276		buildFromSorted(set.size(), set.iterator(), null, defaultVal);

Diff Legend

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