1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/util/TreeMap.java Sat Sep 07 13:51:24 2013 +0200
1.3 @@ -0,0 +1,2442 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +
1.31 +/**
1.32 + * A Red-Black tree based {@link NavigableMap} implementation.
1.33 + * The map is sorted according to the {@linkplain Comparable natural
1.34 + * ordering} of its keys, or by a {@link Comparator} provided at map
1.35 + * creation time, depending on which constructor is used.
1.36 + *
1.37 + * <p>This implementation provides guaranteed log(n) time cost for the
1.38 + * {@code containsKey}, {@code get}, {@code put} and {@code remove}
1.39 + * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
1.40 + * Rivest's <em>Introduction to Algorithms</em>.
1.41 + *
1.42 + * <p>Note that the ordering maintained by a tree map, like any sorted map, and
1.43 + * whether or not an explicit comparator is provided, must be <em>consistent
1.44 + * with {@code equals}</em> if this sorted map is to correctly implement the
1.45 + * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
1.46 + * precise definition of <em>consistent with equals</em>.) This is so because
1.47 + * the {@code Map} interface is defined in terms of the {@code equals}
1.48 + * operation, but a sorted map performs all key comparisons using its {@code
1.49 + * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
1.50 + * this method are, from the standpoint of the sorted map, equal. The behavior
1.51 + * of a sorted map <em>is</em> well-defined even if its ordering is
1.52 + * inconsistent with {@code equals}; it just fails to obey the general contract
1.53 + * of the {@code Map} interface.
1.54 + *
1.55 + * <p><strong>Note that this implementation is not synchronized.</strong>
1.56 + * If multiple threads access a map concurrently, and at least one of the
1.57 + * threads modifies the map structurally, it <em>must</em> be synchronized
1.58 + * externally. (A structural modification is any operation that adds or
1.59 + * deletes one or more mappings; merely changing the value associated
1.60 + * with an existing key is not a structural modification.) This is
1.61 + * typically accomplished by synchronizing on some object that naturally
1.62 + * encapsulates the map.
1.63 + * If no such object exists, the map should be "wrapped" using the
1.64 + * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
1.65 + * method. This is best done at creation time, to prevent accidental
1.66 + * unsynchronized access to the map: <pre>
1.67 + * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
1.68 + *
1.69 + * <p>The iterators returned by the {@code iterator} method of the collections
1.70 + * returned by all of this class's "collection view methods" are
1.71 + * <em>fail-fast</em>: if the map is structurally modified at any time after
1.72 + * the iterator is created, in any way except through the iterator's own
1.73 + * {@code remove} method, the iterator will throw a {@link
1.74 + * ConcurrentModificationException}. Thus, in the face of concurrent
1.75 + * modification, the iterator fails quickly and cleanly, rather than risking
1.76 + * arbitrary, non-deterministic behavior at an undetermined time in the future.
1.77 + *
1.78 + * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
1.79 + * as it is, generally speaking, impossible to make any hard guarantees in the
1.80 + * presence of unsynchronized concurrent modification. Fail-fast iterators
1.81 + * throw {@code ConcurrentModificationException} on a best-effort basis.
1.82 + * Therefore, it would be wrong to write a program that depended on this
1.83 + * exception for its correctness: <em>the fail-fast behavior of iterators
1.84 + * should be used only to detect bugs.</em>
1.85 + *
1.86 + * <p>All {@code Map.Entry} pairs returned by methods in this class
1.87 + * and its views represent snapshots of mappings at the time they were
1.88 + * produced. They do <strong>not</strong> support the {@code Entry.setValue}
1.89 + * method. (Note however that it is possible to change mappings in the
1.90 + * associated map using {@code put}.)
1.91 + *
1.92 + * <p>This class is a member of the
1.93 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.94 + * Java Collections Framework</a>.
1.95 + *
1.96 + * @param <K> the type of keys maintained by this map
1.97 + * @param <V> the type of mapped values
1.98 + *
1.99 + * @author Josh Bloch and Doug Lea
1.100 + * @see Map
1.101 + * @see HashMap
1.102 + * @see Hashtable
1.103 + * @see Comparable
1.104 + * @see Comparator
1.105 + * @see Collection
1.106 + * @since 1.2
1.107 + */
1.108 +
1.109 +public class TreeMap<K,V>
1.110 + extends AbstractMap<K,V>
1.111 + implements NavigableMap<K,V>, Cloneable, java.io.Serializable
1.112 +{
1.113 + /**
1.114 + * The comparator used to maintain order in this tree map, or
1.115 + * null if it uses the natural ordering of its keys.
1.116 + *
1.117 + * @serial
1.118 + */
1.119 + private final Comparator<? super K> comparator;
1.120 +
1.121 + private transient Entry<K,V> root = null;
1.122 +
1.123 + /**
1.124 + * The number of entries in the tree
1.125 + */
1.126 + private transient int size = 0;
1.127 +
1.128 + /**
1.129 + * The number of structural modifications to the tree.
1.130 + */
1.131 + private transient int modCount = 0;
1.132 +
1.133 + /**
1.134 + * Constructs a new, empty tree map, using the natural ordering of its
1.135 + * keys. All keys inserted into the map must implement the {@link
1.136 + * Comparable} interface. Furthermore, all such keys must be
1.137 + * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
1.138 + * a {@code ClassCastException} for any keys {@code k1} and
1.139 + * {@code k2} in the map. If the user attempts to put a key into the
1.140 + * map that violates this constraint (for example, the user attempts to
1.141 + * put a string key into a map whose keys are integers), the
1.142 + * {@code put(Object key, Object value)} call will throw a
1.143 + * {@code ClassCastException}.
1.144 + */
1.145 + public TreeMap() {
1.146 + comparator = null;
1.147 + }
1.148 +
1.149 + /**
1.150 + * Constructs a new, empty tree map, ordered according to the given
1.151 + * comparator. All keys inserted into the map must be <em>mutually
1.152 + * comparable</em> by the given comparator: {@code comparator.compare(k1,
1.153 + * k2)} must not throw a {@code ClassCastException} for any keys
1.154 + * {@code k1} and {@code k2} in the map. If the user attempts to put
1.155 + * a key into the map that violates this constraint, the {@code put(Object
1.156 + * key, Object value)} call will throw a
1.157 + * {@code ClassCastException}.
1.158 + *
1.159 + * @param comparator the comparator that will be used to order this map.
1.160 + * If {@code null}, the {@linkplain Comparable natural
1.161 + * ordering} of the keys will be used.
1.162 + */
1.163 + public TreeMap(Comparator<? super K> comparator) {
1.164 + this.comparator = comparator;
1.165 + }
1.166 +
1.167 + /**
1.168 + * Constructs a new tree map containing the same mappings as the given
1.169 + * map, ordered according to the <em>natural ordering</em> of its keys.
1.170 + * All keys inserted into the new map must implement the {@link
1.171 + * Comparable} interface. Furthermore, all such keys must be
1.172 + * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
1.173 + * a {@code ClassCastException} for any keys {@code k1} and
1.174 + * {@code k2} in the map. This method runs in n*log(n) time.
1.175 + *
1.176 + * @param m the map whose mappings are to be placed in this map
1.177 + * @throws ClassCastException if the keys in m are not {@link Comparable},
1.178 + * or are not mutually comparable
1.179 + * @throws NullPointerException if the specified map is null
1.180 + */
1.181 + public TreeMap(Map<? extends K, ? extends V> m) {
1.182 + comparator = null;
1.183 + putAll(m);
1.184 + }
1.185 +
1.186 + /**
1.187 + * Constructs a new tree map containing the same mappings and
1.188 + * using the same ordering as the specified sorted map. This
1.189 + * method runs in linear time.
1.190 + *
1.191 + * @param m the sorted map whose mappings are to be placed in this map,
1.192 + * and whose comparator is to be used to sort this map
1.193 + * @throws NullPointerException if the specified map is null
1.194 + */
1.195 + public TreeMap(SortedMap<K, ? extends V> m) {
1.196 + comparator = m.comparator();
1.197 + try {
1.198 + buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
1.199 + } catch (java.io.IOException cannotHappen) {
1.200 + } catch (ClassNotFoundException cannotHappen) {
1.201 + }
1.202 + }
1.203 +
1.204 +
1.205 + // Query Operations
1.206 +
1.207 + /**
1.208 + * Returns the number of key-value mappings in this map.
1.209 + *
1.210 + * @return the number of key-value mappings in this map
1.211 + */
1.212 + public int size() {
1.213 + return size;
1.214 + }
1.215 +
1.216 + /**
1.217 + * Returns {@code true} if this map contains a mapping for the specified
1.218 + * key.
1.219 + *
1.220 + * @param key key whose presence in this map is to be tested
1.221 + * @return {@code true} if this map contains a mapping for the
1.222 + * specified key
1.223 + * @throws ClassCastException if the specified key cannot be compared
1.224 + * with the keys currently in the map
1.225 + * @throws NullPointerException if the specified key is null
1.226 + * and this map uses natural ordering, or its comparator
1.227 + * does not permit null keys
1.228 + */
1.229 + public boolean containsKey(Object key) {
1.230 + return getEntry(key) != null;
1.231 + }
1.232 +
1.233 + /**
1.234 + * Returns {@code true} if this map maps one or more keys to the
1.235 + * specified value. More formally, returns {@code true} if and only if
1.236 + * this map contains at least one mapping to a value {@code v} such
1.237 + * that {@code (value==null ? v==null : value.equals(v))}. This
1.238 + * operation will probably require time linear in the map size for
1.239 + * most implementations.
1.240 + *
1.241 + * @param value value whose presence in this map is to be tested
1.242 + * @return {@code true} if a mapping to {@code value} exists;
1.243 + * {@code false} otherwise
1.244 + * @since 1.2
1.245 + */
1.246 + public boolean containsValue(Object value) {
1.247 + for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
1.248 + if (valEquals(value, e.value))
1.249 + return true;
1.250 + return false;
1.251 + }
1.252 +
1.253 + /**
1.254 + * Returns the value to which the specified key is mapped,
1.255 + * or {@code null} if this map contains no mapping for the key.
1.256 + *
1.257 + * <p>More formally, if this map contains a mapping from a key
1.258 + * {@code k} to a value {@code v} such that {@code key} compares
1.259 + * equal to {@code k} according to the map's ordering, then this
1.260 + * method returns {@code v}; otherwise it returns {@code null}.
1.261 + * (There can be at most one such mapping.)
1.262 + *
1.263 + * <p>A return value of {@code null} does not <em>necessarily</em>
1.264 + * indicate that the map contains no mapping for the key; it's also
1.265 + * possible that the map explicitly maps the key to {@code null}.
1.266 + * The {@link #containsKey containsKey} operation may be used to
1.267 + * distinguish these two cases.
1.268 + *
1.269 + * @throws ClassCastException if the specified key cannot be compared
1.270 + * with the keys currently in the map
1.271 + * @throws NullPointerException if the specified key is null
1.272 + * and this map uses natural ordering, or its comparator
1.273 + * does not permit null keys
1.274 + */
1.275 + public V get(Object key) {
1.276 + Entry<K,V> p = getEntry(key);
1.277 + return (p==null ? null : p.value);
1.278 + }
1.279 +
1.280 + public Comparator<? super K> comparator() {
1.281 + return comparator;
1.282 + }
1.283 +
1.284 + /**
1.285 + * @throws NoSuchElementException {@inheritDoc}
1.286 + */
1.287 + public K firstKey() {
1.288 + return key(getFirstEntry());
1.289 + }
1.290 +
1.291 + /**
1.292 + * @throws NoSuchElementException {@inheritDoc}
1.293 + */
1.294 + public K lastKey() {
1.295 + return key(getLastEntry());
1.296 + }
1.297 +
1.298 + /**
1.299 + * Copies all of the mappings from the specified map to this map.
1.300 + * These mappings replace any mappings that this map had for any
1.301 + * of the keys currently in the specified map.
1.302 + *
1.303 + * @param map mappings to be stored in this map
1.304 + * @throws ClassCastException if the class of a key or value in
1.305 + * the specified map prevents it from being stored in this map
1.306 + * @throws NullPointerException if the specified map is null or
1.307 + * the specified map contains a null key and this map does not
1.308 + * permit null keys
1.309 + */
1.310 + public void putAll(Map<? extends K, ? extends V> map) {
1.311 + int mapSize = map.size();
1.312 + if (size==0 && mapSize!=0 && map instanceof SortedMap) {
1.313 + Comparator c = ((SortedMap)map).comparator();
1.314 + if (c == comparator || (c != null && c.equals(comparator))) {
1.315 + ++modCount;
1.316 + try {
1.317 + buildFromSorted(mapSize, map.entrySet().iterator(),
1.318 + null, null);
1.319 + } catch (java.io.IOException cannotHappen) {
1.320 + } catch (ClassNotFoundException cannotHappen) {
1.321 + }
1.322 + return;
1.323 + }
1.324 + }
1.325 + super.putAll(map);
1.326 + }
1.327 +
1.328 + /**
1.329 + * Returns this map's entry for the given key, or {@code null} if the map
1.330 + * does not contain an entry for the key.
1.331 + *
1.332 + * @return this map's entry for the given key, or {@code null} if the map
1.333 + * does not contain an entry for the key
1.334 + * @throws ClassCastException if the specified key cannot be compared
1.335 + * with the keys currently in the map
1.336 + * @throws NullPointerException if the specified key is null
1.337 + * and this map uses natural ordering, or its comparator
1.338 + * does not permit null keys
1.339 + */
1.340 + final Entry<K,V> getEntry(Object key) {
1.341 + // Offload comparator-based version for sake of performance
1.342 + if (comparator != null)
1.343 + return getEntryUsingComparator(key);
1.344 + if (key == null)
1.345 + throw new NullPointerException();
1.346 + Comparable<? super K> k = (Comparable<? super K>) key;
1.347 + Entry<K,V> p = root;
1.348 + while (p != null) {
1.349 + int cmp = k.compareTo(p.key);
1.350 + if (cmp < 0)
1.351 + p = p.left;
1.352 + else if (cmp > 0)
1.353 + p = p.right;
1.354 + else
1.355 + return p;
1.356 + }
1.357 + return null;
1.358 + }
1.359 +
1.360 + /**
1.361 + * Version of getEntry using comparator. Split off from getEntry
1.362 + * for performance. (This is not worth doing for most methods,
1.363 + * that are less dependent on comparator performance, but is
1.364 + * worthwhile here.)
1.365 + */
1.366 + final Entry<K,V> getEntryUsingComparator(Object key) {
1.367 + K k = (K) key;
1.368 + Comparator<? super K> cpr = comparator;
1.369 + if (cpr != null) {
1.370 + Entry<K,V> p = root;
1.371 + while (p != null) {
1.372 + int cmp = cpr.compare(k, p.key);
1.373 + if (cmp < 0)
1.374 + p = p.left;
1.375 + else if (cmp > 0)
1.376 + p = p.right;
1.377 + else
1.378 + return p;
1.379 + }
1.380 + }
1.381 + return null;
1.382 + }
1.383 +
1.384 + /**
1.385 + * Gets the entry corresponding to the specified key; if no such entry
1.386 + * exists, returns the entry for the least key greater than the specified
1.387 + * key; if no such entry exists (i.e., the greatest key in the Tree is less
1.388 + * than the specified key), returns {@code null}.
1.389 + */
1.390 + final Entry<K,V> getCeilingEntry(K key) {
1.391 + Entry<K,V> p = root;
1.392 + while (p != null) {
1.393 + int cmp = compare(key, p.key);
1.394 + if (cmp < 0) {
1.395 + if (p.left != null)
1.396 + p = p.left;
1.397 + else
1.398 + return p;
1.399 + } else if (cmp > 0) {
1.400 + if (p.right != null) {
1.401 + p = p.right;
1.402 + } else {
1.403 + Entry<K,V> parent = p.parent;
1.404 + Entry<K,V> ch = p;
1.405 + while (parent != null && ch == parent.right) {
1.406 + ch = parent;
1.407 + parent = parent.parent;
1.408 + }
1.409 + return parent;
1.410 + }
1.411 + } else
1.412 + return p;
1.413 + }
1.414 + return null;
1.415 + }
1.416 +
1.417 + /**
1.418 + * Gets the entry corresponding to the specified key; if no such entry
1.419 + * exists, returns the entry for the greatest key less than the specified
1.420 + * key; if no such entry exists, returns {@code null}.
1.421 + */
1.422 + final Entry<K,V> getFloorEntry(K key) {
1.423 + Entry<K,V> p = root;
1.424 + while (p != null) {
1.425 + int cmp = compare(key, p.key);
1.426 + if (cmp > 0) {
1.427 + if (p.right != null)
1.428 + p = p.right;
1.429 + else
1.430 + return p;
1.431 + } else if (cmp < 0) {
1.432 + if (p.left != null) {
1.433 + p = p.left;
1.434 + } else {
1.435 + Entry<K,V> parent = p.parent;
1.436 + Entry<K,V> ch = p;
1.437 + while (parent != null && ch == parent.left) {
1.438 + ch = parent;
1.439 + parent = parent.parent;
1.440 + }
1.441 + return parent;
1.442 + }
1.443 + } else
1.444 + return p;
1.445 +
1.446 + }
1.447 + return null;
1.448 + }
1.449 +
1.450 + /**
1.451 + * Gets the entry for the least key greater than the specified
1.452 + * key; if no such entry exists, returns the entry for the least
1.453 + * key greater than the specified key; if no such entry exists
1.454 + * returns {@code null}.
1.455 + */
1.456 + final Entry<K,V> getHigherEntry(K key) {
1.457 + Entry<K,V> p = root;
1.458 + while (p != null) {
1.459 + int cmp = compare(key, p.key);
1.460 + if (cmp < 0) {
1.461 + if (p.left != null)
1.462 + p = p.left;
1.463 + else
1.464 + return p;
1.465 + } else {
1.466 + if (p.right != null) {
1.467 + p = p.right;
1.468 + } else {
1.469 + Entry<K,V> parent = p.parent;
1.470 + Entry<K,V> ch = p;
1.471 + while (parent != null && ch == parent.right) {
1.472 + ch = parent;
1.473 + parent = parent.parent;
1.474 + }
1.475 + return parent;
1.476 + }
1.477 + }
1.478 + }
1.479 + return null;
1.480 + }
1.481 +
1.482 + /**
1.483 + * Returns the entry for the greatest key less than the specified key; if
1.484 + * no such entry exists (i.e., the least key in the Tree is greater than
1.485 + * the specified key), returns {@code null}.
1.486 + */
1.487 + final Entry<K,V> getLowerEntry(K key) {
1.488 + Entry<K,V> p = root;
1.489 + while (p != null) {
1.490 + int cmp = compare(key, p.key);
1.491 + if (cmp > 0) {
1.492 + if (p.right != null)
1.493 + p = p.right;
1.494 + else
1.495 + return p;
1.496 + } else {
1.497 + if (p.left != null) {
1.498 + p = p.left;
1.499 + } else {
1.500 + Entry<K,V> parent = p.parent;
1.501 + Entry<K,V> ch = p;
1.502 + while (parent != null && ch == parent.left) {
1.503 + ch = parent;
1.504 + parent = parent.parent;
1.505 + }
1.506 + return parent;
1.507 + }
1.508 + }
1.509 + }
1.510 + return null;
1.511 + }
1.512 +
1.513 + /**
1.514 + * Associates the specified value with the specified key in this map.
1.515 + * If the map previously contained a mapping for the key, the old
1.516 + * value is replaced.
1.517 + *
1.518 + * @param key key with which the specified value is to be associated
1.519 + * @param value value to be associated with the specified key
1.520 + *
1.521 + * @return the previous value associated with {@code key}, or
1.522 + * {@code null} if there was no mapping for {@code key}.
1.523 + * (A {@code null} return can also indicate that the map
1.524 + * previously associated {@code null} with {@code key}.)
1.525 + * @throws ClassCastException if the specified key cannot be compared
1.526 + * with the keys currently in the map
1.527 + * @throws NullPointerException if the specified key is null
1.528 + * and this map uses natural ordering, or its comparator
1.529 + * does not permit null keys
1.530 + */
1.531 + public V put(K key, V value) {
1.532 + Entry<K,V> t = root;
1.533 + if (t == null) {
1.534 + compare(key, key); // type (and possibly null) check
1.535 +
1.536 + root = new Entry<>(key, value, null);
1.537 + size = 1;
1.538 + modCount++;
1.539 + return null;
1.540 + }
1.541 + int cmp;
1.542 + Entry<K,V> parent;
1.543 + // split comparator and comparable paths
1.544 + Comparator<? super K> cpr = comparator;
1.545 + if (cpr != null) {
1.546 + do {
1.547 + parent = t;
1.548 + cmp = cpr.compare(key, t.key);
1.549 + if (cmp < 0)
1.550 + t = t.left;
1.551 + else if (cmp > 0)
1.552 + t = t.right;
1.553 + else
1.554 + return t.setValue(value);
1.555 + } while (t != null);
1.556 + }
1.557 + else {
1.558 + if (key == null)
1.559 + throw new NullPointerException();
1.560 + Comparable<? super K> k = (Comparable<? super K>) key;
1.561 + do {
1.562 + parent = t;
1.563 + cmp = k.compareTo(t.key);
1.564 + if (cmp < 0)
1.565 + t = t.left;
1.566 + else if (cmp > 0)
1.567 + t = t.right;
1.568 + else
1.569 + return t.setValue(value);
1.570 + } while (t != null);
1.571 + }
1.572 + Entry<K,V> e = new Entry<>(key, value, parent);
1.573 + if (cmp < 0)
1.574 + parent.left = e;
1.575 + else
1.576 + parent.right = e;
1.577 + fixAfterInsertion(e);
1.578 + size++;
1.579 + modCount++;
1.580 + return null;
1.581 + }
1.582 +
1.583 + /**
1.584 + * Removes the mapping for this key from this TreeMap if present.
1.585 + *
1.586 + * @param key key for which mapping should be removed
1.587 + * @return the previous value associated with {@code key}, or
1.588 + * {@code null} if there was no mapping for {@code key}.
1.589 + * (A {@code null} return can also indicate that the map
1.590 + * previously associated {@code null} with {@code key}.)
1.591 + * @throws ClassCastException if the specified key cannot be compared
1.592 + * with the keys currently in the map
1.593 + * @throws NullPointerException if the specified key is null
1.594 + * and this map uses natural ordering, or its comparator
1.595 + * does not permit null keys
1.596 + */
1.597 + public V remove(Object key) {
1.598 + Entry<K,V> p = getEntry(key);
1.599 + if (p == null)
1.600 + return null;
1.601 +
1.602 + V oldValue = p.value;
1.603 + deleteEntry(p);
1.604 + return oldValue;
1.605 + }
1.606 +
1.607 + /**
1.608 + * Removes all of the mappings from this map.
1.609 + * The map will be empty after this call returns.
1.610 + */
1.611 + public void clear() {
1.612 + modCount++;
1.613 + size = 0;
1.614 + root = null;
1.615 + }
1.616 +
1.617 + /**
1.618 + * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
1.619 + * values themselves are not cloned.)
1.620 + *
1.621 + * @return a shallow copy of this map
1.622 + */
1.623 + public Object clone() {
1.624 + TreeMap<K,V> clone = null;
1.625 + try {
1.626 + clone = (TreeMap<K,V>) super.clone();
1.627 + } catch (CloneNotSupportedException e) {
1.628 + throw new InternalError();
1.629 + }
1.630 +
1.631 + // Put clone into "virgin" state (except for comparator)
1.632 + clone.root = null;
1.633 + clone.size = 0;
1.634 + clone.modCount = 0;
1.635 + clone.entrySet = null;
1.636 + clone.navigableKeySet = null;
1.637 + clone.descendingMap = null;
1.638 +
1.639 + // Initialize clone with our mappings
1.640 + try {
1.641 + clone.buildFromSorted(size, entrySet().iterator(), null, null);
1.642 + } catch (java.io.IOException cannotHappen) {
1.643 + } catch (ClassNotFoundException cannotHappen) {
1.644 + }
1.645 +
1.646 + return clone;
1.647 + }
1.648 +
1.649 + // NavigableMap API methods
1.650 +
1.651 + /**
1.652 + * @since 1.6
1.653 + */
1.654 + public Map.Entry<K,V> firstEntry() {
1.655 + return exportEntry(getFirstEntry());
1.656 + }
1.657 +
1.658 + /**
1.659 + * @since 1.6
1.660 + */
1.661 + public Map.Entry<K,V> lastEntry() {
1.662 + return exportEntry(getLastEntry());
1.663 + }
1.664 +
1.665 + /**
1.666 + * @since 1.6
1.667 + */
1.668 + public Map.Entry<K,V> pollFirstEntry() {
1.669 + Entry<K,V> p = getFirstEntry();
1.670 + Map.Entry<K,V> result = exportEntry(p);
1.671 + if (p != null)
1.672 + deleteEntry(p);
1.673 + return result;
1.674 + }
1.675 +
1.676 + /**
1.677 + * @since 1.6
1.678 + */
1.679 + public Map.Entry<K,V> pollLastEntry() {
1.680 + Entry<K,V> p = getLastEntry();
1.681 + Map.Entry<K,V> result = exportEntry(p);
1.682 + if (p != null)
1.683 + deleteEntry(p);
1.684 + return result;
1.685 + }
1.686 +
1.687 + /**
1.688 + * @throws ClassCastException {@inheritDoc}
1.689 + * @throws NullPointerException if the specified key is null
1.690 + * and this map uses natural ordering, or its comparator
1.691 + * does not permit null keys
1.692 + * @since 1.6
1.693 + */
1.694 + public Map.Entry<K,V> lowerEntry(K key) {
1.695 + return exportEntry(getLowerEntry(key));
1.696 + }
1.697 +
1.698 + /**
1.699 + * @throws ClassCastException {@inheritDoc}
1.700 + * @throws NullPointerException if the specified key is null
1.701 + * and this map uses natural ordering, or its comparator
1.702 + * does not permit null keys
1.703 + * @since 1.6
1.704 + */
1.705 + public K lowerKey(K key) {
1.706 + return keyOrNull(getLowerEntry(key));
1.707 + }
1.708 +
1.709 + /**
1.710 + * @throws ClassCastException {@inheritDoc}
1.711 + * @throws NullPointerException if the specified key is null
1.712 + * and this map uses natural ordering, or its comparator
1.713 + * does not permit null keys
1.714 + * @since 1.6
1.715 + */
1.716 + public Map.Entry<K,V> floorEntry(K key) {
1.717 + return exportEntry(getFloorEntry(key));
1.718 + }
1.719 +
1.720 + /**
1.721 + * @throws ClassCastException {@inheritDoc}
1.722 + * @throws NullPointerException if the specified key is null
1.723 + * and this map uses natural ordering, or its comparator
1.724 + * does not permit null keys
1.725 + * @since 1.6
1.726 + */
1.727 + public K floorKey(K key) {
1.728 + return keyOrNull(getFloorEntry(key));
1.729 + }
1.730 +
1.731 + /**
1.732 + * @throws ClassCastException {@inheritDoc}
1.733 + * @throws NullPointerException if the specified key is null
1.734 + * and this map uses natural ordering, or its comparator
1.735 + * does not permit null keys
1.736 + * @since 1.6
1.737 + */
1.738 + public Map.Entry<K,V> ceilingEntry(K key) {
1.739 + return exportEntry(getCeilingEntry(key));
1.740 + }
1.741 +
1.742 + /**
1.743 + * @throws ClassCastException {@inheritDoc}
1.744 + * @throws NullPointerException if the specified key is null
1.745 + * and this map uses natural ordering, or its comparator
1.746 + * does not permit null keys
1.747 + * @since 1.6
1.748 + */
1.749 + public K ceilingKey(K key) {
1.750 + return keyOrNull(getCeilingEntry(key));
1.751 + }
1.752 +
1.753 + /**
1.754 + * @throws ClassCastException {@inheritDoc}
1.755 + * @throws NullPointerException if the specified key is null
1.756 + * and this map uses natural ordering, or its comparator
1.757 + * does not permit null keys
1.758 + * @since 1.6
1.759 + */
1.760 + public Map.Entry<K,V> higherEntry(K key) {
1.761 + return exportEntry(getHigherEntry(key));
1.762 + }
1.763 +
1.764 + /**
1.765 + * @throws ClassCastException {@inheritDoc}
1.766 + * @throws NullPointerException if the specified key is null
1.767 + * and this map uses natural ordering, or its comparator
1.768 + * does not permit null keys
1.769 + * @since 1.6
1.770 + */
1.771 + public K higherKey(K key) {
1.772 + return keyOrNull(getHigherEntry(key));
1.773 + }
1.774 +
1.775 + // Views
1.776 +
1.777 + /**
1.778 + * Fields initialized to contain an instance of the entry set view
1.779 + * the first time this view is requested. Views are stateless, so
1.780 + * there's no reason to create more than one.
1.781 + */
1.782 + private transient EntrySet entrySet = null;
1.783 + private transient KeySet<K> navigableKeySet = null;
1.784 + private transient NavigableMap<K,V> descendingMap = null;
1.785 +
1.786 + /**
1.787 + * Returns a {@link Set} view of the keys contained in this map.
1.788 + * The set's iterator returns the keys in ascending order.
1.789 + * The set is backed by the map, so changes to the map are
1.790 + * reflected in the set, and vice-versa. If the map is modified
1.791 + * while an iteration over the set is in progress (except through
1.792 + * the iterator's own {@code remove} operation), the results of
1.793 + * the iteration are undefined. The set supports element removal,
1.794 + * which removes the corresponding mapping from the map, via the
1.795 + * {@code Iterator.remove}, {@code Set.remove},
1.796 + * {@code removeAll}, {@code retainAll}, and {@code clear}
1.797 + * operations. It does not support the {@code add} or {@code addAll}
1.798 + * operations.
1.799 + */
1.800 + public Set<K> keySet() {
1.801 + return navigableKeySet();
1.802 + }
1.803 +
1.804 + /**
1.805 + * @since 1.6
1.806 + */
1.807 + public NavigableSet<K> navigableKeySet() {
1.808 + KeySet<K> nks = navigableKeySet;
1.809 + return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
1.810 + }
1.811 +
1.812 + /**
1.813 + * @since 1.6
1.814 + */
1.815 + public NavigableSet<K> descendingKeySet() {
1.816 + return descendingMap().navigableKeySet();
1.817 + }
1.818 +
1.819 + /**
1.820 + * Returns a {@link Collection} view of the values contained in this map.
1.821 + * The collection's iterator returns the values in ascending order
1.822 + * of the corresponding keys.
1.823 + * The collection is backed by the map, so changes to the map are
1.824 + * reflected in the collection, and vice-versa. If the map is
1.825 + * modified while an iteration over the collection is in progress
1.826 + * (except through the iterator's own {@code remove} operation),
1.827 + * the results of the iteration are undefined. The collection
1.828 + * supports element removal, which removes the corresponding
1.829 + * mapping from the map, via the {@code Iterator.remove},
1.830 + * {@code Collection.remove}, {@code removeAll},
1.831 + * {@code retainAll} and {@code clear} operations. It does not
1.832 + * support the {@code add} or {@code addAll} operations.
1.833 + */
1.834 + public Collection<V> values() {
1.835 + Collection<V> vs = values;
1.836 + return (vs != null) ? vs : (values = new Values());
1.837 + }
1.838 +
1.839 + /**
1.840 + * Returns a {@link Set} view of the mappings contained in this map.
1.841 + * The set's iterator returns the entries in ascending key order.
1.842 + * The set is backed by the map, so changes to the map are
1.843 + * reflected in the set, and vice-versa. If the map is modified
1.844 + * while an iteration over the set is in progress (except through
1.845 + * the iterator's own {@code remove} operation, or through the
1.846 + * {@code setValue} operation on a map entry returned by the
1.847 + * iterator) the results of the iteration are undefined. The set
1.848 + * supports element removal, which removes the corresponding
1.849 + * mapping from the map, via the {@code Iterator.remove},
1.850 + * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
1.851 + * {@code clear} operations. It does not support the
1.852 + * {@code add} or {@code addAll} operations.
1.853 + */
1.854 + public Set<Map.Entry<K,V>> entrySet() {
1.855 + EntrySet es = entrySet;
1.856 + return (es != null) ? es : (entrySet = new EntrySet());
1.857 + }
1.858 +
1.859 + /**
1.860 + * @since 1.6
1.861 + */
1.862 + public NavigableMap<K, V> descendingMap() {
1.863 + NavigableMap<K, V> km = descendingMap;
1.864 + return (km != null) ? km :
1.865 + (descendingMap = new DescendingSubMap(this,
1.866 + true, null, true,
1.867 + true, null, true));
1.868 + }
1.869 +
1.870 + /**
1.871 + * @throws ClassCastException {@inheritDoc}
1.872 + * @throws NullPointerException if {@code fromKey} or {@code toKey} is
1.873 + * null and this map uses natural ordering, or its comparator
1.874 + * does not permit null keys
1.875 + * @throws IllegalArgumentException {@inheritDoc}
1.876 + * @since 1.6
1.877 + */
1.878 + public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1.879 + K toKey, boolean toInclusive) {
1.880 + return new AscendingSubMap(this,
1.881 + false, fromKey, fromInclusive,
1.882 + false, toKey, toInclusive);
1.883 + }
1.884 +
1.885 + /**
1.886 + * @throws ClassCastException {@inheritDoc}
1.887 + * @throws NullPointerException if {@code toKey} is null
1.888 + * and this map uses natural ordering, or its comparator
1.889 + * does not permit null keys
1.890 + * @throws IllegalArgumentException {@inheritDoc}
1.891 + * @since 1.6
1.892 + */
1.893 + public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1.894 + return new AscendingSubMap(this,
1.895 + true, null, true,
1.896 + false, toKey, inclusive);
1.897 + }
1.898 +
1.899 + /**
1.900 + * @throws ClassCastException {@inheritDoc}
1.901 + * @throws NullPointerException if {@code fromKey} is null
1.902 + * and this map uses natural ordering, or its comparator
1.903 + * does not permit null keys
1.904 + * @throws IllegalArgumentException {@inheritDoc}
1.905 + * @since 1.6
1.906 + */
1.907 + public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1.908 + return new AscendingSubMap(this,
1.909 + false, fromKey, inclusive,
1.910 + true, null, true);
1.911 + }
1.912 +
1.913 + /**
1.914 + * @throws ClassCastException {@inheritDoc}
1.915 + * @throws NullPointerException if {@code fromKey} or {@code toKey} is
1.916 + * null and this map uses natural ordering, or its comparator
1.917 + * does not permit null keys
1.918 + * @throws IllegalArgumentException {@inheritDoc}
1.919 + */
1.920 + public SortedMap<K,V> subMap(K fromKey, K toKey) {
1.921 + return subMap(fromKey, true, toKey, false);
1.922 + }
1.923 +
1.924 + /**
1.925 + * @throws ClassCastException {@inheritDoc}
1.926 + * @throws NullPointerException if {@code toKey} is null
1.927 + * and this map uses natural ordering, or its comparator
1.928 + * does not permit null keys
1.929 + * @throws IllegalArgumentException {@inheritDoc}
1.930 + */
1.931 + public SortedMap<K,V> headMap(K toKey) {
1.932 + return headMap(toKey, false);
1.933 + }
1.934 +
1.935 + /**
1.936 + * @throws ClassCastException {@inheritDoc}
1.937 + * @throws NullPointerException if {@code fromKey} is null
1.938 + * and this map uses natural ordering, or its comparator
1.939 + * does not permit null keys
1.940 + * @throws IllegalArgumentException {@inheritDoc}
1.941 + */
1.942 + public SortedMap<K,V> tailMap(K fromKey) {
1.943 + return tailMap(fromKey, true);
1.944 + }
1.945 +
1.946 + // View class support
1.947 +
1.948 + class Values extends AbstractCollection<V> {
1.949 + public Iterator<V> iterator() {
1.950 + return new ValueIterator(getFirstEntry());
1.951 + }
1.952 +
1.953 + public int size() {
1.954 + return TreeMap.this.size();
1.955 + }
1.956 +
1.957 + public boolean contains(Object o) {
1.958 + return TreeMap.this.containsValue(o);
1.959 + }
1.960 +
1.961 + public boolean remove(Object o) {
1.962 + for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
1.963 + if (valEquals(e.getValue(), o)) {
1.964 + deleteEntry(e);
1.965 + return true;
1.966 + }
1.967 + }
1.968 + return false;
1.969 + }
1.970 +
1.971 + public void clear() {
1.972 + TreeMap.this.clear();
1.973 + }
1.974 + }
1.975 +
1.976 + class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1.977 + public Iterator<Map.Entry<K,V>> iterator() {
1.978 + return new EntryIterator(getFirstEntry());
1.979 + }
1.980 +
1.981 + public boolean contains(Object o) {
1.982 + if (!(o instanceof Map.Entry))
1.983 + return false;
1.984 + Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1.985 + V value = entry.getValue();
1.986 + Entry<K,V> p = getEntry(entry.getKey());
1.987 + return p != null && valEquals(p.getValue(), value);
1.988 + }
1.989 +
1.990 + public boolean remove(Object o) {
1.991 + if (!(o instanceof Map.Entry))
1.992 + return false;
1.993 + Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1.994 + V value = entry.getValue();
1.995 + Entry<K,V> p = getEntry(entry.getKey());
1.996 + if (p != null && valEquals(p.getValue(), value)) {
1.997 + deleteEntry(p);
1.998 + return true;
1.999 + }
1.1000 + return false;
1.1001 + }
1.1002 +
1.1003 + public int size() {
1.1004 + return TreeMap.this.size();
1.1005 + }
1.1006 +
1.1007 + public void clear() {
1.1008 + TreeMap.this.clear();
1.1009 + }
1.1010 + }
1.1011 +
1.1012 + /*
1.1013 + * Unlike Values and EntrySet, the KeySet class is static,
1.1014 + * delegating to a NavigableMap to allow use by SubMaps, which
1.1015 + * outweighs the ugliness of needing type-tests for the following
1.1016 + * Iterator methods that are defined appropriately in main versus
1.1017 + * submap classes.
1.1018 + */
1.1019 +
1.1020 + Iterator<K> keyIterator() {
1.1021 + return new KeyIterator(getFirstEntry());
1.1022 + }
1.1023 +
1.1024 + Iterator<K> descendingKeyIterator() {
1.1025 + return new DescendingKeyIterator(getLastEntry());
1.1026 + }
1.1027 +
1.1028 + static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1.1029 + private final NavigableMap<E, Object> m;
1.1030 + KeySet(NavigableMap<E,Object> map) { m = map; }
1.1031 +
1.1032 + public Iterator<E> iterator() {
1.1033 + if (m instanceof TreeMap)
1.1034 + return ((TreeMap<E,Object>)m).keyIterator();
1.1035 + else
1.1036 + return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1.1037 + }
1.1038 +
1.1039 + public Iterator<E> descendingIterator() {
1.1040 + if (m instanceof TreeMap)
1.1041 + return ((TreeMap<E,Object>)m).descendingKeyIterator();
1.1042 + else
1.1043 + return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1.1044 + }
1.1045 +
1.1046 + public int size() { return m.size(); }
1.1047 + public boolean isEmpty() { return m.isEmpty(); }
1.1048 + public boolean contains(Object o) { return m.containsKey(o); }
1.1049 + public void clear() { m.clear(); }
1.1050 + public E lower(E e) { return m.lowerKey(e); }
1.1051 + public E floor(E e) { return m.floorKey(e); }
1.1052 + public E ceiling(E e) { return m.ceilingKey(e); }
1.1053 + public E higher(E e) { return m.higherKey(e); }
1.1054 + public E first() { return m.firstKey(); }
1.1055 + public E last() { return m.lastKey(); }
1.1056 + public Comparator<? super E> comparator() { return m.comparator(); }
1.1057 + public E pollFirst() {
1.1058 + Map.Entry<E,Object> e = m.pollFirstEntry();
1.1059 + return (e == null) ? null : e.getKey();
1.1060 + }
1.1061 + public E pollLast() {
1.1062 + Map.Entry<E,Object> e = m.pollLastEntry();
1.1063 + return (e == null) ? null : e.getKey();
1.1064 + }
1.1065 + public boolean remove(Object o) {
1.1066 + int oldSize = size();
1.1067 + m.remove(o);
1.1068 + return size() != oldSize;
1.1069 + }
1.1070 + public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1.1071 + E toElement, boolean toInclusive) {
1.1072 + return new KeySet<>(m.subMap(fromElement, fromInclusive,
1.1073 + toElement, toInclusive));
1.1074 + }
1.1075 + public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1.1076 + return new KeySet<>(m.headMap(toElement, inclusive));
1.1077 + }
1.1078 + public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1.1079 + return new KeySet<>(m.tailMap(fromElement, inclusive));
1.1080 + }
1.1081 + public SortedSet<E> subSet(E fromElement, E toElement) {
1.1082 + return subSet(fromElement, true, toElement, false);
1.1083 + }
1.1084 + public SortedSet<E> headSet(E toElement) {
1.1085 + return headSet(toElement, false);
1.1086 + }
1.1087 + public SortedSet<E> tailSet(E fromElement) {
1.1088 + return tailSet(fromElement, true);
1.1089 + }
1.1090 + public NavigableSet<E> descendingSet() {
1.1091 + return new KeySet(m.descendingMap());
1.1092 + }
1.1093 + }
1.1094 +
1.1095 + /**
1.1096 + * Base class for TreeMap Iterators
1.1097 + */
1.1098 + abstract class PrivateEntryIterator<T> implements Iterator<T> {
1.1099 + Entry<K,V> next;
1.1100 + Entry<K,V> lastReturned;
1.1101 + int expectedModCount;
1.1102 +
1.1103 + PrivateEntryIterator(Entry<K,V> first) {
1.1104 + expectedModCount = modCount;
1.1105 + lastReturned = null;
1.1106 + next = first;
1.1107 + }
1.1108 +
1.1109 + public final boolean hasNext() {
1.1110 + return next != null;
1.1111 + }
1.1112 +
1.1113 + final Entry<K,V> nextEntry() {
1.1114 + Entry<K,V> e = next;
1.1115 + if (e == null)
1.1116 + throw new NoSuchElementException();
1.1117 + if (modCount != expectedModCount)
1.1118 + throw new ConcurrentModificationException();
1.1119 + next = successor(e);
1.1120 + lastReturned = e;
1.1121 + return e;
1.1122 + }
1.1123 +
1.1124 + final Entry<K,V> prevEntry() {
1.1125 + Entry<K,V> e = next;
1.1126 + if (e == null)
1.1127 + throw new NoSuchElementException();
1.1128 + if (modCount != expectedModCount)
1.1129 + throw new ConcurrentModificationException();
1.1130 + next = predecessor(e);
1.1131 + lastReturned = e;
1.1132 + return e;
1.1133 + }
1.1134 +
1.1135 + public void remove() {
1.1136 + if (lastReturned == null)
1.1137 + throw new IllegalStateException();
1.1138 + if (modCount != expectedModCount)
1.1139 + throw new ConcurrentModificationException();
1.1140 + // deleted entries are replaced by their successors
1.1141 + if (lastReturned.left != null && lastReturned.right != null)
1.1142 + next = lastReturned;
1.1143 + deleteEntry(lastReturned);
1.1144 + expectedModCount = modCount;
1.1145 + lastReturned = null;
1.1146 + }
1.1147 + }
1.1148 +
1.1149 + final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1.1150 + EntryIterator(Entry<K,V> first) {
1.1151 + super(first);
1.1152 + }
1.1153 + public Map.Entry<K,V> next() {
1.1154 + return nextEntry();
1.1155 + }
1.1156 + }
1.1157 +
1.1158 + final class ValueIterator extends PrivateEntryIterator<V> {
1.1159 + ValueIterator(Entry<K,V> first) {
1.1160 + super(first);
1.1161 + }
1.1162 + public V next() {
1.1163 + return nextEntry().value;
1.1164 + }
1.1165 + }
1.1166 +
1.1167 + final class KeyIterator extends PrivateEntryIterator<K> {
1.1168 + KeyIterator(Entry<K,V> first) {
1.1169 + super(first);
1.1170 + }
1.1171 + public K next() {
1.1172 + return nextEntry().key;
1.1173 + }
1.1174 + }
1.1175 +
1.1176 + final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1.1177 + DescendingKeyIterator(Entry<K,V> first) {
1.1178 + super(first);
1.1179 + }
1.1180 + public K next() {
1.1181 + return prevEntry().key;
1.1182 + }
1.1183 + }
1.1184 +
1.1185 + // Little utilities
1.1186 +
1.1187 + /**
1.1188 + * Compares two keys using the correct comparison method for this TreeMap.
1.1189 + */
1.1190 + final int compare(Object k1, Object k2) {
1.1191 + return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1.1192 + : comparator.compare((K)k1, (K)k2);
1.1193 + }
1.1194 +
1.1195 + /**
1.1196 + * Test two values for equality. Differs from o1.equals(o2) only in
1.1197 + * that it copes with {@code null} o1 properly.
1.1198 + */
1.1199 + static final boolean valEquals(Object o1, Object o2) {
1.1200 + return (o1==null ? o2==null : o1.equals(o2));
1.1201 + }
1.1202 +
1.1203 + /**
1.1204 + * Return SimpleImmutableEntry for entry, or null if null
1.1205 + */
1.1206 + static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1.1207 + return (e == null) ? null :
1.1208 + new AbstractMap.SimpleImmutableEntry<>(e);
1.1209 + }
1.1210 +
1.1211 + /**
1.1212 + * Return key for entry, or null if null
1.1213 + */
1.1214 + static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1.1215 + return (e == null) ? null : e.key;
1.1216 + }
1.1217 +
1.1218 + /**
1.1219 + * Returns the key corresponding to the specified Entry.
1.1220 + * @throws NoSuchElementException if the Entry is null
1.1221 + */
1.1222 + static <K> K key(Entry<K,?> e) {
1.1223 + if (e==null)
1.1224 + throw new NoSuchElementException();
1.1225 + return e.key;
1.1226 + }
1.1227 +
1.1228 +
1.1229 + // SubMaps
1.1230 +
1.1231 + /**
1.1232 + * Dummy value serving as unmatchable fence key for unbounded
1.1233 + * SubMapIterators
1.1234 + */
1.1235 + private static final Object UNBOUNDED = new Object();
1.1236 +
1.1237 + /**
1.1238 + * @serial include
1.1239 + */
1.1240 + abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1.1241 + implements NavigableMap<K,V>, java.io.Serializable {
1.1242 + /**
1.1243 + * The backing map.
1.1244 + */
1.1245 + final TreeMap<K,V> m;
1.1246 +
1.1247 + /**
1.1248 + * Endpoints are represented as triples (fromStart, lo,
1.1249 + * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1.1250 + * true, then the low (absolute) bound is the start of the
1.1251 + * backing map, and the other values are ignored. Otherwise,
1.1252 + * if loInclusive is true, lo is the inclusive bound, else lo
1.1253 + * is the exclusive bound. Similarly for the upper bound.
1.1254 + */
1.1255 + final K lo, hi;
1.1256 + final boolean fromStart, toEnd;
1.1257 + final boolean loInclusive, hiInclusive;
1.1258 +
1.1259 + NavigableSubMap(TreeMap<K,V> m,
1.1260 + boolean fromStart, K lo, boolean loInclusive,
1.1261 + boolean toEnd, K hi, boolean hiInclusive) {
1.1262 + if (!fromStart && !toEnd) {
1.1263 + if (m.compare(lo, hi) > 0)
1.1264 + throw new IllegalArgumentException("fromKey > toKey");
1.1265 + } else {
1.1266 + if (!fromStart) // type check
1.1267 + m.compare(lo, lo);
1.1268 + if (!toEnd)
1.1269 + m.compare(hi, hi);
1.1270 + }
1.1271 +
1.1272 + this.m = m;
1.1273 + this.fromStart = fromStart;
1.1274 + this.lo = lo;
1.1275 + this.loInclusive = loInclusive;
1.1276 + this.toEnd = toEnd;
1.1277 + this.hi = hi;
1.1278 + this.hiInclusive = hiInclusive;
1.1279 + }
1.1280 +
1.1281 + // internal utilities
1.1282 +
1.1283 + final boolean tooLow(Object key) {
1.1284 + if (!fromStart) {
1.1285 + int c = m.compare(key, lo);
1.1286 + if (c < 0 || (c == 0 && !loInclusive))
1.1287 + return true;
1.1288 + }
1.1289 + return false;
1.1290 + }
1.1291 +
1.1292 + final boolean tooHigh(Object key) {
1.1293 + if (!toEnd) {
1.1294 + int c = m.compare(key, hi);
1.1295 + if (c > 0 || (c == 0 && !hiInclusive))
1.1296 + return true;
1.1297 + }
1.1298 + return false;
1.1299 + }
1.1300 +
1.1301 + final boolean inRange(Object key) {
1.1302 + return !tooLow(key) && !tooHigh(key);
1.1303 + }
1.1304 +
1.1305 + final boolean inClosedRange(Object key) {
1.1306 + return (fromStart || m.compare(key, lo) >= 0)
1.1307 + && (toEnd || m.compare(hi, key) >= 0);
1.1308 + }
1.1309 +
1.1310 + final boolean inRange(Object key, boolean inclusive) {
1.1311 + return inclusive ? inRange(key) : inClosedRange(key);
1.1312 + }
1.1313 +
1.1314 + /*
1.1315 + * Absolute versions of relation operations.
1.1316 + * Subclasses map to these using like-named "sub"
1.1317 + * versions that invert senses for descending maps
1.1318 + */
1.1319 +
1.1320 + final TreeMap.Entry<K,V> absLowest() {
1.1321 + TreeMap.Entry<K,V> e =
1.1322 + (fromStart ? m.getFirstEntry() :
1.1323 + (loInclusive ? m.getCeilingEntry(lo) :
1.1324 + m.getHigherEntry(lo)));
1.1325 + return (e == null || tooHigh(e.key)) ? null : e;
1.1326 + }
1.1327 +
1.1328 + final TreeMap.Entry<K,V> absHighest() {
1.1329 + TreeMap.Entry<K,V> e =
1.1330 + (toEnd ? m.getLastEntry() :
1.1331 + (hiInclusive ? m.getFloorEntry(hi) :
1.1332 + m.getLowerEntry(hi)));
1.1333 + return (e == null || tooLow(e.key)) ? null : e;
1.1334 + }
1.1335 +
1.1336 + final TreeMap.Entry<K,V> absCeiling(K key) {
1.1337 + if (tooLow(key))
1.1338 + return absLowest();
1.1339 + TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1.1340 + return (e == null || tooHigh(e.key)) ? null : e;
1.1341 + }
1.1342 +
1.1343 + final TreeMap.Entry<K,V> absHigher(K key) {
1.1344 + if (tooLow(key))
1.1345 + return absLowest();
1.1346 + TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1.1347 + return (e == null || tooHigh(e.key)) ? null : e;
1.1348 + }
1.1349 +
1.1350 + final TreeMap.Entry<K,V> absFloor(K key) {
1.1351 + if (tooHigh(key))
1.1352 + return absHighest();
1.1353 + TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1.1354 + return (e == null || tooLow(e.key)) ? null : e;
1.1355 + }
1.1356 +
1.1357 + final TreeMap.Entry<K,V> absLower(K key) {
1.1358 + if (tooHigh(key))
1.1359 + return absHighest();
1.1360 + TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1.1361 + return (e == null || tooLow(e.key)) ? null : e;
1.1362 + }
1.1363 +
1.1364 + /** Returns the absolute high fence for ascending traversal */
1.1365 + final TreeMap.Entry<K,V> absHighFence() {
1.1366 + return (toEnd ? null : (hiInclusive ?
1.1367 + m.getHigherEntry(hi) :
1.1368 + m.getCeilingEntry(hi)));
1.1369 + }
1.1370 +
1.1371 + /** Return the absolute low fence for descending traversal */
1.1372 + final TreeMap.Entry<K,V> absLowFence() {
1.1373 + return (fromStart ? null : (loInclusive ?
1.1374 + m.getLowerEntry(lo) :
1.1375 + m.getFloorEntry(lo)));
1.1376 + }
1.1377 +
1.1378 + // Abstract methods defined in ascending vs descending classes
1.1379 + // These relay to the appropriate absolute versions
1.1380 +
1.1381 + abstract TreeMap.Entry<K,V> subLowest();
1.1382 + abstract TreeMap.Entry<K,V> subHighest();
1.1383 + abstract TreeMap.Entry<K,V> subCeiling(K key);
1.1384 + abstract TreeMap.Entry<K,V> subHigher(K key);
1.1385 + abstract TreeMap.Entry<K,V> subFloor(K key);
1.1386 + abstract TreeMap.Entry<K,V> subLower(K key);
1.1387 +
1.1388 + /** Returns ascending iterator from the perspective of this submap */
1.1389 + abstract Iterator<K> keyIterator();
1.1390 +
1.1391 + /** Returns descending iterator from the perspective of this submap */
1.1392 + abstract Iterator<K> descendingKeyIterator();
1.1393 +
1.1394 + // public methods
1.1395 +
1.1396 + public boolean isEmpty() {
1.1397 + return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1.1398 + }
1.1399 +
1.1400 + public int size() {
1.1401 + return (fromStart && toEnd) ? m.size() : entrySet().size();
1.1402 + }
1.1403 +
1.1404 + public final boolean containsKey(Object key) {
1.1405 + return inRange(key) && m.containsKey(key);
1.1406 + }
1.1407 +
1.1408 + public final V put(K key, V value) {
1.1409 + if (!inRange(key))
1.1410 + throw new IllegalArgumentException("key out of range");
1.1411 + return m.put(key, value);
1.1412 + }
1.1413 +
1.1414 + public final V get(Object key) {
1.1415 + return !inRange(key) ? null : m.get(key);
1.1416 + }
1.1417 +
1.1418 + public final V remove(Object key) {
1.1419 + return !inRange(key) ? null : m.remove(key);
1.1420 + }
1.1421 +
1.1422 + public final Map.Entry<K,V> ceilingEntry(K key) {
1.1423 + return exportEntry(subCeiling(key));
1.1424 + }
1.1425 +
1.1426 + public final K ceilingKey(K key) {
1.1427 + return keyOrNull(subCeiling(key));
1.1428 + }
1.1429 +
1.1430 + public final Map.Entry<K,V> higherEntry(K key) {
1.1431 + return exportEntry(subHigher(key));
1.1432 + }
1.1433 +
1.1434 + public final K higherKey(K key) {
1.1435 + return keyOrNull(subHigher(key));
1.1436 + }
1.1437 +
1.1438 + public final Map.Entry<K,V> floorEntry(K key) {
1.1439 + return exportEntry(subFloor(key));
1.1440 + }
1.1441 +
1.1442 + public final K floorKey(K key) {
1.1443 + return keyOrNull(subFloor(key));
1.1444 + }
1.1445 +
1.1446 + public final Map.Entry<K,V> lowerEntry(K key) {
1.1447 + return exportEntry(subLower(key));
1.1448 + }
1.1449 +
1.1450 + public final K lowerKey(K key) {
1.1451 + return keyOrNull(subLower(key));
1.1452 + }
1.1453 +
1.1454 + public final K firstKey() {
1.1455 + return key(subLowest());
1.1456 + }
1.1457 +
1.1458 + public final K lastKey() {
1.1459 + return key(subHighest());
1.1460 + }
1.1461 +
1.1462 + public final Map.Entry<K,V> firstEntry() {
1.1463 + return exportEntry(subLowest());
1.1464 + }
1.1465 +
1.1466 + public final Map.Entry<K,V> lastEntry() {
1.1467 + return exportEntry(subHighest());
1.1468 + }
1.1469 +
1.1470 + public final Map.Entry<K,V> pollFirstEntry() {
1.1471 + TreeMap.Entry<K,V> e = subLowest();
1.1472 + Map.Entry<K,V> result = exportEntry(e);
1.1473 + if (e != null)
1.1474 + m.deleteEntry(e);
1.1475 + return result;
1.1476 + }
1.1477 +
1.1478 + public final Map.Entry<K,V> pollLastEntry() {
1.1479 + TreeMap.Entry<K,V> e = subHighest();
1.1480 + Map.Entry<K,V> result = exportEntry(e);
1.1481 + if (e != null)
1.1482 + m.deleteEntry(e);
1.1483 + return result;
1.1484 + }
1.1485 +
1.1486 + // Views
1.1487 + transient NavigableMap<K,V> descendingMapView = null;
1.1488 + transient EntrySetView entrySetView = null;
1.1489 + transient KeySet<K> navigableKeySetView = null;
1.1490 +
1.1491 + public final NavigableSet<K> navigableKeySet() {
1.1492 + KeySet<K> nksv = navigableKeySetView;
1.1493 + return (nksv != null) ? nksv :
1.1494 + (navigableKeySetView = new TreeMap.KeySet(this));
1.1495 + }
1.1496 +
1.1497 + public final Set<K> keySet() {
1.1498 + return navigableKeySet();
1.1499 + }
1.1500 +
1.1501 + public NavigableSet<K> descendingKeySet() {
1.1502 + return descendingMap().navigableKeySet();
1.1503 + }
1.1504 +
1.1505 + public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1.1506 + return subMap(fromKey, true, toKey, false);
1.1507 + }
1.1508 +
1.1509 + public final SortedMap<K,V> headMap(K toKey) {
1.1510 + return headMap(toKey, false);
1.1511 + }
1.1512 +
1.1513 + public final SortedMap<K,V> tailMap(K fromKey) {
1.1514 + return tailMap(fromKey, true);
1.1515 + }
1.1516 +
1.1517 + // View classes
1.1518 +
1.1519 + abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1.1520 + private transient int size = -1, sizeModCount;
1.1521 +
1.1522 + public int size() {
1.1523 + if (fromStart && toEnd)
1.1524 + return m.size();
1.1525 + if (size == -1 || sizeModCount != m.modCount) {
1.1526 + sizeModCount = m.modCount;
1.1527 + size = 0;
1.1528 + Iterator i = iterator();
1.1529 + while (i.hasNext()) {
1.1530 + size++;
1.1531 + i.next();
1.1532 + }
1.1533 + }
1.1534 + return size;
1.1535 + }
1.1536 +
1.1537 + public boolean isEmpty() {
1.1538 + TreeMap.Entry<K,V> n = absLowest();
1.1539 + return n == null || tooHigh(n.key);
1.1540 + }
1.1541 +
1.1542 + public boolean contains(Object o) {
1.1543 + if (!(o instanceof Map.Entry))
1.1544 + return false;
1.1545 + Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1.1546 + K key = entry.getKey();
1.1547 + if (!inRange(key))
1.1548 + return false;
1.1549 + TreeMap.Entry node = m.getEntry(key);
1.1550 + return node != null &&
1.1551 + valEquals(node.getValue(), entry.getValue());
1.1552 + }
1.1553 +
1.1554 + public boolean remove(Object o) {
1.1555 + if (!(o instanceof Map.Entry))
1.1556 + return false;
1.1557 + Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1.1558 + K key = entry.getKey();
1.1559 + if (!inRange(key))
1.1560 + return false;
1.1561 + TreeMap.Entry<K,V> node = m.getEntry(key);
1.1562 + if (node!=null && valEquals(node.getValue(),
1.1563 + entry.getValue())) {
1.1564 + m.deleteEntry(node);
1.1565 + return true;
1.1566 + }
1.1567 + return false;
1.1568 + }
1.1569 + }
1.1570 +
1.1571 + /**
1.1572 + * Iterators for SubMaps
1.1573 + */
1.1574 + abstract class SubMapIterator<T> implements Iterator<T> {
1.1575 + TreeMap.Entry<K,V> lastReturned;
1.1576 + TreeMap.Entry<K,V> next;
1.1577 + final Object fenceKey;
1.1578 + int expectedModCount;
1.1579 +
1.1580 + SubMapIterator(TreeMap.Entry<K,V> first,
1.1581 + TreeMap.Entry<K,V> fence) {
1.1582 + expectedModCount = m.modCount;
1.1583 + lastReturned = null;
1.1584 + next = first;
1.1585 + fenceKey = fence == null ? UNBOUNDED : fence.key;
1.1586 + }
1.1587 +
1.1588 + public final boolean hasNext() {
1.1589 + return next != null && next.key != fenceKey;
1.1590 + }
1.1591 +
1.1592 + final TreeMap.Entry<K,V> nextEntry() {
1.1593 + TreeMap.Entry<K,V> e = next;
1.1594 + if (e == null || e.key == fenceKey)
1.1595 + throw new NoSuchElementException();
1.1596 + if (m.modCount != expectedModCount)
1.1597 + throw new ConcurrentModificationException();
1.1598 + next = successor(e);
1.1599 + lastReturned = e;
1.1600 + return e;
1.1601 + }
1.1602 +
1.1603 + final TreeMap.Entry<K,V> prevEntry() {
1.1604 + TreeMap.Entry<K,V> e = next;
1.1605 + if (e == null || e.key == fenceKey)
1.1606 + throw new NoSuchElementException();
1.1607 + if (m.modCount != expectedModCount)
1.1608 + throw new ConcurrentModificationException();
1.1609 + next = predecessor(e);
1.1610 + lastReturned = e;
1.1611 + return e;
1.1612 + }
1.1613 +
1.1614 + final void removeAscending() {
1.1615 + if (lastReturned == null)
1.1616 + throw new IllegalStateException();
1.1617 + if (m.modCount != expectedModCount)
1.1618 + throw new ConcurrentModificationException();
1.1619 + // deleted entries are replaced by their successors
1.1620 + if (lastReturned.left != null && lastReturned.right != null)
1.1621 + next = lastReturned;
1.1622 + m.deleteEntry(lastReturned);
1.1623 + lastReturned = null;
1.1624 + expectedModCount = m.modCount;
1.1625 + }
1.1626 +
1.1627 + final void removeDescending() {
1.1628 + if (lastReturned == null)
1.1629 + throw new IllegalStateException();
1.1630 + if (m.modCount != expectedModCount)
1.1631 + throw new ConcurrentModificationException();
1.1632 + m.deleteEntry(lastReturned);
1.1633 + lastReturned = null;
1.1634 + expectedModCount = m.modCount;
1.1635 + }
1.1636 +
1.1637 + }
1.1638 +
1.1639 + final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1.1640 + SubMapEntryIterator(TreeMap.Entry<K,V> first,
1.1641 + TreeMap.Entry<K,V> fence) {
1.1642 + super(first, fence);
1.1643 + }
1.1644 + public Map.Entry<K,V> next() {
1.1645 + return nextEntry();
1.1646 + }
1.1647 + public void remove() {
1.1648 + removeAscending();
1.1649 + }
1.1650 + }
1.1651 +
1.1652 + final class SubMapKeyIterator extends SubMapIterator<K> {
1.1653 + SubMapKeyIterator(TreeMap.Entry<K,V> first,
1.1654 + TreeMap.Entry<K,V> fence) {
1.1655 + super(first, fence);
1.1656 + }
1.1657 + public K next() {
1.1658 + return nextEntry().key;
1.1659 + }
1.1660 + public void remove() {
1.1661 + removeAscending();
1.1662 + }
1.1663 + }
1.1664 +
1.1665 + final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1.1666 + DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1.1667 + TreeMap.Entry<K,V> fence) {
1.1668 + super(last, fence);
1.1669 + }
1.1670 +
1.1671 + public Map.Entry<K,V> next() {
1.1672 + return prevEntry();
1.1673 + }
1.1674 + public void remove() {
1.1675 + removeDescending();
1.1676 + }
1.1677 + }
1.1678 +
1.1679 + final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1.1680 + DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1.1681 + TreeMap.Entry<K,V> fence) {
1.1682 + super(last, fence);
1.1683 + }
1.1684 + public K next() {
1.1685 + return prevEntry().key;
1.1686 + }
1.1687 + public void remove() {
1.1688 + removeDescending();
1.1689 + }
1.1690 + }
1.1691 + }
1.1692 +
1.1693 + /**
1.1694 + * @serial include
1.1695 + */
1.1696 + static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1.1697 + private static final long serialVersionUID = 912986545866124060L;
1.1698 +
1.1699 + AscendingSubMap(TreeMap<K,V> m,
1.1700 + boolean fromStart, K lo, boolean loInclusive,
1.1701 + boolean toEnd, K hi, boolean hiInclusive) {
1.1702 + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1.1703 + }
1.1704 +
1.1705 + public Comparator<? super K> comparator() {
1.1706 + return m.comparator();
1.1707 + }
1.1708 +
1.1709 + public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1.1710 + K toKey, boolean toInclusive) {
1.1711 + if (!inRange(fromKey, fromInclusive))
1.1712 + throw new IllegalArgumentException("fromKey out of range");
1.1713 + if (!inRange(toKey, toInclusive))
1.1714 + throw new IllegalArgumentException("toKey out of range");
1.1715 + return new AscendingSubMap(m,
1.1716 + false, fromKey, fromInclusive,
1.1717 + false, toKey, toInclusive);
1.1718 + }
1.1719 +
1.1720 + public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1.1721 + if (!inRange(toKey, inclusive))
1.1722 + throw new IllegalArgumentException("toKey out of range");
1.1723 + return new AscendingSubMap(m,
1.1724 + fromStart, lo, loInclusive,
1.1725 + false, toKey, inclusive);
1.1726 + }
1.1727 +
1.1728 + public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1.1729 + if (!inRange(fromKey, inclusive))
1.1730 + throw new IllegalArgumentException("fromKey out of range");
1.1731 + return new AscendingSubMap(m,
1.1732 + false, fromKey, inclusive,
1.1733 + toEnd, hi, hiInclusive);
1.1734 + }
1.1735 +
1.1736 + public NavigableMap<K,V> descendingMap() {
1.1737 + NavigableMap<K,V> mv = descendingMapView;
1.1738 + return (mv != null) ? mv :
1.1739 + (descendingMapView =
1.1740 + new DescendingSubMap(m,
1.1741 + fromStart, lo, loInclusive,
1.1742 + toEnd, hi, hiInclusive));
1.1743 + }
1.1744 +
1.1745 + Iterator<K> keyIterator() {
1.1746 + return new SubMapKeyIterator(absLowest(), absHighFence());
1.1747 + }
1.1748 +
1.1749 + Iterator<K> descendingKeyIterator() {
1.1750 + return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1.1751 + }
1.1752 +
1.1753 + final class AscendingEntrySetView extends EntrySetView {
1.1754 + public Iterator<Map.Entry<K,V>> iterator() {
1.1755 + return new SubMapEntryIterator(absLowest(), absHighFence());
1.1756 + }
1.1757 + }
1.1758 +
1.1759 + public Set<Map.Entry<K,V>> entrySet() {
1.1760 + EntrySetView es = entrySetView;
1.1761 + return (es != null) ? es : new AscendingEntrySetView();
1.1762 + }
1.1763 +
1.1764 + TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1.1765 + TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1.1766 + TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1.1767 + TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1.1768 + TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1.1769 + TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1.1770 + }
1.1771 +
1.1772 + /**
1.1773 + * @serial include
1.1774 + */
1.1775 + static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1.1776 + private static final long serialVersionUID = 912986545866120460L;
1.1777 + DescendingSubMap(TreeMap<K,V> m,
1.1778 + boolean fromStart, K lo, boolean loInclusive,
1.1779 + boolean toEnd, K hi, boolean hiInclusive) {
1.1780 + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1.1781 + }
1.1782 +
1.1783 + private final Comparator<? super K> reverseComparator =
1.1784 + Collections.reverseOrder(m.comparator);
1.1785 +
1.1786 + public Comparator<? super K> comparator() {
1.1787 + return reverseComparator;
1.1788 + }
1.1789 +
1.1790 + public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1.1791 + K toKey, boolean toInclusive) {
1.1792 + if (!inRange(fromKey, fromInclusive))
1.1793 + throw new IllegalArgumentException("fromKey out of range");
1.1794 + if (!inRange(toKey, toInclusive))
1.1795 + throw new IllegalArgumentException("toKey out of range");
1.1796 + return new DescendingSubMap(m,
1.1797 + false, toKey, toInclusive,
1.1798 + false, fromKey, fromInclusive);
1.1799 + }
1.1800 +
1.1801 + public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1.1802 + if (!inRange(toKey, inclusive))
1.1803 + throw new IllegalArgumentException("toKey out of range");
1.1804 + return new DescendingSubMap(m,
1.1805 + false, toKey, inclusive,
1.1806 + toEnd, hi, hiInclusive);
1.1807 + }
1.1808 +
1.1809 + public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1.1810 + if (!inRange(fromKey, inclusive))
1.1811 + throw new IllegalArgumentException("fromKey out of range");
1.1812 + return new DescendingSubMap(m,
1.1813 + fromStart, lo, loInclusive,
1.1814 + false, fromKey, inclusive);
1.1815 + }
1.1816 +
1.1817 + public NavigableMap<K,V> descendingMap() {
1.1818 + NavigableMap<K,V> mv = descendingMapView;
1.1819 + return (mv != null) ? mv :
1.1820 + (descendingMapView =
1.1821 + new AscendingSubMap(m,
1.1822 + fromStart, lo, loInclusive,
1.1823 + toEnd, hi, hiInclusive));
1.1824 + }
1.1825 +
1.1826 + Iterator<K> keyIterator() {
1.1827 + return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1.1828 + }
1.1829 +
1.1830 + Iterator<K> descendingKeyIterator() {
1.1831 + return new SubMapKeyIterator(absLowest(), absHighFence());
1.1832 + }
1.1833 +
1.1834 + final class DescendingEntrySetView extends EntrySetView {
1.1835 + public Iterator<Map.Entry<K,V>> iterator() {
1.1836 + return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1.1837 + }
1.1838 + }
1.1839 +
1.1840 + public Set<Map.Entry<K,V>> entrySet() {
1.1841 + EntrySetView es = entrySetView;
1.1842 + return (es != null) ? es : new DescendingEntrySetView();
1.1843 + }
1.1844 +
1.1845 + TreeMap.Entry<K,V> subLowest() { return absHighest(); }
1.1846 + TreeMap.Entry<K,V> subHighest() { return absLowest(); }
1.1847 + TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1.1848 + TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
1.1849 + TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
1.1850 + TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
1.1851 + }
1.1852 +
1.1853 + /**
1.1854 + * This class exists solely for the sake of serialization
1.1855 + * compatibility with previous releases of TreeMap that did not
1.1856 + * support NavigableMap. It translates an old-version SubMap into
1.1857 + * a new-version AscendingSubMap. This class is never otherwise
1.1858 + * used.
1.1859 + *
1.1860 + * @serial include
1.1861 + */
1.1862 + private class SubMap extends AbstractMap<K,V>
1.1863 + implements SortedMap<K,V>, java.io.Serializable {
1.1864 + private static final long serialVersionUID = -6520786458950516097L;
1.1865 + private boolean fromStart = false, toEnd = false;
1.1866 + private K fromKey, toKey;
1.1867 + private Object readResolve() {
1.1868 + return new AscendingSubMap(TreeMap.this,
1.1869 + fromStart, fromKey, true,
1.1870 + toEnd, toKey, false);
1.1871 + }
1.1872 + public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1.1873 + public K lastKey() { throw new InternalError(); }
1.1874 + public K firstKey() { throw new InternalError(); }
1.1875 + public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1.1876 + public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1.1877 + public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1.1878 + public Comparator<? super K> comparator() { throw new InternalError(); }
1.1879 + }
1.1880 +
1.1881 +
1.1882 + // Red-black mechanics
1.1883 +
1.1884 + private static final boolean RED = false;
1.1885 + private static final boolean BLACK = true;
1.1886 +
1.1887 + /**
1.1888 + * Node in the Tree. Doubles as a means to pass key-value pairs back to
1.1889 + * user (see Map.Entry).
1.1890 + */
1.1891 +
1.1892 + static final class Entry<K,V> implements Map.Entry<K,V> {
1.1893 + K key;
1.1894 + V value;
1.1895 + Entry<K,V> left = null;
1.1896 + Entry<K,V> right = null;
1.1897 + Entry<K,V> parent;
1.1898 + boolean color = BLACK;
1.1899 +
1.1900 + /**
1.1901 + * Make a new cell with given key, value, and parent, and with
1.1902 + * {@code null} child links, and BLACK color.
1.1903 + */
1.1904 + Entry(K key, V value, Entry<K,V> parent) {
1.1905 + this.key = key;
1.1906 + this.value = value;
1.1907 + this.parent = parent;
1.1908 + }
1.1909 +
1.1910 + /**
1.1911 + * Returns the key.
1.1912 + *
1.1913 + * @return the key
1.1914 + */
1.1915 + public K getKey() {
1.1916 + return key;
1.1917 + }
1.1918 +
1.1919 + /**
1.1920 + * Returns the value associated with the key.
1.1921 + *
1.1922 + * @return the value associated with the key
1.1923 + */
1.1924 + public V getValue() {
1.1925 + return value;
1.1926 + }
1.1927 +
1.1928 + /**
1.1929 + * Replaces the value currently associated with the key with the given
1.1930 + * value.
1.1931 + *
1.1932 + * @return the value associated with the key before this method was
1.1933 + * called
1.1934 + */
1.1935 + public V setValue(V value) {
1.1936 + V oldValue = this.value;
1.1937 + this.value = value;
1.1938 + return oldValue;
1.1939 + }
1.1940 +
1.1941 + public boolean equals(Object o) {
1.1942 + if (!(o instanceof Map.Entry))
1.1943 + return false;
1.1944 + Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1.1945 +
1.1946 + return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1.1947 + }
1.1948 +
1.1949 + public int hashCode() {
1.1950 + int keyHash = (key==null ? 0 : key.hashCode());
1.1951 + int valueHash = (value==null ? 0 : value.hashCode());
1.1952 + return keyHash ^ valueHash;
1.1953 + }
1.1954 +
1.1955 + public String toString() {
1.1956 + return key + "=" + value;
1.1957 + }
1.1958 + }
1.1959 +
1.1960 + /**
1.1961 + * Returns the first Entry in the TreeMap (according to the TreeMap's
1.1962 + * key-sort function). Returns null if the TreeMap is empty.
1.1963 + */
1.1964 + final Entry<K,V> getFirstEntry() {
1.1965 + Entry<K,V> p = root;
1.1966 + if (p != null)
1.1967 + while (p.left != null)
1.1968 + p = p.left;
1.1969 + return p;
1.1970 + }
1.1971 +
1.1972 + /**
1.1973 + * Returns the last Entry in the TreeMap (according to the TreeMap's
1.1974 + * key-sort function). Returns null if the TreeMap is empty.
1.1975 + */
1.1976 + final Entry<K,V> getLastEntry() {
1.1977 + Entry<K,V> p = root;
1.1978 + if (p != null)
1.1979 + while (p.right != null)
1.1980 + p = p.right;
1.1981 + return p;
1.1982 + }
1.1983 +
1.1984 + /**
1.1985 + * Returns the successor of the specified Entry, or null if no such.
1.1986 + */
1.1987 + static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1.1988 + if (t == null)
1.1989 + return null;
1.1990 + else if (t.right != null) {
1.1991 + Entry<K,V> p = t.right;
1.1992 + while (p.left != null)
1.1993 + p = p.left;
1.1994 + return p;
1.1995 + } else {
1.1996 + Entry<K,V> p = t.parent;
1.1997 + Entry<K,V> ch = t;
1.1998 + while (p != null && ch == p.right) {
1.1999 + ch = p;
1.2000 + p = p.parent;
1.2001 + }
1.2002 + return p;
1.2003 + }
1.2004 + }
1.2005 +
1.2006 + /**
1.2007 + * Returns the predecessor of the specified Entry, or null if no such.
1.2008 + */
1.2009 + static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1.2010 + if (t == null)
1.2011 + return null;
1.2012 + else if (t.left != null) {
1.2013 + Entry<K,V> p = t.left;
1.2014 + while (p.right != null)
1.2015 + p = p.right;
1.2016 + return p;
1.2017 + } else {
1.2018 + Entry<K,V> p = t.parent;
1.2019 + Entry<K,V> ch = t;
1.2020 + while (p != null && ch == p.left) {
1.2021 + ch = p;
1.2022 + p = p.parent;
1.2023 + }
1.2024 + return p;
1.2025 + }
1.2026 + }
1.2027 +
1.2028 + /**
1.2029 + * Balancing operations.
1.2030 + *
1.2031 + * Implementations of rebalancings during insertion and deletion are
1.2032 + * slightly different than the CLR version. Rather than using dummy
1.2033 + * nilnodes, we use a set of accessors that deal properly with null. They
1.2034 + * are used to avoid messiness surrounding nullness checks in the main
1.2035 + * algorithms.
1.2036 + */
1.2037 +
1.2038 + private static <K,V> boolean colorOf(Entry<K,V> p) {
1.2039 + return (p == null ? BLACK : p.color);
1.2040 + }
1.2041 +
1.2042 + private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
1.2043 + return (p == null ? null: p.parent);
1.2044 + }
1.2045 +
1.2046 + private static <K,V> void setColor(Entry<K,V> p, boolean c) {
1.2047 + if (p != null)
1.2048 + p.color = c;
1.2049 + }
1.2050 +
1.2051 + private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
1.2052 + return (p == null) ? null: p.left;
1.2053 + }
1.2054 +
1.2055 + private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
1.2056 + return (p == null) ? null: p.right;
1.2057 + }
1.2058 +
1.2059 + /** From CLR */
1.2060 + private void rotateLeft(Entry<K,V> p) {
1.2061 + if (p != null) {
1.2062 + Entry<K,V> r = p.right;
1.2063 + p.right = r.left;
1.2064 + if (r.left != null)
1.2065 + r.left.parent = p;
1.2066 + r.parent = p.parent;
1.2067 + if (p.parent == null)
1.2068 + root = r;
1.2069 + else if (p.parent.left == p)
1.2070 + p.parent.left = r;
1.2071 + else
1.2072 + p.parent.right = r;
1.2073 + r.left = p;
1.2074 + p.parent = r;
1.2075 + }
1.2076 + }
1.2077 +
1.2078 + /** From CLR */
1.2079 + private void rotateRight(Entry<K,V> p) {
1.2080 + if (p != null) {
1.2081 + Entry<K,V> l = p.left;
1.2082 + p.left = l.right;
1.2083 + if (l.right != null) l.right.parent = p;
1.2084 + l.parent = p.parent;
1.2085 + if (p.parent == null)
1.2086 + root = l;
1.2087 + else if (p.parent.right == p)
1.2088 + p.parent.right = l;
1.2089 + else p.parent.left = l;
1.2090 + l.right = p;
1.2091 + p.parent = l;
1.2092 + }
1.2093 + }
1.2094 +
1.2095 + /** From CLR */
1.2096 + private void fixAfterInsertion(Entry<K,V> x) {
1.2097 + x.color = RED;
1.2098 +
1.2099 + while (x != null && x != root && x.parent.color == RED) {
1.2100 + if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
1.2101 + Entry<K,V> y = rightOf(parentOf(parentOf(x)));
1.2102 + if (colorOf(y) == RED) {
1.2103 + setColor(parentOf(x), BLACK);
1.2104 + setColor(y, BLACK);
1.2105 + setColor(parentOf(parentOf(x)), RED);
1.2106 + x = parentOf(parentOf(x));
1.2107 + } else {
1.2108 + if (x == rightOf(parentOf(x))) {
1.2109 + x = parentOf(x);
1.2110 + rotateLeft(x);
1.2111 + }
1.2112 + setColor(parentOf(x), BLACK);
1.2113 + setColor(parentOf(parentOf(x)), RED);
1.2114 + rotateRight(parentOf(parentOf(x)));
1.2115 + }
1.2116 + } else {
1.2117 + Entry<K,V> y = leftOf(parentOf(parentOf(x)));
1.2118 + if (colorOf(y) == RED) {
1.2119 + setColor(parentOf(x), BLACK);
1.2120 + setColor(y, BLACK);
1.2121 + setColor(parentOf(parentOf(x)), RED);
1.2122 + x = parentOf(parentOf(x));
1.2123 + } else {
1.2124 + if (x == leftOf(parentOf(x))) {
1.2125 + x = parentOf(x);
1.2126 + rotateRight(x);
1.2127 + }
1.2128 + setColor(parentOf(x), BLACK);
1.2129 + setColor(parentOf(parentOf(x)), RED);
1.2130 + rotateLeft(parentOf(parentOf(x)));
1.2131 + }
1.2132 + }
1.2133 + }
1.2134 + root.color = BLACK;
1.2135 + }
1.2136 +
1.2137 + /**
1.2138 + * Delete node p, and then rebalance the tree.
1.2139 + */
1.2140 + private void deleteEntry(Entry<K,V> p) {
1.2141 + modCount++;
1.2142 + size--;
1.2143 +
1.2144 + // If strictly internal, copy successor's element to p and then make p
1.2145 + // point to successor.
1.2146 + if (p.left != null && p.right != null) {
1.2147 + Entry<K,V> s = successor(p);
1.2148 + p.key = s.key;
1.2149 + p.value = s.value;
1.2150 + p = s;
1.2151 + } // p has 2 children
1.2152 +
1.2153 + // Start fixup at replacement node, if it exists.
1.2154 + Entry<K,V> replacement = (p.left != null ? p.left : p.right);
1.2155 +
1.2156 + if (replacement != null) {
1.2157 + // Link replacement to parent
1.2158 + replacement.parent = p.parent;
1.2159 + if (p.parent == null)
1.2160 + root = replacement;
1.2161 + else if (p == p.parent.left)
1.2162 + p.parent.left = replacement;
1.2163 + else
1.2164 + p.parent.right = replacement;
1.2165 +
1.2166 + // Null out links so they are OK to use by fixAfterDeletion.
1.2167 + p.left = p.right = p.parent = null;
1.2168 +
1.2169 + // Fix replacement
1.2170 + if (p.color == BLACK)
1.2171 + fixAfterDeletion(replacement);
1.2172 + } else if (p.parent == null) { // return if we are the only node.
1.2173 + root = null;
1.2174 + } else { // No children. Use self as phantom replacement and unlink.
1.2175 + if (p.color == BLACK)
1.2176 + fixAfterDeletion(p);
1.2177 +
1.2178 + if (p.parent != null) {
1.2179 + if (p == p.parent.left)
1.2180 + p.parent.left = null;
1.2181 + else if (p == p.parent.right)
1.2182 + p.parent.right = null;
1.2183 + p.parent = null;
1.2184 + }
1.2185 + }
1.2186 + }
1.2187 +
1.2188 + /** From CLR */
1.2189 + private void fixAfterDeletion(Entry<K,V> x) {
1.2190 + while (x != root && colorOf(x) == BLACK) {
1.2191 + if (x == leftOf(parentOf(x))) {
1.2192 + Entry<K,V> sib = rightOf(parentOf(x));
1.2193 +
1.2194 + if (colorOf(sib) == RED) {
1.2195 + setColor(sib, BLACK);
1.2196 + setColor(parentOf(x), RED);
1.2197 + rotateLeft(parentOf(x));
1.2198 + sib = rightOf(parentOf(x));
1.2199 + }
1.2200 +
1.2201 + if (colorOf(leftOf(sib)) == BLACK &&
1.2202 + colorOf(rightOf(sib)) == BLACK) {
1.2203 + setColor(sib, RED);
1.2204 + x = parentOf(x);
1.2205 + } else {
1.2206 + if (colorOf(rightOf(sib)) == BLACK) {
1.2207 + setColor(leftOf(sib), BLACK);
1.2208 + setColor(sib, RED);
1.2209 + rotateRight(sib);
1.2210 + sib = rightOf(parentOf(x));
1.2211 + }
1.2212 + setColor(sib, colorOf(parentOf(x)));
1.2213 + setColor(parentOf(x), BLACK);
1.2214 + setColor(rightOf(sib), BLACK);
1.2215 + rotateLeft(parentOf(x));
1.2216 + x = root;
1.2217 + }
1.2218 + } else { // symmetric
1.2219 + Entry<K,V> sib = leftOf(parentOf(x));
1.2220 +
1.2221 + if (colorOf(sib) == RED) {
1.2222 + setColor(sib, BLACK);
1.2223 + setColor(parentOf(x), RED);
1.2224 + rotateRight(parentOf(x));
1.2225 + sib = leftOf(parentOf(x));
1.2226 + }
1.2227 +
1.2228 + if (colorOf(rightOf(sib)) == BLACK &&
1.2229 + colorOf(leftOf(sib)) == BLACK) {
1.2230 + setColor(sib, RED);
1.2231 + x = parentOf(x);
1.2232 + } else {
1.2233 + if (colorOf(leftOf(sib)) == BLACK) {
1.2234 + setColor(rightOf(sib), BLACK);
1.2235 + setColor(sib, RED);
1.2236 + rotateLeft(sib);
1.2237 + sib = leftOf(parentOf(x));
1.2238 + }
1.2239 + setColor(sib, colorOf(parentOf(x)));
1.2240 + setColor(parentOf(x), BLACK);
1.2241 + setColor(leftOf(sib), BLACK);
1.2242 + rotateRight(parentOf(x));
1.2243 + x = root;
1.2244 + }
1.2245 + }
1.2246 + }
1.2247 +
1.2248 + setColor(x, BLACK);
1.2249 + }
1.2250 +
1.2251 + private static final long serialVersionUID = 919286545866124006L;
1.2252 +
1.2253 + /**
1.2254 + * Save the state of the {@code TreeMap} instance to a stream (i.e.,
1.2255 + * serialize it).
1.2256 + *
1.2257 + * @serialData The <em>size</em> of the TreeMap (the number of key-value
1.2258 + * mappings) is emitted (int), followed by the key (Object)
1.2259 + * and value (Object) for each key-value mapping represented
1.2260 + * by the TreeMap. The key-value mappings are emitted in
1.2261 + * key-order (as determined by the TreeMap's Comparator,
1.2262 + * or by the keys' natural ordering if the TreeMap has no
1.2263 + * Comparator).
1.2264 + */
1.2265 + private void writeObject(java.io.ObjectOutputStream s)
1.2266 + throws java.io.IOException {
1.2267 + // Write out the Comparator and any hidden stuff
1.2268 + s.defaultWriteObject();
1.2269 +
1.2270 + // Write out size (number of Mappings)
1.2271 + s.writeInt(size);
1.2272 +
1.2273 + // Write out keys and values (alternating)
1.2274 + for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
1.2275 + Map.Entry<K,V> e = i.next();
1.2276 + s.writeObject(e.getKey());
1.2277 + s.writeObject(e.getValue());
1.2278 + }
1.2279 + }
1.2280 +
1.2281 + /**
1.2282 + * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
1.2283 + * deserialize it).
1.2284 + */
1.2285 + private void readObject(final java.io.ObjectInputStream s)
1.2286 + throws java.io.IOException, ClassNotFoundException {
1.2287 + // Read in the Comparator and any hidden stuff
1.2288 + s.defaultReadObject();
1.2289 +
1.2290 + // Read in size
1.2291 + int size = s.readInt();
1.2292 +
1.2293 + buildFromSorted(size, null, s, null);
1.2294 + }
1.2295 +
1.2296 + /** Intended to be called only from TreeSet.readObject */
1.2297 + void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
1.2298 + throws java.io.IOException, ClassNotFoundException {
1.2299 + buildFromSorted(size, null, s, defaultVal);
1.2300 + }
1.2301 +
1.2302 + /** Intended to be called only from TreeSet.addAll */
1.2303 + void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
1.2304 + try {
1.2305 + buildFromSorted(set.size(), set.iterator(), null, defaultVal);
1.2306 + } catch (java.io.IOException cannotHappen) {
1.2307 + } catch (ClassNotFoundException cannotHappen) {
1.2308 + }
1.2309 + }
1.2310 +
1.2311 +
1.2312 + /**
1.2313 + * Linear time tree building algorithm from sorted data. Can accept keys
1.2314 + * and/or values from iterator or stream. This leads to too many
1.2315 + * parameters, but seems better than alternatives. The four formats
1.2316 + * that this method accepts are:
1.2317 + *
1.2318 + * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
1.2319 + * 2) An iterator of keys. (it != null, defaultVal != null).
1.2320 + * 3) A stream of alternating serialized keys and values.
1.2321 + * (it == null, defaultVal == null).
1.2322 + * 4) A stream of serialized keys. (it == null, defaultVal != null).
1.2323 + *
1.2324 + * It is assumed that the comparator of the TreeMap is already set prior
1.2325 + * to calling this method.
1.2326 + *
1.2327 + * @param size the number of keys (or key-value pairs) to be read from
1.2328 + * the iterator or stream
1.2329 + * @param it If non-null, new entries are created from entries
1.2330 + * or keys read from this iterator.
1.2331 + * @param str If non-null, new entries are created from keys and
1.2332 + * possibly values read from this stream in serialized form.
1.2333 + * Exactly one of it and str should be non-null.
1.2334 + * @param defaultVal if non-null, this default value is used for
1.2335 + * each value in the map. If null, each value is read from
1.2336 + * iterator or stream, as described above.
1.2337 + * @throws IOException propagated from stream reads. This cannot
1.2338 + * occur if str is null.
1.2339 + * @throws ClassNotFoundException propagated from readObject.
1.2340 + * This cannot occur if str is null.
1.2341 + */
1.2342 + private void buildFromSorted(int size, Iterator it,
1.2343 + java.io.ObjectInputStream str,
1.2344 + V defaultVal)
1.2345 + throws java.io.IOException, ClassNotFoundException {
1.2346 + this.size = size;
1.2347 + root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
1.2348 + it, str, defaultVal);
1.2349 + }
1.2350 +
1.2351 + /**
1.2352 + * Recursive "helper method" that does the real work of the
1.2353 + * previous method. Identically named parameters have
1.2354 + * identical definitions. Additional parameters are documented below.
1.2355 + * It is assumed that the comparator and size fields of the TreeMap are
1.2356 + * already set prior to calling this method. (It ignores both fields.)
1.2357 + *
1.2358 + * @param level the current level of tree. Initial call should be 0.
1.2359 + * @param lo the first element index of this subtree. Initial should be 0.
1.2360 + * @param hi the last element index of this subtree. Initial should be
1.2361 + * size-1.
1.2362 + * @param redLevel the level at which nodes should be red.
1.2363 + * Must be equal to computeRedLevel for tree of this size.
1.2364 + */
1.2365 + private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
1.2366 + int redLevel,
1.2367 + Iterator it,
1.2368 + java.io.ObjectInputStream str,
1.2369 + V defaultVal)
1.2370 + throws java.io.IOException, ClassNotFoundException {
1.2371 + /*
1.2372 + * Strategy: The root is the middlemost element. To get to it, we
1.2373 + * have to first recursively construct the entire left subtree,
1.2374 + * so as to grab all of its elements. We can then proceed with right
1.2375 + * subtree.
1.2376 + *
1.2377 + * The lo and hi arguments are the minimum and maximum
1.2378 + * indices to pull out of the iterator or stream for current subtree.
1.2379 + * They are not actually indexed, we just proceed sequentially,
1.2380 + * ensuring that items are extracted in corresponding order.
1.2381 + */
1.2382 +
1.2383 + if (hi < lo) return null;
1.2384 +
1.2385 + int mid = (lo + hi) >>> 1;
1.2386 +
1.2387 + Entry<K,V> left = null;
1.2388 + if (lo < mid)
1.2389 + left = buildFromSorted(level+1, lo, mid - 1, redLevel,
1.2390 + it, str, defaultVal);
1.2391 +
1.2392 + // extract key and/or value from iterator or stream
1.2393 + K key;
1.2394 + V value;
1.2395 + if (it != null) {
1.2396 + if (defaultVal==null) {
1.2397 + Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
1.2398 + key = entry.getKey();
1.2399 + value = entry.getValue();
1.2400 + } else {
1.2401 + key = (K)it.next();
1.2402 + value = defaultVal;
1.2403 + }
1.2404 + } else { // use stream
1.2405 + key = (K) str.readObject();
1.2406 + value = (defaultVal != null ? defaultVal : (V) str.readObject());
1.2407 + }
1.2408 +
1.2409 + Entry<K,V> middle = new Entry<>(key, value, null);
1.2410 +
1.2411 + // color nodes in non-full bottommost level red
1.2412 + if (level == redLevel)
1.2413 + middle.color = RED;
1.2414 +
1.2415 + if (left != null) {
1.2416 + middle.left = left;
1.2417 + left.parent = middle;
1.2418 + }
1.2419 +
1.2420 + if (mid < hi) {
1.2421 + Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
1.2422 + it, str, defaultVal);
1.2423 + middle.right = right;
1.2424 + right.parent = middle;
1.2425 + }
1.2426 +
1.2427 + return middle;
1.2428 + }
1.2429 +
1.2430 + /**
1.2431 + * Find the level down to which to assign all nodes BLACK. This is the
1.2432 + * last `full' level of the complete binary tree produced by
1.2433 + * buildTree. The remaining nodes are colored RED. (This makes a `nice'
1.2434 + * set of color assignments wrt future insertions.) This level number is
1.2435 + * computed by finding the number of splits needed to reach the zeroeth
1.2436 + * node. (The answer is ~lg(N), but in any case must be computed by same
1.2437 + * quick O(lg(N)) loop.)
1.2438 + */
1.2439 + private static int computeRedLevel(int sz) {
1.2440 + int level = 0;
1.2441 + for (int m = sz - 1; m >= 0; m = m / 2 - 1)
1.2442 + level++;
1.2443 + return level;
1.2444 + }
1.2445 +}