package SOLUTION.hw7;

public class SinglyLinkedList<T> {
	//INNER CLASS: put here, only the SinglyLinkedList class can
	// instantiate an SListNode object.
	class SListNode<T> {
		//FIELDS -------------------------------------------- 
		T contents;       //payload
		SListNode<T> next;   //reference to next node
		
		//METHODS -------------------------------------------
		public void setData(T val) {
			this.contents = val;
		}
		public void setNext(SListNode<T> n) {
			this.next = n;
		}
		public T getData() {
			return this.contents;
		}
	}//class SListNode

	
	//FIELDS ---------------------------------------------
	SListNode<T> head;
	SListNode<T> tail;  //points to last node in list

	//CONSTRUCTORS ---------------------------------------
	public SinglyLinkedList() {
		this.head = null;
	}

	//METHODS: SinglyLinkedList ---------------------------

	//return value stored in first node
	public T getFirst() {
		if (this.head == null) {
			//this runtime exception indicates that the method
			// "has been invoked at an illegal or inappropriate time"
			throw new java.lang.IllegalStateException("List is empty.");
		}
		else {
			return this.head.contents;
		}
	}
	
	//insert a new node at the front of the list
	public void insertFirst(T val) {
		//create and initialize a new node
		SListNode<T> node = new SListNode<T>();
		node.setData(val);
		node.setNext(this.head);

		//if list was empty, this node is also at the back of the list
		if (this.head == null) {
			this.tail = node;
		}

		//place the node at the front of the list
		this.head = node;
	}

	//insert a new node at the end of the list
	public void insertLast(T val) {
		//create and initialize a new node
		SListNode<T> node = new SListNode<T>();
		node.setData(val);
		node.setNext(null);

		//if list was empty, node is also at front of the list
		if (this.head == null) {
			this.head = node;
			this.tail = node;
		}
		//otherwise, only set tail
		else {
			this.tail.next = node;
			this.tail = node;
		}
	}
	
	//remove the node at the front of the list
	public void removeFirst() {
		if (this.head == null) {
			//this runtime exception indicates that the method
			// "has been invoked at an illegal or inappropriate time"
			throw new java.lang.IllegalStateException("List is empty.");
		}
		else {
			//remove node by re-directing 'head' to the subsequent node
			this.head = this.head.next;
			
			//check whether list is now empty
			if (this.head == null) {
				this.tail = null;
			}
		}
	}

	//remove the last node in the list
	public void removeLast() {
		if (this.head == null) {
			//this runtime exception indicates that the method
			// "has been invoked at an illegal or inappropriate time"
			throw new java.lang.IllegalStateException("List is empty.");
		}

		//special case: single-element list
		if (this.head == this.tail) {
			this.head = null;
			this.tail = null;
		}

		else {
			//must find the penultimate node
			SListNode<T> current = this.head;
			while (current.next != this.tail) {
				current = current.next;
			}
			
			//remove node by setting penultimate's next to null
			current.next = null;
			this.tail = current;
		}
	}
	
	//print the contents of the list, from front to back
	public String toString() {
		String result = "";
		SListNode<T> current = this.head;
		while (current != null) {
			result = result + current.getData() + '\n';
			current = current.next;
		}
		return result;
	}

	public boolean isEmpty() {
		return (this.head == null);
	}
	
	//count the nodes in the list
	public int countNodes() {
		int count = 0;
		SListNode<T> current = head;
		while (current != null) {
			count++;
			current = current.next;
		}
		return count;
	}
	
	//count the nodes in the list
	public boolean contains(T elem) {
		SListNode<T> current = head;
		while (current != null) {
			if (current.getData().equals(elem))
				return true;
			current = current.next;
		}
		return false;
	}
	
}//class SinglyLinkedList