package DataStructures;

import java.util.NoSuchElementException;
import java.util.Iterator;

/**
  * <p>A simple implementation of singly linked lists. </p>
  *
  * <p>Lists are created empty, for example:
  * <pre>
  *   LinkedList list = new LinkedList();
  * </pre>
  * after which items can be inserted at the front of the list by
  * <pre>
  *   list.addFirst(item) 
  * </pre>
  * where <tt>item</tt> is any Object.</p>
  *
  * <p>Items can be removed from the front of the list by</p>
  * <pre>
  *   list.removeFirst();
  * </pre>
  * which removes the first item from the list.
  *
  * Lists can be traversed using an iterator, for example:
  * <pre>
  *   for (Iterator i = list.iterator(); i.hasNext();) {
  *       System.out.println(e.next());
  *   {
  * </pre>
 * @see <a href="http://java.sun.com/products/j2se/1.4/docs/api/java/util/Iterator.html">Iterator</a>
  *
  * @author Peter Williams
  */

public class LinkedList {

    private ListNode head; // the front of the list
    private int size; 
  
    /**
     * Constructs an empty list.
     */
    public LinkedList() {
        head = null;
        size = 0;
    }
  
    /**
     * Tests if the list is empty.
     * @return the status of the list.
     */
    public boolean isEmpty() {
        return (head == null);
    }

    /**
     * Returns the length of the list
     * @return the length of the list
     */
    public int size() {
        return size;
    }

    /**
     * Inserts an item at the front of the list.
     * @param <tt>item</tt> the Object to be inserted.
     */
    public void addFirst(Object item) {
        head = new ListNode(item, head);
        ++size;
    }

    /**
     * Returns the first item in the list.
     * @return the item at the front of the list.
     * @exception NoSuchElementException if the list is empty.
     */
    public Object firstItem() {
        if (head != null) {
            return head.data;
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * Removes the first item from the list.
     * @exception NoSuchElementException if the list is empty.
     */
    public void removeFirst() {
        if (head != null) {
            head = head.next;
            --size;
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * Tests whether an item is present in the list.
     * @param <tt>item</tt> the object to be searched for.
     * @return <tt>true</tt> if the item is present, 
     * <tt>false</tt> otherwise
     */
    public boolean contains(Object item) {
        ListNode current = head;
        while (current != null) {
            if (item.equals(current.data)) {
                return true;
            } else {
                current = current.next;
            }
        }
        return false;
    }
    
    /**
     * Reverses the list.
     */
    public void reverse() {
        ListNode current = head;
        head = null;
        while (current != null) {
            ListNode save = current;
            current = current.next;
            save.next = head;
            head = save;
        }
    }

    /**
     * Iterates over the items in the list.
     * @return the iterator.
     * @exception NoSuchElementException if the <tt>next</tt> method
     *            is called when there is no next element
     * @exception IllegalStateException if the <tt>next</tt> method has not
     *            yet been called, or the <tt>remove</tt> method has already
     *            been called after the last call to the <tt>next</tt>
     *            method.
     */
    public Iterator iterator() {
        return new Iterator() {
            private ListNode header = new ListNode(null, head);
            private ListNode previous = header;
            private ListNode current = head;
            private boolean removeOk = false;
            public boolean hasNext() {
                return current != null;
            }
            public Object next() {
                if (current != null) {
                    Object result = current.data;
                    current = current.next;
                    if (removeOk) {
                        previous = previous.next;
                    }
                    removeOk = true;
                    return result;
                } else {
                    throw new NoSuchElementException();
                }
            }
            public void remove() {
                if (removeOk) {
                    previous.next = current;
                    head = header.next;
                    --size;
                    removeOk = false;
                } else {
                    throw new IllegalStateException();
                }
            }
        };
    }

    /**
     * Implements the <tt>equals</tt> method.
     * @param     <tt>other</tt> the second linked list.
     * @return    <tt>true</tt> if the lists are equal, <tt>false</tt> otherwise.
     */   
    public boolean equals(Object other) {
        if (other == null ||
            !(other instanceof LinkedList) ||
            this.size != ((LinkedList) other).size) {
            return false;
        }
        ListNode p = this.head;
        ListNode q = ((LinkedList) other).head;
        while (p != null) { 
            if (!p.data.equals(q.data)) {
                return false;
            }
            p = p.next;
            q = q.next;
        }
        return true;
    }

    /**
     * Converts the list to a string.
     * @return the string representation.
     */
    public String toString() {
        String string = "";
        string += "[";
        if (head != null) {
            string += head.data;
            ListNode current = head.next;
            while (current != null) {
                string += ", " + current.data;
                current = current.next;
            }
        }
        string += "]";
        return string;
    }
  
}