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.17 by dl, Thu May 26 12:07:07 2005 UTC vs.
Revision 1.32 by dl, Sat Apr 22 16:38:01 2006 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
#	Line 30 | Line 30 | package java.util;
30		* <i>is</i> well-defined even if its ordering is inconsistent with equals; it
31		* just fails to obey the general contract of the <tt>Map</tt> interface.
32		*
33	<	* <p><b>Note that this implementation is not synchronized.</b> If multiple
34	<	* threads access a map concurrently, and at least one of the threads modifies
35	<	* the map structurally, it <i>must</i> be synchronized externally.  (A
36	<	* structural modification is any operation that adds or deletes one or more
37	<	* mappings; merely changing the value associated with an existing key is not
38	<	* a structural modification.)  This is typically accomplished by
39	<	* synchronizing on some object that naturally encapsulates the map.  If no
40	<	* such object exists, the map should be "wrapped" using the
41	<	* <tt>Collections.synchronizedMap</tt> method.  This is best done at creation
42	<	* time, to prevent accidental unsynchronized access to the map:
43	<	* <pre>
44	<	*     Map m = Collections.synchronizedMap(new TreeMap(...));
45	<	* </pre>
33	>	* <p><strong>Note that this implementation is not synchronized.</strong>
34	>	* If multiple threads access a map concurrently, and at least one of the
35	>	* threads modifies the map structurally, it <i>must</i> be synchronized
36	>	* externally.  (A structural modification is any operation that adds or
37	>	* deletes one or more mappings; merely changing the value associated
38	>	* with an existing key is not a structural modification.)  This is
39	>	* typically accomplished by synchronizing on some object that naturally
40	>	* encapsulates the map.
41	>	* If no such object exists, the map should be "wrapped" using the
42	>	* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
43	>	* method.  This is best done at creation time, to prevent accidental
44	>	* unsynchronized access to the map: <pre>
45	>	*   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
46		*
47		* <p>The iterators returned by the <tt>iterator</tt> method of the collections
48		* returned by all of this class's "collection view methods" are
#	Line 82 | Line 82 | package java.util;
82		* @see Comparable
83		* @see Comparator
84		* @see Collection
85	–	* @see Collections#synchronizedMap(Map)
85		* @since 1.2
86		*/
87
#	Line 96 | Line 95 | public class TreeMap<K,V>
95		*
96		* @serial
97		*/
98	<	private Comparator<? super K> comparator = null;
98	>	private final Comparator<? super K> comparator;
99
100		private transient Entry<K,V> root = null;
101
#	Line 126 | Line 125 | public class TreeMap<K,V>
125		* <tt>ClassCastException</tt>.
126		*/
127		public TreeMap() {
128	+	comparator = null;
129		}
130
131		/**
#	Line 161 | Line 161 | public class TreeMap<K,V>
161		* @throws NullPointerException if the specified map is null
162		*/
163		public TreeMap(Map<? extends K, ? extends V> m) {
164	+	comparator = null;
165		putAll(m);
166		}
167
#	Line 216 | Line 217 | public class TreeMap<K,V>
217		* specified value.  More formally, returns <tt>true</tt> if and only if
218		* this map contains at least one mapping to a value <tt>v</tt> such
219		* that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
220	<	* operation requires time linear in the map size.
220	>	* operation will probably require time linear in the map size for
221	>	* most implementations.
222		*
223		* @param value value whose presence in this map is to be tested
224		* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
#	Line 226 | Line 228 | public class TreeMap<K,V>
228		public boolean containsValue(Object value) {
229		return (root==null ? false :
230		(value==null ? valueSearchNull(root)
231	<	: valueSearchNonNull(root, value)));
231	>	: valueSearchNonNull(root, value)));
232		}
233
234		private boolean valueSearchNull(Entry n) {
#	Line 235 | Line 237 | public class TreeMap<K,V>
237
238		// Check left and right subtrees for value
239		return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
240	>	(n.right != null && valueSearchNull(n.right));
241		}
242
243		private boolean valueSearchNonNull(Entry n, Object value) {
#	Line 245 | Line 247 | public class TreeMap<K,V>
247
248		// Check left and right subtrees for value
249		return (n.left  != null && valueSearchNonNull(n.left, value)) ||
250	<	(n.right != null && valueSearchNonNull(n.right, value));
250	>	(n.right != null && valueSearchNonNull(n.right, value));
251		}
252
253		/**
254	<	* Returns the value to which this map maps the specified key, or
255	<	* <tt>null</tt> if the map contains no mapping for the key.  A return
256	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
257	<	* map contains no mapping for the key; it's also possible that the map
258	<	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey}
259	<	* operation may be used to distinguish these two cases.
254	>	* Returns the value to which the specified key is mapped,
255	>	* or {@code null} if this map contains no mapping for the key.
256	>	*
257	>	* <p>More formally, if this map contains a mapping from a key
258	>	* {@code k} to a value {@code v} such that {@code key} compares
259	>	* equal to {@code k} according to the map's ordering, then this
260	>	* method returns {@code v}; otherwise it returns {@code null}.
261	>	* (There can be at most one such mapping.)
262	>	*
263	>	* <p>A return value of {@code null} does not <i>necessarily</i>
264	>	* indicate that the map contains no mapping for the key; it's also
265	>	* possible that the map explicitly maps the key to {@code null}.
266	>	* The {@link #containsKey containsKey} operation may be used to
267	>	* distinguish these two cases.
268		*
259	–	* @param key key whose associated value is to be returned
260	–	* @return the value to which this map maps the specified key, or
261	–	*         <tt>null</tt> if the map contains no mapping for the key
269		* @throws ClassCastException if the specified key cannot be compared
270		*         with the keys currently in the map
271		* @throws NullPointerException if the specified key is null
#	Line 330 | Line 337 | public class TreeMap<K,V>
337		*         and this map uses natural ordering, or its comparator
338		*         does not permit null keys
339		*/
340	<	private Entry<K,V> getEntry(Object key) {
340	>	final Entry<K,V> getEntry(Object key) {
341		// Offload comparator-based version for sake of performance
342		if (comparator != null)
343		return getEntryUsingComparator(key);
344	+	if (key == null)
345	+	throw new NullPointerException();
346		Comparable<? super K> k = (Comparable<? super K>) key;
347		Entry<K,V> p = root;
348		while (p != null) {
#	Line 352 | Line 361 | public class TreeMap<K,V>
361		* Version of getEntry using comparator. Split off from getEntry
362		* for performance. (This is not worth doing for most methods,
363		* that are less dependent on comparator performance, but is
364	<	* worthwhile here.)
364	>	* worthwhile for get and put.)
365		*/
366	<	private Entry<K,V> getEntryUsingComparator(Object key) {
366	>	final Entry<K,V> getEntryUsingComparator(Object key) {
367		K k = (K) key;
368		Comparator<? super K> cpr = comparator;
369		Entry<K,V> p = root;
#	Line 376 | Line 385 | public class TreeMap<K,V>
385		* key; if no such entry exists (i.e., the greatest key in the Tree is less
386		* than the specified key), returns <tt>null</tt>.
387		*/
388	<	private Entry<K,V> getCeilingEntry(K key) {
388	>	final Entry<K,V> getCeilingEntry(K key) {
389		Entry<K,V> p = root;
390	<	if (p==null)
382	<	return null;
383	<
384	<	while (true) {
390	>	while (p != null) {
391		int cmp = compare(key, p.key);
392		if (cmp < 0) {
393		if (p.left != null)
#	Line 403 | Line 409 | public class TreeMap<K,V>
409		} else
410		return p;
411		}
412	+	return null;
413		}
414
415		/**
#	Line 410 | Line 417 | public class TreeMap<K,V>
417		* exists, returns the entry for the greatest key less than the specified
418		* key; if no such entry exists, returns <tt>null</tt>.
419		*/
420	<	private Entry<K,V> getFloorEntry(K key) {
420	>	final Entry<K,V> getFloorEntry(K key) {
421		Entry<K,V> p = root;
422	<	if (p==null)
416	<	return null;
417	<
418	<	while (true) {
422	>	while (p != null) {
423		int cmp = compare(key, p.key);
424		if (cmp > 0) {
425		if (p.right != null)
#	Line 438 | Line 442 | public class TreeMap<K,V>
442		return p;
443
444		}
445	+	return null;
446		}
447
448		/**
#	Line 446 | Line 451 | public class TreeMap<K,V>
451		* key greater than the specified key; if no such entry exists
452		* returns <tt>null</tt>.
453		*/
454	<	private Entry<K,V> getHigherEntry(K key) {
454	>	final Entry<K,V> getHigherEntry(K key) {
455		Entry<K,V> p = root;
456	<	if (p==null)
452	<	return null;
453	<
454	<	while (true) {
456	>	while (p != null) {
457		int cmp = compare(key, p.key);
458		if (cmp < 0) {
459		if (p.left != null)
#	Line 472 | Line 474 | public class TreeMap<K,V>
474		}
475		}
476		}
477	+	return null;
478		}
479
480		/**
#	Line 479 | Line 482 | public class TreeMap<K,V>
482		* no such entry exists (i.e., the least key in the Tree is greater than
483		* the specified key), returns <tt>null</tt>.
484		*/
485	<	private Entry<K,V> getLowerEntry(K key) {
485	>	final Entry<K,V> getLowerEntry(K key) {
486		Entry<K,V> p = root;
487	<	if (p==null)
485	<	return null;
486	<
487	<	while (true) {
487	>	while (p != null) {
488		int cmp = compare(key, p.key);
489		if (cmp > 0) {
490		if (p.right != null)
#	Line 505 | Line 505 | public class TreeMap<K,V>
505		}
506		}
507		}
508	+	return null;
509		}
510
511		/**
512		* Returns the key corresponding to the specified Entry.
513		* @throws NoSuchElementException if the Entry is null
514		*/
515	<	private static <K> K key(Entry<K,?> e) {
515	>	static <K> K key(Entry<K,?> e) {
516		if (e==null)
517		throw new NoSuchElementException();
518		return e.key;
#	Line 519 | Line 520 | public class TreeMap<K,V>
520
521		/**
522		* Associates the specified value with the specified key in this map.
523	<	* If the map previously contained a mapping for this key, the old
523	>	* If the map previously contained a mapping for the key, the old
524		* value is replaced.
525		*
526		* @param key key with which the specified value is to be associated
#	Line 536 | Line 537 | public class TreeMap<K,V>
537		*         does not permit null keys
538		*/
539		public V put(K key, V value) {
540	<	Entry<K,V> t = root;
540	>	// Offload comparator-based version for sake of performance
541	>	if (comparator != null)
542	>	return putUsingComparator(key, value);
543	>	if (key == null)
544	>	throw new NullPointerException();
545	>	Comparable<? super K> k = (Comparable<? super K>) key;
546
547	<	if (t == null) {
548	<	if (key == null) {
549	<	if (comparator == null)
550	<	throw new NullPointerException();
551	<	comparator.compare(key, key);
547	>	Entry<K,V> t = root;
548	>	while (t != null) {
549	>	int cmp = k.compareTo(t.key);
550	>	if (cmp == 0) {
551	>	return t.setValue(value);
552	>	} else if (cmp < 0) {
553	>	if (t.left != null) {
554	>	t = t.left;
555	>	} else {
556	>	incrementSize();
557	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
558	>	return null;
559	>	}
560	>	} else { // cmp > 0
561	>	if (t.right != null) {
562	>	t = t.right;
563	>	} else {
564	>	incrementSize();
565	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
566	>	return null;
567	>	}
568		}
547	–	incrementSize();
548	–	root = new Entry<K,V>(key, value, null);
549	–	return null;
569		}
570	+	incrementSize();
571	+	root = new Entry<K,V>(key, value, null);
572	+	return null;
573	+	}
574
575	<	while (true) {
576	<	int cmp = compare(key, t.key);
575	>	/**
576	>	* Version of put using comparator. Split off from put for
577	>	* performance.
578	>	*/
579	>	final V putUsingComparator(K key, V value) {
580	>	Comparator<? super K> cpr = comparator;
581	>	Entry<K,V> t = root;
582	>	while (t != null) {
583	>	int cmp = cpr.compare(key, t.key);
584		if (cmp == 0) {
585		return t.setValue(value);
586		} else if (cmp < 0) {
#	Line 558 | Line 588 | public class TreeMap<K,V>
588		t = t.left;
589		} else {
590		incrementSize();
591	<	t.left = new Entry<K,V>(key, value, t);
562	<	fixAfterInsertion(t.left);
591	>	fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
592		return null;
593		}
594		} else { // cmp > 0
#	Line 567 | Line 596 | public class TreeMap<K,V>
596		t = t.right;
597		} else {
598		incrementSize();
599	<	t.right = new Entry<K,V>(key, value, t);
571	<	fixAfterInsertion(t.right);
599	>	fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
600		return null;
601		}
602		}
603		}
604	+	cpr.compare(key, key); // type check
605	+	incrementSize();
606	+	root = new Entry<K,V>(key, value, null);
607	+	return null;
608		}
609
610		/**
#	Line 628 | Line 660 | public class TreeMap<K,V>
660		clone.size = 0;
661		clone.modCount = 0;
662		clone.entrySet = null;
663	<	clone.descendingEntrySet = null;
664	<	clone.descendingKeySet = null;
663	>	clone.navigableKeySet = null;
664	>	clone.descendingMap = null;
665
666		// Initialize clone with our mappings
667		try {
#	Line 643 | Line 675 | public class TreeMap<K,V>
675
676		// NavigableMap API methods
677
678	+	/**
679	+	* @since 1.6
680	+	*/
681		public Map.Entry<K,V> firstEntry() {
682		Entry<K,V> e = getFirstEntry();
683		return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
684		}
685
686	+	/**
687	+	* @since 1.6
688	+	*/
689		public Map.Entry<K,V> lastEntry() {
690		Entry<K,V> e = getLastEntry();
691		return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
692		}
693
694	+	/**
695	+	* @since 1.6
696	+	*/
697		public Map.Entry<K,V> pollFirstEntry() {
698		Entry<K,V> p = getFirstEntry();
699		if (p == null)
#	Line 662 | Line 703 | public class TreeMap<K,V>
703		return result;
704		}
705
706	+	/**
707	+	* @since 1.6
708	+	*/
709		public Map.Entry<K,V> pollLastEntry() {
710		Entry<K,V> p = getLastEntry();
711		if (p == null)
#	Line 676 | Line 720 | public class TreeMap<K,V>
720		* @throws NullPointerException if the specified key is null
721		*         and this map uses natural ordering, or its comparator
722		*         does not permit null keys
723	+	* @since 1.6
724		*/
725		public Map.Entry<K,V> lowerEntry(K key) {
726		Entry<K,V> e =  getLowerEntry(key);
#	Line 687 | Line 732 | public class TreeMap<K,V>
732		* @throws NullPointerException if the specified key is null
733		*         and this map uses natural ordering, or its comparator
734		*         does not permit null keys
735	+	* @since 1.6
736		*/
737		public K lowerKey(K key) {
738		Entry<K,V> e =  getLowerEntry(key);
#	Line 698 | Line 744 | public class TreeMap<K,V>
744		* @throws NullPointerException if the specified key is null
745		*         and this map uses natural ordering, or its comparator
746		*         does not permit null keys
747	+	* @since 1.6
748		*/
749		public Map.Entry<K,V> floorEntry(K key) {
750		Entry<K,V> e = getFloorEntry(key);
#	Line 709 | Line 756 | public class TreeMap<K,V>
756		* @throws NullPointerException if the specified key is null
757		*         and this map uses natural ordering, or its comparator
758		*         does not permit null keys
759	+	* @since 1.6
760		*/
761		public K floorKey(K key) {
762		Entry<K,V> e = getFloorEntry(key);
#	Line 720 | Line 768 | public class TreeMap<K,V>
768		* @throws NullPointerException if the specified key is null
769		*         and this map uses natural ordering, or its comparator
770		*         does not permit null keys
771	+	* @since 1.6
772		*/
773		public Map.Entry<K,V> ceilingEntry(K key) {
774		Entry<K,V> e = getCeilingEntry(key);
#	Line 731 | Line 780 | public class TreeMap<K,V>
780		* @throws NullPointerException if the specified key is null
781		*         and this map uses natural ordering, or its comparator
782		*         does not permit null keys
783	+	* @since 1.6
784		*/
785		public K ceilingKey(K key) {
786		Entry<K,V> e = getCeilingEntry(key);
#	Line 742 | Line 792 | public class TreeMap<K,V>
792		* @throws NullPointerException if the specified key is null
793		*         and this map uses natural ordering, or its comparator
794		*         does not permit null keys
795	+	* @since 1.6
796		*/
797		public Map.Entry<K,V> higherEntry(K key) {
798		Entry<K,V> e = getHigherEntry(key);
#	Line 753 | Line 804 | public class TreeMap<K,V>
804		* @throws NullPointerException if the specified key is null
805		*         and this map uses natural ordering, or its comparator
806		*         does not permit null keys
807	+	* @since 1.6
808		*/
809		public K higherKey(K key) {
810		Entry<K,V> e = getHigherEntry(key);
#	Line 766 | Line 818 | public class TreeMap<K,V>
818		* the first time this view is requested.  Views are stateless, so
819		* there's no reason to create more than one.
820		*/
821	<	private transient Set<Map.Entry<K,V>> entrySet = null;
822	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
823	<	private transient Set<K> descendingKeySet = null;
821	>	private transient EntrySet entrySet = null;
822	>	private transient KeySet<K> navigableKeySet = null;
823	>	private transient NavigableMap<K,V> descendingMap = null;
824
825		/**
826		* Returns a {@link Set} view of the keys contained in this map.
#	Line 785 | Line 837 | public class TreeMap<K,V>
837		* operations.
838		*/
839		public Set<K> keySet() {
840	<	Set<K> ks = keySet;
789	<	return (ks != null) ? ks : (keySet = new KeySet());
840	>	return navigableKeySet();
841		}
842
843	<	class KeySet extends AbstractSet<K> {
844	<	public Iterator<K> iterator() {
845	<	return new KeyIterator(getFirstEntry());
846	<	}
847	<
848	<	public int size() {
849	<	return TreeMap.this.size();
799	<	}
800	<
801	<	public boolean contains(Object o) {
802	<	return containsKey(o);
803	<	}
804	<
805	<	public boolean remove(Object o) {
806	<	int oldSize = size;
807	<	TreeMap.this.remove(o);
808	<	return size != oldSize;
809	<	}
843	>	/**
844	>	* @since 1.6
845	>	*/
846	>	public NavigableSet<K> navigableKeySet() {
847	>	KeySet<K> nks = navigableKeySet;
848	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
849	>	}
850
851	<	public void clear() {
852	<	TreeMap.this.clear();
853	<	}
851	>	/**
852	>	* @since 1.6
853	>	*/
854	>	public NavigableSet<K> descendingKeySet() {
855	>	return descendingMap().navigableKeySet();
856		}
857
858		/**
#	Line 833 | Line 875 | public class TreeMap<K,V>
875		return (vs != null) ? vs : (values = new Values());
876		}
877
878	+	/**
879	+	* Returns a {@link Set} view of the mappings contained in this map.
880	+	* The set's iterator returns the entries in ascending key order.
881	+	* The set is backed by the map, so changes to the map are
882	+	* reflected in the set, and vice-versa.  If the map is modified
883	+	* while an iteration over the set is in progress (except through
884	+	* the iterator's own <tt>remove</tt> operation, or through the
885	+	* <tt>setValue</tt> operation on a map entry returned by the
886	+	* iterator) the results of the iteration are undefined.  The set
887	+	* supports element removal, which removes the corresponding
888	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
889	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
890	+	* <tt>clear</tt> operations.  It does not support the
891	+	* <tt>add</tt> or <tt>addAll</tt> operations.
892	+	*/
893	+	public Set<Map.Entry<K,V>> entrySet() {
894	+	EntrySet es = entrySet;
895	+	return (es != null) ? es : (entrySet = new EntrySet());
896	+	}
897	+
898	+	/**
899	+	* @since 1.6
900	+	*/
901	+	public NavigableMap<K, V> descendingMap() {
902	+	NavigableMap<K, V> km = descendingMap;
903	+	return (km != null) ? km :
904	+	(descendingMap = new DescendingSubMap(this,
905	+	true, null, true,
906	+	true, null, true));
907	+	}
908	+
909	+	/**
910	+	* @throws ClassCastException       {@inheritDoc}
911	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
912	+	*         null and this map uses natural ordering, or its comparator
913	+	*         does not permit null keys
914	+	* @throws IllegalArgumentException {@inheritDoc}
915	+	* @since 1.6
916	+	*/
917	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
918	+	K toKey,   boolean toInclusive) {
919	+	return new AscendingSubMap(this,
920	+	false, fromKey, fromInclusive,
921	+	false, toKey,   toInclusive);
922	+	}
923	+
924	+	/**
925	+	* @throws ClassCastException       {@inheritDoc}
926	+	* @throws NullPointerException if <tt>toKey</tt> is null
927	+	*         and this map uses natural ordering, or its comparator
928	+	*         does not permit null keys
929	+	* @throws IllegalArgumentException {@inheritDoc}
930	+	* @since 1.6
931	+	*/
932	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
933	+	return new AscendingSubMap(this,
934	+	true,  null,  true,
935	+	false, toKey, inclusive);
936	+	}
937	+
938	+	/**
939	+	* @throws ClassCastException       {@inheritDoc}
940	+	* @throws NullPointerException if <tt>fromKey</tt> is null
941	+	*         and this map uses natural ordering, or its comparator
942	+	*         does not permit null keys
943	+	* @throws IllegalArgumentException {@inheritDoc}
944	+	* @since 1.6
945	+	*/
946	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
947	+	return new AscendingSubMap(this,
948	+	false, fromKey, inclusive,
949	+	true,  null,    true);
950	+	}
951	+
952	+	/**
953	+	* @throws ClassCastException       {@inheritDoc}
954	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
955	+	*         null and this map uses natural ordering, or its comparator
956	+	*         does not permit null keys
957	+	* @throws IllegalArgumentException {@inheritDoc}
958	+	*/
959	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
960	+	return subMap(fromKey, true, toKey, false);
961	+	}
962	+
963	+	/**
964	+	* @throws ClassCastException       {@inheritDoc}
965	+	* @throws NullPointerException if <tt>toKey</tt> is null
966	+	*         and this map uses natural ordering, or its comparator
967	+	*         does not permit null keys
968	+	* @throws IllegalArgumentException {@inheritDoc}
969	+	*/
970	+	public SortedMap<K,V> headMap(K toKey) {
971	+	return headMap(toKey, false);
972	+	}
973	+
974	+	/**
975	+	* @throws ClassCastException       {@inheritDoc}
976	+	* @throws NullPointerException if <tt>fromKey</tt> is null
977	+	*         and this map uses natural ordering, or its comparator
978	+	*         does not permit null keys
979	+	* @throws IllegalArgumentException {@inheritDoc}
980	+	*/
981	+	public SortedMap<K,V> tailMap(K fromKey) {
982	+	return tailMap(fromKey, true);
983	+	}
984	+
985	+	// View class support
986	+
987		class Values extends AbstractCollection<V> {
988		public Iterator<V> iterator() {
989		return new ValueIterator(getFirstEntry());
#	Line 864 | Line 1015 | public class TreeMap<K,V>
1015		}
1016		}
1017
867	–	/**
868	–	* Returns a {@link Set} view of the mappings contained in this map.
869	–	* The set's iterator returns the entries in ascending key order.
870	–	* The set is backed by the map, so changes to the map are
871	–	* reflected in the set, and vice-versa.  If the map is modified
872	–	* while an iteration over the set is in progress (except through
873	–	* the iterator's own <tt>remove</tt> operation, or through the
874	–	* <tt>setValue</tt> operation on a map entry returned by the
875	–	* iterator) the results of the iteration are undefined.  The set
876	–	* supports element removal, which removes the corresponding
877	–	* mapping from the map, via the <tt>Iterator.remove</tt>,
878	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
879	–	* <tt>clear</tt> operations.  It does not support the
880	–	* <tt>add</tt> or <tt>addAll</tt> operations.
881	–	*/
882	–	public Set<Map.Entry<K,V>> entrySet() {
883	–	Set<Map.Entry<K,V>> es = entrySet;
884	–	return (es != null) ? es : (entrySet = new EntrySet());
885	–	}
886	–
1018		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1019		public Iterator<Map.Entry<K,V>> iterator() {
1020		return new EntryIterator(getFirstEntry());
#	Line 920 | Line 1051 | public class TreeMap<K,V>
1051		}
1052		}
1053
1054	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1055	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
1056	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1057	<	}
1054	>	/*
1055	>	* Unlike Values and EntrySet, the KeySet class is static,
1056	>	* delegating to a NavigableMap to allow use by SubMaps, which
1057	>	* outweighs the ugliness of needing type-tests for the following
1058	>	* Iterator methods that are defined appropriately in main versus
1059	>	* submap classes.
1060	>	*/
1061
1062	<	class DescendingEntrySet extends EntrySet {
1063	<	public Iterator<Map.Entry<K,V>> iterator() {
930	<	return new DescendingEntryIterator(getLastEntry());
931	<	}
1062	>	Iterator<K> keyIterator() {
1063	>	return new KeyIterator(getFirstEntry());
1064		}
1065
1066	<	public Set<K> descendingKeySet() {
1067	<	Set<K> ks = descendingKeySet;
936	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1066	>	Iterator<K> descendingKeyIterator() {
1067	>	return new DescendingKeyIterator(getFirstEntry());
1068		}
1069
1070	<	class DescendingKeySet extends KeySet {
1071	<	public Iterator<K> iterator() {
1072	<	return new DescendingKeyIterator(getLastEntry());
1070	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1071	>	private final NavigableMap<E, Object> m;
1072	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1073	>
1074	>	public Iterator<E> iterator() {
1075	>	if (m instanceof TreeMap)
1076	>	return ((TreeMap<E,Object>)m).keyIterator();
1077	>	else
1078	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1079		}
943	–	}
1080
1081	<	/**
1082	<	* @throws ClassCastException       {@inheritDoc}
1083	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1084	<	*         null and this map uses natural ordering, or its comparator
1085	<	*         does not permit null keys
1086	<	* @throws IllegalArgumentException {@inheritDoc}
1087	<	*/
1088	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1089	<	return new SubMap(fromKey, toKey);
1081	>	public Iterator<E> descendingIterator() {
1082	>	if (m instanceof TreeMap)
1083	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1084	>	else
1085	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1086	>	}
1087	>
1088	>	public int size() { return m.size(); }
1089	>	public boolean isEmpty() { return m.isEmpty(); }
1090	>	public boolean contains(Object o) { return m.containsKey(o); }
1091	>	public void clear() { m.clear(); }
1092	>	public E lower(E e) { return m.lowerKey(e); }
1093	>	public E floor(E e) { return m.floorKey(e); }
1094	>	public E ceiling(E e) { return m.ceilingKey(e); }
1095	>	public E higher(E e) { return m.higherKey(e); }
1096	>	public E first() { return m.firstKey(); }
1097	>	public E last() { return m.lastKey(); }
1098	>	public Comparator<? super E> comparator() { return m.comparator(); }
1099	>	public E pollFirst() {
1100	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1101	>	return e == null? null : e.getKey();
1102	>	}
1103	>	public E pollLast() {
1104	>	Map.Entry<E,Object> e = m.pollLastEntry();
1105	>	return e == null? null : e.getKey();
1106	>	}
1107	>	public boolean remove(Object o) {
1108	>	int oldSize = size();
1109	>	m.remove(o);
1110	>	return size() != oldSize;
1111	>	}
1112	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1113	>	E toElement, boolean toInclusive) {
1114	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1115	>	toElement,   toInclusive));
1116	>	}
1117	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1118	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1119	>	}
1120	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1121	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1122	>	}
1123	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1124	>	return subSet(fromElement, true, toElement, false);
1125	>	}
1126	>	public SortedSet<E> headSet(E toElement) {
1127	>	return headSet(toElement, false);
1128	>	}
1129	>	public SortedSet<E> tailSet(E fromElement) {
1130	>	return tailSet(fromElement, true);
1131	>	}
1132	>	public NavigableSet<E> descendingSet() {
1133	>	return new TreeSet(m.descendingMap());
1134	>	}
1135		}
1136
1137		/**
1138	<	* @throws ClassCastException       {@inheritDoc}
958	<	* @throws NullPointerException if <tt>toKey</tt> is null
959	<	*         and this map uses natural ordering, or its comparator
960	<	*         does not permit null keys
961	<	* @throws IllegalArgumentException {@inheritDoc}
1138	>	* Base class for TreeMap Iterators
1139		*/
1140	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1141	<	return new SubMap(toKey, true);
1140	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1141	>	Entry<K,V> next;
1142	>	Entry<K,V> lastReturned;
1143	>	int expectedModCount;
1144	>
1145	>	PrivateEntryIterator(Entry<K,V> first) {
1146	>	expectedModCount = modCount;
1147	>	lastReturned = null;
1148	>	next = first;
1149	>	}
1150	>
1151	>	public final boolean hasNext() {
1152	>	return next != null;
1153	>	}
1154	>
1155	>	final Entry<K,V> nextEntry() {
1156	>	Entry<K,V> e = lastReturned = next;
1157	>	if (e == null)
1158	>	throw new NoSuchElementException();
1159	>	if (modCount != expectedModCount)
1160	>	throw new ConcurrentModificationException();
1161	>	next = successor(e);
1162	>	return e;
1163	>	}
1164	>
1165	>	final Entry<K,V> prevEntry() {
1166	>	Entry<K,V> e = lastReturned= next;
1167	>	if (e == null)
1168	>	throw new NoSuchElementException();
1169	>	if (modCount != expectedModCount)
1170	>	throw new ConcurrentModificationException();
1171	>	next = predecessor(e);
1172	>	return e;
1173	>	}
1174	>
1175	>	public void remove() {
1176	>	if (lastReturned == null)
1177	>	throw new IllegalStateException();
1178	>	if (modCount != expectedModCount)
1179	>	throw new ConcurrentModificationException();
1180	>	if (lastReturned.left != null && lastReturned.right != null)
1181	>	next = lastReturned;
1182	>	deleteEntry(lastReturned);
1183	>	expectedModCount++;
1184	>	lastReturned = null;
1185	>	}
1186		}
1187
1188	<	/**
1189	<	* @throws ClassCastException       {@inheritDoc}
1190	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1191	<	*         and this map uses natural ordering, or its comparator
1192	<	*         does not permit null keys
1193	<	* @throws IllegalArgumentException {@inheritDoc}
1194	<	*/
974	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
975	<	return new SubMap(fromKey, false);
1188	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1189	>	EntryIterator(Entry<K,V> first) {
1190	>	super(first);
1191	>	}
1192	>	public Map.Entry<K,V> next() {
1193	>	return nextEntry();
1194	>	}
1195		}
1196
1197	<	/**
1198	<	* Equivalent to {@link #navigableSubMap} but with a return type
1199	<	* conforming to the <tt>SortedMap</tt> interface.
1200	<	*
1201	<	* <p>{@inheritDoc}
1202	<	*
1203	<	* @throws ClassCastException       {@inheritDoc}
985	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
986	<	*         null and this map uses natural ordering, or its comparator
987	<	*         does not permit null keys
988	<	* @throws IllegalArgumentException {@inheritDoc}
989	<	*/
990	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
991	<	return new SubMap(fromKey, toKey);
1197	>	final class ValueIterator extends PrivateEntryIterator<V> {
1198	>	ValueIterator(Entry<K,V> first) {
1199	>	super(first);
1200	>	}
1201	>	public V next() {
1202	>	return nextEntry().value;
1203	>	}
1204		}
1205
1206	<	/**
1207	<	* Equivalent to {@link #navigableHeadMap} but with a return type
1208	<	* conforming to the <tt>SortedMap</tt> interface.
1209	<	*
1210	<	* <p>{@inheritDoc}
1211	<	*
1212	<	* @throws ClassCastException       {@inheritDoc}
1001	<	* @throws NullPointerException if <tt>toKey</tt> is null
1002	<	*         and this map uses natural ordering, or its comparator
1003	<	*         does not permit null keys
1004	<	* @throws IllegalArgumentException {@inheritDoc}
1005	<	*/
1006	<	public SortedMap<K,V> headMap(K toKey) {
1007	<	return new SubMap(toKey, true);
1206	>	final class KeyIterator extends PrivateEntryIterator<K> {
1207	>	KeyIterator(Entry<K,V> first) {
1208	>	super(first);
1209	>	}
1210	>	public K next() {
1211	>	return nextEntry().key;
1212	>	}
1213		}
1214
1215	<	/**
1216	<	* Equivalent to {@link #navigableTailMap} but with a return type
1217	<	* conforming to the <tt>SortedMap</tt> interface.
1218	<	*
1219	<	* <p>{@inheritDoc}
1220	<	*
1221	<	* @throws ClassCastException       {@inheritDoc}
1017	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1018	<	*         and this map uses natural ordering, or its comparator
1019	<	*         does not permit null keys
1020	<	* @throws IllegalArgumentException {@inheritDoc}
1021	<	*/
1022	<	public SortedMap<K,V> tailMap(K fromKey) {
1023	<	return new SubMap(fromKey, false);
1215	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1216	>	DescendingKeyIterator(Entry<K,V> first) {
1217	>	super(first);
1218	>	}
1219	>	public K next() {
1220	>	return prevEntry().key;
1221	>	}
1222		}
1223
1224	<	private class SubMap
1027	<	extends AbstractMap<K,V>
1028	<	implements NavigableMap<K,V>, java.io.Serializable {
1029	<	private static final long serialVersionUID = -6520786458950516097L;
1224	>	// SubMaps
1225
1226	<	/**
1227	<	* fromKey is significant only if fromStart is false.  Similarly,
1228	<	* toKey is significant only if toStart is false.
1226	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1227	>	implements NavigableMap<K,V>, java.io.Serializable {
1228	>	/*
1229	>	* The backing map.
1230		*/
1231	<	private boolean fromStart = false, toEnd = false;
1036	<	private K fromKey, toKey;
1231	>	final TreeMap<K,V> m;
1232
1233	<	SubMap(K fromKey, K toKey) {
1234	<	if (compare(fromKey, toKey) > 0)
1235	<	throw new IllegalArgumentException("fromKey > toKey");
1236	<	this.fromKey = fromKey;
1237	<	this.toKey = toKey;
1238	<	}
1233	>	/*
1234	>	* Endpoints are represented as triples (fromStart, lo,
1235	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1236	>	* true, then the low (absolute) bound is the start of the
1237	>	* backing map, and the other values are ignored. Otherwise,
1238	>	* if loInclusive is true, lo is the inclusive bound, else lo
1239	>	* is the exclusive bound. Similarly for the upper bound.
1240	>	*/
1241
1242	<	SubMap(K key, boolean headMap) {
1243	<	compare(key, key); // Type-check key
1244	<
1245	<	if (headMap) {
1246	<	fromStart = true;
1247	<	toKey = key;
1242	>	final K lo, hi;
1243	>	final boolean fromStart, toEnd;
1244	>	final boolean loInclusive, hiInclusive;
1245	>
1246	>	NavigableSubMap(TreeMap<K,V> m,
1247	>	boolean fromStart, K lo, boolean loInclusive,
1248	>	boolean toEnd,     K hi, boolean hiInclusive) {
1249	>	if (!fromStart && !toEnd) {
1250	>	if (m.compare(lo, hi) > 0)
1251	>	throw new IllegalArgumentException("fromKey > toKey");
1252		} else {
1253	<	toEnd = true;
1254	<	fromKey = key;
1253	>	if (!fromStart) // type check
1254	>	m.compare(lo, lo);
1255	>	if (!toEnd)
1256	>	m.compare(hi, hi);
1257		}
1055	–	}
1258
1259	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1259	>	this.m = m;
1260		this.fromStart = fromStart;
1261	<	this.fromKey= fromKey;
1261	>	this.lo = lo;
1262	>	this.loInclusive = loInclusive;
1263		this.toEnd = toEnd;
1264	<	this.toKey = toKey;
1264	>	this.hi = hi;
1265	>	this.hiInclusive = hiInclusive;
1266	>	}
1267	>
1268	>	// internal utilities
1269	>
1270	>	final boolean tooLow(Object key) {
1271	>	if (!fromStart) {
1272	>	int c = m.compare(key, lo);
1273	>	if (c < 0 || (c == 0 && !loInclusive))
1274	>	return true;
1275	>	}
1276	>	return false;
1277		}
1278
1279	+	final boolean tooHigh(Object key) {
1280	+	if (!toEnd) {
1281	+	int c = m.compare(key, hi);
1282	+	if (c > 0 || (c == 0 && !hiInclusive))
1283	+	return true;
1284	+	}
1285	+	return false;
1286	+	}
1287	+
1288	+	final boolean inRange(Object key) {
1289	+	return !tooLow(key) && !tooHigh(key);
1290	+	}
1291	+
1292	+	final boolean inClosedRange(Object key) {
1293	+	return (fromStart || m.compare(key, lo) >= 0)
1294	+	&& (toEnd || m.compare(hi, key) >= 0);
1295	+	}
1296	+
1297	+	final boolean inRange(Object key, boolean inclusive) {
1298	+	return inclusive ? inRange(key) : inClosedRange(key);
1299	+	}
1300	+
1301	+	/**
1302	+	* Return SimpleImmutableEntry for entry, or null if null
1303	+	*/
1304	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1305	+	return e == null? null :
1306	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1307	+	}
1308	+
1309	+	/**
1310	+	* Return key for entry, or null if null
1311	+	*/
1312	+	static <K,V> K exportKey(TreeMap.Entry<K,V> e) {
1313	+	return e == null? null : e.key;
1314	+	}
1315	+
1316	+	/*
1317	+	* Absolute versions of relation operations.
1318	+	* Subclasses map to these using like-named "sub"
1319	+	* versions that invert senses for descending maps
1320	+	*/
1321	+
1322	+	final TreeMap.Entry<K,V> absLowest() {
1323	+	TreeMap.Entry<K,V> e =
1324	+	(fromStart ?  m.getFirstEntry() :
1325	+	(loInclusive ? m.getCeilingEntry(lo) :
1326	+	m.getHigherEntry(lo)));
1327	+	return (e == null || tooHigh(e.key)) ? null : e;
1328	+	}
1329	+
1330	+	final TreeMap.Entry<K,V> absHighest() {
1331	+	TreeMap.Entry<K,V> e =
1332	+	(toEnd ?  m.getLastEntry() :
1333	+	(hiInclusive ?  m.getFloorEntry(hi) :
1334	+	m.getLowerEntry(hi)));
1335	+	return (e == null || tooLow(e.key)) ? null : e;
1336	+	}
1337	+
1338	+	final TreeMap.Entry<K,V> absCeiling(K key) {
1339	+	if (tooLow(key))
1340	+	return absLowest();
1341	+	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1342	+	return (e == null || tooHigh(e.key)) ? null : e;
1343	+	}
1344	+
1345	+	final TreeMap.Entry<K,V> absHigher(K key) {
1346	+	if (tooLow(key))
1347	+	return absLowest();
1348	+	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1349	+	return (e == null || tooHigh(e.key)) ? null : e;
1350	+	}
1351	+
1352	+	final TreeMap.Entry<K,V> absFloor(K key) {
1353	+	if (tooHigh(key))
1354	+	return absHighest();
1355	+	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1356	+	return (e == null || tooLow(e.key)) ? null : e;
1357	+	}
1358	+
1359	+	final TreeMap.Entry<K,V> absLower(K key) {
1360	+	if (tooHigh(key))
1361	+	return absHighest();
1362	+	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1363	+	return (e == null || tooLow(e.key)) ? null : e;
1364	+	}
1365	+
1366	+	/** Returns the absolute high fence for ascending traversal */
1367	+	final TreeMap.Entry<K,V> absHighFence() {
1368	+	return (toEnd ? null : (hiInclusive ?
1369	+	m.getHigherEntry(hi) :
1370	+	m.getCeilingEntry(hi)));
1371	+	}
1372	+
1373	+	/** Return the absolute low fence for descending traversal  */
1374	+	final TreeMap.Entry<K,V> absLowFence() {
1375	+	return (fromStart ? null : (loInclusive ?
1376	+	m.getLowerEntry(lo) :
1377	+	m.getFloorEntry(lo)));
1378	+	}
1379	+
1380	+	// Abstract methods defined in ascending vs descending classes
1381	+	// These relay to the appropriate  absolute versions
1382	+
1383	+	abstract TreeMap.Entry<K,V> subLowest();
1384	+	abstract TreeMap.Entry<K,V> subHighest();
1385	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1386	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1387	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1388	+	abstract TreeMap.Entry<K,V> subLower(K key);
1389	+
1390	+	/** Returns ascending iterator from the perspective of this submap */
1391	+	abstract Iterator<K> keyIterator();
1392	+
1393	+	/** Returns descending iterator from the perspective of this submap */
1394	+	abstract Iterator<K> descendingKeyIterator();
1395	+
1396	+	// public methods
1397	+
1398		public boolean isEmpty() {
1399	<	return entrySet().isEmpty();
1399	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1400		}
1401
1402	<	public boolean containsKey(Object key) {
1403	<	return inRange(key) && TreeMap.this.containsKey(key);
1402	>	public int size() {
1403	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1404		}
1405
1406	<	public V get(Object key) {
1407	<	if (!inRange(key))
1074	<	return null;
1075	<	return TreeMap.this.get(key);
1406	>	public final boolean containsKey(Object key) {
1407	>	return inRange(key) && m.containsKey(key);
1408		}
1409
1410	<	public V put(K key, V value) {
1410	>	public final V put(K key, V value) {
1411		if (!inRange(key))
1412		throw new IllegalArgumentException("key out of range");
1413	<	return TreeMap.this.put(key, value);
1413	>	return m.put(key, value);
1414		}
1415
1416	<	public V remove(Object key) {
1417	<	if (!inRange(key))
1086	<	return null;
1087	<	return TreeMap.this.remove(key);
1416	>	public final V get(Object key) {
1417	>	return !inRange(key)? null :  m.get(key);
1418		}
1419
1420	<	public Comparator<? super K> comparator() {
1421	<	return comparator;
1420	>	public final V remove(Object key) {
1421	>	return !inRange(key)? null  : m.remove(key);
1422		}
1423
1424	<	public K firstKey() {
1425	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1096	<	K first = key(e);
1097	<	if (!toEnd && compare(first, toKey) >= 0)
1098	<	throw new NoSuchElementException();
1099	<	return first;
1424	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1425	>	return exportEntry(subCeiling(key));
1426		}
1427
1428	<	public K lastKey() {
1429	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1104	<	K last = key(e);
1105	<	if (!fromStart && compare(last, fromKey) < 0)
1106	<	throw new NoSuchElementException();
1107	<	return last;
1428	>	public final K ceilingKey(K key) {
1429	>	return exportKey(subCeiling(key));
1430		}
1431
1432	<	public Map.Entry<K,V> firstEntry() {
1433	<	TreeMap.Entry<K,V> e = fromStart ?
1112	<	getFirstEntry() : getCeilingEntry(fromKey);
1113	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1114	<	return null;
1115	<	return e;
1432	>	public final Map.Entry<K,V> higherEntry(K key) {
1433	>	return exportEntry(subHigher(key));
1434		}
1435
1436	<	public Map.Entry<K,V> lastEntry() {
1437	<	TreeMap.Entry<K,V> e = toEnd ?
1120	<	getLastEntry() : getLowerEntry(toKey);
1121	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1122	<	return null;
1123	<	return e;
1436	>	public final K higherKey(K key) {
1437	>	return exportKey(subHigher(key));
1438		}
1439
1440	<	public Map.Entry<K,V> pollFirstEntry() {
1441	<	TreeMap.Entry<K,V> e = fromStart ?
1128	<	getFirstEntry() : getCeilingEntry(fromKey);
1129	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1130	<	return null;
1131	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1132	<	deleteEntry(e);
1133	<	return result;
1440	>	public final Map.Entry<K,V> floorEntry(K key) {
1441	>	return exportEntry(subFloor(key));
1442		}
1443
1444	<	public Map.Entry<K,V> pollLastEntry() {
1445	<	TreeMap.Entry<K,V> e = toEnd ?
1138	<	getLastEntry() : getLowerEntry(toKey);
1139	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1140	<	return null;
1141	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1142	<	deleteEntry(e);
1143	<	return result;
1444	>	public final K floorKey(K key) {
1445	>	return exportKey(subFloor(key));
1446		}
1447
1448	<	private TreeMap.Entry<K,V> subceiling(K key) {
1449	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1148	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1149	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1150	<	return null;
1151	<	return e;
1448	>	public final Map.Entry<K,V> lowerEntry(K key) {
1449	>	return exportEntry(subLower(key));
1450		}
1451
1452	<	public Map.Entry<K,V> ceilingEntry(K key) {
1453	<	TreeMap.Entry<K,V> e = subceiling(key);
1156	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1452	>	public final K lowerKey(K key) {
1453	>	return exportKey(subLower(key));
1454		}
1455
1456	<	public K ceilingKey(K key) {
1457	<	TreeMap.Entry<K,V> e = subceiling(key);
1161	<	return e == null? null : e.key;
1456	>	public final K firstKey() {
1457	>	return key(subLowest());
1458		}
1459
1460	<
1461	<	private TreeMap.Entry<K,V> subhigher(K key) {
1166	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1167	<	getCeilingEntry(fromKey) : getHigherEntry(key);
1168	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1169	<	return null;
1170	<	return e;
1460	>	public final K lastKey() {
1461	>	return key(subHighest());
1462		}
1463
1464	<	public Map.Entry<K,V> higherEntry(K key) {
1465	<	TreeMap.Entry<K,V> e = subhigher(key);
1175	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1464	>	public final Map.Entry<K,V> firstEntry() {
1465	>	return exportEntry(subLowest());
1466		}
1467
1468	<	public K higherKey(K key) {
1469	<	TreeMap.Entry<K,V> e = subhigher(key);
1180	<	return e == null? null : e.key;
1468	>	public final Map.Entry<K,V> lastEntry() {
1469	>	return exportEntry(subHighest());
1470		}
1471
1472	<	private TreeMap.Entry<K,V> subfloor(K key) {
1473	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1474	<	getLowerEntry(toKey) : getFloorEntry(key);
1475	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1476	<	return null;
1477	<	return e;
1472	>	public final Map.Entry<K,V> pollFirstEntry() {
1473	>	TreeMap.Entry<K,V> e = subLowest();
1474	>	Map.Entry<K,V> result = exportEntry(e);
1475	>	if (e != null)
1476	>	m.deleteEntry(e);
1477	>	return result;
1478		}
1479
1480	<	public Map.Entry<K,V> floorEntry(K key) {
1481	<	TreeMap.Entry<K,V> e = subfloor(key);
1482	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1480	>	public final Map.Entry<K,V> pollLastEntry() {
1481	>	TreeMap.Entry<K,V> e = subHighest();
1482	>	Map.Entry<K,V> result = exportEntry(e);
1483	>	if (e != null)
1484	>	m.deleteEntry(e);
1485	>	return result;
1486		}
1487
1488	<	public K floorKey(K key) {
1489	<	TreeMap.Entry<K,V> e = subfloor(key);
1490	<	return e == null? null : e.key;
1488	>	// Views
1489	>	transient NavigableMap<K,V> descendingMapView = null;
1490	>	transient EntrySetView entrySetView = null;
1491	>	transient KeySet<K> navigableKeySetView = null;
1492	>
1493	>	public final NavigableSet<K> navigableKeySet() {
1494	>	KeySet<K> nksv = navigableKeySetView;
1495	>	return (nksv != null) ? nksv :
1496	>	(navigableKeySetView = new TreeMap.KeySet(this));
1497		}
1498
1499	<	private TreeMap.Entry<K,V> sublower(K key) {
1500	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1203	<	getLowerEntry(toKey) :  getLowerEntry(key);
1204	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1205	<	return null;
1206	<	return e;
1499	>	public final Set<K> keySet() {
1500	>	return navigableKeySet();
1501		}
1502
1503	<	public Map.Entry<K,V> lowerEntry(K key) {
1504	<	TreeMap.Entry<K,V> e = sublower(key);
1211	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1503	>	public NavigableSet<K> descendingKeySet() {
1504	>	return descendingMap().navigableKeySet();
1505		}
1506
1507	<	public K lowerKey(K key) {
1508	<	TreeMap.Entry<K,V> e = sublower(key);
1216	<	return e == null? null : e.key;
1507	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1508	>	return subMap(fromKey, true, toKey, false);
1509		}
1510
1511	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1511	>	public final SortedMap<K,V> headMap(K toKey) {
1512	>	return headMap(toKey, false);
1513	>	}
1514
1515	<	public Set<Map.Entry<K,V>> entrySet() {
1516	<	Set<Map.Entry<K,V>> es = entrySet;
1223	<	return (es != null)? es : (entrySet = new EntrySetView());
1515	>	public final SortedMap<K,V> tailMap(K fromKey) {
1516	>	return tailMap(fromKey, true);
1517		}
1518
1519	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1519	>	// View classes
1520	>
1521	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1522		private transient int size = -1, sizeModCount;
1523
1524		public int size() {
1525	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1526	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1525	>	if (fromStart && toEnd)
1526	>	return m.size();
1527	>	if (size == -1 || sizeModCount != m.modCount) {
1528	>	sizeModCount = m.modCount;
1529	>	size = 0;
1530		Iterator i = iterator();
1531		while (i.hasNext()) {
1532		size++;
#	Line 1239 | Line 1537 | public class TreeMap<K,V>
1537		}
1538
1539		public boolean isEmpty() {
1540	<	return !iterator().hasNext();
1540	>	TreeMap.Entry<K,V> n = absLowest();
1541	>	return n == null || tooHigh(n.key);
1542		}
1543
1544		public boolean contains(Object o) {
#	Line 1249 | Line 1548 | public class TreeMap<K,V>
1548		K key = entry.getKey();
1549		if (!inRange(key))
1550		return false;
1551	<	TreeMap.Entry node = getEntry(key);
1551	>	TreeMap.Entry node = m.getEntry(key);
1552		return node != null &&
1553	<	valEquals(node.getValue(), entry.getValue());
1553	>	valEquals(node.getValue(), entry.getValue());
1554		}
1555
1556		public boolean remove(Object o) {
#	Line 1261 | Line 1560 | public class TreeMap<K,V>
1560		K key = entry.getKey();
1561		if (!inRange(key))
1562		return false;
1563	<	TreeMap.Entry<K,V> node = getEntry(key);
1563	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1564		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1565	<	deleteEntry(node);
1565	>	m.deleteEntry(node);
1566		return true;
1567		}
1568		return false;
1569		}
1271	–
1272	–	public Iterator<Map.Entry<K,V>> iterator() {
1273	–	return new SubMapEntryIterator(
1274	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1275	–	(toEnd     ? null            : getCeilingEntry(toKey)));
1276	–	}
1277	–	}
1278	–
1279	–	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1280	–	private transient Set<K> descendingKeySetView = null;
1281	–
1282	–	public Set<Map.Entry<K,V>> descendingEntrySet() {
1283	–	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1284	–	return (es != null) ? es :
1285	–	(descendingEntrySetView = new DescendingEntrySetView());
1570		}
1571
1572	<	public Set<K> descendingKeySet() {
1573	<	Set<K> ks = descendingKeySetView;
1574	<	return (ks != null) ? ks :
1575	<	(descendingKeySetView = new DescendingKeySetView());
1576	<	}
1572	>	/**
1573	>	* Iterators for SubMaps
1574	>	*/
1575	>	abstract class SubMapIterator<T> implements Iterator<T> {
1576	>	TreeMap.Entry<K,V> lastReturned;
1577	>	TreeMap.Entry<K,V> next;
1578	>	final K fenceKey;
1579	>	int expectedModCount;
1580
1581	<	private class DescendingEntrySetView extends EntrySetView {
1582	<	public Iterator<Map.Entry<K,V>> iterator() {
1583	<	return new DescendingSubMapEntryIterator
1584	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1585	<	(fromStart ? null            : getLowerEntry(fromKey)));
1581	>	SubMapIterator(TreeMap.Entry<K,V> first,
1582	>	TreeMap.Entry<K,V> fence) {
1583	>	expectedModCount = m.modCount;
1584	>	lastReturned = null;
1585	>	next = first;
1586	>	fenceKey = fence == null ? null : fence.key;
1587		}
1300	–	}
1588
1589	<	private class DescendingKeySetView extends AbstractSet<K> {
1590	<	public Iterator<K> iterator() {
1591	<	return new Iterator<K>() {
1305	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1589	>	public final boolean hasNext() {
1590	>	return next != null && next.key != fenceKey;
1591	>	}
1592
1593	<	public boolean hasNext() { return i.hasNext(); }
1594	<	public K next() { return i.next().getKey(); }
1595	<	public void remove() { i.remove(); }
1596	<	};
1593	>	final TreeMap.Entry<K,V> nextEntry() {
1594	>	TreeMap.Entry<K,V> e = lastReturned = next;
1595	>	if (e == null || e.key == fenceKey)
1596	>	throw new NoSuchElementException();
1597	>	if (m.modCount != expectedModCount)
1598	>	throw new ConcurrentModificationException();
1599	>	next = successor(e);
1600	>	return e;
1601		}
1602
1603	<	public int size() {
1604	<	return SubMap.this.size();
1603	>	final TreeMap.Entry<K,V> prevEntry() {
1604	>	TreeMap.Entry<K,V> e = lastReturned = next;
1605	>	if (e == null || e.key == fenceKey)
1606	>	throw new NoSuchElementException();
1607	>	if (m.modCount != expectedModCount)
1608	>	throw new ConcurrentModificationException();
1609	>	next = predecessor(e);
1610	>	return e;
1611		}
1612
1613	<	public boolean contains(Object k) {
1614	<	return SubMap.this.containsKey(k);
1613	>	public void remove() {
1614	>	if (lastReturned == null)
1615	>	throw new IllegalStateException();
1616	>	if (m.modCount != expectedModCount)
1617	>	throw new ConcurrentModificationException();
1618	>	if (lastReturned.left != null && lastReturned.right != null)
1619	>	next = lastReturned;
1620	>	m.deleteEntry(lastReturned);
1621	>	expectedModCount++;
1622	>	lastReturned = null;
1623		}
1624		}
1625
1626	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1627	<	if (!inRange2(fromKey))
1628	<	throw new IllegalArgumentException("fromKey out of range");
1629	<	if (!inRange2(toKey))
1630	<	throw new IllegalArgumentException("toKey out of range");
1631	<	return new SubMap(fromKey, toKey);
1626	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1627	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1628	>	TreeMap.Entry<K,V> fence) {
1629	>	super(first, fence);
1630	>	}
1631	>	public Map.Entry<K,V> next() {
1632	>	return nextEntry();
1633	>	}
1634		}
1635
1636	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1637	<	if (!inRange2(toKey))
1638	<	throw new IllegalArgumentException("toKey out of range");
1639	<	return new SubMap(fromStart, fromKey, false, toKey);
1636	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1637	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1638	>	TreeMap.Entry<K,V> fence) {
1639	>	super(first, fence);
1640	>	}
1641	>	public K next() {
1642	>	return nextEntry().key;
1643	>	}
1644		}
1645
1646	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1647	<	if (!inRange2(fromKey))
1648	<	throw new IllegalArgumentException("fromKey out of range");
1649	<	return new SubMap(false, fromKey, toEnd, toKey);
1650	<	}
1646	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1647	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1648	>	TreeMap.Entry<K,V> fence) {
1649	>	super(last, fence);
1650	>	}
1651
1652	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1653	<	return navigableSubMap(fromKey, toKey);
1652	>	public Map.Entry<K,V> next() {
1653	>	return prevEntry();
1654	>	}
1655		}
1656
1657	<	public SortedMap<K,V> headMap(K toKey) {
1658	<	return navigableHeadMap(toKey);
1657	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1658	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1659	>	TreeMap.Entry<K,V> fence) {
1660	>	super(last, fence);
1661	>	}
1662	>	public K next() {
1663	>	return prevEntry().key;
1664	>	}
1665		}
1666	+	}
1667
1668	<	public SortedMap<K,V> tailMap(K fromKey) {
1669	<	return navigableTailMap(fromKey);
1352	<	}
1668	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1669	>	private static final long serialVersionUID = 912986545866124060L;
1670
1671	<	private boolean inRange(Object key) {
1672	<	return (fromStart || compare(key, fromKey) >= 0) &&
1673	<	(toEnd     || compare(key, toKey)   <  0);
1671	>	AscendingSubMap(TreeMap<K,V> m,
1672	>	boolean fromStart, K lo, boolean loInclusive,
1673	>	boolean toEnd, K hi, boolean hiInclusive) {
1674	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1675		}
1676
1677	<	// This form allows the high endpoint (as well as all legit keys)
1678	<	private boolean inRange2(Object key) {
1361	<	return (fromStart || compare(key, fromKey) >= 0) &&
1362	<	(toEnd     || compare(key, toKey)   <= 0);
1677	>	public Comparator<? super K> comparator() {
1678	>	return m.comparator();
1679		}
1364	–	}
1680
1681	<	/**
1682	<	* TreeMap Iterator.
1683	<	*/
1684	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1685	<	int expectedModCount = TreeMap.this.modCount;
1686	<	Entry<K,V> lastReturned = null;
1687	<	Entry<K,V> next;
1688	<
1689	<	PrivateEntryIterator(Entry<K,V> first) {
1375	<	next = first;
1681	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1682	>	K toKey, boolean toInclusive) {
1683	>	if (!inRange(fromKey, fromInclusive))
1684	>	throw new IllegalArgumentException("fromKey out of range");
1685	>	if (!inRange(toKey, toInclusive))
1686	>	throw new IllegalArgumentException("toKey out of range");
1687	>	return new AscendingSubMap(m,
1688	>	false, fromKey, fromInclusive,
1689	>	false, toKey,   toInclusive);
1690		}
1691
1692	<	public boolean hasNext() {
1693	<	return next != null;
1692	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1693	>	if (!inClosedRange(toKey))
1694	>	throw new IllegalArgumentException("toKey out of range");
1695	>	return new AscendingSubMap(m,
1696	>	fromStart, lo,    loInclusive,
1697	>	false,     toKey, inclusive);
1698		}
1699
1700	<	Entry<K,V> nextEntry() {
1701	<	if (next == null)
1702	<	throw new NoSuchElementException();
1703	<	if (modCount != expectedModCount)
1704	<	throw new ConcurrentModificationException();
1705	<	lastReturned = next;
1388	<	next = successor(next);
1389	<	return lastReturned;
1700	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1701	>	if (!inRange(fromKey, inclusive))
1702	>	throw new IllegalArgumentException("fromKey out of range");
1703	>	return new AscendingSubMap(m,
1704	>	false, fromKey, inclusive,
1705	>	toEnd, hi,      hiInclusive);
1706		}
1707
1708	<	public void remove() {
1709	<	if (lastReturned == null)
1710	<	throw new IllegalStateException();
1711	<	if (modCount != expectedModCount)
1712	<	throw new ConcurrentModificationException();
1713	<	if (lastReturned.left != null && lastReturned.right != null)
1714	<	next = lastReturned;
1399	<	deleteEntry(lastReturned);
1400	<	expectedModCount++;
1401	<	lastReturned = null;
1708	>	public NavigableMap<K,V> descendingMap() {
1709	>	NavigableMap<K,V> mv = descendingMapView;
1710	>	return (mv != null) ? mv :
1711	>	(descendingMapView =
1712	>	new DescendingSubMap(m,
1713	>	fromStart, lo, loInclusive,
1714	>	toEnd,     hi, hiInclusive));
1715		}
1403	–	}
1716
1717	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1718	<	EntryIterator(Entry<K,V> first) {
1407	<	super(first);
1717	>	Iterator<K> keyIterator() {
1718	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1719		}
1409	–	public Map.Entry<K,V> next() {
1410	–	return nextEntry();
1411	–	}
1412	–	}
1720
1721	<	class KeyIterator extends PrivateEntryIterator<K> {
1722	<	KeyIterator(Entry<K,V> first) {
1416	<	super(first);
1417	<	}
1418	<	public K next() {
1419	<	return nextEntry().key;
1721	>	Iterator<K> descendingKeyIterator() {
1722	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1723		}
1421	–	}
1724
1725	<	class ValueIterator extends PrivateEntryIterator<V> {
1726	<	ValueIterator(Entry<K,V> first) {
1727	<	super(first);
1725	>	final class AscendingEntrySetView extends EntrySetView {
1726	>	public Iterator<Map.Entry<K,V>> iterator() {
1727	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1728	>	}
1729		}
1730	<	public V next() {
1731	<	return nextEntry().value;
1730	>
1731	>	public Set<Map.Entry<K,V>> entrySet() {
1732	>	EntrySetView es = entrySetView;
1733	>	return (es != null) ? es : new AscendingEntrySetView();
1734		}
1430	–	}
1735
1736	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1737	<	private final K firstExcludedKey;
1736	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1737	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1738	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1739	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1740	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1741	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1742	>	}
1743
1744	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1745	<	super(first);
1746	<	firstExcludedKey = (firstExcluded == null
1747	<	? null
1748	<	: firstExcluded.key);
1744	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1745	>	private static final long serialVersionUID = 912986545866120460L;
1746	>	DescendingSubMap(TreeMap<K,V> m,
1747	>	boolean fromStart, K lo, boolean loInclusive,
1748	>	boolean toEnd, K hi, boolean hiInclusive) {
1749	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1750		}
1751
1752	<	public boolean hasNext() {
1753	<	return next != null && next.key != firstExcludedKey;
1444	<	}
1752	>	private final Comparator<? super K> reverseComparator =
1753	>	Collections.reverseOrder(m.comparator);
1754
1755	<	public Map.Entry<K,V> next() {
1756	<	if (next == null || next.key == firstExcludedKey)
1448	<	throw new NoSuchElementException();
1449	<	return nextEntry();
1755	>	public Comparator<? super K> comparator() {
1756	>	return reverseComparator;
1757		}
1451	–	}
1758
1759	<	/**
1760	<	* Base for Descending Iterators.
1761	<	*/
1762	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1763	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1764	<	super(first);
1759	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1760	>	K toKey, boolean toInclusive) {
1761	>	if (!inRange(fromKey, fromInclusive))
1762	>	throw new IllegalArgumentException("fromKey out of range");
1763	>	if (!inRange(toKey, toInclusive))
1764	>	throw new IllegalArgumentException("toKey out of range");
1765	>	return new DescendingSubMap(m,
1766	>	false, toKey,   toInclusive,
1767	>	false, fromKey, fromInclusive);
1768		}
1769
1770	<	Entry<K,V> nextEntry() {
1771	<	if (next == null)
1772	<	throw new NoSuchElementException();
1773	<	if (modCount != expectedModCount)
1774	<	throw new ConcurrentModificationException();
1775	<	lastReturned = next;
1467	<	next = predecessor(next);
1468	<	return lastReturned;
1770	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1771	>	if (!inRange(toKey, inclusive))
1772	>	throw new IllegalArgumentException("toKey out of range");
1773	>	return new DescendingSubMap(m,
1774	>	false, toKey, inclusive,
1775	>	toEnd, hi,    hiInclusive);
1776		}
1470	–	}
1777
1778	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1779	<	DescendingEntryIterator(Entry<K,V> first) {
1780	<	super(first);
1781	<	}
1782	<	public Map.Entry<K,V> next() {
1783	<	return nextEntry();
1778	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1779	>	if (!inRange(fromKey, inclusive))
1780	>	throw new IllegalArgumentException("fromKey out of range");
1781	>	return new DescendingSubMap(m,
1782	>	fromStart, lo, loInclusive,
1783	>	false, fromKey, inclusive);
1784		}
1479	–	}
1785
1786	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1787	<	DescendingKeyIterator(Entry<K,V> first) {
1788	<	super(first);
1786	>	public NavigableMap<K,V> descendingMap() {
1787	>	NavigableMap<K,V> mv = descendingMapView;
1788	>	return (mv != null) ? mv :
1789	>	(descendingMapView =
1790	>	new AscendingSubMap(m,
1791	>	fromStart, lo, loInclusive,
1792	>	toEnd,     hi, hiInclusive));
1793		}
1485	–	public K next() {
1486	–	return nextEntry().key;
1487	–	}
1488	–	}
1794
1795	+	Iterator<K> keyIterator() {
1796	+	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1797	+	}
1798
1799	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1800	<	private final K lastExcludedKey;
1493	<
1494	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1495	<	super(last);
1496	<	lastExcludedKey = (lastExcluded == null
1497	<	? null
1498	<	: lastExcluded.key);
1799	>	Iterator<K> descendingKeyIterator() {
1800	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1801		}
1802
1803	<	public boolean hasNext() {
1804	<	return next != null && next.key != lastExcludedKey;
1803	>	final class DescendingEntrySetView extends EntrySetView {
1804	>	public Iterator<Map.Entry<K,V>> iterator() {
1805	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1806	>	}
1807		}
1808
1809	<	public Map.Entry<K,V> next() {
1810	<	if (next == null || next.key == lastExcludedKey)
1811	<	throw new NoSuchElementException();
1508	<	return nextEntry();
1809	>	public Set<Map.Entry<K,V>> entrySet() {
1810	>	EntrySetView es = entrySetView;
1811	>	return (es != null) ? es : new DescendingEntrySetView();
1812		}
1813
1814	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1815	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1816	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1817	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1818	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1819	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1820		}
1821
1822		/**
1823		* Compares two keys using the correct comparison method for this TreeMap.
1824		*/
1825	<	private int compare(Object k1, Object k2) {
1825	>	final int compare(Object k1, Object k2) {
1826		return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1827	<	: comparator.compare((K)k1, (K)k2);
1827	>	: comparator.compare((K)k1, (K)k2);
1828		}
1829
1830		/**
1831	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1831	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1832		* that it copes with <tt>null</tt> o1 properly.
1833		*/
1834	<	private static boolean valEquals(Object o1, Object o2) {
1834	>	final static boolean valEquals(Object o1, Object o2) {
1835		return (o1==null ? o2==null : o1.equals(o2));
1836		}
1837
1838	+	/**
1839	+	* This class exists solely for the sake of serialization
1840	+	* compatibility with previous releases of TreeMap that did not
1841	+	* support NavigableMap.  It translates an old-version SubMap into
1842	+	* a new-version AscendingSubMap. This class is never otherwise
1843	+	* used.
1844	+	*/
1845	+	private class SubMap extends AbstractMap<K,V>
1846	+	implements SortedMap<K,V>, java.io.Serializable {
1847	+	private static final long serialVersionUID = -6520786458950516097L;
1848	+	private boolean fromStart = false, toEnd = false;
1849	+	private K fromKey, toKey;
1850	+	private Object readResolve() {
1851	+	return new AscendingSubMap(TreeMap.this,
1852	+	fromStart, fromKey, true,
1853	+	toEnd, toKey, false);
1854	+	}
1855	+	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1856	+	public K lastKey() { throw new InternalError(); }
1857	+	public K firstKey() { throw new InternalError(); }
1858	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1859	+	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1860	+	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1861	+	public Comparator<? super K> comparator() { throw new InternalError(); }
1862	+	}
1863	+
1864	+
1865		private static final boolean RED   = false;
1866		private static final boolean BLACK = true;
1867
#	Line 1534 | Line 1870 | public class TreeMap<K,V>
1870		* user (see Map.Entry).
1871		*/
1872
1873	<	static class Entry<K,V> implements Map.Entry<K,V> {
1873	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1874		K key;
1875		V value;
1876		Entry<K,V> left = null;
#	Line 1606 | Line 1942 | public class TreeMap<K,V>
1942		* Returns the first Entry in the TreeMap (according to the TreeMap's
1943		* key-sort function).  Returns null if the TreeMap is empty.
1944		*/
1945	<	private Entry<K,V> getFirstEntry() {
1945	>	final Entry<K,V> getFirstEntry() {
1946		Entry<K,V> p = root;
1947		if (p != null)
1948		while (p.left != null)
#	Line 1618 | Line 1954 | public class TreeMap<K,V>
1954		* Returns the last Entry in the TreeMap (according to the TreeMap's
1955		* key-sort function).  Returns null if the TreeMap is empty.
1956		*/
1957	<	private Entry<K,V> getLastEntry() {
1957	>	final Entry<K,V> getLastEntry() {
1958		Entry<K,V> p = root;
1959		if (p != null)
1960		while (p.right != null)
#	Line 1629 | Line 1965 | public class TreeMap<K,V>
1965		/**
1966		* Returns the successor of the specified Entry, or null if no such.
1967		*/
1968	<	private Entry<K,V> successor(Entry<K,V> t) {
1968	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1969		if (t == null)
1970		return null;
1971		else if (t.right != null) {
#	Line 1651 | Line 1987 | public class TreeMap<K,V>
1987		/**
1988		* Returns the predecessor of the specified Entry, or null if no such.
1989		*/
1990	<	private Entry<K,V> predecessor(Entry<K,V> t) {
1990	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1991		if (t == null)
1992		return null;
1993		else if (t.left != null) {
#	Line 1768 | Line 2104 | public class TreeMap<K,V>
2104		x = parentOf(x);
2105		rotateRight(x);
2106		}
2107	<	setColor(parentOf(x),  BLACK);
2107	>	setColor(parentOf(x), BLACK);
2108		setColor(parentOf(parentOf(x)), RED);
2109		if (parentOf(parentOf(x)) != null)
2110		rotateLeft(parentOf(parentOf(x)));
#	Line 1844 | Line 2180 | public class TreeMap<K,V>
2180
2181		if (colorOf(leftOf(sib))  == BLACK &&
2182		colorOf(rightOf(sib)) == BLACK) {
2183	<	setColor(sib,  RED);
2183	>	setColor(sib, RED);
2184		x = parentOf(x);
2185		} else {
2186		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 1871 | Line 2207 | public class TreeMap<K,V>
2207
2208		if (colorOf(rightOf(sib)) == BLACK &&
2209		colorOf(leftOf(sib)) == BLACK) {
2210	<	setColor(sib,  RED);
2210	>	setColor(sib, RED);
2211		x = parentOf(x);
2212		} else {
2213		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 1922 | Line 2258 | public class TreeMap<K,V>
2258		}
2259		}
2260
1925	–
1926	–
2261		/**
2262		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2263		* deserialize it).
#	Line 1985 | Line 2319 | public class TreeMap<K,V>
2319		* @throws ClassNotFoundException propagated from readObject.
2320		*         This cannot occur if str is null.
2321		*/
2322	<	private
2323	<	void buildFromSorted(int size, Iterator it,
2324	<	java.io.ObjectInputStream str,
1991	<	V defaultVal)
2322	>	private void buildFromSorted(int size, Iterator it,
2323	>	java.io.ObjectInputStream str,
2324	>	V defaultVal)
2325		throws  java.io.IOException, ClassNotFoundException {
2326		this.size = size;
2327	<	root =
2328	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
1996	<	it, str, defaultVal);
2327	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2328	>	it, str, defaultVal);
2329		}
2330
2331		/**
2332		* Recursive "helper method" that does the real work of the
2333	<	* of the previous method.  Identically named parameters have
2333	>	* previous method.  Identically named parameters have
2334		* identical definitions.  Additional parameters are documented below.
2335		* It is assumed that the comparator and size fields of the TreeMap are
2336		* already set prior to calling this method.  (It ignores both fields.)

Diff Legend

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