/*
  <APPLET CODE="CatApp.class" WIDTH=500 HEIGHT=400>
  </APPLET>
*/
// ====================================================
//
//	CatApp.java
//
//	D E Taylor
//
//	Developed on version 1.1.4 of Java (DEC Alpha)
//
//	Created: 26 November 1998
//
// ====================================================
// 23 December 1998
//	Used ideas from Robbie Gates' code to improve
//	the drawing routines for the trees
//
// 10 January 1999
//	Changed to a composite pattern for Catalan structures
//
// 17 November 1999
//	This version does not use Applet parameters but has
//	choice boxes for the order and type.  The code uses
//	the 1.1 event model.
// ----------------------------------------------------
import java.util.*;
import java.lang.*;
import java.applet.*;
import java.awt.*;
import java.awt.event.*;

/**

  The number of (full) binary trees with n+1 leaves is the
  n-th Catalan number c[n].  Binary trees are in (natural)
  one-to-one correspondence with (inter alia) 
   - balanced strings of n left and n right brackets
   - planar trees with n+1 nodes
   - triangulations of (n+2)-gons

  This applet draws the set of structures of order n for a
  given type, where the types available are
  
    1 binary trees
    2 planar trees
    3 polygon triangulations
  
  In each case, the diagram is labelled with the corresponding
  balanced string of brackets.
*/

public class CatApp extends Applet {
	
    public static final boolean DEBUG = false;

    protected static int[] sSine   = new int[20];
    protected static int[] sCosine = new int[20];

    /* private */ static int sOrder = 3;
    /* private */ static int sType  = 1;

    private Vector[] mCatalanTrees;
    private Drawable mPicture;

    /* private */ static final int BINARY_TREE = 1; 
    /* private */ static final int PLANAR_TREE = 2;
    /* private */ static final int TRIANGULATION = 3;

    protected CatalanCanvas catCanvas;

// ============================ 
  public void init() {
    final int[][] appheight = {
	{110,140,160,380,1000,3600,14450},
	{110,140,160,280,800,3000,11600},
	{140,140,140,250,550,1580,5020}};

    this.setBackground( Color.lightGray );
    setLayout(new BorderLayout());
    Panel controlPanel = new Panel();
    controlPanel.setBackground(Color.gray);
    controlPanel.setLayout(new FlowLayout(FlowLayout.CENTER,20,1));
    this.add(controlPanel,"North");

    Panel p1 = new Panel();
    controlPanel.add(p1);
    p1.add( new Label("Order:") );
    Choice CatalanOrder = new Choice();
    CatalanOrder.addItem(" 1");
    CatalanOrder.addItem(" 2");
    CatalanOrder.addItem(" 3");
    CatalanOrder.addItem(" 4");
    CatalanOrder.addItem(" 5");
    CatalanOrder.addItem(" 6");
    CatalanOrder.addItem(" 7");
    p1.add(CatalanOrder);
    CatalanOrder.select(" "+sOrder);

    Panel p2 = new Panel();
    controlPanel.add(p2);
    p2.add( new Label("Type:") );
    Choice CatalanType = new Choice();
    CatalanType.addItem("Binary trees");
    CatalanType.addItem("Planar trees");
    CatalanType.addItem("Triangulated polygons");
    p2.add(CatalanType);
    
    Button display = new Button("Display");
    controlPanel.add(display);
    
    ScrollPane pane = new ScrollPane();
    this.add(pane,"Center");
    pane.setSize(495,350);
    
    catCanvas = new CatalanCanvas(this);
    catCanvas.setSize(490,350);
    pane.add(catCanvas);
    
// Events (Java 1.1 model)
    CatalanOrder.addItemListener(new ItemListener() {
      public void itemStateChanged(ItemEvent e) {
      	String ev = (String)e.getItem();
        sOrder = Integer.parseInt( ev.trim() );
        catCanvas.clear();
        }
      });

    CatalanType.addItemListener(new ItemListener() {
      public void itemStateChanged(ItemEvent e) {
      	String ev = (String)e.getItem();
        if (ev == "Binary trees") sType = BINARY_TREE;
        else if (ev == "Planar trees") sType = PLANAR_TREE;
        else if (ev == "Triangulated polygons") sType = TRIANGULATION;
        else System.out.println("Unknown type");
        catCanvas.clear();
        }
      });

    display.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent e) {
	int cHeight = appheight[sType-1][sOrder-1];
	int cWidth = 480;
	if ( sType == 3 ) cWidth = (sOrder < 4) ? 350 : 440;
        catCanvas.setSize(cWidth,cHeight);
        if (DEBUG) System.out.println(cWidth + " " + cHeight);
      	createStructures();
// The size of the ScrollPane has been been changed and
// so we need to lay it out once again.
      	validate();
      	repaint();
        }
      });

// Display the default structures
    createStructures();
    repaint();
  }
  
// ============================
  public void createStructures() {

    mCatalanTrees = new Vector[sOrder+1];
    for( int i = 0 ; i < sOrder+1 ; i++ ) mCatalanTrees[i] = new Vector();

    switch (sType) {
      case BINARY_TREE:
	mCatalanTrees[0].addElement( new Leaf() );
        mPicture = new BinPic(sOrder);
        break;
      case PLANAR_TREE:
        mCatalanTrees[0].addElement( new Leaf() );
        mPicture = new PlanarPic(sOrder);
        break;
      case TRIANGULATION:
        mCatalanTrees[0].addElement( new LeafNode() );
        mPicture = new Triangulation();

        for( int k = 0 ; k < sOrder+2 ; k++ ) {
          double d = (3*sOrder+4-4*k)*Math.PI/(2*sOrder+4);
          sSine[k]   = (int)Math.floor(20*Math.sin(d));
          sCosine[k] = (int)Math.floor(20*Math.cos(d));
        }
        break;
      default:
        System.err.println("This Catalan type is not supported");
        throw new IllegalArgumentException("type must be 1, 2 or 3");
    }

// Construct all the trees up to the size we want
    for( int n = 1 ; n < sOrder+1 ; n++ ) {
      for( int i = 0 ; i < n ; i++ ) {
      	for( int j = 0 ; j < mCatalanTrees[i].size() ; j++ ) {
      	  for( int k = 0 ; k < mCatalanTrees[n-i-1].size() ; k++ ) {
            switch (sType) {
	      case BINARY_TREE:
		mCatalanTrees[n].addElement( 
		  new BinaryTree( 
		    (ProfiledTreeD)mCatalanTrees[i].elementAt(j),
		    (ProfiledTreeD)mCatalanTrees[n-i-1].elementAt(k) 
		  )
		);
		break;
	      case PLANAR_TREE:
		mCatalanTrees[n].addElement( 
		  new PlanarTree( 
		    (ProfiledTreeD)mCatalanTrees[i].elementAt(j),
		    (ProfiledTreeD)mCatalanTrees[n-i-1].elementAt(k) 
		  )
		);
		break;
	      case TRIANGULATION:
		mCatalanTrees[n].addElement( 
		  new Node( 
		    (BareTreeD)mCatalanTrees[i].elementAt(j),
		    (BareTreeD)mCatalanTrees[n-i-1].elementAt(k) 
		  )
		);
		break;
	    }
      	  }
      	}
      }
    }
  }

// ============================
  public void showStructures( Graphics g ) {

    CatalanStructureD t;

    g.drawString("c["+sOrder+"] = "+mCatalanTrees[sOrder].size(),20,20);

    mPicture.init();
    for( Enumeration e = mCatalanTrees[sOrder].elements() ; 
                                          e.hasMoreElements() ; ) {
      t = (CatalanStructureD) e.nextElement();
      mPicture.copyFrom( t );
      mPicture.Draw( g, t.toParen() );
    }
  }
  
// ============================
  public void paint(Graphics g) {
    if (DEBUG) System.err.println("CatApp");
    super.paint( g );
    showStructures( catCanvas.getGraphics() );
    }
  }


// ::::::::::::::::::::::::::::
class CatalanCanvas extends Canvas {
	
  CatApp app;
  
  CatalanCanvas( CatApp _app ) {
    app = _app;
    }
  
  public void paint(Graphics g) {
    if (CatApp.DEBUG) System.err.println("CatalanCanvas");
    app.showStructures( g );
    }
    
  public void clear() {
    super.paint(this.getGraphics());
    }
  }


// ::::::::::::::::::::::::::::

/**
   CatalanStructureD is the abstract data type for the
   various Catalan structures used in this applet.
*/

abstract class CatalanStructureD {

  abstract String toParen();
  }


// ::::::::::::::::::::::::::::

abstract class BareTreeD extends CatalanStructureD {

  abstract int leaves();
  }


// ::::::::::::::::::::::::::::

/**
   Instances of Node are the components of (full) binary 
   trees.  Each node has 2 (ordered) children, which are
   either of type Node or LeafNode.
*/

class Node extends BareTreeD {

  BareTreeD left, right;

  Node( BareTreeD aLeft, BareTreeD aRight ) {
    left  = aLeft;
    right = aRight;
    }


// ============================
  int leaves() {
    return left.leaves() + right.leaves();
    }


// ============================
  String toParen() {
    return left.toParen()+"("+right.toParen()+")";
    }
  }


// ::::::::::::::::::::::::::::

class LeafNode extends BareTreeD {
  
// ============================
  int leaves() { return 1; }

// ============================
  String toParen() { return "" ; }

  }


// ::::::::::::::::::::::::::::

abstract class ProfiledTreeD extends CatalanStructureD {

  int mExtent;
  int [] mLeftProfile, mRightProfile;
  }


// ::::::::::::::::::::::::::::

class Leaf extends ProfiledTreeD {
  
  Leaf() {
    mExtent = 1;
    mLeftProfile  = new int[1];
    mRightProfile = new int[1];
    mLeftProfile[0]  = 0;
    mRightProfile[0] = 0;
    }

// ============================
  String toParen() { return "" ; }
  }


// ::::::::::::::::::::::::::::

/**
   Instances of Tree are the components of (full) binary 
   trees.  Each node has 2 (ordered) children, which may
   themselves be of type Tree or Leaf.  A Tree is like a 
   Node with the addition of left and right profile data.
*/

class Tree extends ProfiledTreeD {

  ProfiledTreeD left, right;

  Tree( ProfiledTreeD aLeft, ProfiledTreeD aRight ) {
    left  = aLeft;
    right = aRight;
    }

// ============================
  String toParen() {
    return left.toParen()+"("+right.toParen()+")";
    }


//  Diagnostic code:
// ============================
  void showProfile() {
    for( int i = 0 ; i < mExtent ; i++ ) 
      System.err.print( mLeftProfile[i]+" " );
    System.err.print("/ ");
    for( int i = 0 ; i < mExtent ; i++ ) 
      System.err.print( mRightProfile[i]+" " );
    System.err.println();
    }
  }


// ::::::::::::::::::::::::::::

/**
   We keep track of the width of the tree at each level
   via a pair of arrays holding the left and right profiles.
   The left (resp. right) profile can be thought of as the
   x-coordinate of the leftmost (resp. rightmost) vertex
   at each level.
*/

class BinaryTree extends Tree {

  BinaryTree( ProfiledTreeD aLeft, ProfiledTreeD aRight ) {

    super( aLeft, aRight );

    int lCommon = Math.min( aLeft.mExtent, aRight.mExtent );
    mExtent = 1+Math.max( aLeft.mExtent, aRight.mExtent );

    mLeftProfile  = new int[mExtent];
    mRightProfile = new int[mExtent];

    int lSpread = 0;
    for( int i = 0 ; i < lCommon ; i++ )
      lSpread = Math.max(
          lSpread, 
          aLeft.mRightProfile[i]-aRight.mLeftProfile[i]
          );
    lSpread = lSpread/2 + 1;

    for( int i = 0 ; i < lCommon ; i++ ) {
      mLeftProfile[i+1]  = aLeft.mLeftProfile[i]-lSpread;
      mRightProfile[i+1] = aRight.mRightProfile[i]+lSpread;
      }

    for( int i = lCommon ; i < aLeft.mExtent ; i++ ) {
      mLeftProfile[i+1]  = aLeft.mLeftProfile[i]-lSpread;
      mRightProfile[i+1] = aLeft.mRightProfile[i]-lSpread;
      }

    for( int i = lCommon ; i < aRight.mExtent ; i++ ) {
      mLeftProfile[i+1]  = aRight.mLeftProfile[i]+lSpread;
      mRightProfile[i+1] = aRight.mRightProfile[i]+lSpread;
      }
    }
  }


