import java.lang.System;
import java.lang.Math;

public class permutationSortTest {
    // this procedure provides timing data for the permutation sort
  
    // variable to check correctness
    static boolean checkCorrectness = true;

    public static void permutationSort (int [] a) {
        // method to sort using the permutation sort
        permutationSortKernel (a, a.length-1);

        if (checkCorrectness) {
            boolean ok = true;
            for (int k = 1; k < a.length&&ok; k++) {
                ok = a[k-1] <= a[k];
            }
            if (!ok) {
                SimpleOutput out = new SimpleOutput();
                out.println ("error:  permutation sort");
            }
        }
        
    } // permutationSort

    public static boolean permutationSortKernel (int [] a, int lastIndex) {
        int temp;
        boolean ok;
        if (lastIndex == 0) {
            // check if permutation is ordered
            ok = true;
            for (int k = 1; k < a.length&&ok; k++) {
                ok = a[k-1] <= a[k];
            }
            SimpleOutput out = new SimpleOutput();
            //  out.println();
            //out.println (ok);
            //for (int k = 0; k < a.length; k++)
            //    out.print ("\t" + a[k]);
            //out.println ();
            return ok;
        }
        else {
            
            for (int i = lastIndex; i >= 0; i--){
                // swap position lastIndex with position i
                temp = a[lastIndex];
                a[lastIndex] = a[i];
                a[i] = temp;
                ok = permutationSortKernel (a, lastIndex-1);
                if (ok) 
                    return true;
                else {
                    // swap items back for next round
                    temp = a[lastIndex];
                    a[lastIndex] = a[i];
                    a[i] = temp;
                }
            }
            return false;
        }
    }

    public static void main (String argv[]) {
        // declaration of variables
        SimpleInput in = new SimpleInput();
        SimpleOutput out = new SimpleOutput();

        int numReps = 500;       // number of times experiment completed
        int arraySize;           // size of current array
        int i, j, trial;         // index variables
        long startTime, endTime, elapsedTime; // var. to count milliseconds
        int minArraySize, maxArraySize; // range of array sizes

        out.println ("Program to provide timing data for the permutationsort");
        out.print ("Enter minimum array size to test: ");
        minArraySize = in.readInt ();
        out.print ("Enter maximum array size to test: ");
        maxArraySize = in.readInt ();

        out.println ("Results are based on just one (1)" 
                   + " repetition of the experiment!");

        out.println ();
        out.println ("Results of experiments (all times in milliseconds)");
        out.println ("                             permutation");
        out.println ("data                    array   sort");
        out.println (" set                    size    time");

        for (arraySize = minArraySize; arraySize <= maxArraySize;
             arraySize++) {
            out.println();
            // setup array
            int[] a = new int [arraySize];
            int[] data = new int [arraySize];

            for (trial = 1; trial <= 3; trial++) {
                for (i = 0; i<arraySize; i++) {
                    switch (trial) {
                        case 1: data[i] = 2*i;
                            break;
                        case 2: data[i] = 
                            (int)Math.floor(3*arraySize*Math.random());
                            break;
                        case 3: data[i] = 2*arraySize - 2*i;
                            break;
                    }
                }

                switch (trial) {
                    case 1: out.print ("ascending data:  ");
                        break;
                    case 2: out.print ("random data:     ");
                        break;
                    case 3: out.print ("descending data: ");
                       break;
                }

                out.print ("\t" + arraySize);

                // process permutation sort and record time
                elapsedTime = 0;
                for (j = 0; j < a.length; j++) 
                    a[j] = data[j];
                startTime = System.currentTimeMillis();
                permutationSort (a);
                endTime = System.currentTimeMillis();
                elapsedTime += endTime-startTime;
                out.println ("\t" + elapsedTime);
            }
        }
    } // main
} // sortTest