SWE 619 Assignment 12
Fall 2011

Goal: Liskov: Factories and flyweights.

Reconsider the immutable stack abstraction in assignment 3. A naive solution generates a new stack object on every call to a constructor or a producer. In addition, the call to the constructor ensures a dependency between clients and the stack class. To overcome these drawbacks, make the following changes:

  1. Write an immutable interface IStack with three methods, push(), pop(), and top().
  2. Write a class FlyStack that implements the immutable IStack abstraction: 
        public class FlyStack implements IStack {...}
  3. The representation and constructor for FlyStack should be: 
       final private Object topValue;    // Top of the stack
   final private FlyStack previous;  // Rest of stack

   // holds all existing Stacks = (x, this) generated by this.push(x)
   final private Map<Object, FlyStack> m;

   private final static IStack emptyStack = new FlyStack(null, null);

   private FlyStack (Object top, FlyStack predecessor) {  
       topValue = top;
       previous = predecessor;
       m = new HashMap<Object, FlyStack>();
   }
    Do not provide any additional constructors or add any other representation variables - either at the object or at the class level. The idea with m is that if a stack object has been created previously with x on top of this, then Map m will have an entry in it of the form 
            (x, FlyStack with topValue=x and remainder=this)
    As a result, each different stack will only be created once. This includes the empty stack, which is the rationale for the static emptyStack variable.
  4. Add a factory method makeStack() to FlyStack. 
       public static IStack makeStack() { ... }
  5. Determine if it is necessary to override equals() and hashCode(). If so, override them. If not, explain why not.
  6. Implement toString() in the usual way.
  7. Provide a decent set of JUnit tests.

Possible Bonus Points: