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.14 by jsr166, Mon May 16 08:13:36 2005 UTC vs.
Revision 1.21 by jsr166, Fri Jun 24 00:26:57 2005 UTC

#	Line 6 | Line 6
6		*/
7
8		package java.util;
9	+	import java.util.*; // for javadoc (till 6280605 is fixed)
10
11		/**
12		* A Red-Black tree based {@link NavigableMap} implementation.
#	Line 216 | Line 217 | public class TreeMap<K,V>
217		* specified value.  More formally, returns <tt>true</tt> if and only if
218		* this map contains at least one mapping to a value <tt>v</tt> such
219		* that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
220	<	* operation requires time linear in the map size.
220	>	* operation will probably require time linear in the map size for
221	>	* most implementations.
222		*
223		* @param value value whose presence in this map is to be tested
224		* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
#	Line 253 | Line 255 | public class TreeMap<K,V>
255		* <tt>null</tt> if the map contains no mapping for the key.  A return
256		* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
257		* map contains no mapping for the key; it's also possible that the map
258	<	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey}
259	<	* operation may be used to distinguish these two cases.
258	>	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey
259	>	* containsKey} operation may be used to distinguish these two cases.
260		*
261		* @param key key whose associated value is to be returned
262		* @return the value to which this map maps the specified key, or
#	Line 519 | Line 521 | public class TreeMap<K,V>
521
522		/**
523		* Associates the specified value with the specified key in this map.
524	<	* If the map previously contained a mapping for this key, the old
524	>	* If the map previously contained a mapping for the key, the old
525		* value is replaced.
526		*
527		* @param key key with which the specified value is to be associated
#	Line 645 | Line 647 | public class TreeMap<K,V>
647
648		public Map.Entry<K,V> firstEntry() {
649		Entry<K,V> e = getFirstEntry();
650	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
650	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
651		}
652
653		public Map.Entry<K,V> lastEntry() {
654		Entry<K,V> e = getLastEntry();
655	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
655	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
656		}
657
658		public Map.Entry<K,V> pollFirstEntry() {
659		Entry<K,V> p = getFirstEntry();
660		if (p == null)
661		return null;
662	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
662	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
663		deleteEntry(p);
664		return result;
665		}
#	Line 666 | Line 668 | public class TreeMap<K,V>
668		Entry<K,V> p = getLastEntry();
669		if (p == null)
670		return null;
671	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
671	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
672		deleteEntry(p);
673		return result;
674		}
#	Line 679 | Line 681 | public class TreeMap<K,V>
681		*/
682		public Map.Entry<K,V> lowerEntry(K key) {
683		Entry<K,V> e =  getLowerEntry(key);
684	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
684	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
685		}
686
687		/**
#	Line 701 | Line 703 | public class TreeMap<K,V>
703		*/
704		public Map.Entry<K,V> floorEntry(K key) {
705		Entry<K,V> e = getFloorEntry(key);
706	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
706	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
707		}
708
709		/**
#	Line 723 | Line 725 | public class TreeMap<K,V>
725		*/
726		public Map.Entry<K,V> ceilingEntry(K key) {
727		Entry<K,V> e = getCeilingEntry(key);
728	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
728	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
729		}
730
731		/**
#	Line 745 | Line 747 | public class TreeMap<K,V>
747		*/
748		public Map.Entry<K,V> higherEntry(K key) {
749		Entry<K,V> e = getHigherEntry(key);
750	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
750	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
751		}
752
753		/**
#	Line 780 | Line 782 | public class TreeMap<K,V>
782		* the iteration are undefined.  The set supports element removal,
783		* which removes the corresponding mapping from the map, via the
784		* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
785	<	* <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt>
786	<	* operations.  It does not support the add or <tt>addAll</tt>
785	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
786	>	* operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
787		* operations.
788		*/
789		public Set<K> keySet() {
#	Line 826 | Line 828 | public class TreeMap<K,V>
828		* mapping from the map, via the <tt>Iterator.remove</tt>,
829		* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
830		* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
831	<	* support the add or <tt>addAll</tt> operations.
831	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
832		*/
833		public Collection<V> values() {
834		Collection<V> vs = values;
#	Line 1066 | Line 1068 | public class TreeMap<K,V>
1068		}
1069
1070		public boolean containsKey(Object key) {
1071	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1071	>	return inRange(key) && TreeMap.this.containsKey(key);
1072		}
1073
1074		public V get(Object key) {
1075	<	if (!inRange((K) key))
1075	>	if (!inRange(key))
1076		return null;
1077		return TreeMap.this.get(key);
1078		}
#	Line 1082 | Line 1084 | public class TreeMap<K,V>
1084		}
1085
1086		public V remove(Object key) {
1087	<	if (!inRange((K) key))
1087	>	if (!inRange(key))
1088		return null;
1089		return TreeMap.this.remove(key);
1090		}
#	Line 1128 | Line 1130 | public class TreeMap<K,V>
1130		getFirstEntry() : getCeilingEntry(fromKey);
1131		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1132		return null;
1133	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1133	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1134		deleteEntry(e);
1135		return result;
1136		}
#	Line 1138 | Line 1140 | public class TreeMap<K,V>
1140		getLastEntry() : getLowerEntry(toKey);
1141		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1142		return null;
1143	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1143	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1144		deleteEntry(e);
1145		return result;
1146		}
#	Line 1153 | Line 1155 | public class TreeMap<K,V>
1155
1156		public Map.Entry<K,V> ceilingEntry(K key) {
1157		TreeMap.Entry<K,V> e = subceiling(key);
1158	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1158	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1159		}
1160
1161		public K ceilingKey(K key) {
#	Line 1172 | Line 1174 | public class TreeMap<K,V>
1174
1175		public Map.Entry<K,V> higherEntry(K key) {
1176		TreeMap.Entry<K,V> e = subhigher(key);
1177	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1177	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1178		}
1179
1180		public K higherKey(K key) {
#	Line 1190 | Line 1192 | public class TreeMap<K,V>
1192
1193		public Map.Entry<K,V> floorEntry(K key) {
1194		TreeMap.Entry<K,V> e = subfloor(key);
1195	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1195	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1196		}
1197
1198		public K floorKey(K key) {
#	Line 1208 | Line 1210 | public class TreeMap<K,V>
1210
1211		public Map.Entry<K,V> lowerEntry(K key) {
1212		TreeMap.Entry<K,V> e = sublower(key);
1213	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1213	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1214		}
1215
1216		public K lowerKey(K key) {
#	Line 1351 | Line 1353 | public class TreeMap<K,V>
1353		return navigableTailMap(fromKey);
1354		}
1355
1356	<	private boolean inRange(K key) {
1356	>	private boolean inRange(Object key) {
1357		return (fromStart || compare(key, fromKey) >= 0) &&
1358		(toEnd     || compare(key, toKey)   <  0);
1359		}
1360
1361		// This form allows the high endpoint (as well as all legit keys)
1362	<	private boolean inRange2(K key) {
1362	>	private boolean inRange2(Object key) {
1363		return (fromStart || compare(key, fromKey) >= 0) &&
1364		(toEnd     || compare(key, toKey)   <= 0);
1365		}
#	Line 1513 | Line 1515 | public class TreeMap<K,V>
1515		/**
1516		* Compares two keys using the correct comparison method for this TreeMap.
1517		*/
1518	<	private int compare(K k1, K k2) {
1519	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1520	<	: comparator.compare(k1, k2);
1518	>	private int compare(Object k1, Object k2) {
1519	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1520	>	: comparator.compare((K)k1, (K)k2);
1521		}
1522
1523		/**
1524	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1524	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1525		* that it copes with <tt>null</tt> o1 properly.
1526		*/
1527		private static boolean valEquals(Object o1, Object o2) {

Diff Legend

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