// h3_t2_3.java SJ

// TRA-kirjasto kayttoon:
import fi.joensuu.cs.tra.*;

import java.util.HashSet;

public class h3_t2_3 {

    public static void main(String[] args) {

        // listojen koko
        int N = 10;
        if (args.length > 0)
            N = Integer.valueOf(args[0]);

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

        // luodaan esimerkkilistat
        TraLinkedList<Integer> L1 = new TraLinkedList<Integer>();
        TraLinkedList<Integer> L2 = new TraLinkedList<Integer>();

        // lisätään alkioita
        java.util.Random r = new java.util.Random(siemen);
        for (int i = 0; i < N; i++) {
            L1.insert(L1.EOL, r.nextInt(N));
            L2.insert(L2.EOL, r.nextInt(N*2));
        }

        // tulostetaan listat
        // tässä pohjassa samalla esitellään erilaisia tapoja
        // käydä lista läpi
        if (N <= 20) {

            System.out.print("L1: ");

            // ListNode:lla toisto:
            ListNode n = L1.first();
            while (n != L1.EOL) {
                System.out.print(" " + n.getElement());
                n = n.next();
            }
            System.out.println();


            System.out.print("L2: ");

            // foreach -toisto
            for (Integer e : L2.elements())
                System.out.print(" " + e);
            System.out.println();
        }

        // kutsutaan tehtävää 2

        kaanna(L1);
        // tulostetaan lista, josko on kääntynyt
        if (N <= 20) {
            System.out.print("L1x: ");

            // foreach -toisto
            for (Integer e : L1.elements())
                System.out.print(" " + e);
            System.out.println();
        }


       
        // kutsutaan tehtävää 3

        TraLinkedList<Integer> L = xor(L1, L2);
        // tulostetaan uusi lista
        if (N <= 20) {
            System.out.print("Lxor: ");

            // foreach -toisto
            for (Integer e : L.elements())
                System.out.print(" " + e);
            System.out.println();
        }



    } // main()



    public static void kaanna(TraLinkedList L) {
        ListNode p = L.first();

        ListNode q = p.next();
        while (q != L.EOL) {
            L.insert(L.first(), q.getElement());
            ListNode r = q.next();
            L.remove(q);
            q = r;
        }
    } // kaanna()

    private static boolean contains(TraLinkedList L, Object x) {
        
        // return L.find(L.first(), x) != null; 

        /*
        for (Object y : L.elements()) {
            System.out.println("y " + y);
            if (y.equals(x))
                return true;
        }
        */

        
        ListNode n = L.first();

        while (n != L.EOL) {
            Object y = n.getElement();

            //System.out.println("y " + y);
            if (y.equals(x))
                return true;
            n = n.next();
        }
        
        return false;
        
    }

    public static TraLinkedList xor2(TraLinkedList L1, TraLinkedList L2) {
        HashSet H1 = new HashSet();
        HashSet H2 = new HashSet();
        HashSet H = new HashSet();
        for (Object x : L1.elements())
            H1.add(x);
        for (Object x : L2.elements())
            H2.add(x);

        ListNode p1 = L1.first();
        TraLinkedList L = new TraLinkedList();

        while (p1 != L1.EOL) {
            if (!H.contains(p1.getElement()) &&
                !H2.contains(p1.getElement())) {
                L.insert(L.EOL, p1.getElement());
                H.add(p1.getElement());
            }
            p1 = p1.next();
        }

        ListNode p2 = L2.first();
        while (p2 != L2.EOL) {
            if (!H.contains(p2.getElement()) &&
                !H1.contains(p2.getElement())) {
                L.insert(L.EOL, p2.getElement());
                H.add(p2.getElement());
            }
            p2 = p2.next();
        }
        return L;
    }

        



