View Javadoc
1   /*
2    * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
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.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  package java.util;
27  
28  import java.io.Serializable;
29  import java.util.function.BiConsumer;
30  import java.util.function.BiFunction;
31  import java.util.function.Consumer;
32  
33  /**
34   * A Red-Black tree based {@link NavigableMap} implementation.
35   * The map is sorted according to the {@linkplain Comparable natural
36   * ordering} of its keys, or by a {@link Comparator} provided at map
37   * creation time, depending on which constructor is used.
38   *
39   * <p>This implementation provides guaranteed log(n) time cost for the
40   * {@code containsKey}, {@code get}, {@code put} and {@code remove}
41   * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
42   * Rivest's <em>Introduction to Algorithms</em>.
43   *
44   * <p>Note that the ordering maintained by a tree map, like any sorted map, and
45   * whether or not an explicit comparator is provided, must be <em>consistent
46   * with {@code equals}</em> if this sorted map is to correctly implement the
47   * {@code Map} interface.  (See {@code Comparable} or {@code Comparator} for a
48   * precise definition of <em>consistent with equals</em>.)  This is so because
49   * the {@code Map} interface is defined in terms of the {@code equals}
50   * operation, but a sorted map performs all key comparisons using its {@code
51   * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
52   * this method are, from the standpoint of the sorted map, equal.  The behavior
53   * of a sorted map <em>is</em> well-defined even if its ordering is
54   * inconsistent with {@code equals}; it just fails to obey the general contract
55   * of the {@code Map} interface.
56   *
57   * <p><strong>Note that this implementation is not synchronized.</strong>
58   * If multiple threads access a map concurrently, and at least one of the
59   * threads modifies the map structurally, it <em>must</em> be synchronized
60   * externally.  (A structural modification is any operation that adds or
61   * deletes one or more mappings; merely changing the value associated
62   * with an existing key is not a structural modification.)  This is
63   * typically accomplished by synchronizing on some object that naturally
64   * encapsulates the map.
65   * If no such object exists, the map should be "wrapped" using the
66   * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
67   * method.  This is best done at creation time, to prevent accidental
68   * unsynchronized access to the map: <pre>
69   *   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
70   *
71   * <p>The iterators returned by the {@code iterator} method of the collections
72   * returned by all of this class's "collection view methods" are
73   * <em>fail-fast</em>: if the map is structurally modified at any time after
74   * the iterator is created, in any way except through the iterator's own
75   * {@code remove} method, the iterator will throw a {@link
76   * ConcurrentModificationException}.  Thus, in the face of concurrent
77   * modification, the iterator fails quickly and cleanly, rather than risking
78   * arbitrary, non-deterministic behavior at an undetermined time in the future.
79   *
80   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
81   * as it is, generally speaking, impossible to make any hard guarantees in the
82   * presence of unsynchronized concurrent modification.  Fail-fast iterators
83   * throw {@code ConcurrentModificationException} on a best-effort basis.
84   * Therefore, it would be wrong to write a program that depended on this
85   * exception for its correctness:   <em>the fail-fast behavior of iterators
86   * should be used only to detect bugs.</em>
87   *
88   * <p>All {@code Map.Entry} pairs returned by methods in this class
89   * and its views represent snapshots of mappings at the time they were
90   * produced. They do <strong>not</strong> support the {@code Entry.setValue}
91   * method. (Note however that it is possible to change mappings in the
92   * associated map using {@code put}.)
93   *
94   * <p>This class is a member of the
95   * <a href="{@docRoot}/../technotes/guides/collections/index.html">
96   * Java Collections Framework</a>.
97   *
98   * @param <K> the type of keys maintained by this map
99   * @param <V> the type of mapped values
100  *
101  * @author  Josh Bloch and Doug Lea
102  * @see Map
103  * @see HashMap
104  * @see Hashtable
105  * @see Comparable
106  * @see Comparator
107  * @see Collection
108  * @since 1.2
109  */
110 
111 public class TreeMap<K,V>
112     extends AbstractMap<K,V>
113     implements NavigableMap<K,V>, Cloneable, java.io.Serializable
114 {
115     /**
116      * The comparator used to maintain order in this tree map, or
117      * null if it uses the natural ordering of its keys.
118      *
119      * @serial
120      */
121     private final Comparator<? super K> comparator;
122 
123     private transient Entry<K,V> root = null;
124 
125     /**
126      * The number of entries in the tree
127      */
128     private transient int size = 0;
129 
130     /**
131      * The number of structural modifications to the tree.
132      */
133     private transient int modCount = 0;
134 
135     /**
136      * Constructs a new, empty tree map, using the natural ordering of its
137      * keys.  All keys inserted into the map must implement the {@link
138      * Comparable} interface.  Furthermore, all such keys must be
139      * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
140      * a {@code ClassCastException} for any keys {@code k1} and
141      * {@code k2} in the map.  If the user attempts to put a key into the
142      * map that violates this constraint (for example, the user attempts to
143      * put a string key into a map whose keys are integers), the
144      * {@code put(Object key, Object value)} call will throw a
145      * {@code ClassCastException}.
146      */
147     public TreeMap() {
148         comparator = null;
149     }
150 
151     /**
152      * Constructs a new, empty tree map, ordered according to the given
153      * comparator.  All keys inserted into the map must be <em>mutually
154      * comparable</em> by the given comparator: {@code comparator.compare(k1,
155      * k2)} must not throw a {@code ClassCastException} for any keys
156      * {@code k1} and {@code k2} in the map.  If the user attempts to put
157      * a key into the map that violates this constraint, the {@code put(Object
158      * key, Object value)} call will throw a
159      * {@code ClassCastException}.
160      *
161      * @param comparator the comparator that will be used to order this map.
162      *        If {@code null}, the {@linkplain Comparable natural
163      *        ordering} of the keys will be used.
164      */
165     public TreeMap(Comparator<? super K> comparator) {
166         this.comparator = comparator;
167     }
168 
169     /**
170      * Constructs a new tree map containing the same mappings as the given
171      * map, ordered according to the <em>natural ordering</em> of its keys.
172      * All keys inserted into the new map must implement the {@link
173      * Comparable} interface.  Furthermore, all such keys must be
174      * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
175      * a {@code ClassCastException} for any keys {@code k1} and
176      * {@code k2} in the map.  This method runs in n*log(n) time.
177      *
178      * @param  m the map whose mappings are to be placed in this map
179      * @throws ClassCastException if the keys in m are not {@link Comparable},
180      *         or are not mutually comparable
181      * @throws NullPointerException if the specified map is null
182      */
183     public TreeMap(Map<? extends K, ? extends V> m) {
184         comparator = null;
185         putAll(m);
186     }
187 
188     /**
189      * Constructs a new tree map containing the same mappings and
190      * using the same ordering as the specified sorted map.  This
191      * method runs in linear time.
192      *
193      * @param  m the sorted map whose mappings are to be placed in this map,
194      *         and whose comparator is to be used to sort this map
195      * @throws NullPointerException if the specified map is null
196      */
197     public TreeMap(SortedMap<K, ? extends V> m) {
198         comparator = m.comparator();
199         try {
200             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
201         } catch (java.io.IOException cannotHappen) {
202         } catch (ClassNotFoundException cannotHappen) {
203         }
204     }
205 
206 
207     // Query Operations
208 
209     /**
210      * Returns the number of key-value mappings in this map.
211      *
212      * @return the number of key-value mappings in this map
213      */
214     public int size() {
215         return size;
216     }
217 
218     /**
219      * Returns {@code true} if this map contains a mapping for the specified
220      * key.
221      *
222      * @param key key whose presence in this map is to be tested
223      * @return {@code true} if this map contains a mapping for the
224      *         specified key
225      * @throws ClassCastException if the specified key cannot be compared
226      *         with the keys currently in the map
227      * @throws NullPointerException if the specified key is null
228      *         and this map uses natural ordering, or its comparator
229      *         does not permit null keys
230      */
231     public boolean containsKey(Object key) {
232         return getEntry(key) != null;
233     }
234 
235     /**
236      * Returns {@code true} if this map maps one or more keys to the
237      * specified value.  More formally, returns {@code true} if and only if
238      * this map contains at least one mapping to a value {@code v} such
239      * that {@code (value==null ? v==null : value.equals(v))}.  This
240      * operation will probably require time linear in the map size for
241      * most implementations.
242      *
243      * @param value value whose presence in this map is to be tested
244      * @return {@code true} if a mapping to {@code value} exists;
245      *         {@code false} otherwise
246      * @since 1.2
247      */
248     public boolean containsValue(Object value) {
249         for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
250             if (valEquals(value, e.value))
251                 return true;
252         return false;
253     }
254 
255     /**
256      * Returns the value to which the specified key is mapped,
257      * or {@code null} if this map contains no mapping for the key.
258      *
259      * <p>More formally, if this map contains a mapping from a key
260      * {@code k} to a value {@code v} such that {@code key} compares
261      * equal to {@code k} according to the map's ordering, then this
262      * method returns {@code v}; otherwise it returns {@code null}.
263      * (There can be at most one such mapping.)
264      *
265      * <p>A return value of {@code null} does not <em>necessarily</em>
266      * indicate that the map contains no mapping for the key; it's also
267      * possible that the map explicitly maps the key to {@code null}.
268      * The {@link #containsKey containsKey} operation may be used to
269      * distinguish these two cases.
270      *
271      * @throws ClassCastException if the specified key cannot be compared
272      *         with the keys currently in the map
273      * @throws NullPointerException if the specified key is null
274      *         and this map uses natural ordering, or its comparator
275      *         does not permit null keys
276      */
277     public V get(Object key) {
278         Entry<K,V> p = getEntry(key);
279         return (p==null ? null : p.value);
280     }
281 
282     public Comparator<? super K> comparator() {
283         return comparator;
284     }
285 
286     /**
287      * @throws NoSuchElementException {@inheritDoc}
288      */
289     public K firstKey() {
290         return key(getFirstEntry());
291     }
292 
293     /**
294      * @throws NoSuchElementException {@inheritDoc}
295      */
296     public K lastKey() {
297         return key(getLastEntry());
298     }
299 
300     /**
301      * Copies all of the mappings from the specified map to this map.
302      * These mappings replace any mappings that this map had for any
303      * of the keys currently in the specified map.
304      *
305      * @param  map mappings to be stored in this map
306      * @throws ClassCastException if the class of a key or value in
307      *         the specified map prevents it from being stored in this map
308      * @throws NullPointerException if the specified map is null or
309      *         the specified map contains a null key and this map does not
310      *         permit null keys
311      */
312     public void putAll(Map<? extends K, ? extends V> map) {
313         int mapSize = map.size();
314         if (size==0 && mapSize!=0 && map instanceof SortedMap) {
315             Comparator<?> c = ((SortedMap<?,?>)map).comparator();
316             if (c == comparator || (c != null && c.equals(comparator))) {
317                 ++modCount;
318                 try {
319                     buildFromSorted(mapSize, map.entrySet().iterator(),
320                                     null, null);
321                 } catch (java.io.IOException cannotHappen) {
322                 } catch (ClassNotFoundException cannotHappen) {
323                 }
324                 return;
325             }
326         }
327         super.putAll(map);
328     }
329 
330     /**
331      * Returns this map's entry for the given key, or {@code null} if the map
332      * does not contain an entry for the key.
333      *
334      * @return this map's entry for the given key, or {@code null} if the map
335      *         does not contain an entry for the key
336      * @throws ClassCastException if the specified key cannot be compared
337      *         with the keys currently in the map
338      * @throws NullPointerException if the specified key is null
339      *         and this map uses natural ordering, or its comparator
340      *         does not permit null keys
341      */
342     final Entry<K,V> getEntry(Object key) {
343         // Offload comparator-based version for sake of performance
344         if (comparator != null)
345             return getEntryUsingComparator(key);
346         if (key == null)
347             throw new NullPointerException();
348         @SuppressWarnings("unchecked")
349             Comparable<? super K> k = (Comparable<? super K>) key;
350         Entry<K,V> p = root;
351         while (p != null) {
352             int cmp = k.compareTo(p.key);
353             if (cmp < 0)
354                 p = p.left;
355             else if (cmp > 0)
356                 p = p.right;
357             else
358                 return p;
359         }
360         return null;
361     }
362 
363     /**
364      * Version of getEntry using comparator. Split off from getEntry
365      * for performance. (This is not worth doing for most methods,
366      * that are less dependent on comparator performance, but is
367      * worthwhile here.)
368      */
369     final Entry<K,V> getEntryUsingComparator(Object key) {
370         @SuppressWarnings("unchecked")
371             K k = (K) key;
372         Comparator<? super K> cpr = comparator;
373         if (cpr != null) {
374             Entry<K,V> p = root;
375             while (p != null) {
376                 int cmp = cpr.compare(k, p.key);
377                 if (cmp < 0)
378                     p = p.left;
379                 else if (cmp > 0)
380                     p = p.right;
381                 else
382                     return p;
383             }
384         }
385         return null;
386     }
387 
388     /**
389      * Gets the entry corresponding to the specified key; if no such entry
390      * exists, returns the entry for the least key greater than the specified
391      * key; if no such entry exists (i.e., the greatest key in the Tree is less
392      * than the specified key), returns {@code null}.
393      */
394     final Entry<K,V> getCeilingEntry(K key) {
395         Entry<K,V> p = root;
396         while (p != null) {
397             int cmp = compare(key, p.key);
398             if (cmp < 0) {
399                 if (p.left != null)
400                     p = p.left;
401                 else
402                     return p;
403             } else if (cmp > 0) {
404                 if (p.right != null) {
405                     p = p.right;
406                 } else {
407                     Entry<K,V> parent = p.parent;
408                     Entry<K,V> ch = p;
409                     while (parent != null && ch == parent.right) {
410                         ch = parent;
411                         parent = parent.parent;
412                     }
413                     return parent;
414                 }
415             } else
416                 return p;
417         }
418         return null;
419     }
420 
421     /**
422      * Gets the entry corresponding to the specified key; if no such entry
423      * exists, returns the entry for the greatest key less than the specified
424      * key; if no such entry exists, returns {@code null}.
425      */
426     final Entry<K,V> getFloorEntry(K key) {
427         Entry<K,V> p = root;
428         while (p != null) {
429             int cmp = compare(key, p.key);
430             if (cmp > 0) {
431                 if (p.right != null)
432                     p = p.right;
433                 else
434                     return p;
435             } else if (cmp < 0) {
436                 if (p.left != null) {
437                     p = p.left;
438                 } else {
439                     Entry<K,V> parent = p.parent;
440                     Entry<K,V> ch = p;
441                     while (parent != null && ch == parent.left) {
442                         ch = parent;
443                         parent = parent.parent;
444                     }
445                     return parent;
446                 }
447             } else
448                 return p;
449 
450         }
451         return null;
452     }
453 
454     /**
455      * Gets the entry for the least key greater than the specified
456      * key; if no such entry exists, returns the entry for the least
457      * key greater than the specified key; if no such entry exists
458      * returns {@code null}.
459      */
460     final Entry<K,V> getHigherEntry(K key) {
461         Entry<K,V> p = root;
462         while (p != null) {
463             int cmp = compare(key, p.key);
464             if (cmp < 0) {
465                 if (p.left != null)
466                     p = p.left;
467                 else
468                     return p;
469             } else {
470                 if (p.right != null) {
471                     p = p.right;
472                 } else {
473                     Entry<K,V> parent = p.parent;
474                     Entry<K,V> ch = p;
475                     while (parent != null && ch == parent.right) {
476                         ch = parent;
477                         parent = parent.parent;
478                     }
479                     return parent;
480                 }
481             }
482         }
483         return null;
484     }
485 
486     /**
487      * Returns the entry for the greatest key less than the specified key; if
488      * no such entry exists (i.e., the least key in the Tree is greater than
489      * the specified key), returns {@code null}.
490      */
491     final Entry<K,V> getLowerEntry(K key) {
492         Entry<K,V> p = root;
493         while (p != null) {
494             int cmp = compare(key, p.key);
495             if (cmp > 0) {
496                 if (p.right != null)
497                     p = p.right;
498                 else
499                     return p;
500             } else {
501                 if (p.left != null) {
502                     p = p.left;
503                 } else {
504                     Entry<K,V> parent = p.parent;
505                     Entry<K,V> ch = p;
506                     while (parent != null && ch == parent.left) {
507                         ch = parent;
508                         parent = parent.parent;
509                     }
510                     return parent;
511                 }
512             }
513         }
514         return null;
515     }
516 
517     /**
518      * Associates the specified value with the specified key in this map.
519      * If the map previously contained a mapping for the key, the old
520      * value is replaced.
521      *
522      * @param key key with which the specified value is to be associated
523      * @param value value to be associated with the specified key
524      *
525      * @return the previous value associated with {@code key}, or
526      *         {@code null} if there was no mapping for {@code key}.
527      *         (A {@code null} return can also indicate that the map
528      *         previously associated {@code null} with {@code key}.)
529      * @throws ClassCastException if the specified key cannot be compared
530      *         with the keys currently in the map
531      * @throws NullPointerException if the specified key is null
532      *         and this map uses natural ordering, or its comparator
533      *         does not permit null keys
534      */
535     public V put(K key, V value) {
536         Entry<K,V> t = root;
537         if (t == null) {
538             compare(key, key); // type (and possibly null) check
539 
540             root = new Entry<>(key, value, null);
541             size = 1;
542             modCount++;
543             return null;
544         }
545         int cmp;
546         Entry<K,V> parent;
547         // split comparator and comparable paths
548         Comparator<? super K> cpr = comparator;
549         if (cpr != null) {
550             do {
551                 parent = t;
552                 cmp = cpr.compare(key, t.key);
553                 if (cmp < 0)
554                     t = t.left;
555                 else if (cmp > 0)
556                     t = t.right;
557                 else
558                     return t.setValue(value);
559             } while (t != null);
560         }
561         else {
562             if (key == null)
563                 throw new NullPointerException();
564             @SuppressWarnings("unchecked")
565                 Comparable<? super K> k = (Comparable<? super K>) key;
566             do {
567                 parent = t;
568                 cmp = k.compareTo(t.key);
569                 if (cmp < 0)
570                     t = t.left;
571                 else if (cmp > 0)
572                     t = t.right;
573                 else
574                     return t.setValue(value);
575             } while (t != null);
576         }
577         Entry<K,V> e = new Entry<>(key, value, parent);
578         if (cmp < 0)
579             parent.left = e;
580         else
581             parent.right = e;
582         fixAfterInsertion(e);
583         size++;
584         modCount++;
585         return null;
586     }
587 
588     /**
589      * Removes the mapping for this key from this TreeMap if present.
590      *
591      * @param  key key for which mapping should be removed
592      * @return the previous value associated with {@code key}, or
593      *         {@code null} if there was no mapping for {@code key}.
594      *         (A {@code null} return can also indicate that the map
595      *         previously associated {@code null} with {@code key}.)
596      * @throws ClassCastException if the specified key cannot be compared
597      *         with the keys currently in the map
598      * @throws NullPointerException if the specified key is null
599      *         and this map uses natural ordering, or its comparator
600      *         does not permit null keys
601      */
602     public V remove(Object key) {
603         Entry<K,V> p = getEntry(key);
604         if (p == null)
605             return null;
606 
607         V oldValue = p.value;
608         deleteEntry(p);
609         return oldValue;
610     }
611 
612     /**
613      * Removes all of the mappings from this map.
614      * The map will be empty after this call returns.
615      */
616     public void clear() {
617         modCount++;
618         size = 0;
619         root = null;
620     }
621 
622     /**
623      * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
624      * values themselves are not cloned.)
625      *
626      * @return a shallow copy of this map
627      */
628     public Object clone() {
629         TreeMap<?,?> clone;
630         try {
631             clone = (TreeMap<?,?>) super.clone();
632         } catch (CloneNotSupportedException e) {
633             throw new InternalError(e);
634         }
635 
636         // Put clone into "virgin" state (except for comparator)
637         clone.root = null;
638         clone.size = 0;
639         clone.modCount = 0;
640         clone.entrySet = null;
641         clone.navigableKeySet = null;
642         clone.descendingMap = null;
643 
644         // Initialize clone with our mappings
645         try {
646             clone.buildFromSorted(size, entrySet().iterator(), null, null);
647         } catch (java.io.IOException cannotHappen) {
648         } catch (ClassNotFoundException cannotHappen) {
649         }
650 
651         return clone;
652     }
653 
654     // NavigableMap API methods
655 
656     /**
657      * @since 1.6
658      */
659     public Map.Entry<K,V> firstEntry() {
660         return exportEntry(getFirstEntry());
661     }
662 
663     /**
664      * @since 1.6
665      */
666     public Map.Entry<K,V> lastEntry() {
667         return exportEntry(getLastEntry());
668     }
669 
670     /**
671      * @since 1.6
672      */
673     public Map.Entry<K,V> pollFirstEntry() {
674         Entry<K,V> p = getFirstEntry();
675         Map.Entry<K,V> result = exportEntry(p);
676         if (p != null)
677             deleteEntry(p);
678         return result;
679     }
680 
681     /**
682      * @since 1.6
683      */
684     public Map.Entry<K,V> pollLastEntry() {
685         Entry<K,V> p = getLastEntry();
686         Map.Entry<K,V> result = exportEntry(p);
687         if (p != null)
688             deleteEntry(p);
689         return result;
690     }
691 
692     /**
693      * @throws ClassCastException {@inheritDoc}
694      * @throws NullPointerException if the specified key is null
695      *         and this map uses natural ordering, or its comparator
696      *         does not permit null keys
697      * @since 1.6
698      */
699     public Map.Entry<K,V> lowerEntry(K key) {
700         return exportEntry(getLowerEntry(key));
701     }
702 
703     /**
704      * @throws ClassCastException {@inheritDoc}
705      * @throws NullPointerException if the specified key is null
706      *         and this map uses natural ordering, or its comparator
707      *         does not permit null keys
708      * @since 1.6
709      */
710     public K lowerKey(K key) {
711         return keyOrNull(getLowerEntry(key));
712     }
713 
714     /**
715      * @throws ClassCastException {@inheritDoc}
716      * @throws NullPointerException if the specified key is null
717      *         and this map uses natural ordering, or its comparator
718      *         does not permit null keys
719      * @since 1.6
720      */
721     public Map.Entry<K,V> floorEntry(K key) {
722         return exportEntry(getFloorEntry(key));
723     }
724 
725     /**
726      * @throws ClassCastException {@inheritDoc}
727      * @throws NullPointerException if the specified key is null
728      *         and this map uses natural ordering, or its comparator
729      *         does not permit null keys
730      * @since 1.6
731      */
732     public K floorKey(K key) {
733         return keyOrNull(getFloorEntry(key));
734     }
735 
736     /**
737      * @throws ClassCastException {@inheritDoc}
738      * @throws NullPointerException if the specified key is null
739      *         and this map uses natural ordering, or its comparator
740      *         does not permit null keys
741      * @since 1.6
742      */
743     public Map.Entry<K,V> ceilingEntry(K key) {
744         return exportEntry(getCeilingEntry(key));
745     }
746 
747     /**
748      * @throws ClassCastException {@inheritDoc}
749      * @throws NullPointerException if the specified key is null
750      *         and this map uses natural ordering, or its comparator
751      *         does not permit null keys
752      * @since 1.6
753      */
754     public K ceilingKey(K key) {
755         return keyOrNull(getCeilingEntry(key));
756     }
757 
758     /**
759      * @throws ClassCastException {@inheritDoc}
760      * @throws NullPointerException if the specified key is null
761      *         and this map uses natural ordering, or its comparator
762      *         does not permit null keys
763      * @since 1.6
764      */
765     public Map.Entry<K,V> higherEntry(K key) {
766         return exportEntry(getHigherEntry(key));
767     }
768 
769     /**
770      * @throws ClassCastException {@inheritDoc}
771      * @throws NullPointerException if the specified key is null
772      *         and this map uses natural ordering, or its comparator
773      *         does not permit null keys
774      * @since 1.6
775      */
776     public K higherKey(K key) {
777         return keyOrNull(getHigherEntry(key));
778     }
779 
780     // Views
781 
782     /**
783      * Fields initialized to contain an instance of the entry set view
784      * the first time this view is requested.  Views are stateless, so
785      * there's no reason to create more than one.
786      */
787     private transient EntrySet entrySet = null;
788     private transient KeySet<K> navigableKeySet = null;
789     private transient NavigableMap<K,V> descendingMap = null;
790 
791     /**
792      * Returns a {@link Set} view of the keys contained in this map.
793      *
794      * <p>The set's iterator returns the keys in ascending order.
795      * The set's spliterator is
796      * <em><a href="Spliterator.html#binding">late-binding</a></em>,
797      * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED}
798      * and {@link Spliterator#ORDERED} with an encounter order that is ascending
799      * key order.  The spliterator's comparator (see
800      * {@link java.util.Spliterator#getComparator()}) is {@code null} if
801      * the tree map's comparator (see {@link #comparator()}) is {@code null}.
802      * Otherwise, the spliterator's comparator is the same as or imposes the
803      * same total ordering as the tree map's comparator.
804      *
805      * <p>The set is backed by the map, so changes to the map are
806      * reflected in the set, and vice-versa.  If the map is modified
807      * while an iteration over the set is in progress (except through
808      * the iterator's own {@code remove} operation), the results of
809      * the iteration are undefined.  The set supports element removal,
810      * which removes the corresponding mapping from the map, via the
811      * {@code Iterator.remove}, {@code Set.remove},
812      * {@code removeAll}, {@code retainAll}, and {@code clear}
813      * operations.  It does not support the {@code add} or {@code addAll}
814      * operations.
815      */
816     public Set<K> keySet() {
817         return navigableKeySet();
818     }
819 
820     /**
821      * @since 1.6
822      */
823     public NavigableSet<K> navigableKeySet() {
824         KeySet<K> nks = navigableKeySet;
825         return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
826     }
827 
828     /**
829      * @since 1.6
830      */
831     public NavigableSet<K> descendingKeySet() {
832         return descendingMap().navigableKeySet();
833     }
834 
835     /**
836      * Returns a {@link Collection} view of the values contained in this map.
837      *
838      * <p>The collection's iterator returns the values in ascending order
839      * of the corresponding keys. The collection's spliterator is
840      * <em><a href="Spliterator.html#binding">late-binding</a></em>,
841      * <em>fail-fast</em>, and additionally reports {@link Spliterator#ORDERED}
842      * with an encounter order that is ascending order of the corresponding
843      * keys.
844      *
845      * <p>The collection is backed by the map, so changes to the map are
846      * reflected in the collection, and vice-versa.  If the map is
847      * modified while an iteration over the collection is in progress
848      * (except through the iterator's own {@code remove} operation),
849      * the results of the iteration are undefined.  The collection
850      * supports element removal, which removes the corresponding
851      * mapping from the map, via the {@code Iterator.remove},
852      * {@code Collection.remove}, {@code removeAll},
853      * {@code retainAll} and {@code clear} operations.  It does not
854      * support the {@code add} or {@code addAll} operations.
855      */
856     public Collection<V> values() {
857         Collection<V> vs = values;
858         return (vs != null) ? vs : (values = new Values());
859     }
860 
861     /**
862      * Returns a {@link Set} view of the mappings contained in this map.
863      *
864      * <p>The set's iterator returns the entries in ascending key order. The
865      * sets's spliterator is
866      * <em><a href="Spliterator.html#binding">late-binding</a></em>,
867      * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED} and
868      * {@link Spliterator#ORDERED} with an encounter order that is ascending key
869      * order.
870      *
871      * <p>The set is backed by the map, so changes to the map are
872      * reflected in the set, and vice-versa.  If the map is modified
873      * while an iteration over the set is in progress (except through
874      * the iterator's own {@code remove} operation, or through the
875      * {@code setValue} operation on a map entry returned by the
876      * iterator) the results of the iteration are undefined.  The set
877      * supports element removal, which removes the corresponding
878      * mapping from the map, via the {@code Iterator.remove},
879      * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
880      * {@code clear} operations.  It does not support the
881      * {@code add} or {@code addAll} operations.
882      */
883     public Set<Map.Entry<K,V>> entrySet() {
884         EntrySet es = entrySet;
885         return (es != null) ? es : (entrySet = new EntrySet());
886     }
887 
888     /**
889      * @since 1.6
890      */
891     public NavigableMap<K, V> descendingMap() {
892         NavigableMap<K, V> km = descendingMap;
893         return (km != null) ? km :
894             (descendingMap = new DescendingSubMap<>(this,
895                                                     true, null, true,
896                                                     true, null, true));
897     }
898 
899     /**
900      * @throws ClassCastException       {@inheritDoc}
901      * @throws NullPointerException if {@code fromKey} or {@code toKey} is
902      *         null and this map uses natural ordering, or its comparator
903      *         does not permit null keys
904      * @throws IllegalArgumentException {@inheritDoc}
905      * @since 1.6
906      */
907     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
908                                     K toKey,   boolean toInclusive) {
909         return new AscendingSubMap<>(this,
910                                      false, fromKey, fromInclusive,
911                                      false, toKey,   toInclusive);
912     }
913 
914     /**
915      * @throws ClassCastException       {@inheritDoc}
916      * @throws NullPointerException if {@code toKey} is null
917      *         and this map uses natural ordering, or its comparator
918      *         does not permit null keys
919      * @throws IllegalArgumentException {@inheritDoc}
920      * @since 1.6
921      */
922     public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
923         return new AscendingSubMap<>(this,
924                                      true,  null,  true,
925                                      false, toKey, inclusive);
926     }
927 
928     /**
929      * @throws ClassCastException       {@inheritDoc}
930      * @throws NullPointerException if {@code fromKey} is null
931      *         and this map uses natural ordering, or its comparator
932      *         does not permit null keys
933      * @throws IllegalArgumentException {@inheritDoc}
934      * @since 1.6
935      */
936     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
937         return new AscendingSubMap<>(this,
938                                      false, fromKey, inclusive,
939                                      true,  null,    true);
940     }
941 
942     /**
943      * @throws ClassCastException       {@inheritDoc}
944      * @throws NullPointerException if {@code fromKey} or {@code toKey} is
945      *         null and this map uses natural ordering, or its comparator
946      *         does not permit null keys
947      * @throws IllegalArgumentException {@inheritDoc}
948      */
949     public SortedMap<K,V> subMap(K fromKey, K toKey) {
950         return subMap(fromKey, true, toKey, false);
951     }
952 
953     /**
954      * @throws ClassCastException       {@inheritDoc}
955      * @throws NullPointerException if {@code toKey} is null
956      *         and this map uses natural ordering, or its comparator
957      *         does not permit null keys
958      * @throws IllegalArgumentException {@inheritDoc}
959      */
960     public SortedMap<K,V> headMap(K toKey) {
961         return headMap(toKey, false);
962     }
963 
964     /**
965      * @throws ClassCastException       {@inheritDoc}
966      * @throws NullPointerException if {@code fromKey} is null
967      *         and this map uses natural ordering, or its comparator
968      *         does not permit null keys
969      * @throws IllegalArgumentException {@inheritDoc}
970      */
971     public SortedMap<K,V> tailMap(K fromKey) {
972         return tailMap(fromKey, true);
973     }
974 
975     @Override
976     public boolean replace(K key, V oldValue, V newValue) {
977         Entry<K,V> p = getEntry(key);
978         if (p!=null && Objects.equals(oldValue, p.value)) {
979             p.value = newValue;
980             return true;
981         }
982         return false;
983     }
984 
985     @Override
986     public V replace(K key, V value) {
987         Entry<K,V> p = getEntry(key);
988         if (p!=null) {
989             V oldValue = p.value;
990             p.value = value;
991             return oldValue;
992         }
993         return null;
994     }
995 
996     @Override
997     public void forEach(BiConsumer<? super K, ? super V> action) {
998         Objects.requireNonNull(action);
999         int expectedModCount = modCount;
1000         for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
1001             action.accept(e.key, e.value);
1002 
1003             if (expectedModCount != modCount) {
1004                 throw new ConcurrentModificationException();
1005             }
1006         }
1007     }
1008 
1009     @Override
1010     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1011         Objects.requireNonNull(function);
1012         int expectedModCount = modCount;
1013 
1014         for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
1015             e.value = function.apply(e.key, e.value);
1016 
1017             if (expectedModCount != modCount) {
1018                 throw new ConcurrentModificationException();
1019             }
1020         }
1021     }
1022 
1023     // View class support
1024 
1025     class Values extends AbstractCollection<V> {
1026         public Iterator<V> iterator() {
1027             return new ValueIterator(getFirstEntry());
1028         }
1029 
1030         public int size() {
1031             return TreeMap.this.size();
1032         }
1033 
1034         public boolean contains(Object o) {
1035             return TreeMap.this.containsValue(o);
1036         }
1037 
1038         public boolean remove(Object o) {
1039             for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
1040                 if (valEquals(e.getValue(), o)) {
1041                     deleteEntry(e);
1042                     return true;
1043                 }
1044             }
1045             return false;
1046         }
1047 
1048         public void clear() {
1049             TreeMap.this.clear();
1050         }
1051 
1052         public Spliterator<V> spliterator() {
1053             return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
1054         }
1055     }
1056 
1057     class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1058         public Iterator<Map.Entry<K,V>> iterator() {
1059             return new EntryIterator(getFirstEntry());
1060         }
1061 
1062         public boolean contains(Object o) {
1063             if (!(o instanceof Map.Entry))
1064                 return false;
1065             Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1066             Object value = entry.getValue();
1067             Entry<K,V> p = getEntry(entry.getKey());
1068             return p != null && valEquals(p.getValue(), value);
1069         }
1070 
1071         public boolean remove(Object o) {
1072             if (!(o instanceof Map.Entry))
1073                 return false;
1074             Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1075             Object value = entry.getValue();
1076             Entry<K,V> p = getEntry(entry.getKey());
1077             if (p != null && valEquals(p.getValue(), value)) {
1078                 deleteEntry(p);
1079                 return true;
1080             }
1081             return false;
1082         }
1083 
1084         public int size() {
1085             return TreeMap.this.size();
1086         }
1087 
1088         public void clear() {
1089             TreeMap.this.clear();
1090         }
1091 
1092         public Spliterator<Map.Entry<K,V>> spliterator() {
1093             return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
1094         }
1095     }
1096 
1097     /*
1098      * Unlike Values and EntrySet, the KeySet class is static,
1099      * delegating to a NavigableMap to allow use by SubMaps, which
1100      * outweighs the ugliness of needing type-tests for the following
1101      * Iterator methods that are defined appropriately in main versus
1102      * submap classes.
1103      */
1104 
1105     Iterator<K> keyIterator() {
1106         return new KeyIterator(getFirstEntry());
1107     }
1108 
1109     Iterator<K> descendingKeyIterator() {
1110         return new DescendingKeyIterator(getLastEntry());
1111     }
1112 
1113     static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1114         private final NavigableMap<E, ?> m;
1115         KeySet(NavigableMap<E,?> map) { m = map; }
1116 
1117         public Iterator<E> iterator() {
1118             if (m instanceof TreeMap)
1119                 return ((TreeMap<E,?>)m).keyIterator();
1120             else
1121                 return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
1122         }
1123 
1124         public Iterator<E> descendingIterator() {
1125             if (m instanceof TreeMap)
1126                 return ((TreeMap<E,?>)m).descendingKeyIterator();
1127             else
1128                 return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
1129         }
1130 
1131         public int size() { return m.size(); }
1132         public boolean isEmpty() { return m.isEmpty(); }
1133         public boolean contains(Object o) { return m.containsKey(o); }
1134         public void clear() { m.clear(); }
1135         public E lower(E e) { return m.lowerKey(e); }
1136         public E floor(E e) { return m.floorKey(e); }
1137         public E ceiling(E e) { return m.ceilingKey(e); }
1138         public E higher(E e) { return m.higherKey(e); }
1139         public E first() { return m.firstKey(); }
1140         public E last() { return m.lastKey(); }
1141         public Comparator<? super E> comparator() { return m.comparator(); }
1142         public E pollFirst() {
1143             Map.Entry<E,?> e = m.pollFirstEntry();
1144             return (e == null) ? null : e.getKey();
1145         }
1146         public E pollLast() {
1147             Map.Entry<E,?> e = m.pollLastEntry();
1148             return (e == null) ? null : e.getKey();
1149         }
1150         public boolean remove(Object o) {
1151             int oldSize = size();
1152             m.remove(o);
1153             return size() != oldSize;
1154         }
1155         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1156                                       E toElement,   boolean toInclusive) {
1157             return new KeySet<>(m.subMap(fromElement, fromInclusive,
1158                                           toElement,   toInclusive));
1159         }
1160         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1161             return new KeySet<>(m.headMap(toElement, inclusive));
1162         }
1163         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1164             return new KeySet<>(m.tailMap(fromElement, inclusive));
1165         }
1166         public SortedSet<E> subSet(E fromElement, E toElement) {
1167             return subSet(fromElement, true, toElement, false);
1168         }
1169         public SortedSet<E> headSet(E toElement) {
1170             return headSet(toElement, false);
1171         }
1172         public SortedSet<E> tailSet(E fromElement) {
1173             return tailSet(fromElement, true);
1174         }
1175         public NavigableSet<E> descendingSet() {
1176             return new KeySet<>(m.descendingMap());
1177         }
1178 
1179         public Spliterator<E> spliterator() {
1180             return keySpliteratorFor(m);
1181         }
1182     }
1183 
1184     /**
1185      * Base class for TreeMap Iterators
1186      */
1187     abstract class PrivateEntryIterator<T> implements Iterator<T> {
1188         Entry<K,V> next;
1189         Entry<K,V> lastReturned;
1190         int expectedModCount;
1191 
1192         PrivateEntryIterator(Entry<K,V> first) {
1193             expectedModCount = modCount;
1194             lastReturned = null;
1195             next = first;
1196         }
1197 
1198         public final boolean hasNext() {
1199             return next != null;
1200         }
1201 
1202         final Entry<K,V> nextEntry() {
1203             Entry<K,V> e = next;
1204             if (e == null)
1205                 throw new NoSuchElementException();
1206             if (modCount != expectedModCount)
1207                 throw new ConcurrentModificationException();
1208             next = successor(e);
1209             lastReturned = e;
1210             return e;
1211         }
1212 
1213         final Entry<K,V> prevEntry() {
1214             Entry<K,V> e = next;
1215             if (e == null)
1216                 throw new NoSuchElementException();
1217             if (modCount != expectedModCount)
1218                 throw new ConcurrentModificationException();
1219             next = predecessor(e);
1220             lastReturned = e;
1221             return e;
1222         }
1223 
1224         public void remove() {
1225             if (lastReturned == null)
1226                 throw new IllegalStateException();
1227             if (modCount != expectedModCount)
1228                 throw new ConcurrentModificationException();
1229             // deleted entries are replaced by their successors
1230             if (lastReturned.left != null && lastReturned.right != null)
1231                 next = lastReturned;
1232             deleteEntry(lastReturned);
1233             expectedModCount = modCount;
1234             lastReturned = null;
1235         }
1236     }
1237 
1238     final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1239         EntryIterator(Entry<K,V> first) {
1240             super(first);
1241         }
1242         public Map.Entry<K,V> next() {
1243             return nextEntry();
1244         }
1245     }
1246 
1247     final class ValueIterator extends PrivateEntryIterator<V> {
1248         ValueIterator(Entry<K,V> first) {
1249             super(first);
1250         }
1251         public V next() {
1252             return nextEntry().value;
1253         }
1254     }
1255 
1256     final class KeyIterator extends PrivateEntryIterator<K> {
1257         KeyIterator(Entry<K,V> first) {
1258             super(first);
1259         }
1260         public K next() {
1261             return nextEntry().key;
1262         }
1263     }
1264 
1265     final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1266         DescendingKeyIterator(Entry<K,V> first) {
1267             super(first);
1268         }
1269         public K next() {
1270             return prevEntry().key;
1271         }
1272         public void remove() {
1273             if (lastReturned == null)
1274                 throw new IllegalStateException();
1275             if (modCount != expectedModCount)
1276                 throw new ConcurrentModificationException();
1277             deleteEntry(lastReturned);
1278             lastReturned = null;
1279             expectedModCount = modCount;
1280         }
1281     }
1282 
1283     // Little utilities
1284 
1285     /**
1286      * Compares two keys using the correct comparison method for this TreeMap.
1287      */
1288     @SuppressWarnings("unchecked")
1289     final int compare(Object k1, Object k2) {
1290         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1291             : comparator.compare((K)k1, (K)k2);
1292     }
1293 
1294     /**
1295      * Test two values for equality.  Differs from o1.equals(o2) only in
1296      * that it copes with {@code null} o1 properly.
1297      */
1298     static final boolean valEquals(Object o1, Object o2) {
1299         return (o1==null ? o2==null : o1.equals(o2));
1300     }
1301 
1302     /**
1303      * Return SimpleImmutableEntry for entry, or null if null
1304      */
1305     static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1306         return (e == null) ? null :
1307             new AbstractMap.SimpleImmutableEntry<>(e);
1308     }
1309 
1310     /**
1311      * Return key for entry, or null if null
1312      */
1313     static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1314         return (e == null) ? null : e.key;
1315     }
1316 
1317     /**
1318      * Returns the key corresponding to the specified Entry.
1319      * @throws NoSuchElementException if the Entry is null
1320      */
1321     static <K> K key(Entry<K,?> e) {
1322         if (e==null)
1323             throw new NoSuchElementException();
1324         return e.key;
1325     }
1326 
1327 
1328     // SubMaps
1329 
1330     /**
1331      * Dummy value serving as unmatchable fence key for unbounded
1332      * SubMapIterators
1333      */
1334     private static final Object UNBOUNDED = new Object();
1335 
1336     /**
1337      * @serial include
1338      */
1339     abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1340         implements NavigableMap<K,V>, java.io.Serializable {
1341         /**
1342          * The backing map.
1343          */
1344         final TreeMap<K,V> m;
1345 
1346         /**
1347          * Endpoints are represented as triples (fromStart, lo,
1348          * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1349          * true, then the low (absolute) bound is the start of the
1350          * backing map, and the other values are ignored. Otherwise,
1351          * if loInclusive is true, lo is the inclusive bound, else lo
1352          * is the exclusive bound. Similarly for the upper bound.
1353          */
1354         final K lo, hi;
1355         final boolean fromStart, toEnd;
1356         final boolean loInclusive, hiInclusive;
1357 
1358         NavigableSubMap(TreeMap<K,V> m,
1359                         boolean fromStart, K lo, boolean loInclusive,
1360                         boolean toEnd,     K hi, boolean hiInclusive) {
1361             if (!fromStart && !toEnd) {
1362                 if (m.compare(lo, hi) > 0)
1363                     throw new IllegalArgumentException("fromKey > toKey");
1364             } else {
1365                 if (!fromStart) // type check
1366                     m.compare(lo, lo);
1367                 if (!toEnd)
1368                     m.compare(hi, hi);
1369             }
1370 
1371             this.m = m;
1372             this.fromStart = fromStart;
1373             this.lo = lo;
1374             this.loInclusive = loInclusive;
1375             this.toEnd = toEnd;
1376             this.hi = hi;
1377             this.hiInclusive = hiInclusive;
1378         }
1379 
1380         // internal utilities
1381 
1382         final boolean tooLow(Object key) {
1383             if (!fromStart) {
1384                 int c = m.compare(key, lo);
1385                 if (c < 0 || (c == 0 && !loInclusive))
1386                     return true;
1387             }
1388             return false;
1389         }
1390 
1391         final boolean tooHigh(Object key) {
1392             if (!toEnd) {
1393                 int c = m.compare(key, hi);
1394                 if (c > 0 || (c == 0 && !hiInclusive))
1395                     return true;
1396             }
1397             return false;
1398         }
1399 
1400         final boolean inRange(Object key) {
1401             return !tooLow(key) && !tooHigh(key);
1402         }
1403 
1404         final boolean inClosedRange(Object key) {
1405             return (fromStart || m.compare(key, lo) >= 0)
1406                 && (toEnd || m.compare(hi, key) >= 0);
1407         }
1408 
1409         final boolean inRange(Object key, boolean inclusive) {
1410             return inclusive ? inRange(key) : inClosedRange(key);
1411         }
1412 
1413         /*
1414          * Absolute versions of relation operations.
1415          * Subclasses map to these using like-named "sub"
1416          * versions that invert senses for descending maps
1417          */
1418 
1419         final TreeMap.Entry<K,V> absLowest() {
1420             TreeMap.Entry<K,V> e =
1421                 (fromStart ?  m.getFirstEntry() :
1422                  (loInclusive ? m.getCeilingEntry(lo) :
1423                                 m.getHigherEntry(lo)));
1424             return (e == null || tooHigh(e.key)) ? null : e;
1425         }
1426 
1427         final TreeMap.Entry<K,V> absHighest() {
1428             TreeMap.Entry<K,V> e =
1429                 (toEnd ?  m.getLastEntry() :
1430                  (hiInclusive ?  m.getFloorEntry(hi) :
1431                                  m.getLowerEntry(hi)));
1432             return (e == null || tooLow(e.key)) ? null : e;
1433         }
1434 
1435         final TreeMap.Entry<K,V> absCeiling(K key) {
1436             if (tooLow(key))
1437                 return absLowest();
1438             TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1439             return (e == null || tooHigh(e.key)) ? null : e;
1440         }
1441 
1442         final TreeMap.Entry<K,V> absHigher(K key) {
1443             if (tooLow(key))
1444                 return absLowest();
1445             TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1446             return (e == null || tooHigh(e.key)) ? null : e;
1447         }
1448 
1449         final TreeMap.Entry<K,V> absFloor(K key) {
1450             if (tooHigh(key))
1451                 return absHighest();
1452             TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1453             return (e == null || tooLow(e.key)) ? null : e;
1454         }
1455 
1456         final TreeMap.Entry<K,V> absLower(K key) {
1457             if (tooHigh(key))
1458                 return absHighest();
1459             TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1460             return (e == null || tooLow(e.key)) ? null : e;
1461         }
1462 
1463         /** Returns the absolute high fence for ascending traversal */
1464         final TreeMap.Entry<K,V> absHighFence() {
1465             return (toEnd ? null : (hiInclusive ?
1466                                     m.getHigherEntry(hi) :
1467                                     m.getCeilingEntry(hi)));
1468         }
1469 
1470         /** Return the absolute low fence for descending traversal  */
1471         final TreeMap.Entry<K,V> absLowFence() {
1472             return (fromStart ? null : (loInclusive ?
1473                                         m.getLowerEntry(lo) :
1474                                         m.getFloorEntry(lo)));
1475         }
1476 
1477         // Abstract methods defined in ascending vs descending classes
1478         // These relay to the appropriate absolute versions
1479 
1480         abstract TreeMap.Entry<K,V> subLowest();
1481         abstract TreeMap.Entry<K,V> subHighest();
1482         abstract TreeMap.Entry<K,V> subCeiling(K key);
1483         abstract TreeMap.Entry<K,V> subHigher(K key);
1484         abstract TreeMap.Entry<K,V> subFloor(K key);
1485         abstract TreeMap.Entry<K,V> subLower(K key);
1486 
1487         /** Returns ascending iterator from the perspective of this submap */
1488         abstract Iterator<K> keyIterator();
1489 
1490         abstract Spliterator<K> keySpliterator();
1491 
1492         /** Returns descending iterator from the perspective of this submap */
1493         abstract Iterator<K> descendingKeyIterator();
1494 
1495         // public methods
1496 
1497         public boolean isEmpty() {
1498             return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1499         }
1500 
1501         public int size() {
1502             return (fromStart && toEnd) ? m.size() : entrySet().size();
1503         }
1504 
1505         public final boolean containsKey(Object key) {
1506             return inRange(key) && m.containsKey(key);
1507         }
1508 
1509         public final V put(K key, V value) {
1510             if (!inRange(key))
1511                 throw new IllegalArgumentException("key out of range");
1512             return m.put(key, value);
1513         }
1514 
1515         public final V get(Object key) {
1516             return !inRange(key) ? null :  m.get(key);
1517         }
1518 
1519         public final V remove(Object key) {
1520             return !inRange(key) ? null : m.remove(key);
1521         }
1522 
1523         public final Map.Entry<K,V> ceilingEntry(K key) {
1524             return exportEntry(subCeiling(key));
1525         }
1526 
1527         public final K ceilingKey(K key) {
1528             return keyOrNull(subCeiling(key));
1529         }
1530 
1531         public final Map.Entry<K,V> higherEntry(K key) {
1532             return exportEntry(subHigher(key));
1533         }
1534 
1535         public final K higherKey(K key) {
1536             return keyOrNull(subHigher(key));
1537         }
1538 
1539         public final Map.Entry<K,V> floorEntry(K key) {
1540             return exportEntry(subFloor(key));
1541         }
1542 
1543         public final K floorKey(K key) {
1544             return keyOrNull(subFloor(key));
1545         }
1546 
1547         public final Map.Entry<K,V> lowerEntry(K key) {
1548             return exportEntry(subLower(key));
1549         }
1550 
1551         public final K lowerKey(K key) {
1552             return keyOrNull(subLower(key));
1553         }
1554 
1555         public final K firstKey() {
1556             return key(subLowest());
1557         }
1558 
1559         public final K lastKey() {
1560             return key(subHighest());
1561         }
1562 
1563         public final Map.Entry<K,V> firstEntry() {
1564             return exportEntry(subLowest());
1565         }
1566 
1567         public final Map.Entry<K,V> lastEntry() {
1568             return exportEntry(subHighest());
1569         }
1570 
1571         public final Map.Entry<K,V> pollFirstEntry() {
1572             TreeMap.Entry<K,V> e = subLowest();
1573             Map.Entry<K,V> result = exportEntry(e);
1574             if (e != null)
1575                 m.deleteEntry(e);
1576             return result;
1577         }
1578 
1579         public final Map.Entry<K,V> pollLastEntry() {
1580             TreeMap.Entry<K,V> e = subHighest();
1581             Map.Entry<K,V> result = exportEntry(e);
1582             if (e != null)
1583                 m.deleteEntry(e);
1584             return result;
1585         }
1586 
1587         // Views
1588         transient NavigableMap<K,V> descendingMapView = null;
1589         transient EntrySetView entrySetView = null;
1590         transient KeySet<K> navigableKeySetView = null;
1591 
1592         public final NavigableSet<K> navigableKeySet() {
1593             KeySet<K> nksv = navigableKeySetView;
1594             return (nksv != null) ? nksv :
1595                 (navigableKeySetView = new TreeMap.KeySet<>(this));
1596         }
1597 
1598         public final Set<K> keySet() {
1599             return navigableKeySet();
1600         }
1601 
1602         public NavigableSet<K> descendingKeySet() {
1603             return descendingMap().navigableKeySet();
1604         }
1605 
1606         public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1607             return subMap(fromKey, true, toKey, false);
1608         }
1609 
1610         public final SortedMap<K,V> headMap(K toKey) {
1611             return headMap(toKey, false);
1612         }
1613 
1614         public final SortedMap<K,V> tailMap(K fromKey) {
1615             return tailMap(fromKey, true);
1616         }
1617 
1618         // View classes
1619 
1620         abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1621             private transient int size = -1, sizeModCount;
1622 
1623             public int size() {
1624                 if (fromStart && toEnd)
1625                     return m.size();
1626                 if (size == -1 || sizeModCount != m.modCount) {
1627                     sizeModCount = m.modCount;
1628                     size = 0;
1629                     Iterator<?> i = iterator();
1630                     while (i.hasNext()) {
1631                         size++;
1632                         i.next();
1633                     }
1634                 }
1635                 return size;
1636             }
1637 
1638             public boolean isEmpty() {
1639                 TreeMap.Entry<K,V> n = absLowest();
1640                 return n == null || tooHigh(n.key);
1641             }
1642 
1643             public boolean contains(Object o) {
1644                 if (!(o instanceof Map.Entry))
1645                     return false;
1646                 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1647                 Object key = entry.getKey();
1648                 if (!inRange(key))
1649                     return false;
1650                 TreeMap.Entry<?,?> node = m.getEntry(key);
1651                 return node != null &&
1652                     valEquals(node.getValue(), entry.getValue());
1653             }
1654 
1655             public boolean remove(Object o) {
1656                 if (!(o instanceof Map.Entry))
1657                     return false;
1658                 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1659                 Object key = entry.getKey();
1660                 if (!inRange(key))
1661                     return false;
1662                 TreeMap.Entry<K,V> node = m.getEntry(key);
1663                 if (node!=null && valEquals(node.getValue(),
1664                                             entry.getValue())) {
1665                     m.deleteEntry(node);
1666                     return true;
1667                 }
1668                 return false;
1669             }
1670         }
1671 
1672         /**
1673          * Iterators for SubMaps
1674          */
1675         abstract class SubMapIterator<T> implements Iterator<T> {
1676             TreeMap.Entry<K,V> lastReturned;
1677             TreeMap.Entry<K,V> next;
1678             final Object fenceKey;
1679             int expectedModCount;
1680 
1681             SubMapIterator(TreeMap.Entry<K,V> first,
1682                            TreeMap.Entry<K,V> fence) {
1683                 expectedModCount = m.modCount;
1684                 lastReturned = null;
1685                 next = first;
1686                 fenceKey = fence == null ? UNBOUNDED : fence.key;
1687             }
1688 
1689             public final boolean hasNext() {
1690                 return next != null && next.key != fenceKey;
1691             }
1692 
1693             final TreeMap.Entry<K,V> nextEntry() {
1694                 TreeMap.Entry<K,V> e = next;
1695                 if (e == null || e.key == fenceKey)
1696                     throw new NoSuchElementException();
1697                 if (m.modCount != expectedModCount)
1698                     throw new ConcurrentModificationException();
1699                 next = successor(e);
1700                 lastReturned = e;
1701                 return e;
1702             }
1703 
1704             final TreeMap.Entry<K,V> prevEntry() {
1705                 TreeMap.Entry<K,V> e = next;
1706                 if (e == null || e.key == fenceKey)
1707                     throw new NoSuchElementException();
1708                 if (m.modCount != expectedModCount)
1709                     throw new ConcurrentModificationException();
1710                 next = predecessor(e);
1711                 lastReturned = e;
1712                 return e;
1713             }
1714 
1715             final void removeAscending() {
1716                 if (lastReturned == null)
1717                     throw new IllegalStateException();
1718                 if (m.modCount != expectedModCount)
1719                     throw new ConcurrentModificationException();
1720                 // deleted entries are replaced by their successors
1721                 if (lastReturned.left != null && lastReturned.right != null)
1722                     next = lastReturned;
1723                 m.deleteEntry(lastReturned);
1724                 lastReturned = null;
1725                 expectedModCount = m.modCount;
1726             }
1727 
1728             final void removeDescending() {
1729                 if (lastReturned == null)
1730                     throw new IllegalStateException();
1731                 if (m.modCount != expectedModCount)
1732                     throw new ConcurrentModificationException();
1733                 m.deleteEntry(lastReturned);
1734                 lastReturned = null;
1735                 expectedModCount = m.modCount;
1736             }
1737 
1738         }
1739 
1740         final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1741             SubMapEntryIterator(TreeMap.Entry<K,V> first,
1742                                 TreeMap.Entry<K,V> fence) {
1743                 super(first, fence);
1744             }
1745             public Map.Entry<K,V> next() {
1746                 return nextEntry();
1747             }
1748             public void remove() {
1749                 removeAscending();
1750             }
1751         }
1752 
1753         final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1754             DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1755                                           TreeMap.Entry<K,V> fence) {
1756                 super(last, fence);
1757             }
1758 
1759             public Map.Entry<K,V> next() {
1760                 return prevEntry();
1761             }
1762             public void remove() {
1763                 removeDescending();
1764             }
1765         }
1766 
1767         // Implement minimal Spliterator as KeySpliterator backup
1768         final class SubMapKeyIterator extends SubMapIterator<K>
1769             implements Spliterator<K> {
1770             SubMapKeyIterator(TreeMap.Entry<K,V> first,
1771                               TreeMap.Entry<K,V> fence) {
1772                 super(first, fence);
1773             }
1774             public K next() {
1775                 return nextEntry().key;
1776             }
1777             public void remove() {
1778                 removeAscending();
1779             }
1780             public Spliterator<K> trySplit() {
1781                 return null;
1782             }
1783             public void forEachRemaining(Consumer<? super K> action) {
1784                 while (hasNext())
1785                     action.accept(next());
1786             }
1787             public boolean tryAdvance(Consumer<? super K> action) {
1788                 if (hasNext()) {
1789                     action.accept(next());
1790                     return true;
1791                 }
1792                 return false;
1793             }
1794             public long estimateSize() {
1795                 return Long.MAX_VALUE;
1796             }
1797             public int characteristics() {
1798                 return Spliterator.DISTINCT | Spliterator.ORDERED |
1799                     Spliterator.SORTED;
1800             }
1801             public final Comparator<? super K>  getComparator() {
1802                 return NavigableSubMap.this.comparator();
1803             }
1804         }
1805 
1806         final class DescendingSubMapKeyIterator extends SubMapIterator<K>
1807             implements Spliterator<K> {
1808             DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1809                                         TreeMap.Entry<K,V> fence) {
1810                 super(last, fence);
1811             }
1812             public K next() {
1813                 return prevEntry().key;
1814             }
1815             public void remove() {
1816                 removeDescending();
1817             }
1818             public Spliterator<K> trySplit() {
1819                 return null;
1820             }
1821             public void forEachRemaining(Consumer<? super K> action) {
1822                 while (hasNext())
1823                     action.accept(next());
1824             }
1825             public boolean tryAdvance(Consumer<? super K> action) {
1826                 if (hasNext()) {
1827                     action.accept(next());
1828                     return true;
1829                 }
1830                 return false;
1831             }
1832             public long estimateSize() {
1833                 return Long.MAX_VALUE;
1834             }
1835             public int characteristics() {
1836                 return Spliterator.DISTINCT | Spliterator.ORDERED;
1837             }
1838         }
1839     }
1840 
1841     /**
1842      * @serial include
1843      */
1844     static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1845         private static final long serialVersionUID = 912986545866124060L;
1846 
1847         AscendingSubMap(TreeMap<K,V> m,
1848                         boolean fromStart, K lo, boolean loInclusive,
1849                         boolean toEnd,     K hi, boolean hiInclusive) {
1850             super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1851         }
1852 
1853         public Comparator<? super K> comparator() {
1854             return m.comparator();
1855         }
1856 
1857         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1858                                         K toKey,   boolean toInclusive) {
1859             if (!inRange(fromKey, fromInclusive))
1860                 throw new IllegalArgumentException("fromKey out of range");
1861             if (!inRange(toKey, toInclusive))
1862                 throw new IllegalArgumentException("toKey out of range");
1863             return new AscendingSubMap<>(m,
1864                                          false, fromKey, fromInclusive,
1865                                          false, toKey,   toInclusive);
1866         }
1867 
1868         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1869             if (!inRange(toKey, inclusive))
1870                 throw new IllegalArgumentException("toKey out of range");
1871             return new AscendingSubMap<>(m,
1872                                          fromStart, lo,    loInclusive,
1873                                          false,     toKey, inclusive);
1874         }
1875 
1876         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1877             if (!inRange(fromKey, inclusive))
1878                 throw new IllegalArgumentException("fromKey out of range");
1879             return new AscendingSubMap<>(m,
1880                                          false, fromKey, inclusive,
1881                                          toEnd, hi,      hiInclusive);
1882         }
1883 
1884         public NavigableMap<K,V> descendingMap() {
1885             NavigableMap<K,V> mv = descendingMapView;
1886             return (mv != null) ? mv :
1887                 (descendingMapView =
1888                  new DescendingSubMap<>(m,
1889                                         fromStart, lo, loInclusive,
1890                                         toEnd,     hi, hiInclusive));
1891         }
1892 
1893         Iterator<K> keyIterator() {
1894             return new SubMapKeyIterator(absLowest(), absHighFence());
1895         }
1896 
1897         Spliterator<K> keySpliterator() {
1898             return new SubMapKeyIterator(absLowest(), absHighFence());
1899         }
1900 
1901         Iterator<K> descendingKeyIterator() {
1902             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1903         }
1904 
1905         final class AscendingEntrySetView extends EntrySetView {
1906             public Iterator<Map.Entry<K,V>> iterator() {
1907                 return new SubMapEntryIterator(absLowest(), absHighFence());
1908             }
1909         }
1910 
1911         public Set<Map.Entry<K,V>> entrySet() {
1912             EntrySetView es = entrySetView;
1913             return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
1914         }
1915 
1916         TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1917         TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1918         TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1919         TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1920         TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1921         TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1922     }
1923 
1924     /**
1925      * @serial include
1926      */
1927     static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1928         private static final long serialVersionUID = 912986545866120460L;
1929         DescendingSubMap(TreeMap<K,V> m,
1930                         boolean fromStart, K lo, boolean loInclusive,
1931                         boolean toEnd,     K hi, boolean hiInclusive) {
1932             super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1933         }
1934 
1935         private final Comparator<? super K> reverseComparator =
1936             Collections.reverseOrder(m.comparator);
1937 
1938         public Comparator<? super K> comparator() {
1939             return reverseComparator;
1940         }
1941 
1942         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1943                                         K toKey,   boolean toInclusive) {
1944             if (!inRange(fromKey, fromInclusive))
1945                 throw new IllegalArgumentException("fromKey out of range");
1946             if (!inRange(toKey, toInclusive))
1947                 throw new IllegalArgumentException("toKey out of range");
1948             return new DescendingSubMap<>(m,
1949                                           false, toKey,   toInclusive,
1950                                           false, fromKey, fromInclusive);
1951         }
1952 
1953         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1954             if (!inRange(toKey, inclusive))
1955                 throw new IllegalArgumentException("toKey out of range");
1956             return new DescendingSubMap<>(m,
1957                                           false, toKey, inclusive,
1958                                           toEnd, hi,    hiInclusive);
1959         }
1960 
1961         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1962             if (!inRange(fromKey, inclusive))
1963                 throw new IllegalArgumentException("fromKey out of range");
1964             return new DescendingSubMap<>(m,
1965                                           fromStart, lo, loInclusive,
1966                                           false, fromKey, inclusive);
1967         }
1968 
1969         public NavigableMap<K,V> descendingMap() {
1970             NavigableMap<K,V> mv = descendingMapView;
1971             return (mv != null) ? mv :
1972                 (descendingMapView =
1973                  new AscendingSubMap<>(m,
1974                                        fromStart, lo, loInclusive,
1975                                        toEnd,     hi, hiInclusive));
1976         }
1977 
1978         Iterator<K> keyIterator() {
1979             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1980         }
1981 
1982         Spliterator<K> keySpliterator() {
1983             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1984         }
1985 
1986         Iterator<K> descendingKeyIterator() {
1987             return new SubMapKeyIterator(absLowest(), absHighFence());
1988         }
1989 
1990         final class DescendingEntrySetView extends EntrySetView {
1991             public Iterator<Map.Entry<K,V>> iterator() {
1992                 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1993             }
1994         }
1995 
1996         public Set<Map.Entry<K,V>> entrySet() {
1997             EntrySetView es = entrySetView;
1998             return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
1999         }
2000 
2001         TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
2002         TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
2003         TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
2004         TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
2005         TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
2006         TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
2007     }
2008 
2009     /**
2010      * This class exists solely for the sake of serialization
2011      * compatibility with previous releases of TreeMap that did not
2012      * support NavigableMap.  It translates an old-version SubMap into
2013      * a new-version AscendingSubMap. This class is never otherwise
2014      * used.
2015      *
2016      * @serial include
2017      */
2018     private class SubMap extends AbstractMap<K,V>
2019         implements SortedMap<K,V>, java.io.Serializable {
2020         private static final long serialVersionUID = -6520786458950516097L;
2021         private boolean fromStart = false, toEnd = false;
2022         private K fromKey, toKey;
2023         private Object readResolve() {
2024             return new AscendingSubMap<>(TreeMap.this,
2025                                          fromStart, fromKey, true,
2026                                          toEnd, toKey, false);
2027         }
2028         public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2029         public K lastKey() { throw new InternalError(); }
2030         public K firstKey() { throw new InternalError(); }
2031         public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2032         public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2033         public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2034         public Comparator<? super K> comparator() { throw new InternalError(); }
2035     }
2036 
2037 
2038     // Red-black mechanics
2039 
2040     private static final boolean RED   = false;
2041     private static final boolean BLACK = true;
2042 
2043     /**
2044      * Node in the Tree.  Doubles as a means to pass key-value pairs back to
2045      * user (see Map.Entry).
2046      */
2047 
2048     static final class Entry<K,V> implements Map.Entry<K,V> {
2049         K key;
2050         V value;
2051         Entry<K,V> left = null;
2052         Entry<K,V> right = null;
2053         Entry<K,V> parent;
2054         boolean color = BLACK;
2055 
2056         /**
2057          * Make a new cell with given key, value, and parent, and with
2058          * {@code null} child links, and BLACK color.
2059          */
2060         Entry(K key, V value, Entry<K,V> parent) {
2061             this.key = key;
2062             this.value = value;
2063             this.parent = parent;
2064         }
2065 
2066         /**
2067          * Returns the key.
2068          *
2069          * @return the key
2070          */
2071         public K getKey() {
2072             return key;
2073         }
2074 
2075         /**
2076          * Returns the value associated with the key.
2077          *
2078          * @return the value associated with the key
2079          */
2080         public V getValue() {
2081             return value;
2082         }
2083 
2084         /**
2085          * Replaces the value currently associated with the key with the given
2086          * value.
2087          *
2088          * @return the value associated with the key before this method was
2089          *         called
2090          */
2091         public V setValue(V value) {
2092             V oldValue = this.value;
2093             this.value = value;
2094             return oldValue;
2095         }
2096 
2097         public boolean equals(Object o) {
2098             if (!(o instanceof Map.Entry))
2099                 return false;
2100             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2101 
2102             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
2103         }
2104 
2105         public int hashCode() {
2106             int keyHash = (key==null ? 0 : key.hashCode());
2107             int valueHash = (value==null ? 0 : value.hashCode());
2108             return keyHash ^ valueHash;
2109         }
2110 
2111         public String toString() {
2112             return key + "=" + value;
2113         }
2114     }
2115 
2116     /**
2117      * Returns the first Entry in the TreeMap (according to the TreeMap's
2118      * key-sort function).  Returns null if the TreeMap is empty.
2119      */
2120     final Entry<K,V> getFirstEntry() {
2121         Entry<K,V> p = root;
2122         if (p != null)
2123             while (p.left != null)
2124                 p = p.left;
2125         return p;
2126     }
2127 
2128     /**
2129      * Returns the last Entry in the TreeMap (according to the TreeMap's
2130      * key-sort function).  Returns null if the TreeMap is empty.
2131      */
2132     final Entry<K,V> getLastEntry() {
2133         Entry<K,V> p = root;
2134         if (p != null)
2135             while (p.right != null)
2136                 p = p.right;
2137         return p;
2138     }
2139 
2140     /**
2141      * Returns the successor of the specified Entry, or null if no such.
2142      */
2143     static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2144         if (t == null)
2145             return null;
2146         else if (t.right != null) {
2147             Entry<K,V> p = t.right;
2148             while (p.left != null)
2149                 p = p.left;
2150             return p;
2151         } else {
2152             Entry<K,V> p = t.parent;
2153             Entry<K,V> ch = t;
2154             while (p != null && ch == p.right) {
2155                 ch = p;
2156                 p = p.parent;
2157             }
2158             return p;
2159         }
2160     }
2161 
2162     /**
2163      * Returns the predecessor of the specified Entry, or null if no such.
2164      */
2165     static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2166         if (t == null)
2167             return null;
2168         else if (t.left != null) {
2169             Entry<K,V> p = t.left;
2170             while (p.right != null)
2171                 p = p.right;
2172             return p;
2173         } else {
2174             Entry<K,V> p = t.parent;
2175             Entry<K,V> ch = t;
2176             while (p != null && ch == p.left) {
2177                 ch = p;
2178                 p = p.parent;
2179             }
2180             return p;
2181         }
2182     }
2183 
2184     /**
2185      * Balancing operations.
2186      *
2187      * Implementations of rebalancings during insertion and deletion are
2188      * slightly different than the CLR version.  Rather than using dummy
2189      * nilnodes, we use a set of accessors that deal properly with null.  They
2190      * are used to avoid messiness surrounding nullness checks in the main
2191      * algorithms.
2192      */
2193 
2194     private static <K,V> boolean colorOf(Entry<K,V> p) {
2195         return (p == null ? BLACK : p.color);
2196     }
2197 
2198     private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
2199         return (p == null ? null: p.parent);
2200     }
2201 
2202     private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2203         if (p != null)
2204             p.color = c;
2205     }
2206 
2207     private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
2208         return (p == null) ? null: p.left;
2209     }
2210 
2211     private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
2212         return (p == null) ? null: p.right;
2213     }
2214 
2215     /** From CLR */
2216     private void rotateLeft(Entry<K,V> p) {
2217         if (p != null) {
2218             Entry<K,V> r = p.right;
2219             p.right = r.left;
2220             if (r.left != null)
2221                 r.left.parent = p;
2222             r.parent = p.parent;
2223             if (p.parent == null)
2224                 root = r;
2225             else if (p.parent.left == p)
2226                 p.parent.left = r;
2227             else
2228                 p.parent.right = r;
2229             r.left = p;
2230             p.parent = r;
2231         }
2232     }
2233 
2234     /** From CLR */
2235     private void rotateRight(Entry<K,V> p) {
2236         if (p != null) {
2237             Entry<K,V> l = p.left;
2238             p.left = l.right;
2239             if (l.right != null) l.right.parent = p;
2240             l.parent = p.parent;
2241             if (p.parent == null)
2242                 root = l;
2243             else if (p.parent.right == p)
2244                 p.parent.right = l;
2245             else p.parent.left = l;
2246             l.right = p;
2247             p.parent = l;
2248         }
2249     }
2250 
2251     /** From CLR */
2252     private void fixAfterInsertion(Entry<K,V> x) {
2253         x.color = RED;
2254 
2255         while (x != null && x != root && x.parent.color == RED) {
2256             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2257                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
2258                 if (colorOf(y) == RED) {
2259                     setColor(parentOf(x), BLACK);
2260                     setColor(y, BLACK);
2261                     setColor(parentOf(parentOf(x)), RED);
2262                     x = parentOf(parentOf(x));
2263                 } else {
2264                     if (x == rightOf(parentOf(x))) {
2265                         x = parentOf(x);
2266                         rotateLeft(x);
2267                     }
2268                     setColor(parentOf(x), BLACK);
2269                     setColor(parentOf(parentOf(x)), RED);
2270                     rotateRight(parentOf(parentOf(x)));
2271                 }
2272             } else {
2273                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
2274                 if (colorOf(y) == RED) {
2275                     setColor(parentOf(x), BLACK);
2276                     setColor(y, BLACK);
2277                     setColor(parentOf(parentOf(x)), RED);
2278                     x = parentOf(parentOf(x));
2279                 } else {
2280                     if (x == leftOf(parentOf(x))) {
2281                         x = parentOf(x);
2282                         rotateRight(x);
2283                     }
2284                     setColor(parentOf(x), BLACK);
2285                     setColor(parentOf(parentOf(x)), RED);
2286                     rotateLeft(parentOf(parentOf(x)));
2287                 }
2288             }
2289         }
2290         root.color = BLACK;
2291     }
2292 
2293     /**
2294      * Delete node p, and then rebalance the tree.
2295      */
2296     private void deleteEntry(Entry<K,V> p) {
2297         modCount++;
2298         size--;
2299 
2300         // If strictly internal, copy successor's element to p and then make p
2301         // point to successor.
2302         if (p.left != null && p.right != null) {
2303             Entry<K,V> s = successor(p);
2304             p.key = s.key;
2305             p.value = s.value;
2306             p = s;
2307         } // p has 2 children
2308 
2309         // Start fixup at replacement node, if it exists.
2310         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2311 
2312         if (replacement != null) {
2313             // Link replacement to parent
2314             replacement.parent = p.parent;
2315             if (p.parent == null)
2316                 root = replacement;
2317             else if (p == p.parent.left)
2318                 p.parent.left  = replacement;
2319             else
2320                 p.parent.right = replacement;
2321 
2322             // Null out links so they are OK to use by fixAfterDeletion.
2323             p.left = p.right = p.parent = null;
2324 
2325             // Fix replacement
2326             if (p.color == BLACK)
2327                 fixAfterDeletion(replacement);
2328         } else if (p.parent == null) { // return if we are the only node.
2329             root = null;
2330         } else { //  No children. Use self as phantom replacement and unlink.
2331             if (p.color == BLACK)
2332                 fixAfterDeletion(p);
2333 
2334             if (p.parent != null) {
2335                 if (p == p.parent.left)
2336                     p.parent.left = null;
2337                 else if (p == p.parent.right)
2338                     p.parent.right = null;
2339                 p.parent = null;
2340             }
2341         }
2342     }
2343 
2344     /** From CLR */
2345     private void fixAfterDeletion(Entry<K,V> x) {
2346         while (x != root && colorOf(x) == BLACK) {
2347             if (x == leftOf(parentOf(x))) {
2348                 Entry<K,V> sib = rightOf(parentOf(x));
2349 
2350                 if (colorOf(sib) == RED) {
2351                     setColor(sib, BLACK);
2352                     setColor(parentOf(x), RED);
2353                     rotateLeft(parentOf(x));
2354                     sib = rightOf(parentOf(x));
2355                 }
2356 
2357                 if (colorOf(leftOf(sib))  == BLACK &&
2358                     colorOf(rightOf(sib)) == BLACK) {
2359                     setColor(sib, RED);
2360                     x = parentOf(x);
2361                 } else {
2362                     if (colorOf(rightOf(sib)) == BLACK) {
2363                         setColor(leftOf(sib), BLACK);
2364                         setColor(sib, RED);
2365                         rotateRight(sib);
2366                         sib = rightOf(parentOf(x));
2367                     }
2368                     setColor(sib, colorOf(parentOf(x)));
2369                     setColor(parentOf(x), BLACK);
2370                     setColor(rightOf(sib), BLACK);
2371                     rotateLeft(parentOf(x));
2372                     x = root;
2373                 }
2374             } else { // symmetric
2375                 Entry<K,V> sib = leftOf(parentOf(x));
2376 
2377                 if (colorOf(sib) == RED) {
2378                     setColor(sib, BLACK);
2379                     setColor(parentOf(x), RED);
2380                     rotateRight(parentOf(x));
2381                     sib = leftOf(parentOf(x));
2382                 }
2383 
2384                 if (colorOf(rightOf(sib)) == BLACK &&
2385                     colorOf(leftOf(sib)) == BLACK) {
2386                     setColor(sib, RED);
2387                     x = parentOf(x);
2388                 } else {
2389                     if (colorOf(leftOf(sib)) == BLACK) {
2390                         setColor(rightOf(sib), BLACK);
2391                         setColor(sib, RED);
2392                         rotateLeft(sib);
2393                         sib = leftOf(parentOf(x));
2394                     }
2395                     setColor(sib, colorOf(parentOf(x)));
2396                     setColor(parentOf(x), BLACK);
2397                     setColor(leftOf(sib), BLACK);
2398                     rotateRight(parentOf(x));
2399                     x = root;
2400                 }
2401             }
2402         }
2403 
2404         setColor(x, BLACK);
2405     }
2406 
2407     private static final long serialVersionUID = 919286545866124006L;
2408 
2409     /**
2410      * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2411      * serialize it).
2412      *
2413      * @serialData The <em>size</em> of the TreeMap (the number of key-value
2414      *             mappings) is emitted (int), followed by the key (Object)
2415      *             and value (Object) for each key-value mapping represented
2416      *             by the TreeMap. The key-value mappings are emitted in
2417      *             key-order (as determined by the TreeMap's Comparator,
2418      *             or by the keys' natural ordering if the TreeMap has no
2419      *             Comparator).
2420      */
2421     private void writeObject(java.io.ObjectOutputStream s)
2422         throws java.io.IOException {
2423         // Write out the Comparator and any hidden stuff
2424         s.defaultWriteObject();
2425 
2426         // Write out size (number of Mappings)
2427         s.writeInt(size);
2428 
2429         // Write out keys and values (alternating)
2430         for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2431             Map.Entry<K,V> e = i.next();
2432             s.writeObject(e.getKey());
2433             s.writeObject(e.getValue());
2434         }
2435     }
2436 
2437     /**
2438      * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2439      * deserialize it).
2440      */
2441     private void readObject(final java.io.ObjectInputStream s)
2442         throws java.io.IOException, ClassNotFoundException {
2443         // Read in the Comparator and any hidden stuff
2444         s.defaultReadObject();
2445 
2446         // Read in size
2447         int size = s.readInt();
2448 
2449         buildFromSorted(size, null, s, null);
2450     }
2451 
2452     /** Intended to be called only from TreeSet.readObject */
2453     void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2454         throws java.io.IOException, ClassNotFoundException {
2455         buildFromSorted(size, null, s, defaultVal);
2456     }
2457 
2458     /** Intended to be called only from TreeSet.addAll */
2459     void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2460         try {
2461             buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2462         } catch (java.io.IOException cannotHappen) {
2463         } catch (ClassNotFoundException cannotHappen) {
2464         }
2465     }
2466 
2467 
2468     /**
2469      * Linear time tree building algorithm from sorted data.  Can accept keys
2470      * and/or values from iterator or stream. This leads to too many
2471      * parameters, but seems better than alternatives.  The four formats
2472      * that this method accepts are:
2473      *
2474      *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).
2475      *    2) An iterator of keys.         (it != null, defaultVal != null).
2476      *    3) A stream of alternating serialized keys and values.
2477      *                                   (it == null, defaultVal == null).
2478      *    4) A stream of serialized keys. (it == null, defaultVal != null).
2479      *
2480      * It is assumed that the comparator of the TreeMap is already set prior
2481      * to calling this method.
2482      *
2483      * @param size the number of keys (or key-value pairs) to be read from
2484      *        the iterator or stream
2485      * @param it If non-null, new entries are created from entries
2486      *        or keys read from this iterator.
2487      * @param str If non-null, new entries are created from keys and
2488      *        possibly values read from this stream in serialized form.
2489      *        Exactly one of it and str should be non-null.
2490      * @param defaultVal if non-null, this default value is used for
2491      *        each value in the map.  If null, each value is read from
2492      *        iterator or stream, as described above.
2493      * @throws java.io.IOException propagated from stream reads. This cannot
2494      *         occur if str is null.
2495      * @throws ClassNotFoundException propagated from readObject.
2496      *         This cannot occur if str is null.
2497      */
2498     private void buildFromSorted(int size, Iterator<?> it,
2499                                  java.io.ObjectInputStream str,
2500                                  V defaultVal)
2501         throws  java.io.IOException, ClassNotFoundException {
2502         this.size = size;
2503         root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2504                                it, str, defaultVal);
2505     }
2506 
2507     /**
2508      * Recursive "helper method" that does the real work of the
2509      * previous method.  Identically named parameters have
2510      * identical definitions.  Additional parameters are documented below.
2511      * It is assumed that the comparator and size fields of the TreeMap are
2512      * already set prior to calling this method.  (It ignores both fields.)
2513      *
2514      * @param level the current level of tree. Initial call should be 0.
2515      * @param lo the first element index of this subtree. Initial should be 0.
2516      * @param hi the last element index of this subtree.  Initial should be
2517      *        size-1.
2518      * @param redLevel the level at which nodes should be red.
2519      *        Must be equal to computeRedLevel for tree of this size.
2520      */
2521     @SuppressWarnings("unchecked")
2522     private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2523                                              int redLevel,
2524                                              Iterator<?> it,
2525                                              java.io.ObjectInputStream str,
2526                                              V defaultVal)
2527         throws  java.io.IOException, ClassNotFoundException {
2528         /*
2529          * Strategy: The root is the middlemost element. To get to it, we
2530          * have to first recursively construct the entire left subtree,
2531          * so as to grab all of its elements. We can then proceed with right
2532          * subtree.
2533          *
2534          * The lo and hi arguments are the minimum and maximum
2535          * indices to pull out of the iterator or stream for current subtree.
2536          * They are not actually indexed, we just proceed sequentially,
2537          * ensuring that items are extracted in corresponding order.
2538          */
2539 
2540         if (hi < lo) return null;
2541 
2542         int mid = (lo + hi) >>> 1;
2543 
2544         Entry<K,V> left  = null;
2545         if (lo < mid)
2546             left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2547                                    it, str, defaultVal);
2548 
2549         // extract key and/or value from iterator or stream
2550         K key;
2551         V value;
2552         if (it != null) {
2553             if (defaultVal==null) {
2554                 Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
2555                 key = (K)entry.getKey();
2556                 value = (V)entry.getValue();
2557             } else {
2558                 key = (K)it.next();
2559                 value = defaultVal;
2560             }
2561         } else { // use stream
2562             key = (K) str.readObject();
2563             value = (defaultVal != null ? defaultVal : (V) str.readObject());
2564         }
2565 
2566         Entry<K,V> middle =  new Entry<>(key, value, null);
2567 
2568         // color nodes in non-full bottommost level red
2569         if (level == redLevel)
2570             middle.color = RED;
2571 
2572         if (left != null) {
2573             middle.left = left;
2574             left.parent = middle;
2575         }
2576 
2577         if (mid < hi) {
2578             Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2579                                                it, str, defaultVal);
2580             middle.right = right;
2581             right.parent = middle;
2582         }
2583 
2584         return middle;
2585     }
2586 
2587     /**
2588      * Find the level down to which to assign all nodes BLACK.  This is the
2589      * last `full' level of the complete binary tree produced by
2590      * buildTree. The remaining nodes are colored RED. (This makes a `nice'
2591      * set of color assignments wrt future insertions.) This level number is
2592      * computed by finding the number of splits needed to reach the zeroeth
2593      * node.  (The answer is ~lg(N), but in any case must be computed by same
2594      * quick O(lg(N)) loop.)
2595      */
2596     private static int computeRedLevel(int sz) {
2597         int level = 0;
2598         for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2599             level++;
2600         return level;
2601     }
2602 
2603     /**
2604      * Currently, we support Spliterator-based versions only for the
2605      * full map, in either plain of descending form, otherwise relying
2606      * on defaults because size estimation for submaps would dominate
2607      * costs. The type tests needed to check these for key views are
2608      * not very nice but avoid disrupting existing class
2609      * structures. Callers must use plain default spliterators if this
2610      * returns null.
2611      */
2612     static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
2613         if (m instanceof TreeMap) {
2614             @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2615                 (TreeMap<K,Object>) m;
2616             return t.keySpliterator();
2617         }
2618         if (m instanceof DescendingSubMap) {
2619             @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
2620                 (DescendingSubMap<K,?>) m;
2621             TreeMap<K,?> tm = dm.m;
2622             if (dm == tm.descendingMap) {
2623                 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2624                     (TreeMap<K,Object>) tm;
2625                 return t.descendingKeySpliterator();
2626             }
2627         }
2628         @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
2629             (NavigableSubMap<K,?>) m;
2630         return sm.keySpliterator();
2631     }
2632 
2633     final Spliterator<K> keySpliterator() {
2634         return new KeySpliterator<K,V>(this, null, null, 0, -1, 0);
2635     }
2636 
2637     final Spliterator<K> descendingKeySpliterator() {
2638         return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0);
2639     }
2640 
2641     /**
2642      * Base class for spliterators.  Iteration starts at a given
2643      * origin and continues up to but not including a given fence (or
2644      * null for end).  At top-level, for ascending cases, the first
2645      * split uses the root as left-fence/right-origin. From there,
2646      * right-hand splits replace the current fence with its left
2647      * child, also serving as origin for the split-off spliterator.
2648      * Left-hands are symmetric. Descending versions place the origin
2649      * at the end and invert ascending split rules.  This base class
2650      * is non-commital about directionality, or whether the top-level
2651      * spliterator covers the whole tree. This means that the actual
2652      * split mechanics are located in subclasses. Some of the subclass
2653      * trySplit methods are identical (except for return types), but
2654      * not nicely factorable.
2655      *
2656      * Currently, subclass versions exist only for the full map
2657      * (including descending keys via its descendingMap).  Others are
2658      * possible but currently not worthwhile because submaps require
2659      * O(n) computations to determine size, which substantially limits
2660      * potential speed-ups of using custom Spliterators versus default
2661      * mechanics.
2662      *
2663      * To boostrap initialization, external constructors use
2664      * negative size estimates: -1 for ascend, -2 for descend.
2665      */
2666     static class TreeMapSpliterator<K,V> {
2667         final TreeMap<K,V> tree;
2668         TreeMap.Entry<K,V> current; // traverser; initially first node in range
2669         TreeMap.Entry<K,V> fence;   // one past last, or null
2670         int side;                   // 0: top, -1: is a left split, +1: right
2671         int est;                    // size estimate (exact only for top-level)
2672         int expectedModCount;       // for CME checks
2673 
2674         TreeMapSpliterator(TreeMap<K,V> tree,
2675                            TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2676                            int side, int est, int expectedModCount) {
2677             this.tree = tree;
2678             this.current = origin;
2679             this.fence = fence;
2680             this.side = side;
2681             this.est = est;
2682             this.expectedModCount = expectedModCount;
2683         }
2684 
2685         final int getEstimate() { // force initialization
2686             int s; TreeMap<K,V> t;
2687             if ((s = est) < 0) {
2688                 if ((t = tree) != null) {
2689                     current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
2690                     s = est = t.size;
2691                     expectedModCount = t.modCount;
2692                 }
2693                 else
2694                     s = est = 0;
2695             }
2696             return s;
2697         }
2698 
2699         public final long estimateSize() {
2700             return (long)getEstimate();
2701         }
2702     }
2703 
2704     static final class KeySpliterator<K,V>
2705         extends TreeMapSpliterator<K,V>
2706         implements Spliterator<K> {
2707         KeySpliterator(TreeMap<K,V> tree,
2708                        TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2709                        int side, int est, int expectedModCount) {
2710             super(tree, origin, fence, side, est, expectedModCount);
2711         }
2712 
2713         public KeySpliterator<K,V> trySplit() {
2714             if (est < 0)
2715                 getEstimate(); // force initialization
2716             int d = side;
2717             TreeMap.Entry<K,V> e = current, f = fence,
2718                 s = ((e == null || e == f) ? null :      // empty
2719                      (d == 0)              ? tree.root : // was top
2720                      (d >  0)              ? e.right :   // was right
2721                      (d <  0 && f != null) ? f.left :    // was left
2722                      null);
2723             if (s != null && s != e && s != f &&
2724                 tree.compare(e.key, s.key) < 0) {        // e not already past s
2725                 side = 1;
2726                 return new KeySpliterator<>
2727                     (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2728             }
2729             return null;
2730         }
2731 
2732         public void forEachRemaining(Consumer<? super K> action) {
2733             if (action == null)
2734                 throw new NullPointerException();
2735             if (est < 0)
2736                 getEstimate(); // force initialization
2737             TreeMap.Entry<K,V> f = fence, e, p, pl;
2738             if ((e = current) != null && e != f) {
2739                 current = f; // exhaust
2740                 do {
2741                     action.accept(e.key);
2742                     if ((p = e.right) != null) {
2743                         while ((pl = p.left) != null)
2744                             p = pl;
2745                     }
2746                     else {
2747                         while ((p = e.parent) != null && e == p.right)
2748                             e = p;
2749                     }
2750                 } while ((e = p) != null && e != f);
2751                 if (tree.modCount != expectedModCount)
2752                     throw new ConcurrentModificationException();
2753             }
2754         }
2755 
2756         public boolean tryAdvance(Consumer<? super K> action) {
2757             TreeMap.Entry<K,V> e;
2758             if (action == null)
2759                 throw new NullPointerException();
2760             if (est < 0)
2761                 getEstimate(); // force initialization
2762             if ((e = current) == null || e == fence)
2763                 return false;
2764             current = successor(e);
2765             action.accept(e.key);
2766             if (tree.modCount != expectedModCount)
2767                 throw new ConcurrentModificationException();
2768             return true;
2769         }
2770 
2771         public int characteristics() {
2772             return (side == 0 ? Spliterator.SIZED : 0) |
2773                 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
2774         }
2775 
2776         public final Comparator<? super K>  getComparator() {
2777             return tree.comparator;
2778         }
2779 
2780     }
2781 
2782     static final class DescendingKeySpliterator<K,V>
2783         extends TreeMapSpliterator<K,V>
2784         implements Spliterator<K> {
2785         DescendingKeySpliterator(TreeMap<K,V> tree,
2786                                  TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2787                                  int side, int est, int expectedModCount) {
2788             super(tree, origin, fence, side, est, expectedModCount);
2789         }
2790 
2791         public DescendingKeySpliterator<K,V> trySplit() {
2792             if (est < 0)
2793                 getEstimate(); // force initialization
2794             int d = side;
2795             TreeMap.Entry<K,V> e = current, f = fence,
2796                     s = ((e == null || e == f) ? null :      // empty
2797                          (d == 0)              ? tree.root : // was top
2798                          (d <  0)              ? e.left :    // was left
2799                          (d >  0 && f != null) ? f.right :   // was right
2800                          null);
2801             if (s != null && s != e && s != f &&
2802                 tree.compare(e.key, s.key) > 0) {       // e not already past s
2803                 side = 1;
2804                 return new DescendingKeySpliterator<>
2805                         (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2806             }
2807             return null;
2808         }
2809 
2810         public void forEachRemaining(Consumer<? super K> action) {
2811             if (action == null)
2812                 throw new NullPointerException();
2813             if (est < 0)
2814                 getEstimate(); // force initialization
2815             TreeMap.Entry<K,V> f = fence, e, p, pr;
2816             if ((e = current) != null && e != f) {
2817                 current = f; // exhaust
2818                 do {
2819                     action.accept(e.key);
2820                     if ((p = e.left) != null) {
2821                         while ((pr = p.right) != null)
2822                             p = pr;
2823                     }
2824                     else {
2825                         while ((p = e.parent) != null && e == p.left)
2826                             e = p;
2827                     }
2828                 } while ((e = p) != null && e != f);
2829                 if (tree.modCount != expectedModCount)
2830                     throw new ConcurrentModificationException();
2831             }
2832         }
2833 
2834         public boolean tryAdvance(Consumer<? super K> action) {
2835             TreeMap.Entry<K,V> e;
2836             if (action == null)
2837                 throw new NullPointerException();
2838             if (est < 0)
2839                 getEstimate(); // force initialization
2840             if ((e = current) == null || e == fence)
2841                 return false;
2842             current = predecessor(e);
2843             action.accept(e.key);
2844             if (tree.modCount != expectedModCount)
2845                 throw new ConcurrentModificationException();
2846             return true;
2847         }
2848 
2849         public int characteristics() {
2850             return (side == 0 ? Spliterator.SIZED : 0) |
2851                 Spliterator.DISTINCT | Spliterator.ORDERED;
2852         }
2853     }
2854 
2855     static final class ValueSpliterator<K,V>
2856             extends TreeMapSpliterator<K,V>
2857             implements Spliterator<V> {
2858         ValueSpliterator(TreeMap<K,V> tree,
2859                          TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2860                          int side, int est, int expectedModCount) {
2861             super(tree, origin, fence, side, est, expectedModCount);
2862         }
2863 
2864         public ValueSpliterator<K,V> trySplit() {
2865             if (est < 0)
2866                 getEstimate(); // force initialization
2867             int d = side;
2868             TreeMap.Entry<K,V> e = current, f = fence,
2869                     s = ((e == null || e == f) ? null :      // empty
2870                          (d == 0)              ? tree.root : // was top
2871                          (d >  0)              ? e.right :   // was right
2872                          (d <  0 && f != null) ? f.left :    // was left
2873                          null);
2874             if (s != null && s != e && s != f &&
2875                 tree.compare(e.key, s.key) < 0) {        // e not already past s
2876                 side = 1;
2877                 return new ValueSpliterator<>
2878                         (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2879             }
2880             return null;
2881         }
2882 
2883         public void forEachRemaining(Consumer<? super V> action) {
2884             if (action == null)
2885                 throw new NullPointerException();
2886             if (est < 0)
2887                 getEstimate(); // force initialization
2888             TreeMap.Entry<K,V> f = fence, e, p, pl;
2889             if ((e = current) != null && e != f) {
2890                 current = f; // exhaust
2891                 do {
2892                     action.accept(e.value);
2893                     if ((p = e.right) != null) {
2894                         while ((pl = p.left) != null)
2895                             p = pl;
2896                     }
2897                     else {
2898                         while ((p = e.parent) != null && e == p.right)
2899                             e = p;
2900                     }
2901                 } while ((e = p) != null && e != f);
2902                 if (tree.modCount != expectedModCount)
2903                     throw new ConcurrentModificationException();
2904             }
2905         }
2906 
2907         public boolean tryAdvance(Consumer<? super V> action) {
2908             TreeMap.Entry<K,V> e;
2909             if (action == null)
2910                 throw new NullPointerException();
2911             if (est < 0)
2912                 getEstimate(); // force initialization
2913             if ((e = current) == null || e == fence)
2914                 return false;
2915             current = successor(e);
2916             action.accept(e.value);
2917             if (tree.modCount != expectedModCount)
2918                 throw new ConcurrentModificationException();
2919             return true;
2920         }
2921 
2922         public int characteristics() {
2923             return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.ORDERED;
2924         }
2925     }
2926 
2927     static final class EntrySpliterator<K,V>
2928         extends TreeMapSpliterator<K,V>
2929         implements Spliterator<Map.Entry<K,V>> {
2930         EntrySpliterator(TreeMap<K,V> tree,
2931                          TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2932                          int side, int est, int expectedModCount) {
2933             super(tree, origin, fence, side, est, expectedModCount);
2934         }
2935 
2936         public EntrySpliterator<K,V> trySplit() {
2937             if (est < 0)
2938                 getEstimate(); // force initialization
2939             int d = side;
2940             TreeMap.Entry<K,V> e = current, f = fence,
2941                     s = ((e == null || e == f) ? null :      // empty
2942                          (d == 0)              ? tree.root : // was top
2943                          (d >  0)              ? e.right :   // was right
2944                          (d <  0 && f != null) ? f.left :    // was left
2945                          null);
2946             if (s != null && s != e && s != f &&
2947                 tree.compare(e.key, s.key) < 0) {        // e not already past s
2948                 side = 1;
2949                 return new EntrySpliterator<>
2950                         (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2951             }
2952             return null;
2953         }
2954 
2955         public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
2956             if (action == null)
2957                 throw new NullPointerException();
2958             if (est < 0)
2959                 getEstimate(); // force initialization
2960             TreeMap.Entry<K,V> f = fence, e, p, pl;
2961             if ((e = current) != null && e != f) {
2962                 current = f; // exhaust
2963                 do {
2964                     action.accept(e);
2965                     if ((p = e.right) != null) {
2966                         while ((pl = p.left) != null)
2967                             p = pl;
2968                     }
2969                     else {
2970                         while ((p = e.parent) != null && e == p.right)
2971                             e = p;
2972                     }
2973                 } while ((e = p) != null && e != f);
2974                 if (tree.modCount != expectedModCount)
2975                     throw new ConcurrentModificationException();
2976             }
2977         }
2978 
2979         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
2980             TreeMap.Entry<K,V> e;
2981             if (action == null)
2982                 throw new NullPointerException();
2983             if (est < 0)
2984                 getEstimate(); // force initialization
2985             if ((e = current) == null || e == fence)
2986                 return false;
2987             current = successor(e);
2988             action.accept(e);
2989             if (tree.modCount != expectedModCount)
2990                 throw new ConcurrentModificationException();
2991             return true;
2992         }
2993 
2994         public int characteristics() {
2995             return (side == 0 ? Spliterator.SIZED : 0) |
2996                     Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
2997         }
2998 
2999         @Override
3000         public Comparator<Map.Entry<K, V>> getComparator() {
3001             // Adapt or create a key-based comparator
3002             if (tree.comparator != null) {
3003                 return Map.Entry.comparingByKey(tree.comparator);
3004             }
3005             else {
3006                 return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> {
3007                     @SuppressWarnings("unchecked")
3008                     Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
3009                     return k1.compareTo(e2.getKey());
3010                 };
3011             }
3012         }
3013     }
3014 }