/*
    Copyright 1996 Burton Rosenberg, all rights reserved
*/

// version 9/22/96 9:33 PM
// version 9/23/96 9:41 PM
// became RotateTree 10/18/96 1:00 PM
// version 10/22/96 4:25 PM 


// A Brain-Dead version of Rotate Tree. Student must write
// the single and double rotate code.


import java.awt.* ;
import java.applet.Applet ;

public class RotateTree extends Applet
{
   Tree t ;
   TreeActions pOne ;
   
   public void init() 
   {
      t = new Tree() ;
      setLayout( new BorderLayout() ) ; 
      TreeView    pTwo = new TreeView( t ) ;
      pOne = new TreeActions( t, pTwo ) ;
      add("Center", pTwo ) ;
      add("North", pOne ) ;      
      validate() ;      
   }

   public boolean mouseUp(Event evt, int x, int y ) {
      if ( t.getPicked().length()>0 )
         switch( pOne.mode ) {
            case TreeActions.SINGLEROTATE:
                System.out.println("Do a single rotate at "+t.getPicked()) ;
                break ;
            case TreeActions.DOUBLEROTATE:
                System.out.println("Do a double rotate at "+t.getPicked()) ;
                break ;
         }
      return true ;
   }

   public String getAppletInfo() {
      return "RotateTree by Burton Rosenberg (c) 1996 vers 10/18/96" ;
   }
   
}

class TreeActions extends Panel
{
    Button bOne ;
    Button bTwo ;
    Label lOne ;
    TextField tfOne ;
    TreeView tv ;
    Checkbox showName, singleRotate, doubleRotate ;
    CheckboxGroup cbg ;
    Tree t ;
    
    static final int SHOWNAME = 0 ;
    static final int SINGLEROTATE = 1 ;
    static final int DOUBLEROTATE = 2 ;

    int mode = SHOWNAME ;

    TreeActions(Tree t, TreeView tv )
    {
       super() ;   // construct the Panel
       this.t = t ;
       this.tv = tv ; 
        
       bOne = new Button("Clear Tree" ) ;
       bTwo = new Button("Insert to Tree" ) ;
       lOne = new Label("Value to Insert:") ;
       tfOne = new TextField(15) ;
       cbg = new CheckboxGroup() ;
       showName = new Checkbox( "Show Name", cbg, true ) ;
       singleRotate = new Checkbox( "Single Rotate", cbg, false ) ;
       doubleRotate = new Checkbox( "Double Rotate", cbg, false ) ;
       
       setLayout( new GridLayout( 2,4 ) ) ;
       this.add(bOne) ;
       this.add(bTwo) ;
       this.add(lOne) ;
       this.add(tfOne) ;
       this.add(showName) ; 
       this.add(singleRotate) ;
       this.add(doubleRotate) ;
    }
    
    public boolean action( Event evt, Object arg ) 
    {
       if ( evt.target == bOne )
       {
          // Clear Tree
          t.delete() ;
          tv.repaint() ;
          tfOne.requestFocus() ;
          return true ;
       }
       if ( evt.target == bTwo )
       {
          // Insert to Tree
           String s = tfOne.getText() ;
           s = s.trim() ;
           if ( s.length() > 0 )
           {
             // ignore empty string inserts 
             t.insert( s ) ;
             tv.repaint() ;
           }
           tfOne.setText("") ;
           tfOne.requestFocus() ;
           return true ;
       }
       if ( evt.target == showName ) 
       {
          mode = SHOWNAME ;
          return true ;
       }
       if ( evt.target == singleRotate ) 
       {
          mode = SINGLEROTATE ;
          return true ;
       }
       if ( evt.target == doubleRotate ) 
       {
          mode = DOUBLEROTATE ;
          return true ;
       }
       return false ;
    }
    
}

class TreeNode
{

   private TreeNode leftChild ;
   private TreeNode rightChild ;
   private String content  ;
   private boolean red  ;
   static TreeNode nullNode = new TreeNode("") ;
   
   static TreeNode getNullNode() { return nullNode ; }

   TreeNode( String content) {
      leftChild = rightChild = nullNode ;
      red =false ;
      this.content = content ;
   }

   TreeNode getLeftChild() 
      { return leftChild ; }
      
   TreeNode getRightChild() 
      { return rightChild ; }
      
   String getContent() 
      { return content ; }

   void setLeftChild( TreeNode n ) 
      { leftChild = n ; }
      
   void setRightChild( TreeNode n ) 
      { rightChild = n ; }
      
   void setContent( String s ) 
      { content = s ; }
   
   boolean isRed() { return red ; }
   boolean isBlack() { return (! red ) ; }
   
   void setRed() { red = true ; }
   void setBlack() { red = false ; }
      
}

class Tree
{
   private TreeNode anchor ;
   private TreeNode leaf ;
   private String picked ;
   
   Tree() 
   { 
      leaf = TreeNode.getNullNode() ;
      anchor = new TreeNode( "" ) ;
      // point left child back to itself, so that, after
      // a split, and gg reattaches g, in case of a short
      // tree, (i.e. just anchor and the root) gg reattaches 
      // to itself.
      anchor.setLeftChild( anchor ) ;
      picked = "" ;
   }
   
   void delete() {
      anchor = new TreeNode( "" ) ;
      anchor.setLeftChild( anchor ) ;
   }
   
