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.27 by jsr166, Sun Mar 19 18:03:54 2006 UTC vs.
Revision 1.28 by dl, Wed Apr 19 15:07:14 2006 UTC

#	Line 109 | Line 109 | public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
112	+	/**
113	+	* A sentinel to indicate that an endpoint of a submap is not bounded.
114	+	* It is used to generate head maps, tail maps, and descending views
115	+	* of the entire backing map. The sentinel must be serializable,
116	+	* requiring a little class to express.
117	+	*/
118	+	private static class Unbounded implements java.io.Serializable {}
119	+	private static final Unbounded UNBOUNDED = new Unbounded();
120	+
121		private void incrementSize()   { modCount++; size++; }
122		private void decrementSize()   { modCount++; size--; }
123
#	Line 339 | Line 348 | public class TreeMap<K,V>
348		// Offload comparator-based version for sake of performance
349		if (comparator != null)
350		return getEntryUsingComparator(key);
351	+	if (key == null)
352	+	throw new NullPointerException();
353		Comparable<? super K> k = (Comparable<? super K>) key;
354		Entry<K,V> p = root;
355		while (p != null) {
#	Line 634 | Line 645 | public class TreeMap<K,V>
645		clone.size = 0;
646		clone.modCount = 0;
647		clone.entrySet = null;
648	<	clone.descendingEntrySet = null;
649	<	clone.descendingKeySet = null;
648	>	clone.navigableKeySet = null;
649	>	clone.descendingMap = null;
650
651		// Initialize clone with our mappings
652		try {
#	Line 793 | Line 804 | public class TreeMap<K,V>
804		* there's no reason to create more than one.
805		*/
806		private transient Set<Map.Entry<K,V>> entrySet = null;
807	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
808	<	private transient Set<K> descendingKeySet = null;
807	>	private transient KeySet<K> navigableKeySet = null;
808	>	private transient NavigableMap<K,V> descendingMap = null;
809
810		/**
811		* Returns a {@link Set} view of the keys contained in this map.
#	Line 811 | Line 822 | public class TreeMap<K,V>
822		* operations.
823		*/
824		public Set<K> keySet() {
825	<	Set<K> ks = keySet;
815	<	return (ks != null) ? ks : (keySet = new KeySet());
825	>	return navigableKeySet();
826		}
827
828	<	class KeySet extends AbstractSet<K> {
829	<	public Iterator<K> iterator() {
830	<	return new KeyIterator(getFirstEntry());
831	<	}
832	<
833	<	public int size() {
834	<	return TreeMap.this.size();
825	<	}
826	<
827	<	public boolean contains(Object o) {
828	<	return containsKey(o);
829	<	}
830	<
831	<	public boolean remove(Object o) {
832	<	int oldSize = size;
833	<	TreeMap.this.remove(o);
834	<	return size != oldSize;
835	<	}
828	>	/**
829	>	* @since 1.6
830	>	*/
831	>	public NavigableSet<K> navigableKeySet() {
832	>	NavigableSet<K> nks = navigableKeySet;
833	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
834	>	}
835
836	<	public void clear() {
837	<	TreeMap.this.clear();
838	<	}
836	>	/**
837	>	* @since 1.6
838	>	*/
839	>	public NavigableSet<K> descendingKeySet() {
840	>	return descendingMap().navigableKeySet();
841		}
842
843		/**
#	Line 859 | Line 860 | public class TreeMap<K,V>
860		return (vs != null) ? vs : (values = new Values());
861		}
862
862	–	class Values extends AbstractCollection<V> {
863	–	public Iterator<V> iterator() {
864	–	return new ValueIterator(getFirstEntry());
865	–	}
866	–
867	–	public int size() {
868	–	return TreeMap.this.size();
869	–	}
870	–
871	–	public boolean contains(Object o) {
872	–	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
873	–	if (valEquals(e.getValue(), o))
874	–	return true;
875	–	return false;
876	–	}
877	–
878	–	public boolean remove(Object o) {
879	–	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
880	–	if (valEquals(e.getValue(), o)) {
881	–	deleteEntry(e);
882	–	return true;
883	–	}
884	–	}
885	–	return false;
886	–	}
887	–
888	–	public void clear() {
889	–	TreeMap.this.clear();
890	–	}
891	–	}
892	–
863		/**
864		* Returns a {@link Set} view of the mappings contained in this map.
865		* The set's iterator returns the entries in ascending key order.
#	Line 910 | Line 880 | public class TreeMap<K,V>
880		return (es != null) ? es : (entrySet = new EntrySet());
881		}
882
913	–	class EntrySet extends AbstractSet<Map.Entry<K,V>> {
914	–	public Iterator<Map.Entry<K,V>> iterator() {
915	–	return new EntryIterator(getFirstEntry());
916	–	}
917	–
918	–	public boolean contains(Object o) {
919	–	if (!(o instanceof Map.Entry))
920	–	return false;
921	–	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
922	–	V value = entry.getValue();
923	–	Entry<K,V> p = getEntry(entry.getKey());
924	–	return p != null && valEquals(p.getValue(), value);
925	–	}
926	–
927	–	public boolean remove(Object o) {
928	–	if (!(o instanceof Map.Entry))
929	–	return false;
930	–	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
931	–	V value = entry.getValue();
932	–	Entry<K,V> p = getEntry(entry.getKey());
933	–	if (p != null && valEquals(p.getValue(), value)) {
934	–	deleteEntry(p);
935	–	return true;
936	–	}
937	–	return false;
938	–	}
939	–
940	–	public int size() {
941	–	return TreeMap.this.size();
942	–	}
943	–
944	–	public void clear() {
945	–	TreeMap.this.clear();
946	–	}
947	–	}
948	–
883		/**
884		* @since 1.6
885		*/
886	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
887	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
888	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
889	<	}
890	<
957	<	class DescendingEntrySet extends EntrySet {
958	<	public Iterator<Map.Entry<K,V>> iterator() {
959	<	return new DescendingEntryIterator(getLastEntry());
960	<	}
961	<	}
962	<
963	<	/**
964	<	* @since 1.6
965	<	*/
966	<	public Set<K> descendingKeySet() {
967	<	Set<K> ks = descendingKeySet;
968	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
969	<	}
970	<
971	<	class DescendingKeySet extends KeySet {
972	<	public Iterator<K> iterator() {
973	<	return new DescendingKeyIterator(getLastEntry());
974	<	}
886	>	public NavigableMap<K, V> descendingMap() {
887	>	NavigableMap<K, V> km = descendingMap;
888	>	return (km != null) ? km :
889	>	(descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
890	>	(K)UNBOUNDED, 0));
891		}
892
893		/**
#	Line 982 | Line 898 | public class TreeMap<K,V>
898		* @throws IllegalArgumentException {@inheritDoc}
899		* @since 1.6
900		*/
901	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
902	<	return new SubMap(fromKey, toKey);
901	>	public NavigableMap<K,V> navigableSubMap(K fromKey, boolean fromInclusive,
902	>	K toKey,   boolean toInclusive) {
903	>	return new AscendingSubMap(fromKey, excluded(fromInclusive),
904	>	toKey,   excluded(toInclusive));
905		}
906
907		/**
#	Line 994 | Line 912 | public class TreeMap<K,V>
912		* @throws IllegalArgumentException {@inheritDoc}
913		* @since 1.6
914		*/
915	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
916	<	return new SubMap(toKey, true);
915	>	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
916	>	return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
917		}
918
919		/**
#	Line 1006 | Line 924 | public class TreeMap<K,V>
924		* @throws IllegalArgumentException {@inheritDoc}
925		* @since 1.6
926		*/
927	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
928	<	return new SubMap(fromKey, false);
927	>	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive) {
928	>	return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 0);
929	>	}
930	>
931	>	/**
932	>	* Translates a boolean "inclusive" value to the correct int value
933	>	* for the loExcluded or hiExcluded field.
934	>	*/
935	>	static int excluded(boolean inclusive) {
936	>	return inclusive ? 0 : 1;
937		}
938
939		/**
1014	–	* Equivalent to {@link #navigableSubMap} but with a return type
1015	–	* conforming to the <tt>SortedMap</tt> interface.
1016	–	*
1017	–	* <p>{@inheritDoc}
1018	–	*
940		* @throws ClassCastException       {@inheritDoc}
941		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
942		*         null and this map uses natural ordering, or its comparator
#	Line 1023 | Line 944 | public class TreeMap<K,V>
944		* @throws IllegalArgumentException {@inheritDoc}
945		*/
946		public SortedMap<K,V> subMap(K fromKey, K toKey) {
947	<	return new SubMap(fromKey, toKey);
947	>	return navigableSubMap(fromKey, true, toKey, false);
948		}
949
950		/**
1030	–	* Equivalent to {@link #navigableHeadMap} but with a return type
1031	–	* conforming to the <tt>SortedMap</tt> interface.
1032	–	*
1033	–	* <p>{@inheritDoc}
1034	–	*
951		* @throws ClassCastException       {@inheritDoc}
952		* @throws NullPointerException if <tt>toKey</tt> is null
953		*         and this map uses natural ordering, or its comparator
#	Line 1039 | Line 955 | public class TreeMap<K,V>
955		* @throws IllegalArgumentException {@inheritDoc}
956		*/
957		public SortedMap<K,V> headMap(K toKey) {
958	<	return new SubMap(toKey, true);
958	>	return navigableHeadMap(toKey, false);
959		}
960
961		/**
1046	–	* Equivalent to {@link #navigableTailMap} but with a return type
1047	–	* conforming to the <tt>SortedMap</tt> interface.
1048	–	*
1049	–	* <p>{@inheritDoc}
1050	–	*
962		* @throws ClassCastException       {@inheritDoc}
963		* @throws NullPointerException if <tt>fromKey</tt> is null
964		*         and this map uses natural ordering, or its comparator
#	Line 1055 | Line 966 | public class TreeMap<K,V>
966		* @throws IllegalArgumentException {@inheritDoc}
967		*/
968		public SortedMap<K,V> tailMap(K fromKey) {
969	<	return new SubMap(fromKey, false);
969	>	return navigableTailMap(fromKey, true);
970		}
971
972	<	private class SubMap
1062	<	extends AbstractMap<K,V>
1063	<	implements NavigableMap<K,V>, java.io.Serializable {
1064	<	private static final long serialVersionUID = -6520786458950516097L;
972	>	// View class support
973
974	<	/**
975	<	* fromKey is significant only if fromStart is false.  Similarly,
976	<	* toKey is significant only if toStart is false.
977	<	*/
1070	<	private boolean fromStart = false, toEnd = false;
1071	<	private K fromKey, toKey;
974	>	class Values extends AbstractCollection<V> {
975	>	public Iterator<V> iterator() {
976	>	return new ValueIterator(getFirstEntry());
977	>	}
978
979	<	SubMap(K fromKey, K toKey) {
980	<	if (compare(fromKey, toKey) > 0)
1075	<	throw new IllegalArgumentException("fromKey > toKey");
1076	<	this.fromKey = fromKey;
1077	<	this.toKey = toKey;
979	>	public int size() {
980	>	return TreeMap.this.size();
981		}
982
983	<	SubMap(K key, boolean headMap) {
984	<	compare(key, key); // Type-check key
983	>	public boolean contains(Object o) {
984	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
985	>	if (valEquals(e.getValue(), o))
986	>	return true;
987	>	return false;
988	>	}
989
990	<	if (headMap) {
991	<	fromStart = true;
992	<	toKey = key;
993	<	} else {
994	<	toEnd = true;
995	<	fromKey = key;
990	>	public boolean remove(Object o) {
991	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
992	>	if (valEquals(e.getValue(), o)) {
993	>	deleteEntry(e);
994	>	return true;
995	>	}
996		}
997	+	return false;
998		}
999
1000	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1001	<	this.fromStart = fromStart;
1094	<	this.fromKey= fromKey;
1095	<	this.toEnd = toEnd;
1096	<	this.toKey = toKey;
1000	>	public void clear() {
1001	>	TreeMap.this.clear();
1002		}
1003	+	}
1004
1005	<	public boolean isEmpty() {
1006	<	return entrySet().isEmpty();
1005	>	class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1006	>	public Iterator<Map.Entry<K,V>> iterator() {
1007	>	return new EntryIterator(getFirstEntry());
1008		}
1009
1010	<	public boolean containsKey(Object key) {
1011	<	return inRange(key) && TreeMap.this.containsKey(key);
1010	>	public boolean contains(Object o) {
1011	>	if (!(o instanceof Map.Entry))
1012	>	return false;
1013	>	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1014	>	V value = entry.getValue();
1015	>	Entry<K,V> p = getEntry(entry.getKey());
1016	>	return p != null && valEquals(p.getValue(), value);
1017		}
1018
1019	<	public V get(Object key) {
1020	<	if (!inRange(key))
1021	<	return null;
1022	<	return TreeMap.this.get(key);
1019	>	public boolean remove(Object o) {
1020	>	if (!(o instanceof Map.Entry))
1021	>	return false;
1022	>	Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1023	>	V value = entry.getValue();
1024	>	Entry<K,V> p = getEntry(entry.getKey());
1025	>	if (p != null && valEquals(p.getValue(), value)) {
1026	>	deleteEntry(p);
1027	>	return true;
1028	>	}
1029	>	return false;
1030		}
1031
1032	<	public V put(K key, V value) {
1033	<	if (!inRange(key))
1115	<	throw new IllegalArgumentException("key out of range");
1116	<	return TreeMap.this.put(key, value);
1032	>	public int size() {
1033	>	return TreeMap.this.size();
1034		}
1035
1036	<	public V remove(Object key) {
1037	<	if (!inRange(key))
1121	<	return null;
1122	<	return TreeMap.this.remove(key);
1036	>	public void clear() {
1037	>	TreeMap.this.clear();
1038		}
1039	+	}
1040
1041	<	public Comparator<? super K> comparator() {
1042	<	return comparator;
1041	>	/*
1042	>	* Unlike Values and EntrySet, the KeySet class is static,
1043	>	* delegating to a NavigableMap to allow use by SubMaps, which
1044	>	* outweighs the ugliness of needing type-tests for the following
1045	>	* Iterator methods that are defined appropriately in main versus
1046	>	* submap classes.
1047	>	*/
1048	>
1049	>	Iterator<K> keyIterator() {
1050	>	return new KeyIterator(getFirstEntry());
1051	>	}
1052	>
1053	>	Iterator<K> descendingKeyIterator() {
1054	>	return new DescendingKeyIterator(getFirstEntry());
1055	>	}
1056	>
1057	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1058	>	private final NavigableMap<E, Object> m;
1059	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1060	>
1061	>	public Iterator<E> iterator() {
1062	>	if (m instanceof TreeMap)
1063	>	return ((TreeMap<E,Object>)m).keyIterator();
1064	>	else
1065	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1066		}
1067
1068	<	public K firstKey() {
1069	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1070	<	K first = key(e);
1071	<	if (!toEnd && compare(first, toKey) >= 0)
1072	<	throw new NoSuchElementException();
1134	<	return first;
1068	>	public Iterator<E> descendingIterator() {
1069	>	if (m instanceof TreeMap)
1070	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1071	>	else
1072	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1073		}
1074
1075	<	public K lastKey() {
1076	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1077	<	K last = key(e);
1078	<	if (!fromStart && compare(last, fromKey) < 0)
1079	<	throw new NoSuchElementException();
1080	<	return last;
1075	>	public int size() { return m.size(); }
1076	>	public boolean isEmpty() { return m.isEmpty(); }
1077	>	public boolean contains(Object o) { return m.containsKey(o); }
1078	>	public void clear() { m.clear(); }
1079	>	public E lower(E e) { return m.lowerKey(e); }
1080	>	public E floor(E e) { return m.floorKey(e); }
1081	>	public E ceiling(E e) { return m.ceilingKey(e); }
1082	>	public E higher(E e) { return m.higherKey(e); }
1083	>	public E first() { return m.firstKey(); }
1084	>	public E last() { return m.lastKey(); }
1085	>	public Comparator<? super E> comparator() { return m.comparator(); }
1086	>	public E pollFirst() {
1087	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1088	>	return e == null? null : e.getKey();
1089	>	}
1090	>	public E pollLast() {
1091	>	Map.Entry<E,Object> e = m.pollLastEntry();
1092	>	return e == null? null : e.getKey();
1093	>	}
1094	>	public boolean remove(Object o) {
1095	>	int oldSize = size();
1096	>	m.remove(o);
1097	>	return size() != oldSize;
1098	>	}
1099	>	public NavigableSet<E> navigableSubSet(E fromElement,
1100	>	boolean fromInclusive,
1101	>	E toElement,
1102	>	boolean toInclusive) {
1103	>	return new TreeSet<E>
1104	>	(m.navigableSubMap(fromElement, fromInclusive,
1105	>	toElement,   toInclusive));
1106	>	}
1107	>	public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
1108	>	return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
1109	>	}
1110	>	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
1111	>	return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
1112	>	}
1113	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1114	>	return navigableSubSet(fromElement, true, toElement, false);
1115		}
1116	+	public SortedSet<E> headSet(E toElement) {
1117	+	return navigableHeadSet(toElement, false);
1118	+	}
1119	+	public SortedSet<E> tailSet(E fromElement) {
1120	+	return navigableTailSet(fromElement, true);
1121	+	}
1122	+	public NavigableSet<E> descendingSet() {
1123	+	return new TreeSet(m.descendingMap());
1124	+	}
1125	+	}
1126
1127	<	public Map.Entry<K,V> firstEntry() {
1128	<	TreeMap.Entry<K,V> e = fromStart ?
1129	<	getFirstEntry() : getCeilingEntry(fromKey);
1130	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1131	<	return null;
1132	<	return e;
1127	>	// SubMaps
1128	>
1129	>	abstract class NavigableSubMap extends AbstractMap<K,V>
1130	>	implements NavigableMap<K,V>, java.io.Serializable {
1131	>
1132	>	/**
1133	>	* The low endpoint of this submap in absolute terms.  For ascending
1134	>	* submaps this will be the "first" endpoint; for descending submaps,
1135	>	* the last.  If there is no bound, this field is set to UNBOUNDED.
1136	>	*/
1137	>	K lo;
1138	>
1139	>	/**
1140	>	* Zero if the low endpoint is excluded from this submap, one if
1141	>	* it's included.  This field is unused if lo is UNBOUNDED.
1142	>	*/
1143	>	int loExcluded;
1144	>
1145	>	/**
1146	>	* The high endpoint of this submap in absolute terms.  For ascending
1147	>	* submaps this will be the "last" endpoint; for descending submaps,
1148	>	* the first.  If there is no bound, this field is set to UNBOUNDED.
1149	>	*/
1150	>	K hi;
1151	>
1152	>	/**
1153	>	* Zero if the high endpoint is excluded from this submap, one if
1154	>	* it's included.  This field is unused if hi is UNBOUNDED.
1155	>	*/
1156	>	int hiExcluded;
1157	>
1158	>	NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1159	>	if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
1160	>	throw new IllegalArgumentException("fromKey > toKey");
1161	>	this.lo = lo;
1162	>	this.loExcluded = loExcluded;
1163	>	this.hi = hi;
1164	>	this.hiExcluded = hiExcluded;
1165		}
1166
1167	<	public Map.Entry<K,V> lastEntry() {
1168	<	TreeMap.Entry<K,V> e = toEnd ?
1155	<	getLastEntry() : getLowerEntry(toKey);
1156	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1157	<	return null;
1158	<	return e;
1167	>	public boolean isEmpty() {
1168	>	return entrySet().isEmpty();
1169		}
1170
1171	<	public Map.Entry<K,V> pollFirstEntry() {
1172	<	TreeMap.Entry<K,V> e = fromStart ?
1163	<	getFirstEntry() : getCeilingEntry(fromKey);
1164	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1165	<	return null;
1166	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1167	<	deleteEntry(e);
1168	<	return result;
1171	>	public boolean containsKey(Object key) {
1172	>	return inRange(key) && TreeMap.this.containsKey(key);
1173		}
1174
1175	<	public Map.Entry<K,V> pollLastEntry() {
1176	<	TreeMap.Entry<K,V> e = toEnd ?
1173	<	getLastEntry() : getLowerEntry(toKey);
1174	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1175	>	public V get(Object key) {
1176	>	if (!inRange(key))
1177		return null;
1178	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1177	<	deleteEntry(e);
1178	<	return result;
1178	>	return TreeMap.this.get(key);
1179		}
1180
1181	<	private TreeMap.Entry<K,V> subceiling(K key) {
1182	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1183	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1184	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1181	>	public V put(K key, V value) {
1182	>	if (!inRange(key))
1183	>	throw new IllegalArgumentException("key out of range");
1184	>	return TreeMap.this.put(key, value);
1185	>	}
1186	>
1187	>	public V remove(Object key) {
1188	>	if (!inRange(key))
1189		return null;
1190	<	return e;
1190	>	return TreeMap.this.remove(key);
1191		}
1192
1193		public Map.Entry<K,V> ceilingEntry(K key) {
1194	<	TreeMap.Entry<K,V> e = subceiling(key);
1194	>	TreeMap.Entry<K,V> e = subCeiling(key);
1195		return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1196		}
1197
1198		public K ceilingKey(K key) {
1199	<	TreeMap.Entry<K,V> e = subceiling(key);
1199	>	TreeMap.Entry<K,V> e = subCeiling(key);
1200		return e == null? null : e.key;
1201		}
1202
1199	–
1200	–	private TreeMap.Entry<K,V> subhigher(K key) {
1201	–	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1202	–	getCeilingEntry(fromKey) : getHigherEntry(key);
1203	–	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1204	–	return null;
1205	–	return e;
1206	–	}
1207	–
1203		public Map.Entry<K,V> higherEntry(K key) {
1204	<	TreeMap.Entry<K,V> e = subhigher(key);
1204	>	TreeMap.Entry<K,V> e = subHigher(key);
1205		return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1206		}
1207
1208		public K higherKey(K key) {
1209	<	TreeMap.Entry<K,V> e = subhigher(key);
1209	>	TreeMap.Entry<K,V> e = subHigher(key);
1210		return e == null? null : e.key;
1211		}
1212
1218	–	private TreeMap.Entry<K,V> subfloor(K key) {
1219	–	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1220	–	getLowerEntry(toKey) : getFloorEntry(key);
1221	–	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1222	–	return null;
1223	–	return e;
1224	–	}
1225	–
1213		public Map.Entry<K,V> floorEntry(K key) {
1214	<	TreeMap.Entry<K,V> e = subfloor(key);
1214	>	TreeMap.Entry<K,V> e = subFloor(key);
1215		return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1216		}
1217
1218		public K floorKey(K key) {
1219	<	TreeMap.Entry<K,V> e = subfloor(key);
1219	>	TreeMap.Entry<K,V> e = subFloor(key);
1220		return e == null? null : e.key;
1221		}
1222
1236	–	private TreeMap.Entry<K,V> sublower(K key) {
1237	–	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1238	–	getLowerEntry(toKey) :  getLowerEntry(key);
1239	–	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1240	–	return null;
1241	–	return e;
1242	–	}
1243	–
1223		public Map.Entry<K,V> lowerEntry(K key) {
1224	<	TreeMap.Entry<K,V> e = sublower(key);
1224	>	TreeMap.Entry<K,V> e = subLower(key);
1225		return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1226		}
1227
1228		public K lowerKey(K key) {
1229	<	TreeMap.Entry<K,V> e = sublower(key);
1229	>	TreeMap.Entry<K,V> e = subLower(key);
1230		return e == null? null : e.key;
1231		}
1232
1233	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1233	>	abstract Iterator<K> keyIterator();
1234	>	abstract Iterator<K> descendingKeyIterator();
1235
1236	<	public Set<Map.Entry<K,V>> entrySet() {
1237	<	Set<Map.Entry<K,V>> es = entrySet;
1258	<	return (es != null)? es : (entrySet = new EntrySetView());
1236	>	public NavigableSet<K> descendingKeySet() {
1237	>	return descendingMap().navigableKeySet();
1238		}
1239
1240	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1240	>	// Views
1241	>	transient NavigableMap<K,V> descendingMapView = null;
1242	>	transient Set<Map.Entry<K,V>> entrySetView = null;
1243	>	private transient NavigableSet<K> navigableKeySetView = null;
1244	>
1245	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1246		private transient int size = -1, sizeModCount;
1247
1248		public int size() {
#	Line 1303 | Line 1287 | public class TreeMap<K,V>
1287		}
1288		return false;
1289		}
1290	+	}
1291
1292	<	public Iterator<Map.Entry<K,V>> iterator() {
1293	<	return new SubMapEntryIterator(
1294	<	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1295	<	(toEnd     ? null            : getCeilingEntry(toKey)));
1311	<	}
1292	>	public NavigableSet<K> navigableKeySet() {
1293	>	NavigableSet<K> nksv = navigableKeySetView;
1294	>	return (nksv != null) ? nksv :
1295	>	(navigableKeySetView = new TreeMap.KeySet(this));
1296		}
1297
1298	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1299	<	private transient Set<K> descendingKeySetView = null;
1298	>	public Set<K> keySet() {
1299	>	return navigableKeySet();
1300	>	}
1301
1302	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1303	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1319	<	return (es != null) ? es :
1320	<	(descendingEntrySetView = new DescendingEntrySetView());
1321	<	}
1322	<
1323	<	public Set<K> descendingKeySet() {
1324	<	Set<K> ks = descendingKeySetView;
1325	<	return (ks != null) ? ks :
1326	<	(descendingKeySetView = new DescendingKeySetView());
1327	<	}
1328	<
1329	<	private class DescendingEntrySetView extends EntrySetView {
1330	<	public Iterator<Map.Entry<K,V>> iterator() {
1331	<	return new DescendingSubMapEntryIterator
1332	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1333	<	(fromStart ? null            : getLowerEntry(fromKey)));
1334	<	}
1302	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1303	>	return navigableSubMap(fromKey, true, toKey, false);
1304		}
1305
1306	<	private class DescendingKeySetView extends AbstractSet<K> {
1307	<	public Iterator<K> iterator() {
1308	<	return new Iterator<K>() {
1340	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1341	<
1342	<	public boolean hasNext() { return i.hasNext(); }
1343	<	public K next() { return i.next().getKey(); }
1344	<	public void remove() { i.remove(); }
1345	<	};
1346	<	}
1306	>	public SortedMap<K,V> headMap(K toKey) {
1307	>	return navigableHeadMap(toKey, false);
1308	>	}
1309
1310	<	public int size() {
1311	<	return SubMap.this.size();
1312	<	}
1310	>	public SortedMap<K,V> tailMap(K fromKey) {
1311	>	return navigableTailMap(fromKey, true);
1312	>	}
1313
1314	<	public boolean contains(Object k) {
1315	<	return SubMap.this.containsKey(k);
1316	<	}
1314	>	/** Returns the lowest entry in this submap (absolute ordering) */
1315	>	TreeMap.Entry<K,V> loEntry() {
1316	>	TreeMap.Entry<K,V> result =
1317	>	((lo == UNBOUNDED) ? getFirstEntry() :
1318	>	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1319	>	return (result == null || tooHigh(result.key)) ? null : result;
1320	>	}
1321	>
1322	>	/** Returns the highest key in this submap (absolute ordering) */
1323	>	TreeMap.Entry<K,V> hiEntry() {
1324	>	TreeMap.Entry<K,V> result =
1325	>	((hi == UNBOUNDED) ? getLastEntry() :
1326	>	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1327	>	return (result == null || tooLow(result.key)) ? null : result;
1328	>	}
1329	>
1330	>	/** Polls the lowest entry in this submap (absolute ordering) */
1331	>	Map.Entry<K,V> pollLoEntry() {
1332	>	TreeMap.Entry<K,V> e =
1333	>	((lo == UNBOUNDED) ? getFirstEntry() :
1334	>	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1335	>	if (e == null || tooHigh(e.key))
1336	>	return null;
1337	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1338	>	deleteEntry(e);
1339	>	return result;
1340	>	}
1341	>
1342	>	/** Polls the highest key in this submap (absolute ordering) */
1343	>	Map.Entry<K,V> pollHiEntry() {
1344	>	TreeMap.Entry<K,V> e =
1345	>	((hi == UNBOUNDED) ? getLastEntry() :
1346	>	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1347	>	if (e == null || tooLow(e.key))
1348	>	return null;
1349	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1350	>	deleteEntry(e);
1351	>	return result;
1352	>	}
1353	>
1354	>	// The following four definitions are correct only for
1355	>	// ascending submaps. They are overridden in DescendingSubMap.
1356	>	// They are defined in the base class because the definitions
1357	>	// in DescendingSubMap rely on those for AscendingSubMap.
1358	>
1359	>	/**
1360	>	* Returns the entry corresponding to the ceiling of the specified
1361	>	* key from the perspective of this submap, or null if the submap
1362	>	* contains no such entry.
1363	>	*/
1364	>	TreeMap.Entry<K,V> subCeiling(K key) {
1365	>	if (tooLow(key))
1366	>	return loEntry();
1367	>	TreeMap.Entry<K,V> e = getCeilingEntry(key);
1368	>	return (e == null || tooHigh(e.key)) ? null : e;
1369	>	}
1370	>
1371	>	/**
1372	>	* Returns the entry corresponding to the higher of the specified
1373	>	* key from the perspective of this submap, or null if the submap
1374	>	* contains no such entry.
1375	>	*/
1376	>	TreeMap.Entry<K,V> subHigher(K key) {
1377	>	if (tooLow(key))
1378	>	return loEntry();
1379	>	TreeMap.Entry<K,V> e = getHigherEntry(key);
1380	>	return (e == null || tooHigh(e.key)) ? null : e;
1381		}
1382
1383	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1384	<	if (!inRange2(fromKey))
1383	>	/**
1384	>	* Returns the entry corresponding to the floor of the specified
1385	>	* key from the perspective of this submap, or null if the submap
1386	>	* contains no such entry.
1387	>	*/
1388	>	TreeMap.Entry<K,V> subFloor(K key) {
1389	>	if (tooHigh(key))
1390	>	return hiEntry();
1391	>	TreeMap.Entry<K,V> e = getFloorEntry(key);
1392	>	return (e == null || tooLow(e.key)) ? null : e;
1393	>	}
1394	>
1395	>	/**
1396	>	* Returns the entry corresponding to the lower of the specified
1397	>	* key from the perspective of this submap, or null if the submap
1398	>	* contains no such entry.
1399	>	*/
1400	>	TreeMap.Entry<K,V> subLower(K key) {
1401	>	if (tooHigh(key))
1402	>	return hiEntry();
1403	>	TreeMap.Entry<K,V> e = getLowerEntry(key);
1404	>	return (e == null || tooLow(e.key)) ? null : e;
1405	>	}
1406	>
1407	>	boolean inRange(Object key) {
1408	>	return (lo == UNBOUNDED || compare(key, lo) >= loExcluded)
1409	>	&& (hi == UNBOUNDED || compare(hi, key) >= hiExcluded);
1410	>	}
1411	>
1412	>	boolean inClosedRange(Object key) {
1413	>	return (lo == UNBOUNDED || compare(key, lo) >= 0)
1414	>	&& (hi == UNBOUNDED || compare(hi, key) >= 0);
1415	>	}
1416	>
1417	>	boolean inRange(Object key, boolean inclusive) {
1418	>	return inclusive ? inRange(key) : inClosedRange(key);
1419	>	}
1420	>
1421	>	boolean tooLow(K key) {
1422	>	return lo != UNBOUNDED && compare(key, lo) < loExcluded;
1423	>	}
1424	>
1425	>	boolean tooHigh(K key) {
1426	>	return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
1427	>	}
1428	>	}
1429	>
1430	>	class AscendingSubMap extends NavigableSubMap {
1431	>	private static final long serialVersionUID = 912986545866124060L;
1432	>
1433	>	AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1434	>	super(lo, loExcluded, hi, hiExcluded);
1435	>	}
1436	>
1437	>	public Comparator<? super K> comparator() {
1438	>	return comparator;
1439	>	}
1440	>
1441	>	public NavigableMap<K,V> navigableSubMap(
1442	>	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1443	>	if (!inRange(fromKey, fromInclusive))
1444		throw new IllegalArgumentException("fromKey out of range");
1445	<	if (!inRange2(toKey))
1445	>	if (!inRange(toKey, toInclusive))
1446		throw new IllegalArgumentException("toKey out of range");
1447	<	return new SubMap(fromKey, toKey);
1447	>	return new AscendingSubMap(fromKey, excluded(fromInclusive),
1448	>	toKey,   excluded(toInclusive));
1449		}
1450
1451	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1452	<	if (!inRange2(toKey))
1451	>	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1452	>	if (!inClosedRange(toKey))
1453		throw new IllegalArgumentException("toKey out of range");
1454	<	return new SubMap(fromStart, fromKey, false, toKey);
1454	>	return new AscendingSubMap(lo,    loExcluded,
1455	>	toKey, excluded(inclusive));
1456		}
1457
1458	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1459	<	if (!inRange2(fromKey))
1458	>	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1459	>	if (!inRange(fromKey, inclusive))
1460		throw new IllegalArgumentException("fromKey out of range");
1461	<	return new SubMap(false, fromKey, toEnd, toKey);
1461	>	return new AscendingSubMap(fromKey, excluded(inclusive),
1462	>	hi,      hiExcluded);
1463		}
1464
1465	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1466	<	return navigableSubMap(fromKey, toKey);
1465	>	Iterator<K> keyIterator() {
1466	>	return new SubMapKeyIterator
1467	>	(loEntry(),
1468	>	hi == UNBOUNDED ? null :
1469	>	hiExcluded == 1 ? getCeilingEntry(hi) :
1470	>	getHigherEntry(hi));
1471	>	}
1472	>
1473	>	Iterator<K> descendingKeyIterator() {
1474	>	return new DescendingSubMapKeyIterator
1475	>	(hiEntry(),
1476	>	lo == UNBOUNDED ? null :
1477	>	loExcluded == 1 ? getFloorEntry(lo) :
1478	>	getLowerEntry(lo));
1479		}
1480
1481	<	public SortedMap<K,V> headMap(K toKey) {
1482	<	return navigableHeadMap(toKey);
1481	>	public Set<Map.Entry<K,V>> entrySet() {
1482	>	Set<Map.Entry<K,V>> es = entrySetView;
1483	>	if  (es != null)
1484	>	return es;
1485	>	return entrySetView = new NavigableSubMap.EntrySetView() {
1486	>	public Iterator<Map.Entry<K,V>> iterator() {
1487	>	return new SubMapEntryIterator(loEntry(),
1488	>	hi == UNBOUNDED ? null :
1489	>	hiExcluded == 1 ? getCeilingEntry(hi) :
1490	>	getHigherEntry(hi));
1491	>	}
1492	>	};
1493		}
1494
1495	<	public SortedMap<K,V> tailMap(K fromKey) {
1496	<	return navigableTailMap(fromKey);
1495	>	public K firstKey() {
1496	>	return key(loEntry());
1497	>	}
1498	>
1499	>	public K lastKey() {
1500	>	return key(hiEntry());
1501	>	}
1502	>
1503	>	public Map.Entry<K,V> firstEntry() {
1504	>	return loEntry();
1505	>	}
1506	>
1507	>	public Map.Entry<K,V> lastEntry() {
1508	>	return hiEntry();
1509	>	}
1510	>
1511	>	public Map.Entry<K,V> pollFirstEntry() {
1512	>	return pollLoEntry();
1513	>	}
1514	>
1515	>	public Map.Entry<K,V> pollLastEntry() {
1516	>	return pollHiEntry();
1517	>	}
1518	>
1519	>	public NavigableMap<K,V> descendingMap() {
1520	>	NavigableMap<K,V> m = descendingMapView;
1521	>	return (m != null) ? m :
1522	>	(descendingMapView =
1523	>	new DescendingSubMap(lo, loExcluded, hi, hiExcluded));
1524	>	}
1525	>	}
1526	>
1527	>	class DescendingSubMap extends NavigableSubMap {
1528	>	private static final long serialVersionUID = 912986545866120460L;
1529	>	DescendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1530	>	super(lo, loExcluded, hi, hiExcluded);
1531	>	}
1532	>
1533	>	private final Comparator<? super K> reverseComparator =
1534	>	Collections.reverseOrder(comparator);
1535	>
1536	>	public Comparator<? super K> comparator() {
1537	>	return reverseComparator;
1538	>	}
1539	>
1540	>	public NavigableMap<K,V> navigableSubMap(
1541	>	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1542	>	if (!inRange(fromKey, fromInclusive))
1543	>	throw new IllegalArgumentException("fromKey out of range");
1544	>	if (!inRange(toKey, toInclusive))
1545	>	throw new IllegalArgumentException("toKey out of range");
1546	>	return new DescendingSubMap(toKey,   excluded(toInclusive),
1547	>	fromKey, excluded(fromInclusive));
1548	>	}
1549	>
1550	>	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1551	>	if (!inRange(toKey, inclusive))
1552	>	throw new IllegalArgumentException("toKey out of range");
1553	>	return new DescendingSubMap(toKey, inclusive ? 0:1, hi, hiExcluded);
1554	>	}
1555	>
1556	>	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1557	>	if (!inRange(fromKey, inclusive))
1558	>	throw new IllegalArgumentException("fromKey out of range");
1559	>	return new DescendingSubMap(lo,      loExcluded,
1560	>	fromKey, excluded(inclusive));
1561	>	}
1562	>
1563	>	Iterator<K> keyIterator() {
1564	>	return new DescendingSubMapKeyIterator
1565	>	(hiEntry(),
1566	>	lo == UNBOUNDED ? null :
1567	>	loExcluded == 1 ? getFloorEntry(lo) :
1568	>	getLowerEntry(lo));
1569	>	}
1570	>
1571	>	Iterator<K> descendingKeyIterator() {
1572	>	return new SubMapKeyIterator
1573	>	(loEntry(),
1574	>	hi == UNBOUNDED ? null :
1575	>	hiExcluded == 1 ? getCeilingEntry(hi) :
1576	>	getHigherEntry(hi));
1577	>	}
1578	>
1579	>	public Set<Map.Entry<K,V>> entrySet() {
1580	>	Set<Map.Entry<K,V>> es = entrySetView;
1581	>	if  (es != null)
1582	>	return es;
1583	>	return entrySetView = new NavigableSubMap.EntrySetView() {
1584	>	public Iterator<Map.Entry<K,V>> iterator() {
1585	>	return new DescendingSubMapEntryIterator(hiEntry(),
1586	>	lo == UNBOUNDED ? null :
1587	>	loExcluded == 1 ? getFloorEntry(lo) :
1588	>	getLowerEntry(lo));
1589	>	}
1590	>	};
1591	>	}
1592	>
1593	>	public K firstKey() {
1594	>	return key(hiEntry());
1595	>	}
1596	>
1597	>	public K lastKey() {
1598	>	return key(loEntry());
1599	>	}
1600	>
1601	>	public Map.Entry<K,V> firstEntry() {
1602	>	return hiEntry();
1603		}
1604
1605	<	private boolean inRange(Object key) {
1606	<	return (fromStart || compare(key, fromKey) >= 0) &&
1607	<	(toEnd     || compare(key, toKey)   <  0);
1605	>	public Map.Entry<K,V> lastEntry() {
1606	>	return loEntry();
1607	>	}
1608	>
1609	>	public Map.Entry<K,V> pollFirstEntry() {
1610	>	return pollHiEntry();
1611	>	}
1612	>
1613	>	public Map.Entry<K,V> pollLastEntry() {
1614	>	return pollLoEntry();
1615		}
1616
1617	<	// This form allows the high endpoint (as well as all legit keys)
1618	<	private boolean inRange2(Object key) {
1619	<	return (fromStart || compare(key, fromKey) >= 0) &&
1620	<	(toEnd     || compare(key, toKey)   <= 0);
1617	>	public NavigableMap<K,V> descendingMap() {
1618	>	NavigableMap<K,V> m = descendingMapView;
1619	>	return (m != null) ? m :
1620	>	(descendingMapView =
1621	>	new AscendingSubMap(lo, loExcluded, hi, hiExcluded));
1622		}
1623	+
1624	+	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1625	+	return super.subFloor(key);
1626	+	}
1627	+
1628	+	@Override TreeMap.Entry<K,V> subHigher(K key) {
1629	+	return super.subLower(key);
1630	+	}
1631	+
1632	+	@Override TreeMap.Entry<K,V> subFloor(K key) {
1633	+	return super.subCeiling(key);
1634	+	}
1635	+
1636	+	@Override TreeMap.Entry<K,V> subLower(K key) {
1637	+	return super.subHigher(key);
1638	+	}
1639	+	}
1640	+
1641	+	/**
1642	+	* This class exists solely for the sake of serialization
1643	+	* compatibility with previous releases of TreeMap that did not
1644	+	* support NavigableMap.  It translates an old-version SubMap into
1645	+	* a new-version AscendingSubMap. This class is never otherwise
1646	+	* used.
1647	+	*/
1648	+	private class SubMap extends AbstractMap<K,V>
1649	+	implements SortedMap<K,V>, java.io.Serializable {
1650	+	private static final long serialVersionUID = -6520786458950516097L;
1651	+	private boolean fromStart = false, toEnd = false;
1652	+	private K fromKey, toKey;
1653	+	private Object readResolve() {
1654	+	return new AscendingSubMap
1655	+	(fromStart? ((K)UNBOUNDED) : fromKey, 0,
1656	+	toEnd? ((K)UNBOUNDED) : toKey, 1);
1657	+	}
1658	+	public Set<Map.Entry<K,V>> entrySet() { throw new UnsupportedOperationException(); }
1659	+	public K lastKey() { throw new UnsupportedOperationException(); }
1660	+	public K firstKey() { throw new UnsupportedOperationException(); }
1661	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new UnsupportedOperationException(); }
1662	+	public SortedMap<K,V> headMap(K toKey) { throw new UnsupportedOperationException(); }
1663	+	public SortedMap<K,V> tailMap(K fromKey) { throw new UnsupportedOperationException(); }
1664	+	public Comparator<? super K> comparator() { throw new UnsupportedOperationException(); }
1665		}
1666
1667		/**
#	Line 1410 | Line 1676 | public class TreeMap<K,V>
1676		next = first;
1677		}
1678
1679	<	public boolean hasNext() {
1679	>	public final boolean hasNext() {
1680		return next != null;
1681		}
1682
1683	<	Entry<K,V> nextEntry() {
1683	>	final Entry<K,V> nextEntry() {
1684		if (next == null)
1685		throw new NoSuchElementException();
1686		if (modCount != expectedModCount)
#	Line 1424 | Line 1690 | public class TreeMap<K,V>
1690		return lastReturned;
1691		}
1692
1693	+	final Entry<K,V> prevEntry() {
1694	+	if (next == null)
1695	+	throw new NoSuchElementException();
1696	+	if (modCount != expectedModCount)
1697	+	throw new ConcurrentModificationException();
1698	+	lastReturned = next;
1699	+	next = predecessor(next);
1700	+	return lastReturned;
1701	+	}
1702	+
1703		public void remove() {
1704		if (lastReturned == null)
1705		throw new IllegalStateException();
#	Line 1437 | Line 1713 | public class TreeMap<K,V>
1713		}
1714		}
1715
1716	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1716	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1717		EntryIterator(Entry<K,V> first) {
1718		super(first);
1719		}
#	Line 1446 | Line 1722 | public class TreeMap<K,V>
1722		}
1723		}
1724
1725	<	class KeyIterator extends PrivateEntryIterator<K> {
1725	>	final class ValueIterator extends PrivateEntryIterator<V> {
1726	>	ValueIterator(Entry<K,V> first) {
1727	>	super(first);
1728	>	}
1729	>	public V next() {
1730	>	return nextEntry().value;
1731	>	}
1732	>	}
1733	>
1734	>	final class KeyIterator extends PrivateEntryIterator<K> {
1735		KeyIterator(Entry<K,V> first) {
1736		super(first);
1737		}
#	Line 1455 | Line 1740 | public class TreeMap<K,V>
1740		}
1741		}
1742
1743	<	class ValueIterator extends PrivateEntryIterator<V> {
1744	<	ValueIterator(Entry<K,V> first) {
1743	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1744	>	DescendingKeyIterator(Entry<K,V> first) {
1745		super(first);
1746		}
1747	<	public V next() {
1748	<	return nextEntry().value;
1747	>	public K next() {
1748	>	return prevEntry().key;
1749		}
1750		}
1751
1752	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1753	<	private final K firstExcludedKey;
1752	>	/**
1753	>	* Iterators for SubMaps
1754	>	*/
1755	>	abstract class SubMapIterator<T> implements Iterator<T> {
1756	>	int expectedModCount = TreeMap.this.modCount;
1757	>	Entry<K,V> lastReturned = null;
1758	>	Entry<K,V> next;
1759	>	final K firstExcludedKey;
1760
1761	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	<	super(first);
1763	<	firstExcludedKey = (firstExcluded == null
1473	<	? null
1761	>	SubMapIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	>	next = first;
1763	>	firstExcludedKey = (firstExcluded == null ? null
1764		: firstExcluded.key);
1765		}
1766
1767	<	public boolean hasNext() {
1767	>	public final boolean hasNext() {
1768		return next != null && next.key != firstExcludedKey;
1769		}
1770
1771	<	public Map.Entry<K,V> next() {
1771	>	final Entry<K,V> nextEntry() {
1772		if (next == null || next.key == firstExcludedKey)
1773		throw new NoSuchElementException();
1774	<	return nextEntry();
1775	<	}
1776	<	}
1777	<
1778	<	/**
1489	<	* Base for Descending Iterators.
1490	<	*/
1491	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1492	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1493	<	super(first);
1774	>	if (modCount != expectedModCount)
1775	>	throw new ConcurrentModificationException();
1776	>	lastReturned = next;
1777	>	next = successor(next);
1778	>	return lastReturned;
1779		}
1780
1781	<	Entry<K,V> nextEntry() {
1782	<	if (next == null)
1781	>	final Entry<K,V> prevEntry() {
1782	>	if (next == null || next.key == firstExcludedKey)
1783		throw new NoSuchElementException();
1784		if (modCount != expectedModCount)
1785		throw new ConcurrentModificationException();
#	Line 1502 | Line 1787 | public class TreeMap<K,V>
1787		next = predecessor(next);
1788		return lastReturned;
1789		}
1790	+
1791	+	public void remove() {
1792	+	if (lastReturned == null)
1793	+	throw new IllegalStateException();
1794	+	if (modCount != expectedModCount)
1795	+	throw new ConcurrentModificationException();
1796	+	if (lastReturned.left != null && lastReturned.right != null)
1797	+	next = lastReturned;
1798	+	deleteEntry(lastReturned);
1799	+	expectedModCount++;
1800	+	lastReturned = null;
1801	+	}
1802		}
1803
1804	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1805	<	DescendingEntryIterator(Entry<K,V> first) {
1806	<	super(first);
1804	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1805	>	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1806	>	super(first, firstExcluded);
1807		}
1808		public Map.Entry<K,V> next() {
1809		return nextEntry();
1810		}
1811		}
1812
1813	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1814	<	DescendingKeyIterator(Entry<K,V> first) {
1815	<	super(first);
1813	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1814	>	SubMapKeyIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1815	>	super(first, firstExcluded);
1816		}
1817		public K next() {
1818		return nextEntry().key;
1819		}
1820		}
1821
1822	<
1526	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1527	<	private final K lastExcludedKey;
1528	<
1822	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1823		DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1824	<	super(last);
1531	<	lastExcludedKey = (lastExcluded == null
1532	<	? null
1533	<	: lastExcluded.key);
1534	<	}
1535	<
1536	<	public boolean hasNext() {
1537	<	return next != null && next.key != lastExcludedKey;
1824	>	super(last, lastExcluded);
1825		}
1826
1827		public Map.Entry<K,V> next() {
1828	<	if (next == null || next.key == lastExcludedKey)
1542	<	throw new NoSuchElementException();
1543	<	return nextEntry();
1828	>	return prevEntry();
1829		}
1830	+	}
1831
1832	+	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1833	+	DescendingSubMapKeyIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1834	+	super(last, lastExcluded);
1835	+	}
1836	+	public K next() {
1837	+	return prevEntry().key;
1838	+	}
1839		}
1840
1841		/**
#	Line 1957 | Line 2250 | public class TreeMap<K,V>
2250		}
2251		}
2252
1960	–
1961	–
2253		/**
2254		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2255		* deserialize it).

Diff Legend

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