package com.algobase.share.geo;


public class DouglasPeucker {

  public double distance_to_line(int i, int j, int k) { return 0; }

  class DP_Stack {

     int left[];
     int right[];
     int top;

     public DP_Stack(int sz) {
       left = new int[sz];
       right = new int[sz];
       top = -1;
     }

     public void push(int a, int b) {
         top++;
         left[top] = a;
         right[top] = b;
     }

     public int getLeft() { return left[top]; }
     public int getRight() { return right[top]; }
     public void pop() { top--; }
     public boolean empty() { return top == -1; }
  }

  double delta;

  public DouglasPeucker(double d) { delta = d; }

  public int run(int[] result, int n)
  {
    if (n == 0) return 0;

    DP_Stack stack = new DP_Stack(n+1);
    stack.push(0,n-1);

    int j = 0;

    while (!stack.empty())
    { int l = stack.getLeft();
      int r = stack.getRight();
      stack.pop();

      double max_d = -1;
      int max_i = 0;
      for(int i = l+1; i<r; i++)
      { double d = distance_to_line(l,r,i);
        if (d > max_d)
        { max_d = d;
          max_i = i;
         }
      }

      //if (max_d <= delta && (r-l) < 100)
      if (max_d <= delta)
        result[j++] = l;
      else
      { stack.push(max_i,r);
        stack.push(l,max_i);
       }
    }

    result[j++] = n-1;
    return j;
  }

}