import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.function.Consumer;
import java.io.OutputStream;
import java.io.PrintStream;

/**
 *
 * @author Mark Young (A00000000)
 */
public class ListComparisons {

    private static final String HEADER = "%10s %15s %15s%n";
    private static final String RESULT = "%,10d %,15d %,15d%n";
    private static final int MIN_N = 10;
    private static final int MAX_N = 100000;
    private static final int MULT = 10;
    private static final Scanner KBD = new Scanner(System.in);

    public static void main(String[] args) {
        // introduce yourself
        printIntroduction();
        
        // warm up the engine
        PrintStream oldOut = System.out;
        try {
            System.out.println("\n...warming up the engine...");
            System.setOut(new PrintStream(OutputStream.nullOutputStream()));
            testBuildAndTearDown();
            testRandomAccess();
            System.setOut(oldOut);
        } catch (Exception ex) {
            System.err.println("Something went terribly wrong!");
            System.err.println(ex);
            System.exit(1);
        }
        pause();

        // get timing data
        long start = System.nanoTime();
        testBuildAndTearDown();
        testRandomAccess();       
        long end = System.nanoTime();
        long total = end - start;
        double seconds = total / 1000000000.0;
        
        // report total duration
        System.out.printf("Elapsed time: %.1f seconds.%n",
                seconds);
    }
    
    private static void printIntroduction() {
        System.out.println("\n"
                + "This program compares the time it takes for ArrayLists "
                + "and LinkedLists\nto do the equivalent things.\n\n"
                + "All times in nano-seconds.\n\n"
                + "Original program: Mark Young (A00000000)");
    }

    /**
     * Compare ArrayLists and LinkedLists for how long it takes to add multiple
     * elements and then remove them one by one from the front.
     */
    private static void testBuildAndTearDown() {
        System.out.println("\nTime to build up and then empty a list.\n");

        // create the tests
        Consumer<Integer> testArrayList
                = t -> buildAndTearDown(t, new ArrayList<>());
        Consumer<Integer> testLinkedList
                = t -> buildAndTearDown(t, new LinkedList<>());

        // run the tests
        compareTimes(testArrayList, testLinkedList);
        System.out.println();
    }

    /**
     * Compare ArrayLists and LinkedLists for how long it takes to select
     * elements at random from them.
     */
    private static void testRandomAccess() {
        System.out.println("\nTime to build up and then randomly access "
                + "elements of a list.\n");

        // create the tests
        Consumer<Integer> testArrayList
                = t -> randomAccess(t, new Random(0), new ArrayList<>());
        Consumer<Integer> testLinkedList
                = t -> randomAccess(t, new Random(0), new LinkedList<>());

        // run the tests
        compareTimes(testArrayList, testLinkedList);
        System.out.println();
    }
    
    /**
     * Compare the times taken by an ArrayList vs a LinkedList to accomplish
     * some task. The two Consumer arguments should be doing essentially the
     * same thing so that the time comparisons are meaningful. 
     * 
     * @param testArrayList the version of the task using an ArrayList
     * @param testLinkedList the version of the task using a LinkedList
     */
    private static void compareTimes(
            Consumer<Integer> testArrayList, 
            Consumer<Integer> testLinkedList) {
        // warm up the tests (first use takes extra time)
        testArrayList.accept(10);
        testLinkedList.accept(10);

        // run the tests
        System.out.printf(HEADER,
                "N", "ArrayList(N)", "LinkedList(N)");
        System.out.printf(HEADER,
                "----------", "------------", "-------------");
        for (int n = MIN_N; n <= MAX_N; n *= MULT) {
            long arrayTime = time(n, testArrayList);
            long linkTime = time(n, testLinkedList);
            System.out.printf(RESULT, n, arrayTime, linkTime);
        }
    }
    
    /**
     * Time how long it takes to run the consumer method with the given
     * argument.
     *
     * @param n the number to give to the consumer method
     * @param method a method that takes one integer argument
     * @return the amount of time it takes to complete the task, to nearest 100
     * nanoseconds
     */
    private static long time(int n, Consumer<Integer> method) {
        long start = System.nanoTime();
        method.accept(n);
        return System.nanoTime() - start;
    }

    /**
     * Add <code>numElts</code> elements to the given list, then remove those
     * elements one at a time from the front until the list is empty.
     * 
     * @param numElts the number of elements to add/remove
     * @param list the list to add/remove the elements to/from
     */
    private static void buildAndTearDown(int numElts, List<String> list) {
        for (int i = 0; i < numElts; ++i) {
            list.add("A");
        }
        while (!list.isEmpty()) {
            list.remove(0);
        }
    }
    
    /**
     * Test how long it takes to build up a list of the given length and then 
     * add up half its elements, chosen at random.
     * 
     * @param numElts the number of elements to add to the list
     * @param list the list to add the elements to
     */
    private static void randomAccess(
            int numElts, Random rand, List<Double> list) {
        // create random elements
        for (int i = 0; i < numElts; ++i) {
            list.add(rand.nextDouble());
        }
        
        // choose several elements at random
        for (int i = 0; i < numElts / 2; ++i) {
            list.get(rand.nextInt(numElts));
        }
    }

    /**
     * Prompt the user and wait for them to press the enter key.
     */
    private static void pause() {
        System.out.print("\n...press enter...");
        KBD.nextLine();
        System.out.println();
    }
}