rb.java

红黑数算法及演示源代码

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.
   float left;     // pixels in from left
   float 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; }
   float setLeft(float lf) { return left = lf; }
   float setTop(float tp)  { return top = tp; }
   void  setLevel(int lv)  { level = lv; }
   void  setIndent(int in) { indent = in; }
   void  setShadow(Dot d)  { shadow = d; }
   void  setNumber(int n)  { number = n; }
   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; }
   float leftOf()      { return left; }
   float 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, saved_pick = null;
   Dot deletingNode;
   Color deletingSaveColor;
   boolean deleteNode = false, removingNode = false;

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

   public void run() {
      while (true) {
         repaint();
         try { Thread.sleep(100 + graph.getNDots()); }
         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) {
      if (dot == null) return;
     
      int x  = left(dot);
      int y  = top(dot);
      int tx = (int)dot.leftOf();
      int ty = (int)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((float)(.75*(dot.leftOf()-x) + x));
      dot.setTop((float)(.75*(dot.topOf()-y) + y));
   }

   public void paintPickedDot(Graphics g, Dot dot, FontMetrics fm) {
      if (dot == null) return;
      
      int tx = (int)dot.leftOf();
      int ty = (int)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) {
      if (dot == null) return;
      
      g.setColor(Color.black);
      int x = (int)dot.leftOf()+15;
      int y = (int)dot.topOf()+15;
      if (dot.leftTreeOf() != null) {
         int lx = (int)dot.leftTreeOf().leftOf()+15;
         int ly = (int)dot.leftTreeOf().topOf()+15;
         g.drawLine(x-offset,y,lx-offset,ly);
      }
      if (dot.rightTreeOf() != null) {
         int rx = (int)dot.rightTreeOf().leftOf()+15;
         int ry = (int)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 (dot[i] == null) continue;
         if (x-dot[i].leftOf() < 0 && y-dot[i].topOf() < 30 &&
             x > dot[i].leftOf()-30 && y > dot[i].topOf()) {
            saved_pick = pick = dot[i];
            if (deleteNode == true) {
               deleteNode = false;
               deletingNode = pick;
               deletingSaveColor = deletingNode.colorOf();
               deletingNode.setColor(Color.green);
               removingNode = true;
            }
            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 void setValue(boolean v) { deleteNode = v; }
   public boolean removingOf() { return removingNode; }
   public Dot dotOf() { return deletingNode; }
   public Color saveColorOf() { return deletingSaveColor; }
   public void setRemoving(boolean v) { removingNode = v; }
}

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);
   Dot pushdownward;
   Dot pushupward;
   Dot t_dot;
   Button addbutton, nextbutton, undobutton, startbutton, 
      tempbutton, delbutton, colorit;
   TextField val;
   Panel p;
   Color bgcolor = new Color(190,190,190);
   Color downSaveColor;
   int step = 0;
   boolean inserting = false;

   Dot[] getDots()   { return dot; }
   int   getNDots()  { return ndots; }
   Dot   getNewest() { return newest; }

   Color getColor() {
      if (rev1 == null && rev2 == null && rev3 == null && 
	  !panel.removingOf() &&
          temp == null && !(head == null && newest != null) &&
          ssindex == 0 && (head != null && head.colorOf() == Color.black)) {
         bgcolor = new Color(190,190,190);
         inserting = false;
      } else if (panel.removingOf()) 
	 bgcolor = new Color(0,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(delbutton = new Button("Delete Node"));
      p.add(colorit = new Button("Color It"));

      StringTokenizer t = new StringTokenizer(getParameter("args")," ");
      int n;
      while (t.hasMoreTokens()) {
	 n = Integer.parseInt(t.nextToken());
	 initinsert(n);
	 do { nextinsert(); } while (inserting);
      }
   }

   public void initinsert(int input_no) {
      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 && !panel.removingOf()) {
	 int num = 0;
	 inserting = true;
	 ndots = insertCopy(head = copyTree(head), dot, 0); /* try it */
	 cndots = insertCopy(chead = copyTree(head), cdot, 0);
	 ssindex = 0;
	 num = input_no;
	 newest = new Dot(num, Color.red);
	 newest.setLevel(0);
	 newest.setIndent(0);
	 temp = head;
	 bgcolor = new Color(0,190,190);
      }
   }

   public void nextinsert() {
      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) 
	 Color leftdot, topdot, rightdot;
         topdot = temp.colorOf();
	 if (temp.leftTreeOf() != null)
	    leftdot=temp.leftTreeOf().colorOf();
	 else 
	    leftdot = Color.blue;
	 if (temp.rightTreeOf() != null)
	    rightdot=temp.rightTreeOf().colorOf();
	 else 
	    rightdot = Color.blue;
	 
	 ss[ssindex++] = temp;
	 
	 if ((temp = insertDot(newest, temp)) == stopdot) {
	    if (stopdot.colorOf()==Color.green) {
	       if (rightdot == Color.black) newest.setColor(Color.black);
	       ss[ssindex-1].setLefttree(newest);
	    } else {
	       if (leftdot == Color.black) newest.setColor(Color.black);
	       ss[ssindex-1].setRighttree(newest);
	    }
	    
	    dot[ndots++] = ss[ssindex] = newest;
	    newest = temp = null;
	 }
      } else if (head == null && newest != null) { // Special case - first dot
	 dot[ndots++] = ss[ssindex] = head = newest;
	 newest.setColor(Color.black);
	 newest = temp = null;
      } 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){
	    ssindex = 0;
	 }