// TRAI_23_t9_10.java SJ
// Pääohjelma viikon 2 tehtäviin 9-10

import java.util.*;


/**
 * 8. Suunnittele huolella algoritmi joka saa parametrinaan kaksi järjestämätöntä listaa A ja B
 * (ArrayList) ja joka poistaa listasta A kaikki ne alkiot jotka esiintyvät listassa B. Algoritmi
 * palauttaa poistettujen alkioiden määrän. Nyt ei siis luoda uutta listaa, vaan muokataan
 * parametrina saatua. Älä käytä valmiita remove(Object) tai removeAll() -operaatioita.
 * Piirrä ensin kuva ongelmasta, sitten kirjoita ylös ratkaisuperiaate selväsanaisesti suomeksi.
 * Tämän jälkeen ala täsmentämään ratkaisuperiaatetta täsmällisemmäksi algoritmiksi 1-3
 * vaiheessa siten, että lopullinen ratkaisuperiaate on hyvin täsmällisesti kuvattu ja se on
 * mekaanisesti muutettavissa toimivaksi aliohjelmaksi. Älä muuta syötelistaa B. Mikä on
 * algoritmisi aikavaativuus? Voisiko sitä parantaa?
 *
 * 9. Kirjoita algoritmi joka saa parametrinaan kaksi järjestämätöntä listaa A ja B (ArrayList)
 * ja joka poistaa listasta A kaikki ne alkiot jotka esiintyvät listassa B. Algoritmi palauttaa
 * poistettujen alkioiden määrän. Nyt ei siis luoda uutta listaa, vaan muokataan parametrina
 * saatua. Älä käytä valmista remove(Object) tai removeAll() -operaatioita. Aikavaativuus?
 * Miten aikavaativuutta voisi parantaa?
 * >
 * 10. Kirjoita algoritmi joka saa parametrinaan kaksi järjestämätöntä listaa A ja B (Linked-
 * List) ja joka poistaa listasta A kaikki ne alkiot jotka esiintyvät listassa B. Algoritmi
 * palauttaa poistettujen alkioiden määrän. Nyt ei siis luoda uutta listaa, vaan muokataan
 * parametrina saatua. Älä käytä valmista remove(Object) tai removeAll() -operaatiota.
 * Aikavaativuus? Miten aikavaativuutta voisi parantaa?
 */

public class TRAI_23_t9_10_pohja {


    // Pääohjelman käyttö:
    // java TRAI_23_t9_10 [N] [N2] [S]
    // missä N on alkioiden määrä, N2 on alkoiden määrä toisessa taulukossa
    // ja S on satunnaislukusiemen
    public static void main(String[] args) {

        // alkioiden määrä
        int n1 = 10;
        if (args.length > 0)
            n1 = Integer.parseInt(args[0]);

        int n2 = n1 + 2;
        if (args.length > 1)
            n2 = Integer.parseInt(args[1]);

        int pituus = 1; // merkkijonojen pituus
        if (n1 > 30)
            pituus = 2;

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


        // testataan vaihteeksi merkkijonoilla

        ArrayList<String> AL1 = new ArrayList<>(n1);
        ArrayList<String> AL2 = new ArrayList<>(n2);

        // täytetään alkioilla
        Random r = new Random(siemen);
        for (int i = 0; i < n1; i++) {
            AL1.add(randomString(r, pituus));
        }

        for (int i = 0; i < n2; i++) {
            AL2.add(randomString(r, pituus));
        }

        // tulostetaan taulukot jos alkioita ei ole paljoa
        if (n1 <= 20 && n2 <= 20) {
            System.out.println("AL1: " + AL1);
            System.out.println("AL2: " + AL2);
        }

        // otetaan listoista kopiot tehtävään 10
        LinkedList<String> LL1 = new LinkedList<>(AL1);
        LinkedList<String> LL2 = new LinkedList<>(AL2);


        // testataan tehtävää 9

        int poistettu = poistaKaikki9(AL1, AL2);

        System.out.print("Tehtävä 9, AL1-AL2: poistettu " + poistettu + " alkiota");
        if (n1 <= 20 && n2 <= 20) {
            System.out.println(AL1);
        } else {
            System.out.println(AL1.size() + " alkiota");
        }

        // testataan tehtävää 10

        poistettu = poistaKaikki10(LL1, LL2);

    System.out.print("Tehtävä 10, LL1-LL2: poistettu " + poistettu + " alkiota");
        if (n1 <= 20 && n2 <= 20) {
            System.out.println(LL1);
        } else {
            System.out.println(LL1.size() + " alkiota");
        }


    } // main()


    /**
     * Palauttaa satunnaisen len mittaisen merkkijonon.
     *
     * @param r   satunnaislukugeneraattori
     * @param len merkkijonon pituus
     * @return uusi merkkijono
     */
    public static String randomString(Random r, int len) {
        char[] C = new char[len];
        for (int i = 0; i < len; i++)
            C[i] = (char) (r.nextInt(26) + 'a');
        return new String(C);
    }


    /**
     * Poista kaikki B alkioiden esiintymät listasta A.
     *
     * @param A lista josta poistetaan
     * @param B alkiot jotka poistetaan
     * @return poistettujen alkioiden määrä
     */
    public static <E> int poistaKaikki9(ArrayList<E> A, ArrayList<E> B) {

        int poistettu = 0;

        // TODO

        // vinkki: jos B:n sisällön laittaa HashSet:iin (opiskellaan tarkemmin myöhemmin),
        // niin HashSet.contains(Object) on vakioaikainen.
        // Set<E> Bkopio = new HashSet(B);
        // if (Bkopio.contains(x)) ... // vakioaikainen!

        return poistettu;
    }

    /**
     * Poista kaikki B alkioiden esiintymät listasta A.
     *
     * @param A lista josta poistetaan
     * @param B alkiot jotka poistetaan
     * @return poistettujen alkioiden määrä
     */
    public static <E> int poistaKaikki10(LinkedList<E> A, LinkedList<E> B) {
        int poistettu = 0;

        // TODO

        // vinkki: jos B:n sisällön laittaa HashSet:iin (opiskellaan tarkemmin myöhemmin),
        // niin HashSet.contains(Object) on vakioaikainen.
        // Set<E> Bkopio = new HashSet(B);
        // if (Bkopio.contains(x)) ... // vakioaikainen!

        return poistettu;
    }


} // class