import java.util.Scanner;

/**
 * A program to count the operations in two different algorithms for printing
 * from 1 to N, and use those counts to find a formula for the amount of work
 * those algorithms do.
 *
 * @author Mark Young (A00000000)
 */
public class Analysis {

    // Maximum number to print to
    private static final int MAX = 10;

    public static void main(String[] args) {
        // create variables
        Scanner kbd = new Scanner(System.in);
        int[] vec1 = new int[MAX + 1];
        int[] opCountStupid = new int[MAX + 1];
        int[] opCountBetter = new int[MAX + 1];

        // introduce yourself
        System.out.print("\n\n"
                + "This program compares two methods for filling an array "
                + "with the numbers\nfrom 1 to N. "
                + "It counts the number of operations required "
                + "for each method\nfor N running from 0 to " + MAX
                + ", and then calculates a formula "
                + "for the amount\nof work required.\n\n");
        pause(kbd);

        // get data for the stupid method
        System.out.print("Filling a array using the Stupid method:\n");
        for (int i = 0; i <= MAX; ++i) {
            opCountStupid[i] = fillStupidly(i, vec1);
            printPositives(vec1);
            System.out.print("\tTo fill the array stupidly from 1 to " + i
                    + " takes " + opCountStupid[i] + " steps.\n");
            vec1 = new int[MAX + 1];
        }
        pause(kbd);

        // get data for the intelligent method
        System.out.print("Filling a array using the Better method:\n");
        for (int i = 0; i <= MAX; ++i) {
            opCountBetter[i] = fillIntelligently(i, vec1);
            printPositives(vec1);
            System.out.print("\tTo fill the array intelligently from 1 to " + i
                    + " takes " + opCountBetter[i] + " steps.\n");
            vec1 = new int[MAX + 1];
        }
        pause(kbd);

        // find and report the equation for the stupid method
        System.out.print("\n\nFinding equation for Stupid:\n");
        findEquation(opCountStupid);
        System.out.print("\n\n");
        pause(kbd);

        // find and report the equation for the better method
        System.out.print("\n\nFinding equation for Better:\n");
        findEquation(opCountBetter);
        System.out.print("\n\n");
        pause(kbd);
    }

    /**
     * Stupid algorithm for filling v up with the numbers from 1 to n. Requires
     * that:
     * <ul>
     * <li> n >= 0
     * <li> v.length >= n
     * <li> v[0..n-1] all equal zero
     * </ul>
     * Given those preconditions, after the method has completed
     * <ul>
     * <li> v[0..n-1] set to 1, 2, 3, 4, ..., n (in sequence)
     * <li> the return value is the number of steps the algorithm took to
     * achieve that state.
     * </ul>
     *
     * @param upTo the number to fill up to
     * @param array the array to fill with the numbers
     * @return number of steps taken to complete the filling
     */
    private static int fillStupidly(int upTo, int[] array) {
        int opCount = 0;
        int stepANumber, stepCNumber;

        // Prevent infinite loop!
        if (upTo < 1) {
            return 0;
        }

        // step 1: print the number 1
        ++opCount;  // "print" (assignment)
        array[0] = 1;

        // step 2: repeat
        do {
            // step 2a: count how many numbers we've already printed
            stepANumber = 0;
            while (stepANumber < array.length) {
                // comparison
                if (array[stepANumber] == 0) {
                    break;
                }
                ++opCount;           // AFTER on THIS OCCASION
                // because we want to simulate counting
                // the numbers, and 0 represents that
                // there is no number there,
                // so it doesn't get counted
                ++stepANumber;
            }

            // step 2b: if it's N, stop (we're done)
            ++opCount;               // comparison
            if (stepANumber == upTo) {
                return opCount;
            }

            // step 2c: add 1 to the number from step a
            ++opCount;               // assignment
            stepCNumber = stepANumber + 1;

            // step 2d: find the end of the list
            stepANumber = 0;
            while (stepANumber < array.length) {
                // comparison
                if (array[stepANumber] == 0) {
                    break;
                }
                ++opCount;           // AFTER on THIS OCCASION
                // for same reasons as above
                ++stepANumber;
            }

            // step 2e: print the number you got in step c
            ++opCount;               // assignment
            array[stepANumber] = stepCNumber;
        } while (true);
    }

