/*****************************************************************************\
*  RedBlack.java                   by: TheSilverDirk / Michael Conrad         *
*                                                  and                        *
*                                           Prof. John Franco                 *
*                                                 ECECS                       *
*                                        University of Cincinnati             *
*                                        franco@gauss.ececs.uc.edu            *
*                                                                             *
*  Created: 12/03/2002             Last Modified: 12/10/2002                  *
*                                                                             *
*  Copyright (c) 2002 by Michael Conrad and John Franco                       *
*       This code may be freely distributed under the terms of the            *
*       GNU General Public License.                                           *
*                                                                             *
*  Based on the description of Red-Black Tree algorithms found in             *
*       Berman and Paul.                                                      *
*       Sequential and Parallel Algorithms.                                   *
*       Brooks/Cole PWS Publishing Co,                                        *
*       1997 (ISBN:0-534-94674-7).                                            *
*                                                                             *
*  This is a special version which reads numbers from a parameter list and    *
*  installs objects with those numbers into the red black tree upon startup.  *
*  A sample applet tag looks like this:                                       *
*                                                                             *
*  <applet code="RedBlack.class" width=1024 height=450>                       *
*  <param name="args" value="12 6 25 10 3 18 55 11 7 4 2 15 21 33">           *
*  </applet>                                                                  *
*                                                                             *
\*****************************************************************************/
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.*;
import javax.swing.*;

/*****************************************************************************\
 *  This section contains interfaces which customize the type of object      *
 *  being stored in the Red-Black tree and implementations of those          *
 *  for simple Integer objects.  All storable objects must implement         *
 *  interface TreeObject which requires identity and value (for order).      *
 *  For comparing objects, interfaces RBTree_inorder_class and               *
 *  RBTree_compare_class must be implemented (they prototype two comparison  *
 *  methods).                                                                *
\*****************************************************************************/

// All storeable data items must implement the TreeObject interface
interface TreeObject {
   int getValue ();
   String getIdent ();
}

// In this example, we are storing simple integer objects
class IntObject implements TreeObject {
   int x;
   IntObject (int x) { this.x = x; }
   public int getValue () { return x; }
   public String getIdent () { return String.valueOf(x); }
}

// This interface prototypes the method for comparing one object
// against another to determine which is of lower order
interface RBTree_inorder_class {
   boolean compare (TreeObject obj1, TreeObject obj2);
}

// In this example of simple integer objects the above interface is
// implemented as follows
class IntInorderObject implements RBTree_inorder_class {
   public boolean compare (TreeObject obj1, TreeObject obj2) {
      return obj1.getValue() <= obj2.getValue();
   }
}

// We request a second version of comparison which compares the order number
// of single objects against a previously stored value
interface RBTree_compare_class {
   int evaluate (TreeObject object);
}

// An implementation of the above for the simple integers.
class IntCompare implements RBTree_compare_class {
   int x;
   IntCompare (int x) { this.x = x; }

   public int evaluate (TreeObject object) {
      if (x < object.getValue()) return -1;
      if (x > object.getValue()) return 1;
      return 0;
   }
}

class TO { 
   public boolean value; 
   TO (boolean b) { value = b; }
}

/*****************************************************************************\
 *  This section of code contains the red-black tree library functions and   *
 *  classes.  They are written to allow any type of data objects with some   *
 *  well defined notion of order, expressed as a positive integer value, to  *
 *  be stored in a red-black tree.                                           *
\*****************************************************************************/

// Dot objects provide the infrastruture for maintaining interesting data
// objects (implementing TreeObject interface) and rendering information.
class Dot {
   int   level, indent;
   float left, top;
   Dot   leftTree, rightTree, parent, sentinel;
   Color color, disp_color;
   TreeObject object;
   boolean isCurrent;

   public Dot () { }

   public Dot (Dot sentinel) {  
      disp_color = color = Color.blue;  
      this.sentinel = sentinel; 
      level = 0;
      indent = 0;
      isCurrent = false;
   }

   public Dot (int n, Color clr) {
      color = disp_color = clr;
      object = new IntObject(n);
      leftTree = null;
      rightTree = null;
   }

   public Dot (RBTree tree, int n, Color clr) {
      sentinel = tree.sentinel;
      leftTree = sentinel;
      rightTree = sentinel;
      color = disp_color = clr;
      object = new IntObject(n);
      level = 0;
      indent = 0;
      parent = tree.rootSentinel;
      left = 0;
      top = 0;
   }

   // Finds the next lowest ordered stored object.  Returns null if
   // none exists.
   // Used when deleting a node to find which node should take its place
   // in the tree.
   public Dot getPrev() {
      Dot current = this;
      // If we are not at a leaf, move to the right-most node
      // in the tree to the left of this node.
      if (current.leftTree.leftTree != current.leftTree) {
         current = current.leftTree;
         while (current.rightTree.rightTree != current.rightTree)
            current = current.rightTree;
         return current;
      }
      // Else walk up the tree until we see a parent node to the left
      else {
         Dot cur_parent = current.parent;
         while (cur_parent.leftTree == current) {
            current = cur_parent;
            cur_parent= cur_parent.parent;
            // Check for rootSentinel
            if (cur_parent == null) return null;
         }
         return cur_parent;
      }
   }

   // Finds the next highest stored object.  Returns null if none exists.
   // Used when deleting a node to find which node should take its place
   // in the tree.
   public Dot getNext() {
      Dot current = this;
      // If we are not at a leaf, move to the left-most node
      //  in the tree to the right of this node.
      if (current.rightTree.rightTree != current.rightTree) {
         current = current.rightTree;
         while (current.leftTree.leftTree != current.leftTree)
            current = current.leftTree;
         return current;
      }
      // Else walk up the tree until we see a parent node to the right
      else {
         Dot cur_parent = current.parent;
         while (cur_parent.rightTree == current) {
            current = cur_parent;
            cur_parent = current.parent;
         }
         // Check for the rootSentinel
         if (cur_parent.parent == null) return null;
         return cur_parent;
      }
   }

   public void rightRotate( ) {
      if (this.parent.leftTree == this)
         leftSide_RightRotate( );
      else
         rightSide_RightRotate( );
   }

   public void leftRotate( ) {
      if (this.parent.leftTree == this)
         leftSide_LeftRotate( );
      else
         rightSide_LeftRotate( );
   }

   public void leftSide_LeftRotate() {
      Dot temp = this.parent; // temp is used for parent
      Dot child = this.rightTree;

      temp.leftTree = child;
      child.parent = temp;

      temp = child.leftTree; // temp is now used for grandchild
      this.rightTree = temp;
      temp.parent = this;
      
      child.leftTree = this;
      this.parent = child;
   }

   public void leftSide_RightRotate() {
      Dot temp = this.parent; // temp is used for parent
      Dot child = this.leftTree;

      temp.leftTree = child;
      child.parent = temp;

      temp = child.rightTree; // temp is now used for grandchild
      this.leftTree = temp;
      temp.parent = this;
      
      child.rightTree = this;
      this.parent = child;
   }

   public void rightSide_RightRotate( ) {
      Dot temp = this.parent; // temp is used for parent
      Dot child = this.leftTree;

      temp.rightTree = child;
      child.parent = temp;

      temp = child.rightTree; // temp is now used for grandchild
      this.leftTree = temp;
      temp.parent = this;

      child.rightTree = this;
      this.parent = child;
   }

   public void rightSide_LeftRotate( ) {
      Dot temp = this.parent; // temp is used for parent
      Dot child = this.rightTree;

      temp.rightTree = child;
      child.parent = temp;

      temp = child.leftTree; // temp is now used for grandchild
      this.rightTree= temp;
      temp.parent = this;

      child.leftTree = this;
      this.parent = child;
   }
}

// The next four classes bear the brunt.  They extend a Stream class in order
// to be able to interrupt their operation to display intermediate changes in 
// the red-black tree.  To use these classes without the GUI remove all 
// occurrences of "rbt.level()", "putIt(tot)", and "putIt(null)".  The 
// additional slight change of not extending the Stream class, moving the 
// "run" functions inside the RBTree and Dot classes as needed (replacing 
// the name "run" with a descriptive method name), and invoking those methods 
// instead of grabbing a new object of one of these classes and invoking 
// "next" will streamline the code even further.  
//
// Used when adding a node to put the tree in balance
class Balance extends Stream {
   RedBlack gui;
   // current is the parent node of the node just added.  The child is red.
   Dot current;
   RBTree rbt;
   TO tot = new TO(true);

   public Balance (RedBlack gui, RBTree rbt, Dot dot) { 
      this.gui = gui;
      this.rbt = rbt;
      current = dot; 
   }

   void setCurrent (Dot dot) {
      if (dot == rbt.rootSentinel) dot = dot.leftTree;
      if (dot != null && dot.color == Color.black) dot = null;
      for (int i=0 ; i < gui.ndots ; i++) {
	 if (gui.dot[i] != null) {
	    gui.dot[i].isCurrent = 
	       (gui.dot[i] != dot || dot == null) ? false : true;
	 }
      }
   }

   public void showRule (Dot current, boolean exchange) {
      boolean parent_on_left = false;
      boolean red_child_on_left = false;
      boolean sibling_red = false;
      int sibling_value = 0;
      int red_child_value = 0;
      boolean isRoot = false;

      try {
	 if (current.parent == rbt.rootSentinel) isRoot = true;

	 if (current.parent != null && 
	     current.parent.leftTree == current) {
	    parent_on_left = false;
	 } else if (current.parent != null && 
		    current.parent.rightTree == current) {
	    parent_on_left = true;
	 }
	 
	 if (!parent_on_left) {
	    if (current.parent != null)
	       sibling_red = (current.parent.rightTree.color == Color.red) ?
		  true : false;
	    if (current.parent != null &&
		current.parent.rightTree.object != null)
	       sibling_value = current.parent.rightTree.object.getValue();
	 } else {
	    if (current.parent != null)
	       sibling_red = (current.parent.leftTree.color == Color.red) ?
		  true : false;
	    if (current.parent != null &&
		current.parent.leftTree.object != null)
	       sibling_value = current.parent.leftTree.object.getValue();
	 }
	 if (current.leftTree.color == Color.red) {
	    red_child_on_left = true;
	    if (current.leftTree.object != null)
	       red_child_value = current.leftTree.object.getValue();
	 } else if (current.rightTree.color == Color.red) {
	    red_child_on_left = false;
	    if (current.rightTree.object != null)
	       red_child_value = current.rightTree.object.getValue();
	 }
	 
	 if (exchange) {
	    gui.rules.setText("<3.2> Exchange colors"); 
	    if (current == rbt.rootSentinel) current = current.leftTree;
	    setCurrent(current);
	    if (current.leftTree.color == Color.red) {
	       gui.huh.setText("The red left child "+
			       current.leftTree.object.getValue()+
			       " of red current "+
			       current.object.getValue()+
			       " has a black node count that is too low "+
			       "by 1.  Swapping colors between current "+
			       "and its right child "+
			       current.rightTree.object.getValue()+
			       "\neliminates the "+
			       "black count shortfall and the double "+
			       "red violation.  The black node count "+
			       "of the right child of current is unaffected.");
	    } else {
	       gui.huh.setText("The red right child "+
			       current.rightTree.object.getValue()+
			       " of red current "+
			       current.object.getValue()+
			       " has a black node count that is too low "+
			       "by 1.  Swapping colors between current "+
			       "and its left child "+
			       current.leftTree.object.getValue()+
			       "\neliminates the "+
			       "black count shortfall and the double "+
			       "red violation.  The black node count "+
			       "of the left child of current is unaffected.");
	    }
	 } else if (isRoot) {
	    if (current.color == Color.red) {
	       gui.rules.setText("<4> Color the root black");
	       gui.huh.setText("The root can always be made black without "+
			       "affecting the black node count of any path.");
	       gui.invariant.setText("");
	    } else {
	       gui.rules.setText("Nothing to do - hit 'Next Step' again");
	       gui.huh.setText("");
	       gui.invariant.setText("");
	    }
	 } else if (rbt.rootSentinel == current) {
	    if (rbt.rootSentinel.leftTree.color == Color.red) {
	       gui.rules.setText("<4> Color the root black");
	       gui.huh.setText("The root can always be made black without "+
			       "affecting the black node count of any path.");
	       gui.invariant.setText("");
	    } else {
	       gui.rules.setText("Nothing to do - hit 'Next Step' again");
	       gui.huh.setText("");
	       gui.invariant.setText("");
	    }
	 } else if (current.color == Color.black ) {
	    if (current.parent != null && 
		(current.parent == rbt.rootSentinel ||
		 current.parent.parent == rbt.rootSentinel &&
		 current.parent.color == Color.red)) {
	       gui.rules.setText("<4> Color the root black");
	       gui.huh.setText("The root can always be made black without "+
			       "affecting the black node count of any path.");
	       gui.invariant.setText("");
	    } else {
	       gui.rules.setText("Nothing to do - hit 'Next Step' again");
	       gui.huh.setText("");
	    }
	 } else if (sibling_red) {
	    String text = "<1> Sibling "+sibling_value+" of "+
	       current.object.getValue()+" is red, pull black"+
	       " down from "+current.parent.object.getValue();
	    if (current.parent.parent != null && 
		current.parent.parent.object != null)
	       text += ", set current to "+
		  current.parent.parent.object.getValue();
	    gui.rules.setText(text);
	    if (current.parent.parent != null && 
		current.parent.parent.object != null)
	       gui.huh.setText("Black may be transferred from a parent to "+
			       "its two red children (the parent then taking "+
			       "the color red) without affecting the black\n"+
			       "node count of any path.  However, a double "+
			       "red violation may result two nodes up the "+
			       "tree.  Therefore, current is set to "+
			       current.parent.parent.object.getValue());
	    else
	       gui.huh.setText("Black may be transferred from a parent to "+
			       "its two red children (the parent then taking "+
			       "the color red) without affecting the black\n"+
			       "node count of any path.  Since the parent "+
			       current.parent.object.getValue()+
			       " is the root, the process can be stopped "+
			       "at this point because...");
	 } else if (parent_on_left && !red_child_on_left) {
	    String text = "<3.1> Parent "+current.parent.object.getValue()+
	       " of "+current.object.getValue()+
	       " is on the left and its red child "+red_child_value+
	       " is on the right: rotate counter-clockwise around "+
	       current.parent.object.getValue();
	    gui.rules.setText(text);
	    gui.huh.setText("Since black parent "+
			    current.parent.object.getValue()+
			    " is to the left of red current "+
			    current.object.getValue()+
			    " and red child "+red_child_value+
			    " is to the right of current, a "+
			    "counter-clockwise rotation\naround "+
			    current.parent.object.getValue()+
			    " will subtract a black from paths through "+
			    red_child_value+
			    ".   But this imbalance can be rectified by "+
			    "swapping colors of "+
			    current.parent.object.getValue()+
			    " and "+
			    current.object.getValue()+
			    ".\nDoing so (in the next step) also eliminates "+
			    "the double red violation.");
	 } else if (!parent_on_left && red_child_on_left) {
	    String text = "<3.1> Parent "+current.parent.object.getValue()+
	       " of "+current.object.getValue()+
	       " is on the right and its red child "+red_child_value+
	       " is on the left: rotate clockwise around "+
	       current.parent.object.getValue();
	    gui.rules.setText(text);
	    gui.huh.setText("Since black parent "+
			    current.parent.object.getValue()+
			    " is to the right of red current "+
			    current.object.getValue()+
			    " and red child "+red_child_value+
			    " is to the left of current, a "+
			    "clockwise rotation\naround "+
			    current.parent.object.getValue()+
			    " will subtract a black from paths through "+
			    red_child_value+
			    ".   But this imbalance can be rectified by "+
			    "swapping colors of "+
			    current.parent.object.getValue()+
			    " and "+
			    current.object.getValue()+
			    ".\nDoing so (in the next step) also eliminates "+
                            "the double red violation.");
	 } else if (!parent_on_left && !red_child_on_left) {
	    String text = "<2> Parent "+current.parent.object.getValue()+
	       " of "+current.object.getValue()+
	       " is on the right and its red child "+red_child_value+
	       " is on the right: rotate counter-clockwise around "+
	       current.object.getValue()+", set current to "+red_child_value;
	    gui.rules.setText(text);
	    gui.huh.setText("Since parent "+
			    current.parent.object.getValue()+
			    " is to the right of current "+
			    current.object.getValue()+
			    ", if the red child "+red_child_value+
			    " were to current's left, we could rotate black "+
			    current.parent.object.getValue()+
			    " out of\ncurrent's path then switch it back in "+
			    "to eliminate the double red violation (this is "+
			    "explained in more detail in the next step).\n"+
			    "So, we use this step to set up this possibility "+
			    "by rotating counter-clockwise around "+
			    current.object.getValue()+
			    ".\nThe result is red "+
			    red_child_value+
			    " to the left of black "+
			    current.parent.object.getValue()+
			    " and red "+
			    current.object.getValue()+
			    " to the left of red "+
			    red_child_value+".");
	 } else if (parent_on_left && red_child_on_left) {
	    String text = "<2> Parent "+current.parent.object.getValue()+
	       " of "+current.object.getValue()+
	       " is on the left and its red child "+red_child_value+
	       " is on the left: rotate clockwise around "+
	       current.object.getValue()+", set current to "+red_child_value;
	    gui.rules.setText(text);
	    gui.huh.setText("Since parent "+
			    current.parent.object.getValue()+
			    " is to the left of current "+
			    current.object.getValue()+
			    ", if the red child "+red_child_value+
			    " were to current's right, we could rotate black "+
			    current.parent.object.getValue()+
			    " out of\ncurrent's path then switch it back in "+
			    "to eliminate the double red violation (this is "+
			    "explained in more detail in the next step).\n"+
			    "So, we use this step to set up this possibility "+
			    "by rotating clockwise around "+
			    current.object.getValue()+
			    ".\nThe result is red "+
			    red_child_value+
			    " to the right of black "+
			    current.parent.object.getValue()+
			    " and red "+
			    current.object.getValue()+
			    " to the right of red "+
			    red_child_value+".");
	 } else {
	    gui.rules.setText("");
	    gui.huh.setText("");
	 }
      } catch (Exception e) {
	 gui.rules.setText("-");
	 gui.huh.setText("");
      }
   }

