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.32 by dl, Sat Apr 22 16:38:01 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 109 | Line 127 | public class TreeMap<K,V>
127		*/
128		private transient int modCount = 0;
129
112	–	private void incrementSize()   { modCount++; size++; }
113	–	private void decrementSize()   { modCount++; size--; }
114	–
130		/**
131		* Constructs a new, empty tree map, using the natural ordering of its
132		* keys.  All keys inserted into the map must implement the {@link
#	Line 226 | Line 241 | public class TreeMap<K,V>
241		* @since 1.2
242		*/
243		public boolean containsValue(Object value) {
244	<	return (root==null ? false :
245	<	(value==null ? valueSearchNull(root)
246	<	: valueSearchNonNull(root, value)));
247	<	}
233	<
234	<	private boolean valueSearchNull(Entry n) {
235	<	if (n.value == null)
236	<	return true;
237	<
238	<	// Check left and right subtrees for value
239	<	return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
241	<	}
242	<
243	<	private boolean valueSearchNonNull(Entry n, Object value) {
244	<	// Check this node for the value
245	<	if (value.equals(n.value))
246	<	return true;
247	<
248	<	// Check left and right subtrees for value
249	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
250	<	(n.right != null && valueSearchNonNull(n.right, value));
244	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
245	>	if (valEquals(value, e.value))
246	>	return true;
247	>	return false;
248		}
249
250		/**
#	Line 361 | Line 358 | public class TreeMap<K,V>
358		* Version of getEntry using comparator. Split off from getEntry
359		* for performance. (This is not worth doing for most methods,
360		* that are less dependent on comparator performance, but is
361	<	* worthwhile for get and put.)
361	>	* worthwhile here.)
362		*/
363		final Entry<K,V> getEntryUsingComparator(Object key) {
364		K k = (K) key;
365		Comparator<? super K> cpr = comparator;
366	<	Entry<K,V> p = root;
367	<	while (p != null) {
368	<	int cmp = cpr.compare(k, p.key);
369	<	if (cmp < 0)
370	<	p = p.left;
371	<	else if (cmp > 0)
372	<	p = p.right;
373	<	else
374	<	return p;
366	>	if (cpr != null) {
367	>	Entry<K,V> p = root;
368	>	while (p != null) {
369	>	int cmp = cpr.compare(k, p.key);
370	>	if (cmp < 0)
371	>	p = p.left;
372	>	else if (cmp > 0)
373	>	p = p.right;
374	>	else
375	>	return p;
376	>	}
377		}
378		return null;
379		}
#	Line 509 | Line 508 | public class TreeMap<K,V>
508		}
509
510		/**
512	–	* Returns the key corresponding to the specified Entry.
513	–	* @throws NoSuchElementException if the Entry is null
514	–	*/
515	–	static <K> K key(Entry<K,?> e) {
516	–	if (e==null)
517	–	throw new NoSuchElementException();
518	–	return e.key;
519	–	}
520	–
521	–	/**
511		* Associates the specified value with the specified key in this map.
512		* If the map previously contained a mapping for the key, the old
513		* value is replaced.
#	Line 537 | Line 526 | public class TreeMap<K,V>
526		*         does not permit null keys
527		*/
528		public V put(K key, V value) {
540	–	// Offload comparator-based version for sake of performance
541	–	if (comparator != null)
542	–	return putUsingComparator(key, value);
543	–	if (key == null)
544	–	throw new NullPointerException();
545	–	Comparable<? super K> k = (Comparable<? super K>) key;
546	–
529		Entry<K,V> t = root;
530	<	while (t != null) {
531	<	int cmp = k.compareTo(t.key);
532	<	if (cmp == 0) {
533	<	return t.setValue(value);
534	<	} else if (cmp < 0) {
535	<	if (t.left != null) {
530	>	if (t == null) {
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++;
539	>	return null;
540	>	}
541	>	int cmp;
542	>	Entry<K,V> parent;
543	>	// split comparator and comparable paths
544	>	Comparator<? super K> cpr = comparator;
545	>	if (cpr != null) {
546	>	do {
547	>	parent = t;
548	>	cmp = cpr.compare(key, t.key);
549	>	if (cmp < 0)
550		t = t.left;
551	<	} else {
556	<	incrementSize();
557	<	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
558	<	return null;
559	<	}
560	<	} else { // cmp > 0
561	<	if (t.right != null) {
551	>	else if (cmp > 0)
552		t = t.right;
553	<	} else {
554	<	incrementSize();
555	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	<	return null;
567	<	}
568	<	}
553	>	else
554	>	return t.setValue(value);
555	>	} while (t != null);
556		}
557	<	incrementSize();
558	<	root = new Entry<K,V>(key, value, null);
559	<	return null;
560	<	}
561	<
562	<	/**
563	<	* Version of put using comparator. Split off from put for
564	<	* performance.
578	<	*/
579	<	final V putUsingComparator(K key, V value) {
580	<	Comparator<? super K> cpr = comparator;
581	<	Entry<K,V> t = root;
582	<	while (t != null) {
583	<	int cmp = cpr.compare(key, t.key);
584	<	if (cmp == 0) {
585	<	return t.setValue(value);
586	<	} else if (cmp < 0) {
587	<	if (t.left != null) {
557	>	else {
558	>	if (key == null)
559	>	throw new NullPointerException();
560	>	Comparable<? super K> k = (Comparable<? super K>) key;
561	>	do {
562	>	parent = t;
563	>	cmp = k.compareTo(t.key);
564	>	if (cmp < 0)
565		t = t.left;
566	<	} else {
590	<	incrementSize();
591	<	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592	<	return null;
593	<	}
594	<	} else { // cmp > 0
595	<	if (t.right != null) {
566	>	else if (cmp > 0)
567		t = t.right;
568	<	} else {
569	<	incrementSize();
570	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600	<	return null;
601	<	}
602	<	}
568	>	else
569	>	return t.setValue(value);
570	>	} while (t != null);
571		}
572	<	cpr.compare(key, key); // type check
573	<	incrementSize();
574	<	root = new Entry<K,V>(key, value, null);
572	>	Entry<K,V> e = new Entry<K,V>(key, value, parent);
573	>	if (cmp < 0)
574	>	parent.left = e;
575	>	else
576	>	parent.right = e;
577	>	fixAfterInsertion(e);
578	>	size++;
579	>	modCount++;
580		return null;
581		}
582
#	Line 679 | Line 652 | public class TreeMap<K,V>
652		* @since 1.6
653		*/
654		public Map.Entry<K,V> firstEntry() {
655	<	Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
655	>	return exportEntry(getFirstEntry());
656		}
657
658		/**
659		* @since 1.6
660		*/
661		public Map.Entry<K,V> lastEntry() {
662	<	Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
662	>	return exportEntry(getLastEntry());
663		}
664
665		/**
#	Line 696 | Line 667 | public class TreeMap<K,V>
667		*/
668		public Map.Entry<K,V> pollFirstEntry() {
669		Entry<K,V> p = getFirstEntry();
670	<	if (p == null)
671	<	return null;
672	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702	<	deleteEntry(p);
670	>	Map.Entry<K,V> result = exportEntry(p);
671	>	if (p != null)
672	>	deleteEntry(p);
673		return result;
674		}
675
#	Line 708 | Line 678 | public class TreeMap<K,V>
678		*/
679		public Map.Entry<K,V> pollLastEntry() {
680		Entry<K,V> p = getLastEntry();
681	<	if (p == null)
682	<	return null;
683	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714	<	deleteEntry(p);
681	>	Map.Entry<K,V> result = exportEntry(p);
682	>	if (p != null)
683	>	deleteEntry(p);
684		return result;
685		}
686
#	Line 723 | Line 692 | public class TreeMap<K,V>
692		* @since 1.6
693		*/
694		public Map.Entry<K,V> lowerEntry(K key) {
695	<	Entry<K,V> e =  getLowerEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
695	>	return exportEntry(getLowerEntry(key));
696		}
697
698		/**
#	Line 735 | Line 703 | public class TreeMap<K,V>
703		* @since 1.6
704		*/
705		public K lowerKey(K key) {
706	<	Entry<K,V> e =  getLowerEntry(key);
739	<	return (e == null)? null : e.key;
706	>	return keyOrNull(getLowerEntry(key));
707		}
708
709		/**
#	Line 747 | Line 714 | public class TreeMap<K,V>
714		* @since 1.6
715		*/
716		public Map.Entry<K,V> floorEntry(K key) {
717	<	Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
717	>	return exportEntry(getFloorEntry(key));
718		}
719
720		/**
#	Line 759 | Line 725 | public class TreeMap<K,V>
725		* @since 1.6
726		*/
727		public K floorKey(K key) {
728	<	Entry<K,V> e = getFloorEntry(key);
763	<	return (e == null)? null : e.key;
728	>	return keyOrNull(getFloorEntry(key));
729		}
730
731		/**
#	Line 771 | Line 736 | public class TreeMap<K,V>
736		* @since 1.6
737		*/
738		public Map.Entry<K,V> ceilingEntry(K key) {
739	<	Entry<K,V> e = getCeilingEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
739	>	return exportEntry(getCeilingEntry(key));
740		}
741
742		/**
#	Line 783 | Line 747 | public class TreeMap<K,V>
747		* @since 1.6
748		*/
749		public K ceilingKey(K key) {
750	<	Entry<K,V> e = getCeilingEntry(key);
787	<	return (e == null)? null : e.key;
750	>	return keyOrNull(getCeilingEntry(key));
751		}
752
753		/**
#	Line 795 | Line 758 | public class TreeMap<K,V>
758		* @since 1.6
759		*/
760		public Map.Entry<K,V> higherEntry(K key) {
761	<	Entry<K,V> e = getHigherEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
761	>	return exportEntry(getHigherEntry(key));
762		}
763
764		/**
#	Line 807 | Line 769 | public class TreeMap<K,V>
769		* @since 1.6
770		*/
771		public K higherKey(K key) {
772	<	Entry<K,V> e = getHigherEntry(key);
811	<	return (e == null)? null : e.key;
772	>	return keyOrNull(getHigherEntry(key));
773		}
774
775		// Views
#	Line 994 | Line 955 | public class TreeMap<K,V>
955		}
956
957		public boolean contains(Object o) {
958	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
998	<	if (valEquals(e.getValue(), o))
999	<	return true;
1000	<	return false;
958	>	return TreeMap.this.containsValue(o);
959		}
960
961		public boolean remove(Object o) {
#	Line 1110 | 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 1177 | 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 1221 | Line 1180 | public class TreeMap<K,V>
1180		}
1181		}
1182
1183	+	// Little utilities
1184	+
1185	+	/**
1186	+	* Compares two keys using the correct comparison method for this TreeMap.
1187	+	*/
1188	+	final int compare(Object k1, Object k2) {
1189	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1190	+	: comparator.compare((K)k1, (K)k2);
1191	+	}
1192	+
1193	+	/**
1194	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1195	+	* that it copes with <tt>null</tt> o1 properly.
1196	+	*/
1197	+	final static boolean valEquals(Object o1, Object o2) {
1198	+	return (o1==null ? o2==null : o1.equals(o2));
1199	+	}
1200	+
1201	+	/**
1202	+	* Return SimpleImmutableEntry for entry, or null if null
1203	+	*/
1204	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1205	+	return e == null? null :
1206	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1207	+	}
1208	+
1209	+	/**
1210	+	* Return key for entry, or null if null
1211	+	*/
1212	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1213	+	return e == null? null : e.key;
1214	+	}
1215	+
1216	+	/**
1217	+	* Returns the key corresponding to the specified Entry.
1218	+	* @throws NoSuchElementException if the Entry is null
1219	+	*/
1220	+	static <K> K key(Entry<K,?> e) {
1221	+	if (e==null)
1222	+	throw new NoSuchElementException();
1223	+	return e.key;
1224	+	}
1225	+
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 1238 | 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		*/
1241	–
1253		final K lo, hi;
1254		final boolean fromStart, toEnd;
1255		final boolean loInclusive, hiInclusive;
#	Line 1298 | Line 1309 | public class TreeMap<K,V>
1309		return inclusive ? inRange(key) : inClosedRange(key);
1310		}
1311
1301	–	/**
1302	–	* Return SimpleImmutableEntry for entry, or null if null
1303	–	*/
1304	–	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1305	–	return e == null? null :
1306	–	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1307	–	}
1308	–
1309	–	/**
1310	–	* Return key for entry, or null if null
1311	–	*/
1312	–	static <K,V> K exportKey(TreeMap.Entry<K,V> e) {
1313	–	return e == null? null : e.key;
1314	–	}
1315	–
1312		/*
1313		* Absolute versions of relation operations.
1314		* Subclasses map to these using like-named "sub"
#	Line 1334 | Line 1330 | public class TreeMap<K,V>
1330		m.getLowerEntry(hi)));
1331		return (e == null || tooLow(e.key)) ? null : e;
1332		}
1333	<
1333	>
1334		final TreeMap.Entry<K,V> absCeiling(K key) {
1335		if (tooLow(key))
1336		return absLowest();
#	Line 1365 | Line 1361 | public class TreeMap<K,V>
1361
1362		/** Returns the absolute high fence for ascending traversal */
1363		final TreeMap.Entry<K,V> absHighFence() {
1364	<	return (toEnd ? null : (hiInclusive ?
1364	>	return (toEnd ? null : (hiInclusive ?
1365		m.getHigherEntry(hi) :
1366		m.getCeilingEntry(hi)));
1367		}
#	Line 1378 | 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 1426 | Line 1422 | public class TreeMap<K,V>
1422		}
1423
1424		public final K ceilingKey(K key) {
1425	<	return exportKey(subCeiling(key));
1425	>	return keyOrNull(subCeiling(key));
1426		}
1427
1428		public final Map.Entry<K,V> higherEntry(K key) {
#	Line 1434 | Line 1430 | public class TreeMap<K,V>
1430		}
1431
1432		public final K higherKey(K key) {
1433	<	return exportKey(subHigher(key));
1433	>	return keyOrNull(subHigher(key));
1434		}
1435
1436		public final Map.Entry<K,V> floorEntry(K key) {
#	Line 1442 | Line 1438 | public class TreeMap<K,V>
1438		}
1439
1440		public final K floorKey(K key) {
1441	<	return exportKey(subFloor(key));
1441	>	return keyOrNull(subFloor(key));
1442		}
1443
1444		public final Map.Entry<K,V> lowerEntry(K key) {
#	Line 1450 | Line 1446 | public class TreeMap<K,V>
1446		}
1447
1448		public final K lowerKey(K key) {
1449	<	return exportKey(subLower(key));
1449	>	return keyOrNull(subLower(key));
1450		}
1451
1452		public final K firstKey() {
#	Line 1575 | 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 1583 | 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 1610 | 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);
1621	–	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 1631 | 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 1641 | 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 1652 | 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 1662 | 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 1679 | 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 1690 | 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 1741 | 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 1757 | 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 1820 | Line 1846 | public class TreeMap<K,V>
1846		}
1847
1848		/**
1823	–	* Compares two keys using the correct comparison method for this TreeMap.
1824	–	*/
1825	–	final int compare(Object k1, Object k2) {
1826	–	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1827	–	: comparator.compare((K)k1, (K)k2);
1828	–	}
1829	–
1830	–	/**
1831	–	* Test two values for equality.  Differs from o1.equals(o2) only in
1832	–	* that it copes with <tt>null</tt> o1 properly.
1833	–	*/
1834	–	final static boolean valEquals(Object o1, Object o2) {
1835	–	return (o1==null ? o2==null : o1.equals(o2));
1836	–	}
1837	–
1838	–	/**
1849		* This class exists solely for the sake of serialization
1850		* compatibility with previous releases of TreeMap that did not
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 1862 | Line 1874 | public class TreeMap<K,V>
1874		}
1875
1876
1877	+	// Red-black mechanics
1878	+
1879		private static final boolean RED   = false;
1880		private static final boolean BLACK = true;
1881
#	Line 1922 | 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 2037 | Line 2051 | public class TreeMap<K,V>
2051		return (p == null) ? null: p.right;
2052		}
2053
2054	<	/** From CLR **/
2054	>	/** From CLR */
2055		private void rotateLeft(Entry<K,V> p) {
2056	<	Entry<K,V> r = p.right;
2057	<	p.right = r.left;
2058	<	if (r.left != null)
2059	<	r.left.parent = p;
2060	<	r.parent = p.parent;
2061	<	if (p.parent == null)
2062	<	root = r;
2063	<	else if (p.parent.left == p)
2064	<	p.parent.left = r;
2065	<	else
2066	<	p.parent.right = r;
2067	<	r.left = p;
2068	<	p.parent = r;
2056	>	if (p != null) {
2057	>	Entry<K,V> r = p.right;
2058	>	p.right = r.left;
2059	>	if (r.left != null)
2060	>	r.left.parent = p;
2061	>	r.parent = p.parent;
2062	>	if (p.parent == null)
2063	>	root = r;
2064	>	else if (p.parent.left == p)
2065	>	p.parent.left = r;
2066	>	else
2067	>	p.parent.right = r;
2068	>	r.left = p;
2069	>	p.parent = r;
2070	>	}
2071		}
2072
2073	<	/** From CLR **/
2073	>	/** From CLR */
2074		private void rotateRight(Entry<K,V> p) {
2075	<	Entry<K,V> l = p.left;
2076	<	p.left = l.right;
2077	<	if (l.right != null) l.right.parent = p;
2078	<	l.parent = p.parent;
2079	<	if (p.parent == null)
2080	<	root = l;
2081	<	else if (p.parent.right == p)
2082	<	p.parent.right = l;
2083	<	else p.parent.left = l;
2084	<	l.right = p;
2085	<	p.parent = l;
2075	>	if (p != null) {
2076	>	Entry<K,V> l = p.left;
2077	>	p.left = l.right;
2078	>	if (l.right != null) l.right.parent = p;
2079	>	l.parent = p.parent;
2080	>	if (p.parent == null)
2081	>	root = l;
2082	>	else if (p.parent.right == p)
2083	>	p.parent.right = l;
2084	>	else p.parent.left = l;
2085	>	l.right = p;
2086	>	p.parent = l;
2087	>	}
2088		}
2089
2090	<
2073	<	/** From CLR **/
2090	>	/** From CLR */
2091		private void fixAfterInsertion(Entry<K,V> x) {
2092		x.color = RED;
2093
#	Line 2089 | Line 2106 | public class TreeMap<K,V>
2106		}
2107		setColor(parentOf(x), BLACK);
2108		setColor(parentOf(parentOf(x)), RED);
2109	<	if (parentOf(parentOf(x)) != null)
2093	<	rotateRight(parentOf(parentOf(x)));
2109	>	rotateRight(parentOf(parentOf(x)));
2110		}
2111		} else {
2112		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2106 | Line 2122 | public class TreeMap<K,V>
2122		}
2123		setColor(parentOf(x), BLACK);
2124		setColor(parentOf(parentOf(x)), RED);
2125	<	if (parentOf(parentOf(x)) != null)
2110	<	rotateLeft(parentOf(parentOf(x)));
2125	>	rotateLeft(parentOf(parentOf(x)));
2126		}
2127		}
2128		}
#	Line 2117 | Line 2132 | public class TreeMap<K,V>
2132		/**
2133		* Delete node p, and then rebalance the tree.
2134		*/
2120	–
2135		private void deleteEntry(Entry<K,V> p) {
2136	<	decrementSize();
2136	>	modCount++;
2137	>	size--;
2138
2139		// If strictly internal, copy successor's element to p and then make p
2140		// point to successor.
#	Line 2165 | Line 2180 | public class TreeMap<K,V>
2180		}
2181		}
2182
2183	<	/** From CLR **/
2183	>	/** From CLR */
2184		private void fixAfterDeletion(Entry<K,V> x) {
2185		while (x != root && colorOf(x) == BLACK) {
2186		if (x == leftOf(parentOf(x))) {
#	Line 2273 | Line 2288 | public class TreeMap<K,V>
2288		buildFromSorted(size, null, s, null);
2289		}
2290
2291	<	/** Intended to be called only from TreeSet.readObject **/
2291	>	/** Intended to be called only from TreeSet.readObject */
2292		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2293		throws java.io.IOException, ClassNotFoundException {
2294		buildFromSorted(size, null, s, defaultVal);
2295		}
2296
2297	<	/** Intended to be called only from TreeSet.addAll **/
2297	>	/** Intended to be called only from TreeSet.addAll */
2298		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2299		try {
2300		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
#	Line 2362 | 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