package examples.stack2;

import resources.Element;

/**
 * Author: W. M. Farmer <BR>
 * Revised: February 21, 2007 <BR>
 * <BR>
 * Description: Specifies a stack as doubly linked list of nodes.<BR>
 * <BR>
 * Features:<BR>
 * <OL>
 *   <LI> Any number of stacks can be created.
 *   <LI> An object of type Element can be put on a stack.
 *   <LI> Each stack has unbounded height.
 *   <LI> An exception is thrown when top or pop is applied to an
 *        empty stack.
 * </OL>
 *
 * @author W. M. Farmer
 */
public class Stack implements Element {

    private class StackNode implements Element {

	private Element element_;    // Holds the stack Element.
	private StackNode next_;     // Points towards the bottom of the stack.
	private StackNode previous_; // Points towards the top of the stack.

        private StackNode() {
	    element_ = null;      
	    next_ = null;
	    previous_ = null;
	}

       /**
         * Checks if the Element held by this StackNode is equal to the 
         * Element held by another StackNode.
         *
         * @param e a StackNode
         * @return true iff the StackNodes are equal
         */
	public boolean same(Element e) {
	    return e != null
		&& e instanceof StackNode
		&& element_.same(((StackNode)e).element_); 
	}

       /**
        * Returns a String description of this StackNode.
        *
        * @return a String
        */
        public String toString() {
	    return element_.toString();
	}
	
    }

    private StackNode stack_;
    private int height_;

    /**
     * Constructor that creates an empty stack.
     */
    public Stack() {
	stack_ = null;
	height_ = 0;
    }

    /**
     * Selector that gets the top Element of the stack.
     * 
     * @return top Element of the stack
     * @throws EmptyStackException when stack is empty
     */	
    public Element top() throws EmptyStackException {
	if (height_ == 0) {
	    throw new EmptyStackException(this);
	}
	else {
	    return stack_.element_;
	}
    }

    /**
     * Selector that gets the height of the stack.
     * 
     * @return height of the stack
     */
    public int height() {
	return height_;
    }

    /**
     * Mutator that pushes an element onto the stack.
     * 
     * @param e an Element to be pushed onto the stack
     */
    public void push(Element e) {
	StackNode n = new StackNode();
	n.element_ = e;
        n.next_ = stack_;
        n.previous_ = null;
	if (height_ != 0) stack_.previous_ = n;
	stack_ = n;
        height_ = height_ + 1;
    }

    /**
     * Mutator that pops the stack.
     *
     * @throws EmptyStackException when stack is empty
     */
    public void pop() throws EmptyStackException {
	if (height_ == 0) {
	    throw new EmptyStackException(this);
	}
	else {
	    stack_ = stack_.next_;
            height_ = height_ - 1;
	}
    }

    /**
     * Checks if this Stack is equal to another Stack.
     *
     * @param e a Stack
     * @return true iff the Stacks are equal
     */
    public boolean same(Element e) {
	return e != null
	    && e instanceof Stack
            && height() == ((Stack)e).height()
	    && isSameStack((Stack)e);
    }

    private boolean isSameStack(Stack s) {          // Assumes this and s have 
        StackNode n1 = this.stack_;                 // the same height.
        StackNode n2 = s.stack_;
        boolean b = true;
        int h = height_;
        while (b & h != 0) {
	    b = n1.same(n2);
	    if (b) {
		h = h - 1;
		n1 = n1.next_;
		n2 = n2.next_;
	    }
	}
	return b;
    }

    /**
     * Returns a String description of this Stack.
     *
     * @return a String
     */
    public String toString() {
	if (height_ == 0) {
	    return "[]";
	}
	else {
	    return "[" + toStringAux() + "]";
	}
    }

    private String toStringAux() {              // Assumes stack is not empty.
	String x = "";
        int h = 0;
	for (StackNode n = getBottom(); h != height_; n = n.previous_) {
	    if (h == height_ - 1)                          // At top of stack.
		x = x + n.toString();
	    else
		x = x + n.toString() + ",";
	    h = h + 1;
	}
	return x;
    }

    private StackNode getBottom() {             // Assumes stack is not empty.
	StackNode n = stack_;
	while (n.next_ != null) {
	    n = n.next_;
	}
	return n;
    }

}