   public void run () {
      setCurrent(current);
      // if Current is a black node, no rotations needed
      while (current.color != Color.black) {
         // if (!Current->Parent) break;  XXX may not need this
         // Current is red, the imbalanced child is red, and parent is black.

         Dot cur_parent = current.parent;

         // If the current is on the right of the parent, the parent is 
         // to the left
         if (cur_parent.rightTree == current) {
            // if the sibling is also red, we can pull down the color 
            // black from the parent
            if (cur_parent.leftTree.color == Color.red) {
               cur_parent.leftTree.color = 
                  cur_parent.leftTree.disp_color = Color.black;
               current.color = current.disp_color = Color.black;
               cur_parent.color = cur_parent.disp_color = Color.red;
               rbt.level();
	       setCurrent(cur_parent.parent);
	       showRule(cur_parent.parent, false);
               putIt(tot);
               // jump twice up the tree. if Current reaches the rootSentinel 
               // (black node), the loop will stop
               current = cur_parent.parent;
               continue;
            }
            // if the imbalance (red node) is on the left, and the parent 
            // is on the left, a "prep-slide" is needed. (see diagram)
	    Dot temp = current;
            if (current.leftTree.color == Color.red) {
               current.rightSide_RightRotate( );
               rbt.level();
	       setCurrent(current.parent);
	       showRule(current.parent, false);
               putIt(tot);
	       temp = current.parent;
            }

            // Now we can do our left rotation to balance the tree.
            cur_parent.leftRotate();
            rbt.level();

            if (cur_parent.color == Color.red && 
                cur_parent.parent.color == Color.black) {
	       setCurrent(current);
	       showRule(current, false);
               putIt(null);
               return;
            } else {
	       setCurrent(temp);
	       gui.invariant.setText("");
	       showRule(temp, true);
               putIt(tot);
               cur_parent.color = cur_parent.disp_color = Color.red;
               cur_parent.parent.color = 
                  cur_parent.parent.disp_color = Color.black;
               rbt.level();
	       setCurrent(current);
	       showRule(current, false);
               putIt(null);
               return;
            }
         }
         // else the parent is to the right
         else {
            // if the sibling is also red, we can pull down the color black 
            // from the parent
            if (cur_parent.rightTree.color == Color.red) {
               cur_parent.rightTree.color = 
                  cur_parent.rightTree.disp_color = Color.black;
               current.color = current.disp_color = Color.black;
               cur_parent.color = cur_parent.disp_color = Color.red;
               rbt.level();
	       setCurrent(cur_parent.parent);
	       showRule(cur_parent.parent, false);
               putIt(tot);
               // jump twice up the tree. if Current reaches the rootSentinel 
               // (black node), the loop will stop
               current = cur_parent.parent;
               continue;
            }

	    Dot temp = current;
            // if the imbalance (red node) is on the right, and the parent 
            // is on the right, a "prep-slide" is needed. (see diagram)
            if (current.rightTree.color == Color.red) {
               current.leftSide_LeftRotate( );
               rbt.level();
	       setCurrent(current.parent);
	       temp = current.parent;
	       showRule(current.parent, false);
               putIt(tot);
            }

            // Now we can do our left rotation to balance the tree.
            cur_parent.rightRotate( );
            rbt.level();
            if (cur_parent.color == Color.red &&
                cur_parent.parent.color == Color.black) {
	       setCurrent(current);
	       showRule(current, false);
               putIt(null);
               return;
            } else {
	       setCurrent(temp);
	       gui.invariant.setText("");
	       showRule(temp, true);
               putIt(tot);
               cur_parent.color = cur_parent.disp_color = Color.red;
               cur_parent.parent.color = 
                  cur_parent.parent.disp_color = Color.black;
               rbt.level();
	       setCurrent(current);
	       showRule(current, false);
               putIt(null);
               return;
            }
         }
      }
      rbt.level();
      setCurrent(null);
      //showRule(current);
      putIt(null);
      return;
   }
}

// For adding an object to the red-black tree.
class Add extends Stream {
   RedBlack gui;
   Dot newNode;
   RBTree_inorder_class inorder;
   Dot sentinel, rootSentinel;
   RBTree rbt;
   TO tot = new TO(true);
   TO tof = new TO(false);

   public Add (RedBlack gui, RBTree rbt, Dot newNode, RBTree_inorder_class inorder) {
      this.gui = gui;
      this.newNode = newNode;
      this.inorder = inorder;
      sentinel = rbt.sentinel;
      rootSentinel = rbt.rootSentinel;
      this.rbt = rbt;
   }

   void setCurrent (Dot dot) {
      if (dot == rbt.rootSentinel) dot = dot.leftTree;
      if (dot != null && dot.color == Color.black) dot = null;
      for (int i=0 ; i < gui.ndots ; i++) {
	 if (gui.dot[i] != null) {
	    gui.dot[i].isCurrent = 
	       (gui.dot[i] != dot || dot == null) ? false : true;
	 }
      }
   }

   void showRule(Dot sub_current) {
      boolean parent_on_left = false;
      boolean red_child_on_left = false;
      boolean sibling_red = false;
      int sibling_value = 0;
      int red_child_value = 0;
      boolean isRoot = false;

      Dot current = sub_current.parent;
      if (current.parent == rbt.rootSentinel) isRoot = true;
      if (current.parent != null && current.parent.leftTree == current) {
	 parent_on_left = false;
      } else if (current.parent != null && 
		 current.parent.rightTree == current) {
	 parent_on_left = true;
      }
      if (!parent_on_left) {
	 sibling_red = (current.parent.rightTree.color == Color.red) ?
	    true : false;
	 if (current.parent.rightTree.object != null)
	    sibling_value = current.parent.rightTree.object.getValue();
      } else {
	 sibling_red = (current.parent.leftTree.color == Color.red) ?
	    true : false;
	 if (current.parent.leftTree.object != null)
	    sibling_value = current.parent.leftTree.object.getValue();
      }
      if (sub_current == sub_current.parent.leftTree) {
	 red_child_on_left = true;
	 red_child_value = sub_current.object.getValue();
      } else if (sub_current == sub_current.parent.rightTree) {
	 red_child_on_left = false;
	 red_child_value = sub_current.object.getValue();
      }

      if (isRoot) {
	 if (current.color == Color.red) {
	    gui.rules.setText("<4> Color the root black");
	    gui.huh.setText("The root can always be made black without "+
			    "affecting the black node count of any path.");
	 } else {
	    gui.rules.setText("Nothing to do - hit 'Next Step' again");
	    gui.huh.setText("");
	 }
      } else if (rbt.rootSentinel == current) {
	 if (rbt.rootSentinel.leftTree.color == Color.red) {
	    gui.rules.setText("<4> Color the root black");
	    gui.huh.setText("The root can always be made black without "+
			    "affecting the black node count of any path.");
	 } else {
	    gui.rules.setText("Nothing to do - hit 'Next Step' again");
	    gui.huh.setText("");
	 }
      } else if (current.color == Color.black ) {
	 if (current.parent != null && 
	     (current.parent == rbt.rootSentinel ||
	      current.parent.parent == rbt.rootSentinel &&
	      current.parent.color == Color.red)) {
	    gui.rules.setText("<4> Color the root black"); 
	    gui.huh.setText("The root can always be made black without "+
			    "affecting the black node count of any path.");
	 } else {
	    gui.rules.setText("Nothing to do - hit 'Next Step' again");
	    gui.huh.setText("");
	 }
      } else if (sibling_red) {
	 String text = "<1> Sibling "+sibling_value+" of "+
	    current.object.getValue()+" is red, pull black"+
	    " down from "+current.parent.object.getValue();
	 if (current.parent.parent != null && 
	     current.parent.parent.object != null)
	    text+=", set current to "+current.parent.parent.object.getValue();
	 gui.rules.setText(text);
	    if (current.parent.parent != null && 
		current.parent.parent.object != null)
	       gui.huh.setText("Black may be transferred from a parent to "+
			       "its two red children (the parent then taking "+
			       "the color red) without affecting the black\n"+
			       "node count of any path.  However, a double "+
			       "red violation may result two nodes up the "+
			       "tree.  Therefore, current is set to "+
			       current.parent.parent.object.getValue());
	    else
	       gui.huh.setText("Black may be transferred from a parent to "+
			       "its two red children (the parent then taking "+
			       "the color red) without affecting the black\n"+
			       "node count of any path.  Since the parent "+
			       current.parent.object.getValue()+
			       " is the root, the process can be stopped "+
			       "at this point because...");
      } else if (parent_on_left && !red_child_on_left) {
	 String text = "<3.1> Parent "+current.parent.object.getValue()+
	    " of "+current.object.getValue()+
	    " is on the left and its red child "+red_child_value+
	    " is on the right: rotate counter-clockwise around "+
	    current.parent.object.getValue();
	 gui.rules.setText(text);
	 gui.huh.setText("Since black parent "+
			 current.parent.object.getValue()+
			 " is to the left of red current "+
			 current.object.getValue()+
			 " and red child "+red_child_value+
			 " is to the right of current, a "+
			 "counter-clockwise rotation\naround "+
			 current.parent.object.getValue()+
			 " will subtract a black from paths through "+
			 red_child_value+
			 ".   But this imbalance can be rectified by "+
			 "swapping colors of "+
			 current.parent.object.getValue()+
			 " and "+
			 current.object.getValue()+
			 ".\nDoing so (in the next step) also eliminates "+
			 "the double red violation.");
      } else if (!parent_on_left && red_child_on_left) {
	 String text = "<3.1> Parent "+current.parent.object.getValue()+
	    " of "+current.object.getValue()+
	    " is on the right and its red child "+red_child_value+
	    " is on the left: rotate clockwise around "+
	    current.parent.object.getValue();
	 gui.rules.setText(text);
	 gui.huh.setText("Since black parent "+
			 current.parent.object.getValue()+
			 " is to the right of red current "+
			 current.object.getValue()+
			 " and red child "+red_child_value+
			 " is to the left of current, a "+
			 "clockwise rotation\naround "+
			 current.parent.object.getValue()+
			 " will subtract a black from paths through "+
			 red_child_value+
			 ".   But this imbalance can be rectified by "+
			 "swapping colors of "+
			 current.parent.object.getValue()+
			 " and "+
			 current.object.getValue()+
			 ".\nDoing so (in the next step) also eliminates "+
			 "the double red violation.");
      } else if (!parent_on_left && !red_child_on_left) {
	 String text = "<2> Parent "+current.parent.object.getValue()+
	    " of "+current.object.getValue()+
	    " is on the right and its red child "+red_child_value+
	    " is on the right: rotate counter-clockwise around "+
	    current.object.getValue()+", set current to "+red_child_value;
	 gui.rules.setText(text);
	 gui.huh.setText("Since parent "+
			 current.parent.object.getValue()+
			 " is to the right of current "+
			 current.object.getValue()+
			 ", if the red child "+red_child_value+
			 " were to current's left, we could rotate black "+
			 current.parent.object.getValue()+
			 " out of\ncurrent's path then switch it back in "+
			 "to eliminate the double red violation (this is "+
			 "explained in more detail in the next step).\n"+
			 "So, we use this step to set up this possibility "+
			 "by rotating counter-clockwise around "+
			 current.object.getValue()+
			 ".\nThe result is red "+
			 red_child_value+
			 " to the left of black "+
			 current.parent.object.getValue()+
			 " and red "+
			 current.object.getValue()+
			 " to the left of red "+
			 red_child_value+".");
      } else if (parent_on_left && red_child_on_left) {
	 String text = "<2> Parent "+current.parent.object.getValue()+
	    " of "+current.object.getValue()+
	    " is on the left and its red child "+red_child_value+
	    " is on the left: rotate clockwise around "+
	    current.object.getValue()+", set current to "+red_child_value;
	 gui.rules.setText(text);
	 gui.huh.setText("Since parent "+
			 current.parent.object.getValue()+
			 " is to the left of current "+
			 current.object.getValue()+
			 ", if the red child "+red_child_value+
			 " were to current's right, we could rotate black "+
			 current.parent.object.getValue()+
			 " out of\ncurrent's path then switch it back in "+
			 "to eliminate the double red violation (this is "+
			 "explained in more detail in the next step).\n"+
			 "So, we use this step to set up this possibility "+
			 "by rotating clockwise around "+
			 current.object.getValue()+
			 ".\nThe result is red "+
			 red_child_value+
			 " to the right of black "+
			 current.parent.object.getValue()+
			 " and red "+
			 current.object.getValue()+
			 " to the right of red "+
			 red_child_value+".");
      } else {
	 gui.rules.setText("");
	 gui.huh.setText("");
      }
   }

