package datastructs;

import java.util.Enumeration;

/**
 * Singly-linked list data structure
 * @author Derek Bridge
 */
public class SinglyLinkedList
   implements Sequence
{
/* =======================================================================
       CONSTRUCTORS
   =======================================================================
*/
   /**
    * Allocates a new, empty singly-linked list data structure.
    */
   public SinglyLinkedList()
   {
   }

/* =======================================================================
       PUBLIC INTERFACE
   =======================================================================
*/

/* --Getters----------------------------------------------------------- */

   /**
    * Returns true if and only if the given object is in the list.
    *
    * @param anObject the object being sought.
    * @return true if the given object is in the list; false otherwise
    */
   public boolean contains(final Object anObject)
   {  // Walk along the list, checking each item.
      // If found, return true.
      // This works correctly for an empty list because then the loop body
      // is not executed at all, so false is returned.
      Node n = head;
      int i = 0;
      while (n != null)
      {  if (n.data.equals(anObject))
         {  return true;
         }
         n = n.next;
         i++;
      }
      // Didn't find the object.
      return false;
   }

   /**
    * Returns the first object in the list.
    * This must not be invoked on an empty list.
    *
    * @return the first object in the list.
    */
   public Object getFirst()
   {  return head.data;
   }

   /**
    * Returns the last object in the list.
    * This must not be invoked on an empty list.
    *
    * @return the last object in the list.
    */
   public Object getLast()
   {  return tail.data;
   }

   /**
    * Returns true if and only if this list is empty.
    *
    * @return true if the list is empty; false otherwise.
    */
   public boolean isEmpty()
   {  // List is empty if pointer to its head points to nothing
      return size == 0;
   }

   /**
    * Returns the size of the list.
    *
    * @return the number of nodes in the list.
    */
   public int size()
   {  return size;
   }

   /**    
    * Returns an iterator over the list.
    *
    * @return an iterator (implementing Enumeration) over the list
    */
   public Enumeration elements()
   {  return new Iterator();
   }

/* --Setters----------------------------------------------------------- */

   /**
    * Insert the given object into the list.
    *
    * @param anObject the object being inserted.
    */
   public void add(final Object anObject)
   {  // Since the object can be added anywhere, we
      // add it to the end. (This is still a constant time operation).
      addLast(anObject);
   }

   /**
    * Insert the given object at the front of the list.
    *
    * @param anObject the object being inserted.
    */
   public void addFirst(final Object anObject)
   {  Node n = new Node(anObject, null);
      if (isEmpty())
      {  tail = n;
      }
      else
      {  n.next = head;
      }
      head = n;
      size++;
   }

   /**
    * Insert the given object at the end of the list.
    *
    * @param anObject the object being inserted.
    */
   public void addLast(final Object anObject)
   {  Node n = new Node(anObject, null);
      if (isEmpty())
      {  head = n;
      }
      else
      {  tail.next = n;
      }
      tail = n;
      size++;
   }

   /**
    * Remove the given object from the list, if it is there.
    * If the object appears more than once, its earliest occurrence is 
    * removed.
    * The list is unchanged if the object does not appear in it at all
    * (including if the list is empty).
    *
    * @param anObject the object being removed.
    */
   public void remove(final Object anObject)
   {  if (! isEmpty())
      {  // Removing the first element is special because it requires
         // update of head pointer.
         if (head.data.equals(anObject))
         {  // If this is the only node, the tail needs updating too
            if (head == tail)
            {  head = null;
               tail = null;
            }
            else
            {  head = head.next;
            }
            size--;
         }
         else
         {  // Find the node that is previous to the one to be deleted
            Node previous = head;
            while (previous.next != null && 
               ! previous.next.data.equals(anObject))
            {  previous = previous.next;
            }
            // If we found the object (i.e. didn't reach end of list),
            if (previous != null)
            {  // If the object being deleted is the tail, update tail pointer
               if (previous.next == tail)
               {  tail = previous;
               }
               // Make previous node point to what the removed node pointed to
               previous.next = previous.next.next;
               size--;
            }
         }
      }
   }

   /**
    * Remove the first object from the list.
    * The list is unchanged if it is empty.
    *
    */
   public void removeFirst()
   {  if (! isEmpty())
      {  if (head == tail)
         {  head = null;
            tail = null;
         }
         else
         {  head = head.next;
         }
         size--;
      }
   }

   /**
    * Remove the last object from the list.
    * The list is unchanged if it is empty.
    *
    */
   public void removeLast()
   {  // Even though we have a tail pointer, this operation is still
      // linear in the length of the list. 
      // We need to find the item that comes previous to the last item.
      // The only way to do this is to serach from the head to the end.
      if (! isEmpty())
      {  // If this is the only node, update both pointers
         if (head == tail)
         {  head = null;
            tail = null;
         }
         else
         {  // Find the node that is previous to the one to be deleted
            Node previous = head;
            while (previous.next != null)
            {  previous = previous.next;
            }
            // We're removing previous.next (the last element)
            tail = previous;               
            previous.next = null;
         }
         size--;
      }
   }

/* --Common object interface------------------------------------------- */

  /**
    * Returns a string representation of this list, which includes
    * string representations (computed using toString) of each
    * object in the list.
    *
    * @return a string representation of this list.
    */
   public String toString()
   {  StringBuffer sb = new StringBuffer();
      for (Node current = head; current != null; current = current.next)
      {  sb.append(current.data.toString()).append("   ");
      }
      return sb.toString().trim();
   }

/* =======================================================================
       MEMBER CLASSES
   =======================================================================
*/
   /*
    * Linked list nodes in a singly-linked list.
    */
   private class Node
   {
      /*
       * Allocates a new node for a singly-linked list.
       * This node `points to' the given node.
       *
       * @param anObject the data to be stored at this node.
       * @param aNode the node that this new node will `point to'.
       */
      private Node(final Object anObject, final Node aNode)
      {  data = anObject;
         next = aNode;
      }

      private Object data;
      private Node next;
   }

   /**
    * Linked list iterator.
    */
   private class Iterator 
      implements Enumeration
   {
      /*
       * Allocates an iterator object for this linked list.
       */
      private Iterator()
      {  current = head;
      }
 
      /**
       * Returns true if and only if there are no more elements to visit.
       *
       * @return true if there are no more elements to visit; false otherwise.
       */
      public boolean hasMoreElements()
      {  return current != null;
      }

      /**
       * Returns the next unvisited object in the list.
       * Should only be invoked if there are more elements.
       *
       * @return the next unvisited object.
       */
      public Object nextElement()
      {  Object obj = current.data;
         current = current.next;
         return obj;
      }

      private Node current; // current acts as a cursor for traversing the list
   }

/* =======================================================================
       INSTANCE VARIABLES & CLASS VARIABLES
   =======================================================================
*/

   // Maintaining pointers to head and tail makes insertion at either
   // end a constant time operation.
   // Removal at head is also constant time.
   // Removal from tail still takes time proportional to the length of
   // the list because we need to walk the list to get to the node
   // that comes previous to the node to be deleted.
   private Node head = null;
   private Node tail = null;
   private int size = 0;

/* =======================================================================
       TEST DRIVER
   =======================================================================
*/
   public static void main(String[] args)
   {  /* Lots of test cases needed. At least the following:
         Testing add, addFirst and addLast
            Insertion into empty list, single item list, multi item list 
         Testing getFirst and getLast
            Empty list, single item list, multi item list
         Testing isEmpty
            Empty list, no-empty list
         Testing size
            Empty list, single item list, multi item list
         Testing contains 
            Empty list, single item returning true, single item returning
            false, multi item matching head, multi item matching something
            in the middle, multi item matching tail, multi item but
            returning false
         Testing elements (plus hasMore Elements, nextElement)
            Empty list, single item list, mutli item list
         Testing removeFirst and removeLast
           Empty list, single item list, multi item list
         Testing remove
            Empty list, single item list that matches, single item list but
            not matching, multi item matching head, multi item matching 
            something in the middle, multi item matching tail, multi item but
            matching nothing, multi item but matching more than one thing
         Testing toString
            Empty list, single item list, multi item list
      */
   }
}