/*
    LinkedList.java
    CIS 260
    2014-03-11
    David Klick

    Implementation of a linked list with generics.
*/
import java.util.NoSuchElementException;
import java.util.ArrayList;

public class LinkedList<T> {
    private class Node<T> {
        T data;
        Node<T> next;
        // *** Need to declare a prev ptr
        public Node() { this(null); }
        public Node(T data) {
            next = null;
            // *** Need to initialize prev ptr
            this.data = data;
        }
    }
    
    private Node<T> head;
    private Node<T> tail;
    private int count = 0;
    
    public LinkedList() {
        head = tail = null;
        count = 0;
    }
    
    public LinkedList(LinkedList<T> lst) {
        head = tail = null;
        for (int i=0; i<lst.size(); i++) push_back(lst.get(i));
    }
    
    public int size() {
        return count;
    }

    @Override
    public String toString() {
        StringBuilder out = new StringBuilder();
        Node<T> p = head;
        while (p != null) {
            out.append(p.data.toString());
            p = p.next;
        }
        return out.toString();
    }

    public T peek_front() {
        if (head == null) throw new NoSuchElementException();
        return head.data;
    }

    public T peek_back() {
        if (tail == null) throw new NoSuchElementException();
        return tail.data;
    }

    public T peek() {
        return peek_back();
    }

    public T get(int ndx) {
        if (ndx < 0) throw new NoSuchElementException();
        int temp = 0;
        Node<T> current = head;
        while (temp < ndx) {
            if (current == null) throw new NoSuchElementException();
            if (ndx == temp) return current.data;
            current = current.next;
            temp++;
        }
        if (current == null) throw new NoSuchElementException();
        return current.data;
    }

    public LinkedList<T> set(int ndx, T data) {
        if (ndx < 0 || ndx >= count) throw new NoSuchElementException();
        int temp = 0;
        Node<T> current = head;
        while (temp < ndx) {
            current = current.next;
            temp++;
        }
        current.data = data;
        return this;
    }

    public boolean empty() { return count == 0; }

    public void clear() {
        while (!empty()) pop_back();
    }

    public T pop_front() {
        if (count < 1) throw new NoSuchElementException();
        T data = head.data;
        if (count == 1) {
            head = tail = null;
        } else {
            // *** Set the second node's prev ptr to null
            head = head.next;
        }
        count--;
        return data;
    }
    
    public T pop_back() {
        if (count < 1) throw new NoSuchElementException();
        T data = tail.data;
        if (count == 1) {
            head = tail = null;
        } else {
            // *** Make next to last item's next ptr null
            // *** Make tail point to next to last item
        }
        count--;
        return data;
    }
    
    public T pop() {
        return pop_back();
    }
    
    public LinkedList<T> push_front(T data) {
        Node<T> nNode = new Node<T>(data);
        if (head == null) {
            head = tail = nNode;
        } else {
            // *** Set the old head's prev ptr to the new node
            nNode.next = head;
            head = nNode;
        }
        count++;
        return this;
    }

    public LinkedList<T> push_back(T data) {
        Node<T> nNode = new Node<T>(data);
        if (head == null) {
            head = tail = nNode;
        } else {
            tail.next = nNode;
            // *** Need to set the new node's prev ptr to the tail node
            tail = nNode;
        }
        count++;
        return this;
    }

    public LinkedList<T> push(T data) {
        return push_back(data);
    }

    public boolean remove(T data) {
        if (head == null) return false;
        Node<T> curr = head;
        int pos = 0;
        while (curr != null && !curr.data.equals(data)) {
            curr = curr.next;
            pos++;
        }
        if (curr != null) {
            if (pos == 0) pop_front();
            else if (pos == count-1) pop_back();
            else {
                // *** Adjust the previous and next elements to refer to
                // *** each other (bypassing the current element)
                count--;
            }
            return true;
        } else {
            return false;
        }
    }
    
    public LinkedList<T> insertAt(int pos, T data) {
        if (pos < 0 || pos > count) throw new NoSuchElementException();
        if (pos == 0) push_front(data);
        else if (pos == count) push_back(data);
        else {
            int i = 0;
            Node<T> curr = head;
            while (i < pos) {
                curr = curr.next;
                i++;
            }
            Node<T> nNode = new Node<T>(data);
            // *** Set the previous item's next ptr to the new node
            // *** Set the new node's prev ptr to the previous node
            nNode.next = curr;
            // *** Set the current node's prev ptr to the new node
            count++;
        }
        return this;
    }
    
