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.28 by dl, Wed Apr 19 15:07:14 2006 UTC vs.
Revision 1.46 by jsr166, Sun May 18 23:59:57 2008 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 2006 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;
#	Line 68 | Line 86 | package java.util;
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
93		* @param <V> the type of mapped values
94		*
95		* @author  Josh Bloch and Doug Lea
78	–	* @version %I%, %G%
96		* @see Map
97		* @see HashMap
98		* @see Hashtable
#	Line 95 | Line 112 | public class TreeMap<K,V>
112		*
113		* @serial
114		*/
115	<	private Comparator<? super K> comparator = null;
115	>	private final Comparator<? super K> comparator;
116
117		private transient Entry<K,V> root = null;
118
#	Line 110 | Line 127 | public class TreeMap<K,V>
127		private transient int modCount = 0;
128
129		/**
113	–	* A sentinel to indicate that an endpoint of a submap is not bounded.
114	–	* It is used to generate head maps, tail maps, and descending views
115	–	* of the entire backing map. The sentinel must be serializable,
116	–	* requiring a little class to express.
117	–	*/
118	–	private static class Unbounded implements java.io.Serializable {}
119	–	private static final Unbounded UNBOUNDED = new Unbounded();
120	–
121	–	private void incrementSize()   { modCount++; size++; }
122	–	private void decrementSize()   { modCount++; size--; }
123	–
124	–	/**
130		* Constructs a new, empty tree map, using the natural ordering of its
131		* keys.  All keys inserted into the map must implement the {@link
132		* Comparable} interface.  Furthermore, all such keys must be
#	Line 134 | Line 139 | public class TreeMap<K,V>
139		* <tt>ClassCastException</tt>.
140		*/
141		public TreeMap() {
142	+	comparator = null;
143		}
144
145		/**
#	Line 169 | Line 175 | public class TreeMap<K,V>
175		* @throws NullPointerException if the specified map is null
176		*/
177		public TreeMap(Map<? extends K, ? extends V> m) {
178	+	comparator = null;
179		putAll(m);
180		}
181
#	Line 229 | Line 236 | public class TreeMap<K,V>
236		*
237		* @param value value whose presence in this map is to be tested
238		* @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
239	<	*         <tt>false</tt> otherwise
239	>	*         <tt>false</tt> otherwise
240		* @since 1.2
241		*/
242		public boolean containsValue(Object value) {
243	<	return (root==null ? false :
244	<	(value==null ? valueSearchNull(root)
245	<	: valueSearchNonNull(root, value)));
246	<	}
240	<
241	<	private boolean valueSearchNull(Entry n) {
242	<	if (n.value == null)
243	<	return true;
244	<
245	<	// Check left and right subtrees for value
246	<	return (n.left  != null && valueSearchNull(n.left)) ||
247	<	(n.right != null && valueSearchNull(n.right));
248	<	}
249	<
250	<	private boolean valueSearchNonNull(Entry n, Object value) {
251	<	// Check this node for the value
252	<	if (value.equals(n.value))
253	<	return true;
254	<
255	<	// Check left and right subtrees for value
256	<	return (n.left  != null && valueSearchNonNull(n.left, value)) ||
257	<	(n.right != null && valueSearchNonNull(n.right, value));
243	>	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
244	>	if (valEquals(value, e.value))
245	>	return true;
246	>	return false;
247		}
248
249		/**
#	Line 319 | Line 308 | public class TreeMap<K,V>
308		if (size==0 && mapSize!=0 && map instanceof SortedMap) {
309		Comparator c = ((SortedMap)map).comparator();
310		if (c == comparator || (c != null && c.equals(comparator))) {
311	<	++modCount;
312	<	try {
313	<	buildFromSorted(mapSize, map.entrySet().iterator(),
314	<	null, null);
315	<	} catch (java.io.IOException cannotHappen) {
316	<	} catch (ClassNotFoundException cannotHappen) {
317	<	}
318	<	return;
311	>	++modCount;
312	>	try {
313	>	buildFromSorted(mapSize, map.entrySet().iterator(),
314	>	null, null);
315	>	} catch (java.io.IOException cannotHappen) {
316	>	} catch (ClassNotFoundException cannotHappen) {
317	>	}
318	>	return;
319		}
320		}
321		super.putAll(map);
#	Line 344 | Line 333 | public class TreeMap<K,V>
333		*         and this map uses natural ordering, or its comparator
334		*         does not permit null keys
335		*/
336	<	private Entry<K,V> getEntry(Object key) {
336	>	final Entry<K,V> getEntry(Object key) {
337		// Offload comparator-based version for sake of performance
338		if (comparator != null)
339		return getEntryUsingComparator(key);
340		if (key == null)
341		throw new NullPointerException();
342	<	Comparable<? super K> k = (Comparable<? super K>) key;
342	>	Comparable<? super K> k = (Comparable<? super K>) key;
343		Entry<K,V> p = root;
344		while (p != null) {
345		int cmp = k.compareTo(p.key);
#	Line 370 | Line 359 | public class TreeMap<K,V>
359		* that are less dependent on comparator performance, but is
360		* worthwhile here.)
361		*/
362	<	private Entry<K,V> getEntryUsingComparator(Object key) {
363	<	K k = (K) key;
362	>	final Entry<K,V> getEntryUsingComparator(Object key) {
363	>	K k = (K) key;
364		Comparator<? super K> cpr = comparator;
365	<	Entry<K,V> p = root;
366	<	while (p != null) {
367	<	int cmp = cpr.compare(k, p.key);
368	<	if (cmp < 0)
369	<	p = p.left;
370	<	else if (cmp > 0)
371	<	p = p.right;
372	<	else
373	<	return p;
365	>	if (cpr != null) {
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;
375	>	}
376		}
377		return null;
378		}
#	Line 392 | Line 383 | public class TreeMap<K,V>
383		* key; if no such entry exists (i.e., the greatest key in the Tree is less
384		* than the specified key), returns <tt>null</tt>.
385		*/
386	<	private Entry<K,V> getCeilingEntry(K key) {
386	>	final Entry<K,V> getCeilingEntry(K key) {
387		Entry<K,V> p = root;
388	<	if (p==null)
398	<	return null;
399	<
400	<	while (true) {
388	>	while (p != null) {
389		int cmp = compare(key, p.key);
390		if (cmp < 0) {
391		if (p.left != null)
#	Line 419 | Line 407 | public class TreeMap<K,V>
407		} else
408		return p;
409		}
410	+	return null;
411		}
412
413		/**
#	Line 426 | Line 415 | public class TreeMap<K,V>
415		* exists, returns the entry for the greatest key less than the specified
416		* key; if no such entry exists, returns <tt>null</tt>.
417		*/
418	<	private Entry<K,V> getFloorEntry(K key) {
418	>	final Entry<K,V> getFloorEntry(K key) {
419		Entry<K,V> p = root;
420	<	if (p==null)
432	<	return null;
433	<
434	<	while (true) {
420	>	while (p != null) {
421		int cmp = compare(key, p.key);
422		if (cmp > 0) {
423		if (p.right != null)
#	Line 454 | Line 440 | public class TreeMap<K,V>
440		return p;
441
442		}
443	+	return null;
444		}
445
446		/**
#	Line 462 | Line 449 | public class TreeMap<K,V>
449		* key greater than the specified key; if no such entry exists
450		* returns <tt>null</tt>.
451		*/
452	<	private Entry<K,V> getHigherEntry(K key) {
452	>	final Entry<K,V> getHigherEntry(K key) {
453		Entry<K,V> p = root;
454	<	if (p==null)
468	<	return null;
469	<
470	<	while (true) {
454	>	while (p != null) {
455		int cmp = compare(key, p.key);
456		if (cmp < 0) {
457		if (p.left != null)
#	Line 488 | Line 472 | public class TreeMap<K,V>
472		}
473		}
474		}
475	+	return null;
476		}
477
478		/**
#	Line 495 | Line 480 | public class TreeMap<K,V>
480		* no such entry exists (i.e., the least key in the Tree is greater than
481		* the specified key), returns <tt>null</tt>.
482		*/
483	<	private Entry<K,V> getLowerEntry(K key) {
483	>	final Entry<K,V> getLowerEntry(K key) {
484		Entry<K,V> p = root;
485	<	if (p==null)
501	<	return null;
502	<
503	<	while (true) {
485	>	while (p != null) {
486		int cmp = compare(key, p.key);
487		if (cmp > 0) {
488		if (p.right != null)
#	Line 521 | Line 503 | public class TreeMap<K,V>
503		}
504		}
505		}
506	<	}
525	<
526	<	/**
527	<	* Returns the key corresponding to the specified Entry.
528	<	* @throws NoSuchElementException if the Entry is null
529	<	*/
530	<	private static <K> K key(Entry<K,?> e) {
531	<	if (e==null)
532	<	throw new NoSuchElementException();
533	<	return e.key;
506	>	return null;
507		}
508
509		/**
#	Line 553 | Line 526 | public class TreeMap<K,V>
526		*/
527		public V put(K key, V value) {
528		Entry<K,V> t = root;
556	–
529		if (t == null) {
530	<	// TBD
531	<	//             if (key == null) {
532	<	//                 if (comparator == null)
533	<	//                     throw new NullPointerException();
534	<	//                 comparator.compare(key, key);
563	<	//             }
564	<	incrementSize();
530	>	// TBD:
531	>	// 5045147: (coll) Adding null to an empty TreeSet should
532	>	// throw NullPointerException
533	>	//
534	>	// compare(key, key); // type check
535		root = new Entry<K,V>(key, value, null);
536	+	size = 1;
537	+	modCount++;
538		return null;
539		}
540	<
541	<	while (true) {
542	<	int cmp = compare(key, t.key);
543	<	if (cmp == 0) {
544	<	return t.setValue(value);
545	<	} else if (cmp < 0) {
546	<	if (t.left != null) {
540	>	int cmp;
541	>	Entry<K,V> parent;
542	>	// split comparator and comparable paths
543	>	Comparator<? super K> cpr = comparator;
544	>	if (cpr != null) {
545	>	do {
546	>	parent = t;
547	>	cmp = cpr.compare(key, t.key);
548	>	if (cmp < 0)
549		t = t.left;
550	<	} else {
577	<	incrementSize();
578	<	t.left = new Entry<K,V>(key, value, t);
579	<	fixAfterInsertion(t.left);
580	<	return null;
581	<	}
582	<	} else { // cmp > 0
583	<	if (t.right != null) {
550	>	else if (cmp > 0)
551		t = t.right;
552	<	} else {
553	<	incrementSize();
554	<	t.right = new Entry<K,V>(key, value, t);
555	<	fixAfterInsertion(t.right);
556	<	return null;
557	<	}
558	<	}
552	>	else
553	>	return t.setValue(value);
554	>	} while (t != null);
555	>	}
556	>	else {
557	>	if (key == null)
558	>	throw new NullPointerException();
559	>	Comparable<? super K> k = (Comparable<? super K>) key;
560	>	do {
561	>	parent = t;
562	>	cmp = k.compareTo(t.key);
563	>	if (cmp < 0)
564	>	t = t.left;
565	>	else if (cmp > 0)
566	>	t = t.right;
567	>	else
568	>	return t.setValue(value);
569	>	} while (t != null);
570		}
571	+	Entry<K,V> e = new Entry<K,V>(key, value, parent);
572	+	if (cmp < 0)
573	+	parent.left = e;
574	+	else
575	+	parent.right = e;
576	+	fixAfterInsertion(e);
577	+	size++;
578	+	modCount++;
579	+	return null;
580		}
581
582		/**
#	Line 664 | Line 651 | public class TreeMap<K,V>
651		* @since 1.6
652		*/
653		public Map.Entry<K,V> firstEntry() {
654	<	Entry<K,V> e = getFirstEntry();
668	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
654	>	return exportEntry(getFirstEntry());
655		}
656
657		/**
658		* @since 1.6
659		*/
660		public Map.Entry<K,V> lastEntry() {
661	<	Entry<K,V> e = getLastEntry();
676	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
661	>	return exportEntry(getLastEntry());
662		}
663
664		/**
#	Line 681 | Line 666 | public class TreeMap<K,V>
666		*/
667		public Map.Entry<K,V> pollFirstEntry() {
668		Entry<K,V> p = getFirstEntry();
669	<	if (p == null)
670	<	return null;
671	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
687	<	deleteEntry(p);
669	>	Map.Entry<K,V> result = exportEntry(p);
670	>	if (p != null)
671	>	deleteEntry(p);
672		return result;
673		}
674
#	Line 693 | Line 677 | public class TreeMap<K,V>
677		*/
678		public Map.Entry<K,V> pollLastEntry() {
679		Entry<K,V> p = getLastEntry();
680	<	if (p == null)
681	<	return null;
682	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
699	<	deleteEntry(p);
680	>	Map.Entry<K,V> result = exportEntry(p);
681	>	if (p != null)
682	>	deleteEntry(p);
683		return result;
684		}
685
#	Line 708 | Line 691 | public class TreeMap<K,V>
691		* @since 1.6
692		*/
693		public Map.Entry<K,V> lowerEntry(K key) {
694	<	Entry<K,V> e =  getLowerEntry(key);
712	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
694	>	return exportEntry(getLowerEntry(key));
695		}
696
697		/**
#	Line 720 | Line 702 | public class TreeMap<K,V>
702		* @since 1.6
703		*/
704		public K lowerKey(K key) {
705	<	Entry<K,V> e =  getLowerEntry(key);
724	<	return (e == null)? null : e.key;
705	>	return keyOrNull(getLowerEntry(key));
706		}
707
708		/**
#	Line 732 | Line 713 | public class TreeMap<K,V>
713		* @since 1.6
714		*/
715		public Map.Entry<K,V> floorEntry(K key) {
716	<	Entry<K,V> e = getFloorEntry(key);
736	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
716	>	return exportEntry(getFloorEntry(key));
717		}
718
719		/**
#	Line 744 | Line 724 | public class TreeMap<K,V>
724		* @since 1.6
725		*/
726		public K floorKey(K key) {
727	<	Entry<K,V> e = getFloorEntry(key);
748	<	return (e == null)? null : e.key;
727	>	return keyOrNull(getFloorEntry(key));
728		}
729
730		/**
#	Line 756 | Line 735 | public class TreeMap<K,V>
735		* @since 1.6
736		*/
737		public Map.Entry<K,V> ceilingEntry(K key) {
738	<	Entry<K,V> e = getCeilingEntry(key);
760	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
738	>	return exportEntry(getCeilingEntry(key));
739		}
740
741		/**
#	Line 768 | Line 746 | public class TreeMap<K,V>
746		* @since 1.6
747		*/
748		public K ceilingKey(K key) {
749	<	Entry<K,V> e = getCeilingEntry(key);
772	<	return (e == null)? null : e.key;
749	>	return keyOrNull(getCeilingEntry(key));
750		}
751
752		/**
#	Line 780 | Line 757 | public class TreeMap<K,V>
757		* @since 1.6
758		*/
759		public Map.Entry<K,V> higherEntry(K key) {
760	<	Entry<K,V> e = getHigherEntry(key);
784	<	return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
760	>	return exportEntry(getHigherEntry(key));
761		}
762
763		/**
#	Line 792 | Line 768 | public class TreeMap<K,V>
768		* @since 1.6
769		*/
770		public K higherKey(K key) {
771	<	Entry<K,V> e = getHigherEntry(key);
796	<	return (e == null)? null : e.key;
771	>	return keyOrNull(getHigherEntry(key));
772		}
773
774		// Views
#	Line 803 | Line 778 | public class TreeMap<K,V>
778		* the first time this view is requested.  Views are stateless, so
779		* there's no reason to create more than one.
780		*/
781	<	private transient Set<Map.Entry<K,V>> entrySet = null;
781	>	private transient EntrySet entrySet = null;
782		private transient KeySet<K> navigableKeySet = null;
783		private transient NavigableMap<K,V> descendingMap = null;
784
#	Line 829 | Line 804 | public class TreeMap<K,V>
804		* @since 1.6
805		*/
806		public NavigableSet<K> navigableKeySet() {
807	<	NavigableSet<K> nks = navigableKeySet;
807	>	KeySet<K> nks = navigableKeySet;
808		return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
809		}
810
#	Line 876 | Line 851 | public class TreeMap<K,V>
851		* <tt>add</tt> or <tt>addAll</tt> operations.
852		*/
853		public Set<Map.Entry<K,V>> entrySet() {
854	<	Set<Map.Entry<K,V>> es = entrySet;
854	>	EntrySet es = entrySet;
855		return (es != null) ? es : (entrySet = new EntrySet());
856		}
857
#	Line 886 | Line 861 | public class TreeMap<K,V>
861		public NavigableMap<K, V> descendingMap() {
862		NavigableMap<K, V> km = descendingMap;
863		return (km != null) ? km :
864	<	(descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
865	<	(K)UNBOUNDED, 0));
864	>	(descendingMap = new DescendingSubMap(this,
865	>	true, null, true,
866	>	true, null, true));
867		}
868
869		/**
#	Line 898 | Line 874 | public class TreeMap<K,V>
874		* @throws IllegalArgumentException {@inheritDoc}
875		* @since 1.6
876		*/
877	<	public NavigableMap<K,V> navigableSubMap(K fromKey, boolean fromInclusive,
878	<	K toKey,   boolean toInclusive) {
879	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
880	<	toKey,   excluded(toInclusive));
877	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
878	>	K toKey,   boolean toInclusive) {
879	>	return new AscendingSubMap(this,
880	>	false, fromKey, fromInclusive,
881	>	false, toKey,   toInclusive);
882		}
883
884		/**
#	Line 912 | Line 889 | public class TreeMap<K,V>
889		* @throws IllegalArgumentException {@inheritDoc}
890		* @since 1.6
891		*/
892	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
893	<	return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
892	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
893	>	return new AscendingSubMap(this,
894	>	true,  null,  true,
895	>	false, toKey, inclusive);
896		}
897
898		/**
#	Line 924 | Line 903 | public class TreeMap<K,V>
903		* @throws IllegalArgumentException {@inheritDoc}
904		* @since 1.6
905		*/
906	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive) {
907	<	return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 0);
908	<	}
909	<
931	<	/**
932	<	* Translates a boolean "inclusive" value to the correct int value
933	<	* for the loExcluded or hiExcluded field.
934	<	*/
935	<	static int excluded(boolean inclusive) {
936	<	return inclusive ? 0 : 1;
906	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
907	>	return new AscendingSubMap(this,
908	>	false, fromKey, inclusive,
909	>	true,  null,    true);
910		}
911
912		/**
#	Line 944 | Line 917 | public class TreeMap<K,V>
917		* @throws IllegalArgumentException {@inheritDoc}
918		*/
919		public SortedMap<K,V> subMap(K fromKey, K toKey) {
920	<	return navigableSubMap(fromKey, true, toKey, false);
920	>	return subMap(fromKey, true, toKey, false);
921		}
922
923		/**
#	Line 955 | Line 928 | public class TreeMap<K,V>
928		* @throws IllegalArgumentException {@inheritDoc}
929		*/
930		public SortedMap<K,V> headMap(K toKey) {
931	<	return navigableHeadMap(toKey, false);
931	>	return headMap(toKey, false);
932		}
933
934		/**
#	Line 966 | Line 939 | public class TreeMap<K,V>
939		* @throws IllegalArgumentException {@inheritDoc}
940		*/
941		public SortedMap<K,V> tailMap(K fromKey) {
942	<	return navigableTailMap(fromKey, true);
942	>	return tailMap(fromKey, true);
943		}
944
945		// View class support
#	Line 981 | Line 954 | public class TreeMap<K,V>
954		}
955
956		public boolean contains(Object o) {
957	<	for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
985	<	if (valEquals(e.getValue(), o))
986	<	return true;
987	<	return false;
957	>	return TreeMap.this.containsValue(o);
958		}
959
960		public boolean remove(Object o) {
#	Line 1096 | Line 1066 | public class TreeMap<K,V>
1066		m.remove(o);
1067		return size() != oldSize;
1068		}
1069	<	public NavigableSet<E> navigableSubSet(E fromElement,
1070	<	boolean fromInclusive,
1071	<	E toElement,
1072	<	boolean toInclusive) {
1103	<	return new TreeSet<E>
1104	<	(m.navigableSubMap(fromElement, fromInclusive,
1105	<	toElement,   toInclusive));
1069	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1070	>	E toElement,   boolean toInclusive) {
1071	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1072	>	toElement,   toInclusive));
1073		}
1074	<	public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
1075	<	return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
1074	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1075	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
1076		}
1077	<	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
1078	<	return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
1077	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1078	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1079		}
1080		public SortedSet<E> subSet(E fromElement, E toElement) {
1081	<	return navigableSubSet(fromElement, true, toElement, false);
1081	>	return subSet(fromElement, true, toElement, false);
1082		}
1083		public SortedSet<E> headSet(E toElement) {
1084	<	return navigableHeadSet(toElement, false);
1084	>	return headSet(toElement, false);
1085		}
1086		public SortedSet<E> tailSet(E fromElement) {
1087	<	return navigableTailSet(fromElement, true);
1087	>	return tailSet(fromElement, true);
1088		}
1089		public NavigableSet<E> descendingSet() {
1090		return new TreeSet(m.descendingMap());
1091		}
1092		}
1093
1094	<	// SubMaps
1094	>	/**
1095	>	* Base class for TreeMap Iterators
1096	>	*/
1097	>	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1098	>	Entry<K,V> next;
1099	>	Entry<K,V> lastReturned;
1100	>	int expectedModCount;
1101
1102	<	abstract class NavigableSubMap extends AbstractMap<K,V>
1103	<	implements NavigableMap<K,V>, java.io.Serializable {
1102	>	PrivateEntryIterator(Entry<K,V> first) {
1103	>	expectedModCount = modCount;
1104	>	lastReturned = null;
1105	>	next = first;
1106	>	}
1107
1108	<	/**
1109	<	* The low endpoint of this submap in absolute terms.  For ascending
1110	<	* submaps this will be the "first" endpoint; for descending submaps,
1135	<	* the last.  If there is no bound, this field is set to UNBOUNDED.
1136	<	*/
1137	<	K lo;
1108	>	public final boolean hasNext() {
1109	>	return next != null;
1110	>	}
1111
1112	<	/**
1113	<	* Zero if the low endpoint is excluded from this submap, one if
1114	<	* it's included.  This field is unused if lo is UNBOUNDED.
1115	<	*/
1116	<	int loExcluded;
1112	>	final Entry<K,V> nextEntry() {
1113	>	Entry<K,V> e = next;
1114	>	if (e == null)
1115	>	throw new NoSuchElementException();
1116	>	if (modCount != expectedModCount)
1117	>	throw new ConcurrentModificationException();
1118	>	next = successor(e);
1119	>	lastReturned = e;
1120	>	return e;
1121	>	}
1122	>
1123	>	final Entry<K,V> prevEntry() {
1124	>	Entry<K,V> e = next;
1125	>	if (e == null)
1126	>	throw new NoSuchElementException();
1127	>	if (modCount != expectedModCount)
1128	>	throw new ConcurrentModificationException();
1129	>	next = predecessor(e);
1130	>	lastReturned = e;
1131	>	return e;
1132	>	}
1133	>
1134	>	public void remove() {
1135	>	if (lastReturned == null)
1136	>	throw new IllegalStateException();
1137	>	if (modCount != expectedModCount)
1138	>	throw new ConcurrentModificationException();
1139	>	// deleted entries are replaced by their successors
1140	>	if (lastReturned.left != null && lastReturned.right != null)
1141	>	next = lastReturned;
1142	>	deleteEntry(lastReturned);
1143	>	expectedModCount = modCount;
1144	>	lastReturned = null;
1145	>	}
1146	>	}
1147
1148	+	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1149	+	EntryIterator(Entry<K,V> first) {
1150	+	super(first);
1151	+	}
1152	+	public Map.Entry<K,V> next() {
1153	+	return nextEntry();
1154	+	}
1155	+	}
1156	+
1157	+	final class ValueIterator extends PrivateEntryIterator<V> {
1158	+	ValueIterator(Entry<K,V> first) {
1159	+	super(first);
1160	+	}
1161	+	public V next() {
1162	+	return nextEntry().value;
1163	+	}
1164	+	}
1165	+
1166	+	final class KeyIterator extends PrivateEntryIterator<K> {
1167	+	KeyIterator(Entry<K,V> first) {
1168	+	super(first);
1169	+	}
1170	+	public K next() {
1171	+	return nextEntry().key;
1172	+	}
1173	+	}
1174	+
1175	+	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1176	+	DescendingKeyIterator(Entry<K,V> first) {
1177	+	super(first);
1178	+	}
1179	+	public K next() {
1180	+	return prevEntry().key;
1181	+	}
1182	+	}
1183	+
1184	+	// Little utilities
1185	+
1186	+	/**
1187	+	* Compares two keys using the correct comparison method for this TreeMap.
1188	+	*/
1189	+	final int compare(Object k1, Object k2) {
1190	+	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1191	+	: comparator.compare((K)k1, (K)k2);
1192	+	}
1193	+
1194	+	/**
1195	+	* Test two values for equality.  Differs from o1.equals(o2) only in
1196	+	* that it copes with <tt>null</tt> o1 properly.
1197	+	*/
1198	+	final static boolean valEquals(Object o1, Object o2) {
1199	+	return (o1==null ? o2==null : o1.equals(o2));
1200	+	}
1201	+
1202	+	/**
1203	+	* Return SimpleImmutableEntry for entry, or null if null
1204	+	*/
1205	+	static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1206	+	return e == null? null :
1207	+	new AbstractMap.SimpleImmutableEntry<K,V>(e);
1208	+	}
1209	+
1210	+	/**
1211	+	* Return key for entry, or null if null
1212	+	*/
1213	+	static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1214	+	return e == null? null : e.key;
1215	+	}
1216	+
1217	+	/**
1218	+	* Returns the key corresponding to the specified Entry.
1219	+	* @throws NoSuchElementException if the Entry is null
1220	+	*/
1221	+	static <K> K key(Entry<K,?> e) {
1222	+	if (e==null)
1223	+	throw new NoSuchElementException();
1224	+	return e.key;
1225	+	}
1226	+
1227	+
1228	+	// SubMaps
1229	+
1230	+	/**
1231	+	* Dummy value serving as unmatchable fence key for unbounded
1232	+	* SubMapIterators
1233	+	*/
1234	+	private static final Object UNBOUNDED = new Object();
1235	+
1236	+	/**
1237	+	* @serial include
1238	+	*/
1239	+	static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1240	+	implements NavigableMap<K,V>, java.io.Serializable {
1241		/**
1242	<	* The high endpoint of this submap in absolute terms.  For ascending
1147	<	* submaps this will be the "last" endpoint; for descending submaps,
1148	<	* the first.  If there is no bound, this field is set to UNBOUNDED.
1242	>	* The backing map.
1243		*/
1244	<	K hi;
1244	>	final TreeMap<K,V> m;
1245
1246		/**
1247	<	* Zero if the high endpoint is excluded from this submap, one if
1248	<	* it's included.  This field is unused if hi is UNBOUNDED.
1247	>	* Endpoints are represented as triples (fromStart, lo,
1248	>	* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1249	>	* true, then the low (absolute) bound is the start of the
1250	>	* backing map, and the other values are ignored. Otherwise,
1251	>	* if loInclusive is true, lo is the inclusive bound, else lo
1252	>	* is the exclusive bound. Similarly for the upper bound.
1253		*/
1254	<	int hiExcluded;
1254	>	final K lo, hi;
1255	>	final boolean fromStart, toEnd;
1256	>	final boolean loInclusive, hiInclusive;
1257	>
1258	>	NavigableSubMap(TreeMap<K,V> m,
1259	>	boolean fromStart, K lo, boolean loInclusive,
1260	>	boolean toEnd,     K hi, boolean hiInclusive) {
1261	>	if (!fromStart && !toEnd) {
1262	>	if (m.compare(lo, hi) > 0)
1263	>	throw new IllegalArgumentException("fromKey > toKey");
1264	>	} else {
1265	>	if (!fromStart) // type check
1266	>	m.compare(lo, lo);
1267	>	if (!toEnd)
1268	>	m.compare(hi, hi);
1269	>	}
1270
1271	<	NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1272	<	if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
1160	<	throw new IllegalArgumentException("fromKey > toKey");
1271	>	this.m = m;
1272	>	this.fromStart = fromStart;
1273		this.lo = lo;
1274	<	this.loExcluded = loExcluded;
1274	>	this.loInclusive = loInclusive;
1275	>	this.toEnd = toEnd;
1276		this.hi = hi;
1277	<	this.hiExcluded = hiExcluded;
1277	>	this.hiInclusive = hiInclusive;
1278	>	}
1279	>
1280	>	// internal utilities
1281	>
1282	>	final boolean tooLow(Object key) {
1283	>	if (!fromStart) {
1284	>	int c = m.compare(key, lo);
1285	>	if (c < 0 || (c == 0 && !loInclusive))
1286	>	return true;
1287	>	}
1288	>	return false;
1289	>	}
1290	>
1291	>	final boolean tooHigh(Object key) {
1292	>	if (!toEnd) {
1293	>	int c = m.compare(key, hi);
1294	>	if (c > 0 || (c == 0 && !hiInclusive))
1295	>	return true;
1296	>	}
1297	>	return false;
1298	>	}
1299	>
1300	>	final boolean inRange(Object key) {
1301	>	return !tooLow(key) && !tooHigh(key);
1302	>	}
1303	>
1304	>	final boolean inClosedRange(Object key) {
1305	>	return (fromStart || m.compare(key, lo) >= 0)
1306	>	&& (toEnd || m.compare(hi, key) >= 0);
1307	>	}
1308	>
1309	>	final boolean inRange(Object key, boolean inclusive) {
1310	>	return inclusive ? inRange(key) : inClosedRange(key);
1311	>	}
1312	>
1313	>	/*
1314	>	* Absolute versions of relation operations.
1315	>	* Subclasses map to these using like-named "sub"
1316	>	* versions that invert senses for descending maps
1317	>	*/
1318	>
1319	>	final TreeMap.Entry<K,V> absLowest() {
1320	>	TreeMap.Entry<K,V> e =
1321	>	(fromStart ?  m.getFirstEntry() :
1322	>	(loInclusive ? m.getCeilingEntry(lo) :
1323	>	m.getHigherEntry(lo)));
1324	>	return (e == null || tooHigh(e.key)) ? null : e;
1325	>	}
1326	>
1327	>	final TreeMap.Entry<K,V> absHighest() {
1328	>	TreeMap.Entry<K,V> e =
1329	>	(toEnd ?  m.getLastEntry() :
1330	>	(hiInclusive ?  m.getFloorEntry(hi) :
1331	>	m.getLowerEntry(hi)));
1332	>	return (e == null || tooLow(e.key)) ? null : e;
1333	>	}
1334	>
1335	>	final TreeMap.Entry<K,V> absCeiling(K key) {
1336	>	if (tooLow(key))
1337	>	return absLowest();
1338	>	TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1339	>	return (e == null || tooHigh(e.key)) ? null : e;
1340	>	}
1341	>
1342	>	final TreeMap.Entry<K,V> absHigher(K key) {
1343	>	if (tooLow(key))
1344	>	return absLowest();
1345	>	TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1346	>	return (e == null || tooHigh(e.key)) ? null : e;
1347	>	}
1348	>
1349	>	final TreeMap.Entry<K,V> absFloor(K key) {
1350	>	if (tooHigh(key))
1351	>	return absHighest();
1352	>	TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1353	>	return (e == null || tooLow(e.key)) ? null : e;
1354		}
1355
1356	+	final TreeMap.Entry<K,V> absLower(K key) {
1357	+	if (tooHigh(key))
1358	+	return absHighest();
1359	+	TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1360	+	return (e == null || tooLow(e.key)) ? null : e;
1361	+	}
1362	+
1363	+	/** Returns the absolute high fence for ascending traversal */
1364	+	final TreeMap.Entry<K,V> absHighFence() {
1365	+	return (toEnd ? null : (hiInclusive ?
1366	+	m.getHigherEntry(hi) :
1367	+	m.getCeilingEntry(hi)));
1368	+	}
1369	+
1370	+	/** Return the absolute low fence for descending traversal  */
1371	+	final TreeMap.Entry<K,V> absLowFence() {
1372	+	return (fromStart ? null : (loInclusive ?
1373	+	m.getLowerEntry(lo) :
1374	+	m.getFloorEntry(lo)));
1375	+	}
1376	+
1377	+	// Abstract methods defined in ascending vs descending classes
1378	+	// These relay to the appropriate absolute versions
1379	+
1380	+	abstract TreeMap.Entry<K,V> subLowest();
1381	+	abstract TreeMap.Entry<K,V> subHighest();
1382	+	abstract TreeMap.Entry<K,V> subCeiling(K key);
1383	+	abstract TreeMap.Entry<K,V> subHigher(K key);
1384	+	abstract TreeMap.Entry<K,V> subFloor(K key);
1385	+	abstract TreeMap.Entry<K,V> subLower(K key);
1386	+
1387	+	/** Returns ascending iterator from the perspective of this submap */
1388	+	abstract Iterator<K> keyIterator();
1389	+
1390	+	/** Returns descending iterator from the perspective of this submap */
1391	+	abstract Iterator<K> descendingKeyIterator();
1392	+
1393	+	// public methods
1394	+
1395		public boolean isEmpty() {
1396	<	return entrySet().isEmpty();
1396	>	return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1397		}
1398
1399	<	public boolean containsKey(Object key) {
1400	<	return inRange(key) && TreeMap.this.containsKey(key);
1399	>	public int size() {
1400	>	return (fromStart && toEnd) ? m.size() : entrySet().size();
1401		}
1402
1403	<	public V get(Object key) {
1404	<	if (!inRange(key))
1177	<	return null;
1178	<	return TreeMap.this.get(key);
1403	>	public final boolean containsKey(Object key) {
1404	>	return inRange(key) && m.containsKey(key);
1405		}
1406
1407	<	public V put(K key, V value) {
1407	>	public final V put(K key, V value) {
1408		if (!inRange(key))
1409		throw new IllegalArgumentException("key out of range");
1410	<	return TreeMap.this.put(key, value);
1410	>	return m.put(key, value);
1411		}
1412
1413	<	public V remove(Object key) {
1414	<	if (!inRange(key))
1189	<	return null;
1190	<	return TreeMap.this.remove(key);
1413	>	public final V get(Object key) {
1414	>	return !inRange(key)? null :  m.get(key);
1415		}
1416
1417	<	public Map.Entry<K,V> ceilingEntry(K key) {
1418	<	TreeMap.Entry<K,V> e = subCeiling(key);
1195	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1417	>	public final V remove(Object key) {
1418	>	return !inRange(key)? null  : m.remove(key);
1419		}
1420
1421	<	public K ceilingKey(K key) {
1422	<	TreeMap.Entry<K,V> e = subCeiling(key);
1200	<	return e == null? null : e.key;
1421	>	public final Map.Entry<K,V> ceilingEntry(K key) {
1422	>	return exportEntry(subCeiling(key));
1423		}
1424
1425	<	public Map.Entry<K,V> higherEntry(K key) {
1426	<	TreeMap.Entry<K,V> e = subHigher(key);
1205	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1425	>	public final K ceilingKey(K key) {
1426	>	return keyOrNull(subCeiling(key));
1427		}
1428
1429	<	public K higherKey(K key) {
1430	<	TreeMap.Entry<K,V> e = subHigher(key);
1210	<	return e == null? null : e.key;
1429	>	public final Map.Entry<K,V> higherEntry(K key) {
1430	>	return exportEntry(subHigher(key));
1431		}
1432
1433	<	public Map.Entry<K,V> floorEntry(K key) {
1434	<	TreeMap.Entry<K,V> e = subFloor(key);
1215	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1433	>	public final K higherKey(K key) {
1434	>	return keyOrNull(subHigher(key));
1435		}
1436
1437	<	public K floorKey(K key) {
1438	<	TreeMap.Entry<K,V> e = subFloor(key);
1220	<	return e == null? null : e.key;
1437	>	public final Map.Entry<K,V> floorEntry(K key) {
1438	>	return exportEntry(subFloor(key));
1439		}
1440
1441	<	public Map.Entry<K,V> lowerEntry(K key) {
1442	<	TreeMap.Entry<K,V> e = subLower(key);
1225	<	return e == null? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
1441	>	public final K floorKey(K key) {
1442	>	return keyOrNull(subFloor(key));
1443		}
1444
1445	<	public K lowerKey(K key) {
1446	<	TreeMap.Entry<K,V> e = subLower(key);
1230	<	return e == null? null : e.key;
1445	>	public final Map.Entry<K,V> lowerEntry(K key) {
1446	>	return exportEntry(subLower(key));
1447		}
1448
1449	<	abstract Iterator<K> keyIterator();
1450	<	abstract Iterator<K> descendingKeyIterator();
1449	>	public final K lowerKey(K key) {
1450	>	return keyOrNull(subLower(key));
1451	>	}
1452
1453	<	public NavigableSet<K> descendingKeySet() {
1454	<	return descendingMap().navigableKeySet();
1453	>	public final K firstKey() {
1454	>	return key(subLowest());
1455	>	}
1456	>
1457	>	public final K lastKey() {
1458	>	return key(subHighest());
1459	>	}
1460	>
1461	>	public final Map.Entry<K,V> firstEntry() {
1462	>	return exportEntry(subLowest());
1463	>	}
1464	>
1465	>	public final Map.Entry<K,V> lastEntry() {
1466	>	return exportEntry(subHighest());
1467	>	}
1468	>
1469	>	public final Map.Entry<K,V> pollFirstEntry() {
1470	>	TreeMap.Entry<K,V> e = subLowest();
1471	>	Map.Entry<K,V> result = exportEntry(e);
1472	>	if (e != null)
1473	>	m.deleteEntry(e);
1474	>	return result;
1475	>	}
1476	>
1477	>	public final Map.Entry<K,V> pollLastEntry() {
1478	>	TreeMap.Entry<K,V> e = subHighest();
1479	>	Map.Entry<K,V> result = exportEntry(e);
1480	>	if (e != null)
1481	>	m.deleteEntry(e);
1482	>	return result;
1483		}
1484
1485		// Views
1486		transient NavigableMap<K,V> descendingMapView = null;
1487	<	transient Set<Map.Entry<K,V>> entrySetView = null;
1488	<	private transient NavigableSet<K> navigableKeySetView = null;
1487	>	transient EntrySetView entrySetView = null;
1488	>	transient KeySet<K> navigableKeySetView = null;
1489	>
1490	>	public final NavigableSet<K> navigableKeySet() {
1491	>	KeySet<K> nksv = navigableKeySetView;
1492	>	return (nksv != null) ? nksv :
1493	>	(navigableKeySetView = new TreeMap.KeySet(this));
1494	>	}
1495	>
1496	>	public final Set<K> keySet() {
1497	>	return navigableKeySet();
1498	>	}
1499	>
1500	>	public NavigableSet<K> descendingKeySet() {
1501	>	return descendingMap().navigableKeySet();
1502	>	}
1503	>
1504	>	public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1505	>	return subMap(fromKey, true, toKey, false);
1506	>	}
1507	>
1508	>	public final SortedMap<K,V> headMap(K toKey) {
1509	>	return headMap(toKey, false);
1510	>	}
1511	>
1512	>	public final SortedMap<K,V> tailMap(K fromKey) {
1513	>	return tailMap(fromKey, true);
1514	>	}
1515	>
1516	>	// View classes
1517
1518		abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1519		private transient int size = -1, sizeModCount;
1520
1521		public int size() {
1522	<	if (size == -1 || sizeModCount != TreeMap.this.modCount) {
1523	<	size = 0;  sizeModCount = TreeMap.this.modCount;
1522	>	if (fromStart && toEnd)
1523	>	return m.size();
1524	>	if (size == -1 || sizeModCount != m.modCount) {
1525	>	sizeModCount = m.modCount;
1526	>	size = 0;
1527		Iterator i = iterator();
1528		while (i.hasNext()) {
1529		size++;
#	Line 1258 | Line 1534 | public class TreeMap<K,V>
1534		}
1535
1536		public boolean isEmpty() {
1537	<	return !iterator().hasNext();
1537	>	TreeMap.Entry<K,V> n = absLowest();
1538	>	return n == null || tooHigh(n.key);
1539		}
1540
1541		public boolean contains(Object o) {
#	Line 1268 | Line 1545 | public class TreeMap<K,V>
1545		K key = entry.getKey();
1546		if (!inRange(key))
1547		return false;
1548	<	TreeMap.Entry node = getEntry(key);
1548	>	TreeMap.Entry node = m.getEntry(key);
1549		return node != null &&
1550	<	valEquals(node.getValue(), entry.getValue());
1550	>	valEquals(node.getValue(), entry.getValue());
1551		}
1552
1553		public boolean remove(Object o) {
#	Line 1280 | Line 1557 | public class TreeMap<K,V>
1557		K key = entry.getKey();
1558		if (!inRange(key))
1559		return false;
1560	<	TreeMap.Entry<K,V> node = getEntry(key);
1560	>	TreeMap.Entry<K,V> node = m.getEntry(key);
1561		if (node!=null && valEquals(node.getValue(),entry.getValue())){
1562	<	deleteEntry(node);
1562	>	m.deleteEntry(node);
1563		return true;
1564		}
1565		return false;
1566		}
1567		}
1568
1569	<	public NavigableSet<K> navigableKeySet() {
1570	<	NavigableSet<K> nksv = navigableKeySetView;
1571	<	return (nksv != null) ? nksv :
1572	<	(navigableKeySetView = new TreeMap.KeySet(this));
1573	<	}
1574	<
1575	<	public Set<K> keySet() {
1576	<	return navigableKeySet();
1577	<	}
1578	<
1579	<	public SortedMap<K,V> subMap(K fromKey, K toKey) {
1580	<	return navigableSubMap(fromKey, true, toKey, false);
1581	<	}
1569	>	/**
1570	>	* Iterators for SubMaps
1571	>	*/
1572	>	abstract class SubMapIterator<T> implements Iterator<T> {
1573	>	TreeMap.Entry<K,V> lastReturned;
1574	>	TreeMap.Entry<K,V> next;
1575	>	final Object fenceKey;
1576	>	int expectedModCount;
1577	>
1578	>	SubMapIterator(TreeMap.Entry<K,V> first,
1579	>	TreeMap.Entry<K,V> fence) {
1580	>	expectedModCount = m.modCount;
1581	>	lastReturned = null;
1582	>	next = first;
1583	>	fenceKey = fence == null ? UNBOUNDED : fence.key;
1584	>	}
1585
1586	<	public SortedMap<K,V> headMap(K toKey) {
1587	<	return navigableHeadMap(toKey, false);
1588	<	}
1586	>	public final boolean hasNext() {
1587	>	return next != null && next.key != fenceKey;
1588	>	}
1589
1590	<	public SortedMap<K,V> tailMap(K fromKey) {
1591	<	return navigableTailMap(fromKey, true);
1592	<	}
1593	<
1594	<	/** Returns the lowest entry in this submap (absolute ordering) */
1595	<	TreeMap.Entry<K,V> loEntry() {
1596	<	TreeMap.Entry<K,V> result =
1597	<	((lo == UNBOUNDED) ? getFirstEntry() :
1598	<	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1599	<	return (result == null || tooHigh(result.key)) ? null : result;
1320	<	}
1321	<
1322	<	/** Returns the highest key in this submap (absolute ordering) */
1323	<	TreeMap.Entry<K,V> hiEntry() {
1324	<	TreeMap.Entry<K,V> result =
1325	<	((hi == UNBOUNDED) ? getLastEntry() :
1326	<	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1327	<	return (result == null || tooLow(result.key)) ? null : result;
1328	<	}
1329	<
1330	<	/** Polls the lowest entry in this submap (absolute ordering) */
1331	<	Map.Entry<K,V> pollLoEntry() {
1332	<	TreeMap.Entry<K,V> e =
1333	<	((lo == UNBOUNDED) ? getFirstEntry() :
1334	<	(loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
1335	<	if (e == null || tooHigh(e.key))
1336	<	return null;
1337	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1338	<	deleteEntry(e);
1339	<	return result;
1340	<	}
1341	<
1342	<	/** Polls the highest key in this submap (absolute ordering) */
1343	<	Map.Entry<K,V> pollHiEntry() {
1344	<	TreeMap.Entry<K,V> e =
1345	<	((hi == UNBOUNDED) ? getLastEntry() :
1346	<	(hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
1347	<	if (e == null || tooLow(e.key))
1348	<	return null;
1349	<	Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(e);
1350	<	deleteEntry(e);
1351	<	return result;
1352	<	}
1353	<
1354	<	// The following four definitions are correct only for
1355	<	// ascending submaps. They are overridden in DescendingSubMap.
1356	<	// They are defined in the base class because the definitions
1357	<	// in DescendingSubMap rely on those for AscendingSubMap.
1590	>	final TreeMap.Entry<K,V> nextEntry() {
1591	>	TreeMap.Entry<K,V> e = next;
1592	>	if (e == null || e.key == fenceKey)
1593	>	throw new NoSuchElementException();
1594	>	if (m.modCount != expectedModCount)
1595	>	throw new ConcurrentModificationException();
1596	>	next = successor(e);
1597	>	lastReturned = e;
1598	>	return e;
1599	>	}
1600
1601	<	/**
1602	<	* Returns the entry corresponding to the ceiling of the specified
1603	<	* key from the perspective of this submap, or null if the submap
1604	<	* contains no such entry.
1605	<	*/
1606	<	TreeMap.Entry<K,V> subCeiling(K key) {
1607	<	if (tooLow(key))
1608	<	return loEntry();
1609	<	TreeMap.Entry<K,V> e = getCeilingEntry(key);
1610	<	return (e == null || tooHigh(e.key)) ? null : e;
1369	<	}
1601	>	final TreeMap.Entry<K,V> prevEntry() {
1602	>	TreeMap.Entry<K,V> e = next;
1603	>	if (e == null || e.key == fenceKey)
1604	>	throw new NoSuchElementException();
1605	>	if (m.modCount != expectedModCount)
1606	>	throw new ConcurrentModificationException();
1607	>	next = predecessor(e);
1608	>	lastReturned = e;
1609	>	return e;
1610	>	}
1611
1612	<	/**
1613	<	* Returns the entry corresponding to the higher of the specified
1614	<	* key from the perspective of this submap, or null if the submap
1615	<	* contains no such entry.
1616	<	*/
1617	<	TreeMap.Entry<K,V> subHigher(K key) {
1618	<	if (tooLow(key))
1619	<	return loEntry();
1620	<	TreeMap.Entry<K,V> e = getHigherEntry(key);
1621	<	return (e == null || tooHigh(e.key)) ? null : e;
1622	<	}
1612	>	final void removeAscending() {
1613	>	if (lastReturned == null)
1614	>	throw new IllegalStateException();
1615	>	if (m.modCount != expectedModCount)
1616	>	throw new ConcurrentModificationException();
1617	>	// deleted entries are replaced by their successors
1618	>	if (lastReturned.left != null && lastReturned.right != null)
1619	>	next = lastReturned;
1620	>	m.deleteEntry(lastReturned);
1621	>	lastReturned = null;
1622	>	expectedModCount = m.modCount;
1623	>	}
1624
1625	<	/**
1626	<	* Returns the entry corresponding to the floor of the specified
1627	<	* key from the perspective of this submap, or null if the submap
1628	<	* contains no such entry.
1629	<	*/
1630	<	TreeMap.Entry<K,V> subFloor(K key) {
1631	<	if (tooHigh(key))
1632	<	return hiEntry();
1633	<	TreeMap.Entry<K,V> e = getFloorEntry(key);
1392	<	return (e == null || tooLow(e.key)) ? null : e;
1393	<	}
1625	>	final void removeDescending() {
1626	>	if (lastReturned == null)
1627	>	throw new IllegalStateException();
1628	>	if (m.modCount != expectedModCount)
1629	>	throw new ConcurrentModificationException();
1630	>	m.deleteEntry(lastReturned);
1631	>	lastReturned = null;
1632	>	expectedModCount = m.modCount;
1633	>	}
1634
1395	–	/**
1396	–	* Returns the entry corresponding to the lower of the specified
1397	–	* key from the perspective of this submap, or null if the submap
1398	–	* contains no such entry.
1399	–	*/
1400	–	TreeMap.Entry<K,V> subLower(K key) {
1401	–	if (tooHigh(key))
1402	–	return hiEntry();
1403	–	TreeMap.Entry<K,V> e = getLowerEntry(key);
1404	–	return (e == null || tooLow(e.key)) ? null : e;
1635		}
1636
1637	<	boolean inRange(Object key) {
1638	<	return (lo == UNBOUNDED || compare(key, lo) >= loExcluded)
1639	<	&& (hi == UNBOUNDED || compare(hi, key) >= hiExcluded);
1637	>	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1638	>	SubMapEntryIterator(TreeMap.Entry<K,V> first,
1639	>	TreeMap.Entry<K,V> fence) {
1640	>	super(first, fence);
1641	>	}
1642	>	public Map.Entry<K,V> next() {
1643	>	return nextEntry();
1644	>	}
1645	>	public void remove() {
1646	>	removeAscending();
1647	>	}
1648		}
1649
1650	<	boolean inClosedRange(Object key) {
1651	<	return (lo == UNBOUNDED || compare(key, lo) >= 0)
1652	<	&& (hi == UNBOUNDED || compare(hi, key) >= 0);
1650	>	final class SubMapKeyIterator extends SubMapIterator<K> {
1651	>	SubMapKeyIterator(TreeMap.Entry<K,V> first,
1652	>	TreeMap.Entry<K,V> fence) {
1653	>	super(first, fence);
1654	>	}
1655	>	public K next() {
1656	>	return nextEntry().key;
1657	>	}
1658	>	public void remove() {
1659	>	removeAscending();
1660	>	}
1661		}
1662
1663	<	boolean inRange(Object key, boolean inclusive) {
1664	<	return inclusive ? inRange(key) : inClosedRange(key);
1665	<	}
1663	>	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1664	>	DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1665	>	TreeMap.Entry<K,V> fence) {
1666	>	super(last, fence);
1667	>	}
1668
1669	<	boolean tooLow(K key) {
1670	<	return lo != UNBOUNDED && compare(key, lo) < loExcluded;
1669	>	public Map.Entry<K,V> next() {
1670	>	return prevEntry();
1671	>	}
1672	>	public void remove() {
1673	>	removeDescending();
1674	>	}
1675		}
1676
1677	<	boolean tooHigh(K key) {
1678	<	return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
1677	>	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1678	>	DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1679	>	TreeMap.Entry<K,V> fence) {
1680	>	super(last, fence);
1681	>	}
1682	>	public K next() {
1683	>	return prevEntry().key;
1684	>	}
1685	>	public void remove() {
1686	>	removeDescending();
1687	>	}
1688		}
1689		}
1690
1691	<	class AscendingSubMap extends NavigableSubMap {
1691	>	/**
1692	>	* @serial include
1693	>	*/
1694	>	static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1695		private static final long serialVersionUID = 912986545866124060L;
1696
1697	<	AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1698	<	super(lo, loExcluded, hi, hiExcluded);
1697	>	AscendingSubMap(TreeMap<K,V> m,
1698	>	boolean fromStart, K lo, boolean loInclusive,
1699	>	boolean toEnd,     K hi, boolean hiInclusive) {
1700	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1701		}
1702
1703		public Comparator<? super K> comparator() {
1704	<	return comparator;
1704	>	return m.comparator();
1705		}
1706
1707	<	public NavigableMap<K,V> navigableSubMap(
1708	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1707	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1708	>	K toKey,   boolean toInclusive) {
1709		if (!inRange(fromKey, fromInclusive))
1710		throw new IllegalArgumentException("fromKey out of range");
1711		if (!inRange(toKey, toInclusive))
1712		throw new IllegalArgumentException("toKey out of range");
1713	<	return new AscendingSubMap(fromKey, excluded(fromInclusive),
1714	<	toKey,   excluded(toInclusive));
1713	>	return new AscendingSubMap(m,
1714	>	false, fromKey, fromInclusive,
1715	>	false, toKey,   toInclusive);
1716		}
1717
1718	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1719	<	if (!inClosedRange(toKey))
1718	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1719	>	if (!inRange(toKey, inclusive))
1720		throw new IllegalArgumentException("toKey out of range");
1721	<	return new AscendingSubMap(lo,    loExcluded,
1722	<	toKey, excluded(inclusive));
1721	>	return new AscendingSubMap(m,
1722	>	fromStart, lo,    loInclusive,
1723	>	false,     toKey, inclusive);
1724		}
1725
1726	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1726	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1727		if (!inRange(fromKey, inclusive))
1728		throw new IllegalArgumentException("fromKey out of range");
1729	<	return new AscendingSubMap(fromKey, excluded(inclusive),
1730	<	hi,      hiExcluded);
1731	<	}
1464	<
1465	<	Iterator<K> keyIterator() {
1466	<	return new SubMapKeyIterator
1467	<	(loEntry(),
1468	<	hi == UNBOUNDED ? null :
1469	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1470	<	getHigherEntry(hi));
1471	<	}
1472	<
1473	<	Iterator<K> descendingKeyIterator() {
1474	<	return new DescendingSubMapKeyIterator
1475	<	(hiEntry(),
1476	<	lo == UNBOUNDED ? null :
1477	<	loExcluded == 1 ? getFloorEntry(lo) :
1478	<	getLowerEntry(lo));
1479	<	}
1480	<
1481	<	public Set<Map.Entry<K,V>> entrySet() {
1482	<	Set<Map.Entry<K,V>> es = entrySetView;
1483	<	if  (es != null)
1484	<	return es;
1485	<	return entrySetView = new NavigableSubMap.EntrySetView() {
1486	<	public Iterator<Map.Entry<K,V>> iterator() {
1487	<	return new SubMapEntryIterator(loEntry(),
1488	<	hi == UNBOUNDED ? null :
1489	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1490	<	getHigherEntry(hi));
1491	<	}
1492	<	};
1729	>	return new AscendingSubMap(m,
1730	>	false, fromKey, inclusive,
1731	>	toEnd, hi,      hiInclusive);
1732		}
1733
1734	<	public K firstKey() {
1735	<	return key(loEntry());
1736	<	}
1737	<
1738	<	public K lastKey() {
1739	<	return key(hiEntry());
1734	>	public NavigableMap<K,V> descendingMap() {
1735	>	NavigableMap<K,V> mv = descendingMapView;
1736	>	return (mv != null) ? mv :
1737	>	(descendingMapView =
1738	>	new DescendingSubMap(m,
1739	>	fromStart, lo, loInclusive,
1740	>	toEnd,     hi, hiInclusive));
1741		}
1742
1743	<	public Map.Entry<K,V> firstEntry() {
1744	<	return loEntry();
1743	>	Iterator<K> keyIterator() {
1744	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1745		}
1746
1747	<	public Map.Entry<K,V> lastEntry() {
1748	<	return hiEntry();
1747	>	Iterator<K> descendingKeyIterator() {
1748	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1749		}
1750
1751	<	public Map.Entry<K,V> pollFirstEntry() {
1752	<	return pollLoEntry();
1751	>	final class AscendingEntrySetView extends EntrySetView {
1752	>	public Iterator<Map.Entry<K,V>> iterator() {
1753	>	return new SubMapEntryIterator(absLowest(), absHighFence());
1754	>	}
1755		}
1756
1757	<	public Map.Entry<K,V> pollLastEntry() {
1758	<	return pollHiEntry();
1757	>	public Set<Map.Entry<K,V>> entrySet() {
1758	>	EntrySetView es = entrySetView;
1759	>	return (es != null) ? es : new AscendingEntrySetView();
1760		}
1761
1762	<	public NavigableMap<K,V> descendingMap() {
1763	<	NavigableMap<K,V> m = descendingMapView;
1764	<	return (m != null) ? m :
1765	<	(descendingMapView =
1766	<	new DescendingSubMap(lo, loExcluded, hi, hiExcluded));
1767	<	}
1762	>	TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1763	>	TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1764	>	TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1765	>	TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1766	>	TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1767	>	TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1768		}
1769
1770	<	class DescendingSubMap extends NavigableSubMap {
1770	>	/**
1771	>	* @serial include
1772	>	*/
1773	>	static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1774		private static final long serialVersionUID = 912986545866120460L;
1775	<	DescendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
1776	<	super(lo, loExcluded, hi, hiExcluded);
1775	>	DescendingSubMap(TreeMap<K,V> m,
1776	>	boolean fromStart, K lo, boolean loInclusive,
1777	>	boolean toEnd,     K hi, boolean hiInclusive) {
1778	>	super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1779		}
1780
1781		private final Comparator<? super K> reverseComparator =
1782	<	Collections.reverseOrder(comparator);
1782	>	Collections.reverseOrder(m.comparator);
1783
1784		public Comparator<? super K> comparator() {
1785		return reverseComparator;
1786		}
1787
1788	<	public NavigableMap<K,V> navigableSubMap(
1789	<	K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1788	>	public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1789	>	K toKey,   boolean toInclusive) {
1790		if (!inRange(fromKey, fromInclusive))
1791		throw new IllegalArgumentException("fromKey out of range");
1792		if (!inRange(toKey, toInclusive))
1793		throw new IllegalArgumentException("toKey out of range");
1794	<	return new DescendingSubMap(toKey,   excluded(toInclusive),
1795	<	fromKey, excluded(fromInclusive));
1794	>	return new DescendingSubMap(m,
1795	>	false, toKey,   toInclusive,
1796	>	false, fromKey, fromInclusive);
1797		}
1798
1799	<	public NavigableMap<K,V> navigableHeadMap(K toKey, boolean inclusive) {
1799	>	public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1800		if (!inRange(toKey, inclusive))
1801		throw new IllegalArgumentException("toKey out of range");
1802	<	return new DescendingSubMap(toKey, inclusive ? 0:1, hi, hiExcluded);
1802	>	return new DescendingSubMap(m,
1803	>	false, toKey, inclusive,
1804	>	toEnd, hi,    hiInclusive);
1805		}
1806
1807	<	public NavigableMap<K,V> navigableTailMap(K fromKey, boolean inclusive){
1807	>	public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1808		if (!inRange(fromKey, inclusive))
1809		throw new IllegalArgumentException("fromKey out of range");
1810	<	return new DescendingSubMap(lo,      loExcluded,
1811	<	fromKey, excluded(inclusive));
1812	<	}
1562	<
1563	<	Iterator<K> keyIterator() {
1564	<	return new DescendingSubMapKeyIterator
1565	<	(hiEntry(),
1566	<	lo == UNBOUNDED ? null :
1567	<	loExcluded == 1 ? getFloorEntry(lo) :
1568	<	getLowerEntry(lo));
1569	<	}
1570	<
1571	<	Iterator<K> descendingKeyIterator() {
1572	<	return new SubMapKeyIterator
1573	<	(loEntry(),
1574	<	hi == UNBOUNDED ? null :
1575	<	hiExcluded == 1 ? getCeilingEntry(hi) :
1576	<	getHigherEntry(hi));
1577	<	}
1578	<
1579	<	public Set<Map.Entry<K,V>> entrySet() {
1580	<	Set<Map.Entry<K,V>> es = entrySetView;
1581	<	if  (es != null)
1582	<	return es;
1583	<	return entrySetView = new NavigableSubMap.EntrySetView() {
1584	<	public Iterator<Map.Entry<K,V>> iterator() {
1585	<	return new DescendingSubMapEntryIterator(hiEntry(),
1586	<	lo == UNBOUNDED ? null :
1587	<	loExcluded == 1 ? getFloorEntry(lo) :
1588	<	getLowerEntry(lo));
1589	<	}
1590	<	};
1591	<	}
1592	<
1593	<	public K firstKey() {
1594	<	return key(hiEntry());
1595	<	}
1596	<
1597	<	public K lastKey() {
1598	<	return key(loEntry());
1599	<	}
1600	<
1601	<	public Map.Entry<K,V> firstEntry() {
1602	<	return hiEntry();
1603	<	}
1604	<
1605	<	public Map.Entry<K,V> lastEntry() {
1606	<	return loEntry();
1607	<	}
1608	<
1609	<	public Map.Entry<K,V> pollFirstEntry() {
1610	<	return pollHiEntry();
1611	<	}
1612	<
1613	<	public Map.Entry<K,V> pollLastEntry() {
1614	<	return pollLoEntry();
1810	>	return new DescendingSubMap(m,
1811	>	fromStart, lo, loInclusive,
1812	>	false, fromKey, inclusive);
1813		}
1814
1815		public NavigableMap<K,V> descendingMap() {
1816	<	NavigableMap<K,V> m = descendingMapView;
1817	<	return (m != null) ? m :
1816	>	NavigableMap<K,V> mv = descendingMapView;
1817	>	return (mv != null) ? mv :
1818		(descendingMapView =
1819	<	new AscendingSubMap(lo, loExcluded, hi, hiExcluded));
1819	>	new AscendingSubMap(m,
1820	>	fromStart, lo, loInclusive,
1821	>	toEnd,     hi, hiInclusive));
1822		}
1823
1824	<	@Override TreeMap.Entry<K,V> subCeiling(K key) {
1825	<	return super.subFloor(key);
1824	>	Iterator<K> keyIterator() {
1825	>	return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1826		}
1827
1828	<	@Override TreeMap.Entry<K,V> subHigher(K key) {
1829	<	return super.subLower(key);
1828	>	Iterator<K> descendingKeyIterator() {
1829	>	return new SubMapKeyIterator(absLowest(), absHighFence());
1830		}
1831
1832	<	@Override TreeMap.Entry<K,V> subFloor(K key) {
1833	<	return super.subCeiling(key);
1832	>	final class DescendingEntrySetView extends EntrySetView {
1833	>	public Iterator<Map.Entry<K,V>> iterator() {
1834	>	return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1835	>	}
1836		}
1837
1838	<	@Override TreeMap.Entry<K,V> subLower(K key) {
1839	<	return super.subHigher(key);
1838	>	public Set<Map.Entry<K,V>> entrySet() {
1839	>	EntrySetView es = entrySetView;
1840	>	return (es != null) ? es : new DescendingEntrySetView();
1841		}
1842	+
1843	+	TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1844	+	TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1845	+	TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1846	+	TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1847	+	TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1848	+	TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1849		}
1850
1851		/**
#	Line 1644 | Line 1854 | public class TreeMap<K,V>
1854		* support NavigableMap.  It translates an old-version SubMap into
1855		* a new-version AscendingSubMap. This class is never otherwise
1856		* used.
1857	+	*
1858	+	* @serial include
1859		*/
1860		private class SubMap extends AbstractMap<K,V>
1861	<	implements SortedMap<K,V>, java.io.Serializable {
1861	>	implements SortedMap<K,V>, java.io.Serializable {
1862		private static final long serialVersionUID = -6520786458950516097L;
1863		private boolean fromStart = false, toEnd = false;
1864		private K fromKey, toKey;
1865		private Object readResolve() {
1866	<	return new AscendingSubMap
1867	<	(fromStart? ((K)UNBOUNDED) : fromKey, 0,
1868	<	toEnd? ((K)UNBOUNDED) : toKey, 1);
1657	<	}
1658	<	public Set<Map.Entry<K,V>> entrySet() { throw new UnsupportedOperationException(); }
1659	<	public K lastKey() { throw new UnsupportedOperationException(); }
1660	<	public K firstKey() { throw new UnsupportedOperationException(); }
1661	<	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new UnsupportedOperationException(); }
1662	<	public SortedMap<K,V> headMap(K toKey) { throw new UnsupportedOperationException(); }
1663	<	public SortedMap<K,V> tailMap(K fromKey) { throw new UnsupportedOperationException(); }
1664	<	public Comparator<? super K> comparator() { throw new UnsupportedOperationException(); }
1665	<	}
1666	<
1667	<	/**
1668	<	* TreeMap Iterator.
1669	<	*/
1670	<	abstract class PrivateEntryIterator<T> implements Iterator<T> {
1671	<	int expectedModCount = TreeMap.this.modCount;
1672	<	Entry<K,V> lastReturned = null;
1673	<	Entry<K,V> next;
1674	<
1675	<	PrivateEntryIterator(Entry<K,V> first) {
1676	<	next = first;
1677	<	}
1678	<
1679	<	public final boolean hasNext() {
1680	<	return next != null;
1681	<	}
1682	<
1683	<	final Entry<K,V> nextEntry() {
1684	<	if (next == null)
1685	<	throw new NoSuchElementException();
1686	<	if (modCount != expectedModCount)
1687	<	throw new ConcurrentModificationException();
1688	<	lastReturned = next;
1689	<	next = successor(next);
1690	<	return lastReturned;
1691	<	}
1692	<
1693	<	final Entry<K,V> prevEntry() {
1694	<	if (next == null)
1695	<	throw new NoSuchElementException();
1696	<	if (modCount != expectedModCount)
1697	<	throw new ConcurrentModificationException();
1698	<	lastReturned = next;
1699	<	next = predecessor(next);
1700	<	return lastReturned;
1701	<	}
1702	<
1703	<	public void remove() {
1704	<	if (lastReturned == null)
1705	<	throw new IllegalStateException();
1706	<	if (modCount != expectedModCount)
1707	<	throw new ConcurrentModificationException();
1708	<	if (lastReturned.left != null && lastReturned.right != null)
1709	<	next = lastReturned;
1710	<	deleteEntry(lastReturned);
1711	<	expectedModCount++;
1712	<	lastReturned = null;
1713	<	}
1714	<	}
1715	<
1716	<	final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1717	<	EntryIterator(Entry<K,V> first) {
1718	<	super(first);
1719	<	}
1720	<	public Map.Entry<K,V> next() {
1721	<	return nextEntry();
1722	<	}
1723	<	}
1724	<
1725	<	final class ValueIterator extends PrivateEntryIterator<V> {
1726	<	ValueIterator(Entry<K,V> first) {
1727	<	super(first);
1728	<	}
1729	<	public V next() {
1730	<	return nextEntry().value;
1731	<	}
1732	<	}
1733	<
1734	<	final class KeyIterator extends PrivateEntryIterator<K> {
1735	<	KeyIterator(Entry<K,V> first) {
1736	<	super(first);
1737	<	}
1738	<	public K next() {
1739	<	return nextEntry().key;
1740	<	}
1741	<	}
1742	<
1743	<	final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1744	<	DescendingKeyIterator(Entry<K,V> first) {
1745	<	super(first);
1746	<	}
1747	<	public K next() {
1748	<	return prevEntry().key;
1749	<	}
1750	<	}
1751	<
1752	<	/**
1753	<	* Iterators for SubMaps
1754	<	*/
1755	<	abstract class SubMapIterator<T> implements Iterator<T> {
1756	<	int expectedModCount = TreeMap.this.modCount;
1757	<	Entry<K,V> lastReturned = null;
1758	<	Entry<K,V> next;
1759	<	final K firstExcludedKey;
1760	<
1761	<	SubMapIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1762	<	next = first;
1763	<	firstExcludedKey = (firstExcluded == null ? null
1764	<	: firstExcluded.key);
1765	<	}
1766	<
1767	<	public final boolean hasNext() {
1768	<	return next != null && next.key != firstExcludedKey;
1769	<	}
1770	<
1771	<	final Entry<K,V> nextEntry() {
1772	<	if (next == null || next.key == firstExcludedKey)
1773	<	throw new NoSuchElementException();
1774	<	if (modCount != expectedModCount)
1775	<	throw new ConcurrentModificationException();
1776	<	lastReturned = next;
1777	<	next = successor(next);
1778	<	return lastReturned;
1779	<	}
1780	<
1781	<	final Entry<K,V> prevEntry() {
1782	<	if (next == null || next.key == firstExcludedKey)
1783	<	throw new NoSuchElementException();
1784	<	if (modCount != expectedModCount)
1785	<	throw new ConcurrentModificationException();
1786	<	lastReturned = next;
1787	<	next = predecessor(next);
1788	<	return lastReturned;
1789	<	}
1790	<
1791	<	public void remove() {
1792	<	if (lastReturned == null)
1793	<	throw new IllegalStateException();
1794	<	if (modCount != expectedModCount)
1795	<	throw new ConcurrentModificationException();
1796	<	if (lastReturned.left != null && lastReturned.right != null)
1797	<	next = lastReturned;
1798	<	deleteEntry(lastReturned);
1799	<	expectedModCount++;
1800	<	lastReturned = null;
1801	<	}
1802	<	}
1803	<
1804	<	final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1805	<	SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1806	<	super(first, firstExcluded);
1807	<	}
1808	<	public Map.Entry<K,V> next() {
1809	<	return nextEntry();
1810	<	}
1811	<	}
1812	<
1813	<	final class SubMapKeyIterator extends SubMapIterator<K> {
1814	<	SubMapKeyIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1815	<	super(first, firstExcluded);
1816	<	}
1817	<	public K next() {
1818	<	return nextEntry().key;
1819	<	}
1820	<	}
1821	<
1822	<	final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1823	<	DescendingSubMapEntryIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1824	<	super(last, lastExcluded);
1825	<	}
1826	<
1827	<	public Map.Entry<K,V> next() {
1828	<	return prevEntry();
1866	>	return new AscendingSubMap(TreeMap.this,
1867	>	fromStart, fromKey, true,
1868	>	toEnd, toKey, false);
1869		}
1870	+	public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1871	+	public K lastKey() { throw new InternalError(); }
1872	+	public K firstKey() { throw new InternalError(); }
1873	+	public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1874	+	public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1875	+	public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1876	+	public Comparator<? super K> comparator() { throw new InternalError(); }
1877		}
1878
1832	–	final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1833	–	DescendingSubMapKeyIterator(Entry<K,V> last, Entry<K,V> lastExcluded) {
1834	–	super(last, lastExcluded);
1835	–	}
1836	–	public K next() {
1837	–	return prevEntry().key;
1838	–	}
1839	–	}
1879
1880	<	/**
1842	<	* Compares two keys using the correct comparison method for this TreeMap.
1843	<	*/
1844	<	private int compare(Object k1, Object k2) {
1845	<	return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1846	<	: comparator.compare((K)k1, (K)k2);
1847	<	}
1848	<
1849	<	/**
1850	<	* Test two values for equality.  Differs from o1.equals(o2) only in
1851	<	* that it copes with <tt>null</tt> o1 properly.
1852	<	*/
1853	<	private static boolean valEquals(Object o1, Object o2) {
1854	<	return (o1==null ? o2==null : o1.equals(o2));
1855	<	}
1880	>	// Red-black mechanics
1881
1882		private static final boolean RED   = false;
1883		private static final boolean BLACK = true;
#	Line 1862 | Line 1887 | public class TreeMap<K,V>
1887		* user (see Map.Entry).
1888		*/
1889
1890	<	static class Entry<K,V> implements Map.Entry<K,V> {
1891	<	K key;
1890	>	static final class Entry<K,V> implements Map.Entry<K,V> {
1891	>	K key;
1892		V value;
1893		Entry<K,V> left = null;
1894		Entry<K,V> right = null;
#	Line 1914 | Line 1939 | public class TreeMap<K,V>
1939		public boolean equals(Object o) {
1940		if (!(o instanceof Map.Entry))
1941		return false;
1942	<	Map.Entry e = (Map.Entry)o;
1942	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1943
1944		return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1945		}
#	Line 1934 | Line 1959 | public class TreeMap<K,V>
1959		* Returns the first Entry in the TreeMap (according to the TreeMap's
1960		* key-sort function).  Returns null if the TreeMap is empty.
1961		*/
1962	<	private Entry<K,V> getFirstEntry() {
1962	>	final Entry<K,V> getFirstEntry() {
1963		Entry<K,V> p = root;
1964		if (p != null)
1965		while (p.left != null)
#	Line 1946 | Line 1971 | public class TreeMap<K,V>
1971		* Returns the last Entry in the TreeMap (according to the TreeMap's
1972		* key-sort function).  Returns null if the TreeMap is empty.
1973		*/
1974	<	private Entry<K,V> getLastEntry() {
1974	>	final Entry<K,V> getLastEntry() {
1975		Entry<K,V> p = root;
1976		if (p != null)
1977		while (p.right != null)
#	Line 1957 | Line 1982 | public class TreeMap<K,V>
1982		/**
1983		* Returns the successor of the specified Entry, or null if no such.
1984		*/
1985	<	private Entry<K,V> successor(Entry<K,V> t) {
1985	>	static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1986		if (t == null)
1987		return null;
1988		else if (t.right != null) {
#	Line 1979 | Line 2004 | public class TreeMap<K,V>
2004		/**
2005		* Returns the predecessor of the specified Entry, or null if no such.
2006		*/
2007	<	private Entry<K,V> predecessor(Entry<K,V> t) {
2007	>	static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2008		if (t == null)
2009		return null;
2010		else if (t.left != null) {
#	Line 2018 | Line 2043 | public class TreeMap<K,V>
2043
2044		private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2045		if (p != null)
2046	<	p.color = c;
2046	>	p.color = c;
2047		}
2048
2049		private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
#	Line 2029 | Line 2054 | public class TreeMap<K,V>
2054		return (p == null) ? null: p.right;
2055		}
2056
2057	<	/** From CLR **/
2057	>	/** From CLR */
2058		private void rotateLeft(Entry<K,V> p) {
2059	<	Entry<K,V> r = p.right;
2060	<	p.right = r.left;
2061	<	if (r.left != null)
2062	<	r.left.parent = p;
2063	<	r.parent = p.parent;
2064	<	if (p.parent == null)
2065	<	root = r;
2066	<	else if (p.parent.left == p)
2067	<	p.parent.left = r;
2068	<	else
2069	<	p.parent.right = r;
2070	<	r.left = p;
2071	<	p.parent = r;
2059	>	if (p != null) {
2060	>	Entry<K,V> r = p.right;
2061	>	p.right = r.left;
2062	>	if (r.left != null)
2063	>	r.left.parent = p;
2064	>	r.parent = p.parent;
2065	>	if (p.parent == null)
2066	>	root = r;
2067	>	else if (p.parent.left == p)
2068	>	p.parent.left = r;
2069	>	else
2070	>	p.parent.right = r;
2071	>	r.left = p;
2072	>	p.parent = r;
2073	>	}
2074		}
2075
2076	<	/** From CLR **/
2076	>	/** From CLR */
2077		private void rotateRight(Entry<K,V> p) {
2078	<	Entry<K,V> l = p.left;
2079	<	p.left = l.right;
2080	<	if (l.right != null) l.right.parent = p;
2081	<	l.parent = p.parent;
2082	<	if (p.parent == null)
2083	<	root = l;
2084	<	else if (p.parent.right == p)
2085	<	p.parent.right = l;
2086	<	else p.parent.left = l;
2087	<	l.right = p;
2088	<	p.parent = l;
2078	>	if (p != null) {
2079	>	Entry<K,V> l = p.left;
2080	>	p.left = l.right;
2081	>	if (l.right != null) l.right.parent = p;
2082	>	l.parent = p.parent;
2083	>	if (p.parent == null)
2084	>	root = l;
2085	>	else if (p.parent.right == p)
2086	>	p.parent.right = l;
2087	>	else p.parent.left = l;
2088	>	l.right = p;
2089	>	p.parent = l;
2090	>	}
2091		}
2092
2093	<
2065	<	/** From CLR **/
2093	>	/** From CLR */
2094		private void fixAfterInsertion(Entry<K,V> x) {
2095		x.color = RED;
2096
#	Line 2081 | Line 2109 | public class TreeMap<K,V>
2109		}
2110		setColor(parentOf(x), BLACK);
2111		setColor(parentOf(parentOf(x)), RED);
2112	<	if (parentOf(parentOf(x)) != null)
2085	<	rotateRight(parentOf(parentOf(x)));
2112	>	rotateRight(parentOf(parentOf(x)));
2113		}
2114		} else {
2115		Entry<K,V> y = leftOf(parentOf(parentOf(x)));
#	Line 2096 | Line 2123 | public class TreeMap<K,V>
2123		x = parentOf(x);
2124		rotateRight(x);
2125		}
2126	<	setColor(parentOf(x),  BLACK);
2126	>	setColor(parentOf(x), BLACK);
2127		setColor(parentOf(parentOf(x)), RED);
2128	<	if (parentOf(parentOf(x)) != null)
2102	<	rotateLeft(parentOf(parentOf(x)));
2128	>	rotateLeft(parentOf(parentOf(x)));
2129		}
2130		}
2131		}
#	Line 2109 | Line 2135 | public class TreeMap<K,V>
2135		/**
2136		* Delete node p, and then rebalance the tree.
2137		*/
2112	–
2138		private void deleteEntry(Entry<K,V> p) {
2139	<	decrementSize();
2139	>	modCount++;
2140	>	size--;
2141
2142		// If strictly internal, copy successor's element to p and then make p
2143		// point to successor.
#	Line 2157 | Line 2183 | public class TreeMap<K,V>
2183		}
2184		}
2185
2186	<	/** From CLR **/
2186	>	/** From CLR */
2187		private void fixAfterDeletion(Entry<K,V> x) {
2188		while (x != root && colorOf(x) == BLACK) {
2189		if (x == leftOf(parentOf(x))) {
#	Line 2172 | Line 2198 | public class TreeMap<K,V>
2198
2199		if (colorOf(leftOf(sib))  == BLACK &&
2200		colorOf(rightOf(sib)) == BLACK) {
2201	<	setColor(sib,  RED);
2201	>	setColor(sib, RED);
2202		x = parentOf(x);
2203		} else {
2204		if (colorOf(rightOf(sib)) == BLACK) {
#	Line 2199 | Line 2225 | public class TreeMap<K,V>
2225
2226		if (colorOf(rightOf(sib)) == BLACK &&
2227		colorOf(leftOf(sib)) == BLACK) {
2228	<	setColor(sib,  RED);
2228	>	setColor(sib, RED);
2229		x = parentOf(x);
2230		} else {
2231		if (colorOf(leftOf(sib)) == BLACK) {
#	Line 2265 | Line 2291 | public class TreeMap<K,V>
2291		buildFromSorted(size, null, s, null);
2292		}
2293
2294	<	/** Intended to be called only from TreeSet.readObject **/
2294	>	/** Intended to be called only from TreeSet.readObject */
2295		void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2296		throws java.io.IOException, ClassNotFoundException {
2297		buildFromSorted(size, null, s, defaultVal);
2298		}
2299
2300	<	/** Intended to be called only from TreeSet.addAll **/
2300	>	/** Intended to be called only from TreeSet.addAll */
2301		void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2302	<	try {
2303	<	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304	<	} catch (java.io.IOException cannotHappen) {
2305	<	} catch (ClassNotFoundException cannotHappen) {
2306	<	}
2302	>	try {
2303	>	buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304	>	} catch (java.io.IOException cannotHappen) {
2305	>	} catch (ClassNotFoundException cannotHappen) {
2306	>	}
2307		}
2308
2309
#	Line 2312 | Line 2338 | public class TreeMap<K,V>
2338		*         This cannot occur if str is null.
2339		*/
2340		private void buildFromSorted(int size, Iterator it,
2341	<	java.io.ObjectInputStream str,
2342	<	V defaultVal)
2341	>	java.io.ObjectInputStream str,
2342	>	V defaultVal)
2343		throws  java.io.IOException, ClassNotFoundException {
2344		this.size = size;
2345		root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2346	<	it, str, defaultVal);
2346	>	it, str, defaultVal);
2347		}
2348
2349		/**
#	Line 2335 | Line 2361 | public class TreeMap<K,V>
2361		*        Must be equal to computeRedLevel for tree of this size.
2362		*/
2363		private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2364	<	int redLevel,
2365	<	Iterator it,
2366	<	java.io.ObjectInputStream str,
2367	<	V defaultVal)
2364	>	int redLevel,
2365	>	Iterator it,
2366	>	java.io.ObjectInputStream str,
2367	>	V defaultVal)
2368		throws  java.io.IOException, ClassNotFoundException {
2369		/*
2370		* Strategy: The root is the middlemost element. To get to it, we
#	Line 2354 | Line 2380 | public class TreeMap<K,V>
2380
2381		if (hi < lo) return null;
2382
2383	<	int mid = (lo + hi) / 2;
2383	>	int mid = (lo + hi) >>> 1;
2384
2385		Entry<K,V> left  = null;
2386		if (lo < mid)
2387		left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2388	<	it, str, defaultVal);
2388	>	it, str, defaultVal);
2389
2390		// extract key and/or value from iterator or stream
2391		K key;
#	Line 2391 | Line 2417 | public class TreeMap<K,V>
2417
2418		if (mid < hi) {
2419		Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2420	<	it, str, defaultVal);
2420	>	it, str, defaultVal);
2421		middle.right = right;
2422		right.parent = middle;
2423		}

Diff Legend

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