import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Main {

    static class Result {

        int size;
        long listTime;
        long arrayListTime;

        public Result(int size) {
            this.size = size;
        }
    }

    public static void main(String[] args) throws Exception {

        // warm up code to make the benchmark more accurate
        for (int i = 0; i < 100; i++) {
            listVsArrayListLinearPerformance(1000);
        }

        // print the header
        System.out.printf("%-15s %-20s %-20s%n",
                "#Elements", "ArrayList", "List");

        // perform the benchmarking
        printResult(listVsArrayListLinearPerformance(1000));
        printResult(listVsArrayListLinearPerformance(2000));
        printResult(listVsArrayListLinearPerformance(3000));
        printResult(listVsArrayListLinearPerformance(4000));
        printResult(listVsArrayListLinearPerformance(5000));
        printResult(listVsArrayListLinearPerformance(10000));
        printResult(listVsArrayListLinearPerformance(20000));
    }

    private static void printResult(Result r) {

        long min = Math.min(r.listTime, r.arrayListTime);

        System.out.printf("%-15d %-10d (%-3.0f%%)    %-10d (%-3.0f%%)%n",
                r.size,
                r.arrayListTime, (100 * (double) r.arrayListTime) / min,
                r.listTime, (100 * (double) r.listTime) / min);
    }

    private static Result listVsArrayListLinearPerformance(int size) {

        Integer[] array1 = new Integer[size];
        Integer[] array2 = new Integer[size];
        Random random = new Random(123456789L);

        ArrayList<Integer> simpleList = new ArrayList<>(Arrays.asList(-1));
        ArrayList<Integer> arrayList = new ArrayList<>(Arrays.asList(-1));

        for (int i = 0; i < size; i++) {
            array1[i] = random.nextInt(Integer.MAX_VALUE);
            array2[i] = random.nextInt(Integer.MAX_VALUE);
        }

        Result result = new Result(size);

        long before;
        
        before = System.nanoTime();
        linearInsertionAsList(array1, simpleList);
        result.listTime = (System.nanoTime() - before) / 1000;
        
        before = System.nanoTime();
        linearInsertionAsArrayList(array2, arrayList);
        result.arrayListTime = (System.nanoTime() - before) / 1000;

        return result;
    }

    private static void linearInsertionAsList(Integer[] intArray, List<Integer> list) {
        for (Integer integer : intArray) {
            int list_size = list.size(); // avoid calculating the size every time
            for (int i = 0; i < list_size; i++) {
                if (integer.compareTo(list.get(i)) >= 0) {
                    list.add(i, integer);
                    break;
                }
            }
        }
    }

    private static void linearInsertionAsArrayList(Integer[] intArray, ArrayList<Integer> list) {
        for (Integer integer : intArray) {
            int list_size = list.size(); // avoid calculating the size every time
            for (int i = 0; i < list_size; i++) {
                if (integer.compareTo(list.get(i)) >= 0) {
                    list.add(i, integer);
                    break;
                }
            }
        }
    }
}