import java.util.*;


public class LinkedListPurge {

    public static void main(String[] args) {

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

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


		LinkedList p = new LinkedList<Integer>(new RandomVector<Integer>(N, 1, N, 1));
		LinkedList p1 = new LinkedList<Integer>(new RandomVector<Integer>(N, 1, N, 1));

		if (tulosta) System.out.println(p);
		if (tulosta) System.out.println(p1);
		System.out.println(compare(p, p1));

		purge1(p);


		if (tulosta) System.out.println(p);
		System.out.println(compare(p, p1));

	} // main()

    // iteraattoreilla läpikäynti
    // EI TOIMI kun j.remove() muuttaa kokoelmaa, joten
    // iteraattori i pillastuu (ConcurrentModificationException)
	public static void purge1(LinkedList L) {
		
		ListIterator i = L.listIterator(0);
		while (i.hasNext()) {
			ListIterator j = L.listIterator(i.nextIndex());
			while (j.hasNext()) {
				if (j.next().equals(i.next()))
					j.remove();
			}
		}
	} // purge1()

    // iteraattoreilla läpikäynti, ei tämäkään
    // kun L.remove() muuttaa listaa kesken läpikäynnin
	public static void purge2(LinkedList L) {
		
		ListIterator i = L.listIterator(0);
		while (i.hasNext()) {
			Object x = i.next();
			if (i.hasNext()) {
				int n = L.lastIndexOf(x);
				if (n >= i.nextIndex())
					L.remove(n);
			}
		}
	} // purge2()

	// "taulukkona" kayttaminen
    // melko virhealtis, mutta tässä toimii
    // O(N^2)
	public static void purge3(LinkedList L) {
		int i = 0;
		while (i < L.size()-1) {
			int n = L.lastIndexOf(L.get(i));
			if (n > i)
				L.remove(n);
			else
				i++;
		}

	} // purge3()

    // Listojen sisältöjen vertailu onnistuu kahdella iteraattorilla
    // ihan kätevästi lineaarisessa ajassa
    // Tässä ei siis muuteta listaa
    // O(min(|A|, |B|))
	public static boolean compare(LinkedList A, LinkedList B) {
		ListIterator ai = A.listIterator();
		ListIterator bi = B.listIterator();

		while (ai.hasNext() && bi.hasNext()) {
			if (! ai.next().equals(bi.next()))
				return false;
		}

		if (ai.hasNext() || bi.hasNext())
			return false;
		else
			return true;
	} // compare()
			
    // Indeksejä käyttämällä aikavaativuus on NELIÖLLINEN
	public static boolean compare_VAARIN(LinkedList A, LinkedList B) {

        int ai = 0, bi = 0;

		while (ai < A.size() && bi < B.size()) {
			if (! A.get(ai).equals(B.get(bi)))
				return false;
		}

		if (ai < A.size() || bi < B.size())
			return false;
		else
			return true;
	} // compare_VAARIN()
			
} // class