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.34 by dl, Sun Apr 23 20:59:49 2006 UTC

#	Line 109 | Line 109 | public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
112	–	private void incrementSize()   { modCount++; size++; }
113	–	private void decrementSize()   { modCount++; size--; }
114	–
112		/**
113		* Constructs a new, empty tree map, using the natural ordering of its
114		* keys.  All keys inserted into the map must implement the {@link
#	Line 226 | Line 223 | public class TreeMap<K,V>
223		* @since 1.2
224		*/
225		public boolean containsValue(Object value) {
226	<	return (root==null ? false :
227	<	(value==null ? valueSearchNull(root)
228	<	: valueSearchNonNull(root, value)));
229	<	}
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));
226	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
227	>	if (valEquals(value, e.value))
228	>	return true;
229	>	return false;
230		}
231
232		/**
#	Line 361 | Line 340 | public class TreeMap<K,V>
340		* Version of getEntry using comparator. Split off from getEntry
341		* for performance. (This is not worth doing for most methods,
342		* that are less dependent on comparator performance, but is
343	<	* worthwhile for get and put.)
343	>	* worthwhile here.)
344		*/
345		final Entry<K,V> getEntryUsingComparator(Object key) {
346		K k = (K) key;
347		Comparator<? super K> cpr = comparator;
348	<	Entry<K,V> p = root;
349	<	while (p != null) {
350	<	int cmp = cpr.compare(k, p.key);
351	<	if (cmp < 0)
352	<	p = p.left;
353	<	else if (cmp > 0)
354	<	p = p.right;
355	<	else
356	<	return p;
348	>	if (cpr != null) {
349	>	Entry<K,V> p = root;
350	>	while (p != null) {
351	>	int cmp = cpr.compare(k, p.key);
352	>	if (cmp < 0)
353	>	p = p.left;
354	>	else if (cmp > 0)
355	>	p = p.right;
356	>	else
357	>	return p;
358	>	}
359		}
360		return null;
361		}
#	Line 509 | Line 490 | public class TreeMap<K,V>
490		}
491
492		/**
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	–	/**
493		* Associates the specified value with the specified key in this map.
494		* If the map previously contained a mapping for the key, the old
495		* value is replaced.
#	Line 537 | Line 508 | public class TreeMap<K,V>
508		*         does not permit null keys
509		*/
510		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	–
511		Entry<K,V> t = root;
512	<	while (t != null) {
513	<	int cmp = k.compareTo(t.key);
514	<	if (cmp == 0) {
515	<	return t.setValue(value);
516	<	} else if (cmp < 0) {
517	<	if (t.left != null) {
512	>	if (t == null) {
513	>	compare(key, key); // type check
514	>	root = new Entry<K,V>(key, value, null);
515	>	size = 1;
516	>	modCount++;
517	>	return null;
518	>	}
519	>	int cmp;
520	>	Entry<K,V> parent;
521	>	// split comparator and comparable paths
522	>	Comparator<? super K> cpr = comparator;
523	>	if (cpr != null) {
524	>	do {
525	>	parent = t;
526	>	cmp = cpr.compare(key, t.key);
527	>	if (cmp < 0)
528		t = t.left;
529	<	} 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) {
529	>	else if (cmp > 0)
530		t = t.right;
531	<	} else {
532	<	incrementSize();
533	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	<	return null;
567	<	}
568	<	}
531	>	else
532	>	return t.setValue(value);
533	>	} while (t != null);
534		}
535	<	incrementSize();
536	<	root = new Entry<K,V>(key, value, null);
537	<	return null;
538	<	}
539	<
540	<	/**
541	<	* Version of put using comparator. Split off from put for
542	<	* 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) {
535	>	else {
536	>	if (key == null)
537	>	throw new NullPointerException();
538	>	Comparable<? super K> k = (Comparable<? super K>) key;
539	>	do {
540	>	parent = t;
541	>	cmp = k.compareTo(t.key);
542	>	if (cmp < 0)
543		t = t.left;
544	<	} 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) {
544	>	else if (cmp > 0)
545		t = t.right;
546	<	} else {
547	<	incrementSize();
548	<	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600	<	return null;
601	<	}
602	<	}
546	>	else
547	>	return t.setValue(value);
548	>	} while (t != null);
549		}
550	<	cpr.compare(key, key); // type check
551	<	incrementSize();
552	<	root = new Entry<K,V>(key, value, null);
550	>	Entry<K,V> e = new Entry<K,V>(key, value, parent);
551	>	if (cmp < 0)
552	>	parent.left = e;
553	>	else
554	>	parent.right = e;
555	>	fixAfterInsertion(e);
556	>	size++;
557	>	modCount++;
558		return null;
559		}
560
#	Line 679 | Line 630 | public class TreeMap<K,V>
630		* @since 1.6
631		*/
632		public Map.Entry<K,V> firstEntry() {
633	<	Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
633	>	return exportEntry(getFirstEntry());
634		}
635
636		/**
637		* @since 1.6
638		*/
639		public Map.Entry<K,V> lastEntry() {
640	<	Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
640	>	return exportEntry(getLastEntry());
641		}
642
643		/**
#	Line 696 | Line 645 | public class TreeMap<K,V>
645		*/
646		public Map.Entry<K,V> pollFirstEntry() {
647		Entry<K,V> p = getFirstEntry();
648	<	if (p == null)
649	<	return null;
650	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702	<	deleteEntry(p);
648	>	Map.Entry<K,V> result = exportEntry(p);
649	>	if (p != null)
650	>	deleteEntry(p);
651		return result;
652		}
653
#	Line 708 | Line 656 | public class TreeMap<K,V>
656		*/
657		public Map.Entry<K,V> pollLastEntry() {
658		Entry<K,V> p = getLastEntry();
659	<	if (p == null)
660	<	return null;
661	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714	<	deleteEntry(p);
659	>	Map.Entry<K,V> result = exportEntry(p);
660	>	if (p != null)
661	>	deleteEntry(p);
662		return result;
663		}
664
#	Line 723 | Line 670 | public class TreeMap<K,V>
670		* @since 1.6
671		*/
672		public Map.Entry<K,V> lowerEntry(K key) {
673	<	Entry<K,V> e =  getLowerEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
673	>	return exportEntry(getLowerEntry(key));
674		}
675
676		/**
#	Line 735 | Line 681 | public class TreeMap<K,V>
681		* @since 1.6
682		*/
683		public K lowerKey(K key) {
684	<	Entry<K,V> e =  getLowerEntry(key);
739	<	return (e == null)? null : e.key;
684	>	return keyOrNull(getLowerEntry(key));
685		}
686
687		/**
#	Line 747 | Line 692 | public class TreeMap<K,V>
692		* @since 1.6
693		*/
694		public Map.Entry<K,V> floorEntry(K key) {
695	<	Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
695	>	return exportEntry(getFloorEntry(key));
696		}
697
698		/**
#	Line 759 | Line 703 | public class TreeMap<K,V>
703		* @since 1.6
704		*/
705		public K floorKey(K key) {
706	<	Entry<K,V> e = getFloorEntry(key);
763	<	return (e == null)? null : e.key;
706	>	return keyOrNull(getFloorEntry(key));
707		}
708
709		/**
#	Line 771 | Line 714 | public class TreeMap<K,V>
714		* @since 1.6
715		*/
716		public Map.Entry<K,V> ceilingEntry(K key) {
717	<	Entry<K,V> e = getCeilingEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
717	>	return exportEntry(getCeilingEntry(key));
718		}
719
720		/**
#	Line 783 | Line 725 | public class TreeMap<K,V>
725		* @since 1.6
726		*/
727		public K ceilingKey(K key) {
728	<	Entry<K,V> e = getCeilingEntry(key);
787	<	return (e == null)? null : e.key;
728	>	return keyOrNull(getCeilingEntry(key));
729		}
730
731		/**
#	Line 795 | Line 736 | public class TreeMap<K,V>
736		* @since 1.6
737		*/
738		public Map.Entry<K,V> higherEntry(K key) {
739	<	Entry<K,V> e = getHigherEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
739	>	return exportEntry(getHigherEntry(key));
740		}
741
742		/**
#	Line 807 | Line 747 | public class TreeMap<K,V>
747		* @since 1.6
748		*/
749		public K higherKey(K key) {
750	<	Entry<K,V> e = getHigherEntry(key);
811	<	return (e == null)? null : e.key;
750	>	return keyOrNull(getHigherEntry(key));
751		}
752
753		// Views
#	Line 994 | Line 933 | public class TreeMap<K,V>
933		}
934
935		public boolean contains(Object o) {
936	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
998	<	if (valEquals(e.getValue(), o))
999	<	return true;
1000	<	return false;
936	>	return TreeMap.this.containsValue(o);
937		}
938
939		public boolean remove(Object o) {
#	Line 1221 | Line 1157 | public class TreeMap<K,V>
1157		}
1158		}
1159
1160	+	// Little utilities
1161	+
1162	+	/**
1163	+	* Compares two keys using the correct comparison method for this TreeMap.
1164	+	*/
1165	+	final int compare(Object k1, Object k2) {
1166	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1167	+	: comparator.compare((K)k1, (K)k2);
1168	+	}
1169	+
1170	+	/**
1171	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1172	+	* that it copes with <tt>null</tt> o1 properly.
1173	+	*/
1174	+	final static boolean valEquals(Object o1, Object o2) {
1175	+	return (o1==null ? o2==null : o1.equals(o2));
1176	+	}
1177	+
1178	+	/**
1179	+	* Return SimpleImmutableEntry for entry, or null if null
1180	+	*/
1181	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1182	+	return e == null? null :
1183	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1184	+	}
1185	+
1186	+	/**
1187	+	* Return key for entry, or null if null
1188	+	*/
1189	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1190	+	return e == null? null : e.key;
1191	+	}
1192	+
1193	+	/**
1194	+	* Returns the key corresponding to the specified Entry.
1195	+	* @throws NoSuchElementException if the Entry is null
1196	+	*/
1197	+	static <K> K key(Entry<K,?> e) {
1198	+	if (e==null)
1199	+	throw new NoSuchElementException();
1200	+	return e.key;
1201	+	}
1202	+
1203	+
1204		// SubMaps
1205
1206		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
#	Line 1298 | Line 1278 | public class TreeMap<K,V>
1278		return inclusive ? inRange(key) : inClosedRange(key);
1279		}
1280
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	–
1281		/*
1282		* Absolute versions of relation operations.
1283		* Subclasses map to these using like-named "sub"
#	Line 1334 | Line 1299 | public class TreeMap<K,V>
1299		m.getLowerEntry(hi)));
1300		return (e == null || tooLow(e.key)) ? null : e;
1301		}
1302	<
1302	>
1303		final TreeMap.Entry<K,V> absCeiling(K key) {
1304		if (tooLow(key))
1305		return absLowest();
#	Line 1365 | Line 1330 | public class TreeMap<K,V>
1330
1331		/** Returns the absolute high fence for ascending traversal */
1332		final TreeMap.Entry<K,V> absHighFence() {
1333	<	return (toEnd ? null : (hiInclusive ?
1333	>	return (toEnd ? null : (hiInclusive ?
1334		m.getHigherEntry(hi) :
1335		m.getCeilingEntry(hi)));
1336		}
#	Line 1426 | Line 1391 | public class TreeMap<K,V>
1391		}
1392
1393		public final K ceilingKey(K key) {
1394	<	return exportKey(subCeiling(key));
1394	>	return keyOrNull(subCeiling(key));
1395		}
1396
1397		public final Map.Entry<K,V> higherEntry(K key) {
#	Line 1434 | Line 1399 | public class TreeMap<K,V>
1399		}
1400
1401		public final K higherKey(K key) {
1402	<	return exportKey(subHigher(key));
1402	>	return keyOrNull(subHigher(key));
1403		}
1404
1405		public final Map.Entry<K,V> floorEntry(K key) {
#	Line 1442 | Line 1407 | public class TreeMap<K,V>
1407		}
1408
1409		public final K floorKey(K key) {
1410	<	return exportKey(subFloor(key));
1410	>	return keyOrNull(subFloor(key));
1411		}
1412
1413		public final Map.Entry<K,V> lowerEntry(K key) {
#	Line 1450 | Line 1415 | public class TreeMap<K,V>
1415		}
1416
1417		public final K lowerKey(K key) {
1418	<	return exportKey(subLower(key));
1418	>	return keyOrNull(subLower(key));
1419		}
1420
1421		public final K firstKey() {
#	Line 1820 | Line 1785 | public class TreeMap<K,V>
1785		}
1786
1787		/**
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	–	/**
1788		* This class exists solely for the sake of serialization
1789		* compatibility with previous releases of TreeMap that did not
1790		* support NavigableMap.  It translates an old-version SubMap into
#	Line 1862 | Line 1811 | public class TreeMap<K,V>
1811		}
1812
1813
1814	+	// Red-black mechanics
1815	+
1816		private static final boolean RED   = false;
1817		private static final boolean BLACK = true;
1818
#	Line 2037 | Line 1988 | public class TreeMap<K,V>
1988		return (p == null) ? null: p.right;
1989		}
1990
1991	<	/** From CLR **/
1991	>	/** From CLR */
1992		private void rotateLeft(Entry<K,V> p) {
1993	<	Entry<K,V> r = p.right;
1994	<	p.right = r.left;
1995	<	if (r.left != null)
1996	<	r.left.parent = p;
1997	<	r.parent = p.parent;
1998	<	if (p.parent == null)
1999	<	root = r;
2000	<	else if (p.parent.left == p)
2001	<	p.parent.left = r;
2002	<	else
2003	<	p.parent.right = r;
2004	<	r.left = p;
2005	<	p.parent = r;
1993	>	if (p != null) {
1994	>	Entry<K,V> r = p.right;
1995	>	p.right = r.left;
1996	>	if (r.left != null)
1997	>	r.left.parent = p;
1998	>	r.parent = p.parent;
1999	>	if (p.parent == null)
2000	>	root = r;
2001	>	else if (p.parent.left == p)
2002	>	p.parent.left = r;
2003	>	else
2004	>	p.parent.right = r;
2005	>	r.left = p;
2006	>	p.parent = r;
2007	>	}
2008		}
2009
2010	<	/** From CLR **/
2010	>	/** From CLR */
2011		private void rotateRight(Entry<K,V> p) {
2012	<	Entry<K,V> l = p.left;
2013	<	p.left = l.right;
2014	<	if (l.right != null) l.right.parent = p;
2015	<	l.parent = p.parent;
2016	<	if (p.parent == null)
2017	<	root = l;
2018	<	else if (p.parent.right == p)
2019	<	p.parent.right = l;
2020	<	else p.parent.left = l;
2021	<	l.right = p;
2022	<	p.parent = l;
2012	>	if (p != null) {
2013	>	Entry<K,V> l = p.left;
2014	>	p.left = l.right;
2015	>	if (l.right != null) l.right.parent = p;
2016	>	l.parent = p.parent;
2017	>	if (p.parent == null)
2018	>	root = l;
2019	>	else if (p.parent.right == p)
2020	>	p.parent.right = l;
2021	>	else p.parent.left = l;
2022	>	l.right = p;
2023	>	p.parent = l;
2024	>	}
2025		}
2026
2027	<
2073	<	/** From CLR **/
2027	>	/** From CLR */
2028		private void fixAfterInsertion(Entry<K,V> x) {
2029		x.color = RED;
2030
#	Line 2089 | Line 2043 | public class TreeMap<K,V>
2043		}
2044		setColor(parentOf(x), BLACK);
2045		setColor(parentOf(parentOf(x)), RED);
2046	<	if (parentOf(parentOf(x)) != null)
2093	<	rotateRight(parentOf(parentOf(x)));
2046	>	rotateRight(parentOf(parentOf(x)));
2047		}
2048		} else {
2049		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2106 | Line 2059 | public class TreeMap<K,V>
2059		}
2060		setColor(parentOf(x), BLACK);
2061		setColor(parentOf(parentOf(x)), RED);
2062	<	if (parentOf(parentOf(x)) != null)
2110	<	rotateLeft(parentOf(parentOf(x)));
2062	>	rotateLeft(parentOf(parentOf(x)));
2063		}
2064		}
2065		}
#	Line 2117 | Line 2069 | public class TreeMap<K,V>
2069		/**
2070		* Delete node p, and then rebalance the tree.
2071		*/
2120	–
2072		private void deleteEntry(Entry<K,V> p) {
2073	<	decrementSize();
2073	>	modCount++;
2074	>	size--;
2075
2076		// If strictly internal, copy successor's element to p and then make p
2077		// point to successor.
#	Line 2165 | Line 2117 | public class TreeMap<K,V>
2117		}
2118		}
2119
2120	<	/** From CLR **/
2120	>	/** From CLR */
2121		private void fixAfterDeletion(Entry<K,V> x) {
2122		while (x != root && colorOf(x) == BLACK) {
2123		if (x == leftOf(parentOf(x))) {
#	Line 2273 | Line 2225 | public class TreeMap<K,V>
2225		buildFromSorted(size, null, s, null);
2226		}
2227
2228	<	/** Intended to be called only from TreeSet.readObject **/
2228	>	/** Intended to be called only from TreeSet.readObject */
2229		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2230		throws java.io.IOException, ClassNotFoundException {
2231		buildFromSorted(size, null, s, defaultVal);
2232		}
2233
2234	<	/** Intended to be called only from TreeSet.addAll **/
2234	>	/** Intended to be called only from TreeSet.addAll */
2235		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2236		try {
2237		buildFromSorted(set.size(), set.iterator(), null, defaultVal);

Diff Legend

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