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