// TRAII_24_t3_4.java SJ

/**
 * 3. Write an algorithm that takes as input a collection (Collection<E> C ) and an integer k (k
 * >0), and returns as a result a new list of those elements that appeared in the collection C
 * exactly k times. Each element that appeared k times should appear in the result list exactly
 * once. Do not modify the input. The elements are considered equal if their .equals() method
 * returns true. Use a map (Map<E, Integer>) as an auxiliary structure. What is the time complexity
 * of your algorithm? Use template from Moodle.
 *
 * 4. Compare the speed of the task in 3 when the
 * auxiliary map is (a) HashMap or (b) TreeMap. Write a program that measures and compares their
 * speed as the input grows. How do you explain the results? Use examples and templates from Moodle.
 */
import java.util.*;

public class TRAII_24_t3_4_skeleton {

  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;
    List<Integer> result = null;

    timer = new DsaTimer("" + L.size());
    result = kOccurrences(L, 2);
    timer.stop();
    System.out.println("time: " + timer + ", " + (timer.time() * 1.0 / L.size()) + " ns/elem");
    System.out.println("elements that occurred 2 times " + result);

    // sitten vähän isompi
    L = randomLinkedList(N, r);

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

    timer = new DsaTimer("" + L.size());
    result = kOccurrences(L, 3);
    timer.stop();
    System.out.println("time: " + timer + ", " + (timer.time() * 1.0 / L.size()) + " ns/elem");
    if (result.size() < 20) System.out.println("elements that occurred 3 times " + result);
    else System.out.println("there were " + result.size() + " elements that occurred 3 times");

    // 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?

  } // main()

  /**
   * Which elements occur exactly k times in collection C?
   * Each element in result only once.
   *
   * @param C Input collection
   * @param k number to match
   * @param <E> element type
   * @return a list of all those elements that occurred in C k times.
   */
  public static <E> List<E> kOccurrences(Collection<E> C, int k) {
    List<E> result = new ArrayList<>();

    // TODO
    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