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