// dsaII_17_2_3_skeleton.java SJ

/**
  *
  * 2. Write an algorithm that finds which element of a given collection has
  * most occurrences. The parameter is a Collection<E> and the return value is
  * an element (of type E) that has most occurrences in the collection. If
  * there are multiple elements with equal number of occurrences, return any of
  * those. If the collection is empty, return null. Compare elements with
  * .equals() operation. Use a mapping (Map<E, Integer>) as a helping
  * structure. What is the time complexity of your algorithm?
  *
  * 3. Compare the running time of task 2 when the helping data structure is
  * (a) HashMap, or (b) TreeMap. Write a program that measures the time
  * difference of these when input grows. How you explain the results?
  *
  **/

import java.util.Collection;
import java.util.Random;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.TreeMap;

public class dsaII_17_2_3_skeleton {

	public static void main(String[] args) {

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

        // random number seed
        int seed = 1;
        if (args.length > 1)
            seed = Integer.valueOf(args[1]);

        // element list
        LinkedList<Integer> L = randomLinkedList(N, seed);

        // print list if only few elements
        if (N <= 50) {
            System.out.print("L:");
            for (Integer x : L)
                System.out.print(" " + x);
            System.out.println();
        }


        // warm up processor
        Integer most = mostT(L);
        most = mostH(L);

        // TODO: measure timing for task 3

        most = mostH(L);
        System.out.println("Most occurrences was " + most);

        most = mostT(L);
        System.out.println("Most occurrences was " + most);

        // for better testing, call several times, take minumum
        // iterate over different input sizes

	} // main()


    /**
      * Returns the element that has most occurrences in collection C.
      * @param C collection to inspect
      * @return the most common element
      **/
    public static <E> E mostH(Collection<E> C) {
        // allocating hash table helps a bit
        HashMap<E, Integer> mapping = new HashMap<E, Integer>((int)(1.6*C.size()));
        E maxelem = null;

        // TODO task 2

        return maxelem;

    } // mostH()


    /**
      * Returns the element that has most occurrences in collection C.
      * @param C collection to inspect
      * @return the most common element
      **/
    public static <E extends Comparable<? super E>>
            E mostT(Collection<E> C) {
        TreeMap<E, Integer> mapping = new TreeMap<E, Integer>();

        E maxelem = null;

        // TODO, exact copy of previous, but now using TreeMap 
        // to compare performance in task 3

        return maxelem;

    } // mostT()


    // helping methods

    /**
      * Creates random integer list.
      * @param n number of elements
      * @param seed random number seed
      * @return new list
      **/
    public static LinkedList<Integer> randomLinkedList(int n, int seed) {
        Random r = new Random(seed);
        LinkedList<Integer> V = new LinkedList<Integer>();
        for (int i = 0; i < n; i++)
            V.add(r.nextInt(n));
        return V;
    }
        
} // class dsaII_17_2_3_skeleton