/**Doubly liked list with nodes of type DNode storing strings */

public class DList {

    private int size; //number of elements
    private DNode first, last;

    /** Constructor that creates an empty DList */
    public DList(){size = 0; first = last = null;}
	
    /** Return the number of elements in the DList */
    public int size(){return size;}
	
    /** Return whether the DList is empty */
    public boolean isEmpty(){return (size == 0);}
	
    /** Return the first node of the DList */
    public DNode getFirst(){return first;}
	
    /** Return the last node of the DList */
    public DNode getLast(){return last;}

    /** Is the String s in the DList */
    public boolean isPresent(String s){
	boolean found = false;
	for (DNode cursor = first; cursor != null && !found && cursor.compareTo(s) <= 0; cursor = cursor.getNext())
	    found = cursor.compareTo(s) == 0;
	return found;
    }
    //
    // NOTE: use of for loop ... is this what you would expect?
    //

     /** Is the String s in the DList */
    public boolean found(String s){
	for (DNode cursor = first; cursor != null && cursor.compareTo(s) <= 0; cursor = cursor.getNext())
	    if (cursor.compareTo(s) == 0) return true;
	return false;
    }
	    
    /** Insert string in lex order */
    public void insert(String s){
	if (first == null){first = last = new DNode(s);}
	else if (first.compareTo(s) >= 0) insertAtFirst(new DNode(s));
	else if (last.compareTo(s) <= 0) insertAtLast(new DNode(s));
	else {
	    DNode cursor = first;
	    while (cursor.compareTo(s) < 0) cursor = cursor.getNext();
	    DNode node = new DNode(s);
	    insertBetween(cursor.getPrev(),node,cursor);
	}
	size++;
    }

    /** Insert node at the first of the DList */
    private void insertAtFirst(DNode node){
	node.setNext(first); first.setPrev(node); node.setPrev(null); first = node;
    }

    /** Insert node as the last of the DList */
    private void insertAtLast(DNode node){
	last.setNext(node); node.setPrev(last); node.setNext(null); last = node;
    }

    /** Insert node y between nodes x and z */
    private void insertBetween(DNode x, DNode y, DNode z){
	x.setNext(y); y.setPrev(x); y.setNext(z); z.setPrev(y);
    }

    /** Delete node with matching string s, knowing DList is sorted! */
    public void delete(String s){
	if (first == null || first.compareTo(s) > 0 || last.compareTo(s) < 0) return;
	for (DNode cursor = first; cursor != null && cursor.compareTo(s) <= 0; cursor = cursor.getNext())
	    if (cursor.compareTo(s) == 0){delete(cursor); return;}
    }

    private void delete(DNode node){
	if (size == 1){first = last = null;}
	else if (node == first){first = first.getNext(); first.setPrev(null);}
	else if (node == last){last = last.getPrev(); last.setNext(null);}
	else {
	    node.getPrev().setNext(node.getNext());
	    node.getNext().setPrev(node.getPrev());
	}
	size--;
    }

    /** String representation of list */
    public String toString(){
	DNode cursor = first;
	String s = "(";
	while(cursor != null){
	    s = s + cursor;
	    cursor = cursor.getNext();
	    if (cursor != null) s = s + ",";
	}
	return s + ")";
    }
}