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