   public void run () {
      if (newNode.color != Color.blue) {
         putIt(null);
         return;
      }

      newNode.color = newNode.disp_color = Color.red;
      newNode.sentinel = sentinel;
      newNode.leftTree =  sentinel;
      newNode.rightTree = sentinel;

      Dot current = rootSentinel.leftTree;
      if (current == sentinel) {
         rootSentinel.leftTree = newNode;
         newNode.parent = rootSentinel;
      } else {
         do {
            // if the new node comes before the current node, go left
            if (inorder.compare( newNode.object, current.object )) {
               if (current.leftTree == sentinel) {
                  current.leftTree = newNode;
                  newNode.parent = current;
                  rbt.level();
		  if (current.color == Color.red)
		     gui.invariant.setText("Current is the highest of the "+
					   "only 2 consecutive reds, all "+
					   "black node counts are correct");
		  setCurrent(current);
		  showRule(newNode);
                  putIt(tot);
                  break;
               }
               else current = current.leftTree;
            } else {  // go right
               if (current.rightTree == sentinel) {
                  current.rightTree = newNode;
                  newNode.parent = current;
                  rbt.level();
		  if (current.color == Color.red)
		     gui.invariant.setText("Current is the highest of the "+
					   "only 2 consecutive reds, all "+
					   "black node counts are correct");
		  setCurrent(current);
		  showRule(newNode);
                  putIt(tot);
                  break;
               }
               else current = current.rightTree;
            }
         } while (true);

         TO bal;
         Balance balance = new Balance(gui, rbt, current);
         while ((bal = (TO)balance.next()) != null) {
            rbt.level();
            putIt(bal);
         }
         balance = null;
      }
      rootSentinel.leftTree.color = 
         rootSentinel.leftTree.disp_color = Color.black;
      rbt.level();
      gui.rules.setText("");
      gui.huh.setText("");
      gui.invariant.setText("");
      setCurrent(null);
      putIt(null);
      return;
   }
}

// For removing an object from a red-black tree.
class Prune extends Stream {
   String text,case_one_text;
   RedBlack gui;
   RBTree rbt;
   Dot current;
   TO tot = new TO(true);

   public Prune (RedBlack gui, RBTree rbt, Dot dot) { 
      current = dot; 
      this.rbt = rbt; 
      this.gui = gui;
      text = case_one_text = null;
   }

   void setCurrent (Dot dot) {
      for (int i=0 ; i < gui.ndots ; i++) {
	 if (gui.dot[i] != null) {
	    gui.dot[i].isCurrent = 
	       (gui.dot[i] != dot || dot == null) ? false : true;
	 }
      }
   }

   public void run () {
      if (current.color == Color.blue) {
	 gui.rules.setText("");
	 gui.huh.setText("");
         putIt(null);
         return;
      }

      // If this is a leaf node (or almost a leaf) we can just prune it
      if (current.leftTree.leftTree == current.leftTree || 
          current.rightTree.rightTree == current.rightTree) {
	 setCurrent(current);

	 current.disp_color = Color.green;  // JVF

	 if (current.color == Color.red &&
	     current.leftTree == rbt.sentinel &&
	     current.rightTree == rbt.sentinel) {
	    gui.rules.setText("[1] Current "+
			      current.object.getValue()+
			      " is a red leaf: Delete "+
			      current.object.getValue());
	    gui.huh.setText("Deleting a single red leaf does not affect "+
			    "the black node count of any path.");
	    putIt(new TO(true));
	 } else if (current.color == Color.black &&
		    current.parent != rbt.rootSentinel &&
		    current.leftTree.color == Color.red &&
		    current.rightTree == rbt.sentinel) {
	    gui.rules.setText("[4] Current "+
			      current.object.getValue()+
			      " is black with a red child: Make "+
                              current.leftTree.object.getValue()+
                              " a child of "+
			      current.parent.object.getValue()+
                              ", change its color to black");
	    gui.huh.setText("Current "+
			    current.object.getValue()+
			    " is to be eliminated, leaving a branch of "+
			    current.parent.object.getValue()+
			    " unfilled.  At the same time, "+
                              current.leftTree.object.getValue()+
			    " will be orphaned.\nThe easy fix is to make "+
                              current.leftTree.object.getValue()+
			    " a child of "+
    			    current.parent.object.getValue()+
			    ".\nBut since "+
			    current.object.getValue()+
			    " is black, we need to change "+
                              current.leftTree.object.getValue()+
			    " to black to get the proper black node count "+
			    "through it.");
	    putIt(new TO(true));
	 } else if (current.color == Color.black &&
		    current.parent != rbt.rootSentinel &&
		    current.rightTree.color == Color.red &&
		    current.leftTree == rbt.sentinel) {
	    gui.rules.setText("[4] Current "+
			      current.object.getValue()+
			      " is black with a red child: Make "+
                              current.rightTree.object.getValue()+
                              " a child of "+
			      current.parent.object.getValue()+
                              ", change its color to black");
	    gui.huh.setText("Current "+
			    current.object.getValue()+
			    " is to be eliminated, leaving a branch of "+
			    current.parent.object.getValue()+
			    " unfilled.  At the same time, "+
                              current.rightTree.object.getValue()+
			    " will be orphaned.\nThe easy fix is to make "+
                              current.rightTree.object.getValue()+
			    " a child of "+
    			    current.parent.object.getValue()+
			    ".\nBut since "+
			    current.object.getValue()+
			    " is black, we need to change "+
                              current.rightTree.object.getValue()+
			    " to black to get the proper black node count "+
			    "through it.");
	    putIt(new TO(true));
	 } else if (current.color == Color.black &&
		    current.parent == rbt.rootSentinel &&
		    current.rightTree.color == Color.red &&
		    current.leftTree == rbt.sentinel) {
	    gui.rules.setText("[4] Current "+
			      current.object.getValue()+
			      " is black with a red child: Make "+
                              current.rightTree.object.getValue()+
                              " the (black) root");
	    gui.huh.setText("This is a special case.  There will be one "+
			    "node left.");
	    putIt(new TO(true));
	 } else if (current.color == Color.black &&
		    current.parent == rbt.rootSentinel &&
		    current.leftTree.color == Color.red &&
		    current.rightTree == rbt.sentinel) {
	    gui.rules.setText("[4] Current "+
			      current.object.getValue()+
			      " is black with a red child: Make "+
                              current.leftTree.object.getValue()+
                              " the (black) root");
	    gui.huh.setText("This is a special case.  There will be one "+
			    "node left.");
	    putIt(new TO(true));
	 }

         TO pru;
         PruneLeaf pruner = new PruneLeaf(gui, rbt, current);
         while ((pru = (TO)pruner.next()) != null) {
            rbt.level();
            putIt(pru);
         }
         pruner = null;
	 setCurrent(null);
      }
      // Otherwise we need a successor.  We are guaranteed to have one because
      // the current node has 2 children.
      else {
         Dot successor = current.getNext( );
         // Do we like this successor?  If not, get the other one.
	 String succstr = "successor";
	 String succhuhstr = "the next greater (successor)";
         if (successor.color == Color.black && 
             successor.leftTree.leftTree == successor.leftTree && 
             successor.rightTree.rightTree == successor.rightTree) {
            successor = current.getPrev( );
	    succstr = "predecessor";
	    succhuhstr = "the next smaller (predecessor)";
	 }
	 setCurrent(successor);
	 gui.rules.setText("We will act like we are deleting "+succstr+" "+
			   successor.object.getValue()+
			   " (yellow) and then replace "+
			   current.object.getValue()+
			   "'s node with it at the end of the run");
	 String clr = "It is easy to delete a leaf or near leaf but hard "+
	    "to delete a node higher in the tree.  So, we find "+succhuhstr+
	    " node\n(which must be a leaf or near leaf), remove it from the "+
	    "tree as if it were deleted, rebalance the tree, then replace\n"+
	    "the selected node with it.";
	 if (successor.color == Color.black)
	    clr += "  The "+succstr+" will be colored yellow, it will "+
	       "seem to be a black 'phantom' when applying deletion rules,"+
	       "\nbut it will not contribute to black node counts.";
	 else
	    clr += "  The "+succstr+" will be colored yellow but it will "+
	       "be regarded as a red node in the next step.";
	 gui.huh.setText(clr);
	 successor.disp_color = Color.yellow; // JVF
	 putIt(new TO(true));
	 
	 if (successor.color == Color.red) {
	    text = "[1] Current "+
	       successor.object.getValue()+
	       " is a red leaf: Replace "+
	       current.object.getValue()+
	       " with "+successor.object.getValue();
	    if (current.color == Color.black) 
	       text += ", change its color to black";
	    case_one_text = "Deleting a single red leaf does not affect "+
	       "the black node count of any path.";
	    //putIt(new TO(true));
	 } else if (successor.leftTree != rbt.sentinel) {
	    gui.rules.setText("[4] Current "+
			      successor.object.getValue()+
			      " is black with a red child: Make "+
			      successor.leftTree.object.getValue()+
			      " a child of "+
			      successor.parent.object.getValue()+
			      ", change its color to black");
	    gui.huh.setText("Current "+
			    successor.object.getValue()+
			    " is to be eliminated, leaving a branch of "+
			    successor.parent.object.getValue()+
			    " unfilled.  At the same time, "+
			    successor.leftTree.object.getValue()+
			    " will be orphaned.\nThe easy fix is to make "+
			    successor.leftTree.object.getValue()+
			    " a child of "+
    			    successor.parent.object.getValue()+
			    ".\nBut since "+
			    successor.object.getValue()+
			    " is black, we need to change "+
			    successor.leftTree.object.getValue()+
			    " to black to get the proper black node count "+
			    "through it.");
	    putIt(new TO(true));
	 } else if (successor.rightTree != rbt.sentinel) {
	    gui.rules.setText("[4] Current "+
			      successor.object.getValue()+
			      " is black with a red child: Make "+
			      successor.rightTree.object.getValue()+
			      " a child of "+
			      successor.parent.object.getValue()+
			      ", change its color to black");
	    gui.huh.setText("Current "+
			    successor.object.getValue()+
			    " is to be eliminated, leaving a branch of "+
			    successor.parent.object.getValue()+
			    " unfilled.  At the same time, "+
			    successor.rightTree.object.getValue()+
			    " will be orphaned.\nThe easy fix is to make "+
			    successor.rightTree.object.getValue()+
			    " a child of "+
    			    successor.parent.object.getValue()+
			    ".\nBut since "+
			    successor.object.getValue()+
			    " is black, we need to change "+
			    successor.rightTree.object.getValue()+
			    " to black to get the proper black node count "+
			    "through it.");
	    putIt(new TO(true));
	 }

         TO pru;
         PruneLeaf pruner = new PruneLeaf(gui, rbt, successor);
         while ((pru = (TO)pruner.next()) != null) {
            rbt.level();
            putIt(pru);
         }
         pruner = null;

	 if (text != null) {
	    gui.rules.setText(text);
	    gui.huh.setText(case_one_text);
	 } else {
	    gui.rules.setText("Finish: Replace selected node "+
			      current.object.getValue()+
			      " with "+
			      successor.object.getValue());
	    gui.huh.setText("There are no violations.");
	 }
	 putIt(tot);
	 setCurrent(null);

         // now exchange the successor for the current node
         Dot Temp = current.rightTree;
         successor.rightTree = Temp;
         Temp.parent = successor;
         
         Temp = current.leftTree;
         successor.leftTree = Temp;
         Temp.parent = successor;

         Temp = current.parent;
         successor.parent = Temp;
         if (Temp.leftTree == current) Temp.leftTree = successor; 
         else Temp.rightTree = successor;
         successor.color = successor.disp_color = current.color;

         rbt.level();
      }

      /*++++++++++++*/
      //      current.color = current.disp_color = Color.blue;
      rbt.level();
      gui.rules.setText("");
      gui.huh.setText("");
      putIt(null);
      return;
   }
}