    public boolean contains(T data) {
        boolean found = false;
        Node<T> curr = head;
        while (curr != null && !curr.data.equals(data)) curr = curr.next;
        if (curr != null) found = true;
        return found;
    }
    
    public LinkedList<T> deleteAt(int pos) {
        if (pos < 0 || pos > count-1) throw new NoSuchElementException();
        if (pos == 0) pop_front();
        else if (pos == count-1) pop_back();
        else {
            int i = 0;
            Node<T> curr = head;
            while (i < pos) {
                curr = curr.next;
                i++;
            }
            // *** Adjust the previous and next elements to refer to
            // *** each other (bypassing the current element)
            count--;
        }
        return this;
    }

    public static boolean test() {
        int errors = 0;
        int tests = 0;

        LinkedList<Integer> lst= new LinkedList<>();
        ArrayList<Integer> v = new ArrayList<>();;
        tests++;
        if (!lst.check(v, lst)) {
            System.out.println("Error: default constructor");
            errors++;
        } else {
            System.out.println("Passed: default constructor test");
        }

        lst.push_front(2).push_front(1);
        v.add(0, 2);
        v.add(0, 1);
        tests++;
        if (!lst.check(v, lst)) {
            System.out.println("Error: push_front(int)");
            errors++;
        } else {
            System.out.println("Passed: push_front(int) test");
        }

        lst.push_back(3);
        v.add(3);
        tests++;
        if (!lst.check(v, lst)) {
            System.out.println("Error: push_back(int)");
            errors++;
        } else {
            System.out.println("Passed: push_back(int) test");
        }

        lst.push(4);
        v.add(4);
        tests++;
        if (!lst.check(v, lst)) {
            System.out.println("Error: push(int)");
            errors++;
        } else {
            System.out.println("Passed: push(int) test");
        }

        tests++;
        if (lst.peek_front() != v.get(0)) {
            System.out.println("Error: peek_front()");
            errors++;
        } else {
            System.out.println("Passed: peek_front() test");
        }

        tests++;
        if (lst.peek_back() != v.get(v.size()-1)) {
            System.out.println("Error: peek_back()");
            errors++;
        } else {
            System.out.println("Passed: peek_back() test");
        }

        tests++;
        if (lst.peek() != v.get(v.size()-1)) {
            System.out.println("Error: peek()");
            errors++;
        } else {
            System.out.println("Passed: peek() test");
        }

        // Test insert_at(int, T) function
        tests++;
        lst.insertAt(0, 11);
        lst.insertAt(2, 12);
        lst.insertAt(lst.size(), 13);
        v.add(0, 11);
        v.add(2, 12);
        v.add(v.size(), 13);
        if (!lst.check(v, lst)) {
            System.out.println("Error: insertAt(int, int)");
            errors++;
            display("Is:  ", lst);
            display("S/b: ", v);
        } else {
            System.out.println("Passed: insertAt(int, int) test");
        }

        // Test delete_at(int) function
        tests++;
        v.remove(0);
        v.remove(1);
        v.remove(v.size()-1);
        lst.deleteAt(0);
        lst.deleteAt(1);
        lst.deleteAt(lst.size()-1);
        if (!lst.check(v, lst)) {
            System.out.println("Error: deleteAt(int, int)");
            errors++;
            display("Is:  ", lst);
            display("\nS/b: ", v);
            System.out.println('\n');
        } else {
            System.out.println("Passed: deleteAt(int, int) test");
        }

        // Test remove(T) function
        tests++;
        v.remove(1);
        v.remove(0);
        v.remove(v.size()-1);
        if (!lst.remove(2)) System.out.println("Error: remove(2) failed");
        if (!lst.remove(4)) System.out.println("Error: remove(4) failed");
        if (!lst.remove(1)) System.out.println("Error: remove(1) failed");
        if (lst.remove(7)) System.out.println("Error: remove(7) should have failed");
        if (!lst.check(v, lst)) {
            System.out.println("Error: remove(int)");
            errors++;
            display("Is:  ", lst);
            display("S/b: ", v);
        } else {
            System.out.println("Passed: remove(int) test");
        }

        // Test set(int, T) method
        tests++;
        v.set(0, 5);
        v.add(10);
        v.add(15);
        lst.push(1);
        lst.push(1);
        lst.set(0, 5);
        lst.set(1, lst.get(0) + lst.get(0));
        lst.set(2, lst.get(0) + lst.get(1));
        if (!lst.check(v, lst)) {
            System.out.println("Error: set(int, T) method");
            errors++;
            display("Is:  ", lst);
            display("S/b: ", v);
        } else {
            System.out.println("Passed: set(int, T) test");
        }

        // Test copy constructor
        tests++;
        LinkedList<Integer> lst2 = new LinkedList<Integer>(lst);
        if (!lst.check(v, lst2)) {
            System.out.println("Error: copy constructor");
            errors++;
            display("Is:  ", lst2);
            display("S/b: ", v);
        } else {
            System.out.println("Passed: copy constructor test");
        }

        // Test pop() function
        tests++;
        lst.push_back(20);
        lst.push_back(25);
        if (lst.pop() != 25 || lst.size() != lst2.size()+1) {
            System.out.println("Error: pop()");
            errors++;
        } else {
            System.out.println("Passed: pop() test");
        }

        // Test pop_back() function
        tests++;
        if (lst.pop_back() != 20 || lst.size() != lst2.size()) {
            System.out.println("Error: pop_back()");
            errors++;
        } else {
            System.out.println("Passed: pop_back() test");
        }

        // Test pop_front() function
        tests++;
        if (lst.pop_front() != 5 || lst.size() != lst2.size()-1) {
            System.out.println("Error: pop_front()");
            errors++;
        } else {
            System.out.println("Passed: pop_front() test");
        }

        // Additional test for pop*() functions
        v.clear();
        v.add(10);
        v.add(15);
        tests++;
        if (!lst.check(v, lst)) {
            System.out.println("Error: pop*");
            errors++;
        } else {
            System.out.println("Passed: pop* test");
        }

        // Test contains(T) function
        lst.push_back(20);
        tests++;
        if (!lst.contains(Integer.valueOf(10)) || !lst.contains(Integer.valueOf(15)) || !lst.contains(Integer.valueOf(20)) || lst.contains(Integer.valueOf(5))) {
            System.out.println("Error: contains()");
            errors++;
        } else {
            System.out.println("Passed: contains()");
        }

        // Test clear() function
        lst.clear();
        tests++;
        if (lst.size() != 0 || lst2.size() == 0 || lst.head != null || lst.tail != null) {
            System.out.println("Error: clear()");
            errors++;
        } else {
            System.out.println("Passed: clear() test");
        }

        // Test empty() function
        tests++;
        if (!lst.empty()) {
            System.out.println("Error: empty()");
            errors++;
        } else {
            System.out.println("Passed: empty() test");
        }

        System.out.println(tests + " tests attempted");
        System.out.println(errors + " errors encountered");

        return errors == 0;
    }
    
    private boolean check(ArrayList<T> v, LinkedList<T> lst) {
        if ((v.size() != lst.size()) || (lst.size() != lst.count)) return false;
        if (lst.count == 0 && (lst.head != null || lst.tail != null)) return false;
        if (lst.count != 0 && (lst.head == null || lst.tail == null)) return false;
        Node<T> p = lst.head;
        for (int i=0; i<lst.count; i++) {
            if (p == null) return false;
            if (i == 0 && (lst.head != p || p.prev != null)) return false;
            if (p == null || !p.data.equals(v.get(i))) return false;
            if (i == lst.count-1 && (lst.tail != p || p.next != null)) return false;
            p = p.next;
        }
        return true;
    }

    private static void display(String preamble, ArrayList<Integer> lst) {
        System.out.print(preamble);
        for (int i=0; i<lst.size(); i++) System.out.print(lst.get(i) + " ");
        System.out.println();
    }
    
    private static void display(String preamble, LinkedList<Integer> lst) {
        System.out.print(preamble);
        for (int i=0; i<lst.size(); i++) System.out.print(lst.get(i) + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        boolean passed = LinkedList.test();
        System.out.println("Passed tests: " + passed);
    }
}