Red/Black Trees (animation)

import java.io.*;
import java.util.*;
import java.awt.*;

class Dot
{
   int level;    // 0 is top, 1 is next, etc.
   int indent;   // 0 is leftmost, 1 is next, etc.
   int left;     // pixels in from left
   int top;      // pixels in from top
   Dot leftTree;
   Dot rightTree;
   int number;
   Dot shadow;
   Color color;

   public Dot(int n, Color clr)
   {
      number = n;
      color = clr;
      leftTree = null;
      rightTree = null;
      shadow = null;
   }

   int  numberOf()        { return number; }
   int  setLeft(int lf)   { return left = lf; }
   int  setTop(int tp)    { return top = tp; }
   void setLevel(int lv)  { level = lv; }
   void setIndent(int in) { indent = in; }
   void setShadow(Dot d)  { shadow = d; }
   void setLefttree (Dot lt)
   {
      leftTree = lt;
      lt.setIndent(2*indent);
      lt.setLevel(level+1);
   }
   void setLeftTree (Dot lt)  { leftTree = lt; }
   void setRightTree (Dot rt) { rightTree = rt; }
   void setRighttree(Dot rt)
   {
      rightTree = rt;
      rt.setIndent(2*indent+1);
      rt.setLevel(level+1);
   }
   void setColor(Color c) { color = c; }
   Dot  shadowOf()    { return shadow; } 
   Dot  rightTreeOf() { return rightTree; }
   Dot  leftTreeOf()  { return leftTree; }
   int  leftOf()      { return left; }
   int  topOf()       { return top; }
   int  levelOf()     { return level; }
   int  indentOf()    { return indent; }
   Color colorOf()    { return color; }
}

class DotPanel extends Panel implements Runnable
{
   RB graph;
   Thread relaxer;
   Dot pick;

   DotPanel(RB graph) {  this.graph = graph;  }

   public void run()
   {
      while (true)
      {
         repaint();
         try
         {
            Thread.sleep(85 + graph.getNDots()/2);
	 }
         catch (InterruptedException e) {  break;  }
      }
   }

   Image offscreen;
   Dimension offscreensize;
   Graphics offgraphics;

   int left(Dot dot)
   {
      Dimension d = size();
      double wid = (double)d.width/(1+(1 << dot.levelOf()));
      return (int)(wid*(dot.indentOf()+1)) + 15;
   }

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

   int offset = 28;

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

      String lbl = String.valueOf(dot.numberOf());
      int w = fm.stringWidth(lbl);
      int h = fm.getHeight();
      g.setColor(dot.colorOf());
      g.fillOval(tx+ox-offset, ty+oy, 30, 30);
      g.setColor(Color.white);
      g.drawString(lbl, tx+ox-offset-w/2+15, ty+oy+12+h/2);

      dot.setLeft((dot.leftOf()+x)/2);
      dot.setTop((dot.topOf()+y)/2);
   }

   public void paintPickedDot(Graphics g, Dot dot, FontMetrics fm)
   {
      int tx = dot.leftOf();
      int ty = dot.topOf();

      String lbl = String.valueOf(dot.numberOf());
      int w = fm.stringWidth(lbl);
      int h = fm.getHeight();
      g.setColor(dot.colorOf());
      g.fillOval(tx-offset, ty, 30, 30);
      g.setColor(Color.white);
      g.drawString(lbl, tx-offset-w/2+15, ty+12+h/2);
   }

   public void paintEdgesOfDot(Graphics g, Dot dot)
   {
      g.setColor(Color.black);
      int x = dot.leftOf()+15;
      int y = dot.topOf()+15;
      if (dot.leftTreeOf() != null)
      {
         int lx = dot.leftTreeOf().leftOf()+15;
         int ly = dot.leftTreeOf().topOf()+15;
         g.drawLine(x-offset,y,lx-offset,ly);
      }
      if (dot.rightTreeOf() != null)
      {
         int rx = dot.rightTreeOf().leftOf()+15;
         int ry = dot.rightTreeOf().topOf()+15;
         g.drawLine(x-offset,y,rx-offset,ry);
      }
   }

   public void update(Graphics g)
   {
      Dimension d = size();
      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.getDots();
      int nd  = graph.getNDots();
      for (int i=0 ; i < nd ; i++)
         paintEdgesOfDot(offgraphics, dt[i]);
      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.getNewest() != null)
         paintDot(offgraphics, graph.getNewest(), fm, -30, -15);
      g.drawImage(offscreen, 0, 0, null);
   }

   public boolean mouseDown(Event evt, int x, int y)
   {
      Dot dot[] = graph.getDots();
      for (int i=0 ; i < graph.getNDots() ; i++)
      {
         if (x-dot[i].leftOf() < 0 && y-dot[i].topOf() < 30 &&
             x > dot[i].leftOf()-30 && y > dot[i].topOf())
         {
            pick = dot[i];
            return true;
         }
      }
      return true;
   }

   public boolean mouseDrag(Event evt, int x, int y)
   {
      if (pick != null)
      {
         pick.setLeft(x+20);
         pick.setTop(y-10);
      }
      return true;
   }

   public boolean mouseUp(Event evt, int x, int y)
   {
      pick = null;
      return true;
   }

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

