/*
 * This is LinkedList is very similar to the one
 * we defined in class. I added a toString() method
 * for your convenience. 
 *
 * IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
 *
 *    You should implement the find(), remove(), and insertInOrder() methods.
 * 
 *    These methods should not alter the "index" accessible to the user,
 *    except as necessitated by changes to the indexed node.
 *
 *    You should implement these methods by directly manipulating the
 *    list and the nodes. Do not use the provided methods (constructors
 *    are not methods) to implement these new features. This is for practice.
 */

public class LinkedList
{
        /*
         * This class defines an Exception which can be
         * thrown in the case of an error involving the
         * "index" reference.  It is a public subclass,
         * so that other classes can catch it, but have
         * to explicitly recognize its scope by referring
         * to it by LinkedList.IndexException
         */
        public class IndexException extends Exception
        {
                /*
                 * This method creates a String representation
                 * of the Exception which has occurred
                 */
                public String toString()
                {
                        return ("Bad index in Linked List");
                }
        }


        private Node head;
        private Node tail;
        private Node index;


        /*
         * Constructor.  By default, set all the references
         * to null
         */
        public LinkedList()
        {
                head = tail = index = null;
        }


        public void addHead(Comparable data)
        {
                // Create new node w/data
                Node newNode;
                newNode = new Node(data);

                // Set new node to point to the old head
                newNode.setNext(head);

                // Reset head of list
                head = newNode;

                // Special case: empty list
                if (null == tail)
                {
                        tail = head = index = newNode;
                }
        }


        public void addTail(Comparable data)
        {
                // Create new node w/data
                Node newNode = new Node(data);

                // special case: Empty list
                // can test either head or tail == null
                if (null == head)
                {
                        head = tail = index = newNode;
                        return; // all done
                }

                // Common case: list is not empty
                tail.setNext(newNode);

                tail = newNode;
        }


        /*
         * This is pretty straight-forward. It resets the index
         * to the head of the list. This is particularly important,
         * because index cannot move backwards.
         */
        public void resetIndex()
        {
                index = head;
        }

       
        /*
         * This returns the datum from the node referenced by index. 
         * It returns null if index is null.
         */
        public Comparable getIndexedNode()
        {
                // special case: null index
                if (null == index)
                {
                        return null;
                }

                // Common case: return indexed value
                return index.getData();
        }

        
        /*
         * This moves index ahead by one node. It follows the 
         * next reference within the linked list.
         */
        public void advanceIndex()
        {
                // special case: null index
                if (null == index)
                {
                        return;
                }

                // Common case: move forward
                index = index.getNext();
        }


        /*
         * This adds a piece of data to the linked list
         * after the current index. It throws an exception
         * if index is currently null
         */
        public void insertAfterIndex(Comparable data)
                throws IndexException
        {
                // special case: null index
                if (null == index)
                {
                        throw new IndexException();
                }

                // Common case
                Node newNode = new Node(data);

                newNode.setNext(index.getNext());

                index.setNext(newNode);
        }

 
        /*
         * This deletes the node after the indexed node. It silently fails 
         * if index is null.
         */
        public void deleteAfterIndex()
        {
                // special case 1: null index
                if (null == index)
                {
                        return;
                }

                // special case 2: null index.next
                if (null == index.getNext())
                {
                        return;
                }

                // special case 3: removing the tail
                if (tail == index.getNext())
                {
                        index.setNext(null);
                        tail = index;
                        return;
                }

                // common case
                index.setNext(index.getNext().getNext());

                return;
        }


        /*
         * This is method converts the list to a string by
         * relying on the toString() method of the data element
         * within each node.
         *
         * This method is important, because it is called by 
         * System.out.println(), &c.
         */
        public String toString()
        {
          String ret = new String();

          for (Node current=head; 
               (null != current); 
               current = current.getNext())
            ret += current.getData().toString() + "\n";
          
          return ret;
        } 


        /*
         * You should implement this method. It should
         * return the item if it is found in the list and
         * null otherwise. It should rely on the ".equals()" 
         * or ".compareTo()" to do the comparison
         */
        public Comparable find (Comparable find_me)
        {
          /*
           * Your code here 
           */

          return null; // Change this, as appropriate; just for compilation
        }


        /*
         * You should implement this method. It should
         * remove the first instance of the specified item
         * from the list. If the item is not in the list,
         * it should fail silently
         */
        public void remove (Comparable remove_me)
        {
          /*
           * Your code here 
           */
        }


        /*
         * You should implement this method. It should
         * insert an item into the list "in order", that
         * is to say, it should insert the item after before
         * the first item it finds with a greater value as
         * reported by compareTo(), or at the beginning in an
         * empty list, or at the end of the list, if it is the greatest.
         *
         * For this method to be truly useful, it should be used
         * as the exclusive method of inserting into the list.
         */
        public void insertInOrder (Comparable remove_me)
        {
          /*
           * Your code here 
           */
        }
}