/* Modified by Jen Chen
   Updated on March the 4th, 2003  
*/
package linklist;
import java.util.*;
/******************************************************************************
* An <CODE>IntNode</CODE> provides a node for a linked list with
* integer data in each node.
*
* <dl><dt><b>Limitations:</b>
*   <dd>
*   Lists of nodes can be made of any length, limited only by the amount of
*   free memory in the heap. But beyond <CODE>Integer.MAX_VALUE</CODE> (2,147,483,647),
*   the answer from <CODE>listLength</CODE> is incorrect because of arithmetic
*   overflow.
* </dl>
*
******************************************************************************/
public class IntNode{
   // Invariant of the IntNode class:
   //   1. The node's integer data is in the instance variable data.
   //   2. For the final node of a list, the link part is null.
   //      Otherwise, the link part is a reference to the
   //      next node of the list.
   public int data;
   public IntNode link;

   /**
   * Initialize a node with a specified initial data and link to the next
   * node. Note that the <CODE>initialLink</CODE> may be the null reference,
   * which indicates that the new node has nothing after it.
   * @param <CODE>initialData</CODE>
   *   the initial data of this new node
   * @param <CODE>initialLink</CODE>
   *   a reference to the node after this new node--this reference may be null
   *   to indicate that there is no node after this new node.
   * <dt><b>Postcondition:</b><dd>
   *   This node contains the specified data and link to the next node.
   **/
   public IntNode(int initialData, IntNode initialLink) {
      data = initialData;
      link = initialLink;
   }

   /**
   * Modification method to add a new node after this node.
   * @param <CODE>item</CODE>
   *   the data to place in the new node
   * <dt><b>Postcondition:</b><dd>
   *   A new node has been created and placed after this node.
   *   The data for the new node is <CODE>item</CODE>. Any other nodes
   *   that used to be after this node are now after the new node.
   * @exception OutOfMemoryError
   *   Indicates that there is insufficient memory for a new
   *   <CODE>IntNode</CODE>.
   **/
   public void addNodeAfter(int item){
      link = new IntNode(item, link);
   }

   /**
   * Accessor method to get the data from this node.
   * @param - none
   * @return
   *   the data from this node
   **/
   public int getData(){
      return data;
   }

   /**
   * Accessor method to get a reference to the next node after this node.
   * @param - none
   * @return
   *   a reference to the node after this node (or the null reference if there
   *   is nothing after this node)
   **/
   public IntNode getLink(){
      return link;
   }

   /**
   * Copy a list.
   * @param <CODE>source</CODE>
   *   the head of a linked list that will be copied (which may be
   *   an empty list in where <CODE>source</CODE> is null)
   * @return
   *   The method has made a copy of the linked list starting at
   *   <CODE>source</CODE>. The return value is the head reference for the
   *   copy.
   * @exception OutOfMemoryError
   *   Indicates that there is insufficient memory for the new list.
   **/
   public static IntNode listCopy(IntNode source){
      IntNode copyHead;
      IntNode copyTail;

      // Handle the special case of the empty list.
      if (source == null)
         return null;

      // Make the first node for the newly created list.
      copyHead = new IntNode(source.data, null);
      copyTail = copyHead;

      // Make the rest of the nodes for the newly created list.
      while (source.link != null){
         source = source.link;
         copyTail.addNodeAfter(source.data);
         copyTail = copyTail.link;
      }//end of WHILE()

      // Return the head reference for the new list.
      return copyHead;
   }

   /**
   * Copy a list, returning both a head and tail reference for the copy.
   * @param <CODE>source</CODE>
   *   the head of a linked list that will be copied (which may be
   *   an empty list in where <CODE>source</CODE> is null)
   * @return
   *   The method has made a copy of the linked list starting at
   *   <CODE>source</CODE>.  The return value is an
   *   array where the [0] element is a head reference for the copy and the [1]
   *   element is a tail reference for the copy.
   * @exception OutOfMemoryError
   *   Indicates that there is insufficient memory for the new list.
   **/
   public static IntNode[ ] listCopyWithTail(IntNode source){
      IntNode copyHead;
      IntNode copyTail;
      IntNode[ ] answer = new IntNode[2];

      // Handle the special case of the empty list.
      if (source == null)
         return answer; // The answer has two null references .

      // Make the first node for the newly created list.
      copyHead = new IntNode(source.data, null);
      copyTail = copyHead;

      // Make the rest of the nodes for the newly created list.
      while (source.link != null){
         source = source.link;
         copyTail.addNodeAfter(source.data);
         copyTail = copyTail.link;
      }

      // Return the head and tail references.
      answer[0] = copyHead;
      answer[1] = copyTail;
      return answer;
   }

   /**
   * Compute the number of nodes in a linked list.
   * @param <CODE>head</CODE>
   *   the head reference for a linked list (which may be an empty list
   *   with a null head)
   * @return
   *   the number of nodes in the list with the given head
   * <dt><b>Note:</b><dd>
   *   A wrong answer occurs for lists longer than <CODE>Int.MAX_VALUE</CODE>.
   **/
   public static int listLength(IntNode head){
      IntNode cursor;
      int answer;

      answer = 0;
      for (cursor = head; cursor != null; cursor = cursor.link)
         answer++;

      return answer;
   }