// PruneLeaf performs pruning of nodes with at most one child.
// Used by Prune.
class PruneLeaf extends Stream {
   int thecase;
   RedBlack gui;
   TO tot = new TO(true);
   Dot node;
   int save_del, save_sib, save_par;
   RBTree rbt;
   boolean sibling_red_left, sibling_red_right, begin_left, begin_right, frst;

   public PruneLeaf (RedBlack gui, RBTree rbt, Dot dot) { 
      node = dot; 
      this.rbt = rbt; 
      this.gui = gui;
      sibling_red_right = false;
      sibling_red_left = false;
      save_del = save_sib = save_par = 0;
      begin_left = false;
      begin_right = false;
      frst = true;
      thecase = 0;
   }

   public Dot showRule (Dot current) {
      if (current == null) {
	 gui.rules.setText("");
	 gui.huh.setText("");
	 return null;
      }

      try {
	 if (frst) {
	    save_del = current.object.getValue();
	    if (current.parent.leftTree == current &&
		current.parent.rightTree.object != null)
	       save_sib = current.parent.rightTree.object.getValue();
	    else if (current.parent.rightTree == current &&
		     current.parent.leftTree.object != null)
	       save_sib = current.parent.leftTree.object.getValue();
	    save_par = current.parent.object.getValue();
	    frst = false;
	 }

	 if (begin_left) {
	    String colm = (current.parent.rightTree.color == Color.red) ?
	       "red" : "black";
	    String colp = (current.parent.color == Color.red) ? 
	       "red" : "black";
	    gui.rules.setText("[5.3.3] Sibling "+
			      current.parent.rightTree.object.getValue()+
			      " of "+
			      save_del+
			      " is "+colm+", parent "+
			      current.parent.object.getValue()+
			      " is "+colp+": rotate counter-clockwise around "+
			      current.parent.object.getValue());

	    gui.huh.setText("With the colors set correctly, we rotate the "+
			    "black of "+
			    current.parent.object.getValue()+
			    " into current's path.");
	    begin_left = false;
	    return current;
	 } else if (begin_right) {
	    String colm = (current.parent.leftTree.color == Color.red) ?
	       "red" : "black";
	    String colp = (current.parent.color == Color.red) ? 
	       "red" : "black";
	    gui.rules.setText("[5.3.3] Sibling "+
			      current.parent.leftTree.object.getValue()+
			      " of "+
			      save_del+
			      " is "+colm+", parent "+
			      current.parent.object.getValue()+
			      " is "+colp+": rotate clockwise around "+
			      current.parent.object.getValue());
	    gui.huh.setText("With the colors set correctly, we rotate the "+
			    "black of "+
			    current.parent.object.getValue()+
			    " into current's path.");
	    begin_right = false;
	    return current;
	 } else if (sibling_red_left) {
	    gui.rules.setText("[5.1.2] Sibling "+save_sib+" of "+save_del+
			      " is red, parent "+save_par+
			      " is black: (cont) rotate clockwise around "+
			      save_par);
	    gui.huh.setText("The colors have been exchanged between "+
			    save_sib+" and "+save_par+
			    ", now we can do "+
			    "the rotation.");
	    sibling_red_left = false;
	    return current;
	 } else if (sibling_red_right) {
	    gui.rules.setText("[5.1.2] Sibling "+save_sib+" of "+save_del+
			      " is red, parent "+save_par+" is black: "+
			      "(cont) rotate counter-clockwise around "+
			      save_par);
	    gui.huh.setText("The colors have been exchanged between "+
			    save_sib+" and "+save_par+
			    ", now we can do "+
			    "the rotation.");
	    sibling_red_right = false;
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.color == Color.black &&
		    current.parent.leftTree.color == Color.red &&
		    thecase != 1) {
	    String colm = (current.parent.leftTree.color == Color.red) ?
	       "red" : "black";
	    String colp = (current.parent.color == Color.red) ? 
	       "red" : "black";
	    gui.rules.setText("[5.1.1] Sibling "+
			      current.parent.leftTree.object.getValue()+
			      " of "+
			      current.object.getValue()+
			      " is "+colm+", parent "+
			      current.parent.object.getValue()+
			      " is "+colp+": (begin) exchange colors of "+
			      current.parent.object.getValue()+
			      " and "+
			      current.parent.leftTree.object.getValue());
            gui.huh.setText("We want to rotate "+
			    current.parent.leftTree.object.getValue()+
			    "'s red into "+
			    current.object.getValue()+
			    "'s path to give "+
			    current.object.getValue()+
			    "'s tree a chance to pick up a black.\n"+
			    "But that would reduce the black count in "+
			    current.parent.leftTree.object.getValue()+
			    "'s tree.  So, we exchange colors between "+
			    current.parent.leftTree.object.getValue()+
			    " and "+
			    current.parent.object.getValue()+
			    " and rotate "+
			    current.parent.object.getValue()+
			    "'s new red into "+
			    current.object.getValue()+
			    "'s tree.\nThe black node count on paths through "+
			    current.object.getValue()+
			    " (which stays current) will still be short by 1"+
			    " and will not change for all other paths.");
	    sibling_red_left = true;
	    save_del = current.object.getValue();
	    save_sib = current.parent.leftTree.object.getValue();
	    save_par = current.parent.object.getValue();
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.color == Color.black &&
		    current.parent.rightTree.color == Color.red &&
		    thecase != 1) {
	    String colm = (current.parent.rightTree.color == Color.red) ?
	       "red" : "black";
	    String colp = (current.parent.color == Color.red) ? 
	       "red" : "black";
	    gui.rules.setText("[5.1.1] Sibling "+
			      current.parent.rightTree.object.getValue()+
			      " of "+
			      current.object.getValue()+
			      " is "+colm+", parent "+
			      current.parent.object.getValue()+
			      " is "+colp+": (begin) exchange colors of "+
			      current.parent.object.getValue()+
			      " and "+
			      current.parent.rightTree.object.getValue());
            gui.huh.setText("We want to rotate "+
			    current.parent.rightTree.object.getValue()+
			    "'s red into "+
			    current.object.getValue()+
			    "'s path to give "+
			    current.object.getValue()+
			    "'s tree a chance to pick up a black.\n"+
			    "But that would reduce the black count in "+
			    current.parent.rightTree.object.getValue()+
			    "'s tree.  So, we exchange colors between "+
			    current.parent.rightTree.object.getValue()+
			    " and "+
			    current.parent.object.getValue()+
			    " and rotate "+
			    current.parent.object.getValue()+
			    "'s new red into "+
			    current.object.getValue()+
			    "'s tree.\nThe black node count on paths through "+
			    current.object.getValue()+
			    " (which stays current) will still be short by 1 "+
			    "and will not change for all other paths.");
	    sibling_red_right = true;
	    save_del = current.object.getValue();
	    save_sib = current.parent.rightTree.object.getValue();
	    save_par = current.parent.object.getValue();
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.rightTree != current &&
		    current.parent.rightTree != rbt.sentinel &&
		    current.parent.rightTree.color == Color.black &&
		    current.parent.rightTree.rightTree.color == Color.black &&
		    current.parent.rightTree.leftTree.color == Color.red) {
	    String colm = (current.parent.rightTree.color == Color.red) ?
	       "red" : "black";
	    String colp=(current.parent.rightTree.leftTree.color==Color.red) ? 
	       "red" : "black";
	    gui.rules.setText("[5.3.1] Sibling "+
			current.parent.rightTree.object.getValue()+
			" of "+
			save_del+
			" is "+colm+", current's near nephew "+
			current.parent.rightTree.leftTree.object.getValue()+
			" is "+colp+", current's far nephew"+
			" is black: rotate clockwise around "+
			current.parent.rightTree.object.getValue());
	    if (current.parent.color == Color.black) {
	       gui.huh.setText("This is an opportunity to rotate "+
			       current.parent.rightTree.object.getValue()+
			       "'s black into paths through current "+
			       save_del+".  Because current's "+
			       "near nephew has the same ancestors\nbefore "+
			       "and after the rotation, its black node "+
			       "count will be unaffected.  Current's black "+
			       "node count will be increased by 1, "+
			       "eliminating\nthat violation.  The only "+
			       "problem is the black node count of paths "+
			       "through current's far nephew become 1 "+
			       "short. The fix is set up by\nnext rotating "+
			       "in the red of "+
			 current.parent.rightTree.leftTree.object.getValue()+
			       " and later making it black.");
	    } else {
	       gui.huh.setText("This is an opportunity to rotate "+
			       current.parent.rightTree.object.getValue()+
			       "'s black into paths through current "+
			       current.object.getValue()+
			       ".  But then we risk a "+
			       "double red violation with "+
			       current.parent.object.getValue()+
			       " and its new child.\nSo, in the next step "+
			       "we make "+
			       current.parent.object.getValue()+
			       " black.  But that will increase the black "+
			       "node count through "+
			       current.object.getValue()+
			       ".  We compensate by ensuring the sibling\n"+
			       "of the next step is red.  Because "+
			       "current's near nephew has the same ancestors "+
			       "before and after the rotation, its black "+
			       "node count will be\nunaffected.  Current's "+
			       "black node count will be increased by 1, "+
			       "eliminating that violation.  The only "+
			       "problem is the black node\ncount of paths "+
			       "through current's far nephew become 1 "+
			       "short.  The fix is set up by next rotating "+
			       "in the red of "+
			 current.parent.rightTree.leftTree.object.getValue()+
			       ".");
	    }
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.leftTree != current &&
		    current.parent.leftTree != rbt.sentinel &&
		    current.parent.leftTree.color == Color.black &&
		    current.parent.leftTree.leftTree.color == Color.black &&
		    current.parent.leftTree.rightTree.color == Color.red) { 
	    String colm = (current.parent.leftTree.color == Color.red) ?
	       "red" : "black";
	    String colp=(current.parent.leftTree.rightTree.color==Color.red) ? 
	       "red" : "black";
	    gui.rules.setText("[5.3.1] Sibling "+
			   current.parent.leftTree.object.getValue()+
			   " of "+
			   save_del+
			   " is "+colm+", current's near nephew "+
			   current.parent.leftTree.rightTree.object.getValue()+
			   " is "+colp+", current's far nephew"+
			   " is black: rotate counter-clockwise around "+
			   current.parent.leftTree.object.getValue());
	    if (current.parent.color == Color.black) {
	       gui.huh.setText("This is an opportunity to rotate a "+
			       "black into paths through current "+
			       save_del+".  Because current's "+
			       "near nephew has the same ancestors\nbefore "+
			       "and after the rotation, its black node "+
			       "count will be unaffected.  Current's black "+
			       "node count will be increased by 1, "+
			       "eliminating\nthat violation.  The only "+
			       "problem is the black node count of paths "+
			       "through current's far nephew become 1 "+
			       "short. The fix is set up by\nnext rotating "+
			       "in the red of "+
			 current.parent.leftTree.rightTree.object.getValue()+
			       " and later making it black.");
	    } else {
	       gui.huh.setText("This is an opportunity to rotate a "+
			       "black into paths through current "+
			       current.object.getValue()+
			       ".  But then we risk a "+
			       "double red violation with "+
			       current.parent.object.getValue()+
			       " and its new child.\nSo, in the next step "+
			       "we make "+
			       current.parent.object.getValue()+
			       " black.  But that will increase the black "+
			       "node count through "+
			       current.object.getValue()+
			       ".  We compensate by ensuring the sibling\n"+
			       "of the next step is red.  Because "+
			       "current's near nephew has the same ancestors "+
			       "before and after the rotation, its black "+
			       "node count will be\nunaffected.  Current's "+
			       "black node count will be increased by 1, "+
			       "eliminating that violation.  The only "+
			       "problem is the black node count\nof paths "+
			       "through current's far nephew become 1 "+
			       "short.  The fix is set up by next rotating "+
			       "in the red of "+
			 current.parent.leftTree.rightTree.object.getValue()+
			       ".");
	    }
	    return current;
	 } else if ((!((thecase == 0 || thecase == 3) && 
		      current.parent.rightTree != null &&
		      current.parent.rightTree != rbt.sentinel &&
		      current.parent.rightTree != current &&
		      current.parent.rightTree.leftTree.color == Color.black &&
		      current.parent.rightTree.rightTree.color == Color.black))
		    &&
		    (current.color == Color.black &&
		     current.parent != null &&
		     current.parent.rightTree.object != null &&
		     current.parent.rightTree != current &&
		     ((current.parent.rightTree.rightTree != null &&
		       current.parent.rightTree.rightTree.color!=Color.black)||
		      current.parent.rightTree.color != current.parent.color ||
		      current.parent.color != Color.black))) {
	    if (current.parent.rightTree.rightTree != null &&
		current.parent.rightTree.rightTree.object != null) {
	       gui.rules.setText("[5.3.2] Set color of far nephew "+
			  current.parent.rightTree.rightTree.object.getValue()+
				 " to black, color of sibling "+
				 current.parent.rightTree.object.getValue()+
				 " to color of its parent, color of parent "+
				 current.parent.object.getValue()+
				 " to black");
	       if (current.parent.color == Color.black && 
		   current.parent.rightTree.color == Color.black && 
		   current.parent.rightTree.rightTree.color == Color.red) {
		  gui.huh.setText("This is an opportunity to rotate a "+
				  "black into paths through current "+
				  save_del+".  Because current's "+
				  "near nephew has the same ancestors\n"+
				  "before and after the rotation, its black "+
				  "node count will be unaffected.  Current's "+
				  "black node count will be increased by 1, "+
				  "eliminating\nthat violation.  But "+
				  "current's 'far' nephew must be made black "+
				  "first or else its black node count will "+
				  "be too low by 1.");
	       } else if (current.parent.color == Color.black && 
			  current.parent.rightTree.color == Color.black &&
			  current.parent.rightTree.rightTree.color == Color.black) {
                  /*** this is unchecked ***/
		  gui.huh.setText("This is an opportunity to rotate a "+
				  "black into paths through current "+
				  save_del+".  Because current's "+
				  "near nephew has the same ancestors\n"+
				  "before and after the rotation, its black "+
				  "node count will be unaffected.  Current's "+
				  "black node count will be increased by 1, "+
				  "eliminating\nthat violation.");
	       } else if (current.parent.color == Color.black && 
			  current.parent.rightTree.color == Color.red) {
		  gui.huh.setText("This is an opportunity to rotate "+
				  "a black into paths through current "+
				  save_del+".  First, in this "+
				  "step, make sibling "+
				  current.parent.rightTree.object.getValue()+
				  " black.  Since the sibling must\nhave "+
				  "rotated in to get here, this will make "+
				  "the black node count through current's "+
				  "'far' nephew too high by 1.  But that is "+
				  "to be desired\nas one black will be "+
				  "rotated out in the next step.");
	       } else if (current.parent.color == Color.red &&
			  current.parent.rightTree.rightTree.color==Color.red){
		  gui.huh.setText("This is an opportunity to rotate a "+
				  "black into paths through current "+
				  current.object.getValue()+
				  ".  But then we risk a "+
				  "double red violation with "+
				  current.parent.object.getValue()+
				  " and its new child.\nSo, we make "+
				  current.parent.object.getValue()+
				  " black.  But that will make the "+
				  "black node count through "+
				  current.object.getValue()+
				  " too high by 1 after rotation.  "+
				  "We compensate by making "+
				  current.parent.rightTree.object.getValue()+
				  " red.\nBecause current's near nephew "+
				  "has the same ancestors before and after "+
				  "the rotation, its black node count will "+
				  "be unaffected.  Current's\nblack node "+
				  "count will be increased by 1, eliminating "+
				  "that violation.  The only problem is the "+
				  "black node count through the 'far' "+
				  "nephew\nwould be short by 1 after "+
				  "rotation.  So we make the 'far' nephew "+
			  current.parent.rightTree.rightTree.object.getValue()+
				  " black.");
	       } else {
		  gui.huh.setText("This is an opportunity to rotate a black "+
				  "into paths through current "+
				  current.object.getValue()+
				  " and eliminate a double red "+
				  "violation between parent "+
				  current.parent.object.getValue()+
				  " and\nsibling "+
				  current.parent.rightTree.object.getValue()+
				  " at the same time: we make "+
				  current.parent.object.getValue()+
				  " black.  Since one black ("+
			  current.parent.rightTree.rightTree.object.getValue()+
				  ") had been rotated out of the path of "+
				  current.parent.rightTree.object.getValue()+
				  "'s left child and another\nblack ("+
				  current.parent.object.getValue()+
				  ") will be rotated in, the black node "+
                                  "count to "+
				  current.parent.rightTree.object.getValue()+
				  "'s left child will not change after the "+
				  "rotation of the next step from what it\n"+
				  "was before the rotation of the previous "+
				  "step.  Since "+
				  current.parent.object.getValue()+
				  " is to be set black, the black node count "+
				  "through current's 'far' nephew will be\n"+
				  "too high by 1.  But that is to be "+
				  "desired since black "+
				  current.parent.object.getValue()+
				  " will be rotated out in the next step.");
	       }
	    } else {
	       gui.rules.setText("[5.3.2] Set color of sibling "+
				 current.parent.rightTree.object.getValue()+
				 " to color of its parent, color of parent "+
				 current.parent.object.getValue()+
				 " to black");
	       gui.huh.setText("A1");
	    }
	    begin_left = true;
	    return current;
	 } else if ((!((thecase == 0 || thecase == 3) && 
		      current.parent.leftTree != null &&
		      current.parent.leftTree != rbt.sentinel &&
		      current.parent.leftTree != current &&
		      current.parent.leftTree.leftTree.color == Color.black &&
		      current.parent.leftTree.rightTree.color == Color.black))
		    &&
		    (current.color == Color.black &&
		     current.parent != null &&
		     current.parent.leftTree.object != null &&
		     current.parent.leftTree != current && 
		     ((current.parent.leftTree.leftTree != null &&
		       current.parent.leftTree.leftTree.color != Color.black)||
		      current.parent.leftTree.color != current.parent.color ||
		      current.parent.color != Color.black))) {
	    if (current.parent.leftTree.leftTree != null &&
		current.parent.leftTree.leftTree.object != null) {
	       gui.rules.setText("[5.3.2] Set color of far nephew "+
			current.parent.leftTree.leftTree.object.getValue()+
				 " to black, color of sibling "+
				 current.parent.leftTree.object.getValue()+
				 " to color of its parent, color of parent "+
				 current.parent.object.getValue()+
				 " to black");
	       if (current.parent.color == Color.black && 
		   current.parent.leftTree.color == Color.black && 
		   current.parent.leftTree.leftTree.color == Color.red) {
		  gui.huh.setText("This is an opportunity to rotate a "+
				  "black into paths through current "+
				  save_del+".  Because current's "+
				  "near nephew has the same ancestors\n"+
				  "before and after the rotation, its black "+
				  "node count will be unaffected.  Current's "+
				  "black node count will be increased by 1, "+
				  "eliminating\nthat violation.  But "+
				  "current's 'far' nephew must be made black "+
				  "first or else its black node count will "+
				  "be too low by 1.");
	       } else if (current.parent.color == Color.black && 
			  current.parent.leftTree.color == Color.black &&
			  current.parent.leftTree.leftTree.color == Color.black) {
		  gui.huh.setText("This is an opportunity to rotate a "+
				  "black into paths through current "+
				  save_del+".  Because current's "+
				  "near nephew has the same ancestors\n"+
				  "before and after the rotation, its black "+
				  "node count will be unaffected.  Current's "+
				  "black node count will be increased by 1, "+
				  "eliminating\nthat violation.");
	       } else if (current.parent.color == Color.black && 
			  current.parent.leftTree.color == Color.red) {
		  gui.huh.setText("This is an opportunity to rotate "+
				  "a black into paths through current "+
				  save_del+".  First, in this "+
				  "step, make sibling "+
				  current.parent.leftTree.object.getValue()+
				  " black.  Since the sibling must\nhave "+
				  "rotated in to get here, this will make "+
				  "the black node count through current's "+
				  "'far' nephew too high by 1.  But that is "+
				  "to be desired\nas one black will be "+
				  "rotated out in the next step.");
	       } else if (current.parent.color == Color.red &&
			  current.parent.leftTree.leftTree.color==Color.red){
		  gui.huh.setText("This is an opportunity to rotate a "+
				  "black into paths through current "+
				  current.object.getValue()+
				  ".  But then we risk a "+
				  "double red violation with "+
				  current.parent.object.getValue()+
				  " and its new child.\nSo, we make "+
				  current.parent.object.getValue()+
				  " black.  But that will make the "+
				  "black node count through "+
				  current.object.getValue()+
				  " too high by 1 after rotation.  "+
				  "We compensate by making "+
				  current.parent.leftTree.object.getValue()+
				  " red.\nBecause current's near nephew "+
				  "has the same ancestors before and after "+
				  "the rotation, its black node count will "+
				  "be unaffected.  Current's\nblack node "+
				  "count will be increased by 1, eliminating "+
				  "that violation.  The only problem is the "+
				  "black node count through the 'far' "+
				  "nephew\nwould be short by 1 after "+
				  "rotation.  So we make the 'far' nephew "+
			  current.parent.leftTree.leftTree.object.getValue()+
				  " black.");
	       } else {
		  gui.huh.setText("This is an opportunity to rotate a black "+
				  "into paths through current "+
				  current.object.getValue()+
				  " and eliminate a double red "+
				  "violation between parent "+
				  current.parent.object.getValue()+
				  " and\nsibling "+
				  current.parent.leftTree.object.getValue()+
				  " at the same time: we make "+
				  current.parent.object.getValue()+
				  " black.  Since one black ("+
			  current.parent.leftTree.leftTree.object.getValue()+
				  ") had been rotated out of the path of "+
				  current.parent.leftTree.object.getValue()+
				  "'s right child and another\nblack ("+
				  current.parent.object.getValue()+
				  ") will be rotated in, the black node "+
                                  "count to "+
				  current.parent.leftTree.object.getValue()+
				  "'s right child will not change after the "+
				  "rotation of the next step from what it\n"+
				  "was before the rotation of the previous "+
				  "step.  Since "+
				  current.parent.object.getValue()+
				  " is to be set black, the black node count "+
				  "through current's 'far' nephew will be\n"+
				  "too high by 1.  But that is to be "+
				  "desired since black "+
				  current.parent.object.getValue()+
				  " will be rotated out in the next step.");
	       } 
	    } else {
	       gui.rules.setText("[5.3.2] Set color of far nephew "+
				 current.parent.leftTree.object.getValue()+
				 " to color of its parent, color of parent "+
				 current.parent.object.getValue()+
				 " to black");
	       gui.huh.setText("A2");
	    }
	    begin_right = true;
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.rightTree != rbt.sentinel &&
		    current.parent.rightTree.rightTree != null &&
		    current.parent.rightTree.rightTree.color == Color.black &&
		    current.parent.rightTree.leftTree != null &&
		    current.parent.rightTree.leftTree.color == Color.black) {
	    gui.rules.setText("[5.2.1] Sibling "+
			      current.parent.rightTree.object.getValue()+
			      " of "+save_del+
			      " and its children are black:"+
			      " set the color of "+
      			      current.parent.rightTree.object.getValue()+
			      " to red; set current to parent "+
			      current.parent.object.getValue());
	    gui.huh.setText("We can reduce the black node count in "+
			      current.parent.rightTree.object.getValue()+
			    "'s tree by making it red.  Then the black node "+
			    "count of both trees below "+
			      current.parent.object.getValue()+
			    "\nwill be short by 1.  That allows "+
			    "'current' to be set one node higher to "+
			    current.parent.object.getValue()+".");
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.leftTree != rbt.sentinel &&
		    current.parent.leftTree.rightTree != null &&
		    current.parent.leftTree.rightTree.color == Color.black &&
		    current.parent.leftTree.leftTree != null &&
		    current.parent.leftTree.leftTree.color == Color.black) {
	    gui.rules.setText("[5.2.1] Sibling "+
			      current.parent.leftTree.object.getValue()+
			      " of "+save_del+
			      " and its children are black:"+
			      " set the color of "+
      			      current.parent.leftTree.object.getValue()+
			      " to red; set current to parent "+
			      current.parent.object.getValue());
	    gui.huh.setText("We can reduce the black node count in "+
			      current.parent.leftTree.object.getValue()+
			    "'s tree by making it red.  Then the black node "+
			    "count of both trees below "+
			      current.parent.object.getValue()+
			    "\nwill be short by 1.  That allows "+
			    "'current' to be set one node higher to "+
			    current.parent.object.getValue()+".");
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.color == Color.red &&
		    current.parent.rightTree.object != null &&
		    current.parent.rightTree != rbt.sentinel &&
		    current.parent.rightTree.rightTree == rbt.sentinel &&
		    current.parent.rightTree.leftTree == rbt.sentinel) {
	    gui.rules.setText("Exchange colors of "+
			      current.parent.object.getValue()+
			      " and "+
			      current.parent.rightTree.object.getValue());
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.color == Color.red &&
		    current.parent.leftTree.object != null &&
		    current.parent.leftTree != rbt.sentinel &&
		    current.parent.leftTree.leftTree == rbt.sentinel &&
		    current.parent.leftTree.rightTree == rbt.sentinel) {
	    gui.rules.setText("Exchange colors of "+
			      current.parent.object.getValue()+
			      " and "+
			      current.parent.leftTree.object.getValue());
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.color == Color.red &&
		    current.parent.leftTree.object != null &&
		    current.parent.leftTree != current &&
		    current.parent.leftTree.color == Color.black &&
		    current.parent.leftTree.leftTree != null &&
		    current.parent.leftTree.leftTree.color == Color.red &&
		    current.parent.leftTree.rightTree != null &&
		    current.parent.leftTree.rightTree.color == Color.red &&
		    thecase != 3) {
	    String colm = (current.parent.leftTree.color == Color.red) ?
	       "red" : "black";
	    String colp = (current.parent.color == Color.red) ? "red":"black";
	    gui.rules.setText("[5.3.1] Sibling "+
			      current.parent.leftTree.object.getValue()+
			      " of "+save_del+" is "+colm+
			      ", current's two nephews are red"+
			      ": (begin) exchange colors of "+
			      current.parent.object.getValue()+
			      " and "+
			      current.parent.leftTree.object.getValue());
	    if (current.parent.color == Color.black) {
	       gui.huh.setText("This is an opportunity to rotate "+
			       current.parent.rightTree.object.getValue()+
			       "'s black into paths through current "+
			       save_del+".  Because current's "+
			       "near nephew has the same ancestors\nbefore "+
			       "and after the rotation, its black node "+
			       "count will be unaffected.  Current's black "+
			       "node count will be increased by 1, "+
			       "eliminating\nthat violation.  The only "+
			       "problem is the black node count of paths "+
			       "through current's far nephew become 1 "+
			       "short. The fix is set up by\nnext rotating "+
			       "in the red of "+
			 current.parent.rightTree.leftTree.object.getValue()+
			       " and later making it black.");
	    } else {
	       gui.huh.setText("This is an opportunity to rotate "+
			       current.parent.rightTree.object.getValue()+
			       "'s black into paths through current "+
			       current.object.getValue()+
			       ".  But then we risk a "+
			       "double red violation with "+
			       current.parent.object.getValue()+
			       " and its new child.\nSo, in the next step "+
			       "we make "+
			       current.parent.object.getValue()+
			       " black.  But that will increase the black "+
			       "node count through "+
			       current.object.getValue()+
			       ".  We compensate by making "+
			       current.parent.rightTree.object.getValue()+
			       " red, also in\nthe next step.  Because "+
			       "current's near nephew has the same ancestors "+
			       "before and after the rotation, its black "+
			       "node count will be\nunaffected.  Current's "+
			       "black node count will be increased by 1, "+
			       "eliminating that violation.  The only "+
			       "problem is the black node\ncount of paths "+
			       "through current's far nephew become 1 "+
			       "short.  The fix is set up by next rotating "+
			       "in the red of "+
			 current.parent.rightTree.leftTree.object.getValue()+
			       ".");
	    }
	    return current;
	 } else if (current.color == Color.black &&
		    current.parent != null &&
		    current.parent.color == Color.red &&
		    current.parent.rightTree.object != null &&
		    current.parent.rightTree != current &&
		    current.parent.rightTree.color == Color.black &&
		    current.parent.rightTree.leftTree != null &&
		    current.parent.rightTree.leftTree.color == Color.red &&
		    current.parent.rightTree.rightTree != null &&
		    current.parent.rightTree.rightTree.color == Color.red) {
	    String colm = (current.parent.rightTree.color == Color.red) ?
	       "red" : "black";
	    String colp = (current.parent.color == Color.red) ? "red":"black";
	    gui.rules.setText("[5.3.1] Sibling "+
			      current.parent.rightTree.object.getValue()+
			      " of "+save_del+" is "+colm+
			      ", current's both nephews are red"+
			      ": (begin) exchange colors of "+
			      current.parent.object.getValue()+
			      " and "+
			      current.parent.rightTree.object.getValue());
	    if (current.parent.color == Color.black)
	       gui.huh.setText("This is an opportunity to rotate "+
			       current.parent.rightTree.object.getValue()+
			       "'s black into paths through current "+
			       save_del+".  Because current's "+
			       "near nephew has the same ancestors before "+
			       "and after the rotation,\nits black node "+
			       "count will be unaffected.  Current's black "+
			       "node count will be increased by 1, "+
			       "eliminating that violation.  The only "+
			       "problem is the black node count of paths "+
			       "through"+
			 current.parent.rightTree.rightTree.object.getValue()+
			       " (current's far nephew) become 1 short.\n"+
			       "This is fixed by making the far nephew black "+
                               "on the next step.");
	    else
	       gui.huh.setText("This is an opportunity to rotate "+
			       current.parent.rightTree.object.getValue()+
			       "'s black into paths through current "+
			       current.object.getValue()+
			       ".  But then we risk a "+
			       "double red violation with "+
			       current.parent.object.getValue()+
			       " and its new child.\nSo, in the next step "+
			       "we make "+
			       current.parent.object.getValue()+
			       " black.  But that increases the black node "+
			       " count through "+
			       current.object.getValue()+
			       ".  We compensate by setting "+
			       current.parent.rightTree.object.getValue()+
			       "to red also in the next step.  Because "+
			       "current's near nephew has the same ancestors "+
			       "before and after the rotation,\nits black "+
			       "node count will be unaffected.  Current's "+
			       "black node count will be increased by 1, "+
			       "eliminating that violation.  The only "+
			       "problem is the black node count of paths "+
			       "through"+
			 current.parent.rightTree.rightTree.object.getValue()+
			       " (current's far nephew) become 1 short.\n"+
			       "This is fixed by rotating in the red of "+
			 current.parent.rightTree.leftTree.object.getValue()+
			       "and later setting one of the reds in the "+
			       " far nephew's path to black.");
	    return current;
	 }
      } catch (Exception e) {
	 gui.rules.setText("Exception");
      }
      gui.rules.setText("");
      gui.huh.setText("");
      return null;
   }

