import java.util.*;

public class TRAII_25_t3_4_example {

  public static void main(String[] args) {

    // input size
    int N = 1200000;
    if (args.length > 0) N = Integer.parseInt(args[0]);

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

    // first small list
    Random r = new Random(seed);
    LinkedList<Integer> L = randomLinkedList(20, r);

    // print list
    System.out.println(L.size() < 30 ? L : (L.size() + " element input list"));
    DsaTimer timer = null;
    Integer result = null;

    timer = new DsaTimer("" + L.size());
    result = mostCommon(L);
    timer.stop();
    System.out.println("time: " + timer + ", " + (timer.time() * 1.0 / L.size()) + " ns/elem");
    System.out.println("most common: " + result);

    // a bit larger
    L = randomLinkedList(N, r);

    System.out.println(L.size() < 30 ? L : (L.size() + " element input list"));

    timer = new DsaTimer("" + L.size());
    result = mostCommon(L);
    timer.stop();
    System.out.println("time: " + timer + ", " + (timer.time() * 1.0 / L.size()) + " ns/elem");
    System.out.println("most common: " + result);

    // TODO T4
    // make a program that measures the speed of HashMap and TreeMap for growing input sizes.
    // remember to eliminate possible sources of timing errors (as described at lecture 2).
    // remember to evaluate the results, are they sensible?

      // warm up run
      System.out.println("Warm up starts");
      compareHashSetTreeSet(200000, 10);
      System.out.println("Warm up ends\n");

      // main test
      System.out.println("Measurements:\n");
      compareHashSetTreeSet(1200000, 10);


  } // main()

    /**
     * Test HashMap and TreeMap max N input.
     * K runs, take minimum
     * @param Nmax max input
     * @param K runs for each input
     */
    public static void compareHashSetTreeSet(int Nmax, int K) {

        Random r = new Random(System.currentTimeMillis());

        String nf = "%9d";
        String ef = "%4d";
        String sf = "%5.2f";


        System.out.println("\n        N        TM TM/e        HM HM/e TM/HM");
        Integer result = null;
        int N = 1;
        DsaTimer a = null;
        long timeT = 0;
        long timeH = 0;

        // repeat for different input sizes
        while (N < Nmax) {

            // a bit less repeats for large N
            if (N > 10 * 1000 * 1000 && K > 2)
                K = 2;

            LinkedList<Integer> L = randomLinkedList(N, r);

            timeT = Long.MAX_VALUE;
            // several runs, take minimum
            for (int k = 0; k < K; k++) {
                a = new DsaTimer("TreeMap");
                result = mostCommonT(L);
                a.stop();
                if (a.time() < timeT)
                    timeT = a.time();
            }
            System.out.format(nf + " " + nf + " " + ef, N, timeT, Math.round(timeT * 1.0 / N));

            timeH = Long.MAX_VALUE;
            // several runs, take minimum
            for (int k = 0; k < K; k++) {
                a = new DsaTimer("HashMap");
                result = mostCommonH(L);
                a.stop();
                if (a.time() < timeH)
                    timeH = a.time();
            }
            System.out.format(" " + nf + " " + ef + " " + sf + "\n", timeH, Math.round(timeH * 1.0 / N), 1.0 * timeT / timeH);

            N *= 2;
        } // while N

    }



    /**
   * Which element occur most often in collection C?
   * If several elements have the same number of occurences, any of those.
   * @param C Input collection
   * @param <E> element type
   * @return the element that has most occurences.
   */
  public static <E> E mostCommon(Collection<E> C) {
    return mostCommonH(C);
  }

    public static <E> E mostCommonH(Collection<E> C) {
      return mostCommon(C, new HashMap<>());
    }

    public static <E extends Comparable<? super E>> E mostCommonT(Collection<E> C) {
        return mostCommon(C, new TreeMap<>());
    }




    public static <E> E mostCommon(Collection<E> C, Map<E, Integer> occurences) {

        E result = null;
        int max = 0;

        // input travelsal, count occurences
        for (E x : C) {
            // (old value or 0) + 1
            Integer old = occurences.get(x);
            if (old == null)
                old = 0;

            int newVal = old + 1;
            occurences.put(x, newVal);
            if (newVal > max) {
                result = x;
                max = newVal;
            }
        }

        return result;
    }



    public static LinkedList<Integer> randomLinkedList(int n, int seed) {
    Random r = new Random(seed);
    LinkedList<Integer> V = new LinkedList<>();
    for (int i = 0; i < n; i++) V.add(r.nextInt(n));
    return V;
  }

  public static LinkedList<Integer> randomLinkedList(int n, Random r) {
    LinkedList<Integer> V = new LinkedList<>();
    for (int i = 0; i < n; i++) V.add(r.nextInt(n));
    return V;
  }
} // class