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