   void setDeleteNodePosition(Dot node, Dot current, int place) {
      //System.out.println("("+place+")");

      boolean on_left = false;
      try {
	 node.parent.rightTree.object.getValue();
	 on_left = true;
      } catch (Exception e) {}
      try {
	 if (node.parent != null && 
	     node.parent.parent != null &&
	     node.parent != rbt.rootSentinel &&
	     node.parent.parent != rbt.rootSentinel) {
	    node.level = node.parent.level+1;
	    if (on_left) node.indent = node.parent.indent*2;
	    else node.indent = node.parent.indent*2+1;
	 }
      } catch (Exception e) {}
   }

   void setCurrent (Dot dot) {
      for (int i=0 ; i < gui.ndots ; i++) {
	 if (gui.dot[i] != null) {
	    gui.dot[i].isCurrent = 
	       (gui.dot[i] != dot || dot == null) ? false : true;
	 }
      }
   }

   public void run () {
      Dot node_parent = node.parent;
      boolean leftSide = (node_parent.leftTree == node);

      // if the node is red and has at most one child, then it has no child.
      // So prune it.
      if (node.color == Color.red) {
         if (leftSide) node_parent.leftTree = rbt.sentinel;
         else node_parent.rightTree = rbt.sentinel;
         rbt.level();
	 showRule(null);
	 setCurrent(node);
         putIt(null);       /*** JVF - OK ***/
         return;
      }

      // Node is black here.  If it has a child, the child will be red.
      if (node.leftTree != rbt.sentinel) {
         // swap with child
         node.leftTree.color = node.leftTree.disp_color = Color.black;
         node.leftTree.parent = node_parent;
         if (leftSide) node_parent.leftTree = node.leftTree;
         else node_parent.rightTree = node.leftTree;
         rbt.level();
	 showRule(null);
	 setCurrent(node);
         putIt(null);
         return;
      }
      // Node is black here.  If it has a child, the child will be red.
      if (node.rightTree != rbt.sentinel) {
         // swap with child
         node.rightTree.color = node.rightTree.disp_color = Color.black;
         node.rightTree.parent = node_parent;
         if (leftSide) node_parent.leftTree = node.rightTree;
         else node_parent.rightTree = node.rightTree;
         rbt.level();
	 showRule(null);
	 setCurrent(node);
         putIt(null);
         return;
      }

      /* Now, we have determined that node is a black leaf node with no 
       * children.  The tree must have the same number of black nodes 
       * along any path from root to leaf.  We want to remove a black node, 
       * disrupting the number of black nodes along the path from the root 
       * to the current leaf.  To correct this, we must either shorten all 
       * other paths, or add a black node to the current path.  Then we can 
       * freely remove our black leaf.

       * While we are pointing to it, we will go ahead and delete the leaf 
       * and replace it with the sentinel (which is also black, so it won't 
       * affect the algorithm).
       */
      if (leftSide) node_parent.leftTree = rbt.sentinel; 
      else node_parent.rightTree = rbt.sentinel;
      rbt.level();
      if (node.parent == rbt.rootSentinel &&
	  node.leftTree == rbt.sentinel &&
	  node.rightTree == rbt.sentinel) {
	 gui.rules.setText("[5] The tree consists only of a root - delete it");
	 gui.huh.setText("This is a no brainer");
      } else {
	 showRule(node);
      }
      setDeleteNodePosition(node, node, 4);
      setCurrent(node);
      putIt(tot);

      Dot sibling = (leftSide) ? node_parent.rightTree : node_parent.leftTree;
      Dot current = node;
      
      // Loop until the current node is red, or until we get to the root node.
      // (The root node's parent is the rootSentinel, which will have a NULL 
      // parent.)
      while (current.color == Color.black && node_parent.parent != null) {
         // If the sibling is red, we are unable to reduce the number of black
         // nodes in the sibling tree, and we can't increase the number of 
         // black nodes in our tree..  Thus we must do a rotation from the 
         // sibling tree to our tree to give us some extra (red) nodes to 
         // play with. This is Case 1 from the text
         if (sibling.color == Color.red) {
            node_parent.color = node_parent.disp_color = Color.red;
            sibling.color = sibling.disp_color = Color.black;
            rbt.level();
	    showRule(current);
	    setDeleteNodePosition(node, current, 5);
	    setCurrent(current);
            putIt(tot);

            if (leftSide) {
               node_parent.leftRotate( );
               sibling = node_parent.rightTree;
            } else {
               node_parent.rightRotate( );
               sibling = node_parent.leftTree;
            }
            rbt.level();
	    showRule(current);
	    setDeleteNodePosition(node, current, 6);
	    setCurrent(current);
            putIt(tot);
            continue;
         }
         // Sibling will be black here
         
         // If the sibling is black and both children are black, we have to
         //  reduce the black node count in the sibling's tree to match ours.
         // This is Case 2a from the text.
	 thecase = 3;
         if (sibling.rightTree.color == Color.black && 
             sibling.leftTree.color == Color.black) {
            if (sibling.color != Color.red) {
               sibling.color = sibling.disp_color = Color.red;
               rbt.level();
	       if (node_parent.color == Color.red || 
		   node_parent.parent == rbt.rootSentinel) {
		  if (node_parent.object != null) {
		     gui.rules.setText("[5.2.2] Make current "+
				       node_parent.object.getValue()+
				       " black");
		     gui.huh.setText("Since current "+
				     node_parent.object.getValue()+
				     " is red, we can just make "+
				     "it black and increase the black node "+
				     "count of all paths through it by 1.\n"+
				     "Doing so eliminates all violations due "+
				     "to black counts being low because, "+
				     "according to the invariant,\n"+
				     "the black node count of all paths "+
				     "through current and only those paths "+
				     "is low by 1.");
		  } else {
		     gui.rules.setText("[5.2.2] Make current black");
		     gui.huh.setText("Current is the root.  If it is black "+
				     "there is no problem because now the "+
				     "black node count of all paths will be "+
				     "the same.\n"+
				     "If it is red, just make it black "+
				     "with the same result.");
		  }
		  setCurrent(node_parent);
		  setDeleteNodePosition(node, current, 7);
		  putIt(tot);
	       } else {
		  frst = true;
		  showRule(node_parent);
		  setDeleteNodePosition(node, node_parent, 8);
		  setCurrent(node_parent);
		  putIt(tot);
	       }
            }

            // Now we move one level up the tree to continue fixing the
            // other branches.
            current = node_parent;
            node_parent = current.parent;
            leftSide = (node_parent.leftTree == current);
            sibling = (leftSide)? node_parent.rightTree : node_parent.leftTree;
            continue;         
	 }
	 thecase = 0;
         // Sibling will be black with 1 or 2 red children here
         
         // << Case 2b is handled by the while loop. >>

         // If one of the sibling's children are red, we again can't make the
         // sibling red to balance the tree at the parent, so we have to do a
         // rotation.  If the "near" nephew is red and the "far" nephew is
         // black, we need to do a "prep-slide" (aka "double rotation")
         // After doing a rotation and rearranging a few colors, the effect is
         // that we maintain the same number of black nodes per path on the 
         // far side of the parent, and we gain a black node on the current 
         // side, so we are done.
         // This is Case 4 from the text. (Case 3 is the double rotation)
         if (leftSide) {
	    thecase = 1;
            if (sibling.rightTree.color == Color.black) { // Case 3 from text
               sibling.rightSide_RightRotate( );
               sibling = node_parent.rightTree;
               rbt.level();
	       showRule(current);
	       setDeleteNodePosition(node, current, 9);
	       setCurrent(current);
               putIt(tot);
            }
	    thecase = 2;

            // now Case 4 from the text
            if (sibling.rightTree.color != Color.black ||
                sibling.color != node_parent.color ||
                node_parent.color != Color.black) {
               sibling.rightTree.color = 
                  sibling.rightTree.disp_color = Color.black;
               sibling.color = sibling.disp_color = node_parent.color;
               node_parent.color = node_parent.disp_color = Color.black;
               rbt.level();
	       showRule(current);
	       setDeleteNodePosition(node, current, 10);
	       setCurrent(current);
               putIt(tot);
            }
	    thecase = 0;

            current = node_parent;
            node_parent = current.parent;
            // I would have assigned to leftSide here,
            //   but we are exiting the function, so why bother?
            // leftSide= (Parent->Left == Current);
            if (node_parent.leftTree == current)
               current.leftSide_LeftRotate( );
            else
               current.rightSide_LeftRotate( );
            rbt.level();
	    showRule(null);
	    setDeleteNodePosition(node, current, 11);
	    setCurrent(null);
            putIt(null);
            return;
         } else {
	    thecase = 1;
            if (sibling.leftTree.color == Color.black) { // Case 3 from text
               sibling.leftSide_LeftRotate( );
               sibling = node_parent.leftTree;
               rbt.level();
	       showRule(current);
	       setDeleteNodePosition(node, current, 12);
	       setCurrent(current);
               putIt(tot);
            }
	    thecase = 2;

            // Case 4 from the text
            if (sibling.leftTree.color != Color.black ||
                sibling.color != node_parent.color ||
                node_parent.color != Color.black) {
               sibling.leftTree.color = 
                  sibling.leftTree.disp_color = Color.black;
               sibling.color = sibling.disp_color = node_parent.color;
               node_parent.color = node_parent.disp_color = Color.black;
               rbt.level();
	       showRule(current);
	       setDeleteNodePosition(node, current, 13);
               putIt(tot);
            }
	    thecase = 0;

            current = node_parent;
            node_parent = current.parent;
            // I would have assigned to leftSide here,
            // but we are exiting the function, so why bother?
            // leftSide = (Parent->Left == Current);
            if (node_parent.leftTree == current)
               current.leftSide_RightRotate();
            else
               current.rightSide_RightRotate();
            rbt.level();
	    showRule(null);
	    setDeleteNodePosition(node, current, 16);
            putIt(null);
            return;
         }
      }

      // Now, make the current node black (to fulfill Case 2b)
      // Case 4 will have exited directly out of the function.
      // If we stopped because we reached the top of the tree,
      //   the head is black anyway so don't worry about it.
      current.color = current.disp_color = Color.black;
      rbt.level();
      showRule(null);
      setDeleteNodePosition(node, current, 15);
      putIt(null);
      return;
   }
}

