/*
    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
// version 11/7/96  implement single rotate, and synchronize on
//     tree update 
// Nov 24 96 10:13 became SplayTree.java
//    2:14 PM checkin.
//    4:59 PM checkout. Making it look nice.


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

public class SplayTree extends Applet
{
   Tree t ;
   TreeActions pOne ;
   TreeView pTwo ;
   
   public void init() 
   {
      t = new Tree() ;
      setLayout( new BorderLayout() ) ; 
      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) && (pOne.splayMode) )
         t.splayTree(t.getPicked()) ;
      pTwo.repaint() ;
      return true ;
   }

   public String getAppletInfo() {
      return "SplayTree by Burton Rosenberg (c) 1996  Nov 24 1996" ;
   }
   
}

class TreeActions extends Panel
{
    Button bOne ;
    Button bTwo ;

    TextField tfOne ;
    TreeView tv ;
    
    Checkbox cbNamesYes, cbNamesNo ;
    Checkbox cbSplayYes, cbSplayNo ;
    CheckboxGroup cbgSplay, cbgNames ;
    Label namesLabel, splayLabel ;
    
    Tree t ;
    
    boolean splayMode ;

    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" ) ;
    
       tfOne = new TextField(15) ;
       
       namesLabel = new Label("Show names?") ;
       splayLabel = new Label("Splay at picked?") ;
       cbgSplay = new CheckboxGroup() ;
       cbgNames = new CheckboxGroup() ;
       cbNamesYes = new Checkbox( "Yes", cbgNames, true ) ;
       cbNamesNo = new Checkbox( "No", cbgNames, false ) ;
       tv.setDrawNames(true) ;
       cbSplayYes = new Checkbox( "Yes", cbgSplay, true ) ;
       cbSplayNo = new Checkbox( "No", cbgSplay, false ) ;
       splayMode = true ;
       
       setLayout( new GridLayout( 3,3 ) ) ;
       this.add(bOne) ;
       this.add(bTwo) ;
     
       this.add(tfOne) ;
       
       this.add(namesLabel) ; 
       this.add(cbNamesYes) ;
       this.add(cbNamesNo) ;
       this.add(splayLabel) ; 
       this.add(cbSplayYes) ;
       this.add(cbSplayNo) ;
       
       validate() ;
    }
    
    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 == cbNamesYes )  {
          tv.setDrawNames( true ) ;
          tv.repaint() ;
          return true ;
       }
       
       if ( evt.target == cbNamesNo )  {
          tv.setDrawNames( false ) ;
          tv.repaint() ;
          return true ;
       }
       
       if ( evt.target == cbSplayYes )  {
          splayMode = true ;
          return true ;
       }
       
       if ( evt.target == cbSplayNo ) {
          splayMode = false ;
          return true ;
       }
       
       return false ;
    }
    
}

class TreeNode
{

   private TreeNode leftChild ;
   private TreeNode rightChild ;
   private String content  ;
   static TreeNode nullNode = new TreeNode("") ;
   private int x, y ;
   
   static TreeNode getNullNode() { return nullNode ; }

   TreeNode( String content) {
      leftChild = rightChild = nullNode ;
      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 false ; } // for Red/Black implementation
   
   void setXY( int x, int y ) {
      this.x = x ;
      this.y = y ;
   }
   
   int getX() { return x ; }
   int getY() { return y ; }  
    
}

class Tree
{
   public TreeNode anchor ;
   private TreeNode leaf ;
   private String picked ;
   
   Tree() 
   { 
      leaf = TreeNode.getNullNode() ;
      anchor = new TreeNode( "" ) ;
      // point left child back 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 ; }

   private TreeNode singleRotateAux(TreeNode parent, boolean onLeftChild ) {
    
     TreeNode newParent ;

     if ( onLeftChild ) {
        // on the left
        newParent = parent.getLeftChild() ;
        parent.setLeftChild( newParent.getRightChild() ) ;
        newParent.setRightChild( parent ) ;
     } else {
        // on the right
        newParent = parent.getRightChild() ;
        parent.setRightChild( newParent.getLeftChild() ) ;
        newParent.setLeftChild( parent ) ;
     }
     return newParent ;
   }
    
   int descentPath ;       // global for splayTreeAux
   boolean evenLevel ;     // global for splayTreeAux  
   
   void splayTree( String nodeToSplay ) { 

      try {
        anchor.setRightChild( 
           splayTreeAux( anchor.getRightChild(), nodeToSplay ) ) ;     
        if (  !evenLevel ) {
           // the right child of the dummy anchor did not get splayed
           if ( (descentPath & 0x01) == 1 ) {
              // right child of root
              anchor.setRightChild( singleRotateAux( anchor.getRightChild(), false ) ) ;
           } else {
              // left child of root
              anchor.setRightChild( singleRotateAux( anchor.getRightChild(), true ) ) ;
           }
        }
        
      } catch ( Exception e ) {
         System.out.println("splayTree: exception thrown") ;
      }
      
   } 
   
   private TreeNode splayTreeAux(TreeNode n, String s)
   throws Exception { 
   
//System.out.println("splayTreeAux: " + n.getContent() ) ;

      if ( n == leaf ) // something's wrong
         throw new Exception() ;
   
      // processing on the way down.
      int i = n.getContent().compareTo( s )  ;
      if ( i > 0 ) {
         // go left
         n.setLeftChild( splayTreeAux( n.getLeftChild(), s )) ;
         descentPath = descentPath<<1 ;   
      }
      else if ( i < 0 ) {
         // go right
         n.setRightChild( splayTreeAux( n.getRightChild(), s )) ;
         descentPath = (descentPath<<1) + 1 ;
      }
      else { // ( i==0 ) 
         evenLevel = true ;
         descentPath = 0 ; // unnecessary assignment done for stylistic reasons.
         return n ; 
         // BREAK HERE!   
      }
      evenLevel = ! evenLevel ;
      // only get here is i is not 0
      
      // processing on the way up. 
      if ( evenLevel ) {
         // splay.
//  System.out.println("splayTreeAux: doing dbl rotate "+(descentPath&0x03)) ;
     
        switch( descentPath & 0x03 ) {

        case 0:
           // zig-zig left-left
           n = singleRotateAux( n, true ) ;
           n = singleRotateAux( n, true ) ;
           break ;
        case 1:
           // zig-zag right-left
           n.setRightChild( singleRotateAux( n.getRightChild(), true ) ) ;
           n = singleRotateAux( n, false ) ;
           break ;  
        case 2:
           // zig-zag left-right
           n.setLeftChild( singleRotateAux( n.getLeftChild(), false ) ) ;
           n = singleRotateAux( n, true ) ;
           break ;
        case 3:
           // zig-zig right-right
           n = singleRotateAux( n, false ) ;
           n = singleRotateAux( n, false ) ;
           break ;
        }
      }            
      return n; 
   }
}

class TreeView extends Panel
{
   Tree t ;
   boolean drawNames = true ;
 
   TreeView( Tree t ) {
       super() ;    // construct the Panel
       this.t = t ;
   }
   
   public void setDrawNames( boolean t ) {
      drawNames = 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 drawName( Graphics gc, FontMetrics fm, TreeNode n ) {
       if ( n != nullNode ) 
       {
          // drawn name of n
          String s = n.getContent() ;
          int x = n.getX() ;
          int y = n.getY() ;
          gc.setColor( getBackground() ) ;   
          gc.fillRect( x+BOXSIZE, y - fm.getAscent(),
            fm.stringWidth( s )+2*BOXSIZE, fm.getHeight() ) ;
          gc.setColor( Color.black ) ;
          gc.drawString( s, x+2*BOXSIZE, y ) ;
          
          // recurse 
          drawName( gc, fm, n.getLeftChild() ) ;
          drawName( gc, fm, n.getRightChild() ) ;
       }
   }
   
   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 ;
         n.setXY(x,y) ;
         
         // 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() ;
      
      // lock tree and draw
      synchronized(t) {
         draw(gc, t.getRoot(), 0, 1, 0, -1, -1 ) ;
         if ( drawNames)
            drawName(gc, gc.getFontMetrics(), t.getRoot() ) ;
      }
      
      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( "" ) ;
           
   }   
  
}