/*
 * ConvexHullAlgThread.java
 *
 * An implementation of Graham's Scan algorithm for convex hull
 *
 * Author: JiMo Jung, June, 2004
 */

import java.awt.*;
import java.io.*;
import java.net.*;
import ciips.animation.*;

public class ConvexHullAlgThread extends AlgThread {

  // Framework variables
  AlgAnimFrame frame;
  static DrawingPanel drawing_panel;

  //int delay = 2000;
  static int N_HISTORY_PANELS = 1;

  static {
    AlgAnimFrame.COMPANEL_LINES = 3;
  }

  static {
    ciips.animation.UIFrame.allowUI(false);
  }

  /*
   * Phase of the algorithm:
   * 0 = ready
   * 1 = generating points
   * 2 = scanning for extreme point
   * 3 = sorting
   * 4 = building hull
   * 5 = done
   */
  int phase;

  // the center of the star-shaped polygon obtained after the sort
  Point pivot;

  int npts; // number of points
  int nvpts; // number of valid points
  Point pts[] = null; // data points

  float maxy; // maximum y value during scan for extreme point
  int maxyi; // index of point with maximum y value during scan for extreme point
  int curpt; // index of current point during any scan

  Point hull[] = null; // The hull points

  int hulli[]; // Indices into original list of points, from the hull points
  int nhull; // Hull size

  Point p1, p2, p3; // The two points being compared during sorting
  int i1, i2, i3; // The indices of the three points

  // Variables needed for drawing
  private Graphics offScreenGraphics;
  int PointLabelWidth, PointLabelHeight, PointLabelLeading, AngleR;
  Font myFont;

  // Returns True if the sequence of points p,q,r form a right-hand turn (CCW)
  float ccw(Point p, Point q) {
    p1 = p;
    p2 = pivot;
    p3 = q;
    return ccw(p, pivot, q);
  }

  float ccw(Point p, Point q, Point r) {
    return (p.x - q.x) * (r.y - q.y) - (p.y - q.y) * (r.x - q.x);
  }

  void erase_point_label(Graphics g, int i, int x) {
    g.clearRect(x, (i + 1) * (PointLabelHeight
                              + PointLabelLeading),
                PointLabelWidth,
                PointLabelHeight + PointLabelLeading + 1);
  }

  void draw_point_label(Graphics g, int i, int x) {
    g.drawString("(" + pts[i].x + "," + pts[i].y + ")",
                 x,
                 (i + 2) * (PointLabelHeight + PointLabelLeading)
                 - PointLabelLeading
                 );
  }

  // swap of two point
  void swap(Point pts[], int i, int j, boolean draw) {
    if (draw) {
      erase_point_label(offScreenGraphics, i, 400);
      erase_point_label(offScreenGraphics, j, 400);
      erase_angle(offScreenGraphics, i);
      erase_angle(offScreenGraphics, j);
    }

    Point tmp = pts[i];
    pts[i] = pts[j];
    pts[j] = tmp;

    if (draw) {
      offScreenGraphics.setColor(Color.blue);
      draw_point_label(offScreenGraphics, i, 400);
      draw_point_label(offScreenGraphics, j, 400);
      show_angle(offScreenGraphics, i);
      show_angle(offScreenGraphics, j);

     pause(100);
    }
  }

  float compare(int i, int j) {
    return ccw(pts[i], pts[j]);
  }

  // Quick sort for points
  void quicksort(Point a[], int p, int q) {
    Point x;
    int i, j;

    if (p < q) {
      x = a[npts] = a[p];
      i = p - 1;
      j = q + 1;

      while (true) {
        while (compare(--j, npts) > 0.0) { ; }
        while (compare(++i, npts) < 0.0) { ; }
        if (i < j) {
          swap(a, i, j, true);
        }
        else {
          break;
        }
      }
      quicksort(a, p, j);
      quicksort(a, j + 1, q);
    }
  }

  // Make sample random data
  void init_points() {
    int i;
    System.out.println("npts = " + npts);
    pts = new Point[npts + 1];
    nvpts = 0;
    for (i = 0; i < npts; i++) {
      pts[i] = new Point(0, 0);
      pts[i].x = (int) (Math.random() * 400 * 0.9 + 400 * 0.05);
      pts[i].y = (int) (Math.random() * 400 * 0.8 + 400 * 0.05);
      nvpts++;

      System.out.println("point[" + i + "] = " + pts[i].x + ", " + pts[i].y);
      show_point(offScreenGraphics, i, Color.blue);
      draw_point_label(offScreenGraphics, i, 400);
      pause(300);
    }
  }

  // Draw holizental line
  void h_line(Graphics g, int i, Color c) {
    g.setColor(c);
    g.drawLine(0, pts[i].y, 400, pts[i].y);
  }

  void erase_h_line(int i) {
    h_line(offScreenGraphics, i, drawing_panel.getBackground());
    show_point(offScreenGraphics, i, Color.blue);
  }