class RBTree {
   Dot sentinel, rootSentinel;

   RBTree() {
      sentinel = new Dot(sentinel);
      sentinel.leftTree = sentinel;
      sentinel.rightTree = sentinel;
      sentinel.parent = sentinel;
      sentinel.color = sentinel.disp_color = Color.black;
      sentinel.object = null;
      rootSentinel = new Dot(sentinel);
      rootSentinel.color = rootSentinel.disp_color = Color.black;
      rootSentinel.leftTree = sentinel;
      rootSentinel.rightTree = sentinel;
      rootSentinel.parent = null; // uniquely marks this as the root sentinel
      rootSentinel.object = null;
   }

   RBTree(RBTree tree) {
      sentinel = new Dot(sentinel);
      sentinel.leftTree = sentinel;
      sentinel.rightTree = sentinel;
      sentinel.parent = sentinel;
      sentinel.color = sentinel.disp_color = Color.black;
      sentinel.object = null;
      rootSentinel = new Dot(sentinel);
      rootSentinel.color = rootSentinel.disp_color = Color.black;
      rootSentinel.leftTree = sentinel;
      rootSentinel.rightTree = sentinel;
      rootSentinel.parent = null; // uniquely marks this as the root sentinel
      rootSentinel.object = null;
      rootSentinel.leftTree = 
         copyTree(tree.rootSentinel.leftTree, rootSentinel);
   }

