package eg.edu.alexu.csd.datastructure.linkedList.cs61;

import eg.edu.alexu.csd.datastructure.linkedList.ILinkedList;
// TODO: Auto-generated Javadoc

/**
 * The Class DoublyLinkedList.
 */
public class DoublyLinkedList implements ILinkedList {

	/** The len. */
	private int len = 0;

	/** The head. */
	private Node head = new Node(null, null, null);

	/**
	 * The Class Node.
	 */
	private class Node {

		/** The data. */
		private Object data;

		/** The next. */
		private Node next;

		/** The prev. */
		private Node prev;

		/**
		 * Instantiates a new node.
		 *
		 * @param data
		 *            the data
		 * @param next
		 *            the next
		 * @param prev
		 *            the prev
		 */
		public Node(Object data, Node next, Node prev) {
			this.data = data;
			this.next = next;
			this.prev = prev;
		}
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#add(int,
	 * java.lang.Object)
	 */
	public void add(int index, Object element) {
		if (index > len + 1 || index < 0) {
			throw new RuntimeException("add function");
		}
		else {

			Node link = new Node(null, head, null);
			int counter = 0;
			if (index != 0 && head.next == null) {
				throw new RuntimeException("add function");
			}
			if (index == 0 && head.next == null) {
				head.next = link;
				link.data = element;
				link.next = null;
				link.prev = head;
				len++;
			} else {
				while (counter <= index) {
					counter++;
					link = link.next;
				}
				if (counter > index && head.next != null) {
					Node temp = new Node(element, link.next, link);
					link.next = temp;
					len++;
				}

			}
		}

	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#add(java.lang.
	 * Object)
	 */
	public void add(Object element) {
		int length = size(); // It's the length of the list
		int index = 0; // It's the counter to reach the tail
		Node link = new Node(null, head, null);
		while (index <= length) {
			link = link.next;
			index++;
		}
		Node temp = new Node(element, null, link);
		link.next = temp;
		len++;
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#get(int)
	 */
	public Object get(int index) {
		if (len == 0 || index < 0 || index > len) { // It checks if the list is
													// empty
			throw new RuntimeException("get function"); // or the index is
		}                                            		// greater than the size
		else {                                           // or the index is negative

			Object getter;
			int counter = -1;
			Node link = new Node(null, head, null);
			while (counter < index) { // There's no need to check if the next is
										// null
				(link.next).prev = link;
				link = link.next; // because it's checked at first that the
									// index is less
				counter++; // than the length
			}
			getter = (link.next).data;
			return getter;
		}
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#set(int,
	 * java.lang.Object)
	 */
	public void set(int index, Object element) {
		if (head.next == null || index < 0 || index >= len) {
			throw new RuntimeException("set function");
		}
		else {
			int counter = -1; // It's initializes with -1 because the index
			Node link = new Node(null, head, null); // is initialized with 0
			while (counter < index) { // With that loop all it does is reaching
										// the required
				counter++; // index
				(link.next).prev = link;
				link = link.next;
			}
			(link.next).data = element;
		}
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#clear()
	 */
	public void clear() {
		len = 0;
		head.next = null;
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#isEmpty()
	 */
	public boolean isEmpty() {

		return size() == 0;
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#remove(int)
	 */
	public void remove(int index) {
		if (head.next == null || index < 0 || index >= len) {
			throw new RuntimeException("remove function");
		}

		else {
			Node link = new Node(null, head, null);
			int counter = 0;
			while (counter <= index) {
				// (link.next).prev = link ;
				link = link.next;
				counter++;
			}

			link.next = (link.next) != null ? (link.next).next : link.next;
			if (link.next != null) {
				(link.next).prev = link;
			}
			len--;
		}
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#size()
	 */
	public int size() {

		return len;
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#sublist(int,
	 * int)
	 */
	public ILinkedList sublist(int fromIndex, int toIndex) {

		if (len == 0 || fromIndex < 0 || fromIndex > len || toIndex < 0 || toIndex > len || fromIndex > toIndex) {
			throw new RuntimeException("sublist error");
		}
		else {
			SinglyLinkedList sub = new SinglyLinkedList();
			int counter = fromIndex;
			while (counter <= toIndex) {
				sub.add(counter - fromIndex, get(counter));
				counter++;
			}
			return sub;
		}
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see
	 * eg.edu.alexu.csd.datastructure.linkedList.ILinkedList#contains(java.lang.
	 * Object)
	 */
	public boolean contains(Object o) {

		if (len == 0) { // The list is empty
			return false;
		}
		else {
			Node link = new Node(null, head.next, null);
			while (link.next != null) { // Checking till the end of the list
				if ((link.next).data.equals(o)) { // or catching the element
												// whichever comes first
					return true;
				}
				(link.next).prev = link;
				link = link.next;
			}
			return false;

		}
	}

}