GNU Classpath (0.20) | |
Frames | No Frames |
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 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: * @see Map 83: * @see HashMap 84: * @see Hashtable 85: * @see LinkedHashMap 86: * @see Comparable 87: * @see Comparator 88: * @see Collection 89: * @see Collections#synchronizedSortedMap(SortedMap) 90: * @since 1.2 91: * @status updated to 1.4 92: */ 93: public class TreeMap extends AbstractMap 94: implements SortedMap, Cloneable, Serializable 95: { 96: // Implementation note: 97: // A red-black tree is a binary search tree with the additional properties 98: // that all paths to a leaf node visit the same number of black nodes, 99: // and no red node has red children. To avoid some null-pointer checks, 100: // we use the special node nil which is always black, has no relatives, 101: // and has key and value of null (but is not equal to a mapping of null). 102: 103: /** 104: * Compatible with JDK 1.2. 105: */ 106: private static final long serialVersionUID = 919286545866124006L; 107: 108: /** 109: * Color status of a node. Package visible for use by nested classes. 110: */ 111: static final int RED = -1, 112: BLACK = 1; 113: 114: /** 115: * Sentinal node, used to avoid null checks for corner cases and make the 116: * delete rebalance code simpler. The rebalance code must never assign 117: * the parent, left, or right of nil, but may safely reassign the color 118: * to be black. This object must never be used as a key in a TreeMap, or 119: * it will break bounds checking of a SubMap. 120: */ 121: static final Node nil = new Node(null, null, BLACK); 122: static 123: { 124: // Nil is self-referential, so we must initialize it after creation. 125: nil.parent = nil; 126: nil.left = nil; 127: nil.right = nil; 128: } 129: 130: /** 131: * The root node of this TreeMap. 132: */ 133: private transient Node root; 134: 135: /** 136: * The size of this TreeMap. Package visible for use by nested classes. 137: */ 138: transient int size; 139: 140: /** 141: * The cache for {@link #entrySet()}. 142: */ 143: private transient Set entries; 144: 145: /** 146: * Counts the number of modifications this TreeMap has undergone, used 147: * by Iterators to know when to throw ConcurrentModificationExceptions. 148: * Package visible for use by nested classes. 149: */ 150: transient int modCount; 151: 152: /** 153: * This TreeMap's comparator, or null for natural ordering. 154: * Package visible for use by nested classes. 155: * @serial the comparator ordering this tree, or null 156: */ 157: final Comparator comparator; 158: 159: /** 160: * Class to represent an entry in the tree. Holds a single key-value pair, 161: * plus pointers to parent and child nodes. 162: * 163: * @author Eric Blake (ebb9@email.byu.edu) 164: */ 165: private static final class Node extends AbstractMap.BasicMapEntry 166: { 167: // All fields package visible for use by nested classes. 168: /** The color of this node. */ 169: int color; 170: 171: /** The left child node. */ 172: Node left = nil; 173: /** The right child node. */ 174: Node right = nil; 175: /** The parent node. */ 176: Node parent = nil; 177: 178: /** 179: * Simple constructor. 180: * @param key the key 181: * @param value the value 182: */ 183: Node(Object key, Object value, int color) 184: { 185: super(key, value); 186: this.color = color; 187: } 188: } 189: 190: /** 191: * Instantiate a new TreeMap with no elements, using the keys' natural 192: * ordering to sort. All entries in the map must have a key which implements 193: * Comparable, and which are <i>mutually comparable</i>, otherwise map 194: * operations may throw a {@link ClassCastException}. Attempts to use 195: * a null key will throw a {@link NullPointerException}. 196: * 197: * @see Comparable 198: */ 199: public TreeMap() 200: { 201: this((Comparator) null); 202: } 203: 204: /** 205: * Instantiate a new TreeMap with no elements, using the provided comparator 206: * to sort. All entries in the map must have keys which are mutually 207: * comparable by the Comparator, otherwise map operations may throw a 208: * {@link ClassCastException}. 209: * 210: * @param c the sort order for the keys of this map, or null 211: * for the natural order 212: */ 213: public TreeMap(Comparator c) 214: { 215: comparator = c; 216: fabricateTree(0); 217: } 218: 219: /** 220: * Instantiate a new TreeMap, initializing it with all of the elements in 221: * the provided Map. The elements will be sorted using the natural 222: * ordering of the keys. This algorithm runs in n*log(n) time. All entries 223: * in the map must have keys which implement Comparable and are mutually 224: * comparable, otherwise map operations may throw a 225: * {@link ClassCastException}. 226: * 227: * @param map a Map, whose entries will be put into this TreeMap 228: * @throws ClassCastException if the keys in the provided Map are not 229: * comparable 230: * @throws NullPointerException if map is null 231: * @see Comparable 232: */ 233: public TreeMap(Map map) 234: { 235: this((Comparator) null); 236: putAll(map); 237: } 238: 239: /** 240: * Instantiate a new TreeMap, initializing it with all of the elements in 241: * the provided SortedMap. The elements will be sorted using the same 242: * comparator as in the provided SortedMap. This runs in linear time. 243: * 244: * @param sm a SortedMap, whose entries will be put into this TreeMap 245: * @throws NullPointerException if sm is null 246: */ 247: public TreeMap(SortedMap sm) 248: { 249: this(sm.comparator()); 250: int pos = sm.size(); 251: Iterator itr = sm.entrySet().iterator(); 252: 253: fabricateTree(pos); 254: Node node = firstNode(); 255: 256: while (--pos >= 0) 257: { 258: Map.Entry me = (Map.Entry) itr.next(); 259: node.key = me.getKey(); 260: node.value = me.getValue(); 261: node = successor(node); 262: } 263: } 264: 265: /** 266: * Clears the Map so it has no keys. This is O(1). 267: */ 268: public void clear() 269: { 270: if (size > 0) 271: { 272: modCount++; 273: root = nil; 274: size = 0; 275: } 276: } 277: 278: /** 279: * Returns a shallow clone of this TreeMap. The Map itself is cloned, 280: * but its contents are not. 281: * 282: * @return the clone 283: */ 284: public Object clone() 285: { 286: TreeMap copy = null; 287: try 288: { 289: copy = (TreeMap) super.clone(); 290: } 291: catch (CloneNotSupportedException x) 292: { 293: } 294: copy.entries = null; 295: copy.fabricateTree(size); 296: 297: Node node = firstNode(); 298: Node cnode = copy.firstNode(); 299: 300: while (node != nil) 301: { 302: cnode.key = node.key; 303: cnode.value = node.value; 304: node = successor(node); 305: cnode = copy.successor(cnode); 306: } 307: return copy; 308: } 309: 310: /** 311: * Return the comparator used to sort this map, or null if it is by 312: * natural order. 313: * 314: * @return the map's comparator 315: */ 316: public Comparator comparator() 317: { 318: return comparator; 319: } 320: 321: /** 322: * Returns true if the map contains a mapping for the given key. 323: * 324: * @param key the key to look for 325: * @return true if the key has a mapping 326: * @throws ClassCastException if key is not comparable to map elements 327: * @throws NullPointerException if key is null and the comparator is not 328: * tolerant of nulls 329: */ 330: public boolean containsKey(Object key) 331: { 332: return getNode(key) != nil; 333: } 334: 335: /** 336: * Returns true if the map contains at least one mapping to the given value. 337: * This requires linear time. 338: * 339: * @param value the value to look for 340: * @return true if the value appears in a mapping 341: */ 342: public boolean containsValue(Object value) 343: { 344: Node node = firstNode(); 345: while (node != nil) 346: { 347: if (equals(value, node.value)) 348: return true; 349: node = successor(node); 350: } 351: return false; 352: } 353: 354: /** 355: * Returns a "set view" of this TreeMap's entries. The set is backed by 356: * the TreeMap, so changes in one show up in the other. The set supports 357: * element removal, but not element addition.<p> 358: * 359: * Note that the iterators for all three views, from keySet(), entrySet(), 360: * and values(), traverse the TreeMap in sorted sequence. 361: * 362: * @return a set view of the entries 363: * @see #keySet() 364: * @see #values() 365: * @see Map.Entry 366: */ 367: public Set entrySet() 368: { 369: if (entries == null) 370: // Create an AbstractSet with custom implementations of those methods 371: // that can be overriden easily and efficiently. 372: entries = new AbstractSet() 373: { 374: public int size() 375: { 376: return size; 377: } 378: 379: public Iterator iterator() 380: { 381: return new TreeIterator(ENTRIES); 382: } 383: 384: public void clear() 385: { 386: TreeMap.this.clear(); 387: } 388: 389: public boolean contains(Object o) 390: { 391: if (! (o instanceof Map.Entry)) 392: return false; 393: Map.Entry me = (Map.Entry) o; 394: Node n = getNode(me.getKey()); 395: return n != nil && AbstractSet.equals(me.getValue(), n.value); 396: } 397: 398: public boolean remove(Object o) 399: { 400: if (! (o instanceof Map.Entry)) 401: return false; 402: Map.Entry me = (Map.Entry) o; 403: Node n = getNode(me.getKey()); 404: if (n != nil && AbstractSet.equals(me.getValue(), n.value)) 405: { 406: removeNode(n); 407: return true; 408: } 409: return false; 410: } 411: }; 412: return entries; 413: } 414: 415: /** 416: * Returns the first (lowest) key in the map. 417: * 418: * @return the first key 419: * @throws NoSuchElementException if the map is empty 420: */ 421: public Object firstKey() 422: { 423: if (root == nil) 424: throw new NoSuchElementException(); 425: return firstNode().key; 426: } 427: 428: /** 429: * Return the value in this TreeMap associated with the supplied key, 430: * or <code>null</code> if the key maps to nothing. NOTE: Since the value 431: * could also be null, you must use containsKey to see if this key 432: * actually maps to something. 433: * 434: * @param key the key for which to fetch an associated value 435: * @return what the key maps to, if present 436: * @throws ClassCastException if key is not comparable to elements in the map 437: * @throws NullPointerException if key is null but the comparator does not 438: * tolerate nulls 439: * @see #put(Object, Object) 440: * @see #containsKey(Object) 441: */ 442: public Object get(Object key) 443: { 444: // Exploit fact that nil.value == null. 445: return getNode(key).value; 446: } 447: 448: /** 449: * Returns a view of this Map including all entries with keys less than 450: * <code>toKey</code>. The returned map is backed by the original, so changes 451: * in one appear in the other. The submap will throw an 452: * {@link IllegalArgumentException} for any attempt to access or add an 453: * element beyond the specified cutoff. The returned map does not include 454: * the endpoint; if you want inclusion, pass the successor element. 455: * 456: * @param toKey the (exclusive) cutoff point 457: * @return a view of the map less than the cutoff 458: * @throws ClassCastException if <code>toKey</code> is not compatible with 459: * the comparator (or is not Comparable, for natural ordering) 460: * @throws NullPointerException if toKey is null, but the comparator does not 461: * tolerate null elements 462: */ 463: public SortedMap headMap(Object toKey) 464: { 465: return new SubMap(nil, toKey); 466: } 467: 468: /** 469: * Returns a "set view" of this TreeMap's keys. The set is backed by the 470: * TreeMap, so changes in one show up in the other. The set supports 471: * element removal, but not element addition. 472: * 473: * @return a set view of the keys 474: * @see #values() 475: * @see #entrySet() 476: */ 477: public Set keySet() 478: { 479: if (keys == null) 480: // Create an AbstractSet with custom implementations of those methods 481: // that can be overriden easily and efficiently. 482: keys = new AbstractSet() 483: { 484: public int size() 485: { 486: return size; 487: } 488: 489: public Iterator iterator() 490: { 491: return new TreeIterator(KEYS); 492: } 493: 494: public void clear() 495: { 496: TreeMap.this.clear(); 497: } 498: 499: public boolean contains(Object o) 500: { 501: return containsKey(o); 502: } 503: 504: public boolean remove(Object key) 505: { 506: Node n = getNode(key); 507: if (n == nil) 508: return false; 509: removeNode(n); 510: return true; 511: } 512: }; 513: return keys; 514: } 515: 516: /** 517: * Returns the last (highest) key in the map. 518: * 519: * @return the last key 520: * @throws NoSuchElementException if the map is empty 521: */ 522: public Object lastKey() 523: { 524: if (root == nil) 525: throw new NoSuchElementException("empty"); 526: return lastNode().key; 527: } 528: 529: /** 530: * Puts the supplied value into the Map, mapped by the supplied key. 531: * The value may be retrieved by any object which <code>equals()</code> 532: * this key. NOTE: Since the prior value could also be null, you must 533: * first use containsKey if you want to see if you are replacing the 534: * key's mapping. 535: * 536: * @param key the key used to locate the value 537: * @param value the value to be stored in the Map 538: * @return the prior mapping of the key, or null if there was none 539: * @throws ClassCastException if key is not comparable to current map keys 540: * @throws NullPointerException if key is null, but the comparator does 541: * not tolerate nulls 542: * @see #get(Object) 543: * @see Object#equals(Object) 544: */ 545: public Object put(Object key, Object value) 546: { 547: Node current = root; 548: Node parent = nil; 549: int comparison = 0; 550: 551: // Find new node's parent. 552: while (current != nil) 553: { 554: parent = current; 555: comparison = compare(key, current.key); 556: if (comparison > 0) 557: current = current.right; 558: else if (comparison < 0) 559: current = current.left; 560: else // Key already in tree. 561: return current.setValue(value); 562: } 563: 564: // Set up new node. 565: Node n = new Node(key, value, RED); 566: n.parent = parent; 567: 568: // Insert node in tree. 569: modCount++; 570: size++; 571: if (parent == nil) 572: { 573: // Special case inserting into an empty tree. 574: root = n; 575: return null; 576: } 577: if (comparison > 0) 578: parent.right = n; 579: else 580: parent.left = n; 581: 582: // Rebalance after insert. 583: insertFixup(n); 584: return null; 585: } 586: 587: /** 588: * Copies all elements of the given map into this TreeMap. If this map 589: * already has a mapping for a key, the new mapping replaces the current 590: * one. 591: * 592: * @param m the map to be added 593: * @throws ClassCastException if a key in m is not comparable with keys 594: * in the map 595: * @throws NullPointerException if a key in m is null, and the comparator 596: * does not tolerate nulls 597: */ 598: public void putAll(Map m) 599: { 600: Iterator itr = m.entrySet().iterator(); 601: int pos = m.size(); 602: while (--pos >= 0) 603: { 604: Map.Entry e = (Map.Entry) itr.next(); 605: put(e.getKey(), e.getValue()); 606: } 607: } 608: 609: /** 610: * Removes from the TreeMap and returns the value which is mapped by the 611: * supplied key. If the key maps to nothing, then the TreeMap remains 612: * unchanged, and <code>null</code> is returned. NOTE: Since the value 613: * could also be null, you must use containsKey to see if you are 614: * actually removing a mapping. 615: * 616: * @param key the key used to locate the value to remove 617: * @return whatever the key mapped to, if present 618: * @throws ClassCastException if key is not comparable to current map keys 619: * @throws NullPointerException if key is null, but the comparator does 620: * not tolerate nulls 621: */ 622: public Object remove(Object key) 623: { 624: Node n = getNode(key); 625: if (n == nil) 626: return null; 627: // Note: removeNode can alter the contents of n, so save value now. 628: Object result = n.value; 629: removeNode(n); 630: return result; 631: } 632: 633: /** 634: * Returns the number of key-value mappings currently in this Map. 635: * 636: * @return the size 637: */ 638: public int size() 639: { 640: return size; 641: } 642: 643: /** 644: * Returns a view of this Map including all entries with keys greater or 645: * equal to <code>fromKey</code> and less than <code>toKey</code> (a 646: * half-open interval). The returned map is backed by the original, so 647: * changes in one appear in the other. The submap will throw an 648: * {@link IllegalArgumentException} for any attempt to access or add an 649: * element beyond the specified cutoffs. The returned map includes the low 650: * endpoint but not the high; if you want to reverse this behavior on 651: * either end, pass in the successor element. 652: * 653: * @param fromKey the (inclusive) low cutoff point 654: * @param toKey the (exclusive) high cutoff point 655: * @return a view of the map between the cutoffs 656: * @throws ClassCastException if either cutoff is not compatible with 657: * the comparator (or is not Comparable, for natural ordering) 658: * @throws NullPointerException if fromKey or toKey is null, but the 659: * comparator does not tolerate null elements 660: * @throws IllegalArgumentException if fromKey is greater than toKey 661: */ 662: public SortedMap subMap(Object fromKey, Object toKey) 663: { 664: return new SubMap(fromKey, toKey); 665: } 666: 667: /** 668: * Returns a view of this Map including all entries with keys greater or 669: * equal to <code>fromKey</code>. The returned map is backed by the 670: * original, so changes in one appear in the other. The submap will throw an 671: * {@link IllegalArgumentException} for any attempt to access or add an 672: * element beyond the specified cutoff. The returned map includes the 673: * endpoint; if you want to exclude it, pass in the successor element. 674: * 675: * @param fromKey the (inclusive) low cutoff point 676: * @return a view of the map above the cutoff 677: * @throws ClassCastException if <code>fromKey</code> is not compatible with 678: * the comparator (or is not Comparable, for natural ordering) 679: * @throws NullPointerException if fromKey is null, but the comparator 680: * does not tolerate null elements 681: */ 682: public SortedMap tailMap(Object fromKey) 683: { 684: return new SubMap(fromKey, nil); 685: } 686: 687: /** 688: * Returns a "collection view" (or "bag view") of this TreeMap's values. 689: * The collection is backed by the TreeMap, so changes in one show up 690: * in the other. The collection supports element removal, but not element 691: * addition. 692: * 693: * @return a bag view of the values 694: * @see #keySet() 695: * @see #entrySet() 696: */ 697: public Collection values() 698: { 699: if (values == null) 700: // We don't bother overriding many of the optional methods, as doing so 701: // wouldn't provide any significant performance advantage. 702: values = new AbstractCollection() 703: { 704: public int size() 705: { 706: return size; 707: } 708: 709: public Iterator iterator() 710: { 711: return new TreeIterator(VALUES); 712: } 713: 714: public void clear() 715: { 716: TreeMap.this.clear(); 717: } 718: }; 719: return values; 720: } 721: 722: /** 723: * Compares two elements by the set comparator, or by natural ordering. 724: * Package visible for use by nested classes. 725: * 726: * @param o1 the first object 727: * @param o2 the second object 728: * @throws ClassCastException if o1 and o2 are not mutually comparable, 729: * or are not Comparable with natural ordering 730: * @throws NullPointerException if o1 or o2 is null with natural ordering 731: */ 732: final int compare(Object o1, Object o2) 733: { 734: return (comparator == null 735: ? ((Comparable) o1).compareTo(o2) 736: : comparator.compare(o1, o2)); 737: } 738: 739: /** 740: * Maintain red-black balance after deleting a node. 741: * 742: * @param node the child of the node just deleted, possibly nil 743: * @param parent the parent of the node just deleted, never nil 744: */ 745: private void deleteFixup(Node node, Node parent) 746: { 747: // if (parent == nil) 748: // throw new InternalError(); 749: // If a black node has been removed, we need to rebalance to avoid 750: // violating the "same number of black nodes on any path" rule. If 751: // node is red, we can simply recolor it black and all is well. 752: while (node != root && node.color == BLACK) 753: { 754: if (node == parent.left) 755: { 756: // Rebalance left side. 757: Node sibling = parent.right; 758: // if (sibling == nil) 759: // throw new InternalError(); 760: if (sibling.color == RED) 761: { 762: // Case 1: Sibling is red. 763: // Recolor sibling and parent, and rotate parent left. 764: sibling.color = BLACK; 765: parent.color = RED; 766: rotateLeft(parent); 767: sibling = parent.right; 768: } 769: 770: if (sibling.left.color == BLACK && sibling.right.color == BLACK) 771: { 772: // Case 2: Sibling has no red children. 773: // Recolor sibling, and move to parent. 774: sibling.color = RED; 775: node = parent; 776: parent = parent.parent; 777: } 778: else 779: { 780: if (sibling.right.color == BLACK) 781: { 782: // Case 3: Sibling has red left child. 783: // Recolor sibling and left child, rotate sibling right. 784: sibling.left.color = BLACK; 785: sibling.color = RED; 786: rotateRight(sibling); 787: sibling = parent.right; 788: } 789: // Case 4: Sibling has red right child. Recolor sibling, 790: // right child, and parent, and rotate parent left. 791: sibling.color = parent.color; 792: parent.color = BLACK; 793: sibling.right.color = BLACK; 794: rotateLeft(parent); 795: node = root; // Finished. 796: } 797: } 798: else 799: { 800: // Symmetric "mirror" of left-side case. 801: Node sibling = parent.left; 802: // if (sibling == nil) 803: // throw new InternalError(); 804: if (sibling.color == RED) 805: { 806: // Case 1: Sibling is red. 807: // Recolor sibling and parent, and rotate parent right. 808: sibling.color = BLACK; 809: parent.color = RED; 810: rotateRight(parent); 811: sibling = parent.left; 812: } 813: 814: if (sibling.right.color == BLACK && sibling.left.color == BLACK) 815: { 816: // Case 2: Sibling has no red children. 817: // Recolor sibling, and move to parent. 818: sibling.color = RED; 819: node = parent; 820: parent = parent.parent; 821: } 822: else 823: { 824: if (sibling.left.color == BLACK) 825: { 826: // Case 3: Sibling has red right child. 827: // Recolor sibling and right child, rotate sibling left. 828: sibling.right.color = BLACK; 829: sibling.color = RED; 830: rotateLeft(sibling); 831: sibling = parent.left; 832: } 833: // Case 4: Sibling has red left child. Recolor sibling, 834: // left child, and parent, and rotate parent right. 835: sibling.color = parent.color; 836: parent.color = BLACK; 837: sibling.left.color = BLACK; 838: rotateRight(parent); 839: node = root; // Finished. 840: } 841: } 842: } 843: node.color = BLACK; 844: } 845: 846: /** 847: * Construct a perfectly balanced tree consisting of n "blank" nodes. This 848: * permits a tree to be generated from pre-sorted input in linear time. 849: * 850: * @param count the number of blank nodes, non-negative 851: */ 852: private void fabricateTree(final int count) 853: { 854: if (count == 0) 855: { 856: root = nil; 857: size = 0; 858: return; 859: } 860: 861: // We color every row of nodes black, except for the overflow nodes. 862: // I believe that this is the optimal arrangement. We construct the tree 863: // in place by temporarily linking each node to the next node in the row, 864: // then updating those links to the children when working on the next row. 865: 866: // Make the root node. 867: root = new Node(null, null, BLACK); 868: size = count; 869: Node row = root; 870: int rowsize; 871: 872: // Fill each row that is completely full of nodes. 873: for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) 874: { 875: Node parent = row; 876: Node last = null; 877: for (int i = 0; i < rowsize; i += 2) 878: { 879: Node left = new Node(null, null, BLACK); 880: Node right = new Node(null, null, BLACK); 881: left.parent = parent; 882: left.right = right; 883: right.parent = parent; 884: parent.left = left; 885: Node next = parent.right; 886: parent.right = right; 887: parent = next; 888: if (last != null) 889: last.right = left; 890: last = right; 891: } 892: row = row.left; 893: } 894: 895: // Now do the partial final row in red. 896: int overflow = count - rowsize; 897: Node parent = row; 898: int i; 899: for (i = 0; i < overflow; i += 2) 900: { 901: Node left = new Node(null, null, RED); 902: Node right = new Node(null, null, RED); 903: left.parent = parent; 904: right.parent = parent; 905: parent.left = left; 906: Node next = parent.right; 907: parent.right = right; 908: parent = next; 909: } 910: // Add a lone left node if necessary. 911: if (i - overflow == 0) 912: { 913: Node left = new Node(null, null, RED); 914: left.parent = parent; 915: parent.left = left; 916: parent = parent.right; 917: left.parent.right = nil; 918: } 919: // Unlink the remaining nodes of the previous row. 920: while (parent != nil) 921: { 922: Node next = parent.right; 923: parent.right = nil; 924: parent = next; 925: } 926: } 927: 928: /** 929: * Returns the first sorted node in the map, or nil if empty. Package 930: * visible for use by nested classes. 931: * 932: * @return the first node 933: */ 934: final Node firstNode() 935: { 936: // Exploit fact that nil.left == nil. 937: Node node = root; 938: while (node.left != nil) 939: node = node.left; 940: return node; 941: } 942: 943: /** 944: * Return the TreeMap.Node associated with key, or the nil node if no such 945: * node exists in the tree. Package visible for use by nested classes. 946: * 947: * @param key the key to search for 948: * @return the node where the key is found, or nil 949: */ 950: final Node getNode(Object key) 951: { 952: Node current = root; 953: while (current != nil) 954: { 955: int comparison = compare(key, current.key); 956: if (comparison > 0) 957: current = current.right; 958: else if (comparison < 0) 959: current = current.left; 960: else 961: return current; 962: } 963: return current; 964: } 965: 966: /** 967: * Find the "highest" node which is < key. If key is nil, return last 968: * node. Package visible for use by nested classes. 969: * 970: * @param key the upper bound, exclusive 971: * @return the previous node 972: */ 973: final Node highestLessThan(Object key) 974: { 975: if (key == nil) 976: return lastNode(); 977: 978: Node last = nil; 979: Node current = root; 980: int comparison = 0; 981: 982: while (current != nil) 983: { 984: last = current; 985: comparison = compare(key, current.key); 986: if (comparison > 0) 987: current = current.right; 988: else if (comparison < 0) 989: current = current.left; 990: else // Exact match. 991: return predecessor(last); 992: } 993: return comparison <= 0 ? predecessor(last) : last; 994: } 995: 996: /** 997: * Maintain red-black balance after inserting a new node. 998: * 999: * @param n the newly inserted node 1000: */ 1001: private void insertFixup(Node n) 1002: { 1003: // Only need to rebalance when parent is a RED node, and while at least 1004: // 2 levels deep into the tree (ie: node has a grandparent). Remember 1005: // that nil.color == BLACK. 1006: while (n.parent.color == RED && n.parent.parent != nil) 1007: { 1008: if (n.parent == n.parent.parent.left) 1009: { 1010: Node uncle = n.parent.parent.right; 1011: // Uncle may be nil, in which case it is BLACK. 1012: if (uncle.color == RED) 1013: { 1014: // Case 1. Uncle is RED: Change colors of parent, uncle, 1015: // and grandparent, and move n to grandparent. 1016: n.parent.color = BLACK; 1017: uncle.color = BLACK; 1018: uncle.parent.color = RED; 1019: n = uncle.parent; 1020: } 1021: else 1022: { 1023: if (n == n.parent.right) 1024: { 1025: // Case 2. Uncle is BLACK and x is right child. 1026: // Move n to parent, and rotate n left. 1027: n = n.parent; 1028: rotateLeft(n); 1029: } 1030: // Case 3. Uncle is BLACK and x is left child. 1031: // Recolor parent, grandparent, and rotate grandparent right. 1032: n.parent.color = BLACK; 1033: n.parent.parent.color = RED; 1034: rotateRight(n.parent.parent); 1035: } 1036: } 1037: else 1038: { 1039: // Mirror image of above code. 1040: Node uncle = n.parent.parent.left; 1041: // Uncle may be nil, in which case it is BLACK. 1042: if (uncle.color == RED) 1043: { 1044: // Case 1. Uncle is RED: Change colors of parent, uncle, 1045: // and grandparent, and move n to grandparent. 1046: n.parent.color = BLACK; 1047: uncle.color = BLACK; 1048: uncle.parent.color = RED; 1049: n = uncle.parent; 1050: } 1051: else 1052: { 1053: if (n == n.parent.left) 1054: { 1055: // Case 2. Uncle is BLACK and x is left child. 1056: // Move n to parent, and rotate n right. 1057: n = n.parent; 1058: rotateRight(n); 1059: } 1060: // Case 3. Uncle is BLACK and x is right child. 1061: // Recolor parent, grandparent, and rotate grandparent left. 1062: n.parent.color = BLACK; 1063: n.parent.parent.color = RED; 1064: rotateLeft(n.parent.parent); 1065: } 1066: } 1067: } 1068: root.color = BLACK; 1069: } 1070: 1071: /** 1072: * Returns the last sorted node in the map, or nil if empty. 1073: * 1074: * @return the last node 1075: */ 1076: private Node lastNode() 1077: { 1078: // Exploit fact that nil.right == nil. 1079: Node node = root; 1080: while (node.right != nil) 1081: node = node.right; 1082: return node; 1083: } 1084: 1085: /** 1086: * Find the "lowest" node which is >= key. If key is nil, return either 1087: * nil or the first node, depending on the parameter first. 1088: * Package visible for use by nested classes. 1089: * 1090: * @param key the lower bound, inclusive 1091: * @param first true to return the first element instead of nil for nil key 1092: * @return the next node 1093: */ 1094: final Node lowestGreaterThan(Object key, boolean first) 1095: { 1096: if (key == nil) 1097: return first ? firstNode() : nil; 1098: 1099: Node last = nil; 1100: Node current = root; 1101: int comparison = 0; 1102: 1103: while (current != nil) 1104: { 1105: last = current; 1106: comparison = compare(key, current.key); 1107: if (comparison > 0) 1108: current = current.right; 1109: else if (comparison < 0) 1110: current = current.left; 1111: else 1112: return current; 1113: } 1114: return comparison > 0 ? successor(last) : last; 1115: } 1116: 1117: /** 1118: * Return the node preceding the given one, or nil if there isn't one. 1119: * 1120: * @param node the current node, not nil 1121: * @return the prior node in sorted order 1122: */ 1123: private Node predecessor(Node node) 1124: { 1125: if (node.left != nil) 1126: { 1127: node = node.left; 1128: while (node.right != nil) 1129: node = node.right; 1130: return node; 1131: } 1132: 1133: Node parent = node.parent; 1134: // Exploit fact that nil.left == nil and node is non-nil. 1135: while (node == parent.left) 1136: { 1137: node = parent; 1138: parent = node.parent; 1139: } 1140: return parent; 1141: } 1142: 1143: /** 1144: * Construct a tree from sorted keys in linear time. Package visible for 1145: * use by TreeSet. 1146: * 1147: * @param s the stream to read from 1148: * @param count the number of keys to read 1149: * @param readValues true to read values, false to insert "" as the value 1150: * @throws ClassNotFoundException if the underlying stream fails 1151: * @throws IOException if the underlying stream fails 1152: * @see #readObject(ObjectInputStream) 1153: * @see TreeSet#readObject(ObjectInputStream) 1154: */ 1155: final void putFromObjStream(ObjectInputStream s, int count, 1156: boolean readValues) 1157: throws IOException, ClassNotFoundException 1158: { 1159: fabricateTree(count); 1160: Node node = firstNode(); 1161: 1162: while (--count >= 0) 1163: { 1164: node.key = s.readObject(); 1165: node.value = readValues ? s.readObject() : ""; 1166: node = successor(node); 1167: } 1168: } 1169: 1170: /** 1171: * Construct a tree from sorted keys in linear time, with values of "". 1172: * Package visible for use by TreeSet. 1173: * 1174: * @param keys the iterator over the sorted keys 1175: * @param count the number of nodes to insert 1176: * @see TreeSet#TreeSet(SortedSet) 1177: */ 1178: final void putKeysLinear(Iterator keys, int count) 1179: { 1180: fabricateTree(count); 1181: Node node = firstNode(); 1182: 1183: while (--count >= 0) 1184: { 1185: node.key = keys.next(); 1186: node.value = ""; 1187: node = successor(node); 1188: } 1189: } 1190: 1191: /** 1192: * Deserializes this object from the given stream. 1193: * 1194: * @param s the stream to read from 1195: * @throws ClassNotFoundException if the underlying stream fails 1196: * @throws IOException if the underlying stream fails 1197: * @serialData the <i>size</i> (int), followed by key (Object) and value 1198: * (Object) pairs in sorted order 1199: */ 1200: private void readObject(ObjectInputStream s) 1201: throws IOException, ClassNotFoundException 1202: { 1203: s.defaultReadObject(); 1204: int size = s.readInt(); 1205: putFromObjStream(s, size, true); 1206: } 1207: 1208: /** 1209: * Remove node from tree. This will increment modCount and decrement size. 1210: * Node must exist in the tree. Package visible for use by nested classes. 1211: * 1212: * @param node the node to remove 1213: */ 1214: final void removeNode(Node node) 1215: { 1216: Node splice; 1217: Node child; 1218: 1219: modCount++; 1220: size--; 1221: 1222: // Find splice, the node at the position to actually remove from the tree. 1223: if (node.left == nil) 1224: { 1225: // Node to be deleted has 0 or 1 children. 1226: splice = node; 1227: child = node.right; 1228: } 1229: else if (node.right == nil) 1230: { 1231: // Node to be deleted has 1 child. 1232: splice = node; 1233: child = node.left; 1234: } 1235: else 1236: { 1237: // Node has 2 children. Splice is node's predecessor, and we swap 1238: // its contents into node. 1239: splice = node.left; 1240: while (splice.right != nil) 1241: splice = splice.right; 1242: child = splice.left; 1243: node.key = splice.key; 1244: node.value = splice.value; 1245: } 1246: 1247: // Unlink splice from the tree. 1248: Node parent = splice.parent; 1249: if (child != nil) 1250: child.parent = parent; 1251: if (parent == nil) 1252: { 1253: // Special case for 0 or 1 node remaining. 1254: root = child; 1255: return; 1256: } 1257: if (splice == parent.left) 1258: parent.left = child; 1259: else 1260: parent.right = child; 1261: 1262: if (splice.color == BLACK) 1263: deleteFixup(child, parent); 1264: } 1265: 1266: /** 1267: * Rotate node n to the left. 1268: * 1269: * @param node the node to rotate 1270: */ 1271: private void rotateLeft(Node node) 1272: { 1273: Node child = node.right; 1274: // if (node == nil || child == nil) 1275: // throw new InternalError(); 1276: 1277: // Establish node.right link. 1278: node.right = child.left; 1279: if (child.left != nil) 1280: child.left.parent = node; 1281: 1282: // Establish child->parent link. 1283: child.parent = node.parent; 1284: if (node.parent != nil) 1285: { 1286: if (node == node.parent.left) 1287: node.parent.left = child; 1288: else 1289: node.parent.right = child; 1290: } 1291: else 1292: root = child; 1293: 1294: // Link n and child. 1295: child.left = node; 1296: node.parent = child; 1297: } 1298: 1299: /** 1300: * Rotate node n to the right. 1301: * 1302: * @param node the node to rotate 1303: */ 1304: private void rotateRight(Node node) 1305: { 1306: Node child = node.left; 1307: // if (node == nil || child == nil) 1308: // throw new InternalError(); 1309: 1310: // Establish node.left link. 1311: node.left = child.right; 1312: if (child.right != nil) 1313: child.right.parent = node; 1314: 1315: // Establish child->parent link. 1316: child.parent = node.parent; 1317: if (node.parent != nil) 1318: { 1319: if (node == node.parent.right) 1320: node.parent.right = child; 1321: else 1322: node.parent.left = child; 1323: } 1324: else 1325: root = child; 1326: 1327: // Link n and child. 1328: child.right = node; 1329: node.parent = child; 1330: } 1331: 1332: /** 1333: * Return the node following the given one, or nil if there isn't one. 1334: * Package visible for use by nested classes. 1335: * 1336: * @param node the current node, not nil 1337: * @return the next node in sorted order 1338: */ 1339: final Node successor(Node node) 1340: { 1341: if (node.right != nil) 1342: { 1343: node = node.right; 1344: while (node.left != nil) 1345: node = node.left; 1346: return node; 1347: } 1348: 1349: Node parent = node.parent; 1350: // Exploit fact that nil.right == nil and node is non-nil. 1351: while (node == parent.right) 1352: { 1353: node = parent; 1354: parent = parent.parent; 1355: } 1356: return parent; 1357: } 1358: 1359: /** 1360: * Serializes this object to the given stream. 1361: * 1362: * @param s the stream to write to 1363: * @throws IOException if the underlying stream fails 1364: * @serialData the <i>size</i> (int), followed by key (Object) and value 1365: * (Object) pairs in sorted order 1366: */ 1367: private void writeObject(ObjectOutputStream s) throws IOException 1368: { 1369: s.defaultWriteObject(); 1370: 1371: Node node = firstNode(); 1372: s.writeInt(size); 1373: while (node != nil) 1374: { 1375: s.writeObject(node.key); 1376: s.writeObject(node.value); 1377: node = successor(node); 1378: } 1379: } 1380: 1381: /** 1382: * Iterate over TreeMap's entries. This implementation is parameterized 1383: * to give a sequential view of keys, values, or entries. 1384: * 1385: * @author Eric Blake (ebb9@email.byu.edu) 1386: */ 1387: private final class TreeIterator implements Iterator 1388: { 1389: /** 1390: * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 1391: * or {@link #ENTRIES}. 1392: */ 1393: private final int type; 1394: /** The number of modifications to the backing Map that we know about. */ 1395: private int knownMod = modCount; 1396: /** The last Entry returned by a next() call. */ 1397: private Node last; 1398: /** The next entry that should be returned by next(). */ 1399: private Node next; 1400: /** 1401: * The last node visible to this iterator. This is used when iterating 1402: * on a SubMap. 1403: */ 1404: private final Node max; 1405: 1406: /** 1407: * Construct a new TreeIterator with the supplied type. 1408: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 1409: */ 1410: TreeIterator(int type) 1411: { 1412: // FIXME gcj cannot handle this. Bug java/4695 1413: // this(type, firstNode(), nil); 1414: this.type = type; 1415: this.next = firstNode(); 1416: this.max = nil; 1417: } 1418: 1419: /** 1420: * Construct a new TreeIterator with the supplied type. Iteration will 1421: * be from "first" (inclusive) to "max" (exclusive). 1422: * 1423: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 1424: * @param first where to start iteration, nil for empty iterator 1425: * @param max the cutoff for iteration, nil for all remaining nodes 1426: */ 1427: TreeIterator(int type, Node first, Node max) 1428: { 1429: this.type = type; 1430: this.next = first; 1431: this.max = max; 1432: } 1433: 1434: /** 1435: * Returns true if the Iterator has more elements. 1436: * @return true if there are more elements 1437: * @throws ConcurrentModificationException if the TreeMap was modified 1438: */ 1439: public boolean hasNext() 1440: { 1441: if (knownMod != modCount) 1442: throw new ConcurrentModificationException(); 1443: return next != max; 1444: } 1445: 1446: /** 1447: * Returns the next element in the Iterator's sequential view. 1448: * @return the next element 1449: * @throws ConcurrentModificationException if the TreeMap was modified 1450: * @throws NoSuchElementException if there is none 1451: */ 1452: public Object next() 1453: { 1454: if (knownMod != modCount) 1455: throw new ConcurrentModificationException(); 1456: if (next == max) 1457: throw new NoSuchElementException(); 1458: last = next; 1459: next = successor(last); 1460: 1461: if (type == VALUES) 1462: return last.value; 1463: else if (type == KEYS) 1464: return last.key; 1465: return last; 1466: } 1467: 1468: /** 1469: * Removes from the backing TreeMap the last element which was fetched 1470: * with the <code>next()</code> method. 1471: * @throws ConcurrentModificationException if the TreeMap was modified 1472: * @throws IllegalStateException if called when there is no last element 1473: */ 1474: public void remove() 1475: { 1476: if (last == null) 1477: throw new IllegalStateException(); 1478: if (knownMod != modCount) 1479: throw new ConcurrentModificationException(); 1480: 1481: removeNode(last); 1482: last = null; 1483: knownMod++; 1484: } 1485: } // class TreeIterator 1486: 1487: /** 1488: * Implementation of {@link #subMap(Object, Object)} and other map 1489: * ranges. This class provides a view of a portion of the original backing 1490: * map, and throws {@link IllegalArgumentException} for attempts to 1491: * access beyond that range. 1492: * 1493: * @author Eric Blake (ebb9@email.byu.edu) 1494: */ 1495: private final class SubMap extends AbstractMap implements SortedMap 1496: { 1497: /** 1498: * The lower range of this view, inclusive, or nil for unbounded. 1499: * Package visible for use by nested classes. 1500: */ 1501: final Object minKey; 1502: 1503: /** 1504: * The upper range of this view, exclusive, or nil for unbounded. 1505: * Package visible for use by nested classes. 1506: */ 1507: final Object maxKey; 1508: 1509: /** 1510: * The cache for {@link #entrySet()}. 1511: */ 1512: private Set entries; 1513: 1514: /** 1515: * Create a SubMap representing the elements between minKey (inclusive) 1516: * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound 1517: * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap). 1518: * 1519: * @param minKey the lower bound 1520: * @param maxKey the upper bound 1521: * @throws IllegalArgumentException if minKey > maxKey 1522: */ 1523: SubMap(Object minKey, Object maxKey) 1524: { 1525: if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0) 1526: throw new IllegalArgumentException("fromKey > toKey"); 1527: this.minKey = minKey; 1528: this.maxKey = maxKey; 1529: } 1530: 1531: /** 1532: * Check if "key" is in within the range bounds for this SubMap. The 1533: * lower ("from") SubMap range is inclusive, and the upper ("to") bound 1534: * is exclusive. Package visible for use by nested classes. 1535: * 1536: * @param key the key to check 1537: * @return true if the key is in range 1538: */ 1539: boolean keyInRange(Object key) 1540: { 1541: return ((minKey == nil || compare(key, minKey) >= 0) 1542: && (maxKey == nil || compare(key, maxKey) < 0)); 1543: } 1544: 1545: public void clear() 1546: { 1547: Node next = lowestGreaterThan(minKey, true); 1548: Node max = lowestGreaterThan(maxKey, false); 1549: while (next != max) 1550: { 1551: Node current = next; 1552: next = successor(current); 1553: removeNode(current); 1554: } 1555: } 1556: 1557: public Comparator comparator() 1558: { 1559: return comparator; 1560: } 1561: 1562: public boolean containsKey(Object key) 1563: { 1564: return keyInRange(key) && TreeMap.this.containsKey(key); 1565: } 1566: 1567: public boolean containsValue(Object value) 1568: { 1569: Node node = lowestGreaterThan(minKey, true); 1570: Node max = lowestGreaterThan(maxKey, false); 1571: while (node != max) 1572: { 1573: if (equals(value, node.getValue())) 1574: return true; 1575: node = successor(node); 1576: } 1577: return false; 1578: } 1579: 1580: public Set entrySet() 1581: { 1582: if (entries == null) 1583: // Create an AbstractSet with custom implementations of those methods 1584: // that can be overriden easily and efficiently. 1585: entries = new AbstractSet() 1586: { 1587: public int size() 1588: { 1589: return SubMap.this.size(); 1590: } 1591: 1592: public Iterator iterator() 1593: { 1594: Node first = lowestGreaterThan(minKey, true); 1595: Node max = lowestGreaterThan(maxKey, false); 1596: return new TreeIterator(ENTRIES, first, max); 1597: } 1598: 1599: public void clear() 1600: { 1601: SubMap.this.clear(); 1602: } 1603: 1604: public boolean contains(Object o) 1605: { 1606: if (! (o instanceof Map.Entry)) 1607: return false; 1608: Map.Entry me = (Map.Entry) o; 1609: Object key = me.getKey(); 1610: if (! keyInRange(key)) 1611: return false; 1612: Node n = getNode(key); 1613: return n != nil && AbstractSet.equals(me.getValue(), n.value); 1614: } 1615: 1616: public boolean remove(Object o) 1617: { 1618: if (! (o instanceof Map.Entry)) 1619: return false; 1620: Map.Entry me = (Map.Entry) o; 1621: Object key = me.getKey(); 1622: if (! keyInRange(key)) 1623: return false; 1624: Node n = getNode(key); 1625: if (n != nil && AbstractSet.equals(me.getValue(), n.value)) 1626: { 1627: removeNode(n); 1628: return true; 1629: } 1630: return false; 1631: } 1632: }; 1633: return entries; 1634: } 1635: 1636: public Object firstKey() 1637: { 1638: Node node = lowestGreaterThan(minKey, true); 1639: if (node == nil || ! keyInRange(node.key)) 1640: throw new NoSuchElementException(); 1641: return node.key; 1642: } 1643: 1644: public Object get(Object key) 1645: { 1646: if (keyInRange(key)) 1647: return TreeMap.this.get(key); 1648: return null; 1649: } 1650: 1651: public SortedMap headMap(Object toKey) 1652: { 1653: if (! keyInRange(toKey)) 1654: throw new IllegalArgumentException("key outside range"); 1655: return new SubMap(minKey, toKey); 1656: } 1657: 1658: public Set keySet() 1659: { 1660: if (this.keys == null) 1661: // Create an AbstractSet with custom implementations of those methods 1662: // that can be overriden easily and efficiently. 1663: this.keys = new AbstractSet() 1664: { 1665: public int size() 1666: { 1667: return SubMap.this.size(); 1668: } 1669: 1670: public Iterator iterator() 1671: { 1672: Node first = lowestGreaterThan(minKey, true); 1673: Node max = lowestGreaterThan(maxKey, false); 1674: return new TreeIterator(KEYS, first, max); 1675: } 1676: 1677: public void clear() 1678: { 1679: SubMap.this.clear(); 1680: } 1681: 1682: public boolean contains(Object o) 1683: { 1684: if (! keyInRange(o)) 1685: return false; 1686: return getNode(o) != nil; 1687: } 1688: 1689: public boolean remove(Object o) 1690: { 1691: if (! keyInRange(o)) 1692: return false; 1693: Node n = getNode(o); 1694: if (n != nil) 1695: { 1696: removeNode(n); 1697: return true; 1698: } 1699: return false; 1700: } 1701: }; 1702: return this.keys; 1703: } 1704: 1705: public Object lastKey() 1706: { 1707: Node node = highestLessThan(maxKey); 1708: if (node == nil || ! keyInRange(node.key)) 1709: throw new NoSuchElementException(); 1710: return node.key; 1711: } 1712: 1713: public Object put(Object key, Object value) 1714: { 1715: if (! keyInRange(key)) 1716: throw new IllegalArgumentException("Key outside range"); 1717: return TreeMap.this.put(key, value); 1718: } 1719: 1720: public Object remove(Object key) 1721: { 1722: if (keyInRange(key)) 1723: return TreeMap.this.remove(key); 1724: return null; 1725: } 1726: 1727: public int size() 1728: { 1729: Node node = lowestGreaterThan(minKey, true); 1730: Node max = lowestGreaterThan(maxKey, false); 1731: int count = 0; 1732: while (node != max) 1733: { 1734: count++; 1735: node = successor(node); 1736: } 1737: return count; 1738: } 1739: 1740: public SortedMap subMap(Object fromKey, Object toKey) 1741: { 1742: if (! keyInRange(fromKey) || ! keyInRange(toKey)) 1743: throw new IllegalArgumentException("key outside range"); 1744: return new SubMap(fromKey, toKey); 1745: } 1746: 1747: public SortedMap tailMap(Object fromKey) 1748: { 1749: if (! keyInRange(fromKey)) 1750: throw new IllegalArgumentException("key outside range"); 1751: return new SubMap(fromKey, maxKey); 1752: } 1753: 1754: public Collection values() 1755: { 1756: if (this.values == null) 1757: // Create an AbstractCollection with custom implementations of those 1758: // methods that can be overriden easily and efficiently. 1759: this.values = new AbstractCollection() 1760: { 1761: public int size() 1762: { 1763: return SubMap.this.size(); 1764: } 1765: 1766: public Iterator iterator() 1767: { 1768: Node first = lowestGreaterThan(minKey, true); 1769: Node max = lowestGreaterThan(maxKey, false); 1770: return new TreeIterator(VALUES, first, max); 1771: } 1772: 1773: public void clear() 1774: { 1775: SubMap.this.clear(); 1776: } 1777: }; 1778: return this.values; 1779: } 1780: } // class SubMap 1781: } // class TreeMap
GNU Classpath (0.20) |