| GNU Classpath (0.95) | |
| 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, 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: