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

/** Interactive test bed for polygon realization algorithm
*/

public class Realize extends Applet {
  
  PolygonTri p;  //the polygon displayed in the polygon canvas
  int n;  //number of sides p has
  TextField noSidesField;  //the field which the user can use to set n 
  TextField bracketsField; // bracket version of polygon displayed here
  PolygonCanvas canvas;
  Checkbox circumCheckbox  = new Checkbox("Circumcircles");
  Checkbox angleCheckbox  = new Checkbox("Angles");
  Checkbox triangleCheckbox  = new Checkbox("Triangles",null,true);
  Checkbox vertexCheckbox  = new Checkbox("Vertices",null,true);
  
  public void init() {
    
    setBackground(Color.white);

    setLayout(new BorderLayout());

    Panel leftside = new Panel();
    leftside.setLayout(new StackLayout(20));

    noSidesField = new TextField(getParameter("nosides"),2);
    Panel sidespanel = new Panel();
    sidespanel.add(new Label("Sides:"));
    sidespanel.add(noSidesField);
    leftside.add(sidespanel);
    
    Panel makepanel = new Panel();
    makepanel.setLayout(new StackLayout(0));
    makepanel.add(new Label("Make:"));
    makepanel.add(new Button("Fan"));
    makepanel.add(new Button("Zigzag"));
    makepanel.add(new Button("Ring"));
    makepanel.add(new Button("Random"));
    leftside.add(makepanel);

    Panel showpanel = new Panel();
    showpanel.setLayout(new StackLayout(0));
    showpanel.add(new Label("Show:"));
    showpanel.add(circumCheckbox);
    showpanel.add(angleCheckbox);
    showpanel.add(triangleCheckbox);
    showpanel.add(vertexCheckbox);
    leftside.add(showpanel);
        
    
    Panel bottom = new Panel();
    bottom.add(new Label("Parentheses:"));
    bottom.add(bracketsField = new TextField(60));

    canvas = new PolygonCanvas();

    this.add("South",bottom);
    this.add("West",leftside);
    this.add("Center",canvas);

    action(new Event(noSidesField,Event.ACTION_EVENT,null), null);
  }

  public boolean action(Event e, Object arg) {
    if (e.target == noSidesField) {
      n = getNoSides();
      if (p==null) {
	p = new PolygonTri(n,bracketsField);
	canvas.setPolygon(p);
	p.setShowCircum(circumCheckbox.getState());
	p.setShowAngles(angleCheckbox.getState());
	p.setShowDiagonals(triangleCheckbox.getState());
	p.setShowVertices(vertexCheckbox.getState());
      }
      p.setNoVertices(n);
    } else if (e.target == bracketsField) {
	bracketsToPoly((String) arg, p);
    } else if (e.target == circumCheckbox) {
	p.setShowCircum(((Boolean)arg).booleanValue());
    } else if (e.target == angleCheckbox) {
	p.setShowAngles(((Boolean)arg).booleanValue());
    } else if (e.target == triangleCheckbox) {
	p.setShowDiagonals(((Boolean)arg).booleanValue());
    } else if (e.target == vertexCheckbox) {
	p.setShowVertices(((Boolean)arg).booleanValue());
    } else if (e.target instanceof Button) {
      p.clear();
      if (((String)arg).equals("Fan")) {
	for (int i = 2; i < n - 1; i++) {
	  p.addEdge(0,i);
	}
      } else if (((String)arg).equals("Zigzag")) {
	for (int i = 1; 2*i < n; i++) {
	  p.addEdge(i,n-i);
	  p.addEdge(i,n-i+1);
	}
      } else if (((String)arg).equals("Ring")) {
	int noToAdd = n - 3;  //number of edges needed to triangulte poly
	for (int step = 2; step < n; step *= 2) {
	  for (int i = 0; i <= n-step; i+=step) {
	    if (noToAdd-- > 0) {
	      p.addEdge(i, (i+step)%n);
	    }
	  }
	}
      } else if (((String)arg).equals("Random")) {
	String s = randomParen(n-2);
	bracketsToPoly(s,p);
      }
    }
    canvas.repaint();
    return true;
  }

  public boolean MouseEnter(Event e,int x, int y){
    System.out.println(e.target);
    return true;
  }

  public int getNoSides() {
    noSidesField.selectAll();
    try {
      int n = Integer.parseInt(noSidesField.getSelectedText());
      return (n>3 ? n : 3);  //poly must have at least three sides
    } catch (NumberFormatException e) {
      return 8; //default no of sides
    }
  }

  /** create a random balanced parenthesis string using algorithm given by
    Arnold and Sleep TOPLAS 2 p122-128 (1980) */

  static String randomParen(int n) {
    int r = 0;
    StringBuffer s = new StringBuffer(2*n);
    for (int k = 2*n; k > r; k--) {
      if ((r==0) || (Math.random() > (r*(r+k+2))/(double)(2*k*(r+1)))) {
	s.append('(');
	r++;
      }else {
	s.append(')');
	r--;
      }
    }
    while (r-- > 0) {
      s.append(')');
    }
    return s.toString();
  }

  /** Convert a balanced string of parentheses to a triangulated polygon */
  public void bracketsToPoly(String s, PolygonTri p) {
    StringScan ss = new StringScan(s);
    int no = 1+noVertices(ss);
    if (ss.consumed() != s.length()) {
      showStatus("Leftover characters in parenthesis string");
      bracketsField.select(ss.consumed(),s.length());
    } else {
      showStatus("");
      n = no;
      noSidesField.setText(Integer.toString(n));
      p.setNoVertices(n);
      bToP(0, new StringScan(s), p);
    }
  }

  /* recursive auxiliary function for bracketsToPoly */
  /* balanced bracket string is of form (r)l where r and l are
     (possibly empty) balanced bracket strings.  Correspondingly
     the triangle abx splits the polygon into two smaller polygons.
     The one with ax as an edge corresponds to r.
     The one with xb as an edge corresponds to l. 
     Given a, this function returns b - number of vertices in poly
     is */
  private int bToP(int a, StringScan s, PolygonTri p) {
    if (s.get('(')) {
      int x = bToP(a,s,p); //poly with base ax
      s.get(')');
      int b = bToP(x,s,p); //poly with base xb
      p.addEdge(a,b);
      return b;
    } else {
      return a+1;
    }
  }

  /* count number of vertices in polygon defined by a bracket string */
  private int noVertices(StringScan s) {
    if (s.get('(')) {
      int x = noVertices(s);
      s.get(')');
      return x + noVertices(s);
    } else {
      return 1;
    }
  }
    
}
/* class needed by bracketsToPoly
   It consumes parentheses one by one from a string */
class StringScan {
  private String s;
  private int i;
  
  StringScan (String s) {
    i = 0;
    this.s = s;
  }
  
  /* If first character is a c, remove it and return true, otherwise
     leave it and return false */
  boolean get (char c) {
    if (i < s.length() && c==s.charAt(i)) {
      i++;
      return true;
    } else {
      return false;
    }
  }

  /* return no of characters successfully consumed */
  int consumed() {
    return i;
  }
}