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