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