1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27 package java.util; 28 29 import java.io.Serializable; 30 import java.util.function.BiConsumer; 31 import java.util.function.BiFunction; 32 import java.util.function.Consumer; 33 34 /** 35 * A Red-Black tree based {@link NavigableMap} implementation. 36 * The map is sorted according to the {@linkplain Comparable natural 37 * ordering} of its keys, or by a {@link Comparator} provided at map 38 * creation time, depending on which constructor is used. 39 * 40 * <p>This implementation provides guaranteed log(n) time cost for the 41 * {@code containsKey}, {@code get}, {@code put} and {@code remove} 42 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and 43 * Rivest's <em>Introduction to Algorithms</em>. 44 * 45 * <p>Note that the ordering maintained by a tree map, like any sorted map, and 46 * whether or not an explicit comparator is provided, must be <em>consistent 47 * with {@code equals}</em> if this sorted map is to correctly implement the 48 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a 49 * precise definition of <em>consistent with equals</em>.) This is so because 50 * the {@code Map} interface is defined in terms of the {@code equals} 51 * operation, but a sorted map performs all key comparisons using its {@code 52 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by 53 * this method are, from the standpoint of the sorted map, equal. The behavior 54 * of a sorted map <em>is</em> well-defined even if its ordering is 55 * inconsistent with {@code equals}; it just fails to obey the general contract 56 * of the {@code Map} interface. 57 * 58 * <p><strong>Note that this implementation is not synchronized.</strong> 59 * If multiple threads access a map concurrently, and at least one of the 60 * threads modifies the map structurally, it <em>must</em> be synchronized 61 * externally. (A structural modification is any operation that adds or 62 * deletes one or more mappings; merely changing the value associated 63 * with an existing key is not a structural modification.) This is 64 * typically accomplished by synchronizing on some object that naturally 65 * encapsulates the map. 66 * If no such object exists, the map should be "wrapped" using the 67 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap} 68 * method. This is best done at creation time, to prevent accidental 69 * unsynchronized access to the map: <pre> 70 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre> 71 * 72 * <p>The iterators returned by the {@code iterator} method of the collections 73 * returned by all of this class's "collection view methods" are 74 * <em>fail-fast</em>: if the map is structurally modified at any time after 75 * the iterator is created, in any way except through the iterator's own 76 * {@code remove} method, the iterator will throw a {@link 77 * ConcurrentModificationException}. Thus, in the face of concurrent 78 * modification, the iterator fails quickly and cleanly, rather than risking 79 * arbitrary, non-deterministic behavior at an undetermined time in the future. 80 * 81 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 82 * as it is, generally speaking, impossible to make any hard guarantees in the 83 * presence of unsynchronized concurrent modification. Fail-fast iterators 84 * throw {@code ConcurrentModificationException} on a best-effort basis. 85 * Therefore, it would be wrong to write a program that depended on this 86 * exception for its correctness: <em>the fail-fast behavior of iterators 87 * should be used only to detect bugs.</em> 88 * 89 * <p>All {@code Map.Entry} pairs returned by methods in this class 90 * and its views represent snapshots of mappings at the time they were 91 * produced. They do <strong>not</strong> support the {@code Entry.setValue} 92 * method. (Note however that it is possible to change mappings in the 93 * associated map using {@code put}.) 94 * 95 * <p>This class is a member of the 96 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 97 * Java Collections Framework</a>. 98 * 99 * @param <K> the type of keys maintained by this map 100 * @param <V> the type of mapped values 101 * 102 * @author Josh Bloch and Doug Lea 103 * @see Map 104 * @see HashMap 105 * @see Hashtable 106 * @see Comparable 107 * @see Comparator 108 * @see Collection 109 * @since 1.2 110 */ 111 112 public class TreeMap<K,V> 113 extends AbstractMap<K,V> 114 implements NavigableMap<K,V>, Cloneable, java.io.Serializable 115 { 116 /** 117 * The comparator used to maintain order in this tree map, or 118 * null if it uses the natural ordering of its keys. 119 * 120 * @serial 121 */ 122 private final Comparator<? super K> comparator; 123 124 private transient TreeMapEntry<K,V> root = null; 125 126 /** 127 * The number of entries in the tree 128 */ 129 private transient int size = 0; 130 131 /** 132 * The number of structural modifications to the tree. 133 */ 134 private transient int modCount = 0; 135 136 /** 137 * Constructs a new, empty tree map, using the natural ordering of its 138 * keys. All keys inserted into the map must implement the {@link 139 * Comparable} interface. Furthermore, all such keys must be 140 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw 141 * a {@code ClassCastException} for any keys {@code k1} and 142 * {@code k2} in the map. If the user attempts to put a key into the 143 * map that violates this constraint (for example, the user attempts to 144 * put a string key into a map whose keys are integers), the 145 * {@code put(Object key, Object value)} call will throw a 146 * {@code ClassCastException}. 147 */ TreeMap()148 public TreeMap() { 149 comparator = null; 150 } 151 152 /** 153 * Constructs a new, empty tree map, ordered according to the given 154 * comparator. All keys inserted into the map must be <em>mutually 155 * comparable</em> by the given comparator: {@code comparator.compare(k1, 156 * k2)} must not throw a {@code ClassCastException} for any keys 157 * {@code k1} and {@code k2} in the map. If the user attempts to put 158 * a key into the map that violates this constraint, the {@code put(Object 159 * key, Object value)} call will throw a 160 * {@code ClassCastException}. 161 * 162 * @param comparator the comparator that will be used to order this map. 163 * If {@code null}, the {@linkplain Comparable natural 164 * ordering} of the keys will be used. 165 */ TreeMap(Comparator<? super K> comparator)166 public TreeMap(Comparator<? super K> comparator) { 167 this.comparator = comparator; 168 } 169 170 /** 171 * Constructs a new tree map containing the same mappings as the given 172 * map, ordered according to the <em>natural ordering</em> of its keys. 173 * All keys inserted into the new map must implement the {@link 174 * Comparable} interface. Furthermore, all such keys must be 175 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw 176 * a {@code ClassCastException} for any keys {@code k1} and 177 * {@code k2} in the map. This method runs in n*log(n) time. 178 * 179 * @param m the map whose mappings are to be placed in this map 180 * @throws ClassCastException if the keys in m are not {@link Comparable}, 181 * or are not mutually comparable 182 * @throws NullPointerException if the specified map is null 183 */ TreeMap(Map<? extends K, ? extends V> m)184 public TreeMap(Map<? extends K, ? extends V> m) { 185 comparator = null; 186 putAll(m); 187 } 188 189 /** 190 * Constructs a new tree map containing the same mappings and 191 * using the same ordering as the specified sorted map. This 192 * method runs in linear time. 193 * 194 * @param m the sorted map whose mappings are to be placed in this map, 195 * and whose comparator is to be used to sort this map 196 * @throws NullPointerException if the specified map is null 197 */ TreeMap(SortedMap<K, ? extends V> m)198 public TreeMap(SortedMap<K, ? extends V> m) { 199 comparator = m.comparator(); 200 try { 201 buildFromSorted(m.size(), m.entrySet().iterator(), null, null); 202 } catch (java.io.IOException cannotHappen) { 203 } catch (ClassNotFoundException cannotHappen) { 204 } 205 } 206 207 208 // Query Operations 209 210 /** 211 * Returns the number of key-value mappings in this map. 212 * 213 * @return the number of key-value mappings in this map 214 */ size()215 public int size() { 216 return size; 217 } 218 219 /** 220 * Returns {@code true} if this map contains a mapping for the specified 221 * key. 222 * 223 * @param key key whose presence in this map is to be tested 224 * @return {@code true} if this map contains a mapping for the 225 * specified key 226 * @throws ClassCastException if the specified key cannot be compared 227 * with the keys currently in the map 228 * @throws NullPointerException if the specified key is null 229 * and this map uses natural ordering, or its comparator 230 * does not permit null keys 231 */ containsKey(Object key)232 public boolean containsKey(Object key) { 233 return getEntry(key) != null; 234 } 235 236 /** 237 * Returns {@code true} if this map maps one or more keys to the 238 * specified value. More formally, returns {@code true} if and only if 239 * this map contains at least one mapping to a value {@code v} such 240 * that {@code (value==null ? v==null : value.equals(v))}. This 241 * operation will probably require time linear in the map size for 242 * most implementations. 243 * 244 * @param value value whose presence in this map is to be tested 245 * @return {@code true} if a mapping to {@code value} exists; 246 * {@code false} otherwise 247 * @since 1.2 248 */ containsValue(Object value)249 public boolean containsValue(Object value) { 250 for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e)) 251 if (valEquals(value, e.value)) 252 return true; 253 return false; 254 } 255 256 /** 257 * Returns the value to which the specified key is mapped, 258 * or {@code null} if this map contains no mapping for the key. 259 * 260 * <p>More formally, if this map contains a mapping from a key 261 * {@code k} to a value {@code v} such that {@code key} compares 262 * equal to {@code k} according to the map's ordering, then this 263 * method returns {@code v}; otherwise it returns {@code null}. 264 * (There can be at most one such mapping.) 265 * 266 * <p>A return value of {@code null} does not <em>necessarily</em> 267 * indicate that the map contains no mapping for the key; it's also 268 * possible that the map explicitly maps the key to {@code null}. 269 * The {@link #containsKey containsKey} operation may be used to 270 * distinguish these two cases. 271 * 272 * @throws ClassCastException if the specified key cannot be compared 273 * with the keys currently in the map 274 * @throws NullPointerException if the specified key is null 275 * and this map uses natural ordering, or its comparator 276 * does not permit null keys 277 */ get(Object key)278 public V get(Object key) { 279 TreeMapEntry<K,V> p = getEntry(key); 280 return (p==null ? null : p.value); 281 } 282 comparator()283 public Comparator<? super K> comparator() { 284 return comparator; 285 } 286 287 /** 288 * @throws NoSuchElementException {@inheritDoc} 289 */ firstKey()290 public K firstKey() { 291 return key(getFirstEntry()); 292 } 293 294 /** 295 * @throws NoSuchElementException {@inheritDoc} 296 */ lastKey()297 public K lastKey() { 298 return key(getLastEntry()); 299 } 300 301 /** 302 * Copies all of the mappings from the specified map to this map. 303 * These mappings replace any mappings that this map had for any 304 * of the keys currently in the specified map. 305 * 306 * @param map mappings to be stored in this map 307 * @throws ClassCastException if the class of a key or value in 308 * the specified map prevents it from being stored in this map 309 * @throws NullPointerException if the specified map is null or 310 * the specified map contains a null key and this map does not 311 * permit null keys 312 */ putAll(Map<? extends K, ? extends V> map)313 public void putAll(Map<? extends K, ? extends V> map) { 314 int mapSize = map.size(); 315 if (size==0 && mapSize!=0 && map instanceof SortedMap) { 316 Comparator<?> c = ((SortedMap<?,?>)map).comparator(); 317 if (c == comparator || (c != null && c.equals(comparator))) { 318 ++modCount; 319 try { 320 buildFromSorted(mapSize, map.entrySet().iterator(), 321 null, null); 322 } catch (java.io.IOException cannotHappen) { 323 } catch (ClassNotFoundException cannotHappen) { 324 } 325 return; 326 } 327 } 328 super.putAll(map); 329 } 330 331 /** 332 * Returns this map's entry for the given key, or {@code null} if the map 333 * does not contain an entry for the key. 334 * 335 * @return this map's entry for the given key, or {@code null} if the map 336 * does not contain an entry for the key 337 * @throws ClassCastException if the specified key cannot be compared 338 * with the keys currently in the map 339 * @throws NullPointerException if the specified key is null 340 * and this map uses natural ordering, or its comparator 341 * does not permit null keys 342 */ getEntry(Object key)343 final TreeMapEntry<K,V> getEntry(Object key) { 344 // Offload comparator-based version for sake of performance 345 if (comparator != null) 346 return getEntryUsingComparator(key); 347 if (key == null) 348 throw new NullPointerException(); 349 @SuppressWarnings("unchecked") 350 Comparable<? super K> k = (Comparable<? super K>) key; 351 TreeMapEntry<K,V> p = root; 352 while (p != null) { 353 int cmp = k.compareTo(p.key); 354 if (cmp < 0) 355 p = p.left; 356 else if (cmp > 0) 357 p = p.right; 358 else 359 return p; 360 } 361 return null; 362 } 363 364 /** 365 * Version of getEntry using comparator. Split off from getEntry 366 * for performance. (This is not worth doing for most methods, 367 * that are less dependent on comparator performance, but is 368 * worthwhile here.) 369 */ getEntryUsingComparator(Object key)370 final TreeMapEntry<K,V> getEntryUsingComparator(Object key) { 371 @SuppressWarnings("unchecked") 372 K k = (K) key; 373 Comparator<? super K> cpr = comparator; 374 if (cpr != null) { 375 TreeMapEntry<K,V> p = root; 376 while (p != null) { 377 int cmp = cpr.compare(k, p.key); 378 if (cmp < 0) 379 p = p.left; 380 else if (cmp > 0) 381 p = p.right; 382 else 383 return p; 384 } 385 } 386 return null; 387 } 388 389 /** 390 * Gets the entry corresponding to the specified key; if no such entry 391 * exists, returns the entry for the least key greater than the specified 392 * key; if no such entry exists (i.e., the greatest key in the Tree is less 393 * than the specified key), returns {@code null}. 394 */ getCeilingEntry(K key)395 final TreeMapEntry<K,V> getCeilingEntry(K key) { 396 TreeMapEntry<K,V> p = root; 397 while (p != null) { 398 int cmp = compare(key, p.key); 399 if (cmp < 0) { 400 if (p.left != null) 401 p = p.left; 402 else 403 return p; 404 } else if (cmp > 0) { 405 if (p.right != null) { 406 p = p.right; 407 } else { 408 TreeMapEntry<K,V> parent = p.parent; 409 TreeMapEntry<K,V> ch = p; 410 while (parent != null && ch == parent.right) { 411 ch = parent; 412 parent = parent.parent; 413 } 414 return parent; 415 } 416 } else 417 return p; 418 } 419 return null; 420 } 421 422 /** 423 * Gets the entry corresponding to the specified key; if no such entry 424 * exists, returns the entry for the greatest key less than the specified 425 * key; if no such entry exists, returns {@code null}. 426 */ getFloorEntry(K key)427 final TreeMapEntry<K,V> getFloorEntry(K key) { 428 TreeMapEntry<K,V> p = root; 429 while (p != null) { 430 int cmp = compare(key, p.key); 431 if (cmp > 0) { 432 if (p.right != null) 433 p = p.right; 434 else 435 return p; 436 } else if (cmp < 0) { 437 if (p.left != null) { 438 p = p.left; 439 } else { 440 TreeMapEntry<K,V> parent = p.parent; 441 TreeMapEntry<K,V> ch = p; 442 while (parent != null && ch == parent.left) { 443 ch = parent; 444 parent = parent.parent; 445 } 446 return parent; 447 } 448 } else 449 return p; 450 451 } 452 return null; 453 } 454 455 /** 456 * Gets the entry for the least key greater than the specified 457 * key; if no such entry exists, returns the entry for the least 458 * key greater than the specified key; if no such entry exists 459 * returns {@code null}. 460 */ getHigherEntry(K key)461 final TreeMapEntry<K,V> getHigherEntry(K key) { 462 TreeMapEntry<K,V> p = root; 463 while (p != null) { 464 int cmp = compare(key, p.key); 465 if (cmp < 0) { 466 if (p.left != null) 467 p = p.left; 468 else 469 return p; 470 } else { 471 if (p.right != null) { 472 p = p.right; 473 } else { 474 TreeMapEntry<K,V> parent = p.parent; 475 TreeMapEntry<K,V> ch = p; 476 while (parent != null && ch == parent.right) { 477 ch = parent; 478 parent = parent.parent; 479 } 480 return parent; 481 } 482 } 483 } 484 return null; 485 } 486 487 /** 488 * Returns the entry for the greatest key less than the specified key; if 489 * no such entry exists (i.e., the least key in the Tree is greater than 490 * the specified key), returns {@code null}. 491 */ getLowerEntry(K key)492 final TreeMapEntry<K,V> getLowerEntry(K key) { 493 TreeMapEntry<K,V> p = root; 494 while (p != null) { 495 int cmp = compare(key, p.key); 496 if (cmp > 0) { 497 if (p.right != null) 498 p = p.right; 499 else 500 return p; 501 } else { 502 if (p.left != null) { 503 p = p.left; 504 } else { 505 TreeMapEntry<K,V> parent = p.parent; 506 TreeMapEntry<K,V> ch = p; 507 while (parent != null && ch == parent.left) { 508 ch = parent; 509 parent = parent.parent; 510 } 511 return parent; 512 } 513 } 514 } 515 return null; 516 } 517 518 /** 519 * Associates the specified value with the specified key in this map. 520 * If the map previously contained a mapping for the key, the old 521 * value is replaced. 522 * 523 * @param key key with which the specified value is to be associated 524 * @param value value to be associated with the specified key 525 * 526 * @return the previous value associated with {@code key}, or 527 * {@code null} if there was no mapping for {@code key}. 528 * (A {@code null} return can also indicate that the map 529 * previously associated {@code null} with {@code key}.) 530 * @throws ClassCastException if the specified key cannot be compared 531 * with the keys currently in the map 532 * @throws NullPointerException if the specified key is null 533 * and this map uses natural ordering, or its comparator 534 * does not permit null keys 535 */ put(K key, V value)536 public V put(K key, V value) { 537 TreeMapEntry<K,V> t = root; 538 if (t == null) { 539 // We could just call compare(key, key) for its side effect of checking the type and 540 // nullness of the input key. However, several applications seem to have written comparators 541 // that only expect to be called on elements that aren't equal to each other (after 542 // making assumptions about the domain of the map). Clearly, such comparators are bogus 543 // because get() would never work, but TreeSets are frequently used for sorting a set 544 // of distinct elements. 545 // 546 // As a temporary work around, we perform the null & instanceof checks by hand so that 547 // we can guarantee that elements are never compared against themselves. 548 // 549 // compare(key, key); 550 // 551 // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE **** 552 if (comparator != null) { 553 if (key == null) { 554 comparator.compare(key, key); 555 } 556 } else { 557 if (key == null) { 558 throw new NullPointerException("key == null"); 559 } else if (!(key instanceof Comparable)) { 560 throw new ClassCastException( 561 "Cannot cast" + key.getClass().getName() + " to Comparable."); 562 } 563 } 564 565 root = new TreeMapEntry<>(key, value, null); 566 size = 1; 567 modCount++; 568 return null; 569 } 570 int cmp; 571 TreeMapEntry<K,V> parent; 572 // split comparator and comparable paths 573 Comparator<? super K> cpr = comparator; 574 if (cpr != null) { 575 do { 576 parent = t; 577 cmp = cpr.compare(key, t.key); 578 if (cmp < 0) 579 t = t.left; 580 else if (cmp > 0) 581 t = t.right; 582 else 583 return t.setValue(value); 584 } while (t != null); 585 } 586 else { 587 if (key == null) 588 throw new NullPointerException(); 589 @SuppressWarnings("unchecked") 590 Comparable<? super K> k = (Comparable<? super K>) key; 591 do { 592 parent = t; 593 cmp = k.compareTo(t.key); 594 if (cmp < 0) 595 t = t.left; 596 else if (cmp > 0) 597 t = t.right; 598 else 599 return t.setValue(value); 600 } while (t != null); 601 } 602 TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent); 603 if (cmp < 0) 604 parent.left = e; 605 else 606 parent.right = e; 607 fixAfterInsertion(e); 608 size++; 609 modCount++; 610 return null; 611 } 612 613 /** 614 * Removes the mapping for this key from this TreeMap if present. 615 * 616 * @param key key for which mapping should be removed 617 * @return the previous value associated with {@code key}, or 618 * {@code null} if there was no mapping for {@code key}. 619 * (A {@code null} return can also indicate that the map 620 * previously associated {@code null} with {@code key}.) 621 * @throws ClassCastException if the specified key cannot be compared 622 * with the keys currently in the map 623 * @throws NullPointerException if the specified key is null 624 * and this map uses natural ordering, or its comparator 625 * does not permit null keys 626 */ remove(Object key)627 public V remove(Object key) { 628 TreeMapEntry<K,V> p = getEntry(key); 629 if (p == null) 630 return null; 631 632 V oldValue = p.value; 633 deleteEntry(p); 634 return oldValue; 635 } 636 637 /** 638 * Removes all of the mappings from this map. 639 * The map will be empty after this call returns. 640 */ clear()641 public void clear() { 642 modCount++; 643 size = 0; 644 root = null; 645 } 646 647 /** 648 * Returns a shallow copy of this {@code TreeMap} instance. (The keys and 649 * values themselves are not cloned.) 650 * 651 * @return a shallow copy of this map 652 */ clone()653 public Object clone() { 654 TreeMap<?,?> clone; 655 try { 656 clone = (TreeMap<?,?>) super.clone(); 657 } catch (CloneNotSupportedException e) { 658 throw new InternalError(e); 659 } 660 661 // Put clone into "virgin" state (except for comparator) 662 clone.root = null; 663 clone.size = 0; 664 clone.modCount = 0; 665 clone.entrySet = null; 666 clone.navigableKeySet = null; 667 clone.descendingMap = null; 668 669 // Initialize clone with our mappings 670 try { 671 clone.buildFromSorted(size, entrySet().iterator(), null, null); 672 } catch (java.io.IOException cannotHappen) { 673 } catch (ClassNotFoundException cannotHappen) { 674 } 675 676 return clone; 677 } 678 679 // NavigableMap API methods 680 681 /** 682 * @since 1.6 683 */ firstEntry()684 public Map.Entry<K,V> firstEntry() { 685 return exportEntry(getFirstEntry()); 686 } 687 688 /** 689 * @since 1.6 690 */ lastEntry()691 public Map.Entry<K,V> lastEntry() { 692 return exportEntry(getLastEntry()); 693 } 694 695 /** 696 * @since 1.6 697 */ pollFirstEntry()698 public Map.Entry<K,V> pollFirstEntry() { 699 TreeMapEntry<K,V> p = getFirstEntry(); 700 Map.Entry<K,V> result = exportEntry(p); 701 if (p != null) 702 deleteEntry(p); 703 return result; 704 } 705 706 /** 707 * @since 1.6 708 */ pollLastEntry()709 public Map.Entry<K,V> pollLastEntry() { 710 TreeMapEntry<K,V> p = getLastEntry(); 711 Map.Entry<K,V> result = exportEntry(p); 712 if (p != null) 713 deleteEntry(p); 714 return result; 715 } 716 717 /** 718 * @throws ClassCastException {@inheritDoc} 719 * @throws NullPointerException if the specified key is null 720 * and this map uses natural ordering, or its comparator 721 * does not permit null keys 722 * @since 1.6 723 */ lowerEntry(K key)724 public Map.Entry<K,V> lowerEntry(K key) { 725 return exportEntry(getLowerEntry(key)); 726 } 727 728 /** 729 * @throws ClassCastException {@inheritDoc} 730 * @throws NullPointerException if the specified key is null 731 * and this map uses natural ordering, or its comparator 732 * does not permit null keys 733 * @since 1.6 734 */ lowerKey(K key)735 public K lowerKey(K key) { 736 return keyOrNull(getLowerEntry(key)); 737 } 738 739 /** 740 * @throws ClassCastException {@inheritDoc} 741 * @throws NullPointerException if the specified key is null 742 * and this map uses natural ordering, or its comparator 743 * does not permit null keys 744 * @since 1.6 745 */ floorEntry(K key)746 public Map.Entry<K,V> floorEntry(K key) { 747 return exportEntry(getFloorEntry(key)); 748 } 749 750 /** 751 * @throws ClassCastException {@inheritDoc} 752 * @throws NullPointerException if the specified key is null 753 * and this map uses natural ordering, or its comparator 754 * does not permit null keys 755 * @since 1.6 756 */ floorKey(K key)757 public K floorKey(K key) { 758 return keyOrNull(getFloorEntry(key)); 759 } 760 761 /** 762 * @throws ClassCastException {@inheritDoc} 763 * @throws NullPointerException if the specified key is null 764 * and this map uses natural ordering, or its comparator 765 * does not permit null keys 766 * @since 1.6 767 */ ceilingEntry(K key)768 public Map.Entry<K,V> ceilingEntry(K key) { 769 return exportEntry(getCeilingEntry(key)); 770 } 771 772 /** 773 * @throws ClassCastException {@inheritDoc} 774 * @throws NullPointerException if the specified key is null 775 * and this map uses natural ordering, or its comparator 776 * does not permit null keys 777 * @since 1.6 778 */ ceilingKey(K key)779 public K ceilingKey(K key) { 780 return keyOrNull(getCeilingEntry(key)); 781 } 782 783 /** 784 * @throws ClassCastException {@inheritDoc} 785 * @throws NullPointerException if the specified key is null 786 * and this map uses natural ordering, or its comparator 787 * does not permit null keys 788 * @since 1.6 789 */ higherEntry(K key)790 public Map.Entry<K,V> higherEntry(K key) { 791 return exportEntry(getHigherEntry(key)); 792 } 793 794 /** 795 * @throws ClassCastException {@inheritDoc} 796 * @throws NullPointerException if the specified key is null 797 * and this map uses natural ordering, or its comparator 798 * does not permit null keys 799 * @since 1.6 800 */ higherKey(K key)801 public K higherKey(K key) { 802 return keyOrNull(getHigherEntry(key)); 803 } 804 805 // Views 806 807 /** 808 * Fields initialized to contain an instance of the entry set view 809 * the first time this view is requested. Views are stateless, so 810 * there's no reason to create more than one. 811 */ 812 private transient EntrySet entrySet = null; 813 private transient KeySet<K> navigableKeySet = null; 814 private transient NavigableMap<K,V> descendingMap = null; 815 816 /** 817 * Returns a {@link Set} view of the keys contained in this map. 818 * 819 * <p>The set's iterator returns the keys in ascending order. 820 * The set's spliterator is 821 * <em><a href="Spliterator.html#binding">late-binding</a></em>, 822 * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED} 823 * and {@link Spliterator#ORDERED} with an encounter order that is ascending 824 * key order. The spliterator's comparator (see 825 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 826 * the tree map's comparator (see {@link #comparator()}) is {@code null}. 827 * Otherwise, the spliterator's comparator is the same as or imposes the 828 * same total ordering as the tree map's comparator. 829 * 830 * <p>The set is backed by the map, so changes to the map are 831 * reflected in the set, and vice-versa. If the map is modified 832 * while an iteration over the set is in progress (except through 833 * the iterator's own {@code remove} operation), the results of 834 * the iteration are undefined. The set supports element removal, 835 * which removes the corresponding mapping from the map, via the 836 * {@code Iterator.remove}, {@code Set.remove}, 837 * {@code removeAll}, {@code retainAll}, and {@code clear} 838 * operations. It does not support the {@code add} or {@code addAll} 839 * operations. 840 */ keySet()841 public Set<K> keySet() { 842 return navigableKeySet(); 843 } 844 845 /** 846 * @since 1.6 847 */ navigableKeySet()848 public NavigableSet<K> navigableKeySet() { 849 KeySet<K> nks = navigableKeySet; 850 return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this)); 851 } 852 853 /** 854 * @since 1.6 855 */ descendingKeySet()856 public NavigableSet<K> descendingKeySet() { 857 return descendingMap().navigableKeySet(); 858 } 859 860 /** 861 * Returns a {@link Collection} view of the values contained in this map. 862 * 863 * <p>The collection's iterator returns the values in ascending order 864 * of the corresponding keys. The collection's spliterator is 865 * <em><a href="Spliterator.html#binding">late-binding</a></em>, 866 * <em>fail-fast</em>, and additionally reports {@link Spliterator#ORDERED} 867 * with an encounter order that is ascending order of the corresponding 868 * keys. 869 * 870 * <p>The collection is backed by the map, so changes to the map are 871 * reflected in the collection, and vice-versa. If the map is 872 * modified while an iteration over the collection is in progress 873 * (except through the iterator's own {@code remove} operation), 874 * the results of the iteration are undefined. The collection 875 * supports element removal, which removes the corresponding 876 * mapping from the map, via the {@code Iterator.remove}, 877 * {@code Collection.remove}, {@code removeAll}, 878 * {@code retainAll} and {@code clear} operations. It does not 879 * support the {@code add} or {@code addAll} operations. 880 */ values()881 public Collection<V> values() { 882 Collection<V> vs = values; 883 return (vs != null) ? vs : (values = new Values()); 884 } 885 886 /** 887 * Returns a {@link Set} view of the mappings contained in this map. 888 * 889 * <p>The set's iterator returns the entries in ascending key order. The 890 * sets's spliterator is 891 * <em><a href="Spliterator.html#binding">late-binding</a></em>, 892 * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED} and 893 * {@link Spliterator#ORDERED} with an encounter order that is ascending key 894 * order. 895 * 896 * <p>The set is backed by the map, so changes to the map are 897 * reflected in the set, and vice-versa. If the map is modified 898 * while an iteration over the set is in progress (except through 899 * the iterator's own {@code remove} operation, or through the 900 * {@code setValue} operation on a map entry returned by the 901 * iterator) the results of the iteration are undefined. The set 902 * supports element removal, which removes the corresponding 903 * mapping from the map, via the {@code Iterator.remove}, 904 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and 905 * {@code clear} operations. It does not support the 906 * {@code add} or {@code addAll} operations. 907 */ entrySet()908 public Set<Map.Entry<K,V>> entrySet() { 909 EntrySet es = entrySet; 910 return (es != null) ? es : (entrySet = new EntrySet()); 911 } 912 913 /** 914 * @since 1.6 915 */ descendingMap()916 public NavigableMap<K, V> descendingMap() { 917 NavigableMap<K, V> km = descendingMap; 918 return (km != null) ? km : 919 (descendingMap = new DescendingSubMap<>(this, 920 true, null, true, 921 true, null, true)); 922 } 923 924 /** 925 * @throws ClassCastException {@inheritDoc} 926 * @throws NullPointerException if {@code fromKey} or {@code toKey} is 927 * null and this map uses natural ordering, or its comparator 928 * does not permit null keys 929 * @throws IllegalArgumentException {@inheritDoc} 930 * @since 1.6 931 */ subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)932 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 933 K toKey, boolean toInclusive) { 934 return new AscendingSubMap<>(this, 935 false, fromKey, fromInclusive, 936 false, toKey, toInclusive); 937 } 938 939 /** 940 * @throws ClassCastException {@inheritDoc} 941 * @throws NullPointerException if {@code toKey} is null 942 * and this map uses natural ordering, or its comparator 943 * does not permit null keys 944 * @throws IllegalArgumentException {@inheritDoc} 945 * @since 1.6 946 */ headMap(K toKey, boolean inclusive)947 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { 948 return new AscendingSubMap<>(this, 949 true, null, true, 950 false, toKey, inclusive); 951 } 952 953 /** 954 * @throws ClassCastException {@inheritDoc} 955 * @throws NullPointerException if {@code fromKey} is null 956 * and this map uses natural ordering, or its comparator 957 * does not permit null keys 958 * @throws IllegalArgumentException {@inheritDoc} 959 * @since 1.6 960 */ tailMap(K fromKey, boolean inclusive)961 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { 962 return new AscendingSubMap<>(this, 963 false, fromKey, inclusive, 964 true, null, true); 965 } 966 967 /** 968 * @throws ClassCastException {@inheritDoc} 969 * @throws NullPointerException if {@code fromKey} or {@code toKey} is 970 * null and this map uses natural ordering, or its comparator 971 * does not permit null keys 972 * @throws IllegalArgumentException {@inheritDoc} 973 */ subMap(K fromKey, K toKey)974 public SortedMap<K,V> subMap(K fromKey, K toKey) { 975 return subMap(fromKey, true, toKey, false); 976 } 977 978 /** 979 * @throws ClassCastException {@inheritDoc} 980 * @throws NullPointerException if {@code toKey} is null 981 * and this map uses natural ordering, or its comparator 982 * does not permit null keys 983 * @throws IllegalArgumentException {@inheritDoc} 984 */ headMap(K toKey)985 public SortedMap<K,V> headMap(K toKey) { 986 return headMap(toKey, false); 987 } 988 989 /** 990 * @throws ClassCastException {@inheritDoc} 991 * @throws NullPointerException if {@code fromKey} is null 992 * and this map uses natural ordering, or its comparator 993 * does not permit null keys 994 * @throws IllegalArgumentException {@inheritDoc} 995 */ tailMap(K fromKey)996 public SortedMap<K,V> tailMap(K fromKey) { 997 return tailMap(fromKey, true); 998 } 999 1000 @Override replace(K key, V oldValue, V newValue)1001 public boolean replace(K key, V oldValue, V newValue) { 1002 TreeMapEntry<K,V> p = getEntry(key); 1003 if (p!=null && Objects.equals(oldValue, p.value)) { 1004 p.value = newValue; 1005 return true; 1006 } 1007 return false; 1008 } 1009 1010 @Override replace(K key, V value)1011 public V replace(K key, V value) { 1012 TreeMapEntry<K,V> p = getEntry(key); 1013 if (p!=null) { 1014 V oldValue = p.value; 1015 p.value = value; 1016 return oldValue; 1017 } 1018 return null; 1019 } 1020 1021 @Override forEach(BiConsumer<? super K, ? super V> action)1022 public void forEach(BiConsumer<? super K, ? super V> action) { 1023 Objects.requireNonNull(action); 1024 int expectedModCount = modCount; 1025 for (TreeMapEntry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { 1026 action.accept(e.key, e.value); 1027 1028 if (expectedModCount != modCount) { 1029 throw new ConcurrentModificationException(); 1030 } 1031 } 1032 } 1033 1034 @Override replaceAll(BiFunction<? super K, ? super V, ? extends V> function)1035 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1036 Objects.requireNonNull(function); 1037 int expectedModCount = modCount; 1038 1039 for (TreeMapEntry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { 1040 e.value = function.apply(e.key, e.value); 1041 1042 if (expectedModCount != modCount) { 1043 throw new ConcurrentModificationException(); 1044 } 1045 } 1046 } 1047 1048 // View class support 1049 1050 class Values extends AbstractCollection<V> { iterator()1051 public Iterator<V> iterator() { 1052 return new ValueIterator(getFirstEntry()); 1053 } 1054 size()1055 public int size() { 1056 return TreeMap.this.size(); 1057 } 1058 contains(Object o)1059 public boolean contains(Object o) { 1060 return TreeMap.this.containsValue(o); 1061 } 1062 remove(Object o)1063 public boolean remove(Object o) { 1064 for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e)) { 1065 if (valEquals(e.getValue(), o)) { 1066 deleteEntry(e); 1067 return true; 1068 } 1069 } 1070 return false; 1071 } 1072 clear()1073 public void clear() { 1074 TreeMap.this.clear(); 1075 } 1076 spliterator()1077 public Spliterator<V> spliterator() { 1078 return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0); 1079 } 1080 } 1081 1082 class EntrySet extends AbstractSet<Map.Entry<K,V>> { iterator()1083 public Iterator<Map.Entry<K,V>> iterator() { 1084 return new EntryIterator(getFirstEntry()); 1085 } 1086 contains(Object o)1087 public boolean contains(Object o) { 1088 if (!(o instanceof Map.Entry)) 1089 return false; 1090 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 1091 V value = entry.getValue(); 1092 TreeMapEntry<K,V> p = getEntry(entry.getKey()); 1093 return p != null && valEquals(p.getValue(), value); 1094 } 1095 remove(Object o)1096 public boolean remove(Object o) { 1097 if (!(o instanceof Map.Entry)) 1098 return false; 1099 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 1100 V value = entry.getValue(); 1101 TreeMapEntry<K,V> p = getEntry(entry.getKey()); 1102 if (p != null && valEquals(p.getValue(), value)) { 1103 deleteEntry(p); 1104 return true; 1105 } 1106 return false; 1107 } 1108 size()1109 public int size() { 1110 return TreeMap.this.size(); 1111 } 1112 clear()1113 public void clear() { 1114 TreeMap.this.clear(); 1115 } 1116 spliterator()1117 public Spliterator<Map.Entry<K,V>> spliterator() { 1118 return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0); 1119 } 1120 } 1121 1122 /* 1123 * Unlike Values and EntrySet, the KeySet class is static, 1124 * delegating to a NavigableMap to allow use by SubMaps, which 1125 * outweighs the ugliness of needing type-tests for the following 1126 * Iterator methods that are defined appropriately in main versus 1127 * submap classes. 1128 */ 1129 keyIterator()1130 Iterator<K> keyIterator() { 1131 return new KeyIterator(getFirstEntry()); 1132 } 1133 descendingKeyIterator()1134 Iterator<K> descendingKeyIterator() { 1135 return new DescendingKeyIterator(getLastEntry()); 1136 } 1137 1138 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { 1139 private final NavigableMap<E, ?> m; KeySet(NavigableMap<E,?> map)1140 KeySet(NavigableMap<E,?> map) { m = map; } 1141 iterator()1142 public Iterator<E> iterator() { 1143 if (m instanceof TreeMap) 1144 return ((TreeMap<E,?>)m).keyIterator(); 1145 else 1146 return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator(); 1147 } 1148 descendingIterator()1149 public Iterator<E> descendingIterator() { 1150 if (m instanceof TreeMap) 1151 return ((TreeMap<E,?>)m).descendingKeyIterator(); 1152 else 1153 return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator(); 1154 } 1155 size()1156 public int size() { return m.size(); } isEmpty()1157 public boolean isEmpty() { return m.isEmpty(); } contains(Object o)1158 public boolean contains(Object o) { return m.containsKey(o); } clear()1159 public void clear() { m.clear(); } lower(E e)1160 public E lower(E e) { return m.lowerKey(e); } floor(E e)1161 public E floor(E e) { return m.floorKey(e); } ceiling(E e)1162 public E ceiling(E e) { return m.ceilingKey(e); } higher(E e)1163 public E higher(E e) { return m.higherKey(e); } first()1164 public E first() { return m.firstKey(); } last()1165 public E last() { return m.lastKey(); } comparator()1166 public Comparator<? super E> comparator() { return m.comparator(); } pollFirst()1167 public E pollFirst() { 1168 Map.Entry<E,?> e = m.pollFirstEntry(); 1169 return (e == null) ? null : e.getKey(); 1170 } pollLast()1171 public E pollLast() { 1172 Map.Entry<E,?> e = m.pollLastEntry(); 1173 return (e == null) ? null : e.getKey(); 1174 } remove(Object o)1175 public boolean remove(Object o) { 1176 int oldSize = size(); 1177 m.remove(o); 1178 return size() != oldSize; 1179 } subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)1180 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, 1181 E toElement, boolean toInclusive) { 1182 return new KeySet<>(m.subMap(fromElement, fromInclusive, 1183 toElement, toInclusive)); 1184 } headSet(E toElement, boolean inclusive)1185 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 1186 return new KeySet<>(m.headMap(toElement, inclusive)); 1187 } tailSet(E fromElement, boolean inclusive)1188 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 1189 return new KeySet<>(m.tailMap(fromElement, inclusive)); 1190 } subSet(E fromElement, E toElement)1191 public SortedSet<E> subSet(E fromElement, E toElement) { 1192 return subSet(fromElement, true, toElement, false); 1193 } headSet(E toElement)1194 public SortedSet<E> headSet(E toElement) { 1195 return headSet(toElement, false); 1196 } tailSet(E fromElement)1197 public SortedSet<E> tailSet(E fromElement) { 1198 return tailSet(fromElement, true); 1199 } descendingSet()1200 public NavigableSet<E> descendingSet() { 1201 return new KeySet<>(m.descendingMap()); 1202 } 1203 spliterator()1204 public Spliterator<E> spliterator() { 1205 return keySpliteratorFor(m); 1206 } 1207 } 1208 1209 /** 1210 * Base class for TreeMap Iterators 1211 */ 1212 abstract class PrivateEntryIterator<T> implements Iterator<T> { 1213 TreeMapEntry<K,V> next; 1214 TreeMapEntry<K,V> lastReturned; 1215 int expectedModCount; 1216 PrivateEntryIterator(TreeMapEntry<K,V> first)1217 PrivateEntryIterator(TreeMapEntry<K,V> first) { 1218 expectedModCount = modCount; 1219 lastReturned = null; 1220 next = first; 1221 } 1222 hasNext()1223 public final boolean hasNext() { 1224 return next != null; 1225 } 1226 nextEntry()1227 final TreeMapEntry<K,V> nextEntry() { 1228 TreeMapEntry<K,V> e = next; 1229 if (e == null) 1230 throw new NoSuchElementException(); 1231 if (modCount != expectedModCount) 1232 throw new ConcurrentModificationException(); 1233 next = successor(e); 1234 lastReturned = e; 1235 return e; 1236 } 1237 prevEntry()1238 final TreeMapEntry<K,V> prevEntry() { 1239 TreeMapEntry<K,V> e = next; 1240 if (e == null) 1241 throw new NoSuchElementException(); 1242 if (modCount != expectedModCount) 1243 throw new ConcurrentModificationException(); 1244 next = predecessor(e); 1245 lastReturned = e; 1246 return e; 1247 } 1248 remove()1249 public void remove() { 1250 if (lastReturned == null) 1251 throw new IllegalStateException(); 1252 if (modCount != expectedModCount) 1253 throw new ConcurrentModificationException(); 1254 // deleted entries are replaced by their successors 1255 if (lastReturned.left != null && lastReturned.right != null) 1256 next = lastReturned; 1257 deleteEntry(lastReturned); 1258 expectedModCount = modCount; 1259 lastReturned = null; 1260 } 1261 } 1262 1263 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> { EntryIterator(TreeMapEntry<K,V> first)1264 EntryIterator(TreeMapEntry<K,V> first) { 1265 super(first); 1266 } next()1267 public Map.Entry<K,V> next() { 1268 return nextEntry(); 1269 } 1270 } 1271 1272 final class ValueIterator extends PrivateEntryIterator<V> { ValueIterator(TreeMapEntry<K,V> first)1273 ValueIterator(TreeMapEntry<K,V> first) { 1274 super(first); 1275 } next()1276 public V next() { 1277 return nextEntry().value; 1278 } 1279 } 1280 1281 final class KeyIterator extends PrivateEntryIterator<K> { KeyIterator(TreeMapEntry<K,V> first)1282 KeyIterator(TreeMapEntry<K,V> first) { 1283 super(first); 1284 } next()1285 public K next() { 1286 return nextEntry().key; 1287 } 1288 } 1289 1290 final class DescendingKeyIterator extends PrivateEntryIterator<K> { DescendingKeyIterator(TreeMapEntry<K,V> first)1291 DescendingKeyIterator(TreeMapEntry<K,V> first) { 1292 super(first); 1293 } next()1294 public K next() { 1295 return prevEntry().key; 1296 } remove()1297 public void remove() { 1298 if (lastReturned == null) 1299 throw new IllegalStateException(); 1300 if (modCount != expectedModCount) 1301 throw new ConcurrentModificationException(); 1302 deleteEntry(lastReturned); 1303 lastReturned = null; 1304 expectedModCount = modCount; 1305 } 1306 } 1307 1308 // Little utilities 1309 1310 /** 1311 * Compares two keys using the correct comparison method for this TreeMap. 1312 */ 1313 @SuppressWarnings("unchecked") compare(Object k1, Object k2)1314 final int compare(Object k1, Object k2) { 1315 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) 1316 : comparator.compare((K)k1, (K)k2); 1317 } 1318 1319 /** 1320 * Test two values for equality. Differs from o1.equals(o2) only in 1321 * that it copes with {@code null} o1 properly. 1322 */ valEquals(Object o1, Object o2)1323 static final boolean valEquals(Object o1, Object o2) { 1324 return (o1==null ? o2==null : o1.equals(o2)); 1325 } 1326 1327 /** 1328 * Return SimpleImmutableEntry for entry, or null if null 1329 */ exportEntry(TreeMapEntry<K,V> e)1330 static <K,V> Map.Entry<K,V> exportEntry(TreeMapEntry<K,V> e) { 1331 return (e == null) ? null : 1332 new AbstractMap.SimpleImmutableEntry<>(e); 1333 } 1334 1335 /** 1336 * Return key for entry, or null if null 1337 */ keyOrNull(TreeMapEntry<K,V> e)1338 static <K,V> K keyOrNull(TreeMapEntry<K,V> e) { 1339 return (e == null) ? null : e.key; 1340 } 1341 1342 /** 1343 * Returns the key corresponding to the specified Entry. 1344 * @throws NoSuchElementException if the Entry is null 1345 */ key(TreeMapEntry<K,?> e)1346 static <K> K key(TreeMapEntry<K,?> e) { 1347 if (e==null) 1348 throw new NoSuchElementException(); 1349 return e.key; 1350 } 1351 1352 1353 // SubMaps 1354 1355 /** 1356 * Dummy value serving as unmatchable fence key for unbounded 1357 * SubMapIterators 1358 */ 1359 private static final Object UNBOUNDED = new Object(); 1360 1361 /** 1362 * @serial include 1363 */ 1364 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V> 1365 implements NavigableMap<K,V>, java.io.Serializable { 1366 // Android-changed: Explicitly add a serialVersionUID so that we're serialization 1367 // compatible with the Java-7 version of this class. Several new methods were added 1368 // in Java-8 but none of them have any bearing on the serialized format of the class 1369 // or require any additional state to be preserved. 1370 private static final long serialVersionUID = 2765629423043303731L; 1371 1372 /** 1373 * The backing map. 1374 */ 1375 final TreeMap<K,V> m; 1376 1377 /** 1378 * Endpoints are represented as triples (fromStart, lo, 1379 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is 1380 * true, then the low (absolute) bound is the start of the 1381 * backing map, and the other values are ignored. Otherwise, 1382 * if loInclusive is true, lo is the inclusive bound, else lo 1383 * is the exclusive bound. Similarly for the upper bound. 1384 */ 1385 final K lo, hi; 1386 final boolean fromStart, toEnd; 1387 final boolean loInclusive, hiInclusive; 1388 NavigableSubMap(TreeMap<K,V> m, boolean fromStart, K lo, boolean loInclusive, boolean toEnd, K hi, boolean hiInclusive)1389 NavigableSubMap(TreeMap<K,V> m, 1390 boolean fromStart, K lo, boolean loInclusive, 1391 boolean toEnd, K hi, boolean hiInclusive) { 1392 if (!fromStart && !toEnd) { 1393 if (m.compare(lo, hi) > 0) 1394 throw new IllegalArgumentException("fromKey > toKey"); 1395 } else { 1396 if (!fromStart) // type check 1397 m.compare(lo, lo); 1398 if (!toEnd) 1399 m.compare(hi, hi); 1400 } 1401 1402 this.m = m; 1403 this.fromStart = fromStart; 1404 this.lo = lo; 1405 this.loInclusive = loInclusive; 1406 this.toEnd = toEnd; 1407 this.hi = hi; 1408 this.hiInclusive = hiInclusive; 1409 } 1410 1411 // internal utilities 1412 tooLow(Object key)1413 final boolean tooLow(Object key) { 1414 if (!fromStart) { 1415 int c = m.compare(key, lo); 1416 if (c < 0 || (c == 0 && !loInclusive)) 1417 return true; 1418 } 1419 return false; 1420 } 1421 tooHigh(Object key)1422 final boolean tooHigh(Object key) { 1423 if (!toEnd) { 1424 int c = m.compare(key, hi); 1425 if (c > 0 || (c == 0 && !hiInclusive)) 1426 return true; 1427 } 1428 return false; 1429 } 1430 inRange(Object key)1431 final boolean inRange(Object key) { 1432 return !tooLow(key) && !tooHigh(key); 1433 } 1434 inClosedRange(Object key)1435 final boolean inClosedRange(Object key) { 1436 return (fromStart || m.compare(key, lo) >= 0) 1437 && (toEnd || m.compare(hi, key) >= 0); 1438 } 1439 inRange(Object key, boolean inclusive)1440 final boolean inRange(Object key, boolean inclusive) { 1441 return inclusive ? inRange(key) : inClosedRange(key); 1442 } 1443 1444 /* 1445 * Absolute versions of relation operations. 1446 * Subclasses map to these using like-named "sub" 1447 * versions that invert senses for descending maps 1448 */ 1449 absLowest()1450 final TreeMapEntry<K,V> absLowest() { 1451 TreeMapEntry<K,V> e = 1452 (fromStart ? m.getFirstEntry() : 1453 (loInclusive ? m.getCeilingEntry(lo) : 1454 m.getHigherEntry(lo))); 1455 return (e == null || tooHigh(e.key)) ? null : e; 1456 } 1457 absHighest()1458 final TreeMapEntry<K,V> absHighest() { 1459 TreeMapEntry<K,V> e = 1460 (toEnd ? m.getLastEntry() : 1461 (hiInclusive ? m.getFloorEntry(hi) : 1462 m.getLowerEntry(hi))); 1463 return (e == null || tooLow(e.key)) ? null : e; 1464 } 1465 absCeiling(K key)1466 final TreeMapEntry<K,V> absCeiling(K key) { 1467 if (tooLow(key)) 1468 return absLowest(); 1469 TreeMapEntry<K,V> e = m.getCeilingEntry(key); 1470 return (e == null || tooHigh(e.key)) ? null : e; 1471 } 1472 absHigher(K key)1473 final TreeMapEntry<K,V> absHigher(K key) { 1474 if (tooLow(key)) 1475 return absLowest(); 1476 TreeMapEntry<K,V> e = m.getHigherEntry(key); 1477 return (e == null || tooHigh(e.key)) ? null : e; 1478 } 1479 absFloor(K key)1480 final TreeMapEntry<K,V> absFloor(K key) { 1481 if (tooHigh(key)) 1482 return absHighest(); 1483 TreeMapEntry<K,V> e = m.getFloorEntry(key); 1484 return (e == null || tooLow(e.key)) ? null : e; 1485 } 1486 absLower(K key)1487 final TreeMapEntry<K,V> absLower(K key) { 1488 if (tooHigh(key)) 1489 return absHighest(); 1490 TreeMapEntry<K,V> e = m.getLowerEntry(key); 1491 return (e == null || tooLow(e.key)) ? null : e; 1492 } 1493 1494 /** Returns the absolute high fence for ascending traversal */ absHighFence()1495 final TreeMapEntry<K,V> absHighFence() { 1496 return (toEnd ? null : (hiInclusive ? 1497 m.getHigherEntry(hi) : 1498 m.getCeilingEntry(hi))); 1499 } 1500 1501 /** Return the absolute low fence for descending traversal */ absLowFence()1502 final TreeMapEntry<K,V> absLowFence() { 1503 return (fromStart ? null : (loInclusive ? 1504 m.getLowerEntry(lo) : 1505 m.getFloorEntry(lo))); 1506 } 1507 1508 // Abstract methods defined in ascending vs descending classes 1509 // These relay to the appropriate absolute versions 1510 subLowest()1511 abstract TreeMapEntry<K,V> subLowest(); subHighest()1512 abstract TreeMapEntry<K,V> subHighest(); subCeiling(K key)1513 abstract TreeMapEntry<K,V> subCeiling(K key); subHigher(K key)1514 abstract TreeMapEntry<K,V> subHigher(K key); subFloor(K key)1515 abstract TreeMapEntry<K,V> subFloor(K key); subLower(K key)1516 abstract TreeMapEntry<K,V> subLower(K key); 1517 1518 /** Returns ascending iterator from the perspective of this submap */ keyIterator()1519 abstract Iterator<K> keyIterator(); 1520 keySpliterator()1521 abstract Spliterator<K> keySpliterator(); 1522 1523 /** Returns descending iterator from the perspective of this submap */ descendingKeyIterator()1524 abstract Iterator<K> descendingKeyIterator(); 1525 1526 // public methods 1527 isEmpty()1528 public boolean isEmpty() { 1529 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty(); 1530 } 1531 size()1532 public int size() { 1533 return (fromStart && toEnd) ? m.size() : entrySet().size(); 1534 } 1535 containsKey(Object key)1536 public final boolean containsKey(Object key) { 1537 return inRange(key) && m.containsKey(key); 1538 } 1539 put(K key, V value)1540 public final V put(K key, V value) { 1541 if (!inRange(key)) 1542 throw new IllegalArgumentException("key out of range"); 1543 return m.put(key, value); 1544 } 1545 get(Object key)1546 public final V get(Object key) { 1547 return !inRange(key) ? null : m.get(key); 1548 } 1549 remove(Object key)1550 public final V remove(Object key) { 1551 return !inRange(key) ? null : m.remove(key); 1552 } 1553 ceilingEntry(K key)1554 public final Map.Entry<K,V> ceilingEntry(K key) { 1555 return exportEntry(subCeiling(key)); 1556 } 1557 ceilingKey(K key)1558 public final K ceilingKey(K key) { 1559 return keyOrNull(subCeiling(key)); 1560 } 1561 higherEntry(K key)1562 public final Map.Entry<K,V> higherEntry(K key) { 1563 return exportEntry(subHigher(key)); 1564 } 1565 higherKey(K key)1566 public final K higherKey(K key) { 1567 return keyOrNull(subHigher(key)); 1568 } 1569 floorEntry(K key)1570 public final Map.Entry<K,V> floorEntry(K key) { 1571 return exportEntry(subFloor(key)); 1572 } 1573 floorKey(K key)1574 public final K floorKey(K key) { 1575 return keyOrNull(subFloor(key)); 1576 } 1577 lowerEntry(K key)1578 public final Map.Entry<K,V> lowerEntry(K key) { 1579 return exportEntry(subLower(key)); 1580 } 1581 lowerKey(K key)1582 public final K lowerKey(K key) { 1583 return keyOrNull(subLower(key)); 1584 } 1585 firstKey()1586 public final K firstKey() { 1587 return key(subLowest()); 1588 } 1589 lastKey()1590 public final K lastKey() { 1591 return key(subHighest()); 1592 } 1593 firstEntry()1594 public final Map.Entry<K,V> firstEntry() { 1595 return exportEntry(subLowest()); 1596 } 1597 lastEntry()1598 public final Map.Entry<K,V> lastEntry() { 1599 return exportEntry(subHighest()); 1600 } 1601 pollFirstEntry()1602 public final Map.Entry<K,V> pollFirstEntry() { 1603 TreeMapEntry<K,V> e = subLowest(); 1604 Map.Entry<K,V> result = exportEntry(e); 1605 if (e != null) 1606 m.deleteEntry(e); 1607 return result; 1608 } 1609 pollLastEntry()1610 public final Map.Entry<K,V> pollLastEntry() { 1611 TreeMapEntry<K,V> e = subHighest(); 1612 Map.Entry<K,V> result = exportEntry(e); 1613 if (e != null) 1614 m.deleteEntry(e); 1615 return result; 1616 } 1617 1618 // Views 1619 transient NavigableMap<K,V> descendingMapView = null; 1620 transient EntrySetView entrySetView = null; 1621 transient KeySet<K> navigableKeySetView = null; 1622 navigableKeySet()1623 public final NavigableSet<K> navigableKeySet() { 1624 KeySet<K> nksv = navigableKeySetView; 1625 return (nksv != null) ? nksv : 1626 (navigableKeySetView = new TreeMap.KeySet<>(this)); 1627 } 1628 keySet()1629 public final Set<K> keySet() { 1630 return navigableKeySet(); 1631 } 1632 descendingKeySet()1633 public NavigableSet<K> descendingKeySet() { 1634 return descendingMap().navigableKeySet(); 1635 } 1636 subMap(K fromKey, K toKey)1637 public final SortedMap<K,V> subMap(K fromKey, K toKey) { 1638 return subMap(fromKey, true, toKey, false); 1639 } 1640 headMap(K toKey)1641 public final SortedMap<K,V> headMap(K toKey) { 1642 return headMap(toKey, false); 1643 } 1644 tailMap(K fromKey)1645 public final SortedMap<K,V> tailMap(K fromKey) { 1646 return tailMap(fromKey, true); 1647 } 1648 1649 // View classes 1650 1651 abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> { 1652 private transient int size = -1, sizeModCount; 1653 size()1654 public int size() { 1655 if (fromStart && toEnd) 1656 return m.size(); 1657 if (size == -1 || sizeModCount != m.modCount) { 1658 sizeModCount = m.modCount; 1659 size = 0; 1660 Iterator<?> i = iterator(); 1661 while (i.hasNext()) { 1662 size++; 1663 i.next(); 1664 } 1665 } 1666 return size; 1667 } 1668 isEmpty()1669 public boolean isEmpty() { 1670 TreeMapEntry<K,V> n = absLowest(); 1671 return n == null || tooHigh(n.key); 1672 } 1673 contains(Object o)1674 public boolean contains(Object o) { 1675 if (!(o instanceof Map.Entry)) 1676 return false; 1677 Map.Entry<?,?> entry = (Map.Entry<?,?>) o; 1678 Object key = entry.getKey(); 1679 if (!inRange(key)) 1680 return false; 1681 TreeMapEntry<?, ?> node = m.getEntry(key); 1682 return node != null && 1683 valEquals(node.getValue(), entry.getValue()); 1684 } 1685 remove(Object o)1686 public boolean remove(Object o) { 1687 if (!(o instanceof Map.Entry)) 1688 return false; 1689 Map.Entry<?,?> entry = (Map.Entry<?,?>) o; 1690 Object key = entry.getKey(); 1691 if (!inRange(key)) 1692 return false; 1693 TreeMapEntry<K,V> node = m.getEntry(key); 1694 if (node!=null && valEquals(node.getValue(), 1695 entry.getValue())) { 1696 m.deleteEntry(node); 1697 return true; 1698 } 1699 return false; 1700 } 1701 } 1702 1703 /** 1704 * Iterators for SubMaps 1705 */ 1706 abstract class SubMapIterator<T> implements Iterator<T> { 1707 TreeMapEntry<K,V> lastReturned; 1708 TreeMapEntry<K,V> next; 1709 final Object fenceKey; 1710 int expectedModCount; 1711 SubMapIterator(TreeMapEntry<K,V> first, TreeMapEntry<K,V> fence)1712 SubMapIterator(TreeMapEntry<K,V> first, 1713 TreeMapEntry<K,V> fence) { 1714 expectedModCount = m.modCount; 1715 lastReturned = null; 1716 next = first; 1717 fenceKey = fence == null ? UNBOUNDED : fence.key; 1718 } 1719 hasNext()1720 public final boolean hasNext() { 1721 return next != null && next.key != fenceKey; 1722 } 1723 nextEntry()1724 final TreeMapEntry<K,V> nextEntry() { 1725 TreeMapEntry<K,V> e = next; 1726 if (e == null || e.key == fenceKey) 1727 throw new NoSuchElementException(); 1728 if (m.modCount != expectedModCount) 1729 throw new ConcurrentModificationException(); 1730 next = successor(e); 1731 lastReturned = e; 1732 return e; 1733 } 1734 prevEntry()1735 final TreeMapEntry<K,V> prevEntry() { 1736 TreeMapEntry<K,V> e = next; 1737 if (e == null || e.key == fenceKey) 1738 throw new NoSuchElementException(); 1739 if (m.modCount != expectedModCount) 1740 throw new ConcurrentModificationException(); 1741 next = predecessor(e); 1742 lastReturned = e; 1743 return e; 1744 } 1745 removeAscending()1746 final void removeAscending() { 1747 if (lastReturned == null) 1748 throw new IllegalStateException(); 1749 if (m.modCount != expectedModCount) 1750 throw new ConcurrentModificationException(); 1751 // deleted entries are replaced by their successors 1752 if (lastReturned.left != null && lastReturned.right != null) 1753 next = lastReturned; 1754 m.deleteEntry(lastReturned); 1755 lastReturned = null; 1756 expectedModCount = m.modCount; 1757 } 1758 removeDescending()1759 final void removeDescending() { 1760 if (lastReturned == null) 1761 throw new IllegalStateException(); 1762 if (m.modCount != expectedModCount) 1763 throw new ConcurrentModificationException(); 1764 m.deleteEntry(lastReturned); 1765 lastReturned = null; 1766 expectedModCount = m.modCount; 1767 } 1768 1769 } 1770 1771 final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { SubMapEntryIterator(TreeMapEntry<K,V> first, TreeMapEntry<K,V> fence)1772 SubMapEntryIterator(TreeMapEntry<K,V> first, 1773 TreeMapEntry<K,V> fence) { 1774 super(first, fence); 1775 } next()1776 public Map.Entry<K,V> next() { 1777 return nextEntry(); 1778 } remove()1779 public void remove() { 1780 removeAscending(); 1781 } 1782 } 1783 1784 final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { DescendingSubMapEntryIterator(TreeMapEntry<K,V> last, TreeMapEntry<K,V> fence)1785 DescendingSubMapEntryIterator(TreeMapEntry<K,V> last, 1786 TreeMapEntry<K,V> fence) { 1787 super(last, fence); 1788 } 1789 next()1790 public Map.Entry<K,V> next() { 1791 return prevEntry(); 1792 } remove()1793 public void remove() { 1794 removeDescending(); 1795 } 1796 } 1797 1798 // Implement minimal Spliterator as KeySpliterator backup 1799 final class SubMapKeyIterator extends SubMapIterator<K> 1800 implements Spliterator<K> { SubMapKeyIterator(TreeMapEntry<K,V> first, TreeMapEntry<K,V> fence)1801 SubMapKeyIterator(TreeMapEntry<K,V> first, 1802 TreeMapEntry<K,V> fence) { 1803 super(first, fence); 1804 } next()1805 public K next() { 1806 return nextEntry().key; 1807 } remove()1808 public void remove() { 1809 removeAscending(); 1810 } trySplit()1811 public Spliterator<K> trySplit() { 1812 return null; 1813 } forEachRemaining(Consumer<? super K> action)1814 public void forEachRemaining(Consumer<? super K> action) { 1815 while (hasNext()) 1816 action.accept(next()); 1817 } tryAdvance(Consumer<? super K> action)1818 public boolean tryAdvance(Consumer<? super K> action) { 1819 if (hasNext()) { 1820 action.accept(next()); 1821 return true; 1822 } 1823 return false; 1824 } estimateSize()1825 public long estimateSize() { 1826 return Long.MAX_VALUE; 1827 } characteristics()1828 public int characteristics() { 1829 return Spliterator.DISTINCT | Spliterator.ORDERED | 1830 Spliterator.SORTED; 1831 } getComparator()1832 public final Comparator<? super K> getComparator() { 1833 return NavigableSubMap.this.comparator(); 1834 } 1835 } 1836 1837 final class DescendingSubMapKeyIterator extends SubMapIterator<K> 1838 implements Spliterator<K> { DescendingSubMapKeyIterator(TreeMapEntry<K,V> last, TreeMapEntry<K,V> fence)1839 DescendingSubMapKeyIterator(TreeMapEntry<K,V> last, 1840 TreeMapEntry<K,V> fence) { 1841 super(last, fence); 1842 } next()1843 public K next() { 1844 return prevEntry().key; 1845 } remove()1846 public void remove() { 1847 removeDescending(); 1848 } trySplit()1849 public Spliterator<K> trySplit() { 1850 return null; 1851 } forEachRemaining(Consumer<? super K> action)1852 public void forEachRemaining(Consumer<? super K> action) { 1853 while (hasNext()) 1854 action.accept(next()); 1855 } tryAdvance(Consumer<? super K> action)1856 public boolean tryAdvance(Consumer<? super K> action) { 1857 if (hasNext()) { 1858 action.accept(next()); 1859 return true; 1860 } 1861 return false; 1862 } estimateSize()1863 public long estimateSize() { 1864 return Long.MAX_VALUE; 1865 } characteristics()1866 public int characteristics() { 1867 return Spliterator.DISTINCT | Spliterator.ORDERED; 1868 } 1869 } 1870 } 1871 1872 /** 1873 * @serial include 1874 */ 1875 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> { 1876 private static final long serialVersionUID = 912986545866124060L; 1877 AscendingSubMap(TreeMap<K,V> m, boolean fromStart, K lo, boolean loInclusive, boolean toEnd, K hi, boolean hiInclusive)1878 AscendingSubMap(TreeMap<K,V> m, 1879 boolean fromStart, K lo, boolean loInclusive, 1880 boolean toEnd, K hi, boolean hiInclusive) { 1881 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); 1882 } 1883 comparator()1884 public Comparator<? super K> comparator() { 1885 return m.comparator(); 1886 } 1887 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)1888 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 1889 K toKey, boolean toInclusive) { 1890 if (!inRange(fromKey, fromInclusive)) 1891 throw new IllegalArgumentException("fromKey out of range"); 1892 if (!inRange(toKey, toInclusive)) 1893 throw new IllegalArgumentException("toKey out of range"); 1894 return new AscendingSubMap<>(m, 1895 false, fromKey, fromInclusive, 1896 false, toKey, toInclusive); 1897 } 1898 headMap(K toKey, boolean inclusive)1899 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { 1900 /* ----- BEGIN android ----- 1901 Fix for edge cases 1902 if (!inRange(toKey, inclusive)) */ 1903 if (!inRange(toKey) && !(!toEnd && m.compare(toKey, hi) == 0 && 1904 !hiInclusive && !inclusive)) 1905 // ----- END android ----- 1906 throw new IllegalArgumentException("toKey out of range"); 1907 return new AscendingSubMap<>(m, 1908 fromStart, lo, loInclusive, 1909 false, toKey, inclusive); 1910 } 1911 tailMap(K fromKey, boolean inclusive)1912 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { 1913 /* ----- BEGIN android ----- 1914 Fix for edge cases 1915 if (!inRange(fromKey, inclusive)) */ 1916 if (!inRange(fromKey) && !(!fromStart && m.compare(fromKey, lo) == 0 && 1917 !loInclusive && !inclusive)) 1918 // ----- END android ----- 1919 throw new IllegalArgumentException("fromKey out of range"); 1920 return new AscendingSubMap<>(m, 1921 false, fromKey, inclusive, 1922 toEnd, hi, hiInclusive); 1923 } 1924 descendingMap()1925 public NavigableMap<K,V> descendingMap() { 1926 NavigableMap<K,V> mv = descendingMapView; 1927 return (mv != null) ? mv : 1928 (descendingMapView = 1929 new DescendingSubMap<>(m, 1930 fromStart, lo, loInclusive, 1931 toEnd, hi, hiInclusive)); 1932 } 1933 keyIterator()1934 Iterator<K> keyIterator() { 1935 return new SubMapKeyIterator(absLowest(), absHighFence()); 1936 } 1937 keySpliterator()1938 Spliterator<K> keySpliterator() { 1939 return new SubMapKeyIterator(absLowest(), absHighFence()); 1940 } 1941 descendingKeyIterator()1942 Iterator<K> descendingKeyIterator() { 1943 return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); 1944 } 1945 1946 final class AscendingEntrySetView extends EntrySetView { iterator()1947 public Iterator<Map.Entry<K,V>> iterator() { 1948 return new SubMapEntryIterator(absLowest(), absHighFence()); 1949 } 1950 } 1951 entrySet()1952 public Set<Map.Entry<K,V>> entrySet() { 1953 EntrySetView es = entrySetView; 1954 return (es != null) ? es : new AscendingEntrySetView(); 1955 } 1956 subLowest()1957 TreeMapEntry<K,V> subLowest() { return absLowest(); } subHighest()1958 TreeMapEntry<K,V> subHighest() { return absHighest(); } subCeiling(K key)1959 TreeMapEntry<K,V> subCeiling(K key) { return absCeiling(key); } subHigher(K key)1960 TreeMapEntry<K,V> subHigher(K key) { return absHigher(key); } subFloor(K key)1961 TreeMapEntry<K,V> subFloor(K key) { return absFloor(key); } subLower(K key)1962 TreeMapEntry<K,V> subLower(K key) { return absLower(key); } 1963 } 1964 1965 /** 1966 * @serial include 1967 */ 1968 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { 1969 private static final long serialVersionUID = 912986545866120460L; DescendingSubMap(TreeMap<K,V> m, boolean fromStart, K lo, boolean loInclusive, boolean toEnd, K hi, boolean hiInclusive)1970 DescendingSubMap(TreeMap<K,V> m, 1971 boolean fromStart, K lo, boolean loInclusive, 1972 boolean toEnd, K hi, boolean hiInclusive) { 1973 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); 1974 } 1975 1976 private final Comparator<? super K> reverseComparator = 1977 Collections.reverseOrder(m.comparator); 1978 comparator()1979 public Comparator<? super K> comparator() { 1980 return reverseComparator; 1981 } 1982 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)1983 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 1984 K toKey, boolean toInclusive) { 1985 if (!inRange(fromKey, fromInclusive)) 1986 throw new IllegalArgumentException("fromKey out of range"); 1987 if (!inRange(toKey, toInclusive)) 1988 throw new IllegalArgumentException("toKey out of range"); 1989 return new DescendingSubMap<>(m, 1990 false, toKey, toInclusive, 1991 false, fromKey, fromInclusive); 1992 } 1993 headMap(K toKey, boolean inclusive)1994 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { 1995 /* ----- BEGIN android ----- 1996 Fix for edge cases 1997 if (!inRange(toKey, inclusive)) */ 1998 if (!inRange(toKey) && !(!fromStart && m.compare(toKey, lo) == 0 && 1999 !loInclusive && !inclusive)) 2000 // ----- END android ----- 2001 throw new IllegalArgumentException("toKey out of range"); 2002 return new DescendingSubMap<>(m, 2003 false, toKey, inclusive, 2004 toEnd, hi, hiInclusive); 2005 } 2006 tailMap(K fromKey, boolean inclusive)2007 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { 2008 /* ----- BEGIN android ----- 2009 Fix for edge cases 2010 if (!inRange(fromKey, inclusive)) */ 2011 if (!inRange(fromKey) && !(!toEnd && m.compare(fromKey, hi) == 0 && 2012 !hiInclusive && !inclusive)) 2013 // ----- END android ----- 2014 throw new IllegalArgumentException("fromKey out of range"); 2015 return new DescendingSubMap<>(m, 2016 fromStart, lo, loInclusive, 2017 false, fromKey, inclusive); 2018 } 2019 descendingMap()2020 public NavigableMap<K,V> descendingMap() { 2021 NavigableMap<K,V> mv = descendingMapView; 2022 return (mv != null) ? mv : 2023 (descendingMapView = 2024 new AscendingSubMap<>(m, 2025 fromStart, lo, loInclusive, 2026 toEnd, hi, hiInclusive)); 2027 } 2028 keyIterator()2029 Iterator<K> keyIterator() { 2030 return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); 2031 } 2032 keySpliterator()2033 Spliterator<K> keySpliterator() { 2034 return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); 2035 } 2036 descendingKeyIterator()2037 Iterator<K> descendingKeyIterator() { 2038 return new SubMapKeyIterator(absLowest(), absHighFence()); 2039 } 2040 2041 final class DescendingEntrySetView extends EntrySetView { iterator()2042 public Iterator<Map.Entry<K,V>> iterator() { 2043 return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); 2044 } 2045 } 2046 entrySet()2047 public Set<Map.Entry<K,V>> entrySet() { 2048 EntrySetView es = entrySetView; 2049 return (es != null) ? es : (entrySetView = new DescendingEntrySetView()); 2050 } 2051 subLowest()2052 TreeMapEntry<K,V> subLowest() { return absHighest(); } subHighest()2053 TreeMapEntry<K,V> subHighest() { return absLowest(); } subCeiling(K key)2054 TreeMapEntry<K,V> subCeiling(K key) { return absFloor(key); } subHigher(K key)2055 TreeMapEntry<K,V> subHigher(K key) { return absLower(key); } subFloor(K key)2056 TreeMapEntry<K,V> subFloor(K key) { return absCeiling(key); } subLower(K key)2057 TreeMapEntry<K,V> subLower(K key) { return absHigher(key); } 2058 } 2059 2060 /** 2061 * This class exists solely for the sake of serialization 2062 * compatibility with previous releases of TreeMap that did not 2063 * support NavigableMap. It translates an old-version SubMap into 2064 * a new-version AscendingSubMap. This class is never otherwise 2065 * used. 2066 * 2067 * @serial include 2068 */ 2069 private class SubMap extends AbstractMap<K,V> 2070 implements SortedMap<K,V>, java.io.Serializable { 2071 private static final long serialVersionUID = -6520786458950516097L; 2072 private boolean fromStart = false, toEnd = false; 2073 private K fromKey, toKey; readResolve()2074 private Object readResolve() { 2075 return new AscendingSubMap<>(TreeMap.this, 2076 fromStart, fromKey, true, 2077 toEnd, toKey, false); 2078 } entrySet()2079 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); } lastKey()2080 public K lastKey() { throw new InternalError(); } firstKey()2081 public K firstKey() { throw new InternalError(); } subMap(K fromKey, K toKey)2082 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); } headMap(K toKey)2083 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); } tailMap(K fromKey)2084 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); } comparator()2085 public Comparator<? super K> comparator() { throw new InternalError(); } 2086 } 2087 2088 2089 // Red-black mechanics 2090 2091 private static final boolean RED = false; 2092 private static final boolean BLACK = true; 2093 2094 /** 2095 * Node in the Tree. Doubles as a means to pass key-value pairs back to 2096 * user (see Map.Entry). 2097 */ 2098 2099 static final class TreeMapEntry<K,V> implements Map.Entry<K,V> { 2100 K key; 2101 V value; 2102 TreeMapEntry<K,V> left = null; 2103 TreeMapEntry<K,V> right = null; 2104 TreeMapEntry<K,V> parent; 2105 boolean color = BLACK; 2106 2107 /** 2108 * Make a new cell with given key, value, and parent, and with 2109 * {@code null} child links, and BLACK color. 2110 */ TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent)2111 TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) { 2112 this.key = key; 2113 this.value = value; 2114 this.parent = parent; 2115 } 2116 2117 /** 2118 * Returns the key. 2119 * 2120 * @return the key 2121 */ getKey()2122 public K getKey() { 2123 return key; 2124 } 2125 2126 /** 2127 * Returns the value associated with the key. 2128 * 2129 * @return the value associated with the key 2130 */ getValue()2131 public V getValue() { 2132 return value; 2133 } 2134 2135 /** 2136 * Replaces the value currently associated with the key with the given 2137 * value. 2138 * 2139 * @return the value associated with the key before this method was 2140 * called 2141 */ setValue(V value)2142 public V setValue(V value) { 2143 V oldValue = this.value; 2144 this.value = value; 2145 return oldValue; 2146 } 2147 equals(Object o)2148 public boolean equals(Object o) { 2149 if (!(o instanceof Map.Entry)) 2150 return false; 2151 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 2152 2153 return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); 2154 } 2155 hashCode()2156 public int hashCode() { 2157 int keyHash = (key==null ? 0 : key.hashCode()); 2158 int valueHash = (value==null ? 0 : value.hashCode()); 2159 return keyHash ^ valueHash; 2160 } 2161 toString()2162 public String toString() { 2163 return key + "=" + value; 2164 } 2165 } 2166 2167 /** 2168 * Returns the first Entry in the TreeMap (according to the TreeMap's 2169 * key-sort function). Returns null if the TreeMap is empty. 2170 */ getFirstEntry()2171 final TreeMapEntry<K,V> getFirstEntry() { 2172 TreeMapEntry<K,V> p = root; 2173 if (p != null) 2174 while (p.left != null) 2175 p = p.left; 2176 return p; 2177 } 2178 2179 /** 2180 * Returns the last Entry in the TreeMap (according to the TreeMap's 2181 * key-sort function). Returns null if the TreeMap is empty. 2182 */ getLastEntry()2183 final TreeMapEntry<K,V> getLastEntry() { 2184 TreeMapEntry<K,V> p = root; 2185 if (p != null) 2186 while (p.right != null) 2187 p = p.right; 2188 return p; 2189 } 2190 2191 /** 2192 * Returns the successor of the specified Entry, or null if no such. 2193 */ successor(TreeMapEntry<K,V> t)2194 static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) { 2195 if (t == null) 2196 return null; 2197 else if (t.right != null) { 2198 TreeMapEntry<K,V> p = t.right; 2199 while (p.left != null) 2200 p = p.left; 2201 return p; 2202 } else { 2203 TreeMapEntry<K,V> p = t.parent; 2204 TreeMapEntry<K,V> ch = t; 2205 while (p != null && ch == p.right) { 2206 ch = p; 2207 p = p.parent; 2208 } 2209 return p; 2210 } 2211 } 2212 2213 /** 2214 * Returns the predecessor of the specified Entry, or null if no such. 2215 */ predecessor(TreeMapEntry<K,V> t)2216 static <K,V> TreeMapEntry<K,V> predecessor(TreeMapEntry<K,V> t) { 2217 if (t == null) 2218 return null; 2219 else if (t.left != null) { 2220 TreeMapEntry<K,V> p = t.left; 2221 while (p.right != null) 2222 p = p.right; 2223 return p; 2224 } else { 2225 TreeMapEntry<K,V> p = t.parent; 2226 TreeMapEntry<K,V> ch = t; 2227 while (p != null && ch == p.left) { 2228 ch = p; 2229 p = p.parent; 2230 } 2231 return p; 2232 } 2233 } 2234 2235 /** 2236 * Balancing operations. 2237 * 2238 * Implementations of rebalancings during insertion and deletion are 2239 * slightly different than the CLR version. Rather than using dummy 2240 * nilnodes, we use a set of accessors that deal properly with null. They 2241 * are used to avoid messiness surrounding nullness checks in the main 2242 * algorithms. 2243 */ 2244 colorOf(TreeMapEntry<K,V> p)2245 private static <K,V> boolean colorOf(TreeMapEntry<K,V> p) { 2246 return (p == null ? BLACK : p.color); 2247 } 2248 parentOf(TreeMapEntry<K,V> p)2249 private static <K,V> TreeMapEntry<K,V> parentOf(TreeMapEntry<K,V> p) { 2250 return (p == null ? null: p.parent); 2251 } 2252 setColor(TreeMapEntry<K,V> p, boolean c)2253 private static <K,V> void setColor(TreeMapEntry<K,V> p, boolean c) { 2254 if (p != null) 2255 p.color = c; 2256 } 2257 leftOf(TreeMapEntry<K,V> p)2258 private static <K,V> TreeMapEntry<K,V> leftOf(TreeMapEntry<K,V> p) { 2259 return (p == null) ? null: p.left; 2260 } 2261 rightOf(TreeMapEntry<K,V> p)2262 private static <K,V> TreeMapEntry<K,V> rightOf(TreeMapEntry<K,V> p) { 2263 return (p == null) ? null: p.right; 2264 } 2265 2266 /** From CLR */ rotateLeft(TreeMapEntry<K,V> p)2267 private void rotateLeft(TreeMapEntry<K,V> p) { 2268 if (p != null) { 2269 TreeMapEntry<K,V> r = p.right; 2270 p.right = r.left; 2271 if (r.left != null) 2272 r.left.parent = p; 2273 r.parent = p.parent; 2274 if (p.parent == null) 2275 root = r; 2276 else if (p.parent.left == p) 2277 p.parent.left = r; 2278 else 2279 p.parent.right = r; 2280 r.left = p; 2281 p.parent = r; 2282 } 2283 } 2284 2285 /** From CLR */ rotateRight(TreeMapEntry<K,V> p)2286 private void rotateRight(TreeMapEntry<K,V> p) { 2287 if (p != null) { 2288 TreeMapEntry<K,V> l = p.left; 2289 p.left = l.right; 2290 if (l.right != null) l.right.parent = p; 2291 l.parent = p.parent; 2292 if (p.parent == null) 2293 root = l; 2294 else if (p.parent.right == p) 2295 p.parent.right = l; 2296 else p.parent.left = l; 2297 l.right = p; 2298 p.parent = l; 2299 } 2300 } 2301 2302 /** From CLR */ fixAfterInsertion(TreeMapEntry<K,V> x)2303 private void fixAfterInsertion(TreeMapEntry<K,V> x) { 2304 x.color = RED; 2305 2306 while (x != null && x != root && x.parent.color == RED) { 2307 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 2308 TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x))); 2309 if (colorOf(y) == RED) { 2310 setColor(parentOf(x), BLACK); 2311 setColor(y, BLACK); 2312 setColor(parentOf(parentOf(x)), RED); 2313 x = parentOf(parentOf(x)); 2314 } else { 2315 if (x == rightOf(parentOf(x))) { 2316 x = parentOf(x); 2317 rotateLeft(x); 2318 } 2319 setColor(parentOf(x), BLACK); 2320 setColor(parentOf(parentOf(x)), RED); 2321 rotateRight(parentOf(parentOf(x))); 2322 } 2323 } else { 2324 TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x))); 2325 if (colorOf(y) == RED) { 2326 setColor(parentOf(x), BLACK); 2327 setColor(y, BLACK); 2328 setColor(parentOf(parentOf(x)), RED); 2329 x = parentOf(parentOf(x)); 2330 } else { 2331 if (x == leftOf(parentOf(x))) { 2332 x = parentOf(x); 2333 rotateRight(x); 2334 } 2335 setColor(parentOf(x), BLACK); 2336 setColor(parentOf(parentOf(x)), RED); 2337 rotateLeft(parentOf(parentOf(x))); 2338 } 2339 } 2340 } 2341 root.color = BLACK; 2342 } 2343 2344 /** 2345 * Delete node p, and then rebalance the tree. 2346 */ deleteEntry(TreeMapEntry<K,V> p)2347 private void deleteEntry(TreeMapEntry<K,V> p) { 2348 modCount++; 2349 size--; 2350 2351 // If strictly internal, copy successor's element to p and then make p 2352 // point to successor. 2353 if (p.left != null && p.right != null) { 2354 TreeMapEntry<K,V> s = successor(p); 2355 p.key = s.key; 2356 p.value = s.value; 2357 p = s; 2358 } // p has 2 children 2359 2360 // Start fixup at replacement node, if it exists. 2361 TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right); 2362 2363 if (replacement != null) { 2364 // Link replacement to parent 2365 replacement.parent = p.parent; 2366 if (p.parent == null) 2367 root = replacement; 2368 else if (p == p.parent.left) 2369 p.parent.left = replacement; 2370 else 2371 p.parent.right = replacement; 2372 2373 // Null out links so they are OK to use by fixAfterDeletion. 2374 p.left = p.right = p.parent = null; 2375 2376 // Fix replacement 2377 if (p.color == BLACK) 2378 fixAfterDeletion(replacement); 2379 } else if (p.parent == null) { // return if we are the only node. 2380 root = null; 2381 } else { // No children. Use self as phantom replacement and unlink. 2382 if (p.color == BLACK) 2383 fixAfterDeletion(p); 2384 2385 if (p.parent != null) { 2386 if (p == p.parent.left) 2387 p.parent.left = null; 2388 else if (p == p.parent.right) 2389 p.parent.right = null; 2390 p.parent = null; 2391 } 2392 } 2393 } 2394 2395 /** From CLR */ fixAfterDeletion(TreeMapEntry<K,V> x)2396 private void fixAfterDeletion(TreeMapEntry<K,V> x) { 2397 while (x != root && colorOf(x) == BLACK) { 2398 if (x == leftOf(parentOf(x))) { 2399 TreeMapEntry<K,V> sib = rightOf(parentOf(x)); 2400 2401 if (colorOf(sib) == RED) { 2402 setColor(sib, BLACK); 2403 setColor(parentOf(x), RED); 2404 rotateLeft(parentOf(x)); 2405 sib = rightOf(parentOf(x)); 2406 } 2407 2408 if (colorOf(leftOf(sib)) == BLACK && 2409 colorOf(rightOf(sib)) == BLACK) { 2410 setColor(sib, RED); 2411 x = parentOf(x); 2412 } else { 2413 if (colorOf(rightOf(sib)) == BLACK) { 2414 setColor(leftOf(sib), BLACK); 2415 setColor(sib, RED); 2416 rotateRight(sib); 2417 sib = rightOf(parentOf(x)); 2418 } 2419 setColor(sib, colorOf(parentOf(x))); 2420 setColor(parentOf(x), BLACK); 2421 setColor(rightOf(sib), BLACK); 2422 rotateLeft(parentOf(x)); 2423 x = root; 2424 } 2425 } else { // symmetric 2426 TreeMapEntry<K,V> sib = leftOf(parentOf(x)); 2427 2428 if (colorOf(sib) == RED) { 2429 setColor(sib, BLACK); 2430 setColor(parentOf(x), RED); 2431 rotateRight(parentOf(x)); 2432 sib = leftOf(parentOf(x)); 2433 } 2434 2435 if (colorOf(rightOf(sib)) == BLACK && 2436 colorOf(leftOf(sib)) == BLACK) { 2437 setColor(sib, RED); 2438 x = parentOf(x); 2439 } else { 2440 if (colorOf(leftOf(sib)) == BLACK) { 2441 setColor(rightOf(sib), BLACK); 2442 setColor(sib, RED); 2443 rotateLeft(sib); 2444 sib = leftOf(parentOf(x)); 2445 } 2446 setColor(sib, colorOf(parentOf(x))); 2447 setColor(parentOf(x), BLACK); 2448 setColor(leftOf(sib), BLACK); 2449 rotateRight(parentOf(x)); 2450 x = root; 2451 } 2452 } 2453 } 2454 2455 setColor(x, BLACK); 2456 } 2457 2458 private static final long serialVersionUID = 919286545866124006L; 2459 2460 /** 2461 * Save the state of the {@code TreeMap} instance to a stream (i.e., 2462 * serialize it). 2463 * 2464 * @serialData The <em>size</em> of the TreeMap (the number of key-value 2465 * mappings) is emitted (int), followed by the key (Object) 2466 * and value (Object) for each key-value mapping represented 2467 * by the TreeMap. The key-value mappings are emitted in 2468 * key-order (as determined by the TreeMap's Comparator, 2469 * or by the keys' natural ordering if the TreeMap has no 2470 * Comparator). 2471 */ writeObject(java.io.ObjectOutputStream s)2472 private void writeObject(java.io.ObjectOutputStream s) 2473 throws java.io.IOException { 2474 // Write out the Comparator and any hidden stuff 2475 s.defaultWriteObject(); 2476 2477 // Write out size (number of Mappings) 2478 s.writeInt(size); 2479 2480 // Write out keys and values (alternating) 2481 for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) { 2482 Map.Entry<K,V> e = i.next(); 2483 s.writeObject(e.getKey()); 2484 s.writeObject(e.getValue()); 2485 } 2486 } 2487 2488 /** 2489 * Reconstitute the {@code TreeMap} instance from a stream (i.e., 2490 * deserialize it). 2491 */ readObject(final java.io.ObjectInputStream s)2492 private void readObject(final java.io.ObjectInputStream s) 2493 throws java.io.IOException, ClassNotFoundException { 2494 // Read in the Comparator and any hidden stuff 2495 s.defaultReadObject(); 2496 2497 // Read in size 2498 int size = s.readInt(); 2499 2500 buildFromSorted(size, null, s, null); 2501 } 2502 2503 /** Intended to be called only from TreeSet.readObject */ readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)2504 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal) 2505 throws java.io.IOException, ClassNotFoundException { 2506 buildFromSorted(size, null, s, defaultVal); 2507 } 2508 2509 /** Intended to be called only from TreeSet.addAll */ addAllForTreeSet(SortedSet<? extends K> set, V defaultVal)2510 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) { 2511 try { 2512 buildFromSorted(set.size(), set.iterator(), null, defaultVal); 2513 } catch (java.io.IOException cannotHappen) { 2514 } catch (ClassNotFoundException cannotHappen) { 2515 } 2516 } 2517 2518 2519 /** 2520 * Linear time tree building algorithm from sorted data. Can accept keys 2521 * and/or values from iterator or stream. This leads to too many 2522 * parameters, but seems better than alternatives. The four formats 2523 * that this method accepts are: 2524 * 2525 * 1) An iterator of Map.Entries. (it != null, defaultVal == null). 2526 * 2) An iterator of keys. (it != null, defaultVal != null). 2527 * 3) A stream of alternating serialized keys and values. 2528 * (it == null, defaultVal == null). 2529 * 4) A stream of serialized keys. (it == null, defaultVal != null). 2530 * 2531 * It is assumed that the comparator of the TreeMap is already set prior 2532 * to calling this method. 2533 * 2534 * @param size the number of keys (or key-value pairs) to be read from 2535 * the iterator or stream 2536 * @param it If non-null, new entries are created from entries 2537 * or keys read from this iterator. 2538 * @param str If non-null, new entries are created from keys and 2539 * possibly values read from this stream in serialized form. 2540 * Exactly one of it and str should be non-null. 2541 * @param defaultVal if non-null, this default value is used for 2542 * each value in the map. If null, each value is read from 2543 * iterator or stream, as described above. 2544 * @throws java.io.IOException propagated from stream reads. This cannot 2545 * occur if str is null. 2546 * @throws ClassNotFoundException propagated from readObject. 2547 * This cannot occur if str is null. 2548 */ buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal)2549 private void buildFromSorted(int size, Iterator<?> it, 2550 java.io.ObjectInputStream str, 2551 V defaultVal) 2552 throws java.io.IOException, ClassNotFoundException { 2553 this.size = size; 2554 root = buildFromSorted(0, 0, size-1, computeRedLevel(size), 2555 it, str, defaultVal); 2556 } 2557 2558 /** 2559 * Recursive "helper method" that does the real work of the 2560 * previous method. Identically named parameters have 2561 * identical definitions. Additional parameters are documented below. 2562 * It is assumed that the comparator and size fields of the TreeMap are 2563 * already set prior to calling this method. (It ignores both fields.) 2564 * 2565 * @param level the current level of tree. Initial call should be 0. 2566 * @param lo the first element index of this subtree. Initial should be 0. 2567 * @param hi the last element index of this subtree. Initial should be 2568 * size-1. 2569 * @param redLevel the level at which nodes should be red. 2570 * Must be equal to computeRedLevel for tree of this size. 2571 */ 2572 @SuppressWarnings("unchecked") buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal)2573 private final TreeMapEntry<K,V> buildFromSorted(int level, int lo, int hi, 2574 int redLevel, 2575 Iterator<?> it, 2576 java.io.ObjectInputStream str, 2577 V defaultVal) 2578 throws java.io.IOException, ClassNotFoundException { 2579 /* 2580 * Strategy: The root is the middlemost element. To get to it, we 2581 * have to first recursively construct the entire left subtree, 2582 * so as to grab all of its elements. We can then proceed with right 2583 * subtree. 2584 * 2585 * The lo and hi arguments are the minimum and maximum 2586 * indices to pull out of the iterator or stream for current subtree. 2587 * They are not actually indexed, we just proceed sequentially, 2588 * ensuring that items are extracted in corresponding order. 2589 */ 2590 2591 if (hi < lo) return null; 2592 2593 int mid = (lo + hi) >>> 1; 2594 2595 TreeMapEntry<K,V> left = null; 2596 if (lo < mid) 2597 left = buildFromSorted(level+1, lo, mid - 1, redLevel, 2598 it, str, defaultVal); 2599 2600 // extract key and/or value from iterator or stream 2601 K key; 2602 V value; 2603 if (it != null) { 2604 if (defaultVal==null) { 2605 Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next(); 2606 key = entry.getKey(); 2607 value = entry.getValue(); 2608 } else { 2609 key = (K)it.next(); 2610 value = defaultVal; 2611 } 2612 } else { // use stream 2613 key = (K) str.readObject(); 2614 value = (defaultVal != null ? defaultVal : (V) str.readObject()); 2615 } 2616 2617 TreeMapEntry<K,V> middle = new TreeMapEntry<>(key, value, null); 2618 2619 // color nodes in non-full bottommost level red 2620 if (level == redLevel) 2621 middle.color = RED; 2622 2623 if (left != null) { 2624 middle.left = left; 2625 left.parent = middle; 2626 } 2627 2628 if (mid < hi) { 2629 TreeMapEntry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, 2630 it, str, defaultVal); 2631 middle.right = right; 2632 right.parent = middle; 2633 } 2634 2635 return middle; 2636 } 2637 2638 /** 2639 * Find the level down to which to assign all nodes BLACK. This is the 2640 * last `full' level of the complete binary tree produced by 2641 * buildTree. The remaining nodes are colored RED. (This makes a `nice' 2642 * set of color assignments wrt future insertions.) This level number is 2643 * computed by finding the number of splits needed to reach the zeroeth 2644 * node. (The answer is ~lg(N), but in any case must be computed by same 2645 * quick O(lg(N)) loop.) 2646 */ computeRedLevel(int sz)2647 private static int computeRedLevel(int sz) { 2648 int level = 0; 2649 for (int m = sz - 1; m >= 0; m = m / 2 - 1) 2650 level++; 2651 return level; 2652 } 2653 2654 /** 2655 * Currently, we support Spliterator-based versions only for the 2656 * full map, in either plain of descending form, otherwise relying 2657 * on defaults because size estimation for submaps would dominate 2658 * costs. The type tests needed to check these for key views are 2659 * not very nice but avoid disrupting existing class 2660 * structures. Callers must use plain default spliterators if this 2661 * returns null. 2662 */ keySpliteratorFor(NavigableMap<K,?> m)2663 static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) { 2664 if (m instanceof TreeMap) { 2665 @SuppressWarnings("unchecked") TreeMap<K,Object> t = 2666 (TreeMap<K,Object>) m; 2667 return t.keySpliterator(); 2668 } 2669 if (m instanceof DescendingSubMap) { 2670 @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm = 2671 (DescendingSubMap<K,?>) m; 2672 TreeMap<K,?> tm = dm.m; 2673 if (dm == tm.descendingMap) { 2674 @SuppressWarnings("unchecked") TreeMap<K,Object> t = 2675 (TreeMap<K,Object>) tm; 2676 return t.descendingKeySpliterator(); 2677 } 2678 } 2679 @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm = 2680 (NavigableSubMap<K,?>) m; 2681 return sm.keySpliterator(); 2682 } 2683 keySpliterator()2684 final Spliterator<K> keySpliterator() { 2685 return new KeySpliterator<K,V>(this, null, null, 0, -1, 0); 2686 } 2687 descendingKeySpliterator()2688 final Spliterator<K> descendingKeySpliterator() { 2689 return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0); 2690 } 2691 2692 /** 2693 * Base class for spliterators. Iteration starts at a given 2694 * origin and continues up to but not including a given fence (or 2695 * null for end). At top-level, for ascending cases, the first 2696 * split uses the root as left-fence/right-origin. From there, 2697 * right-hand splits replace the current fence with its left 2698 * child, also serving as origin for the split-off spliterator. 2699 * Left-hands are symmetric. Descending versions place the origin 2700 * at the end and invert ascending split rules. This base class 2701 * is non-commital about directionality, or whether the top-level 2702 * spliterator covers the whole tree. This means that the actual 2703 * split mechanics are located in subclasses. Some of the subclass 2704 * trySplit methods are identical (except for return types), but 2705 * not nicely factorable. 2706 * 2707 * Currently, subclass versions exist only for the full map 2708 * (including descending keys via its descendingMap). Others are 2709 * possible but currently not worthwhile because submaps require 2710 * O(n) computations to determine size, which substantially limits 2711 * potential speed-ups of using custom Spliterators versus default 2712 * mechanics. 2713 * 2714 * To boostrap initialization, external constructors use 2715 * negative size estimates: -1 for ascend, -2 for descend. 2716 */ 2717 static class TreeMapSpliterator<K,V> { 2718 final TreeMap<K,V> tree; 2719 TreeMapEntry<K,V> current; // traverser; initially first node in range 2720 TreeMapEntry<K,V> fence; // one past last, or null 2721 int side; // 0: top, -1: is a left split, +1: right 2722 int est; // size estimate (exact only for top-level) 2723 int expectedModCount; // for CME checks 2724 TreeMapSpliterator(TreeMap<K,V> tree, TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, int side, int est, int expectedModCount)2725 TreeMapSpliterator(TreeMap<K,V> tree, 2726 TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, 2727 int side, int est, int expectedModCount) { 2728 this.tree = tree; 2729 this.current = origin; 2730 this.fence = fence; 2731 this.side = side; 2732 this.est = est; 2733 this.expectedModCount = expectedModCount; 2734 } 2735 getEstimate()2736 final int getEstimate() { // force initialization 2737 int s; TreeMap<K,V> t; 2738 if ((s = est) < 0) { 2739 if ((t = tree) != null) { 2740 current = (s == -1) ? t.getFirstEntry() : t.getLastEntry(); 2741 s = est = t.size; 2742 expectedModCount = t.modCount; 2743 } 2744 else 2745 s = est = 0; 2746 } 2747 return s; 2748 } 2749 estimateSize()2750 public final long estimateSize() { 2751 return (long)getEstimate(); 2752 } 2753 } 2754 2755 static final class KeySpliterator<K,V> 2756 extends TreeMapSpliterator<K,V> 2757 implements Spliterator<K> { KeySpliterator(TreeMap<K,V> tree, TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, int side, int est, int expectedModCount)2758 KeySpliterator(TreeMap<K,V> tree, 2759 TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, 2760 int side, int est, int expectedModCount) { 2761 super(tree, origin, fence, side, est, expectedModCount); 2762 } 2763 trySplit()2764 public KeySpliterator<K,V> trySplit() { 2765 if (est < 0) 2766 getEstimate(); // force initialization 2767 int d = side; 2768 TreeMapEntry<K,V> e = current, f = fence, 2769 s = ((e == null || e == f) ? null : // empty 2770 (d == 0) ? tree.root : // was top 2771 (d > 0) ? e.right : // was right 2772 (d < 0 && f != null) ? f.left : // was left 2773 null); 2774 if (s != null && s != e && s != f && 2775 tree.compare(e.key, s.key) < 0) { // e not already past s 2776 side = 1; 2777 return new KeySpliterator<> 2778 (tree, e, current = s, -1, est >>>= 1, expectedModCount); 2779 } 2780 return null; 2781 } 2782 forEachRemaining(Consumer<? super K> action)2783 public void forEachRemaining(Consumer<? super K> action) { 2784 if (action == null) 2785 throw new NullPointerException(); 2786 if (est < 0) 2787 getEstimate(); // force initialization 2788 TreeMapEntry<K,V> f = fence, e, p, pl; 2789 if ((e = current) != null && e != f) { 2790 current = f; // exhaust 2791 do { 2792 action.accept(e.key); 2793 if ((p = e.right) != null) { 2794 while ((pl = p.left) != null) 2795 p = pl; 2796 } 2797 else { 2798 while ((p = e.parent) != null && e == p.right) 2799 e = p; 2800 } 2801 } while ((e = p) != null && e != f); 2802 if (tree.modCount != expectedModCount) 2803 throw new ConcurrentModificationException(); 2804 } 2805 } 2806 tryAdvance(Consumer<? super K> action)2807 public boolean tryAdvance(Consumer<? super K> action) { 2808 TreeMapEntry<K,V> e; 2809 if (action == null) 2810 throw new NullPointerException(); 2811 if (est < 0) 2812 getEstimate(); // force initialization 2813 if ((e = current) == null || e == fence) 2814 return false; 2815 current = successor(e); 2816 action.accept(e.key); 2817 if (tree.modCount != expectedModCount) 2818 throw new ConcurrentModificationException(); 2819 return true; 2820 } 2821 characteristics()2822 public int characteristics() { 2823 return (side == 0 ? Spliterator.SIZED : 0) | 2824 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED; 2825 } 2826 getComparator()2827 public final Comparator<? super K> getComparator() { 2828 return tree.comparator; 2829 } 2830 2831 } 2832 2833 static final class DescendingKeySpliterator<K,V> 2834 extends TreeMapSpliterator<K,V> 2835 implements Spliterator<K> { DescendingKeySpliterator(TreeMap<K,V> tree, TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, int side, int est, int expectedModCount)2836 DescendingKeySpliterator(TreeMap<K,V> tree, 2837 TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, 2838 int side, int est, int expectedModCount) { 2839 super(tree, origin, fence, side, est, expectedModCount); 2840 } 2841 trySplit()2842 public DescendingKeySpliterator<K,V> trySplit() { 2843 if (est < 0) 2844 getEstimate(); // force initialization 2845 int d = side; 2846 TreeMapEntry<K,V> e = current, f = fence, 2847 s = ((e == null || e == f) ? null : // empty 2848 (d == 0) ? tree.root : // was top 2849 (d < 0) ? e.left : // was left 2850 (d > 0 && f != null) ? f.right : // was right 2851 null); 2852 if (s != null && s != e && s != f && 2853 tree.compare(e.key, s.key) > 0) { // e not already past s 2854 side = 1; 2855 return new DescendingKeySpliterator<> 2856 (tree, e, current = s, -1, est >>>= 1, expectedModCount); 2857 } 2858 return null; 2859 } 2860 forEachRemaining(Consumer<? super K> action)2861 public void forEachRemaining(Consumer<? super K> action) { 2862 if (action == null) 2863 throw new NullPointerException(); 2864 if (est < 0) 2865 getEstimate(); // force initialization 2866 TreeMapEntry<K,V> f = fence, e, p, pr; 2867 if ((e = current) != null && e != f) { 2868 current = f; // exhaust 2869 do { 2870 action.accept(e.key); 2871 if ((p = e.left) != null) { 2872 while ((pr = p.right) != null) 2873 p = pr; 2874 } 2875 else { 2876 while ((p = e.parent) != null && e == p.left) 2877 e = p; 2878 } 2879 } while ((e = p) != null && e != f); 2880 if (tree.modCount != expectedModCount) 2881 throw new ConcurrentModificationException(); 2882 } 2883 } 2884 tryAdvance(Consumer<? super K> action)2885 public boolean tryAdvance(Consumer<? super K> action) { 2886 TreeMapEntry<K,V> e; 2887 if (action == null) 2888 throw new NullPointerException(); 2889 if (est < 0) 2890 getEstimate(); // force initialization 2891 if ((e = current) == null || e == fence) 2892 return false; 2893 current = predecessor(e); 2894 action.accept(e.key); 2895 if (tree.modCount != expectedModCount) 2896 throw new ConcurrentModificationException(); 2897 return true; 2898 } 2899 characteristics()2900 public int characteristics() { 2901 return (side == 0 ? Spliterator.SIZED : 0) | 2902 Spliterator.DISTINCT | Spliterator.ORDERED; 2903 } 2904 } 2905 2906 static final class ValueSpliterator<K,V> 2907 extends TreeMapSpliterator<K,V> 2908 implements Spliterator<V> { ValueSpliterator(TreeMap<K,V> tree, TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, int side, int est, int expectedModCount)2909 ValueSpliterator(TreeMap<K,V> tree, 2910 TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, 2911 int side, int est, int expectedModCount) { 2912 super(tree, origin, fence, side, est, expectedModCount); 2913 } 2914 trySplit()2915 public ValueSpliterator<K,V> trySplit() { 2916 if (est < 0) 2917 getEstimate(); // force initialization 2918 int d = side; 2919 TreeMapEntry<K,V> e = current, f = fence, 2920 s = ((e == null || e == f) ? null : // empty 2921 (d == 0) ? tree.root : // was top 2922 (d > 0) ? e.right : // was right 2923 (d < 0 && f != null) ? f.left : // was left 2924 null); 2925 if (s != null && s != e && s != f && 2926 tree.compare(e.key, s.key) < 0) { // e not already past s 2927 side = 1; 2928 return new ValueSpliterator<> 2929 (tree, e, current = s, -1, est >>>= 1, expectedModCount); 2930 } 2931 return null; 2932 } 2933 forEachRemaining(Consumer<? super V> action)2934 public void forEachRemaining(Consumer<? super V> action) { 2935 if (action == null) 2936 throw new NullPointerException(); 2937 if (est < 0) 2938 getEstimate(); // force initialization 2939 TreeMapEntry<K,V> f = fence, e, p, pl; 2940 if ((e = current) != null && e != f) { 2941 current = f; // exhaust 2942 do { 2943 action.accept(e.value); 2944 if ((p = e.right) != null) { 2945 while ((pl = p.left) != null) 2946 p = pl; 2947 } 2948 else { 2949 while ((p = e.parent) != null && e == p.right) 2950 e = p; 2951 } 2952 } while ((e = p) != null && e != f); 2953 if (tree.modCount != expectedModCount) 2954 throw new ConcurrentModificationException(); 2955 } 2956 } 2957 tryAdvance(Consumer<? super V> action)2958 public boolean tryAdvance(Consumer<? super V> action) { 2959 TreeMapEntry<K,V> e; 2960 if (action == null) 2961 throw new NullPointerException(); 2962 if (est < 0) 2963 getEstimate(); // force initialization 2964 if ((e = current) == null || e == fence) 2965 return false; 2966 current = successor(e); 2967 action.accept(e.value); 2968 if (tree.modCount != expectedModCount) 2969 throw new ConcurrentModificationException(); 2970 return true; 2971 } 2972 characteristics()2973 public int characteristics() { 2974 return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.ORDERED; 2975 } 2976 } 2977 2978 static final class EntrySpliterator<K,V> 2979 extends TreeMapSpliterator<K,V> 2980 implements Spliterator<Map.Entry<K,V>> { EntrySpliterator(TreeMap<K,V> tree, TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, int side, int est, int expectedModCount)2981 EntrySpliterator(TreeMap<K,V> tree, 2982 TreeMapEntry<K,V> origin, TreeMapEntry<K,V> fence, 2983 int side, int est, int expectedModCount) { 2984 super(tree, origin, fence, side, est, expectedModCount); 2985 } 2986 trySplit()2987 public EntrySpliterator<K,V> trySplit() { 2988 if (est < 0) 2989 getEstimate(); // force initialization 2990 int d = side; 2991 TreeMapEntry<K,V> e = current, f = fence, 2992 s = ((e == null || e == f) ? null : // empty 2993 (d == 0) ? tree.root : // was top 2994 (d > 0) ? e.right : // was right 2995 (d < 0 && f != null) ? f.left : // was left 2996 null); 2997 if (s != null && s != e && s != f && 2998 tree.compare(e.key, s.key) < 0) { // e not already past s 2999 side = 1; 3000 return new EntrySpliterator<> 3001 (tree, e, current = s, -1, est >>>= 1, expectedModCount); 3002 } 3003 return null; 3004 } 3005 forEachRemaining(Consumer<? super Map.Entry<K, V>> action)3006 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) { 3007 if (action == null) 3008 throw new NullPointerException(); 3009 if (est < 0) 3010 getEstimate(); // force initialization 3011 TreeMapEntry<K,V> f = fence, e, p, pl; 3012 if ((e = current) != null && e != f) { 3013 current = f; // exhaust 3014 do { 3015 action.accept(e); 3016 if ((p = e.right) != null) { 3017 while ((pl = p.left) != null) 3018 p = pl; 3019 } 3020 else { 3021 while ((p = e.parent) != null && e == p.right) 3022 e = p; 3023 } 3024 } while ((e = p) != null && e != f); 3025 if (tree.modCount != expectedModCount) 3026 throw new ConcurrentModificationException(); 3027 } 3028 } 3029 tryAdvance(Consumer<? super Map.Entry<K,V>> action)3030 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 3031 TreeMapEntry<K,V> e; 3032 if (action == null) 3033 throw new NullPointerException(); 3034 if (est < 0) 3035 getEstimate(); // force initialization 3036 if ((e = current) == null || e == fence) 3037 return false; 3038 current = successor(e); 3039 action.accept(e); 3040 if (tree.modCount != expectedModCount) 3041 throw new ConcurrentModificationException(); 3042 return true; 3043 } 3044 characteristics()3045 public int characteristics() { 3046 return (side == 0 ? Spliterator.SIZED : 0) | 3047 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED; 3048 } 3049 3050 @Override getComparator()3051 public Comparator<Map.Entry<K, V>> getComparator() { 3052 // Adapt or create a key-based comparator 3053 if (tree.comparator != null) { 3054 return Map.Entry.comparingByKey(tree.comparator); 3055 } 3056 else { 3057 return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> { 3058 @SuppressWarnings("unchecked") 3059 Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey(); 3060 return k1.compareTo(e2.getKey()); 3061 }; 3062 } 3063 } 3064 } 3065 } 3066