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.40 by dl, Mon Jun 12 14:00:38 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 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)
518	<	t = t.right;
519	<	else
520	<	return t.setValue(value);
521	<	}
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	>	// 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	<	else
524	<	root = e;
525	<	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) {
523	>	int cmp;
524	>	Entry<K,V> parent;
525	>	// split comparator and comparable paths
526		Comparator<? super K> cpr = comparator;
527	<	int cmp = 0;
528	<	Entry<K,V> parent = null;
529	<	Entry<K,V> t = root;
530	<	if (t == null)
531	<	cpr.compare(key, key); // type check
532	<	while (t != null) {
533	<	parent = t;
534	<	cmp = cpr.compare(key, t.key);
535	<	if (cmp < 0)
536	<	t = t.left;
537	<	else if (cmp > 0)
538	<	t = t.right;
539	<	else
540	<	return t.setValue(value);
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 if (cmp > 0)
534	>	t = t.right;
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++;
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;
562		return null;
563		}
564
#	Line 969 | 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))
973	<	if (valEquals(e.getValue(), o))
974	<	return true;
975	<	return false;
940	>	return TreeMap.this.containsValue(o);
941		}
942
943		public boolean remove(Object o) {
#	Line 1085 | 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 1152 | 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 1242 | Line 1208 | public class TreeMap<K,V>
1208
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	<	/*
1216	>	/**
1217		* The backing map.
1218		*/
1219		final TreeMap<K,V> m;
1220
1221	<	/*
1221	>	/**
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
#	Line 1257 | Line 1226 | public class TreeMap<K,V>
1226		* if loInclusive is true, lo is the inclusive bound, else lo
1227		* is the exclusive bound. Similarly for the upper bound.
1228		*/
1260	–
1229		final K lo, hi;
1230		final boolean fromStart, toEnd;
1231		final boolean loInclusive, hiInclusive;
#	Line 1382 | Line 1350 | public class TreeMap<K,V>
1350		}
1351
1352		// Abstract methods defined in ascending vs descending classes
1353	<	// These relay to the appropriate  absolute versions
1353	>	// These relay to the appropriate absolute versions
1354
1355		abstract TreeMap.Entry<K,V> subLowest();
1356		abstract TreeMap.Entry<K,V> subHighest();
#	Line 1614 | Line 1582 | public class TreeMap<K,V>
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);
1625	–	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>> {
#	Line 1635 | Line 1615 | public class TreeMap<K,V>
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> {
#	Line 1645 | Line 1628 | public class TreeMap<K,V>
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>> {
#	Line 1656 | Line 1642 | public class TreeMap<K,V>
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> {
#	Line 1666 | Line 1655 | public class TreeMap<K,V>
1655		public K next() {
1656		return prevEntry().key;
1657		}
1658	+	public void remove() {
1659	+	removeDescending();
1660	+	}
1661		}
1662		}
1663
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, boolean loInclusive,
1672	<	boolean toEnd, K hi, boolean hiInclusive) {
1672	>	boolean toEnd,     K hi, boolean hiInclusive) {
1673		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1674		}
1675
#	Line 1683 | Line 1678 | public class TreeMap<K,V>
1678		}
1679
1680		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1681	<	K toKey, boolean toInclusive) {
1681	>	K toKey,   boolean toInclusive) {
1682		if (!inRange(fromKey, fromInclusive))
1683		throw new IllegalArgumentException("fromKey out of range");
1684		if (!inRange(toKey, toInclusive))
#	Line 1694 | Line 1689 | public class TreeMap<K,V>
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,    loInclusive,
#	Line 1745 | Line 1740 | public class TreeMap<K,V>
1740		TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1741		}
1742
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, boolean loInclusive,
1750	<	boolean toEnd, K hi, boolean hiInclusive) {
1750	>	boolean toEnd,     K hi, boolean hiInclusive) {
1751		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1752		}
1753
#	Line 1761 | Line 1759 | public class TreeMap<K,V>
1759		}
1760
1761		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1762	<	K toKey, boolean toInclusive) {
1762	>	K toKey,   boolean toInclusive) {
1763		if (!inRange(fromKey, fromInclusive))
1764		throw new IllegalArgumentException("fromKey out of range");
1765		if (!inRange(toKey, toInclusive))
#	Line 1829 | 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 1912 | 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 2029 | Line 2029 | public class TreeMap<K,V>
2029
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 */
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
2062	–
2066		/** From CLR */
2067		private void fixAfterInsertion(Entry<K,V> x) {
2068		x.color = RED;
#	Line 2079 | 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)
2083	<	rotateRight(parentOf(parentOf(x)));
2085	>	rotateRight(parentOf(parentOf(x)));
2086		}
2087		} else {
2088		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2096 | Line 2098 | public class TreeMap<K,V>
2098		}
2099		setColor(parentOf(x), BLACK);
2100		setColor(parentOf(parentOf(x)), RED);
2101	<	if (parentOf(parentOf(x)) != null)
2100	<	rotateLeft(parentOf(parentOf(x)));
2101	>	rotateLeft(parentOf(parentOf(x)));
2102		}
2103		}
2104		}
#	Line 2107 | Line 2108 | public class TreeMap<K,V>
2108		/**
2109		* Delete node p, and then rebalance the tree.
2110		*/
2110	–
2111		private void deleteEntry(Entry<K,V> p) {
2112		modCount++;
2113		size--;
#	Line 2353 | Line 2353 | public class TreeMap<K,V>
2353
2354		if (hi < lo) return null;
2355
2356	<	int mid = (lo + hi) / 2;
2356	>	int mid = (lo + hi) >>> 1;
2357
2358		Entry<K,V> left  = null;
2359		if (lo < mid)

Diff Legend

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