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