// ::::::::::::::::::::::::::::

/**
   A planar tree can be thought of as a binary tree in
   which the length of each left leaning branch has length
   zero.  We keep track of the width at each level via a 
   pair of arrays holding the left and right profiles.
*/

class PlanarTree extends Tree {

  PlanarTree( ProfiledTreeD aLeft, ProfiledTreeD aRight ) {

    super( aLeft, aRight );

    mExtent = 1+Math.max( aLeft.mExtent-1, aRight.mExtent );
    mLeftProfile  = new int[mExtent];
    mRightProfile = new int[mExtent];

    if ( 1 == aLeft.mExtent ) {
      for( int i = 0 ; i < aRight.mExtent ; i++ ) {
        mLeftProfile[i+1]  = aRight.mLeftProfile[i];
        mRightProfile[i+1] = aRight.mRightProfile[i];
        }
      }
    else {
      int lCommon = Math.min( aLeft.mExtent-1, aRight.mExtent );

      int lSpread = 0;
      for( int i = 0 ; i < lCommon ; i++ )
        lSpread = Math.max(
            lSpread, 
            aLeft.mRightProfile[i+1]-aRight.mLeftProfile[i]
            );
      
      int lRightShift = (lSpread-aLeft.mLeftProfile[1])/2 + 1;
      int lLeftShift  = (lSpread+aLeft.mLeftProfile[1])/2 + 1;

      for( int i = 0 ; i < lCommon ; i++ ) {
        mLeftProfile[i+1]  = aLeft.mLeftProfile[i+1]-lLeftShift;
        mRightProfile[i+1] = aRight.mRightProfile[i]+lRightShift;
        }

      for( int i = lCommon ; i < aLeft.mExtent-1 ; i++ ) {
        mLeftProfile[i+1]  = aLeft.mLeftProfile[i+1]-lLeftShift;
        mRightProfile[i+1] = aLeft.mRightProfile[i]-lLeftShift;
        }

      for( int i = lCommon ; i < aRight.mExtent ; i++ ) {
        mLeftProfile[i+1]  = aRight.mLeftProfile[i]+lRightShift;
        mRightProfile[i+1] = aRight.mRightProfile[i]+lRightShift;
        }
      }
    }
  }


// IIIIIIIIIIIIIIIIIIIIIIIIIIII

interface Drawable {

  void init();
  void copyFrom( CatalanStructureD t );
  void Draw( Graphics g, String label );
  }


// ::::::::::::::::::::::::::::

/**
  The generic drawing code for binary and planar trees
*/

class TreePic {

  Point[] mNode;
    int[] mEdge;

  static int sNodeIndex = 0;
  static int sHeight = 0;

  protected static final int XSKIP = 10;
  protected static final int YSKIP = 15;

  private static final int XMARGIN = 30;
  private static final int YMARGIN = 0;
  private static final int XLIMIT  = 480;

