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.34 by dl, Sun Apr 23 20:59:49 2006 UTC vs.
Revision 1.42 by jsr166, Tue Jan 30 03:54:29 2007 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
#	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 510 | Line 510 | public class TreeMap<K,V>
510		public V put(K key, V value) {
511		Entry<K,V> t = root;
512		if (t == null) {
513	<	compare(key, key); // type check
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++;
#	Line 1046 | 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 1113 | 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 1203 | Line 1208 | public class TreeMap<K,V>
1208
1209		// SubMaps
1210
1211	+	/**
1212	+	* Dummy value serving as unmatchable fence key for unbounded
1213	+	* SubMapIterators
1214	+	*/
1215	+	private static final Object UNBOUNDED = new Object();
1216	+
1217	+	/**
1218	+	* @serial include
1219	+	*/
1220		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1221		implements NavigableMap<K,V>, java.io.Serializable {
1222	<	/*
1222	>	/**
1223		* The backing map.
1224		*/
1225		final TreeMap<K,V> m;
1226
1227	<	/*
1227	>	/**
1228		* Endpoints are represented as triples (fromStart, lo,
1229		* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1230		* true, then the low (absolute) bound is the start of the
#	Line 1218 | Line 1232 | public class TreeMap<K,V>
1232		* if loInclusive is true, lo is the inclusive bound, else lo
1233		* is the exclusive bound. Similarly for the upper bound.
1234		*/
1221	–
1235		final K lo, hi;
1236		final boolean fromStart, toEnd;
1237		final boolean loInclusive, hiInclusive;
#	Line 1343 | Line 1356 | public class TreeMap<K,V>
1356		}
1357
1358		// Abstract methods defined in ascending vs descending classes
1359	<	// These relay to the appropriate  absolute versions
1359	>	// These relay to the appropriate absolute versions
1360
1361		abstract TreeMap.Entry<K,V> subLowest();
1362		abstract TreeMap.Entry<K,V> subHighest();
#	Line 1540 | Line 1553 | public class TreeMap<K,V>
1553		abstract class SubMapIterator<T> implements Iterator<T> {
1554		TreeMap.Entry<K,V> lastReturned;
1555		TreeMap.Entry<K,V> next;
1556	<	final K fenceKey;
1556	>	final Object fenceKey;
1557		int expectedModCount;
1558
1559		SubMapIterator(TreeMap.Entry<K,V> first,
#	Line 1548 | Line 1561 | public class TreeMap<K,V>
1561		expectedModCount = m.modCount;
1562		lastReturned = null;
1563		next = first;
1564	<	fenceKey = fence == null ? null : fence.key;
1564	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1565		}
1566
1567		public final boolean hasNext() {
#	Line 1575 | Line 1588 | public class TreeMap<K,V>
1588		return e;
1589		}
1590
1591	<	public void remove() {
1591	>	final void removeAscending() {
1592		if (lastReturned == null)
1593		throw new IllegalStateException();
1594		if (m.modCount != expectedModCount)
1595		throw new ConcurrentModificationException();
1596	+	// deleted entries are replaced by their successors
1597		if (lastReturned.left != null && lastReturned.right != null)
1598		next = lastReturned;
1599		m.deleteEntry(lastReturned);
1586	–	expectedModCount++;
1600		lastReturned = null;
1601	+	expectedModCount = m.modCount;
1602		}
1603	+
1604	+	final void removeDescending() {
1605	+	if (lastReturned == null)
1606	+	throw new IllegalStateException();
1607	+	if (m.modCount != expectedModCount)
1608	+	throw new ConcurrentModificationException();
1609	+	m.deleteEntry(lastReturned);
1610	+	lastReturned = null;
1611	+	expectedModCount = m.modCount;
1612	+	}
1613	+
1614		}
1615
1616		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1596 | Line 1621 | public class TreeMap<K,V>
1621		public Map.Entry<K,V> next() {
1622		return nextEntry();
1623		}
1624	+	public void remove() {
1625	+	removeAscending();
1626	+	}
1627		}
1628
1629		final class SubMapKeyIterator extends SubMapIterator<K> {
#	Line 1606 | Line 1634 | public class TreeMap<K,V>
1634		public K next() {
1635		return nextEntry().key;
1636		}
1637	+	public void remove() {
1638	+	removeAscending();
1639	+	}
1640		}
1641
1642		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1617 | Line 1648 | public class TreeMap<K,V>
1648		public Map.Entry<K,V> next() {
1649		return prevEntry();
1650		}
1651	+	public void remove() {
1652	+	removeDescending();
1653	+	}
1654		}
1655
1656		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
#	Line 1627 | Line 1661 | public class TreeMap<K,V>
1661		public K next() {
1662		return prevEntry().key;
1663		}
1664	+	public void remove() {
1665	+	removeDescending();
1666	+	}
1667		}
1668		}
1669
1670	+	/**
1671	+	* @serial include
1672	+	*/
1673		static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1674		private static final long serialVersionUID = 912986545866124060L;
1675
1676		AscendingSubMap(TreeMap<K,V> m,
1677		boolean fromStart, K lo, boolean loInclusive,
1678	<	boolean toEnd, K hi, boolean hiInclusive) {
1678	>	boolean toEnd,     K hi, boolean hiInclusive) {
1679		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1680		}
1681
#	Line 1644 | Line 1684 | public class TreeMap<K,V>
1684		}
1685
1686		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1687	<	K toKey, boolean toInclusive) {
1687	>	K toKey,   boolean toInclusive) {
1688		if (!inRange(fromKey, fromInclusive))
1689		throw new IllegalArgumentException("fromKey out of range");
1690		if (!inRange(toKey, toInclusive))
#	Line 1655 | Line 1695 | public class TreeMap<K,V>
1695		}
1696
1697		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1698	<	if (!inClosedRange(toKey))
1698	>	if (!inRange(toKey, inclusive))
1699		throw new IllegalArgumentException("toKey out of range");
1700		return new AscendingSubMap(m,
1701		fromStart, lo,    loInclusive,
#	Line 1706 | Line 1746 | public class TreeMap<K,V>
1746		TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1747		}
1748
1749	+	/**
1750	+	* @serial include
1751	+	*/
1752		static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1753		private static final long serialVersionUID = 912986545866120460L;
1754		DescendingSubMap(TreeMap<K,V> m,
1755		boolean fromStart, K lo, boolean loInclusive,
1756	<	boolean toEnd, K hi, boolean hiInclusive) {
1756	>	boolean toEnd,     K hi, boolean hiInclusive) {
1757		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1758		}
1759
#	Line 1722 | Line 1765 | public class TreeMap<K,V>
1765		}
1766
1767		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1768	<	K toKey, boolean toInclusive) {
1768	>	K toKey,   boolean toInclusive) {
1769		if (!inRange(fromKey, fromInclusive))
1770		throw new IllegalArgumentException("fromKey out of range");
1771		if (!inRange(toKey, toInclusive))
#	Line 1790 | Line 1833 | public class TreeMap<K,V>
1833		* support NavigableMap.  It translates an old-version SubMap into
1834		* a new-version AscendingSubMap. This class is never otherwise
1835		* used.
1836	+	*
1837	+	* @serial include
1838		*/
1839		private class SubMap extends AbstractMap<K,V>
1840		implements SortedMap<K,V>, java.io.Serializable {
#	Line 1873 | Line 1918 | public class TreeMap<K,V>
1918		public boolean equals(Object o) {
1919		if (!(o instanceof Map.Entry))
1920		return false;
1921	<	Map.Entry e = (Map.Entry)o;
1921	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1922
1923		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1924		}
#	Line 2314 | Line 2359 | public class TreeMap<K,V>
2359
2360		if (hi < lo) return null;
2361
2362	<	int mid = (lo + hi) / 2;
2362	>	int mid = (lo + hi) >>> 1;
2363
2364		Entry<K,V> left  = null;
2365		if (lo < mid)

Diff Legend

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