  // Finding pivot point
  int find_pivot() {
    maxyi = 0;
    h_line(offScreenGraphics, maxyi, Color.red);
    draw_point_label(offScreenGraphics, maxyi, 400);

    for (curpt = 1, maxy = pts[maxyi].y; curpt < npts; curpt++) {

      if (curpt - 1 != maxyi) {
        erase_h_line(curpt - 1);
        draw_point_label(offScreenGraphics, curpt - 1, 400);
      }

      h_line(offScreenGraphics, curpt, Color.green);
      draw_point_label(offScreenGraphics, curpt, 400);

      if (pts[curpt].y > maxy) {
        erase_h_line(maxyi);
        draw_point_label(offScreenGraphics, maxyi, 400);

        maxy = pts[curpt].y;
        maxyi = curpt;

        h_line(offScreenGraphics, maxyi, Color.red);
        draw_point_label(offScreenGraphics, maxyi, 400);
      }
      pause(200);
    }

    return maxyi;
  }

  void display_points(Point pts[], int n) {
    int i;

    System.out.println(" i  x  y");
    for (i = 0; i < n; i++) {
      System.out.println(" " + i + " " + pts[i].x + " " + pts[i].y);
    }
  }

  void set_pivot() {
    int pivoti;

    pivoti = find_pivot();
    pivot = pts[pivoti];
    swap(pts, 0, pivoti, false);
    maxyi = 0;
  }

  void sort_points() {
    quicksort(pts, 1, npts - 1);
  }

  void draw_hull_edge(Graphics g, int i, Color c) {
    g.setColor(c);
    g.drawLine(hull[i].x, hull[i].y, hull[i + 1].x, hull[i + 1].y);
  }

  void erase_hull_edge(Graphics g, int i) {
    int j;

    draw_hull_edge(g, i, drawing_panel.getBackground());
    for (j = hulli[i]; j < hulli[i + 1]; j++) {
      g.setColor(Color.green);
      g.drawLine(pts[j].x, pts[j].y, pts[j + 1].x, pts[j + 1].y);
      show_point(g, j, Color.blue);
    }
    show_point(g, j, Color.blue);
  }

  // Finally make convex hull
  void make_hull() {
    int i;

    hull = new Point[npts];
    hulli = new int[npts];

    hull[0] = pts[0];
    hulli[0] = 0;
    hull[1] = pts[1];
    hulli[1] = 1;
    nhull = 2;
    draw_hull_edge(offScreenGraphics, 0, Color.red);

    pause(400);

    for (i = 2; i < npts; i++) {
      while (ccw(hull[nhull - 2], hull[nhull - 1], pts[i]) < 0.0) {
        erase_hull_edge(offScreenGraphics, nhull - 2);
        erase_point_label(offScreenGraphics, hulli[nhull - 1], 500);
        nhull--;
        pause(400);
      }
      hulli[nhull] = i;
      hull[nhull++] = pts[i];
      draw_hull_edge(offScreenGraphics, nhull - 2, Color.red);
      show_hull_point(offScreenGraphics, nhull - 1, Color.red);
      pause(400);
    }
  }

  // Main job
  public void run() {
    // Set framework
    drawing_panel = frame.getCurrentPanel();
    offScreenGraphics = drawing_panel.getGraphics();

    // Initialize data
    init();

    // Set font to panel
    offScreenGraphics.setFont(myFont);

    // Phase 0 = ready
    phase = 0;
    frame.setText(0, "Ready");
    pause(1000);

    // Phase 1 = generating points
    phase = 1;
    show_all(offScreenGraphics);
    frame.setText(0, "Initial points");
    init_points();
    pause(2000);

    // Phase 2 = scanning for extreme point
    phase = 2;
    frame.setText(0, "Finding extreme point");
    set_pivot();
    show_all(offScreenGraphics);
    pause(2000);

    // Phase 3 = sorting
    phase = 3;
    show_all(offScreenGraphics);
    frame.setText(0, "Sorting about the extreme point");
    sort_points();
    pause(2000);

    // Phase 4 = building hull
    //show_all(offScreenGraphics);
    phase = 4;
    show_all(offScreenGraphics);
    frame.setText(0, "Scanning for the hull");
    make_hull();
    pause(400);

    // Phase 5 = done
    phase = 5;
    frame.setText(0, "Done");
    show_all(offScreenGraphics);
  }

  // Initialize framework
  public void init() {
    phase = 0;

    npts = 20;
    nvpts = 0;

    //drawing_panel.resize(600, 400);
    myFont = new Font("Courier", Font.PLAIN, 10);
    FontMetrics fm = drawing_panel.getFontMetrics(myFont);
    PointLabelWidth = fm.charWidth('X') * 9 + 1;
    PointLabelHeight = fm.getHeight();
    PointLabelLeading = fm.getLeading() / 2;
    AngleR = (PointLabelHeight + PointLabelLeading) / 2;
  }