public class RB extends java.applet.Applet
{
   DotPanel panel;
   Dot shadow;
   int sysLock = 0;
   Dot cdot[] = new Dot[100];
   int cndots = 0;
   Dot dot[] = new Dot[100];
   int ndots = 0;
   Dot ss[] = new Dot[100];
   Dot rev1 = null, rev2 = null, rev3 = null;
   int ssindex = 0;
   Dot head = null;
   Dot chead = null;
   Dot temp = null;
   Dot newest = null;
   Dot stopdot = new Dot(0, Color.black);
   Button addbutton, nextbutton, undobutton, startbutton, tempbutton;
   TextField val;
   Panel p;
   Color bgcolor = new Color(190,190,190);

   Dot[] getDots()   { return dot; }
   int   getNDots()  { return ndots; }
   Dot   getNewest() { return newest; }
   Color getColor()
   {
      if (rev1 == null && rev2 == null && rev3 == null &&
          temp == null && !(head == null && newest != null) &&
          ssindex == 0 && (head != null && head.colorOf() == Color.black))
      {
         bgcolor = new Color(190,190,190);
      }
      return bgcolor;
   }

   public void init()
   {
      setLayout(new BorderLayout());

      panel = new DotPanel(this);
      add("Center", panel);
      p = new Panel();
      add("South", p);
      p.add(startbutton = new Button("Restart"));
      p.add(undobutton = new Button("Undo"));
      p.add(val = new TextField(5));
      p.add(addbutton = new Button("Add Node"));
      p.add(nextbutton = new Button("Next Step"));
      p.add(new Button("Delete Node (future)"));
   }

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

   Dot copyTree(Dot root)
   {
      if (root == null) return null;
      Dot dot = new Dot(root.numberOf(), root.colorOf());
      dot.setTop(root.topOf());
      dot.setLeft(root.leftOf());
      dot.setLevel(root.levelOf());
      dot.setIndent(root.indentOf());
      dot.setLeftTree(copyTree(root.leftTreeOf()));
      dot.setRightTree(copyTree(root.rightTreeOf()));
      root.setShadow(dot);
      return dot;
   }

   int insertCopy(Dot root, Dot p[], int ss)
   {
      if (root == null) return ss;
      p[ss++] = root;
      ss = insertCopy(root.leftTreeOf(), p, ss);
      ss = insertCopy(root.rightTreeOf(), p, ss);
      return ss;
   }

   void reLevel(Dot dot, int ind, int lvl)
   {
      if (dot == null) return;
      dot.setLevel(lvl);
      dot.setIndent(ind);
      reLevel(dot.leftTreeOf(),  2*ind, lvl+1);
      reLevel(dot.rightTreeOf(), 2*ind+1 , lvl+1);
   }

   void leftRotate(Dot chld, Dot prnt)
   {
      prnt.setLeftTree(chld.rightTreeOf());
      chld.setRightTree(prnt.leftTreeOf().leftTreeOf());
      prnt.leftTreeOf().setLeftTree(chld);
      reLevel(head, 0, 0);
   }

   void srightRotate(Dot chld, Dot prnt)
   {
      prnt.setRightTree(chld.leftTreeOf());
      chld.setLeftTree(prnt.rightTreeOf().rightTreeOf());
      prnt.rightTreeOf().setRightTree(chld);
      reLevel(head, 0, 0);
   }

   void rightRotate(Dot chld, Dot prnt)
   {
      prnt.setLeftTree(chld.leftTreeOf());
      chld.setLeftTree(prnt.leftTreeOf().rightTreeOf());
      prnt.leftTreeOf().setRightTree(chld);
      reLevel(head, 0, 0);
   }

   void sleftRotate(Dot chld, Dot prnt)
   {
      prnt.setRightTree(chld.rightTreeOf());
      chld.setRightTree(prnt.rightTreeOf().leftTreeOf());
      prnt.rightTreeOf().setLeftTree(chld);
      reLevel(head, 0, 0);
   }

