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