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.32 by dl, Sat Apr 22 16:38:01 2006 UTC vs.
Revision 1.36 by jsr166, Tue May 9 16:35:40 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 994 | 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))
998	<	if (valEquals(e.getValue(), o))
999	<	return true;
1000	<	return false;
940	>	return TreeMap.this.containsValue(o);
941		}
942
943		public boolean remove(Object o) {
#	Line 1110 | Line 1050 | public class TreeMap<K,V>
1050		return size() != oldSize;
1051		}
1052		public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1053	<	E toElement, boolean toInclusive) {
1053	>	E toElement,   boolean toInclusive) {
1054		return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1055		toElement,   toInclusive));
1056		}
#	Line 1221 | 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	+	/**
1211	+	* @serial include
1212	+	*/
1213		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1214		implements NavigableMap<K,V>, java.io.Serializable {
1215	<	/*
1215	>	/**
1216		* The backing map.
1217		*/
1218		final TreeMap<K,V> m;
1219
1220	<	/*
1220	>	/**
1221		* Endpoints are represented as triples (fromStart, lo,
1222		* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1223		* true, then the low (absolute) bound is the start of the
#	Line 1238 | Line 1225 | public class TreeMap<K,V>
1225		* if loInclusive is true, lo is the inclusive bound, else lo
1226		* is the exclusive bound. Similarly for the upper bound.
1227		*/
1241	–
1228		final K lo, hi;
1229		final boolean fromStart, toEnd;
1230		final boolean loInclusive, hiInclusive;
#	Line 1298 | Line 1284 | public class TreeMap<K,V>
1284		return inclusive ? inRange(key) : inClosedRange(key);
1285		}
1286
1301	–	/**
1302	–	* Return SimpleImmutableEntry for entry, or null if null
1303	–	*/
1304	–	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1305	–	return e == null? null :
1306	–	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1307	–	}
1308	–
1309	–	/**
1310	–	* Return key for entry, or null if null
1311	–	*/
1312	–	static <K,V> K exportKey(TreeMap.Entry<K,V> e) {
1313	–	return e == null? null : e.key;
1314	–	}
1315	–
1287		/*
1288		* Absolute versions of relation operations.
1289		* Subclasses map to these using like-named "sub"
#	Line 1334 | Line 1305 | public class TreeMap<K,V>
1305		m.getLowerEntry(hi)));
1306		return (e == null || tooLow(e.key)) ? null : e;
1307		}
1308	<
1308	>
1309		final TreeMap.Entry<K,V> absCeiling(K key) {
1310		if (tooLow(key))
1311		return absLowest();
#	Line 1365 | Line 1336 | public class TreeMap<K,V>
1336
1337		/** Returns the absolute high fence for ascending traversal */
1338		final TreeMap.Entry<K,V> absHighFence() {
1339	<	return (toEnd ? null : (hiInclusive ?
1339	>	return (toEnd ? null : (hiInclusive ?
1340		m.getHigherEntry(hi) :
1341		m.getCeilingEntry(hi)));
1342		}
#	Line 1378 | Line 1349 | public class TreeMap<K,V>
1349		}
1350
1351		// Abstract methods defined in ascending vs descending classes
1352	<	// These relay to the appropriate  absolute versions
1352	>	// These relay to the appropriate absolute versions
1353
1354		abstract TreeMap.Entry<K,V> subLowest();
1355		abstract TreeMap.Entry<K,V> subHighest();
#	Line 1426 | Line 1397 | public class TreeMap<K,V>
1397		}
1398
1399		public final K ceilingKey(K key) {
1400	<	return exportKey(subCeiling(key));
1400	>	return keyOrNull(subCeiling(key));
1401		}
1402
1403		public final Map.Entry<K,V> higherEntry(K key) {
#	Line 1434 | Line 1405 | public class TreeMap<K,V>
1405		}
1406
1407		public final K higherKey(K key) {
1408	<	return exportKey(subHigher(key));
1408	>	return keyOrNull(subHigher(key));
1409		}
1410
1411		public final Map.Entry<K,V> floorEntry(K key) {
#	Line 1442 | Line 1413 | public class TreeMap<K,V>
1413		}
1414
1415		public final K floorKey(K key) {
1416	<	return exportKey(subFloor(key));
1416	>	return keyOrNull(subFloor(key));
1417		}
1418
1419		public final Map.Entry<K,V> lowerEntry(K key) {
#	Line 1450 | Line 1421 | public class TreeMap<K,V>
1421		}
1422
1423		public final K lowerKey(K key) {
1424	<	return exportKey(subLower(key));
1424	>	return keyOrNull(subLower(key));
1425		}
1426
1427		public final K firstKey() {
#	Line 1665 | Line 1636 | public class TreeMap<K,V>
1636		}
1637		}
1638
1639	+	/**
1640	+	* @serial include
1641	+	*/
1642		static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1643		private static final long serialVersionUID = 912986545866124060L;
1644
1645		AscendingSubMap(TreeMap<K,V> m,
1646		boolean fromStart, K lo, boolean loInclusive,
1647	<	boolean toEnd, K hi, boolean hiInclusive) {
1647	>	boolean toEnd,     K hi, boolean hiInclusive) {
1648		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1649		}
1650
#	Line 1679 | Line 1653 | public class TreeMap<K,V>
1653		}
1654
1655		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1656	<	K toKey, boolean toInclusive) {
1656	>	K toKey,   boolean toInclusive) {
1657		if (!inRange(fromKey, fromInclusive))
1658		throw new IllegalArgumentException("fromKey out of range");
1659		if (!inRange(toKey, toInclusive))
#	Line 1741 | Line 1715 | public class TreeMap<K,V>
1715		TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1716		}
1717
1718	+	/**
1719	+	* @serial include
1720	+	*/
1721		static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1722		private static final long serialVersionUID = 912986545866120460L;
1723		DescendingSubMap(TreeMap<K,V> m,
1724		boolean fromStart, K lo, boolean loInclusive,
1725	<	boolean toEnd, K hi, boolean hiInclusive) {
1725	>	boolean toEnd,     K hi, boolean hiInclusive) {
1726		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1727		}
1728
#	Line 1757 | Line 1734 | public class TreeMap<K,V>
1734		}
1735
1736		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1737	<	K toKey, boolean toInclusive) {
1737	>	K toKey,   boolean toInclusive) {
1738		if (!inRange(fromKey, fromInclusive))
1739		throw new IllegalArgumentException("fromKey out of range");
1740		if (!inRange(toKey, toInclusive))
#	Line 1820 | Line 1797 | public class TreeMap<K,V>
1797		}
1798
1799		/**
1823	–	* Compares two keys using the correct comparison method for this TreeMap.
1824	–	*/
1825	–	final int compare(Object k1, Object k2) {
1826	–	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1827	–	: comparator.compare((K)k1, (K)k2);
1828	–	}
1829	–
1830	–	/**
1831	–	* Test two values for equality.  Differs from o1.equals(o2) only in
1832	–	* that it copes with <tt>null</tt> o1 properly.
1833	–	*/
1834	–	final static boolean valEquals(Object o1, Object o2) {
1835	–	return (o1==null ? o2==null : o1.equals(o2));
1836	–	}
1837	–
1838	–	/**
1800		* This class exists solely for the sake of serialization
1801		* compatibility with previous releases of TreeMap that did not
1802		* support NavigableMap.  It translates an old-version SubMap into
1803		* a new-version AscendingSubMap. This class is never otherwise
1804		* used.
1805	+	*
1806	+	* @serial include
1807		*/
1808		private class SubMap extends AbstractMap<K,V>
1809		implements SortedMap<K,V>, java.io.Serializable {
#	Line 1862 | Line 1825 | public class TreeMap<K,V>
1825		}
1826
1827
1828	+	// Red-black mechanics
1829	+
1830		private static final boolean RED   = false;
1831		private static final boolean BLACK = true;
1832
#	Line 1922 | Line 1887 | public class TreeMap<K,V>
1887		public boolean equals(Object o) {
1888		if (!(o instanceof Map.Entry))
1889		return false;
1890	<	Map.Entry e = (Map.Entry)o;
1890	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1891
1892		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1893		}
#	Line 2037 | Line 2002 | public class TreeMap<K,V>
2002		return (p == null) ? null: p.right;
2003		}
2004
2005	<	/** From CLR **/
2005	>	/** From CLR */
2006		private void rotateLeft(Entry<K,V> p) {
2007	<	Entry<K,V> r = p.right;
2008	<	p.right = r.left;
2009	<	if (r.left != null)
2010	<	r.left.parent = p;
2011	<	r.parent = p.parent;
2012	<	if (p.parent == null)
2013	<	root = r;
2014	<	else if (p.parent.left == p)
2015	<	p.parent.left = r;
2016	<	else
2017	<	p.parent.right = r;
2018	<	r.left = p;
2019	<	p.parent = r;
2007	>	if (p != null) {
2008	>	Entry<K,V> r = p.right;
2009	>	p.right = r.left;
2010	>	if (r.left != null)
2011	>	r.left.parent = p;
2012	>	r.parent = p.parent;
2013	>	if (p.parent == null)
2014	>	root = r;
2015	>	else if (p.parent.left == p)
2016	>	p.parent.left = r;
2017	>	else
2018	>	p.parent.right = r;
2019	>	r.left = p;
2020	>	p.parent = r;
2021	>	}
2022		}
2023
2024	<	/** From CLR **/
2024	>	/** From CLR */
2025		private void rotateRight(Entry<K,V> p) {
2026	<	Entry<K,V> l = p.left;
2027	<	p.left = l.right;
2028	<	if (l.right != null) l.right.parent = p;
2029	<	l.parent = p.parent;
2030	<	if (p.parent == null)
2031	<	root = l;
2032	<	else if (p.parent.right == p)
2033	<	p.parent.right = l;
2034	<	else p.parent.left = l;
2035	<	l.right = p;
2036	<	p.parent = l;
2026	>	if (p != null) {
2027	>	Entry<K,V> l = p.left;
2028	>	p.left = l.right;
2029	>	if (l.right != null) l.right.parent = p;
2030	>	l.parent = p.parent;
2031	>	if (p.parent == null)
2032	>	root = l;
2033	>	else if (p.parent.right == p)
2034	>	p.parent.right = l;
2035	>	else p.parent.left = l;
2036	>	l.right = p;
2037	>	p.parent = l;
2038	>	}
2039		}
2040
2041	<
2073	<	/** From CLR **/
2041	>	/** From CLR */
2042		private void fixAfterInsertion(Entry<K,V> x) {
2043		x.color = RED;
2044
#	Line 2089 | Line 2057 | public class TreeMap<K,V>
2057		}
2058		setColor(parentOf(x), BLACK);
2059		setColor(parentOf(parentOf(x)), RED);
2060	<	if (parentOf(parentOf(x)) != null)
2093	<	rotateRight(parentOf(parentOf(x)));
2060	>	rotateRight(parentOf(parentOf(x)));
2061		}
2062		} else {
2063		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2106 | Line 2073 | public class TreeMap<K,V>
2073		}
2074		setColor(parentOf(x), BLACK);
2075		setColor(parentOf(parentOf(x)), RED);
2076	<	if (parentOf(parentOf(x)) != null)
2110	<	rotateLeft(parentOf(parentOf(x)));
2076	>	rotateLeft(parentOf(parentOf(x)));
2077		}
2078		}
2079		}
#	Line 2117 | Line 2083 | public class TreeMap<K,V>
2083		/**
2084		* Delete node p, and then rebalance the tree.
2085		*/
2120	–
2086		private void deleteEntry(Entry<K,V> p) {
2087	<	decrementSize();
2087	>	modCount++;
2088	>	size--;
2089
2090		// If strictly internal, copy successor's element to p and then make p
2091		// point to successor.
#	Line 2165 | Line 2131 | public class TreeMap<K,V>
2131		}
2132		}
2133
2134	<	/** From CLR **/
2134	>	/** From CLR */
2135		private void fixAfterDeletion(Entry<K,V> x) {
2136		while (x != root && colorOf(x) == BLACK) {
2137		if (x == leftOf(parentOf(x))) {
#	Line 2273 | Line 2239 | public class TreeMap<K,V>
2239		buildFromSorted(size, null, s, null);
2240		}
2241
2242	<	/** Intended to be called only from TreeSet.readObject **/
2242	>	/** Intended to be called only from TreeSet.readObject */
2243		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2244		throws java.io.IOException, ClassNotFoundException {
2245		buildFromSorted(size, null, s, defaultVal);
2246		}
2247
2248	<	/** Intended to be called only from TreeSet.addAll **/
2248	>	/** Intended to be called only from TreeSet.addAll */
2249		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2250		try {
2251		buildFromSorted(set.size(), set.iterator(), null, defaultVal);

Diff Legend

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