// dsaII_17_4_6_skeleton.java SJ

/**
 * 4. Write a program that tests the performance difference of LinkedList and
 * ArrayList. The algorithm should add n elements to the list, traverse the
 * elements, and remove the elements one by one. Write a single algorithm that
 * uses operations of interface List operations and then write a test method
 * that calls the algorithm using both list implementations.
 *
 * 5. Add to the task 4 an algorithm that does the same performance testing
 * for a standard array (E[]) instead of collection.
 *
 * 6. Add to the task 5 comparison of performance of Integer array and int
 * array.
 *
 **/


import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;

public class dsaII_17_4_6_skeleton {

	public static void main(String[] args) {

        // number of elements
		int N = 10;
		if (args.length > 0)
			N = Integer.valueOf(args[0]);


        // call example testing
        testWrongCompare(N, 10);

        // call for exercises, if you choose to use example method
        test456(N, 100);
		
	} // main()

    /**
      * Call testListWrong() using both LinkedList and ArrayList
      * for 1..Nmax, each K rounds, take minimum.
      * You can use these as an example for tasks 4-6.
      * @param Nmax maximum N
      * @param K number of tests for each N
      **/
    public static void testWrongCompare(int Nmax, int K) {

        int N = 1;
        long t = 0;
        long timeL = 0;
        long timeA = 0;
        long timeIntegerA = 0;
        long timeintA = 0;
        while (N <= Nmax) {

            // limit number of tries for large N
            if (N > 10*1000 && K > 5)
                K = 10;

            if (N > 100*1000 && K > 2)
                K = 2;


            // test ArrayList
            ArrayList<Integer> AL = new ArrayList<Integer>();

            // make first one call to test with printing
            t = testListWrong(AL, N, true);
            timeA = t;
            System.out.println();

            // make several calls without printing, take minimum
            for (int k = 0; k < K; k++) {
                
                t = testList(AL, N, false);
                if (t < timeA)
                    t = timeA;
            }


            System.out.println("ArrayListN " + N + " " + timeA + " " +
                               (timeA*1.0/N) + "\n");

            // test LinkedList
            LinkedList<Integer> LL = new LinkedList<Integer>();

            // make first one call to test with printing
            t = testListWrong(LL, N, true);
            timeL = t;
            System.out.println();

            // make several calls without printing, take minimum
            for (int k = 0; k < K; k++) {
                
                t = testList(LL, N, false);
                if (t < timeL)
                    t = timeL;
            }


            System.out.println("LinkedList " + N + " " + timeL + " " +
                               (timeL*1.0/N) + "\n");

            // print ratio of times
            System.out.println("LL/AL " + timeL*1.0/timeA + "\n");

            N *= 10;

        }

    } // testWrongCompare()

    /**
      * Tests lists using operations that are very inefficient (wrong) either
      * for arraylist and linked list  here as an example and skeleton for
      * tasks 4-6.
      * @param L List to be tested
      * @param n number of elements to insert and iterate
      * @param print print timing if true
      * @return total nanoseconds for add and iterate.
      **/
    public static long testListWrong(List<Integer> L, int n, boolean print) {

        DsaTimer whole = new DsaTimer("whole test " + n);
        DsaTimer add = new DsaTimer("add0");
        DsaTimer iter = new DsaTimer("for_i");

        // add n elements to the beginning of list
        whole.start();
        add.start();
        for (int i = 0; i < n; i++)
            L.add(0, i);   // <- WRONG FOR ARRAYLIST
        add.stop();

        // iterate n elements using for and indexing
        long sum = 0L;
        iter.start();
        for (int i = 0 ; i < n; i++)
            sum += L.get(i); // <- WRONG FOR LINKEDLIST
        iter.stop();

        whole.stop();

        if (print) {
            System.out.println("Tested " + L.getClass().toString() + ", n = " + n);
            System.out.println("" + add + " + " + iter +
                               " = " + whole);
            System.out.println("add0: " + add.nanos()/n +
                               " + for_i: " + iter.nanos()/n +
                               " = total: " + whole.nanos()/n + " ns/element");
        }

        return whole.nanos();
    }   // testListWrong()



    // example headers for tasks 4-6, use if you want
    public static long testArray(Integer[] A, int n, boolean print) {
        // TODO 
        return 0;
    }


    public static long testArray(int[] A, int n, boolean print) {
        // TODO
        return 0;
    }

    public static long testList(List<Integer> L, int n, boolean print) {
        // TODO
        return 0;
    }


    // test N 1..N, each K rounds, take minimum
    public static void test456(int Nmax, int K) {

        // call actual test methods here
        // TODO

        int N = 1;
        long t = 0;
        while (N <= Nmax) {

            // TODO

            ArrayList<Integer> AL = new ArrayList<Integer>();

            t = testList(AL, N, true);


            LinkedList<Integer> LL = new LinkedList<Integer>();

            t = testList(LL, N, true);

            Integer[] A = new Integer[N];

            t = testArray(A, N, true);

            int[] iA = new int[N];

            t = testArray(iA, N, true);


            N *= 10;

        }

    }


	
} // class dsaII_17_2_3_skeleton