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