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