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.52 by jsr166, Sat Oct 16 16:44:39 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 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
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 109 | Line 126 | public class TreeMap<K,V>
126		*/
127		private transient int modCount = 0;
128
112	–	private void incrementSize()   { modCount++; size++; }
113	–	private void decrementSize()   { modCount++; size--; }
114	–
129		/**
130		* Constructs a new, empty tree map, using the natural ordering of its
131		* keys.  All keys inserted into the map must implement the {@link
#	Line 222 | 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) {
243	<	return (root==null ? false :
244	<	(value==null ? valueSearchNull(root)
245	<	: valueSearchNonNull(root, value)));
246	<	}
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));
243	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
244	>	if (valEquals(value, e.value))
245	>	return true;
246	>	return false;
247		}
248
249		/**
#	Line 312 | 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 343 | 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 361 | Line 357 | public class TreeMap<K,V>
357		* Version of getEntry using comparator. Split off from getEntry
358		* for performance. (This is not worth doing for most methods,
359		* that are less dependent on comparator performance, but is
360	<	* worthwhile for get and put.)
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	<	Entry<K,V> p = root;
366	<	while (p != null) {
367	<	int cmp = cpr.compare(k, p.key);
368	<	if (cmp < 0)
369	<	p = p.left;
370	<	else if (cmp > 0)
371	<	p = p.right;
372	<	else
373	<	return p;
365	>	if (cpr != null) {
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;
375	>	}
376		}
377		return null;
378		}
#	Line 509 | Line 507 | public class TreeMap<K,V>
507		}
508
509		/**
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	–	/**
510		* Associates the specified value with the specified key in this map.
511		* If the map previously contained a mapping for the key, the old
512		* value is replaced.
#	Line 537 | Line 525 | public class TreeMap<K,V>
525		*         does not permit null keys
526		*/
527		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	–
528		Entry<K,V> t = root;
529	<	while (t != null) {
530	<	int cmp = k.compareTo(t.key);
531	<	if (cmp == 0) {
532	<	return t.setValue(value);
533	<	} else if (cmp < 0) {
534	<	if (t.left != null) {
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
535	>	root = new Entry<K,V>(key, value, null);
536	>	size = 1;
537	>	modCount++;
538	>	return null;
539	>	}
540	>	int cmp;
541	>	Entry<K,V> parent;
542	>	// split comparator and comparable paths
543	>	Comparator<? super K> cpr = comparator;
544	>	if (cpr != null) {
545	>	do {
546	>	parent = t;
547	>	cmp = cpr.compare(key, t.key);
548	>	if (cmp < 0)
549		t = t.left;
550	<	} 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) {
550	>	else if (cmp > 0)
551		t = t.right;
552	<	} else {
553	<	incrementSize();
554	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	<	return null;
567	<	}
568	<	}
552	>	else
553	>	return t.setValue(value);
554	>	} while (t != null);
555		}
556	<	incrementSize();
557	<	root = new Entry<K,V>(key, value, null);
558	<	return null;
559	<	}
560	<
561	<	/**
562	<	* Version of put using comparator. Split off from put for
563	<	* 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) {
556	>	else {
557	>	if (key == null)
558	>	throw new NullPointerException();
559	>	Comparable<? super K> k = (Comparable<? super K>) key;
560	>	do {
561	>	parent = t;
562	>	cmp = k.compareTo(t.key);
563	>	if (cmp < 0)
564		t = t.left;
565	<	} 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) {
565	>	else if (cmp > 0)
566		t = t.right;
567	<	} else {
568	<	incrementSize();
569	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600	<	return null;
601	<	}
602	<	}
567	>	else
568	>	return t.setValue(value);
569	>	} while (t != null);
570		}
571	<	cpr.compare(key, key); // type check
572	<	incrementSize();
573	<	root = new Entry<K,V>(key, value, null);
571	>	Entry<K,V> e = new Entry<K,V>(key, value, parent);
572	>	if (cmp < 0)
573	>	parent.left = e;
574	>	else
575	>	parent.right = e;
576	>	fixAfterInsertion(e);
577	>	size++;
578	>	modCount++;
579		return null;
580		}
581
#	Line 679 | Line 651 | public class TreeMap<K,V>
651		* @since 1.6
652		*/
653		public Map.Entry<K,V> firstEntry() {
654	<	Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
654	>	return exportEntry(getFirstEntry());
655		}
656
657		/**
658		* @since 1.6
659		*/
660		public Map.Entry<K,V> lastEntry() {
661	<	Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
661	>	return exportEntry(getLastEntry());
662		}
663
664		/**
#	Line 696 | Line 666 | public class TreeMap<K,V>
666		*/
667		public Map.Entry<K,V> pollFirstEntry() {
668		Entry<K,V> p = getFirstEntry();
669	<	if (p == null)
670	<	return null;
671	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702	<	deleteEntry(p);
669	>	Map.Entry<K,V> result = exportEntry(p);
670	>	if (p != null)
671	>	deleteEntry(p);
672		return result;
673		}
674
#	Line 708 | Line 677 | public class TreeMap<K,V>
677		*/
678		public Map.Entry<K,V> pollLastEntry() {
679		Entry<K,V> p = getLastEntry();
680	<	if (p == null)
681	<	return null;
682	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714	<	deleteEntry(p);
680	>	Map.Entry<K,V> result = exportEntry(p);
681	>	if (p != null)
682	>	deleteEntry(p);
683		return result;
684		}
685
#	Line 723 | Line 691 | public class TreeMap<K,V>
691		* @since 1.6
692		*/
693		public Map.Entry<K,V> lowerEntry(K key) {
694	<	Entry<K,V> e =  getLowerEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
694	>	return exportEntry(getLowerEntry(key));
695		}
696
697		/**
#	Line 735 | Line 702 | public class TreeMap<K,V>
702		* @since 1.6
703		*/
704		public K lowerKey(K key) {
705	<	Entry<K,V> e =  getLowerEntry(key);
739	<	return (e == null)? null : e.key;
705	>	return keyOrNull(getLowerEntry(key));
706		}
707
708		/**
#	Line 747 | Line 713 | public class TreeMap<K,V>
713		* @since 1.6
714		*/
715		public Map.Entry<K,V> floorEntry(K key) {
716	<	Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
716	>	return exportEntry(getFloorEntry(key));
717		}
718
719		/**
#	Line 759 | Line 724 | public class TreeMap<K,V>
724		* @since 1.6
725		*/
726		public K floorKey(K key) {
727	<	Entry<K,V> e = getFloorEntry(key);
763	<	return (e == null)? null : e.key;
727	>	return keyOrNull(getFloorEntry(key));
728		}
729
730		/**
#	Line 771 | Line 735 | public class TreeMap<K,V>
735		* @since 1.6
736		*/
737		public Map.Entry<K,V> ceilingEntry(K key) {
738	<	Entry<K,V> e = getCeilingEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
738	>	return exportEntry(getCeilingEntry(key));
739		}
740
741		/**
#	Line 783 | Line 746 | public class TreeMap<K,V>
746		* @since 1.6
747		*/
748		public K ceilingKey(K key) {
749	<	Entry<K,V> e = getCeilingEntry(key);
787	<	return (e == null)? null : e.key;
749	>	return keyOrNull(getCeilingEntry(key));
750		}
751
752		/**
#	Line 795 | Line 757 | public class TreeMap<K,V>
757		* @since 1.6
758		*/
759		public Map.Entry<K,V> higherEntry(K key) {
760	<	Entry<K,V> e = getHigherEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
760	>	return exportEntry(getHigherEntry(key));
761		}
762
763		/**
#	Line 807 | Line 768 | public class TreeMap<K,V>
768		* @since 1.6
769		*/
770		public K higherKey(K key) {
771	<	Entry<K,V> e = getHigherEntry(key);
811	<	return (e == null)? null : e.key;
771	>	return keyOrNull(getHigherEntry(key));
772		}
773
774		// Views
#	Line 994 | Line 954 | public class TreeMap<K,V>
954		}
955
956		public boolean contains(Object o) {
957	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
998	<	if (valEquals(e.getValue(), o))
999	<	return true;
1000	<	return false;
957	>	return TreeMap.this.containsValue(o);
958		}
959
960		public boolean remove(Object o) {
#	Line 1064 | 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 1110 | Line 1067 | public class TreeMap<K,V>
1067		return size() != oldSize;
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));
1070	>	E toElement,   boolean 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 1130 | 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 1152 | 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 1177 | Line 1136 | public class TreeMap<K,V>
1136		throw new IllegalStateException();
1137		if (modCount != expectedModCount)
1138		throw new ConcurrentModificationException();
1139	+	// deleted entries are replaced by their successors
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 1221 | Line 1181 | public class TreeMap<K,V>
1181		}
1182		}
1183
1184	+	// Little utilities
1185	+
1186	+	/**
1187	+	* Compares two keys using the correct comparison method for this TreeMap.
1188	+	*/
1189	+	final int compare(Object k1, Object k2) {
1190	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1191	+	: comparator.compare((K)k1, (K)k2);
1192	+	}
1193	+
1194	+	/**
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	+	static final boolean valEquals(Object o1, Object o2) {
1199	+	return (o1==null ? o2==null : o1.equals(o2));
1200	+	}
1201	+
1202	+	/**
1203	+	* Return SimpleImmutableEntry for entry, or null if null
1204	+	*/
1205	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1206	+	return e == null? null :
1207	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1208	+	}
1209	+
1210	+	/**
1211	+	* Return key for entry, or null if null
1212	+	*/
1213	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1214	+	return e == null? null : e.key;
1215	+	}
1216	+
1217	+	/**
1218	+	* Returns the key corresponding to the specified Entry.
1219	+	* @throws NoSuchElementException if the Entry is null
1220	+	*/
1221	+	static <K> K key(Entry<K,?> e) {
1222	+	if (e==null)
1223	+	throw new NoSuchElementException();
1224	+	return e.key;
1225	+	}
1226	+
1227	+
1228		// SubMaps
1229
1230	<	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
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	>	abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1240		implements NavigableMap<K,V>, java.io.Serializable {
1241	<	/*
1241	>	/**
1242		* The backing map.
1243		*/
1244		final TreeMap<K,V> m;
1245
1246	<	/*
1246	>	/**
1247		* Endpoints are represented as triples (fromStart, lo,
1248		* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1249		* true, then the low (absolute) bound is the start of the
#	Line 1238 | Line 1251 | public class TreeMap<K,V>
1251		* if loInclusive is true, lo is the inclusive bound, else lo
1252		* is the exclusive bound. Similarly for the upper bound.
1253		*/
1241	–
1254		final K lo, hi;
1255		final boolean fromStart, toEnd;
1256		final boolean loInclusive, hiInclusive;
#	Line 1298 | Line 1310 | public class TreeMap<K,V>
1310		return inclusive ? inRange(key) : inClosedRange(key);
1311		}
1312
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	–
1313		/*
1314		* Absolute versions of relation operations.
1315		* Subclasses map to these using like-named "sub"
#	Line 1320 | 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 1328 | 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)));
1332		return (e == null || tooLow(e.key)) ? null : e;
1333		}
1334	<
1334	>
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
1363		/** Returns the absolute high fence for ascending traversal */
1364		final TreeMap.Entry<K,V> absHighFence() {
1365	<	return (toEnd ? null : (hiInclusive ?
1365	>	return (toEnd ? null : (hiInclusive ?
1366		m.getHigherEntry(hi) :
1367		m.getCeilingEntry(hi)));
1368		}
#	Line 1378 | Line 1375 | public class TreeMap<K,V>
1375		}
1376
1377		// Abstract methods defined in ascending vs descending classes
1378	<	// These relay to the appropriate  absolute versions
1378	>	// These relay to the appropriate absolute versions
1379
1380		abstract TreeMap.Entry<K,V> subLowest();
1381		abstract TreeMap.Entry<K,V> subHighest();
#	Line 1426 | Line 1423 | public class TreeMap<K,V>
1423		}
1424
1425		public final K ceilingKey(K key) {
1426	<	return exportKey(subCeiling(key));
1426	>	return keyOrNull(subCeiling(key));
1427		}
1428
1429		public final Map.Entry<K,V> higherEntry(K key) {
#	Line 1434 | Line 1431 | public class TreeMap<K,V>
1431		}
1432
1433		public final K higherKey(K key) {
1434	<	return exportKey(subHigher(key));
1434	>	return keyOrNull(subHigher(key));
1435		}
1436
1437		public final Map.Entry<K,V> floorEntry(K key) {
#	Line 1442 | Line 1439 | public class TreeMap<K,V>
1439		}
1440
1441		public final K floorKey(K key) {
1442	<	return exportKey(subFloor(key));
1442	>	return keyOrNull(subFloor(key));
1443		}
1444
1445		public final Map.Entry<K,V> lowerEntry(K key) {
#	Line 1450 | Line 1447 | public class TreeMap<K,V>
1447		}
1448
1449		public final K lowerKey(K key) {
1450	<	return exportKey(subLower(key));
1450	>	return keyOrNull(subLower(key));
1451		}
1452
1453		public final K firstKey() {
#	Line 1470 | 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 1478 | 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 1561 | Line 1558 | public class TreeMap<K,V>
1558		if (!inRange(key))
1559		return false;
1560		TreeMap.Entry<K,V> node = m.getEntry(key);
1561	<	if (node!=null && valEquals(node.getValue(),entry.getValue())){
1561	>	if (node!=null && valEquals(node.getValue(),
1562	>	entry.getValue())) {
1563		m.deleteEntry(node);
1564		return true;
1565		}
#	Line 1575 | 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 1583 | 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 1591 | 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);
1621	–	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 1631 | 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 1641 | 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 1652 | 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 1662 | 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 1679 | 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 1690 | 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,
1724		false,     toKey, inclusive);
1725		}
1726
1727	<	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1727	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1728		if (!inRange(fromKey, inclusive))
1729		throw new IllegalArgumentException("fromKey out of range");
1730		return new AscendingSubMap(m,
#	Line 1741 | 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 1757 | 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 1775 | Line 1805 | public class TreeMap<K,V>
1805		toEnd, hi,    hiInclusive);
1806		}
1807
1808	<	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1808	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1809		if (!inRange(fromKey, inclusive))
1810		throw new IllegalArgumentException("fromKey out of range");
1811		return new DescendingSubMap(m,
#	Line 1820 | Line 1850 | public class TreeMap<K,V>
1850		}
1851
1852		/**
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	–	/**
1853		* This class exists solely for the sake of serialization
1854		* compatibility with previous releases of TreeMap that did not
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 {
1862	>	implements SortedMap<K,V>, java.io.Serializable {
1863		private static final long serialVersionUID = -6520786458950516097L;
1864		private boolean fromStart = false, toEnd = false;
1865		private K fromKey, toKey;
#	Line 1862 | Line 1878 | public class TreeMap<K,V>
1878		}
1879
1880
1881	+	// Red-black mechanics
1882	+
1883		private static final boolean RED   = false;
1884		private static final boolean BLACK = true;
1885
#	Line 1871 | Line 1889 | public class TreeMap<K,V>
1889		*/
1890
1891		static final class Entry<K,V> implements Map.Entry<K,V> {
1892	<	K key;
1892	>	K key;
1893		V value;
1894		Entry<K,V> left = null;
1895		Entry<K,V> right = null;
#	Line 1922 | 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 2026 | Line 2044 | public class TreeMap<K,V>
2044
2045		private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2046		if (p != null)
2047	<	p.color = c;
2047	>	p.color = c;
2048		}
2049
2050		private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
#	Line 2037 | Line 2055 | public class TreeMap<K,V>
2055		return (p == null) ? null: p.right;
2056		}
2057
2058	<	/** From CLR **/
2058	>	/** From CLR */
2059		private void rotateLeft(Entry<K,V> p) {
2060	<	Entry<K,V> r = p.right;
2061	<	p.right = r.left;
2062	<	if (r.left != null)
2063	<	r.left.parent = p;
2064	<	r.parent = p.parent;
2065	<	if (p.parent == null)
2066	<	root = r;
2067	<	else if (p.parent.left == p)
2068	<	p.parent.left = r;
2069	<	else
2070	<	p.parent.right = r;
2071	<	r.left = p;
2072	<	p.parent = r;
2060	>	if (p != null) {
2061	>	Entry<K,V> r = p.right;
2062	>	p.right = r.left;
2063	>	if (r.left != null)
2064	>	r.left.parent = p;
2065	>	r.parent = p.parent;
2066	>	if (p.parent == null)
2067	>	root = r;
2068	>	else if (p.parent.left == p)
2069	>	p.parent.left = r;
2070	>	else
2071	>	p.parent.right = r;
2072	>	r.left = p;
2073	>	p.parent = r;
2074	>	}
2075		}
2076
2077	<	/** From CLR **/
2077	>	/** From CLR */
2078		private void rotateRight(Entry<K,V> p) {
2079	<	Entry<K,V> l = p.left;
2080	<	p.left = l.right;
2081	<	if (l.right != null) l.right.parent = p;
2082	<	l.parent = p.parent;
2083	<	if (p.parent == null)
2084	<	root = l;
2085	<	else if (p.parent.right == p)
2086	<	p.parent.right = l;
2087	<	else p.parent.left = l;
2088	<	l.right = p;
2089	<	p.parent = l;
2079	>	if (p != null) {
2080	>	Entry<K,V> l = p.left;
2081	>	p.left = l.right;
2082	>	if (l.right != null) l.right.parent = p;
2083	>	l.parent = p.parent;
2084	>	if (p.parent == null)
2085	>	root = l;
2086	>	else if (p.parent.right == p)
2087	>	p.parent.right = l;
2088	>	else p.parent.left = l;
2089	>	l.right = p;
2090	>	p.parent = l;
2091	>	}
2092		}
2093
2094	<
2073	<	/** From CLR **/
2094	>	/** From CLR */
2095		private void fixAfterInsertion(Entry<K,V> x) {
2096		x.color = RED;
2097
#	Line 2089 | Line 2110 | public class TreeMap<K,V>
2110		}
2111		setColor(parentOf(x), BLACK);
2112		setColor(parentOf(parentOf(x)), RED);
2113	<	if (parentOf(parentOf(x)) != null)
2093	<	rotateRight(parentOf(parentOf(x)));
2113	>	rotateRight(parentOf(parentOf(x)));
2114		}
2115		} else {
2116		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2106 | Line 2126 | public class TreeMap<K,V>
2126		}
2127		setColor(parentOf(x), BLACK);
2128		setColor(parentOf(parentOf(x)), RED);
2129	<	if (parentOf(parentOf(x)) != null)
2110	<	rotateLeft(parentOf(parentOf(x)));
2129	>	rotateLeft(parentOf(parentOf(x)));
2130		}
2131		}
2132		}
#	Line 2117 | Line 2136 | public class TreeMap<K,V>
2136		/**
2137		* Delete node p, and then rebalance the tree.
2138		*/
2120	–
2139		private void deleteEntry(Entry<K,V> p) {
2140	<	decrementSize();
2140	>	modCount++;
2141	>	size--;
2142
2143		// If strictly internal, copy successor's element to p and then make p
2144		// point to successor.
2145		if (p.left != null && p.right != null) {
2146	<	Entry<K,V> s = successor (p);
2146	>	Entry<K,V> s = successor(p);
2147		p.key = s.key;
2148		p.value = s.value;
2149		p = s;
#	Line 2165 | Line 2184 | public class TreeMap<K,V>
2184		}
2185		}
2186
2187	<	/** From CLR **/
2187	>	/** From CLR */
2188		private void fixAfterDeletion(Entry<K,V> x) {
2189		while (x != root && colorOf(x) == BLACK) {
2190		if (x == leftOf(parentOf(x))) {
#	Line 2273 | Line 2292 | public class TreeMap<K,V>
2292		buildFromSorted(size, null, s, null);
2293		}
2294
2295	<	/** Intended to be called only from TreeSet.readObject **/
2295	>	/** Intended to be called only from TreeSet.readObject */
2296		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2297		throws java.io.IOException, ClassNotFoundException {
2298		buildFromSorted(size, null, s, defaultVal);
2299		}
2300
2301	<	/** Intended to be called only from TreeSet.addAll **/
2301	>	/** Intended to be called only from TreeSet.addAll */
2302		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2303	<	try {
2304	<	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2305	<	} catch (java.io.IOException cannotHappen) {
2306	<	} catch (ClassNotFoundException cannotHappen) {
2307	<	}
2303	>	try {
2304	>	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2305	>	} catch (java.io.IOException cannotHappen) {
2306	>	} catch (ClassNotFoundException cannotHappen) {
2307	>	}
2308		}
2309
2310
#	Line 2320 | Line 2339 | public class TreeMap<K,V>
2339		*         This cannot occur if str is null.
2340		*/
2341		private void buildFromSorted(int size, Iterator it,
2342	<	java.io.ObjectInputStream str,
2343	<	V defaultVal)
2342	>	java.io.ObjectInputStream str,
2343	>	V defaultVal)
2344		throws  java.io.IOException, ClassNotFoundException {
2345		this.size = size;
2346		root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2347	<	it, str, defaultVal);
2347	>	it, str, defaultVal);
2348		}
2349
2350		/**
#	Line 2343 | Line 2362 | public class TreeMap<K,V>
2362		*        Must be equal to computeRedLevel for tree of this size.
2363		*/
2364		private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2365	<	int redLevel,
2366	<	Iterator it,
2367	<	java.io.ObjectInputStream str,
2368	<	V defaultVal)
2365	>	int redLevel,
2366	>	Iterator it,
2367	>	java.io.ObjectInputStream str,
2368	>	V defaultVal)
2369		throws  java.io.IOException, ClassNotFoundException {
2370		/*
2371		* Strategy: The root is the middlemost element. To get to it, we
#	Line 2362 | 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)
2388		left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2389	<	it, str, defaultVal);
2389	>	it, str, defaultVal);
2390
2391		// extract key and/or value from iterator or stream
2392		K key;
#	Line 2399 | Line 2418 | public class TreeMap<K,V>
2418
2419		if (mid < hi) {
2420		Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2421	<	it, str, defaultVal);
2421	>	it, str, defaultVal);
2422		middle.right = right;
2423		right.parent = middle;
2424		}

Diff Legend

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