/* With methods added by Jen Chen
Updated on 03/18/03
*/
package cs212p4_solution;

public class myList implements Cloneable{
   // Invariant of the myList class:
   //   1. The elements in the bag are stored on a linked list.
   //   2. The head reference of the list is in the instance variable head.
   //   3. The total number of elements in the list is in the instance variable manyNodes.
   private IntNode head;
   private IntNode tail;
   private int manyNodes;

   /**
   * Initialize an empty bag.
   * @param - none
   * -Postcondition:-
   *   This bag is empty.
   **/
   public myList(){
      head = null;
      tail = null;
      manyNodes = 0;
   }

   /**
   * Add a new element to this bag.
   * @param "element": the new element that is being added
   * -Postcondition:-
   *   A new copy of the element has been added to this bag.
   * @exception OutOfMemoryError: Indicates insufficient memory a new IntNode.
   **/
   public void add(int element) {
      head = new IntNode(element, head);
      manyNodes++;
   }

   /**
   * Add the contents of another bag to this bag.
   * @param "addend": a bag whose contents will be added to this bag
   * -Precondition:-
   *   The parameter, "addend", is not null.
   * -Postcondition:-
   *   The elements from "addend" have been added to this bag.
   * @exception NullPointerException: Indicates that "addend" is null.
   * @exception OutOfMemoryError: Indicates insufficient memory to increase the size of the bag.
   **/
   public void addAll(myList addend){
      IntNode[] copyInfo;

      // The precondition indicates that addend is not null. If it is null,
      // then a NullPointerException is thrown here.
      if (addend.manyNodes > 0){
         copyInfo = IntNode.listCopyWithTail(addend.head);
         copyInfo[1].setLink(head); // Link the tail of copy to my own head...
         head = copyInfo[0];        // and set my own head to the head of the copy.
         manyNodes += addend.manyNodes;
      }
   }

   /**
   * Generate a copy of this bag.
   * @param - none
   * @return
   *   The return value is a copy of this bag. Subsequent changes to the
   *   copy will not affect the original, nor vice versa. Note that the return
   *   value must be type cast to an "myList" before it can be used.
   * @exception OutOfMemoryError: Indicates insufficient memory for creating the clone.
   **/
   public Object clone( ){  // Clone a nmyList object.
      myList answer;

      try{
         answer = (myList) super.clone( );
      }catch (CloneNotSupportedException e){  // This exception should not occur. But if it does, it would probably
         // indicate a programming error that made super.clone unavailable.
         // The most common error would be forgetting the "Implements Cloneable"
         // clause at the start of this class.
         throw new RuntimeException
         ("This class does not implement Cloneable");
      }
      answer.head = IntNode.listCopy(head);
      return answer;
   }

   /**
   * Accessor method to count the number of occurrences of a particular element in this bag.
   * @param "target": the element that needs to be counted
   * @return
   *   the number of times that "target" occurs in this bag
   **/
   public int countOccurrences(int target){
      int answer;
      IntNode cursor;

      answer = 0;
      cursor = IntNode.listSearch(head, target);
      while (cursor != null)
      {  // Each time that cursor is not null, we have another occurrence of
         // target, so we add one to answer and then move cursor to the next
         // occurrence of the target.
         answer++;
         cursor = cursor.getLink( );
         cursor = IntNode.listSearch(cursor, target);
      }
      return answer;
   }

   /**
   * Remove one copy of a specified element from this bag.
   * @param "target":  the element to remove from the bag
   * -Postcondition:-
   *   If "target" was found in the bag, then one copy of "target" has been removed
   *   and the method returns true.
   *   Otherwise the bag remains unchanged and the method returns false.
   **/
   public boolean remove(int target){
      IntNode targetNode; // The node that contains the target

      targetNode = IntNode.listSearch(head, target);//return the node that is found.
      if (targetNode == null)
         // The target was not found, so nothing is removed.
         return false;
      else{  // The target was found at targetNode. So copy the head data to targetNode
         // and then remove the extra copy of the head data.
         targetNode.setData(head.getData( ));
         head = head.getLink( );
         manyNodes--;
         return true;
      }
   }

   /**
   * Determine the number of elements in this bag.
   * @param - none
   * @return:  the number of elements in this bag
   **/
   public int size( ){
      return manyNodes;
   }

   /**
   * Create a new bag that contains all the elements from two other bags.
   * @param "b1": the first of two bags
   * @param "b2": the second of two bags
   * -Precondition:-
   *   Neither b1 nor b2 is null.
   * @return: the union of b1 and b2
   * @exception IllegalArgumentException: Indicates that one of the arguments is null.
   * @exception OutOfMemoryError: Indicates insufficient memory for the new bag.
   **/

   public static myList union(myList b1, myList b2) {
      // The precondition requires that neither b1 nor b2 is null.
      // If one of them is null, then addAll will throw a NullPointerException.
      myList answer = new myList( );

      answer.addAll(b1);
      answer.addAll(b2);
      return answer;
   }

