/******************************************************************************
 * file: DoubleLinkedList.java
 * 
 * description: provides a class to create double linked lists and methods
 * to perform typical operations on these type of data set
 *****************************************************************************/


import java.util.Enumeration;
class DLL_Node {
    
    public DLL_Node(Object o, DLL_Node prev, DLL_Node next) {
        this.content = o;
        this.nextNode = next;
        this.prevNode = prev;
    }
    
  /* returns the content of this node */
  public Object getContent() {
    return this.content;
  }

    
  /* sets the content of this node to o */
  public void setContent(Object o) {
    this.content = o;
  }

    
  /* returns the predecessor of this node */
  public DLL_Node getPreviousNode() {
      return this.prevNode;
  }

    
  /* sets the predecessor of this node to p */
  public void setPreviousNode(DLL_Node p) {
      this.prevNode = p;
  }

    
  /* returns the successor of this node */
  public DLL_Node getNextNode() {
    return this.nextNode;
  }

    
  /* sets the successor of this node to n */
  public void setNextNode(DLL_Node n) {
    this.nextNode  = n;
  }

    
    /* returns the node's content as a string */
    public String toString() {
	return (String) this.content;
    }
    private Object content;
    private DLL_Node nextNode;
    private DLL_Node prevNode;

}


/* a double linked list */
public class DoubleLinkedListSimple {

    
    /* variables */
    protected DLL_Node head;
    protected DLL_Node tail;
    
    /* constructor */
    public DoubleLinkedListSimple() {
	this.head = null;
	this.tail = null;
    }
    
    
    /* returns true if this list is empty, otherwise false */
    public boolean isEmpty() {
	return (this.head == null);
    }
    
    public void insertHead(Object o) {
	if (this.isEmpty())
	    this.head = this.tail = new DLL_Node(o, null, null);
	else {
	    this.head.setPreviousNode(new DLL_Node(o, null, this.head));
	    this.head = this.head.getPreviousNode();
	}
    }

    public void insertTail(Object o) {
	if (this.isEmpty())
	    this.insertHead(o);
	else {
	    this.tail.setNextNode(new DLL_Node(o, this.tail, null));
	    this.tail = this.tail.getNextNode();
	}
    }

    public DLL_Node getHead(){
	return this.head;
    }
    
    public void removeHead(){
	this.removeNode(this.head);
    }

    public void removeTail(){
	this.removeNode(this.tail);
    }

    public void removeNode(DLL_Node n){
	DLL_Node nextNode = n.getNextNode();
	DLL_Node prevNode = n.getPreviousNode();
	if (this.head == n)
	    this.head = nextNode;
	if (this.tail == n)
	    this.tail = prevNode;
	if (prevNode != null)
	    prevNode.setNextNode(nextNode);
	if (nextNode != null)
	    nextNode.setPreviousNode(prevNode);
    }
    
    public void reverse(){
	DLL_Node tmp = this.head;
	while (tmp != null){
	    // swap prev and next
	    DLL_Node next  = tmp.getNextNode();
	    tmp.setNextNode(tmp.getPreviousNode());
	    tmp.setPreviousNode(next);
	    tmp = next;
	}
	// swap head and tail
	tmp = this.head;
	this.head = this.tail;
	this.tail = tmp;
    }

    
    /* returns the list's content as a string object */
    public String toString() {
	String str = "[";
	DLL_Node tmp = this.head;
	while (tmp != null) {
	    str += tmp.getContent().toString();
	    tmp = tmp.getNextNode();
	    if (tmp != null)
		str += ", ";
	}
	return str+"]";
    }

}