package test;

import java.util.*;

public class DoublyLinkedList {

	
	class Node<E> {
		
		//Node Data
		private E value;
		private Node<E> prev;
		private Node<E> next;
		
		//Node constructor
		Node(E value) {
			this.value = value;
		}

		Node(E value, Node<E> prev, Node<E> next) {
			this.value = value;
			setPrev(prev);
			setNext(next);
		}
		
		//Node Setter
		void setPrev(Node<E> prev) {
			this.prev = prev;
		}

		void setNext(Node<E> next) {
			this.next = next;
		}
		
		//Node Getter
		Node<E> getPrev() {
			return prev;
		}

		Node<E> getNext() {
			return next;
		}

		E getValue() {
			return value;
		}
		
		
		//<<List_data>>=
		private Node<E> head = new Node<E>(null);
		private Node<E> tail = new Node<E>(null);
		private int length = 0;
				
		//<<List_construct>>=
		{
			head.setPrev(null);
			head.setNext(tail);
			tail.setPrev(head);
			tail.setNext(null);
		}
		
		// <<List_get>>=
		public Node<E> get(int index) throws IndexOutOfBoundsException {
				if (index < 0 || index > length) {
					throw new IndexOutOfBoundsException();
				} else {
					Node<E> cursor = head;
					for (int i = 0; i < index; i++) {
						cursor = cursor.getNext();
					}
					return cursor;
				}
		}				
					
					
		
		//<<List_remove>>=
				public E remove(int index) throws IndexOutOfBoundsException {
					if (index == 0) {
						throw new IndexOutOfBoundsException();
					} else {
						Node<E> result = get(index);
						result.getNext().setPrev(result.getPrev());
						result.getPrev().setNext(result.getNext());
						length--;
						return result.getValue();
					}
				}
		
		
		
				//<<List_add>>=
						public void add(int index, E value) throws IndexOutOfBoundsException {
							Node<E> cursor = get(index);
							Node<E> temp = new Node<E>(value);
							temp.setPrev(cursor);
							temp.setNext(cursor.getNext());
							cursor.getNext().setPrev(temp);
							cursor.setNext(temp);
							length++;
						}

						public void addHead(E value) {
							Node<E> cursor = head;
							Node<E> temp = new Node<E>(value);
							temp.setPrev(cursor);
							temp.setNext(cursor.getNext());
							cursor.getNext().setPrev(temp);
							cursor.setNext(temp);
							length++;
						}

						public void addTail(E value) {
							Node<E> cursor = tail.getPrev();
							Node<E> temp = new Node<E>(value);
							temp.setPrev(cursor);
							temp.setNext(cursor.getNext());
							cursor.getNext().setPrev(temp);
							cursor.setNext(temp);
							length++;
						}
		
				//<<List_utils>>=
						public int size() {
							return length;
						}
									
						public boolean isEmpty() {
								return length == 0;
						}
									
						public String toString() {
							StringBuffer result = new StringBuffer();
							result.append("(head) - ");
							Node<E> temp = head;
							while (temp.getNext() != tail) {
								temp = temp.getNext();
								result.append(temp.getValue() + " - ");
							}
									result.append("(tail)");
									return result.toString();
							}
	}
	
	//<<List_test>>=
			public static void main(String argv[]) {
				DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();  //Error here-> the type DoublyLinkedList is not generic it cannot be parameterized with arguments
				list.addHead(new Integer(1));
				list.addHead(new Integer(2));
				list.addTail(new Integer(9));
				list.addHead(new Integer(3));
				list.addTail(new Integer(11));
				list.add(2, new Integer(0));
				System.out.println(list);
				list.remove(list.size());
				System.out.println(list);
			}

}