   public void showAll(){//method added by JC
    IntNode cur = head;
    for(int i = 1; i <= manyNodes; i++){
      if(i%10 != 0){
        System.out.print(cur.getData() + "\t");
        cur = cur.getLink();  //set the pointer points to the next node.
      }else{
        System.out.print(cur.getData() + "\n");
        cur = cur.getLink();  //set the pointer points to the next node.
      }//end of if()
    }//end of FOR()
   }//end of showAll()

   public boolean isEmpty(){
    return head==null;
   }

  public void myRemove(int target){//method added by JC
    if(!isEmpty())
      if(head==tail && target == head.getData())
        head = tail = null;
      else if(target == head.getData())
        head = head.getLink();
      else {
        IntNode pred, tmp;
        for(pred = head, tmp = head.getLink();
            tmp != null && tmp.getData() != target;
          pred = pred.getLink(), tmp = tmp.getLink());
        if(tmp != null){
          pred.setLink(tmp.getLink());
          if(tmp == tail)  //if target is the last node
            tail = pred;
        }
        }
    manyNodes--;
  }//end of myRemove()

//A method to insert a node AFTER the current node!
  public void insertAfter(int position, int data){//Method added by JC
    IntNode prev = head;
    if(head == null)
      System.out.println("Empty list! Can not add element AFTER an empty list");
    else{
      for(int count = 1; count <= position; count++){
        if(count == position){
          prev.addNodeAfter(data);
          manyNodes++;
        }else
          prev = prev.getLink();
      }//end of FOR()
    }//end of outer if()
  }//end of insertAfter()

//A method to insert a node BEFORE the current node!
  public void insertBefore(int position, int data){//Method added by JC
    IntNode prev = head;
    if(head == null)
      System.out.println("Empty list! Can not add element BEFORE an empty list");
    else{
      for(int count = 1; count <= position; count++){
        if(count == (position - 2)){
          prev.addNodeAfter(data);
          manyNodes++;
        }else
          prev = prev.getLink();
      }//end of FOR()
    }//em=nd of outer if()
  }//end of insertBefore()

//A method to delete a node BEFORE the current node!
  public void deleteBefore(int position){//Method added by JC
    IntNode prev = head;
    if(head == null)
      System.out.println("Empty list! Can not DELETE in an empty list");
    else if(this.size() == 2)//If there are only two nodes, then delete the head node!
      this.head = this.tail;
    else{
      for(int count = 1; count < position; count++){
        if(count == (position - 2)){
          prev.removeNodeAfter();
          manyNodes--;
        }else
          prev = prev.getLink();
      }//end of FOR()
    }//end of outer if()
  }//end of deleteBefore()

//A method to delete a node AFTER the current node!
  public void deleteAfter(int position){//Method added by JC
    IntNode prev = head;
    if(head == null)
      System.out.println("Empty list! Can not DELETE in an empty list");
    else{
      for(int count = 1; count <= position; count++){
        if(count == position){
          prev.removeNodeAfter();
          manyNodes--;
        }else
          prev = prev.getLink();
      }//end of FOR()
    }//end of outer if()
  }//end of deleteAfter()

  public void listAdvance(int position){ //method to advance a node to the spcified position in a link list.
    IntNode cur = head;                //Thus listAdvance(5) will advance the pointer to the 5th node of the link list.
    for(int i = 0; i <= position; i++){
        cur = cur.getLink();  //set the current pointer to be the next opinter, thus moves the current node to the next node.
    }
  }//end of method.

  public void swapList(myList list_1, myList list_2){//Swap the elements of two lists.
    IntNode tmp, tmp2;
    int tmpNum, tmpNum2;
    tmp = list_1.head;
    tmp2 = list_2.head;
    tmpNum = tmp.getData();
    tmpNum2 = tmp2.getData();
    tmp2.setData(tmpNum);
    tmp.setData(tmpNum2);
    while(tmp.link != null){
      tmp = tmp.link;
      tmp2 = tmp2.link;
      tmpNum = tmp.getData();
      tmpNum2 = tmp2.getData();
      tmp.setData(tmpNum2);
      tmp2.setData(tmpNum);
    }
  }//end of method.

  public void appendList(myList list_1, myList list_2){ //Appending one list to an existing link list.
    IntNode tmp, tmp2;
    int tmpNum, count = 1;
    tmp = list_1.head;
    tmp2 = list_2.head;
    while(tmp.link != null){ //move to the end of the first list (which is the tail of the first list)
      count++;
      tmp = tmp.link;
    }
    while( tmp2.link != null){
      list_1.insertAfter(count, tmp2.getData());
      tmp2 = tmp2.link;
      count++;
      if(tmp2.link == null)//count stops counting BEFORE the tail node, thus we have to add a node AT the TAIL NODE.
        list_1.insertAfter(count, tmp2.getData());
    }
  }//end of method.

//A method to SORT the elements in the list
  public void sortList(myList list){

  }//end of sortList()
}