   Dot copyTree (Dot dot, Dot parent) {
      Dot leftTree, rightTree, newdot;
      if (dot == dot.sentinel) return sentinel;
      if (dot.object == null) return sentinel;
      newdot = new Dot();
      newdot.parent = parent;
      newdot.color = newdot.disp_color = dot.color;
      newdot.left = dot.left;
      newdot.top = dot.top;
      newdot.level = dot.level;
      newdot.indent = dot.indent;
      newdot.object = dot.object;
      if (dot.leftTree == dot.sentinel) newdot.leftTree = sentinel;
      else newdot.leftTree = copyTree(dot.leftTree, newdot);
      if (dot.rightTree == dot.sentinel) newdot.rightTree = sentinel;
      else newdot.rightTree = copyTree(dot.rightTree, newdot);
      return newdot;
   }

   // Set up the array of Dots (we draw with those) and use current positions,
   // if objects remain, to allow a smooth transition back to position before
   // the undo was called.
   int traverse (Dot tree, Dot dot[], int ndots, Dot dott[], int ndotts) {
      if (tree == sentinel || tree == rootSentinel) return ndotts;
      dott[ndotts] = tree;
      for (int i=0 ; i < ndots ; i++) {
         if (dot[i] == null || dot[i].object == null) continue;
         if (dot[i].object == tree.object) {
            dott[ndotts].left = dot[i].left;
            dott[ndotts].top = dot[i].top;
            break;
         }
      }
      int n = traverse(tree.leftTree, dot, ndots, dott, ndotts+1);
      return traverse(tree.rightTree, dot, ndots, dott, n);
   }

   int setDots (Dot dot[], int ndots, Dot dott[], int ndotts) {
      return traverse(rootSentinel.leftTree, dot, ndots, dott, ndotts);
   }

   void reLevel(Dot dot, int ind, int lvl) {
      if (dot == sentinel) return;
      dot.level = lvl;
      dot.indent = ind;
      reLevel(dot.leftTree,  2*ind,   lvl+1);
      reLevel(dot.rightTree, 2*ind+1, lvl+1);
   }

   public void level() {
      reLevel(rootSentinel, 0, -1);
   }
}

// Where all the drawing takes place
class DotPanel extends Panel 
   implements Runnable, MouseListener, MouseMotionListener {
   RedBlack graph;
   Thread relaxer;
   Dot pick, saved_pick, deletingNode;
   boolean deleteNode = false, removingNode = false;
   int delayer = 50;

   DotPanel(RedBlack graph) {  
      this.graph = graph;
      addMouseListener(this);
      addMouseMotionListener(this);
   }

   public void run() {
      while (true) {
         repaint();
         try { Thread.sleep(delayer); }
         catch (InterruptedException e) {  break;  }
      }
   }

   Image offscreen;
   Dimension offscreensize;
   Graphics offgraphics;

   int left (Dot dot) {
      Dimension d = getSize();
      double wid = (double)d.width/(1+(1 << dot.level));
      return (int)(wid*(dot.indent+1)) + 15;
   }

   int top(Dot dot) {  return 20+dot.level*50 + 15;  }

   int offset = 28;

   public void paintDot(Graphics g, Dot dot, FontMetrics fm, int ox, int oy) {
      if (dot == null) return;
     
      int x  = left(dot);
      int y  = top(dot);
      int tx = (int)dot.left;
      int ty = (int)dot.top;

      String lbl = String.valueOf(dot.object.getIdent());
      int w = fm.stringWidth(lbl);
      int h = fm.getHeight();
      g.setColor(dot.disp_color);
      g.fillOval(tx+ox-offset, ty+oy, 30, 30);
      if (dot.isCurrent) {
	 g.setColor(new Color(255,214,153));
	 g.drawOval(tx+ox-offset, ty+oy,31,31);
	 g.drawOval(tx+ox-offset, ty+oy,32,32);
	 // g.drawOval(tx+ox-offset, ty+oy,33,33);
      }
      if (dot.disp_color == Color.yellow || dot.disp_color == Color.green)
	 g.setColor(Color.black);
      else
	 g.setColor(Color.white);
      g.drawString(lbl, tx+ox-offset-w/2+15, ty+oy+12+h/2);
      dot.left = (float)(.9*(dot.left-x) + x);
      dot.top = (float)(.9*(dot.top-y) + y);
   }

   public void paintPickedDot(Graphics g, Dot dot, FontMetrics fm) {
      if (dot == null) return;

      int tx = (int)dot.left;
      int ty = (int)dot.top;

      String lbl = String.valueOf(dot.object.getIdent());
      int w = fm.stringWidth(lbl);
      int h = fm.getHeight();
      g.setColor(dot.disp_color);
      g.fillOval(tx-offset, ty, 30, 30);
      if (dot.disp_color == Color.yellow)
	 g.setColor(Color.black);
      else
	 g.setColor(Color.white);
      g.drawString(lbl, tx-offset-w/2+15, ty+12+h/2);
   }

   public void paintEdgesOfDot(Graphics g, Dot dot) {
      if (dot == null || 
          dot == graph.tree.sentinel || 
          dot == graph.tree.rootSentinel) return;
      
      g.setColor(Color.black);
      int x = (int)dot.left+15;
      int y = (int)dot.top+15;
      if (dot.leftTree != null && dot.leftTree != graph.tree.sentinel) {
         int lx = (int)dot.leftTree.left+15;
         int ly = (int)dot.leftTree.top+15;
         g.drawLine(x-offset,y,lx-offset,ly);
      }
      if (dot.rightTree != null && dot.rightTree != graph.tree.sentinel) {
         int rx = (int)dot.rightTree.left+15;
         int ry = (int)dot.rightTree.top+15;
         g.drawLine(x-offset,y,rx-offset,ry);
      }
   }

   public void update(Graphics g) {
      Dimension d = getSize();
      if ((offscreen == null) || (d.width != offscreensize.width) ||
          (d.height != offscreensize.height)) {
         offscreen = createImage(d.width, d.height);
         offscreensize = d;
         offgraphics = offscreen.getGraphics();
         offgraphics.setFont(getFont());
      }

      offgraphics.setColor(graph.getColor());
      offgraphics.fillRect(0, 0, d.width, d.height);
      FontMetrics fm = offgraphics.getFontMetrics();
      Dot dt[] = graph.dot;
      int nd  = graph.ndots;
      for (int i=0 ; i < nd ; i++)
         paintEdgesOfDot(offgraphics, dt[i]);
      try {
	 for (int i=0 ; i < nd ; i++)
	    if (dt[i] != pick) paintDot(offgraphics, dt[i], fm, 0, 0);
	    else paintPickedDot(offgraphics, dt[i], fm);
	 if (graph.newest != null)
	    paintDot(offgraphics, graph.newest, fm, -30, -15);
      } catch (Exception e) {}
      g.drawImage(offscreen, 0, 0, null);
   }

   public void mousePressed (MouseEvent evt) {
      if (graph.msgon) {
	 graph.huh.setText("");
	 graph.msgon = false;
      }
      Dot dot[] = graph.dot;
      for (int i=0 ; i < graph.ndots ; i++) {
         if (dot[i] == null) continue;
         if (evt.getX() - dot[i].left < 0 && evt.getY() - dot[i].top < 30 &&
             evt.getX() > dot[i].left-30 && evt.getY() > dot[i].top) {
            pick = dot[i];
//	    saved_pick = pick;          /***** colorit  *****/
            if (deleteNode == true) {
	       saved_pick = pick;
               deleteNode = false;
               deletingNode = pick;
               deletingNode.disp_color = Color.green;
               removingNode = true;
            }
         }
      }
   }

   public void mouseDragged (MouseEvent evt) {
      if (pick != null) {
         pick.left = evt.getX()+20;
         pick.top = evt.getY()-10;
      }
   }

   public void mouseReleased (MouseEvent evt) {  pick = null;  }

   public void mouseClicked (MouseEvent evt) {  }
   public void mouseEntered (MouseEvent evt) {  }
   public void mouseExited (MouseEvent evt) {  }
   public void mouseMoved (MouseEvent evt) {  }

   public void start() { relaxer = new Thread(this);  relaxer.start(); }
}

public class RedBlack extends Applet implements ActionListener, KeyListener {
   DotPanel panel;
   RBTree tree = null, saved_tree = null;
   Add adder = null;
   Prune pruner = null;
   Dot dot[] = new Dot[100], root = null, newest = null;
   int ndots = 0;
   JButton addbutton, nextbutton, undobutton, colorit,
      restartbutton, tempbutton, delbutton;
   JTextArea huh;
   JComboBox speed, dup;
   Color bgcolor = new Color(190,190,190);
   int number = 0;
   JTextField value, rules, invariant;
   Label label;
   JLabel a1,a2,a3,a4,a5,a6,b1,b2,b3;
   boolean msgon;