   /**
   * Copy part of a list, providing a head and tail reference for the new copy.
   * @param <CODE>start/end</CODE>
   *   references to two nodes of a linked list
   * @param <CODE>copyHead/copyTail</CODE>
   *   the method sets these to refer to the head and tail node of the new
   *   list that is created
   * <dt><b>Precondition:</b><dd>
   *   <CODE>start</CODE> and <CODE>end</CODE> are non-null references to nodes
   *   on the same linked list,
   *   with the start node at or before the end node.
   * @return
   *   The method has made a copy of the part of a linked list, from the
   *   specified start node to the specified end node. The return value is an
   *   array where the [0] component is a head reference for the copy and the
   *   [1] component is a tail reference for the copy.
   * @exception IllegalArgumentException
   *   Indicates that <CODE>start</CODE> and <CODE>end</CODE> are not references
   *   to nodes on the same list.
   * @exception NullPointerException
   *   Indicates that start is null.
   * @exception OutOfMemoryError
   *   Indicates that there is insufficient memory for the new list.
   **/
   public static IntNode[] listPart(IntNode start, IntNode end){
      IntNode copyHead;
      IntNode copyTail;
      IntNode cursor;
      IntNode[] answer = new IntNode[2];

      // Make the first node for the newly created list. Notice that this will
      // cause a NullPointerException if start is null.
      copyHead = new IntNode(start.data, null);
      copyTail = copyHead;
      cursor = start;

      // Make the rest of the nodes for the newly created list.
      while (cursor != end){
         cursor = start.link;
         if (cursor == null)
            throw new IllegalArgumentException
            ("end node was not found on the list");
         copyTail.addNodeAfter(cursor.data);
         copyTail = copyTail.link;
      }

      // Return the head and tail references
      answer[0] = copyHead;
      answer[1] = copyTail;
      return answer;
   }

   /**
   * Find a node at a specified position in a linked list.
   * @param <CODE>head</CODE>
   *   the head reference for a linked list (which may be an empty list in
   *   which case the head is null)
   * @param <CODE>position</CODE>
   *   a node number
   * <dt><b>Precondition:</b><dd>
   *   position > 0.
   * @return
   *   The return value is a reference to the node at the specified position in
   *   the list. (The head node is position 1, the next node is position 2, and
   *   so on.) If there is no such position (because the list is too short),
   *   then the null reference is returned.
   * @exception IllegalArgumentException
   *   Indicates that <CODE>position</CODE> is not positive.
   **/
   public static IntNode listPosition(IntNode head, int position){
      IntNode cursor;
      int i;

      if (position <= 0)
           throw new IllegalArgumentException("position is not positive");

      cursor = head;
      for (i = 1; (i < position) && (cursor != null); i++)
         cursor = cursor.link;

      return cursor;
   }

   /**
   * Search for a particular piece of data in a linked list.
   * @param <CODE>head</CODE>
   *   the head reference for a linked list (which may be an empty list in
   *   which case the head is null)
   * @param <CODE>target</CODE>
   *   a piece of data to search for
   * @return
   *   The return value is a reference to the first node that contains the
   *   specified target. If there is no such node, the null reference is
   *   returned.
   **/
   public static IntNode listSearch(IntNode head, int target){
      IntNode cursor;

      for (cursor = head; cursor != null; cursor = cursor.link)
         if (target == cursor.data)
            return cursor;

      return null;
   }

   /**
   * Modification method to remove the node after this node.
   * @param - none
   * <dt><b>Precondition:</b><dd>
   *   This node must not be the tail node of the list.
   * <dt><b>Postcondition:</b><dd>
   *   The node after this node has been removed from the linked list.
   *   If there were further nodes after that one, they are still
   *   present on the list.
   * @exception NullPointerException
   *   Indicates that this was the tail node of the list, so there is nothing
   *   after it to remove.
   **/
   public void removeNodeAfter(){
      link = link.link;
   }

   /**
   * Modification method to set the data in this node.
   * @param <CODE>newData</CODE>
   *   the new data to place in this node
   * <dt><b>Postcondition:</b><dd>
   *   The data of this node has been set to <CODE>newData</CODE>.
   **/
   public void setData(int newData) {
      data = newData;
   }

   /**
   * Modification method to set the link to the next node after this node.
   * @param <CODE>newLink</CODE>
   *   a reference to the node that should appear after this node in the linked
   *   list (or the null reference if there is no node after this node)
   * <dt><b>Postcondition:</b><dd>
   *   The link to the node after this node has been set to <CODE>newLink</CODE>.
   *   Any other node (that used to be in this link) is no longer connected to
   *   this node.
   **/
   public void setLink(IntNode newLink) {
      link = newLink;
   }

  public static IntNode listAdvance(IntNode nod){//Method added by JC
      IntNode cursor;
        cursor = nod.link;
      return cursor;
   }

//Method to return the position of a matched data found in the link list.
//Note that this method will return ONLY the position of the first element found
//in the link list!
   public static int firstFoundData(IntNode head, int target){//method added by JC.
      IntNode cursor;
      int tmp = 1;
      for (cursor = head; cursor != null; cursor = cursor.link){
         if (target == cursor.data)
            return tmp;
         else
            tmp++;
      }//end of FOR()
      return tmp;
   }

//Method to return the position (array of position) of matched data found in the link list.
//Note that there may be more than noe element that matched the data, thus we use vector
//to return the indexof the element(s) found inthe link list.
   public static Vector nodePosition(IntNode head, int target){//method added by JC.
      IntNode cursor;
      int tmp = 1;
      Vector vec = new Vector();
      for (cursor = head; cursor != null; cursor = cursor.link){
         if (target == cursor.data){
            vec.addElement(new Integer(tmp));
            tmp++;
         }
         else
            tmp++;
      }//end of FOR()
      return vec;
   }
}//end of class IntNode{}