/**
  * Bloch's Stack example page 56, 2nd edition
  * converted to a flyweight IMMUTABLE class ImmutableStack
  * This is a non generic version
  * @author Paul Ammann
  */

import java.util.*;

public final class ImmutableStack {

   final private Object top;                 //  top of stack
   final private ImmutableStack remainder;   // rest of stack - null for empty stack

   final private static ImmutableStack emptyStack = new ImmutableStack(null, null);

   final private Map<Object, ImmutableStack> map = new HashMap<Object, ImmutableStack>();

   public static ImmutableStack getStack() { return emptyStack; }

   private ImmutableStack(Object top,  ImmutableStack remainder) {
     this.top = top;
     this.remainder = remainder;
   }

   public ImmutableStack push (Object e) {
     if (map.containsKey(e)) return map.get(e);

     ImmutableStack result;
     synchronized(this) {
        if (map.containsKey(e)) return map.get(e);   // double check idiom
        result = new ImmutableStack(e, this);
        map.put(e, result);
     }
     return result;
   }

   public ImmutableStack pop () {
     if (isEmpty()) throw new IllegalStateException("Stack.pop");
     return remainder;
   }

   public Object top () {
     if (isEmpty()) throw new IllegalStateException("Stack.top");
     return top;
   }

   public boolean isEmpty () {
     return (this.equals(emptyStack));
   }

   @Override public String toString() {
      if (isEmpty()) return "[]";
      String s = "]";
      for (ImmutableStack st = this; !st.isEmpty(); st = st.remainder) {
         s = st.top + s;
         if (!st.remainder.isEmpty()) s = ", " + s;
      }
      s = "[" + s;
      return s;
   }
}