001 /* TreeMap.java -- a class providing a basic Red-Black Tree data structure, 002 mapping Object --> Object 003 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. 004 005 This file is part of GNU Classpath. 006 007 GNU Classpath is free software; you can redistribute it and/or modify 008 it under the terms of the GNU General Public License as published by 009 the Free Software Foundation; either version 2, or (at your option) 010 any later version. 011 012 GNU Classpath is distributed in the hope that it will be useful, but 013 WITHOUT ANY WARRANTY; without even the implied warranty of 014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015 General Public License for more details. 016 017 You should have received a copy of the GNU General Public License 018 along with GNU Classpath; see the file COPYING. If not, write to the 019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 020 02110-1301 USA. 021 022 Linking this library statically or dynamically with other modules is 023 making a combined work based on this library. Thus, the terms and 024 conditions of the GNU General Public License cover the whole 025 combination. 026 027 As a special exception, the copyright holders of this library give you 028 permission to link this library with independent modules to produce an 029 executable, regardless of the license terms of these independent 030 modules, and to copy and distribute the resulting executable under 031 terms of your choice, provided that you also meet, for each linked 032 independent module, the terms and conditions of the license of that 033 module. An independent module is a module which is not derived from 034 or based on this library. If you modify this library, you may extend 035 this exception to your version of the library, but you are not 036 obligated to do so. If you do not wish to do so, delete this 037 exception statement from your version. */ 038 039 040 package java.util; 041 042 import java.io.IOException; 043 import java.io.ObjectInputStream; 044 import java.io.ObjectOutputStream; 045 import java.io.Serializable; 046 047 /** 048 * This class provides a red-black tree implementation of the SortedMap 049 * interface. Elements in the Map will be sorted by either a user-provided 050 * Comparator object, or by the natural ordering of the keys. 051 * 052 * The algorithms are adopted from Corman, Leiserson, and Rivest's 053 * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n) 054 * insertion and deletion of elements. That being said, there is a large 055 * enough constant coefficient in front of that "log n" (overhead involved 056 * in keeping the tree balanced), that TreeMap may not be the best choice 057 * for small collections. If something is already sorted, you may want to 058 * just use a LinkedHashMap to maintain the order while providing O(1) access. 059 * 060 * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed 061 * only if a Comparator is used which can deal with them; natural ordering 062 * cannot cope with null. Null values are always allowed. Note that the 063 * ordering must be <i>consistent with equals</i> to correctly implement 064 * the Map interface. If this condition is violated, the map is still 065 * well-behaved, but you may have suprising results when comparing it to 066 * other maps.<p> 067 * 068 * This implementation is not synchronized. If you need to share this between 069 * multiple threads, do something like:<br> 070 * <code>SortedMap m 071 * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p> 072 * 073 * The iterators are <i>fail-fast</i>, meaning that any structural 074 * modification, except for <code>remove()</code> called on the iterator 075 * itself, cause the iterator to throw a 076 * <code>ConcurrentModificationException</code> rather than exhibit 077 * non-deterministic behavior. 078 * 079 * @author Jon Zeppieri 080 * @author Bryce McKinlay 081 * @author Eric Blake (ebb9@email.byu.edu) 082 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 083 * @see Map 084 * @see HashMap 085 * @see Hashtable 086 * @see LinkedHashMap 087 * @see Comparable 088 * @see Comparator 089 * @see Collection 090 * @see Collections#synchronizedSortedMap(SortedMap) 091 * @since 1.2 092 * @status updated to 1.6 093 */ 094 public class TreeMap<K, V> extends AbstractMap<K, V> 095 implements NavigableMap<K, V>, Cloneable, Serializable 096 { 097 // Implementation note: 098 // A red-black tree is a binary search tree with the additional properties 099 // that all paths to a leaf node visit the same number of black nodes, 100 // and no red node has red children. To avoid some null-pointer checks, 101 // we use the special node nil which is always black, has no relatives, 102 // and has key and value of null (but is not equal to a mapping of null). 103 104 /** 105 * Compatible with JDK 1.2. 106 */ 107 private static final long serialVersionUID = 919286545866124006L; 108 109 /** 110 * Color status of a node. Package visible for use by nested classes. 111 */ 112 static final int RED = -1, 113 BLACK = 1; 114 115 /** 116 * Sentinal node, used to avoid null checks for corner cases and make the 117 * delete rebalance code simpler. The rebalance code must never assign 118 * the parent, left, or right of nil, but may safely reassign the color 119 * to be black. This object must never be used as a key in a TreeMap, or 120 * it will break bounds checking of a SubMap. 121 */ 122 static final Node nil = new Node(null, null, BLACK); 123 static 124 { 125 // Nil is self-referential, so we must initialize it after creation. 126 nil.parent = nil; 127 nil.left = nil; 128 nil.right = nil; 129 } 130 131 /** 132 * The root node of this TreeMap. 133 */ 134 private transient Node root; 135 136 /** 137 * The size of this TreeMap. Package visible for use by nested classes. 138 */ 139 transient int size; 140 141 /** 142 * The cache for {@link #entrySet()}. 143 */ 144 private transient Set<Map.Entry<K,V>> entries; 145 146 /** 147 * The cache for {@link #descendingMap()}. 148 */ 149 private transient NavigableMap<K,V> descendingMap; 150 151 /** 152 * The cache for {@link #navigableKeySet()}. 153 */ 154 private transient NavigableSet<K> nKeys; 155 156 /** 157 * Counts the number of modifications this TreeMap has undergone, used 158 * by Iterators to know when to throw ConcurrentModificationExceptions. 159 * Package visible for use by nested classes. 160 */ 161 transient int modCount; 162 163 /** 164 * This TreeMap's comparator, or null for natural ordering. 165 * Package visible for use by nested classes. 166 * @serial the comparator ordering this tree, or null 167 */ 168 final Comparator<? super K> comparator; 169 170 /** 171 * Class to represent an entry in the tree. Holds a single key-value pair, 172 * plus pointers to parent and child nodes. 173 * 174 * @author Eric Blake (ebb9@email.byu.edu) 175 */ 176 private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V> 177 { 178 // All fields package visible for use by nested classes. 179 /** The color of this node. */ 180 int color; 181 182 /** The left child node. */ 183 Node<K, V> left = nil; 184 /** The right child node. */ 185 Node<K, V> right = nil; 186 /** The parent node. */ 187 Node<K, V> parent = nil; 188 189 /** 190 * Simple constructor. 191 * @param key the key 192 * @param value the value 193 */ 194 Node(K key, V value, int color) 195 { 196 super(key, value); 197 this.color = color; 198 } 199 } 200 201 /** 202 * Instantiate a new TreeMap with no elements, using the keys' natural 203 * ordering to sort. All entries in the map must have a key which implements 204 * Comparable, and which are <i>mutually comparable</i>, otherwise map 205 * operations may throw a {@link ClassCastException}. Attempts to use 206 * a null key will throw a {@link NullPointerException}. 207 * 208 * @see Comparable 209 */ 210 public TreeMap() 211 { 212 this((Comparator) null); 213 } 214 215 /** 216 * Instantiate a new TreeMap with no elements, using the provided comparator 217 * to sort. All entries in the map must have keys which are mutually 218 * comparable by the Comparator, otherwise map operations may throw a 219 * {@link ClassCastException}. 220 * 221 * @param c the sort order for the keys of this map, or null 222 * for the natural order 223 */ 224 public TreeMap(Comparator<? super K> c) 225 { 226 comparator = c; 227 fabricateTree(0); 228 } 229 230 /** 231 * Instantiate a new TreeMap, initializing it with all of the elements in 232 * the provided Map. The elements will be sorted using the natural 233 * ordering of the keys. This algorithm runs in n*log(n) time. All entries 234 * in the map must have keys which implement Comparable and are mutually 235 * comparable, otherwise map operations may throw a 236 * {@link ClassCastException}. 237 * 238 * @param map a Map, whose entries will be put into this TreeMap 239 * @throws ClassCastException if the keys in the provided Map are not 240 * comparable 241 * @throws NullPointerException if map is null 242 * @see Comparable 243 */ 244 public TreeMap(Map<? extends K, ? extends V> map) 245 { 246 this((Comparator) null); 247 putAll(map); 248 } 249 250 /** 251 * Instantiate a new TreeMap, initializing it with all of the elements in 252 * the provided SortedMap. The elements will be sorted using the same 253 * comparator as in the provided SortedMap. This runs in linear time. 254 * 255 * @param sm a SortedMap, whose entries will be put into this TreeMap 256 * @throws NullPointerException if sm is null 257 */ 258 public TreeMap(SortedMap<K, ? extends V> sm) 259 { 260 this(sm.comparator()); 261 int pos = sm.size(); 262 Iterator itr = sm.entrySet().iterator(); 263 264 fabricateTree(pos); 265 Node node = firstNode(); 266 267 while (--pos >= 0) 268 { 269 Map.Entry me = (Map.Entry) itr.next(); 270 node.key = me.getKey(); 271 node.value = me.getValue(); 272 node = successor(node); 273 } 274 } 275 276 /** 277 * Clears the Map so it has no keys. This is O(1). 278 */ 279 public void clear() 280 { 281 if (size > 0) 282 { 283 modCount++; 284 root = nil; 285 size = 0; 286 } 287 } 288 289 /** 290 * Returns a shallow clone of this TreeMap. The Map itself is cloned, 291 * but its contents are not. 292 * 293 * @return the clone 294 */ 295 public Object clone() 296 { 297 TreeMap copy = null; 298 try 299 { 300 copy = (TreeMap) super.clone(); 301 } 302 catch (CloneNotSupportedException x) 303 { 304 } 305 copy.entries = null; 306 copy.fabricateTree(size); 307 308 Node node = firstNode(); 309 Node cnode = copy.firstNode(); 310 311 while (node != nil) 312 { 313 cnode.key = node.key; 314 cnode.value = node.value; 315 node = successor(node); 316 cnode = copy.successor(cnode); 317 } 318 return copy; 319 } 320 321 /** 322 * Return the comparator used to sort this map, or null if it is by 323 * natural order. 324 * 325 * @return the map's comparator 326 */ 327 public Comparator<? super K> comparator() 328 { 329 return comparator; 330 } 331 332 /** 333 * Returns true if the map contains a mapping for the given key. 334 * 335 * @param key the key to look for 336 * @return true if the key has a mapping 337 * @throws ClassCastException if key is not comparable to map elements 338 * @throws NullPointerException if key is null and the comparator is not 339 * tolerant of nulls 340 */ 341 public boolean containsKey(Object key) 342 { 343 return getNode((K) key) != nil; 344 } 345 346 /** 347 * Returns true if the map contains at least one mapping to the given value. 348 * This requires linear time. 349 * 350 * @param value the value to look for 351 * @return true if the value appears in a mapping 352 */ 353 public boolean containsValue(Object value) 354 { 355 Node node = firstNode(); 356 while (node != nil) 357 { 358 if (equals(value, node.value)) 359 return true; 360 node = successor(node); 361 } 362 return false; 363 } 364 365 /** 366 * Returns a "set view" of this TreeMap's entries. The set is backed by 367 * the TreeMap, so changes in one show up in the other. The set supports 368 * element removal, but not element addition.<p> 369 * 370 * Note that the iterators for all three views, from keySet(), entrySet(), 371 * and values(), traverse the TreeMap in sorted sequence. 372 * 373 * @return a set view of the entries 374 * @see #keySet() 375 * @see #values() 376 * @see Map.Entry 377 */ 378 public Set<Map.Entry<K,V>> entrySet() 379 { 380 if (entries == null) 381 // Create an AbstractSet with custom implementations of those methods 382 // that can be overriden easily and efficiently. 383 entries = new NavigableEntrySet(); 384 return entries; 385 } 386 387 /** 388 * Returns the first (lowest) key in the map. 389 * 390 * @return the first key 391 * @throws NoSuchElementException if the map is empty 392 */ 393 public K firstKey() 394 { 395 if (root == nil) 396 throw new NoSuchElementException(); 397 return firstNode().key; 398 } 399 400 /** 401 * Return the value in this TreeMap associated with the supplied key, 402 * or <code>null</code> if the key maps to nothing. NOTE: Since the value 403 * could also be null, you must use containsKey to see if this key 404 * actually maps to something. 405 * 406 * @param key the key for which to fetch an associated value 407 * @return what the key maps to, if present 408 * @throws ClassCastException if key is not comparable to elements in the map 409 * @throws NullPointerException if key is null but the comparator does not 410 * tolerate nulls 411 * @see #put(Object, Object) 412 * @see #containsKey(Object) 413 */ 414 public V get(Object key) 415 { 416 // Exploit fact that nil.value == null. 417 return getNode((K) key).value; 418 } 419 420 /** 421 * Returns a view of this Map including all entries with keys less than 422 * <code>toKey</code>. The returned map is backed by the original, so changes 423 * in one appear in the other. The submap will throw an 424 * {@link IllegalArgumentException} for any attempt to access or add an 425 * element beyond the specified cutoff. The returned map does not include 426 * the endpoint; if you want inclusion, pass the successor element 427 * or call <code>headMap(toKey, true)</code>. This is equivalent to 428 * calling <code>headMap(toKey, false)</code>. 429 * 430 * @param toKey the (exclusive) cutoff point 431 * @return a view of the map less than the cutoff 432 * @throws ClassCastException if <code>toKey</code> is not compatible with 433 * the comparator (or is not Comparable, for natural ordering) 434 * @throws NullPointerException if toKey is null, but the comparator does not 435 * tolerate null elements 436 */ 437 public SortedMap<K, V> headMap(K toKey) 438 { 439 return headMap(toKey, false); 440 } 441 442 /** 443 * Returns a view of this Map including all entries with keys less than 444 * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>. 445 * The returned map is backed by the original, so changes in one appear 446 * in the other. The submap will throw an {@link IllegalArgumentException} 447 * for any attempt to access or add an element beyond the specified cutoff. 448 * 449 * @param toKey the cutoff point 450 * @param inclusive true if the cutoff point should be included. 451 * @return a view of the map less than (or equal to, if <code>inclusive</code> 452 * is true) the cutoff. 453 * @throws ClassCastException if <code>toKey</code> is not compatible with 454 * the comparator (or is not Comparable, for natural ordering) 455 * @throws NullPointerException if toKey is null, but the comparator does not 456 * tolerate null elements 457 */ 458 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) 459 { 460 return new SubMap((K)(Object)nil, inclusive 461 ? successor(getNode(toKey)).key : toKey); 462 } 463 464 /** 465 * Returns a "set view" of this TreeMap's keys. The set is backed by the 466 * TreeMap, so changes in one show up in the other. The set supports 467 * element removal, but not element addition. 468 * 469 * @return a set view of the keys 470 * @see #values() 471 * @see #entrySet() 472 */ 473 public Set<K> keySet() 474 { 475 if (keys == null) 476 // Create an AbstractSet with custom implementations of those methods 477 // that can be overriden easily and efficiently. 478 keys = new KeySet(); 479 return keys; 480 } 481 482 /** 483 * Returns the last (highest) key in the map. 484 * 485 * @return the last key 486 * @throws NoSuchElementException if the map is empty 487 */ 488 public K lastKey() 489 { 490 if (root == nil) 491 throw new NoSuchElementException("empty"); 492 return lastNode().key; 493 } 494 495 /** 496 * Puts the supplied value into the Map, mapped by the supplied key. 497 * The value may be retrieved by any object which <code>equals()</code> 498 * this key. NOTE: Since the prior value could also be null, you must 499 * first use containsKey if you want to see if you are replacing the 500 * key's mapping. 501 * 502 * @param key the key used to locate the value 503 * @param value the value to be stored in the Map 504 * @return the prior mapping of the key, or null if there was none 505 * @throws ClassCastException if key is not comparable to current map keys 506 * @throws NullPointerException if key is null, but the comparator does 507 * not tolerate nulls 508 * @see #get(Object) 509 * @see Object#equals(Object) 510 */ 511 public V put(K key, V value) 512 { 513 Node<K,V> current = root; 514 Node<K,V> parent = nil; 515 int comparison = 0; 516 517 // Find new node's parent. 518 while (current != nil) 519 { 520 parent = current; 521 comparison = compare(key, current.key); 522 if (comparison > 0) 523 current = current.right; 524 else if (comparison < 0) 525 current = current.left; 526 else // Key already in tree. 527 return current.setValue(value); 528 } 529 530 // Set up new node. 531 Node n = new Node(key, value, RED); 532 n.parent = parent; 533 534 // Insert node in tree. 535 modCount++; 536 size++; 537 if (parent == nil) 538 { 539 // Special case inserting into an empty tree. 540 root = n; 541 return null; 542 } 543 if (comparison > 0) 544 parent.right = n; 545 else 546 parent.left = n; 547 548 // Rebalance after insert. 549 insertFixup(n); 550 return null; 551 } 552 553 /** 554 * Copies all elements of the given map into this TreeMap. If this map 555 * already has a mapping for a key, the new mapping replaces the current 556 * one. 557 * 558 * @param m the map to be added 559 * @throws ClassCastException if a key in m is not comparable with keys 560 * in the map 561 * @throws NullPointerException if a key in m is null, and the comparator 562 * does not tolerate nulls 563 */ 564 public void putAll(Map<? extends K, ? extends V> m) 565 { 566 Iterator itr = m.entrySet().iterator(); 567 int pos = m.size(); 568 while (--pos >= 0) 569 { 570 Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next(); 571 put(e.getKey(), e.getValue()); 572 } 573 } 574 575 /** 576 * Removes from the TreeMap and returns the value which is mapped by the 577 * supplied key. If the key maps to nothing, then the TreeMap remains 578 * unchanged, and <code>null</code> is returned. NOTE: Since the value 579 * could also be null, you must use containsKey to see if you are 580 * actually removing a mapping. 581 * 582 * @param key the key used to locate the value to remove 583 * @return whatever the key mapped to, if present 584 * @throws ClassCastException if key is not comparable to current map keys 585 * @throws NullPointerException if key is null, but the comparator does 586 * not tolerate nulls 587 */ 588 public V remove(Object key) 589 { 590 Node<K, V> n = getNode((K)key); 591 if (n == nil) 592 return null; 593 // Note: removeNode can alter the contents of n, so save value now. 594 V result = n.value; 595 removeNode(n); 596 return result; 597 } 598 599 /** 600 * Returns the number of key-value mappings currently in this Map. 601 * 602 * @return the size 603 */ 604 public int size() 605 { 606 return size; 607 } 608 609 /** 610 * Returns a view of this Map including all entries with keys greater or 611 * equal to <code>fromKey</code> and less than <code>toKey</code> (a 612 * half-open interval). The returned map is backed by the original, so 613 * changes in one appear in the other. The submap will throw an 614 * {@link IllegalArgumentException} for any attempt to access or add an 615 * element beyond the specified cutoffs. The returned map includes the low 616 * endpoint but not the high; if you want to reverse this behavior on 617 * either end, pass in the successor element or call 618 * {@link #subMap(K,boolean,K,boolean)}. This call is equivalent to 619 * <code>subMap(fromKey, true, toKey, false)</code>. 620 * 621 * @param fromKey the (inclusive) low cutoff point 622 * @param toKey the (exclusive) high cutoff point 623 * @return a view of the map between the cutoffs 624 * @throws ClassCastException if either cutoff is not compatible with 625 * the comparator (or is not Comparable, for natural ordering) 626 * @throws NullPointerException if fromKey or toKey is null, but the 627 * comparator does not tolerate null elements 628 * @throws IllegalArgumentException if fromKey is greater than toKey 629 */ 630 public SortedMap<K, V> subMap(K fromKey, K toKey) 631 { 632 return subMap(fromKey, true, toKey, false); 633 } 634 635 /** 636 * Returns a view of this Map including all entries with keys greater (or 637 * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and 638 * less than (or equal to, if <code>toInclusive</code> is true) 639 * <code>toKey</code>. The returned map is backed by the original, so 640 * changes in one appear in the other. The submap will throw an 641 * {@link IllegalArgumentException} for any attempt to access or add an 642 * element beyond the specified cutoffs. 643 * 644 * @param fromKey the low cutoff point 645 * @param fromInclusive true if the low cutoff point should be included. 646 * @param toKey the high cutoff point 647 * @param toInclusive true if the high cutoff point should be included. 648 * @return a view of the map for the specified range. 649 * @throws ClassCastException if either cutoff is not compatible with 650 * the comparator (or is not Comparable, for natural ordering) 651 * @throws NullPointerException if fromKey or toKey is null, but the 652 * comparator does not tolerate null elements 653 * @throws IllegalArgumentException if fromKey is greater than toKey 654 */ 655 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, 656 K toKey, boolean toInclusive) 657 { 658 return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, 659 toInclusive ? successor(getNode(toKey)).key : toKey); 660 } 661 662 /** 663 * Returns a view of this Map including all entries with keys greater or 664 * equal to <code>fromKey</code>. The returned map is backed by the 665 * original, so changes in one appear in the other. The submap will throw an 666 * {@link IllegalArgumentException} for any attempt to access or add an 667 * element beyond the specified cutoff. The returned map includes the 668 * endpoint; if you want to exclude it, pass in the successor element. 669 * This is equivalent to calling <code>tailMap(fromKey, true)</code>. 670 * 671 * @param fromKey the (inclusive) low cutoff point 672 * @return a view of the map above the cutoff 673 * @throws ClassCastException if <code>fromKey</code> is not compatible with 674 * the comparator (or is not Comparable, for natural ordering) 675 * @throws NullPointerException if fromKey is null, but the comparator 676 * does not tolerate null elements 677 */ 678 public SortedMap<K, V> tailMap(K fromKey) 679 { 680 return tailMap(fromKey, true); 681 } 682 683 /** 684 * Returns a view of this Map including all entries with keys greater or 685 * equal to <code>fromKey</code>. The returned map is backed by the 686 * original, so changes in one appear in the other. The submap will throw an 687 * {@link IllegalArgumentException} for any attempt to access or add an 688 * element beyond the specified cutoff. The returned map includes the 689 * endpoint; if you want to exclude it, pass in the successor element. 690 * 691 * @param fromKey the low cutoff point 692 * @param inclusive true if the cutoff point should be included. 693 * @return a view of the map above the cutoff 694 * @throws ClassCastException if <code>fromKey</code> is not compatible with 695 * the comparator (or is not Comparable, for natural ordering) 696 * @throws NullPointerException if fromKey is null, but the comparator 697 * does not tolerate null elements 698 */ 699 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) 700 { 701 return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key, 702 (K)(Object)nil); 703 } 704 705 /** 706 * Returns a "collection view" (or "bag view") of this TreeMap's values. 707 * The collection is backed by the TreeMap, so changes in one show up 708 * in the other. The collection supports element removal, but not element 709 * addition. 710 * 711 * @return a bag view of the values 712 * @see #keySet() 713 * @see #entrySet() 714 */ 715 public Collection<V> values() 716 { 717 if (values == null) 718 // We don't bother overriding many of the optional methods, as doing so 719 // wouldn't provide any significant performance advantage. 720 values = new AbstractCollection<V>() 721 { 722 public int size() 723 { 724 return size; 725 } 726 727 public Iterator<V> iterator() 728 { 729 return new TreeIterator(VALUES); 730 } 731 732 public void clear() 733 { 734 TreeMap.this.clear(); 735 } 736 }; 737 return values; 738 } 739 740 /** 741 * Compares two elements by the set comparator, or by natural ordering. 742 * Package visible for use by nested classes. 743 * 744 * @param o1 the first object 745 * @param o2 the second object 746 * @throws ClassCastException if o1 and o2 are not mutually comparable, 747 * or are not Comparable with natural ordering 748 * @throws NullPointerException if o1 or o2 is null with natural ordering 749 */ 750 final int compare(K o1, K o2) 751 { 752 return (comparator == null 753 ? ((Comparable) o1).compareTo(o2) 754 : comparator.compare(o1, o2)); 755 } 756 757 /** 758 * Maintain red-black balance after deleting a node. 759 * 760 * @param node the child of the node just deleted, possibly nil 761 * @param parent the parent of the node just deleted, never nil 762 */ 763 private void deleteFixup(Node<K,V> node, Node<K,V> parent) 764 { 765 // if (parent == nil) 766 // throw new InternalError(); 767 // If a black node has been removed, we need to rebalance to avoid 768 // violating the "same number of black nodes on any path" rule. If 769 // node is red, we can simply recolor it black and all is well. 770 while (node != root && node.color == BLACK) 771 { 772 if (node == parent.left) 773 { 774 // Rebalance left side. 775 Node<K,V> sibling = parent.right; 776 // if (sibling == nil) 777 // throw new InternalError(); 778 if (sibling.color == RED) 779 { 780 // Case 1: Sibling is red. 781 // Recolor sibling and parent, and rotate parent left. 782 sibling.color = BLACK; 783 parent.color = RED; 784 rotateLeft(parent); 785 sibling = parent.right; 786 } 787 788 if (sibling.left.color == BLACK && sibling.right.color == BLACK) 789 { 790 // Case 2: Sibling has no red children. 791 // Recolor sibling, and move to parent. 792 sibling.color = RED; 793 node = parent; 794 parent = parent.parent; 795 } 796 else 797 { 798 if (sibling.right.color == BLACK) 799 { 800 // Case 3: Sibling has red left child. 801 // Recolor sibling and left child, rotate sibling right. 802 sibling.left.color = BLACK; 803 sibling.color = RED; 804 rotateRight(sibling); 805 sibling = parent.right; 806 } 807 // Case 4: Sibling has red right child. Recolor sibling, 808 // right child, and parent, and rotate parent left. 809 sibling.color = parent.color; 810 parent.color = BLACK; 811 sibling.right.color = BLACK; 812 rotateLeft(parent); 813 node = root; // Finished. 814 } 815 } 816 else 817 { 818 // Symmetric "mirror" of left-side case. 819 Node<K,V> sibling = parent.left; 820 // if (sibling == nil) 821 // throw new InternalError(); 822 if (sibling.color == RED) 823 { 824 // Case 1: Sibling is red. 825 // Recolor sibling and parent, and rotate parent right. 826 sibling.color = BLACK; 827 parent.color = RED; 828 rotateRight(parent); 829 sibling = parent.left; 830 } 831 832 if (sibling.right.color == BLACK && sibling.left.color == BLACK) 833 { 834 // Case 2: Sibling has no red children. 835 // Recolor sibling, and move to parent. 836 sibling.color = RED; 837 node = parent; 838 parent = parent.parent; 839 } 840 else 841 { 842 if (sibling.left.color == BLACK) 843 { 844 // Case 3: Sibling has red right child. 845 // Recolor sibling and right child, rotate sibling left. 846 sibling.right.color = BLACK; 847 sibling.color = RED; 848 rotateLeft(sibling); 849 sibling = parent.left; 850 } 851 // Case 4: Sibling has red left child. Recolor sibling, 852 // left child, and parent, and rotate parent right. 853 sibling.color = parent.color; 854 parent.color = BLACK; 855 sibling.left.color = BLACK; 856 rotateRight(parent); 857 node = root; // Finished. 858 } 859 } 860 } 861 node.color = BLACK; 862 } 863 864 /** 865 * Construct a perfectly balanced tree consisting of n "blank" nodes. This 866 * permits a tree to be generated from pre-sorted input in linear time. 867 * 868 * @param count the number of blank nodes, non-negative 869 */ 870 private void fabricateTree(final int count) 871 { 872 if (count == 0) 873 { 874 root = nil; 875 size = 0; 876 return; 877 } 878 879 // We color every row of nodes black, except for the overflow nodes. 880 // I believe that this is the optimal arrangement. We construct the tree 881 // in place by temporarily linking each node to the next node in the row, 882 // then updating those links to the children when working on the next row. 883 884 // Make the root node. 885 root = new Node(null, null, BLACK); 886 size = count; 887 Node row = root; 888 int rowsize; 889 890 // Fill each row that is completely full of nodes. 891 for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) 892 { 893 Node parent = row; 894 Node last = null; 895 for (int i = 0; i < rowsize; i += 2) 896 { 897 Node left = new Node(null, null, BLACK); 898 Node right = new Node(null, null, BLACK); 899 left.parent = parent; 900 left.right = right; 901 right.parent = parent; 902 parent.left = left; 903 Node next = parent.right; 904 parent.right = right; 905 parent = next; 906 if (last != null) 907 last.right = left; 908 last = right; 909 } 910 row = row.left; 911 } 912 913 // Now do the partial final row in red. 914 int overflow = count - rowsize; 915 Node parent = row; 916 int i; 917 for (i = 0; i < overflow; i += 2) 918 { 919 Node left = new Node(null, null, RED); 920 Node right = new Node(null, null, RED); 921 left.parent = parent; 922 right.parent = parent; 923 parent.left = left; 924 Node next = parent.right; 925 parent.right = right; 926 parent = next; 927 } 928 // Add a lone left node if necessary. 929 if (i - overflow == 0) 930 { 931 Node left = new Node(null, null, RED); 932 left.parent = parent; 933 parent.left = left; 934 parent = parent.right; 935 left.parent.right = nil; 936 } 937 // Unlink the remaining nodes of the previous row. 938 while (parent != nil) 939 { 940 Node next = parent.right; 941 parent.right = nil; 942 parent = next; 943 } 944 } 945 946 /** 947 * Returns the first sorted node in the map, or nil if empty. Package 948 * visible for use by nested classes. 949 * 950 * @return the first node 951 */ 952 final Node<K, V> firstNode() 953 { 954 // Exploit fact that nil.left == nil. 955 Node node = root; 956 while (node.left != nil) 957 node = node.left; 958 return node; 959 } 960 961 /** 962 * Return the TreeMap.Node associated with key, or the nil node if no such 963 * node exists in the tree. Package visible for use by nested classes. 964 * 965 * @param key the key to search for 966 * @return the node where the key is found, or nil 967 */ 968 final Node<K, V> getNode(K key) 969 { 970 Node<K,V> current = root; 971 while (current != nil) 972 { 973 int comparison = compare(key, current.key); 974 if (comparison > 0) 975 current = current.right; 976 else if (comparison < 0) 977 current = current.left; 978 else 979 return current; 980 } 981 return current; 982 } 983 984 /** 985 * Find the "highest" node which is < key. If key is nil, return last 986 * node. Package visible for use by nested classes. 987 * 988 * @param key the upper bound, exclusive 989 * @return the previous node 990 */ 991 final Node<K,V> highestLessThan(K key) 992 { 993 return highestLessThan(key, false); 994 } 995 996 /** 997 * Find the "highest" node which is < (or equal to, 998 * if <code>equal</code> is true) key. If key is nil, 999 * return last node. Package visible for use by nested 1000 * classes. 1001 * 1002 * @param key the upper bound, exclusive 1003 * @param equal true if the key should be returned if found. 1004 * @return the previous node 1005 */ 1006 final Node<K,V> highestLessThan(K key, boolean equal) 1007 { 1008 if (key == nil) 1009 return lastNode(); 1010 1011 Node<K,V> last = nil; 1012 Node<K,V> current = root; 1013 int comparison = 0; 1014 1015 while (current != nil) 1016 { 1017 last = current; 1018 comparison = compare(key, current.key); 1019 if (comparison > 0) 1020 current = current.right; 1021 else if (comparison < 0) 1022 current = current.left; 1023 else // Exact match. 1024 return (equal ? last : predecessor(last)); 1025 } 1026 return comparison < 0 ? predecessor(last) : last; 1027 } 1028 1029 /** 1030 * Maintain red-black balance after inserting a new node. 1031 * 1032 * @param n the newly inserted node 1033 */ 1034 private void insertFixup(Node<K,V> n) 1035 { 1036 // Only need to rebalance when parent is a RED node, and while at least 1037 // 2 levels deep into the tree (ie: node has a grandparent). Remember 1038 // that nil.color == BLACK. 1039 while (n.parent.color == RED && n.parent.parent != nil) 1040 { 1041 if (n.parent == n.parent.parent.left) 1042 { 1043 Node uncle = n.parent.parent.right; 1044 // Uncle may be nil, in which case it is BLACK. 1045 if (uncle.color == RED) 1046 { 1047 // Case 1. Uncle is RED: Change colors of parent, uncle, 1048 // and grandparent, and move n to grandparent. 1049 n.parent.color = BLACK; 1050 uncle.color = BLACK; 1051 uncle.parent.color = RED; 1052 n = uncle.parent; 1053 } 1054 else 1055 { 1056 if (n == n.parent.right) 1057 { 1058 // Case 2. Uncle is BLACK and x is right child. 1059 // Move n to parent, and rotate n left. 1060 n = n.parent; 1061 rotateLeft(n); 1062 } 1063 // Case 3. Uncle is BLACK and x is left child. 1064 // Recolor parent, grandparent, and rotate grandparent right. 1065 n.parent.color = BLACK; 1066 n.parent.parent.color = RED; 1067 rotateRight(n.parent.parent); 1068 } 1069 } 1070 else 1071 { 1072 // Mirror image of above code. 1073 Node uncle = n.parent.parent.left; 1074 // Uncle may be nil, in which case it is BLACK. 1075 if (uncle.color == RED) 1076 { 1077 // Case 1. Uncle is RED: Change colors of parent, uncle, 1078 // and grandparent, and move n to grandparent. 1079 n.parent.color = BLACK; 1080 uncle.color = BLACK; 1081 uncle.parent.color = RED; 1082 n = uncle.parent; 1083 } 1084 else 1085 { 1086 if (n == n.parent.left) 1087 { 1088 // Case 2. Uncle is BLACK and x is left child. 1089 // Move n to parent, and rotate n right. 1090 n = n.parent; 1091 rotateRight(n); 1092 } 1093 // Case 3. Uncle is BLACK and x is right child. 1094 // Recolor parent, grandparent, and rotate grandparent left. 1095 n.parent.color = BLACK; 1096 n.parent.parent.color = RED; 1097 rotateLeft(n.parent.parent); 1098 } 1099 } 1100 } 1101 root.color = BLACK; 1102 } 1103 1104 /** 1105 * Returns the last sorted node in the map, or nil if empty. 1106 * 1107 * @return the last node 1108 */ 1109 private Node<K,V> lastNode() 1110 { 1111 // Exploit fact that nil.right == nil. 1112 Node node = root; 1113 while (node.right != nil) 1114 node = node.right; 1115 return node; 1116 } 1117 1118 /** 1119 * Find the "lowest" node which is >= key. If key is nil, return either 1120 * nil or the first node, depending on the parameter first. Package visible 1121 * for use by nested classes. 1122 * 1123 * @param key the lower bound, inclusive 1124 * @param first true to return the first element instead of nil for nil key 1125 * @return the next node 1126 */ 1127 final Node<K,V> lowestGreaterThan(K key, boolean first) 1128 { 1129 return lowestGreaterThan(key, first, true); 1130 } 1131 1132 /** 1133 * Find the "lowest" node which is > (or equal to, if <code>equal</code> 1134 * is true) key. If key is nil, return either nil or the first node, depending 1135 * on the parameter first. Package visible for use by nested classes. 1136 * 1137 * @param key the lower bound, inclusive 1138 * @param first true to return the first element instead of nil for nil key 1139 * @param equal true if the key should be returned if found. 1140 * @return the next node 1141 */ 1142 final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal) 1143 { 1144 if (key == nil) 1145 return first ? firstNode() : nil; 1146 1147 Node<K,V> last = nil; 1148 Node<K,V> current = root; 1149 int comparison = 0; 1150 1151 while (current != nil) 1152 { 1153 last = current; 1154 comparison = compare(key, current.key); 1155 if (comparison > 0) 1156 current = current.right; 1157 else if (comparison < 0) 1158 current = current.left; 1159 else 1160 return (equal ? current : successor(current)); 1161 } 1162 return comparison > 0 ? successor(last) : last; 1163 } 1164 1165 /** 1166 * Return the node preceding the given one, or nil if there isn't one. 1167 * 1168 * @param node the current node, not nil 1169 * @return the prior node in sorted order 1170 */ 1171 private Node<K,V> predecessor(Node<K,V> node) 1172 { 1173 if (node.left != nil) 1174 { 1175 node = node.left; 1176 while (node.right != nil) 1177 node = node.right; 1178 return node; 1179 } 1180 1181 Node parent = node.parent; 1182 // Exploit fact that nil.left == nil and node is non-nil. 1183 while (node == parent.left) 1184 { 1185 node = parent; 1186 parent = node.parent; 1187 } 1188 return parent; 1189 } 1190 1191 /** 1192 * Construct a tree from sorted keys in linear time. Package visible for 1193 * use by TreeSet. 1194 * 1195 * @param s the stream to read from 1196 * @param count the number of keys to read 1197 * @param readValues true to read values, false to insert "" as the value 1198 * @throws ClassNotFoundException if the underlying stream fails 1199 * @throws IOException if the underlying stream fails 1200 * @see #readObject(ObjectInputStream) 1201 * @see TreeSet#readObject(ObjectInputStream) 1202 */ 1203 final void putFromObjStream(ObjectInputStream s, int count, 1204 boolean readValues) 1205 throws IOException, ClassNotFoundException 1206 { 1207 fabricateTree(count); 1208 Node node = firstNode(); 1209 1210 while (--count >= 0) 1211 { 1212 node.key = s.readObject(); 1213 node.value = readValues ? s.readObject() : ""; 1214 node = successor(node); 1215 } 1216 } 1217 1218 /** 1219 * Construct a tree from sorted keys in linear time, with values of "". 1220 * Package visible for use by TreeSet, which uses a value type of String. 1221 * 1222 * @param keys the iterator over the sorted keys 1223 * @param count the number of nodes to insert 1224 * @see TreeSet#TreeSet(SortedSet) 1225 */ 1226 final void putKeysLinear(Iterator<K> keys, int count) 1227 { 1228 fabricateTree(count); 1229 Node<K,V> node = firstNode(); 1230 1231 while (--count >= 0) 1232 { 1233 node.key = keys.next(); 1234 node.value = (V) ""; 1235 node = successor(node); 1236 } 1237 } 1238 1239 /** 1240 * Deserializes this object from the given stream. 1241 * 1242 * @param s the stream to read from 1243 * @throws ClassNotFoundException if the underlying stream fails 1244 * @throws IOException if the underlying stream fails 1245 * @serialData the <i>size</i> (int), followed by key (Object) and value 1246 * (Object) pairs in sorted order 1247 */ 1248 private void readObject(ObjectInputStream s) 1249 throws IOException, ClassNotFoundException 1250 { 1251 s.defaultReadObject(); 1252 int size = s.readInt(); 1253 putFromObjStream(s, size, true); 1254 } 1255 1256 /** 1257 * Remove node from tree. This will increment modCount and decrement size. 1258 * Node must exist in the tree. Package visible for use by nested classes. 1259 * 1260 * @param node the node to remove 1261 */ 1262 final void removeNode(Node<K,V> node) 1263 { 1264 Node<K,V> splice; 1265 Node<K,V> child; 1266 1267 modCount++; 1268 size--; 1269 1270 // Find splice, the node at the position to actually remove from the tree. 1271 if (node.left == nil) 1272 { 1273 // Node to be deleted has 0 or 1 children. 1274 splice = node; 1275 child = node.right; 1276 } 1277 else if (node.right == nil) 1278 { 1279 // Node to be deleted has 1 child. 1280 splice = node; 1281 child = node.left; 1282 } 1283 else 1284 { 1285 // Node has 2 children. Splice is node's predecessor, and we swap 1286 // its contents into node. 1287 splice = node.left; 1288 while (splice.right != nil) 1289 splice = splice.right; 1290 child = splice.left; 1291 node.key = splice.key; 1292 node.value = splice.value; 1293 } 1294 1295 // Unlink splice from the tree. 1296 Node parent = splice.parent; 1297 if (child != nil) 1298 child.parent = parent; 1299 if (parent == nil) 1300 { 1301 // Special case for 0 or 1 node remaining. 1302 root = child; 1303 return; 1304 } 1305 if (splice == parent.left) 1306 parent.left = child; 1307 else 1308 parent.right = child; 1309 1310 if (splice.color == BLACK) 1311 deleteFixup(child, parent); 1312 } 1313 1314 /** 1315 * Rotate node n to the left. 1316 * 1317 * @param node the node to rotate 1318 */ 1319 private void rotateLeft(Node<K,V> node) 1320 { 1321 Node child = node.right; 1322 // if (node == nil || child == nil) 1323 // throw new InternalError(); 1324 1325 // Establish node.right link. 1326 node.right = child.left; 1327 if (child.left != nil) 1328 child.left.parent = node; 1329 1330 // Establish child->parent link. 1331 child.parent = node.parent; 1332 if (node.parent != nil) 1333 { 1334 if (node == node.parent.left) 1335 node.parent.left = child; 1336 else 1337 node.parent.right = child; 1338 } 1339 else 1340 root = child; 1341 1342 // Link n and child. 1343 child.left = node; 1344 node.parent = child; 1345 } 1346 1347 /** 1348 * Rotate node n to the right. 1349 * 1350 * @param node the node to rotate 1351 */ 1352 private void rotateRight(Node<K,V> node) 1353 { 1354 Node child = node.left; 1355 // if (node == nil || child == nil) 1356 // throw new InternalError(); 1357 1358 // Establish node.left link. 1359 node.left = child.right; 1360 if (child.right != nil) 1361 child.right.parent = node; 1362 1363 // Establish child->parent link. 1364 child.parent = node.parent; 1365 if (node.parent != nil) 1366 { 1367 if (node == node.parent.right) 1368 node.parent.right = child; 1369 else 1370 node.parent.left = child; 1371 } 1372 else 1373 root = child; 1374 1375 // Link n and child. 1376 child.right = node; 1377 node.parent = child; 1378 } 1379 1380 /** 1381 * Return the node following the given one, or nil if there isn't one. 1382 * Package visible for use by nested classes. 1383 * 1384 * @param node the current node, not nil 1385 * @return the next node in sorted order 1386 */ 1387 final Node<K,V> successor(Node<K,V> node) 1388 { 1389 if (node.right != nil) 1390 { 1391 node = node.right; 1392 while (node.left != nil) 1393 node = node.left; 1394 return node; 1395 } 1396 1397 Node<K,V> parent = node.parent; 1398 // Exploit fact that nil.right == nil and node is non-nil. 1399 while (node == parent.right) 1400 { 1401 node = parent; 1402 parent = parent.parent; 1403 } 1404 return parent; 1405 } 1406 1407 /** 1408 * Serializes this object to the given stream. 1409 * 1410 * @param s the stream to write to 1411 * @throws IOException if the underlying stream fails 1412 * @serialData the <i>size</i> (int), followed by key (Object) and value 1413 * (Object) pairs in sorted order 1414 */ 1415 private void writeObject(ObjectOutputStream s) throws IOException 1416 { 1417 s.defaultWriteObject(); 1418 1419 Node node = firstNode(); 1420 s.writeInt(size); 1421 while (node != nil) 1422 { 1423 s.writeObject(node.key); 1424 s.writeObject(node.value); 1425 node = successor(node); 1426 } 1427 } 1428 1429 /** 1430 * Iterate over TreeMap's entries. This implementation is parameterized 1431 * to give a sequential view of keys, values, or entries. 1432 * 1433 * @author Eric Blake (ebb9@email.byu.edu) 1434 */ 1435 private final class TreeIterator implements Iterator 1436 { 1437 /** 1438 * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 1439 * or {@link #ENTRIES}. 1440 */ 1441 private final int type; 1442 /** The number of modifications to the backing Map that we know about. */ 1443 private int knownMod = modCount; 1444 /** The last Entry returned by a next() call. */ 1445 private Node last; 1446 /** The next entry that should be returned by next(). */ 1447 private Node next; 1448 /** 1449 * The last node visible to this iterator. This is used when iterating 1450 * on a SubMap. 1451 */ 1452 private final Node max; 1453 1454 /** 1455 * Construct a new TreeIterator with the supplied type. 1456 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 1457 */ 1458 TreeIterator(int type) 1459 { 1460 this(type, firstNode(), nil); 1461 } 1462 1463 /** 1464 * Construct a new TreeIterator with the supplied type. Iteration will 1465 * be from "first" (inclusive) to "max" (exclusive). 1466 * 1467 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 1468 * @param first where to start iteration, nil for empty iterator 1469 * @param max the cutoff for iteration, nil for all remaining nodes 1470 */ 1471 TreeIterator(int type, Node first, Node max) 1472 { 1473 this.type = type; 1474 this.next = first; 1475 this.max = max; 1476 } 1477 1478 /** 1479 * Returns true if the Iterator has more elements. 1480 * @return true if there are more elements 1481 */ 1482 public boolean hasNext() 1483 { 1484 return next != max; 1485 } 1486 1487 /** 1488 * Returns the next element in the Iterator's sequential view. 1489 * @return the next element 1490 * @throws ConcurrentModificationException if the TreeMap was modified 1491 * @throws NoSuchElementException if there is none 1492 */ 1493 public Object next() 1494 { 1495 if (knownMod != modCount) 1496 throw new ConcurrentModificationException(); 1497 if (next == max) 1498 throw new NoSuchElementException(); 1499 last = next; 1500 next = successor(last); 1501 1502 if (type == VALUES) 1503 return last.value; 1504 else if (type == KEYS) 1505 return last.key; 1506 return last; 1507 } 1508 1509 /** 1510 * Removes from the backing TreeMap the last element which was fetched 1511 * with the <code>next()</code> method. 1512 * @throws ConcurrentModificationException if the TreeMap was modified 1513 * @throws IllegalStateException if called when there is no last element 1514 */ 1515 public void remove() 1516 { 1517 if (last == null) 1518 throw new IllegalStateException(); 1519 if (knownMod != modCount) 1520 throw new ConcurrentModificationException(); 1521 1522 removeNode(last); 1523 last = null; 1524 knownMod++; 1525 } 1526 } // class TreeIterator 1527 1528 /** 1529 * Implementation of {@link #subMap(Object, Object)} and other map 1530 * ranges. This class provides a view of a portion of the original backing 1531 * map, and throws {@link IllegalArgumentException} for attempts to 1532 * access beyond that range. 1533 * 1534 * @author Eric Blake (ebb9@email.byu.edu) 1535 */ 1536 private final class SubMap 1537 extends AbstractMap<K,V> 1538 implements NavigableMap<K,V> 1539 { 1540 /** 1541 * The lower range of this view, inclusive, or nil for unbounded. 1542 * Package visible for use by nested classes. 1543 */ 1544 final K minKey; 1545 1546 /** 1547 * The upper range of this view, exclusive, or nil for unbounded. 1548 * Package visible for use by nested classes. 1549 */ 1550 final K maxKey; 1551 1552 /** 1553 * The cache for {@link #entrySet()}. 1554 */ 1555 private Set<Map.Entry<K,V>> entries; 1556 1557 /** 1558 * The cache for {@link #descendingMap()}. 1559 */ 1560 private NavigableMap<K,V> descendingMap; 1561 1562 /** 1563 * The cache for {@link #navigableKeySet()}. 1564 */ 1565 private NavigableSet<K> nKeys; 1566 1567 /** 1568 * Create a SubMap representing the elements between minKey (inclusive) 1569 * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound 1570 * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap). 1571 * 1572 * @param minKey the lower bound 1573 * @param maxKey the upper bound 1574 * @throws IllegalArgumentException if minKey > maxKey 1575 */ 1576 SubMap(K minKey, K maxKey) 1577 { 1578 if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0) 1579 throw new IllegalArgumentException("fromKey > toKey"); 1580 this.minKey = minKey; 1581 this.maxKey = maxKey; 1582 } 1583 1584 /** 1585 * Check if "key" is in within the range bounds for this SubMap. The 1586 * lower ("from") SubMap range is inclusive, and the upper ("to") bound 1587 * is exclusive. Package visible for use by nested classes. 1588 * 1589 * @param key the key to check 1590 * @return true if the key is in range 1591 */ 1592 boolean keyInRange(K key) 1593 { 1594 return ((minKey == nil || compare(key, minKey) >= 0) 1595 && (maxKey == nil || compare(key, maxKey) < 0)); 1596 } 1597 1598 public Entry<K,V> ceilingEntry(K key) 1599 { 1600 Entry<K,V> n = TreeMap.this.ceilingEntry(key); 1601 if (n != null && keyInRange(n.getKey())) 1602 return n; 1603 return null; 1604 } 1605 1606 public K ceilingKey(K key) 1607 { 1608 K found = TreeMap.this.ceilingKey(key); 1609 if (keyInRange(found)) 1610 return found; 1611 else 1612 return null; 1613 } 1614 1615 public NavigableSet<K> descendingKeySet() 1616 { 1617 return descendingMap().navigableKeySet(); 1618 } 1619 1620 public NavigableMap<K,V> descendingMap() 1621 { 1622 if (descendingMap == null) 1623 descendingMap = new DescendingMap(this); 1624 return descendingMap; 1625 } 1626 1627 public void clear() 1628 { 1629 Node next = lowestGreaterThan(minKey, true); 1630 Node max = lowestGreaterThan(maxKey, false); 1631 while (next != max) 1632 { 1633 Node current = next; 1634 next = successor(current); 1635 removeNode(current); 1636 } 1637 } 1638 1639 public Comparator<? super K> comparator() 1640 { 1641 return comparator; 1642 } 1643 1644 public boolean containsKey(Object key) 1645 { 1646 return keyInRange((K) key) && TreeMap.this.containsKey(key); 1647 } 1648 1649 public boolean containsValue(Object value) 1650 { 1651 Node node = lowestGreaterThan(minKey, true); 1652 Node max = lowestGreaterThan(maxKey, false); 1653 while (node != max) 1654 { 1655 if (equals(value, node.getValue())) 1656 return true; 1657 node = successor(node); 1658 } 1659 return false; 1660 } 1661 1662 public Set<Map.Entry<K,V>> entrySet() 1663 { 1664 if (entries == null) 1665 // Create an AbstractSet with custom implementations of those methods 1666 // that can be overriden easily and efficiently. 1667 entries = new SubMap.NavigableEntrySet(); 1668 return entries; 1669 } 1670 1671 public Entry<K,V> firstEntry() 1672 { 1673 Node<K,V> node = lowestGreaterThan(minKey, true); 1674 if (node == nil || ! keyInRange(node.key)) 1675 return null; 1676 return node; 1677 } 1678 1679 public K firstKey() 1680 { 1681 Entry<K,V> e = firstEntry(); 1682 if (e == null) 1683 throw new NoSuchElementException(); 1684 return e.getKey(); 1685 } 1686 1687 public Entry<K,V> floorEntry(K key) 1688 { 1689 Entry<K,V> n = TreeMap.this.floorEntry(key); 1690 if (n != null && keyInRange(n.getKey())) 1691 return n; 1692 return null; 1693 } 1694 1695 public K floorKey(K key) 1696 { 1697 K found = TreeMap.this.floorKey(key); 1698 if (keyInRange(found)) 1699 return found; 1700 else 1701 return null; 1702 } 1703 1704 public V get(Object key) 1705 { 1706 if (keyInRange((K) key)) 1707 return TreeMap.this.get(key); 1708 return null; 1709 } 1710 1711 public SortedMap<K,V> headMap(K toKey) 1712 { 1713 return headMap(toKey, false); 1714 } 1715 1716 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) 1717 { 1718 if (!keyInRange(toKey)) 1719 throw new IllegalArgumentException("Key outside submap range"); 1720 return new SubMap(minKey, (inclusive ? 1721 successor(getNode(toKey)).key : toKey)); 1722 } 1723 1724 public Set<K> keySet() 1725 { 1726 if (this.keys == null) 1727 // Create an AbstractSet with custom implementations of those methods 1728 // that can be overriden easily and efficiently. 1729 this.keys = new SubMap.KeySet(); 1730 return this.keys; 1731 } 1732 1733 public Entry<K,V> higherEntry(K key) 1734 { 1735 Entry<K,V> n = TreeMap.this.higherEntry(key); 1736 if (n != null && keyInRange(n.getKey())) 1737 return n; 1738 return null; 1739 } 1740 1741 public K higherKey(K key) 1742 { 1743 K found = TreeMap.this.higherKey(key); 1744 if (keyInRange(found)) 1745 return found; 1746 else 1747 return null; 1748 } 1749 1750 public Entry<K,V> lastEntry() 1751 { 1752 return lowerEntry(maxKey); 1753 } 1754 1755 public K lastKey() 1756 { 1757 Entry<K,V> e = lastEntry(); 1758 if (e == null) 1759 throw new NoSuchElementException(); 1760 return e.getKey(); 1761 } 1762 1763 public Entry<K,V> lowerEntry(K key) 1764 { 1765 Entry<K,V> n = TreeMap.this.lowerEntry(key); 1766 if (n != null && keyInRange(n.getKey())) 1767 return n; 1768 return null; 1769 } 1770 1771 public K lowerKey(K key) 1772 { 1773 K found = TreeMap.this.lowerKey(key); 1774 if (keyInRange(found)) 1775 return found; 1776 else 1777 return null; 1778 } 1779 1780 public NavigableSet<K> navigableKeySet() 1781 { 1782 if (this.nKeys == null) 1783 // Create an AbstractSet with custom implementations of those methods 1784 // that can be overriden easily and efficiently. 1785 this.nKeys = new SubMap.NavigableKeySet(); 1786 return this.nKeys; 1787 } 1788 1789 public Entry<K,V> pollFirstEntry() 1790 { 1791 Entry<K,V> e = firstEntry(); 1792 if (e != null) 1793 removeNode((Node<K,V>) e); 1794 return e; 1795 } 1796 1797 public Entry<K,V> pollLastEntry() 1798 { 1799 Entry<K,V> e = lastEntry(); 1800 if (e != null) 1801 removeNode((Node<K,V>) e); 1802 return e; 1803 } 1804 1805 public V put(K key, V value) 1806 { 1807 if (! keyInRange(key)) 1808 throw new IllegalArgumentException("Key outside range"); 1809 return TreeMap.this.put(key, value); 1810 } 1811 1812 public V remove(Object key) 1813 { 1814 if (keyInRange((K)key)) 1815 return TreeMap.this.remove(key); 1816 return null; 1817 } 1818 1819 public int size() 1820 { 1821 Node node = lowestGreaterThan(minKey, true); 1822 Node max = lowestGreaterThan(maxKey, false); 1823 int count = 0; 1824 while (node != max) 1825 { 1826 count++; 1827 node = successor(node); 1828 } 1829 return count; 1830 } 1831 1832 public SortedMap<K,V> subMap(K fromKey, K toKey) 1833 { 1834 return subMap(fromKey, true, toKey, false); 1835 } 1836 1837 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 1838 K toKey, boolean toInclusive) 1839 { 1840 if (! keyInRange(fromKey) || ! keyInRange(toKey)) 1841 throw new IllegalArgumentException("key outside range"); 1842 return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, 1843 toInclusive ? successor(getNode(toKey)).key : toKey); 1844 } 1845 1846 public SortedMap<K, V> tailMap(K fromKey) 1847 { 1848 return tailMap(fromKey, true); 1849 } 1850 1851 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) 1852 { 1853 if (! keyInRange(fromKey)) 1854 throw new IllegalArgumentException("key outside range"); 1855 return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key, 1856 maxKey); 1857 } 1858 1859 public Collection<V> values() 1860 { 1861 if (this.values == null) 1862 // Create an AbstractCollection with custom implementations of those 1863 // methods that can be overriden easily and efficiently. 1864 this.values = new AbstractCollection() 1865 { 1866 public int size() 1867 { 1868 return SubMap.this.size(); 1869 } 1870 1871 public Iterator<V> iterator() 1872 { 1873 Node first = lowestGreaterThan(minKey, true); 1874 Node max = lowestGreaterThan(maxKey, false); 1875 return new TreeIterator(VALUES, first, max); 1876 } 1877 1878 public void clear() 1879 { 1880 SubMap.this.clear(); 1881 } 1882 }; 1883 return this.values; 1884 } 1885 1886 private class KeySet 1887 extends AbstractSet<K> 1888 { 1889 public int size() 1890 { 1891 return SubMap.this.size(); 1892 } 1893 1894 public Iterator<K> iterator() 1895 { 1896 Node first = lowestGreaterThan(minKey, true); 1897 Node max = lowestGreaterThan(maxKey, false); 1898 return new TreeIterator(KEYS, first, max); 1899 } 1900 1901 public void clear() 1902 { 1903 SubMap.this.clear(); 1904 } 1905 1906 public boolean contains(Object o) 1907 { 1908 if (! keyInRange((K) o)) 1909 return false; 1910 return getNode((K) o) != nil; 1911 } 1912 1913 public boolean remove(Object o) 1914 { 1915 if (! keyInRange((K) o)) 1916 return false; 1917 Node n = getNode((K) o); 1918 if (n != nil) 1919 { 1920 removeNode(n); 1921 return true; 1922 } 1923 return false; 1924 } 1925 1926 } // class SubMap.KeySet 1927 1928 private final class NavigableKeySet 1929 extends KeySet 1930 implements NavigableSet<K> 1931 { 1932 1933 public K ceiling(K k) 1934 { 1935 return SubMap.this.ceilingKey(k); 1936 } 1937 1938 public Comparator<? super K> comparator() 1939 { 1940 return comparator; 1941 } 1942 1943 public Iterator<K> descendingIterator() 1944 { 1945 return descendingSet().iterator(); 1946 } 1947 1948 public NavigableSet<K> descendingSet() 1949 { 1950 return new DescendingSet(this); 1951 } 1952 1953 public K first() 1954 { 1955 return SubMap.this.firstKey(); 1956 } 1957 1958 public K floor(K k) 1959 { 1960 return SubMap.this.floorKey(k); 1961 } 1962 1963 public SortedSet<K> headSet(K to) 1964 { 1965 return headSet(to, false); 1966 } 1967 1968 public NavigableSet<K> headSet(K to, boolean inclusive) 1969 { 1970 return SubMap.this.headMap(to, inclusive).navigableKeySet(); 1971 } 1972 1973 public K higher(K k) 1974 { 1975 return SubMap.this.higherKey(k); 1976 } 1977 1978 public K last() 1979 { 1980 return SubMap.this.lastKey(); 1981 } 1982 1983 public K lower(K k) 1984 { 1985 return SubMap.this.lowerKey(k); 1986 } 1987 1988 public K pollFirst() 1989 { 1990 return SubMap.this.pollFirstEntry().getKey(); 1991 } 1992 1993 public K pollLast() 1994 { 1995 return SubMap.this.pollLastEntry().getKey(); 1996 } 1997 1998 public SortedSet<K> subSet(K from, K to) 1999 { 2000 return subSet(from, true, to, false); 2001 } 2002 2003 public NavigableSet<K> subSet(K from, boolean fromInclusive, 2004 K to, boolean toInclusive) 2005 { 2006 return SubMap.this.subMap(from, fromInclusive, 2007 to, toInclusive).navigableKeySet(); 2008 } 2009 2010 public SortedSet<K> tailSet(K from) 2011 { 2012 return tailSet(from, true); 2013 } 2014 2015 public NavigableSet<K> tailSet(K from, boolean inclusive) 2016 { 2017 return SubMap.this.tailMap(from, inclusive).navigableKeySet(); 2018 } 2019 2020 } // class SubMap.NavigableKeySet 2021 2022 /** 2023 * Implementation of {@link #entrySet()}. 2024 */ 2025 private class EntrySet 2026 extends AbstractSet<Entry<K,V>> 2027 { 2028 2029 public int size() 2030 { 2031 return SubMap.this.size(); 2032 } 2033 2034 public Iterator<Map.Entry<K,V>> iterator() 2035 { 2036 Node first = lowestGreaterThan(minKey, true); 2037 Node max = lowestGreaterThan(maxKey, false); 2038 return new TreeIterator(ENTRIES, first, max); 2039 } 2040 2041 public void clear() 2042 { 2043 SubMap.this.clear(); 2044 } 2045 2046 public boolean contains(Object o) 2047 { 2048 if (! (o instanceof Map.Entry)) 2049 return false; 2050 Map.Entry<K,V> me = (Map.Entry<K,V>) o; 2051 K key = me.getKey(); 2052 if (! keyInRange(key)) 2053 return false; 2054 Node<K,V> n = getNode(key); 2055 return n != nil && AbstractSet.equals(me.getValue(), n.value); 2056 } 2057 2058 public boolean remove(Object o) 2059 { 2060 if (! (o instanceof Map.Entry)) 2061 return false; 2062 Map.Entry<K,V> me = (Map.Entry<K,V>) o; 2063 K key = me.getKey(); 2064 if (! keyInRange(key)) 2065 return false; 2066 Node<K,V> n = getNode(key); 2067 if (n != nil && AbstractSet.equals(me.getValue(), n.value)) 2068 { 2069 removeNode(n); 2070 return true; 2071 } 2072 return false; 2073 } 2074 } // class SubMap.EntrySet 2075 2076 private final class NavigableEntrySet 2077 extends EntrySet 2078 implements NavigableSet<Entry<K,V>> 2079 { 2080 2081 public Entry<K,V> ceiling(Entry<K,V> e) 2082 { 2083 return SubMap.this.ceilingEntry(e.getKey()); 2084 } 2085 2086 public Comparator<? super Entry<K,V>> comparator() 2087 { 2088 return new Comparator<Entry<K,V>>() 2089 { 2090 public int compare(Entry<K,V> t1, Entry<K,V> t2) 2091 { 2092 return comparator.compare(t1.getKey(), t2.getKey()); 2093 } 2094 }; 2095 } 2096 2097 public Iterator<Entry<K,V>> descendingIterator() 2098 { 2099 return descendingSet().iterator(); 2100 } 2101 2102 public NavigableSet<Entry<K,V>> descendingSet() 2103 { 2104 return new DescendingSet(this); 2105 } 2106 2107 public Entry<K,V> first() 2108 { 2109 return SubMap.this.firstEntry(); 2110 } 2111 2112 public Entry<K,V> floor(Entry<K,V> e) 2113 { 2114 return SubMap.this.floorEntry(e.getKey()); 2115 } 2116 2117 public SortedSet<Entry<K,V>> headSet(Entry<K,V> to) 2118 { 2119 return headSet(to, false); 2120 } 2121 2122 public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive) 2123 { 2124 return (NavigableSet<Entry<K,V>>) 2125 SubMap.this.headMap(to.getKey(), inclusive).entrySet(); 2126 } 2127 2128 public Entry<K,V> higher(Entry<K,V> e) 2129 { 2130 return SubMap.this.higherEntry(e.getKey()); 2131 } 2132 2133 public Entry<K,V> last() 2134 { 2135 return SubMap.this.lastEntry(); 2136 } 2137 2138 public Entry<K,V> lower(Entry<K,V> e) 2139 { 2140 return SubMap.this.lowerEntry(e.getKey()); 2141 } 2142 2143 public Entry<K,V> pollFirst() 2144 { 2145 return SubMap.this.pollFirstEntry(); 2146 } 2147 2148 public Entry<K,V> pollLast() 2149 { 2150 return SubMap.this.pollLastEntry(); 2151 } 2152 2153 public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to) 2154 { 2155 return subSet(from, true, to, false); 2156 } 2157 2158 public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive, 2159 Entry<K,V> to, boolean toInclusive) 2160 { 2161 return (NavigableSet<Entry<K,V>>) 2162 SubMap.this.subMap(from.getKey(), fromInclusive, 2163 to.getKey(), toInclusive).entrySet(); 2164 } 2165 2166 public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from) 2167 { 2168 return tailSet(from, true); 2169 } 2170 2171 public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive) 2172 { 2173 return (NavigableSet<Entry<K,V>>) 2174 SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet(); 2175 } 2176 2177 } // class SubMap.NavigableEntrySet 2178 2179 } // class SubMap 2180 2181 /** 2182 * Returns the entry associated with the least or lowest key 2183 * that is greater than or equal to the specified key, or 2184 * <code>null</code> if there is no such key. 2185 * 2186 * @param key the key relative to the returned entry. 2187 * @return the entry with the least key greater than or equal 2188 * to the given key, or <code>null</code> if there is 2189 * no such key. 2190 * @throws ClassCastException if the specified key can not 2191 * be compared with those in the map. 2192 * @throws NullPointerException if the key is <code>null</code> 2193 * and this map either uses natural 2194 * ordering or a comparator that does 2195 * not permit null keys. 2196 * @since 1.6 2197 */ 2198 public Entry<K,V> ceilingEntry(K key) 2199 { 2200 Node<K,V> n = lowestGreaterThan(key, false); 2201 return (n == nil) ? null : n; 2202 } 2203 2204 /** 2205 * Returns the the least or lowest key that is greater than 2206 * or equal to the specified key, or <code>null</code> if 2207 * there is no such key. 2208 * 2209 * @param key the key relative to the returned entry. 2210 * @return the least key greater than or equal to the given key, 2211 * or <code>null</code> if there is no such key. 2212 * @throws ClassCastException if the specified key can not 2213 * be compared with those in the map. 2214 * @throws NullPointerException if the key is <code>null</code> 2215 * and this map either uses natural 2216 * ordering or a comparator that does 2217 * not permit null keys. 2218 * @since 1.6 2219 */ 2220 public K ceilingKey(K key) 2221 { 2222 Entry<K,V> e = ceilingEntry(key); 2223 return (e == null) ? null : e.getKey(); 2224 } 2225 2226 /** 2227 * Returns a reverse ordered {@link NavigableSet} view of this 2228 * map's keys. The set is backed by the {@link TreeMap}, so changes 2229 * in one show up in the other. The set supports element removal, 2230 * but not element addition. 2231 * 2232 * @return a reverse ordered set view of the keys. 2233 * @since 1.6 2234 * @see #descendingMap() 2235 */ 2236 public NavigableSet<K> descendingKeySet() 2237 { 2238 return descendingMap().navigableKeySet(); 2239 } 2240 2241 /** 2242 * Returns a view of the map in reverse order. The descending map 2243 * is backed by the original map, so that changes affect both maps. 2244 * Any changes occurring to either map while an iteration is taking 2245 * place (with the exception of a {@link Iterator#remove()} operation) 2246 * result in undefined behaviour from the iteration. The ordering 2247 * of the descending map is the same as for a map with a 2248 * {@link Comparator} given by {@link Collections#reverseOrder()}, 2249 * and calling {@link #descendingMap()} on the descending map itself 2250 * results in a view equivalent to the original map. 2251 * 2252 * @return a reverse order view of the map. 2253 * @since 1.6 2254 */ 2255 public NavigableMap<K,V> descendingMap() 2256 { 2257 if (descendingMap == null) 2258 descendingMap = new DescendingMap<K,V>(this); 2259 return descendingMap; 2260 } 2261 2262 /** 2263 * Returns the entry associated with the least or lowest key 2264 * in the map, or <code>null</code> if the map is empty. 2265 * 2266 * @return the lowest entry, or <code>null</code> if the map 2267 * is empty. 2268 * @since 1.6 2269 */ 2270 public Entry<K,V> firstEntry() 2271 { 2272 Node<K,V> n = firstNode(); 2273 return (n == nil) ? null : n; 2274 } 2275 2276 /** 2277 * Returns the entry associated with the greatest or highest key 2278 * that is less than or equal to the specified key, or 2279 * <code>null</code> if there is no such key. 2280 * 2281 * @param key the key relative to the returned entry. 2282 * @return the entry with the greatest key less than or equal 2283 * to the given key, or <code>null</code> if there is 2284 * no such key. 2285 * @throws ClassCastException if the specified key can not 2286 * be compared with those in the map. 2287 * @throws NullPointerException if the key is <code>null</code> 2288 * and this map either uses natural 2289 * ordering or a comparator that does 2290 * not permit null keys. 2291 * @since 1.6 2292 */ 2293 public Entry<K,V> floorEntry(K key) 2294 { 2295 Node<K,V> n = highestLessThan(key, true); 2296 return (n == nil) ? null : n; 2297 } 2298 2299 /** 2300 * Returns the the greatest or highest key that is less than 2301 * or equal to the specified key, or <code>null</code> if 2302 * there is no such key. 2303 * 2304 * @param key the key relative to the returned entry. 2305 * @return the greatest key less than or equal to the given key, 2306 * or <code>null</code> if there is no such key. 2307 * @throws ClassCastException if the specified key can not 2308 * be compared with those in the map. 2309 * @throws NullPointerException if the key is <code>null</code> 2310 * and this map either uses natural 2311 * ordering or a comparator that does 2312 * not permit null keys. 2313 * @since 1.6 2314 */ 2315 public K floorKey(K key) 2316 { 2317 Entry<K,V> e = floorEntry(key); 2318 return (e == null) ? null : e.getKey(); 2319 } 2320 2321 /** 2322 * Returns the entry associated with the least or lowest key 2323 * that is strictly greater than the specified key, or 2324 * <code>null</code> if there is no such key. 2325 * 2326 * @param key the key relative to the returned entry. 2327 * @return the entry with the least key greater than 2328 * the given key, or <code>null</code> if there is 2329 * no such key. 2330 * @throws ClassCastException if the specified key can not 2331 * be compared with those in the map. 2332 * @throws NullPointerException if the key is <code>null</code> 2333 * and this map either uses natural 2334 * ordering or a comparator that does 2335 * not permit null keys. 2336 * @since 1.6 2337 */ 2338 public Entry<K,V> higherEntry(K key) 2339 { 2340 Node<K,V> n = lowestGreaterThan(key, false, false); 2341 return (n == nil) ? null : n; 2342 } 2343 2344 /** 2345 * Returns the the least or lowest key that is strictly 2346 * greater than the specified key, or <code>null</code> if 2347 * there is no such key. 2348 * 2349 * @param key the key relative to the returned entry. 2350 * @return the least key greater than the given key, 2351 * or <code>null</code> if there is no such key. 2352 * @throws ClassCastException if the specified key can not 2353 * be compared with those in the map. 2354 * @throws NullPointerException if the key is <code>null</code> 2355 * and this map either uses natural 2356 * ordering or a comparator that does 2357 * not permit null keys. 2358 * @since 1.6 2359 */ 2360 public K higherKey(K key) 2361 { 2362 Entry<K,V> e = higherEntry(key); 2363 return (e == null) ? null : e.getKey(); 2364 } 2365 2366 /** 2367 * Returns the entry associated with the greatest or highest key 2368 * in the map, or <code>null</code> if the map is empty. 2369 * 2370 * @return the highest entry, or <code>null</code> if the map 2371 * is empty. 2372 * @since 1.6 2373 */ 2374 public Entry<K,V> lastEntry() 2375 { 2376 Node<K,V> n = lastNode(); 2377 return (n == nil) ? null : n; 2378 } 2379 2380 /** 2381 * Returns the entry associated with the greatest or highest key 2382 * that is strictly less than the specified key, or 2383 * <code>null</code> if there is no such key. 2384 * 2385 * @param key the key relative to the returned entry. 2386 * @return the entry with the greatest key less than 2387 * the given key, or <code>null</code> if there is 2388 * no such key. 2389 * @throws ClassCastException if the specified key can not 2390 * be compared with those in the map. 2391 * @throws NullPointerException if the key is <code>null</code> 2392 * and this map either uses natural 2393 * ordering or a comparator that does 2394 * not permit null keys. 2395 * @since 1.6 2396 */ 2397 public Entry<K,V> lowerEntry(K key) 2398 { 2399 Node<K,V> n = highestLessThan(key); 2400 return (n == nil) ? null : n; 2401 } 2402 2403 /** 2404 * Returns the the greatest or highest key that is strictly 2405 * less than the specified key, or <code>null</code> if 2406 * there is no such key. 2407 * 2408 * @param key the key relative to the returned entry. 2409 * @return the greatest key less than the given key, 2410 * or <code>null</code> if there is no such key. 2411 * @throws ClassCastException if the specified key can not 2412 * be compared with those in the map. 2413 * @throws NullPointerException if the key is <code>null</code> 2414 * and this map either uses natural 2415 * ordering or a comparator that does 2416 * not permit null keys. 2417 * @since 1.6 2418 */ 2419 public K lowerKey(K key) 2420 { 2421 Entry<K,V> e = lowerEntry(key); 2422 return (e == null) ? null : e.getKey(); 2423 } 2424 2425 /** 2426 * Returns a {@link NavigableSet} view of this map's keys. The set is 2427 * backed by the {@link TreeMap}, so changes in one show up in the other. 2428 * Any changes occurring to either while an iteration is taking 2429 * place (with the exception of a {@link Iterator#remove()} operation) 2430 * result in undefined behaviour from the iteration. The ordering 2431 * The set supports element removal, but not element addition. 2432 * 2433 * @return a {@link NavigableSet} view of the keys. 2434 * @since 1.6 2435 */ 2436 public NavigableSet<K> navigableKeySet() 2437 { 2438 if (nKeys == null) 2439 nKeys = new NavigableKeySet(); 2440 return nKeys; 2441 } 2442 2443 /** 2444 * Removes and returns the entry associated with the least 2445 * or lowest key in the map, or <code>null</code> if the map 2446 * is empty. 2447 * 2448 * @return the removed first entry, or <code>null</code> if the 2449 * map is empty. 2450 * @since 1.6 2451 */ 2452 public Entry<K,V> pollFirstEntry() 2453 { 2454 Entry<K,V> e = firstEntry(); 2455 if (e != null) 2456 removeNode((Node<K,V>)e); 2457 return e; 2458 } 2459 2460 /** 2461 * Removes and returns the entry associated with the greatest 2462 * or highest key in the map, or <code>null</code> if the map 2463 * is empty. 2464 * 2465 * @return the removed last entry, or <code>null</code> if the 2466 * map is empty. 2467 * @since 1.6 2468 */ 2469 public Entry<K,V> pollLastEntry() 2470 { 2471 Entry<K,V> e = lastEntry(); 2472 if (e != null) 2473 removeNode((Node<K,V>)e); 2474 return e; 2475 } 2476 2477 /** 2478 * Implementation of {@link #descendingMap()} and associated 2479 * derivatives. This class provides a view of the 2480 * original backing map in reverse order, and throws 2481 * {@link IllegalArgumentException} for attempts to 2482 * access beyond that range. 2483 * 2484 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 2485 */ 2486 private static final class DescendingMap<DK,DV> 2487 implements NavigableMap<DK,DV> 2488 { 2489 2490 /** 2491 * The cache for {@link #entrySet()}. 2492 */ 2493 private Set<Map.Entry<DK,DV>> entries; 2494 2495 /** 2496 * The cache for {@link #keySet()}. 2497 */ 2498 private Set<DK> keys; 2499 2500 /** 2501 * The cache for {@link #navigableKeySet()}. 2502 */ 2503 private NavigableSet<DK> nKeys; 2504 2505 /** 2506 * The cache for {@link #values()}. 2507 */ 2508 private Collection<DV> values; 2509 2510 /** 2511 * The backing {@link NavigableMap}. 2512 */ 2513 private NavigableMap<DK,DV> map; 2514 2515 /** 2516 * Create a {@link DescendingMap} around the specified 2517 * map. 2518 * 2519 * @param map the map to wrap. 2520 */ 2521 public DescendingMap(NavigableMap<DK,DV> map) 2522 { 2523 this.map = map; 2524 } 2525 2526 public Map.Entry<DK,DV> ceilingEntry(DK key) 2527 { 2528 return map.floorEntry(key); 2529 } 2530 2531 public DK ceilingKey(DK key) 2532 { 2533 return map.floorKey(key); 2534 } 2535 2536 public void clear() 2537 { 2538 map.clear(); 2539 } 2540 2541 public Comparator<? super DK> comparator() 2542 { 2543 return Collections.reverseOrder(map.comparator()); 2544 } 2545 2546 public boolean containsKey(Object o) 2547 { 2548 return map.containsKey(o); 2549 } 2550 2551 public boolean containsValue(Object o) 2552 { 2553 return map.containsValue(o); 2554 } 2555 2556 public NavigableSet<DK> descendingKeySet() 2557 { 2558 return descendingMap().navigableKeySet(); 2559 } 2560 2561 public NavigableMap<DK,DV> descendingMap() 2562 { 2563 return map; 2564 } 2565 2566 public Set<Entry<DK,DV>> entrySet() 2567 { 2568 if (entries == null) 2569 entries = 2570 new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>) 2571 map.entrySet()); 2572 return entries; 2573 } 2574 2575 public boolean equals(Object o) 2576 { 2577 return map.equals(o); 2578 } 2579 2580 public Entry<DK,DV> firstEntry() 2581 { 2582 return map.lastEntry(); 2583 } 2584 2585 public DK firstKey() 2586 { 2587 return map.lastKey(); 2588 } 2589 2590 public Entry<DK,DV> floorEntry(DK key) 2591 { 2592 return map.ceilingEntry(key); 2593 } 2594 2595 public DK floorKey(DK key) 2596 { 2597 return map.ceilingKey(key); 2598 } 2599 2600 public DV get(Object key) 2601 { 2602 return map.get(key); 2603 } 2604 2605 public int hashCode() 2606 { 2607 return map.hashCode(); 2608 } 2609 2610 public SortedMap<DK,DV> headMap(DK toKey) 2611 { 2612 return headMap(toKey, false); 2613 } 2614 2615 public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive) 2616 { 2617 return new DescendingMap(map.tailMap(toKey, inclusive)); 2618 } 2619 2620 public Entry<DK,DV> higherEntry(DK key) 2621 { 2622 return map.lowerEntry(key); 2623 } 2624 2625 public DK higherKey(DK key) 2626 { 2627 return map.lowerKey(key); 2628 } 2629 2630 public Set<DK> keySet() 2631 { 2632 if (keys == null) 2633 keys = new DescendingSet<DK>(map.navigableKeySet()); 2634 return keys; 2635 } 2636 2637 public boolean isEmpty() 2638 { 2639 return map.isEmpty(); 2640 } 2641 2642 public Entry<DK,DV> lastEntry() 2643 { 2644 return map.firstEntry(); 2645 } 2646 2647 public DK lastKey() 2648 { 2649 return map.firstKey(); 2650 } 2651 2652 public Entry<DK,DV> lowerEntry(DK key) 2653 { 2654 return map.higherEntry(key); 2655 } 2656 2657 public DK lowerKey(DK key) 2658 { 2659 return map.higherKey(key); 2660 } 2661 2662 public NavigableSet<DK> navigableKeySet() 2663 { 2664 if (nKeys == null) 2665 nKeys = new DescendingSet<DK>(map.navigableKeySet()); 2666 return nKeys; 2667 } 2668 2669 public Entry<DK,DV> pollFirstEntry() 2670 { 2671 return pollLastEntry(); 2672 } 2673 2674 public Entry<DK,DV> pollLastEntry() 2675 { 2676 return pollFirstEntry(); 2677 } 2678 2679 public DV put(DK key, DV value) 2680 { 2681 return map.put(key, value); 2682 } 2683 2684 public void putAll(Map<? extends DK, ? extends DV> m) 2685 { 2686 map.putAll(m); 2687 } 2688 2689 public DV remove(Object key) 2690 { 2691 return map.remove(key); 2692 } 2693 2694 public int size() 2695 { 2696 return map.size(); 2697 } 2698 2699 public SortedMap<DK,DV> subMap(DK fromKey, DK toKey) 2700 { 2701 return subMap(fromKey, true, toKey, false); 2702 } 2703 2704 public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive, 2705 DK toKey, boolean toInclusive) 2706 { 2707 return new DescendingMap(map.subMap(fromKey, fromInclusive, 2708 toKey, toInclusive)); 2709 } 2710 2711 public SortedMap<DK,DV> tailMap(DK fromKey) 2712 { 2713 return tailMap(fromKey, true); 2714 } 2715 2716 public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive) 2717 { 2718 return new DescendingMap(map.headMap(fromKey, inclusive)); 2719 } 2720 2721 public String toString() 2722 { 2723 StringBuilder r = new StringBuilder("{"); 2724 final Iterator<Entry<DK,DV>> it = entrySet().iterator(); 2725 while (it.hasNext()) 2726 { 2727 final Entry<DK,DV> e = it.next(); 2728 r.append(e.getKey()); 2729 r.append('='); 2730 r.append(e.getValue()); 2731 r.append(", "); 2732 } 2733 r.replace(r.length() - 2, r.length(), "}"); 2734 return r.toString(); 2735 } 2736 2737 public Collection<DV> values() 2738 { 2739 if (values == null) 2740 // Create an AbstractCollection with custom implementations of those 2741 // methods that can be overriden easily and efficiently. 2742 values = new AbstractCollection() 2743 { 2744 public int size() 2745 { 2746 return size(); 2747 } 2748 2749 public Iterator<DV> iterator() 2750 { 2751 return new Iterator<DV>() 2752 { 2753 /** The last Entry returned by a next() call. */ 2754 private Entry<DK,DV> last; 2755 2756 /** The next entry that should be returned by next(). */ 2757 private Entry<DK,DV> next = firstEntry(); 2758 2759 public boolean hasNext() 2760 { 2761 return next != null; 2762 } 2763 2764 public DV next() 2765 { 2766 if (next == null) 2767 throw new NoSuchElementException(); 2768 last = next; 2769 next = higherEntry(last.getKey()); 2770 2771 return last.getValue(); 2772 } 2773 2774 public void remove() 2775 { 2776 if (last == null) 2777 throw new IllegalStateException(); 2778 2779 DescendingMap.this.remove(last.getKey()); 2780 last = null; 2781 } 2782 }; 2783 } 2784 2785 public void clear() 2786 { 2787 clear(); 2788 } 2789 }; 2790 return values; 2791 } 2792 2793 } // class DescendingMap 2794 2795 /** 2796 * Implementation of {@link #keySet()}. 2797 */ 2798 private class KeySet 2799 extends AbstractSet<K> 2800 { 2801 2802 public int size() 2803 { 2804 return size; 2805 } 2806 2807 public Iterator<K> iterator() 2808 { 2809 return new TreeIterator(KEYS); 2810 } 2811 2812 public void clear() 2813 { 2814 TreeMap.this.clear(); 2815 } 2816 2817 public boolean contains(Object o) 2818 { 2819 return containsKey(o); 2820 } 2821 2822 public boolean remove(Object key) 2823 { 2824 Node<K,V> n = getNode((K) key); 2825 if (n == nil) 2826 return false; 2827 removeNode(n); 2828 return true; 2829 } 2830 } // class KeySet 2831 2832 /** 2833 * Implementation of {@link #navigableKeySet()}. 2834 * 2835 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 2836 */ 2837 private final class NavigableKeySet 2838 extends KeySet 2839 implements NavigableSet<K> 2840 { 2841 2842 public K ceiling(K k) 2843 { 2844 return ceilingKey(k); 2845 } 2846 2847 public Comparator<? super K> comparator() 2848 { 2849 return comparator; 2850 } 2851 2852 public Iterator<K> descendingIterator() 2853 { 2854 return descendingSet().iterator(); 2855 } 2856 2857 public NavigableSet<K> descendingSet() 2858 { 2859 return new DescendingSet<K>(this); 2860 } 2861 2862 public K first() 2863 { 2864 return firstKey(); 2865 } 2866 2867 public K floor(K k) 2868 { 2869 return floorKey(k); 2870 } 2871 2872 public SortedSet<K> headSet(K to) 2873 { 2874 return headSet(to, false); 2875 } 2876 2877 public NavigableSet<K> headSet(K to, boolean inclusive) 2878 { 2879 return headMap(to, inclusive).navigableKeySet(); 2880 } 2881 2882 public K higher(K k) 2883 { 2884 return higherKey(k); 2885 } 2886 2887 public K last() 2888 { 2889 return lastKey(); 2890 } 2891 2892 public K lower(K k) 2893 { 2894 return lowerKey(k); 2895 } 2896 2897 public K pollFirst() 2898 { 2899 return pollFirstEntry().getKey(); 2900 } 2901 2902 public K pollLast() 2903 { 2904 return pollLastEntry().getKey(); 2905 } 2906 2907 public SortedSet<K> subSet(K from, K to) 2908 { 2909 return subSet(from, true, to, false); 2910 } 2911 2912 public NavigableSet<K> subSet(K from, boolean fromInclusive, 2913 K to, boolean toInclusive) 2914 { 2915 return subMap(from, fromInclusive, 2916 to, toInclusive).navigableKeySet(); 2917 } 2918 2919 public SortedSet<K> tailSet(K from) 2920 { 2921 return tailSet(from, true); 2922 } 2923 2924 public NavigableSet<K> tailSet(K from, boolean inclusive) 2925 { 2926 return tailMap(from, inclusive).navigableKeySet(); 2927 } 2928 2929 2930 } // class NavigableKeySet 2931 2932 /** 2933 * Implementation of {@link #descendingSet()} and associated 2934 * derivatives. This class provides a view of the 2935 * original backing set in reverse order, and throws 2936 * {@link IllegalArgumentException} for attempts to 2937 * access beyond that range. 2938 * 2939 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 2940 */ 2941 private static final class DescendingSet<D> 2942 implements NavigableSet<D> 2943 { 2944 2945 /** 2946 * The backing {@link NavigableSet}. 2947 */ 2948 private NavigableSet<D> set; 2949 2950 /** 2951 * Create a {@link DescendingSet} around the specified 2952 * set. 2953 * 2954 * @param map the set to wrap. 2955 */ 2956 public DescendingSet(NavigableSet<D> set) 2957 { 2958 this.set = set; 2959 } 2960 2961 public boolean add(D e) 2962 { 2963 return set.add(e); 2964 } 2965 2966 public boolean addAll(Collection<? extends D> c) 2967 { 2968 return set.addAll(c); 2969 } 2970 2971 public D ceiling(D e) 2972 { 2973 return set.floor(e); 2974 } 2975 2976 public void clear() 2977 { 2978 set.clear(); 2979 } 2980 2981 public Comparator<? super D> comparator() 2982 { 2983 return Collections.reverseOrder(set.comparator()); 2984 } 2985 2986 public boolean contains(Object o) 2987 { 2988 return set.contains(o); 2989 } 2990 2991 public boolean containsAll(Collection<?> c) 2992 { 2993 return set.containsAll(c); 2994 } 2995 2996 public Iterator<D> descendingIterator() 2997 { 2998 return descendingSet().iterator(); 2999 } 3000 3001 public NavigableSet<D> descendingSet() 3002 { 3003 return set; 3004 } 3005 3006 public boolean equals(Object o) 3007 { 3008 return set.equals(o); 3009 } 3010 3011 public D first() 3012 { 3013 return set.last(); 3014 } 3015 3016 public D floor(D e) 3017 { 3018 return set.ceiling(e); 3019 } 3020 3021 public int hashCode() 3022 { 3023 return set.hashCode(); 3024 } 3025 3026 public SortedSet<D> headSet(D to) 3027 { 3028 return headSet(to, false); 3029 } 3030 3031 public NavigableSet<D> headSet(D to, boolean inclusive) 3032 { 3033 return new DescendingSet(set.tailSet(to, inclusive)); 3034 } 3035 3036 public D higher(D e) 3037 { 3038 return set.lower(e); 3039 } 3040 3041 public boolean isEmpty() 3042 { 3043 return set.isEmpty(); 3044 } 3045 3046 public Iterator<D> iterator() 3047 { 3048 return new Iterator<D>() 3049 { 3050 3051 /** The last element returned by a next() call. */ 3052 private D last; 3053 3054 /** The next element that should be returned by next(). */ 3055 private D next = first(); 3056 3057 public boolean hasNext() 3058 { 3059 return next != null; 3060 } 3061 3062 public D next() 3063 { 3064 if (next == null) 3065 throw new NoSuchElementException(); 3066 last = next; 3067 next = higher(last); 3068 3069 return last; 3070 } 3071 3072 public void remove() 3073 { 3074 if (last == null) 3075 throw new IllegalStateException(); 3076 3077 DescendingSet.this.remove(last); 3078 last = null; 3079 } 3080 }; 3081 } 3082 3083 public D last() 3084 { 3085 return set.first(); 3086 } 3087 3088 public D lower(D e) 3089 { 3090 return set.higher(e); 3091 } 3092 3093 public D pollFirst() 3094 { 3095 return set.pollLast(); 3096 } 3097 3098 public D pollLast() 3099 { 3100 return set.pollFirst(); 3101 } 3102 3103 public boolean remove(Object o) 3104 { 3105 return set.remove(o); 3106 } 3107 3108 public boolean removeAll(Collection<?> c) 3109 { 3110 return set.removeAll(c); 3111 } 3112 3113 public boolean retainAll(Collection<?> c) 3114 { 3115 return set.retainAll(c); 3116 } 3117 3118 public int size() 3119 { 3120 return set.size(); 3121 } 3122 3123 public SortedSet<D> subSet(D from, D to) 3124 { 3125 return subSet(from, true, to, false); 3126 } 3127 3128 public NavigableSet<D> subSet(D from, boolean fromInclusive, 3129 D to, boolean toInclusive) 3130 { 3131 return new DescendingSet(set.subSet(from, fromInclusive, 3132 to, toInclusive)); 3133 } 3134 3135 public SortedSet<D> tailSet(D from) 3136 { 3137 return tailSet(from, true); 3138 } 3139 3140 public NavigableSet<D> tailSet(D from, boolean inclusive) 3141 { 3142 return new DescendingSet(set.headSet(from, inclusive)); 3143 } 3144 3145 public Object[] toArray() 3146 { 3147 D[] array = (D[]) set.toArray(); 3148 Arrays.sort(array, comparator()); 3149 return array; 3150 } 3151 3152 public <T> T[] toArray(T[] a) 3153 { 3154 T[] array = set.toArray(a); 3155 Arrays.sort(array, (Comparator<? super T>) comparator()); 3156 return array; 3157 } 3158 3159 public String toString() 3160 { 3161 StringBuilder r = new StringBuilder("["); 3162 final Iterator<D> it = iterator(); 3163 while (it.hasNext()) 3164 { 3165 final D o = it.next(); 3166 if (o == this) 3167 r.append("<this>"); 3168 else 3169 r.append(o); 3170 r.append(", "); 3171 } 3172 r.replace(r.length() - 2, r.length(), "]"); 3173 return r.toString(); 3174 } 3175 3176 } // class DescendingSet 3177 3178 private class EntrySet 3179 extends AbstractSet<Entry<K,V>> 3180 { 3181 public int size() 3182 { 3183 return size; 3184 } 3185 3186 public Iterator<Map.Entry<K,V>> iterator() 3187 { 3188 return new TreeIterator(ENTRIES); 3189 } 3190 3191 public void clear() 3192 { 3193 TreeMap.this.clear(); 3194 } 3195 3196 public boolean contains(Object o) 3197 { 3198 if (! (o instanceof Map.Entry)) 3199 return false; 3200 Map.Entry<K,V> me = (Map.Entry<K,V>) o; 3201 Node<K,V> n = getNode(me.getKey()); 3202 return n != nil && AbstractSet.equals(me.getValue(), n.value); 3203 } 3204 3205 public boolean remove(Object o) 3206 { 3207 if (! (o instanceof Map.Entry)) 3208 return false; 3209 Map.Entry<K,V> me = (Map.Entry<K,V>) o; 3210 Node<K,V> n = getNode(me.getKey()); 3211 if (n != nil && AbstractSet.equals(me.getValue(), n.value)) 3212 { 3213 removeNode(n); 3214 return true; 3215 } 3216 return false; 3217 } 3218 } 3219 3220 private final class NavigableEntrySet 3221 extends EntrySet 3222 implements NavigableSet<Entry<K,V>> 3223 { 3224 3225 public Entry<K,V> ceiling(Entry<K,V> e) 3226 { 3227 return ceilingEntry(e.getKey()); 3228 } 3229 3230 public Comparator<? super Entry<K,V>> comparator() 3231 { 3232 return new Comparator<Entry<K,V>>() 3233 { 3234 public int compare(Entry<K,V> t1, Entry<K,V> t2) 3235 { 3236 return comparator.compare(t1.getKey(), t2.getKey()); 3237 } 3238 }; 3239 } 3240 3241 public Iterator<Entry<K,V>> descendingIterator() 3242 { 3243 return descendingSet().iterator(); 3244 } 3245 3246 public NavigableSet<Entry<K,V>> descendingSet() 3247 { 3248 return new DescendingSet(this); 3249 } 3250 3251 public Entry<K,V> first() 3252 { 3253 return firstEntry(); 3254 } 3255 3256 public Entry<K,V> floor(Entry<K,V> e) 3257 { 3258 return floorEntry(e.getKey()); 3259 } 3260 3261 public SortedSet<Entry<K,V>> headSet(Entry<K,V> to) 3262 { 3263 return headSet(to, false); 3264 } 3265 3266 public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive) 3267 { 3268 return (NavigableSet<Entry<K,V>>) headMap(to.getKey(), inclusive).entrySet(); 3269 } 3270 3271 public Entry<K,V> higher(Entry<K,V> e) 3272 { 3273 return higherEntry(e.getKey()); 3274 } 3275 3276 public Entry<K,V> last() 3277 { 3278 return lastEntry(); 3279 } 3280 3281 public Entry<K,V> lower(Entry<K,V> e) 3282 { 3283 return lowerEntry(e.getKey()); 3284 } 3285 3286 public Entry<K,V> pollFirst() 3287 { 3288 return pollFirstEntry(); 3289 } 3290 3291 public Entry<K,V> pollLast() 3292 { 3293 return pollLastEntry(); 3294 } 3295 3296 public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to) 3297 { 3298 return subSet(from, true, to, false); 3299 } 3300 3301 public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive, 3302 Entry<K,V> to, boolean toInclusive) 3303 { 3304 return (NavigableSet<Entry<K,V>>) subMap(from.getKey(), fromInclusive, 3305 to.getKey(), toInclusive).entrySet(); 3306 } 3307 3308 public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from) 3309 { 3310 return tailSet(from, true); 3311 } 3312 3313 public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive) 3314 { 3315 return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet(); 3316 } 3317 3318 } // class NavigableEntrySet 3319 3320 } // class TreeMap