Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    1   /*
    2    * Copyright (c) 1997, 2011, 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   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]