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.12 by jsr166, Mon May 2 21:44:01 2005 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
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 351 | Line 351 | public class TreeMap<K,V>
351		// Offload comparator-based version for sake of performance
352		if (comparator != null)
353		return getEntryUsingComparator(key);
354	<	Comparable<K> k = (Comparable<K>) key;
354	>	Comparable<? super K> k = (Comparable<? super K>) key;
355		Entry<K,V> p = root;
356		while (p != null) {
357		int cmp = k.compareTo(p.key);
#	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;
878	<
879	<	transient Set<K> keySet = null;        // XXX remove when integrated
880	<	transient Collection<V> values = null; // XXX remove when integrated
875	>	private transient Set<K> descendingKeySet = null;
876
877		/**
878		* Returns a Set view of the keys contained in this map.  The set's
#	Line 900 | Line 895 | public class TreeMap<K,V>
895		public Iterator<K> iterator() {
896		return new KeyIterator(getFirstEntry());
897		}
898	<
898	>
899		public int size() {
900		return TreeMap.this.size();
901		}
902	<
902	>
903		public boolean contains(Object o) {
904		return containsKey(o);
905		}
906	<
906	>
907		public boolean remove(Object o) {
908		int oldSize = size;
909		TreeMap.this.remove(o);
910		return size != oldSize;
911		}
912	<
912	>
913		public void clear() {
914		TreeMap.this.clear();
915		}
#	Line 942 | Line 937 | public class TreeMap<K,V>
937		public Iterator<V> iterator() {
938		return new ValueIterator(getFirstEntry());
939		}
940	<
940	>
941		public int size() {
942		return TreeMap.this.size();
943		}
944	<
944	>
945		public boolean contains(Object o) {
946		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
947		if (valEquals(e.getValue(), o))
948		return true;
949		return false;
950		}
951	<
951	>
952		public boolean remove(Object o) {
953		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
954		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 958 | public class TreeMap<K,V>
958		}
959		return false;
960		}
961	<
961	>
962		public void clear() {
963		TreeMap.this.clear();
964		}
#	Line 992 | Line 987 | public class TreeMap<K,V>
987		public Iterator<Map.Entry<K,V>> iterator() {
988		return new EntryIterator(getFirstEntry());
989		}
990	<
990	>
991		public boolean contains(Object o) {
992		if (!(o instanceof Map.Entry))
993		return false;
#	Line 1001 | Line 996 | public class TreeMap<K,V>
996		Entry<K,V> p = getEntry(entry.getKey());
997		return p != null && valEquals(p.getValue(), value);
998		}
999	<
999	>
1000		public boolean remove(Object o) {
1001		if (!(o instanceof Map.Entry))
1002		return false;
#	Line 1014 | Line 1009 | public class TreeMap<K,V>
1009		}
1010		return false;
1011		}
1012	<
1012	>
1013		public int size() {
1014		return TreeMap.this.size();
1015		}
1016	<
1016	>
1017		public void clear() {
1018		TreeMap.this.clear();
1019		}
#	Line 1026 | Line 1021 | public class TreeMap<K,V>
1021
1022		/**
1023		* Returns a set view of the mappings contained in this map.  The
1024	<	* set's iterator returns the mappings in descrending key order.
1024	>	* set's iterator returns the mappings in descending key order.
1025		* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1026		* set is backed by this map, so changes to this map are reflected
1027		* in the set, and vice-versa.  The set supports element removal,
#	Line 1036 | Line 1031 | public class TreeMap<K,V>
1031		* operations.  It does not support the <tt>add</tt> or
1032		* <tt>addAll</tt> operations.
1033		*
1034	<	* @return a set view of the mappings contained in this map, in
1034	>	* @return a set view of the mappings contained in this map, in
1035		* descending key order
1036		* @see Map.Entry
1037		*/
#	Line 1078 | Line 1073 | public class TreeMap<K,V>
1073		/**
1074		* Returns a view of the portion of this map whose keys range from
1075		* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1076	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
1077	<	* is empty.)  The returned sorted map is backed by this map, so changes
1078	<	* in the returned sorted map are reflected in this map, and vice-versa.
1079	<	* The returned sorted map supports all optional map operations.<p>
1076	>	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1077	>	* navigable map is empty.)  The returned navigable map is backed
1078	>	* by this map, so changes in the returned navigable map are
1079	>	* reflected in this map, and vice-versa.  The returned navigable
1080	>	* map supports all optional map operations.<p>
1081		*
1082	<	* The sorted map returned by this method will throw an
1082	>	* The navigable map returned by this method will throw an
1083		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1084		* less than <tt>fromKey</tt> or greater than or equal to
1085		* <tt>toKey</tt>.<p>
#	Line 1091 | Line 1087 | public class TreeMap<K,V>
1087		* Note: this method always returns a <i>half-open range</i> (which
1088		* includes its low endpoint but not its high endpoint).  If you need a
1089		* <i>closed range</i> (which includes both endpoints), and the key type
1090	<	* allows for calculation of the successor a given key, merely request the
1090	>	* allows for calculation of the successor of a given key, merely request the
1091		* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1092	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys are
1092	>	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1093		* strings.  The following idiom obtains a view containing all of the
1094		* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1095		* and <tt>high</tt>, inclusive:
1096	<	*             <pre>    NavigableMap sub = m.submap(low, high+"\0");</pre>
1096	>	* <pre>  NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1097		* A similar technique can be used to generate an <i>open range</i> (which
1098		* contains neither endpoint).  The following idiom obtains a view
1099		* containing all of the key-value mappings in <tt>m</tt> whose keys are
1100		* between <tt>low</tt> and <tt>high</tt>, exclusive:
1101	<	*             <pre>    NavigableMap sub = m.subMap(low+"\0", high);</pre>
1101	>	* <pre>  NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1102		*
1103		* @param fromKey low endpoint (inclusive) of the subMap.
1104		* @param toKey high endpoint (exclusive) of the subMap.
#	Line 1119 | Line 1115 | public class TreeMap<K,V>
1115		*               <tt>null</tt> and this map uses natural order, or its
1116		*               comparator does not tolerate <tt>null</tt> keys.
1117		*/
1118	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1118	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1119		return new SubMap(fromKey, toKey);
1120		}
1121
1122	+
1123		/**
1124		* Returns a view of the portion of this map whose keys are strictly less
1125	<	* than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
1126	<	* changes in the returned sorted map are reflected in this map, and
1127	<	* vice-versa.  The returned sorted map supports all optional map
1125	>	* than <tt>toKey</tt>.  The returned navigable map is backed by this map, so
1126	>	* changes in the returned navigable map are reflected in this map, and
1127	>	* vice-versa.  The returned navigable map supports all optional map
1128		* operations.<p>
1129		*
1130	<	* The sorted map returned by this method will throw an
1130	>	* The navigable map returned by this method will throw an
1131		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1132		* greater than or equal to <tt>toKey</tt>.<p>
1133		*
1134		* Note: this method always returns a view that does not contain its
1135		* (high) endpoint.  If you need a view that does contain this endpoint,
1136	<	* and the key type allows for calculation of the successor a given key,
1136	>	* and the key type allows for calculation of the successor of a given key,
1137		* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1138	<	* For example, suppose that suppose that <tt>m</tt> is a sorted map whose
1138	>	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1139		* keys are strings.  The following idiom obtains a view containing all of
1140		* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1141		* to <tt>high</tt>:
1142		* <pre>
1143	<	*     NavigableMap head = m.headMap(high+"\0");
1143	>	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1144		* </pre>
1145		*
1146		* @param toKey high endpoint (exclusive) of the headMap.
#	Line 1160 | Line 1157 | public class TreeMap<K,V>
1157		*               this map uses natural order, or its comparator does not
1158		*               tolerate <tt>null</tt> keys.
1159		*/
1160	<	public NavigableMap<K,V> headMap(K toKey) {
1160	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1161		return new SubMap(toKey, true);
1162		}
1163
1164		/**
1165		* Returns a view of the portion of this map whose keys are greater than
1166	<	* or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
1167	<	* this map, so changes in the returned sorted map are reflected in this
1168	<	* map, and vice-versa.  The returned sorted map supports all optional map
1166	>	* or equal to <tt>fromKey</tt>.  The returned navigable map is backed by
1167	>	* this map, so changes in the returned navigable map are reflected in this
1168	>	* map, and vice-versa.  The returned navigable map supports all optional map
1169		* operations.<p>
1170		*
1171	<	* The sorted map returned by this method will throw an
1171	>	* The navigable map returned by this method will throw an
1172		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1173		* less than <tt>fromKey</tt>.<p>
1174		*
1175		* Note: this method always returns a view that contains its (low)
1176		* endpoint.  If you need a view that does not contain this endpoint, and
1177	<	* the element type allows for calculation of the successor a given value,
1177	>	* the element type allows for calculation of the successor of a given value,
1178		* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1179	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys
1179	>	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1180		* are strings.  The following idiom obtains a view containing
1181		* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1182		* greater than <tt>low</tt>: <pre>
1183	<	*     NavigableMap tail = m.tailMap(low+"\0");
1183	>	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1184		* </pre>
1185		*
1186		* @param fromKey low endpoint (inclusive) of the tailMap.
#	Line 1199 | Line 1196 | public class TreeMap<K,V>
1196		*               this map uses natural order, or its comparator does not
1197		*               tolerate <tt>null</tt> keys.
1198		*/
1199	<	public NavigableMap<K,V> tailMap(K fromKey) {
1199	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1200	>	return new SubMap(fromKey, false);
1201	>	}
1202	>
1203	>	/**
1204	>	* Equivalent to <tt>navigableSubMap</tt> but with a return
1205	>	* type conforming to the <tt>SortedMap</tt> interface.
1206	>	* @param fromKey low endpoint (inclusive) of the subMap.
1207	>	* @param toKey high endpoint (exclusive) of the subMap.
1208	>	*
1209	>	* @return a view of the portion of this map whose keys range from
1210	>	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1211	>	*
1212	>	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1213	>	*         cannot be compared to one another using this map's comparator
1214	>	*         (or, if the map has no comparator, using natural ordering).
1215	>	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1216	>	*         <tt>toKey</tt>.
1217	>	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1218	>	*               <tt>null</tt> and this map uses natural order, or its
1219	>	*               comparator does not tolerate <tt>null</tt> keys.
1220	>	*/
1221	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1222	>	return new SubMap(fromKey, toKey);
1223	>	}
1224	>
1225	>
1226	>	/**
1227	>	* Equivalent to <tt>navigableHeadMap</tt> but with a return
1228	>	* type conforming to the <tt>SortedMap</tt> interface.
1229	>	*
1230	>	* @param toKey high endpoint (exclusive) of the headMap.
1231	>	* @return a view of the portion of this map whose keys are strictly
1232	>	*                less than <tt>toKey</tt>.
1233	>	*
1234	>	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1235	>	*         with this map's comparator (or, if the map has no comparator,
1236	>	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1237	>	* @throws IllegalArgumentException if this map is itself a subMap,
1238	>	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1239	>	*         specified range of the subMap, headMap, or tailMap.
1240	>	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1241	>	*               this map uses natural order, or its comparator does not
1242	>	*               tolerate <tt>null</tt> keys.
1243	>	*/
1244	>	public SortedMap<K,V> headMap(K toKey) {
1245	>	return new SubMap(toKey, true);
1246	>	}
1247	>
1248	>	/**
1249	>	* Equivalent to <tt>navigableTailMap</tt> but with a return
1250	>	* type conforming to the <tt>SortedMap</tt> interface.
1251	>	*
1252	>	* @param fromKey low endpoint (inclusive) of the tailMap.
1253	>	* @return a view of the portion of this map whose keys are greater
1254	>	*                than or equal to <tt>fromKey</tt>.
1255	>	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1256	>	*         with this map's comparator (or, if the map has no comparator,
1257	>	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1258	>	* @throws IllegalArgumentException if this map is itself a subMap,
1259	>	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1260	>	*         specified range of the subMap, headMap, or tailMap.
1261	>	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1262	>	*               this map uses natural order, or its comparator does not
1263	>	*               tolerate <tt>null</tt> keys.
1264	>	*/
1265	>	public SortedMap<K,V> tailMap(K fromKey) {
1266		return new SubMap(fromKey, false);
1267		}
1268
#	Line 1242 | Line 1305 | public class TreeMap<K,V>
1305		}
1306
1307		public boolean isEmpty() {
1308	<	return entrySet.isEmpty();
1308	>	return entrySet().isEmpty();
1309		}
1310
1311		public boolean containsKey(Object key) {
#	Line 1275 | Line 1338 | public class TreeMap<K,V>
1338		TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1339		K first = key(e);
1340		if (!toEnd && compare(first, toKey) >= 0)
1341	<	throw(new NoSuchElementException());
1341	>	throw new NoSuchElementException();
1342		return first;
1343		}
1344
#	Line 1283 | Line 1346 | public class TreeMap<K,V>
1346		TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1347		K last = key(e);
1348		if (!fromStart && compare(last, fromKey) < 0)
1349	<	throw(new NoSuchElementException());
1349	>	throw new NoSuchElementException();
1350		return last;
1351		}
1352
1353		public Map.Entry<K,V> firstEntry() {
1354	<	TreeMap.Entry<K,V> e = fromStart ?
1354	>	TreeMap.Entry<K,V> e = fromStart ?
1355		getFirstEntry() : getCeilingEntry(fromKey);
1356		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1357		return null;
#	Line 1296 | Line 1359 | public class TreeMap<K,V>
1359		}
1360
1361		public Map.Entry<K,V> lastEntry() {
1362	<	TreeMap.Entry<K,V> e = toEnd ?
1362	>	TreeMap.Entry<K,V> e = toEnd ?
1363		getLastEntry() : getLowerEntry(toKey);
1364		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1365		return null;
#	Line 1304 | Line 1367 | public class TreeMap<K,V>
1367		}
1368
1369		public Map.Entry<K,V> pollFirstEntry() {
1370	<	TreeMap.Entry<K,V> e = fromStart ?
1370	>	TreeMap.Entry<K,V> e = fromStart ?
1371		getFirstEntry() : getCeilingEntry(fromKey);
1372	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1372	>	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1373		return null;
1374	<	Map.Entry result = new SnapshotEntry(e);
1374	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1375		deleteEntry(e);
1376		return result;
1377		}
1378
1379		public Map.Entry<K,V> pollLastEntry() {
1380	<	TreeMap.Entry<K,V> e = toEnd ?
1380	>	TreeMap.Entry<K,V> e = toEnd ?
1381		getLastEntry() : getLowerEntry(toKey);
1382	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1382	>	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1383		return null;
1384	<	Map.Entry result = new SnapshotEntry(e);
1384	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1385		deleteEntry(e);
1386		return result;
1387		}
#	Line 1333 | Line 1396 | public class TreeMap<K,V>
1396
1397		public Map.Entry<K,V> ceilingEntry(K key) {
1398		TreeMap.Entry<K,V> e = subceiling(key);
1399	<	return e == null? null : new SnapshotEntry(e);
1399	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1400		}
1401
1402		public K ceilingKey(K key) {
#	Line 1352 | Line 1415 | public class TreeMap<K,V>
1415
1416		public Map.Entry<K,V> higherEntry(K key) {
1417		TreeMap.Entry<K,V> e = subhigher(key);
1418	<	return e == null? null : new SnapshotEntry(e);
1418	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1419		}
1420
1421		public K higherKey(K key) {
#	Line 1370 | Line 1433 | public class TreeMap<K,V>
1433
1434		public Map.Entry<K,V> floorEntry(K key) {
1435		TreeMap.Entry<K,V> e = subfloor(key);
1436	<	return e == null? null : new SnapshotEntry(e);
1436	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1437		}
1438
1439		public K floorKey(K key) {
#	Line 1388 | Line 1451 | public class TreeMap<K,V>
1451
1452		public Map.Entry<K,V> lowerEntry(K key) {
1453		TreeMap.Entry<K,V> e = sublower(key);
1454	<	return e == null? null : new SnapshotEntry(e);
1454	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1455		}
1456
1457		public K lowerKey(K key) {
#	Line 1396 | Line 1459 | public class TreeMap<K,V>
1459		return e == null? null : e.key;
1460		}
1461
1462	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1462	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1463
1464		public Set<Map.Entry<K,V>> entrySet() {
1465	<	return entrySet;
1465	>	Set<Map.Entry<K,V>> es = entrySet;
1466	>	return (es != null)? es : (entrySet = new EntrySetView());
1467		}
1468
1469		private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
#	Line 1456 | Line 1520 | public class TreeMap<K,V>
1520		}
1521
1522		private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1523	<	private transient Set<K> descendingKeySetView = null;
1523	>	private transient Set<K> descendingKeySetView = null;
1524
1525		public Set<Map.Entry<K,V>> descendingEntrySet() {
1526		Set<Map.Entry<K,V>> es = descendingEntrySetView;
#	Line 1480 | Line 1544 | public class TreeMap<K,V>
1544		public Iterator<K> iterator() {
1545		return new Iterator<K>() {
1546		private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1547	<
1547	>
1548		public boolean hasNext() { return i.hasNext(); }
1549		public K next() { return i.next().getKey(); }
1550		public void remove() { i.remove(); }
1551		};
1552		}
1553	<
1553	>
1554		public int size() {
1555		return SubMap.this.size();
1556		}
1557	<
1557	>
1558		public boolean contains(Object k) {
1559		return SubMap.this.containsKey(k);
1560		}
1561		}
1562
1563
1564	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1564	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1565		if (!inRange2(fromKey))
1566		throw new IllegalArgumentException("fromKey out of range");
1567		if (!inRange2(toKey))
#	Line 1505 | Line 1569 | public class TreeMap<K,V>
1569		return new SubMap(fromKey, toKey);
1570		}
1571
1572	<	public NavigableMap<K,V> headMap(K toKey) {
1572	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1573		if (!inRange2(toKey))
1574		throw new IllegalArgumentException("toKey out of range");
1575		return new SubMap(fromStart, fromKey, false, toKey);
1576		}
1577
1578	<	public NavigableMap<K,V> tailMap(K fromKey) {
1578	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1579		if (!inRange2(fromKey))
1580		throw new IllegalArgumentException("fromKey out of range");
1581		return new SubMap(false, fromKey, toEnd, toKey);
1582		}
1583
1584	+
1585	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1586	+	return navigableSubMap(fromKey, toKey);
1587	+	}
1588	+
1589	+	public SortedMap<K,V> headMap(K toKey) {
1590	+	return navigableHeadMap(toKey);
1591	+	}
1592	+
1593	+	public SortedMap<K,V> tailMap(K fromKey) {
1594	+	return navigableTailMap(fromKey);
1595	+	}
1596	+
1597		private boolean inRange(K key) {
1598		return (fromStart || compare(key, fromKey) >= 0) &&
1599		(toEnd     || compare(key, toKey)   <  0);
#	Line 1683 | Line 1760 | public class TreeMap<K,V>
1760		* Compares two keys using the correct comparison method for this TreeMap.
1761		*/
1762		private int compare(K k1, K k2) {
1763	<	return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
1764	<	: comparator.compare((K)k1, (K)k2));
1763	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1764	>	: comparator.compare(k1, k2);
1765		}
1766
1767		/**
#	Line 2083 | Line 2160 | public class TreeMap<K,V>
2160		// Write out size (number of Mappings)
2161		s.writeInt(size);
2162
2163	+	Set<Map.Entry<K,V>> es = entrySet();
2164		// Write out keys and values (alternating)
2165	<	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2165	>	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
2166		Map.Entry<K,V> e = i.next();
2167		s.writeObject(e.getKey());
2168		s.writeObject(e.getValue());
#	Line 2115 | Line 2193 | public class TreeMap<K,V>
2193		}
2194
2195		/** Intended to be called only from TreeSet.addAll **/
2196	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
2196	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2197		try {
2198		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2199		} catch (java.io.IOException cannotHappen) {
#	Line 2260 | Line 2338 | public class TreeMap<K,V>
2338		return level;
2339		}
2340
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	–
2341		}

Diff Legend

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