package yi.graph.polygon;

import java.util.*;
import java.awt.*;

/**
 * Vertexes is a vector of Point
 */

public class Vertexes extends Vector {

  public static Random rand = new Random();

  private static int random(int range) {
    return Math.round(rand.nextFloat() * (float) range);
  }

  private static void swap(Vector v, int a, int b) {
    Object temp = v.elementAt(a);
    v.setElementAt(v.elementAt(b), a);
    v.setElementAt(temp, b);
  }

  private static int partition(Vector v, int l, int r) {
    int pivot, pivoty, pivotpos;

    pivotpos = l + random(r - l);
    swap(v, l, pivotpos);
    pivotpos = l;
    pivot = ( (Point) v.elementAt(pivotpos)).x;
    pivoty = ( (Point) v.elementAt(pivotpos)).y;

    for (int i = l + 1; i <= r; i++) {
      Point temp = (Point) v.elementAt(i);
      if (temp.x < pivot || (temp.x == pivot && temp.y < pivoty)) {
        pivotpos++;
        swap(v, pivotpos, i);
      }
    }

    swap(v, l, pivotpos);
    return pivotpos;
  }

  private static void qSort(Vector v, int l, int r, int threshold) {
    int pivot;

    if (r - l > threshold) {
      pivot = partition(v, l, r);
      qSort(v, l, pivot, threshold);
      qSort(v, pivot, r, threshold);
    }
  }

  public Vertexes sort() {
//    Vertexes result = new Vertexes();
//    for (int i = 0; i < size(); i++)
//      result.addElement(elementAt(i));
//    qSort(result, 0, result.size() - 1, 1);

    // changed by YI (11/17/2004)
    // quick sort doesn't work some time (stack overflow)
    // array to store the index of the data
    Integer[] index = new Integer[size()];
    for (int i=0; i<size(); i++) {
      index[i] = new Integer(i);
    }

    // sort the index
    Arrays.sort(index, new Comparator() {
      public int compare(Object o1, Object o2) {
        int index1 = ((Integer)o1).intValue();
        int index2 = ((Integer)o2).intValue();
        Point p1 = ((Point)elementAt(index1));
        Point p2 = ((Point)elementAt(index2));
        if (p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y)) {
          return -1;
        }
        else if (p1.x == p2.x && p1.y == p2.y) return 0;
        return 1;
      }
    });
    Vertexes result = new Vertexes();
    for (int i = 0; i < size(); i++)
      result.addElement(elementAt(((Integer)index[i]).intValue()));

    return result;
  }

}