   public void init () {
      setBackground(bgcolor);
      setLayout(new BorderLayout());
      tree = new RBTree();

      panel = new DotPanel(this);
      panel.addKeyListener(this);
      panel.setBackground(bgcolor);
      add("Center", panel);

      Panel q = new Panel();
      q.setLayout(new BorderLayout());

      Panel p = new Panel();
      p.setLayout(new GridLayout(2,1));

      Panel p1 = new Panel();
      p1.add(new JLabel("value:",JLabel.RIGHT));
      p1.add(value = new JTextField(5));
      value.setFont(new Font("TimesRoman", Font.PLAIN, 20));
      //      value.addActionListener(this);
      value.setEditable(false);
      value.setBackground(Color.white);
      value.addKeyListener(this);
      System.out.println(value.requestFocusInWindow());
      p1.add(addbutton = new JButton("Add Node"));
      addbutton.addActionListener(this);
      addbutton.addKeyListener(this);
      p1.add(nextbutton = new JButton("Next Step"));
      nextbutton.addActionListener(this);
      nextbutton.addKeyListener(this);
      p1.add(delbutton = new JButton("Delete Node"));
      delbutton.addActionListener(this);
      delbutton.addKeyListener(this);
      p.add(p1);

      p1 = new Panel();
      p1.add(dup = new JComboBox());
      dup.addItem("Don't allow duplicates");
      dup.addItem("Allow duplicates");
      p1.add(restartbutton = new JButton("Restart"));
      restartbutton.addActionListener(this);
      restartbutton.addKeyListener(this);
      p1.add(label = new Label("            ", Label.CENTER));
      p1.add(undobutton = new JButton("Undo"));
      undobutton.addActionListener(this);
      undobutton.addKeyListener(this);
//      p1.add(colorit = new JButton("Color"));  /***** colorit   ****/
//      colorit.addActionListener(this);         /***** colorit   ****/
      p1.add(speed = new JComboBox());
      speed.addActionListener(this);
      speed.addItem("Fast");
      speed.addItem("Slow");
      speed.addItem("Crawl");
      p.add(p1);

      q.add("North",p);

      Panel p2 = new Panel();
      p2.setLayout(new BorderLayout(6,6));

      p1 = new Panel();
      p1.setLayout(new BorderLayout());
      p1.add("North",b1=new JLabel("        Rule:"));
      p1.add("Center",rules = new JTextField(75));
      p1.add("East",a1=new JLabel("        "));
      p1.add("West",a2=new JLabel("        "));
      p2.add("North",p1);

      p1 = new Panel();
      p1.setLayout(new BorderLayout());
      p1.add("North",b2=new JLabel("        Reason:"));
      p1.add("Center",huh = new JTextArea(6,75));
      p1.add("East",a3=new JLabel("        "));
      p1.add("West",a4=new JLabel("        "));
      p2.add("Center",p1);

      p1 = new Panel();
      p1.setLayout(new BorderLayout());
      p1.add("North",b3=new JLabel("        Invariant:"));
      p1.add("Center",invariant = new JTextField(75));
      p1.add("East",a5=new JLabel("        "));
      p1.add("West",a6=new JLabel("        "));
      p2.add("South",p1);

      q.add("Center",p2);

      add("South", q);
      label.setBackground(bgcolor);
      value.setBackground(Color.white);
      rules.setEditable(false);
      rules.setBackground(Color.white);
      huh.setEditable(false);
      huh.setBackground(Color.white);
      invariant.setEditable(false);
      invariant.setBackground(Color.white);
      rules.addKeyListener(this);
      huh.addKeyListener(this);
      invariant.addKeyListener(this);
      a1.addKeyListener(this);
      a2.addKeyListener(this);
      a3.addKeyListener(this);
      a4.addKeyListener(this);
      a5.addKeyListener(this);
      a6.addKeyListener(this);
      b1.addKeyListener(this);
      b2.addKeyListener(this);
      b3.addKeyListener(this);
      initialize();
      value.requestFocus();
      msgon = true;
      String msg1 = 
	 "Click on the panel above the buttons to be able to enter values";
      String msg2 =
	 "Note: the value field (a white box to the right of 'value') does not get a cursor";
      huh.setText("\n\n");
      for (int i=0 ; i < 58 ; i++) huh.append(" ");
      huh.append(msg1+"\n");
      for (int i=0 ; i < 45 ; i++) huh.append(" ");
      huh.append(msg2);
  }

   public void add_one (int number) {
      if (ndots >= 99) return;

      newest = new Dot(number, Color.blue);
      root = tree.rootSentinel.leftTree;
         
      while (true) {
         if (newest != null && adder == null) {
            if ((root = insertDot(newest, root)) == tree.sentinel) {
               dot[ndots++] = newest;
               adder = new Add(this, tree, newest, new IntInorderObject());
               TO to = (TO)adder.next();
               if (to == null) {
                  adder = null;
                  number = 0;
                  tree.level();
                  break;
               }
               tree.level();
               newest = root = null;
            } else if (root == null) { // Done adding a node
               newest = root = null;
               number = 0;
               tree.level();
               break;
            } // otherwise root is set to the next node down the tree
         } else if (adder != null) {  // Adding a node continuing...
            TO to = (TO)adder.next();
            if (to == null) {
               adder = null; 
               number = 0;
               tree.level();
               break;
            }
            tree.level();
         }
      }
   }

   public void quick_add () {
      if (ndots >= 99) return;
      if (label.getText().equals("Deleting") ||
	  label.getText().equals("Adding")) return;

      try {
         int number = Integer.parseInt(value.getText());
         saved_tree = new RBTree(tree);
	 // if tree is empty add a node by hand
	 if (tree.rootSentinel.leftTree == tree.sentinel) {
	    tree.rootSentinel.leftTree = new Dot(tree, number, Color.black);
	    dot = new Dot[100];
	    ndots = 0;
	    dot[ndots++] = tree.rootSentinel.leftTree;
	    tree.level();
	 } else {
	    add_one (number);
	 }
	 value.setText("");
	 label.setBackground(bgcolor);
	 label.setText("");
	 number = 0;
      } catch (Exception e) {}
      value.setText("");
      label.setBackground(bgcolor);
      label.setText("");
      number = 0;
   }

   public void initialize () {
      restart();
      try {
         StringTokenizer t = new StringTokenizer(getParameter("args")," ");
         int number;
         if (t.hasMoreTokens()) {
            number = Integer.parseInt(t.nextToken());
            tree.rootSentinel.leftTree = new Dot(tree, number, Color.black);
            dot[ndots++] = tree.rootSentinel.leftTree;
         }
         while (t.hasMoreTokens()) {
            number = Integer.parseInt(t.nextToken());
            add_one (number);
         }
      } catch (Exception e) {}
   }

   public void setNumber (int n) {
      number *= 10; 
      number += n; 
      if (number != 0) value.setText(String.valueOf(number)); 
      else value.setText("     ");
   }

   public void backup () {
      if (number > 0) {
         number /= 10; 
         if (number > 0) value.setText(String.valueOf(number)); 
         else value.setText("     ");
      } else {
         value.setText("     ");
      }
   }

   public void keyTyped (KeyEvent evt) {
      char key = evt.getKeyChar();
      switch (key) {
      case 'u':  undo();      break;
      case 'U':  undo();      break;
      case 'a':  add();       break;
      case 'A':  add();       break;
      case 'd':  delete();    break;
      case 'D':  delete();    break;
      case 'r':  restart();   break;
      case 'R':  restart();   break;
      case 'n':  next();      break;
      case 'N':  next();      break;
      case '\n': quick_add(); break;
      case '\b': backup();    break;
      case '0':  if (number < 1000) setNumber(0); break;
      case ')':  if (number < 1000) setNumber(0); break;
      case '1':  if (number < 1000) setNumber(1); break;
      case '!':  if (number < 1000) setNumber(1); break;
      case '2':  if (number < 1000) setNumber(2); break;
      case '@':  if (number < 1000) setNumber(2); break;
      case '3':  if (number < 1000) setNumber(3); break;
      case '#':  if (number < 1000) setNumber(3); break;
      case '4':  if (number < 1000) setNumber(4); break;
      case '$':  if (number < 1000) setNumber(4); break;
      case '5':  if (number < 1000) setNumber(5); break;
      case '%':  if (number < 1000) setNumber(5); break;
      case '6':  if (number < 1000) setNumber(6); break;
      case '^':  if (number < 1000) setNumber(6); break;
      case '7':  if (number < 1000) setNumber(7); break;
      case '&':  if (number < 1000) setNumber(7); break;
      case '8':  if (number < 1000) setNumber(8); break;
      case '*':  if (number < 1000) setNumber(8); break;
      case '9':  if (number < 1000) setNumber(9); break;
      case '(':  if (number < 1000) setNumber(9); break;
      }
   }

   public void keyPressed (KeyEvent evt) {}
   public void keyReleased (KeyEvent evt) {}

   public void colorIt() {
      if (panel.saved_pick != null) {
         if (panel.saved_pick.color == Color.red) {
            panel.saved_pick.color = Color.black;
            panel.saved_pick.disp_color = Color.black;
         } else {
            panel.saved_pick.color = Color.red;
            panel.saved_pick.disp_color = Color.red;
         }
      }
   }
                                                                 
   public void delete () {
      if (newest == null && adder == null && 
          !panel.removingNode && !panel.deleteNode && tree != null) {
         saved_tree = new RBTree(tree);
         panel.deleteNode = true;
         label.setBackground(Color.green);
         label.setText("Deleting");
	 invariant.setText("The black count on leaves below 'current' and only those leaves is short by 1");
      }
   }

   public void undo () {
      rules.setText("");
      huh.setText("");
      if (saved_tree == null) return;
      tree = new RBTree(saved_tree);
      Dot dott[] = new Dot[100];
      ndots = tree.setDots(dot, ndots, dott, 0);
      dot = dott;
      tree.level();
      newest = root = null;
      adder = null;
      pruner = null;
      panel.deleteNode = panel.removingNode = false;
      panel.saved_pick = null;
      label.setBackground(bgcolor);
      label.setText("");
      invariant.setText("");
   }

   public void restart () {
      rules.setText("");
      huh.setText("");
      invariant.setText("");
      saved_tree = null;
      tree = new RBTree();
      newest = root = null;
      adder = null;
      pruner = null;
      dot = new Dot[100];
      ndots = 0;
      panel.deleteNode = panel.removingNode = false;
      panel.saved_pick = null;
      label.setBackground(bgcolor);
      label.setText("            ");
      invariant.setText("");
      value.setText("");
      number = 0;
   }

   public void next () {
      if (newest != null && adder == null) {  // Adding a node starting...
	 if (ndots < 99) {
	    if ((root = insertDot(newest, root)) == tree.sentinel) {
	       dot[ndots++] = newest;
	       adder = new Add(this, tree, newest, new IntInorderObject());
	       TO to = (TO)adder.next();
	       if (to == null) {
		  adder = null;
		  label.setBackground(bgcolor);
		  label.setText("            ");
		  invariant.setText("");
		  value.setText("");
		  number = 0;
	       }
	       tree.level();
	       newest = root = null;
	    } else if (root == null) { // Done adding a node
	       newest = root = null;
	       label.setBackground(bgcolor);
	       label.setText("            ");
	       invariant.setText("");
	       value.setText("");
	       number = 0;
	    } // otherwise root is set to the next node down the tree
	 } else {
	    newest = root = null;
	    label.setBackground(bgcolor);
	    label.setText("            ");
	    invariant.setText("");
	    value.setText("");
	    number = 0;
	 }
      } else if (adder != null) {  // Adding a node continuing...
         TO to = (TO)adder.next();
         if (to == null) {
            adder = null; 
            label.setBackground(bgcolor);
            label.setText("            ");
	    invariant.setText("");
            value.setText("");
            number = 0;
         }
         tree.level();
      } else if (panel.removingNode) {  // Removing a node
         if (pruner == null) {
            panel.saved_pick.disp_color = panel.saved_pick.color;
            /************* JVF  moved to a few lines down
            deleteDot(panel.saved_pick);
	    ************/
            pruner = new Prune(this, tree, panel.saved_pick);
         }
         TO to = (TO)pruner.next();
         if (to == null) {
	    /************* JVF    ********/
            deleteDot(panel.saved_pick);
	    /************/
            pruner = null; 
            label.setBackground(bgcolor);
            label.setText("            ");
	    invariant.setText("");
            value.setText("");
            number = 0;
            panel.removingNode = false;
         }
         tree.level();
      }
   }

   public void add () {
      if (newest == null && adder == null && 
          !panel.removingNode && !panel.deleteNode) {
         saved_tree = new RBTree(tree);
         try {
            number = Integer.parseInt(value.getText());
            newest = new Dot(number, Color.blue);
            root = tree.rootSentinel.leftTree;
            label.setBackground(Color.yellow);
            label.setText("Adding");
         } catch (Exception e) {
            value.setText("-=*=-");
         }
      }
   }

   public void fast () { panel.delayer = 50; }
   public void slow () { panel.delayer = 100; }
   public void crawl () { panel.delayer = 150; }

   public void actionPerformed (ActionEvent evt) {
      if (evt.getSource() == delbutton) delete();
      else if (evt.getSource() == undobutton) undo();
      else if (evt.getSource() == restartbutton) restart();
      else if (evt.getSource() == nextbutton) next();
      else if (evt.getSource() == addbutton) add();
      else if (evt.getSource() == value) quick_add();
      else if (evt.getSource() == speed) {
         if (speed.getSelectedItem().equals("Fast")) fast();
         else if (speed.getSelectedItem().equals("Slow")) slow();
         else if (speed.getSelectedItem().equals("Crawl")) crawl();
      }
//      else if (evt.getSource() == colorit) colorIt();  /**** colorit  ****/
   }

   public void deleteDot(Dot d) {
      int m;
      for (int k=0 ; k < ndots ; k++) {
         if (dot[k] == null) continue;
         if (dot[k] == d) {
            dot[k] = null;
            break;
         }
      }
   }

   public Dot insertDot(Dot dot, Dot root) {
      if (root == null) return null;
      if (root == tree.sentinel) return tree.sentinel;
      
      /*  Code to prevent duplicate data objects  */
      if (!dup.getSelectedItem().equals("Allow duplicates")) {
         if (dot.object.getValue() == root.object.getValue()) {
            return null;
         }
      }
      if (dot.object.getValue() <= root.object.getValue()) {
         dot.level = root.level+1;
         dot.indent = 2*root.indent;
         if (root.leftTree == null || root.leftTree == tree.sentinel) {
            return tree.sentinel;
         }
         return root.leftTree;
      } else {
         dot.level = root.level+1;
         dot.indent = 2*root.indent+1;
         if (root.rightTree == null || root.rightTree == tree.sentinel) {
            return tree.sentinel;
         }
         return root.rightTree;
      }
   }

   public void start() {  panel.start();  }

   public Color getColor() {  return bgcolor;  }
}