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