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.37 by dl, Tue May 9 18:17:08 2006 UTC vs.
Revision 1.51 by jsr166, Mon Sep 27 19:15:15 2010 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright (c) 1997, 2008, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22	>	* or visit www.oracle.com if you need additional information or have any
23	>	* questions.
24		*/
25
26		package java.util;
#	Line 75 | Line 93 | package java.util;
93		* @param <V> the type of mapped values
94		*
95		* @author  Josh Bloch and Doug Lea
78	–	* @version %I%, %G%
96		* @see Map
97		* @see HashMap
98		* @see Hashtable
#	Line 219 | Line 236 | public class TreeMap<K,V>
236		*
237		* @param value value whose presence in this map is to be tested
238		* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
239	<	*         <tt>false</tt> otherwise
239	>	*         <tt>false</tt> otherwise
240		* @since 1.2
241		*/
242		public boolean containsValue(Object value) {
#	Line 291 | Line 308 | public class TreeMap<K,V>
308		if (size==0 && mapSize!=0 && map instanceof SortedMap) {
309		Comparator c = ((SortedMap)map).comparator();
310		if (c == comparator || (c != null && c.equals(comparator))) {
311	<	++modCount;
312	<	try {
313	<	buildFromSorted(mapSize, map.entrySet().iterator(),
314	<	null, null);
315	<	} catch (java.io.IOException cannotHappen) {
316	<	} catch (ClassNotFoundException cannotHappen) {
317	<	}
318	<	return;
311	>	++modCount;
312	>	try {
313	>	buildFromSorted(mapSize, map.entrySet().iterator(),
314	>	null, null);
315	>	} catch (java.io.IOException cannotHappen) {
316	>	} catch (ClassNotFoundException cannotHappen) {
317	>	}
318	>	return;
319		}
320		}
321		super.putAll(map);
#	Line 322 | Line 339 | public class TreeMap<K,V>
339		return getEntryUsingComparator(key);
340		if (key == null)
341		throw new NullPointerException();
342	<	Comparable<? super K> k = (Comparable<? super K>) key;
342	>	Comparable<? super K> k = (Comparable<? super K>) key;
343		Entry<K,V> p = root;
344		while (p != null) {
345		int cmp = k.compareTo(p.key);
#	Line 343 | Line 360 | public class TreeMap<K,V>
360		* worthwhile here.)
361		*/
362		final Entry<K,V> getEntryUsingComparator(Object key) {
363	<	K k = (K) key;
363	>	K k = (K) key;
364		Comparator<? super K> cpr = comparator;
365		if (cpr != null) {
366		Entry<K,V> p = root;
#	Line 510 | Line 527 | public class TreeMap<K,V>
527		public V put(K key, V value) {
528		Entry<K,V> t = root;
529		if (t == null) {
530	<	// TBD:
531	<	// 5045147: (coll) Adding null to an empty TreeSet should
532	<	// throw NullPointerException
533	<	//
534	<	// compare(key, key); // type check
530	>	// TBD:
531	>	// 5045147: (coll) Adding null to an empty TreeSet should
532	>	// throw NullPointerException
533	>	//
534	>	// compare(key, key); // type check
535		root = new Entry<K,V>(key, value, null);
536		size = 1;
537		modCount++;
#	Line 1004 | Line 1021 | public class TreeMap<K,V>
1021		}
1022
1023		Iterator<K> descendingKeyIterator() {
1024	<	return new DescendingKeyIterator(getFirstEntry());
1024	>	return new DescendingKeyIterator(getLastEntry());
1025		}
1026
1027		static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
#	Line 1051 | Line 1068 | public class TreeMap<K,V>
1068		}
1069		public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1070		E toElement,   boolean toInclusive) {
1071	<	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1072	<	toElement,   toInclusive));
1071	>	return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1072	>	toElement,   toInclusive));
1073		}
1074		public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1075	<	return new TreeSet<E>(m.headMap(toElement, inclusive));
1075	>	return new KeySet<E>(m.headMap(toElement, inclusive));
1076		}
1077		public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1078	<	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1078	>	return new KeySet<E>(m.tailMap(fromElement, inclusive));
1079		}
1080		public SortedSet<E> subSet(E fromElement, E toElement) {
1081		return subSet(fromElement, true, toElement, false);
#	Line 1070 | Line 1087 | public class TreeMap<K,V>
1087		return tailSet(fromElement, true);
1088		}
1089		public NavigableSet<E> descendingSet() {
1090	<	return new TreeSet(m.descendingMap());
1090	>	return new KeySet(m.descendingMap());
1091		}
1092		}
1093
#	Line 1092 | Line 1109 | public class TreeMap<K,V>
1109		return next != null;
1110		}
1111
1112	<	final Entry<K,V> nextEntry() {
1113	<	Entry<K,V> e = lastReturned = next;
1112	>	final Entry<K,V> nextEntry() {
1113	>	Entry<K,V> e = next;
1114		if (e == null)
1115		throw new NoSuchElementException();
1116		if (modCount != expectedModCount)
1117		throw new ConcurrentModificationException();
1118		next = successor(e);
1119	+	lastReturned = e;
1120		return e;
1121		}
1122
1123		final Entry<K,V> prevEntry() {
1124	<	Entry<K,V> e = lastReturned= next;
1124	>	Entry<K,V> e = next;
1125		if (e == null)
1126		throw new NoSuchElementException();
1127		if (modCount != expectedModCount)
1128		throw new ConcurrentModificationException();
1129		next = predecessor(e);
1130	+	lastReturned = e;
1131		return e;
1132		}
1133
#	Line 1121 | Line 1140 | public class TreeMap<K,V>
1140		if (lastReturned.left != null && lastReturned.right != null)
1141		next = lastReturned;
1142		deleteEntry(lastReturned);
1143	<	expectedModCount++;
1143	>	expectedModCount = modCount;
1144		lastReturned = null;
1145		}
1146		}
#	Line 1176 | Line 1195 | public class TreeMap<K,V>
1195		* Test two values for equality.  Differs from o1.equals(o2) only in
1196		* that it copes with <tt>null</tt> o1 properly.
1197		*/
1198	<	final static boolean valEquals(Object o1, Object o2) {
1198	>	static final boolean valEquals(Object o1, Object o2) {
1199		return (o1==null ? o2==null : o1.equals(o2));
1200		}
1201
#	Line 1209 | Line 1228 | public class TreeMap<K,V>
1228		// SubMaps
1229
1230		/**
1231	+	* Dummy value serving as unmatchable fence key for unbounded
1232	+	* SubMapIterators
1233	+	*/
1234	+	private static final Object UNBOUNDED = new Object();
1235	+
1236	+	/**
1237		* @serial include
1238		*/
1239	<	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1239	>	abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1240		implements NavigableMap<K,V>, java.io.Serializable {
1241		/**
1242		* The backing map.
#	Line 1292 | Line 1317 | public class TreeMap<K,V>
1317		*/
1318
1319		final TreeMap.Entry<K,V> absLowest() {
1320	<	TreeMap.Entry<K,V> e =
1320	>	TreeMap.Entry<K,V> e =
1321		(fromStart ?  m.getFirstEntry() :
1322		(loInclusive ? m.getCeilingEntry(lo) :
1323		m.getHigherEntry(lo)));
#	Line 1300 | Line 1325 | public class TreeMap<K,V>
1325		}
1326
1327		final TreeMap.Entry<K,V> absHighest() {
1328	<	TreeMap.Entry<K,V> e =
1328	>	TreeMap.Entry<K,V> e =
1329		(toEnd ?  m.getLastEntry() :
1330		(hiInclusive ?  m.getFloorEntry(hi) :
1331		m.getLowerEntry(hi)));
#	Line 1310 | Line 1335 | public class TreeMap<K,V>
1335		final TreeMap.Entry<K,V> absCeiling(K key) {
1336		if (tooLow(key))
1337		return absLowest();
1338	<	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1338	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1339		return (e == null || tooHigh(e.key)) ? null : e;
1340		}
1341
1342		final TreeMap.Entry<K,V> absHigher(K key) {
1343		if (tooLow(key))
1344		return absLowest();
1345	<	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1345	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1346		return (e == null || tooHigh(e.key)) ? null : e;
1347		}
1348
1349		final TreeMap.Entry<K,V> absFloor(K key) {
1350		if (tooHigh(key))
1351		return absHighest();
1352	<	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1352	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1353		return (e == null || tooLow(e.key)) ? null : e;
1354		}
1355
1356		final TreeMap.Entry<K,V> absLower(K key) {
1357		if (tooHigh(key))
1358		return absHighest();
1359	<	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1359	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1360		return (e == null || tooLow(e.key)) ? null : e;
1361		}
1362
#	Line 1442 | Line 1467 | public class TreeMap<K,V>
1467		}
1468
1469		public final Map.Entry<K,V> pollFirstEntry() {
1470	<	TreeMap.Entry<K,V> e = subLowest();
1470	>	TreeMap.Entry<K,V> e = subLowest();
1471		Map.Entry<K,V> result = exportEntry(e);
1472		if (e != null)
1473		m.deleteEntry(e);
#	Line 1450 | Line 1475 | public class TreeMap<K,V>
1475		}
1476
1477		public final Map.Entry<K,V> pollLastEntry() {
1478	<	TreeMap.Entry<K,V> e = subHighest();
1478	>	TreeMap.Entry<K,V> e = subHighest();
1479		Map.Entry<K,V> result = exportEntry(e);
1480		if (e != null)
1481		m.deleteEntry(e);
#	Line 1547 | Line 1572 | public class TreeMap<K,V>
1572		abstract class SubMapIterator<T> implements Iterator<T> {
1573		TreeMap.Entry<K,V> lastReturned;
1574		TreeMap.Entry<K,V> next;
1575	<	final K fenceKey;
1575	>	final Object fenceKey;
1576		int expectedModCount;
1577
1578		SubMapIterator(TreeMap.Entry<K,V> first,
#	Line 1555 | Line 1580 | public class TreeMap<K,V>
1580		expectedModCount = m.modCount;
1581		lastReturned = null;
1582		next = first;
1583	<	fenceKey = fence == null ? null : fence.key;
1583	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1584		}
1585
1586		public final boolean hasNext() {
#	Line 1563 | Line 1588 | public class TreeMap<K,V>
1588		}
1589
1590		final TreeMap.Entry<K,V> nextEntry() {
1591	<	TreeMap.Entry<K,V> e = lastReturned = next;
1591	>	TreeMap.Entry<K,V> e = next;
1592		if (e == null || e.key == fenceKey)
1593		throw new NoSuchElementException();
1594		if (m.modCount != expectedModCount)
1595		throw new ConcurrentModificationException();
1596		next = successor(e);
1597	+	lastReturned = e;
1598		return e;
1599		}
1600
1601		final TreeMap.Entry<K,V> prevEntry() {
1602	<	TreeMap.Entry<K,V> e = lastReturned = next;
1602	>	TreeMap.Entry<K,V> e = next;
1603		if (e == null || e.key == fenceKey)
1604		throw new NoSuchElementException();
1605		if (m.modCount != expectedModCount)
1606		throw new ConcurrentModificationException();
1607		next = predecessor(e);
1608	+	lastReturned = e;
1609		return e;
1610		}
1611
#	Line 1689 | Line 1716 | public class TreeMap<K,V>
1716		}
1717
1718		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1719	<	if (!inClosedRange(toKey))
1719	>	if (!inRange(toKey, inclusive))
1720		throw new IllegalArgumentException("toKey out of range");
1721		return new AscendingSubMap(m,
1722		fromStart, lo,    loInclusive,
#	Line 1831 | Line 1858 | public class TreeMap<K,V>
1858		* @serial include
1859		*/
1860		private class SubMap extends AbstractMap<K,V>
1861	<	implements SortedMap<K,V>, java.io.Serializable {
1861	>	implements SortedMap<K,V>, java.io.Serializable {
1862		private static final long serialVersionUID = -6520786458950516097L;
1863		private boolean fromStart = false, toEnd = false;
1864		private K fromKey, toKey;
#	Line 1861 | Line 1888 | public class TreeMap<K,V>
1888		*/
1889
1890		static final class Entry<K,V> implements Map.Entry<K,V> {
1891	<	K key;
1891	>	K key;
1892		V value;
1893		Entry<K,V> left = null;
1894		Entry<K,V> right = null;
#	Line 2016 | Line 2043 | public class TreeMap<K,V>
2043
2044		private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2045		if (p != null)
2046	<	p.color = c;
2046	>	p.color = c;
2047		}
2048
2049		private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
#	Line 2115 | Line 2142 | public class TreeMap<K,V>
2142		// If strictly internal, copy successor's element to p and then make p
2143		// point to successor.
2144		if (p.left != null && p.right != null) {
2145	<	Entry<K,V> s = successor (p);
2145	>	Entry<K,V> s = successor(p);
2146		p.key = s.key;
2147		p.value = s.value;
2148		p = s;
#	Line 2272 | Line 2299 | public class TreeMap<K,V>
2299
2300		/** Intended to be called only from TreeSet.addAll */
2301		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2302	<	try {
2303	<	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304	<	} catch (java.io.IOException cannotHappen) {
2305	<	} catch (ClassNotFoundException cannotHappen) {
2306	<	}
2302	>	try {
2303	>	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304	>	} catch (java.io.IOException cannotHappen) {
2305	>	} catch (ClassNotFoundException cannotHappen) {
2306	>	}
2307		}
2308
2309
#	Line 2311 | Line 2338 | public class TreeMap<K,V>
2338		*         This cannot occur if str is null.
2339		*/
2340		private void buildFromSorted(int size, Iterator it,
2341	<	java.io.ObjectInputStream str,
2342	<	V defaultVal)
2341	>	java.io.ObjectInputStream str,
2342	>	V defaultVal)
2343		throws  java.io.IOException, ClassNotFoundException {
2344		this.size = size;
2345		root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2346	<	it, str, defaultVal);
2346	>	it, str, defaultVal);
2347		}
2348
2349		/**
#	Line 2334 | Line 2361 | public class TreeMap<K,V>
2361		*        Must be equal to computeRedLevel for tree of this size.
2362		*/
2363		private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2364	<	int redLevel,
2365	<	Iterator it,
2366	<	java.io.ObjectInputStream str,
2367	<	V defaultVal)
2364	>	int redLevel,
2365	>	Iterator it,
2366	>	java.io.ObjectInputStream str,
2367	>	V defaultVal)
2368		throws  java.io.IOException, ClassNotFoundException {
2369		/*
2370		* Strategy: The root is the middlemost element. To get to it, we
#	Line 2353 | Line 2380 | public class TreeMap<K,V>
2380
2381		if (hi < lo) return null;
2382
2383	<	int mid = (lo + hi) / 2;
2383	>	int mid = (lo + hi) >>> 1;
2384
2385		Entry<K,V> left  = null;
2386		if (lo < mid)
2387		left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2388	<	it, str, defaultVal);
2388	>	it, str, defaultVal);
2389
2390		// extract key and/or value from iterator or stream
2391		K key;
#	Line 2390 | Line 2417 | public class TreeMap<K,V>
2417
2418		if (mid < hi) {
2419		Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2420	<	it, str, defaultVal);
2420	>	it, str, defaultVal);
2421		middle.right = right;
2422		right.parent = middle;
2423		}

Diff Legend

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