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.43 by jsr166, Sun May 20 07:54:01 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 1113 | Line 1135 | public class TreeMap<K,V>
1135		throw new IllegalStateException();
1136		if (modCount != expectedModCount)
1137		throw new ConcurrentModificationException();
1138	+	// deleted entries are replaced by their successors
1139		if (lastReturned.left != null && lastReturned.right != null)
1140		next = lastReturned;
1141		deleteEntry(lastReturned);
1142	<	expectedModCount++;
1142	>	expectedModCount = modCount;
1143		lastReturned = null;
1144		}
1145		}
#	Line 1203 | Line 1226 | public class TreeMap<K,V>
1226
1227		// SubMaps
1228
1229	+	/**
1230	+	* Dummy value serving as unmatchable fence key for unbounded
1231	+	* SubMapIterators
1232	+	*/
1233	+	private static final Object UNBOUNDED = new Object();
1234	+
1235	+	/**
1236	+	* @serial include
1237	+	*/
1238		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1239		implements NavigableMap<K,V>, java.io.Serializable {
1240	<	/*
1240	>	/**
1241		* The backing map.
1242		*/
1243		final TreeMap<K,V> m;
1244
1245	<	/*
1245	>	/**
1246		* Endpoints are represented as triples (fromStart, lo,
1247		* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1248		* true, then the low (absolute) bound is the start of the
#	Line 1218 | Line 1250 | public class TreeMap<K,V>
1250		* if loInclusive is true, lo is the inclusive bound, else lo
1251		* is the exclusive bound. Similarly for the upper bound.
1252		*/
1221	–
1253		final K lo, hi;
1254		final boolean fromStart, toEnd;
1255		final boolean loInclusive, hiInclusive;
#	Line 1343 | Line 1374 | public class TreeMap<K,V>
1374		}
1375
1376		// Abstract methods defined in ascending vs descending classes
1377	<	// These relay to the appropriate  absolute versions
1377	>	// These relay to the appropriate absolute versions
1378
1379		abstract TreeMap.Entry<K,V> subLowest();
1380		abstract TreeMap.Entry<K,V> subHighest();
#	Line 1540 | Line 1571 | public class TreeMap<K,V>
1571		abstract class SubMapIterator<T> implements Iterator<T> {
1572		TreeMap.Entry<K,V> lastReturned;
1573		TreeMap.Entry<K,V> next;
1574	<	final K fenceKey;
1574	>	final Object fenceKey;
1575		int expectedModCount;
1576
1577		SubMapIterator(TreeMap.Entry<K,V> first,
#	Line 1548 | Line 1579 | public class TreeMap<K,V>
1579		expectedModCount = m.modCount;
1580		lastReturned = null;
1581		next = first;
1582	<	fenceKey = fence == null ? null : fence.key;
1582	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1583		}
1584
1585		public final boolean hasNext() {
#	Line 1575 | Line 1606 | public class TreeMap<K,V>
1606		return e;
1607		}
1608
1609	<	public void remove() {
1609	>	final void removeAscending() {
1610		if (lastReturned == null)
1611		throw new IllegalStateException();
1612		if (m.modCount != expectedModCount)
1613		throw new ConcurrentModificationException();
1614	+	// deleted entries are replaced by their successors
1615		if (lastReturned.left != null && lastReturned.right != null)
1616		next = lastReturned;
1617		m.deleteEntry(lastReturned);
1586	–	expectedModCount++;
1618		lastReturned = null;
1619	+	expectedModCount = m.modCount;
1620	+	}
1621	+
1622	+	final void removeDescending() {
1623	+	if (lastReturned == null)
1624	+	throw new IllegalStateException();
1625	+	if (m.modCount != expectedModCount)
1626	+	throw new ConcurrentModificationException();
1627	+	m.deleteEntry(lastReturned);
1628	+	lastReturned = null;
1629	+	expectedModCount = m.modCount;
1630		}
1631	+
1632		}
1633
1634		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1596 | Line 1639 | public class TreeMap<K,V>
1639		public Map.Entry<K,V> next() {
1640		return nextEntry();
1641		}
1642	+	public void remove() {
1643	+	removeAscending();
1644	+	}
1645		}
1646
1647		final class SubMapKeyIterator extends SubMapIterator<K> {
#	Line 1606 | Line 1652 | public class TreeMap<K,V>
1652		public K next() {
1653		return nextEntry().key;
1654		}
1655	+	public void remove() {
1656	+	removeAscending();
1657	+	}
1658		}
1659
1660		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
#	Line 1617 | Line 1666 | public class TreeMap<K,V>
1666		public Map.Entry<K,V> next() {
1667		return prevEntry();
1668		}
1669	+	public void remove() {
1670	+	removeDescending();
1671	+	}
1672		}
1673
1674		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
#	Line 1627 | Line 1679 | public class TreeMap<K,V>
1679		public K next() {
1680		return prevEntry().key;
1681		}
1682	+	public void remove() {
1683	+	removeDescending();
1684	+	}
1685		}
1686		}
1687
1688	+	/**
1689	+	* @serial include
1690	+	*/
1691		static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1692		private static final long serialVersionUID = 912986545866124060L;
1693
1694		AscendingSubMap(TreeMap<K,V> m,
1695		boolean fromStart, K lo, boolean loInclusive,
1696	<	boolean toEnd, K hi, boolean hiInclusive) {
1696	>	boolean toEnd,     K hi, boolean hiInclusive) {
1697		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1698		}
1699
#	Line 1644 | Line 1702 | public class TreeMap<K,V>
1702		}
1703
1704		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1705	<	K toKey, boolean toInclusive) {
1705	>	K toKey,   boolean toInclusive) {
1706		if (!inRange(fromKey, fromInclusive))
1707		throw new IllegalArgumentException("fromKey out of range");
1708		if (!inRange(toKey, toInclusive))
#	Line 1655 | Line 1713 | public class TreeMap<K,V>
1713		}
1714
1715		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1716	<	if (!inClosedRange(toKey))
1716	>	if (!inRange(toKey, inclusive))
1717		throw new IllegalArgumentException("toKey out of range");
1718		return new AscendingSubMap(m,
1719		fromStart, lo,    loInclusive,
#	Line 1706 | Line 1764 | public class TreeMap<K,V>
1764		TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1765		}
1766
1767	+	/**
1768	+	* @serial include
1769	+	*/
1770		static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1771		private static final long serialVersionUID = 912986545866120460L;
1772		DescendingSubMap(TreeMap<K,V> m,
1773		boolean fromStart, K lo, boolean loInclusive,
1774	<	boolean toEnd, K hi, boolean hiInclusive) {
1774	>	boolean toEnd,     K hi, boolean hiInclusive) {
1775		super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1776		}
1777
#	Line 1722 | Line 1783 | public class TreeMap<K,V>
1783		}
1784
1785		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1786	<	K toKey, boolean toInclusive) {
1786	>	K toKey,   boolean toInclusive) {
1787		if (!inRange(fromKey, fromInclusive))
1788		throw new IllegalArgumentException("fromKey out of range");
1789		if (!inRange(toKey, toInclusive))
#	Line 1790 | Line 1851 | public class TreeMap<K,V>
1851		* support NavigableMap.  It translates an old-version SubMap into
1852		* a new-version AscendingSubMap. This class is never otherwise
1853		* used.
1854	+	*
1855	+	* @serial include
1856		*/
1857		private class SubMap extends AbstractMap<K,V>
1858		implements SortedMap<K,V>, java.io.Serializable {
#	Line 1873 | Line 1936 | public class TreeMap<K,V>
1936		public boolean equals(Object o) {
1937		if (!(o instanceof Map.Entry))
1938		return false;
1939	<	Map.Entry e = (Map.Entry)o;
1939	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1940
1941		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1942		}
#	Line 2314 | Line 2377 | public class TreeMap<K,V>
2377
2378		if (hi < lo) return null;
2379
2380	<	int mid = (lo + hi) / 2;
2380	>	int mid = (lo + hi) >>> 1;
2381
2382		Entry<K,V> left  = null;
2383		if (lo < mid)

Diff Legend

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