import java.util. *;
import java.awt. *;
import java.io. *;
import java.net. *;
import java.applet.Applet;

/** Execute a splay tree operation on a binary search tree. */

class SplayTreeOperation extends DictionaryOperation implements Runnable {

  /** Initialize with a given Action, snapshot of the current graph
   ** (SimpleGraph), the tree's panel and an IconLibrary */

  SplayTreeOperation(Action a, Tree t, SimpleGraph sg, 
		     SplayTreePanel p, IconLibrary ih)
  {
     super(a, t, sg, (GraphPanel) p, ih);
  }

  private Node whereToSplay = null;

  /** execute the splay after binary search tree operations are
   ** completed */
  public void prologue(int op, Node n) throws InterruptedException {

      if (n == null) return;

      switch (op) {

	case DELETE :
	      Node toDelete = n.deleteWhich();
	      if (toDelete != null)
		whereToSplay = toDelete.parent;
	      else
		whereToSplay = null;
	      break;

	default :
	      whereToSplay = n;
	      break;
      }
  }

  /** execute the splay after binary search tree operations are
   ** completed */
  public void epilogue(int op, Node n) throws InterruptedException {

      if (whereToSplay == null) return;

      switch (op) {

        case PAUSE:	
        case WAIT:	
        case NOOP:	
		return;

	case DELETE:
  	case INSERT:
	case LOCATE:
		whereToSplay.splay (true);
		splay (whereToSplay);
	        waitToSettle (whereToSplay);
		whereToSplay.splay (false);
	      	break;

	default :
	      break;
      }
  }

  void splay (Node n) throws InterruptedException {

    Node p = null;
    Node first, second;  // parent and grandparent
    Node rotating;	 // current rotating node

    n.splay(true);

    int stepNo = 1;

    panel.title("Splay:");

    while (n.parent != null) {

	n.inserting = false;

	waitToSettle(n);
	n.setGraphics();

	p = n.parent;

	if (p.parent != null) {

	    panel.title("Splay (step " + stepNo + "):");

	    boolean x_left = n.isLeft();
	    boolean p_left = p.isLeft();

	    if (x_left == p_left) {
		first = p;
		second = p.parent;
	    }
	    else {
		first = p.parent;
		second = p;
	    }
	    first.working(true);
	    second.working(true);

	    // first rotation 

	    second.rotating(true);

	    Node toRotate = (x_left == p_left) ? n.parent : n;

	    panel.caption((toRotate == n) ? 
			  ("Rotate twice at the selected node (" 
				     + n.value 
				     + ").") : 
			  "First rotate at its parent ... ");

	    rotate (snapshot, toRotate);
	    waitToSettle (toRotate);

	    second.working(false);
	    second.found(false);

	    briefPause();

	    if (toBeDeleted != null) {
	      toBeDeleted.deletePick = false;
	      toBeDeleted.setGraphics();
	    }

	    if (toRotate != n) 
		panel.caption("and then at the selected node ("+n.value+").");
	}
	else {
	    panel.title("Splay:");
	    panel.caption("Rotate at the selected node (" + n.value + ").");
	    first = p;
	    first.working(true);
	}

	rotate(snapshot, n);
	waitToSettle(n);
	briefPause();

	first.working(false);
	first.found(false);
    }
  }
}

/** */
class SplayTreePanel extends GraphPanel implements Runnable {

  SplayTreePanel (SplayTree st, Layout l, Dimension dim, IconLibrary im) {
    super((Graph) st, l, dim, im);
  }

  public void launchAction(int action) {

    if (rotating || pick == null) return;

    Action a = new Action();
    a.op = action;

    switch(action) {

	  case DictionaryOperation.INSERT : 
	    	a.node = insertAndPlace(getInsertValue(pick));
	    	a.node.x = pick.x;
	    	a.node.y = pick.y;
	       	break;

	  case DictionaryOperation.DELETE :
	  case DictionaryOperation.LOCATE :
	    	a.node = pick;
	    	break;

	  default :
	    	break;
    }

    nextAction(a);
    unpick();
  }

  /** */
  public synchronized void startOperation() {
    rotating = true;
    super.startOperation();
  }

  /** */
  public synchronized void endOperation() {
    rotating = false;
    super.endOperation();
  }

  protected void animate (Action a) {

    if (layout.demoMode) {
	follow = a.node;
    }
    SplayTreeOperation splay; 
    splay = new SplayTreeOperation(a,tree,snapshot,this,images);
    Thread t = new Thread(splay);
    tree.continuation(t);
    t.start();
  }
}

public class SplayTree extends Graph {

  SplayTreePanel stPanel;

  protected void launchAction (Object arg) {
     if ("Insert".equals (arg)) 
        stPanel.launchAction(DictionaryOperation.INSERT);
     else if ("Delete".equals (arg)) 
	stPanel.launchAction(DictionaryOperation.DELETE);
     else if ("Locate".equals (arg))
	stPanel.launchAction(DictionaryOperation.LOCATE);
  }

  public void init() {
      initPrelude();

      Dimension d = size();
      Dimension pDim = new Dimension(d.width, d.height-100);

      stPanel = new SplayTreePanel (this, layout, pDim, images);
      panel = stPanel;

      add ("Center", panel);
      showChoices();
      showButtons();
  }
  public void start() {
      stPanel.initialTree = edges;
      stPanel.start();
  }
  public void stop() {
      stPanel.stop();
  }
}