/**
 *  <PRE>
 *  LinkedList.java
 *
 *  Revisions: 1.0 Sep. 21, 2002
 *               Created the LinkedList class
 *             1.1 Sep. 26, 2002
 *               Compiled, Finished, Commented
 *
 *  </PRE>
 *
 *	Collaboration Statement:
 *    I worked on the homework assignment alone, using only             
 *    course materials.
 *  
 *  Created with JCreatorLE, some indents are off when viewed through notepad
 *    or EMACS
 * 
 *  @author <A HREF="mailto:gtg184g@mail.gatech.edu">Jose Manuel Caban</A>
 *  @version Version 1.1, Sep. 26, 2002
 */

public class LinkedList {
  
  /**
   *Front of the list
   */
  private LLNode head; 
  
  /**
   *Back of the List
   */
  private LLNode tail;
  
  //there's actually something to debug this time!
  private static final boolean bDebug = false; 

  ////////////////
  //Constructors//
  ////////////////
  
  /**
   *Default constructor for LinkedList
   *sets head and tail to null
   */
  public LinkedList(){
  	head = null;
  	tail = null;
  }
  
  ///////////
  //Methods//
  ///////////
  
  /**
   *Add node to front of list
   *@param o, the data to be stored in the node
   */
  public void addToFront(Object o){
  	LLNode node = new LLNode(o,head);
  	
  	if(bDebug){System.out.print("Adding to Front:");}
  	
  	head = node;
  	if(tail == null){
  		this.tail = node;
  	}
  	
  	if(bDebug){System.out.println("Done.");}
  }
  
  /**
   *Add node to back of list
   *@param o, the data to be stored in the node
   */
  public void addToBack(Object o){
  	LLNode node = new LLNode(o);
  	
  	if(bDebug){System.out.print("Adding to Back:");}
  	  	
  	if(tail != null){
  		tail.setNext(node);  	
    }
    
  	tail = node;
  	if(head == null){
  		head = node;
  	}
  	
  	if(bDebug){System.out.println("Done.");}
  }
  
  /**
   *@return the data stored by the first node
   */
  public Object getFirst(){
  	if(head != null){
  		return head.getData();
  	}
  	
  	else {
  		return null;
  	}
  }
  
  /**
   *@return the data stored by the last node
   */
  public Object getLast(){
  	if(tail != null){
  		return tail.getData();
  	}
  	else {
  		return null;
  	}
  }
  
  /**
   *@return the data stored by the first node, destroy first node
   */
  public Object removeFromFront(){
  	if(head == null){
  		return null;
  	}
  	
  	if(bDebug){System.out.print("Removing from Front:");}
  	
  	Object temp = head.getData();
  	  
  	head = head.getNext();
  	
  	if(head == null){
  		tail = null;
  	}
  	
  	if(bDebug){System.out.println("Done.");}
  	
  	return temp;
  }
  
  /**
   *@return the data stored by the last node, destroy the last node
   */
  public Object removeFromBack(){
  	if(tail == null){
  		return null;
  	}
  	
  	if(bDebug){System.out.print("Removing from Back:");}
  	
  	Object temp = tail.getData();
  	LLNode current = head;
  	
  	if(current != tail){
  		//find second to last node
  		while(current.getNext() != tail){
  			current = current.getNext();
  		}
  		tail = current;
  		tail.setNext(null);
  	}
  	
  	else {
  		tail = null;
  	}
  	
  	if(tail == null){
  		head = null;
  	}
  	
  	if(bDebug){System.out.println("Done.");}
  	
  	return temp;
  }
  
  /**
   *@return the number of nodes in the LinkedList
   */
  public int size(){
  	
  	if(head == null){
  		return 0;
  	}
  	
  	if(head == tail){
  		return 1;
  	}
  	
  	int count=0;
  	LLNode current = head;
  	
  	while(current!= null){
  		current = current.getNext();
  		count++;
  	}
  	
  	return (count);
  }
  
  /**
   *Turn the LinkedList into an Array
   *@return array containing all the data held by the LinkedList
   */
  public Object[] asArray(){
  	
  	Object[] array = new Object[this.size()];
  	
  	if(head == null){
  		return array;
  	}
  	
  	LLNode current = head;
  	int i=0;
  	while(current != null){
  		array[i] = current.getData();
  		i++;
  		current = current.getNext();
	}
  	
  	return array;
  }
  
  /**
   *temp method to output list on screen
   *meant for debugging to circumvent the array method
   */
  public void listOut(){
  	LLNode current = head;
  	
  	while(current != null){
  		System.out.println(current.getData());
  		current = current.getNext();
  	}
  }
  
