import fi.uef.cs.tra.ListNode;
import fi.uef.cs.tra.TraLinkedList;

import java.util.*;

public class TRAI_25_t11_13_example {
    public static void main(String[] args) {

        Random rnd = new Random();
        // input size
        int N = 10;
        if (args.length > 0)
            N = Integer.parseInt(args[0]);

        // seed
        int seed = N;
        if (args.length > 1)
            seed = Integer.parseInt(args[1]);


        // a couple of different tests of size N
        for (int i = 0; i < 5; i++) {

            // generate inputs
            rnd.setSeed(seed + i);
            LinkedList<String> LL = randomStringList(rnd, N, 4, 1);
            ArrayList<String> AL = new ArrayList<>(LL);
            TraLinkedList<String> TL = listToTraLinkedList(LL);

            // pick a random element as the limit
            // String limit = AL.get(rnd.nextInt(AL.size()));
            // vary the limit
            String limit = new String(new byte[]{(byte) ('a' + i)});

            System.out.println("\nInput: " + LL);
            System.out.println("Limit: " + limit);

            // task 11
            int removedAL = removeLarger(AL, limit);
            System.out.println("Result AL (" + removedAL + ") : " + AL);

            // task 12
            int removedLL = removeLarger(LL, limit);
            System.out.println("Result LL (" + removedLL + ") : " + LL);

            // task 13
            int removedTL = removeLarger(TL, limit);
            System.out.println("Result TL (" + removedTL + ") : " + listToString(TL));

        } // for i

        // test large input

        LinkedList<String> LL = randomStringList(rnd, 10_000_000, 4, 1);
        ArrayList<String> AL = new ArrayList<>(LL);
        TraLinkedList<String> TL = listToTraLinkedList(LL);
        String limit = "b";
        System.out.println("\nInput: " + LL.size() + " elements");

        System.out.println("Start task 11 (AL)");
        int removedAL = removeLarger(AL, limit);
        System.out.println("Result AL, removed " + removedAL + " elements, remaining : " + AL.size());

        System.out.println("Start task 12 (LL)");
        int removedLL = removeLarger(LL, limit);
        System.out.println("Result LL, removed " + removedLL + " elements, remaining : " + LL.size());

        System.out.println("Start task 13 (TL)");
        int removedTL = removeLarger(TL, limit);
        System.out.println("Result TL, removed " + removedTL + " elements, remaining : " + listSize(TL));


    }   // main()


    /**
     * 11.
     * Remove elements that are larger than limit.
     *
     * @param AL    input list
     * @param limit larger that this will be removed
     * @param <E>   element type
     * @return number of removed elements
     */
    static <E extends Comparable<? super E>> int removeLarger(ArrayList<E> AL, E limit) {
        int removed = 0;
        int read = 0;
        int write = 0;
        while (read < AL.size()) {
            if (AL.get(read).compareTo(limit) > 0) {
                // do not preserve, don't update write
                removed++;
            } else {
                // preserve the element
                AL.set(write++, AL.get(read));
            }
            read++;
        }

        for (int i = 0; i < removed; i++)
            AL.remove(AL.size() - 1);

        return removed;
    }

    static <E extends Comparable<? super E>> int removeLargerWrong2(ArrayList<E> AL, E limit) {
        int removed = 0;
        Iterator<E> it = AL.iterator();
        while (it.hasNext()) {
            E x = it.next();
            if (x.compareTo(limit) > 0) {
                it.remove();
                removed++;
            }
        }
        return removed;
    }

    /**
     * 12.
     * Remove elements that are larger than limit.
     *
     * @param LL    input list
     * @param limit larger that this will be removed
     * @param <E>   element type
     * @return number of removed elements
     */
    static <E extends Comparable<? super E>> int removeLarger(LinkedList<E> LL, E limit) {
        int removed = 0;
        Iterator<E> it = LL.iterator();
        while (it.hasNext()) {
            E x = it.next();
            if (x.compareTo(limit) > 0) {
                it.remove();
                removed++;
            }
        }
        return removed;
    }

    static <E extends Comparable<? super E>> int removeLargerWrong2(LinkedList<E> LL, E limit) {
        int removed = 0;
        int read = 0;
        int write = 0;
        while (read < LL.size()) {
            if (LL.get(read).compareTo(limit) > 0) {
                removed++;
            } else {
                LL.set(write++, LL.get(read));
            }
            read++;
        }

        for (int i = 0; i < removed; i++)
            LL.remove(LL.size() - 1);

        return removed;
    }

    /**
     * 13.
     * Remove elements that are larger than limit.
     *
     * @param TL    input list
     * @param limit larger that this will be removed
     * @param <E>   element type
     * @return number of removed elements
     */
    static <E extends Comparable<? super E>> int removeLarger(TraLinkedList<E> TL, E limit) {
        int removed = 0;
        ListNode<E> p = TL.first();
        while (p != TL.EOL) {
            if (p.getElement().compareTo(limit) > 0) {
                ListNode<E> q = p.next();
                TL.remove(p);
                p = q;
                removed++;
            } else
                p = p.next();
        }
        return removed;
    }


    // input generation helpers

    public static LinkedList<String> randomStringList(Random r, int n, int s, int len) {
        LinkedList<String> L = new LinkedList<>();
        for (int i = 0; i < n; i++)
            L.add(randomString(r, len, s));
        return L;
    }

    public static String randomString(Random r, int len, int s) {
        char[] C = new char[len];
        for (int i = 0; i < len; i++)
            C[i] = (char) (r.nextInt(s) + 'b');
        return new String(C);
    }

    public static <E> TraLinkedList<E> listToTraLinkedList(List<E> A) {
        TraLinkedList<E> TL = new TraLinkedList<>();
        for (E x : A)
            TL.insert(TL.EOL, x);
        return TL;
    }

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

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

}