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