  // pause in milliseconds
  void pause(int milliseconds) {
    try {
      Thread.sleep(milliseconds);
    }
    catch (InterruptedException e) {}
    ;
  }

  // Graphic Routines
  void show_point(Graphics g, int i, Color c) {
    g.setColor(c);
    g.fillOval(pts[i].x - 2, pts[i].y - 2, 5, 5);
  }

  void show_hull_point(Graphics g, int i, Color c) {
    g.setColor(c);
    draw_point_label(g, hulli[i], 500);
  }

  void erase_angle(Graphics g, int i) {
    g.clearRect(400 + PointLabelWidth,
                (i + 1) * (PointLabelHeight + PointLabelLeading),
                2 * AngleR, 2 * AngleR);
  }

  void show_angle(Graphics g, int i) {
    int dx, dy;
    double len, lx, ly;

    g.setColor(Color.darkGray);
    lx = pts[i].x - pivot.x;
    ly = pts[i].y - pivot.y;
    len = Math.sqrt(lx * lx + ly * ly);
    dx = (int) (AngleR * lx / len);
    dy = (int) (AngleR * ly / len);
    g.drawLine(400 + PointLabelWidth + AngleR + dx,
               (i + 1) * (PointLabelHeight + PointLabelLeading) + AngleR + dy,
               400 + PointLabelWidth + AngleR - dx,
               (i + 1) * (PointLabelHeight + PointLabelLeading) + AngleR - dy);
  }

  void show_points(Graphics g) {
    int i;

    g.setColor(Color.blue);
    g.drawString("Points", 400, PointLabelHeight);

    for (i = 0; i < nvpts; i++) {
      show_point(g, i, Color.blue);
      draw_point_label(g, i, 400);
    }
  }

  void show_maxy(Graphics g) {
    if (curpt >= 0 && curpt < npts) {
      h_line(g, curpt, Color.green);
      show_point(g, curpt, Color.green);
      draw_point_label(g, curpt, 400);
    }
    h_line(g, maxyi, Color.red);
    show_point(g, maxyi, Color.red);
    draw_point_label(g, maxyi, 400);
  }

  void show_spokes(Graphics g) {
    int i, x[], y[];

    x = new int[npts];
    y = new int[npts];
    g.setColor(Color.darkGray);
    for (i = 0; i < npts; i++) {
      g.drawLine(pivot.x, pivot.y, pts[i].x, pts[i].y);
    }
  }

  void show_angles(Graphics g) {
    int i;

    g.setColor(Color.darkGray);
    for (i = 0; i < npts; i++) {
      show_angle(g, i);
    }
  }

  void show_comparison(Graphics g) {
    g.setColor(Color.red);
    g.drawLine(p1.x, p1.y, p2.x, p2.y);
    g.drawLine(p2.x, p2.y, p3.x, p3.y);
  }

  void show_star(Graphics g) {
    int i, x[], y[];

    x = new int[npts + 1];
    y = new int[npts + 1];
    g.setColor(Color.green);
    for (i = 0; i < npts; i++) {
      x[i] = pts[i].x;
      y[i] = pts[i].y;
    }
    x[npts] = pts[0].x;
    y[npts] = pts[0].y;
    g.drawPolygon(x, y, npts + 1);
  }

  void show_hull(Graphics g) {
    int i, x[], y[];

    x = new int[nhull + 1];
    y = new int[nhull + 1];

    g.setColor(Color.red);
    g.drawString("Hull", 500, PointLabelHeight);

    for (i = 0; i < nhull; i++) {
      x[i] = hull[i].x;
      y[i] = hull[i].y;
      show_hull_point(g, i, Color.red);
    }
    if (phase == 5) {
      x[nhull] = hull[0].x;
      y[nhull] = hull[0].y;
      g.drawPolygon(x, y, nhull + 1);
    }
    else {
      g.drawPolygon(x, y, nhull);
    }
  }

  public void show_all(Graphics g) {
    g.clearRect(0, 0, 600, 400);
    switch (phase) {
      case 0:
        break;
      case 1:
        show_points(g);
        break;
      case 2:
        show_points(g);
        show_maxy(g);
        break;
      case 3:
        show_points(g);
        show_spokes(g);
        show_angles(g);
        break;
      case 4:
        show_points(g);
        show_star(g);
        show_hull(g);
        break;
      case 5:
        show_points(g);
        show_hull(g);
        break;
      default:
        break;
    }
  }

  // Main starting point
  public ConvexHullAlgThread(AlgAnimFrame frame) {
    super();
    setParms(frame, "ConvexHull", N_HISTORY_PANELS);
    this.frame = frame;
    System.out.println("ConvexHullAlgThread: super called");
    System.out.flush();

    System.out.println("ConvexHullAlgThread: cons complete");
    System.out.flush();
  }

  public boolean loadData( int choice ) {
          return false;
          }
}