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.33 by dl, Sat Apr 22 23:02:25 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 509 | Line 506 | public class TreeMap<K,V>
506		}
507
508		/**
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	–	/**
509		* Associates the specified value with the specified key in this map.
510		* If the map previously contained a mapping for the key, the old
511		* value is replaced.
#	Line 543 | Line 530 | public class TreeMap<K,V>
530		if (key == null)
531		throw new NullPointerException();
532		Comparable<? super K> k = (Comparable<? super K>) key;
533	<
533	>	int cmp = 0;
534	>	Entry<K,V> parent = null;
535		Entry<K,V> t = root;
536		while (t != null) {
537	<	int cmp = k.compareTo(t.key);
538	<	if (cmp == 0) {
537	>	parent = t;
538	>	cmp = k.compareTo(t.key);
539	>	if (cmp < 0)
540	>	t = t.left;
541	>	else if (cmp > 0)
542	>	t = t.right;
543	>	else
544		return t.setValue(value);
552	–	} else if (cmp < 0) {
553	–	if (t.left != null) {
554	–	t = t.left;
555	–	} 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) {
562	–	t = t.right;
563	–	} else {
564	–	incrementSize();
565	–	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	–	return null;
567	–	}
568	–	}
545		}
546	<	incrementSize();
547	<	root = new Entry<K,V>(key, value, null);
546	>	Entry<K,V> e = new Entry<K,V>((K)k, value, parent);
547	>	size++;
548	>	modCount++;
549	>	if (parent != null) {
550	>	if (cmp < 0)
551	>	parent.left = e;
552	>	else
553	>	parent.right = e;
554	>	fixAfterInsertion(e);
555	>	}
556	>	else
557	>	root = e;
558		return null;
559		}
560
#	Line 578 | Line 564 | public class TreeMap<K,V>
564		*/
565		final V putUsingComparator(K key, V value) {
566		Comparator<? super K> cpr = comparator;
567	+	int cmp = 0;
568	+	Entry<K,V> parent = null;
569		Entry<K,V> t = root;
570	+	if (t == null)
571	+	cpr.compare(key, key); // type check
572		while (t != null) {
573	<	int cmp = cpr.compare(key, t.key);
574	<	if (cmp == 0) {
573	>	parent = t;
574	>	cmp = cpr.compare(key, t.key);
575	>	if (cmp < 0)
576	>	t = t.left;
577	>	else if (cmp > 0)
578	>	t = t.right;
579	>	else
580		return t.setValue(value);
586	–	} else if (cmp < 0) {
587	–	if (t.left != null) {
588	–	t = t.left;
589	–	} 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) {
596	–	t = t.right;
597	–	} else {
598	–	incrementSize();
599	–	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600	–	return null;
601	–	}
602	–	}
581		}
582	<	cpr.compare(key, key); // type check
583	<	incrementSize();
584	<	root = new Entry<K,V>(key, value, null);
582	>	Entry<K,V> e = new Entry<K,V>(key, value, parent);
583	>	size++;
584	>	modCount++;
585	>	if (parent != null) {
586	>	if (cmp < 0)
587	>	parent.left = e;
588	>	else
589	>	parent.right = e;
590	>	fixAfterInsertion(e);
591	>	}
592	>	else
593	>	root = e;
594		return null;
595		}
596
#	Line 679 | Line 666 | public class TreeMap<K,V>
666		* @since 1.6
667		*/
668		public Map.Entry<K,V> firstEntry() {
669	<	Entry<K,V> e = getFirstEntry();
683	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
669	>	return exportEntry(getFirstEntry());
670		}
671
672		/**
673		* @since 1.6
674		*/
675		public Map.Entry<K,V> lastEntry() {
676	<	Entry<K,V> e = getLastEntry();
691	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
676	>	return exportEntry(getLastEntry());
677		}
678
679		/**
#	Line 696 | Line 681 | public class TreeMap<K,V>
681		*/
682		public Map.Entry<K,V> pollFirstEntry() {
683		Entry<K,V> p = getFirstEntry();
684	<	if (p == null)
685	<	return null;
686	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702	<	deleteEntry(p);
684	>	Map.Entry<K,V> result = exportEntry(p);
685	>	if (p != null)
686	>	deleteEntry(p);
687		return result;
688		}
689
#	Line 708 | Line 692 | public class TreeMap<K,V>
692		*/
693		public Map.Entry<K,V> pollLastEntry() {
694		Entry<K,V> p = getLastEntry();
695	<	if (p == null)
696	<	return null;
697	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714	<	deleteEntry(p);
695	>	Map.Entry<K,V> result = exportEntry(p);
696	>	if (p != null)
697	>	deleteEntry(p);
698		return result;
699		}
700
#	Line 723 | Line 706 | public class TreeMap<K,V>
706		* @since 1.6
707		*/
708		public Map.Entry<K,V> lowerEntry(K key) {
709	<	Entry<K,V> e =  getLowerEntry(key);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
709	>	return exportEntry(getLowerEntry(key));
710		}
711
712		/**
#	Line 735 | Line 717 | public class TreeMap<K,V>
717		* @since 1.6
718		*/
719		public K lowerKey(K key) {
720	<	Entry<K,V> e =  getLowerEntry(key);
739	<	return (e == null)? null : e.key;
720	>	return keyOrNull(getLowerEntry(key));
721		}
722
723		/**
#	Line 747 | Line 728 | public class TreeMap<K,V>
728		* @since 1.6
729		*/
730		public Map.Entry<K,V> floorEntry(K key) {
731	<	Entry<K,V> e = getFloorEntry(key);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
731	>	return exportEntry(getFloorEntry(key));
732		}
733
734		/**
#	Line 759 | Line 739 | public class TreeMap<K,V>
739		* @since 1.6
740		*/
741		public K floorKey(K key) {
742	<	Entry<K,V> e = getFloorEntry(key);
763	<	return (e == null)? null : e.key;
742	>	return keyOrNull(getFloorEntry(key));
743		}
744
745		/**
#	Line 771 | Line 750 | public class TreeMap<K,V>
750		* @since 1.6
751		*/
752		public Map.Entry<K,V> ceilingEntry(K key) {
753	<	Entry<K,V> e = getCeilingEntry(key);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
753	>	return exportEntry(getCeilingEntry(key));
754		}
755
756		/**
#	Line 783 | Line 761 | public class TreeMap<K,V>
761		* @since 1.6
762		*/
763		public K ceilingKey(K key) {
764	<	Entry<K,V> e = getCeilingEntry(key);
787	<	return (e == null)? null : e.key;
764	>	return keyOrNull(getCeilingEntry(key));
765		}
766
767		/**
#	Line 795 | Line 772 | public class TreeMap<K,V>
772		* @since 1.6
773		*/
774		public Map.Entry<K,V> higherEntry(K key) {
775	<	Entry<K,V> e = getHigherEntry(key);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
775	>	return exportEntry(getHigherEntry(key));
776		}
777
778		/**
#	Line 807 | Line 783 | public class TreeMap<K,V>
783		* @since 1.6
784		*/
785		public K higherKey(K key) {
786	<	Entry<K,V> e = getHigherEntry(key);
811	<	return (e == null)? null : e.key;
786	>	return keyOrNull(getHigherEntry(key));
787		}
788
789		// Views
#	Line 1221 | Line 1196 | public class TreeMap<K,V>
1196		}
1197		}
1198
1199	+	// Little utilities
1200	+
1201	+	/**
1202	+	* Compares two keys using the correct comparison method for this TreeMap.
1203	+	*/
1204	+	final int compare(Object k1, Object k2) {
1205	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1206	+	: comparator.compare((K)k1, (K)k2);
1207	+	}
1208	+
1209	+	/**
1210	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1211	+	* that it copes with <tt>null</tt> o1 properly.
1212	+	*/
1213	+	final static boolean valEquals(Object o1, Object o2) {
1214	+	return (o1==null ? o2==null : o1.equals(o2));
1215	+	}
1216	+
1217	+	/**
1218	+	* Return SimpleImmutableEntry for entry, or null if null
1219	+	*/
1220	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1221	+	return e == null? null :
1222	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1223	+	}
1224	+
1225	+	/**
1226	+	* Return key for entry, or null if null
1227	+	*/
1228	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1229	+	return e == null? null : e.key;
1230	+	}
1231	+
1232	+	/**
1233	+	* Returns the key corresponding to the specified Entry.
1234	+	* @throws NoSuchElementException if the Entry is null
1235	+	*/
1236	+	static <K> K key(Entry<K,?> e) {
1237	+	if (e==null)
1238	+	throw new NoSuchElementException();
1239	+	return e.key;
1240	+	}
1241	+
1242	+
1243		// SubMaps
1244
1245		static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
#	Line 1298 | Line 1317 | public class TreeMap<K,V>
1317		return inclusive ? inRange(key) : inClosedRange(key);
1318		}
1319
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	–
1320		/*
1321		* Absolute versions of relation operations.
1322		* Subclasses map to these using like-named "sub"
#	Line 1334 | Line 1338 | public class TreeMap<K,V>
1338		m.getLowerEntry(hi)));
1339		return (e == null || tooLow(e.key)) ? null : e;
1340		}
1341	<
1341	>
1342		final TreeMap.Entry<K,V> absCeiling(K key) {
1343		if (tooLow(key))
1344		return absLowest();
#	Line 1365 | Line 1369 | public class TreeMap<K,V>
1369
1370		/** Returns the absolute high fence for ascending traversal */
1371		final TreeMap.Entry<K,V> absHighFence() {
1372	<	return (toEnd ? null : (hiInclusive ?
1372	>	return (toEnd ? null : (hiInclusive ?
1373		m.getHigherEntry(hi) :
1374		m.getCeilingEntry(hi)));
1375		}
#	Line 1426 | Line 1430 | public class TreeMap<K,V>
1430		}
1431
1432		public final K ceilingKey(K key) {
1433	<	return exportKey(subCeiling(key));
1433	>	return keyOrNull(subCeiling(key));
1434		}
1435
1436		public final Map.Entry<K,V> higherEntry(K key) {
#	Line 1434 | Line 1438 | public class TreeMap<K,V>
1438		}
1439
1440		public final K higherKey(K key) {
1441	<	return exportKey(subHigher(key));
1441	>	return keyOrNull(subHigher(key));
1442		}
1443
1444		public final Map.Entry<K,V> floorEntry(K key) {
#	Line 1442 | Line 1446 | public class TreeMap<K,V>
1446		}
1447
1448		public final K floorKey(K key) {
1449	<	return exportKey(subFloor(key));
1449	>	return keyOrNull(subFloor(key));
1450		}
1451
1452		public final Map.Entry<K,V> lowerEntry(K key) {
#	Line 1450 | Line 1454 | public class TreeMap<K,V>
1454		}
1455
1456		public final K lowerKey(K key) {
1457	<	return exportKey(subLower(key));
1457	>	return keyOrNull(subLower(key));
1458		}
1459
1460		public final K firstKey() {
#	Line 1820 | Line 1824 | public class TreeMap<K,V>
1824		}
1825
1826		/**
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	–	/**
1827		* This class exists solely for the sake of serialization
1828		* compatibility with previous releases of TreeMap that did not
1829		* support NavigableMap.  It translates an old-version SubMap into
#	Line 1862 | Line 1850 | public class TreeMap<K,V>
1850		}
1851
1852
1853	+	// Red-black mechanics
1854	+
1855		private static final boolean RED   = false;
1856		private static final boolean BLACK = true;
1857
#	Line 2037 | Line 2027 | public class TreeMap<K,V>
2027		return (p == null) ? null: p.right;
2028		}
2029
2030	<	/** From CLR **/
2030	>	/** From CLR */
2031		private void rotateLeft(Entry<K,V> p) {
2032		Entry<K,V> r = p.right;
2033		p.right = r.left;
#	Line 2054 | Line 2044 | public class TreeMap<K,V>
2044		p.parent = r;
2045		}
2046
2047	<	/** From CLR **/
2047	>	/** From CLR */
2048		private void rotateRight(Entry<K,V> p) {
2049		Entry<K,V> l = p.left;
2050		p.left = l.right;
#	Line 2070 | Line 2060 | public class TreeMap<K,V>
2060		}
2061
2062
2063	<	/** From CLR **/
2063	>	/** From CLR */
2064		private void fixAfterInsertion(Entry<K,V> x) {
2065		x.color = RED;
2066
#	Line 2119 | Line 2109 | public class TreeMap<K,V>
2109		*/
2110
2111		private void deleteEntry(Entry<K,V> p) {
2112	<	decrementSize();
2112	>	modCount++;
2113	>	size--;
2114
2115		// If strictly internal, copy successor's element to p and then make p
2116		// point to successor.
#	Line 2165 | Line 2156 | public class TreeMap<K,V>
2156		}
2157		}
2158
2159	<	/** From CLR **/
2159	>	/** From CLR */
2160		private void fixAfterDeletion(Entry<K,V> x) {
2161		while (x != root && colorOf(x) == BLACK) {
2162		if (x == leftOf(parentOf(x))) {
#	Line 2273 | Line 2264 | public class TreeMap<K,V>
2264		buildFromSorted(size, null, s, null);
2265		}
2266
2267	<	/** Intended to be called only from TreeSet.readObject **/
2267	>	/** Intended to be called only from TreeSet.readObject */
2268		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2269		throws java.io.IOException, ClassNotFoundException {
2270		buildFromSorted(size, null, s, defaultVal);
2271		}
2272
2273	<	/** Intended to be called only from TreeSet.addAll **/
2273	>	/** Intended to be called only from TreeSet.addAll */
2274		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2275		try {
2276		buildFromSorted(set.size(), set.iterator(), null, defaultVal);

Diff Legend

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