    /**
     * Better algorithm for filling v up with the numbers from 1 to n. Requires
     * that:
     * <ul>
     * <li> n >= 0
     * <li> v.length >= n
     * </ul>
     * Given those preconditions, after the method has completed
     * <ul>
     * <li> v[0..n-1] set to 1, 2, 3, 4, ..., n (in sequence)
     * <li> the return value is the number of steps the algorithm took to
     * achieve that state.
     * </ul>
     *
     * @param upTo the number to fill up to
     * @param array the array to fill with the numbers
     * @return number of steps taken to complete the filling
     */
    private static int fillIntelligently(int upTo, int[] array) {
        int opCount = 0;
        int numToPrint;

        // step 1: set k to 1
        ++opCount;                   // assignment
        numToPrint = 1;

        while (true) {
            // step 2: while k <= n
            ++opCount;               // comparison
            if (numToPrint > upTo) {
                return opCount;
            }

            // step 2a: print k
            ++opCount;               // assignment
            array[numToPrint - 1] = numToPrint;

            // step 2b: add one to k
            ++opCount;               // increment
            ++numToPrint;
        }
    }

    /**
     * Print out the non-zero values at the front of an array.
     *
     * @param array the array to print numbers from
     */
    private static void printPositives(int[] array) {
        for (int n : array) {
            if (n > 0) {
                System.out.print(n + " ");
            } else {
                break;
            }
        }
        System.out.println();
    }

    /**
     * Find and print an equation describing the function stored in an array.
     * The array must be filled in with the values of an integer function such
     * that values[i] = f(i), and that function must be either constant, linear
     * or quadratic.
     *
     * The method tries to find a formula for the function, and prints out the
     * actual and predicted values in a table. If they match, it reports the
     * formula it found. Otherwise it prints a message saying it's none of
     * those.
     *
     * @param values an array holding the values of an int function
     */
    public static void findEquation(int[] values) {
        // try to find a, b and c using:
        // v[1] = a + b + c
        // v[2] = 4a + 2b + c
        // v[3] = 9a + 3b + c
        // SO, LET
        //   v1 = v[1]          == a + b + c
        //   v2 = v[2] - 4 * v1 == -2b + -3c
        //   v3 = v[3] - 9 * v1 == -6b + -8c
        //   v3 -= 3 * v2       == c
        //   v2 += 3 * v3       == -2b
        //   v2 /= -2           == b
        //   v1 -= v2 + v3      == a

        double v1 = values[1];
        double v2 = values[2] - 4 * v1;
        double v3 = values[3] - 9 * v1;
        v3 -= 3 * v2;
        v2 += 3 * v3;
        v2 /= -2;
        v1 -= v2 + v3;

        // check if that works!
        for (int i = 1; i < values.length; ++i) {
            double value = v3 + i * (v2 + i * v1);
            System.out.println("\t\tCheck: " + values[i] + " =?= " + value);
            if (values[i] != value) {
                System.out.print("\tThe formula is not constant, "
                        + "linear or quadratic!\n");
                return;
            }
        }
        if (v1 == 0) {
            if (v2 == 0) {
                System.out.print("\tThe formula is constant: "
                        + v3 + ".\n");
            } else {
                System.out.print("\tThe formula is linear: "
                        + v2 + "N + " + v3 + ".\n");
            }
        } else {
            System.out.print("\tThe formula is quadratic: "
                    + v1 + "N^2 + " + v2 + "N + " + v3 + ".\n");
        }
    }

    /**
     * Prompt and wait for the user to press the enter key. Uses a Scanner
     * parameter so that we don't run into the problems that arise from having
     * multiple Scanners attached to System.in, and also to avoid having a
     * static Scanner, which might get created when some other program tries to
     * use findEquation.
     *
     * @param kbd the Scanner(System.in) to wait for the enter key on
     */
    private static void pause(Scanner kbd) {
        System.out.print("\nPress enter...");
        kbd.nextLine();
        System.out.println();
    }

}