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