  private static int sCursorX = 0;
  private static int sCursorY = YMARGIN;

// ============================
  TreePic( int aSize ) {

    this.init();
    mNode = new Point[aSize];
    mEdge = new int[aSize];    // must have same length as mNode
    }

// ============================
  void init() {

    sCursorX = XLIMIT;
    sCursorY = 0;
    sHeight  = 0;
    }

// ============================
  void removeEdges() {

    sNodeIndex = 0;
    for( int i = 0 ; i < mEdge.length ; i++ ) mEdge[i] = -1;
    }

// ============================
  int height() {

    int lHeight = 0;
    for( int i = 0 ; i < mNode.length ; i++ )
      lHeight = Math.max( lHeight, mNode[i].y );

    return lHeight;
    }

// ============================
  int leftWidth() {

    int wd = 0;
    for( int i = 0 ; i < mNode.length ; i++ )
      wd = Math.min( wd, mNode[i].x );
    return -wd;
    }
  
  
// ============================
  int rightWidth() {

    int wd = 0;
    for( int i = 0 ; i < mNode.length ; i++ )
      wd = Math.max( wd, mNode[i].x );
    return wd;
    }
  

//  Diagnostic code:
// ============================
  void printNodes() {

    for( int i = 0 ; i < mNode.length ; i++ ) 
      System.err.print( mNode[i]+" " );
    System.err.println();
    }


//  Diagnostic code:
// ============================
  void printEdges() {

    for( int i = 0 ; i < mEdge.length ; i++ ) 
      System.err.print( mEdge[i]+" " );
    System.err.println();
    }

// ============================
  public void Draw( Graphics g, String aLabel ) {  

    FontMetrics fm = g.getFontMetrics();
    int lWidth = fm.stringWidth( aLabel )/2;

    if ( 0 == sHeight ) sHeight = height();

    sCursorX += Math.max(leftWidth(),lWidth);
    if ( XLIMIT < sCursorX+Math.max(rightWidth(),lWidth)+10 ) {
      sCursorX = XMARGIN + Math.max(leftWidth(),lWidth);
      sCursorY += sHeight+40;
      }

    g.setColor( Color.yellow );
    g.drawLine(
        sCursorX - 10, sCursorY,
        sCursorX + 10, sCursorY
        );
    g.setColor( Color.red );
    for( int i = 0 ; i < mNode.length ; i++ ) {
      if ( 0 <= mEdge[i] ) {
      	Point p = mNode[i];
      	Point q = mNode[mEdge[i]];
        g.drawLine(
            p.x+sCursorX, -p.y+sCursorY,
            q.x+sCursorX, -q.y+sCursorY 
            );
        }
      }
    g.setColor( Color.green );
    for( int i = 0 ; i < mNode.length ; i++ ) {
      Point p = mNode[i];
      g.fillArc(
          sCursorX + p.x - 2, sCursorY - p.y - 2,
          4, 4,
          0, 360
          );
      }
    g.setColor( Color.black );
    g.drawString( aLabel, sCursorX - lWidth, sCursorY+20 );
    sCursorX += Math.max(rightWidth(),lWidth)+15;
    }
  }


// ::::::::::::::::::::::::::::

class BinPic extends TreePic implements Drawable {

  BinPic( int aOrder ) {
    super( 2*aOrder + 1 );
    }

// ============================
  public void init() {
    super.init();
    }

// ============================
  public void copyFrom( CatalanStructureD t ) {

    removeEdges();
    copyFrom( 0, 0, (ProfiledTreeD)t );
    }

// ============================
  int copyFrom( int aOffsetX, int aLevel, ProfiledTreeD t ) {  
    int lReturnedNode, lThisNode;

    if ( t instanceof Leaf ) {
      lThisNode = sNodeIndex;
      mNode[sNodeIndex++] = new Point(aOffsetX*XSKIP, aLevel*YSKIP);
      }
    else {
      lReturnedNode = copyFrom(
          aOffsetX+((BinaryTree)t).mLeftProfile[1],
          aLevel+1, 
          ((BinaryTree)t).left
          );
      lThisNode = sNodeIndex;
      mEdge[lReturnedNode] = lThisNode;
      mNode[sNodeIndex++] = new Point(aOffsetX*XSKIP, aLevel*YSKIP);
      lReturnedNode = copyFrom(
          aOffsetX+((BinaryTree)t).mRightProfile[1], 
          aLevel+1,
          ((BinaryTree)t).right
          );
      mEdge[lReturnedNode] = lThisNode;
      }
    return lThisNode;
    }

// ============================ 
  public void Draw( Graphics g, String aLabel ) {
    super.Draw( g, aLabel );
    }
  }


// ::::::::::::::::::::::::::::

/**
  The purpose of this class is to convert a binary tree
  with n+1 leaves into a planar tree with n+1 nodes.  This
  is done by shrinking all left branches to 0 length.  That
  is, as we travel around the binary tree we draw a node 
  only when we travel up a right branch.
*/

