import java.applet.Applet;
import java.awt.*;
import java.util.Random;


abstract public class Animate extends Applet implements Runnable 
  { Graphics g;
    Thread animatorThread;
    int dotSize, inGen;
    int N;
    double[] a;
    int delay = 0;


    public void start() {
        g = getGraphics();
        animatorThread = new Thread(this);
        animatorThread.start();
    }

    public void pause(int delay) {
       try { Thread.sleep(delay); }
       catch (InterruptedException e) { }
    }


    public void stop() { animatorThread = null; }

    public void run() {
        N =       Integer.parseInt(getParameter("N"));  
        dotSize = Integer.parseInt(getParameter("dotSize"));  
        inGen =   Integer.parseInt(getParameter("inGen"));  
        delay =   Integer.parseInt(getParameter("delay"));  
        
        // generate sequence of real numbers between 0 and 1
        System.out.println("Generating " + N + " input values");
        a = new double[N];

        // random inputs between 0.0 and 1.0
        if (inGen == 1)
            for (int i = 0; i < N; i++) a[i] = Math.random();

        // uniformly spaced inputs between 0.0 and 1.0 in reverse order
        else if (inGen == 2)
            for (int i = 0; i < N; i++) a[i] = (N-1-i)/(double) N;

        // uniformly spaced inputs between 0.0 and 1.0 that are shuffled
        else if (inGen == 3) {
            Random generator = new Random();
            for (int i = 0; i < N; i++) {
                // int r = generator.nextInt(i + 1);   // Java 1.2 
                int r = Math.abs(generator.nextInt()) % (i + 1);
                a[i] = a[r];
                a[r] = i / (double) N;
            }
        }
        else if (inGen == 4) {
            for (int i = 0; i < N; i++) 
            if ((i % 2) == 0)
                a[i] = ((int) (3*Math.random()))/3.0;
            else a[i] = Math.random();
        }

        for (int i = 0; i < N; i++) 
            dot(X(i), Y(a[i]), Color.black);

        System.out.println("Sorting");
        sort(a, 0, N-1);
    }

    int X(int i) 
      { return ((i+1)*getSize().width)/(N+2); }

    int Y(double v) 
      { return (int) (0.005 + (0.99 - 0.99*v)*getSize().height); }

    void dot(int x, int y, Color c) 
      { g.setColor(c); g.fillOval(x, y, dotSize, dotSize); pause(delay); }

    // return 1 if a[i] is less than a[j]
    boolean less(double [] a, int i, int j) { 
        dot(X(i), Y(a[i]), Color.black);
        dot(X(j), Y(a[j]), Color.black);
        return a[i] < a[j]; 
    }

    // swap a[i] and a[j]
    void exch(double [] a, int i, int j) {
        double t = a[i]; a[i] = a[j]; a[j] = t;
        dot(X(i), Y(a[j]), Color.green);
        dot(X(j), Y(a[i]), Color.green);
        dot(X(i), Y(a[i]), Color.black);
        dot(X(j), Y(a[j]), Color.black);
    }

    abstract void sort(double a[], int l, int r); 
}