package algs13;
import stdlib.*;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
 *  Compilation:  javac LinkedList.java
 *  Execution:    java LinkedList
 *
 *  A list implemented with a doubly linked list. The elements are stored
 *  (and iterated over) in the same order that they are inserted.
 *
 *  % java List
 *  This
 *  is
 *  a
 *  test.
 *
 *  This
 *  is
 *  a
 *  test.
 *
 *************************************************************************/

public class LinkedList<T> implements Iterable<T> {
	private int N;                 // number of elements on list
	private final Node<T> pre;     // sentinel before first item
	private final Node<T> post;    // sentinel after last item
	private long opcount;

	public LinkedList() {
		pre  = new Node<>();
		post = new Node<>();
		pre.next = post;
		post.prev = pre;
	}

	// linked list node helper data type
	private static class Node<T> {
		public Node() { }
		public T item;
		public Node<T> next;
		public Node<T> prev;
	}

	public boolean isEmpty()    { return N == 0; }
	public int size()           { return N;      }

	// add the item to the end of the list
	public void add(T item) {
		Node<T> last = post.prev;
		Node<T> x = new Node<>();
		x.item = item;
		x.next = post;
		x.prev = last;
		post.prev = x;
		last.next = x;
		N++;
		opcount++;
	}

	public ListIterator<T> iterator()  { return new LinkedListIterator(); }

	// assumes no calls to add() during iteration
	private class LinkedListIterator implements ListIterator<T> {
		private Node<T> current      = pre.next;  // the node that is returned by next()
		private Node<T> lastAccessed = null;      // the last node to be returned by prev() or next()
		// reset to null upon intervening remove() or add()
		private int index = 0;
		private long oc = opcount;
		private void ocCheck() { if (opcount != oc) throw new ConcurrentModificationException (); }
		private void ocInc()   { ocCheck(); opcount++; oc++; }

		public boolean hasNext()      { ocCheck(); return index < N; }
		public boolean hasPrevious()  { ocCheck(); return index > 0; }
		public int previousIndex()    { ocCheck(); return index - 1; }
		public int nextIndex()        { ocCheck(); return index;     }

		public T next() {
			ocCheck();
			if (!hasNext()) throw new NoSuchElementException();
			lastAccessed = current;
			T item = current.item;
			current = current.next;
			index++;
			return item;
		}

		public T previous() {
			ocCheck();
			if (!hasPrevious()) throw new NoSuchElementException();
			current = current.prev;
			lastAccessed = current;
			T item = current.item;
			index--;
			return item;
		}

		// replace the item of the element that was last accessed by next() or previous()
		// condition: no calls to remove() or add() after last call to next() or previous()
		public void set(T item) {
			ocInc();
			if (lastAccessed == null) throw new Error();
			lastAccessed.item = item;
		}

		// remove the element that was last accessed by next() or previous()
		// condition: no calls to remove() or add() after last call to next() or previous()
		public void remove() {
			ocInc();
			if (lastAccessed == null) throw new Error();
			Node<T> lastPrev = lastAccessed.prev;
			Node<T> lastNext = lastAccessed.next;
			lastPrev.next = lastNext;
			lastNext.prev = lastPrev;
			N--;
			if (current == lastAccessed)
				current = lastNext;
			else
				index--;
			lastAccessed = null;
		}

		// add element to list
		public void add(T item) {
			ocInc();
			Node<T> first  = current.prev;
			Node<T> middle = new Node<>();
			Node<T> last   = current;
			middle.item = item;
			first. next = middle;
			middle.next = last;
			last.  prev = middle;
			middle.prev = first;
			N++;
			index++;
			lastAccessed = null;
		}

	}

	public String toString () {
		StringBuilder sb = new StringBuilder ();
		Iterator<T> it = this.iterator ();
		if (it.hasNext ())
			sb.append (it.next ());
		while (it.hasNext ()) {
			sb.append (" ");
			sb.append (it.next ());
		}
		return sb.toString ();
	}

	public static <T> void printForward(String s, LinkedList<Integer> list, ListIterator<T> iterator) {
		StdOut.println();
		StdOut.println(s);
		StdOut.println(list);
		while (iterator.hasNext())
			StdOut.format ("[%d,%d] ", iterator.nextIndex (), iterator.next ());
		while (iterator.hasPrevious())
			StdOut.format ("[%d,%d] ", iterator.previousIndex (), iterator.previous());
		StdOut.println ();
	}
	public static <T> void printBackward(String s, LinkedList<Integer> list, ListIterator<T> iterator) {
		StdOut.println();
		StdOut.println(s);
		StdOut.println(list);
		while (iterator.hasPrevious())
			StdOut.format ("[%d,%d] ", iterator.previousIndex (), iterator.previous());
		while (iterator.hasNext())
			StdOut.format ("[%d,%d] ", iterator.nextIndex (), iterator.next ());
		StdOut.println ();
	}
	// a test client
	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<>();

		list.add(93);
		list.add(48);
		list.add(94);
		list.add(4);
		list.add(48);
		list.add(94);

		ListIterator<Integer> iterator = list.iterator();
		printForward ("original", list, iterator);

		// set forwards
		while (iterator.hasNext()) {
			int x = iterator.next();
			iterator.set(x + 1);
		}
		printBackward ("after set forward", list, iterator);

		// set backwards
		while (iterator.hasPrevious()) {
			int x = iterator.previous();
			iterator.set(3 * x);
		}
		printForward ("after set backward", list, iterator);


		// remove forwards
		while (iterator.hasNext()) {
			int x = iterator.next();
			if (x % 2 == 0) iterator.remove();
		}
		printBackward ("after remove forward", list, iterator);

		// remove backwards
		while (iterator.hasPrevious()) {
			int x = iterator.previous();
			if (x % 5 == 0) iterator.remove();
		}
		printForward ("after remove backward", list, iterator);

		// add forwards
		while (iterator.hasNext()) {
			int x = iterator.next();
			iterator.add(x + 10);
		}
		printBackward ("after add forward", list, iterator);

		// add backwards
		while (iterator.hasPrevious()) {
			int x = iterator.previous();
			iterator.add(x - 1);
			iterator.previous();
		}
		printForward ("after add backward", list, iterator);
	}
}