import java.util.ArrayList;
import java.util.Iterator;
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 RemovalComparisons {

    public static final Scanner input = Utilities.KBD;
    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 int MAX_LEN = 5;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        printIntroduction();
        Utilities.pause();

        Utilities.printTitle("Using List.remove(int)");
        compareArrayLinked(list -> removeInt(list));
        Utilities.pause();

        Utilities.printTitle("Using List.remove(T)");
        compareArrayLinked(list -> removeValue(list));
        Utilities.pause();

        Utilities.printTitle("Using Iterator.remove()");
        compareArrayLinked(list -> removeIterator(list));
        Utilities.pause();
    }

    private static void printIntroduction() {
        Utilities.printTitle("Comparing Times for Removing List Elements");
        Utilities.printParagraph("This program compares timing data for "
                + "removing elements from ArrayLists and LinkedLists. "
                + "It compares three different ways of doing the task.");
        Utilities.printParagraph("All times are in nano-seconds. "
                + "Times will vary from one run to another, "
                + "sometimes by significant amounts. "
                + "The pattern of results is what you should be considering.");
        Utilities.printParagraph("By Mark Young (A00000000)");
    }

    /**
     * Compare the run time for ArrayLists versus LinkedLists on the same task.
     * Print out the timing comparison for various sizes of list.
     *
     * @param task the task to compare the lists on
     */
    private static void compareArrayLinked(
            Consumer<List<String>> task) {
        // warm up the engine
        task.accept(getArrayList(10000));
        task.accept(getLinkedList(10000));

        // 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(getArrayList(n), task);
            long linkTime = time(getLinkedList(n), task);
            System.out.printf(RESULT, n, arrayTime, linkTime);
        }
    }

    /**
     * Create an ArrayList of the given size.
     *
     * @param size the size of the List to return
     * @return a List of the given length
     */
    private static List<String> getArrayList(int size) {
        return addItems(size, new ArrayList<>());
    }

    /**
     * Create a LinkedList of the given size.
     *
     * @param size the size of the List to return
     * @return a List of the given length
     */
    private static List<String> getLinkedList(int size) {
        return addItems(size, new LinkedList<>());
    }

    /**
     * Fill the given list with the first {@code size} items of the same
     * pseudo-random sequence. When called twice with the same first argument,
     * this method will produce two equal lists in its second argument.
     *
     * @param size the number of items to take
     * @param list the list to put those items in
     * @return a list containing the first {
     * @size} items of a fixed sequence
     */
    private static List<String> addItems(int size, List<String> list) {
        // start with same random number generator every time
        Random rand = getRandom();

        // make sure the list is empty
        list.clear();

        // fill up the list
        for (int i = 0; i < size; ++i) {
            list.add(nextString(rand));
        }

        // send it back
        return list;
    }

    /**
     * Create a new Random object with the same seed every time. This guarantees
     * the ability to generate the same pseudo-random sequence time and time
     * again.
     *
     * @return a Random with the same seed every time
     */
    private static Random getRandom() {
        return new Random(20240229);
    }

    /**
     * Generate a random-length (0 to MAX_LEN) String of 'a's.
     *
     * @param rand the random number generator to use
     * @return a String with 0 to MAX_LEN 'a's.
     */
    private static String nextString(Random rand) {
        return "a".repeat(rand.nextInt(MAX_LEN));
    }

    /**
     * Time how long it takes to run the consumer method with the given
     * argument.
     *
     * @param list the List to give to the consumer method
     * @param method a method that takes one List argument
     * @return the amount of time it takes to complete the task, to nearest 100
     * nanoseconds
     */
    private static long time(List<String> list, Consumer<List<String>> method) {
        long start = System.nanoTime();
        method.accept(list);
        return System.nanoTime() - start;
    }

    /**
     * Remove empty Strings from the given list. Use a count-controlled loop to
     * go thru the list and use List.remove(int) to remove the String.
     *
     * @param list the List to remove empty Strings from
     */
    private static void removeInt(List<String> list) {
        for (int i = 0; i < list.size(); ++i) {
            if (list.get(i).isEmpty()) {
                list.remove(i);

                // BEEP the index so we don't skip what was the next item
                --i;
            }
        }
    }

    /**
     * Remove empty Strings from the given list. Use a count-controlled loop to
     * go thru the list and use List.remove(T) to remove the String.
     *
     * @param list the List to remove empty Strings from
     */
    private static void removeValue(List<String> list) {
        for (int i = 0; i < list.size(); ++i) {
            String word = list.get(i);
            if (word.isEmpty()) {
                list.remove(word);

                // BEEP the index so we don't skip what was the next item
                --i;
            }
        }
    }

    /**
     * Remove empty Strings from the given list. Use an iterator to go thru the
     * list and use Iterator.remove() to remove the String.
     *
     * @param list the List to remove empty Strings from
     */
    private static void removeIterator(List<String> list) {
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String word = it.next();
            if (word.isEmpty()) {
                it.remove();
            }
        }
    }

}