ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/TreeMap.java

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.27 by jsr166, Sun Mar 19 18:03:54 2006 UTC vs.
Revision 1.34 by dl, Sun Apr 23 20:59:49 2006 UTC

#	Line 95 | 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 109 | Line 109 | public class TreeMap<K,V>
109		*/
110		private transient int modCount = 0;
111
112	–	private void incrementSize()   { modCount++; size++; }
113	–	private void decrementSize()   { modCount++; size--; }
114	–
112		/**
113		* Constructs a new, empty tree map, using the natural ordering of its
114		* keys.  All keys inserted into the map must implement the {@link
#	Line 125 | Line 122 | public class TreeMap<K,V>
122		* <tt>ClassCastException</tt>.
123		*/
124		public TreeMap() {
125	+	comparator = null;
126		}
127
128		/**
#	Line 160 | Line 158 | public class TreeMap<K,V>
158		* @throws NullPointerException if the specified map is null
159		*/
160		public TreeMap(Map<? extends K, ? extends V> m) {
161	+	comparator = null;
162		putAll(m);
163		}
164
#	Line 224 | Line 223 | public class TreeMap<K,V>
223		* @since 1.2
224		*/
225		public boolean containsValue(Object value) {
226	<	return (root==null ? false :
227	<	(value==null ? valueSearchNull(root)
228	<	: valueSearchNonNull(root, value)));
229	<	}
231	<
232	<	private boolean valueSearchNull(Entry n) {
233	<	if (n.value == null)
234	<	return true;
235	<
236	<	// Check left and right subtrees for value
237	<	return (n.left  != null && valueSearchNull(n.left)) ||
238	<	(n.right != null && valueSearchNull(n.right));
239	<	}
240	<
241	<	private boolean valueSearchNonNull(Entry n, Object value) {
242	<	// Check this node for the value
243	<	if (value.equals(n.value))
244	<	return true;
245	<
246	<	// Check left and right subtrees for value
247	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
248	<	(n.right != null && valueSearchNonNull(n.right, value));
226	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
227	>	if (valEquals(value, e.value))
228	>	return true;
229	>	return false;
230		}
231
232		/**
#	Line 335 | Line 316 | public class TreeMap<K,V>
316		*         and this map uses natural ordering, or its comparator
317		*         does not permit null keys
318		*/
319	<	private Entry<K,V> getEntry(Object key) {
319	>	final Entry<K,V> getEntry(Object key) {
320		// Offload comparator-based version for sake of performance
321		if (comparator != null)
322		return getEntryUsingComparator(key);
323	+	if (key == null)
324	+	throw new NullPointerException();
325		Comparable<? super K> k = (Comparable<? super K>) key;
326		Entry<K,V> p = root;
327		while (p != null) {
#	Line 359 | Line 342 | public class TreeMap<K,V>
342		* that are less dependent on comparator performance, but is
343		* worthwhile here.)
344		*/
345	<	private Entry<K,V> getEntryUsingComparator(Object key) {
345	>	final Entry<K,V> getEntryUsingComparator(Object key) {
346		K k = (K) key;
347		Comparator<? super K> cpr = comparator;
348	<	Entry<K,V> p = root;
349	<	while (p != null) {
350	<	int cmp = cpr.compare(k, p.key);
351	<	if (cmp < 0)
352	<	p = p.left;
353	<	else if (cmp > 0)
354	<	p = p.right;
355	<	else
356	<	return p;
348	>	if (cpr != null) {
349	>	Entry<K,V> p = root;
350	>	while (p != null) {
351	>	int cmp = cpr.compare(k, p.key);
352	>	if (cmp < 0)
353	>	p = p.left;
354	>	else if (cmp > 0)
355	>	p = p.right;
356	>	else
357	>	return p;
358	>	}
359		}
360		return null;
361		}
#	Line 381 | Line 366 | public class TreeMap<K,V>
366		* key; if no such entry exists (i.e., the greatest key in the Tree is less
367		* than the specified key), returns <tt>null</tt>.
368		*/
369	<	private Entry<K,V> getCeilingEntry(K key) {
369	>	final Entry<K,V> getCeilingEntry(K key) {
370		Entry<K,V> p = root;
371	<	if (p==null)
387	<	return null;
388	<
389	<	while (true) {
371	>	while (p != null) {
372		int cmp = compare(key, p.key);
373		if (cmp < 0) {
374		if (p.left != null)
#	Line 408 | Line 390 | public class TreeMap<K,V>
390		} else
391		return p;
392		}
393	+	return null;
394		}
395
396		/**
#	Line 415 | Line 398 | public class TreeMap<K,V>
398		* exists, returns the entry for the greatest key less than the specified
399		* key; if no such entry exists, returns <tt>null</tt>.
400		*/
401	<	private Entry<K,V> getFloorEntry(K key) {
401	>	final Entry<K,V> getFloorEntry(K key) {
402		Entry<K,V> p = root;
403	<	if (p==null)
421	<	return null;
422	<
423	<	while (true) {
403	>	while (p != null) {
404		int cmp = compare(key, p.key);
405		if (cmp > 0) {
406		if (p.right != null)
#	Line 443 | Line 423 | public class TreeMap<K,V>
423		return p;
424
425		}
426	+	return null;
427		}
428
429		/**
#	Line 451 | Line 432 | public class TreeMap<K,V>
432		* key greater than the specified key; if no such entry exists
433		* returns <tt>null</tt>.
434		*/
435	<	private Entry<K,V> getHigherEntry(K key) {
435	>	final Entry<K,V> getHigherEntry(K key) {
436		Entry<K,V> p = root;
437	<	if (p==null)
457	<	return null;
458	<
459	<	while (true) {
437	>	while (p != null) {
438		int cmp = compare(key, p.key);
439		if (cmp < 0) {
440		if (p.left != null)
#	Line 477 | Line 455 | public class TreeMap<K,V>
455		}
456		}
457		}
458	+	return null;
459		}
460
461		/**
#	Line 484 | Line 463 | public class TreeMap<K,V>
463		* no such entry exists (i.e., the least key in the Tree is greater than
464		* the specified key), returns <tt>null</tt>.
465		*/
466	<	private Entry<K,V> getLowerEntry(K key) {
466	>	final Entry<K,V> getLowerEntry(K key) {
467		Entry<K,V> p = root;
468	<	if (p==null)
490	<	return null;
491	<
492	<	while (true) {
468	>	while (p != null) {
469		int cmp = compare(key, p.key);
470		if (cmp > 0) {
471		if (p.right != null)
#	Line 510 | Line 486 | public class TreeMap<K,V>
486		}
487		}
488		}
489	<	}
514	<
515	<	/**
516	<	* Returns the key corresponding to the specified Entry.
517	<	* @throws NoSuchElementException if the Entry is null
518	<	*/
519	<	private static <K> K key(Entry<K,?> e) {
520	<	if (e==null)
521	<	throw new NoSuchElementException();
522	<	return e.key;
489	>	return null;
490		}
491
492		/**
#	Line 542 | Line 509 | public class TreeMap<K,V>
509		*/
510		public V put(K key, V value) {
511		Entry<K,V> t = root;
545	–
512		if (t == null) {
513	<	// TBD
548	<	//             if (key == null) {
549	<	//                 if (comparator == null)
550	<	//                     throw new NullPointerException();
551	<	//                 comparator.compare(key, key);
552	<	//             }
553	<	incrementSize();
513	>	compare(key, key); // type check
514		root = new Entry<K,V>(key, value, null);
515	+	size = 1;
516	+	modCount++;
517		return null;
518		}
519	<
520	<	while (true) {
521	<	int cmp = compare(key, t.key);
522	<	if (cmp == 0) {
523	<	return t.setValue(value);
524	<	} else if (cmp < 0) {
525	<	if (t.left != null) {
519	>	int cmp;
520	>	Entry<K,V> parent;
521	>	// split comparator and comparable paths
522	>	Comparator<? super K> cpr = comparator;
523	>	if (cpr != null) {
524	>	do {
525	>	parent = t;
526	>	cmp = cpr.compare(key, t.key);
527	>	if (cmp < 0)
528		t = t.left;
529	<	} else {
566	<	incrementSize();
567	<	t.left = new Entry<K,V>(key, value, t);
568	<	fixAfterInsertion(t.left);
569	<	return null;
570	<	}
571	<	} else { // cmp > 0
572	<	if (t.right != null) {
529	>	else if (cmp > 0)
530		t = t.right;
531	<	} else {
532	<	incrementSize();
533	<	t.right = new Entry<K,V>(key, value, t);
534	<	fixAfterInsertion(t.right);
535	<	return null;
536	<	}
537	<	}
531	>	else
532	>	return t.setValue(value);
533	>	} while (t != null);
534	>	}
535	>	else {
536	>	if (key == null)
537	>	throw new NullPointerException();
538	>	Comparable<? super K> k = (Comparable<? super K>) key;
539	>	do {
540	>	parent = t;
541	>	cmp = k.compareTo(t.key);
542	>	if (cmp < 0)
543	>	t = t.left;
544	>	else if (cmp > 0)
545	>	t = t.right;
546	>	else
547	>	return t.setValue(value);
548	>	} while (t != null);
549		}
550	+	Entry<K,V> e = new Entry<K,V>(key, value, parent);
551	+	if (cmp < 0)
552	+	parent.left = e;
553	+	else
554	+	parent.right = e;
555	+	fixAfterInsertion(e);
556	+	size++;
557	+	modCount++;
558	+	return null;
559		}
560
561		/**
#	Line 634 | Line 611 | public class TreeMap<K,V>
611		clone.size = 0;
612		clone.modCount = 0;
613		clone.entrySet = null;
614	<	clone.descendingEntrySet = null;
615	<	clone.descendingKeySet = null;
614	>	clone.navigableKeySet = null;
615	>	clone.descendingMap = null;
616
617		// Initialize clone with our mappings
618		try {
#	Line 653 | Line 630 | public class TreeMap<K,V>
630		* @since 1.6
631		*/
632		public Map.Entry<K,V> firstEntry() {
633	<	Entry<K,V> e = getFirstEntry();
657	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
633	>	return exportEntry(getFirstEntry());
634		}
635
636		/**
637		* @since 1.6
638		*/
639		public Map.Entry<K,V> lastEntry() {
640	<	Entry<K,V> e = getLastEntry();
665	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
640	>	return exportEntry(getLastEntry());
641		}
642
643		/**
#	Line 670 | Line 645 | public class TreeMap<K,V>
645		*/
646		public Map.Entry<K,V> pollFirstEntry() {
647		Entry<K,V> p = getFirstEntry();
648	<	if (p == null)
649	<	return null;
650	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
676	<	deleteEntry(p);
648	>	Map.Entry<K,V> result = exportEntry(p);
649	>	if (p != null)
650	>	deleteEntry(p);
651		return result;
652		}
653
#	Line 682 | Line 656 | public class TreeMap<K,V>
656		*/
657		public Map.Entry<K,V> pollLastEntry() {
658		Entry<K,V> p = getLastEntry();
659	<	if (p == null)
660	<	return null;
661	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
688	<	deleteEntry(p);
659	>	Map.Entry<K,V> result = exportEntry(p);
660	>	if (p != null)
661	>	deleteEntry(p);
662		return result;
663		}
664
#	Line 697 | Line 670 | public class TreeMap<K,V>
670		* @since 1.6
671		*/
672		public Map.Entry<K,V> lowerEntry(K key) {
673	<	Entry<K,V> e =  getLowerEntry(key);
701	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
673	>	return exportEntry(getLowerEntry(key));
674		}
675
676		/**
#	Line 709 | Line 681 | public class TreeMap<K,V>
681		* @since 1.6
682		*/
683		public K lowerKey(K key) {
684	<	Entry<K,V> e =  getLowerEntry(key);
713	<	return (e == null)? null : e.key;
684	>	return keyOrNull(getLowerEntry(key));
685		}
686
687		/**
#	Line 721 | Line 692 | public class TreeMap<K,V>
692		* @since 1.6
693		*/
694		public Map.Entry<K,V> floorEntry(K key) {
695	<	Entry<K,V> e = getFloorEntry(key);
725	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
695	>	return exportEntry(getFloorEntry(key));
696		}
697
698		/**
#	Line 733 | Line 703 | public class TreeMap<K,V>
703		* @since 1.6
704		*/
705		public K floorKey(K key) {
706	<	Entry<K,V> e = getFloorEntry(key);
737	<	return (e == null)? null : e.key;
706	>	return keyOrNull(getFloorEntry(key));
707		}
708
709		/**
#	Line 745 | Line 714 | public class TreeMap<K,V>
714		* @since 1.6
715		*/
716		public Map.Entry<K,V> ceilingEntry(K key) {
717	<	Entry<K,V> e = getCeilingEntry(key);
749	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
717	>	return exportEntry(getCeilingEntry(key));
718		}
719
720		/**
#	Line 757 | Line 725 | public class TreeMap<K,V>
725		* @since 1.6
726		*/
727		public K ceilingKey(K key) {
728	<	Entry<K,V> e = getCeilingEntry(key);
761	<	return (e == null)? null : e.key;
728	>	return keyOrNull(getCeilingEntry(key));
729		}
730
731		/**
#	Line 769 | Line 736 | public class TreeMap<K,V>
736		* @since 1.6
737		*/
738		public Map.Entry<K,V> higherEntry(K key) {
739	<	Entry<K,V> e = getHigherEntry(key);
773	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
739	>	return exportEntry(getHigherEntry(key));
740		}
741
742		/**
#	Line 781 | Line 747 | public class TreeMap<K,V>
747		* @since 1.6
748		*/
749		public K higherKey(K key) {
750	<	Entry<K,V> e = getHigherEntry(key);
785	<	return (e == null)? null : e.key;
750	>	return keyOrNull(getHigherEntry(key));
751		}
752
753		// Views
#	Line 792 | Line 757 | public class TreeMap<K,V>
757		* the first time this view is requested.  Views are stateless, so
758		* there's no reason to create more than one.
759		*/
760	<	private transient Set<Map.Entry<K,V>> entrySet = null;
761	<	private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
762	<	private transient Set<K> descendingKeySet = null;
760	>	private transient EntrySet entrySet = null;
761	>	private transient KeySet<K> navigableKeySet = null;
762	>	private transient NavigableMap<K,V> descendingMap = null;
763
764		/**
765		* Returns a {@link Set} view of the keys contained in this map.
#	Line 811 | Line 776 | public class TreeMap<K,V>
776		* operations.
777		*/
778		public Set<K> keySet() {
779	<	Set<K> ks = keySet;
815	<	return (ks != null) ? ks : (keySet = new KeySet());
779	>	return navigableKeySet();
780		}
781
782	<	class KeySet extends AbstractSet<K> {
783	<	public Iterator<K> iterator() {
784	<	return new KeyIterator(getFirstEntry());
785	<	}
786	<
787	<	public int size() {
788	<	return TreeMap.this.size();
825	<	}
826	<
827	<	public boolean contains(Object o) {
828	<	return containsKey(o);
829	<	}
830	<
831	<	public boolean remove(Object o) {
832	<	int oldSize = size;
833	<	TreeMap.this.remove(o);
834	<	return size != oldSize;
835	<	}
782	>	/**
783	>	* @since 1.6
784	>	*/
785	>	public NavigableSet<K> navigableKeySet() {
786	>	KeySet<K> nks = navigableKeySet;
787	>	return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
788	>	}
789
790	<	public void clear() {
791	<	TreeMap.this.clear();
792	<	}
790	>	/**
791	>	* @since 1.6
792	>	*/
793	>	public NavigableSet<K> descendingKeySet() {
794	>	return descendingMap().navigableKeySet();
795		}
796
797		/**
#	Line 859 | Line 814 | public class TreeMap<K,V>
814		return (vs != null) ? vs : (values = new Values());
815		}
816
817	+	/**
818	+	* Returns a {@link Set} view of the mappings contained in this map.
819	+	* The set's iterator returns the entries in ascending key order.
820	+	* The set is backed by the map, so changes to the map are
821	+	* reflected in the set, and vice-versa.  If the map is modified
822	+	* while an iteration over the set is in progress (except through
823	+	* the iterator's own <tt>remove</tt> operation, or through the
824	+	* <tt>setValue</tt> operation on a map entry returned by the
825	+	* iterator) the results of the iteration are undefined.  The set
826	+	* supports element removal, which removes the corresponding
827	+	* mapping from the map, via the <tt>Iterator.remove</tt>,
828	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
829	+	* <tt>clear</tt> operations.  It does not support the
830	+	* <tt>add</tt> or <tt>addAll</tt> operations.
831	+	*/
832	+	public Set<Map.Entry<K,V>> entrySet() {
833	+	EntrySet es = entrySet;
834	+	return (es != null) ? es : (entrySet = new EntrySet());
835	+	}
836	+
837	+	/**
838	+	* @since 1.6
839	+	*/
840	+	public NavigableMap<K, V> descendingMap() {
841	+	NavigableMap<K, V> km = descendingMap;
842	+	return (km != null) ? km :
843	+	(descendingMap = new DescendingSubMap(this,
844	+	true, null, true,
845	+	true, null, true));
846	+	}
847	+
848	+	/**
849	+	* @throws ClassCastException       {@inheritDoc}
850	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
851	+	*         null and this map uses natural ordering, or its comparator
852	+	*         does not permit null keys
853	+	* @throws IllegalArgumentException {@inheritDoc}
854	+	* @since 1.6
855	+	*/
856	+	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
857	+	K toKey,   boolean toInclusive) {
858	+	return new AscendingSubMap(this,
859	+	false, fromKey, fromInclusive,
860	+	false, toKey,   toInclusive);
861	+	}
862	+
863	+	/**
864	+	* @throws ClassCastException       {@inheritDoc}
865	+	* @throws NullPointerException if <tt>toKey</tt> is null
866	+	*         and this map uses natural ordering, or its comparator
867	+	*         does not permit null keys
868	+	* @throws IllegalArgumentException {@inheritDoc}
869	+	* @since 1.6
870	+	*/
871	+	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
872	+	return new AscendingSubMap(this,
873	+	true,  null,  true,
874	+	false, toKey, inclusive);
875	+	}
876	+
877	+	/**
878	+	* @throws ClassCastException       {@inheritDoc}
879	+	* @throws NullPointerException if <tt>fromKey</tt> is null
880	+	*         and this map uses natural ordering, or its comparator
881	+	*         does not permit null keys
882	+	* @throws IllegalArgumentException {@inheritDoc}
883	+	* @since 1.6
884	+	*/
885	+	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
886	+	return new AscendingSubMap(this,
887	+	false, fromKey, inclusive,
888	+	true,  null,    true);
889	+	}
890	+
891	+	/**
892	+	* @throws ClassCastException       {@inheritDoc}
893	+	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
894	+	*         null and this map uses natural ordering, or its comparator
895	+	*         does not permit null keys
896	+	* @throws IllegalArgumentException {@inheritDoc}
897	+	*/
898	+	public SortedMap<K,V> subMap(K fromKey, K toKey) {
899	+	return subMap(fromKey, true, toKey, false);
900	+	}
901	+
902	+	/**
903	+	* @throws ClassCastException       {@inheritDoc}
904	+	* @throws NullPointerException if <tt>toKey</tt> is null
905	+	*         and this map uses natural ordering, or its comparator
906	+	*         does not permit null keys
907	+	* @throws IllegalArgumentException {@inheritDoc}
908	+	*/
909	+	public SortedMap<K,V> headMap(K toKey) {
910	+	return headMap(toKey, false);
911	+	}
912	+
913	+	/**
914	+	* @throws ClassCastException       {@inheritDoc}
915	+	* @throws NullPointerException if <tt>fromKey</tt> is null
916	+	*         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> tailMap(K fromKey) {
921	+	return tailMap(fromKey, true);
922	+	}
923	+
924	+	// View class support
925	+
926		class Values extends AbstractCollection<V> {
927		public Iterator<V> iterator() {
928		return new ValueIterator(getFirstEntry());
#	Line 869 | Line 933 | public class TreeMap<K,V>
933		}
934
935		public boolean contains(Object o) {
936	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
873	<	if (valEquals(e.getValue(), o))
874	<	return true;
875	<	return false;
936	>	return TreeMap.this.containsValue(o);
937		}
938
939		public boolean remove(Object o) {
#	Line 890 | Line 951 | public class TreeMap<K,V>
951		}
952		}
953
893	–	/**
894	–	* Returns a {@link Set} view of the mappings contained in this map.
895	–	* The set's iterator returns the entries in ascending key order.
896	–	* The set is backed by the map, so changes to the map are
897	–	* reflected in the set, and vice-versa.  If the map is modified
898	–	* while an iteration over the set is in progress (except through
899	–	* the iterator's own <tt>remove</tt> operation, or through the
900	–	* <tt>setValue</tt> operation on a map entry returned by the
901	–	* iterator) the results of the iteration are undefined.  The set
902	–	* supports element removal, which removes the corresponding
903	–	* mapping from the map, via the <tt>Iterator.remove</tt>,
904	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
905	–	* <tt>clear</tt> operations.  It does not support the
906	–	* <tt>add</tt> or <tt>addAll</tt> operations.
907	–	*/
908	–	public Set<Map.Entry<K,V>> entrySet() {
909	–	Set<Map.Entry<K,V>> es = entrySet;
910	–	return (es != null) ? es : (entrySet = new EntrySet());
911	–	}
912	–
954		class EntrySet extends AbstractSet<Map.Entry<K,V>> {
955		public Iterator<Map.Entry<K,V>> iterator() {
956		return new EntryIterator(getFirstEntry());
#	Line 946 | Line 987 | public class TreeMap<K,V>
987		}
988		}
989
990	<	/**
991	<	* @since 1.6
990	>	/*
991	>	* Unlike Values and EntrySet, the KeySet class is static,
992	>	* delegating to a NavigableMap to allow use by SubMaps, which
993	>	* outweighs the ugliness of needing type-tests for the following
994	>	* Iterator methods that are defined appropriately in main versus
995	>	* submap classes.
996		*/
997	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
998	<	Set<Map.Entry<K,V>> es = descendingEntrySet;
999	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
997	>
998	>	Iterator<K> keyIterator() {
999	>	return new KeyIterator(getFirstEntry());
1000		}
1001
1002	<	class DescendingEntrySet extends EntrySet {
1003	<	public Iterator<Map.Entry<K,V>> iterator() {
1004	<	return new DescendingEntryIterator(getLastEntry());
1002	>	Iterator<K> descendingKeyIterator() {
1003	>	return new DescendingKeyIterator(getFirstEntry());
1004	>	}
1005	>
1006	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1007	>	private final NavigableMap<E, Object> m;
1008	>	KeySet(NavigableMap<E,Object> map) { m = map; }
1009	>
1010	>	public Iterator<E> iterator() {
1011	>	if (m instanceof TreeMap)
1012	>	return ((TreeMap<E,Object>)m).keyIterator();
1013	>	else
1014	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1015	>	}
1016	>
1017	>	public Iterator<E> descendingIterator() {
1018	>	if (m instanceof TreeMap)
1019	>	return ((TreeMap<E,Object>)m).descendingKeyIterator();
1020	>	else
1021	>	return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1022	>	}
1023	>
1024	>	public int size() { return m.size(); }
1025	>	public boolean isEmpty() { return m.isEmpty(); }
1026	>	public boolean contains(Object o) { return m.containsKey(o); }
1027	>	public void clear() { m.clear(); }
1028	>	public E lower(E e) { return m.lowerKey(e); }
1029	>	public E floor(E e) { return m.floorKey(e); }
1030	>	public E ceiling(E e) { return m.ceilingKey(e); }
1031	>	public E higher(E e) { return m.higherKey(e); }
1032	>	public E first() { return m.firstKey(); }
1033	>	public E last() { return m.lastKey(); }
1034	>	public Comparator<? super E> comparator() { return m.comparator(); }
1035	>	public E pollFirst() {
1036	>	Map.Entry<E,Object> e = m.pollFirstEntry();
1037	>	return e == null? null : e.getKey();
1038	>	}
1039	>	public E pollLast() {
1040	>	Map.Entry<E,Object> e = m.pollLastEntry();
1041	>	return e == null? null : e.getKey();
1042	>	}
1043	>	public boolean remove(Object o) {
1044	>	int oldSize = size();
1045	>	m.remove(o);
1046	>	return size() != oldSize;
1047	>	}
1048	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1049	>	E toElement, boolean toInclusive) {
1050	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1051	>	toElement,   toInclusive));
1052	>	}
1053	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1054	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1055	>	}
1056	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1057	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1058	>	}
1059	>	public SortedSet<E> subSet(E fromElement, E toElement) {
1060	>	return subSet(fromElement, true, toElement, false);
1061	>	}
1062	>	public SortedSet<E> headSet(E toElement) {
1063	>	return headSet(toElement, false);
1064	>	}
1065	>	public SortedSet<E> tailSet(E fromElement) {
1066	>	return tailSet(fromElement, true);
1067	>	}
1068	>	public NavigableSet<E> descendingSet() {
1069	>	return new TreeSet(m.descendingMap());
1070		}
1071		}
1072
1073		/**
1074	<	* @since 1.6
1074	>	* Base class for TreeMap Iterators
1075		*/
1076	<	public Set<K> descendingKeySet() {
1077	<	Set<K> ks = descendingKeySet;
1078	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1076	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1077	>	Entry<K,V> next;
1078	>	Entry<K,V> lastReturned;
1079	>	int expectedModCount;
1080	>
1081	>	PrivateEntryIterator(Entry<K,V> first) {
1082	>	expectedModCount = modCount;
1083	>	lastReturned = null;
1084	>	next = first;
1085	>	}
1086	>
1087	>	public final boolean hasNext() {
1088	>	return next != null;
1089	>	}
1090	>
1091	>	final Entry<K,V> nextEntry() {
1092	>	Entry<K,V> e = lastReturned = next;
1093	>	if (e == null)
1094	>	throw new NoSuchElementException();
1095	>	if (modCount != expectedModCount)
1096	>	throw new ConcurrentModificationException();
1097	>	next = successor(e);
1098	>	return e;
1099	>	}
1100	>
1101	>	final Entry<K,V> prevEntry() {
1102	>	Entry<K,V> e = lastReturned= next;
1103	>	if (e == null)
1104	>	throw new NoSuchElementException();
1105	>	if (modCount != expectedModCount)
1106	>	throw new ConcurrentModificationException();
1107	>	next = predecessor(e);
1108	>	return e;
1109	>	}
1110	>
1111	>	public void remove() {
1112	>	if (lastReturned == null)
1113	>	throw new IllegalStateException();
1114	>	if (modCount != expectedModCount)
1115	>	throw new ConcurrentModificationException();
1116	>	if (lastReturned.left != null && lastReturned.right != null)
1117	>	next = lastReturned;
1118	>	deleteEntry(lastReturned);
1119	>	expectedModCount++;
1120	>	lastReturned = null;
1121	>	}
1122		}
1123
1124	<	class DescendingKeySet extends KeySet {
1125	<	public Iterator<K> iterator() {
1126	<	return new DescendingKeyIterator(getLastEntry());
1124	>	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1125	>	EntryIterator(Entry<K,V> first) {
1126	>	super(first);
1127	>	}
1128	>	public Map.Entry<K,V> next() {
1129	>	return nextEntry();
1130		}
1131		}
1132
1133	<	/**
1134	<	* @throws ClassCastException       {@inheritDoc}
1135	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1136	<	*         null and this map uses natural ordering, or its comparator
1137	<	*         does not permit null keys
1138	<	* @throws IllegalArgumentException {@inheritDoc}
1139	<	* @since 1.6
1140	<	*/
1141	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1142	<	return new SubMap(fromKey, toKey);
1133	>	final class ValueIterator extends PrivateEntryIterator<V> {
1134	>	ValueIterator(Entry<K,V> first) {
1135	>	super(first);
1136	>	}
1137	>	public V next() {
1138	>	return nextEntry().value;
1139	>	}
1140	>	}
1141	>
1142	>	final class KeyIterator extends PrivateEntryIterator<K> {
1143	>	KeyIterator(Entry<K,V> first) {
1144	>	super(first);
1145	>	}
1146	>	public K next() {
1147	>	return nextEntry().key;
1148	>	}
1149	>	}
1150	>
1151	>	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1152	>	DescendingKeyIterator(Entry<K,V> first) {
1153	>	super(first);
1154	>	}
1155	>	public K next() {
1156	>	return prevEntry().key;
1157	>	}
1158		}
1159
1160	+	// Little utilities
1161	+
1162		/**
1163	<	* @throws ClassCastException       {@inheritDoc}
991	<	* @throws NullPointerException if <tt>toKey</tt> is null
992	<	*         and this map uses natural ordering, or its comparator
993	<	*         does not permit null keys
994	<	* @throws IllegalArgumentException {@inheritDoc}
995	<	* @since 1.6
1163	>	* Compares two keys using the correct comparison method for this TreeMap.
1164		*/
1165	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1166	<	return new SubMap(toKey, true);
1165	>	final int compare(Object k1, Object k2) {
1166	>	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1167	>	: comparator.compare((K)k1, (K)k2);
1168		}
1169
1170		/**
1171	<	* @throws ClassCastException       {@inheritDoc}
1172	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1004	<	*         and this map uses natural ordering, or its comparator
1005	<	*         does not permit null keys
1006	<	* @throws IllegalArgumentException {@inheritDoc}
1007	<	* @since 1.6
1171	>	* Test two values for equality.  Differs from o1.equals(o2) only in
1172	>	* that it copes with <tt>null</tt> o1 properly.
1173		*/
1174	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1175	<	return new SubMap(fromKey, false);
1174	>	final static boolean valEquals(Object o1, Object o2) {
1175	>	return (o1==null ? o2==null : o1.equals(o2));
1176		}
1177
1178		/**
1179	<	* Equivalent to {@link #navigableSubMap} but with a return type
1015	<	* conforming to the <tt>SortedMap</tt> interface.
1016	<	*
1017	<	* <p>{@inheritDoc}
1018	<	*
1019	<	* @throws ClassCastException       {@inheritDoc}
1020	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
1021	<	*         null and this map uses natural ordering, or its comparator
1022	<	*         does not permit null keys
1023	<	* @throws IllegalArgumentException {@inheritDoc}
1179	>	* Return SimpleImmutableEntry for entry, or null if null
1180		*/
1181	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1182	<	return new SubMap(fromKey, toKey);
1181	>	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1182	>	return e == null? null :
1183	>	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1184		}
1185
1186		/**
1187	<	* Equivalent to {@link #navigableHeadMap} but with a return type
1031	<	* conforming to the <tt>SortedMap</tt> interface.
1032	<	*
1033	<	* <p>{@inheritDoc}
1034	<	*
1035	<	* @throws ClassCastException       {@inheritDoc}
1036	<	* @throws NullPointerException if <tt>toKey</tt> is null
1037	<	*         and this map uses natural ordering, or its comparator
1038	<	*         does not permit null keys
1039	<	* @throws IllegalArgumentException {@inheritDoc}
1187	>	* Return key for entry, or null if null
1188		*/
1189	<	public SortedMap<K,V> headMap(K toKey) {
1190	<	return new SubMap(toKey, true);
1189	>	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1190	>	return e == null? null : e.key;
1191		}
1192
1193		/**
1194	<	* Equivalent to {@link #navigableTailMap} but with a return type
1195	<	* conforming to the <tt>SortedMap</tt> interface.
1048	<	*
1049	<	* <p>{@inheritDoc}
1050	<	*
1051	<	* @throws ClassCastException       {@inheritDoc}
1052	<	* @throws NullPointerException if <tt>fromKey</tt> is null
1053	<	*         and this map uses natural ordering, or its comparator
1054	<	*         does not permit null keys
1055	<	* @throws IllegalArgumentException {@inheritDoc}
1194	>	* Returns the key corresponding to the specified Entry.
1195	>	* @throws NoSuchElementException if the Entry is null
1196		*/
1197	<	public SortedMap<K,V> tailMap(K fromKey) {
1198	<	return new SubMap(fromKey, false);
1197	>	static <K> K key(Entry<K,?> e) {
1198	>	if (e==null)
1199	>	throw new NoSuchElementException();
1200	>	return e.key;
1201		}
1202
1061	–	private class SubMap
1062	–	extends AbstractMap<K,V>
1063	–	implements NavigableMap<K,V>, java.io.Serializable {
1064	–	private static final long serialVersionUID = -6520786458950516097L;
1203
1204	<	/**
1205	<	* fromKey is significant only if fromStart is false.  Similarly,
1206	<	* toKey is significant only if toStart is false.
1204	>	// SubMaps
1205	>
1206	>	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1207	>	implements NavigableMap<K,V>, java.io.Serializable {
1208	>	/*
1209	>	* The backing map.
1210		*/
1211	<	private boolean fromStart = false, toEnd = false;
1071	<	private K fromKey, toKey;
1211	>	final TreeMap<K,V> m;
1212
1213	<	SubMap(K fromKey, K toKey) {
1214	<	if (compare(fromKey, toKey) > 0)
1215	<	throw new IllegalArgumentException("fromKey > toKey");
1216	<	this.fromKey = fromKey;
1217	<	this.toKey = toKey;
1218	<	}
1213	>	/*
1214	>	* Endpoints are represented as triples (fromStart, lo,
1215	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1216	>	* true, then the low (absolute) bound is the start of the
1217	>	* backing map, and the other values are ignored. Otherwise,
1218	>	* if loInclusive is true, lo is the inclusive bound, else lo
1219	>	* is the exclusive bound. Similarly for the upper bound.
1220	>	*/
1221
1222	<	SubMap(K key, boolean headMap) {
1223	<	compare(key, key); // Type-check key
1224	<
1225	<	if (headMap) {
1226	<	fromStart = true;
1227	<	toKey = key;
1222	>	final K lo, hi;
1223	>	final boolean fromStart, toEnd;
1224	>	final boolean loInclusive, hiInclusive;
1225	>
1226	>	NavigableSubMap(TreeMap<K,V> m,
1227	>	boolean fromStart, K lo, boolean loInclusive,
1228	>	boolean toEnd,     K hi, boolean hiInclusive) {
1229	>	if (!fromStart && !toEnd) {
1230	>	if (m.compare(lo, hi) > 0)
1231	>	throw new IllegalArgumentException("fromKey > toKey");
1232		} else {
1233	<	toEnd = true;
1234	<	fromKey = key;
1233	>	if (!fromStart) // type check
1234	>	m.compare(lo, lo);
1235	>	if (!toEnd)
1236	>	m.compare(hi, hi);
1237		}
1090	–	}
1238
1239	<	SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
1239	>	this.m = m;
1240		this.fromStart = fromStart;
1241	<	this.fromKey= fromKey;
1241	>	this.lo = lo;
1242	>	this.loInclusive = loInclusive;
1243		this.toEnd = toEnd;
1244	<	this.toKey = toKey;
1244	>	this.hi = hi;
1245	>	this.hiInclusive = hiInclusive;
1246	>	}
1247	>
1248	>	// internal utilities
1249	>
1250	>	final boolean tooLow(Object key) {
1251	>	if (!fromStart) {
1252	>	int c = m.compare(key, lo);
1253	>	if (c < 0 || (c == 0 && !loInclusive))
1254	>	return true;
1255	>	}
1256	>	return false;
1257	>	}
1258	>
1259	>	final boolean tooHigh(Object key) {
1260	>	if (!toEnd) {
1261	>	int c = m.compare(key, hi);
1262	>	if (c > 0 || (c == 0 && !hiInclusive))
1263	>	return true;
1264	>	}
1265	>	return false;
1266	>	}
1267	>
1268	>	final boolean inRange(Object key) {
1269	>	return !tooLow(key) && !tooHigh(key);
1270	>	}
1271	>
1272	>	final boolean inClosedRange(Object key) {
1273	>	return (fromStart || m.compare(key, lo) >= 0)
1274	>	&& (toEnd || m.compare(hi, key) >= 0);
1275	>	}
1276	>
1277	>	final boolean inRange(Object key, boolean inclusive) {
1278	>	return inclusive ? inRange(key) : inClosedRange(key);
1279	>	}
1280	>
1281	>	/*
1282	>	* Absolute versions of relation operations.
1283	>	* Subclasses map to these using like-named "sub"
1284	>	* versions that invert senses for descending maps
1285	>	*/
1286	>
1287	>	final TreeMap.Entry<K,V> absLowest() {
1288	>	TreeMap.Entry<K,V> e =
1289	>	(fromStart ?  m.getFirstEntry() :
1290	>	(loInclusive ? m.getCeilingEntry(lo) :
1291	>	m.getHigherEntry(lo)));
1292	>	return (e == null || tooHigh(e.key)) ? null : e;
1293	>	}
1294	>
1295	>	final TreeMap.Entry<K,V> absHighest() {
1296	>	TreeMap.Entry<K,V> e =
1297	>	(toEnd ?  m.getLastEntry() :
1298	>	(hiInclusive ?  m.getFloorEntry(hi) :
1299	>	m.getLowerEntry(hi)));
1300	>	return (e == null || tooLow(e.key)) ? null : e;
1301	>	}
1302	>
1303	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1304	>	if (tooLow(key))
1305	>	return absLowest();
1306	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1307	>	return (e == null || tooHigh(e.key)) ? null : e;
1308	>	}
1309	>
1310	>	final TreeMap.Entry<K,V> absHigher(K key) {
1311	>	if (tooLow(key))
1312	>	return absLowest();
1313	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1314	>	return (e == null || tooHigh(e.key)) ? null : e;
1315	>	}
1316	>
1317	>	final TreeMap.Entry<K,V> absFloor(K key) {
1318	>	if (tooHigh(key))
1319	>	return absHighest();
1320	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1321	>	return (e == null || tooLow(e.key)) ? null : e;
1322	>	}
1323	>
1324	>	final TreeMap.Entry<K,V> absLower(K key) {
1325	>	if (tooHigh(key))
1326	>	return absHighest();
1327	>	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1328	>	return (e == null || tooLow(e.key)) ? null : e;
1329	>	}
1330	>
1331	>	/** Returns the absolute high fence for ascending traversal */
1332	>	final TreeMap.Entry<K,V> absHighFence() {
1333	>	return (toEnd ? null : (hiInclusive ?
1334	>	m.getHigherEntry(hi) :
1335	>	m.getCeilingEntry(hi)));
1336	>	}
1337	>
1338	>	/** Return the absolute low fence for descending traversal  */
1339	>	final TreeMap.Entry<K,V> absLowFence() {
1340	>	return (fromStart ? null : (loInclusive ?
1341	>	m.getLowerEntry(lo) :
1342	>	m.getFloorEntry(lo)));
1343		}
1344
1345	+	// Abstract methods defined in ascending vs descending classes
1346	+	// These relay to the appropriate  absolute versions
1347	+
1348	+	abstract TreeMap.Entry<K,V> subLowest();
1349	+	abstract TreeMap.Entry<K,V> subHighest();
1350	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1351	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1352	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1353	+	abstract TreeMap.Entry<K,V> subLower(K key);
1354	+
1355	+	/** Returns ascending iterator from the perspective of this submap */
1356	+	abstract Iterator<K> keyIterator();
1357	+
1358	+	/** Returns descending iterator from the perspective of this submap */
1359	+	abstract Iterator<K> descendingKeyIterator();
1360	+
1361	+	// public methods
1362	+
1363		public boolean isEmpty() {
1364	<	return entrySet().isEmpty();
1364	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1365		}
1366
1367	<	public boolean containsKey(Object key) {
1368	<	return inRange(key) && TreeMap.this.containsKey(key);
1367	>	public int size() {
1368	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1369		}
1370
1371	<	public V get(Object key) {
1372	<	if (!inRange(key))
1109	<	return null;
1110	<	return TreeMap.this.get(key);
1371	>	public final boolean containsKey(Object key) {
1372	>	return inRange(key) && m.containsKey(key);
1373		}
1374
1375	<	public V put(K key, V value) {
1375	>	public final V put(K key, V value) {
1376		if (!inRange(key))
1377		throw new IllegalArgumentException("key out of range");
1378	<	return TreeMap.this.put(key, value);
1378	>	return m.put(key, value);
1379		}
1380
1381	<	public V remove(Object key) {
1382	<	if (!inRange(key))
1121	<	return null;
1122	<	return TreeMap.this.remove(key);
1381	>	public final V get(Object key) {
1382	>	return !inRange(key)? null :  m.get(key);
1383		}
1384
1385	<	public Comparator<? super K> comparator() {
1386	<	return comparator;
1385	>	public final V remove(Object key) {
1386	>	return !inRange(key)? null  : m.remove(key);
1387		}
1388
1389	<	public K firstKey() {
1390	<	TreeMap.Entry<K,V> e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
1131	<	K first = key(e);
1132	<	if (!toEnd && compare(first, toKey) >= 0)
1133	<	throw new NoSuchElementException();
1134	<	return first;
1389	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1390	>	return exportEntry(subCeiling(key));
1391		}
1392
1393	<	public K lastKey() {
1394	<	TreeMap.Entry<K,V> e = toEnd ? getLastEntry() : getLowerEntry(toKey);
1139	<	K last = key(e);
1140	<	if (!fromStart && compare(last, fromKey) < 0)
1141	<	throw new NoSuchElementException();
1142	<	return last;
1393	>	public final K ceilingKey(K key) {
1394	>	return keyOrNull(subCeiling(key));
1395		}
1396
1397	<	public Map.Entry<K,V> firstEntry() {
1398	<	TreeMap.Entry<K,V> e = fromStart ?
1147	<	getFirstEntry() : getCeilingEntry(fromKey);
1148	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1149	<	return null;
1150	<	return e;
1397	>	public final Map.Entry<K,V> higherEntry(K key) {
1398	>	return exportEntry(subHigher(key));
1399		}
1400
1401	<	public Map.Entry<K,V> lastEntry() {
1402	<	TreeMap.Entry<K,V> e = toEnd ?
1155	<	getLastEntry() : getLowerEntry(toKey);
1156	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1157	<	return null;
1158	<	return e;
1401	>	public final K higherKey(K key) {
1402	>	return keyOrNull(subHigher(key));
1403		}
1404
1405	<	public Map.Entry<K,V> pollFirstEntry() {
1406	<	TreeMap.Entry<K,V> e = fromStart ?
1163	<	getFirstEntry() : getCeilingEntry(fromKey);
1164	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1165	<	return null;
1166	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1167	<	deleteEntry(e);
1168	<	return result;
1405	>	public final Map.Entry<K,V> floorEntry(K key) {
1406	>	return exportEntry(subFloor(key));
1407		}
1408
1409	<	public Map.Entry<K,V> pollLastEntry() {
1410	<	TreeMap.Entry<K,V> e = toEnd ?
1173	<	getLastEntry() : getLowerEntry(toKey);
1174	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1175	<	return null;
1176	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1177	<	deleteEntry(e);
1178	<	return result;
1409	>	public final K floorKey(K key) {
1410	>	return keyOrNull(subFloor(key));
1411		}
1412
1413	<	private TreeMap.Entry<K,V> subceiling(K key) {
1414	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1183	<	getCeilingEntry(fromKey) : getCeilingEntry(key);
1184	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1185	<	return null;
1186	<	return e;
1413	>	public final Map.Entry<K,V> lowerEntry(K key) {
1414	>	return exportEntry(subLower(key));
1415		}
1416
1417	<	public Map.Entry<K,V> ceilingEntry(K key) {
1418	<	TreeMap.Entry<K,V> e = subceiling(key);
1191	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1417	>	public final K lowerKey(K key) {
1418	>	return keyOrNull(subLower(key));
1419		}
1420
1421	<	public K ceilingKey(K key) {
1422	<	TreeMap.Entry<K,V> e = subceiling(key);
1196	<	return e == null? null : e.key;
1421	>	public final K firstKey() {
1422	>	return key(subLowest());
1423		}
1424
1425	<
1426	<	private TreeMap.Entry<K,V> subhigher(K key) {
1201	<	TreeMap.Entry<K,V> e = (!fromStart && compare(key, fromKey) < 0)?
1202	<	getCeilingEntry(fromKey) : getHigherEntry(key);
1203	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1204	<	return null;
1205	<	return e;
1425	>	public final K lastKey() {
1426	>	return key(subHighest());
1427		}
1428
1429	<	public Map.Entry<K,V> higherEntry(K key) {
1430	<	TreeMap.Entry<K,V> e = subhigher(key);
1210	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1429	>	public final Map.Entry<K,V> firstEntry() {
1430	>	return exportEntry(subLowest());
1431		}
1432
1433	<	public K higherKey(K key) {
1434	<	TreeMap.Entry<K,V> e = subhigher(key);
1215	<	return e == null? null : e.key;
1433	>	public final Map.Entry<K,V> lastEntry() {
1434	>	return exportEntry(subHighest());
1435		}
1436
1437	<	private TreeMap.Entry<K,V> subfloor(K key) {
1438	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1439	<	getLowerEntry(toKey) : getFloorEntry(key);
1440	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1441	<	return null;
1442	<	return e;
1437	>	public final Map.Entry<K,V> pollFirstEntry() {
1438	>	TreeMap.Entry<K,V> e = subLowest();
1439	>	Map.Entry<K,V> result = exportEntry(e);
1440	>	if (e != null)
1441	>	m.deleteEntry(e);
1442	>	return result;
1443		}
1444
1445	<	public Map.Entry<K,V> floorEntry(K key) {
1446	<	TreeMap.Entry<K,V> e = subfloor(key);
1447	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1445	>	public final Map.Entry<K,V> pollLastEntry() {
1446	>	TreeMap.Entry<K,V> e = subHighest();
1447	>	Map.Entry<K,V> result = exportEntry(e);
1448	>	if (e != null)
1449	>	m.deleteEntry(e);
1450	>	return result;
1451		}
1452
1453	<	public K floorKey(K key) {
1454	<	TreeMap.Entry<K,V> e = subfloor(key);
1455	<	return e == null? null : e.key;
1453	>	// Views
1454	>	transient NavigableMap<K,V> descendingMapView = null;
1455	>	transient EntrySetView entrySetView = null;
1456	>	transient KeySet<K> navigableKeySetView = null;
1457	>
1458	>	public final NavigableSet<K> navigableKeySet() {
1459	>	KeySet<K> nksv = navigableKeySetView;
1460	>	return (nksv != null) ? nksv :
1461	>	(navigableKeySetView = new TreeMap.KeySet(this));
1462		}
1463
1464	<	private TreeMap.Entry<K,V> sublower(K key) {
1465	<	TreeMap.Entry<K,V> e = (!toEnd && compare(key, toKey) >= 0)?
1238	<	getLowerEntry(toKey) :  getLowerEntry(key);
1239	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1240	<	return null;
1241	<	return e;
1464	>	public final Set<K> keySet() {
1465	>	return navigableKeySet();
1466		}
1467
1468	<	public Map.Entry<K,V> lowerEntry(K key) {
1469	<	TreeMap.Entry<K,V> e = sublower(key);
1246	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1468	>	public NavigableSet<K> descendingKeySet() {
1469	>	return descendingMap().navigableKeySet();
1470		}
1471
1472	<	public K lowerKey(K key) {
1473	<	TreeMap.Entry<K,V> e = sublower(key);
1251	<	return e == null? null : e.key;
1472	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1473	>	return subMap(fromKey, true, toKey, false);
1474		}
1475
1476	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1476	>	public final SortedMap<K,V> headMap(K toKey) {
1477	>	return headMap(toKey, false);
1478	>	}
1479
1480	<	public Set<Map.Entry<K,V>> entrySet() {
1481	<	Set<Map.Entry<K,V>> es = entrySet;
1258	<	return (es != null)? es : (entrySet = new EntrySetView());
1480	>	public final SortedMap<K,V> tailMap(K fromKey) {
1481	>	return tailMap(fromKey, true);
1482		}
1483
1484	<	private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1484	>	// View classes
1485	>
1486	>	abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1487		private transient int size = -1, sizeModCount;
1488
1489		public int size() {
1490	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1491	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1490	>	if (fromStart && toEnd)
1491	>	return m.size();
1492	>	if (size == -1 || sizeModCount != m.modCount) {
1493	>	sizeModCount = m.modCount;
1494	>	size = 0;
1495		Iterator i = iterator();
1496		while (i.hasNext()) {
1497		size++;
#	Line 1274 | Line 1502 | public class TreeMap<K,V>
1502		}
1503
1504		public boolean isEmpty() {
1505	<	return !iterator().hasNext();
1505	>	TreeMap.Entry<K,V> n = absLowest();
1506	>	return n == null || tooHigh(n.key);
1507		}
1508
1509		public boolean contains(Object o) {
#	Line 1284 | Line 1513 | public class TreeMap<K,V>
1513		K key = entry.getKey();
1514		if (!inRange(key))
1515		return false;
1516	<	TreeMap.Entry node = getEntry(key);
1516	>	TreeMap.Entry node = m.getEntry(key);
1517		return node != null &&
1518	<	valEquals(node.getValue(), entry.getValue());
1518	>	valEquals(node.getValue(), entry.getValue());
1519		}
1520
1521		public boolean remove(Object o) {
#	Line 1296 | Line 1525 | public class TreeMap<K,V>
1525		K key = entry.getKey();
1526		if (!inRange(key))
1527		return false;
1528	<	TreeMap.Entry<K,V> node = getEntry(key);
1528	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1529		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1530	<	deleteEntry(node);
1530	>	m.deleteEntry(node);
1531		return true;
1532		}
1533		return false;
1534		}
1306	–
1307	–	public Iterator<Map.Entry<K,V>> iterator() {
1308	–	return new SubMapEntryIterator(
1309	–	(fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
1310	–	(toEnd     ? null            : getCeilingEntry(toKey)));
1311	–	}
1535		}
1536
1537	<	private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1538	<	private transient Set<K> descendingKeySetView = null;
1539	<
1540	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
1541	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
1542	<	return (es != null) ? es :
1543	<	(descendingEntrySetView = new DescendingEntrySetView());
1544	<	}
1322	<
1323	<	public Set<K> descendingKeySet() {
1324	<	Set<K> ks = descendingKeySetView;
1325	<	return (ks != null) ? ks :
1326	<	(descendingKeySetView = new DescendingKeySetView());
1327	<	}
1537	>	/**
1538	>	* Iterators for SubMaps
1539	>	*/
1540	>	abstract class SubMapIterator<T> implements Iterator<T> {
1541	>	TreeMap.Entry<K,V> lastReturned;
1542	>	TreeMap.Entry<K,V> next;
1543	>	final K fenceKey;
1544	>	int expectedModCount;
1545
1546	<	private class DescendingEntrySetView extends EntrySetView {
1547	<	public Iterator<Map.Entry<K,V>> iterator() {
1548	<	return new DescendingSubMapEntryIterator
1549	<	((toEnd     ? getLastEntry()  : getLowerEntry(toKey)),
1550	<	(fromStart ? null            : getLowerEntry(fromKey)));
1546	>	SubMapIterator(TreeMap.Entry<K,V> first,
1547	>	TreeMap.Entry<K,V> fence) {
1548	>	expectedModCount = m.modCount;
1549	>	lastReturned = null;
1550	>	next = first;
1551	>	fenceKey = fence == null ? null : fence.key;
1552		}
1335	–	}
1553
1554	<	private class DescendingKeySetView extends AbstractSet<K> {
1555	<	public Iterator<K> iterator() {
1556	<	return new Iterator<K>() {
1340	<	private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1554	>	public final boolean hasNext() {
1555	>	return next != null && next.key != fenceKey;
1556	>	}
1557
1558	<	public boolean hasNext() { return i.hasNext(); }
1559	<	public K next() { return i.next().getKey(); }
1560	<	public void remove() { i.remove(); }
1561	<	};
1558	>	final TreeMap.Entry<K,V> nextEntry() {
1559	>	TreeMap.Entry<K,V> e = lastReturned = next;
1560	>	if (e == null || e.key == fenceKey)
1561	>	throw new NoSuchElementException();
1562	>	if (m.modCount != expectedModCount)
1563	>	throw new ConcurrentModificationException();
1564	>	next = successor(e);
1565	>	return e;
1566		}
1567
1568	<	public int size() {
1569	<	return SubMap.this.size();
1568	>	final TreeMap.Entry<K,V> prevEntry() {
1569	>	TreeMap.Entry<K,V> e = lastReturned = next;
1570	>	if (e == null || e.key == fenceKey)
1571	>	throw new NoSuchElementException();
1572	>	if (m.modCount != expectedModCount)
1573	>	throw new ConcurrentModificationException();
1574	>	next = predecessor(e);
1575	>	return e;
1576		}
1577
1578	<	public boolean contains(Object k) {
1579	<	return SubMap.this.containsKey(k);
1578	>	public void remove() {
1579	>	if (lastReturned == null)
1580	>	throw new IllegalStateException();
1581	>	if (m.modCount != expectedModCount)
1582	>	throw new ConcurrentModificationException();
1583	>	if (lastReturned.left != null && lastReturned.right != null)
1584	>	next = lastReturned;
1585	>	m.deleteEntry(lastReturned);
1586	>	expectedModCount++;
1587	>	lastReturned = null;
1588		}
1589		}
1590
1591	<	public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
1592	<	if (!inRange2(fromKey))
1593	<	throw new IllegalArgumentException("fromKey out of range");
1594	<	if (!inRange2(toKey))
1595	<	throw new IllegalArgumentException("toKey out of range");
1596	<	return new SubMap(fromKey, toKey);
1591	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1592	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1593	>	TreeMap.Entry<K,V> fence) {
1594	>	super(first, fence);
1595	>	}
1596	>	public Map.Entry<K,V> next() {
1597	>	return nextEntry();
1598	>	}
1599		}
1600
1601	<	public NavigableMap<K,V> navigableHeadMap(K toKey) {
1602	<	if (!inRange2(toKey))
1603	<	throw new IllegalArgumentException("toKey out of range");
1604	<	return new SubMap(fromStart, fromKey, false, toKey);
1601	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1602	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1603	>	TreeMap.Entry<K,V> fence) {
1604	>	super(first, fence);
1605	>	}
1606	>	public K next() {
1607	>	return nextEntry().key;
1608	>	}
1609		}
1610
1611	<	public NavigableMap<K,V> navigableTailMap(K fromKey) {
1612	<	if (!inRange2(fromKey))
1613	<	throw new IllegalArgumentException("fromKey out of range");
1614	<	return new SubMap(false, fromKey, toEnd, toKey);
1615	<	}
1611	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1612	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1613	>	TreeMap.Entry<K,V> fence) {
1614	>	super(last, fence);
1615	>	}
1616
1617	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1618	<	return navigableSubMap(fromKey, toKey);
1617	>	public Map.Entry<K,V> next() {
1618	>	return prevEntry();
1619	>	}
1620		}
1621
1622	<	public SortedMap<K,V> headMap(K toKey) {
1623	<	return navigableHeadMap(toKey);
1622	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1623	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1624	>	TreeMap.Entry<K,V> fence) {
1625	>	super(last, fence);
1626	>	}
1627	>	public K next() {
1628	>	return prevEntry().key;
1629	>	}
1630		}
1631	+	}
1632
1633	<	public SortedMap<K,V> tailMap(K fromKey) {
1634	<	return navigableTailMap(fromKey);
1387	<	}
1633	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1634	>	private static final long serialVersionUID = 912986545866124060L;
1635
1636	<	private boolean inRange(Object key) {
1637	<	return (fromStart || compare(key, fromKey) >= 0) &&
1638	<	(toEnd     || compare(key, toKey)   <  0);
1636	>	AscendingSubMap(TreeMap<K,V> m,
1637	>	boolean fromStart, K lo, boolean loInclusive,
1638	>	boolean toEnd, K hi, boolean hiInclusive) {
1639	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1640		}
1641
1642	<	// This form allows the high endpoint (as well as all legit keys)
1643	<	private boolean inRange2(Object key) {
1396	<	return (fromStart || compare(key, fromKey) >= 0) &&
1397	<	(toEnd     || compare(key, toKey)   <= 0);
1642	>	public Comparator<? super K> comparator() {
1643	>	return m.comparator();
1644		}
1399	–	}
1400	–
1401	–	/**
1402	–	* TreeMap Iterator.
1403	–	*/
1404	–	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1405	–	int expectedModCount = TreeMap.this.modCount;
1406	–	Entry<K,V> lastReturned = null;
1407	–	Entry<K,V> next;
1645
1646	<	PrivateEntryIterator(Entry<K,V> first) {
1647	<	next = first;
1646	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1647	>	K toKey, boolean toInclusive) {
1648	>	if (!inRange(fromKey, fromInclusive))
1649	>	throw new IllegalArgumentException("fromKey out of range");
1650	>	if (!inRange(toKey, toInclusive))
1651	>	throw new IllegalArgumentException("toKey out of range");
1652	>	return new AscendingSubMap(m,
1653	>	false, fromKey, fromInclusive,
1654	>	false, toKey,   toInclusive);
1655		}
1656
1657	<	public boolean hasNext() {
1658	<	return next != null;
1657	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1658	>	if (!inClosedRange(toKey))
1659	>	throw new IllegalArgumentException("toKey out of range");
1660	>	return new AscendingSubMap(m,
1661	>	fromStart, lo,    loInclusive,
1662	>	false,     toKey, inclusive);
1663		}
1664
1665	<	Entry<K,V> nextEntry() {
1666	<	if (next == null)
1667	<	throw new NoSuchElementException();
1668	<	if (modCount != expectedModCount)
1669	<	throw new ConcurrentModificationException();
1670	<	lastReturned = next;
1423	<	next = successor(next);
1424	<	return lastReturned;
1665	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1666	>	if (!inRange(fromKey, inclusive))
1667	>	throw new IllegalArgumentException("fromKey out of range");
1668	>	return new AscendingSubMap(m,
1669	>	false, fromKey, inclusive,
1670	>	toEnd, hi,      hiInclusive);
1671		}
1672
1673	<	public void remove() {
1674	<	if (lastReturned == null)
1675	<	throw new IllegalStateException();
1676	<	if (modCount != expectedModCount)
1677	<	throw new ConcurrentModificationException();
1678	<	if (lastReturned.left != null && lastReturned.right != null)
1679	<	next = lastReturned;
1434	<	deleteEntry(lastReturned);
1435	<	expectedModCount++;
1436	<	lastReturned = null;
1673	>	public NavigableMap<K,V> descendingMap() {
1674	>	NavigableMap<K,V> mv = descendingMapView;
1675	>	return (mv != null) ? mv :
1676	>	(descendingMapView =
1677	>	new DescendingSubMap(m,
1678	>	fromStart, lo, loInclusive,
1679	>	toEnd,     hi, hiInclusive));
1680		}
1438	–	}
1681
1682	<	class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1683	<	EntryIterator(Entry<K,V> first) {
1442	<	super(first);
1682	>	Iterator<K> keyIterator() {
1683	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1684		}
1444	–	public Map.Entry<K,V> next() {
1445	–	return nextEntry();
1446	–	}
1447	–	}
1685
1686	<	class KeyIterator extends PrivateEntryIterator<K> {
1687	<	KeyIterator(Entry<K,V> first) {
1451	<	super(first);
1452	<	}
1453	<	public K next() {
1454	<	return nextEntry().key;
1686	>	Iterator<K> descendingKeyIterator() {
1687	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1688		}
1456	–	}
1689
1690	<	class ValueIterator extends PrivateEntryIterator<V> {
1691	<	ValueIterator(Entry<K,V> first) {
1692	<	super(first);
1690	>	final class AscendingEntrySetView extends EntrySetView {
1691	>	public Iterator<Map.Entry<K,V>> iterator() {
1692	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1693	>	}
1694		}
1695	<	public V next() {
1696	<	return nextEntry().value;
1695	>
1696	>	public Set<Map.Entry<K,V>> entrySet() {
1697	>	EntrySetView es = entrySetView;
1698	>	return (es != null) ? es : new AscendingEntrySetView();
1699		}
1465	–	}
1700
1701	<	class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1702	<	private final K firstExcludedKey;
1701	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1702	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1703	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1704	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1705	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1706	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1707	>	}
1708
1709	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1710	<	super(first);
1711	<	firstExcludedKey = (firstExcluded == null
1712	<	? null
1713	<	: firstExcluded.key);
1709	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1710	>	private static final long serialVersionUID = 912986545866120460L;
1711	>	DescendingSubMap(TreeMap<K,V> m,
1712	>	boolean fromStart, K lo, boolean loInclusive,
1713	>	boolean toEnd, K hi, boolean hiInclusive) {
1714	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1715		}
1716
1717	<	public boolean hasNext() {
1718	<	return next != null && next.key != firstExcludedKey;
1479	<	}
1717	>	private final Comparator<? super K> reverseComparator =
1718	>	Collections.reverseOrder(m.comparator);
1719
1720	<	public Map.Entry<K,V> next() {
1721	<	if (next == null || next.key == firstExcludedKey)
1483	<	throw new NoSuchElementException();
1484	<	return nextEntry();
1720	>	public Comparator<? super K> comparator() {
1721	>	return reverseComparator;
1722		}
1486	–	}
1723
1724	<	/**
1725	<	* Base for Descending Iterators.
1726	<	*/
1727	<	abstract class DescendingPrivateEntryIterator<T> extends PrivateEntryIterator<T> {
1728	<	DescendingPrivateEntryIterator(Entry<K,V> first) {
1729	<	super(first);
1724	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1725	>	K toKey, boolean toInclusive) {
1726	>	if (!inRange(fromKey, fromInclusive))
1727	>	throw new IllegalArgumentException("fromKey out of range");
1728	>	if (!inRange(toKey, toInclusive))
1729	>	throw new IllegalArgumentException("toKey out of range");
1730	>	return new DescendingSubMap(m,
1731	>	false, toKey,   toInclusive,
1732	>	false, fromKey, fromInclusive);
1733		}
1734
1735	<	Entry<K,V> nextEntry() {
1736	<	if (next == null)
1737	<	throw new NoSuchElementException();
1738	<	if (modCount != expectedModCount)
1739	<	throw new ConcurrentModificationException();
1740	<	lastReturned = next;
1502	<	next = predecessor(next);
1503	<	return lastReturned;
1735	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1736	>	if (!inRange(toKey, inclusive))
1737	>	throw new IllegalArgumentException("toKey out of range");
1738	>	return new DescendingSubMap(m,
1739	>	false, toKey, inclusive,
1740	>	toEnd, hi,    hiInclusive);
1741		}
1505	–	}
1742
1743	<	class DescendingEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1744	<	DescendingEntryIterator(Entry<K,V> first) {
1745	<	super(first);
1746	<	}
1747	<	public Map.Entry<K,V> next() {
1748	<	return nextEntry();
1743	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1744	>	if (!inRange(fromKey, inclusive))
1745	>	throw new IllegalArgumentException("fromKey out of range");
1746	>	return new DescendingSubMap(m,
1747	>	fromStart, lo, loInclusive,
1748	>	false, fromKey, inclusive);
1749		}
1514	–	}
1750
1751	<	class DescendingKeyIterator extends DescendingPrivateEntryIterator<K> {
1752	<	DescendingKeyIterator(Entry<K,V> first) {
1753	<	super(first);
1754	<	}
1755	<	public K next() {
1756	<	return nextEntry().key;
1751	>	public NavigableMap<K,V> descendingMap() {
1752	>	NavigableMap<K,V> mv = descendingMapView;
1753	>	return (mv != null) ? mv :
1754	>	(descendingMapView =
1755	>	new AscendingSubMap(m,
1756	>	fromStart, lo, loInclusive,
1757	>	toEnd,     hi, hiInclusive));
1758		}
1523	–	}
1524	–
1759
1760	<	class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator<Map.Entry<K,V>> {
1761	<	private final K lastExcludedKey;
1760	>	Iterator<K> keyIterator() {
1761	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1762	>	}
1763
1764	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1765	<	super(last);
1531	<	lastExcludedKey = (lastExcluded == null
1532	<	? null
1533	<	: lastExcluded.key);
1764	>	Iterator<K> descendingKeyIterator() {
1765	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1766		}
1767
1768	<	public boolean hasNext() {
1769	<	return next != null && next.key != lastExcludedKey;
1768	>	final class DescendingEntrySetView extends EntrySetView {
1769	>	public Iterator<Map.Entry<K,V>> iterator() {
1770	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1771	>	}
1772		}
1773
1774	<	public Map.Entry<K,V> next() {
1775	<	if (next == null || next.key == lastExcludedKey)
1776	<	throw new NoSuchElementException();
1543	<	return nextEntry();
1774	>	public Set<Map.Entry<K,V>> entrySet() {
1775	>	EntrySetView es = entrySetView;
1776	>	return (es != null) ? es : new DescendingEntrySetView();
1777		}
1778
1779	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1780	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1781	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1782	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1783	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1784	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1785		}
1786
1787		/**
1788	<	* Compares two keys using the correct comparison method for this TreeMap.
1788	>	* This class exists solely for the sake of serialization
1789	>	* compatibility with previous releases of TreeMap that did not
1790	>	* support NavigableMap.  It translates an old-version SubMap into
1791	>	* a new-version AscendingSubMap. This class is never otherwise
1792	>	* used.
1793		*/
1794	<	private int compare(Object k1, Object k2) {
1795	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1796	<	: comparator.compare((K)k1, (K)k2);
1794	>	private class SubMap extends AbstractMap<K,V>
1795	>	implements SortedMap<K,V>, java.io.Serializable {
1796	>	private static final long serialVersionUID = -6520786458950516097L;
1797	>	private boolean fromStart = false, toEnd = false;
1798	>	private K fromKey, toKey;
1799	>	private Object readResolve() {
1800	>	return new AscendingSubMap(TreeMap.this,
1801	>	fromStart, fromKey, true,
1802	>	toEnd, toKey, false);
1803	>	}
1804	>	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1805	>	public K lastKey() { throw new InternalError(); }
1806	>	public K firstKey() { throw new InternalError(); }
1807	>	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1808	>	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1809	>	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1810	>	public Comparator<? super K> comparator() { throw new InternalError(); }
1811		}
1812
1813	<	/**
1814	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1558	<	* that it copes with <tt>null</tt> o1 properly.
1559	<	*/
1560	<	private static boolean valEquals(Object o1, Object o2) {
1561	<	return (o1==null ? o2==null : o1.equals(o2));
1562	<	}
1813	>
1814	>	// Red-black mechanics
1815
1816		private static final boolean RED   = false;
1817		private static final boolean BLACK = true;
#	Line 1569 | Line 1821 | public class TreeMap<K,V>
1821		* user (see Map.Entry).
1822		*/
1823
1824	<	static class Entry<K,V> implements Map.Entry<K,V> {
1824	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1825		K key;
1826		V value;
1827		Entry<K,V> left = null;
#	Line 1641 | Line 1893 | public class TreeMap<K,V>
1893		* Returns the first Entry in the TreeMap (according to the TreeMap's
1894		* key-sort function).  Returns null if the TreeMap is empty.
1895		*/
1896	<	private Entry<K,V> getFirstEntry() {
1896	>	final Entry<K,V> getFirstEntry() {
1897		Entry<K,V> p = root;
1898		if (p != null)
1899		while (p.left != null)
#	Line 1653 | Line 1905 | public class TreeMap<K,V>
1905		* Returns the last Entry in the TreeMap (according to the TreeMap's
1906		* key-sort function).  Returns null if the TreeMap is empty.
1907		*/
1908	<	private Entry<K,V> getLastEntry() {
1908	>	final Entry<K,V> getLastEntry() {
1909		Entry<K,V> p = root;
1910		if (p != null)
1911		while (p.right != null)
#	Line 1664 | Line 1916 | public class TreeMap<K,V>
1916		/**
1917		* Returns the successor of the specified Entry, or null if no such.
1918		*/
1919	<	private Entry<K,V> successor(Entry<K,V> t) {
1919	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1920		if (t == null)
1921		return null;
1922		else if (t.right != null) {
#	Line 1686 | Line 1938 | public class TreeMap<K,V>
1938		/**
1939		* Returns the predecessor of the specified Entry, or null if no such.
1940		*/
1941	<	private Entry<K,V> predecessor(Entry<K,V> t) {
1941	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1942		if (t == null)
1943		return null;
1944		else if (t.left != null) {
#	Line 1736 | Line 1988 | public class TreeMap<K,V>
1988		return (p == null) ? null: p.right;
1989		}
1990
1991	<	/** From CLR **/
1991	>	/** From CLR */
1992		private void rotateLeft(Entry<K,V> p) {
1993	<	Entry<K,V> r = p.right;
1994	<	p.right = r.left;
1995	<	if (r.left != null)
1996	<	r.left.parent = p;
1997	<	r.parent = p.parent;
1998	<	if (p.parent == null)
1999	<	root = r;
2000	<	else if (p.parent.left == p)
2001	<	p.parent.left = r;
2002	<	else
2003	<	p.parent.right = r;
2004	<	r.left = p;
2005	<	p.parent = r;
1993	>	if (p != null) {
1994	>	Entry<K,V> r = p.right;
1995	>	p.right = r.left;
1996	>	if (r.left != null)
1997	>	r.left.parent = p;
1998	>	r.parent = p.parent;
1999	>	if (p.parent == null)
2000	>	root = r;
2001	>	else if (p.parent.left == p)
2002	>	p.parent.left = r;
2003	>	else
2004	>	p.parent.right = r;
2005	>	r.left = p;
2006	>	p.parent = r;
2007	>	}
2008		}
2009
2010	<	/** From CLR **/
2010	>	/** From CLR */
2011		private void rotateRight(Entry<K,V> p) {
2012	<	Entry<K,V> l = p.left;
2013	<	p.left = l.right;
2014	<	if (l.right != null) l.right.parent = p;
2015	<	l.parent = p.parent;
2016	<	if (p.parent == null)
2017	<	root = l;
2018	<	else if (p.parent.right == p)
2019	<	p.parent.right = l;
2020	<	else p.parent.left = l;
2021	<	l.right = p;
2022	<	p.parent = l;
2012	>	if (p != null) {
2013	>	Entry<K,V> l = p.left;
2014	>	p.left = l.right;
2015	>	if (l.right != null) l.right.parent = p;
2016	>	l.parent = p.parent;
2017	>	if (p.parent == null)
2018	>	root = l;
2019	>	else if (p.parent.right == p)
2020	>	p.parent.right = l;
2021	>	else p.parent.left = l;
2022	>	l.right = p;
2023	>	p.parent = l;
2024	>	}
2025		}
2026
2027	<
1772	<	/** From CLR **/
2027	>	/** From CLR */
2028		private void fixAfterInsertion(Entry<K,V> x) {
2029		x.color = RED;
2030
#	Line 1788 | Line 2043 | public class TreeMap<K,V>
2043		}
2044		setColor(parentOf(x), BLACK);
2045		setColor(parentOf(parentOf(x)), RED);
2046	<	if (parentOf(parentOf(x)) != null)
1792	<	rotateRight(parentOf(parentOf(x)));
2046	>	rotateRight(parentOf(parentOf(x)));
2047		}
2048		} else {
2049		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 1803 | Line 2057 | public class TreeMap<K,V>
2057		x = parentOf(x);
2058		rotateRight(x);
2059		}
2060	<	setColor(parentOf(x),  BLACK);
2060	>	setColor(parentOf(x), BLACK);
2061		setColor(parentOf(parentOf(x)), RED);
2062	<	if (parentOf(parentOf(x)) != null)
1809	<	rotateLeft(parentOf(parentOf(x)));
2062	>	rotateLeft(parentOf(parentOf(x)));
2063		}
2064		}
2065		}
#	Line 1816 | Line 2069 | public class TreeMap<K,V>
2069		/**
2070		* Delete node p, and then rebalance the tree.
2071		*/
1819	–
2072		private void deleteEntry(Entry<K,V> p) {
2073	<	decrementSize();
2073	>	modCount++;
2074	>	size--;
2075
2076		// If strictly internal, copy successor's element to p and then make p
2077		// point to successor.
#	Line 1864 | Line 2117 | public class TreeMap<K,V>
2117		}
2118		}
2119
2120	<	/** From CLR **/
2120	>	/** From CLR */
2121		private void fixAfterDeletion(Entry<K,V> x) {
2122		while (x != root && colorOf(x) == BLACK) {
2123		if (x == leftOf(parentOf(x))) {
#	Line 1879 | Line 2132 | public class TreeMap<K,V>
2132
2133		if (colorOf(leftOf(sib))  == BLACK &&
2134		colorOf(rightOf(sib)) == BLACK) {
2135	<	setColor(sib,  RED);
2135	>	setColor(sib, RED);
2136		x = parentOf(x);
2137		} else {
2138		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 1906 | Line 2159 | public class TreeMap<K,V>
2159
2160		if (colorOf(rightOf(sib)) == BLACK &&
2161		colorOf(leftOf(sib)) == BLACK) {
2162	<	setColor(sib,  RED);
2162	>	setColor(sib, RED);
2163		x = parentOf(x);
2164		} else {
2165		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 1957 | Line 2210 | public class TreeMap<K,V>
2210		}
2211		}
2212
1960	–
1961	–
2213		/**
2214		* Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2215		* deserialize it).
#	Line 1974 | Line 2225 | public class TreeMap<K,V>
2225		buildFromSorted(size, null, s, null);
2226		}
2227
2228	<	/** Intended to be called only from TreeSet.readObject **/
2228	>	/** Intended to be called only from TreeSet.readObject */
2229		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2230		throws java.io.IOException, ClassNotFoundException {
2231		buildFromSorted(size, null, s, defaultVal);
2232		}
2233
2234	<	/** Intended to be called only from TreeSet.addAll **/
2234	>	/** Intended to be called only from TreeSet.addAll */
2235		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2236		try {
2237		buildFromSorted(set.size(), set.iterator(), null, defaultVal);

Diff Legend

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