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 synchronized 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 synchronized 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 = Objects.requireNonNull(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     }
1273 
1274     // Little utilities
1275 
1276     /**
1277      * Compares two keys using the correct comparison method for this TreeMap.
1278      */
1279     @SuppressWarnings("unchecked")
1280     final int compare(Object k1, Object k2) {
1281         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1282             : comparator.compare((K)k1, (K)k2);
1283     }
1284 
1285     /**
1286      * Test two values for equality.  Differs from o1.equals(o2) only in
1287      * that it copes with {@code null} o1 properly.
1288      */
1289     static final boolean valEquals(Object o1, Object o2) {
1290         return (o1==null ? o2==null : o1.equals(o2));
1291     }
1292 
1293     /**
1294      * Return SimpleImmutableEntry for entry, or null if null
1295      */
1296     static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1297         return (e == null) ? null :
1298             new AbstractMap.SimpleImmutableEntry<>(e);
1299     }
1300 
1301     /**
1302      * Return key for entry, or null if null
1303      */
1304     static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1305         return (e == null) ? null : e.key;
1306     }
1307 
1308     /**
1309      * Returns the key corresponding to the specified Entry.
1310      * @throws NoSuchElementException if the Entry is null
1311      */
1312     static <K> K key(Entry<K,?> e) {
1313         if (e==null)
1314             throw new NoSuchElementException();
1315         return e.key;
1316     }
1317 
1318 
1319     // SubMaps
1320 
1321     /**
1322      * Dummy value serving as unmatchable fence key for unbounded
1323      * SubMapIterators
1324      */
1325     private static final Object UNBOUNDED = new Object();
1326 
1327     /**
1328      * @serial include
1329      */
1330     abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1331         implements NavigableMap<K,V>, java.io.Serializable {
1332         /**
1333          * The backing map.
1334          */
1335         final TreeMap<K,V> m;
1336 
1337         /**
1338          * Endpoints are represented as triples (fromStart, lo,
1339          * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1340          * true, then the low (absolute) bound is the start of the
1341          * backing map, and the other values are ignored. Otherwise,
1342          * if loInclusive is true, lo is the inclusive bound, else lo
1343          * is the exclusive bound. Similarly for the upper bound.
1344          */
1345         final K lo, hi;
1346         final boolean fromStart, toEnd;
1347         final boolean loInclusive, hiInclusive;
1348 
1349         NavigableSubMap(TreeMap<K,V> m,
1350                         boolean fromStart, K lo, boolean loInclusive,
1351                         boolean toEnd,     K hi, boolean hiInclusive) {
1352             if (!fromStart && !toEnd) {
1353                 if (m.compare(lo, hi) > 0)
1354                     throw new IllegalArgumentException("fromKey > toKey");
1355             } else {
1356                 if (!fromStart) // type check
1357                     m.compare(lo, lo);
1358                 if (!toEnd)
1359                     m.compare(hi, hi);
1360             }
1361 
1362             this.m = m;
1363             this.fromStart = fromStart;
1364             this.lo = lo;
1365             this.loInclusive = loInclusive;
1366             this.toEnd = toEnd;
1367             this.hi = hi;
1368             this.hiInclusive = hiInclusive;
1369         }
1370 
1371         // internal utilities
1372 
1373         final boolean tooLow(Object key) {
1374             if (!fromStart) {
1375                 int c = m.compare(key, lo);
1376                 if (c < 0 || (c == 0 && !loInclusive))
1377                     return true;
1378             }
1379             return false;
1380         }
1381 
1382         final boolean tooHigh(Object key) {
1383             if (!toEnd) {
1384                 int c = m.compare(key, hi);
1385                 if (c > 0 || (c == 0 && !hiInclusive))
1386                     return true;
1387             }
1388             return false;
1389         }
1390 
1391         final boolean inRange(Object key) {
1392             return !tooLow(key) && !tooHigh(key);
1393         }
1394 
1395         final boolean inClosedRange(Object key) {
1396             return (fromStart || m.compare(key, lo) >= 0)
1397                 && (toEnd || m.compare(hi, key) >= 0);
1398         }
1399 
1400         final boolean inRange(Object key, boolean inclusive) {
1401             return inclusive ? inRange(key) : inClosedRange(key);
1402         }
1403 
1404         /*
1405          * Absolute versions of relation operations.
1406          * Subclasses map to these using like-named "sub"
1407          * versions that invert senses for descending maps
1408          */
1409 
1410         final TreeMap.Entry<K,V> absLowest() {
1411             TreeMap.Entry<K,V> e =
1412                 (fromStart ?  m.getFirstEntry() :
1413                  (loInclusive ? m.getCeilingEntry(lo) :
1414                                 m.getHigherEntry(lo)));
1415             return (e == null || tooHigh(e.key)) ? null : e;
1416         }
1417 
1418         final TreeMap.Entry<K,V> absHighest() {
1419             TreeMap.Entry<K,V> e =
1420                 (toEnd ?  m.getLastEntry() :
1421                  (hiInclusive ?  m.getFloorEntry(hi) :
1422                                  m.getLowerEntry(hi)));
1423             return (e == null || tooLow(e.key)) ? null : e;
1424         }
1425 
1426         final TreeMap.Entry<K,V> absCeiling(K key) {
1427             if (tooLow(key))
1428                 return absLowest();
1429             TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1430             return (e == null || tooHigh(e.key)) ? null : e;
1431         }
1432 
1433         final TreeMap.Entry<K,V> absHigher(K key) {
1434             if (tooLow(key))
1435                 return absLowest();
1436             TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1437             return (e == null || tooHigh(e.key)) ? null : e;
1438         }
1439 
1440         final TreeMap.Entry<K,V> absFloor(K key) {
1441             if (tooHigh(key))
1442                 return absHighest();
1443             TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1444             return (e == null || tooLow(e.key)) ? null : e;
1445         }
1446 
1447         final TreeMap.Entry<K,V> absLower(K key) {
1448             if (tooHigh(key))
1449                 return absHighest();
1450             TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1451             return (e == null || tooLow(e.key)) ? null : e;
1452         }
1453 
1454         /** Returns the absolute high fence for ascending traversal */
1455         final TreeMap.Entry<K,V> absHighFence() {
1456             return (toEnd ? null : (hiInclusive ?
1457                                     m.getHigherEntry(hi) :
1458                                     m.getCeilingEntry(hi)));
1459         }
1460 
1461         /** Return the absolute low fence for descending traversal  */
1462         final TreeMap.Entry<K,V> absLowFence() {
1463             return (fromStart ? null : (loInclusive ?
1464                                         m.getLowerEntry(lo) :
1465                                         m.getFloorEntry(lo)));
1466         }
1467 
1468         // Abstract methods defined in ascending vs descending classes
1469         // These relay to the appropriate absolute versions
1470 
1471         abstract TreeMap.Entry<K,V> subLowest();
1472         abstract TreeMap.Entry<K,V> subHighest();
1473         abstract TreeMap.Entry<K,V> subCeiling(K key);
1474         abstract TreeMap.Entry<K,V> subHigher(K key);
1475         abstract TreeMap.Entry<K,V> subFloor(K key);
1476         abstract TreeMap.Entry<K,V> subLower(K key);
1477 
1478         /** Returns ascending iterator from the perspective of this submap */
1479         abstract Iterator<K> keyIterator();
1480 
1481         abstract Spliterator<K> keySpliterator();
1482 
1483         /** Returns descending iterator from the perspective of this submap */
1484         abstract Iterator<K> descendingKeyIterator();
1485 
1486         // public methods
1487 
1488         public boolean isEmpty() {
1489             return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1490         }
1491 
1492         public int size() {
1493             return (fromStart && toEnd) ? m.size() : entrySet().size();
1494         }
1495 
1496         public final boolean containsKey(Object key) {
1497             return inRange(key) && m.containsKey(key);
1498         }
1499 
1500         public final V put(K key, V value) {
1501             if (!inRange(key))
1502                 throw new IllegalArgumentException("key out of range");
1503             return m.put(key, value);
1504         }
1505 
1506         public final V get(Object key) {
1507             return !inRange(key) ? null :  m.get(key);
1508         }
1509 
1510         public final V remove(Object key) {
1511             return !inRange(key) ? null : m.remove(key);
1512         }
1513 
1514         public final Map.Entry<K,V> ceilingEntry(K key) {
1515             return exportEntry(subCeiling(key));
1516         }
1517 
1518         public final K ceilingKey(K key) {
1519             return keyOrNull(subCeiling(key));
1520         }
1521 
1522         public final Map.Entry<K,V> higherEntry(K key) {
1523             return exportEntry(subHigher(key));
1524         }
1525 
1526         public final K higherKey(K key) {
1527             return keyOrNull(subHigher(key));
1528         }
1529 
1530         public final Map.Entry<K,V> floorEntry(K key) {
1531             return exportEntry(subFloor(key));
1532         }
1533 
1534         public final K floorKey(K key) {
1535             return keyOrNull(subFloor(key));
1536         }
1537 
1538         public final Map.Entry<K,V> lowerEntry(K key) {
1539             return exportEntry(subLower(key));
1540         }
1541 
1542         public final K lowerKey(K key) {
1543             return keyOrNull(subLower(key));
1544         }
1545 
1546         public final K firstKey() {
1547             return key(subLowest());
1548         }
1549 
1550         public final K lastKey() {
1551             return key(subHighest());
1552         }
1553 
1554         public final Map.Entry<K,V> firstEntry() {
1555             return exportEntry(subLowest());
1556         }
1557 
1558         public final Map.Entry<K,V> lastEntry() {
1559             return exportEntry(subHighest());
1560         }
1561 
1562         public final Map.Entry<K,V> pollFirstEntry() {
1563             TreeMap.Entry<K,V> e = subLowest();
1564             Map.Entry<K,V> result = exportEntry(e);
1565             if (e != null)
1566                 m.deleteEntry(e);
1567             return result;
1568         }
1569 
1570         public final Map.Entry<K,V> pollLastEntry() {
1571             TreeMap.Entry<K,V> e = subHighest();
1572             Map.Entry<K,V> result = exportEntry(e);
1573             if (e != null)
1574                 m.deleteEntry(e);
1575             return result;
1576         }
1577 
1578         // Views
1579         transient NavigableMap<K,V> descendingMapView = null;
1580         transient EntrySetView entrySetView = null;
1581         transient KeySet<K> navigableKeySetView = null;
1582 
1583         public final NavigableSet<K> navigableKeySet() {
1584             KeySet<K> nksv = navigableKeySetView;
1585             return (nksv != null) ? nksv :
1586                 (navigableKeySetView = new TreeMap.KeySet<>(this));
1587         }
1588 
1589         public final Set<K> keySet() {
1590             return navigableKeySet();
1591         }
1592 
1593         public NavigableSet<K> descendingKeySet() {
1594             return descendingMap().navigableKeySet();
1595         }
1596 
1597         public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1598             return subMap(fromKey, true, toKey, false);
1599         }
1600 
1601         public final SortedMap<K,V> headMap(K toKey) {
1602             return headMap(toKey, false);
1603         }
1604 
1605         public final SortedMap<K,V> tailMap(K fromKey) {
1606             return tailMap(fromKey, true);
1607         }
1608 
1609         // View classes
1610 
1611         abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1612             private transient int size = -1, sizeModCount;
1613 
1614             public int size() {
1615                 if (fromStart && toEnd)
1616                     return m.size();
1617                 if (size == -1 || sizeModCount != m.modCount) {
1618                     sizeModCount = m.modCount;
1619                     size = 0;
1620                     Iterator<?> i = iterator();
1621                     while (i.hasNext()) {
1622                         size++;
1623                         i.next();
1624                     }
1625                 }
1626                 return size;
1627             }
1628 
1629             public boolean isEmpty() {
1630                 TreeMap.Entry<K,V> n = absLowest();
1631                 return n == null || tooHigh(n.key);
1632             }
1633 
1634             public boolean contains(Object o) {
1635                 if (!(o instanceof Map.Entry))
1636                     return false;
1637                 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1638                 Object key = entry.getKey();
1639                 if (!inRange(key))
1640                     return false;
1641                 TreeMap.Entry<?,?> node = m.getEntry(key);
1642                 return node != null &&
1643                     valEquals(node.getValue(), entry.getValue());
1644             }
1645 
1646             public boolean remove(Object o) {
1647                 if (!(o instanceof Map.Entry))
1648                     return false;
1649                 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1650                 Object key = entry.getKey();
1651                 if (!inRange(key))
1652                     return false;
1653                 TreeMap.Entry<K,V> node = m.getEntry(key);
1654                 if (node!=null && valEquals(node.getValue(),
1655                                             entry.getValue())) {
1656                     m.deleteEntry(node);
1657                     return true;
1658                 }
1659                 return false;
1660             }
1661         }
1662 
1663         /**
1664          * Iterators for SubMaps
1665          */
1666         abstract class SubMapIterator<T> implements Iterator<T> {
1667             TreeMap.Entry<K,V> lastReturned;
1668             TreeMap.Entry<K,V> next;
1669             final Object fenceKey;
1670             int expectedModCount;
1671 
1672             SubMapIterator(TreeMap.Entry<K,V> first,
1673                            TreeMap.Entry<K,V> fence) {
1674                 expectedModCount = m.modCount;
1675                 lastReturned = null;
1676                 next = first;
1677                 fenceKey = fence == null ? UNBOUNDED : fence.key;
1678             }
1679 
1680             public final boolean hasNext() {
1681                 return next != null && next.key != fenceKey;
1682             }
1683 
1684             final TreeMap.Entry<K,V> nextEntry() {
1685                 TreeMap.Entry<K,V> e = next;
1686                 if (e == null || e.key == fenceKey)
1687                     throw new NoSuchElementException();
1688                 if (m.modCount != expectedModCount)
1689                     throw new ConcurrentModificationException();
1690                 next = successor(e);
1691                 lastReturned = e;
1692                 return e;
1693             }
1694 
1695             final TreeMap.Entry<K,V> prevEntry() {
1696                 TreeMap.Entry<K,V> e = next;
1697                 if (e == null || e.key == fenceKey)
1698                     throw new NoSuchElementException();
1699                 if (m.modCount != expectedModCount)
1700                     throw new ConcurrentModificationException();
1701                 next = predecessor(e);
1702                 lastReturned = e;
1703                 return e;
1704             }
1705 
1706             final void removeAscending() {
1707                 if (lastReturned == null)
1708                     throw new IllegalStateException();
1709                 if (m.modCount != expectedModCount)
1710                     throw new ConcurrentModificationException();
1711                 // deleted entries are replaced by their successors
1712                 if (lastReturned.left != null && lastReturned.right != null)
1713                     next = lastReturned;
1714                 m.deleteEntry(lastReturned);
1715                 lastReturned = null;
1716                 expectedModCount = m.modCount;
1717             }
1718 
1719             final void removeDescending() {
1720                 if (lastReturned == null)
1721                     throw new IllegalStateException();
1722                 if (m.modCount != expectedModCount)
1723                     throw new ConcurrentModificationException();
1724                 m.deleteEntry(lastReturned);
1725                 lastReturned = null;
1726                 expectedModCount = m.modCount;
1727             }
1728 
1729         }
1730 
1731         final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1732             SubMapEntryIterator(TreeMap.Entry<K,V> first,
1733                                 TreeMap.Entry<K,V> fence) {
1734                 super(first, fence);
1735             }
1736             public Map.Entry<K,V> next() {
1737                 return nextEntry();
1738             }
1739             public void remove() {
1740                 removeAscending();
1741             }
1742         }
1743 
1744         final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1745             DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1746                                           TreeMap.Entry<K,V> fence) {
1747                 super(last, fence);
1748             }
1749 
1750             public Map.Entry<K,V> next() {
1751                 return prevEntry();
1752             }
1753             public void remove() {
1754                 removeDescending();
1755             }
1756         }
1757 
1758         // Implement minimal Spliterator as KeySpliterator backup
1759         final class SubMapKeyIterator extends SubMapIterator<K>
1760             implements Spliterator<K> {
1761             SubMapKeyIterator(TreeMap.Entry<K,V> first,
1762                               TreeMap.Entry<K,V> fence) {
1763                 super(first, fence);
1764             }
1765             public K next() {
1766                 return nextEntry().key;
1767             }
1768             public void remove() {
1769                 removeAscending();
1770             }
1771             public Spliterator<K> trySplit() {
1772                 return null;
1773             }
1774             public void forEachRemaining(Consumer<? super K> action) {
1775                 while (hasNext())
1776                     action.accept(next());
1777             }
1778             public boolean tryAdvance(Consumer<? super K> action) {
1779                 if (hasNext()) {
1780                     action.accept(next());
1781                     return true;
1782                 }
1783                 return false;
1784             }
1785             public long estimateSize() {
1786                 return Long.MAX_VALUE;
1787             }
1788             public int characteristics() {
1789                 return Spliterator.DISTINCT | Spliterator.ORDERED |
1790                     Spliterator.SORTED;
1791             }
1792             public final Comparator<? super K>  getComparator() {
1793                 return NavigableSubMap.this.comparator();
1794             }
1795         }
1796 
1797         final class DescendingSubMapKeyIterator extends SubMapIterator<K>
1798             implements Spliterator<K> {
1799             DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1800                                         TreeMap.Entry<K,V> fence) {
1801                 super(last, fence);
1802             }
1803             public K next() {
1804                 return prevEntry().key;
1805             }
1806             public void remove() {
1807                 removeDescending();
1808             }
1809             public Spliterator<K> trySplit() {
1810                 return null;
1811             }
1812             public void forEachRemaining(Consumer<? super K> action) {
1813                 while (hasNext())
1814                     action.accept(next());
1815             }
1816             public boolean tryAdvance(Consumer<? super K> action) {
1817                 if (hasNext()) {
1818                     action.accept(next());
1819                     return true;
1820                 }
1821                 return false;
1822             }
1823             public long estimateSize() {
1824                 return Long.MAX_VALUE;
1825             }
1826             public int characteristics() {
1827                 return Spliterator.DISTINCT | Spliterator.ORDERED;
1828             }
1829         }
1830     }
1831 
1832     /**
1833      * @serial include
1834      */
1835     static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1836         private static final long serialVersionUID = 912986545866124060L;
1837 
1838         AscendingSubMap(TreeMap<K,V> m,
1839                         boolean fromStart, K lo, boolean loInclusive,
1840                         boolean toEnd,     K hi, boolean hiInclusive) {
1841             super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1842         }
1843 
1844         public Comparator<? super K> comparator() {
1845             return m.comparator();
1846         }
1847 
1848         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1849                                         K toKey,   boolean toInclusive) {
1850             if (!inRange(fromKey, fromInclusive))
1851                 throw new IllegalArgumentException("fromKey out of range");
1852             if (!inRange(toKey, toInclusive))
1853                 throw new IllegalArgumentException("toKey out of range");
1854             return new AscendingSubMap<>(m,
1855                                          false, fromKey, fromInclusive,
1856                                          false, toKey,   toInclusive);
1857         }
1858 
1859         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1860             if (!inRange(toKey, inclusive))
1861                 throw new IllegalArgumentException("toKey out of range");
1862             return new AscendingSubMap<>(m,
1863                                          fromStart, lo,    loInclusive,
1864                                          false,     toKey, inclusive);
1865         }
1866 
1867         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1868             if (!inRange(fromKey, inclusive))
1869                 throw new IllegalArgumentException("fromKey out of range");
1870             return new AscendingSubMap<>(m,
1871                                          false, fromKey, inclusive,
1872                                          toEnd, hi,      hiInclusive);
1873         }
1874 
1875         public NavigableMap<K,V> descendingMap() {
1876             NavigableMap<K,V> mv = descendingMapView;
1877             return (mv != null) ? mv :
1878                 (descendingMapView =
1879                  new DescendingSubMap<>(m,
1880                                         fromStart, lo, loInclusive,
1881                                         toEnd,     hi, hiInclusive));
1882         }
1883 
1884         Iterator<K> keyIterator() {
1885             return new SubMapKeyIterator(absLowest(), absHighFence());
1886         }
1887 
1888         Spliterator<K> keySpliterator() {
1889             return new SubMapKeyIterator(absLowest(), absHighFence());
1890         }
1891 
1892         Iterator<K> descendingKeyIterator() {
1893             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1894         }
1895 
1896         final class AscendingEntrySetView extends EntrySetView {
1897             public Iterator<Map.Entry<K,V>> iterator() {
1898                 return new SubMapEntryIterator(absLowest(), absHighFence());
1899             }
1900         }
1901 
1902         public Set<Map.Entry<K,V>> entrySet() {
1903             EntrySetView es = entrySetView;
1904             return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
1905         }
1906 
1907         TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1908         TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1909         TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1910         TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1911         TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1912         TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1913     }
1914 
1915     /**
1916      * @serial include
1917      */
1918     static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1919         private static final long serialVersionUID = 912986545866120460L;
1920         DescendingSubMap(TreeMap<K,V> m,
1921                         boolean fromStart, K lo, boolean loInclusive,
1922                         boolean toEnd,     K hi, boolean hiInclusive) {
1923             super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1924         }
1925 
1926         private final Comparator<? super K> reverseComparator =
1927             Collections.reverseOrder(m.comparator);
1928 
1929         public Comparator<? super K> comparator() {
1930             return reverseComparator;
1931         }
1932 
1933         public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1934                                         K toKey,   boolean toInclusive) {
1935             if (!inRange(fromKey, fromInclusive))
1936                 throw new IllegalArgumentException("fromKey out of range");
1937             if (!inRange(toKey, toInclusive))
1938                 throw new IllegalArgumentException("toKey out of range");
1939             return new DescendingSubMap<>(m,
1940                                           false, toKey,   toInclusive,
1941                                           false, fromKey, fromInclusive);
1942         }
1943 
1944         public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1945             if (!inRange(toKey, inclusive))
1946                 throw new IllegalArgumentException("toKey out of range");
1947             return new DescendingSubMap<>(m,
1948                                           false, toKey, inclusive,
1949                                           toEnd, hi,    hiInclusive);
1950         }
1951 
1952         public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1953             if (!inRange(fromKey, inclusive))
1954                 throw new IllegalArgumentException("fromKey out of range");
1955             return new DescendingSubMap<>(m,
1956                                           fromStart, lo, loInclusive,
1957                                           false, fromKey, inclusive);
1958         }
1959 
1960         public NavigableMap<K,V> descendingMap() {
1961             NavigableMap<K,V> mv = descendingMapView;
1962             return (mv != null) ? mv :
1963                 (descendingMapView =
1964                  new AscendingSubMap<>(m,
1965                                        fromStart, lo, loInclusive,
1966                                        toEnd,     hi, hiInclusive));
1967         }
1968 
1969         Iterator<K> keyIterator() {
1970             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1971         }
1972 
1973         Spliterator<K> keySpliterator() {
1974             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1975         }
1976 
1977         Iterator<K> descendingKeyIterator() {
1978             return new SubMapKeyIterator(absLowest(), absHighFence());
1979         }
1980 
1981         final class DescendingEntrySetView extends EntrySetView {
1982             public Iterator<Map.Entry<K,V>> iterator() {
1983                 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1984             }
1985         }
1986 
1987         public Set<Map.Entry<K,V>> entrySet() {
1988             EntrySetView es = entrySetView;
1989             return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
1990         }
1991 
1992         TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1993         TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1994         TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1995         TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1996         TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1997         TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1998     }
1999 
2000     /**
2001      * This class exists solely for the sake of serialization
2002      * compatibility with previous releases of TreeMap that did not
2003      * support NavigableMap.  It translates an old-version SubMap into
2004      * a new-version AscendingSubMap. This class is never otherwise
2005      * used.
2006      *
2007      * @serial include
2008      */
2009     private class SubMap extends AbstractMap<K,V>
2010         implements SortedMap<K,V>, java.io.Serializable {
2011         private static final long serialVersionUID = -6520786458950516097L;
2012         private boolean fromStart = false, toEnd = false;
2013         private K fromKey, toKey;
2014         private Object readResolve() {
2015             return new AscendingSubMap<>(TreeMap.this,
2016                                          fromStart, fromKey, true,
2017                                          toEnd, toKey, false);
2018         }
2019         public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2020         public K lastKey() { throw new InternalError(); }
2021         public K firstKey() { throw new InternalError(); }
2022         public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2023         public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2024         public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2025         public Comparator<? super K> comparator() { throw new InternalError(); }
2026     }
2027 
2028 
2029     // Red-black mechanics
2030 
2031     private static final boolean RED   = false;
2032     private static final boolean BLACK = true;
2033 
2034     /**
2035      * Node in the Tree.  Doubles as a means to pass key-value pairs back to
2036      * user (see Map.Entry).
2037      */
2038 
2039     static final class Entry<K,V> implements Map.Entry<K,V> {
2040         K key;
2041         V value;
2042         Entry<K,V> left = null;
2043         Entry<K,V> right = null;
2044         Entry<K,V> parent;
2045         boolean color = BLACK;
2046 
2047         /**
2048          * Make a new cell with given key, value, and parent, and with
2049          * {@code null} child links, and BLACK color.
2050          */
2051         Entry(K key, V value, Entry<K,V> parent) {
2052             this.key = key;
2053             this.value = value;
2054             this.parent = parent;
2055         }
2056 
2057         /**
2058          * Returns the key.
2059          *
2060          * @return the key
2061          */
2062         public K getKey() {
2063             return key;
2064         }
2065 
2066         /**
2067          * Returns the value associated with the key.
2068          *
2069          * @return the value associated with the key
2070          */
2071         public V getValue() {
2072             return value;
2073         }
2074 
2075         /**
2076          * Replaces the value currently associated with the key with the given
2077          * value.
2078          *
2079          * @return the value associated with the key before this method was
2080          *         called
2081          */
2082         public V setValue(V value) {
2083             V oldValue = this.value;
2084             this.value = value;
2085             return oldValue;
2086         }
2087 
2088         public boolean equals(Object o) {
2089             if (!(o instanceof Map.Entry))
2090                 return false;
2091             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2092 
2093             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
2094         }
2095 
2096         public int hashCode() {
2097             int keyHash = (key==null ? 0 : key.hashCode());
2098             int valueHash = (value==null ? 0 : value.hashCode());
2099             return keyHash ^ valueHash;
2100         }
2101 
2102         public String toString() {
2103             return key + "=" + value;
2104         }
2105     }
2106 
2107     /**
2108      * Returns the first Entry in the TreeMap (according to the TreeMap's
2109      * key-sort function).  Returns null if the TreeMap is empty.
2110      */
2111     final Entry<K,V> getFirstEntry() {
2112         Entry<K,V> p = root;
2113         if (p != null)
2114             while (p.left != null)
2115                 p = p.left;
2116         return p;
2117     }
2118 
2119     /**
2120      * Returns the last Entry in the TreeMap (according to the TreeMap's
2121      * key-sort function).  Returns null if the TreeMap is empty.
2122      */
2123     final Entry<K,V> getLastEntry() {
2124         Entry<K,V> p = root;
2125         if (p != null)
2126             while (p.right != null)
2127                 p = p.right;
2128         return p;
2129     }
2130 
2131     /**
2132      * Returns the successor of the specified Entry, or null if no such.
2133      */
2134     static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2135         if (t == null)
2136             return null;
2137         else if (t.right != null) {
2138             Entry<K,V> p = t.right;
2139             while (p.left != null)
2140                 p = p.left;
2141             return p;
2142         } else {
2143             Entry<K,V> p = t.parent;
2144             Entry<K,V> ch = t;
2145             while (p != null && ch == p.right) {
2146                 ch = p;
2147                 p = p.parent;
2148             }
2149             return p;
2150         }
2151     }
2152 
2153     /**
2154      * Returns the predecessor of the specified Entry, or null if no such.
2155      */
2156     static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2157         if (t == null)
2158             return null;
2159         else if (t.left != null) {
2160             Entry<K,V> p = t.left;
2161             while (p.right != null)
2162                 p = p.right;
2163             return p;
2164         } else {
2165             Entry<K,V> p = t.parent;
2166             Entry<K,V> ch = t;
2167             while (p != null && ch == p.left) {
2168                 ch = p;
2169                 p = p.parent;
2170             }
2171             return p;
2172         }
2173     }
2174 
2175     /**
2176      * Balancing operations.
2177      *
2178      * Implementations of rebalancings during insertion and deletion are
2179      * slightly different than the CLR version.  Rather than using dummy
2180      * nilnodes, we use a set of accessors that deal properly with null.  They
2181      * are used to avoid messiness surrounding nullness checks in the main
2182      * algorithms.
2183      */
2184 
2185     private static <K,V> boolean colorOf(Entry<K,V> p) {
2186         return (p == null ? BLACK : p.color);
2187     }
2188 
2189     private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
2190         return (p == null ? null: p.parent);
2191     }
2192 
2193     private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2194         if (p != null)
2195             p.color = c;
2196     }
2197 
2198     private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
2199         return (p == null) ? null: p.left;
2200     }
2201 
2202     private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
2203         return (p == null) ? null: p.right;
2204     }
2205 
2206     /** From CLR */
2207     private void rotateLeft(Entry<K,V> p) {
2208         if (p != null) {
2209             Entry<K,V> r = p.right;
2210             p.right = r.left;
2211             if (r.left != null)
2212                 r.left.parent = p;
2213             r.parent = p.parent;
2214             if (p.parent == null)
2215                 root = r;
2216             else if (p.parent.left == p)
2217                 p.parent.left = r;
2218             else
2219                 p.parent.right = r;
2220             r.left = p;
2221             p.parent = r;
2222         }
2223     }
2224 
2225     /** From CLR */
2226     private void rotateRight(Entry<K,V> p) {
2227         if (p != null) {
2228             Entry<K,V> l = p.left;
2229             p.left = l.right;
2230             if (l.right != null) l.right.parent = p;
2231             l.parent = p.parent;
2232             if (p.parent == null)
2233                 root = l;
2234             else if (p.parent.right == p)
2235                 p.parent.right = l;
2236             else p.parent.left = l;
2237             l.right = p;
2238             p.parent = l;
2239         }
2240     }
2241 
2242     /** From CLR */
2243     private void fixAfterInsertion(Entry<K,V> x) {
2244         x.color = RED;
2245 
2246         while (x != null && x != root && x.parent.color == RED) {
2247             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2248                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
2249                 if (colorOf(y) == RED) {
2250                     setColor(parentOf(x), BLACK);
2251                     setColor(y, BLACK);
2252                     setColor(parentOf(parentOf(x)), RED);
2253                     x = parentOf(parentOf(x));
2254                 } else {
2255                     if (x == rightOf(parentOf(x))) {
2256                         x = parentOf(x);
2257                         rotateLeft(x);
2258                     }
2259                     setColor(parentOf(x), BLACK);
2260                     setColor(parentOf(parentOf(x)), RED);
2261                     rotateRight(parentOf(parentOf(x)));
2262                 }
2263             } else {
2264                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
2265                 if (colorOf(y) == RED) {
2266                     setColor(parentOf(x), BLACK);
2267                     setColor(y, BLACK);
2268                     setColor(parentOf(parentOf(x)), RED);
2269                     x = parentOf(parentOf(x));
2270                 } else {
2271                     if (x == leftOf(parentOf(x))) {
2272                         x = parentOf(x);
2273                         rotateRight(x);
2274                     }
2275                     setColor(parentOf(x), BLACK);
2276                     setColor(parentOf(parentOf(x)), RED);
2277                     rotateLeft(parentOf(parentOf(x)));
2278                 }
2279             }
2280         }
2281         root.color = BLACK;
2282     }
2283 
2284     /**
2285      * Delete node p, and then rebalance the tree.
2286      */
2287     private void deleteEntry(Entry<K,V> p) {
2288         modCount++;
2289         size--;
2290 
2291         // If strictly internal, copy successor's element to p and then make p
2292         // point to successor.
2293         if (p.left != null && p.right != null) {
2294             Entry<K,V> s = successor(p);
2295             p.key = s.key;
2296             p.value = s.value;
2297             p = s;
2298         } // p has 2 children
2299 
2300         // Start fixup at replacement node, if it exists.
2301         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2302 
2303         if (replacement != null) {
2304             // Link replacement to parent
2305             replacement.parent = p.parent;
2306             if (p.parent == null)
2307                 root = replacement;
2308             else if (p == p.parent.left)
2309                 p.parent.left  = replacement;
2310             else
2311                 p.parent.right = replacement;
2312 
2313             // Null out links so they are OK to use by fixAfterDeletion.
2314             p.left = p.right = p.parent = null;
2315 
2316             // Fix replacement
2317             if (p.color == BLACK)
2318                 fixAfterDeletion(replacement);
2319         } else if (p.parent == null) { // return if we are the only node.
2320             root = null;
2321         } else { //  No children. Use self as phantom replacement and unlink.
2322             if (p.color == BLACK)
2323                 fixAfterDeletion(p);
2324 
2325             if (p.parent != null) {
2326                 if (p == p.parent.left)
2327                     p.parent.left = null;
2328                 else if (p == p.parent.right)
2329                     p.parent.right = null;
2330                 p.parent = null;
2331             }
2332         }
2333     }
2334 
2335     /** From CLR */
2336     private void fixAfterDeletion(Entry<K,V> x) {
2337         while (x != root && colorOf(x) == BLACK) {
2338             if (x == leftOf(parentOf(x))) {
2339                 Entry<K,V> sib = rightOf(parentOf(x));
2340 
2341                 if (colorOf(sib) == RED) {
2342                     setColor(sib, BLACK);
2343                     setColor(parentOf(x), RED);
2344                     rotateLeft(parentOf(x));
2345                     sib = rightOf(parentOf(x));
2346                 }
2347 
2348                 if (colorOf(leftOf(sib))  == BLACK &&
2349                     colorOf(rightOf(sib)) == BLACK) {
2350                     setColor(sib, RED);
2351                     x = parentOf(x);
2352                 } else {
2353                     if (colorOf(rightOf(sib)) == BLACK) {
2354                         setColor(leftOf(sib), BLACK);
2355                         setColor(sib, RED);
2356                         rotateRight(sib);
2357                         sib = rightOf(parentOf(x));
2358                     }
2359                     setColor(sib, colorOf(parentOf(x)));
2360                     setColor(parentOf(x), BLACK);
2361                     setColor(rightOf(sib), BLACK);
2362                     rotateLeft(parentOf(x));
2363                     x = root;
2364                 }
2365             } else { // symmetric
2366                 Entry<K,V> sib = leftOf(parentOf(x));
2367 
2368                 if (colorOf(sib) == RED) {
2369                     setColor(sib, BLACK);
2370                     setColor(parentOf(x), RED);
2371                     rotateRight(parentOf(x));
2372                     sib = leftOf(parentOf(x));
2373                 }
2374 
2375                 if (colorOf(rightOf(sib)) == BLACK &&
2376                     colorOf(leftOf(sib)) == BLACK) {
2377                     setColor(sib, RED);
2378                     x = parentOf(x);
2379                 } else {
2380                     if (colorOf(leftOf(sib)) == BLACK) {
2381                         setColor(rightOf(sib), BLACK);
2382                         setColor(sib, RED);
2383                         rotateLeft(sib);
2384                         sib = leftOf(parentOf(x));
2385                     }
2386                     setColor(sib, colorOf(parentOf(x)));
2387                     setColor(parentOf(x), BLACK);
2388                     setColor(leftOf(sib), BLACK);
2389                     rotateRight(parentOf(x));
2390                     x = root;
2391                 }
2392             }
2393         }
2394 
2395         setColor(x, BLACK);
2396     }
2397 
2398     private static final long serialVersionUID = 919286545866124006L;
2399 
2400     /**
2401      * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2402      * serialize it).
2403      *
2404      * @serialData The <em>size</em> of the TreeMap (the number of key-value
2405      *             mappings) is emitted (int), followed by the key (Object)
2406      *             and value (Object) for each key-value mapping represented
2407      *             by the TreeMap. The key-value mappings are emitted in
2408      *             key-order (as determined by the TreeMap's Comparator,
2409      *             or by the keys' natural ordering if the TreeMap has no
2410      *             Comparator).
2411      */
2412     private void writeObject(java.io.ObjectOutputStream s)
2413         throws java.io.IOException {
2414         // Write out the Comparator and any hidden stuff
2415         s.defaultWriteObject();
2416 
2417         // Write out size (number of Mappings)
2418         s.writeInt(size);
2419 
2420         // Write out keys and values (alternating)
2421         for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2422             Map.Entry<K,V> e = i.next();
2423             s.writeObject(e.getKey());
2424             s.writeObject(e.getValue());
2425         }
2426     }
2427 
2428     /**
2429      * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2430      * deserialize it).
2431      */
2432     private void readObject(final java.io.ObjectInputStream s)
2433         throws java.io.IOException, ClassNotFoundException {
2434         // Read in the Comparator and any hidden stuff
2435         s.defaultReadObject();
2436 
2437         // Read in size
2438         int size = s.readInt();
2439 
2440         buildFromSorted(size, null, s, null);
2441     }
2442 
2443     /** Intended to be called only from TreeSet.readObject */
2444     void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2445         throws java.io.IOException, ClassNotFoundException {
2446         buildFromSorted(size, null, s, defaultVal);
2447     }
2448 
2449     /** Intended to be called only from TreeSet.addAll */
2450     void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2451         try {
2452             buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2453         } catch (java.io.IOException cannotHappen) {
2454         } catch (ClassNotFoundException cannotHappen) {
2455         }
2456     }
2457 
2458 
2459     /**
2460      * Linear time tree building algorithm from sorted data.  Can accept keys
2461      * and/or values from iterator or stream. This leads to too many
2462      * parameters, but seems better than alternatives.  The four formats
2463      * that this method accepts are:
2464      *
2465      *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).
2466      *    2) An iterator of keys.         (it != null, defaultVal != null).
2467      *    3) A stream of alternating serialized keys and values.
2468      *                                   (it == null, defaultVal == null).
2469      *    4) A stream of serialized keys. (it == null, defaultVal != null).
2470      *
2471      * It is assumed that the comparator of the TreeMap is already set prior
2472      * to calling this method.
2473      *
2474      * @param size the number of keys (or key-value pairs) to be read from
2475      *        the iterator or stream
2476      * @param it If non-null, new entries are created from entries
2477      *        or keys read from this iterator.
2478      * @param str If non-null, new entries are created from keys and
2479      *        possibly values read from this stream in serialized form.
2480      *        Exactly one of it and str should be non-null.
2481      * @param defaultVal if non-null, this default value is used for
2482      *        each value in the map.  If null, each value is read from
2483      *        iterator or stream, as described above.
2484      * @throws java.io.IOException propagated from stream reads. This cannot
2485      *         occur if str is null.
2486      * @throws ClassNotFoundException propagated from readObject.
2487      *         This cannot occur if str is null.
2488      */
2489     private void buildFromSorted(int size, Iterator<?> it,
2490                                  java.io.ObjectInputStream str,
2491                                  V defaultVal)
2492         throws  java.io.IOException, ClassNotFoundException {
2493         this.size = size;
2494         root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2495                                it, str, defaultVal);
2496     }
2497 
2498     /**
2499      * Recursive "helper method" that does the real work of the
2500      * previous method.  Identically named parameters have
2501      * identical definitions.  Additional parameters are documented below.
2502      * It is assumed that the comparator and size fields of the TreeMap are
2503      * already set prior to calling this method.  (It ignores both fields.)
2504      *
2505      * @param level the current level of tree. Initial call should be 0.
2506      * @param lo the first element index of this subtree. Initial should be 0.
2507      * @param hi the last element index of this subtree.  Initial should be
2508      *        size-1.
2509      * @param redLevel the level at which nodes should be red.
2510      *        Must be equal to computeRedLevel for tree of this size.
2511      */
2512     @SuppressWarnings("unchecked")
2513     private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2514                                              int redLevel,
2515                                              Iterator<?> it,
2516                                              java.io.ObjectInputStream str,
2517                                              V defaultVal)
2518         throws  java.io.IOException, ClassNotFoundException {
2519         /*
2520          * Strategy: The root is the middlemost element. To get to it, we
2521          * have to first recursively construct the entire left subtree,
2522          * so as to grab all of its elements. We can then proceed with right
2523          * subtree.
2524          *
2525          * The lo and hi arguments are the minimum and maximum
2526          * indices to pull out of the iterator or stream for current subtree.
2527          * They are not actually indexed, we just proceed sequentially,
2528          * ensuring that items are extracted in corresponding order.
2529          */
2530 
2531         if (hi < lo) return null;
2532 
2533         int mid = (lo + hi) >>> 1;
2534 
2535         Entry<K,V> left  = null;
2536         if (lo < mid)
2537             left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2538                                    it, str, defaultVal);
2539 
2540         // extract key and/or value from iterator or stream
2541         K key;
2542         V value;
2543         if (it != null) {
2544             if (defaultVal==null) {
2545                 Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
2546                 key = (K)entry.getKey();
2547                 value = (V)entry.getValue();
2548             } else {
2549                 key = (K)it.next();
2550                 value = defaultVal;
2551             }
2552         } else { // use stream
2553             key = (K) str.readObject();
2554             value = (defaultVal != null ? defaultVal : (V) str.readObject());
2555         }
2556 
2557         Entry<K,V> middle =  new Entry<>(key, value, null);
2558 
2559         // color nodes in non-full bottommost level red
2560         if (level == redLevel)
2561             middle.color = RED;
2562 
2563         if (left != null) {
2564             middle.left = left;
2565             left.parent = middle;
2566         }
2567 
2568         if (mid < hi) {
2569             Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2570                                                it, str, defaultVal);
2571             middle.right = right;
2572             right.parent = middle;
2573         }
2574 
2575         return middle;
2576     }
2577 
2578     /**
2579      * Find the level down to which to assign all nodes BLACK.  This is the
2580      * last `full' level of the complete binary tree produced by
2581      * buildTree. The remaining nodes are colored RED. (This makes a `nice'
2582      * set of color assignments wrt future insertions.) This level number is
2583      * computed by finding the number of splits needed to reach the zeroeth
2584      * node.  (The answer is ~lg(N), but in any case must be computed by same
2585      * quick O(lg(N)) loop.)
2586      */
2587     private static int computeRedLevel(int sz) {
2588         int level = 0;
2589         for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2590             level++;
2591         return level;
2592     }
2593 
2594     /**
2595      * Currently, we support Spliterator-based versions only for the
2596      * full map, in either plain of descending form, otherwise relying
2597      * on defaults because size estimation for submaps would dominate
2598      * costs. The type tests needed to check these for key views are
2599      * not very nice but avoid disrupting existing class
2600      * structures. Callers must use plain default spliterators if this
2601      * returns null.
2602      */
2603     static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
2604         if (m instanceof TreeMap) {
2605             @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2606                 (TreeMap<K,Object>) m;
2607             return t.keySpliterator();
2608         }
2609         if (m instanceof DescendingSubMap) {
2610             @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
2611                 (DescendingSubMap<K,?>) m;
2612             TreeMap<K,?> tm = dm.m;
2613             if (dm == tm.descendingMap) {
2614                 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2615                     (TreeMap<K,Object>) tm;
2616                 return t.descendingKeySpliterator();
2617             }
2618         }
2619         @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
2620             (NavigableSubMap<K,?>) m;
2621         return sm.keySpliterator();
2622     }
2623 
2624     final Spliterator<K> keySpliterator() {
2625         return new KeySpliterator<K,V>(this, null, null, 0, -1, 0);
2626     }
2627 
2628     final Spliterator<K> descendingKeySpliterator() {
2629         return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0);
2630     }
2631 
2632     /**
2633      * Base class for spliterators.  Iteration starts at a given
2634      * origin and continues up to but not including a given fence (or
2635      * null for end).  At top-level, for ascending cases, the first
2636      * split uses the root as left-fence/right-origin. From there,
2637      * right-hand splits replace the current fence with its left
2638      * child, also serving as origin for the split-off spliterator.
2639      * Left-hands are symmetric. Descending versions place the origin
2640      * at the end and invert ascending split rules.  This base class
2641      * is non-commital about directionality, or whether the top-level
2642      * spliterator covers the whole tree. This means that the actual
2643      * split mechanics are located in subclasses. Some of the subclass
2644      * trySplit methods are identical (except for return types), but
2645      * not nicely factorable.
2646      *
2647      * Currently, subclass versions exist only for the full map
2648      * (including descending keys via its descendingMap).  Others are
2649      * possible but currently not worthwhile because submaps require
2650      * O(n) computations to determine size, which substantially limits
2651      * potential speed-ups of using custom Spliterators versus default
2652      * mechanics.
2653      *
2654      * To boostrap initialization, external constructors use
2655      * negative size estimates: -1 for ascend, -2 for descend.
2656      */
2657     static class TreeMapSpliterator<K,V> {
2658         final TreeMap<K,V> tree;
2659         TreeMap.Entry<K,V> current; // traverser; initially first node in range
2660         TreeMap.Entry<K,V> fence;   // one past last, or null
2661         int side;                   // 0: top, -1: is a left split, +1: right
2662         int est;                    // size estimate (exact only for top-level)
2663         int expectedModCount;       // for CME checks
2664 
2665         TreeMapSpliterator(TreeMap<K,V> tree,
2666                            TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2667                            int side, int est, int expectedModCount) {
2668             this.tree = tree;
2669             this.current = origin;
2670             this.fence = fence;
2671             this.side = side;
2672             this.est = est;
2673             this.expectedModCount = expectedModCount;
2674         }
2675 
2676         final int getEstimate() { // force initialization
2677             int s; TreeMap<K,V> t;
2678             if ((s = est) < 0) {
2679                 if ((t = tree) != null) {
2680                     current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
2681                     s = est = t.size;
2682                     expectedModCount = t.modCount;
2683                 }
2684                 else
2685                     s = est = 0;
2686             }
2687             return s;
2688         }
2689 
2690         public final long estimateSize() {
2691             return (long)getEstimate();
2692         }
2693     }
2694 
2695     static final class KeySpliterator<K,V>
2696         extends TreeMapSpliterator<K,V>
2697         implements Spliterator<K> {
2698         KeySpliterator(TreeMap<K,V> tree,
2699                        TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2700                        int side, int est, int expectedModCount) {
2701             super(tree, origin, fence, side, est, expectedModCount);
2702         }
2703 
2704         public KeySpliterator<K,V> trySplit() {
2705             if (est < 0)
2706                 getEstimate(); // force initialization
2707             int d = side;
2708             TreeMap.Entry<K,V> e = current, f = fence,
2709                 s = ((e == null || e == f) ? null :      // empty
2710                      (d == 0)              ? tree.root : // was top
2711                      (d >  0)              ? e.right :   // was right
2712                      (d <  0 && f != null) ? f.left :    // was left
2713                      null);
2714             if (s != null && s != e && s != f &&
2715                 tree.compare(e.key, s.key) < 0) {        // e not already past s
2716                 side = 1;
2717                 return new KeySpliterator<>
2718                     (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2719             }
2720             return null;
2721         }
2722 
2723         public void forEachRemaining(Consumer<? super K> action) {
2724             if (action == null)
2725                 throw new NullPointerException();
2726             if (est < 0)
2727                 getEstimate(); // force initialization
2728             TreeMap.Entry<K,V> f = fence, e, p, pl;
2729             if ((e = current) != null && e != f) {
2730                 current = f; // exhaust
2731                 do {
2732                     action.accept(e.key);
2733                     if ((p = e.right) != null) {
2734                         while ((pl = p.left) != null)
2735                             p = pl;
2736                     }
2737                     else {
2738                         while ((p = e.parent) != null && e == p.right)
2739                             e = p;
2740                     }
2741                 } while ((e = p) != null && e != f);
2742                 if (tree.modCount != expectedModCount)
2743                     throw new ConcurrentModificationException();
2744             }
2745         }
2746 
2747         public boolean tryAdvance(Consumer<? super K> action) {
2748             TreeMap.Entry<K,V> e;
2749             if (action == null)
2750                 throw new NullPointerException();
2751             if (est < 0)
2752                 getEstimate(); // force initialization
2753             if ((e = current) == null || e == fence)
2754                 return false;
2755             current = successor(e);
2756             action.accept(e.key);
2757             if (tree.modCount != expectedModCount)
2758                 throw new ConcurrentModificationException();
2759             return true;
2760         }
2761 
2762         public int characteristics() {
2763             return (side == 0 ? Spliterator.SIZED : 0) |
2764                 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
2765         }
2766 
2767         public final Comparator<? super K>  getComparator() {
2768             return tree.comparator;
2769         }
2770 
2771     }
2772 
2773     static final class DescendingKeySpliterator<K,V>
2774         extends TreeMapSpliterator<K,V>
2775         implements Spliterator<K> {
2776         DescendingKeySpliterator(TreeMap<K,V> tree,
2777                                  TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2778                                  int side, int est, int expectedModCount) {
2779             super(tree, origin, fence, side, est, expectedModCount);
2780         }
2781 
2782         public DescendingKeySpliterator<K,V> trySplit() {
2783             if (est < 0)
2784                 getEstimate(); // force initialization
2785             int d = side;
2786             TreeMap.Entry<K,V> e = current, f = fence,
2787                     s = ((e == null || e == f) ? null :      // empty
2788                          (d == 0)              ? tree.root : // was top
2789                          (d <  0)              ? e.left :    // was left
2790                          (d >  0 && f != null) ? f.right :   // was right
2791                          null);
2792             if (s != null && s != e && s != f &&
2793                 tree.compare(e.key, s.key) > 0) {       // e not already past s
2794                 side = 1;
2795                 return new DescendingKeySpliterator<>
2796                         (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2797             }
2798             return null;
2799         }
2800 
2801         public void forEachRemaining(Consumer<? super K> action) {
2802             if (action == null)
2803                 throw new NullPointerException();
2804             if (est < 0)
2805                 getEstimate(); // force initialization
2806             TreeMap.Entry<K,V> f = fence, e, p, pr;
2807             if ((e = current) != null && e != f) {
2808                 current = f; // exhaust
2809                 do {
2810                     action.accept(e.key);
2811                     if ((p = e.left) != null) {
2812                         while ((pr = p.right) != null)
2813                             p = pr;
2814                     }
2815                     else {
2816                         while ((p = e.parent) != null && e == p.left)
2817                             e = p;
2818                     }
2819                 } while ((e = p) != null && e != f);
2820                 if (tree.modCount != expectedModCount)
2821                     throw new ConcurrentModificationException();
2822             }
2823         }
2824 
2825         public boolean tryAdvance(Consumer<? super K> action) {
2826             TreeMap.Entry<K,V> e;
2827             if (action == null)
2828                 throw new NullPointerException();
2829             if (est < 0)
2830                 getEstimate(); // force initialization
2831             if ((e = current) == null || e == fence)
2832                 return false;
2833             current = predecessor(e);
2834             action.accept(e.key);
2835             if (tree.modCount != expectedModCount)
2836                 throw new ConcurrentModificationException();
2837             return true;
2838         }
2839 
2840         public int characteristics() {
2841             return (side == 0 ? Spliterator.SIZED : 0) |
2842                 Spliterator.DISTINCT | Spliterator.ORDERED;
2843         }
2844     }
2845 
2846     static final class ValueSpliterator<K,V>
2847             extends TreeMapSpliterator<K,V>
2848             implements Spliterator<V> {
2849         ValueSpliterator(TreeMap<K,V> tree,
2850                          TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2851                          int side, int est, int expectedModCount) {
2852             super(tree, origin, fence, side, est, expectedModCount);
2853         }
2854 
2855         public ValueSpliterator<K,V> trySplit() {
2856             if (est < 0)
2857                 getEstimate(); // force initialization
2858             int d = side;
2859             TreeMap.Entry<K,V> e = current, f = fence,
2860                     s = ((e == null || e == f) ? null :      // empty
2861                          (d == 0)              ? tree.root : // was top
2862                          (d >  0)              ? e.right :   // was right
2863                          (d <  0 && f != null) ? f.left :    // was left
2864                          null);
2865             if (s != null && s != e && s != f &&
2866                 tree.compare(e.key, s.key) < 0) {        // e not already past s
2867                 side = 1;
2868                 return new ValueSpliterator<>
2869                         (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2870             }
2871             return null;
2872         }
2873 
2874         public void forEachRemaining(Consumer<? super V> action) {
2875             if (action == null)
2876                 throw new NullPointerException();
2877             if (est < 0)
2878                 getEstimate(); // force initialization
2879             TreeMap.Entry<K,V> f = fence, e, p, pl;
2880             if ((e = current) != null && e != f) {
2881                 current = f; // exhaust
2882                 do {
2883                     action.accept(e.value);
2884                     if ((p = e.right) != null) {
2885                         while ((pl = p.left) != null)
2886                             p = pl;
2887                     }
2888                     else {
2889                         while ((p = e.parent) != null && e == p.right)
2890                             e = p;
2891                     }
2892                 } while ((e = p) != null && e != f);
2893                 if (tree.modCount != expectedModCount)
2894                     throw new ConcurrentModificationException();
2895             }
2896         }
2897 
2898         public boolean tryAdvance(Consumer<? super V> action) {
2899             TreeMap.Entry<K,V> e;
2900             if (action == null)
2901                 throw new NullPointerException();
2902             if (est < 0)
2903                 getEstimate(); // force initialization
2904             if ((e = current) == null || e == fence)
2905                 return false;
2906             current = successor(e);
2907             action.accept(e.value);
2908             if (tree.modCount != expectedModCount)
2909                 throw new ConcurrentModificationException();
2910             return true;
2911         }
2912 
2913         public int characteristics() {
2914             return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.ORDERED;
2915         }
2916     }
2917 
2918     static final class EntrySpliterator<K,V>
2919         extends TreeMapSpliterator<K,V>
2920         implements Spliterator<Map.Entry<K,V>> {
2921         EntrySpliterator(TreeMap<K,V> tree,
2922                          TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2923                          int side, int est, int expectedModCount) {
2924             super(tree, origin, fence, side, est, expectedModCount);
2925         }
2926 
2927         public EntrySpliterator<K,V> trySplit() {
2928             if (est < 0)
2929                 getEstimate(); // force initialization
2930             int d = side;
2931             TreeMap.Entry<K,V> e = current, f = fence,
2932                     s = ((e == null || e == f) ? null :      // empty
2933                          (d == 0)              ? tree.root : // was top
2934                          (d >  0)              ? e.right :   // was right
2935                          (d <  0 && f != null) ? f.left :    // was left
2936                          null);
2937             if (s != null && s != e && s != f &&
2938                 tree.compare(e.key, s.key) < 0) {        // e not already past s
2939                 side = 1;
2940                 return new EntrySpliterator<>
2941                         (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2942             }
2943             return null;
2944         }
2945 
2946         public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
2947             if (action == null)
2948                 throw new NullPointerException();
2949             if (est < 0)
2950                 getEstimate(); // force initialization
2951             TreeMap.Entry<K,V> f = fence, e, p, pl;
2952             if ((e = current) != null && e != f) {
2953                 current = f; // exhaust
2954                 do {
2955                     action.accept(e);
2956                     if ((p = e.right) != null) {
2957                         while ((pl = p.left) != null)
2958                             p = pl;
2959                     }
2960                     else {
2961                         while ((p = e.parent) != null && e == p.right)
2962                             e = p;
2963                     }
2964                 } while ((e = p) != null && e != f);
2965                 if (tree.modCount != expectedModCount)
2966                     throw new ConcurrentModificationException();
2967             }
2968         }
2969 
2970         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
2971             TreeMap.Entry<K,V> e;
2972             if (action == null)
2973                 throw new NullPointerException();
2974             if (est < 0)
2975                 getEstimate(); // force initialization
2976             if ((e = current) == null || e == fence)
2977                 return false;
2978             current = successor(e);
2979             action.accept(e);
2980             if (tree.modCount != expectedModCount)
2981                 throw new ConcurrentModificationException();
2982             return true;
2983         }
2984 
2985         public int characteristics() {
2986             return (side == 0 ? Spliterator.SIZED : 0) |
2987                     Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
2988         }
2989 
2990         @Override
2991         public Comparator<Map.Entry<K, V>> getComparator() {
2992             // Adapt or create a key-based comparator
2993             if (tree.comparator != null) {
2994                 return Map.Entry.comparingByKey(tree.comparator);
2995             }
2996             else {
2997                 return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> {
2998                     @SuppressWarnings("unchecked")
2999                     Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
3000                     return k1.compareTo(e2.getKey());
3001                 };
3002             }
3003         }
3004     }
3005 }