import java.util.Random;

public class PancakeSorting {
    int [] pancakes = new int[1];
    Random random;
    int n;

    public PancakeSorting(int n) {
        random = new Random();
        this.n = n;
        cookPancakes();
    }

    public void start() {
        System.out.println("Original : ");
        show(pancakes);
        System.out.println("===================\n");

        sort(pancakes);

        System.out.println("===================\n");
        System.out.println("Sorted : ");
        show(pancakes);
    }

    // Cook some pancakes
    private void cookPancakes() {
        pancakes = new int[n];

        for (int i = 0; i < n; i++) {
            pancakes[i] = random.nextInt(n) + 1;
        }
    }

    // sort the pancakes by flipping them
    private void sort(int [] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            int idx = getMaxIndex(arr, i); // find the largest pancake from the stack we consider

            if (idx == i)
            {
                // pancake is already in it's correct place
                // Nothing to do skipping here
                show(arr);
                System.out.println((i+1) + "th pancake is already in correct place, skipping to next");
                System.out.println();
            }
            else if (idx == 0) {
                flip(arr, i); // its in the front, then send it back
            } else {
                // Nothing works, its in middle somewhere, then bring it front, then flip to back
                flip(arr, idx); // bring it to front
                flip(arr, i); // send it to back and move on
            }
        }
    }

    // returns max elem index in a given limit
    private int getMaxIndex(int [] arr, int limit){
        int idx = 0;

        for (int i = 0; i <= limit; i++) {
            if (arr[idx] < arr[i]) idx = i;
        }

        return idx;
    }

    // flips the array at given end
    private void flip(int [] arr, int end) {
        int start = 0;

        show(arr);
        System.out.println("Spatula is under " + (end + 1) + "th pancake");
        System.out.println();

        // flip element by element from given end point
        while (start < end) {
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

    // show the stack of pancakes
    private void show(int [] arr) {
        System.out.print("Pancakes : ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        System.out.println();
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            showUsage();
        }
        int n = -1;
        try {
            n = Integer.parseInt(args[0]);
            if (n <= 0)
                showUsage();
        }catch (Exception e) {
            showUsage();
        }

        PancakeSorting pancakeSorting = new PancakeSorting(n);
        pancakeSorting.start();
    }

    static void showUsage() {
        System.out.println("Invalid parameter");
        System.out.println("Usage: PancakeSorting <number of pancakes>");
        System.exit(1);
    }
}