/* File: DoublyLinkedList.java - May 2017 */
package l16;

/**
*  @author Michael Albert
*
*  Defines an implementation of a basic doubly linked list.
*
*  The metaphor is that of a loose leaf binder -- user access
*  is basically restricted to a "current" page plus forward and
*  back navigation, and the option to reset so that the first page
*  is the current page.
*
*  An invariant is that the current page should never be null unless
*  the list is empty.
*
*/

public class DoublyLinkedList<T>  {

  private DLLNode<T> first;
  private DLLNode<T> last;
  private DLLNode<T> current;

  public DoublyLinkedList() {
    this.first = null;
    this.last = null;
    this.current = null;
  }
  
  public boolean isEmpty() {
    return (current == null);
  }
  
  public void insert(T value) {
  
    DLLNode<T> newNode = new DLLNode<>(value);
    
    if (isEmpty()) {
      first = newNode;
      last = newNode;
      current = newNode;
    } else {
      formLink(current.prev, newNode);
      formLink(newNode, current);
      if (current == first) {
        first = newNode;
      }
      current = newNode;
    }
  }
  
  public void delete() {
    if (isEmpty()) return;
    formLink(current.prev, current.next);
    if (current.next != null) {
      current = current.next;
    } else {
      current = current.prev;
      // If we've deleted the last element then we need to reset all
      // references to null.
      if (isEmpty()) {
        first = null;
        last = null;
      }
    }
  }
  
  public void next() {
    if (current.next != null) current = current.next;
  }
  
  public void prev() {
    if (current.prev != null) current = current.prev;
  }
  
  public void reset() {
    current = first;
  }
  
  private void formLink(DLLNode<T> a, DLLNode<T> b) {
    if (a != null) a.next = b;
    if (b != null) b.prev = a;
  }


  public String toString() {
    StringBuilder result = new StringBuilder();
    result.append("<DLL>: <-> ");
    DLLNode<T> node  = this.first;
    while (node != null) {
      if (node == current) {
        result.append("(*)");
      }
      result.append(node.value);
      result.append(" <-> ");
      node = node.next;
    }
    return result.toString();
  }

  private class DLLNode<T> {
    private T value;
    private DLLNode<T> next;
    private DLLNode<T> prev;

    private DLLNode(T value) {
      this.value = value;
      this.next = null;
      this.prev = null;
    }

  }

}