import java.awt.*;
import java.util.LinkedList;
public class BezierCurve extends Widget{
  protected Point[] vertices;
  protected Point[] vertices_before_drag;
  Handle[] handles;
  int number_of_vertices = 0;
  Color vertex_color = Color.BLACK;
  Color connector_color = new Color(100,100,255);
  Color curve_color = Color.BLACK;
  Color convex_hull_color = new Color(255,100,100);
  int drag_offset_x;
  int drag_offset_y;
  int max_recursion_depth;
  boolean show_handles;
  boolean show_connectors;
  boolean show_points;
  boolean show_lines;
  boolean show_convex_hull;
  boolean is_current_curve;

  public BezierCurve(){
    vertices = new Point[0];
    handles = new Handle[0];
  }

  public void expand_arrays(){
    Point[] new_vertices = new Point[Math.max(vertices.length*2,1)];
    for(int i=0;i<vertices.length;i++) new_vertices[i] = vertices[i];
    vertices = new_vertices;

    Handle[] new_handles = new Handle[Math.max(handles.length*2,1)];
    for(int i=0;i<handles.length;i++) new_handles[i] = handles[i];
    handles = new_handles;
  }

  public void remove_all_vertices(){
    for(int index=0;index<number_of_vertices;index++)
      disconnect(index);

    number_of_vertices = 0;
    vertices = new Point[0];
    handles = new Handle[0];
  }

  public void disconnect(int index){
    if(null!= handles[index].twin_curve){
    if(null!= handles[index].twin())
      handles[index].twin().twin_curve = null;
      //sever connections with this curve
      for(int i=0;i<number_of_vertices;i++) {
        if(handles[index].twin_curve == handles[i].twin_curve){
          if(null!= handles[i].twin())
            handles[i].twin().twin_curve = null;
          handles[i].twin_curve = null;
        }
      }
    }
  }

  public int remove_vertex(int index){
    disconnect(index);

    Point[] new_vertices = 
      new Point[number_of_vertices-1];
    Handle[] new_handles = 
      new Handle[number_of_vertices-1];
    for(int i=0;i<number_of_vertices;i++) {
      if(i<index){
        new_vertices[i] = vertices[i];
        new_handles[i] = handles[i];
      }else if(i>index){
        new_vertices[i-1] = vertices[i];
        new_handles[i-1] = handles[i];
      }
    }
    handles = new_handles;
    vertices = new_vertices;
    return number_of_vertices--;
  }

  public int elevate_degree(){
    // don't bother with zero or one
    if(number_of_vertices<2) return number_of_vertices;

    //for now just dicconect this curve from spline
    for(int index=0;index<number_of_vertices;index++)
      disconnect(index);

    Point[] new_vertices = new Point[number_of_vertices+1];
    Handle[] new_handles = new Handle[number_of_vertices+1];
    // initialize instances
    for(int i=0;i<number_of_vertices+1;i++){
      if(i==0){
        new_vertices[0] = new Point(
          vertices[0].x,
          vertices[0].y);
        new_handles[0] = new Handle(
          (int)vertices[0].x,
          (int)vertices[0].y,this);
      }else if(i==number_of_vertices){
        new_vertices[i] = new Point(
          vertices[number_of_vertices-1].x,
          vertices[number_of_vertices-1].y);
        new_handles[i] = new Handle(
          (int)vertices[number_of_vertices-1].x,
          (int)vertices[number_of_vertices-1].y,this);
      }else{
        new_vertices[i] = new Point(
          ((double)i)/(double)(number_of_vertices+0)*vertices[i-1].x+
          (1.0-((double)i)/(double)(number_of_vertices+0))*vertices[i].x,
          ((double)i)/(double)(number_of_vertices+0)*vertices[i-1].y+
          (1.0-((double)i)/(double)(number_of_vertices+0))*vertices[i].y);
        new_handles[i] = new Handle(
          (int)new_vertices[i].x,(int)new_vertices[i].y,this);
      }
    }
    vertices = new_vertices;
    handles = new_handles;
    return number_of_vertices++;
  }

  final double LOW_DRAW_DISTANCE = 0.5;
  public void set_sampling_resolution(double f){
    max_recursion_depth = (int)(
      (1.0-f)*0.0 + f*10.0);
  }

  public int add_vertex(double x, double y,boolean disconnect){
    if(disconnect)
      for(int index=0;index<number_of_vertices;index++)
        disconnect(index);
    return add_vertex(x,y);
  }
  public int add_vertex(double x, double y){
    if(number_of_vertices+1>vertices.length)
      expand_arrays();
    vertices[number_of_vertices] = new Point(x,y);
    handles[number_of_vertices] = new Handle((int)x,(int)y,this);
    return number_of_vertices++;
  }

  public void deCasteljau_recursive(
    Point[] control_points, 
    double t_before,
    double t_after,
    Point p_before,
    Point p_after,
    int depth,
    boolean force
    ){

      p_before.t =t_before;
      p_after.t =t_after;
    // BASE CASES
    if( !force && depth >= max_recursion_depth) return;
    if( !force && 
      LOW_DRAW_DISTANCE > Point.distance(p_before,p_after)) return;

    double t = (t_before+t_after)/2.0;
    Point[] first_half = new Point[control_points.length];
    Point[] second_half = new Point[control_points.length];
    subdivide(control_points,number_of_vertices,first_half,second_half,t);
    Point p_middle = second_half[0];
    p_before.next = p_middle;
    p_after.previous = p_middle;
    p_middle.next = p_after;
    p_middle.previous = p_before;
    // before
    deCasteljau_recursive(
      control_points,
      t_before,
      t,
      p_before,
      p_middle,
      depth +1,
      false);
    // after
    deCasteljau_recursive(
      control_points,
      t,
      t_after,
      p_middle,
      p_after,
      depth+1,
      false);
  }

  public Point deCasteljau(Point[] points, double t){
    // find max distance between any two points
    double max_distance = 0;
    for(int i=0;i<points.length;i++)
      if(i>0) 
        max_distance = Math.max(max_distance,
          (points[i-1].x-points[i].x)*(points[i-1].x-points[i].x)+
          (points[i-1].y-points[i].y)*(points[i-1].y-points[i].y));
    // BASECASE
    // will appear as a line on the screen anyway
    if(max_distance<1.0) return points[points.length-1];
    
    Point[] first_half = new Point[points.length];
    Point[] second_half = new Point[points.length];
    subdivide(points,number_of_vertices,first_half,second_half,t);
    return second_half[0];
    
  }

  public void select(int mx, int my){
    select(mx,my,true);
  }
  public void select(int mx, int my, boolean affect_twins){
    if(affect_twins){
      LinkedList<BezierCurve> twin_list = 
        new LinkedList<BezierCurve>();
      twin_list(twin_list);
      for(BezierCurve curve: twin_list){
          curve.select(mx,my,false);
      }
    }

    drag_offset_x = mx;
    drag_offset_y = my;
    vertices_before_drag = new Point[number_of_vertices];
    for(int i=0;i<number_of_vertices;i++){
      vertices_before_drag[i] = new Point(vertices[i].x,vertices[i].y);
    }
  }

  public void twin_list(
    LinkedList<BezierCurve> list_so_far){
    for(int i=0;i<number_of_vertices;i++){
      if(null!=handles[i].twin_curve && 
        !list_so_far.contains(handles[i].twin_curve)){
        list_so_far.add(handles[i].twin_curve);
        handles[i].twin_curve.twin_list(list_so_far);
      }
    }
  }

  public boolean drag(int mx, int my){
    return drag(mx,my,true);
  }
  public boolean drag(int mx, int my, boolean affect_twins){
    if(is_down){

      if(affect_twins){
        LinkedList<BezierCurve> twin_list = 
          new LinkedList<BezierCurve>();
        twin_list(twin_list);

        for(BezierCurve curve: twin_list){
          curve.is_down = true;
          curve.drag(mx,my,false);
        }
      }

      for(int i=0;i<number_of_vertices;i++){
        move(
          i,
          vertices_before_drag[i].x+(mx-drag_offset_x),
          vertices_before_drag[i].y+(my-drag_offset_y)); 
      }
    }
    return is_down;
  }

  public void scale_all_toward_point(int x, int y, double scale){
    for(int i=0;i<number_of_vertices;i++){
      double new_x = (vertices[i].x-x)*scale+x;
      double new_y = (vertices[i].y-y)*scale+y;
      move(i,new_x,new_y);
    }
  }

  public void subdivide(
    Point[] originals, 
    int n,
    Point[] first_half, 
    Point[] second_half,
    double t)
  {
    Point[][] matrix = new Point[originals.length+1][originals.length+1];

    // initialize matrix
    for(int j=0;j<matrix.length;j++)
    for(int i=0;i<matrix.length;i++)
      matrix[i][j] = new Point(
        originals[n-1].x,
        originals[n-1].y);

    for(int j=0;j<n;j++)
      matrix[0][j] = new Point(originals[j].x,originals[j].y);

    for(int i=1;i<n;i++)
    for(int j=0;j<n;j++){
      matrix[i][j].x = (1.0-t)*matrix[i-1][j].x+t*matrix[i-1][j+1].x;
      matrix[i][j].y = (1.0-t)*matrix[i-1][j].y+t*matrix[i-1][j+1].y;
    }

    for(int k=0;k<n;k++){
      second_half[k] = matrix[n-1-k][k];
      first_half[k] = matrix[k][0];
    }
  }

  public boolean down(int x, int y){
    if(inside(x,y)){
      was_pressed = true;
      is_down = true;
      select(x,y);
      return true;
    }
    return false;
  }

  public boolean inside(int mx, int my){
    if(number_of_vertices<1) return false;

    if(false){
      Point[] copy = new Point[number_of_vertices];
      int distance = 1;
      for(int i=0;i<number_of_vertices;i++){
        copy[i] = new Point(vertices[i].x,vertices[i].y);
        if(i>0)
          distance += (int) Point.distance(vertices[i-1],vertices[i]);
      }
      int resolution = Math.max(1,(distance));
      double t_step = 1.0/(double)resolution;
      double t = 0.0;
      for(int i=0;i<resolution;i++){
        Point point = deCasteljau(copy,t);
        if(16>= (point.x-mx)*(point.x-mx)+(point.y-my)*(point.y-my))
          return true;
        t+=t_step;
      }
    }else{
      
      if(parameter_of_point_at(mx,my)>0) return true;

      if(show_connectors){
        for(int i = 0; i<number_of_vertices; i++)
          if(i>0)
            if(inside_line(
              vertices[i-1].x,vertices[i-1].y,
              vertices[i].x,vertices[i].y,
              mx,my))
                return true;
      }

      if(show_convex_hull){
        Point[] convex_hull = graham_scan(vertices,number_of_vertices);
        for(int i = 0; i<convex_hull.length; i++)
          if(inside_line(
            convex_hull[i].x,
            convex_hull[i].y,
            convex_hull[(i+1)%convex_hull.length].x,
            convex_hull[(i+1)%convex_hull.length].y,
            mx,
            my))
              return true;
      }
    }
    return false;
  }

  public double parameter_of_point_at(int x, int y){
      Point p0 = new Point(vertices[0].x,vertices[0].y);
        Point p1 = new Point(
          vertices[number_of_vertices-1].x,
          vertices[number_of_vertices-1].y);
        p0.next = p1;
        p1.previous = p0;
        deCasteljau_recursive(vertices,0.0,1.0,p0,p1,0,true);
        Point p = p0;
        while(null != p){
          if(16>= (p.x-x)*(p.x-x)+(p.y-y)*(p.y-y))
            return p.t ;
          if(null!=p.next)
            if(inside_line(p.next.x,p.next.y,p.x,p.y,x,y)){
              return (p.t+p.next.t)*0.5;// this could be even better... 
            }
          p = p.next;
      }
      return -1;
    }

  public BezierCurve cut_at(int x, int y){
    double t = parameter_of_point_at(x,y);
    if(t<0) return null;
    Point[] first_half = new Point[number_of_vertices];
    Point[] second_half = new Point[number_of_vertices];
    subdivide(vertices,number_of_vertices,first_half,second_half,t);

    vertices = first_half;
    for(int i=0;i<first_half.length;i++){
      handles[i].x = (int) first_half[i].x;
      handles[i].y = (int) first_half[i].y;
    }
    //number_of_vertices = first_half.length;

    BezierCurve new_curve = new BezierCurve();
    for(int i=0;i<second_half.length;i++){
      new_curve.add_vertex(second_half[i].x, second_half[i].y);
    }
    return new_curve;
  }

  public boolean between(double a,double b, double x){
    return ((a>x&&b<x)||(b>x&&a<x));
  }

  public boolean inside_line(
    double p1x, double p1y, 
    double p2x, double p2y, 
    double x, double y)
  {
     if(0==p1x-p2x){
        return Math.abs(x-p1x)<4 && between(p1y,p2y,y);
     }
     if(0==p1y-p2y){
        return Math.abs(y-p1y)<4 && between(p1x,p2x,x);
     }
     double m = (p1y-p2y)/(p1x-p2x);
     double b = -m*p1x+p1y;
     double distance_to_line = Math.abs(y-m*x-b)/Math.sqrt(m*m+1);
     if(distance_to_line<4){
       return between(p1x,p2x,x) && between(p1y,p2y,y);
     }
     return false;
  }

  //int[] sorted_order;
  public Point[] graham_scan(Point[] originals, int number_of_originals){
    if(number_of_originals<3) return new Point[0];
    
    Point p = find_lowest_point(originals);
    Point[] sorted = merge_sort(originals, number_of_originals,p);
    Point[] temp = new Point[sorted.length+1];
    for(int i=0;i<temp.length;i++) temp[i] = sorted[i%sorted.length];
    sorted = temp;
    /*sorted_order = new int[sorted.length];
    for(int i=0;i<number_of_vertices;i++)
      for(int j=0;j<sorted.length;j++)
        if(vertices[i]==sorted[j])
          sorted_order[i] = j;
    */

    int index = 1;
    for(int i=2;i<sorted.length;i++){
      while(index-1 >= 0 && 
        cw(sorted[index-1],sorted[index],sorted[i])>=0)
      {
        index--;
      }
      index++;
      swap(sorted, index, i);
    }

    Point[] convex_hull = new Point[index];
    for(int i=0;i<index;i++)
      convex_hull[i] = sorted[i];
    return convex_hull;
  }

  public void swap(Point a, Point b){
    Point temp = a;
    a = b;
    b = temp;
  }
  public void swap(Point[] points, int i, int j){
    Point temp = points[i];
    points[i] = points[j];
    points[j] = temp;
  }


  public double cw(Point p1, Point p2, Point p3){
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
  }

  public Point[] merge_sort(
    Point[] originals, 
    int number_of_originals,
    Point p){
    Point[] left, right, result;

    //base case
    if(number_of_originals <= 1)
      return originals;

    int middle = number_of_originals/2;
    left = new Point[middle];
    right = new Point[number_of_originals - middle];
    for(int j=0;j<left.length;j++)
      left[j] = originals[j];
    for(int j=0;j<right.length;j++)
      right[j] = originals[middle+j];

    //recursive call
    left = merge_sort(left, left.length,p);
    right = merge_sort(right, right.length,p);
    
    merge(left, right,result= new Point[number_of_originals],p);
    return result;
  }

  private void merge(
    Point[] left, 
    Point[] right, 
    Point[] result,
    Point p){
    int li = 0;
    int ri = 0;
    
    while(li < left.length && ri < right.length){
      double cotangent_left = cotangent(left[li],p);
      double cotangent_right = cotangent(right[ri],p);
      if( p == left[li]){
        result[li+ri] = left[li];
        li++;
      }else if( p == right[ri]){
        result[li+ri] = right[ri];
        ri++;
      }else if(
        cotangent_left<cotangent_right 
      ){
        result[li+ri] = left[li];
        li++;
      }else if(
        cotangent_left>cotangent_right 
      ){
        result[li+ri] = right[ri];
        ri++;
      }else{
        // break tie with distance
        if(Point.distance(left[li],p)<Point.distance(right[ri],p)){
          result[li+ri] = left[li];
          li++;
        }else{
          result[li+ri] = right[ri];
          ri++;
        }
      }
    }

    while(li<left.length){
      result[li+ri] = left[li];
      li++;
    }
    while(ri<right.length){
      result[li+ri] = right[ri];
      ri++;
    }
  }