    public static TraLinkedList xor(TraLinkedList L1, TraLinkedList L2) {

        ListNode p1 = L1.first();
        TraLinkedList L = new TraLinkedList();

        while (p1 != L1.EOL) {
            if (!contains(L, p1.getElement()) &&
                !contains(L2, p1.getElement()))
                {L.insert(L.EOL, p1.getElement());System.out.println("Lisatty" + p1.getElement());}
            p1 = p1.next();
        }

        ListNode p2 = L2.first();
        while (p2 != L2.EOL) {
            if (!contains(L, p2.getElement()) &&
                !contains(L1, p2.getElement()))
                {L.insert(L.EOL, p2.getElement());System.out.println("Lisatty" + p2.getElement());}
            p2 = p2.next();
        }

        return L;

    } // xor()


} // class

=====================================================================================================

// h3_t4_5.java SJ

// Java API:n LinkedList käyttöön:
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;


public class h3_t4_5 {

    public static void main(String[] args) {

        // listojen koko
        int NN = 32;
        if (args.length > 0)
            NN = Integer.valueOf(args[0]);

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

        int alku = 32;
        if (NN < alku)
            alku = NN;

        System.out.println("n kaanna1 kaanna2 xor1 xor2 xor3");

        for (int N = alku; N <= NN; N *= 2) {

        // luodaan esimerkkilistat
        LinkedList<Integer> L1 = new LinkedList<Integer>();
        LinkedList<Integer> L2 = new LinkedList<Integer>();

        // lisätään alkioita
        java.util.Random r = new java.util.Random(siemen);
        for (int i = 0; i < N; i++) {
            L1.addLast(r.nextInt(N));
            L2.addLast(r.nextInt(N*2));
        }

            // tulostetaan listat
            if (N <= 20) {

                System.out.print("L1: ");

                for (Integer e : L1)
                    System.out.print(" " + e);
                System.out.println();


                System.out.print("L2: ");

                // foreach -toisto
                for (Integer e : L2)
                    System.out.print(" " + e);
                System.out.println();
            }

            // kutsutaan tehtavaa 4

            System.out.print(N + " ");


            kaanna1(L1);

            // tulostetaan lista, josko on kääntynyt
            if (N <= 20) {
                System.out.print("L1x: ");

                // foreach -toisto
                for (Integer e : L1)
                    System.out.print(" " + e);
                System.out.println();
            }

            if (N < 500000) {
                kaanna2(L1);
            } else
                System.out.print("-1 ");



            // kutsutaan tehtavaa 5

            LinkedList<Integer> L = null;

            L = xor1(L1, L2);

            if (N < 120000) {
                L = xor2(L1, L2);
            } else
                System.out.print("-1 ");

            if (N < 7000) {
                L = xor3(L1, L2);
            } else
                System.out.print("-1 ");

            // tulostetaan uusi lista
            if (N <= 20) {
                System.out.print("Lxor: ");

                // foreach -toisto
                for (Integer e : L)
                    System.out.print(" " + e);
                System.out.println();
            }

            System.out.println();
        }


    } // main()



    // kääntäminen lineaarisessa ajassa kahden iteraattorin
    // set() operaatioilla
    public static void kaanna1(LinkedList L) {
        int N = L.size();

        ListIterator i1 = L.listIterator(0);
        ListIterator i2 = L.listIterator(N);

        int i = 0;
        while (i < N/2) {
            Object tmp = i1.next();
            Object tmp2 = i2.previous();
            i2.set(tmp);
            i1.set(tmp2);
            i++;
        }
    }

    // kääntäminen neliöllisessä ajassa add() operaatoilla
    public static void kaanna2(LinkedList L) {
        int N = L.size();

        for (int i = 0; i < N-1; i++)
            L.add(i, L.removeLast());
    }




