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.22 by jsr166, Fri Jun 24 20:44:49 2005 UTC vs.
Revision 1.43 by jsr166, Sun May 20 07:54:01 2007 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
9	–	import java.util.*; // for javadoc (till 6280605 is fixed)
27
28		/**
29		* A Red-Black tree based {@link NavigableMap} implementation.
#	Line 31 | Line 48 | import java.util.*; // for javadoc (till
48		* <i>is</i> well-defined even if its ordering is inconsistent with equals; it
49		* just fails to obey the general contract of the <tt>Map</tt> interface.
50		*
51	<	* <p><b>Note that this implementation is not synchronized.</b> If multiple
52	<	* threads access a map concurrently, and at least one of the threads modifies
53	<	* the map structurally, it <i>must</i> be synchronized externally.  (A
54	<	* structural modification is any operation that adds or deletes one or more
55	<	* mappings; merely changing the value associated with an existing key is not
56	<	* a structural modification.)  This is typically accomplished by
57	<	* synchronizing on some object that naturally encapsulates the map.  If no
58	<	* such object exists, the map should be "wrapped" using the
59	<	* <tt>Collections.synchronizedMap</tt> method.  This is best done at creation
60	<	* time, to prevent accidental unsynchronized access to the map:
61	<	* <pre>
62	<	*     Map m = Collections.synchronizedMap(new TreeMap(...));
63	<	* </pre>
51	>	* <p><strong>Note that this implementation is not synchronized.</strong>
52	>	* If multiple threads access a map concurrently, and at least one of the
53	>	* threads modifies the map structurally, it <i>must</i> be synchronized
54	>	* externally.  (A structural modification is any operation that adds or
55	>	* deletes one or more mappings; merely changing the value associated
56	>	* with an existing key is not a structural modification.)  This is
57	>	* typically accomplished by synchronizing on some object that naturally
58	>	* encapsulates the map.
59	>	* If no such object exists, the map should be "wrapped" using the
60	>	* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
61	>	* method.  This is best done at creation time, to prevent accidental
62	>	* unsynchronized access to the map: <pre>
63	>	*   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
64		*
65		* <p>The iterators returned by the <tt>iterator</tt> method of the collections
66		* returned by all of this class's "collection view methods" are
#	Line 69 | Line 86 | import java.util.*; // for javadoc (till
86		* associated map using <tt>put</tt>.)
87		*
88		* <p>This class is a member of the
89	<	* <a href="{@docRoot}/../guide/collections/index.html">
89	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
90		* Java Collections Framework</a>.
91		*
92		* @param <K> the type of keys maintained by this map
#	Line 83 | Line 100 | import java.util.*; // for javadoc (till
100		* @see Comparable
101		* @see Comparator
102		* @see Collection
86	–	* @see Collections#synchronizedMap(Map)
103		* @since 1.2
104		*/
105
#	Line 97 | Line 113 | public class TreeMap<K,V>
113		*
114		* @serial
115		*/
116	<	private Comparator<? super K> comparator = null;
116	>	private final Comparator<? super K> comparator;
117
118		private transient Entry<K,V> root = null;
119
#	Line 111 | Line 127 | public class TreeMap<K,V>
127		*/
128		private transient int modCount = 0;
129
114	–	private void incrementSize()   { modCount++; size++; }
115	–	private void decrementSize()   { modCount++; size--; }
116	–
130		/**
131		* Constructs a new, empty tree map, using the natural ordering of its
132		* keys.  All keys inserted into the map must implement the {@link
#	Line 127 | Line 140 | public class TreeMap<K,V>
140		* <tt>ClassCastException</tt>.
141		*/
142		public TreeMap() {
143	+	comparator = null;
144		}
145
146		/**
#	Line 162 | Line 176 | public class TreeMap<K,V>
176		* @throws NullPointerException if the specified map is null
177		*/
178		public TreeMap(Map<? extends K, ? extends V> m) {
179	+	comparator = null;
180		putAll(m);
181		}
182
#	Line 226 | Line 241 | public class TreeMap<K,V>
241		* @since 1.2
242		*/
243		public boolean containsValue(Object value) {
244	<	return (root==null ? false :
245	<	(value==null ? valueSearchNull(root)
246	<	: valueSearchNonNull(root, value)));
247	<	}
233	<
234	<	private boolean valueSearchNull(Entry n) {
235	<	if (n.value == null)
236	<	return true;
237	<
238	<	// Check left and right subtrees for value
239	<	return (n.left  != null && valueSearchNull(n.left)) ||
240	<	(n.right != null && valueSearchNull(n.right));
241	<	}
242	<
243	<	private boolean valueSearchNonNull(Entry n, Object value) {
244	<	// Check this node for the value
245	<	if (value.equals(n.value))
246	<	return true;
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));
244	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
245	>	if (valEquals(value, e.value))
246	>	return true;
247	>	return false;
248		}
249
250		/**
251	<	* Returns the value to which this map maps the specified key, or
252	<	* <tt>null</tt> if the map contains no mapping for the key.  A return
253	<	* value of <tt>null</tt> does not <i>necessarily</i> indicate that the
254	<	* map contains no mapping for the key; it's also possible that the map
255	<	* explicitly maps the key to <tt>null</tt>.  The {@link #containsKey
256	<	* containsKey} operation may be used to distinguish these two cases.
251	>	* Returns the value to which the specified key is mapped,
252	>	* or {@code null} if this map contains no mapping for the key.
253	>	*
254	>	* <p>More formally, if this map contains a mapping from a key
255	>	* {@code k} to a value {@code v} such that {@code key} compares
256	>	* equal to {@code k} according to the map's ordering, then this
257	>	* method returns {@code v}; otherwise it returns {@code null}.
258	>	* (There can be at most one such mapping.)
259	>	*
260	>	* <p>A return value of {@code null} does not <i>necessarily</i>
261	>	* indicate that the map contains no mapping for the key; it's also
262	>	* possible that the map explicitly maps the key to {@code null}.
263	>	* The {@link #containsKey containsKey} operation may be used to
264	>	* distinguish these two cases.
265		*
261	–	* @param key key whose associated value is to be returned
262	–	* @return the value to which this map maps the specified key, or
263	–	*         <tt>null</tt> if the map contains no mapping for the key
266		* @throws ClassCastException if the specified key cannot be compared
267		*         with the keys currently in the map
268		* @throws NullPointerException if the specified key is null
#	Line 332 | Line 334 | public class TreeMap<K,V>
334		*         and this map uses natural ordering, or its comparator
335		*         does not permit null keys
336		*/
337	<	private Entry<K,V> getEntry(Object key) {
337	>	final Entry<K,V> getEntry(Object key) {
338		// Offload comparator-based version for sake of performance
339		if (comparator != null)
340		return getEntryUsingComparator(key);
341	+	if (key == null)
342	+	throw new NullPointerException();
343		Comparable<? super K> k = (Comparable<? super K>) key;
344		Entry<K,V> p = root;
345		while (p != null) {
#	Line 356 | Line 360 | public class TreeMap<K,V>
360		* that are less dependent on comparator performance, but is
361		* worthwhile here.)
362		*/
363	<	private Entry<K,V> getEntryUsingComparator(Object key) {
363	>	final Entry<K,V> getEntryUsingComparator(Object key) {
364		K k = (K) key;
365		Comparator<? super K> cpr = comparator;
366	<	Entry<K,V> p = root;
367	<	while (p != null) {
368	<	int cmp = cpr.compare(k, p.key);
369	<	if (cmp < 0)
370	<	p = p.left;
371	<	else if (cmp > 0)
372	<	p = p.right;
373	<	else
374	<	return p;
366	>	if (cpr != null) {
367	>	Entry<K,V> p = root;
368	>	while (p != null) {
369	>	int cmp = cpr.compare(k, p.key);
370	>	if (cmp < 0)
371	>	p = p.left;
372	>	else if (cmp > 0)
373	>	p = p.right;
374	>	else
375	>	return p;
376	>	}
377		}
378		return null;
379		}
#	Line 378 | Line 384 | public class TreeMap<K,V>
384		* key; if no such entry exists (i.e., the greatest key in the Tree is less
385		* than the specified key), returns <tt>null</tt>.
386		*/
387	<	private Entry<K,V> getCeilingEntry(K key) {
387	>	final Entry<K,V> getCeilingEntry(K key) {
388		Entry<K,V> p = root;
389	<	if (p==null)
384	<	return null;
385	<
386	<	while (true) {
389	>	while (p != null) {
390		int cmp = compare(key, p.key);
391		if (cmp < 0) {
392		if (p.left != null)
#	Line 405 | Line 408 | public class TreeMap<K,V>
408		} else
409		return p;
410		}
411	+	return null;
412		}
413
414		/**
#	Line 412 | Line 416 | public class TreeMap<K,V>
416		* exists, returns the entry for the greatest key less than the specified
417		* key; if no such entry exists, returns <tt>null</tt>.
418		*/
419	<	private Entry<K,V> getFloorEntry(K key) {
419	>	final Entry<K,V> getFloorEntry(K key) {
420		Entry<K,V> p = root;
421	<	if (p==null)
418	<	return null;
419	<
420	<	while (true) {
421	>	while (p != null) {
422		int cmp = compare(key, p.key);
423		if (cmp > 0) {
424		if (p.right != null)
#	Line 440 | Line 441 | public class TreeMap<K,V>
441		return p;
442
443		}
444	+	return null;
445		}
446
447		/**
#	Line 448 | Line 450 | public class TreeMap<K,V>
450		* key greater than the specified key; if no such entry exists
451		* returns <tt>null</tt>.
452		*/
453	<	private Entry<K,V> getHigherEntry(K key) {
453	>	final Entry<K,V> getHigherEntry(K key) {
454		Entry<K,V> p = root;
455	<	if (p==null)
454	<	return null;
455	<
456	<	while (true) {
455	>	while (p != null) {
456		int cmp = compare(key, p.key);
457		if (cmp < 0) {
458		if (p.left != null)
#	Line 474 | Line 473 | public class TreeMap<K,V>
473		}
474		}
475		}
476	+	return null;
477		}
478
479		/**
#	Line 481 | Line 481 | public class TreeMap<K,V>
481		* no such entry exists (i.e., the least key in the Tree is greater than
482		* the specified key), returns <tt>null</tt>.
483		*/
484	<	private Entry<K,V> getLowerEntry(K key) {
484	>	final Entry<K,V> getLowerEntry(K key) {
485		Entry<K,V> p = root;
486	<	if (p==null)
487	<	return null;
488	<
489	<	while (true) {
486	>	while (p != null) {
487		int cmp = compare(key, p.key);
488		if (cmp > 0) {
489		if (p.right != null)
#	Line 507 | Line 504 | public class TreeMap<K,V>
504		}
505		}
506		}
507	<	}
511	<
512	<	/**
513	<	* Returns the key corresponding to the specified Entry.
514	<	* @throws NoSuchElementException if the Entry is null
515	<	*/
516	<	private static <K> K key(Entry<K,?> e) {
517	<	if (e==null)
518	<	throw new NoSuchElementException();
519	<	return e.key;
507	>	return null;
508		}
509
510		/**
#	Line 539 | Line 527 | public class TreeMap<K,V>
527		*/
528		public V put(K key, V value) {
529		Entry<K,V> t = root;
542	–
530		if (t == null) {
531	<	if (key == null) {
532	<	if (comparator == null)
533	<	throw new NullPointerException();
534	<	comparator.compare(key, key);
535	<	}
549	<	incrementSize();
531	>	// TBD:
532	>	// 5045147: (coll) Adding null to an empty TreeSet should
533	>	// throw NullPointerException
534	>	//
535	>	// compare(key, key); // type check
536		root = new Entry<K,V>(key, value, null);
537	+	size = 1;
538	+	modCount++;
539		return null;
540		}
541	<
542	<	while (true) {
543	<	int cmp = compare(key, t.key);
544	<	if (cmp == 0) {
545	<	return t.setValue(value);
546	<	} else if (cmp < 0) {
547	<	if (t.left != null) {
541	>	int cmp;
542	>	Entry<K,V> parent;
543	>	// split comparator and comparable paths
544	>	Comparator<? super K> cpr = comparator;
545	>	if (cpr != null) {
546	>	do {
547	>	parent = t;
548	>	cmp = cpr.compare(key, t.key);
549	>	if (cmp < 0)
550		t = t.left;
551	<	} else {
562	<	incrementSize();
563	<	t.left = new Entry<K,V>(key, value, t);
564	<	fixAfterInsertion(t.left);
565	<	return null;
566	<	}
567	<	} else { // cmp > 0
568	<	if (t.right != null) {
551	>	else if (cmp > 0)
552		t = t.right;
553	<	} else {
554	<	incrementSize();
555	<	t.right = new Entry<K,V>(key, value, t);
556	<	fixAfterInsertion(t.right);
557	<	return null;
558	<	}
559	<	}
553	>	else
554	>	return t.setValue(value);
555	>	} while (t != null);
556	>	}
557	>	else {
558	>	if (key == null)
559	>	throw new NullPointerException();
560	>	Comparable<? super K> k = (Comparable<? super K>) key;
561	>	do {
562	>	parent = t;
563	>	cmp = k.compareTo(t.key);
564	>	if (cmp < 0)
565	>	t = t.left;
566	>	else if (cmp > 0)
567	>	t = t.right;
568	>	else
569	>	return t.setValue(value);
570	>	} while (t != null);
571		}
572	+	Entry<K,V> e = new Entry<K,V>(key, value, parent);
573	+	if (cmp < 0)
574	+	parent.left = e;
575	+	else
576	+	parent.right = e;
577	+	fixAfterInsertion(e);
578	+	size++;
579	+	modCount++;
580	+	return null;
581		}
582
583		/**
#	Line 630 | Line 633 | public class TreeMap<K,V>
633		clone.size = 0;
634		clone.modCount = 0;
635		clone.entrySet = null;
636	<	clone.descendingEntrySet = null;
637	<	clone.descendingKeySet = null;
636	>	clone.navigableKeySet = null;
637	>	clone.descendingMap = null;
638
639		// Initialize clone with our mappings
640		try {
#	Line 649 | Line 652 | public class TreeMap<K,V>
652		* @since 1.6
653		*/
654		public Map.Entry<K,V> firstEntry() {
655	<	Entry<K,V> e = getFirstEntry();
653	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
655	>	return exportEntry(getFirstEntry());
656		}
657
658		/**
659		* @since 1.6
660		*/
661		public Map.Entry<K,V> lastEntry() {
662	<	Entry<K,V> e = getLastEntry();
661	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
662	>	return exportEntry(getLastEntry());
663		}
664
665		/**
#	Line 666 | Line 667 | public class TreeMap<K,V>
667		*/
668		public Map.Entry<K,V> pollFirstEntry() {
669		Entry<K,V> p = getFirstEntry();
670	<	if (p == null)
671	<	return null;
672	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
672	<	deleteEntry(p);
670	>	Map.Entry<K,V> result = exportEntry(p);
671	>	if (p != null)
672	>	deleteEntry(p);
673		return result;
674		}
675
#	Line 678 | Line 678 | public class TreeMap<K,V>
678		*/
679		public Map.Entry<K,V> pollLastEntry() {
680		Entry<K,V> p = getLastEntry();
681	<	if (p == null)
682	<	return null;
683	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
684	<	deleteEntry(p);
681	>	Map.Entry<K,V> result = exportEntry(p);
682	>	if (p != null)
683	>	deleteEntry(p);
684		return result;
685		}
686
#	Line 693 | Line 692 | public class TreeMap<K,V>
692		* @since 1.6
693		*/
694		public Map.Entry<K,V> lowerEntry(K key) {
695	<	Entry<K,V> e =  getLowerEntry(key);
697	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
695	>	return exportEntry(getLowerEntry(key));
696		}
697
698		/**
#	Line 705 | Line 703 | public class TreeMap<K,V>
703		* @since 1.6
704		*/
705		public K lowerKey(K key) {
706	<	Entry<K,V> e =  getLowerEntry(key);
709	<	return (e == null)? null : e.key;
706	>	return keyOrNull(getLowerEntry(key));
707		}
708
709		/**
#	Line 717 | Line 714 | public class TreeMap<K,V>
714		* @since 1.6
715		*/
716		public Map.Entry<K,V> floorEntry(K key) {
717	<	Entry<K,V> e = getFloorEntry(key);
721	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
717	>	return exportEntry(getFloorEntry(key));
718		}
719
720		/**
#	Line 729 | Line 725 | public class TreeMap<K,V>
725		* @since 1.6
726		*/
727		public K floorKey(K key) {
728	<	Entry<K,V> e = getFloorEntry(key);
733	<	return (e == null)? null : e.key;
728	>	return keyOrNull(getFloorEntry(key));
729		}
730
731		/**
#	Line 741 | Line 736 | public class TreeMap<K,V>
736		* @since 1.6
737		*/
738		public Map.Entry<K,V> ceilingEntry(K key) {
739	<	Entry<K,V> e = getCeilingEntry(key);
745	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
739	>	return exportEntry(getCeilingEntry(key));
740		}
741
742		/**
#	Line 753 | Line 747 | public class TreeMap<K,V>
747		* @since 1.6
748		*/
749		public K ceilingKey(K key) {
750	<	Entry<K,V> e = getCeilingEntry(key);
757	<	return (e == null)? null : e.key;
750	>	return keyOrNull(getCeilingEntry(key));
751		}
752
753		/**
#	Line 765 | Line 758 | public class TreeMap<K,V>
758		* @since 1.6
759		*/
760		public Map.Entry<K,V> higherEntry(K key) {
761	<	Entry<K,V> e = getHigherEntry(key);
769	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
761	>	return exportEntry(getHigherEntry(key));
762		}
763
764		/**
#	Line 777 | Line 769 | public class TreeMap<K,V>
769		* @since 1.6
770		*/
771		public K higherKey(K key) {
772	<	Entry<K,V> e = getHigherEntry(key);
781	<	return (e == null)? null : e.key;
772	>	return keyOrNull(getHigherEntry(key));
773		}
774
775		// Views
#	Line 788 | Line 779 | public class TreeMap<K,V>
779		* the first time this view is requested.  Views are stateless, so
780		* there's no reason to create more than one.
781		*/
782	<	private transient Set<Map.Entry<K,V>> entrySet = null;
783	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
784	<	private transient Set<K> descendingKeySet = null;
782	>	private transient EntrySet entrySet = null;
783	>	private transient KeySet<K> navigableKeySet = null;
784	>	private transient NavigableMap<K,V> descendingMap = null;
785
786		/**
787		* Returns a {@link Set} view of the keys contained in this map.
#	Line 807 | Line 798 | public class TreeMap<K,V>
798		* operations.
799		*/
800		public Set<K> keySet() {
801	<	Set<K> ks = keySet;
811	<	return (ks != null) ? ks : (keySet = new KeySet());
801	>	return navigableKeySet();
802		}
803
804	<	class KeySet extends AbstractSet<K> {
805	<	public Iterator<K> iterator() {
806	<	return new KeyIterator(getFirstEntry());
807	<	}
808	<
809	<	public int size() {
810	<	return TreeMap.this.size();
821	<	}
822	<
823	<	public boolean contains(Object o) {
824	<	return containsKey(o);
825	<	}
826	<
827	<	public boolean remove(Object o) {
828	<	int oldSize = size;
829	<	TreeMap.this.remove(o);
830	<	return size != oldSize;
831	<	}
804	>	/**
805	>	* @since 1.6
806	>	*/
807	>	public NavigableSet<K> navigableKeySet() {
808	>	KeySet<K> nks = navigableKeySet;
809	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
810	>	}
811
812	<	public void clear() {
813	<	TreeMap.this.clear();
814	<	}
812	>	/**
813	>	* @since 1.6
814	>	*/
815	>	public NavigableSet<K> descendingKeySet() {
816	>	return descendingMap().navigableKeySet();
817		}
818
819		/**
#	Line 855 | Line 836 | public class TreeMap<K,V>
836		return (vs != null) ? vs : (values = new Values());
837		}
838
839	+	/**
840	+	* Returns a {@link Set} view of the mappings contained in this map.
841	+	* The set's iterator returns the entries in ascending key order.
842	+	* The set is backed by the map, so changes to the map are
843	+	* reflected in the set, and vice-versa.  If the map is modified
844	+	* while an iteration over the set is in progress (except through
845	+	* the iterator's own <tt>remove</tt> operation, or through the
846	+	* <tt>setValue</tt> operation on a map entry returned by the
847	+	* iterator) the results of the iteration are undefined.  The set
848	+	* supports element removal, which removes the corresponding
849	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
850	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
851	+	* <tt>clear</tt> operations.  It does not support the
852	+	* <tt>add</tt> or <tt>addAll</tt> operations.
853	+	*/
854	+	public Set<Map.Entry<K,V>> entrySet() {
855	+	EntrySet es = entrySet;
856	+	return (es != null) ? es : (entrySet = new EntrySet());
857	+	}
858	+
859	+	/**
860	+	* @since 1.6
861	+	*/
862	+	public NavigableMap<K, V> descendingMap() {
863	+	NavigableMap<K, V> km = descendingMap;
864	+	return (km != null) ? km :
865	+	(descendingMap = new DescendingSubMap(this,
866	+	true, null, true,
867	+	true, null, true));
868	+	}
869	+
870	+	/**
871	+	* @throws ClassCastException       {@inheritDoc}
872	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
873	+	*         null and this map uses natural ordering, or its comparator
874	+	*         does not permit null keys
875	+	* @throws IllegalArgumentException {@inheritDoc}
876	+	* @since 1.6
877	+	*/
878	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
879	+	K toKey,   boolean toInclusive) {
880	+	return new AscendingSubMap(this,
881	+	false, fromKey, fromInclusive,
882	+	false, toKey,   toInclusive);
883	+	}
884	+
885	+	/**
886	+	* @throws ClassCastException       {@inheritDoc}
887	+	* @throws NullPointerException if <tt>toKey</tt> is null
888	+	*         and this map uses natural ordering, or its comparator
889	+	*         does not permit null keys
890	+	* @throws IllegalArgumentException {@inheritDoc}
891	+	* @since 1.6
892	+	*/
893	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
894	+	return new AscendingSubMap(this,
895	+	true,  null,  true,
896	+	false, toKey, inclusive);
897	+	}
898	+
899	+	/**
900	+	* @throws ClassCastException       {@inheritDoc}
901	+	* @throws NullPointerException if <tt>fromKey</tt> is null
902	+	*         and this map uses natural ordering, or its comparator
903	+	*         does not permit null keys
904	+	* @throws IllegalArgumentException {@inheritDoc}
905	+	* @since 1.6
906	+	*/
907	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
908	+	return new AscendingSubMap(this,
909	+	false, fromKey, inclusive,
910	+	true,  null,    true);
911	+	}
912	+
913	+	/**
914	+	* @throws ClassCastException       {@inheritDoc}
915	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
916	+	*         null and this map uses natural ordering, or its comparator
917	+	*         does not permit null keys
918	+	* @throws IllegalArgumentException {@inheritDoc}
919	+	*/
920	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
921	+	return subMap(fromKey, true, toKey, false);
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	+	*/
931	+	public SortedMap<K,V> headMap(K toKey) {
932	+	return headMap(toKey, false);
933	+	}
934	+
935	+	/**
936	+	* @throws ClassCastException       {@inheritDoc}
937	+	* @throws NullPointerException if <tt>fromKey</tt> is null
938	+	*         and this map uses natural ordering, or its comparator
939	+	*         does not permit null keys
940	+	* @throws IllegalArgumentException {@inheritDoc}
941	+	*/
942	+	public SortedMap<K,V> tailMap(K fromKey) {
943	+	return tailMap(fromKey, true);
944	+	}
945	+
946	+	// View class support
947	+
948		class Values extends AbstractCollection<V> {
949		public Iterator<V> iterator() {
950		return new ValueIterator(getFirstEntry());
#	Line 865 | Line 955 | public class TreeMap<K,V>
955		}
956
957		public boolean contains(Object o) {
958	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
869	<	if (valEquals(e.getValue(), o))
870	<	return true;
871	<	return false;
958	>	return TreeMap.this.containsValue(o);
959		}
960
961		public boolean remove(Object o) {
#	Line 886 | Line 973 | public class TreeMap<K,V>
973		}
974		}
975
889	–	/**
890	–	* Returns a {@link Set} view of the mappings contained in this map.
891	–	* The set's iterator returns the entries in ascending key order.
892	–	* The set is backed by the map, so changes to the map are
893	–	* reflected in the set, and vice-versa.  If the map is modified
894	–	* while an iteration over the set is in progress (except through
895	–	* the iterator's own <tt>remove</tt> operation, or through the
896	–	* <tt>setValue</tt> operation on a map entry returned by the
897	–	* iterator) the results of the iteration are undefined.  The set
898	–	* supports element removal, which removes the corresponding
899	–	* mapping from the map, via the <tt>Iterator.remove</tt>,
900	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
901	–	* <tt>clear</tt> operations.  It does not support the
902	–	* <tt>add</tt> or <tt>addAll</tt> operations.
903	–	*/
904	–	public Set<Map.Entry<K,V>> entrySet() {
905	–	Set<Map.Entry<K,V>> es = entrySet;
906	–	return (es != null) ? es : (entrySet = new EntrySet());
907	–	}
908	–
976		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
977		public Iterator<Map.Entry<K,V>> iterator() {
978		return new EntryIterator(getFirstEntry());
#	Line 942 | Line 1009 | public class TreeMap<K,V>
1009		}
1010		}
1011
1012	<	/**
1013	<	* @since 1.6
1012	>	/*
1013	>	* Unlike Values and EntrySet, the KeySet class is static,
1014	>	* delegating to a NavigableMap to allow use by SubMaps, which
1015	>	* outweighs the ugliness of needing type-tests for the following
1016	>	* Iterator methods that are defined appropriately in main versus
1017	>	* submap classes.
1018		*/
1019	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1020	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
1021	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1019	>
1020	>	Iterator<K> keyIterator() {
1021	>	return new KeyIterator(getFirstEntry());
1022		}
1023
1024	<	class DescendingEntrySet extends EntrySet {
1025	<	public Iterator<Map.Entry<K,V>> iterator() {
1026	<	return new DescendingEntryIterator(getLastEntry());
1024	>	Iterator<K> descendingKeyIterator() {
1025	>	return new DescendingKeyIterator(getFirstEntry());
1026	>	}
1027	>
1028	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1029	>	private final NavigableMap<E, Object> m;
1030	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1031	>
1032	>	public Iterator<E> iterator() {
1033	>	if (m instanceof TreeMap)
1034	>	return ((TreeMap<E,Object>)m).keyIterator();
1035	>	else
1036	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1037	>	}
1038	>
1039	>	public Iterator<E> descendingIterator() {
1040	>	if (m instanceof TreeMap)
1041	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1042	>	else
1043	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1044	>	}
1045	>
1046	>	public int size() { return m.size(); }
1047	>	public boolean isEmpty() { return m.isEmpty(); }
1048	>	public boolean contains(Object o) { return m.containsKey(o); }
1049	>	public void clear() { m.clear(); }
1050	>	public E lower(E e) { return m.lowerKey(e); }
1051	>	public E floor(E e) { return m.floorKey(e); }
1052	>	public E ceiling(E e) { return m.ceilingKey(e); }
1053	>	public E higher(E e) { return m.higherKey(e); }
1054	>	public E first() { return m.firstKey(); }
1055	>	public E last() { return m.lastKey(); }
1056	>	public Comparator<? super E> comparator() { return m.comparator(); }
1057	>	public E pollFirst() {
1058	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1059	>	return e == null? null : e.getKey();
1060	>	}
1061	>	public E pollLast() {
1062	>	Map.Entry<E,Object> e = m.pollLastEntry();
1063	>	return e == null? null : e.getKey();
1064	>	}
1065	>	public boolean remove(Object o) {
1066	>	int oldSize = size();
1067	>	m.remove(o);
1068	>	return size() != oldSize;
1069	>	}
1070	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071	>	E toElement,   boolean toInclusive) {
1072	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1073	>	toElement,   toInclusive));
1074	>	}
1075	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1076	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1077	>	}
1078	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1079	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1080	>	}
1081	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1082	>	return subSet(fromElement, true, toElement, false);
1083	>	}
1084	>	public SortedSet<E> headSet(E toElement) {
1085	>	return headSet(toElement, false);
1086	>	}
1087	>	public SortedSet<E> tailSet(E fromElement) {
1088	>	return tailSet(fromElement, true);
1089	>	}
1090	>	public NavigableSet<E> descendingSet() {
1091	>	return new TreeSet(m.descendingMap());
1092		}
1093		}
1094
1095		/**
1096	<	* @since 1.6
1096	>	* Base class for TreeMap Iterators
1097		*/
1098	<	public Set<K> descendingKeySet() {
1099	<	Set<K> ks = descendingKeySet;
1100	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1098	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1099	>	Entry<K,V> next;
1100	>	Entry<K,V> lastReturned;
1101	>	int expectedModCount;
1102	>
1103	>	PrivateEntryIterator(Entry<K,V> first) {
1104	>	expectedModCount = modCount;
1105	>	lastReturned = null;
1106	>	next = first;
1107	>	}
1108	>
1109	>	public final boolean hasNext() {
1110	>	return next != null;
1111	>	}
1112	>
1113	>	final Entry<K,V> nextEntry() {
1114	>	Entry<K,V> e = lastReturned = next;
1115	>	if (e == null)
1116	>	throw new NoSuchElementException();
1117	>	if (modCount != expectedModCount)
1118	>	throw new ConcurrentModificationException();
1119	>	next = successor(e);
1120	>	return e;
1121	>	}
1122	>
1123	>	final Entry<K,V> prevEntry() {
1124	>	Entry<K,V> e = lastReturned= next;
1125	>	if (e == null)
1126	>	throw new NoSuchElementException();
1127	>	if (modCount != expectedModCount)
1128	>	throw new ConcurrentModificationException();
1129	>	next = predecessor(e);
1130	>	return e;
1131	>	}
1132	>
1133	>	public void remove() {
1134	>	if (lastReturned == null)
1135	>	throw new IllegalStateException();
1136	>	if (modCount != expectedModCount)
1137	>	throw new ConcurrentModificationException();
1138	>	// deleted entries are replaced by their successors
1139	>	if (lastReturned.left != null && lastReturned.right != null)
1140	>	next = lastReturned;
1141	>	deleteEntry(lastReturned);
1142	>	expectedModCount = modCount;
1143	>	lastReturned = null;
1144	>	}
1145	>	}
1146	>
1147	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1148	>	EntryIterator(Entry<K,V> first) {
1149	>	super(first);
1150	>	}
1151	>	public Map.Entry<K,V> next() {
1152	>	return nextEntry();
1153	>	}
1154	>	}
1155	>
1156	>	final class ValueIterator extends PrivateEntryIterator<V> {
1157	>	ValueIterator(Entry<K,V> first) {
1158	>	super(first);
1159	>	}
1160	>	public V next() {
1161	>	return nextEntry().value;
1162	>	}
1163	>	}
1164	>
1165	>	final class KeyIterator extends PrivateEntryIterator<K> {
1166	>	KeyIterator(Entry<K,V> first) {
1167	>	super(first);
1168	>	}
1169	>	public K next() {
1170	>	return nextEntry().key;
1171	>	}
1172		}
1173
1174	<	class DescendingKeySet extends KeySet {
1175	<	public Iterator<K> iterator() {
1176	<	return new DescendingKeyIterator(getLastEntry());
1174	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1175	>	DescendingKeyIterator(Entry<K,V> first) {
1176	>	super(first);
1177	>	}
1178	>	public K next() {
1179	>	return prevEntry().key;
1180		}
1181		}
1182
1183	+	// Little utilities
1184	+
1185		/**
1186	<	* @throws ClassCastException       {@inheritDoc}
975	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
976	<	*         null and this map uses natural ordering, or its comparator
977	<	*         does not permit null keys
978	<	* @throws IllegalArgumentException {@inheritDoc}
979	<	* @since 1.6
1186	>	* Compares two keys using the correct comparison method for this TreeMap.
1187		*/
1188	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1189	<	return new SubMap(fromKey, toKey);
1188	>	final int compare(Object k1, Object k2) {
1189	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1190	>	: comparator.compare((K)k1, (K)k2);
1191		}
1192
1193		/**
1194	<	* @throws ClassCastException       {@inheritDoc}
1195	<	* @throws NullPointerException if <tt>toKey</tt> is null
988	<	*         and this map uses natural ordering, or its comparator
989	<	*         does not permit null keys
990	<	* @throws IllegalArgumentException {@inheritDoc}
991	<	* @since 1.6
1194	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1195	>	* that it copes with <tt>null</tt> o1 properly.
1196		*/
1197	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1198	<	return new SubMap(toKey, true);
1197	>	final static boolean valEquals(Object o1, Object o2) {
1198	>	return (o1==null ? o2==null : o1.equals(o2));
1199		}
1200
1201		/**
1202	<	* @throws ClassCastException       {@inheritDoc}
999	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1000	<	*         and this map uses natural ordering, or its comparator
1001	<	*         does not permit null keys
1002	<	* @throws IllegalArgumentException {@inheritDoc}
1003	<	* @since 1.6
1202	>	* Return SimpleImmutableEntry for entry, or null if null
1203		*/
1204	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1205	<	return new SubMap(fromKey, false);
1204	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1205	>	return e == null? null :
1206	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1207		}
1208
1209		/**
1210	<	* Equivalent to {@link #navigableSubMap} but with a return type
1011	<	* conforming to the <tt>SortedMap</tt> interface.
1012	<	*
1013	<	* <p>{@inheritDoc}
1014	<	*
1015	<	* @throws ClassCastException       {@inheritDoc}
1016	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1017	<	*         null and this map uses natural ordering, or its comparator
1018	<	*         does not permit null keys
1019	<	* @throws IllegalArgumentException {@inheritDoc}
1210	>	* Return key for entry, or null if null
1211		*/
1212	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1213	<	return new SubMap(fromKey, toKey);
1212	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1213	>	return e == null? null : e.key;
1214		}
1215
1216		/**
1217	<	* Equivalent to {@link #navigableHeadMap} but with a return type
1218	<	* conforming to the <tt>SortedMap</tt> interface.
1028	<	*
1029	<	* <p>{@inheritDoc}
1030	<	*
1031	<	* @throws ClassCastException       {@inheritDoc}
1032	<	* @throws NullPointerException if <tt>toKey</tt> is null
1033	<	*         and this map uses natural ordering, or its comparator
1034	<	*         does not permit null keys
1035	<	* @throws IllegalArgumentException {@inheritDoc}
1217	>	* Returns the key corresponding to the specified Entry.
1218	>	* @throws NoSuchElementException if the Entry is null
1219		*/
1220	<	public SortedMap<K,V> headMap(K toKey) {
1221	<	return new SubMap(toKey, true);
1220	>	static <K> K key(Entry<K,?> e) {
1221	>	if (e==null)
1222	>	throw new NoSuchElementException();
1223	>	return e.key;
1224		}
1225
1226	+
1227	+	// SubMaps
1228	+
1229		/**
1230	<	* Equivalent to {@link #navigableTailMap} but with a return type
1231	<	* conforming to the <tt>SortedMap</tt> interface.
1044	<	*
1045	<	* <p>{@inheritDoc}
1046	<	*
1047	<	* @throws ClassCastException       {@inheritDoc}
1048	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1049	<	*         and this map uses natural ordering, or its comparator
1050	<	*         does not permit null keys
1051	<	* @throws IllegalArgumentException {@inheritDoc}
1230	>	* Dummy value serving as unmatchable fence key for unbounded
1231	>	* SubMapIterators
1232		*/
1233	<	public SortedMap<K,V> tailMap(K fromKey) {
1054	<	return new SubMap(fromKey, false);
1055	<	}
1233	>	private static final Object UNBOUNDED = new Object();
1234
1235	<	private class SubMap
1236	<	extends AbstractMap<K,V>
1237	<	implements NavigableMap<K,V>, java.io.Serializable {
1238	<	private static final long serialVersionUID = -6520786458950516097L;
1235	>	/**
1236	>	* @serial include
1237	>	*/
1238	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1239	>	implements NavigableMap<K,V>, java.io.Serializable {
1240	>	/**
1241	>	* The backing map.
1242	>	*/
1243	>	final TreeMap<K,V> m;
1244
1245		/**
1246	<	* fromKey is significant only if fromStart is false.  Similarly,
1247	<	* toKey is significant only if toStart is false.
1246	>	* Endpoints are represented as triples (fromStart, lo,
1247	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1248	>	* true, then the low (absolute) bound is the start of the
1249	>	* backing map, and the other values are ignored. Otherwise,
1250	>	* if loInclusive is true, lo is the inclusive bound, else lo
1251	>	* is the exclusive bound. Similarly for the upper bound.
1252		*/
1253	<	private boolean fromStart = false, toEnd = false;
1254	<	private K fromKey, toKey;
1253	>	final K lo, hi;
1254	>	final boolean fromStart, toEnd;
1255	>	final boolean loInclusive, hiInclusive;
1256	>
1257	>	NavigableSubMap(TreeMap<K,V> m,
1258	>	boolean fromStart, K lo, boolean loInclusive,
1259	>	boolean toEnd,     K hi, boolean hiInclusive) {
1260	>	if (!fromStart && !toEnd) {
1261	>	if (m.compare(lo, hi) > 0)
1262	>	throw new IllegalArgumentException("fromKey > toKey");
1263	>	} else {
1264	>	if (!fromStart) // type check
1265	>	m.compare(lo, lo);
1266	>	if (!toEnd)
1267	>	m.compare(hi, hi);
1268	>	}
1269
1270	<	SubMap(K fromKey, K toKey) {
1271	<	if (compare(fromKey, toKey) > 0)
1272	<	throw new IllegalArgumentException("fromKey > toKey");
1273	<	this.fromKey = fromKey;
1274	<	this.toKey = toKey;
1270	>	this.m = m;
1271	>	this.fromStart = fromStart;
1272	>	this.lo = lo;
1273	>	this.loInclusive = loInclusive;
1274	>	this.toEnd = toEnd;
1275	>	this.hi = hi;
1276	>	this.hiInclusive = hiInclusive;
1277		}
1278
1279	<	SubMap(K key, boolean headMap) {
1280	<	compare(key, key); // Type-check key
1281	<
1282	<	if (headMap) {
1283	<	fromStart = true;
1284	<	toKey = key;
1285	<	} else {
1083	<	toEnd = true;
1084	<	fromKey = key;
1279	>	// internal utilities
1280	>
1281	>	final boolean tooLow(Object key) {
1282	>	if (!fromStart) {
1283	>	int c = m.compare(key, lo);
1284	>	if (c < 0 || (c == 0 && !loInclusive))
1285	>	return true;
1286		}
1287	+	return false;
1288		}
1289
1290	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1291	<	this.fromStart = fromStart;
1292	<	this.fromKey= fromKey;
1293	<	this.toEnd = toEnd;
1294	<	this.toKey = toKey;
1290	>	final boolean tooHigh(Object key) {
1291	>	if (!toEnd) {
1292	>	int c = m.compare(key, hi);
1293	>	if (c > 0 || (c == 0 && !hiInclusive))
1294	>	return true;
1295	>	}
1296	>	return false;
1297		}
1298
1299	+	final boolean inRange(Object key) {
1300	+	return !tooLow(key) && !tooHigh(key);
1301	+	}
1302	+
1303	+	final boolean inClosedRange(Object key) {
1304	+	return (fromStart || m.compare(key, lo) >= 0)
1305	+	&& (toEnd || m.compare(hi, key) >= 0);
1306	+	}
1307	+
1308	+	final boolean inRange(Object key, boolean inclusive) {
1309	+	return inclusive ? inRange(key) : inClosedRange(key);
1310	+	}
1311	+
1312	+	/*
1313	+	* Absolute versions of relation operations.
1314	+	* Subclasses map to these using like-named "sub"
1315	+	* versions that invert senses for descending maps
1316	+	*/
1317	+
1318	+	final TreeMap.Entry<K,V> absLowest() {
1319	+	TreeMap.Entry<K,V> e =
1320	+	(fromStart ?  m.getFirstEntry() :
1321	+	(loInclusive ? m.getCeilingEntry(lo) :
1322	+	m.getHigherEntry(lo)));
1323	+	return (e == null || tooHigh(e.key)) ? null : e;
1324	+	}
1325	+
1326	+	final TreeMap.Entry<K,V> absHighest() {
1327	+	TreeMap.Entry<K,V> e =
1328	+	(toEnd ?  m.getLastEntry() :
1329	+	(hiInclusive ?  m.getFloorEntry(hi) :
1330	+	m.getLowerEntry(hi)));
1331	+	return (e == null || tooLow(e.key)) ? null : e;
1332	+	}
1333	+
1334	+	final TreeMap.Entry<K,V> absCeiling(K key) {
1335	+	if (tooLow(key))
1336	+	return absLowest();
1337	+	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1338	+	return (e == null || tooHigh(e.key)) ? null : e;
1339	+	}
1340	+
1341	+	final TreeMap.Entry<K,V> absHigher(K key) {
1342	+	if (tooLow(key))
1343	+	return absLowest();
1344	+	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1345	+	return (e == null || tooHigh(e.key)) ? null : e;
1346	+	}
1347	+
1348	+	final TreeMap.Entry<K,V> absFloor(K key) {
1349	+	if (tooHigh(key))
1350	+	return absHighest();
1351	+	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1352	+	return (e == null || tooLow(e.key)) ? null : e;
1353	+	}
1354	+
1355	+	final TreeMap.Entry<K,V> absLower(K key) {
1356	+	if (tooHigh(key))
1357	+	return absHighest();
1358	+	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1359	+	return (e == null || tooLow(e.key)) ? null : e;
1360	+	}
1361	+
1362	+	/** Returns the absolute high fence for ascending traversal */
1363	+	final TreeMap.Entry<K,V> absHighFence() {
1364	+	return (toEnd ? null : (hiInclusive ?
1365	+	m.getHigherEntry(hi) :
1366	+	m.getCeilingEntry(hi)));
1367	+	}
1368	+
1369	+	/** Return the absolute low fence for descending traversal  */
1370	+	final TreeMap.Entry<K,V> absLowFence() {
1371	+	return (fromStart ? null : (loInclusive ?
1372	+	m.getLowerEntry(lo) :
1373	+	m.getFloorEntry(lo)));
1374	+	}
1375	+
1376	+	// Abstract methods defined in ascending vs descending classes
1377	+	// These relay to the appropriate absolute versions
1378	+
1379	+	abstract TreeMap.Entry<K,V> subLowest();
1380	+	abstract TreeMap.Entry<K,V> subHighest();
1381	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1382	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1383	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1384	+	abstract TreeMap.Entry<K,V> subLower(K key);
1385	+
1386	+	/** Returns ascending iterator from the perspective of this submap */
1387	+	abstract Iterator<K> keyIterator();
1388	+
1389	+	/** Returns descending iterator from the perspective of this submap */
1390	+	abstract Iterator<K> descendingKeyIterator();
1391	+
1392	+	// public methods
1393	+
1394		public boolean isEmpty() {
1395	<	return entrySet().isEmpty();
1395	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1396		}
1397
1398	<	public boolean containsKey(Object key) {
1399	<	return inRange(key) && TreeMap.this.containsKey(key);
1398	>	public int size() {
1399	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1400		}
1401
1402	<	public V get(Object key) {
1403	<	if (!inRange(key))
1105	<	return null;
1106	<	return TreeMap.this.get(key);
1402	>	public final boolean containsKey(Object key) {
1403	>	return inRange(key) && m.containsKey(key);
1404		}
1405
1406	<	public V put(K key, V value) {
1406	>	public final V put(K key, V value) {
1407		if (!inRange(key))
1408		throw new IllegalArgumentException("key out of range");
1409	<	return TreeMap.this.put(key, value);
1409	>	return m.put(key, value);
1410		}
1411
1412	<	public V remove(Object key) {
1413	<	if (!inRange(key))
1117	<	return null;
1118	<	return TreeMap.this.remove(key);
1412	>	public final V get(Object key) {
1413	>	return !inRange(key)? null :  m.get(key);
1414		}
1415
1416	<	public Comparator<? super K> comparator() {
1417	<	return comparator;
1416	>	public final V remove(Object key) {
1417	>	return !inRange(key)? null  : m.remove(key);
1418		}
1419
1420	<	public K firstKey() {
1421	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1127	<	K first = key(e);
1128	<	if (!toEnd && compare(first, toKey) >= 0)
1129	<	throw new NoSuchElementException();
1130	<	return first;
1420	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1421	>	return exportEntry(subCeiling(key));
1422		}
1423
1424	<	public K lastKey() {
1425	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1135	<	K last = key(e);
1136	<	if (!fromStart && compare(last, fromKey) < 0)
1137	<	throw new NoSuchElementException();
1138	<	return last;
1424	>	public final K ceilingKey(K key) {
1425	>	return keyOrNull(subCeiling(key));
1426		}
1427
1428	<	public Map.Entry<K,V> firstEntry() {
1429	<	TreeMap.Entry<K,V> e = fromStart ?
1143	<	getFirstEntry() : getCeilingEntry(fromKey);
1144	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1145	<	return null;
1146	<	return e;
1428	>	public final Map.Entry<K,V> higherEntry(K key) {
1429	>	return exportEntry(subHigher(key));
1430		}
1431
1432	<	public Map.Entry<K,V> lastEntry() {
1433	<	TreeMap.Entry<K,V> e = toEnd ?
1151	<	getLastEntry() : getLowerEntry(toKey);
1152	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1153	<	return null;
1154	<	return e;
1432	>	public final K higherKey(K key) {
1433	>	return keyOrNull(subHigher(key));
1434		}
1435
1436	<	public Map.Entry<K,V> pollFirstEntry() {
1437	<	TreeMap.Entry<K,V> e = fromStart ?
1159	<	getFirstEntry() : getCeilingEntry(fromKey);
1160	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1161	<	return null;
1162	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1163	<	deleteEntry(e);
1164	<	return result;
1436	>	public final Map.Entry<K,V> floorEntry(K key) {
1437	>	return exportEntry(subFloor(key));
1438		}
1439
1440	<	public Map.Entry<K,V> pollLastEntry() {
1441	<	TreeMap.Entry<K,V> e = toEnd ?
1169	<	getLastEntry() : getLowerEntry(toKey);
1170	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1171	<	return null;
1172	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1173	<	deleteEntry(e);
1174	<	return result;
1440	>	public final K floorKey(K key) {
1441	>	return keyOrNull(subFloor(key));
1442		}
1443
1444	<	private TreeMap.Entry<K,V> subceiling(K key) {
1445	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1179	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1180	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1181	<	return null;
1182	<	return e;
1444	>	public final Map.Entry<K,V> lowerEntry(K key) {
1445	>	return exportEntry(subLower(key));
1446		}
1447
1448	<	public Map.Entry<K,V> ceilingEntry(K key) {
1449	<	TreeMap.Entry<K,V> e = subceiling(key);
1187	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1448	>	public final K lowerKey(K key) {
1449	>	return keyOrNull(subLower(key));
1450		}
1451
1452	<	public K ceilingKey(K key) {
1453	<	TreeMap.Entry<K,V> e = subceiling(key);
1192	<	return e == null? null : e.key;
1452	>	public final K firstKey() {
1453	>	return key(subLowest());
1454		}
1455
1456	<
1457	<	private TreeMap.Entry<K,V> subhigher(K key) {
1197	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1198	<	getCeilingEntry(fromKey) : getHigherEntry(key);
1199	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1200	<	return null;
1201	<	return e;
1456	>	public final K lastKey() {
1457	>	return key(subHighest());
1458		}
1459
1460	<	public Map.Entry<K,V> higherEntry(K key) {
1461	<	TreeMap.Entry<K,V> e = subhigher(key);
1206	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1460	>	public final Map.Entry<K,V> firstEntry() {
1461	>	return exportEntry(subLowest());
1462		}
1463
1464	<	public K higherKey(K key) {
1465	<	TreeMap.Entry<K,V> e = subhigher(key);
1211	<	return e == null? null : e.key;
1464	>	public final Map.Entry<K,V> lastEntry() {
1465	>	return exportEntry(subHighest());
1466		}
1467
1468	<	private TreeMap.Entry<K,V> subfloor(K key) {
1469	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1470	<	getLowerEntry(toKey) : getFloorEntry(key);
1471	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1472	<	return null;
1473	<	return e;
1468	>	public final Map.Entry<K,V> pollFirstEntry() {
1469	>	TreeMap.Entry<K,V> e = subLowest();
1470	>	Map.Entry<K,V> result = exportEntry(e);
1471	>	if (e != null)
1472	>	m.deleteEntry(e);
1473	>	return result;
1474		}
1475
1476	<	public Map.Entry<K,V> floorEntry(K key) {
1477	<	TreeMap.Entry<K,V> e = subfloor(key);
1478	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1476	>	public final Map.Entry<K,V> pollLastEntry() {
1477	>	TreeMap.Entry<K,V> e = subHighest();
1478	>	Map.Entry<K,V> result = exportEntry(e);
1479	>	if (e != null)
1480	>	m.deleteEntry(e);
1481	>	return result;
1482		}
1483
1484	<	public K floorKey(K key) {
1485	<	TreeMap.Entry<K,V> e = subfloor(key);
1486	<	return e == null? null : e.key;
1484	>	// Views
1485	>	transient NavigableMap<K,V> descendingMapView = null;
1486	>	transient EntrySetView entrySetView = null;
1487	>	transient KeySet<K> navigableKeySetView = null;
1488	>
1489	>	public final NavigableSet<K> navigableKeySet() {
1490	>	KeySet<K> nksv = navigableKeySetView;
1491	>	return (nksv != null) ? nksv :
1492	>	(navigableKeySetView = new TreeMap.KeySet(this));
1493		}
1494
1495	<	private TreeMap.Entry<K,V> sublower(K key) {
1496	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1234	<	getLowerEntry(toKey) :  getLowerEntry(key);
1235	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1236	<	return null;
1237	<	return e;
1495	>	public final Set<K> keySet() {
1496	>	return navigableKeySet();
1497		}
1498
1499	<	public Map.Entry<K,V> lowerEntry(K key) {
1500	<	TreeMap.Entry<K,V> e = sublower(key);
1242	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1499	>	public NavigableSet<K> descendingKeySet() {
1500	>	return descendingMap().navigableKeySet();
1501		}
1502
1503	<	public K lowerKey(K key) {
1504	<	TreeMap.Entry<K,V> e = sublower(key);
1247	<	return e == null? null : e.key;
1503	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1504	>	return subMap(fromKey, true, toKey, false);
1505		}
1506
1507	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1507	>	public final SortedMap<K,V> headMap(K toKey) {
1508	>	return headMap(toKey, false);
1509	>	}
1510
1511	<	public Set<Map.Entry<K,V>> entrySet() {
1512	<	Set<Map.Entry<K,V>> es = entrySet;
1254	<	return (es != null)? es : (entrySet = new EntrySetView());
1511	>	public final SortedMap<K,V> tailMap(K fromKey) {
1512	>	return tailMap(fromKey, true);
1513		}
1514
1515	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1515	>	// View classes
1516	>
1517	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1518		private transient int size = -1, sizeModCount;
1519
1520		public int size() {
1521	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1522	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1521	>	if (fromStart && toEnd)
1522	>	return m.size();
1523	>	if (size == -1 || sizeModCount != m.modCount) {
1524	>	sizeModCount = m.modCount;
1525	>	size = 0;
1526		Iterator i = iterator();
1527		while (i.hasNext()) {
1528		size++;
#	Line 1270 | Line 1533 | public class TreeMap<K,V>
1533		}
1534
1535		public boolean isEmpty() {
1536	<	return !iterator().hasNext();
1536	>	TreeMap.Entry<K,V> n = absLowest();
1537	>	return n == null || tooHigh(n.key);
1538		}
1539
1540		public boolean contains(Object o) {
#	Line 1280 | Line 1544 | public class TreeMap<K,V>
1544		K key = entry.getKey();
1545		if (!inRange(key))
1546		return false;
1547	<	TreeMap.Entry node = getEntry(key);
1547	>	TreeMap.Entry node = m.getEntry(key);
1548		return node != null &&
1549	<	valEquals(node.getValue(), entry.getValue());
1549	>	valEquals(node.getValue(), entry.getValue());
1550		}
1551
1552		public boolean remove(Object o) {
#	Line 1292 | Line 1556 | public class TreeMap<K,V>
1556		K key = entry.getKey();
1557		if (!inRange(key))
1558		return false;
1559	<	TreeMap.Entry<K,V> node = getEntry(key);
1559	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1560		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1561	<	deleteEntry(node);
1561	>	m.deleteEntry(node);
1562		return true;
1563		}
1564		return false;
1565		}
1302	–
1303	–	public Iterator<Map.Entry<K,V>> iterator() {
1304	–	return new SubMapEntryIterator(
1305	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1306	–	(toEnd     ? null            : getCeilingEntry(toKey)));
1307	–	}
1308	–	}
1309	–
1310	–	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1311	–	private transient Set<K> descendingKeySetView = null;
1312	–
1313	–	public Set<Map.Entry<K,V>> descendingEntrySet() {
1314	–	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1315	–	return (es != null) ? es :
1316	–	(descendingEntrySetView = new DescendingEntrySetView());
1566		}
1567
1568	<	public Set<K> descendingKeySet() {
1569	<	Set<K> ks = descendingKeySetView;
1570	<	return (ks != null) ? ks :
1571	<	(descendingKeySetView = new DescendingKeySetView());
1572	<	}
1568	>	/**
1569	>	* Iterators for SubMaps
1570	>	*/
1571	>	abstract class SubMapIterator<T> implements Iterator<T> {
1572	>	TreeMap.Entry<K,V> lastReturned;
1573	>	TreeMap.Entry<K,V> next;
1574	>	final Object fenceKey;
1575	>	int expectedModCount;
1576
1577	<	private class DescendingEntrySetView extends EntrySetView {
1578	<	public Iterator<Map.Entry<K,V>> iterator() {
1579	<	return new DescendingSubMapEntryIterator
1580	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1581	<	(fromStart ? null            : getLowerEntry(fromKey)));
1577	>	SubMapIterator(TreeMap.Entry<K,V> first,
1578	>	TreeMap.Entry<K,V> fence) {
1579	>	expectedModCount = m.modCount;
1580	>	lastReturned = null;
1581	>	next = first;
1582	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1583		}
1331	–	}
1332	–
1333	–	private class DescendingKeySetView extends AbstractSet<K> {
1334	–	public Iterator<K> iterator() {
1335	–	return new Iterator<K>() {
1336	–	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1584
1585	<	public boolean hasNext() { return i.hasNext(); }
1586	<	public K next() { return i.next().getKey(); }
1340	<	public void remove() { i.remove(); }
1341	<	};
1585	>	public final boolean hasNext() {
1586	>	return next != null && next.key != fenceKey;
1587		}
1588
1589	<	public int size() {
1590	<	return SubMap.this.size();
1589	>	final TreeMap.Entry<K,V> nextEntry() {
1590	>	TreeMap.Entry<K,V> e = lastReturned = next;
1591	>	if (e == null || e.key == fenceKey)
1592	>	throw new NoSuchElementException();
1593	>	if (m.modCount != expectedModCount)
1594	>	throw new ConcurrentModificationException();
1595	>	next = successor(e);
1596	>	return e;
1597		}
1598
1599	<	public boolean contains(Object k) {
1600	<	return SubMap.this.containsKey(k);
1599	>	final TreeMap.Entry<K,V> prevEntry() {
1600	>	TreeMap.Entry<K,V> e = lastReturned = next;
1601	>	if (e == null || e.key == fenceKey)
1602	>	throw new NoSuchElementException();
1603	>	if (m.modCount != expectedModCount)
1604	>	throw new ConcurrentModificationException();
1605	>	next = predecessor(e);
1606	>	return e;
1607		}
1351	–	}
1608
1609	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1610	<	if (!inRange2(fromKey))
1611	<	throw new IllegalArgumentException("fromKey out of range");
1612	<	if (!inRange2(toKey))
1613	<	throw new IllegalArgumentException("toKey out of range");
1614	<	return new SubMap(fromKey, toKey);
1615	<	}
1609	>	final void removeAscending() {
1610	>	if (lastReturned == null)
1611	>	throw new IllegalStateException();
1612	>	if (m.modCount != expectedModCount)
1613	>	throw new ConcurrentModificationException();
1614	>	// deleted entries are replaced by their successors
1615	>	if (lastReturned.left != null && lastReturned.right != null)
1616	>	next = lastReturned;
1617	>	m.deleteEntry(lastReturned);
1618	>	lastReturned = null;
1619	>	expectedModCount = m.modCount;
1620	>	}
1621
1622	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1623	<	if (!inRange2(toKey))
1624	<	throw new IllegalArgumentException("toKey out of range");
1625	<	return new SubMap(fromStart, fromKey, false, toKey);
1626	<	}
1622	>	final void removeDescending() {
1623	>	if (lastReturned == null)
1624	>	throw new IllegalStateException();
1625	>	if (m.modCount != expectedModCount)
1626	>	throw new ConcurrentModificationException();
1627	>	m.deleteEntry(lastReturned);
1628	>	lastReturned = null;
1629	>	expectedModCount = m.modCount;
1630	>	}
1631
1367	–	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1368	–	if (!inRange2(fromKey))
1369	–	throw new IllegalArgumentException("fromKey out of range");
1370	–	return new SubMap(false, fromKey, toEnd, toKey);
1632		}
1633
1634	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1635	<	return navigableSubMap(fromKey, toKey);
1634	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1635	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1636	>	TreeMap.Entry<K,V> fence) {
1637	>	super(first, fence);
1638	>	}
1639	>	public Map.Entry<K,V> next() {
1640	>	return nextEntry();
1641	>	}
1642	>	public void remove() {
1643	>	removeAscending();
1644	>	}
1645		}
1646
1647	<	public SortedMap<K,V> headMap(K toKey) {
1648	<	return navigableHeadMap(toKey);
1647	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1648	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1649	>	TreeMap.Entry<K,V> fence) {
1650	>	super(first, fence);
1651	>	}
1652	>	public K next() {
1653	>	return nextEntry().key;
1654	>	}
1655	>	public void remove() {
1656	>	removeAscending();
1657	>	}
1658		}
1659
1660	<	public SortedMap<K,V> tailMap(K fromKey) {
1661	<	return navigableTailMap(fromKey);
1662	<	}
1660	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1661	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1662	>	TreeMap.Entry<K,V> fence) {
1663	>	super(last, fence);
1664	>	}
1665
1666	<	private boolean inRange(Object key) {
1667	<	return (fromStart || compare(key, fromKey) >= 0) &&
1668	<	(toEnd     || compare(key, toKey)   <  0);
1666	>	public Map.Entry<K,V> next() {
1667	>	return prevEntry();
1668	>	}
1669	>	public void remove() {
1670	>	removeDescending();
1671	>	}
1672		}
1673
1674	<	// This form allows the high endpoint (as well as all legit keys)
1675	<	private boolean inRange2(Object key) {
1676	<	return (fromStart || compare(key, fromKey) >= 0) &&
1677	<	(toEnd     || compare(key, toKey)   <= 0);
1674	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1675	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1676	>	TreeMap.Entry<K,V> fence) {
1677	>	super(last, fence);
1678	>	}
1679	>	public K next() {
1680	>	return prevEntry().key;
1681	>	}
1682	>	public void remove() {
1683	>	removeDescending();
1684	>	}
1685		}
1686		}
1687
1688		/**
1689	<	* TreeMap Iterator.
1689	>	* @serial include
1690		*/
1691	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1692	<	int expectedModCount = TreeMap.this.modCount;
1402	<	Entry<K,V> lastReturned = null;
1403	<	Entry<K,V> next;
1691	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1692	>	private static final long serialVersionUID = 912986545866124060L;
1693
1694	<	PrivateEntryIterator(Entry<K,V> first) {
1695	<	next = first;
1694	>	AscendingSubMap(TreeMap<K,V> m,
1695	>	boolean fromStart, K lo, boolean loInclusive,
1696	>	boolean toEnd,     K hi, boolean hiInclusive) {
1697	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1698		}
1699
1700	<	public boolean hasNext() {
1701	<	return next != null;
1700	>	public Comparator<? super K> comparator() {
1701	>	return m.comparator();
1702		}
1703
1704	<	Entry<K,V> nextEntry() {
1705	<	if (next == null)
1706	<	throw new NoSuchElementException();
1707	<	if (modCount != expectedModCount)
1708	<	throw new ConcurrentModificationException();
1709	<	lastReturned = next;
1710	<	next = successor(next);
1711	<	return lastReturned;
1704	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1705	>	K toKey,   boolean toInclusive) {
1706	>	if (!inRange(fromKey, fromInclusive))
1707	>	throw new IllegalArgumentException("fromKey out of range");
1708	>	if (!inRange(toKey, toInclusive))
1709	>	throw new IllegalArgumentException("toKey out of range");
1710	>	return new AscendingSubMap(m,
1711	>	false, fromKey, fromInclusive,
1712	>	false, toKey,   toInclusive);
1713		}
1714
1715	<	public void remove() {
1716	<	if (lastReturned == null)
1717	<	throw new IllegalStateException();
1718	<	if (modCount != expectedModCount)
1719	<	throw new ConcurrentModificationException();
1720	<	if (lastReturned.left != null && lastReturned.right != null)
1429	<	next = lastReturned;
1430	<	deleteEntry(lastReturned);
1431	<	expectedModCount++;
1432	<	lastReturned = null;
1715	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1716	>	if (!inRange(toKey, inclusive))
1717	>	throw new IllegalArgumentException("toKey out of range");
1718	>	return new AscendingSubMap(m,
1719	>	fromStart, lo,    loInclusive,
1720	>	false,     toKey, inclusive);
1721		}
1434	–	}
1722
1723	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1724	<	EntryIterator(Entry<K,V> first) {
1725	<	super(first);
1726	<	}
1727	<	public Map.Entry<K,V> next() {
1728	<	return nextEntry();
1723	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1724	>	if (!inRange(fromKey, inclusive))
1725	>	throw new IllegalArgumentException("fromKey out of range");
1726	>	return new AscendingSubMap(m,
1727	>	false, fromKey, inclusive,
1728	>	toEnd, hi,      hiInclusive);
1729		}
1443	–	}
1730
1731	<	class KeyIterator extends PrivateEntryIterator<K> {
1732	<	KeyIterator(Entry<K,V> first) {
1733	<	super(first);
1734	<	}
1735	<	public K next() {
1736	<	return nextEntry().key;
1731	>	public NavigableMap<K,V> descendingMap() {
1732	>	NavigableMap<K,V> mv = descendingMapView;
1733	>	return (mv != null) ? mv :
1734	>	(descendingMapView =
1735	>	new DescendingSubMap(m,
1736	>	fromStart, lo, loInclusive,
1737	>	toEnd,     hi, hiInclusive));
1738		}
1452	–	}
1739
1740	<	class ValueIterator extends PrivateEntryIterator<V> {
1741	<	ValueIterator(Entry<K,V> first) {
1456	<	super(first);
1740	>	Iterator<K> keyIterator() {
1741	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1742		}
1458	–	public V next() {
1459	–	return nextEntry().value;
1460	–	}
1461	–	}
1743
1744	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1745	<	private final K firstExcludedKey;
1465	<
1466	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1467	<	super(first);
1468	<	firstExcludedKey = (firstExcluded == null
1469	<	? null
1470	<	: firstExcluded.key);
1744	>	Iterator<K> descendingKeyIterator() {
1745	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1746		}
1747
1748	<	public boolean hasNext() {
1749	<	return next != null && next.key != firstExcludedKey;
1748	>	final class AscendingEntrySetView extends EntrySetView {
1749	>	public Iterator<Map.Entry<K,V>> iterator() {
1750	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1751	>	}
1752		}
1753
1754	<	public Map.Entry<K,V> next() {
1755	<	if (next == null || next.key == firstExcludedKey)
1756	<	throw new NoSuchElementException();
1480	<	return nextEntry();
1754	>	public Set<Map.Entry<K,V>> entrySet() {
1755	>	EntrySetView es = entrySetView;
1756	>	return (es != null) ? es : new AscendingEntrySetView();
1757		}
1758	+
1759	+	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1760	+	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1761	+	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1762	+	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1763	+	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1764	+	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1765		}
1766
1767		/**
1768	<	* Base for Descending Iterators.
1768	>	* @serial include
1769		*/
1770	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1771	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1772	<	super(first);
1770	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1771	>	private static final long serialVersionUID = 912986545866120460L;
1772	>	DescendingSubMap(TreeMap<K,V> m,
1773	>	boolean fromStart, K lo, boolean loInclusive,
1774	>	boolean toEnd,     K hi, boolean hiInclusive) {
1775	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1776		}
1777
1778	<	Entry<K,V> nextEntry() {
1779	<	if (next == null)
1494	<	throw new NoSuchElementException();
1495	<	if (modCount != expectedModCount)
1496	<	throw new ConcurrentModificationException();
1497	<	lastReturned = next;
1498	<	next = predecessor(next);
1499	<	return lastReturned;
1500	<	}
1501	<	}
1778	>	private final Comparator<? super K> reverseComparator =
1779	>	Collections.reverseOrder(m.comparator);
1780
1781	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1782	<	DescendingEntryIterator(Entry<K,V> first) {
1505	<	super(first);
1781	>	public Comparator<? super K> comparator() {
1782	>	return reverseComparator;
1783		}
1784	<	public Map.Entry<K,V> next() {
1785	<	return nextEntry();
1784	>
1785	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1786	>	K toKey,   boolean toInclusive) {
1787	>	if (!inRange(fromKey, fromInclusive))
1788	>	throw new IllegalArgumentException("fromKey out of range");
1789	>	if (!inRange(toKey, toInclusive))
1790	>	throw new IllegalArgumentException("toKey out of range");
1791	>	return new DescendingSubMap(m,
1792	>	false, toKey,   toInclusive,
1793	>	false, fromKey, fromInclusive);
1794		}
1510	–	}
1795
1796	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1797	<	DescendingKeyIterator(Entry<K,V> first) {
1798	<	super(first);
1796	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1797	>	if (!inRange(toKey, inclusive))
1798	>	throw new IllegalArgumentException("toKey out of range");
1799	>	return new DescendingSubMap(m,
1800	>	false, toKey, inclusive,
1801	>	toEnd, hi,    hiInclusive);
1802		}
1803	<	public K next() {
1804	<	return nextEntry().key;
1803	>
1804	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1805	>	if (!inRange(fromKey, inclusive))
1806	>	throw new IllegalArgumentException("fromKey out of range");
1807	>	return new DescendingSubMap(m,
1808	>	fromStart, lo, loInclusive,
1809	>	false, fromKey, inclusive);
1810		}
1519	–	}
1811
1812	+	public NavigableMap<K,V> descendingMap() {
1813	+	NavigableMap<K,V> mv = descendingMapView;
1814	+	return (mv != null) ? mv :
1815	+	(descendingMapView =
1816	+	new AscendingSubMap(m,
1817	+	fromStart, lo, loInclusive,
1818	+	toEnd,     hi, hiInclusive));
1819	+	}
1820
1821	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1822	<	private final K lastExcludedKey;
1821	>	Iterator<K> keyIterator() {
1822	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1823	>	}
1824
1825	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1826	<	super(last);
1527	<	lastExcludedKey = (lastExcluded == null
1528	<	? null
1529	<	: lastExcluded.key);
1825	>	Iterator<K> descendingKeyIterator() {
1826	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1827		}
1828
1829	<	public boolean hasNext() {
1830	<	return next != null && next.key != lastExcludedKey;
1829	>	final class DescendingEntrySetView extends EntrySetView {
1830	>	public Iterator<Map.Entry<K,V>> iterator() {
1831	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1832	>	}
1833		}
1834
1835	<	public Map.Entry<K,V> next() {
1836	<	if (next == null || next.key == lastExcludedKey)
1837	<	throw new NoSuchElementException();
1539	<	return nextEntry();
1835	>	public Set<Map.Entry<K,V>> entrySet() {
1836	>	EntrySetView es = entrySetView;
1837	>	return (es != null) ? es : new DescendingEntrySetView();
1838		}
1839
1840	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1841	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1842	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1843	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1844	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1845	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1846		}
1847
1848		/**
1849	<	* Compares two keys using the correct comparison method for this TreeMap.
1849	>	* This class exists solely for the sake of serialization
1850	>	* compatibility with previous releases of TreeMap that did not
1851	>	* support NavigableMap.  It translates an old-version SubMap into
1852	>	* a new-version AscendingSubMap. This class is never otherwise
1853	>	* used.
1854	>	*
1855	>	* @serial include
1856		*/
1857	<	private int compare(Object k1, Object k2) {
1858	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1859	<	: comparator.compare((K)k1, (K)k2);
1857	>	private class SubMap extends AbstractMap<K,V>
1858	>	implements SortedMap<K,V>, java.io.Serializable {
1859	>	private static final long serialVersionUID = -6520786458950516097L;
1860	>	private boolean fromStart = false, toEnd = false;
1861	>	private K fromKey, toKey;
1862	>	private Object readResolve() {
1863	>	return new AscendingSubMap(TreeMap.this,
1864	>	fromStart, fromKey, true,
1865	>	toEnd, toKey, false);
1866	>	}
1867	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1868	>	public K lastKey() { throw new InternalError(); }
1869	>	public K firstKey() { throw new InternalError(); }
1870	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1871	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1872	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1873	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1874		}
1875
1876	<	/**
1877	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1554	<	* that it copes with <tt>null</tt> o1 properly.
1555	<	*/
1556	<	private static boolean valEquals(Object o1, Object o2) {
1557	<	return (o1==null ? o2==null : o1.equals(o2));
1558	<	}
1876	>
1877	>	// Red-black mechanics
1878
1879		private static final boolean RED   = false;
1880		private static final boolean BLACK = true;
#	Line 1565 | Line 1884 | public class TreeMap<K,V>
1884		* user (see Map.Entry).
1885		*/
1886
1887	<	static class Entry<K,V> implements Map.Entry<K,V> {
1887	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1888		K key;
1889		V value;
1890		Entry<K,V> left = null;
#	Line 1617 | Line 1936 | public class TreeMap<K,V>
1936		public boolean equals(Object o) {
1937		if (!(o instanceof Map.Entry))
1938		return false;
1939	<	Map.Entry e = (Map.Entry)o;
1939	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1940
1941		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1942		}
#	Line 1637 | Line 1956 | public class TreeMap<K,V>
1956		* Returns the first Entry in the TreeMap (according to the TreeMap's
1957		* key-sort function).  Returns null if the TreeMap is empty.
1958		*/
1959	<	private Entry<K,V> getFirstEntry() {
1959	>	final Entry<K,V> getFirstEntry() {
1960		Entry<K,V> p = root;
1961		if (p != null)
1962		while (p.left != null)
#	Line 1649 | Line 1968 | public class TreeMap<K,V>
1968		* Returns the last Entry in the TreeMap (according to the TreeMap's
1969		* key-sort function).  Returns null if the TreeMap is empty.
1970		*/
1971	<	private Entry<K,V> getLastEntry() {
1971	>	final Entry<K,V> getLastEntry() {
1972		Entry<K,V> p = root;
1973		if (p != null)
1974		while (p.right != null)
#	Line 1660 | Line 1979 | public class TreeMap<K,V>
1979		/**
1980		* Returns the successor of the specified Entry, or null if no such.
1981		*/
1982	<	private Entry<K,V> successor(Entry<K,V> t) {
1982	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1983		if (t == null)
1984		return null;
1985		else if (t.right != null) {
#	Line 1682 | Line 2001 | public class TreeMap<K,V>
2001		/**
2002		* Returns the predecessor of the specified Entry, or null if no such.
2003		*/
2004	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2004	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2005		if (t == null)
2006		return null;
2007		else if (t.left != null) {
#	Line 1732 | Line 2051 | public class TreeMap<K,V>
2051		return (p == null) ? null: p.right;
2052		}
2053
2054	<	/** From CLR **/
2054	>	/** From CLR */
2055		private void rotateLeft(Entry<K,V> p) {
2056	<	Entry<K,V> r = p.right;
2057	<	p.right = r.left;
2058	<	if (r.left != null)
2059	<	r.left.parent = p;
2060	<	r.parent = p.parent;
2061	<	if (p.parent == null)
2062	<	root = r;
2063	<	else if (p.parent.left == p)
2064	<	p.parent.left = r;
2065	<	else
2066	<	p.parent.right = r;
2067	<	r.left = p;
2068	<	p.parent = r;
2056	>	if (p != null) {
2057	>	Entry<K,V> r = p.right;
2058	>	p.right = r.left;
2059	>	if (r.left != null)
2060	>	r.left.parent = p;
2061	>	r.parent = p.parent;
2062	>	if (p.parent == null)
2063	>	root = r;
2064	>	else if (p.parent.left == p)
2065	>	p.parent.left = r;
2066	>	else
2067	>	p.parent.right = r;
2068	>	r.left = p;
2069	>	p.parent = r;
2070	>	}
2071		}
2072
2073	<	/** From CLR **/
2073	>	/** From CLR */
2074		private void rotateRight(Entry<K,V> p) {
2075	<	Entry<K,V> l = p.left;
2076	<	p.left = l.right;
2077	<	if (l.right != null) l.right.parent = p;
2078	<	l.parent = p.parent;
2079	<	if (p.parent == null)
2080	<	root = l;
2081	<	else if (p.parent.right == p)
2082	<	p.parent.right = l;
2083	<	else p.parent.left = l;
2084	<	l.right = p;
2085	<	p.parent = l;
2075	>	if (p != null) {
2076	>	Entry<K,V> l = p.left;
2077	>	p.left = l.right;
2078	>	if (l.right != null) l.right.parent = p;
2079	>	l.parent = p.parent;
2080	>	if (p.parent == null)
2081	>	root = l;
2082	>	else if (p.parent.right == p)
2083	>	p.parent.right = l;
2084	>	else p.parent.left = l;
2085	>	l.right = p;
2086	>	p.parent = l;
2087	>	}
2088		}
2089
2090	<
1768	<	/** From CLR **/
2090	>	/** From CLR */
2091		private void fixAfterInsertion(Entry<K,V> x) {
2092		x.color = RED;
2093
#	Line 1784 | Line 2106 | public class TreeMap<K,V>
2106		}
2107		setColor(parentOf(x), BLACK);
2108		setColor(parentOf(parentOf(x)), RED);
2109	<	if (parentOf(parentOf(x)) != null)
1788	<	rotateRight(parentOf(parentOf(x)));
2109	>	rotateRight(parentOf(parentOf(x)));
2110		}
2111		} else {
2112		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 1799 | Line 2120 | public class TreeMap<K,V>
2120		x = parentOf(x);
2121		rotateRight(x);
2122		}
2123	<	setColor(parentOf(x),  BLACK);
2123	>	setColor(parentOf(x), BLACK);
2124		setColor(parentOf(parentOf(x)), RED);
2125	<	if (parentOf(parentOf(x)) != null)
1805	<	rotateLeft(parentOf(parentOf(x)));
2125	>	rotateLeft(parentOf(parentOf(x)));
2126		}
2127		}
2128		}
#	Line 1812 | Line 2132 | public class TreeMap<K,V>
2132		/**
2133		* Delete node p, and then rebalance the tree.
2134		*/
1815	–
2135		private void deleteEntry(Entry<K,V> p) {
2136	<	decrementSize();
2136	>	modCount++;
2137	>	size--;
2138
2139		// If strictly internal, copy successor's element to p and then make p
2140		// point to successor.
#	Line 1860 | Line 2180 | public class TreeMap<K,V>
2180		}
2181		}
2182
2183	<	/** From CLR **/
2183	>	/** From CLR */
2184		private void fixAfterDeletion(Entry<K,V> x) {
2185		while (x != root && colorOf(x) == BLACK) {
2186		if (x == leftOf(parentOf(x))) {
#	Line 1875 | Line 2195 | public class TreeMap<K,V>
2195
2196		if (colorOf(leftOf(sib))  == BLACK &&
2197		colorOf(rightOf(sib)) == BLACK) {
2198	<	setColor(sib,  RED);
2198	>	setColor(sib, RED);
2199		x = parentOf(x);
2200		} else {
2201		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 1902 | Line 2222 | public class TreeMap<K,V>
2222
2223		if (colorOf(rightOf(sib)) == BLACK &&
2224		colorOf(leftOf(sib)) == BLACK) {
2225	<	setColor(sib,  RED);
2225	>	setColor(sib, RED);
2226		x = parentOf(x);
2227		} else {
2228		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 1953 | Line 2273 | public class TreeMap<K,V>
2273		}
2274		}
2275
1956	–
1957	–
2276		/**
2277		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2278		* deserialize it).
#	Line 1970 | Line 2288 | public class TreeMap<K,V>
2288		buildFromSorted(size, null, s, null);
2289		}
2290
2291	<	/** Intended to be called only from TreeSet.readObject **/
2291	>	/** Intended to be called only from TreeSet.readObject */
2292		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2293		throws java.io.IOException, ClassNotFoundException {
2294		buildFromSorted(size, null, s, defaultVal);
2295		}
2296
2297	<	/** Intended to be called only from TreeSet.addAll **/
2297	>	/** Intended to be called only from TreeSet.addAll */
2298		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2299		try {
2300		buildFromSorted(set.size(), set.iterator(), null, defaultVal);
#	Line 2016 | Line 2334 | public class TreeMap<K,V>
2334		* @throws ClassNotFoundException propagated from readObject.
2335		*         This cannot occur if str is null.
2336		*/
2337	<	private
2338	<	void buildFromSorted(int size, Iterator it,
2339	<	java.io.ObjectInputStream str,
2022	<	V defaultVal)
2337	>	private void buildFromSorted(int size, Iterator it,
2338	>	java.io.ObjectInputStream str,
2339	>	V defaultVal)
2340		throws  java.io.IOException, ClassNotFoundException {
2341		this.size = size;
2342	<	root =
2343	<	buildFromSorted(0, 0, size-1, computeRedLevel(size),
2027	<	it, str, defaultVal);
2342	>	root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2343	>	it, str, defaultVal);
2344		}
2345
2346		/**
2347		* Recursive "helper method" that does the real work of the
2348	<	* of the previous method.  Identically named parameters have
2348	>	* previous method.  Identically named parameters have
2349		* identical definitions.  Additional parameters are documented below.
2350		* It is assumed that the comparator and size fields of the TreeMap are
2351		* already set prior to calling this method.  (It ignores both fields.)
#	Line 2061 | Line 2377 | public class TreeMap<K,V>
2377
2378		if (hi < lo) return null;
2379
2380	<	int mid = (lo + hi) / 2;
2380	>	int mid = (lo + hi) >>> 1;
2381
2382		Entry<K,V> left  = null;
2383		if (lo < mid)

Diff Legend

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