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

#	Line 95 | Line 95 | public class TreeMap<K,V>
95		*
96		* @serial
97		*/
98	<	private Comparator<? super K> comparator = null;
98	>	private final Comparator<? super K> comparator;
99
100		private transient Entry<K,V> root = null;
101
#	Line 125 | Line 125 | public class TreeMap<K,V>
125		* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128	+	comparator = null;
129		}
130
131		/**
#	Line 160 | Line 161 | public class TreeMap<K,V>
161		* @throws NullPointerException if the specified map is null
162		*/
163		public TreeMap(Map<? extends K, ? extends V> m) {
164	+	comparator = null;
165		putAll(m);
166		}
167
#	Line 359 | Line 361 | public class TreeMap<K,V>
361		* Version of getEntry using comparator. Split off from getEntry
362		* for performance. (This is not worth doing for most methods,
363		* that are less dependent on comparator performance, but is
364	<	* worthwhile here.)
364	>	* worthwhile for get and put.)
365		*/
366		final Entry<K,V> getEntryUsingComparator(Object key) {
367		K k = (K) key;
#	Line 385 | Line 387 | public class TreeMap<K,V>
387		*/
388		final Entry<K,V> getCeilingEntry(K key) {
389		Entry<K,V> p = root;
390	<	if (p==null)
389	<	return null;
390	<
391	<	while (true) {
390	>	while (p != null) {
391		int cmp = compare(key, p.key);
392		if (cmp < 0) {
393		if (p.left != null)
#	Line 410 | Line 409 | public class TreeMap<K,V>
409		} else
410		return p;
411		}
412	+	return null;
413		}
414
415		/**
#	Line 419 | Line 419 | public class TreeMap<K,V>
419		*/
420		final Entry<K,V> getFloorEntry(K key) {
421		Entry<K,V> p = root;
422	<	if (p==null)
423	<	return null;
424	<
425	<	while (true) {
422	>	while (p != null) {
423		int cmp = compare(key, p.key);
424		if (cmp > 0) {
425		if (p.right != null)
#	Line 445 | Line 442 | public class TreeMap<K,V>
442		return p;
443
444		}
445	+	return null;
446		}
447
448		/**
#	Line 455 | Line 453 | public class TreeMap<K,V>
453		*/
454		final Entry<K,V> getHigherEntry(K key) {
455		Entry<K,V> p = root;
456	<	if (p==null)
459	<	return null;
460	<
461	<	while (true) {
456	>	while (p != null) {
457		int cmp = compare(key, p.key);
458		if (cmp < 0) {
459		if (p.left != null)
#	Line 479 | Line 474 | public class TreeMap<K,V>
474		}
475		}
476		}
477	+	return null;
478		}
479
480		/**
#	Line 488 | Line 484 | public class TreeMap<K,V>
484		*/
485		final Entry<K,V> getLowerEntry(K key) {
486		Entry<K,V> p = root;
487	<	if (p==null)
492	<	return null;
493	<
494	<	while (true) {
487	>	while (p != null) {
488		int cmp = compare(key, p.key);
489		if (cmp > 0) {
490		if (p.right != null)
#	Line 512 | Line 505 | public class TreeMap<K,V>
505		}
506		}
507		}
508	+	return null;
509		}
510
511		/**
#	Line 543 | Line 537 | public class TreeMap<K,V>
537		*         does not permit null keys
538		*/
539		public V put(K key, V value) {
540	<	Entry<K,V> t = root;
540	>	// Offload comparator-based version for sake of performance
541	>	if (comparator != null)
542	>	return putUsingComparator(key, value);
543	>	if (key == null)
544	>	throw new NullPointerException();
545	>	Comparable<? super K> k = (Comparable<? super K>) key;
546
547	<	if (t == null) {
548	<	// TBD
549	<	//             if (key == null) {
550	<	//                 if (comparator == null)
551	<	//                     throw new NullPointerException();
552	<	//                 comparator.compare(key, key);
553	<	//             }
554	<	incrementSize();
555	<	root = new Entry<K,V>(key, value, null);
556	<	return null;
547	>	Entry<K,V> t = root;
548	>	while (t != null) {
549	>	int cmp = k.compareTo(t.key);
550	>	if (cmp == 0) {
551	>	return t.setValue(value);
552	>	} else if (cmp < 0) {
553	>	if (t.left != null) {
554	>	t = t.left;
555	>	} else {
556	>	incrementSize();
557	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
558	>	return null;
559	>	}
560	>	} else { // cmp > 0
561	>	if (t.right != null) {
562	>	t = t.right;
563	>	} else {
564	>	incrementSize();
565	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	>	return null;
567	>	}
568	>	}
569		}
570	+	incrementSize();
571	+	root = new Entry<K,V>(key, value, null);
572	+	return null;
573	+	}
574
575	<	while (true) {
576	<	int cmp = compare(key, t.key);
575	>	/**
576	>	* Version of put using comparator. Split off from put for
577	>	* performance.
578	>	*/
579	>	final V putUsingComparator(K key, V value) {
580	>	Comparator<? super K> cpr = comparator;
581	>	Entry<K,V> t = root;
582	>	while (t != null) {
583	>	int cmp = cpr.compare(key, t.key);
584		if (cmp == 0) {
585		return t.setValue(value);
586		} else if (cmp < 0) {
#	Line 566 | Line 588 | public class TreeMap<K,V>
588		t = t.left;
589		} else {
590		incrementSize();
591	<	t.left = new Entry<K,V>(key, value, t);
570	<	fixAfterInsertion(t.left);
591	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592		return null;
593		}
594		} else { // cmp > 0
#	Line 575 | Line 596 | public class TreeMap<K,V>
596		t = t.right;
597		} else {
598		incrementSize();
599	<	t.right = new Entry<K,V>(key, value, t);
579	<	fixAfterInsertion(t.right);
599	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600		return null;
601		}
602		}
603		}
604	+	cpr.compare(key, key); // type check
605	+	incrementSize();
606	+	root = new Entry<K,V>(key, value, null);
607	+	return null;
608		}
609
610		/**
#	Line 877 | Line 901 | public class TreeMap<K,V>
901		public NavigableMap<K, V> descendingMap() {
902		NavigableMap<K, V> km = descendingMap;
903		return (km != null) ? km :
904	<	(descendingMap = new DescendingSubMap(this,
904	>	(descendingMap = new DescendingSubMap(this,
905		true, null, 0,
906		true, null, 0));
907		}
#	Line 892 | Line 916 | public class TreeMap<K,V>
916		*/
917		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
918		K toKey,   boolean toInclusive) {
919	<	return new AscendingSubMap(this,
919	>	return new AscendingSubMap(this,
920		false, fromKey, excluded(fromInclusive),
921		false, toKey,   excluded(toInclusive));
922		}
#	Line 906 | Line 930 | public class TreeMap<K,V>
930		* @since 1.6
931		*/
932		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
933	<	return new AscendingSubMap(this,
934	<	true, null, 0,
933	>	return new AscendingSubMap(this,
934	>	true,  null,  0,
935		false, toKey, excluded(inclusive));
936		}
937
#	Line 920 | Line 944 | public class TreeMap<K,V>
944		* @since 1.6
945		*/
946		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
947	<	return new AscendingSubMap(this,
948	<	false, fromKey, excluded(inclusive),
949	<	true, null, 0);
947	>	return new AscendingSubMap(this,
948	>	false, fromKey, excluded(inclusive),
949	>	true,  null,    0);
950		}
951
952		/**
#	Line 1093 | Line 1117 | public class TreeMap<K,V>
1117		m.remove(o);
1118		return size() != oldSize;
1119		}
1120	<	public NavigableSet<E> subSet(E fromElement,
1121	<	boolean fromInclusive,
1122	<	E toElement,
1123	<	boolean toInclusive) {
1100	<	return new TreeSet<E>
1101	<	(m.subMap(fromElement, fromInclusive,
1102	<	toElement,   toInclusive));
1120	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1121	>	E toElement, boolean toInclusive) {
1122	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1123	>	toElement,   toInclusive));
1124		}
1125		public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1126		return new TreeSet<E>(m.headMap(toElement, inclusive));
#	Line 1125 | Line 1146 | public class TreeMap<K,V>
1146		* Base class for TreeMap Iterators
1147		*/
1148		abstract class PrivateEntryIterator<T> implements Iterator<T> {
1128	–	int expectedModCount = TreeMap.this.modCount;
1129	–	Entry<K,V> lastReturned = null;
1149		Entry<K,V> next;
1150	+	Entry<K,V> lastReturned;
1151	+	int expectedModCount;
1152
1153		PrivateEntryIterator(Entry<K,V> first) {
1154	+	expectedModCount = modCount;
1155	+	lastReturned = null;
1156		next = first;
1157		}
1158
#	Line 1138 | Line 1161 | public class TreeMap<K,V>
1161		}
1162
1163		final Entry<K,V> nextEntry() {
1164	<	if (next == null)
1164	>	Entry<K,V> e = lastReturned = next;
1165	>	if (e == null)
1166		throw new NoSuchElementException();
1167		if (modCount != expectedModCount)
1168		throw new ConcurrentModificationException();
1169	<	lastReturned = next;
1170	<	next = successor(next);
1147	<	return lastReturned;
1169	>	next = successor(e);
1170	>	return e;
1171		}
1172
1173		final Entry<K,V> prevEntry() {
1174	<	if (next == null)
1174	>	Entry<K,V> e = lastReturned= next;
1175	>	if (e == null)
1176		throw new NoSuchElementException();
1177		if (modCount != expectedModCount)
1178		throw new ConcurrentModificationException();
1179	<	lastReturned = next;
1180	<	next = predecessor(next);
1157	<	return lastReturned;
1179	>	next = predecessor(e);
1180	>	return e;
1181		}
1182
1183		public void remove() {
#	Line 1214 | Line 1237 | public class TreeMap<K,V>
1237		/*
1238		* The backing map.
1239		*/
1240	<	final TreeMap<K,V> m;
1218	<
1219	<	/** True if low point is from start of backing map */
1220	<	boolean fromStart;
1221	<
1222	<	/**
1223	<	* The low endpoint of this submap in absolute terms, or null
1224	<	* if fromStart.
1225	<	*/
1226	<	K lo;
1227	<
1228	<	/**
1229	<	* Zero if the low endpoint is excluded from this submap, one if
1230	<	* it's included.  This field is unused if fromStart.
1231	<	*/
1232	<	int loExcluded;
1233	<
1234	<	/** True if high point is to End of backing map */
1235	<	boolean toEnd;
1240	>	final TreeMap<K,V> m;
1241
1242	<	/**
1243	<	* The high endpoint of this submap in absolute terms, or null
1244	<	* if toEnd.
1242	>	/*
1243	>	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1244	>	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1245	>	* the low (absolute) bound is the start of the backing map, and the
1246	>	* other values are ignored. Otherwise, if loExcluded is
1247	>	* zero, lo is the inclusive bound, else loExcluded is one,
1248	>	* and lo is the exclusive bound. Similarly for the upper bound.
1249		*/
1241	–	K hi;
1250
1251	<	/**
1252	<	* Zero if the high endpoint is excluded from this submap, one if
1253	<	* it's included.  This field is unused if toEnd.
1254	<	*/
1255	<	int hiExcluded;
1251	>	final K lo, hi;
1252	>	final boolean fromStart, toEnd;
1253	>	final int loExcluded, hiExcluded;
1254	>
1255	>	NavigableSubMap(TreeMap<K,V> m,
1256	>	boolean fromStart, K lo, int loExcluded,
1257	>	boolean toEnd,     K hi, int hiExcluded) {
1258	>	if (!fromStart && !toEnd) {
1259	>	if (m.compare(lo, hi) > 0)
1260	>	throw new IllegalArgumentException("fromKey > toKey");
1261	>	}
1262	>	else if (!fromStart) // type check
1263	>	m.compare(lo, lo);
1264	>	else if (!toEnd)
1265	>	m.compare(hi, hi);
1266
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");
1267		this.m = m;
1268		this.fromStart = fromStart;
1269		this.lo = lo;
#	Line 1284 | Line 1297 | public class TreeMap<K,V>
1297		return !toEnd && m.compare(hi, key) < hiExcluded;
1298		}
1299
1287	–
1300		/** Returns the lowest entry in this submap (absolute ordering) */
1301		final TreeMap.Entry<K,V> loEntry() {
1302	<	TreeMap.Entry<K,V> result =
1302	>	TreeMap.Entry<K,V> result =
1303		(fromStart ?  m.getFirstEntry() :
1304		(loExcluded == 0 ? m.getCeilingEntry(lo) :
1305		m.getHigherEntry(lo)));
#	Line 1434 | Line 1446 | public class TreeMap<K,V>
1446		return m.size();
1447		if (size == -1 || sizeModCount != m.modCount) {
1448		sizeModCount = m.modCount;
1449	<	size = 0;
1449	>	size = 0;
1450		Iterator i = iterator();
1451		while (i.hasNext()) {
1452		size++;
#	Line 1499 | Line 1511 | public class TreeMap<K,V>
1511		return tailMap(fromKey, true);
1512		}
1513
1502	–
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
#	Line 1557 | Line 1568 | public class TreeMap<K,V>
1568		* Iterators for SubMaps
1569		*/
1570		abstract class SubMapIterator<T> implements Iterator<T> {
1571	<	int expectedModCount = m.modCount;
1561	<	TreeMap.Entry<K,V> lastReturned = null;
1571	>	TreeMap.Entry<K,V> lastReturned;
1572		TreeMap.Entry<K,V> next;
1573	<	final K firstExcludedKey;
1573	>	final K fenceKey;
1574	>	int expectedModCount;
1575
1576	<	SubMapIterator(TreeMap.Entry<K,V> first,
1577	<	TreeMap.Entry<K,V> firstExcluded) {
1576	>	SubMapIterator(TreeMap.Entry<K,V> first,
1577	>	TreeMap.Entry<K,V> fence) {
1578	>	expectedModCount = m.modCount;
1579	>	lastReturned = null;
1580		next = first;
1581	<	firstExcludedKey = (firstExcluded == null ? null
1569	<	: firstExcluded.key);
1581	>	fenceKey = fence == null ? null : fence.key;
1582		}
1583
1584		public final boolean hasNext() {
1585	<	return next != null && next.key != firstExcludedKey;
1585	>	return next != null && next.key != fenceKey;
1586		}
1587
1588		final TreeMap.Entry<K,V> nextEntry() {
1589	<	if (next == null || next.key == firstExcludedKey)
1589	>	TreeMap.Entry<K,V> e = lastReturned = next;
1590	>	if (e == null || e.key == fenceKey)
1591		throw new NoSuchElementException();
1592		if (m.modCount != expectedModCount)
1593		throw new ConcurrentModificationException();
1594	<	lastReturned = next;
1595	<	next = m.successor(next);
1583	<	return lastReturned;
1594	>	next = successor(e);
1595	>	return e;
1596		}
1597
1598		final TreeMap.Entry<K,V> prevEntry() {
1599	<	if (next == null || next.key == firstExcludedKey)
1599	>	TreeMap.Entry<K,V> e = lastReturned = next;
1600	>	if (e == null || e.key == fenceKey)
1601		throw new NoSuchElementException();
1602		if (m.modCount != expectedModCount)
1603		throw new ConcurrentModificationException();
1604	<	lastReturned = next;
1605	<	next = m.predecessor(next);
1593	<	return lastReturned;
1604	>	next = predecessor(e);
1605	>	return e;
1606		}
1607
1608		public void remove() {
#	Line 1607 | Line 1619 | public class TreeMap<K,V>
1619		}
1620
1621		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1622	<	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1623	<	TreeMap.Entry<K,V> firstExcluded) {
1624	<	super(first, firstExcluded);
1622	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1623	>	TreeMap.Entry<K,V> fence) {
1624	>	super(first, fence);
1625		}
1626		public Map.Entry<K,V> next() {
1627		return nextEntry();
#	Line 1617 | Line 1629 | public class TreeMap<K,V>
1629		}
1630
1631		final class SubMapKeyIterator extends SubMapIterator<K> {
1632	<	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1633	<	TreeMap.Entry<K,V> firstExcluded) {
1634	<	super(first, firstExcluded);
1632	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1633	>	TreeMap.Entry<K,V> fence) {
1634	>	super(first, fence);
1635		}
1636		public K next() {
1637		return nextEntry().key;
#	Line 1627 | Line 1639 | public class TreeMap<K,V>
1639		}
1640
1641		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1642	<	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1642	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1643		TreeMap.Entry<K,V> lastExcluded) {
1644		super(last, lastExcluded);
1645		}
#	Line 1638 | Line 1650 | public class TreeMap<K,V>
1650		}
1651
1652		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1653	<	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1653	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1654		TreeMap.Entry<K,V> lastExcluded) {
1655		super(last, lastExcluded);
1656		}
#	Line 1651 | Line 1663 | public class TreeMap<K,V>
1663		static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1664		private static final long serialVersionUID = 912986545866124060L;
1665
1666	<	AscendingSubMap(TreeMap<K,V> m,
1667	<	boolean fromStart, K lo, int loExcluded,
1666	>	AscendingSubMap(TreeMap<K,V> m,
1667	>	boolean fromStart, K lo, int loExcluded,
1668		boolean toEnd, K hi, int hiExcluded) {
1669		super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1670		}
#	Line 1661 | Line 1673 | public class TreeMap<K,V>
1673		return m.comparator();
1674		}
1675
1676	<	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1676	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1677		K toKey, boolean toInclusive) {
1678		if (!inRange(fromKey, fromInclusive))
1679		throw new IllegalArgumentException("fromKey out of range");
1680		if (!inRange(toKey, toInclusive))
1681		throw new IllegalArgumentException("toKey out of range");
1682	<	return new AscendingSubMap(m,
1682	>	return new AscendingSubMap(m,
1683		false, fromKey, excluded(fromInclusive),
1684		false, toKey,   excluded(toInclusive));
1685		}
#	Line 1675 | Line 1687 | public class TreeMap<K,V>
1687		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1688		if (!inClosedRange(toKey))
1689		throw new IllegalArgumentException("toKey out of range");
1690	<	return new AscendingSubMap(m,
1690	>	return new AscendingSubMap(m,
1691		fromStart, lo,    loExcluded,
1692	<	false, toKey, excluded(inclusive));
1692	>	false,     toKey, excluded(inclusive));
1693		}
1694
1695		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1696		if (!inRange(fromKey, inclusive))
1697		throw new IllegalArgumentException("fromKey out of range");
1698	<	return new AscendingSubMap(m,
1698	>	return new AscendingSubMap(m,
1699		false, fromKey, excluded(inclusive),
1700		toEnd, hi,      hiExcluded);
1701		}
#	Line 1735 | Line 1747 | public class TreeMap<K,V>
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));
1750	>	new DescendingSubMap(m,
1751	>	fromStart, lo, loExcluded,
1752	>	toEnd,     hi, hiExcluded));
1753		}
1754		}
1755
1756		static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1757		private static final long serialVersionUID = 912986545866120460L;
1758	<	DescendingSubMap(TreeMap<K,V> m,
1759	<	boolean fromStart, K lo, int loExcluded,
1758	>	DescendingSubMap(TreeMap<K,V> m,
1759	>	boolean fromStart, K lo, int loExcluded,
1760		boolean toEnd, K hi, int hiExcluded) {
1761		super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1762		}
#	Line 1756 | Line 1768 | public class TreeMap<K,V>
1768		return reverseComparator;
1769		}
1770
1771	<	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1771	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1772		K toKey, boolean toInclusive) {
1773		if (!inRange(fromKey, fromInclusive))
1774		throw new IllegalArgumentException("fromKey out of range");
1775		if (!inRange(toKey, toInclusive))
1776		throw new IllegalArgumentException("toKey out of range");
1777	<	return new DescendingSubMap(m,
1777	>	return new DescendingSubMap(m,
1778		false, toKey,   excluded(toInclusive),
1779		false, fromKey, excluded(fromInclusive));
1780		}
#	Line 1770 | Line 1782 | public class TreeMap<K,V>
1782		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1783		if (!inRange(toKey, inclusive))
1784		throw new IllegalArgumentException("toKey out of range");
1785	<	return new DescendingSubMap(m,
1786	<	false, toKey, excluded(inclusive),
1787	<	toEnd, hi, hiExcluded);
1785	>	return new DescendingSubMap(m,
1786	>	false, toKey, excluded(inclusive),
1787	>	toEnd, hi,    hiExcluded);
1788		}
1789
1790		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1791		if (!inRange(fromKey, inclusive))
1792		throw new IllegalArgumentException("fromKey out of range");
1793	<	return new DescendingSubMap(m,
1794	<	fromStart, lo,      loExcluded,
1793	>	return new DescendingSubMap(m,
1794	>	fromStart, lo, loExcluded,
1795		false, fromKey, excluded(inclusive));
1796		}
1797
#	Line 1830 | Line 1842 | public class TreeMap<K,V>
1842		NavigableMap<K,V> mv = descendingMapView;
1843		return (mv != null) ? mv :
1844		(descendingMapView =
1845	<	new AscendingSubMap(m,
1846	<	fromStart, lo, loExcluded,
1845	>	new AscendingSubMap(m,
1846	>	fromStart, lo, loExcluded,
1847		toEnd, hi, hiExcluded));
1848		}
1849
#	Line 1881 | Line 1893 | public class TreeMap<K,V>
1893		private boolean fromStart = false, toEnd = false;
1894		private K fromKey, toKey;
1895		private Object readResolve() {
1896	<	return new AscendingSubMap(TreeMap.this,
1897	<	fromStart, fromKey, 0,
1896	>	return new AscendingSubMap(TreeMap.this,
1897	>	fromStart, fromKey, 0,
1898		toEnd, toKey, 1);
1899		}
1900		public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
#	Line 1998 | Line 2010 | public class TreeMap<K,V>
2010		/**
2011		* Returns the successor of the specified Entry, or null if no such.
2012		*/
2013	<	final Entry<K,V> successor(Entry<K,V> t) {
2013	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2014		if (t == null)
2015		return null;
2016		else if (t.right != null) {
#	Line 2020 | Line 2032 | public class TreeMap<K,V>
2032		/**
2033		* Returns the predecessor of the specified Entry, or null if no such.
2034		*/
2035	<	final Entry<K,V> predecessor(Entry<K,V> t) {
2035	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2036		if (t == null)
2037		return null;
2038		else if (t.left != null) {
#	Line 2137 | Line 2149 | public class TreeMap<K,V>
2149		x = parentOf(x);
2150		rotateRight(x);
2151		}
2152	<	setColor(parentOf(x),  BLACK);
2152	>	setColor(parentOf(x), BLACK);
2153		setColor(parentOf(parentOf(x)), RED);
2154		if (parentOf(parentOf(x)) != null)
2155		rotateLeft(parentOf(parentOf(x)));
#	Line 2213 | Line 2225 | public class TreeMap<K,V>
2225
2226		if (colorOf(leftOf(sib))  == BLACK &&
2227		colorOf(rightOf(sib)) == BLACK) {
2228	<	setColor(sib,  RED);
2228	>	setColor(sib, RED);
2229		x = parentOf(x);
2230		} else {
2231		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2240 | Line 2252 | public class TreeMap<K,V>
2252
2253		if (colorOf(rightOf(sib)) == BLACK &&
2254		colorOf(leftOf(sib)) == BLACK) {
2255	<	setColor(sib,  RED);
2255	>	setColor(sib, RED);
2256		x = parentOf(x);
2257		} else {
2258		if (colorOf(leftOf(sib)) == BLACK) {

Diff Legend

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