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.30 by jsr166, Thu Apr 20 21:49:36 2006 UTC vs.
Revision 1.31 by dl, Fri Apr 21 13:42:57 2006 UTC

#	Line 95 | Line 95 | public class TreeMap<K,V>
95		*
96		* @serial
97		*/
98	<	private Comparator<? super K> comparator = null;
98	>	private final Comparator<? super K> comparator;
99
100		private transient Entry<K,V> root = null;
101
#	Line 125 | Line 125 | public class TreeMap<K,V>
125		* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128	+	comparator = null;
129		}
130
131		/**
#	Line 160 | Line 161 | public class TreeMap<K,V>
161		* @throws NullPointerException if the specified map is null
162		*/
163		public TreeMap(Map<? extends K, ? extends V> m) {
164	+	comparator = null;
165		putAll(m);
166		}
167
#	Line 359 | Line 361 | public class TreeMap<K,V>
361		* Version of getEntry using comparator. Split off from getEntry
362		* for performance. (This is not worth doing for most methods,
363		* that are less dependent on comparator performance, but is
364	<	* worthwhile here.)
364	>	* worthwhile for get and put.)
365		*/
366		final Entry<K,V> getEntryUsingComparator(Object key) {
367		K k = (K) key;
#	Line 385 | Line 387 | public class TreeMap<K,V>
387		*/
388		final Entry<K,V> getCeilingEntry(K key) {
389		Entry<K,V> p = root;
390	<	if (p==null)
389	<	return null;
390	<
391	<	while (true) {
390	>	while (p != null) {
391		int cmp = compare(key, p.key);
392		if (cmp < 0) {
393		if (p.left != null)
#	Line 410 | Line 409 | public class TreeMap<K,V>
409		} else
410		return p;
411		}
412	+	return null;
413		}
414
415		/**
#	Line 419 | Line 419 | public class TreeMap<K,V>
419		*/
420		final Entry<K,V> getFloorEntry(K key) {
421		Entry<K,V> p = root;
422	<	if (p==null)
423	<	return null;
424	<
425	<	while (true) {
422	>	while (p != null) {
423		int cmp = compare(key, p.key);
424		if (cmp > 0) {
425		if (p.right != null)
#	Line 445 | Line 442 | public class TreeMap<K,V>
442		return p;
443
444		}
445	+	return null;
446		}
447
448		/**
#	Line 455 | Line 453 | public class TreeMap<K,V>
453		*/
454		final Entry<K,V> getHigherEntry(K key) {
455		Entry<K,V> p = root;
456	<	if (p==null)
459	<	return null;
460	<
461	<	while (true) {
456	>	while (p != null) {
457		int cmp = compare(key, p.key);
458		if (cmp < 0) {
459		if (p.left != null)
#	Line 479 | Line 474 | public class TreeMap<K,V>
474		}
475		}
476		}
477	+	return null;
478		}
479
480		/**
#	Line 488 | Line 484 | public class TreeMap<K,V>
484		*/
485		final Entry<K,V> getLowerEntry(K key) {
486		Entry<K,V> p = root;
487	<	if (p==null)
492	<	return null;
493	<
494	<	while (true) {
487	>	while (p != null) {
488		int cmp = compare(key, p.key);
489		if (cmp > 0) {
490		if (p.right != null)
#	Line 512 | Line 505 | public class TreeMap<K,V>
505		}
506		}
507		}
508	+	return null;
509		}
510
511		/**
#	Line 543 | Line 537 | public class TreeMap<K,V>
537		*         does not permit null keys
538		*/
539		public V put(K key, V value) {
540	<	Entry<K,V> t = root;
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
547	<	if (t == null) {
548	<	// TBD
549	<	//             if (key == null) {
550	<	//                 if (comparator == null)
551	<	//                     throw new NullPointerException();
552	<	//                 comparator.compare(key, key);
553	<	//             }
554	<	incrementSize();
555	<	root = new Entry<K,V>(key, value, null);
556	<	return null;
547	>	Entry<K,V> t = root;
548	>	while (t != null) {
549	>	int cmp = k.compareTo(t.key);
550	>	if (cmp == 0) {
551	>	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	>	}
569		}
570	+	incrementSize();
571	+	root = new Entry<K,V>(key, value, null);
572	+	return null;
573	+	}
574
575	<	while (true) {
576	<	int cmp = compare(key, t.key);
575	>	/**
576	>	* Version of put using comparator. Split off from put for
577	>	* 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) {
#	Line 566 | Line 588 | public class TreeMap<K,V>
588		t = t.left;
589		} else {
590		incrementSize();
591	<	t.left = new Entry<K,V>(key, value, t);
570	<	fixAfterInsertion(t.left);
591	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592		return null;
593		}
594		} else { // cmp > 0
#	Line 575 | Line 596 | public class TreeMap<K,V>
596		t = t.right;
597		} else {
598		incrementSize();
599	<	t.right = new Entry<K,V>(key, value, t);
579	<	fixAfterInsertion(t.right);
599	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600		return null;
601		}
602		}
603		}
604	+	cpr.compare(key, key); // type check
605	+	incrementSize();
606	+	root = new Entry<K,V>(key, value, null);
607	+	return null;
608		}
609
610		/**
#	Line 907 | Line 931 | public class TreeMap<K,V>
931		*/
932		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
933		return new AscendingSubMap(this,
934	<	true, null, 0,
934	>	true,  null,  0,
935		false, toKey, excluded(inclusive));
936		}
937
#	Line 922 | Line 946 | public class TreeMap<K,V>
946		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
947		return new AscendingSubMap(this,
948		false, fromKey, excluded(inclusive),
949	<	true, null, 0);
949	>	true,  null,    0);
950		}
951
952		/**
#	Line 1093 | Line 1117 | public class TreeMap<K,V>
1117		m.remove(o);
1118		return size() != oldSize;
1119		}
1120	<	public NavigableSet<E> subSet(E fromElement,
1121	<	boolean fromInclusive,
1122	<	E toElement,
1123	<	boolean toInclusive) {
1100	<	return new TreeSet<E>
1101	<	(m.subMap(fromElement, fromInclusive,
1102	<	toElement,   toInclusive));
1120	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1121	>	E toElement, boolean toInclusive) {
1122	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1123	>	toElement,   toInclusive));
1124		}
1125		public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1126		return new TreeSet<E>(m.headMap(toElement, inclusive));
#	Line 1125 | Line 1146 | public class TreeMap<K,V>
1146		* Base class for TreeMap Iterators
1147		*/
1148		abstract class PrivateEntryIterator<T> implements Iterator<T> {
1128	–	int expectedModCount = TreeMap.this.modCount;
1129	–	Entry<K,V> lastReturned = null;
1149		Entry<K,V> next;
1150	+	Entry<K,V> lastReturned;
1151	+	int expectedModCount;
1152
1153		PrivateEntryIterator(Entry<K,V> first) {
1154	+	expectedModCount = modCount;
1155	+	lastReturned = null;
1156		next = first;
1157		}
1158
#	Line 1138 | Line 1161 | public class TreeMap<K,V>
1161		}
1162
1163		final Entry<K,V> nextEntry() {
1164	<	if (next == null)
1164	>	Entry<K,V> e = lastReturned = next;
1165	>	if (e == null)
1166		throw new NoSuchElementException();
1167		if (modCount != expectedModCount)
1168		throw new ConcurrentModificationException();
1169	<	lastReturned = next;
1170	<	next = successor(next);
1147	<	return lastReturned;
1169	>	next = successor(e);
1170	>	return e;
1171		}
1172
1173		final Entry<K,V> prevEntry() {
1174	<	if (next == null)
1174	>	Entry<K,V> e = lastReturned= next;
1175	>	if (e == null)
1176		throw new NoSuchElementException();
1177		if (modCount != expectedModCount)
1178		throw new ConcurrentModificationException();
1179	<	lastReturned = next;
1180	<	next = predecessor(next);
1157	<	return lastReturned;
1179	>	next = predecessor(e);
1180	>	return e;
1181		}
1182
1183		public void remove() {
#	Line 1216 | Line 1239 | public class TreeMap<K,V>
1239		*/
1240		final TreeMap<K,V> m;
1241
1242	<	/** True if low point is from start of backing map */
1243	<	boolean fromStart;
1244	<
1245	<	/**
1246	<	* The low endpoint of this submap in absolute terms, or null
1247	<	* if fromStart.
1248	<	*/
1226	<	K lo;
1227	<
1228	<	/**
1229	<	* Zero if the low endpoint is excluded from this submap, one if
1230	<	* it's included.  This field is unused if fromStart.
1242	>	/*
1243	>	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1244	>	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1245	>	* the low (absolute) bound is the start of the backing map, and the
1246	>	* other values are ignored. Otherwise, if loExcluded is
1247	>	* zero, lo is the inclusive bound, else loExcluded is one,
1248	>	* and lo is the exclusive bound. Similarly for the upper bound.
1249		*/
1232	–	int loExcluded;
1250
1251	<	/** True if high point is to End of backing map */
1252	<	boolean toEnd;
1253	<
1237	<	/**
1238	<	* The high endpoint of this submap in absolute terms, or null
1239	<	* if toEnd.
1240	<	*/
1241	<	K hi;
1242	<
1243	<	/**
1244	<	* Zero if the high endpoint is excluded from this submap, one if
1245	<	* it's included.  This field is unused if toEnd.
1246	<	*/
1247	<	int hiExcluded;
1251	>	final K lo, hi;
1252	>	final boolean fromStart, toEnd;
1253	>	final int loExcluded, hiExcluded;
1254
1255		NavigableSubMap(TreeMap<K,V> m,
1256		boolean fromStart, K lo, int loExcluded,
1257	<	boolean toEnd, K hi, int hiExcluded) {
1258	<	if (!fromStart && !toEnd && m.compare(lo, hi) > 0)
1259	<	throw new IllegalArgumentException("fromKey > toKey");
1257	>	boolean toEnd,     K hi, int hiExcluded) {
1258	>	if (!fromStart && !toEnd) {
1259	>	if (m.compare(lo, hi) > 0)
1260	>	throw new IllegalArgumentException("fromKey > toKey");
1261	>	}
1262	>	else if (!fromStart) // type check
1263	>	m.compare(lo, lo);
1264	>	else if (!toEnd)
1265	>	m.compare(hi, hi);
1266	>
1267		this.m = m;
1268		this.fromStart = fromStart;
1269		this.lo = lo;
#	Line 1284 | Line 1297 | public class TreeMap<K,V>
1297		return !toEnd && m.compare(hi, key) < hiExcluded;
1298		}
1299
1287	–
1300		/** Returns the lowest entry in this submap (absolute ordering) */
1301		final TreeMap.Entry<K,V> loEntry() {
1302		TreeMap.Entry<K,V> result =
#	Line 1499 | Line 1511 | public class TreeMap<K,V>
1511		return tailMap(fromKey, true);
1512		}
1513
1502	–
1514		// The following four definitions are correct only for
1515		// ascending submaps. They are overridden in DescendingSubMap.
1516		// They are defined in the base class because the definitions
#	Line 1557 | Line 1568 | public class TreeMap<K,V>
1568		* Iterators for SubMaps
1569		*/
1570		abstract class SubMapIterator<T> implements Iterator<T> {
1571	<	int expectedModCount = m.modCount;
1561	<	TreeMap.Entry<K,V> lastReturned = null;
1571	>	TreeMap.Entry<K,V> lastReturned;
1572		TreeMap.Entry<K,V> next;
1573	<	final K firstExcludedKey;
1573	>	final K fenceKey;
1574	>	int expectedModCount;
1575
1576		SubMapIterator(TreeMap.Entry<K,V> first,
1577	<	TreeMap.Entry<K,V> firstExcluded) {
1577	>	TreeMap.Entry<K,V> fence) {
1578	>	expectedModCount = m.modCount;
1579	>	lastReturned = null;
1580		next = first;
1581	<	firstExcludedKey = (firstExcluded == null ? null
1569	<	: firstExcluded.key);
1581	>	fenceKey = fence == null ? null : fence.key;
1582		}
1583
1584		public final boolean hasNext() {
1585	<	return next != null && next.key != firstExcludedKey;
1585	>	return next != null && next.key != fenceKey;
1586		}
1587
1588		final TreeMap.Entry<K,V> nextEntry() {
1589	<	if (next == null || next.key == firstExcludedKey)
1589	>	TreeMap.Entry<K,V> e = lastReturned = next;
1590	>	if (e == null || e.key == fenceKey)
1591		throw new NoSuchElementException();
1592		if (m.modCount != expectedModCount)
1593		throw new ConcurrentModificationException();
1594	<	lastReturned = next;
1595	<	next = m.successor(next);
1583	<	return lastReturned;
1594	>	next = successor(e);
1595	>	return e;
1596		}
1597
1598		final TreeMap.Entry<K,V> prevEntry() {
1599	<	if (next == null || next.key == firstExcludedKey)
1599	>	TreeMap.Entry<K,V> e = lastReturned = next;
1600	>	if (e == null || e.key == fenceKey)
1601		throw new NoSuchElementException();
1602		if (m.modCount != expectedModCount)
1603		throw new ConcurrentModificationException();
1604	<	lastReturned = next;
1605	<	next = m.predecessor(next);
1593	<	return lastReturned;
1604	>	next = predecessor(e);
1605	>	return e;
1606		}
1607
1608		public void remove() {
#	Line 1608 | Line 1620 | public class TreeMap<K,V>
1620
1621		final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1622		SubMapEntryIterator(TreeMap.Entry<K,V> first,
1623	<	TreeMap.Entry<K,V> firstExcluded) {
1624	<	super(first, firstExcluded);
1623	>	TreeMap.Entry<K,V> fence) {
1624	>	super(first, fence);
1625		}
1626		public Map.Entry<K,V> next() {
1627		return nextEntry();
#	Line 1618 | Line 1630 | public class TreeMap<K,V>
1630
1631		final class SubMapKeyIterator extends SubMapIterator<K> {
1632		SubMapKeyIterator(TreeMap.Entry<K,V> first,
1633	<	TreeMap.Entry<K,V> firstExcluded) {
1634	<	super(first, firstExcluded);
1633	>	TreeMap.Entry<K,V> fence) {
1634	>	super(first, fence);
1635		}
1636		public K next() {
1637		return nextEntry().key;
#	Line 1677 | Line 1689 | public class TreeMap<K,V>
1689		throw new IllegalArgumentException("toKey out of range");
1690		return new AscendingSubMap(m,
1691		fromStart, lo,    loExcluded,
1692	<	false, toKey, excluded(inclusive));
1692	>	false,     toKey, excluded(inclusive));
1693		}
1694
1695		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
#	Line 1737 | Line 1749 | public class TreeMap<K,V>
1749		(descendingMapView =
1750		new DescendingSubMap(m,
1751		fromStart, lo, loExcluded,
1752	<	toEnd, hi, hiExcluded));
1752	>	toEnd,     hi, hiExcluded));
1753		}
1754		}
1755
#	Line 1772 | Line 1784 | public class TreeMap<K,V>
1784		throw new IllegalArgumentException("toKey out of range");
1785		return new DescendingSubMap(m,
1786		false, toKey, excluded(inclusive),
1787	<	toEnd, hi, hiExcluded);
1787	>	toEnd, hi,    hiExcluded);
1788		}
1789
1790		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1791		if (!inRange(fromKey, inclusive))
1792		throw new IllegalArgumentException("fromKey out of range");
1793		return new DescendingSubMap(m,
1794	<	fromStart, lo,      loExcluded,
1794	>	fromStart, lo, loExcluded,
1795		false, fromKey, excluded(inclusive));
1796		}
1797
#	Line 1998 | Line 2010 | public class TreeMap<K,V>
2010		/**
2011		* Returns the successor of the specified Entry, or null if no such.
2012		*/
2013	<	final Entry<K,V> successor(Entry<K,V> t) {
2013	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2014		if (t == null)
2015		return null;
2016		else if (t.right != null) {
#	Line 2020 | Line 2032 | public class TreeMap<K,V>
2032		/**
2033		* Returns the predecessor of the specified Entry, or null if no such.
2034		*/
2035	<	final Entry<K,V> predecessor(Entry<K,V> t) {
2035	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2036		if (t == null)
2037		return null;
2038		else if (t.left != null) {
#	Line 2137 | Line 2149 | public class TreeMap<K,V>
2149		x = parentOf(x);
2150		rotateRight(x);
2151		}
2152	<	setColor(parentOf(x),  BLACK);
2152	>	setColor(parentOf(x), BLACK);
2153		setColor(parentOf(parentOf(x)), RED);
2154		if (parentOf(parentOf(x)) != null)
2155		rotateLeft(parentOf(parentOf(x)));
#	Line 2213 | Line 2225 | public class TreeMap<K,V>
2225
2226		if (colorOf(leftOf(sib))  == BLACK &&
2227		colorOf(rightOf(sib)) == BLACK) {
2228	<	setColor(sib,  RED);
2228	>	setColor(sib, RED);
2229		x = parentOf(x);
2230		} else {
2231		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2240 | Line 2252 | public class TreeMap<K,V>
2252
2253		if (colorOf(rightOf(sib)) == BLACK &&
2254		colorOf(leftOf(sib)) == BLACK) {
2255	<	setColor(sib,  RED);
2255	>	setColor(sib, RED);
2256		x = parentOf(x);
2257		} else {
2258		if (colorOf(leftOf(sib)) == BLACK) {

Diff Legend

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