package utilities;
/**
 * <P>Skeletal implementation of a singly linked list that takes generic types.
 * Note: a singly linked list is either empty or is a singly linked list that
 * contains at least one Node. These are essentially the methods that we discussed and
 * partially implemented in class last Thursday. These are presented for educational
 * purposes only. Clearly, your Project requires 
 * <ul>
 *  <li>That your List class support a two-node, <code>head</code> and <code>tail</code> 
 *  implementation;</li>
 *  <li>That the methods implemented on your List class be <strong>iterative</strong>, whereas
 *  these are recursive. And,</li>
 *  <li>That your list implementation include <strong>both</strong> an unordered as well as
 *  an ordered list.
 * </ul></P>
 * <br>
 * <P>Note: every method here is recursively implemented; you are expected to implement your
 * own <strong> iterative</strong> versions of these. (Although, you can probably skip the <code>clone</code> method.)</P>
 * @author tomreinhardt
 *
 * @param <T>
 */
public class SinglyLinkedList<T> implements Cloneable {
	
	private class Node { 
		T	value;
		Node next=null;
		
		Node( T value ) { this.value = value; }
		Node( T value, Node next ) {
			this( value);
			this.next=next;
		}
	}
	
	/* instance variables belonging to list. */
	private Node	my_list=null;
	
	/* One ctor, for sure ... */
	public SinglyLinkedList () { } // everything is done.
	

	/* overrides */
	/** Provides a "Python-style" String.*/
	public String toString() {
		return "[" + toString_aux( this.my_list) + "]";
	}

	private String toString_aux(Node myList) {
		if( myList == null ) return "";
		else return myList.value.toString() + ", "
			+ toString_aux( myList.next );
	}
	
	
	@SuppressWarnings("unchecked")
	/** <P>Actually, Java's <code>clone()</code> design is broken at some level.
	 * I'm thinking that you should just implement a copy constructor rather than
	 * ever doing this kind of thing ....</P>
	 */
	public SinglyLinkedList<T> clone() {
		SinglyLinkedList<T> myList=null;
		try {
			myList = (SinglyLinkedList<T>) super.clone();
			myList.my_list = clone_aux( my_list );
		}catch( CloneNotSupportedException what ) {
			System.err.print("Impossible situation happened when cloning list." );
			throw new AssertionError("Apparently SinglyLinkedLists are not clonable?");
		}
		return myList;
	}
	private Node  clone_aux( Node lst ) {
		if( lst == null ) return lst;
		else return new Node( lst.value, clone_aux( lst.next ) );
	}
	
	/* Public Interface */
	public void add( T ele ) {
		this.my_list = add_aux( ele, this.my_list);
	}

	private Node add_aux(T ele, Node myList) {
		if( myList == null ) return new Node( ele );
		else return new Node( myList.value,
				add_aux( ele, myList.next ) );
	}
	
	public int length() {
		return length_aux( this.my_list);
	}

	private int length_aux(Node theList ) {
		if( theList == null  ) return 0;
		else return 1 + (length_aux( theList.next ) );
	}
	
	public boolean contains( T ele ) {
		return contains_aux( ele, this.my_list );
	}

	private boolean contains_aux(T ele, Node theList ) {
		if( theList == null ) return false;
		else if( ele.equals( theList.value ))
			return true;
		else return contains_aux( ele, theList.next );
	}
	
	public void remove( T ele ) {
		this.my_list = this.remove_aux( ele, this.my_list );
	}

	private Node remove_aux(T ele, Node lst ) {
		if( lst == null ) return lst;
		else if( lst.value.equals( ele ) ) 
			return remove_aux( ele, lst.next );
		else return new Node( lst.value, 
				remove_aux( ele, lst.next ) );
	}

}