// Recipe implementation of the Stack<E> ADT.

public abstract class Stacks<E> {

    public static <E> Stack<E> empty () {
        return new EmptyStack<E>();
    }

    // Recipe implementation of the Stack<E> ADT.

    static abstract class StackBase<E> implements Stack<E> {

        public abstract Stack<E> push (E x);
        public abstract boolean  isEmpty();
        public abstract E        top();
        public abstract Stack<E> pop();
        public abstract int      size();

    }

    // Empty stacks.
    // 
    // For purpose statements and algebraic specification, see Stack.java.

    static class EmptyStack<E> extends StackBase<E> {

        EmptyStack () { }

        public Stack<E> push (E x) {
            return new Push<E> (this, x);
        }

        public boolean  isEmpty () {
            return true;
        }

        public E top () {
            String msg1
                = "attempted to compute the top of an empty StackInt";
            throw new RuntimeException (msg1);
        }

        public Stack<E> pop () {
            return this;                   // FIXME: this is evil
        }

        public int size () {
            return 0;
        }
    }

    // Non-empty stacks.
    // 
    // For purpose statements and algebraic specification, see Stack.java.

    static class Push<E> extends StackBase<E> {

        private Stack<E> s;       // the other elements of this Stack
        private E x;              // the topmost element of this Stack

        Push (Stack<E> s, E x) {
            this.s = s;
            this.x = x;
        }

        public Stack<E> push (E x) {
            return new Push<E> (this, x);
        }

        public boolean isEmpty () {
            return false;
        }

        public E top () {
            return x;
        }

        public Stack<E> pop () {
            return s;
        }

        public int size () {
            return 1 + s.size();
        }
    }
}