  /**
   *Find the equality of the LinkedList
   *@param LL, the list to be compared to
   *@return the equality value
   */
  public boolean equals(Object obj){
  	if(!(obj instanceof LinkedList)){
  		return false;
  	}
  	
  	LinkedList LL = (LinkedList)obj;
  	
  	LLNode thisCurrent = this.head;
  	LLNode temp = LL.head;
  	
  	if(this.size() != LL.size()){
  		return false;
  	}
  	while(thisCurrent != null){
  		if(!(thisCurrent.getData().equals(temp.getData()))){
  			return false;
  		}
  		thisCurrent = thisCurrent.getNext();
  		temp = temp.getNext();
  	}
  	
    return true;
  }
  
  /**
   * Change standard string to output to be used for this specific program
   * @return phrase as string
   */
  public String toString(){
  	String ReallyLong;
  	ReallyLong = "[ ";
  	LLNode current = head;
  	while(current != null){
  		ReallyLong += current.getData().toString();
  		if(current.getNext() != null){
  			ReallyLong += ", ";
  		}
  		current = current.getNext();
  	}
  	ReallyLong += "]";
  	
  	return ReallyLong;
  }
  
  /**
   *Check if there is an object in the list matching o
   *@return true if such an object exists
   */
  public boolean contains(Object o){
  	LLNode current = head;
  	while(current != null){
  		if(current.getData().equals(o)){
  			return true;
  		}
  		current = current.getNext();
  	}
  	return false;
  }
  
  /**
   *Method meant for debugging
   *clears the list
   */
  public void clear(){
  	head = null;
  	tail = null;
  }
  
  /*********************************************************/
  
  /**
   *  Debugging main for class LinkedList.  
   *  This method will rigorously test my code.
   *
   *  <br><br>
   *  @param args a String array of command line arguments.
   */
  public static void main(String[] args) {
    LinkedList LL = new LinkedList();
    Object[] array;
    LinkedList LL2 = new LinkedList();
    
    System.out.println("test 1");
    LL.addToFront("2");
    LL.addToFront("1");
    LL.addToBack("3");
    LL.addToBack("4");
    LL.listOut();
    array = LL.asArray();
    
    for(int i=0; i<array.length; i++){
    	System.out.println(array[i]);
    }
    
    System.out.println("test 2");
    LL.removeFromFront();
    LL.removeFromBack();
    LL.removeFromBack();
    
    array = LL.asArray();
    
    for(int i=0; i<array.length; i++){
    	System.out.println(array[i]);
    }
    
    System.out.println(LL.equals(LL2));
    
    LL.clear();
    LL.addToFront("1");
    LL.addToFront("2");
    LL.addToBack("3");
    LL2.addToFront("1");
    LL2.addToFront("2");
    LL2.addToBack("3");
    
    System.out.println(LL2.equals(LL));
    
    LL.clear();
    LL2.clear();
    
    LL.addToBack("2");
    
    LL.addToFront(new Integer(1));
    LL2.addToBack("2");
    
    System.out.println(LL.equals(LL2));
    
    LL2.addToFront(new Integer(1));
    
    System.out.println(LL2.equals(LL));
    
    LL2.removeFromBack();
    
    System.out.println(LL2.equals(LL));
    System.out.println(LL.equals(LL));
    LL.clear();
    System.out.println(LL.equals(LL2));
    
    //test what autograder finds as wrong
    //431, 653, 95, 201, 331, 326, 627, 38, 284, 350, 960, 36 
    LL.clear();
    LL2.clear();
    
    LL.addToBack(new Integer(36));
    LL.addToFront(new Integer(960));
    LL.addToFront(new Integer(350));
    LL.addToFront(new Integer(284));
    LL.addToFront(new Integer(38));
    LL.addToFront(new Integer(627));
    LL.addToFront(new Integer(326));
    LL.addToFront(new Integer(331));
    LL.addToFront(new Integer(201));
    LL.addToFront(new Integer(95));
    LL.addToFront(new Integer(653));
    LL.addToFront(new Integer(431));
    
    System.out.println(LL.equals(LL));
    System.out.println(LL.equals(LL2));
    LL2 = LL;
    System.out.println(LL.equals(LL2));
    
    //Holy crap this is a long debug main!
    LL2.clear();
    
    LL2.addToFront(new Integer(960));
    LL2.addToFront(new Integer(350));
    LL2.addToFront(new Integer(284));
    LL2.addToFront(new Integer(38));
    LL2.addToFront(new Integer(627));
    LL2.addToFront(new Integer(326));
    LL2.addToFront(new Integer(331));
    LL2.addToFront(new Integer(201));
    LL2.addToFront(new Integer(95));
    LL2.addToFront(new Integer(653));
    LL2.addToFront(new Integer(431));
    
    System.out.println(LL.equals(LL2));
    
    
    
    
    
  }// end of main(String[] args)

}// end of class LinkedList