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