Robust/src/ClassLibrary/MGC/gnu/TreeMap.java

   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 /**
  43  * This class provides a red-black tree implementation of the SortedMap
  44  * interface.  Elements in the Map will be sorted by either a user-provided
  45  * Comparator object, or by the natural ordering of the keys.
  46  *
  47  * The algorithms are adopted from Corman, Leiserson, and Rivest's
  48  * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
  49  * insertion and deletion of elements.  That being said, there is a large
  50  * enough constant coefficient in front of that "log n" (overhead involved
  51  * in keeping the tree balanced), that TreeMap may not be the best choice
  52  * for small collections. If something is already sorted, you may want to
  53  * just use a LinkedHashMap to maintain the order while providing O(1) access.
  54  *
  55  * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
  56  * only if a Comparator is used which can deal with them; natural ordering
  57  * cannot cope with null.  Null values are always allowed. Note that the
  58  * ordering must be <i>consistent with equals</i> to correctly implement
  59  * the Map interface. If this condition is violated, the map is still
  60  * well-behaved, but you may have suprising results when comparing it to
  61  * other maps.<p>
  62  *
  63  * This implementation is not synchronized. If you need to share this between
  64  * multiple threads, do something like:<br>
  65  * <code>SortedMap m
  66  *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
  67  *
  68  * The iterators are <i>fail-fast</i>, meaning that any structural
  69  * modification, except for <code>remove()</code> called on the iterator
  70  * itself, cause the iterator to throw a
  71  * <code>ConcurrentModificationException</code> rather than exhibit
  72  * non-deterministic behavior.
  73  *
  74  * @author Jon Zeppieri
  75  * @author Bryce McKinlay
  76  * @author Eric Blake (ebb9@email.byu.edu)
  77  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  78  * @see Map
  79  * @see HashMap
  80  * @see Hashtable
  81  * @see LinkedHashMap
  82  * @see Comparable
  83  * @see Comparator
  84  * @see Collection
  85  * @see Collections#synchronizedSortedMap(SortedMap)
  86  * @since 1.2
  87  * @status updated to 1.6
  88  */
  89 public class TreeMap//<K, V> extends AbstractMap<K, V>
  90   implements Map//, SortedMap //NavigableMap<K, V>, Cloneable, Serializable
  91 {
  92   // Implementation note:
  93   // A red-black tree is a binary search tree with the additional properties
  94   // that all paths to a leaf node visit the same number of black nodes,
  95   // and no red node has red children. To avoid some null-pointer checks,
  96   // we use the special node nil which is always black, has no relatives,
  97   // and has key and value of null (but is not equal to a mapping of null).
  98
  99   /**
 100    * Compatible with JDK 1.2.
 101    */
 102   private static final long serialVersionUID = 919286545866124006L;
 103
 104   /**
 105    * Color status of a node. Package visible for use by nested classes.
 106    */
 107   static final int RED = -1,
 108                    BLACK = 1;
 109
 110   /**
 111    * Sentinal node, used to avoid null checks for corner cases and make the
 112    * delete rebalance code simpler. The rebalance code must never assign
 113    * the parent, left, or right of nil, but may safely reassign the color
 114    * to be black. This object must never be used as a key in a TreeMap, or
 115    * it will break bounds checking of a SubMap.
 116    */
 117   static final TreeNode nil = new TreeNode(/*null, null, */BLACK);
 118   static
 119     {
 120       // Nil is self-referential, so we must initialize it after creation.
 121       nil.parent = nil;
 122       nil.left = nil;
 123       nil.right = nil;
 124     }
 125
 126   /**
 127    * The root node of this TreeMap.
 128    */
 129   private transient TreeNode root;
 130
 131   /**
 132    * The size of this TreeMap. Package visible for use by nested classes.
 133    */
 134   transient int size;
 135
 136   /**
 137    * The cache for {@link #entrySet()}.
 138    */
 139   //private transient Set<Map.Entry<K,V>> entries;
 140
 141   /**
 142    * The cache for {@link #descendingMap()}.
 143    */
 144   //private transient NavigableMap<K,V> descendingMap;
 145
 146   /**
 147    * The cache for {@link #navigableKeySet()}.
 148    */
 149   //private transient NavigableSet<K> nKeys;
 150
 151   /**
 152    * Counts the number of modifications this TreeMap has undergone, used
 153    * by Iterators to know when to throw ConcurrentModificationExceptions.
 154    * Package visible for use by nested classes.
 155    */
 156   transient int modCount;
 157
 158   /**
 159    * This TreeMap's comparator, or null for natural ordering.
 160    * Package visible for use by nested classes.
 161    * @serial the comparator ordering this tree, or null
 162    */
 163   //final Comparator<? super K> comparator;
 164
 165   /**
 166    * Instantiate a new TreeMap with no elements, using the keys' natural
 167    * ordering to sort. All entries in the map must have a key which implements
 168    * Comparable, and which are <i>mutually comparable</i>, otherwise map
 169    * operations may throw a {@link ClassCastException}. Attempts to use
 170    * a null key will throw a {@link NullPointerException}.
 171    *
 172    * @see Comparable
 173    */
 174   public TreeMap()
 175   {
 176     /*this((Comparator) null);
 177   }
 178
 179   /**
 180    * Instantiate a new TreeMap with no elements, using the provided comparator
 181    * to sort. All entries in the map must have keys which are mutually
 182    * comparable by the Comparator, otherwise map operations may throw a
 183    * {@link ClassCastException}.
 184    *
 185    * @param c the sort order for the keys of this map, or null
 186    *        for the natural order
 187    */
 188   /*public TreeMap(Comparator<? super K> c)
 189   {
 190     comparator = c;*/
 191     fabricateTree(0);
 192   }
 193
 194   /**
 195    * Instantiate a new TreeMap, initializing it with all of the elements in
 196    * the provided Map.  The elements will be sorted using the natural
 197    * ordering of the keys. This algorithm runs in n*log(n) time. All entries
 198    * in the map must have keys which implement Comparable and are mutually
 199    * comparable, otherwise map operations may throw a
 200    * {@link ClassCastException}.
 201    *
 202    * @param map a Map, whose entries will be put into this TreeMap
 203    * @throws ClassCastException if the keys in the provided Map are not
 204    *         comparable
 205    * @throws NullPointerException if map is null
 206    * @see Comparable
 207    */
 208   /*public TreeMap(Map<? extends K, ? extends V> map)
 209   {
 210     this((Comparator) null);
 211     putAll(map);
 212   }*/
 213
 214   /**
 215    * Instantiate a new TreeMap, initializing it with all of the elements in
 216    * the provided SortedMap.  The elements will be sorted using the same
 217    * comparator as in the provided SortedMap. This runs in linear time.
 218    *
 219    * @param sm a SortedMap, whose entries will be put into this TreeMap
 220    * @throws NullPointerException if sm is null
 221    */
 222   /*public TreeMap(SortedMap<K, ? extends V> sm)
 223   {
 224     this(sm.comparator());
 225     int pos = sm.size();
 226     Iterator itr = sm.entrySet().iterator();
 227
 228     fabricateTree(pos);
 229     Node node = firstNode();
 230
 231     while (--pos >= 0)
 232       {
 233         Map.Entry me = (Map.Entry) itr.next();
 234         node.key = me.getKey();
 235         node.value = me.getValue();
 236         node = successor(node);
 237       }
 238   }*/
 239
 240   /**
 241    * Clears the Map so it has no keys. This is O(1).
 242    */
 243   public void clear()
 244   {
 245     if (size > 0)
 246       {
 247         modCount++;
 248         root = nil;
 249         size = 0;
 250       }
 251   }
 252
 253   /**
 254    * Returns a shallow clone of this TreeMap. The Map itself is cloned,
 255    * but its contents are not.
 256    *
 257    * @return the clone
 258    */
 259   /*public Object clone()
 260   {
 261     TreeMap copy = null;
 262     try
 263       {
 264         copy = (TreeMap) super.clone();
 265       }
 266     catch (CloneNotSupportedException x)
 267       {
 268       }
 269     copy.entries = null;
 270     copy.fabricateTree(size);
 271
 272     Node node = firstNode();
 273     Node cnode = copy.firstNode();
 274
 275     while (node != nil)
 276       {
 277         cnode.key = node.key;
 278         cnode.value = node.value;
 279         node = successor(node);
 280         cnode = copy.successor(cnode);
 281       }
 282     return copy;
 283   }*/
 284
 285   /**
 286    * Return the comparator used to sort this map, or null if it is by
 287    * natural order.
 288    *
 289    * @return the map's comparator
 290    */
 291   /*public Comparator<? super K> comparator()
 292   {
 293     return comparator;
 294   }*/
 295
 296   /**
 297    * Returns true if the map contains a mapping for the given key.
 298    *
 299    * @param key the key to look for
 300    * @return true if the key has a mapping
 301    * @throws ClassCastException if key is not comparable to map elements
 302    * @throws NullPointerException if key is null and the comparator is not
 303    *         tolerant of nulls
 304    */
 305   public boolean containsKey(Object key)
 306   {
 307     return getNode(key) != nil;
 308   }
 309
 310   /**
 311    * Returns true if the map contains at least one mapping to the given value.
 312    * This requires linear time.
 313    *
 314    * @param value the value to look for
 315    * @return true if the value appears in a mapping
 316    */
 317   /*public boolean containsValue(Object value)
 318   {
 319     Node node = firstNode();
 320     while (node != nil)
 321       {
 322         if (equals(value, node.value))
 323           return true;
 324         node = successor(node);
 325       }
 326     return false;
 327   }*/
 328
 329   /**
 330    * Returns a "set view" of this TreeMap's entries. The set is backed by
 331    * the TreeMap, so changes in one show up in the other.  The set supports
 332    * element removal, but not element addition.<p>
 333    *
 334    * Note that the iterators for all three views, from keySet(), entrySet(),
 335    * and values(), traverse the TreeMap in sorted sequence.
 336    *
 337    * @return a set view of the entries
 338    * @see #keySet()
 339    * @see #values()
 340    * @see Map.Entry
 341    */
 342   /*public Set<Map.Entry<K,V>> entrySet()
 343   {
 344     if (entries == null)
 345       // Create an AbstractSet with custom implementations of those methods
 346       // that can be overriden easily and efficiently.
 347       entries = new NavigableEntrySet();
 348     return entries;
 349   }*/
 350
 351   /**
 352    * Returns the first (lowest) key in the map.
 353    *
 354    * @return the first key
 355    * @throws NoSuchElementException if the map is empty
 356    */
 357   public Object firstKey()
 358   {
 359     if (root == nil)
 360       throw new /*NoSuchElement*/Exception("NoSuchElementException");
 361     return firstNode().key;
 362   }
 363
 364   /**
 365    * Return the value in this TreeMap associated with the supplied key,
 366    * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
 367    * could also be null, you must use containsKey to see if this key
 368    * actually maps to something.
 369    *
 370    * @param key the key for which to fetch an associated value
 371    * @return what the key maps to, if present
 372    * @throws ClassCastException if key is not comparable to elements in the map
 373    * @throws NullPointerException if key is null but the comparator does not
 374    *         tolerate nulls
 375    * @see #put(Object, Object)
 376    * @see #containsKey(Object)
 377    */
 378   public Object get(Object key)
 379   {
 380     // Exploit fact that nil.value == null.
 381     return getNode(key).value;
 382   }
 383
 384   /**
 385    * Returns the last (highest) key in the map.
 386    *
 387    * @return the last key
 388    * @throws NoSuchElementException if the map is empty
 389    */
 390   public Object lastKey()
 391   {
 392     if (root == nil)
 393       throw new /*NoSuchElement*/Exception("NoSuchElementException empty");
 394     return lastNode().key;
 395   }
 396
 397   /**
 398    * Puts the supplied value into the Map, mapped by the supplied key.
 399    * The value may be retrieved by any object which <code>equals()</code>
 400    * this key. NOTE: Since the prior value could also be null, you must
 401    * first use containsKey if you want to see if you are replacing the
 402    * key's mapping.
 403    *
 404    * @param key the key used to locate the value
 405    * @param value the value to be stored in the Map
 406    * @return the prior mapping of the key, or null if there was none
 407    * @throws ClassCastException if key is not comparable to current map keys
 408    * @throws NullPointerException if key is null, but the comparator does
 409    *         not tolerate nulls
 410    * @see #get(Object)
 411    * @see Object#equals(Object)
 412    */
 413   public Object put(Object key, Object value)
 414   {
 415     TreeNode current = root;
 416     TreeNode parent = nil;
 417     int comparison = 0;
 418
 419     // Find new node's parent.
 420     while (current != nil)
 421       {
 422         parent = current;
 423         comparison = compare(key, current.key);
 424         if (comparison > 0)
 425           current = current.right;
 426         else if (comparison < 0)
 427           current = current.left;
 428         else // Key already in tree.
 429           return current.setValue(value);
 430       }
 431
 432     // Set up new node.
 433     TreeNode n = new TreeNode(key, value, RED);
 434     n.parent = parent;
 435
 436     // Insert node in tree.
 437     modCount++;
 438     size++;
 439     if (parent == nil)
 440       {
 441         // Special case inserting into an empty tree.
 442         root = n;
 443         return null;
 444       }
 445     if (comparison > 0) {
 446       parent.right = n;
 447     } else {
 448       parent.left = n;
 449     }
 450
 451     // Rebalance after insert.
 452     insertFixup(n);
 453     return null;
 454   }
 455
 456   /**
 457    * Copies all elements of the given map into this TreeMap.  If this map
 458    * already has a mapping for a key, the new mapping replaces the current
 459    * one.
 460    *
 461    * @param m the map to be added
 462    * @throws ClassCastException if a key in m is not comparable with keys
 463    *         in the map
 464    * @throws NullPointerException if a key in m is null, and the comparator
 465    *         does not tolerate nulls
 466    */
 467   /*public void putAll(Map<? extends K, ? extends V> m)
 468   {
 469     Iterator itr = m.entrySet().iterator();
 470     int pos = m.size();
 471     while (--pos >= 0)
 472       {
 473         Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
 474         put(e.getKey(), e.getValue());
 475       }
 476   }*/
 477
 478   /**
 479    * Removes from the TreeMap and returns the value which is mapped by the
 480    * supplied key. If the key maps to nothing, then the TreeMap remains
 481    * unchanged, and <code>null</code> is returned. NOTE: Since the value
 482    * could also be null, you must use containsKey to see if you are
 483    * actually removing a mapping.
 484    *
 485    * @param key the key used to locate the value to remove
 486    * @return whatever the key mapped to, if present
 487    * @throws ClassCastException if key is not comparable to current map keys
 488    * @throws NullPointerException if key is null, but the comparator does
 489    *         not tolerate nulls
 490    */
 491   public Object remove(Object key)
 492   {
 493     TreeNode n = getNode(key);
 494     if (n == nil)
 495       return null;
 496     // Note: removeNode can alter the contents of n, so save value now.
 497     Object result = n.value;
 498     removeNode(n);
 499     return result;
 500   }
 501
 502   /**
 503    * Returns the number of key-value mappings currently in this Map.
 504    *
 505    * @return the size
 506    */
 507   public int size()
 508   {
 509     return size;
 510   }
 511
 512   /**
 513    * Maintain red-black balance after deleting a node.
 514    *
 515    * @param node the child of the node just deleted, possibly nil
 516    * @param parent the parent of the node just deleted, never nil
 517    */
 518   private void deleteFixup(TreeNode node, TreeNode parent)
 519   {
 520     // if (parent == nil)
 521     //   throw new InternalError();
 522     // If a black node has been removed, we need to rebalance to avoid
 523     // violating the "same number of black nodes on any path" rule. If
 524     // node is red, we can simply recolor it black and all is well.
 525     while (node != root && node.color == BLACK)
 526       {
 527         if (node == parent.left)
 528           {
 529             // Rebalance left side.
 530             TreeNode sibling = parent.right;
 531             // if (sibling == nil)
 532             //   throw new InternalError();
 533             if (sibling.color == RED)
 534               {
 535                 // Case 1: Sibling is red.
 536                 // Recolor sibling and parent, and rotate parent left.
 537                 sibling.color = BLACK;
 538                 parent.color = RED;
 539                 rotateLeft(parent);
 540                 sibling = parent.right;
 541               }
 542
 543             if (sibling.left.color == BLACK && sibling.right.color == BLACK)
 544               {
 545                 // Case 2: Sibling has no red children.
 546                 // Recolor sibling, and move to parent.
 547                 sibling.color = RED;
 548                 node = parent;
 549                 parent = parent.parent;
 550               }
 551             else
 552               {
 553                 if (sibling.right.color == BLACK)
 554                   {
 555                     // Case 3: Sibling has red left child.
 556                     // Recolor sibling and left child, rotate sibling right.
 557                     sibling.left.color = BLACK;
 558                     sibling.color = RED;
 559                     rotateRight(sibling);
 560                     sibling = parent.right;
 561                   }
 562                 // Case 4: Sibling has red right child. Recolor sibling,
 563                 // right child, and parent, and rotate parent left.
 564                 sibling.color = parent.color;
 565                 parent.color = BLACK;
 566                 sibling.right.color = BLACK;
 567                 rotateLeft(parent);
 568                 node = root; // Finished.
 569               }
 570           }
 571         else
 572           {
 573             // Symmetric "mirror" of left-side case.
 574             TreeNode sibling = parent.left;
 575             // if (sibling == nil)
 576             //   throw new InternalError();
 577             if (sibling.color == RED)
 578               {
 579                 // Case 1: Sibling is red.
 580                 // Recolor sibling and parent, and rotate parent right.
 581                 sibling.color = BLACK;
 582                 parent.color = RED;
 583                 rotateRight(parent);
 584                 sibling = parent.left;
 585               }
 586
 587             if (sibling.right.color == BLACK && sibling.left.color == BLACK)
 588               {
 589                 // Case 2: Sibling has no red children.
 590                 // Recolor sibling, and move to parent.
 591                 sibling.color = RED;
 592                 node = parent;
 593                 parent = parent.parent;
 594               }
 595             else
 596               {
 597                 if (sibling.left.color == BLACK)
 598                   {
 599                     // Case 3: Sibling has red right child.
 600                     // Recolor sibling and right child, rotate sibling left.
 601                     sibling.right.color = BLACK;
 602                     sibling.color = RED;
 603                     rotateLeft(sibling);
 604                     sibling = parent.left;
 605                   }
 606                 // Case 4: Sibling has red left child. Recolor sibling,
 607                 // left child, and parent, and rotate parent right.
 608                 sibling.color = parent.color;
 609                 parent.color = BLACK;
 610                 sibling.left.color = BLACK;
 611                 rotateRight(parent);
 612                 node = root; // Finished.
 613               }
 614           }
 615       }
 616     node.color = BLACK;
 617   }
 618
 619   /**
 620    * Construct a perfectly balanced tree consisting of n "blank" nodes. This
 621    * permits a tree to be generated from pre-sorted input in linear time.
 622    *
 623    * @param count the number of blank nodes, non-negative
 624    */
 625   private void fabricateTree(final int count)
 626   {
 627     if (count == 0)
 628       {
 629         root = nil;
 630         size = 0;
 631         return;
 632       }
 633
 634     // We color every row of nodes black, except for the overflow nodes.
 635     // I believe that this is the optimal arrangement. We construct the tree
 636     // in place by temporarily linking each node to the next node in the row,
 637     // then updating those links to the children when working on the next row.
 638
 639     // Make the root node.
 640     root = new TreeNode(null, null, BLACK);
 641     size = count;
 642     TreeNode row = root;
 643     int rowsize;
 644
 645     // Fill each row that is completely full of nodes.
 646     for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
 647       {
 648         TreeNode parent = row;
 649         TreeNode last = null;
 650         for (int i = 0; i < rowsize; i += 2)
 651           {
 652             TreeNode left = new TreeNode(null, null, BLACK);
 653             TreeNode right = new TreeNode(null, null, BLACK);
 654             left.parent = parent;
 655             left.right = right;
 656             right.parent = parent;
 657             parent.left = left;
 658             TreeNode next = parent.right;
 659             parent.right = right;
 660             parent = next;
 661             if (last != null)
 662               last.right = left;
 663             last = right;
 664           }
 665         row = row.left;
 666       }
 667
 668     // Now do the partial final row in red.
 669     int overflow = count - rowsize;
 670     TreeNode parent = row;
 671     int i;
 672     for (i = 0; i < overflow; i += 2)
 673       {
 674         TreeNode left = new TreeNode(null, null, RED);
 675         TreeNode right = new TreeNode(null, null, RED);
 676         left.parent = parent;
 677         right.parent = parent;
 678         parent.left = left;
 679         TreeNode next = parent.right;
 680         parent.right = right;
 681         parent = next;
 682       }
 683     // Add a lone left node if necessary.
 684     if (i - overflow == 0)
 685       {
 686         TreeNode left = new TreeNode(null, null, RED);
 687         left.parent = parent;
 688         parent.left = left;
 689         parent = parent.right;
 690         left.parent.right = nil;
 691       }
 692     // Unlink the remaining nodes of the previous row.
 693     while (parent != nil)
 694       {
 695         TreeNode next = parent.right;
 696         parent.right = nil;
 697         parent = next;
 698       }
 699   }
 700
 701   /**
 702    * Returns the first sorted node in the map, or nil if empty. Package
 703    * visible for use by nested classes.
 704    *
 705    * @return the first node
 706    */
 707   final TreeNode firstNode()
 708   {
 709     // Exploit fact that nil.left == nil.
 710     TreeNode node = root;
 711     while (node.left != nil)
 712       node = node.left;
 713     return node;
 714   }
 715
 716   /**
 717    * Return the node following the given one, or nil if there isn't one.
 718    * Package visible for use by nested classes.
 719    *
 720    * @param node the current node, not nil
 721    * @return the next node in sorted order
 722    */
 723   final TreeNode successor(TreeNode node)
 724   {
 725     if (node.right != nil)
 726       {
 727         node = node.right;
 728         while (node.left != nil)
 729           node = node.left;
 730         return node;
 731       }
 732
 733     TreeNode parent = node.parent;
 734     // Exploit fact that nil.right == nil and node is non-nil.
 735     while (node == parent.right)
 736       {
 737         node = parent;
 738         parent = parent.parent;
 739       }
 740     return parent;
 741   }
 742
 743
 744   /**
 745    * Return the TreeMap.Node associated with key, or the nil node if no such
 746    * node exists in the tree. Package visible for use by nested classes.
 747    *
 748    * @param key the key to search for
 749    * @return the node where the key is found, or nil
 750    */
 751   final TreeNode getNode(Object key)
 752   {
 753     TreeNode current = root;
 754     while (current != nil)
 755       {
 756         int comparison = compare(key, current.key);
 757         if (comparison > 0)
 758           current = current.right;
 759         else if (comparison < 0)
 760           current = current.left;
 761         else
 762           return current;
 763       }
 764     return current;
 765   }
 766
 767   final int compare(Object o1, Object o2)
 768   {
 769     if((o1 instanceof Integer) && (o2 instanceof Integer)) {
 770       return ((Integer)o1).compareTo((Integer)o2);
 771     } else if((o1 instanceof Long) && (o2 instanceof Long)) {
 772       return ((Long)o1).compareTo((Long)o2);
 773     } else if((o1 instanceof String) && (o2 instanceof String)) {
 774       return ((String)o1).compareTo((String)o2);
 775     }
 776     System.println("Compare non-int values in TreeMap.compare(Object, Object)");
 777     return 0;
 778   }
 779
 780   /**
 781    * Maintain red-black balance after inserting a new node.
 782    *
 783    * @param n the newly inserted node
 784    */
 785   private void insertFixup(TreeNode n)
 786   {
 787     // Only need to rebalance when parent is a RED node, and while at least
 788     // 2 levels deep into the tree (ie: node has a grandparent). Remember
 789     // that nil.color == BLACK.
 790     while (n.parent.color == RED && n.parent.parent != nil)
 791       {
 792         if (n.parent == n.parent.parent.left)
 793           {
 794             TreeNode uncle = n.parent.parent.right;
 795             // Uncle may be nil, in which case it is BLACK.
 796             if (uncle.color == RED)
 797               {
 798                 // Case 1. Uncle is RED: Change colors of parent, uncle,
 799                 // and grandparent, and move n to grandparent.
 800                 n.parent.color = BLACK;
 801                 uncle.color = BLACK;
 802                 uncle.parent.color = RED;
 803                 n = uncle.parent;
 804               }
 805             else
 806               {
 807                 if (n == n.parent.right)
 808                   {
 809                     // Case 2. Uncle is BLACK and x is right child.
 810                     // Move n to parent, and rotate n left.
 811                     n = n.parent;
 812                     rotateLeft(n);
 813                   }
 814                 // Case 3. Uncle is BLACK and x is left child.
 815                 // Recolor parent, grandparent, and rotate grandparent right.
 816                 n.parent.color = BLACK;
 817                 n.parent.parent.color = RED;
 818                 rotateRight(n.parent.parent);
 819               }
 820           }
 821         else
 822           {
 823             // Mirror image of above code.
 824             TreeNode uncle = n.parent.parent.left;
 825             // Uncle may be nil, in which case it is BLACK.
 826             if (uncle.color == RED)
 827               {
 828                 // Case 1. Uncle is RED: Change colors of parent, uncle,
 829                 // and grandparent, and move n to grandparent.
 830                 n.parent.color = BLACK;
 831                 uncle.color = BLACK;
 832                 uncle.parent.color = RED;
 833                 n = uncle.parent;
 834               }
 835             else
 836               {
 837                 if (n == n.parent.left)
 838                 {
 839                     // Case 2. Uncle is BLACK and x is left child.
 840                     // Move n to parent, and rotate n right.
 841                     n = n.parent;
 842                     rotateRight(n);
 843                   }
 844                 // Case 3. Uncle is BLACK and x is right child.
 845                 // Recolor parent, grandparent, and rotate grandparent left.
 846                 n.parent.color = BLACK;
 847                 n.parent.parent.color = RED;
 848                 rotateLeft(n.parent.parent);
 849               }
 850           }
 851       }
 852     root.color = BLACK;
 853   }
 854
 855   /**
 856    * Returns the last sorted node in the map, or nil if empty.
 857    *
 858    * @return the last node
 859    */
 860   public TreeNode lastNode()
 861   {
 862     // Exploit fact that nil.right == nil.
 863     TreeNode node = root;
 864     while (node.right != nil)
 865       node = node.right;
 866     return node;
 867   }
 868
 869   /**
 870    * Remove node from tree. This will increment modCount and decrement size.
 871    * Node must exist in the tree. Package visible for use by nested classes.
 872    *
 873    * @param node the node to remove
 874    */
 875   final void removeNode(TreeNode node)
 876   {
 877     TreeNode splice;
 878     TreeNode child;
 879
 880     modCount++;
 881     size--;
 882
 883     // Find splice, the node at the position to actually remove from the tree.
 884     if (node.left == nil)
 885       {
 886         // Node to be deleted has 0 or 1 children.
 887         splice = node;
 888         child = node.right;
 889       }
 890     else if (node.right == nil)
 891       {
 892         // Node to be deleted has 1 child.
 893         splice = node;
 894         child = node.left;
 895       }
 896     else
 897       {
 898         // Node has 2 children. Splice is node's predecessor, and we swap
 899         // its contents into node.
 900         splice = node.left;
 901         while (splice.right != nil)
 902           splice = splice.right;
 903         child = splice.left;
 904         node.key = splice.key;
 905         node.value = splice.value;
 906       }
 907
 908     // Unlink splice from the tree.
 909     TreeNode parent = splice.parent;
 910     if (child != nil)
 911       child.parent = parent;
 912     if (parent == nil)
 913       {
 914         // Special case for 0 or 1 node remaining.
 915         root = child;
 916         return;
 917       }
 918     if (splice == parent.left)
 919       parent.left = child;
 920     else
 921       parent.right = child;
 922
 923     if (splice.color == BLACK)
 924       deleteFixup(child, parent);
 925   }
 926
 927   /**
 928    * Rotate node n to the left.
 929    *
 930    * @param node the node to rotate
 931    */
 932   private void rotateLeft(TreeNode node)
 933   {
 934     TreeNode child = node.right;
 935     // if (node == nil || child == nil)
 936     //   throw new InternalError();
 937
 938     // Establish node.right link.
 939     node.right = child.left;
 940     if (child.left != nil)
 941       child.left.parent = node;
 942
 943     // Establish child->parent link.
 944     child.parent = node.parent;
 945     if (node.parent != nil)
 946       {
 947         if (node == node.parent.left)
 948           node.parent.left = child;
 949         else
 950           node.parent.right = child;
 951       }
 952     else
 953       root = child;
 954
 955     // Link n and child.
 956     child.left = node;
 957     node.parent = child;
 958   }
 959
 960   /**
 961    * Rotate node n to the right.
 962    *
 963    * @param node the node to rotate
 964    */
 965   private void rotateRight(TreeNode node)
 966   {
 967     TreeNode child = node.left;
 968     // if (node == nil || child == nil)
 969     //   throw new InternalError();
 970
 971     // Establish node.left link.
 972     node.left = child.right;
 973     if (child.right != nil)
 974       child.right.parent = node;
 975
 976     // Establish child->parent link.
 977     child.parent = node.parent;
 978     if (node.parent != nil)
 979       {
 980         if (node == node.parent.right)
 981           node.parent.right = child;
 982         else
 983           node.parent.left = child;
 984       }
 985     else
 986       root = child;
 987
 988     // Link n and child.
 989     child.right = node;
 990     node.parent = child;
 991   }
 992
 993   public TreeSubMap subMap(Object fromKey, Object toKey)
 994   {
 995     return new TreeSubMap(this, fromKey, toKey);
 996   }
 997
 998   /**
 999    * Find the "lowest" node which is &gt;= key. If key is nil, return either
1000    * nil or the first node, depending on the parameter first.  Package visible
1001    * for use by nested classes.
1002    *
1003    * @param key the lower bound, inclusive
1004    * @param first true to return the first element instead of nil for nil key
1005    * @return the next node
1006    */
1007   final TreeNode lowestGreaterThan(Object key, boolean first)
1008   {
1009     return lowestGreaterThan(key, first, true);
1010   }
1011
1012   /**
1013    * Find the "lowest" node which is &gt; (or equal to, if <code>equal</code>
1014    * is true) key. If key is nil, return either nil or the first node, depending
1015    * on the parameter first.  Package visible for use by nested classes.
1016    *
1017    * @param key the lower bound, inclusive
1018    * @param first true to return the first element instead of nil for nil key
1019    * @param equal true if the key should be returned if found.
1020    * @return the next node
1021    */
1022   final TreeNode lowestGreaterThan(Object key, boolean first, boolean equal)
1023   {
1024     if (key == nil)
1025       return first ? firstNode() : nil;
1026
1027     TreeNode last = nil;
1028     TreeNode current = root;
1029     int comparison = 0;
1030
1031     while (current != nil)
1032       {
1033         last = current;
1034         comparison = compare(key, current.key);
1035         if (comparison > 0)
1036           current = current.right;
1037         else if (comparison < 0)
1038           current = current.left;
1039         else
1040           return (equal ? current : successor(current));
1041       }
1042     return comparison > 0 ? successor(last) : last;
1043   }
1044
1045   /* 0=keys, 1=values, 2=entities */
1046   public Iterator iterator(int type) {
1047     return (Iterator)(new TreeMapIterator(this, type));
1048   }
1049 } // class TreeMap