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.13 by dl, Wed May 11 11:16:08 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 556 | Line 556 | public class TreeMap<K,V>
556		Entry<K,V> t = root;
557
558		if (t == null) {
559	+	if (key == null) {
560	+	if (comparator == null)
561	+	throw new NullPointerException();
562	+	comparator.compare(key, key);
563	+	}
564		incrementSize();
565		root = new Entry<K,V>(key, value, null);
566		return null;
567	<	}
567	>	}
568
569		while (true) {
570		int cmp = compare(key, t.key);
#	Line 591 | Line 596 | public class TreeMap<K,V>
596		* Removes the mapping for this key from this TreeMap if present.
597		*
598		* @param  key key for which mapping should be removed
599	<	* @return previous value associated with specified key, or <tt>null</tt>
599	>	* @return the previous value associated with specified key, or <tt>null</tt>
600		*         if there was no mapping for key.  A <tt>null</tt> return can
601		*         also indicate that the map previously associated
602		*         <tt>null</tt> with the specified key.
603		*
604	<	* @throws    ClassCastException key cannot be compared with the keys
604	>	* @throws    ClassCastException if key cannot be compared with the keys
605		*            currently in the map.
606	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
606	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
607		*         natural order, or its comparator does not tolerate
608		*         <tt>null</tt> keys.
609		*/
#	Line 658 | Line 663 | public class TreeMap<K,V>
663		/**
664		* Returns a key-value mapping associated with the least
665		* key in this map, or <tt>null</tt> if the map is empty.
666	<	*
667	<	* @return an Entry with least key, or <tt>null</tt>
666	>	*
667	>	* @return an Entry with least key, or <tt>null</tt>
668		* if the map is empty.
669		*/
670		public Map.Entry<K,V> firstEntry() {
671		Entry<K,V> e = getFirstEntry();
672	<	return (e == null)? null : new SnapshotEntry(e);
672	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
673		}
674
675		/**
676		* Returns a key-value mapping associated with the greatest
677		* key in this map, or <tt>null</tt> if the map is empty.
678	<	* The returned entry does <em>not</em> support
674	<	* the <tt>Entry.setValue</tt> method.
675	<	*
678	>	*
679		* @return an Entry with greatest key, or <tt>null</tt>
680		* if the map is empty.
681		*/
682		public Map.Entry<K,V> lastEntry() {
683		Entry<K,V> e = getLastEntry();
684	<	return (e == null)? null : new SnapshotEntry(e);
684	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
685		}
686
687		/**
688		* Removes and returns a key-value mapping associated with
689		* the least key in this map, or <tt>null</tt> if the map is empty.
690	<	*
690	>	*
691		* @return the removed first entry of this map, or <tt>null</tt>
692		* if the map is empty.
693		*/
694		public Map.Entry<K,V> pollFirstEntry() {
695		Entry<K,V> p = getFirstEntry();
696	<	if (p == null)
696	>	if (p == null)
697		return null;
698	<	Map.Entry result = new SnapshotEntry(p);
698	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
699		deleteEntry(p);
700		return result;
701		}
#	Line 700 | Line 703 | public class TreeMap<K,V>
703		/**
704		* Removes and returns a key-value mapping associated with
705		* the greatest key in this map, or <tt>null</tt> if the map is empty.
706	<	*
706	>	*
707		* @return the removed last entry of this map, or <tt>null</tt>
708		* if the map is empty.
709		*/
710		public Map.Entry<K,V> pollLastEntry() {
711		Entry<K,V> p = getLastEntry();
712	<	if (p == null)
712	>	if (p == null)
713		return null;
714	<	Map.Entry result = new SnapshotEntry(p);
714	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
715		deleteEntry(p);
716		return result;
717		}
#	Line 716 | Line 719 | public class TreeMap<K,V>
719		/**
720		* Returns a key-value mapping associated with the least key
721		* greater than or equal to the given key, or <tt>null</tt> if
722	<	* there is no such entry.
723	<	*
722	>	* there is no such entry.
723	>	*
724		* @param key the key.
725		* @return an Entry associated with ceiling of given key, or
726		* <tt>null</tt> if there is no such Entry.
727		* @throws ClassCastException if key cannot be compared with the
728		* keys currently in the map.
729	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
729	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
730		*         natural order, or its comparator does not tolerate
731		*         <tt>null</tt> keys.
732		*/
733		public Map.Entry<K,V> ceilingEntry(K key) {
734		Entry<K,V> e = getCeilingEntry(key);
735	<	return (e == null)? null : new SnapshotEntry(e);
735	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
736		}
737
738
739		/**
740		* Returns least key greater than or equal to the given key, or
741		* <tt>null</tt> if there is no such key.
742	<	*
742	>	*
743		* @param key the key.
744		* @return the ceiling key, or <tt>null</tt>
745		* if there is no such key.
746		* @throws ClassCastException if key cannot be compared with the keys
747		*            currently in the map.
748	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
748	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
749		*         natural order, or its comparator does not tolerate
750		*         <tt>null</tt> keys.
751		*/
#	Line 756 | Line 759 | public class TreeMap<K,V>
759		/**
760		* Returns a key-value mapping associated with the greatest key
761		* less than or equal to the given key, or <tt>null</tt> if there
762	<	* is no such entry.
763	<	*
762	>	* is no such entry.
763	>	*
764		* @param key the key.
765		* @return an Entry associated with floor of given key, or <tt>null</tt>
766		* if there is no such Entry.
767		* @throws ClassCastException if key cannot be compared with the keys
768		*            currently in the map.
769	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
769	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
770		*         natural order, or its comparator does not tolerate
771		*         <tt>null</tt> keys.
772		*/
773		public Map.Entry<K,V> floorEntry(K key) {
774		Entry<K,V> e = getFloorEntry(key);
775	<	return (e == null)? null : new SnapshotEntry(e);
775	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
776		}
777
778		/**
779		* Returns the greatest key
780		* less than or equal to the given key, or <tt>null</tt> if there
781		* is no such key.
782	<	*
782	>	*
783		* @param key the key.
784		* @return the floor of given key, or <tt>null</tt> if there is no
785		* such key.
786		* @throws ClassCastException if key cannot be compared with the keys
787		*            currently in the map.
788	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
788	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
789		*         natural order, or its comparator does not tolerate
790		*         <tt>null</tt> keys.
791		*/
#	Line 794 | Line 797 | public class TreeMap<K,V>
797		/**
798		* Returns a key-value mapping associated with the least key
799		* strictly greater than the given key, or <tt>null</tt> if there
800	<	* is no such entry.
801	<	*
800	>	* is no such entry.
801	>	*
802		* @param key the key.
803		* @return an Entry with least key greater than the given key, or
804		* <tt>null</tt> if there is no such Entry.
805		* @throws ClassCastException if key cannot be compared with the keys
806		*            currently in the map.
807	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
807	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
808		*         natural order, or its comparator does not tolerate
809		*         <tt>null</tt> keys.
810		*/
811		public Map.Entry<K,V> higherEntry(K key) {
812		Entry<K,V> e = getHigherEntry(key);
813	<	return (e == null)? null : new SnapshotEntry(e);
813	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
814		}
815
816		/**
817		* Returns the least key strictly greater than the given key, or
818		* <tt>null</tt> if there is no such key.
819	<	*
819	>	*
820		* @param key the key.
821		* @return the least key greater than the given key, or
822		* <tt>null</tt> if there is no such key.
823		* @throws ClassCastException if key cannot be compared with the keys
824		*            currently in the map.
825	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
825	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
826		*         natural order, or its comparator does not tolerate
827		*         <tt>null</tt> keys.
828		*/
#	Line 831 | Line 834 | public class TreeMap<K,V>
834		/**
835		* Returns a key-value mapping associated with the greatest
836		* key strictly less than the given key, or <tt>null</tt> if there is no
837	<	* such entry.
838	<	*
837	>	* such entry.
838	>	*
839		* @param key the key.
840		* @return an Entry with greatest key less than the given
841		* key, or <tt>null</tt> if there is no such Entry.
842		* @throws ClassCastException if key cannot be compared with the keys
843		*            currently in the map.
844	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
844	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
845		*         natural order, or its comparator does not tolerate
846		*         <tt>null</tt> keys.
847		*/
848		public Map.Entry<K,V> lowerEntry(K key) {
849		Entry<K,V> e =  getLowerEntry(key);
850	<	return (e == null)? null : new SnapshotEntry(e);
850	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
851		}
852
853		/**
854		* Returns the greatest key strictly less than the given key, or
855		* <tt>null</tt> if there is no such key.
856	<	*
856	>	*
857		* @param key the key.
858		* @return the greatest key less than the given
859		* key, or <tt>null</tt> if there is no such key.
860		* @throws ClassCastException if key cannot be compared with the keys
861		*            currently in the map.
862	<	* @throws NullPointerException key is <tt>null</tt> and this map uses
862	>	* @throws NullPointerException if key is <tt>null</tt> and this map uses
863		*         natural order, or its comparator does not tolerate
864		*         <tt>null</tt> keys.
865		*/
#	Line 874 | Line 877 | public class TreeMap<K,V>
877		*/
878		private transient Set<Map.Entry<K,V>> entrySet = null;
879		private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
880	<	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
880	>	private transient Set<K> descendingKeySet = null;
881
882		/**
883		* Returns a Set view of the keys contained in this map.  The set's
#	Line 900 | Line 900 | public class TreeMap<K,V>
900		public Iterator<K> iterator() {
901		return new KeyIterator(getFirstEntry());
902		}
903	<
903	>
904		public int size() {
905		return TreeMap.this.size();
906		}
907	<
907	>
908		public boolean contains(Object o) {
909		return containsKey(o);
910		}
911	<
911	>
912		public boolean remove(Object o) {
913		int oldSize = size;
914		TreeMap.this.remove(o);
915		return size != oldSize;
916		}
917	<
917	>
918		public void clear() {
919		TreeMap.this.clear();
920		}
#	Line 942 | Line 942 | public class TreeMap<K,V>
942		public Iterator<V> iterator() {
943		return new ValueIterator(getFirstEntry());
944		}
945	<
945	>
946		public int size() {
947		return TreeMap.this.size();
948		}
949	<
949	>
950		public boolean contains(Object o) {
951		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
952		if (valEquals(e.getValue(), o))
953		return true;
954		return false;
955		}
956	<
956	>
957		public boolean remove(Object o) {
958		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
959		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 963 | public class TreeMap<K,V>
963		}
964		return false;
965		}
966	<
966	>
967		public void clear() {
968		TreeMap.this.clear();
969		}
#	Line 992 | Line 992 | public class TreeMap<K,V>
992		public Iterator<Map.Entry<K,V>> iterator() {
993		return new EntryIterator(getFirstEntry());
994		}
995	<
995	>
996		public boolean contains(Object o) {
997		if (!(o instanceof Map.Entry))
998		return false;
#	Line 1001 | Line 1001 | public class TreeMap<K,V>
1001		Entry<K,V> p = getEntry(entry.getKey());
1002		return p != null && valEquals(p.getValue(), value);
1003		}
1004	<
1004	>
1005		public boolean remove(Object o) {
1006		if (!(o instanceof Map.Entry))
1007		return false;
#	Line 1014 | Line 1014 | public class TreeMap<K,V>
1014		}
1015		return false;
1016		}
1017	<
1017	>
1018		public int size() {
1019		return TreeMap.this.size();
1020		}
1021	<
1021	>
1022		public void clear() {
1023		TreeMap.this.clear();
1024		}
#	Line 1026 | Line 1026 | public class TreeMap<K,V>
1026
1027		/**
1028		* Returns a set view of the mappings contained in this map.  The
1029	<	* set's iterator returns the mappings in descrending key order.
1029	>	* set's iterator returns the mappings in descending key order.
1030		* Each element in the returned set is a <tt>Map.Entry</tt>.  The
1031		* set is backed by this map, so changes to this map are reflected
1032		* in the set, and vice-versa.  The set supports element removal,
#	Line 1036 | Line 1036 | public class TreeMap<K,V>
1036		* operations.  It does not support the <tt>add</tt> or
1037		* <tt>addAll</tt> operations.
1038		*
1039	<	* @return a set view of the mappings contained in this map, in
1039	>	* @return a set view of the mappings contained in this map, in
1040		* descending key order
1041		* @see Map.Entry
1042		*/
#	Line 1078 | Line 1078 | public class TreeMap<K,V>
1078		/**
1079		* Returns a view of the portion of this map whose keys range from
1080		* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
1081	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
1082	<	* is empty.)  The returned sorted map is backed by this map, so changes
1083	<	* in the returned sorted map are reflected in this map, and vice-versa.
1084	<	* The returned sorted map supports all optional map operations.<p>
1081	>	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
1082	>	* navigable map is empty.)  The returned navigable map is backed
1083	>	* by this map, so changes in the returned navigable map are
1084	>	* reflected in this map, and vice-versa.  The returned navigable
1085	>	* map supports all optional map operations.<p>
1086		*
1087	<	* The sorted map returned by this method will throw an
1087	>	* The navigable map returned by this method will throw an
1088		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1089		* less than <tt>fromKey</tt> or greater than or equal to
1090		* <tt>toKey</tt>.<p>
#	Line 1091 | Line 1092 | public class TreeMap<K,V>
1092		* Note: this method always returns a <i>half-open range</i> (which
1093		* includes its low endpoint but not its high endpoint).  If you need a
1094		* <i>closed range</i> (which includes both endpoints), and the key type
1095	<	* allows for calculation of the successor a given key, merely request the
1095	>	* allows for calculation of the successor of a given key, merely request the
1096		* subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
1097	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys are
1097	>	* For example, suppose that <tt>m</tt> is a navigable map whose keys are
1098		* strings.  The following idiom obtains a view containing all of the
1099		* key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
1100		* and <tt>high</tt>, inclusive:
1101	<	*             <pre>    NavigableMap sub = m.submap(low, high+"\0");</pre>
1101	>	* <pre>  NavigableMap sub = m.navigableSubMap(low, high+"\0");</pre>
1102		* A similar technique can be used to generate an <i>open range</i> (which
1103		* contains neither endpoint).  The following idiom obtains a view
1104		* containing all of the key-value mappings in <tt>m</tt> whose keys are
1105		* between <tt>low</tt> and <tt>high</tt>, exclusive:
1106	<	*             <pre>    NavigableMap sub = m.subMap(low+"\0", high);</pre>
1106	>	* <pre>  NavigableMap sub = m.navigableSubMap(low+"\0", high);</pre>
1107		*
1108		* @param fromKey low endpoint (inclusive) of the subMap.
1109		* @param toKey high endpoint (exclusive) of the subMap.
#	Line 1119 | Line 1120 | public class TreeMap<K,V>
1120		*               <tt>null</tt> and this map uses natural order, or its
1121		*               comparator does not tolerate <tt>null</tt> keys.
1122		*/
1123	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1123	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1124		return new SubMap(fromKey, toKey);
1125		}
1126
1127	+
1128		/**
1129		* Returns a view of the portion of this map whose keys are strictly less
1130	<	* than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
1131	<	* changes in the returned sorted map are reflected in this map, and
1132	<	* vice-versa.  The returned sorted map supports all optional map
1130	>	* than <tt>toKey</tt>.  The returned navigable map is backed by this map, so
1131	>	* changes in the returned navigable map are reflected in this map, and
1132	>	* vice-versa.  The returned navigable map supports all optional map
1133		* operations.<p>
1134		*
1135	<	* The sorted map returned by this method will throw an
1135	>	* The navigable map returned by this method will throw an
1136		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1137		* greater than or equal to <tt>toKey</tt>.<p>
1138		*
1139		* Note: this method always returns a view that does not contain its
1140		* (high) endpoint.  If you need a view that does contain this endpoint,
1141	<	* and the key type allows for calculation of the successor a given key,
1141	>	* and the key type allows for calculation of the successor of a given key,
1142		* merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
1143	<	* For example, suppose that suppose that <tt>m</tt> is a sorted map whose
1143	>	* For example, suppose that suppose that <tt>m</tt> is a navigable map whose
1144		* keys are strings.  The following idiom obtains a view containing all of
1145		* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1146		* to <tt>high</tt>:
1147		* <pre>
1148	<	*     NavigableMap head = m.headMap(high+"\0");
1148	>	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1149		* </pre>
1150		*
1151		* @param toKey high endpoint (exclusive) of the headMap.
#	Line 1160 | Line 1162 | public class TreeMap<K,V>
1162		*               this map uses natural order, or its comparator does not
1163		*               tolerate <tt>null</tt> keys.
1164		*/
1165	<	public NavigableMap<K,V> headMap(K toKey) {
1165	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1166		return new SubMap(toKey, true);
1167		}
1168
1169		/**
1170		* Returns a view of the portion of this map whose keys are greater than
1171	<	* or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
1172	<	* this map, so changes in the returned sorted map are reflected in this
1173	<	* map, and vice-versa.  The returned sorted map supports all optional map
1171	>	* or equal to <tt>fromKey</tt>.  The returned navigable map is backed by
1172	>	* this map, so changes in the returned navigable map are reflected in this
1173	>	* map, and vice-versa.  The returned navigable map supports all optional map
1174		* operations.<p>
1175		*
1176	<	* The sorted map returned by this method will throw an
1176	>	* The navigable map returned by this method will throw an
1177		* <tt>IllegalArgumentException</tt> if the user attempts to insert a key
1178		* less than <tt>fromKey</tt>.<p>
1179		*
1180		* Note: this method always returns a view that contains its (low)
1181		* endpoint.  If you need a view that does not contain this endpoint, and
1182	<	* the element type allows for calculation of the successor a given value,
1182	>	* the element type allows for calculation of the successor of a given value,
1183		* merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
1184	<	* For example, suppose that <tt>m</tt> is a sorted map whose keys
1184	>	* For example, suppose that <tt>m</tt> is a navigable map whose keys
1185		* are strings.  The following idiom obtains a view containing
1186		* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1187		* greater than <tt>low</tt>: <pre>
1188	<	*     NavigableMap tail = m.tailMap(low+"\0");
1188	>	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1189		* </pre>
1190		*
1191		* @param fromKey low endpoint (inclusive) of the tailMap.
#	Line 1199 | Line 1201 | public class TreeMap<K,V>
1201		*               this map uses natural order, or its comparator does not
1202		*               tolerate <tt>null</tt> keys.
1203		*/
1204	<	public NavigableMap<K,V> tailMap(K fromKey) {
1204	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1205	>	return new SubMap(fromKey, false);
1206	>	}
1207	>
1208	>	/**
1209	>	* Equivalent to <tt>navigableSubMap</tt> but with a return
1210	>	* type conforming to the <tt>SortedMap</tt> interface.
1211	>	* @param fromKey low endpoint (inclusive) of the subMap.
1212	>	* @param toKey high endpoint (exclusive) of the subMap.
1213	>	*
1214	>	* @return a view of the portion of this map whose keys range from
1215	>	*                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
1216	>	*
1217	>	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
1218	>	*         cannot be compared to one another using this map's comparator
1219	>	*         (or, if the map has no comparator, using natural ordering).
1220	>	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
1221	>	*         <tt>toKey</tt>.
1222	>	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1223	>	*               <tt>null</tt> and this map uses natural order, or its
1224	>	*               comparator does not tolerate <tt>null</tt> keys.
1225	>	*/
1226	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1227	>	return new SubMap(fromKey, toKey);
1228	>	}
1229	>
1230	>
1231	>	/**
1232	>	* Equivalent to <tt>navigableHeadMap</tt> but with a return
1233	>	* type conforming to the <tt>SortedMap</tt> interface.
1234	>	*
1235	>	* @param toKey high endpoint (exclusive) of the headMap.
1236	>	* @return a view of the portion of this map whose keys are strictly
1237	>	*                less than <tt>toKey</tt>.
1238	>	*
1239	>	* @throws ClassCastException if <tt>toKey</tt> is not compatible
1240	>	*         with this map's comparator (or, if the map has no comparator,
1241	>	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
1242	>	* @throws IllegalArgumentException if this map is itself a subMap,
1243	>	*         headMap, or tailMap, and <tt>toKey</tt> is not within the
1244	>	*         specified range of the subMap, headMap, or tailMap.
1245	>	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
1246	>	*               this map uses natural order, or its comparator does not
1247	>	*               tolerate <tt>null</tt> keys.
1248	>	*/
1249	>	public SortedMap<K,V> headMap(K toKey) {
1250	>	return new SubMap(toKey, true);
1251	>	}
1252	>
1253	>	/**
1254	>	* Equivalent to <tt>navigableTailMap</tt> but with a return
1255	>	* type conforming to the <tt>SortedMap</tt> interface.
1256	>	*
1257	>	* @param fromKey low endpoint (inclusive) of the tailMap.
1258	>	* @return a view of the portion of this map whose keys are greater
1259	>	*                than or equal to <tt>fromKey</tt>.
1260	>	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
1261	>	*         with this map's comparator (or, if the map has no comparator,
1262	>	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
1263	>	* @throws IllegalArgumentException if this map is itself a subMap,
1264	>	*         headMap, or tailMap, and <tt>fromKey</tt> is not within the
1265	>	*         specified range of the subMap, headMap, or tailMap.
1266	>	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
1267	>	*               this map uses natural order, or its comparator does not
1268	>	*               tolerate <tt>null</tt> keys.
1269	>	*/
1270	>	public SortedMap<K,V> tailMap(K fromKey) {
1271		return new SubMap(fromKey, false);
1272		}
1273
#	Line 1242 | Line 1310 | public class TreeMap<K,V>
1310		}
1311
1312		public boolean isEmpty() {
1313	<	return entrySet.isEmpty();
1313	>	return entrySet().isEmpty();
1314		}
1315
1316		public boolean containsKey(Object key) {
#	Line 1275 | Line 1343 | public class TreeMap<K,V>
1343		TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1344		K first = key(e);
1345		if (!toEnd && compare(first, toKey) >= 0)
1346	<	throw(new NoSuchElementException());
1346	>	throw new NoSuchElementException();
1347		return first;
1348		}
1349
#	Line 1283 | Line 1351 | public class TreeMap<K,V>
1351		TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1352		K last = key(e);
1353		if (!fromStart && compare(last, fromKey) < 0)
1354	<	throw(new NoSuchElementException());
1354	>	throw new NoSuchElementException();
1355		return last;
1356		}
1357
1358		public Map.Entry<K,V> firstEntry() {
1359	<	TreeMap.Entry<K,V> e = fromStart ?
1359	>	TreeMap.Entry<K,V> e = fromStart ?
1360		getFirstEntry() : getCeilingEntry(fromKey);
1361		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1362		return null;
#	Line 1296 | Line 1364 | public class TreeMap<K,V>
1364		}
1365
1366		public Map.Entry<K,V> lastEntry() {
1367	<	TreeMap.Entry<K,V> e = toEnd ?
1367	>	TreeMap.Entry<K,V> e = toEnd ?
1368		getLastEntry() : getLowerEntry(toKey);
1369		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1370		return null;
#	Line 1304 | Line 1372 | public class TreeMap<K,V>
1372		}
1373
1374		public Map.Entry<K,V> pollFirstEntry() {
1375	<	TreeMap.Entry<K,V> e = fromStart ?
1375	>	TreeMap.Entry<K,V> e = fromStart ?
1376		getFirstEntry() : getCeilingEntry(fromKey);
1377	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1377	>	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1378		return null;
1379	<	Map.Entry result = new SnapshotEntry(e);
1379	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1380		deleteEntry(e);
1381		return result;
1382		}
1383
1384		public Map.Entry<K,V> pollLastEntry() {
1385	<	TreeMap.Entry<K,V> e = toEnd ?
1385	>	TreeMap.Entry<K,V> e = toEnd ?
1386		getLastEntry() : getLowerEntry(toKey);
1387	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1387	>	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1388		return null;
1389	<	Map.Entry result = new SnapshotEntry(e);
1389	>	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1390		deleteEntry(e);
1391		return result;
1392		}
#	Line 1333 | Line 1401 | public class TreeMap<K,V>
1401
1402		public Map.Entry<K,V> ceilingEntry(K key) {
1403		TreeMap.Entry<K,V> e = subceiling(key);
1404	<	return e == null? null : new SnapshotEntry(e);
1404	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1405		}
1406
1407		public K ceilingKey(K key) {
#	Line 1352 | Line 1420 | public class TreeMap<K,V>
1420
1421		public Map.Entry<K,V> higherEntry(K key) {
1422		TreeMap.Entry<K,V> e = subhigher(key);
1423	<	return e == null? null : new SnapshotEntry(e);
1423	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1424		}
1425
1426		public K higherKey(K key) {
#	Line 1370 | Line 1438 | public class TreeMap<K,V>
1438
1439		public Map.Entry<K,V> floorEntry(K key) {
1440		TreeMap.Entry<K,V> e = subfloor(key);
1441	<	return e == null? null : new SnapshotEntry(e);
1441	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1442		}
1443
1444		public K floorKey(K key) {
#	Line 1388 | Line 1456 | public class TreeMap<K,V>
1456
1457		public Map.Entry<K,V> lowerEntry(K key) {
1458		TreeMap.Entry<K,V> e = sublower(key);
1459	<	return e == null? null : new SnapshotEntry(e);
1459	>	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1460		}
1461
1462		public K lowerKey(K key) {
#	Line 1396 | Line 1464 | public class TreeMap<K,V>
1464		return e == null? null : e.key;
1465		}
1466
1467	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1467	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1468
1469		public Set<Map.Entry<K,V>> entrySet() {
1470	<	return entrySet;
1470	>	Set<Map.Entry<K,V>> es = entrySet;
1471	>	return (es != null)? es : (entrySet = new EntrySetView());
1472		}
1473
1474		private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
#	Line 1456 | Line 1525 | public class TreeMap<K,V>
1525		}
1526
1527		private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1528	<	private transient Set<K> descendingKeySetView = null;
1528	>	private transient Set<K> descendingKeySetView = null;
1529
1530		public Set<Map.Entry<K,V>> descendingEntrySet() {
1531		Set<Map.Entry<K,V>> es = descendingEntrySetView;
#	Line 1480 | Line 1549 | public class TreeMap<K,V>
1549		public Iterator<K> iterator() {
1550		return new Iterator<K>() {
1551		private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1552	<
1552	>
1553		public boolean hasNext() { return i.hasNext(); }
1554		public K next() { return i.next().getKey(); }
1555		public void remove() { i.remove(); }
1556		};
1557		}
1558	<
1558	>
1559		public int size() {
1560		return SubMap.this.size();
1561		}
1562	<
1562	>
1563		public boolean contains(Object k) {
1564		return SubMap.this.containsKey(k);
1565		}
1566		}
1567
1568
1569	<	public NavigableMap<K,V> subMap(K fromKey, K toKey) {
1569	>	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1570		if (!inRange2(fromKey))
1571		throw new IllegalArgumentException("fromKey out of range");
1572		if (!inRange2(toKey))
#	Line 1505 | Line 1574 | public class TreeMap<K,V>
1574		return new SubMap(fromKey, toKey);
1575		}
1576
1577	<	public NavigableMap<K,V> headMap(K toKey) {
1577	>	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1578		if (!inRange2(toKey))
1579		throw new IllegalArgumentException("toKey out of range");
1580		return new SubMap(fromStart, fromKey, false, toKey);
1581		}
1582
1583	<	public NavigableMap<K,V> tailMap(K fromKey) {
1583	>	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1584		if (!inRange2(fromKey))
1585		throw new IllegalArgumentException("fromKey out of range");
1586		return new SubMap(false, fromKey, toEnd, toKey);
1587		}
1588
1589	+
1590	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1591	+	return navigableSubMap(fromKey, toKey);
1592	+	}
1593	+
1594	+	public SortedMap<K,V> headMap(K toKey) {
1595	+	return navigableHeadMap(toKey);
1596	+	}
1597	+
1598	+	public SortedMap<K,V> tailMap(K fromKey) {
1599	+	return navigableTailMap(fromKey);
1600	+	}
1601	+
1602		private boolean inRange(K key) {
1603		return (fromStart || compare(key, fromKey) >= 0) &&
1604		(toEnd     || compare(key, toKey)   <  0);
#	Line 1683 | Line 1765 | public class TreeMap<K,V>
1765		* Compares two keys using the correct comparison method for this TreeMap.
1766		*/
1767		private int compare(K k1, K k2) {
1768	<	return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
1769	<	: comparator.compare((K)k1, (K)k2));
1768	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1769	>	: comparator.compare(k1, k2);
1770		}
1771
1772		/**
#	Line 2083 | Line 2165 | public class TreeMap<K,V>
2165		// Write out size (number of Mappings)
2166		s.writeInt(size);
2167
2168	+	Set<Map.Entry<K,V>> es = entrySet();
2169		// Write out keys and values (alternating)
2170	<	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2170	>	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
2171		Map.Entry<K,V> e = i.next();
2172		s.writeObject(e.getKey());
2173		s.writeObject(e.getValue());
#	Line 2115 | Line 2198 | public class TreeMap<K,V>
2198		}
2199
2200		/** Intended to be called only from TreeSet.addAll **/
2201	<	void addAllForTreeSet(SortedSet<Map.Entry<K,V>> set, V defaultVal) {
2201	>	void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2202		try {
2203		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2204		} catch (java.io.IOException cannotHappen) {
#	Line 2260 | Line 2343 | public class TreeMap<K,V>
2343		return level;
2344		}
2345
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	–
2346		}

Diff Legend

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