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.31 by dl, Fri Apr 21 13:42:57 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 902 | Line 877 | public class TreeMap<K,V>
877		NavigableMap<K, V> km = descendingMap;
878		return (km != null) ? km :
879		(descendingMap = new DescendingSubMap(this,
880	<	true, null, 0,
881	<	true, null, 0));
880	>	true, null, true,
881	>	true, null, true));
882		}
883
884		/**
#	Line 917 | Line 892 | public class TreeMap<K,V>
892		public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
893		K toKey,   boolean toInclusive) {
894		return new AscendingSubMap(this,
895	<	false, fromKey, excluded(fromInclusive),
896	<	false, toKey,   excluded(toInclusive));
895	>	false, fromKey, fromInclusive,
896	>	false, toKey,   toInclusive);
897		}
898
899		/**
#	Line 931 | Line 906 | public class TreeMap<K,V>
906		*/
907		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
908		return new AscendingSubMap(this,
909	<	true,  null,  0,
910	<	false, toKey, excluded(inclusive));
909	>	true,  null,  true,
910	>	false, toKey, inclusive);
911		}
912
913		/**
#	Line 945 | Line 920 | public class TreeMap<K,V>
920		*/
921		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
922		return new AscendingSubMap(this,
923	<	false, fromKey, excluded(inclusive),
924	<	true,  null,    0);
950	<	}
951	<
952	<	/**
953	<	* Translates a boolean "inclusive" value to the correct int value
954	<	* for the loExcluded or hiExcluded field.
955	<	*/
956	<	static int excluded(boolean inclusive) {
957	<	return inclusive ? 0 : 1;
923	>	false, fromKey, inclusive,
924	>	true,  null,    true);
925		}
926
927		/**
#	Line 1229 | 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>
1246		implements NavigableMap<K,V>, java.io.Serializable {
1236	–
1247		/*
1248		* The backing map.
1249		*/
1250		final TreeMap<K,V> m;
1251
1252		/*
1253	<	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1254	<	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1255	<	* the low (absolute) bound is the start of the backing map, and the
1256	<	* other values are ignored. Otherwise, if loExcluded is
1257	<	* zero, lo is the inclusive bound, else loExcluded is one,
1258	<	* and lo is the exclusive bound. Similarly for the upper bound.
1253	>	* Endpoints are represented as triples (fromStart, lo,
1254	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1255	>	* true, then the low (absolute) bound is the start of the
1256	>	* backing map, and the other values are ignored. Otherwise,
1257	>	* if loInclusive is true, lo is the inclusive bound, else lo
1258	>	* is the exclusive bound. Similarly for the upper bound.
1259		*/
1260
1261		final K lo, hi;
1262		final boolean fromStart, toEnd;
1263	<	final int loExcluded, hiExcluded;
1263	>	final boolean loInclusive, hiInclusive;
1264
1265		NavigableSubMap(TreeMap<K,V> m,
1266	<	boolean fromStart, K lo, int loExcluded,
1267	<	boolean toEnd,     K hi, int hiExcluded) {
1266	>	boolean fromStart, K lo, boolean loInclusive,
1267	>	boolean toEnd,     K hi, boolean hiInclusive) {
1268		if (!fromStart && !toEnd) {
1269		if (m.compare(lo, hi) > 0)
1270		throw new IllegalArgumentException("fromKey > toKey");
1271	+	} else {
1272	+	if (!fromStart) // type check
1273	+	m.compare(lo, lo);
1274	+	if (!toEnd)
1275	+	m.compare(hi, hi);
1276		}
1262	–	else if (!fromStart) // type check
1263	–	m.compare(lo, lo);
1264	–	else if (!toEnd)
1265	–	m.compare(hi, hi);
1277
1278		this.m = m;
1279		this.fromStart = fromStart;
1280		this.lo = lo;
1281	<	this.loExcluded = loExcluded;
1281	>	this.loInclusive = loInclusive;
1282		this.toEnd = toEnd;
1283		this.hi = hi;
1284	<	this.hiExcluded = hiExcluded;
1284	>	this.hiInclusive = hiInclusive;
1285		}
1286
1287		// internal utilities
1288
1289	+	final boolean tooLow(Object key) {
1290	+	if (!fromStart) {
1291	+	int c = m.compare(key, lo);
1292	+	if (c < 0 || (c == 0 && !loInclusive))
1293	+	return true;
1294	+	}
1295	+	return false;
1296	+	}
1297	+
1298	+	final boolean tooHigh(Object key) {
1299	+	if (!toEnd) {
1300	+	int c = m.compare(key, hi);
1301	+	if (c > 0 || (c == 0 && !hiInclusive))
1302	+	return true;
1303	+	}
1304	+	return false;
1305	+	}
1306	+
1307		final boolean inRange(Object key) {
1308	<	return (fromStart || m.compare(key, lo) >= loExcluded)
1280	<	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1308	>	return !tooLow(key) && !tooHigh(key);
1309		}
1310
1311		final boolean inClosedRange(Object key) {
#	Line 1289 | Line 1317 | public class TreeMap<K,V>
1317		return inclusive ? inRange(key) : inClosedRange(key);
1318		}
1319
1320	<	final boolean tooLow(K key) {
1321	<	return !fromStart && m.compare(key, lo) < loExcluded;
1322	<	}
1323	<
1324	<	final boolean tooHigh(K key) {
1297	<	return !toEnd && m.compare(hi, key) < hiExcluded;
1298	<	}
1320	>	/*
1321	>	* Absolute versions of relation operations.
1322	>	* Subclasses map to these using like-named "sub"
1323	>	* versions that invert senses for descending maps
1324	>	*/
1325
1326	<	/** Returns the lowest entry in this submap (absolute ordering) */
1327	<	final TreeMap.Entry<K,V> loEntry() {
1302	<	TreeMap.Entry<K,V> result =
1326	>	final TreeMap.Entry<K,V> absLowest() {
1327	>	TreeMap.Entry<K,V> e =
1328		(fromStart ?  m.getFirstEntry() :
1329	<	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1330	<	m.getHigherEntry(lo)));
1331	<	return (result == null || tooHigh(result.key)) ? null : result;
1329	>	(loInclusive ? m.getCeilingEntry(lo) :
1330	>	m.getHigherEntry(lo)));
1331	>	return (e == null || tooHigh(e.key)) ? null : e;
1332		}
1333
1334	<	/** Returns the highest key in this submap (absolute ordering) */
1335	<	final TreeMap.Entry<K,V> hiEntry() {
1311	<	TreeMap.Entry<K,V> result =
1334	>	final TreeMap.Entry<K,V> absHighest() {
1335	>	TreeMap.Entry<K,V> e =
1336		(toEnd ?  m.getLastEntry() :
1337	<	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1338	<	m.getLowerEntry(hi)));
1339	<	return (result == null || tooLow(result.key)) ? null : result;
1337	>	(hiInclusive ?  m.getFloorEntry(hi) :
1338	>	m.getLowerEntry(hi)));
1339	>	return (e == null || tooLow(e.key)) ? null : e;
1340		}
1341
1342	<	/** Polls the lowest entry in this submap (absolute ordering) */
1343	<	final Map.Entry<K,V> pollLoEntry() {
1344	<	TreeMap.Entry<K,V> e = loEntry();
1345	<	if (e == null)
1346	<	return null;
1323	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1324	<	m.deleteEntry(e);
1325	<	return result;
1342	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1343	>	if (tooLow(key))
1344	>	return absLowest();
1345	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1346	>	return (e == null || tooHigh(e.key)) ? null : e;
1347		}
1348
1349	<	/** Polls the highest key in this submap (absolute ordering) */
1350	<	final Map.Entry<K,V> pollHiEntry() {
1351	<	TreeMap.Entry<K,V> e = hiEntry();
1352	<	if (e == null)
1353	<	return null;
1333	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1334	<	m.deleteEntry(e);
1335	<	return result;
1349	>	final TreeMap.Entry<K,V> absHigher(K key) {
1350	>	if (tooLow(key))
1351	>	return absLowest();
1352	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1353	>	return (e == null || tooHigh(e.key)) ? null : e;
1354		}
1355
1356	<	/**
1357	<	* Return the absolute high fence for ascending traversal
1358	<	*/
1359	<	final TreeMap.Entry<K,V> hiFence() {
1360	<	if (toEnd)
1343	<	return null;
1344	<	else if (hiExcluded == 0)
1345	<	return m.getHigherEntry(hi);
1346	<	else
1347	<	return m.getCeilingEntry(hi);
1356	>	final TreeMap.Entry<K,V> absFloor(K key) {
1357	>	if (tooHigh(key))
1358	>	return absHighest();
1359	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1360	>	return (e == null || tooLow(e.key)) ? null : e;
1361		}
1362
1363	<	/**
1364	<	* Return the absolute low fence for descending traversal
1365	<	*/
1366	<	final TreeMap.Entry<K,V> loFence() {
1367	<	if (fromStart)
1355	<	return null;
1356	<	else if (loExcluded == 0)
1357	<	return m.getLowerEntry(lo);
1358	<	else
1359	<	return m.getFloorEntry(lo);
1363	>	final TreeMap.Entry<K,V> absLower(K key) {
1364	>	if (tooHigh(key))
1365	>	return absHighest();
1366	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1367	>	return (e == null || tooLow(e.key)) ? null : e;
1368		}
1369
1370	+	/** Returns the absolute high fence for ascending traversal */
1371	+	final TreeMap.Entry<K,V> absHighFence() {
1372	+	return (toEnd ? null : (hiInclusive ?
1373	+	m.getHigherEntry(hi) :
1374	+	m.getCeilingEntry(hi)));
1375	+	}
1376	+
1377	+	/** Return the absolute low fence for descending traversal  */
1378	+	final TreeMap.Entry<K,V> absLowFence() {
1379	+	return (fromStart ? null : (loInclusive ?
1380	+	m.getLowerEntry(lo) :
1381	+	m.getFloorEntry(lo)));
1382	+	}
1383	+
1384	+	// Abstract methods defined in ascending vs descending classes
1385	+	// These relay to the appropriate  absolute versions
1386	+
1387	+	abstract TreeMap.Entry<K,V> subLowest();
1388	+	abstract TreeMap.Entry<K,V> subHighest();
1389	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1390	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1391	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1392	+	abstract TreeMap.Entry<K,V> subLower(K key);
1393	+
1394	+	/** Returns ascending iterator from the perspective of this submap */
1395	+	abstract Iterator<K> keyIterator();
1396	+
1397	+	/** Returns descending iterator from the perspective of this submap */
1398	+	abstract Iterator<K> descendingKeyIterator();
1399	+
1400	+	// public methods
1401
1402		public boolean isEmpty() {
1403	<	return entrySet().isEmpty();
1403	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1404		}
1405
1406	<	public boolean containsKey(Object key) {
1407	<	return inRange(key) && m.containsKey(key);
1406	>	public int size() {
1407	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1408		}
1409
1410	<	public V get(Object key) {
1411	<	if (!inRange(key))
1373	<	return null;
1374	<	return m.get(key);
1410	>	public final boolean containsKey(Object key) {
1411	>	return inRange(key) && m.containsKey(key);
1412		}
1413
1414	<	public V put(K key, V value) {
1414	>	public final V put(K key, V value) {
1415		if (!inRange(key))
1416		throw new IllegalArgumentException("key out of range");
1417		return m.put(key, value);
1418		}
1419
1420	<	public V remove(Object key) {
1421	<	if (!inRange(key))
1385	<	return null;
1386	<	return m.remove(key);
1420	>	public final V get(Object key) {
1421	>	return !inRange(key)? null :  m.get(key);
1422		}
1423
1424	<	public Map.Entry<K,V> ceilingEntry(K key) {
1425	<	TreeMap.Entry<K,V> e = subCeiling(key);
1391	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1424	>	public final V remove(Object key) {
1425	>	return !inRange(key)? null  : m.remove(key);
1426		}
1427
1428	<	public K ceilingKey(K key) {
1429	<	TreeMap.Entry<K,V> e = subCeiling(key);
1396	<	return e == null? null : e.key;
1428	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1429	>	return exportEntry(subCeiling(key));
1430		}
1431
1432	<	public Map.Entry<K,V> higherEntry(K key) {
1433	<	TreeMap.Entry<K,V> e = subHigher(key);
1401	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1432	>	public final K ceilingKey(K key) {
1433	>	return keyOrNull(subCeiling(key));
1434		}
1435
1436	<	public K higherKey(K key) {
1437	<	TreeMap.Entry<K,V> e = subHigher(key);
1406	<	return e == null? null : e.key;
1436	>	public final Map.Entry<K,V> higherEntry(K key) {
1437	>	return exportEntry(subHigher(key));
1438		}
1439
1440	<	public Map.Entry<K,V> floorEntry(K key) {
1441	<	TreeMap.Entry<K,V> e = subFloor(key);
1411	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1440	>	public final K higherKey(K key) {
1441	>	return keyOrNull(subHigher(key));
1442		}
1443
1444	<	public K floorKey(K key) {
1445	<	TreeMap.Entry<K,V> e = subFloor(key);
1416	<	return e == null? null : e.key;
1444	>	public final Map.Entry<K,V> floorEntry(K key) {
1445	>	return exportEntry(subFloor(key));
1446		}
1447
1448	<	public Map.Entry<K,V> lowerEntry(K key) {
1449	<	TreeMap.Entry<K,V> e = subLower(key);
1421	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1448	>	public final K floorKey(K key) {
1449	>	return keyOrNull(subFloor(key));
1450		}
1451
1452	<	public K lowerKey(K key) {
1453	<	TreeMap.Entry<K,V> e = subLower(key);
1426	<	return e == null? null : e.key;
1452	>	public final Map.Entry<K,V> lowerEntry(K key) {
1453	>	return exportEntry(subLower(key));
1454		}
1455
1456	<	abstract Iterator<K> keyIterator();
1457	<	abstract Iterator<K> descendingKeyIterator();
1456	>	public final K lowerKey(K key) {
1457	>	return keyOrNull(subLower(key));
1458	>	}
1459
1460	<	public NavigableSet<K> descendingKeySet() {
1461	<	return descendingMap().navigableKeySet();
1460	>	public final K firstKey() {
1461	>	return key(subLowest());
1462	>	}
1463	>
1464	>	public final K lastKey() {
1465	>	return key(subHighest());
1466	>	}
1467	>
1468	>	public final Map.Entry<K,V> firstEntry() {
1469	>	return exportEntry(subLowest());
1470	>	}
1471	>
1472	>	public final Map.Entry<K,V> lastEntry() {
1473	>	return exportEntry(subHighest());
1474	>	}
1475	>
1476	>	public final Map.Entry<K,V> pollFirstEntry() {
1477	>	TreeMap.Entry<K,V> e = subLowest();
1478	>	Map.Entry<K,V> result = exportEntry(e);
1479	>	if (e != null)
1480	>	m.deleteEntry(e);
1481	>	return result;
1482	>	}
1483	>
1484	>	public final Map.Entry<K,V> pollLastEntry() {
1485	>	TreeMap.Entry<K,V> e = subHighest();
1486	>	Map.Entry<K,V> result = exportEntry(e);
1487	>	if (e != null)
1488	>	m.deleteEntry(e);
1489	>	return result;
1490		}
1491
1492		// Views
#	Line 1438 | Line 1494 | public class TreeMap<K,V>
1494		transient EntrySetView entrySetView = null;
1495		transient KeySet<K> navigableKeySetView = null;
1496
1497	+	public final NavigableSet<K> navigableKeySet() {
1498	+	KeySet<K> nksv = navigableKeySetView;
1499	+	return (nksv != null) ? nksv :
1500	+	(navigableKeySetView = new TreeMap.KeySet(this));
1501	+	}
1502	+
1503	+	public final Set<K> keySet() {
1504	+	return navigableKeySet();
1505	+	}
1506	+
1507	+	public NavigableSet<K> descendingKeySet() {
1508	+	return descendingMap().navigableKeySet();
1509	+	}
1510	+
1511	+	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1512	+	return subMap(fromKey, true, toKey, false);
1513	+	}
1514	+
1515	+	public final SortedMap<K,V> headMap(K toKey) {
1516	+	return headMap(toKey, false);
1517	+	}
1518	+
1519	+	public final SortedMap<K,V> tailMap(K fromKey) {
1520	+	return tailMap(fromKey, true);
1521	+	}
1522	+
1523	+	// View classes
1524	+
1525		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1526		private transient int size = -1, sizeModCount;
1527
#	Line 1457 | Line 1541 | public class TreeMap<K,V>
1541		}
1542
1543		public boolean isEmpty() {
1544	<	TreeMap.Entry<K,V> n = loEntry();
1544	>	TreeMap.Entry<K,V> n = absLowest();
1545		return n == null || tooHigh(n.key);
1546		}
1547
#	Line 1489 | Line 1573 | public class TreeMap<K,V>
1573		}
1574		}
1575
1492	–	public NavigableSet<K> navigableKeySet() {
1493	–	KeySet<K> nksv = navigableKeySetView;
1494	–	return (nksv != null) ? nksv :
1495	–	(navigableKeySetView = new TreeMap.KeySet(this));
1496	–	}
1497	–
1498	–	public Set<K> keySet() {
1499	–	return navigableKeySet();
1500	–	}
1501	–
1502	–	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1503	–	return subMap(fromKey, true, toKey, false);
1504	–	}
1505	–
1506	–	public SortedMap<K,V> headMap(K toKey) {
1507	–	return headMap(toKey, false);
1508	–	}
1509	–
1510	–	public SortedMap<K,V> tailMap(K fromKey) {
1511	–	return tailMap(fromKey, true);
1512	–	}
1513	–
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
1517	–	// in DescendingSubMap rely on those for AscendingSubMap.
1518	–
1519	–	/**
1520	–	* Returns the entry corresponding to the ceiling of the specified
1521	–	* key from the perspective of this submap, or null if the submap
1522	–	* contains no such entry.
1523	–	*/
1524	–	TreeMap.Entry<K,V> subCeiling(K key) {
1525	–	if (tooLow(key))
1526	–	return loEntry();
1527	–	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1528	–	return (e == null || tooHigh(e.key)) ? null : e;
1529	–	}
1530	–
1531	–	/**
1532	–	* Returns the entry corresponding to the higher of the specified
1533	–	* key from the perspective of this submap, or null if the submap
1534	–	* contains no such entry.
1535	–	*/
1536	–	TreeMap.Entry<K,V> subHigher(K key) {
1537	–	if (tooLow(key))
1538	–	return loEntry();
1539	–	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1540	–	return (e == null || tooHigh(e.key)) ? null : e;
1541	–	}
1542	–
1543	–	/**
1544	–	* Returns the entry corresponding to the floor of the specified
1545	–	* key from the perspective of this submap, or null if the submap
1546	–	* contains no such entry.
1547	–	*/
1548	–	TreeMap.Entry<K,V> subFloor(K key) {
1549	–	if (tooHigh(key))
1550	–	return hiEntry();
1551	–	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1552	–	return (e == null || tooLow(e.key)) ? null : e;
1553	–	}
1554	–
1555	–	/**
1556	–	* Returns the entry corresponding to the lower of the specified
1557	–	* key from the perspective of this submap, or null if the submap
1558	–	* contains no such entry.
1559	–	*/
1560	–	TreeMap.Entry<K,V> subLower(K key) {
1561	–	if (tooHigh(key))
1562	–	return hiEntry();
1563	–	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1564	–	return (e == null || tooLow(e.key)) ? null : e;
1565	–	}
1566	–
1576		/**
1577		* Iterators for SubMaps
1578		*/
#	Line 1640 | Line 1649 | public class TreeMap<K,V>
1649
1650		final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1651		DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1652	<	TreeMap.Entry<K,V> lastExcluded) {
1653	<	super(last, lastExcluded);
1652	>	TreeMap.Entry<K,V> fence) {
1653	>	super(last, fence);
1654		}
1655
1656		public Map.Entry<K,V> next() {
#	Line 1651 | Line 1660 | public class TreeMap<K,V>
1660
1661		final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1662		DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1663	<	TreeMap.Entry<K,V> lastExcluded) {
1664	<	super(last, lastExcluded);
1663	>	TreeMap.Entry<K,V> fence) {
1664	>	super(last, fence);
1665		}
1666		public K next() {
1667		return prevEntry().key;
#	Line 1660 | Line 1669 | public class TreeMap<K,V>
1669		}
1670		}
1671
1672	<	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1672	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1673		private static final long serialVersionUID = 912986545866124060L;
1674
1675		AscendingSubMap(TreeMap<K,V> m,
1676	<	boolean fromStart, K lo, int loExcluded,
1677	<	boolean toEnd, K hi, int hiExcluded) {
1678	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1676	>	boolean fromStart, K lo, boolean loInclusive,
1677	>	boolean toEnd, K hi, boolean hiInclusive) {
1678	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1679		}
1680
1681		public Comparator<? super K> comparator() {
#	Line 1680 | Line 1689 | public class TreeMap<K,V>
1689		if (!inRange(toKey, toInclusive))
1690		throw new IllegalArgumentException("toKey out of range");
1691		return new AscendingSubMap(m,
1692	<	false, fromKey, excluded(fromInclusive),
1693	<	false, toKey,   excluded(toInclusive));
1692	>	false, fromKey, fromInclusive,
1693	>	false, toKey,   toInclusive);
1694		}
1695
1696		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1697		if (!inClosedRange(toKey))
1698		throw new IllegalArgumentException("toKey out of range");
1699		return new AscendingSubMap(m,
1700	<	fromStart, lo,    loExcluded,
1701	<	false,     toKey, excluded(inclusive));
1700	>	fromStart, lo,    loInclusive,
1701	>	false,     toKey, inclusive);
1702		}
1703
1704		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1705		if (!inRange(fromKey, inclusive))
1706		throw new IllegalArgumentException("fromKey out of range");
1707		return new AscendingSubMap(m,
1708	<	false, fromKey, excluded(inclusive),
1709	<	toEnd, hi,      hiExcluded);
1708	>	false, fromKey, inclusive,
1709	>	toEnd, hi,      hiInclusive);
1710	>	}
1711	>
1712	>	public NavigableMap<K,V> descendingMap() {
1713	>	NavigableMap<K,V> mv = descendingMapView;
1714	>	return (mv != null) ? mv :
1715	>	(descendingMapView =
1716	>	new DescendingSubMap(m,
1717	>	fromStart, lo, loInclusive,
1718	>	toEnd,     hi, hiInclusive));
1719		}
1720
1721		Iterator<K> keyIterator() {
1722	<	return new SubMapKeyIterator(loEntry(), hiFence());
1722	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1723		}
1724
1725		Iterator<K> descendingKeyIterator() {
1726	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1726	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1727		}
1728
1729	<	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1729	>	final class AscendingEntrySetView extends EntrySetView {
1730		public Iterator<Map.Entry<K,V>> iterator() {
1731	<	return new SubMapEntryIterator(loEntry(), hiFence());
1731	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1732		}
1733		}
1734
#	Line 1719 | Line 1737 | public class TreeMap<K,V>
1737		return (es != null) ? es : new AscendingEntrySetView();
1738		}
1739
1740	<	public K firstKey() {
1741	<	return key(loEntry());
1742	<	}
1743	<
1744	<	public K lastKey() {
1745	<	return key(hiEntry());
1728	<	}
1729	<
1730	<	public Map.Entry<K,V> firstEntry() {
1731	<	return loEntry();
1732	<	}
1733	<
1734	<	public Map.Entry<K,V> lastEntry() {
1735	<	return hiEntry();
1736	<	}
1737	<
1738	<	public Map.Entry<K,V> pollFirstEntry() {
1739	<	return pollLoEntry();
1740	<	}
1741	<
1742	<	public Map.Entry<K,V> pollLastEntry() {
1743	<	return pollHiEntry();
1744	<	}
1745	<
1746	<	public NavigableMap<K,V> descendingMap() {
1747	<	NavigableMap<K,V> mv = descendingMapView;
1748	<	return (mv != null) ? mv :
1749	<	(descendingMapView =
1750	<	new DescendingSubMap(m,
1751	<	fromStart, lo, loExcluded,
1752	<	toEnd,     hi, hiExcluded));
1753	<	}
1740	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1741	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1742	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1743	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1744	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1745	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1746		}
1747
1748	<	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1748	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1749		private static final long serialVersionUID = 912986545866120460L;
1750		DescendingSubMap(TreeMap<K,V> m,
1751	<	boolean fromStart, K lo, int loExcluded,
1752	<	boolean toEnd, K hi, int hiExcluded) {
1753	<	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1751	>	boolean fromStart, K lo, boolean loInclusive,
1752	>	boolean toEnd, K hi, boolean hiInclusive) {
1753	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1754		}
1755
1756		private final Comparator<? super K> reverseComparator =
#	Line 1775 | Line 1767 | public class TreeMap<K,V>
1767		if (!inRange(toKey, toInclusive))
1768		throw new IllegalArgumentException("toKey out of range");
1769		return new DescendingSubMap(m,
1770	<	false, toKey,   excluded(toInclusive),
1771	<	false, fromKey, excluded(fromInclusive));
1770	>	false, toKey,   toInclusive,
1771	>	false, fromKey, fromInclusive);
1772		}
1773
1774		public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1775		if (!inRange(toKey, inclusive))
1776		throw new IllegalArgumentException("toKey out of range");
1777		return new DescendingSubMap(m,
1778	<	false, toKey, excluded(inclusive),
1779	<	toEnd, hi,    hiExcluded);
1778	>	false, toKey, inclusive,
1779	>	toEnd, hi,    hiInclusive);
1780		}
1781
1782		public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1783		if (!inRange(fromKey, inclusive))
1784		throw new IllegalArgumentException("fromKey out of range");
1785		return new DescendingSubMap(m,
1786	<	fromStart, lo, loExcluded,
1787	<	false, fromKey, excluded(inclusive));
1796	<	}
1797	<
1798	<	Iterator<K> keyIterator() {
1799	<	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1800	<	}
1801	<
1802	<	Iterator<K> descendingKeyIterator() {
1803	<	return new SubMapKeyIterator(loEntry(), hiFence());
1804	<	}
1805	<
1806	<	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1807	<	public Iterator<Map.Entry<K,V>> iterator() {
1808	<	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1809	<	}
1810	<	}
1811	<
1812	<	public Set<Map.Entry<K,V>> entrySet() {
1813	<	EntrySetView es = entrySetView;
1814	<	return (es != null) ? es : new DescendingEntrySetView();
1815	<	}
1816	<
1817	<	public K firstKey() {
1818	<	return key(hiEntry());
1819	<	}
1820	<
1821	<	public K lastKey() {
1822	<	return key(loEntry());
1823	<	}
1824	<
1825	<	public Map.Entry<K,V> firstEntry() {
1826	<	return hiEntry();
1827	<	}
1828	<
1829	<	public Map.Entry<K,V> lastEntry() {
1830	<	return loEntry();
1831	<	}
1832	<
1833	<	public Map.Entry<K,V> pollFirstEntry() {
1834	<	return pollHiEntry();
1835	<	}
1836	<
1837	<	public Map.Entry<K,V> pollLastEntry() {
1838	<	return pollLoEntry();
1786	>	fromStart, lo, loInclusive,
1787	>	false, fromKey, inclusive);
1788		}
1789
1790		public NavigableMap<K,V> descendingMap() {
#	Line 1843 | Line 1792 | public class TreeMap<K,V>
1792		return (mv != null) ? mv :
1793		(descendingMapView =
1794		new AscendingSubMap(m,
1795	<	fromStart, lo, loExcluded,
1796	<	toEnd, hi, hiExcluded));
1795	>	fromStart, lo, loInclusive,
1796	>	toEnd,     hi, hiInclusive));
1797		}
1798
1799	<	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1800	<	return super.subFloor(key);
1799	>	Iterator<K> keyIterator() {
1800	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1801		}
1802
1803	<	@Override TreeMap.Entry<K,V> subHigher(K key) {
1804	<	return super.subLower(key);
1803	>	Iterator<K> descendingKeyIterator() {
1804	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1805		}
1806
1807	<	@Override TreeMap.Entry<K,V> subFloor(K key) {
1808	<	return super.subCeiling(key);
1807	>	final class DescendingEntrySetView extends EntrySetView {
1808	>	public Iterator<Map.Entry<K,V>> iterator() {
1809	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1810	>	}
1811		}
1812
1813	<	@Override TreeMap.Entry<K,V> subLower(K key) {
1814	<	return super.subHigher(key);
1813	>	public Set<Map.Entry<K,V>> entrySet() {
1814	>	EntrySetView es = entrySetView;
1815	>	return (es != null) ? es : new DescendingEntrySetView();
1816		}
1865	–	}
1866	–
1867	–	/**
1868	–	* Compares two keys using the correct comparison method for this TreeMap.
1869	–	*/
1870	–	final int compare(Object k1, Object k2) {
1871	–	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1872	–	: comparator.compare((K)k1, (K)k2);
1873	–	}
1817
1818	<	/**
1819	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1820	<	* that it copes with <tt>null</tt> o1 properly.
1821	<	*/
1822	<	final static boolean valEquals(Object o1, Object o2) {
1823	<	return (o1==null ? o2==null : o1.equals(o2));
1818	>	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1819	>	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1820	>	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1821	>	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1822	>	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1823	>	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1824		}
1825
1826		/**
#	Line 1894 | Line 1837 | public class TreeMap<K,V>
1837		private K fromKey, toKey;
1838		private Object readResolve() {
1839		return new AscendingSubMap(TreeMap.this,
1840	<	fromStart, fromKey, 0,
1841	<	toEnd, toKey, 1);
1840	>	fromStart, fromKey, true,
1841	>	toEnd, toKey, false);
1842		}
1843		public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1844		public K lastKey() { throw new InternalError(); }
#	Line 1907 | 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 2082 | 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 2099 | 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 2115 | 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 2164 | 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 2210 | 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 2318 | 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