import java.util.function.Consumer;

/**
 * A simple circular, doubly-linked generic list
 * 
 * @author Professor William Killian
 *
 * @param <E> Underlying type to store
 */
public class LinkedList<E> {

	// Class invariant:
	//
	// 1). head will never store any data
	// 2). head.next refers to the front of the linked list (or itself if empty)
	// 3). head.prev refers to the back of the linked list (or itself if empty)
	// 4). size is the number of elements currently stored in the linked list
	// 5). For any node N in our linked list: N.next.prev == N
	// 6). For any node N in our linked list: N.prev.next == N

	/**
	 * The dummy "header" of the linked list
	 */
	private Node<E> head;

	/**
	 * the number of elements stored within the linked list
	 */
	private int size;

	/**
	 * creates an empty linked list
	 */
	public LinkedList() {
		head = Node.createCircularNode();
		this.size = 0;
	}
	
	public LinkedList(LinkedList<E> other) {
		this();
		addAll(head, other);
	}

	/**
	 * Accessor for number of elements in the linked list
	 * 
	 * @return The number of elements currently contained in the linked list
	 */
	public int size() {
		return size;
	}

	/**
	 * @return true if the linked list is empty (size == 0), false otherwise
	 */
	public boolean isEmpty() {
		return size() == 0;
	}

	/**
	 * Adds an element to the beginning of the linked list
	 * 
	 * @param val value to add
	 */
	public void insertFront(E val) {
		insert(head.next, val);
	}

	/**
	 * Adds an element to the end of the linked list
	 * 
	 * @param val value to add
	 */
	public void insertBack(E val) {
		insert(head, val);
	}

	/**
	 * Adds an element immediately before the specified index
	 * 
	 * @param index zero-based index of where to insert
	 * @param val   value to add
	 */
	public void insertBefore(int index, E e) {
		Node<E> node = getNode(index);
		insert(node, e);
	}

	/**
	 * Adds an element immediately after the specified index
	 * 
	 * @param index zero-based index of where to insert
	 * @param val   value to add
	 */
	public void insertAfter(int index, E e) {
		Node<E> node = getNode(index);
		insert(node.next, e);
	}

	/**
	 * removes the first element of the linked list
	 * 
	 * @return the value of the element removed
	 */
	public E removeFront() {
		return remove(head.next);
	}

	/**
	 * removes the last element of the linked list
	 * 
	 * @return the value of the element removed
	 */
	public E removeBack() {
		return remove(head.prev);
	}

	/**
	 * removes the specified zero-based element of the linked list
	 * 
	 * @param index zero-based index of the element to remove
	 * @return the value of the element removed
	 */
	public E removeAt(int index) {
		Node<E> node = getNode(index);
		return remove(node);
	}

	/**
	 * Adds all elements of a linked list to the end of our list
	 * 
	 * @param list another linked list;
	 */
	public void addAll(LinkedList<E> list) {
		addAll(head, list);
	}

	/**
	 * Adds all elements of a linked list at the specified index
	 * 
	 * @param index zero-based index of where to insert before
	 * @param list  another linked list;
	 */
	public void addAll(int index, LinkedList<E> list) {
		Node<E> node = getNode(index);
		addAll(node, list);
	}

	/**
	 * Clears a linked list
	 */
	public void clear() {
		head.next = head;
		head.prev = head;
		size = 0;
	}

	/**
	 * Gets the element at a specified zero-based index
	 * 
	 * @param index zero-based index of the list to retrieve
	 * @return the data stored at index
	 */
	public E get(int index) {
		Node<E> node = getNode(index);
		return node.data;
	}

	/**
	 * updates the value at a specified zero-based index
	 * 
	 * @param index   zero-based index of the list to update
	 * @param element the new value
	 * @return the old value stored at index
	 */
	public E set(int index, E element) {
		Node<E> node = getNode(index);
		E oldValue = node.data;
		node.data = element;
		return oldValue;
	}

	/**
	 * returns the zero-based index of where the value passed value was first found
	 * in the list
	 * 
	 * @param o object to find
	 * @return the zero-based index of the list or -1 if not found
	 */
	public int indexOf(Object o) {
		Node<E> curr = head.next;
		int index = 0;
		while (curr != head) {
			if (curr.data.equals(o)) {
				return index;
			}
			++index;
			curr = curr.next;
		}
		return -1;
	}

	/**
	 * returns the zero-based index of where the value passed value was last found
	 * in the list
	 * 
	 * @param o object to find
	 * @return the zero-based index of the list or -1 if not found
	 */
	public int lastIndexOf(Object o) {
		Node<E> last = head.prev;
		int index = size - 1;
		while (last != head) {
			if (last.data.equals(o)) {
				return index;
			}
			--index;
			last = last.prev;
		}
		return -1;
	}

	/**
	 * Inserts a new node with value BEFORE the passed node
	 * 
	 * @param n node to insert before
	 * @param e value to insert
	 */
	private Node<E> insert(Node<E> next, E e) {
		Node<E> prev = next.prev;
		Node<E> node = new Node<E>(e, prev, next);
		prev.next = node;
		next.prev = node;
		++size;
		return node;
	}

	/**
	 * Removes the passed node from the linked list
	 * 
	 * @param node the node to remove
	 */
	private E remove(Node<E> node) {
		if (isEmpty())
			throw new IllegalStateException("Cannot remove from an empty list");
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		prev.next = next;
		next.prev = prev;
		--size;
		return node.data;
	}

	/**
	 * insert all elements of linked list BEFORE passed node
	 * 
	 * @param node location to insert all items of c *before*
	 * @param c    linked list
	 */
	private void addAll(Node<E> node, LinkedList<E> list) {
		list.forEach((E val) -> {
			insert(node, val);
		});
	}

	/**
	 * Returns the node at the specified index
	 * 
	 * @param index zero-based index of the node
	 * @return
	 */
	private Node<E> getNode(int index) throws IllegalArgumentException {
		if (index > size()) {
			throw new IllegalArgumentException("Index is out of bounds");
		}
		if (index == size()) {
			return head;
		}
		Node<E> curr = head;
		while (index >= 0) {
			curr = curr.next;
			--index;
		}
		return curr;
	}

	/**
	 * Apply a function to each element of the linked list
	 * 
	 * @param f consumer (lambda/function) to invoke for each element in the linked
	 *          list
	 */
	public void forEach(Consumer<E> f) {
		for (Node<E> n = head.next; n != head; n = n.next) {
			f.accept(n.data);
		}
	}

	/**
	 * A string representation of the linked list
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder("[ ");
		forEach((E val) -> {
			sb.append(val);
			sb.append(' ');
		});
		return sb.append(']').toString();
	}

	/**
	 * A double-linked node class
	 * 
	 * @author Professor William Killian
	 *
	 * @param <T> The underlying storage type
	 */
	private static class Node<T> {

		// Class Invariant:
		//
		// 1). data refers to the data stored within the node
		// 2). prev refers to the node which comes before our node
		// 3). next refers to the node which comes before our node

		public T data;
		public Node<T> prev;
		public Node<T> next;

		private Node() {
			this(null, null, null);
		}

		/**
		 * Creates a new node given data, prev pointer, and next pointer
		 * 
		 * @param data underlying data to store
		 * @param prev node which precedes this node
		 * @param next node which follows this node
		 */
		public Node(T data, Node<T> prev, Node<T> next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}

		/**
		 * Creates a dummy node N which has N.prev == N.next == N
		 * 
		 * @return a new node
		 */
		public static <U> Node<U> createCircularNode() {
			Node<U> node = new Node<U>();
			node.prev = node;
			node.next = node;
			return node;
		}
	}
}