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>, Collection<E>, Deque<E>, List<E>, Queue<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 all of the elements in the specified collection to the end of this list, 
	 * in the order that they are returned by the specified collection's iterator. 
	 * Returns true if this list changed as a result of the call. 
	 * Throws NullPointerException - if the specified collection is null
	 */
	public boolean addAll(Collection<? extends E> c) {
		throw new UnsupportedOperationException();
	}
		
	/*
	 * Inserts all of the elements in the specified collection into this list, 
	 * starting at the specified position. Returns true if this list 
	 * changed as a result of the call. Throws IndexOutOfBoundsException - if the index 
	 * is out of range (index < 0 || index > size()) NullPointerException - if the 
	 * specified collection is null
	 */
	public boolean addAll(int index, Collection<? extends E> c) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Returns true if this collection contains all of the elements in the specified collection. 
	 * Throws ClassCastException - if the types of one or more elements in the specified 
	 * collection are incompatible with this collection (optional). NullPointerException - 
	 * if the specified collection contains one or more null elements and this collection 
	 * does not permit null elements (optional), or if the specified collection is null
	 */
	public boolean containsAll(Collection<?> c){
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Removes all of this collection's elements that are also contained in the specified 
	 * collection (optional operation).
	 * Throws UnsupportedOperationException - if the removeAll method is not supported by this collection 
	 * ClassCastException - if the types of one or more elements in this collection are incompatible with the specified collection (optional) 
	 * NullPointerException - if this collection contains one or more null elements 
	 * and the specified collection does not support null elements (optional), 
	 * or if the specified collection is null
	 */
	public boolean removeAll(Collection<?> c){
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Retains only the elements in this collection that are contained in the specified collection 
	 * (optional operation). 
	 * Returns true if this collection changed as a result of the call. 
	 * Throws UnsupportedOperationException - if the retainAll operation is not supported by this collection 
	 * ClassCastException - if the types of one or more elements in this collection are incompatible 
	 * with the specified collection (optional) 
	 * NullPointerException - if this collection contains one or more null elements 
	 * and the specified collection does not permit null elements (optional), 
	 * or if the specified collection is null
	 */
	public boolean retainAll(Collection<?> c){
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Pushes an element onto the stack represented by this list. 
	 * In other words, inserts the element at the front of this list. 
	 * This method is equivalent to addFirst(E). 
	 */
	public void push(E e) {
		throw new UnsupportedOperationException();
	}

	/*
	 * Pops an element from the stack represented by this list. In other words, 
	 * removes and returns the first element of this list. This method is equivalent to removeFirst().
	 * Throws NoSuchElementException - if this list is empty
	 */
	public E pop() {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * 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 the element at the specified position in this list. 
	 * Returns the element at the specified position in this list. 
	 * Throws IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())
	 */
	public E get(int index) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Returns the first element in this list. Throws NoSuchElementException - 
	 * if this list is empty
	 */
	public E getFirst() {	
		if (size == 0)
			throw new NoSuchElementException();
		return head.data;
	}
	
	/*
	 * Returns the last element in this list. 
	 * Throws NoSuchElementException - if this list is empty
	 */
	public E getLast() {
		if (size == 0)
			throw new NoSuchElementException();
		return head.prev.data;
	}
	
	/*
	 * Retrieves, but does not remove, the head (first element) of this list. 
	 * Returns the head of this list, or null if this list is empty
	 */
	public E peek() {
		throw new UnsupportedOperationException();
	}

	/*
	 * Retrieves, but does not remove, the head (first element) of this list. 
	 * Returns the head of this list Throws NoSuchElementException - if this list is empty
	 */
	public E element() {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Retrieves, but does not remove, the first element of this list, or returns null 
	 * if this list is empty. Returns the first element of this list, 
	 * or null if this list is empty
	 */
	public E peekFirst() {
		throw new UnsupportedOperationException();
	}

	/*
	 * Retrieves, but does not remove, the last element of this list, or returns null 
	 * if this list is empty. Returns the last element of this list, or null if this list is empty
	 */
	public E peekLast() {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Retrieves and removes the head (first element) of this list. 
	 * Returns the head of this list, or null if this list is empty
	 */
	public E poll() {
		if (size == 0)
			return null;
		return removeFirst();

	}
	
	/*
	 * Retrieves and removes the first element of this list, or returns null if this list is empty. 
	 * Returns the first element of this list, or null if this list is empty
	 */
	public E pollFirst() {
		return poll();
	}
	
	/*
	 * Retrieves and removes the last element of this list, or returns null if this list is empty. 
	 * Returns the last element of this list, or null if this list is empty
	 */
	public E pollLast() {
		if (size == 0)
			return null;
		return removeLast();

	}
	
	/*
	 * Adds the specified element as the tail (last element) of this list. 
	 * Returns true (as specified by Queue.offer(E))
	 */
	public boolean offer(E e) {
		throw new UnsupportedOperationException();
	}

	/*
	 * Inserts the specified element at the front of this list. 
	 * Returns true (as specified by Deque.offerFirst(E))
	 */
	public boolean offerFirst(E e){
		throw new UnsupportedOperationException();
	}
	/*
	 * Inserts the specified element at the end of this list. 
	 * Returns the first element of this list, or null if this list is empty
	 */
	public boolean offerLast(E e) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Retrieves and removes the head (first element) of this list. 
	 * Returns the head of this list 
	 * Throws NoSuchElementException - if this list is empty
	 */
	public E remove() {
		return removeFirst();
	}
	
	/*
	 * Removes and returns the first element from this list. 
	 * Throws NoSuchElementException - if this list is empty
	 */
	public E removeFirst() {
		if (size == 0)
			throw new NoSuchElementException();
		E tmp = head.data;
		if(size == 1) 		
			head = null;
		else {
			head.next.prev = head.prev;
			head.prev.next = head.next;head = head.next;
		}
		size--;
		return tmp;
	}
	
	/*
	 * Removes and returns the last element from this list. 
	 * Returns the last element from this list. 
	 * Throws NoSuchElementException - if this list is empty
	 */
	public E removeLast()  {
		if (size == 0)
			throw new NoSuchElementException();
		E tmp;
		if(size == 1){ 	
			tmp = head.data; // head = tail
			head = null;
		}
		else {
			tmp = head.prev.data;
			head.prev.prev.next = head;
			head.prev = head.prev.prev;
		}
		size--;
		return tmp;	
	}
	
	/*
	 * Removes the element at the specified position in this list. 
	 * Shifts any subsequent elements to the left (subtracts one from their indices). 
	 * Returns the element that was removed from the list. 
	 * Returns the element previously at the specified position. 
	 * Throws IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())
	 */
	public E remove(int index) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Removes the first occurrence of the specified element in this list (
	 * when traversing the list from head to tail). If the list does not contain the element, 
	 * it is unchanged. Returns true if the list contained the specified element
	 */
	public boolean removeFirstOccurrence(Object o){
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Removes the last occurrence of the specified element in this list 
	 * (when traversing the list from head to tail). If the list does not contain the element, 
	 * it is unchanged. Returns true if the list contained the specified element		
	 */
	public boolean removeLastOccurrence(Object o) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Returns the index of the first occurrence of the specified element in this list, 
	 * or -1 if this list does not contain the element.
	 */
	public int indexOf(Object o) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Returns the index of the last occurrence of the specified element in this list, 
	 * or -1 if this list does not contain the element. 
	 */
	public int lastIndexOf(Object o) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Replaces the element at the specified position in this list with the specified element. 
	 * Returns the element previously at the specified position. 
	 * Throws IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())
	 */
	public E set(int index, E element) {
		throw new UnsupportedOperationException();
	} 
		
	/*
	 * Returns true if this list contains the specified element. 
	 * More formally, returns true if and only if this list contains at least one element e 
	 * such that (o==null ? e==null : o.equals(e)). 
	 */
	public boolean contains(Object o) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Removes the first occurrence of the specified element from this list, 
	 * if it is present. If this list does not contain the element, it is unchanged. 
	 */
	public boolean remove(Object o) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 *  Returns a view of the portion of this list between the specified fromIndex, 
	 *  inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, 
	 *  the returned list is empty.) The returned list is backed by this list, 
	 *  so non-structural changes in the returned list are reflected in this list, and vice-versa. 
	 *  The returned list supports all of the optional list operations supported by this list. 
	 *  Throws IndexOutOfBoundsException - for an illegal endpoint index value 
	 *  (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
	 */
	public List<E> subList(int fromIndex, int toIndex){
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Removes all items from this list.
	 */
	public void removeAll() {
		throw new UnsupportedOperationException();
	}
		
	/*
	 * Returns true if this collection contains no elements.
	 */
	public boolean isEmpty() {
		return size == 0;
	}
            	
	/*
	 * Removes all of the elements from this list.
	 */
	public void clear() {
		throw new UnsupportedOperationException();
	} 
	
	/*
	 * Returns the number of elements in this list.
	 */
	public int size() {
		return 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();
	}
	
	/*
	 * Returns a shallow copy of this LinkedList. (The elements themselves are not cloned.) 
	 */
	public Object clone() {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Indicates whether some other object is "equal to" this one. 
	 * The equals method implements an equivalence relation on non-null object references. 
	 * Returns true if this object is the same as the obj argument; false otherwise.
	 */
	public boolean equals(Object obj) {
		throw new UnsupportedOperationException();
	}
	
	/*
	 *  Returns a string representation of the object.
	 */
	public String toString() {
		throw new UnsupportedOperationException();
	}
	
	/*
	 * Returns an array containing all of the elements in this list in proper sequence 
	 * (from first to last element). 
	 * The returned array will be "safe" in that no references to it are maintained by this list. 
	 * (In other words, this method must allocate a new array). The caller is thus free 
	 * to modify the returned array. 
	*/
	public Object[] toArray() {
		throw new UnsupportedOperationException();
	}
		
	/*
	 * Returns an array containing all of the elements in this list in proper sequence 
	 * (from first to last element); the runtime type of the returned array is that of the 
	 * specified array. If the list fits in the specified array, it is returned therein. 
	 * Otherwise, a new array is allocated with the runtime type of the specified array and the size 
	 * of this list. 
	 * ArrayStoreException - if the runtime type of the specified array is not a supertype of the 
	 * runtime type of every element in this list. 
	 * NullPointerException - if the specified array is null
	 */
	public <T> T[] toArray(T[] a) {
		throw new UnsupportedOperationException();
	}
	
	//private class ListIteratorImpl implements ListIterator<E> {
	// . . . . . 
	//}
}