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.44 by jsr166, Mon May 21 20:23:38 2007 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
#	Line 68 | Line 86 | package java.util;
86		* associated map using <tt>put</tt>.)
87		*
88		* <p>This class is a member of the
89	<	* <a href="{@docRoot}/../guide/collections/index.html">
89	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
90		* Java Collections Framework</a>.
91		*
92		* @param <K> the type of keys maintained by this map
#	Line 510 | Line 528 | public class TreeMap<K,V>
528		public V put(K key, V value) {
529		Entry<K,V> t = root;
530		if (t == null) {
531	<	compare(key, key); // type check
531	>	// TBD:
532	>	// 5045147: (coll) Adding null to an empty TreeSet should
533	>	// throw NullPointerException
534	>	//
535	>	// compare(key, key); // type check
536		root = new Entry<K,V>(key, value, null);
537		size = 1;
538		modCount++;
#	Line 1046 | Line 1068 | public class TreeMap<K,V>
1068		return size() != oldSize;
1069		}
1070		public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071	<	E toElement, boolean toInclusive) {
1071	>	E toElement,   boolean toInclusive) {
1072		return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1073		toElement,   toInclusive));
1074		}
#	Line 1089 | Line 1111 | public class TreeMap<K,V>
1111		}
1112
1113		final Entry<K,V> nextEntry() {
1114	<	Entry<K,V> e = lastReturned = next;
1114	>	Entry<K,V> e = next;
1115		if (e == null)
1116		throw new NoSuchElementException();
1117		if (modCount != expectedModCount)
1118		throw new ConcurrentModificationException();
1119		next = successor(e);
1120	+	lastReturned = e;
1121		return e;
1122		}
1123
1124		final Entry<K,V> prevEntry() {
1125	<	Entry<K,V> e = lastReturned= next;
1125	>	Entry<K,V> e = next;
1126		if (e == null)
1127		throw new NoSuchElementException();
1128		if (modCount != expectedModCount)
1129		throw new ConcurrentModificationException();
1130		next = predecessor(e);
1131	+	lastReturned = e;
1132		return e;
1133		}
1134
#	Line 1113 | Line 1137 | public class TreeMap<K,V>
1137		throw new IllegalStateException();
1138		if (modCount != expectedModCount)
1139		throw new ConcurrentModificationException();
1140	+	// deleted entries are replaced by their successors
1141		if (lastReturned.left != null && lastReturned.right != null)
1142		next = lastReturned;
1143		deleteEntry(lastReturned);
1144	<	expectedModCount++;
1144	>	expectedModCount = modCount;
1145		lastReturned = null;
1146		}
1147		}
#	Line 1203 | Line 1228 | public class TreeMap<K,V>
1228
1229		// SubMaps
1230
1231	+	/**
1232	+	* Dummy value serving as unmatchable fence key for unbounded
1233	+	* SubMapIterators
1234	+	*/
1235	+	private static final Object UNBOUNDED = new Object();
1236	+
1237	+	/**
1238	+	* @serial include
1239	+	*/
1240		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241		implements NavigableMap<K,V>, java.io.Serializable {
1242	<	/*
1242	>	/**
1243		* The backing map.
1244		*/
1245		final TreeMap<K,V> m;
1246
1247	<	/*
1247	>	/**
1248		* Endpoints are represented as triples (fromStart, lo,
1249		* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250		* true, then the low (absolute) bound is the start of the
#	Line 1218 | Line 1252 | public class TreeMap<K,V>
1252		* if loInclusive is true, lo is the inclusive bound, else lo
1253		* is the exclusive bound. Similarly for the upper bound.
1254		*/
1221	–
1255		final K lo, hi;
1256		final boolean fromStart, toEnd;
1257		final boolean loInclusive, hiInclusive;
#	Line 1343 | Line 1376 | public class TreeMap<K,V>
1376		}
1377
1378		// Abstract methods defined in ascending vs descending classes
1379	<	// These relay to the appropriate  absolute versions
1379	>	// These relay to the appropriate absolute versions
1380
1381		abstract TreeMap.Entry<K,V> subLowest();
1382		abstract TreeMap.Entry<K,V> subHighest();
#	Line 1540 | Line 1573 | public class TreeMap<K,V>
1573		abstract class SubMapIterator<T> implements Iterator<T> {
1574		TreeMap.Entry<K,V> lastReturned;
1575		TreeMap.Entry<K,V> next;
1576	<	final K fenceKey;
1576	>	final Object fenceKey;
1577		int expectedModCount;
1578
1579		SubMapIterator(TreeMap.Entry<K,V> first,
#	Line 1548 | Line 1581 | public class TreeMap<K,V>
1581		expectedModCount = m.modCount;
1582		lastReturned = null;
1583		next = first;
1584	<	fenceKey = fence == null ? null : fence.key;
1584	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1585		}
1586
1587		public final boolean hasNext() {
#	Line 1556 | Line 1589 | public class TreeMap<K,V>
1589		}
1590
1591		final TreeMap.Entry<K,V> nextEntry() {
1592	<	TreeMap.Entry<K,V> e = lastReturned = next;
1592	>	TreeMap.Entry<K,V> e = next;
1593		if (e == null || e.key == fenceKey)
1594		throw new NoSuchElementException();
1595		if (m.modCount != expectedModCount)
1596		throw new ConcurrentModificationException();
1597		next = successor(e);
1598	+	lastReturned = e;
1599		return e;
1600		}
1601
1602		final TreeMap.Entry<K,V> prevEntry() {
1603	<	TreeMap.Entry<K,V> e = lastReturned = next;
1603	>	TreeMap.Entry<K,V> e = next;
1604		if (e == null || e.key == fenceKey)
1605		throw new NoSuchElementException();
1606		if (m.modCount != expectedModCount)
1607		throw new ConcurrentModificationException();
1608		next = predecessor(e);
1609	+	lastReturned = e;
1610		return e;
1611		}
1612
1613	<	public void remove() {
1613	>	final void removeAscending() {
1614		if (lastReturned == null)
1615		throw new IllegalStateException();
1616		if (m.modCount != expectedModCount)
1617		throw new ConcurrentModificationException();
1618	+	// deleted entries are replaced by their successors
1619		if (lastReturned.left != null && lastReturned.right != null)
1620		next = lastReturned;
1621		m.deleteEntry(lastReturned);
1586	–	expectedModCount++;
1622		lastReturned = null;
1623	+	expectedModCount = m.modCount;
1624	+	}
1625	+
1626	+	final void removeDescending() {
1627	+	if (lastReturned == null)
1628	+	throw new IllegalStateException();
1629	+	if (m.modCount != expectedModCount)
1630	+	throw new ConcurrentModificationException();
1631	+	m.deleteEntry(lastReturned);
1632	+	lastReturned = null;
1633	+	expectedModCount = m.modCount;
1634		}
1635	+
1636		}
1637
1638		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1596 | Line 1643 | public class TreeMap<K,V>
1643		public Map.Entry<K,V> next() {
1644		return nextEntry();
1645		}
1646	+	public void remove() {
1647	+	removeAscending();
1648	+	}
1649		}
1650
1651		final class SubMapKeyIterator extends SubMapIterator<K> {
#	Line 1606 | Line 1656 | public class TreeMap<K,V>
1656		public K next() {
1657		return nextEntry().key;
1658		}
1659	+	public void remove() {
1660	+	removeAscending();
1661	+	}
1662		}
1663
1664		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1617 | Line 1670 | public class TreeMap<K,V>
1670		public Map.Entry<K,V> next() {
1671		return prevEntry();
1672		}
1673	+	public void remove() {
1674	+	removeDescending();
1675	+	}
1676		}
1677
1678		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
#	Line 1627 | Line 1683 | public class TreeMap<K,V>
1683		public K next() {
1684		return prevEntry().key;
1685		}
1686	+	public void remove() {
1687	+	removeDescending();
1688	+	}
1689		}
1690		}
1691
1692	+	/**
1693	+	* @serial include
1694	+	*/
1695		static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1696		private static final long serialVersionUID = 912986545866124060L;
1697
1698		AscendingSubMap(TreeMap<K,V> m,
1699		boolean fromStart, K lo, boolean loInclusive,
1700	<	boolean toEnd, K hi, boolean hiInclusive) {
1700	>	boolean toEnd,     K hi, boolean hiInclusive) {
1701		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1702		}
1703
#	Line 1644 | Line 1706 | public class TreeMap<K,V>
1706		}
1707
1708		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1709	<	K toKey, boolean toInclusive) {
1709	>	K toKey,   boolean toInclusive) {
1710		if (!inRange(fromKey, fromInclusive))
1711		throw new IllegalArgumentException("fromKey out of range");
1712		if (!inRange(toKey, toInclusive))
#	Line 1655 | Line 1717 | public class TreeMap<K,V>
1717		}
1718
1719		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1720	<	if (!inClosedRange(toKey))
1720	>	if (!inRange(toKey, inclusive))
1721		throw new IllegalArgumentException("toKey out of range");
1722		return new AscendingSubMap(m,
1723		fromStart, lo,    loInclusive,
#	Line 1706 | Line 1768 | public class TreeMap<K,V>
1768		TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1769		}
1770
1771	+	/**
1772	+	* @serial include
1773	+	*/
1774		static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1775		private static final long serialVersionUID = 912986545866120460L;
1776		DescendingSubMap(TreeMap<K,V> m,
1777		boolean fromStart, K lo, boolean loInclusive,
1778	<	boolean toEnd, K hi, boolean hiInclusive) {
1778	>	boolean toEnd,     K hi, boolean hiInclusive) {
1779		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1780		}
1781
#	Line 1722 | Line 1787 | public class TreeMap<K,V>
1787		}
1788
1789		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1790	<	K toKey, boolean toInclusive) {
1790	>	K toKey,   boolean toInclusive) {
1791		if (!inRange(fromKey, fromInclusive))
1792		throw new IllegalArgumentException("fromKey out of range");
1793		if (!inRange(toKey, toInclusive))
#	Line 1790 | Line 1855 | public class TreeMap<K,V>
1855		* support NavigableMap.  It translates an old-version SubMap into
1856		* a new-version AscendingSubMap. This class is never otherwise
1857		* used.
1858	+	*
1859	+	* @serial include
1860		*/
1861		private class SubMap extends AbstractMap<K,V>
1862		implements SortedMap<K,V>, java.io.Serializable {
#	Line 1873 | Line 1940 | public class TreeMap<K,V>
1940		public boolean equals(Object o) {
1941		if (!(o instanceof Map.Entry))
1942		return false;
1943	<	Map.Entry e = (Map.Entry)o;
1943	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1944
1945		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1946		}
#	Line 2314 | Line 2381 | public class TreeMap<K,V>
2381
2382		if (hi < lo) return null;
2383
2384	<	int mid = (lo + hi) / 2;
2384	>	int mid = (lo + hi) >>> 1;
2385
2386		Entry<K,V> left  = null;
2387		if (lo < mid)

Diff Legend

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