// TraI_19_t5_6_pohja.java SJ
// Esimerkkiratkaisu viikon 1 tehtäviin 5-6

/**
 * 4. Kirjoita algoritmi (Java-metodi) joka saa parametrinaan kaksi kokonaislukutaulukkoa (In-
 * teger[] A, Integer[] B) ja joka luo ja palauttaa uuden kokonaislukutaulukon jossa on kaikki
 * ne alkiot jotka löytyvät taulukosta A mutta eivät löydy taulukosta B (siis niiden erotuksen).
 * Älä muuta syötetaulukoita. Mikä on algoritmisi aikavaativuus? Voisiko sitä parantaa? Ota
 * tehtävään pääohjelma kurssin www-sivulta.
 *
 * 5. Kertaa Olio-ohjelmointi (Ohjelmointi III) -kurssilla käsitelty ArrayList -luokka. Lisätie-
 * toa: http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html. Muuta
 * edellisen tehtävän 4 algoritmi toimimaan taulukoiden sijaan ArrayList -kokoelmilla. Älä käytä
 * valmista .removeAll() -metodia. Mikä on algoritmisi aikavaativuus? Voisiko sitä parantaa?
 **/

import java.util.ArrayList;
import java.util.Arrays;

public class TRAI_23_t4_esim {


    // Pääohjelman käyttö:
    // java TRAI_23_t4_5_pohja [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) {

        // taulukoiden koko
        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]);

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

        // luodaan esimerkkitaulukot
        Integer[] T1 = new Integer[n1];
        Integer[] T2 = new Integer[n2];

        // täytetään alkioilla
        java.util.Random r = new java.util.Random(siemen);
        for (int i = 0; i < n1; i++) {
            T1[i] = r.nextInt(n1);
        }

        for (int i = 0; i < n2; i++) {
            T2[i] = r.nextInt(n2 * 2);
        }

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

        // kutsutaan tehtävää 4
        Integer[] E4 = erotus4(T1, T2);

        System.out.print("Tehtävä 4, erotus = ");
        if (n1 <= 20 && n2 <= 20) {
            System.out.println(Arrays.toString(E4));
        } else {
            System.out.println(E4.length + " alkioinen taulukko");
            // huom: tämä tulostaa taulukon koon, ei todellisten alkioiden määrää!
        }



    } // main()




    /**
     * 4.
     * Palauttaa taulukoiden erotukset, siis ne alkiot jotka ovat
     * taulukossa T1, mutta eivät taulukossa T2.
     * Taulukot käsitellään kokonaan, null alkiot ohitetaan.
     *
     * @param T1 ensimmäinen taulukko
     * @param T2 toinen taulukko
     * @return erotus taulukkona
     **/
    // neliöllinen ratkaisu, tehdään myöhemmin tehokkaampi
    public static Integer[] erotus4(Integer[] T1, Integer[] T2) {

        // kerätään aputaulukkkoon kaikki T1:tulosMaara alkiot jotka ovat T2:ssa,
        // mutta ei vielä aputaulukossa
        Integer[] apuTulos = new Integer[T1.length];
        int tulosMaara = 0; // alkioiden määrä tulostaulukossa
        for (Integer x : T1) {
            if (! sisaltaako(T2, x))    // tässä apumetodi
                apuTulos[tulosMaara++] = x;
        }

        // muodostetaan oikean kokoinen tulostaulukko
        Integer[] tulos = new Integer[tulosMaara];
        for (int i = 0; i < tulosMaara; i++)
            tulos[i] = apuTulos[i];

        return tulos;
    } // erotus4


    /**
     * Sisältääkö taulukko A alkion x.
     * @param A taulukko
     * @param x haettava alkio
     * @return totuusarvo
     */
    public static boolean sisaltaako(Integer[] A, Integer x) {
        for (Integer i : A) {
            if (i == null)
                return false;
            else if (i.equals(x))
                return true;
        }
        return false;
    }   // sisaltaako()



} // class