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.1 by dl, Tue Dec 28 12:14:07 2004 UTC vs.
Revision 1.8 by dl, Sat Apr 2 11:29:42 2005 UTC

#	Line 5 | Line 5
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
8	<	package java.util;
8	>	package java.util;
9
10
11		/**
12		* Red-Black tree based implementation of the <tt>NavigableMap</tt> interface.
13		* This class guarantees that the map will be in ascending key order, sorted
14	<	* according to the <i>natural order</i> for the key's class (see
14	>	* according to the <i>natural order</i> for the keys' class (see
15		* <tt>Comparable</tt>), or by the comparator provided at creation time,
16		* depending on which constructor is used.<p>
17		*
#	Line 61 | Line 61 | package java.util;
61		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
62		* Therefore, it would be wrong to write a program that depended on this
63		* exception for its correctness:   <i>the fail-fast behavior of iterators
64	<	* should be used only to detect bugs.</i><p>
64	>	* should be used only to detect bugs.</i>
65		*
66		* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
67		* and its views represent snapshots of mappings at the time they were
#	Line 203 | Line 203 | public class TreeMap<K,V>
203		*            specified key.
204		* @throws ClassCastException if the key cannot be compared with the keys
205		*                  currently in the map.
206	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
206	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
207		*                  natural ordering, or its comparator does not tolerate
208		*            <tt>null</tt> keys.
209		*/
#	Line 260 | Line 260 | public class TreeMap<K,V>
260		* @param key key whose associated value is to be returned.
261		* @return the value to which this map maps the specified key, or
262		*               <tt>null</tt> if the map contains no mapping for the key.
263	<	* @throws    ClassCastException key cannot be compared with the keys
263	>	* @throws    ClassCastException if key cannot be compared with the keys
264		*                  currently in the map.
265	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
265	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
266		*                  natural ordering, or its comparator does not tolerate
267		*                  <tt>null</tt> keys.
268		*
#	Line 343 | Line 343 | public class TreeMap<K,V>
343		*                does not contain an entry for the key.
344		* @throws ClassCastException if the key cannot be compared with the keys
345		*                  currently in the map.
346	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
346	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
347		*                  natural order, or its comparator does not tolerate *
348		*                  <tt>null</tt> keys.
349		*/
#	Line 542 | Line 542 | public class TreeMap<K,V>
542		* @param key key with which the specified value is to be associated.
543		* @param value value to be associated with the specified key.
544		*
545	<	* @return previous value associated with specified key, or <tt>null</tt>
545	>	* @return the previous value associated with specified key, or <tt>null</tt>
546		*         if there was no mapping for key.  A <tt>null</tt> return can
547		*         also indicate that the map previously associated <tt>null</tt>
548		*         with the specified key.
549	<	* @throws    ClassCastException key cannot be compared with the keys
549	>	* @throws    ClassCastException if key cannot be compared with the keys
550		*            currently in the map.
551	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
551	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
552		*         natural order, or its comparator does not tolerate
553		*         <tt>null</tt> keys.
554		*/
#	Line 559 | Line 559 | public class TreeMap<K,V>
559		incrementSize();
560		root = new Entry<K,V>(key, value, null);
561		return null;
562	<	}
562	>	}
563
564		while (true) {
565		int cmp = compare(key, t.key);
#	Line 591 | Line 591 | public class TreeMap<K,V>
591		* Removes the mapping for this key from this TreeMap if present.
592		*
593		* @param  key key for which mapping should be removed
594	<	* @return previous value associated with specified key, or <tt>null</tt>
594	>	* @return the previous value associated with specified key, or <tt>null</tt>
595		*         if there was no mapping for key.  A <tt>null</tt> return can
596		*         also indicate that the map previously associated
597		*         <tt>null</tt> with the specified key.
598		*
599	<	* @throws    ClassCastException key cannot be compared with the keys
599	>	* @throws    ClassCastException if key cannot be compared with the keys
600		*            currently in the map.
601	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
601	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
602		*         natural order, or its comparator does not tolerate
603		*         <tt>null</tt> keys.
604		*/
#	Line 658 | Line 658 | public class TreeMap<K,V>
658		/**
659		* Returns a key-value mapping associated with the least
660		* key in this map, or <tt>null</tt> if the map is empty.
661	<	*
662	<	* @return an Entry with least key, or <tt>null</tt>
661	>	*
662	>	* @return an Entry with least key, or <tt>null</tt>
663		* if the map is empty.
664		*/
665		public Map.Entry<K,V> firstEntry() {
666		Entry<K,V> e = getFirstEntry();
667	<	return (e == null)? null : new SnapshotEntry(e);
667	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
668		}
669
670		/**
671		* Returns a key-value mapping associated with the greatest
672		* key in this map, or <tt>null</tt> if the map is empty.
673	<	* The returned entry does <em>not</em> support
674	<	* the <tt>Entry.setValue</tt> method.
675	<	*
673	>	*
674		* @return an Entry with greatest key, or <tt>null</tt>
675		* if the map is empty.
676		*/
677		public Map.Entry<K,V> lastEntry() {
678		Entry<K,V> e = getLastEntry();
679	<	return (e == null)? null : new SnapshotEntry(e);
679	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
680		}
681
682		/**
683		* Removes and returns a key-value mapping associated with
684		* the least key in this map, or <tt>null</tt> if the map is empty.
685	<	*
685	>	*
686		* @return the removed first entry of this map, or <tt>null</tt>
687		* if the map is empty.
688		*/
689		public Map.Entry<K,V> pollFirstEntry() {
690		Entry<K,V> p = getFirstEntry();
691	<	if (p == null)
691	>	if (p == null)
692		return null;
693	<	Map.Entry result = new SnapshotEntry(p);
693	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
694		deleteEntry(p);
695		return result;
696		}
#	Line 700 | Line 698 | public class TreeMap<K,V>
698		/**
699		* Removes and returns a key-value mapping associated with
700		* the greatest key in this map, or <tt>null</tt> if the map is empty.
701	<	*
701	>	*
702		* @return the removed last entry of this map, or <tt>null</tt>
703		* if the map is empty.
704		*/
705		public Map.Entry<K,V> pollLastEntry() {
706		Entry<K,V> p = getLastEntry();
707	<	if (p == null)
707	>	if (p == null)
708		return null;
709	<	Map.Entry result = new SnapshotEntry(p);
709	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
710		deleteEntry(p);
711		return result;
712		}
#	Line 716 | Line 714 | public class TreeMap<K,V>
714		/**
715		* Returns a key-value mapping associated with the least key
716		* greater than or equal to the given key, or <tt>null</tt> if
717	<	* there is no such entry.
718	<	*
717	>	* there is no such entry.
718	>	*
719		* @param key the key.
720		* @return an Entry associated with ceiling of given key, or
721		* <tt>null</tt> if there is no such Entry.
722		* @throws ClassCastException if key cannot be compared with the
723		* keys currently in the map.
724	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
724	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
725		*         natural order, or its comparator does not tolerate
726		*         <tt>null</tt> keys.
727		*/
728		public Map.Entry<K,V> ceilingEntry(K key) {
729		Entry<K,V> e = getCeilingEntry(key);
730	<	return (e == null)? null : new SnapshotEntry(e);
730	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
731		}
732
733
734		/**
735		* Returns least key greater than or equal to the given key, or
736		* <tt>null</tt> if there is no such key.
737	<	*
737	>	*
738		* @param key the key.
739		* @return the ceiling key, or <tt>null</tt>
740		* if there is no such key.
741		* @throws ClassCastException if key cannot be compared with the keys
742		*            currently in the map.
743	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
743	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
744		*         natural order, or its comparator does not tolerate
745		*         <tt>null</tt> keys.
746		*/
#	Line 756 | Line 754 | public class TreeMap<K,V>
754		/**
755		* Returns a key-value mapping associated with the greatest key
756		* less than or equal to the given key, or <tt>null</tt> if there
757	<	* is no such entry.
758	<	*
757	>	* is no such entry.
758	>	*
759		* @param key the key.
760		* @return an Entry associated with floor of given key, or <tt>null</tt>
761		* if there is no such Entry.
762		* @throws ClassCastException if key cannot be compared with the keys
763		*            currently in the map.
764	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
764	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
765		*         natural order, or its comparator does not tolerate
766		*         <tt>null</tt> keys.
767		*/
768		public Map.Entry<K,V> floorEntry(K key) {
769		Entry<K,V> e = getFloorEntry(key);
770	<	return (e == null)? null : new SnapshotEntry(e);
770	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
771		}
772
773		/**
774		* Returns the greatest key
775		* less than or equal to the given key, or <tt>null</tt> if there
776		* is no such key.
777	<	*
777	>	*
778		* @param key the key.
779		* @return the floor of given key, or <tt>null</tt> if there is no
780		* such key.
781		* @throws ClassCastException if key cannot be compared with the keys
782		*            currently in the map.
783	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
783	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
784		*         natural order, or its comparator does not tolerate
785		*         <tt>null</tt> keys.
786		*/
#	Line 794 | Line 792 | public class TreeMap<K,V>
792		/**
793		* Returns a key-value mapping associated with the least key
794		* strictly greater than the given key, or <tt>null</tt> if there
795	<	* is no such entry.
796	<	*
795	>	* is no such entry.
796	>	*
797		* @param key the key.
798		* @return an Entry with least key greater than the given key, or
799		* <tt>null</tt> if there is no such Entry.
800		* @throws ClassCastException if key cannot be compared with the keys
801		*            currently in the map.
802	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
802	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
803		*         natural order, or its comparator does not tolerate
804		*         <tt>null</tt> keys.
805		*/
806		public Map.Entry<K,V> higherEntry(K key) {
807		Entry<K,V> e = getHigherEntry(key);
808	<	return (e == null)? null : new SnapshotEntry(e);
808	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
809		}
810
811		/**
812		* Returns the least key strictly greater than the given key, or
813		* <tt>null</tt> if there is no such key.
814	<	*
814	>	*
815		* @param key the key.
816		* @return the least key greater than the given key, or
817		* <tt>null</tt> if there is no such key.
818		* @throws ClassCastException if key cannot be compared with the keys
819		*            currently in the map.
820	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
820	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
821		*         natural order, or its comparator does not tolerate
822		*         <tt>null</tt> keys.
823		*/
#	Line 831 | Line 829 | public class TreeMap<K,V>
829		/**
830		* Returns a key-value mapping associated with the greatest
831		* key strictly less than the given key, or <tt>null</tt> if there is no
832	<	* such entry.
833	<	*
832	>	* such entry.
833	>	*
834		* @param key the key.
835		* @return an Entry with greatest key less than the given
836		* key, or <tt>null</tt> if there is no such Entry.
837		* @throws ClassCastException if key cannot be compared with the keys
838		*            currently in the map.
839	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
839	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
840		*         natural order, or its comparator does not tolerate
841		*         <tt>null</tt> keys.
842		*/
843		public Map.Entry<K,V> lowerEntry(K key) {
844		Entry<K,V> e =  getLowerEntry(key);
845	<	return (e == null)? null : new SnapshotEntry(e);
845	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
846		}
847
848		/**
849		* Returns the greatest key strictly less than the given key, or
850		* <tt>null</tt> if there is no such key.
851	<	*
851	>	*
852		* @param key the key.
853		* @return the greatest key less than the given
854		* key, or <tt>null</tt> if there is no such key.
855		* @throws ClassCastException if key cannot be compared with the keys
856		*            currently in the map.
857	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
857	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
858		*         natural order, or its comparator does not tolerate
859		*         <tt>null</tt> keys.
860		*/
#	Line 874 | Line 872 | public class TreeMap<K,V>
872		*/
873		private transient Set<Map.Entry<K,V>> entrySet = null;
874		private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
875	<	private transient Set<K> descendingKeySet = null;
875	>	private transient Set<K> descendingKeySet = null;
876
877		transient Set<K> keySet = null;        // XXX remove when integrated
878		transient Collection<V> values = null; // XXX remove when integrated
#	Line 900 | Line 898 | public class TreeMap<K,V>
898		public Iterator<K> iterator() {
899		return new KeyIterator(getFirstEntry());
900		}
901	<
901	>
902		public int size() {
903		return TreeMap.this.size();
904		}
905	<
905	>
906		public boolean contains(Object o) {
907		return containsKey(o);
908		}
909	<
909	>
910		public boolean remove(Object o) {
911		int oldSize = size;
912		TreeMap.this.remove(o);
913		return size != oldSize;
914		}
915	<
915	>
916		public void clear() {
917		TreeMap.this.clear();
918		}
#	Line 942 | Line 940 | public class TreeMap<K,V>
940		public Iterator<V> iterator() {
941		return new ValueIterator(getFirstEntry());
942		}
943	<
943	>
944		public int size() {
945		return TreeMap.this.size();
946		}
947	<
947	>
948		public boolean contains(Object o) {
949		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
950		if (valEquals(e.getValue(), o))
951		return true;
952		return false;
953		}
954	<
954	>
955		public boolean remove(Object o) {
956		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
957		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 961 | public class TreeMap<K,V>
961		}
962		return false;
963		}
964	<
964	>
965		public void clear() {
966		TreeMap.this.clear();
967		}
#	Line 992 | Line 990 | public class TreeMap<K,V>
990		public Iterator<Map.Entry<K,V>> iterator() {
991		return new EntryIterator(getFirstEntry());
992		}
993	<
993	>
994		public boolean contains(Object o) {
995		if (!(o instanceof Map.Entry))
996		return false;
#	Line 1001 | Line 999 | public class TreeMap<K,V>
999		Entry<K,V> p = getEntry(entry.getKey());
1000		return p != null && valEquals(p.getValue(), value);
1001		}
1002	<
1002	>
1003		public boolean remove(Object o) {
1004		if (!(o instanceof Map.Entry))
1005		return false;
#	Line 1014 | Line 1012 | public class TreeMap<K,V>
1012		}
1013		return false;
1014		}
1015	<
1015	>
1016		public int size() {
1017		return TreeMap.this.size();
1018		}
1019	<
1019	>
1020		public void clear() {
1021		TreeMap.this.clear();
1022		}
#	Line 1026 | Line 1024 | public class TreeMap<K,V>
1024
1025		/**
1026		* Returns a set view of the mappings contained in this map.  The
1027	<	* set's iterator returns the mappings in descrending key order.
1027	>	* set's iterator returns the mappings in descending key order.
1028		* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1029		* set is backed by this map, so changes to this map are reflected
1030		* in the set, and vice-versa.  The set supports element removal,
#	Line 1036 | Line 1034 | public class TreeMap<K,V>
1034		* operations.  It does not support the <tt>add</tt> or
1035		* <tt>addAll</tt> operations.
1036		*
1037	<	* @return a set view of the mappings contained in this map, in
1037	>	* @return a set view of the mappings contained in this map, in
1038		* descending key order
1039		* @see Map.Entry
1040		*/
#	Line 1078 | Line 1076 | public class TreeMap<K,V>
1076		/**
1077		* Returns a view of the portion of this map whose keys range from
1078		* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1079	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
1080	<	* is empty.)  The returned sorted map is backed by this map, so changes
1081	<	* in the returned sorted map are reflected in this map, and vice-versa.
1082	<	* The returned sorted map supports all optional map operations.<p>
1079	>	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1080	>	* navigable map is empty.)  The returned navigable map is backed
1081	>	* by this map, so changes in the returned navigable map are
1082	>	* reflected in this map, and vice-versa.  The returned navigable
1083	>	* map supports all optional map operations.<p>
1084		*
1085	<	* The sorted map returned by this method will throw an
1085	>	* The navigable map returned by this method will throw an
1086		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1087		* less than <tt>fromKey</tt> or greater than or equal to
1088		* <tt>toKey</tt>.<p>
#	Line 1091 | Line 1090 | public class TreeMap<K,V>
1090		* Note: this method always returns a <i>half-open range</i> (which
1091		* includes its low endpoint but not its high endpoint).  If you need a
1092		* <i>closed range</i> (which includes both endpoints), and the key type
1093	<	* allows for calculation of the successor a given key, merely request the
1093	>	* allows for calculation of the successor of a given key, merely request the
1094		* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1095	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys are
1095	>	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1096		* strings.  The following idiom obtains a view containing all of the
1097		* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1098		* and <tt>high</tt>, inclusive:
1099	<	*             <pre>    NavigableMap sub = m.submap(low, high+"\0");</pre>
1099	>	* <pre>  NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1100		* A similar technique can be used to generate an <i>open range</i> (which
1101		* contains neither endpoint).  The following idiom obtains a view
1102		* containing all of the key-value mappings in <tt>m</tt> whose keys are
1103		* between <tt>low</tt> and <tt>high</tt>, exclusive:
1104	<	*             <pre>    NavigableMap sub = m.subMap(low+"\0", high);</pre>
1104	>	* <pre>  NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1105		*
1106		* @param fromKey low endpoint (inclusive) of the subMap.
1107		* @param toKey high endpoint (exclusive) of the subMap.
#	Line 1119 | Line 1118 | public class TreeMap<K,V>
1118		*               <tt>null</tt> and this map uses natural order, or its
1119		*               comparator does not tolerate <tt>null</tt> keys.
1120		*/
1121	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1121	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1122		return new SubMap(fromKey, toKey);
1123		}
1124
1125	+
1126		/**
1127		* Returns a view of the portion of this map whose keys are strictly less
1128	<	* than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
1129	<	* changes in the returned sorted map are reflected in this map, and
1130	<	* vice-versa.  The returned sorted map supports all optional map
1128	>	* than <tt>toKey</tt>.  The returned navigable map is backed by this map, so
1129	>	* changes in the returned navigable map are reflected in this map, and
1130	>	* vice-versa.  The returned navigable map supports all optional map
1131		* operations.<p>
1132		*
1133	<	* The sorted map returned by this method will throw an
1133	>	* The navigable map returned by this method will throw an
1134		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1135		* greater than or equal to <tt>toKey</tt>.<p>
1136		*
1137		* Note: this method always returns a view that does not contain its
1138		* (high) endpoint.  If you need a view that does contain this endpoint,
1139	<	* and the key type allows for calculation of the successor a given key,
1139	>	* and the key type allows for calculation of the successor of a given key,
1140		* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1141	<	* For example, suppose that suppose that <tt>m</tt> is a sorted map whose
1141	>	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1142		* keys are strings.  The following idiom obtains a view containing all of
1143		* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1144		* to <tt>high</tt>:
1145		* <pre>
1146	<	*     NavigableMap head = m.headMap(high+"\0");
1146	>	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1147		* </pre>
1148		*
1149		* @param toKey high endpoint (exclusive) of the headMap.
#	Line 1160 | Line 1160 | public class TreeMap<K,V>
1160		*               this map uses natural order, or its comparator does not
1161		*               tolerate <tt>null</tt> keys.
1162		*/
1163	<	public NavigableMap<K,V> headMap(K toKey) {
1163	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1164		return new SubMap(toKey, true);
1165		}
1166
1167		/**
1168		* Returns a view of the portion of this map whose keys are greater than
1169	<	* or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
1170	<	* this map, so changes in the returned sorted map are reflected in this
1171	<	* map, and vice-versa.  The returned sorted map supports all optional map
1169	>	* or equal to <tt>fromKey</tt>.  The returned navigable map is backed by
1170	>	* this map, so changes in the returned navigable map are reflected in this
1171	>	* map, and vice-versa.  The returned navigable map supports all optional map
1172		* operations.<p>
1173		*
1174	<	* The sorted map returned by this method will throw an
1174	>	* The navigable map returned by this method will throw an
1175		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1176		* less than <tt>fromKey</tt>.<p>
1177		*
1178		* Note: this method always returns a view that contains its (low)
1179		* endpoint.  If you need a view that does not contain this endpoint, and
1180	<	* the element type allows for calculation of the successor a given value,
1180	>	* the element type allows for calculation of the successor of a given value,
1181		* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1182	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys
1182	>	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1183		* are strings.  The following idiom obtains a view containing
1184		* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1185		* greater than <tt>low</tt>: <pre>
1186	<	*     NavigableMap tail = m.tailMap(low+"\0");
1186	>	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1187		* </pre>
1188		*
1189		* @param fromKey low endpoint (inclusive) of the tailMap.
#	Line 1199 | Line 1199 | public class TreeMap<K,V>
1199		*               this map uses natural order, or its comparator does not
1200		*               tolerate <tt>null</tt> keys.
1201		*/
1202	<	public NavigableMap<K,V> tailMap(K fromKey) {
1202	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1203	>	return new SubMap(fromKey, false);
1204	>	}
1205	>
1206	>	/**
1207	>	* Equivalent to <tt>navigableSubMap</tt> but with a return
1208	>	* type conforming to the <tt>SortedMap</tt> interface.
1209	>	* @param fromKey low endpoint (inclusive) of the subMap.
1210	>	* @param toKey high endpoint (exclusive) of the subMap.
1211	>	*
1212	>	* @return a view of the portion of this map whose keys range from
1213	>	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1214	>	*
1215	>	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1216	>	*         cannot be compared to one another using this map's comparator
1217	>	*         (or, if the map has no comparator, using natural ordering).
1218	>	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1219	>	*         <tt>toKey</tt>.
1220	>	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1221	>	*               <tt>null</tt> and this map uses natural order, or its
1222	>	*               comparator does not tolerate <tt>null</tt> keys.
1223	>	*/
1224	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1225	>	return new SubMap(fromKey, toKey);
1226	>	}
1227	>
1228	>
1229	>	/**
1230	>	* Equivalent to <tt>navigableHeadMap</tt> but with a return
1231	>	* type conforming to the <tt>SortedMap</tt> interface.
1232	>	*
1233	>	* @param toKey high endpoint (exclusive) of the headMap.
1234	>	* @return a view of the portion of this map whose keys are strictly
1235	>	*                less than <tt>toKey</tt>.
1236	>	*
1237	>	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1238	>	*         with this map's comparator (or, if the map has no comparator,
1239	>	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1240	>	* @throws IllegalArgumentException if this map is itself a subMap,
1241	>	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1242	>	*         specified range of the subMap, headMap, or tailMap.
1243	>	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1244	>	*               this map uses natural order, or its comparator does not
1245	>	*               tolerate <tt>null</tt> keys.
1246	>	*/
1247	>	public SortedMap<K,V> headMap(K toKey) {
1248	>	return new SubMap(toKey, true);
1249	>	}
1250	>
1251	>	/**
1252	>	* Equivalent to <tt>navigableTailMap</tt> but with a return
1253	>	* type conforming to the <tt>SortedMap</tt> interface.
1254	>	*
1255	>	* @param fromKey low endpoint (inclusive) of the tailMap.
1256	>	* @return a view of the portion of this map whose keys are greater
1257	>	*                than or equal to <tt>fromKey</tt>.
1258	>	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1259	>	*         with this map's comparator (or, if the map has no comparator,
1260	>	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1261	>	* @throws IllegalArgumentException if this map is itself a subMap,
1262	>	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1263	>	*         specified range of the subMap, headMap, or tailMap.
1264	>	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1265	>	*               this map uses natural order, or its comparator does not
1266	>	*               tolerate <tt>null</tt> keys.
1267	>	*/
1268	>	public SortedMap<K,V> tailMap(K fromKey) {
1269		return new SubMap(fromKey, false);
1270		}
1271
#	Line 1242 | Line 1308 | public class TreeMap<K,V>
1308		}
1309
1310		public boolean isEmpty() {
1311	<	return entrySet.isEmpty();
1311	>	return entrySet().isEmpty();
1312		}
1313
1314		public boolean containsKey(Object key) {
#	Line 1288 | Line 1354 | public class TreeMap<K,V>
1354		}
1355
1356		public Map.Entry<K,V> firstEntry() {
1357	<	TreeMap.Entry<K,V> e = fromStart ?
1357	>	TreeMap.Entry<K,V> e = fromStart ?
1358		getFirstEntry() : getCeilingEntry(fromKey);
1359		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1360		return null;
#	Line 1296 | Line 1362 | public class TreeMap<K,V>
1362		}
1363
1364		public Map.Entry<K,V> lastEntry() {
1365	<	TreeMap.Entry<K,V> e = toEnd ?
1365	>	TreeMap.Entry<K,V> e = toEnd ?
1366		getLastEntry() : getLowerEntry(toKey);
1367		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1368		return null;
#	Line 1304 | Line 1370 | public class TreeMap<K,V>
1370		}
1371
1372		public Map.Entry<K,V> pollFirstEntry() {
1373	<	TreeMap.Entry<K,V> e = fromStart ?
1373	>	TreeMap.Entry<K,V> e = fromStart ?
1374		getFirstEntry() : getCeilingEntry(fromKey);
1375	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1375	>	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1376		return null;
1377	<	Map.Entry result = new SnapshotEntry(e);
1377	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1378		deleteEntry(e);
1379		return result;
1380		}
1381
1382		public Map.Entry<K,V> pollLastEntry() {
1383	<	TreeMap.Entry<K,V> e = toEnd ?
1383	>	TreeMap.Entry<K,V> e = toEnd ?
1384		getLastEntry() : getLowerEntry(toKey);
1385	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1385	>	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1386		return null;
1387	<	Map.Entry result = new SnapshotEntry(e);
1387	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1388		deleteEntry(e);
1389		return result;
1390		}
#	Line 1333 | Line 1399 | public class TreeMap<K,V>
1399
1400		public Map.Entry<K,V> ceilingEntry(K key) {
1401		TreeMap.Entry<K,V> e = subceiling(key);
1402	<	return e == null? null : new SnapshotEntry(e);
1402	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1403		}
1404
1405		public K ceilingKey(K key) {
#	Line 1352 | Line 1418 | public class TreeMap<K,V>
1418
1419		public Map.Entry<K,V> higherEntry(K key) {
1420		TreeMap.Entry<K,V> e = subhigher(key);
1421	<	return e == null? null : new SnapshotEntry(e);
1421	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1422		}
1423
1424		public K higherKey(K key) {
#	Line 1370 | Line 1436 | public class TreeMap<K,V>
1436
1437		public Map.Entry<K,V> floorEntry(K key) {
1438		TreeMap.Entry<K,V> e = subfloor(key);
1439	<	return e == null? null : new SnapshotEntry(e);
1439	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1440		}
1441
1442		public K floorKey(K key) {
#	Line 1388 | Line 1454 | public class TreeMap<K,V>
1454
1455		public Map.Entry<K,V> lowerEntry(K key) {
1456		TreeMap.Entry<K,V> e = sublower(key);
1457	<	return e == null? null : new SnapshotEntry(e);
1457	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1458		}
1459
1460		public K lowerKey(K key) {
#	Line 1396 | Line 1462 | public class TreeMap<K,V>
1462		return e == null? null : e.key;
1463		}
1464
1465	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1465	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1466
1467		public Set<Map.Entry<K,V>> entrySet() {
1468	<	return entrySet;
1468	>	Set<Map.Entry<K,V>> es = entrySet;
1469	>	return (es != null)? es : (entrySet = new EntrySetView());
1470		}
1471
1472		private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
#	Line 1456 | Line 1523 | public class TreeMap<K,V>
1523		}
1524
1525		private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1526	<	private transient Set<K> descendingKeySetView = null;
1526	>	private transient Set<K> descendingKeySetView = null;
1527
1528		public Set<Map.Entry<K,V>> descendingEntrySet() {
1529		Set<Map.Entry<K,V>> es = descendingEntrySetView;
#	Line 1480 | Line 1547 | public class TreeMap<K,V>
1547		public Iterator<K> iterator() {
1548		return new Iterator<K>() {
1549		private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1550	<
1550	>
1551		public boolean hasNext() { return i.hasNext(); }
1552		public K next() { return i.next().getKey(); }
1553		public void remove() { i.remove(); }
1554		};
1555		}
1556	<
1556	>
1557		public int size() {
1558		return SubMap.this.size();
1559		}
1560	<
1560	>
1561		public boolean contains(Object k) {
1562		return SubMap.this.containsKey(k);
1563		}
1564		}
1565
1566
1567	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1567	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1568		if (!inRange2(fromKey))
1569		throw new IllegalArgumentException("fromKey out of range");
1570		if (!inRange2(toKey))
#	Line 1505 | Line 1572 | public class TreeMap<K,V>
1572		return new SubMap(fromKey, toKey);
1573		}
1574
1575	<	public NavigableMap<K,V> headMap(K toKey) {
1575	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1576		if (!inRange2(toKey))
1577		throw new IllegalArgumentException("toKey out of range");
1578		return new SubMap(fromStart, fromKey, false, toKey);
1579		}
1580
1581	<	public NavigableMap<K,V> tailMap(K fromKey) {
1581	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1582		if (!inRange2(fromKey))
1583		throw new IllegalArgumentException("fromKey out of range");
1584		return new SubMap(false, fromKey, toEnd, toKey);
1585		}
1586
1587	+
1588	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1589	+	return navigableSubMap(fromKey, toKey);
1590	+	}
1591	+
1592	+	public SortedMap<K,V> headMap(K toKey) {
1593	+	return navigableHeadMap(toKey);
1594	+	}
1595	+
1596	+	public SortedMap<K,V> tailMap(K fromKey) {
1597	+	return navigableTailMap(fromKey);
1598	+	}
1599	+
1600		private boolean inRange(K key) {
1601		return (fromStart || compare(key, fromKey) >= 0) &&
1602		(toEnd     || compare(key, toKey)   <  0);
#	Line 2083 | Line 2163 | public class TreeMap<K,V>
2163		// Write out size (number of Mappings)
2164		s.writeInt(size);
2165
2166	+	Set<Map.Entry<K,V>> es = entrySet();
2167		// Write out keys and values (alternating)
2168	<	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2168	>	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
2169		Map.Entry<K,V> e = i.next();
2170		s.writeObject(e.getKey());
2171		s.writeObject(e.getValue());
#	Line 2260 | Line 2341 | public class TreeMap<K,V>
2341		return level;
2342		}
2343
2263	–
2264	–	/**
2265	–	* Entry holding a snapshot of a key-value pair
2266	–	*/
2267	–	static class SnapshotEntry<K,V> implements Map.Entry<K,V> {
2268	–	final K key;
2269	–	final V value;
2270	–
2271	–	public SnapshotEntry(Entry<K,V> e) {
2272	–	this.key   = e.getKey();
2273	–	this.value = e.getValue();
2274	–	}
2275	–
2276	–	public K getKey() {
2277	–	return key;
2278	–	}
2279	–
2280	–	public V getValue() {
2281	–	return value;
2282	–	}
2283	–
2284	–	/**
2285	–	* Always fails, throwing <tt>UnsupportedOperationException</tt>.
2286	–	* @throws UnsupportedOperationException always.
2287	–	*/
2288	–	public V setValue(V value) {
2289	–	throw new UnsupportedOperationException();
2290	–	}
2291	–
2292	–	public boolean equals(Object o) {
2293	–	if (!(o instanceof Map.Entry))
2294	–	return false;
2295	–	Map.Entry e = (Map.Entry)o;
2296	–	return eq(key, e.getKey()) && eq(value, e.getValue());
2297	–	}
2298	–
2299	–	public int hashCode() {
2300	–	return ((key   == null)   ? 0 :   key.hashCode()) ^
2301	–	((value == null)   ? 0 : value.hashCode());
2302	–	}
2303	–
2304	–	public String toString() {
2305	–	return key + "=" + value;
2306	–	}
2307	–
2308	–	private static boolean eq(Object o1, Object o2) {
2309	–	return (o1 == null ? o2 == null : o1.equals(o2));
2310	–	}
2311	–	}
2312	–
2344		}

Diff Legend

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