    // xor ~lineaarisessa ajassa HashSet.contains() operaatiolla
    public static LinkedList xor1(LinkedList L1, LinkedList L2) {

        LinkedList L = new LinkedList();

        HashSet H1 = new HashSet(L1);   // L1:n alkiot haettavassa muodossa
        HashSet H2 = new HashSet(L2);   // L2:n alkiot haettavassa muodossa
        HashSet H = new HashSet();      // Tähän lisätään L:n alkiot jotta haku olisi nopeaa


        for (Object x : L1)
            if (!H2.contains(x) && !H.contains(x)) {
                L.add(x);
                H.add(x);
            }

        for (Object x : L2)
            if (!H1.contains(x) && !H.contains(x)) {
                L.add(x);
                H.add(x);
            }

        return L;
    }

    // xor neliöllisessä ajassa indexOf() operaatiolla
    public static LinkedList xor2(LinkedList L1, LinkedList L2) {
        LinkedList L = new LinkedList();

        for (Object x : L1)
            if ((L2.indexOf(x) == -1) && (L.indexOf(x) == -1))
                L.add(x);

        for (Object x : L2)
            if ((L1.indexOf(x) == -1) && (L.indexOf(x) == -1))
                L.add(x);

        return L;
    }

    // xor kuutiollisessa ajassa indeksiläpikäynneillä ja get:llä
    // TÄMÄ ON SIIS PAHASTI VÄÄRÄ TAPA KÄYTTÄÄ LISTÄÄ, TÄSSÄ MUKANA 
    // VAIN KAUHUESIMERKKINÄ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    public static LinkedList xor3(LinkedList L1, LinkedList L2) {
        LinkedList L = new LinkedList();

        // L1:n potentiaaliset lisättävät
        for (int i = 0 ; i < L1.size(); i++) {
            boolean loytyi = false;

            // löytyykö alkio L2:sta?
            for (int j = 0 ; j < L2.size(); j++) {
                if (L1.get(i).equals(L2.get(j))) {
                    loytyi = true;
                    break;
                }
            }
            // löytyykö alkio jo L:sta?
            for (int k = 0 ; k < L.size(); k++) {
                if (L1.get(i).equals(L.get(k))) {
                    loytyi = true;
                    break;
                }
            }
            // jollei löytynyt L2:sta, eikä L:stä, niin lisätään
            if (! loytyi)
                L.add(L1.get(i));
        }

        // L2:n potentiaaliset lisättävät
        for (int i = 0 ; i < L2.size(); i++) {
            boolean loytyi = false;

            // löytyykö alkio L1:sta?
            for (int j = 0 ; j < L1.size(); j++) {
                if (L2.get(i).equals(L1.get(j))) {
                    loytyi = true;
                    break;
                }
            }
            // löytyykö alkio jo L:sta?
            for (int k = 0 ; k < L.size(); k++) {
                if (L2.get(i).equals(L.get(k))) {
                    loytyi = true;
                    break;
                }
            }
            // jollei löytynyt L1:sta, eikä L:stä, niin lisätään
            if (! loytyi)
                L.add(L2.get(i));
        }

        return L;
    } // xor3()


} // class

===========================================================================

// h3_t6.java SJ

import fi.joensuu.cs.tra.*;

public class h3_t6 {

	public static void main(String[] args) {

		int N = 10;
		if (args.length > 0)
			N = Integer.valueOf(args[0]);

		int k = 5;
		if (args.length > 1)
			k = Integer.valueOf(args[1]);

		boolean tulosta = false;
		if (args.length > 2)
			tulosta = true;


		LinkedStack<Integer> S = new LinkedStack<Integer>();
		for (int i = 0; i < N; i++)
			S.push(i);

		if (tulosta)
			System.out.println(S);

		reverse_k(S, k);
		if (tulosta)
			System.out.println(S);

	} // main()

	public static void reverse_k(LinkedStack S, int k) {
		LinkedQueue Q = new LinkedQueue();
		int i = 0;
		while (! S.isEmpty() && i < k) {
			Q.offer(S.pop());
			i++;
		}
		while (! Q.isEmpty())
			S.push(Q.poll());
	}

} // class h3_t6