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

import fi.uef.cs.tra.*;
import java.util.*;

/**
 * 11. Kirjoita algoritmi (metodi) joka saa parametrinaan kaksi kasvavassa järjestyksessä olevaa
 * linkitettyä listaa (java.util.TraLinkedList) ja joka muodostaa ja palauttaa uuden listan joka
 * sisältää kasvavassa järjestyksessä kaikki ne alkiot jotka vain jommassakummassa listassa. Jos
 * alkio a esiintyy yhdessä listassa k kertaa, mutta toisessa listassa ei lainkaan, niin se tulee
 * tuloslistaan k kertaa. Jos alkio a esiintyy yhdessä listassa k kertaa ja toisessa listassa
 * vähintään kerran, niin sitä ei tule tuloslistaan lainkaan. Myös tuloslistan tulee olla kasva-
 * vassa järjestyksessä. Älä käytä removeAll() tai lajittelu-metodeja, äläkä joukkotyyppejä
 * (Set/Map) apuna. Älä oleta alkioiden olevan kokonaislukuja, vaan käytä .compareTo() metodia. Voit
 * olettaa, ettei listassa ole null-alkioita. Mikä on algoritmisi aikavaativuus?
 *
 * 12. Kirjoita algoritmi (metodi) joka saa parametrinaan kaksi kasvavassa järjestyksessä olevaa
 * asemapohjaista linkitettyä listaa (TraTraLinkedList) ja joka muodostaa ja palauttaa uuden listan
 * joka sisältää kasvavassa järjestyksessä kaikki ne alkiot jotka vain jommassakummas- sa listassa.
 * Jos alkio a esiintyy yhdessä listassa k kertaa, mutta toisessa listassa ei lainkaan, niin se
 * tulee tuloslistaan k kertaa. Jos alkio a esiintyy yhdessä listassa k kertaa ja toisessa listassa
 * vähintään kerran, niin sitä ei tule tuloslistaan lainkaan. Myös tuloslistan tulee olla kasvavassa
 * järjestyksessä. Älä käytä removeAll() tai lajittelu-metodeja, äläkä joukkotyyp- pejä (Set/Map)
 * apuna. Älä oleta alkioiden olevan kokonaislukuja, vaan käytä .compareTo() metodia. Voit olettaa,
 * ettei listassa ole null-alkioita. Mikä on algoritmisi aikavaativuus?
 */
public class TRAI_23_t11_12_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

    LinkedList<String> LL1 = new LinkedList<>();
    LinkedList<String> LL2 = new LinkedList<>();

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

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

    Collections.sort(LL1);
    Collections.sort(LL2);

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

    // otetaan listoista kopiot tehtävään 12
    TraLinkedList<String> TLL1 = new TraLinkedList<>();
    for (String x : LL1) TLL1.insert(TLL1.EOL, x);
    TraLinkedList<String> TLL2 = new TraLinkedList<>();
    for (String x : LL2) TLL2.insert(TLL2.EOL, x);

    // testataan tehtävää 11

    LinkedList<String> tulos11 = listaXor(LL1, LL2);

    System.out.print("Tehtävä 11, LL1^LL2:   ");
    if (tulos11.size() <= 20) {
      System.out.println(tulos11);
    } else {
      System.out.println(tulos11.size() + " alkiota");
    }

    // testataan tehtävää 12

    TraLinkedList<String> tulos12 = listaXor(TLL1, TLL2);

    System.out.print("Tehtävä 12, TLL1^TLL2: ");
    if (n1 <= 20 && n2 <= 20) {
      System.out.println(TraLLtoString(tulos12));
    } else {
      System.out.println(TraLLtoSize(tulos12) + " 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);
  }

  public static <E> String TraLLtoString(TraLinkedList<E> L) {
    StringBuilder sb = new StringBuilder();
    sb.append("(");
    ListNode<E> n = L.first();
    while (n != L.EOL) {
      sb.append(n.getElement());
      n = n.next();
      if (n != L.EOL) sb.append(", ");
    }
    sb.append(")");
    return sb.toString();
  }

  public static <E> int TraLLtoSize(TraLinkedList<E> L) {
    int count = 0;
    ListNode<E> n = L.first();
    while (n != L.EOL) {
      count++;
      n = n.next();
    }
    return count;
  }

  /**
   * Järjestettyjen listojen joko-tai-yhdiste
   *
   * @param A syötelista
   * @param B syötelista
   * @return lista jossa on ne alkiot jotka ovat vain  yhdessä listassa
   */
  public static <E extends Comparable<? super E>> LinkedList<E> listaXor(
      LinkedList<E> A, LinkedList<E> B) {

    LinkedList<E> tulos = new LinkedList<>();

    // TODO


    return tulos;
  }


  /**
   * Järjestettyjen listojen joko-tai-yhdiste
   *
   * @param A syötelista
   * @param B syötelista
   * @return lista jossa on ne alkiot jotka ovat vain  yhdessä listassa
   */
  public static <E extends Comparable<? super E>> TraLinkedList<E> listaXor(
      TraLinkedList<E> A, TraLinkedList<E> B) {
    TraLinkedList<E> tulos = new TraLinkedList<>();

    // TODO
    
    return tulos;
  }
} // class