/**
 * An object of type StringList represents a list of strings.  Methods
 * are provided to insert a string into the list, to delete a string
 * from the list, and to check whether a given string occurs in the list.
 * (For testing purposes, a method is also provided that will return an
 * array containing all the strings in the list.)
 *    Strings that are inserted into the list must be non-null.  Inserting
 * a null string will cause NullPointerExceptions when the list is used
 * in subsequent operations.
 *    Note that this class is certainly NOT meant to be a full-featured
 * List class.  It is for demonstration only.
 */
public class StringList {


   /**
    * Internally, the list of strings is represented as a linked list of 
    * nodes belonging to the nested class Node.  The strings in the list 
    * are stored in increasing order (using the order given by the 
    * compareTo() method from the string class, which is the same as 
    * alphabetical order if all the strings are made up of lower 
    * case letters).
    */
   private static class Node {
      String item;   // One of the items in the list
      Node next;     // Pointer to the node containing the next item.
                     //   In the last node of the list, next is null.
   }


   private Node head;  // A pointer to the first node in the linked list.
                       // If the list is empty, the value is null.


   /**
    * Searches the list for a specified item.  (Note: for demonstration
    * purposes, this method does not use the fact that the items in the
    * list are ordered.)
    * @param searchItem the item that is to be searched for
    * @return true if searchItem is one of the items in the list or false if
    *    searchItem does not occur in the list.
    */
   public boolean find(String searchItem) {

      Node runner;    // A pointer for traversing the list.

      runner = head;  // Start by looking at the head of the list.
      
      while ( runner != null ) {
            // Go through the list looking at the string in each
            // node.  If the string is the one we are looking for,
            // return true, since the string has been found in the list.
            // (Note:  Since the list is ordered, if we find an item
            // that is greater than searchItem, we could immediately
            // return false.)
         if ( runner.item.equals(searchItem) )
            return true;
         runner = runner.next;  // Move on to the next node.
      }

      // At this point, we have looked at all the items in the list
      // without finding searchItem.  Return false to indicate that
      // the item does not exist in the list.

      return false;

   } // end find()


   /**
    * Delete a specified item from the list, if that item is present.
    * If multiple copies of the item are present in the list, only
    * the one that comes first in the list one is deleted.
    * @param deleteItem the item to be deleted
    * @return true if the item was found and deleted, or false if the item
    *    was not in the list.
    */
   public boolean delete(String deleteItem) {

      if ( head == null ) {
             // The list is empty, so it certainly doesn't contain deleteString.
         return false;
      }
      else if ( head.item.equals(deleteItem) ) {
              // The string is the first item of the list.  Remove it.
         head = head.next;
         return true;
      }
      else {
             // The string, if it occurs at all, is somewhere beyond the 
             // first element of the list.  Search the list.
         Node runner;     // A node for traversing the list.
         Node previous;   // Always points to the node preceding runner.
         runner = head.next;   // Start by looking at the SECOND list node.
         previous = head;
         while ( runner != null && runner.item.compareTo(deleteItem) < 0 ) {
                // Move previous and runner along the list until runner
                // falls off the end or hits a list element that is
                // greater than or equal to deleteItem.  When this 
                // loop ends, runner indicates the position where
                // deleteItem must be, if it is in the list.
            previous = runner;
            runner = runner.next;
         }
         if ( runner != null && runner.item.equals(deleteItem) ) {
                // Runner points to the node that is to be deleted.
                // Remove it by changing the pointer in the previous node.
            previous.next = runner.next;
            return true;
         }
         else {
                // The item does not exist in the list.
            return false;
         }
      }

   } // end delete()


   /**
    * Insert a specified item to the list, keeping the list in order.
    * @param insertItem the item that is to be inserted.
    */
   public void insert(String insertItem) {

      Node newNode;          // A Node to contain the new item.
      newNode = new Node();
      newNode.item = insertItem;  // (N.B.  newNode.next is null.)

      if ( head == null ) {
             // The new item is the first (and only) one in the list.
             // Set head to point to it.
         head = newNode;
      }
      else if ( head.item.compareTo(insertItem) >= 0 ) {
             // The new item is less than the first item in the list,
             // so it has to be inserted at the head of the list.
         newNode.next = head;
         head = newNode;
      }
      else {
             // The new item belongs somewhere after the first item
             // in the list.  Search for its proper position and insert it.
         Node runner;     // A node for traversing the list.
         Node previous;   // Always points to the node preceding runner.
         runner = head.next;   // Start by looking at the SECOND position.
         previous = head;
         while ( runner != null && runner.item.compareTo(insertItem) < 0 ) {
                // Move previous and runner along the list until runner
                // falls off the end or hits a list element that is
                // greater than or equal to insertItem.  When this 
                // loop ends, previous indicates the position where
                // insertItem must be inserted.
            previous = runner;
            runner = runner.next;
         }
         newNode.next = runner;     // Insert newNode after previous.
         previous.next = newNode;
      }

   }  // end insert()


   /**
    * Returns an array that contains all the elements in the list.
    * If the list is empty, the return value is an array of length zero.
    */
   public String[] getElements() {

      int count;          // For counting elements in the list.
      Node runner;        // For traversing the list.
      String[] elements;  // An array to hold the list elements.

      // First, go through the list and count the number
      // of elements that it contains.

      count = 0;
      runner = head;
      while (runner != null) {
         count++;
         runner = runner.next;
      }

      // Create an array just large enough to hold all the
      // list elements.  Go through the list again and
      // fill the array with elements from the list.

      elements = new String[count];
      runner = head;
      count = 0;
      while (runner != null) {
         elements[count] = runner.item;
         count++;
         runner = runner.next;
      }

      // Return the array that has been filled with the list elements.

      return elements;

   } // end getElements()


} // end class StringList