  public double cotangent(Point a, Point p){
    if(a.y==p.y){
      if(a.x>p.x)
        return Double.MAX_VALUE;
      else
        return -Double.MAX_VALUE;
    }
    return (a.x-p.x)/(a.y-p.y);
  }

  public Point find_lowest_point(Point[] points){
    Point p = null;
    for(int i=0;i<points.length && null!=points[i];i++){
      if(null==p || p.y>points[i].y || (p.y==points[i].y && p.x> points[i].x))
        p = points[i];
    }
    return p;
  }

  public void draw(Graphics2D g2){
    // Draw Handle Connectors
    if(show_connectors){
      g2.setColor(!is_current_curve ? Color.GRAY: connector_color);
      for(int i = 0; i<number_of_vertices; i++)
        if(i>0)
          g2.drawLine(
            (int)vertices[i-1].x,
            (int)vertices[i-1].y,
            (int)vertices[i].x,
            (int)vertices[i].y);
    }
    if(show_convex_hull){
      Point[] convex_hull = graham_scan(vertices,number_of_vertices);
      g2.setColor(!is_current_curve ? Color.GRAY: convex_hull_color);
      /*
      if(number_of_vertices>=3)
      for(int i = 0; i<number_of_vertices; i++)
        g2.drawString(
          ""+i+","+sorted_order[i],
          (int)vertices[i].x,
          (int)vertices[i].y);
          */
      for(int i=0;i<convex_hull.length;i++)
        if(null != convex_hull[i] && 
          null != convex_hull[(i+1)%convex_hull.length])
          g2.drawLine(
            (int)convex_hull[i].x,
            (int)convex_hull[i].y,
            (int)convex_hull[(i+1)%convex_hull.length].x,
            (int)convex_hull[(i+1)%convex_hull.length].y);
    }

    // Draw Curve
    if(number_of_vertices>1){
      // make a copy to save memory and protect original
      Point[] copy = new Point[number_of_vertices];
      int distance = 1;
      for(int i=0;i<number_of_vertices;i++){
        copy[i] = new Point(vertices[i].x,vertices[i].y);
        if(i>0)
          distance += (int) Point.distance(vertices[i-1],vertices[i]);
      }
      
      //int resolution = Math.max(1,(int)Math.sqrt(distance));
      if(false){
        int resolution = Math.max(1,(distance));
        double t_step = 1.0/(double)resolution;
        Point[] draw_points = new Point[resolution];
        double t = 0.0;
        for(int i=0;i<resolution;i++){
          draw_points[i] = deCasteljau(copy,t);
          g2.setColor(!is_current_curve ? Color.GRAY: vertex_color);
          g2.fillOval(
            (int)draw_points[i].x-1,
            (int)draw_points[i].y-1,
            2,
            2);
          g2.setColor(!is_current_curve ? Color.GRAY: curve_color);
          if(i>0)
            g2.drawLine(
              (int)draw_points[i-1].x,
              (int)draw_points[i-1].y,
              (int)draw_points[i].x,
              (int)draw_points[i].y);
          t += t_step;
        }
      }else{
        Point p0 = new Point(vertices[0].x,vertices[0].y);
        Point p1 = new Point(
          vertices[number_of_vertices-1].x,
          vertices[number_of_vertices-1].y);
        p0.next = p1;
        p1.previous = p0;
        deCasteljau_recursive(vertices,0.0,1.0,p0,p1,0,true);
        Point p = p0;
        while(null != p){
          if(show_points){
            g2.setColor(!is_current_curve ? Color.GRAY: vertex_color);
            g2.fillOval(
              (int)p.x-1,
              (int)p.y-1,
              2,
              2);
          }
          if(show_lines){
            g2.setColor(!is_current_curve ? Color.GRAY: curve_color);
            if(null!=p.next)
              g2.drawLine(
                (int)p.next.x,
                (int)p.next.y,
                (int)p.x,
                (int)p.y);
          }
          p = p.next;
        }
      }
    }

    //Draw handles
    if(show_handles){
      for(int i = 0; i<number_of_vertices; i++)
        handles[i].draw(g2);
    }

  }
  
  
  public void move(int i, double x, double y){
    handles[i].x = (int) x;
    handles[i].y = (int) y;
    vertices[i].x = x;
    vertices[i].y = y;
  }
}