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.22 by jsr166, Fri Jun 24 20:44:49 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 643 | Line 645 | public class TreeMap<K,V>
645
646		// NavigableMap API methods
647
648	+	/**
649	+	* @since 1.6
650	+	*/
651		public Map.Entry<K,V> firstEntry() {
652		Entry<K,V> e = getFirstEntry();
653	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
653	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
654		}
655
656	+	/**
657	+	* @since 1.6
658	+	*/
659		public Map.Entry<K,V> lastEntry() {
660		Entry<K,V> e = getLastEntry();
661	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
661	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
662		}
663
664	+	/**
665	+	* @since 1.6
666	+	*/
667		public Map.Entry<K,V> pollFirstEntry() {
668		Entry<K,V> p = getFirstEntry();
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		}
675
676	+	/**
677	+	* @since 1.6
678	+	*/
679		public Map.Entry<K,V> pollLastEntry() {
680		Entry<K,V> p = getLastEntry();
681		if (p == null)
682		return null;
683	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
683	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
684		deleteEntry(p);
685		return result;
686		}
#	Line 676 | Line 690 | public class TreeMap<K,V>
690		* @throws NullPointerException if the specified key is null
691		*         and this map uses natural ordering, or its comparator
692		*         does not permit null keys
693	+	* @since 1.6
694		*/
695		public Map.Entry<K,V> lowerEntry(K key) {
696		Entry<K,V> e =  getLowerEntry(key);
697	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
697	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
698		}
699
700		/**
#	Line 687 | Line 702 | public class TreeMap<K,V>
702		* @throws NullPointerException if the specified key is null
703		*         and this map uses natural ordering, or its comparator
704		*         does not permit null keys
705	+	* @since 1.6
706		*/
707		public K lowerKey(K key) {
708		Entry<K,V> e =  getLowerEntry(key);
#	Line 698 | Line 714 | public class TreeMap<K,V>
714		* @throws NullPointerException if the specified key is null
715		*         and this map uses natural ordering, or its comparator
716		*         does not permit null keys
717	+	* @since 1.6
718		*/
719		public Map.Entry<K,V> floorEntry(K key) {
720		Entry<K,V> e = getFloorEntry(key);
721	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
721	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
722		}
723
724		/**
#	Line 709 | Line 726 | public class TreeMap<K,V>
726		* @throws NullPointerException if the specified key is null
727		*         and this map uses natural ordering, or its comparator
728		*         does not permit null keys
729	+	* @since 1.6
730		*/
731		public K floorKey(K key) {
732		Entry<K,V> e = getFloorEntry(key);
#	Line 720 | Line 738 | public class TreeMap<K,V>
738		* @throws NullPointerException if the specified key is null
739		*         and this map uses natural ordering, or its comparator
740		*         does not permit null keys
741	+	* @since 1.6
742		*/
743		public Map.Entry<K,V> ceilingEntry(K key) {
744		Entry<K,V> e = getCeilingEntry(key);
745	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
745	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
746		}
747
748		/**
#	Line 731 | Line 750 | public class TreeMap<K,V>
750		* @throws NullPointerException if the specified key is null
751		*         and this map uses natural ordering, or its comparator
752		*         does not permit null keys
753	+	* @since 1.6
754		*/
755		public K ceilingKey(K key) {
756		Entry<K,V> e = getCeilingEntry(key);
#	Line 742 | Line 762 | public class TreeMap<K,V>
762		* @throws NullPointerException if the specified key is null
763		*         and this map uses natural ordering, or its comparator
764		*         does not permit null keys
765	+	* @since 1.6
766		*/
767		public Map.Entry<K,V> higherEntry(K key) {
768		Entry<K,V> e = getHigherEntry(key);
769	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
769	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
770		}
771
772		/**
#	Line 753 | Line 774 | public class TreeMap<K,V>
774		* @throws NullPointerException if the specified key is null
775		*         and this map uses natural ordering, or its comparator
776		*         does not permit null keys
777	+	* @since 1.6
778		*/
779		public K higherKey(K key) {
780		Entry<K,V> e = getHigherEntry(key);
#	Line 780 | Line 802 | public class TreeMap<K,V>
802		* the iteration are undefined.  The set supports element removal,
803		* which removes the corresponding mapping from the map, via the
804		* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
805	<	* <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt>
806	<	* operations.  It does not support the add or <tt>addAll</tt>
805	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
806	>	* operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
807		* operations.
808		*/
809		public Set<K> keySet() {
#	Line 826 | Line 848 | public class TreeMap<K,V>
848		* mapping from the map, via the <tt>Iterator.remove</tt>,
849		* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
850		* <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
851	<	* support the add or <tt>addAll</tt> operations.
851	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
852		*/
853		public Collection<V> values() {
854		Collection<V> vs = values;
#	Line 920 | Line 942 | public class TreeMap<K,V>
942		}
943		}
944
945	+	/**
946	+	* @since 1.6
947	+	*/
948		public Set<Map.Entry<K,V>> descendingEntrySet() {
949		Set<Map.Entry<K,V>> es = descendingEntrySet;
950		return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
#	Line 931 | Line 956 | public class TreeMap<K,V>
956		}
957		}
958
959	+	/**
960	+	* @since 1.6
961	+	*/
962		public Set<K> descendingKeySet() {
963		Set<K> ks = descendingKeySet;
964		return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
#	Line 948 | Line 976 | public class TreeMap<K,V>
976		*         null and this map uses natural ordering, or its comparator
977		*         does not permit null keys
978		* @throws IllegalArgumentException {@inheritDoc}
979	+	* @since 1.6
980		*/
981		public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
982		return new SubMap(fromKey, toKey);
#	Line 959 | Line 988 | public class TreeMap<K,V>
988		*         and this map uses natural ordering, or its comparator
989		*         does not permit null keys
990		* @throws IllegalArgumentException {@inheritDoc}
991	+	* @since 1.6
992		*/
993		public NavigableMap<K,V> navigableHeadMap(K toKey) {
994		return new SubMap(toKey, true);
#	Line 970 | Line 1000 | public class TreeMap<K,V>
1000		*         and this map uses natural ordering, or its comparator
1001		*         does not permit null keys
1002		* @throws IllegalArgumentException {@inheritDoc}
1003	+	* @since 1.6
1004		*/
1005		public NavigableMap<K,V> navigableTailMap(K fromKey) {
1006		return new SubMap(fromKey, false);
#	Line 1066 | Line 1097 | public class TreeMap<K,V>
1097		}
1098
1099		public boolean containsKey(Object key) {
1100	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1100	>	return inRange(key) && TreeMap.this.containsKey(key);
1101		}
1102
1103		public V get(Object key) {
1104	<	if (!inRange((K) key))
1104	>	if (!inRange(key))
1105		return null;
1106		return TreeMap.this.get(key);
1107		}
#	Line 1082 | Line 1113 | public class TreeMap<K,V>
1113		}
1114
1115		public V remove(Object key) {
1116	<	if (!inRange((K) key))
1116	>	if (!inRange(key))
1117		return null;
1118		return TreeMap.this.remove(key);
1119		}
#	Line 1128 | Line 1159 | public class TreeMap<K,V>
1159		getFirstEntry() : getCeilingEntry(fromKey);
1160		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1161		return null;
1162	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1162	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1163		deleteEntry(e);
1164		return result;
1165		}
#	Line 1138 | Line 1169 | public class TreeMap<K,V>
1169		getLastEntry() : getLowerEntry(toKey);
1170		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1171		return null;
1172	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1172	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1173		deleteEntry(e);
1174		return result;
1175		}
#	Line 1153 | Line 1184 | public class TreeMap<K,V>
1184
1185		public Map.Entry<K,V> ceilingEntry(K key) {
1186		TreeMap.Entry<K,V> e = subceiling(key);
1187	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1187	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1188		}
1189
1190		public K ceilingKey(K key) {
#	Line 1172 | Line 1203 | public class TreeMap<K,V>
1203
1204		public Map.Entry<K,V> higherEntry(K key) {
1205		TreeMap.Entry<K,V> e = subhigher(key);
1206	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1206	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1207		}
1208
1209		public K higherKey(K key) {
#	Line 1190 | Line 1221 | public class TreeMap<K,V>
1221
1222		public Map.Entry<K,V> floorEntry(K key) {
1223		TreeMap.Entry<K,V> e = subfloor(key);
1224	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1224	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1225		}
1226
1227		public K floorKey(K key) {
#	Line 1208 | Line 1239 | public class TreeMap<K,V>
1239
1240		public Map.Entry<K,V> lowerEntry(K key) {
1241		TreeMap.Entry<K,V> e = sublower(key);
1242	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1242	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1243		}
1244
1245		public K lowerKey(K key) {
#	Line 1351 | Line 1382 | public class TreeMap<K,V>
1382		return navigableTailMap(fromKey);
1383		}
1384
1385	<	private boolean inRange(K key) {
1385	>	private boolean inRange(Object key) {
1386		return (fromStart || compare(key, fromKey) >= 0) &&
1387		(toEnd     || compare(key, toKey)   <  0);
1388		}
1389
1390		// This form allows the high endpoint (as well as all legit keys)
1391	<	private boolean inRange2(K key) {
1391	>	private boolean inRange2(Object key) {
1392		return (fromStart || compare(key, fromKey) >= 0) &&
1393		(toEnd     || compare(key, toKey)   <= 0);
1394		}
#	Line 1513 | Line 1544 | public class TreeMap<K,V>
1544		/**
1545		* Compares two keys using the correct comparison method for this TreeMap.
1546		*/
1547	<	private int compare(K k1, K k2) {
1548	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1549	<	: comparator.compare(k1, k2);
1547	>	private int compare(Object k1, Object k2) {
1548	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1549	>	: comparator.compare((K)k1, (K)k2);
1550		}
1551
1552		/**
1553	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1553	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1554		* that it copes with <tt>null</tt> o1 properly.
1555		*/
1556		private static boolean valEquals(Object o1, Object o2) {

Diff Legend

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