// TRAII_23_t3_4_pohja.java SJ

/**
 3. Kirjoita algoritmi, joka saa syötteenään kokoelman, ja palauttaa tuloksenaan sen alkion,
joka esiintyi syötteessä useimmin. (Jos mahdollisia tuloksia on monta, niin algoritmisi voi
palauttaa niistä minkä tahansa.) Vertaile alkioita alkion .equals() -operaatiolla. Käytä apuna
kuvausta (Map<E, Integer>). Mikä on algoritmisi aikavaativuus? Ota pohjaa ja esimerkkiä
Moodlesta.
4. Vertaa tehtävän 3 toimintaa kun apuvälinekuvauksena on (a) HashMap tai (b) TreeMap.
Kirjoita ohjelma joka mittaa näiden nopeutta kun syöte kasvaa. Miten selität tulokset? Ota
pohjaa ja esimerkkiä Moodlesta.

 */

import java.util.*;

public class TRAII_23_t3_4_pohja {


    // Pääohjelman käyttö:
    // java TRAII_23_t3_4_pohja [N] [siemen]
    // missä N on alkioiden määrä
    // ja siemen on satunnaislukusiemen

    public static void main(String[] args) {

        // ḱokoelman koko
        int N = 1000000;
        if (args.length > 0)
            N = Integer.parseInt(args[0]);


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


        // ensin pieni lista
        Random r = new Random(siemen);
        LinkedList<Integer> L = randomLinkedList(20, r);

        // tulostetaan lista jos alkioita ei ole paljoa
        if (L.size() <= 30) {
            System.out.println(L);
        }
        Ajastin2 at = null;
        Integer useimmin = null;


        at = new Ajastin2("" + L.size());
        useimmin = useimmin(L);
        at.stop();
        System.out.println("aika: " + at + ", " +
                (at.time() * 1.0 / N) + " ns/elem");
        System.out.println("Useimmin esiintyi " + useimmin);

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

        // tulostetaan lista jos alkioita ei ole paljoa
        if (N <= 30) {
            System.out.println(L);
        }

        at = new Ajastin2("" + L.size());
        useimmin = useimmin(L);
        at.stop();
        System.out.println("aika: " + at + ", " +
                (at.time() * 1.0 / N) + " ns/elem");
        System.out.println("Useimmin esiintyi " + useimmin);

        // TODO: tehtävä 4: vertaa tehokkuuksia



    } // main()


    /**
     * Mikä alkio esiintyy useimmin kokoelmassa C?
     * Jos usea alkio esiintyy yhtä usein, palautetaan niistä yksi.
     * @param C Syötekokoelma
     * @param <E> alkiotyyppi
     * @return yleisin alkio, tai null jos kokoelman on tyhjä
     */
    public static <E> E useimmin(Collection<E> C) {
        return  null; // TODO
    }

    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