CS U370 Object Oriented Design
Fall 2007- Prof. Hafner

RECIPE for implementing in java an immutable ADT named T, given an algebraic
specification

ASSUMPTIONS:
 i.  The operations of the ADT are to be implemented as static methods of
     a class named T.
 ii. Except for the basic creators, each operation of the ADT takes at least
     one argument of type T.
 iii.Except for the basic creators, each operation of the ADT is specified
     by one or more equations.  If an operation is specified by more than
     one equation, then the left hand sides of the equations differ
     according to which basic creator was used to create the argument 
     of type T.

Step 1. Determine which operations of the ADT are creators
Step 2  Define an abstract class called T
Step 3  For each creator c, define a concrete subclass CT of T, whose
	instance variables correspond to the arguments passed to c,
        and whose constructor takes the same arguments as c and stores them
	in the instance variables.
Step 4  For each operation f of T that is not a creator, define a static
	method f of T, and a corresponding non-static ("dynamic") abstract 
	method f' which takes one less argument than f. The missing argument 
	must be of type T.  Each static method will delegate to the 
	corresponding dynamic method, passing it all but one of its 
	arguments. (The missing argument appears as a prefix to the dynamic 
	method call, and can be referenced in the dynamic method using "this".)
Step 5  For each creator c, define a static method in the abstract class
	that creates and returns a new instance of the corresponding subclass
	by calling the appropriate constructor.
Step 6  For each operation f of T that is not a creator, and for each
	concrete subclass of T, define f' as a non-static method within the 
	subclass that follows the algebraic specification for the 
	appropriate creator's generated objects.  If f is not defined for 
	this subclass, throw a RuntimeException, such as an 
	UnsupportedOperationException.

****************************************************************
Example: an immutable ADT, Stack (of int)

    empty:                 -->  Stack
    push:     Stack x int  -->  Stack
    isEmpty:  Stack        -->  boolean
    top:      Stack        -->  int
    pop:      Stack        -->  Stack

    isEmpty (empty())  =  true
    isEmpty (push (s, n))  =  false

    top (push (s, n))  =  n

    pop (push (s, n))  =  s

Note:  This specification does not define pop and top on an
empty stack.

****************************************************************
public abstract class Stack {

 // The basic creators are empty and push.

    // Returns an empty stack.

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

    // Returns a stack representing n pushed onto s.

    public static Stack push (Stack s, int n) {
        return new PushStack (s, n);
    }

 // Other public methods.

    // Returns true iff the given stack is empty.

    public static boolean isEmpty (Stack s) {
        return s.isEmpty1();
    }

    // Returns the top element of the given stack, which must be nonempty.

    public static int top (Stack s) {
        return s.top1();
    }

    // Returns the pop of the given stack, which must be nonempty.

    public static Stack pop (Stack s) {
        return s.pop1();
    }

 // Abstract methods for the accessors.

    // Returns true iff this stack is empty.

    abstract boolean isEmpty1 ();

    // Returns the top element of this stack, which must be nonempty.

    abstract int top1 ();

    // Returns the other elements of this stack, which must be nonempty.

    abstract Stack pop1 ();
}

// The class of objects created by empty().

class EmptyStack extends Stack {

    // Initializes this empty stack.

    EmptyStack () { }

    boolean isEmpty1 () { return true; }

    int top1 () {
        throw new IllegalArgumentException (msgTop);
    }

    Stack pop1 () {
        throw new IllegalArgumentException (msgPop);
    }

    private static final String msgTop
        = "Can't take the top of an empty stack.";

    private static final String msgPop
        = "Can't pop an empty stack.";
}

// The class of objects created by push(s,n).

class PushStack extends Stack {

    private Stack s;                 // the pop of this Stack
    private int n;                   // the top of this Stack

    // Initializes this stack with top n and pop s.

    PushStack (Stack s, int n) {
        this.s = s;
        this.n = n;
    }

    boolean isEmpty1 () { return false; }

    int top1 () {
        return n;
    }

    Stack pop1 () {
        return s;
    }
}