   TreeNode getRoot () {   
      return anchor.getRightChild() ;
   }

   TreeNode insert( String content )
   {
   
      TreeNode n ;
      TreeNode np ;     
      boolean lastWentLeft ;

      np = anchor ;
      n = anchor.getRightChild() ;
      lastWentLeft = false ;
      // INVARIANT: np is the parent node of n.

      while ( n!=leaf )
      {
	     np = n ;
	     if ( n.getContent().compareTo( content ) > 0 )
	     {
	        // go left
           lastWentLeft = true ;
	        n = n.getLeftChild() ;
	     }
	     else 
         {
	        // go right
            lastWentLeft = false ;
	         n = n.getRightChild() ;
	      }
       }

       // ASSERT: lastWentLeft set inside while loop
       if ( lastWentLeft )
       {
	  // add as a left child of np
	  n = new TreeNode( content ) ;
	  np.setLeftChild( n ) ;
       }
       else
       {
	  n = new TreeNode( content ) ;
	  np.setRightChild( n ) ;
       }

       return n ;
   }

   void setPicked( String s ) { picked = s ; }
   String getPicked() { return picked ; }

}

class TreeView extends Panel
{
   Tree t ;
 
   TreeView( Tree t ) {
       super() ;    // construct the Panel
       this.t = t ;
   }
   
   public void repaint() {  
       super.repaint() ;
   }
      
   public boolean mouseDown(Event evt, int x, int y ) {
      pickx = x ;
      picky = y ;
      nodePick = true ;
      repaint() ;
      return true ;
   }

   public boolean mouseUp(Event evt, int x, int y ) {
      nodePick = false ;
      repaint() ;
      // on mouseUp: also process parent, so return false
      //   (this is an unpardonable hack!)
      return false ;
   }

   boolean nodePick = false ;
   int pickx, picky ;
      
   Dimension d ;
   final int YSKIP = 20 ;
   final int BOXSIZE = 4 ;
   final int HALFBOXSIZE = 2 ; // must be half of BOXSIZE
   
   void draw( Graphics gc, TreeNode n, int k, int twoPwrK, int gOfK, 
      int px, int py) {
   
      // let width be [-1,1], then a node at level k, whose path from
      // the root is b_1 b_2 ... b_k, where b_i = 1 for descend left and
      // b_i = 0 for descend right, b_0 is defined to be 0, then
      // S(n) = sum_{0<i<=k} (-1)^b_i (1/2)^i
      // To keep everything in integers, let G(n) = 2^k S(n), where k is
      // the depth of n (the root is at depth 0). The
      // Recursion formula follows:
      //    if the path to m give G(m), and n is a left child of m,
      //       then G(n) = 2 G(m) - 1, and if n is a right child of m,
      //       then G(n) = 2 G(m) + 1.

      if ( n != nullNode )
      {   
         // draw n (1) calculate position.
         int x = (( gOfK + twoPwrK ) * d.width ) / ( twoPwrK * 2 ) ;
         int y = YSKIP * k + 3*BOXSIZE ;
         
         // if k>0 draw lines
         if ( k > 0 ) 
         {
            if ( n.isRed() ) gc.setColor( Color.red ) ;
            else gc.setColor( Color.black ) ;
            gc.drawLine( px, py, x, y ) ;
         }
         
	     draw( gc, n.getLeftChild(), k+1, 2*twoPwrK, 2*gOfK-1, x, y ) ;
 	     draw( gc, n.getRightChild(), k+1, 2*twoPwrK, 2*gOfK+1, x, y ) ;
 	     
 	     if ( n.isRed() ) gc.setColor( Color.red ) ;
         else gc.setColor( Color.black ) ;
 	     gc.fillRect( x-HALFBOXSIZE, y-HALFBOXSIZE, BOXSIZE, BOXSIZE ) ;
 	     if ( nodePick ) 
 	     {
 	         // label this node, if it is picked
 	         if ( x-BOXSIZE < pickx && x+BOXSIZE > pickx 
 	            && y-BOXSIZE < picky && y+BOXSIZE > picky ) 
 	         {
 	               foundx = x ;
 	               foundy = y ;
 	               pickFound = true ; 	               
 	               foundString = n.getContent() ;
 	         }
 	      }
 	  }	  
   }

   String foundString ;
   int foundx, foundy ;
   boolean pickFound ;
   TreeNode nullNode ;
   
   public void paint(Graphics gc)
   {
      //System.out.println("TreeView.paint: entered") ;
      d = size() ;
      pickFound = false ;
      nullNode = TreeNode.getNullNode() ;
      
      draw(gc, t.getRoot(), 0, 1, 0, -1, -1 ) ;
      if (pickFound) 
      {
         gc.setColor( getBackground() ) ;
         FontMetrics fm = gc.getFontMetrics() ;
         gc.fillRect( foundx+BOXSIZE, foundy - fm.getAscent(),
            fm.stringWidth( foundString )+2*BOXSIZE, fm.getHeight() ) ;
         gc.setColor( Color.black ) ;
         gc.drawString( foundString, foundx+2*BOXSIZE, foundy ) ;
   
         t.setPicked( foundString ) ;
      }
      else 
      {
         t.setPicked( "" ) ;
      }      
   }   
  
}