   void rightRotate(Dot dot)
   {
      head = dot.leftTreeOf();
      dot.setLeftTree(head.rightTreeOf());
      head.setRightTree(dot);
      reLevel(head, 0, 0);
   }

   void sleftRotate(Dot dot)
   {
      head = dot.rightTreeOf();
      dot.setRightTree(head.leftTreeOf());
      head.setLeftTree(dot);
      reLevel(head, 0, 0);
   }
  
   int upward()
   {
      if (ssindex > 0)
      {
         if (ss[ssindex-1].colorOf() == Color.red &&
             ss[ssindex].colorOf() == Color.red)
         {
            if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].leftTreeOf() &&
                ss[ssindex-1] == ss[ssindex-2].leftTreeOf())
            {
               if (ss[ssindex-2].rightTreeOf() == null ||
                   ss[ssindex-2].rightTreeOf().colorOf() == Color.black)
               {
                  if (ssindex > 2)
                  {
                     if (ss[ssindex-3].leftTreeOf() == ss[ssindex-2])
                        rightRotate(ss[ssindex-2], ss[ssindex-3]);
                     else
                        srightRotate(ss[ssindex-2], ss[ssindex-3]);
                     play(getCodeBase(), "audio/ah.au");
                     rev1 = ss[ssindex-1];
                     rev2 = ss[ssindex-2];
                     ss[ssindex-2] = ss[ssindex-1];
                     ssindex -= 2;
                     return 1;
                  }
                  else
                  {
                     rightRotate(ss[ssindex-2]);
                     play(getCodeBase(), "audio/ooh.au");
                     rev1 = head;
                     rev2 = head.rightTreeOf();
                     ssindex = 0;
                     return 1;
                  }
               }
               else
               {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            }
            else
            if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].rightTreeOf() &&
                ss[ssindex-1] == ss[ssindex-2].leftTreeOf())
            {
               if (ss[ssindex-2].rightTreeOf() == null ||
                   ss[ssindex-2].rightTreeOf().colorOf() == Color.black)
               {
                  leftRotate(ss[ssindex-1], ss[ssindex-2]);
                  play(getCodeBase(), "audio/ah.au");
                  Dot tt = ss[ssindex];
                  ss[ssindex] = ss[ssindex-1];
                  ss[ssindex-1] = tt;
                  return 1;
               }
               else
               {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            }
            else
            if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].rightTreeOf() &&
                ss[ssindex-1] == ss[ssindex-2].rightTreeOf())
            {
               if (ss[ssindex-2].leftTreeOf() == null ||
                   ss[ssindex-2].leftTreeOf().colorOf() == Color.black)
               {
                  if (ssindex > 2)
                  {
                     if (ss[ssindex-3].rightTreeOf() == ss[ssindex-2])
                        sleftRotate(ss[ssindex-2], ss[ssindex-3]);
                     else
                        leftRotate(ss[ssindex-2], ss[ssindex-3]);
                     play(getCodeBase(), "audio/ooh.au");
                     rev1 = ss[ssindex-1];
                     rev2 = ss[ssindex-2];
                     ss[ssindex-2] = ss[ssindex-1];
                     ssindex -= 2;
                     return 1;
                  }
                  else
                  {
                     sleftRotate(ss[ssindex-2]);
                     play(getCodeBase(), "audio/ooh.au");
                     rev1 = head;
                     rev2 = head.leftTreeOf();
                     ssindex = 0;
                     return 1;
                  }
               }
               else
               {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            }
            else
            if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].leftTreeOf() &&
                ss[ssindex-1] == ss[ssindex-2].rightTreeOf())
            {
               if (ss[ssindex-2].leftTreeOf() == null ||
                   ss[ssindex-2].leftTreeOf().colorOf() == Color.black)
               {
                  srightRotate(ss[ssindex-1], ss[ssindex-2]);
                  play(getCodeBase(), "audio/ah.au");
                  Dot tt = ss[ssindex];
                  ss[ssindex] = ss[ssindex-1];
                  ss[ssindex-1] = tt;
                  return 1;
               }
               else
               {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            }
         }
         else
	 {
            return 0;
	 }
      }
      return 0;
   }

   Dot insertDot(Dot dot, Dot root)
   {
      if (root == null) return null;

      if (dot.numberOf() == root.numberOf())
      {
         play(getCodeBase(), "audio/drip.au");
         return newest = null;
      }
      else
      if (dot.numberOf() < root.numberOf())
      {
         dot.setLevel(root.levelOf()+1);
         dot.setIndent(2*root.indentOf());
         if (root.leftTreeOf() == null)
         {
            stopdot.setColor(Color.green);
            return stopdot;
         }
         return root.leftTreeOf();
      }
      else
      {
         dot.setLevel(root.levelOf()+1);
         dot.setIndent(2*root.indentOf()+1);
         if (root.rightTreeOf() == null)
         {
            stopdot.setColor(Color.yellow);
            return stopdot;
         }
         return root.rightTreeOf();
      }
   }

   Dot reverseColor(Dot dot)
   {
      if (dot.colorOf() == Color.black) dot.setColor(Color.red);
      else
      if (dot.colorOf() == Color.red) dot.setColor(Color.black);
      return null;
   }

   public boolean action(Event evt, Object arg)
   {
      if (evt.target.equals(startbutton))
      {
         ndots = cndots = ssindex = 0;
         head = chead = rev1 = rev2 = rev3 = newest = temp = null;
         for (int i=0 ; i < 100 ; i++) { dot[i] = cdot[i] = ss[i] = null; }
         bgcolor = new Color(190, 190, 190);
         return super.action(evt, arg);
      }
      else
      if (evt.target.equals(undobutton))
      {
         if (chead == null) return super.action(evt, arg);
         for (int i=0 ; i < ndots ; i++)
	 {
            if ((shadow = dot[i].shadowOf()) != null)
	    {
               shadow.setLeft(dot[i].leftOf());
               shadow.setTop(dot[i].topOf());
	    }
	 }
         for (int i=0 ; i < cndots ; i++) { dot[i] = cdot[i]; ss[i] = null; }
         ndots = cndots;
         head = chead;
         chead = null;
         rev1 = rev2 = rev3 = newest = temp = null;
         ssindex = 0;
         return super.action(evt, arg);
      }
      else
      if (evt.target.equals(addbutton))
      {
         if (rev1 != null || rev2 != null || rev3 != null ||
             temp != null || (head == null && newest != null) ||
             ssindex != 0 || (head != null && head.colorOf() != Color.black))
	 {
            play(getCodeBase(), "audio/ooh.au");
	 }
         else
         if (newest == null)
         {
            cndots = insertCopy(chead = copyTree(head), cdot, 0);
            ssindex = 0;
            int num = Integer.parseInt(val.getText());
            newest = new Dot(num, Color.red);
            newest.setLevel(0);
            newest.setIndent(0);
            temp = head;
            bgcolor = new Color(0,190,190);
         }
         return super.action(evt, arg);
      }
      else
      if (evt.target.equals(nextbutton))
      {
         if (rev1 != null || rev2 != null || rev3 != null)
         {
            if (rev1 != null)  rev1 = reverseColor(rev1);
            if (rev2 != null)  rev2 = reverseColor(rev2);
            if (rev3 != null)  rev3 = reverseColor(rev3);
         }
         else
         if (temp != null) // Insert the dot (way down)
         {
            ss[ssindex++] = temp;
            if ((temp = insertDot(newest, temp)) == stopdot)
            {
               if (stopdot.colorOf()==Color.green)
                 ss[ssindex-1].setLefttree(newest);
               else
                 ss[ssindex-1].setRighttree(newest);
               dot[ndots++] = ss[ssindex] = newest;
               newest = temp = null;
               play(getCodeBase(), "audio/ooh.au");
            }
         }
         else
         if (head == null && newest != null)  // Special case - first dot
         {
            dot[ndots++] = ss[ssindex] = head = newest;
            newest.setColor(Color.black);
            newest = temp = null;
            play(getCodeBase(), "audio/whoopy.au");
         }
         else
         if (ssindex > 0)
         {
            int tell;
            if ((tell = upward()) == 2)
            {
               if (rev1 != null) rev1 = reverseColor(rev1);
               if (rev2 != null) rev2 = reverseColor(rev2);
               if (rev3 != null) rev3 = reverseColor(rev3);
            }
            else
            if (tell == 0 && rev1 == null && rev2 == null && rev3 == null)
	    {
              play(getCodeBase(), "audio/train.au");
              ssindex = 0;
	    }
         }
         else
         if (head.colorOf() != Color.black)
            head.setColor(Color.black);

         if (rev1 == null && rev2 == null && rev3 == null &&
             temp == null && !(head == null && newest != null) &&
             ssindex == 0 && (head != null && head.colorOf() == Color.black))
	 {
            play(getCodeBase(), "audio/train.au");
            bgcolor = new Color(190,190,190);
	 }
      }
      return super.action(evt, arg);
   }
}