class PlanarPic extends TreePic implements Drawable {

  PlanarPic( int aOrder ) {

    super( aOrder+1 );
    }

// ============================
  public void init() {
    super.init();
    }

// ============================
  public void copyFrom( CatalanStructureD t ) {

    removeEdges();
    mNode[0] = new Point(0,0);
    if ( t instanceof PlanarTree ) {
      leftCopy( 0, 
           ((PlanarTree)t).mLeftProfile[1],
           0,
           ((PlanarTree)t).left
           );
      rightCopy( 0, 
          ((PlanarTree)t).mRightProfile[1],
          1,
          ((PlanarTree)t).right
          );
      }
    }

// ============================
  void leftCopy( int aLastNode, int aOffsetX, int aLevel, ProfiledTreeD t ) {

    if ( t instanceof PlanarTree ) {
      leftCopy( aLastNode,
          aOffsetX,
          aLevel,
          ((PlanarTree)t).left
          );
      rightCopy( aLastNode,
          aOffsetX-((PlanarTree)t).mLeftProfile[1]+((PlanarTree)t).mRightProfile[1],
          aLevel+1,
          ((PlanarTree)t).right
          );
      }
    }

// ============================
  void rightCopy( int aLastNode, int aOffsetX, int aLevel, ProfiledTreeD t ) {

    int lThisNode = ++sNodeIndex; // retain our own copy of the class variable
    mNode[lThisNode] = new Point(aOffsetX*XSKIP, aLevel*YSKIP);
    mEdge[lThisNode] = aLastNode;

    if ( t instanceof PlanarTree ) {
      leftCopy( lThisNode,
          aOffsetX+((PlanarTree)t).mLeftProfile[1],
          aLevel,
          ((PlanarTree)t).left
          );
      rightCopy( lThisNode,
          aOffsetX+((PlanarTree)t).mRightProfile[1],
          aLevel+1,
          ((PlanarTree)t).right
          );
      }
    }

// ============================ 
  public void Draw( Graphics g, String aLabel ) {
    super.Draw( g, aLabel );
    }
  }


// ::::::::::::::::::::::::::::

/**
   A triangulation of a polygon is a list of pairs of vertices
   representing the edges of the triangles.  The vertices are
   labelled 0, 1, 2, ...
*/

class Triangulation extends Vector implements Drawable {

  static final int XMARGIN = 40;
  static final int XDELTA  = 60;
  static final int XLIMIT  = 460;
  static final int YDELTA  = 80;

  static int sCursorX = 0;
  static int sCursorY = 0;

// ============================
  public void init() {
    sCursorX = XLIMIT;
    sCursorY = 0;
    }

// ============================
  Triangulation() {

    super();
    this.init();
    }
  
// ============================
  public void copyFrom( CatalanStructureD t ) {

    removeAllElements();
    copyFrom( 0, (BareTreeD)t );
    }

// ============================
  void copyFrom( int aOffset, BareTreeD t ) {  

    if ( t instanceof Node ) {
      copyFrom(aOffset,((Node)t).left);
      copyFrom(aOffset+((Node)t).left.leaves(),((Node)t).right);
      }
    addElement( new Point(aOffset, aOffset+t.leaves()) );
    }

// ============================
  public void Draw( Graphics g, String aLabel ) {  

    if ( XLIMIT <= sCursorX ) {
      sCursorX = XMARGIN;
      sCursorY += YDELTA;
      }
    g.setColor( Color.red );
    for( Enumeration e = elements() ; e.hasMoreElements() ; ) {
      Point p = (Point) e.nextElement();
      g.drawLine(
          CatApp.sCosine[p.x]+sCursorX, -CatApp.sSine[p.x]+sCursorY,
          CatApp.sCosine[p.y]+sCursorX, -CatApp.sSine[p.y]+sCursorY
         );
      }
    g.setColor( Color.black );
    g.drawString( aLabel, sCursorX-20, sCursorY+35 );
    sCursorX += XDELTA;
    }
  }