// Program to test solutions to problem #3 on the cse143 midterm, spring 2008
// Fill in your solution to removeLast, then compile and run the program

class LinkedIntList {
    public void removeLast(int n) {
        // fill in your solution here
        // you can also rename the parameter above
    }

    private ListNode front;  // first value in the list

    // this is the sample solution
    public void removeLast2(int n) {
        if (front != null) {
            ListNode current = front;
            ListNode spot = null;
            while (current.next != null) {
                if (current.next.data == n)
                    spot = current;
                current = current.next;
            }
            if (spot != null)
                spot.next = spot.next.next;
            else if (front.data == n)
                front = front.next;
        }
    }

    // post: constructs an empty list
    public LinkedIntList() {
        front = null;
    }

    // post: returns the current number of elements in the list
    public int size() {
        int count = 0;
        ListNode current = front;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }

    // pre : 0 <= index < size()
    // post: returns the integer at the given index in the list
    public int get(int index) {
        ListNode current = front;
        for (int i = 0; i < index; i++)
            current = current.next;
        return current.data;
    }

    // post: creates a comma-separated, bracketed version of the list
    public String toString() {
        if (front == null)
            return "[]";
        else {
            String result = "[" + front.data;
            ListNode current = front.next;
            while (current != null) {
                result += ", " + current.data;
                current = current.next;
            }
            result += "]";
            return result;
        }
    }

    // post : returns the position of the first occurence of the given
    //        value (-1 if not found)
    public int indexOf(int value) {
        int index = 0;
        ListNode current = front;
        while (current !=  null) {
            if (current.data == value)
                return index;
            index++;
            current = current.next;
        }
        return -1;
    }

    // post: appends the given value to the end of the list
    public void add(int value) {
        if (front == null)
            front = new ListNode(value);
        else {
            ListNode current = front;
            while (current.next != null)
                current = current.next;
            current.next = new ListNode(value);
        }
    }

    // pre: 0 <= index <= size()
    // post: inserts the given value at the given index, shifting subsequent
    //       values right
    public void add(int index, int value) {
        if (index == 0)
            front = new ListNode(value, front);
        else {
            ListNode current = front;
            for (int i = 0; i < index - 1; i++)
                current = current.next;
            current.next = new ListNode(value, current.next);
        }
    }

    // pre : 0 <= index < size()
    // post: removes value at the given index, shifting subsequent values left
    public void remove(int index) {
        if (index == 0)
            front = front.next;
        else {
            ListNode current = front;
            for (int i = 0; i < index - 1; i++)
                current = current.next;
            current.next = current.next.next;
        }
    }
}

public class Test3 {
    public static void main(String[] args) {
        test(new int[] {3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0, 3});
        test(new int[] {2, 13, 4, 1, 0, 9, 2, 7, 4, 12, 3, 2});
        test(new int[] {1, 1, 1, 1, 1, 1});
    }

    public static void test(int[] data) {
        LinkedIntList list1 = new LinkedIntList();
        LinkedIntList list2 = new LinkedIntList();
        for (int n : data) {
            list1.add(n);
            list2.add(n);
        }
        boolean fail = false;
        while (!fail && list1.size() > 0) {
            int target = list1.get(0);
            System.out.println("removing " + target + " from " + list1);
            int n = list1.size();
            for (;;) {
                list1.removeLast2(target);
                System.out.println("    next result should = " + list1);
                try {
                    list2.removeLast(target);
                } catch (RuntimeException e) {
                    System.out.println("    threw " + e);
                    fail = true;
                }
                if (!fail && !list1.toString().equals(list2.toString())) {
                    System.out.println("    actual result      = " + list2);
                    fail = true;
                }
                if (!fail)
                    System.out.println("    success");
                if (fail || list1.size() == n)
                    break;
                n--;
            }
        }
        if (fail)
            System.out.println("failed");
        else
            System.out.println("passed");
        System.out.println();
    }
}

class ListNode {
    public int data;       // data stored in this node
    public ListNode next;  // link to next node in the list

    // post: constructs a node with data 0 and null link
    public ListNode() {
        this(0, null);
    }

    // post: constructs a node with given data and null link
    public ListNode(int data) {
        this(data, null);
    }

    // post: constructs a node with given data and given link
    public ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
    }
}