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.15 by jsr166, Wed May 18 01:39:35 2005 UTC vs.
Revision 1.31 by dl, Fri Apr 21 13:42:57 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(e);
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(e);
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)
700		return null;
701	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
701	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
702		deleteEntry(p);
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)
712		return null;
713	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
713	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
714		deleteEntry(p);
715		return result;
716		}
#	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);
727	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
727	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
728		}
729
730		/**
#	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);
751	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
751	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
752		}
753
754		/**
#	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);
775	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
775	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
776		}
777
778		/**
#	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);
799	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
799	>	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
800		}
801
802		/**
#	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, 0,
906	+	true, null, 0));
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, excluded(fromInclusive),
921	+	false, toKey,   excluded(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,  0,
935	+	false, toKey, excluded(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, excluded(inclusive),
949	+	true,  null,    0);
950	+	}
951	+
952	+	/**
953	+	* Translates a boolean "inclusive" value to the correct int value
954	+	* for the loExcluded or hiExcluded field.
955	+	*/
956	+	static int excluded(boolean inclusive) {
957	+	return inclusive ? 0 : 1;
958	+	}
959	+
960	+	/**
961	+	* @throws ClassCastException       {@inheritDoc}
962	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
963	+	*         null and this map uses natural ordering, or its comparator
964	+	*         does not permit null keys
965	+	* @throws IllegalArgumentException {@inheritDoc}
966	+	*/
967	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
968	+	return subMap(fromKey, true, toKey, false);
969	+	}
970	+
971	+	/**
972	+	* @throws ClassCastException       {@inheritDoc}
973	+	* @throws NullPointerException if <tt>toKey</tt> is null
974	+	*         and this map uses natural ordering, or its comparator
975	+	*         does not permit null keys
976	+	* @throws IllegalArgumentException {@inheritDoc}
977	+	*/
978	+	public SortedMap<K,V> headMap(K toKey) {
979	+	return headMap(toKey, false);
980	+	}
981	+
982	+	/**
983	+	* @throws ClassCastException       {@inheritDoc}
984	+	* @throws NullPointerException if <tt>fromKey</tt> is null
985	+	*         and this map uses natural ordering, or its comparator
986	+	*         does not permit null keys
987	+	* @throws IllegalArgumentException {@inheritDoc}
988	+	*/
989	+	public SortedMap<K,V> tailMap(K fromKey) {
990	+	return tailMap(fromKey, true);
991	+	}
992	+
993	+	// View class support
994	+
995		class Values extends AbstractCollection<V> {
996		public Iterator<V> iterator() {
997		return new ValueIterator(getFirstEntry());
#	Line 864 | Line 1023 | public class TreeMap<K,V>
1023		}
1024		}
1025
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	–
1026		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1027		public Iterator<Map.Entry<K,V>> iterator() {
1028		return new EntryIterator(getFirstEntry());
#	Line 920 | Line 1059 | public class TreeMap<K,V>
1059		}
1060		}
1061
1062	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1063	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
1064	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1065	<	}
1062	>	/*
1063	>	* Unlike Values and EntrySet, the KeySet class is static,
1064	>	* delegating to a NavigableMap to allow use by SubMaps, which
1065	>	* outweighs the ugliness of needing type-tests for the following
1066	>	* Iterator methods that are defined appropriately in main versus
1067	>	* submap classes.
1068	>	*/
1069
1070	<	class DescendingEntrySet extends EntrySet {
1071	<	public Iterator<Map.Entry<K,V>> iterator() {
930	<	return new DescendingEntryIterator(getLastEntry());
931	<	}
1070	>	Iterator<K> keyIterator() {
1071	>	return new KeyIterator(getFirstEntry());
1072		}
1073
1074	<	public Set<K> descendingKeySet() {
1075	<	Set<K> ks = descendingKeySet;
936	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1074	>	Iterator<K> descendingKeyIterator() {
1075	>	return new DescendingKeyIterator(getFirstEntry());
1076		}
1077
1078	<	class DescendingKeySet extends KeySet {
1079	<	public Iterator<K> iterator() {
1080	<	return new DescendingKeyIterator(getLastEntry());
1078	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1079	>	private final NavigableMap<E, Object> m;
1080	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1081	>
1082	>	public Iterator<E> iterator() {
1083	>	if (m instanceof TreeMap)
1084	>	return ((TreeMap<E,Object>)m).keyIterator();
1085	>	else
1086	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1087		}
943	–	}
1088
1089	<	/**
1090	<	* @throws ClassCastException       {@inheritDoc}
1091	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1092	<	*         null and this map uses natural ordering, or its comparator
1093	<	*         does not permit null keys
1094	<	* @throws IllegalArgumentException {@inheritDoc}
1095	<	*/
1096	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1097	<	return new SubMap(fromKey, toKey);
1089	>	public Iterator<E> descendingIterator() {
1090	>	if (m instanceof TreeMap)
1091	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1092	>	else
1093	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1094	>	}
1095	>
1096	>	public int size() { return m.size(); }
1097	>	public boolean isEmpty() { return m.isEmpty(); }
1098	>	public boolean contains(Object o) { return m.containsKey(o); }
1099	>	public void clear() { m.clear(); }
1100	>	public E lower(E e) { return m.lowerKey(e); }
1101	>	public E floor(E e) { return m.floorKey(e); }
1102	>	public E ceiling(E e) { return m.ceilingKey(e); }
1103	>	public E higher(E e) { return m.higherKey(e); }
1104	>	public E first() { return m.firstKey(); }
1105	>	public E last() { return m.lastKey(); }
1106	>	public Comparator<? super E> comparator() { return m.comparator(); }
1107	>	public E pollFirst() {
1108	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1109	>	return e == null? null : e.getKey();
1110	>	}
1111	>	public E pollLast() {
1112	>	Map.Entry<E,Object> e = m.pollLastEntry();
1113	>	return e == null? null : e.getKey();
1114	>	}
1115	>	public boolean remove(Object o) {
1116	>	int oldSize = size();
1117	>	m.remove(o);
1118	>	return size() != oldSize;
1119	>	}
1120	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1121	>	E toElement, boolean toInclusive) {
1122	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1123	>	toElement,   toInclusive));
1124	>	}
1125	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1126	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1127	>	}
1128	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1129	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1130	>	}
1131	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1132	>	return subSet(fromElement, true, toElement, false);
1133	>	}
1134	>	public SortedSet<E> headSet(E toElement) {
1135	>	return headSet(toElement, false);
1136	>	}
1137	>	public SortedSet<E> tailSet(E fromElement) {
1138	>	return tailSet(fromElement, true);
1139	>	}
1140	>	public NavigableSet<E> descendingSet() {
1141	>	return new TreeSet(m.descendingMap());
1142	>	}
1143		}
1144
1145		/**
1146	<	* @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}
1146	>	* Base class for TreeMap Iterators
1147		*/
1148	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1149	<	return new SubMap(toKey, true);
1148	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1149	>	Entry<K,V> next;
1150	>	Entry<K,V> lastReturned;
1151	>	int expectedModCount;
1152	>
1153	>	PrivateEntryIterator(Entry<K,V> first) {
1154	>	expectedModCount = modCount;
1155	>	lastReturned = null;
1156	>	next = first;
1157	>	}
1158	>
1159	>	public final boolean hasNext() {
1160	>	return next != null;
1161	>	}
1162	>
1163	>	final Entry<K,V> nextEntry() {
1164	>	Entry<K,V> e = lastReturned = next;
1165	>	if (e == null)
1166	>	throw new NoSuchElementException();
1167	>	if (modCount != expectedModCount)
1168	>	throw new ConcurrentModificationException();
1169	>	next = successor(e);
1170	>	return e;
1171	>	}
1172	>
1173	>	final Entry<K,V> prevEntry() {
1174	>	Entry<K,V> e = lastReturned= next;
1175	>	if (e == null)
1176	>	throw new NoSuchElementException();
1177	>	if (modCount != expectedModCount)
1178	>	throw new ConcurrentModificationException();
1179	>	next = predecessor(e);
1180	>	return e;
1181	>	}
1182	>
1183	>	public void remove() {
1184	>	if (lastReturned == null)
1185	>	throw new IllegalStateException();
1186	>	if (modCount != expectedModCount)
1187	>	throw new ConcurrentModificationException();
1188	>	if (lastReturned.left != null && lastReturned.right != null)
1189	>	next = lastReturned;
1190	>	deleteEntry(lastReturned);
1191	>	expectedModCount++;
1192	>	lastReturned = null;
1193	>	}
1194		}
1195
1196	<	/**
1197	<	* @throws ClassCastException       {@inheritDoc}
1198	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1199	<	*         and this map uses natural ordering, or its comparator
1200	<	*         does not permit null keys
1201	<	* @throws IllegalArgumentException {@inheritDoc}
1202	<	*/
974	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
975	<	return new SubMap(fromKey, false);
1196	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1197	>	EntryIterator(Entry<K,V> first) {
1198	>	super(first);
1199	>	}
1200	>	public Map.Entry<K,V> next() {
1201	>	return nextEntry();
1202	>	}
1203		}
1204
1205	<	/**
1206	<	* Equivalent to {@link #navigableSubMap} but with a return type
1207	<	* conforming to the <tt>SortedMap</tt> interface.
1208	<	*
1209	<	* <p>{@inheritDoc}
1210	<	*
1211	<	* @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);
1205	>	final class ValueIterator extends PrivateEntryIterator<V> {
1206	>	ValueIterator(Entry<K,V> first) {
1207	>	super(first);
1208	>	}
1209	>	public V next() {
1210	>	return nextEntry().value;
1211	>	}
1212		}
1213
1214	<	/**
1215	<	* Equivalent to {@link #navigableHeadMap} but with a return type
1216	<	* conforming to the <tt>SortedMap</tt> interface.
1217	<	*
1218	<	* <p>{@inheritDoc}
1219	<	*
1220	<	* @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);
1214	>	final class KeyIterator extends PrivateEntryIterator<K> {
1215	>	KeyIterator(Entry<K,V> first) {
1216	>	super(first);
1217	>	}
1218	>	public K next() {
1219	>	return nextEntry().key;
1220	>	}
1221		}
1222
1223	<	/**
1224	<	* Equivalent to {@link #navigableTailMap} but with a return type
1225	<	* conforming to the <tt>SortedMap</tt> interface.
1226	<	*
1227	<	* <p>{@inheritDoc}
1228	<	*
1229	<	* @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);
1223	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1224	>	DescendingKeyIterator(Entry<K,V> first) {
1225	>	super(first);
1226	>	}
1227	>	public K next() {
1228	>	return prevEntry().key;
1229	>	}
1230		}
1231
1232	<	private class SubMap
1027	<	extends AbstractMap<K,V>
1028	<	implements NavigableMap<K,V>, java.io.Serializable {
1029	<	private static final long serialVersionUID = -6520786458950516097L;
1232	>	// SubMaps
1233
1234	<	/**
1235	<	* fromKey is significant only if fromStart is false.  Similarly,
1236	<	* toKey is significant only if toStart is false.
1234	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1235	>	implements NavigableMap<K,V>, java.io.Serializable {
1236	>
1237	>	/*
1238	>	* The backing map.
1239		*/
1240	<	private boolean fromStart = false, toEnd = false;
1036	<	private K fromKey, toKey;
1240	>	final TreeMap<K,V> m;
1241
1242	<	SubMap(K fromKey, K toKey) {
1243	<	if (compare(fromKey, toKey) > 0)
1244	<	throw new IllegalArgumentException("fromKey > toKey");
1245	<	this.fromKey = fromKey;
1246	<	this.toKey = toKey;
1247	<	}
1242	>	/*
1243	>	* Endpoints are represented as triples (fromStart, lo, loExcluded)
1244	>	* and (toEnd, hi, hiExcluded). If fromStart is true, then
1245	>	* the low (absolute) bound is the start of the backing map, and the
1246	>	* other values are ignored. Otherwise, if loExcluded is
1247	>	* zero, lo is the inclusive bound, else loExcluded is one,
1248	>	* and lo is the exclusive bound. Similarly for the upper bound.
1249	>	*/
1250
1251	<	SubMap(K key, boolean headMap) {
1252	<	compare(key, key); // Type-check key
1253	<
1254	<	if (headMap) {
1255	<	fromStart = true;
1256	<	toKey = key;
1257	<	} else {
1258	<	toEnd = true;
1259	<	fromKey = key;
1260	<	}
1261	<	}
1251	>	final K lo, hi;
1252	>	final boolean fromStart, toEnd;
1253	>	final int loExcluded, hiExcluded;
1254	>
1255	>	NavigableSubMap(TreeMap<K,V> m,
1256	>	boolean fromStart, K lo, int loExcluded,
1257	>	boolean toEnd,     K hi, int hiExcluded) {
1258	>	if (!fromStart && !toEnd) {
1259	>	if (m.compare(lo, hi) > 0)
1260	>	throw new IllegalArgumentException("fromKey > toKey");
1261	>	}
1262	>	else if (!fromStart) // type check
1263	>	m.compare(lo, lo);
1264	>	else if (!toEnd)
1265	>	m.compare(hi, hi);
1266
1267	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1267	>	this.m = m;
1268		this.fromStart = fromStart;
1269	<	this.fromKey= fromKey;
1269	>	this.lo = lo;
1270	>	this.loExcluded = loExcluded;
1271		this.toEnd = toEnd;
1272	<	this.toKey = toKey;
1272	>	this.hi = hi;
1273	>	this.hiExcluded = hiExcluded;
1274		}
1275
1276	<	public boolean isEmpty() {
1277	<	return entrySet().isEmpty();
1276	>	// internal utilities
1277	>
1278	>	final boolean inRange(Object key) {
1279	>	return (fromStart || m.compare(key, lo) >= loExcluded)
1280	>	&& (toEnd || m.compare(hi, key) >= hiExcluded);
1281		}
1282
1283	<	public boolean containsKey(Object key) {
1284	<	return inRange((K) key) && TreeMap.this.containsKey(key);
1283	>	final boolean inClosedRange(Object key) {
1284	>	return (fromStart || m.compare(key, lo) >= 0)
1285	>	&& (toEnd || m.compare(hi, key) >= 0);
1286		}
1287
1288	<	public V get(Object key) {
1289	<	if (!inRange((K) key))
1074	<	return null;
1075	<	return TreeMap.this.get(key);
1288	>	final boolean inRange(Object key, boolean inclusive) {
1289	>	return inclusive ? inRange(key) : inClosedRange(key);
1290		}
1291
1292	<	public V put(K key, V value) {
1293	<	if (!inRange(key))
1080	<	throw new IllegalArgumentException("key out of range");
1081	<	return TreeMap.this.put(key, value);
1292	>	final boolean tooLow(K key) {
1293	>	return !fromStart && m.compare(key, lo) < loExcluded;
1294		}
1295
1296	<	public V remove(Object key) {
1297	<	if (!inRange((K) key))
1086	<	return null;
1087	<	return TreeMap.this.remove(key);
1296	>	final boolean tooHigh(K key) {
1297	>	return !toEnd && m.compare(hi, key) < hiExcluded;
1298		}
1299
1300	<	public Comparator<? super K> comparator() {
1301	<	return comparator;
1300	>	/** Returns the lowest entry in this submap (absolute ordering) */
1301	>	final TreeMap.Entry<K,V> loEntry() {
1302	>	TreeMap.Entry<K,V> result =
1303	>	(fromStart ?  m.getFirstEntry() :
1304	>	(loExcluded == 0 ? m.getCeilingEntry(lo) :
1305	>	m.getHigherEntry(lo)));
1306	>	return (result == null || tooHigh(result.key)) ? null : result;
1307		}
1308
1309	<	public K firstKey() {
1310	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1311	<	K first = key(e);
1312	<	if (!toEnd && compare(first, toKey) >= 0)
1313	<	throw new NoSuchElementException();
1314	<	return first;
1309	>	/** Returns the highest key in this submap (absolute ordering) */
1310	>	final TreeMap.Entry<K,V> hiEntry() {
1311	>	TreeMap.Entry<K,V> result =
1312	>	(toEnd ?  m.getLastEntry() :
1313	>	(hiExcluded == 0 ?  m.getFloorEntry(hi) :
1314	>	m.getLowerEntry(hi)));
1315	>	return (result == null || tooLow(result.key)) ? null : result;
1316		}
1317
1318	<	public K lastKey() {
1319	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1320	<	K last = key(e);
1321	<	if (!fromStart && compare(last, fromKey) < 0)
1322	<	throw new NoSuchElementException();
1323	<	return last;
1318	>	/** Polls the lowest entry in this submap (absolute ordering) */
1319	>	final Map.Entry<K,V> pollLoEntry() {
1320	>	TreeMap.Entry<K,V> e = loEntry();
1321	>	if (e == null)
1322	>	return null;
1323	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1324	>	m.deleteEntry(e);
1325	>	return result;
1326		}
1327
1328	<	public Map.Entry<K,V> firstEntry() {
1329	<	TreeMap.Entry<K,V> e = fromStart ?
1330	<	getFirstEntry() : getCeilingEntry(fromKey);
1331	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1328	>	/** Polls the highest key in this submap (absolute ordering) */
1329	>	final Map.Entry<K,V> pollHiEntry() {
1330	>	TreeMap.Entry<K,V> e = hiEntry();
1331	>	if (e == null)
1332		return null;
1333	<	return e;
1333	>	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1334	>	m.deleteEntry(e);
1335	>	return result;
1336		}
1337
1338	<	public Map.Entry<K,V> lastEntry() {
1339	<	TreeMap.Entry<K,V> e = toEnd ?
1340	<	getLastEntry() : getLowerEntry(toKey);
1341	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1338	>	/**
1339	>	* Return the absolute high fence for ascending traversal
1340	>	*/
1341	>	final TreeMap.Entry<K,V> hiFence() {
1342	>	if (toEnd)
1343		return null;
1344	<	return e;
1344	>	else if (hiExcluded == 0)
1345	>	return m.getHigherEntry(hi);
1346	>	else
1347	>	return m.getCeilingEntry(hi);
1348		}
1349
1350	<	public Map.Entry<K,V> pollFirstEntry() {
1351	<	TreeMap.Entry<K,V> e = fromStart ?
1352	<	getFirstEntry() : getCeilingEntry(fromKey);
1353	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1350	>	/**
1351	>	* Return the absolute low fence for descending traversal
1352	>	*/
1353	>	final TreeMap.Entry<K,V> loFence() {
1354	>	if (fromStart)
1355		return null;
1356	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1357	<	deleteEntry(e);
1358	<	return result;
1356	>	else if (loExcluded == 0)
1357	>	return m.getLowerEntry(lo);
1358	>	else
1359	>	return m.getFloorEntry(lo);
1360		}
1361
1362	<	public Map.Entry<K,V> pollLastEntry() {
1363	<	TreeMap.Entry<K,V> e = toEnd ?
1364	<	getLastEntry() : getLowerEntry(toKey);
1365	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1362	>
1363	>	public boolean isEmpty() {
1364	>	return entrySet().isEmpty();
1365	>	}
1366	>
1367	>	public boolean containsKey(Object key) {
1368	>	return inRange(key) && m.containsKey(key);
1369	>	}
1370	>
1371	>	public V get(Object key) {
1372	>	if (!inRange(key))
1373		return null;
1374	<	Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1142	<	deleteEntry(e);
1143	<	return result;
1374	>	return m.get(key);
1375		}
1376
1377	<	private TreeMap.Entry<K,V> subceiling(K key) {
1378	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1379	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1380	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1377	>	public V put(K key, V value) {
1378	>	if (!inRange(key))
1379	>	throw new IllegalArgumentException("key out of range");
1380	>	return m.put(key, value);
1381	>	}
1382	>
1383	>	public V remove(Object key) {
1384	>	if (!inRange(key))
1385		return null;
1386	<	return e;
1386	>	return m.remove(key);
1387		}
1388
1389		public Map.Entry<K,V> ceilingEntry(K key) {
1390	<	TreeMap.Entry<K,V> e = subceiling(key);
1391	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1390	>	TreeMap.Entry<K,V> e = subCeiling(key);
1391	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1392		}
1393
1394		public K ceilingKey(K key) {
1395	<	TreeMap.Entry<K,V> e = subceiling(key);
1395	>	TreeMap.Entry<K,V> e = subCeiling(key);
1396		return e == null? null : e.key;
1397		}
1398
1164	–
1165	–	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;
1171	–	}
1172	–
1399		public Map.Entry<K,V> higherEntry(K key) {
1400	<	TreeMap.Entry<K,V> e = subhigher(key);
1401	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1400	>	TreeMap.Entry<K,V> e = subHigher(key);
1401	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1402		}
1403
1404		public K higherKey(K key) {
1405	<	TreeMap.Entry<K,V> e = subhigher(key);
1405	>	TreeMap.Entry<K,V> e = subHigher(key);
1406		return e == null? null : e.key;
1407		}
1408
1183	–	private TreeMap.Entry<K,V> subfloor(K key) {
1184	–	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1185	–	getLowerEntry(toKey) : getFloorEntry(key);
1186	–	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1187	–	return null;
1188	–	return e;
1189	–	}
1190	–
1409		public Map.Entry<K,V> floorEntry(K key) {
1410	<	TreeMap.Entry<K,V> e = subfloor(key);
1411	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1410	>	TreeMap.Entry<K,V> e = subFloor(key);
1411	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1412		}
1413
1414		public K floorKey(K key) {
1415	<	TreeMap.Entry<K,V> e = subfloor(key);
1415	>	TreeMap.Entry<K,V> e = subFloor(key);
1416		return e == null? null : e.key;
1417		}
1418
1201	–	private TreeMap.Entry<K,V> sublower(K key) {
1202	–	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;
1207	–	}
1208	–
1419		public Map.Entry<K,V> lowerEntry(K key) {
1420	<	TreeMap.Entry<K,V> e = sublower(key);
1421	<	return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
1420	>	TreeMap.Entry<K,V> e = subLower(key);
1421	>	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1422		}
1423
1424		public K lowerKey(K key) {
1425	<	TreeMap.Entry<K,V> e = sublower(key);
1425	>	TreeMap.Entry<K,V> e = subLower(key);
1426		return e == null? null : e.key;
1427		}
1428
1429	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1429	>	abstract Iterator<K> keyIterator();
1430	>	abstract Iterator<K> descendingKeyIterator();
1431
1432	<	public Set<Map.Entry<K,V>> entrySet() {
1433	<	Set<Map.Entry<K,V>> es = entrySet;
1223	<	return (es != null)? es : (entrySet = new EntrySetView());
1432	>	public NavigableSet<K> descendingKeySet() {
1433	>	return descendingMap().navigableKeySet();
1434		}
1435
1436	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1436	>	// Views
1437	>	transient NavigableMap<K,V> descendingMapView = null;
1438	>	transient EntrySetView entrySetView = null;
1439	>	transient KeySet<K> navigableKeySetView = null;
1440	>
1441	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1442		private transient int size = -1, sizeModCount;
1443
1444		public int size() {
1445	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1446	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1445	>	if (fromStart && toEnd)
1446	>	return m.size();
1447	>	if (size == -1 || sizeModCount != m.modCount) {
1448	>	sizeModCount = m.modCount;
1449	>	size = 0;
1450		Iterator i = iterator();
1451		while (i.hasNext()) {
1452		size++;
#	Line 1239 | Line 1457 | public class TreeMap<K,V>
1457		}
1458
1459		public boolean isEmpty() {
1460	<	return !iterator().hasNext();
1460	>	TreeMap.Entry<K,V> n = loEntry();
1461	>	return n == null || tooHigh(n.key);
1462		}
1463
1464		public boolean contains(Object o) {
#	Line 1249 | Line 1468 | public class TreeMap<K,V>
1468		K key = entry.getKey();
1469		if (!inRange(key))
1470		return false;
1471	<	TreeMap.Entry node = getEntry(key);
1471	>	TreeMap.Entry node = m.getEntry(key);
1472		return node != null &&
1473	<	valEquals(node.getValue(), entry.getValue());
1473	>	valEquals(node.getValue(), entry.getValue());
1474		}
1475
1476		public boolean remove(Object o) {
#	Line 1261 | Line 1480 | public class TreeMap<K,V>
1480		K key = entry.getKey();
1481		if (!inRange(key))
1482		return false;
1483	<	TreeMap.Entry<K,V> node = getEntry(key);
1483	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1484		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1485	<	deleteEntry(node);
1485	>	m.deleteEntry(node);
1486		return true;
1487		}
1488		return false;
1489		}
1490	+	}
1491
1492	<	public Iterator<Map.Entry<K,V>> iterator() {
1493	<	return new SubMapEntryIterator(
1494	<	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1495	<	(toEnd     ? null            : getCeilingEntry(toKey)));
1276	<	}
1492	>	public NavigableSet<K> navigableKeySet() {
1493	>	KeySet<K> nksv = navigableKeySetView;
1494	>	return (nksv != null) ? nksv :
1495	>	(navigableKeySetView = new TreeMap.KeySet(this));
1496		}
1497
1498	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1499	<	private transient Set<K> descendingKeySetView = null;
1498	>	public Set<K> keySet() {
1499	>	return navigableKeySet();
1500	>	}
1501
1502	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1503	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1284	<	return (es != null) ? es :
1285	<	(descendingEntrySetView = new DescendingEntrySetView());
1502	>	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1503	>	return subMap(fromKey, true, toKey, false);
1504		}
1505
1506	<	public Set<K> descendingKeySet() {
1507	<	Set<K> ks = descendingKeySetView;
1290	<	return (ks != null) ? ks :
1291	<	(descendingKeySetView = new DescendingKeySetView());
1506	>	public SortedMap<K,V> headMap(K toKey) {
1507	>	return headMap(toKey, false);
1508		}
1509
1510	<	private class DescendingEntrySetView extends EntrySetView {
1511	<	public Iterator<Map.Entry<K,V>> iterator() {
1512	<	return new DescendingSubMapEntryIterator
1513	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1514	<	(fromStart ? null            : getLowerEntry(fromKey)));
1510	>	public SortedMap<K,V> tailMap(K fromKey) {
1511	>	return tailMap(fromKey, true);
1512	>	}
1513	>
1514	>	// The following four definitions are correct only for
1515	>	// ascending submaps. They are overridden in DescendingSubMap.
1516	>	// They are defined in the base class because the definitions
1517	>	// in DescendingSubMap rely on those for AscendingSubMap.
1518	>
1519	>	/**
1520	>	* Returns the entry corresponding to the ceiling of the specified
1521	>	* key from the perspective of this submap, or null if the submap
1522	>	* contains no such entry.
1523	>	*/
1524	>	TreeMap.Entry<K,V> subCeiling(K key) {
1525	>	if (tooLow(key))
1526	>	return loEntry();
1527	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1528	>	return (e == null || tooHigh(e.key)) ? null : e;
1529	>	}
1530	>
1531	>	/**
1532	>	* Returns the entry corresponding to the higher of the specified
1533	>	* key from the perspective of this submap, or null if the submap
1534	>	* contains no such entry.
1535	>	*/
1536	>	TreeMap.Entry<K,V> subHigher(K key) {
1537	>	if (tooLow(key))
1538	>	return loEntry();
1539	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1540	>	return (e == null || tooHigh(e.key)) ? null : e;
1541	>	}
1542	>
1543	>	/**
1544	>	* Returns the entry corresponding to the floor of the specified
1545	>	* key from the perspective of this submap, or null if the submap
1546	>	* contains no such entry.
1547	>	*/
1548	>	TreeMap.Entry<K,V> subFloor(K key) {
1549	>	if (tooHigh(key))
1550	>	return hiEntry();
1551	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1552	>	return (e == null || tooLow(e.key)) ? null : e;
1553	>	}
1554	>
1555	>	/**
1556	>	* Returns the entry corresponding to the lower of the specified
1557	>	* key from the perspective of this submap, or null if the submap
1558	>	* contains no such entry.
1559	>	*/
1560	>	TreeMap.Entry<K,V> subLower(K key) {
1561	>	if (tooHigh(key))
1562	>	return hiEntry();
1563	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1564	>	return (e == null || tooLow(e.key)) ? null : e;
1565	>	}
1566	>
1567	>	/**
1568	>	* Iterators for SubMaps
1569	>	*/
1570	>	abstract class SubMapIterator<T> implements Iterator<T> {
1571	>	TreeMap.Entry<K,V> lastReturned;
1572	>	TreeMap.Entry<K,V> next;
1573	>	final K fenceKey;
1574	>	int expectedModCount;
1575	>
1576	>	SubMapIterator(TreeMap.Entry<K,V> first,
1577	>	TreeMap.Entry<K,V> fence) {
1578	>	expectedModCount = m.modCount;
1579	>	lastReturned = null;
1580	>	next = first;
1581	>	fenceKey = fence == null ? null : fence.key;
1582	>	}
1583	>
1584	>	public final boolean hasNext() {
1585	>	return next != null && next.key != fenceKey;
1586	>	}
1587	>
1588	>	final TreeMap.Entry<K,V> nextEntry() {
1589	>	TreeMap.Entry<K,V> e = lastReturned = next;
1590	>	if (e == null || e.key == fenceKey)
1591	>	throw new NoSuchElementException();
1592	>	if (m.modCount != expectedModCount)
1593	>	throw new ConcurrentModificationException();
1594	>	next = successor(e);
1595	>	return e;
1596	>	}
1597	>
1598	>	final TreeMap.Entry<K,V> prevEntry() {
1599	>	TreeMap.Entry<K,V> e = lastReturned = next;
1600	>	if (e == null || e.key == fenceKey)
1601	>	throw new NoSuchElementException();
1602	>	if (m.modCount != expectedModCount)
1603	>	throw new ConcurrentModificationException();
1604	>	next = predecessor(e);
1605	>	return e;
1606	>	}
1607	>
1608	>	public void remove() {
1609	>	if (lastReturned == null)
1610	>	throw new IllegalStateException();
1611	>	if (m.modCount != expectedModCount)
1612	>	throw new ConcurrentModificationException();
1613	>	if (lastReturned.left != null && lastReturned.right != null)
1614	>	next = lastReturned;
1615	>	m.deleteEntry(lastReturned);
1616	>	expectedModCount++;
1617	>	lastReturned = null;
1618		}
1619		}
1620
1621	<	private class DescendingKeySetView extends AbstractSet<K> {
1622	<	public Iterator<K> iterator() {
1623	<	return new Iterator<K>() {
1624	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1621	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1622	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1623	>	TreeMap.Entry<K,V> fence) {
1624	>	super(first, fence);
1625	>	}
1626	>	public Map.Entry<K,V> next() {
1627	>	return nextEntry();
1628	>	}
1629	>	}
1630
1631	<	public boolean hasNext() { return i.hasNext(); }
1632	<	public K next() { return i.next().getKey(); }
1633	<	public void remove() { i.remove(); }
1634	<	};
1631	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1632	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1633	>	TreeMap.Entry<K,V> fence) {
1634	>	super(first, fence);
1635		}
1636	+	public K next() {
1637	+	return nextEntry().key;
1638	+	}
1639	+	}
1640
1641	<	public int size() {
1642	<	return SubMap.this.size();
1641	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1642	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1643	>	TreeMap.Entry<K,V> lastExcluded) {
1644	>	super(last, lastExcluded);
1645	>	}
1646	>
1647	>	public Map.Entry<K,V> next() {
1648	>	return prevEntry();
1649		}
1650	+	}
1651
1652	<	public boolean contains(Object k) {
1653	<	return SubMap.this.containsKey(k);
1652	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1653	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1654	>	TreeMap.Entry<K,V> lastExcluded) {
1655	>	super(last, lastExcluded);
1656	>	}
1657	>	public K next() {
1658	>	return prevEntry().key;
1659		}
1660		}
1661	+	}
1662	+
1663	+	static class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1664	+	private static final long serialVersionUID = 912986545866124060L;
1665
1666	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1667	<	if (!inRange2(fromKey))
1666	>	AscendingSubMap(TreeMap<K,V> m,
1667	>	boolean fromStart, K lo, int loExcluded,
1668	>	boolean toEnd, K hi, int hiExcluded) {
1669	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1670	>	}
1671	>
1672	>	public Comparator<? super K> comparator() {
1673	>	return m.comparator();
1674	>	}
1675	>
1676	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1677	>	K toKey, boolean toInclusive) {
1678	>	if (!inRange(fromKey, fromInclusive))
1679		throw new IllegalArgumentException("fromKey out of range");
1680	<	if (!inRange2(toKey))
1680	>	if (!inRange(toKey, toInclusive))
1681		throw new IllegalArgumentException("toKey out of range");
1682	<	return new SubMap(fromKey, toKey);
1682	>	return new AscendingSubMap(m,
1683	>	false, fromKey, excluded(fromInclusive),
1684	>	false, toKey,   excluded(toInclusive));
1685		}
1686
1687	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1688	<	if (!inRange2(toKey))
1687	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1688	>	if (!inClosedRange(toKey))
1689		throw new IllegalArgumentException("toKey out of range");
1690	<	return new SubMap(fromStart, fromKey, false, toKey);
1690	>	return new AscendingSubMap(m,
1691	>	fromStart, lo,    loExcluded,
1692	>	false,     toKey, excluded(inclusive));
1693		}
1694
1695	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1696	<	if (!inRange2(fromKey))
1695	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1696	>	if (!inRange(fromKey, inclusive))
1697		throw new IllegalArgumentException("fromKey out of range");
1698	<	return new SubMap(false, fromKey, toEnd, toKey);
1698	>	return new AscendingSubMap(m,
1699	>	false, fromKey, excluded(inclusive),
1700	>	toEnd, hi,      hiExcluded);
1701		}
1702
1703	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1704	<	return navigableSubMap(fromKey, toKey);
1703	>	Iterator<K> keyIterator() {
1704	>	return new SubMapKeyIterator(loEntry(), hiFence());
1705		}
1706
1707	<	public SortedMap<K,V> headMap(K toKey) {
1708	<	return navigableHeadMap(toKey);
1707	>	Iterator<K> descendingKeyIterator() {
1708	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1709		}
1710
1711	<	public SortedMap<K,V> tailMap(K fromKey) {
1712	<	return navigableTailMap(fromKey);
1711	>	class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
1712	>	public Iterator<Map.Entry<K,V>> iterator() {
1713	>	return new SubMapEntryIterator(loEntry(), hiFence());
1714	>	}
1715		}
1716
1717	<	private boolean inRange(K key) {
1718	<	return (fromStart || compare(key, fromKey) >= 0) &&
1719	<	(toEnd     || compare(key, toKey)   <  0);
1717	>	public Set<Map.Entry<K,V>> entrySet() {
1718	>	EntrySetView es = entrySetView;
1719	>	return (es != null) ? es : new AscendingEntrySetView();
1720		}
1721
1722	<	// This form allows the high endpoint (as well as all legit keys)
1723	<	private boolean inRange2(K key) {
1361	<	return (fromStart || compare(key, fromKey) >= 0) &&
1362	<	(toEnd     || compare(key, toKey)   <= 0);
1722	>	public K firstKey() {
1723	>	return key(loEntry());
1724		}
1364	–	}
1725
1726	<	/**
1727	<	* TreeMap Iterator.
1368	<	*/
1369	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1370	<	int expectedModCount = TreeMap.this.modCount;
1371	<	Entry<K,V> lastReturned = null;
1372	<	Entry<K,V> next;
1373	<
1374	<	PrivateEntryIterator(Entry<K,V> first) {
1375	<	next = first;
1726	>	public K lastKey() {
1727	>	return key(hiEntry());
1728		}
1729
1730	<	public boolean hasNext() {
1731	<	return next != null;
1730	>	public Map.Entry<K,V> firstEntry() {
1731	>	return loEntry();
1732		}
1733
1734	<	Entry<K,V> nextEntry() {
1735	<	if (next == null)
1384	<	throw new NoSuchElementException();
1385	<	if (modCount != expectedModCount)
1386	<	throw new ConcurrentModificationException();
1387	<	lastReturned = next;
1388	<	next = successor(next);
1389	<	return lastReturned;
1734	>	public Map.Entry<K,V> lastEntry() {
1735	>	return hiEntry();
1736		}
1737
1738	<	public void remove() {
1739	<	if (lastReturned == null)
1394	<	throw new IllegalStateException();
1395	<	if (modCount != expectedModCount)
1396	<	throw new ConcurrentModificationException();
1397	<	if (lastReturned.left != null && lastReturned.right != null)
1398	<	next = lastReturned;
1399	<	deleteEntry(lastReturned);
1400	<	expectedModCount++;
1401	<	lastReturned = null;
1738	>	public Map.Entry<K,V> pollFirstEntry() {
1739	>	return pollLoEntry();
1740		}
1403	–	}
1741
1742	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1743	<	EntryIterator(Entry<K,V> first) {
1407	<	super(first);
1742	>	public Map.Entry<K,V> pollLastEntry() {
1743	>	return pollHiEntry();
1744		}
1745	<	public Map.Entry<K,V> next() {
1746	<	return nextEntry();
1745	>
1746	>	public NavigableMap<K,V> descendingMap() {
1747	>	NavigableMap<K,V> mv = descendingMapView;
1748	>	return (mv != null) ? mv :
1749	>	(descendingMapView =
1750	>	new DescendingSubMap(m,
1751	>	fromStart, lo, loExcluded,
1752	>	toEnd,     hi, hiExcluded));
1753		}
1754		}
1755
1756	<	class KeyIterator extends PrivateEntryIterator<K> {
1757	<	KeyIterator(Entry<K,V> first) {
1758	<	super(first);
1756	>	static class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1757	>	private static final long serialVersionUID = 912986545866120460L;
1758	>	DescendingSubMap(TreeMap<K,V> m,
1759	>	boolean fromStart, K lo, int loExcluded,
1760	>	boolean toEnd, K hi, int hiExcluded) {
1761	>	super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
1762		}
1763	<	public K next() {
1764	<	return nextEntry().key;
1763	>
1764	>	private final Comparator<? super K> reverseComparator =
1765	>	Collections.reverseOrder(m.comparator);
1766	>
1767	>	public Comparator<? super K> comparator() {
1768	>	return reverseComparator;
1769		}
1421	–	}
1770
1771	<	class ValueIterator extends PrivateEntryIterator<V> {
1772	<	ValueIterator(Entry<K,V> first) {
1773	<	super(first);
1771	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1772	>	K toKey, boolean toInclusive) {
1773	>	if (!inRange(fromKey, fromInclusive))
1774	>	throw new IllegalArgumentException("fromKey out of range");
1775	>	if (!inRange(toKey, toInclusive))
1776	>	throw new IllegalArgumentException("toKey out of range");
1777	>	return new DescendingSubMap(m,
1778	>	false, toKey,   excluded(toInclusive),
1779	>	false, fromKey, excluded(fromInclusive));
1780		}
1781	<	public V next() {
1782	<	return nextEntry().value;
1781	>
1782	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1783	>	if (!inRange(toKey, inclusive))
1784	>	throw new IllegalArgumentException("toKey out of range");
1785	>	return new DescendingSubMap(m,
1786	>	false, toKey, excluded(inclusive),
1787	>	toEnd, hi,    hiExcluded);
1788		}
1430	–	}
1789
1790	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1791	<	private final K firstExcludedKey;
1790	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1791	>	if (!inRange(fromKey, inclusive))
1792	>	throw new IllegalArgumentException("fromKey out of range");
1793	>	return new DescendingSubMap(m,
1794	>	fromStart, lo, loExcluded,
1795	>	false, fromKey, excluded(inclusive));
1796	>	}
1797
1798	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1799	<	super(first);
1437	<	firstExcludedKey = (firstExcluded == null
1438	<	? null
1439	<	: firstExcluded.key);
1798	>	Iterator<K> keyIterator() {
1799	>	return new DescendingSubMapKeyIterator(hiEntry(), loFence());
1800		}
1801
1802	<	public boolean hasNext() {
1803	<	return next != null && next.key != firstExcludedKey;
1802	>	Iterator<K> descendingKeyIterator() {
1803	>	return new SubMapKeyIterator(loEntry(), hiFence());
1804		}
1805
1806	<	public Map.Entry<K,V> next() {
1807	<	if (next == null || next.key == firstExcludedKey)
1808	<	throw new NoSuchElementException();
1809	<	return nextEntry();
1806	>	class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
1807	>	public Iterator<Map.Entry<K,V>> iterator() {
1808	>	return new DescendingSubMapEntryIterator(hiEntry(), loFence());
1809	>	}
1810		}
1451	–	}
1811
1812	<	/**
1813	<	* Base for Descending Iterators.
1814	<	*/
1456	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1457	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1458	<	super(first);
1812	>	public Set<Map.Entry<K,V>> entrySet() {
1813	>	EntrySetView es = entrySetView;
1814	>	return (es != null) ? es : new DescendingEntrySetView();
1815		}
1816
1817	<	Entry<K,V> nextEntry() {
1818	<	if (next == null)
1463	<	throw new NoSuchElementException();
1464	<	if (modCount != expectedModCount)
1465	<	throw new ConcurrentModificationException();
1466	<	lastReturned = next;
1467	<	next = predecessor(next);
1468	<	return lastReturned;
1817	>	public K firstKey() {
1818	>	return key(hiEntry());
1819		}
1470	–	}
1820
1821	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1822	<	DescendingEntryIterator(Entry<K,V> first) {
1474	<	super(first);
1821	>	public K lastKey() {
1822	>	return key(loEntry());
1823		}
1824	<	public Map.Entry<K,V> next() {
1825	<	return nextEntry();
1824	>
1825	>	public Map.Entry<K,V> firstEntry() {
1826	>	return hiEntry();
1827		}
1479	–	}
1828
1829	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1830	<	DescendingKeyIterator(Entry<K,V> first) {
1483	<	super(first);
1829	>	public Map.Entry<K,V> lastEntry() {
1830	>	return loEntry();
1831		}
1832	<	public K next() {
1833	<	return nextEntry().key;
1832	>
1833	>	public Map.Entry<K,V> pollFirstEntry() {
1834	>	return pollHiEntry();
1835		}
1488	–	}
1836
1837	+	public Map.Entry<K,V> pollLastEntry() {
1838	+	return pollLoEntry();
1839	+	}
1840
1841	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1842	<	private final K lastExcludedKey;
1841	>	public NavigableMap<K,V> descendingMap() {
1842	>	NavigableMap<K,V> mv = descendingMapView;
1843	>	return (mv != null) ? mv :
1844	>	(descendingMapView =
1845	>	new AscendingSubMap(m,
1846	>	fromStart, lo, loExcluded,
1847	>	toEnd, hi, hiExcluded));
1848	>	}
1849
1850	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1851	<	super(last);
1496	<	lastExcludedKey = (lastExcluded == null
1497	<	? null
1498	<	: lastExcluded.key);
1850	>	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1851	>	return super.subFloor(key);
1852		}
1853
1854	<	public boolean hasNext() {
1855	<	return next != null && next.key != lastExcludedKey;
1854	>	@Override TreeMap.Entry<K,V> subHigher(K key) {
1855	>	return super.subLower(key);
1856		}
1857
1858	<	public Map.Entry<K,V> next() {
1859	<	if (next == null || next.key == lastExcludedKey)
1507	<	throw new NoSuchElementException();
1508	<	return nextEntry();
1858	>	@Override TreeMap.Entry<K,V> subFloor(K key) {
1859	>	return super.subCeiling(key);
1860		}
1861
1862	+	@Override TreeMap.Entry<K,V> subLower(K key) {
1863	+	return super.subHigher(key);
1864	+	}
1865		}
1866
1867		/**
1868		* Compares two keys using the correct comparison method for this TreeMap.
1869		*/
1870	<	private int compare(K k1, K k2) {
1871	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo(k2)
1872	<	: comparator.compare(k1, k2);
1870	>	final int compare(Object k1, Object k2) {
1871	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1872	>	: comparator.compare((K)k1, (K)k2);
1873		}
1874
1875		/**
1876	<	* Test two values  for equality.  Differs from o1.equals(o2) only in
1876	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1877		* that it copes with <tt>null</tt> o1 properly.
1878		*/
1879	<	private static boolean valEquals(Object o1, Object o2) {
1879	>	final static boolean valEquals(Object o1, Object o2) {
1880		return (o1==null ? o2==null : o1.equals(o2));
1881		}
1882
1883	+	/**
1884	+	* This class exists solely for the sake of serialization
1885	+	* compatibility with previous releases of TreeMap that did not
1886	+	* support NavigableMap.  It translates an old-version SubMap into
1887	+	* a new-version AscendingSubMap. This class is never otherwise
1888	+	* used.
1889	+	*/
1890	+	private class SubMap extends AbstractMap<K,V>
1891	+	implements SortedMap<K,V>, java.io.Serializable {
1892	+	private static final long serialVersionUID = -6520786458950516097L;
1893	+	private boolean fromStart = false, toEnd = false;
1894	+	private K fromKey, toKey;
1895	+	private Object readResolve() {
1896	+	return new AscendingSubMap(TreeMap.this,
1897	+	fromStart, fromKey, 0,
1898	+	toEnd, toKey, 1);
1899	+	}
1900	+	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1901	+	public K lastKey() { throw new InternalError(); }
1902	+	public K firstKey() { throw new InternalError(); }
1903	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1904	+	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1905	+	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1906	+	public Comparator<? super K> comparator() { throw new InternalError(); }
1907	+	}
1908	+
1909	+
1910		private static final boolean RED   = false;
1911		private static final boolean BLACK = true;
1912
#	Line 1534 | Line 1915 | public class TreeMap<K,V>
1915		* user (see Map.Entry).
1916		*/
1917
1918	<	static class Entry<K,V> implements Map.Entry<K,V> {
1918	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1919		K key;
1920		V value;
1921		Entry<K,V> left = null;
#	Line 1606 | Line 1987 | public class TreeMap<K,V>
1987		* Returns the first Entry in the TreeMap (according to the TreeMap's
1988		* key-sort function).  Returns null if the TreeMap is empty.
1989		*/
1990	<	private Entry<K,V> getFirstEntry() {
1990	>	final Entry<K,V> getFirstEntry() {
1991		Entry<K,V> p = root;
1992		if (p != null)
1993		while (p.left != null)
#	Line 1618 | Line 1999 | public class TreeMap<K,V>
1999		* Returns the last Entry in the TreeMap (according to the TreeMap's
2000		* key-sort function).  Returns null if the TreeMap is empty.
2001		*/
2002	<	private Entry<K,V> getLastEntry() {
2002	>	final Entry<K,V> getLastEntry() {
2003		Entry<K,V> p = root;
2004		if (p != null)
2005		while (p.right != null)
#	Line 1629 | Line 2010 | public class TreeMap<K,V>
2010		/**
2011		* Returns the successor of the specified Entry, or null if no such.
2012		*/
2013	<	private Entry<K,V> successor(Entry<K,V> t) {
2013	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2014		if (t == null)
2015		return null;
2016		else if (t.right != null) {
#	Line 1651 | Line 2032 | public class TreeMap<K,V>
2032		/**
2033		* Returns the predecessor of the specified Entry, or null if no such.
2034		*/
2035	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2035	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2036		if (t == null)
2037		return null;
2038		else if (t.left != null) {
#	Line 1768 | Line 2149 | public class TreeMap<K,V>
2149		x = parentOf(x);
2150		rotateRight(x);
2151		}
2152	<	setColor(parentOf(x),  BLACK);
2152	>	setColor(parentOf(x), BLACK);
2153		setColor(parentOf(parentOf(x)), RED);
2154		if (parentOf(parentOf(x)) != null)
2155		rotateLeft(parentOf(parentOf(x)));
#	Line 1844 | Line 2225 | public class TreeMap<K,V>
2225
2226		if (colorOf(leftOf(sib))  == BLACK &&
2227		colorOf(rightOf(sib)) == BLACK) {
2228	<	setColor(sib,  RED);
2228	>	setColor(sib, RED);
2229		x = parentOf(x);
2230		} else {
2231		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 1871 | Line 2252 | public class TreeMap<K,V>
2252
2253		if (colorOf(rightOf(sib)) == BLACK &&
2254		colorOf(leftOf(sib)) == BLACK) {
2255	<	setColor(sib,  RED);
2255	>	setColor(sib, RED);
2256		x = parentOf(x);
2257		} else {
2258		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 1922 | Line 2303 | public class TreeMap<K,V>
2303		}
2304		}
2305
1925	–
1926	–
2306		/**
2307		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2308		* deserialize it).
#	Line 1985 | Line 2364 | public class TreeMap<K,V>
2364		* @throws ClassNotFoundException propagated from readObject.
2365		*         This cannot occur if str is null.
2366		*/
2367	<	private
2368	<	void buildFromSorted(int size, Iterator it,
2369	<	java.io.ObjectInputStream str,
1991	<	V defaultVal)
2367	>	private void buildFromSorted(int size, Iterator it,
2368	>	java.io.ObjectInputStream str,
2369	>	V defaultVal)
2370		throws  java.io.IOException, ClassNotFoundException {
2371		this.size = size;
2372	<	root =
2373	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
1996	<	it, str, defaultVal);
2372	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2373	>	it, str, defaultVal);
2374		}
2375
2376		/**
2377		* Recursive "helper method" that does the real work of the
2378	<	* of the previous method.  Identically named parameters have
2378	>	* previous method.  Identically named parameters have
2379		* identical definitions.  Additional parameters are documented below.
2380		* It is assumed that the comparator and size fields of the TreeMap are
2381		* already set prior to calling this method.  (It ignores both fields.)

Diff Legend

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