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.33 by dl, Sat Apr 22 23:02:25 2006 UTC vs.
Revision 1.34 by dl, Sun Apr 23 20:59:49 2006 UTC

#	Line 223 | 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	<	}
230	<
231	<	private boolean valueSearchNull(Entry n) {
232	<	if (n.value == null)
233	<	return true;
234	<
235	<	// Check left and right subtrees for value
236	<	return (n.left  != null && valueSearchNull(n.left)) ||
237	<	(n.right != null && valueSearchNull(n.right));
238	<	}
239	<
240	<	private boolean valueSearchNonNull(Entry n, Object value) {
241	<	// Check this node for the value
242	<	if (value.equals(n.value))
243	<	return true;
244	<
245	<	// Check left and right subtrees for value
246	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
247	<	(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 358 | 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 524 | Line 508 | public class TreeMap<K,V>
508		*         does not permit null keys
509		*/
510		public V put(K key, V value) {
527	–	// Offload comparator-based version for sake of performance
528	–	if (comparator != null)
529	–	return putUsingComparator(key, value);
530	–	if (key == null)
531	–	throw new NullPointerException();
532	–	Comparable<? super K> k = (Comparable<? super K>) key;
533	–	int cmp = 0;
534	–	Entry<K,V> parent = null;
511		Entry<K,V> t = root;
512	<	while (t != null) {
513	<	parent = t;
514	<	cmp = k.compareTo(t.key);
515	<	if (cmp < 0)
516	<	t = t.left;
517	<	else if (cmp > 0)
542	<	t = t.right;
543	<	else
544	<	return t.setValue(value);
545	<	}
546	<	Entry<K,V> e = new Entry<K,V>((K)k, value, parent);
547	<	size++;
548	<	modCount++;
549	<	if (parent != null) {
550	<	if (cmp < 0)
551	<	parent.left = e;
552	<	else
553	<	parent.right = e;
554	<	fixAfterInsertion(e);
512	>	if (t == null) {
513	>	compare(key, key); // type check
514	>	root = new Entry<K,V>(key, value, null);
515	>	size = 1;
516	>	modCount++;
517	>	return null;
518		}
519	<	else
520	<	root = e;
521	<	return null;
559	<	}
560	<
561	<	/**
562	<	* Version of put using comparator. Split off from put for
563	<	* performance.
564	<	*/
565	<	final V putUsingComparator(K key, V value) {
519	>	int cmp;
520	>	Entry<K,V> parent;
521	>	// split comparator and comparable paths
522		Comparator<? super K> cpr = comparator;
523	<	int cmp = 0;
524	<	Entry<K,V> parent = null;
525	<	Entry<K,V> t = root;
526	<	if (t == null)
527	<	cpr.compare(key, key); // type check
528	<	while (t != null) {
529	<	parent = t;
530	<	cmp = cpr.compare(key, t.key);
531	<	if (cmp < 0)
532	<	t = t.left;
533	<	else if (cmp > 0)
534	<	t = t.right;
535	<	else
536	<	return t.setValue(value);
523	>	if (cpr != null) {
524	>	do {
525	>	parent = t;
526	>	cmp = cpr.compare(key, t.key);
527	>	if (cmp < 0)
528	>	t = t.left;
529	>	else if (cmp > 0)
530	>	t = t.right;
531	>	else
532	>	return t.setValue(value);
533	>	} while (t != null);
534	>	}
535	>	else {
536	>	if (key == null)
537	>	throw new NullPointerException();
538	>	Comparable<? super K> k = (Comparable<? super K>) key;
539	>	do {
540	>	parent = t;
541	>	cmp = k.compareTo(t.key);
542	>	if (cmp < 0)
543	>	t = t.left;
544	>	else if (cmp > 0)
545	>	t = t.right;
546	>	else
547	>	return t.setValue(value);
548	>	} while (t != null);
549		}
550		Entry<K,V> e = new Entry<K,V>(key, value, parent);
551	+	if (cmp < 0)
552	+	parent.left = e;
553	+	else
554	+	parent.right = e;
555	+	fixAfterInsertion(e);
556		size++;
557		modCount++;
585	–	if (parent != null) {
586	–	if (cmp < 0)
587	–	parent.left = e;
588	–	else
589	–	parent.right = e;
590	–	fixAfterInsertion(e);
591	–	}
592	–	else
593	–	root = e;
558		return null;
559		}
560
#	Line 969 | Line 933 | public class TreeMap<K,V>
933		}
934
935		public boolean contains(Object o) {
936	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
973	<	if (valEquals(e.getValue(), o))
974	<	return true;
975	<	return false;
936	>	return TreeMap.this.containsValue(o);
937		}
938
939		public boolean remove(Object o) {
#	Line 2029 | Line 1990 | public class TreeMap<K,V>
1990
1991		/** From CLR */
1992		private void rotateLeft(Entry<K,V> p) {
1993	<	Entry<K,V> r = p.right;
1994	<	p.right = r.left;
1995	<	if (r.left != null)
1996	<	r.left.parent = p;
1997	<	r.parent = p.parent;
1998	<	if (p.parent == null)
1999	<	root = r;
2000	<	else if (p.parent.left == p)
2001	<	p.parent.left = r;
2002	<	else
2003	<	p.parent.right = r;
2004	<	r.left = p;
2005	<	p.parent = r;
1993	>	if (p != null) {
1994	>	Entry<K,V> r = p.right;
1995	>	p.right = r.left;
1996	>	if (r.left != null)
1997	>	r.left.parent = p;
1998	>	r.parent = p.parent;
1999	>	if (p.parent == null)
2000	>	root = r;
2001	>	else if (p.parent.left == p)
2002	>	p.parent.left = r;
2003	>	else
2004	>	p.parent.right = r;
2005	>	r.left = p;
2006	>	p.parent = r;
2007	>	}
2008		}
2009
2010		/** From CLR */
2011		private void rotateRight(Entry<K,V> p) {
2012	<	Entry<K,V> l = p.left;
2013	<	p.left = l.right;
2014	<	if (l.right != null) l.right.parent = p;
2015	<	l.parent = p.parent;
2016	<	if (p.parent == null)
2017	<	root = l;
2018	<	else if (p.parent.right == p)
2019	<	p.parent.right = l;
2020	<	else p.parent.left = l;
2021	<	l.right = p;
2022	<	p.parent = l;
2012	>	if (p != null) {
2013	>	Entry<K,V> l = p.left;
2014	>	p.left = l.right;
2015	>	if (l.right != null) l.right.parent = p;
2016	>	l.parent = p.parent;
2017	>	if (p.parent == null)
2018	>	root = l;
2019	>	else if (p.parent.right == p)
2020	>	p.parent.right = l;
2021	>	else p.parent.left = l;
2022	>	l.right = p;
2023	>	p.parent = l;
2024	>	}
2025		}
2026
2062	–
2027		/** From CLR */
2028		private void fixAfterInsertion(Entry<K,V> x) {
2029		x.color = RED;
#	Line 2079 | Line 2043 | public class TreeMap<K,V>
2043		}
2044		setColor(parentOf(x), BLACK);
2045		setColor(parentOf(parentOf(x)), RED);
2046	<	if (parentOf(parentOf(x)) != null)
2083	<	rotateRight(parentOf(parentOf(x)));
2046	>	rotateRight(parentOf(parentOf(x)));
2047		}
2048		} else {
2049		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2096 | Line 2059 | public class TreeMap<K,V>
2059		}
2060		setColor(parentOf(x), BLACK);
2061		setColor(parentOf(parentOf(x)), RED);
2062	<	if (parentOf(parentOf(x)) != null)
2100	<	rotateLeft(parentOf(parentOf(x)));
2062	>	rotateLeft(parentOf(parentOf(x)));
2063		}
2064		}
2065		}
#	Line 2107 | Line 2069 | public class TreeMap<K,V>
2069		/**
2070		* Delete node p, and then rebalance the tree.
2071		*/
2110	–
2072		private void deleteEntry(Entry<K,V> p) {
2073		modCount++;
2074		size--;

Diff Legend

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