package lists;

import java.io.Serializable;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Queue;
import java.util.NoSuchElementException;

public class LinkedList<E> implements Serializable, Cloneable, Iterable<E>{
	
	private static final long serialVersionUID = 1L;

	/* Class to represent a node of the List */
	protected final class Node    { 
		E    data;   
		Node next;    
		Node prev; 
		
		Node(E data) {
			this.data = data;
			next = prev = null;
		}
		
		Node(E data, Node prev, Node next) {
			this(data);
			this.prev = prev;
			this.next = next;
		}
	} 
	
	/* Start of the List */
	protected Node head; 
	
	/* End of the List */
	protected int  size;   
	
	/* Constructor to make an empty List */
	public LinkedList() { 
		head = null; 
		size = 0;  
	} 
	
	/*
	 * Checks validity of index
	 */
	private void checkIndex(int index) {
		if(index <0 || index > size)
			throw new IndexOutOfBoundsException("Index " + index + " out of [0," + size + "]");
	}
	
	/*
	 * Returns a reference to the node with given index
	 */
	private Node getNode(int index) {
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
		Node tmp;
		if(index < size/2) {
			tmp = head;
			while(index-- > 0)
				tmp = tmp.next;
		}
		else {
			tmp = head.prev;
			while(++index < size)
				tmp = tmp.prev;
		}
		return tmp;
	}
	
	/*
	 * Removes specified node 
	 */
	private void removeNode(Node node) {
		if(node == null)
			throw new NullPointerException();
		if(size == 1) {
			head = null;
			size = 0;
		}
		else if(size > 1) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
			if(node == head)
				head = head.next;
			node.next = node.prev = null;
			size--;
		}	
	}
	

	/*
	 * Appends the specified element to the end of this list. 
	 * This method is equivalent to addLast(e). Returns true (as specified by Collection.add(e))
	 */
	public boolean add(E e) {
		addLast(e);
		return true;
	}
	
	/*
	 * Inserts the specified element at the specified position in this list. 
	 * Shifts the element currently at that position (if any) and any subsequent elements 
	 * to the right (adds one to their indices). 
	 * Throws IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())
	 */
	public void add(int index, E e) {
		checkIndex(index);
		if(index == 0)
			addFirst(e);
		else if(index == size)
			addLast(e);
		else {
			Node tmpNext = getNode(index);
			Node tmp = new Node(e, tmpNext.prev, tmpNext);
			tmpNext.prev = tmpNext.prev.next = tmp;
			size++;
		}	
	}
		
	/*
	 * Inserts the specified element at the beginning of this list. 
	 */
	public void addFirst(E e) {
		if (size == 0){
			head = new Node(e);
			head.prev = head.next = head;
		}
		else {
			head.prev = head.prev.next = new Node(e);
			head = head.prev;
		}
		size++;
	}

	/*
	 * Appends the specified element to the end of this list. 
	 * This method is equivalent to add(E). 
	 */
	public void addLast(E e) {
		if (size == 0){
			head = new Node(e);
			head.prev = head.next = head;
		}
		else 
			head.prev = head.prev.next = new Node(e);
		size++;
	}
	
	/*
	 * Returns a list-iterator of the elements in this list (in proper sequence), 
	 * starting at the beginning of the list. 
	 */
	public ListIterator<E> listIterator() {
		return new ListIteratorImpl(0);
	}
	
	/*
	 * Returns a list-iterator of the elements in this list (in proper sequence), 
	 * starting at the specified position in the list. Obeys the general contract of 
	 * List.listIterator(int). 
	 * Throws IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())
	 */
	public ListIterator<E> listIterator(int index) {
		return new ListIteratorImpl(index);
	}
	
	/*
	 * Returns an iterator over the elements in this list. 
	 * The elements will be returned in order from first (head) to last (tail). 
	 */
	public Iterator<E> iterator() {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Returns an iterator over the elements in this list in reverse sequential order. 
	 * The elements will be returned in order from last (tail) to first (head). 
	 */
	public Iterator<E> descendingIterator() {
		throw new UnsupportedOperationException();
	}
	
	
	/* Class to implement interface ListIterator */
	private class ListIteratorImpl implements ListIterator<E> {
		private Node lastReturned = null; // node containing element last returned
		private Node next; // node after cursor
		private int nextIndex; // index of node after cursor
		
		/**
	     * Constructs an list iterator starting at index.
	     */
		ListIteratorImpl(int index) {
			checkIndex(index);
			if (index < (size >> 1)) {
				next = head;
				for (nextIndex = 0; nextIndex < index; nextIndex++)
					next = next.next;
			} 
			else {
				next = head;
				for (nextIndex = size; nextIndex > index; nextIndex--)
					next = next.prev;
			}
		}
		
		/**
	     * Returns true if this list iterator has more elements when
	     * traversing the list in the forward direction. 
	     */
		public boolean hasNext() {
			return nextIndex != size;
		}
		 
		/**
		 * Returns the next element in the list and advances the cursor position.
		 * This method may be called repeatedly to iterate through the list,
		 * or intermixed with calls to previous to go back and forth.
		 */
		public E next() {
			if (nextIndex == size)
				throw new NoSuchElementException();
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.data;
		}
		
		/**
		 * Returns true if this list iterator has more elements when
		 * traversing the list in the reverse direction. 
		 */
		public boolean hasPrevious() {
			return nextIndex != 0;
		}
		
		/**
		 * Returns the previous element in the list and moves the cursor
		 * position backwards.  This method may be called repeatedly to
		 * iterate through the list backwards, or intermixed with calls to
		 * next to go back and forth.  
		 */
		public E previous() {
			if (nextIndex == 0)
				throw new NoSuchElementException();
			lastReturned = next = next.prev;
			nextIndex--;
			return lastReturned.data;
		}
		
		/**
		 * Returns the index of the element that would be returned by a
		 * subsequent call to next. (Returns list size if the list
		 * iterator is at the end of the list.)       
		 */
		public int nextIndex() {
			return nextIndex;
		}
		
		/**
		 * Returns the index of the element that would be returned by a
		 * subsequent call to previous. (Returns -1 if the list
		 * iterator is at the beginning of the list.)
		 */
		public int previousIndex() {
			return nextIndex - 1;
		}
		 
		/**
		 * Removes from the list the last element that was returned by 
		 * next or previous (optional operation).  This call can
		 * only be made once per call to next or  previous.
		 */
		public void remove() {
			if(lastReturned == null)
				throw new IllegalStateException();
			Node lastNext = lastReturned.next;		
			LinkedList.this.removeNode(lastReturned);	
			if (next == lastReturned) // after previous
				next = lastNext;
			else  // after next
				nextIndex--;
			lastReturned = null;
		}
		
		/**
		 * Replaces the last element returned by next or
		 * previous with the specified element (optional operation).
		 * This call can be made only if neither remove nor
		 * add have been called after the last call to  next or previous.
		 */
		public void set(E e) {
			if (lastReturned == null)
				throw new IllegalStateException();
			lastReturned.data = e;
		}
   
		
		/**
		 * Inserts the specified element into the list (optional operation).
		 * The element is inserted immediately before the next element that
		 * would be returned by next, if any, and after the next
		 * element that would be returned by previous, if any.  (If the
		 * list contains no elements, the new element becomes the sole element
		 * cursor: a subsequent call to next would be unaffected, and a
		 * subsequent call to  previous would return the new element.
		 */
		public void add(E e) {
			lastReturned = null;
			LinkedList.this.add(nextIndex, e);
			nextIndex++;
	   }
	} // end of class ListIteratorImpl
	
}