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