Immutability, part 2: Creating a simple immutable stack - SLaks.Blog

Immutability, part 2: Creating a simple immutable stack – SLaks.Blog
Also check http://blogs.msdn.com/b/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx
The simplest useful example of an immutable class is an immutable stack. Immutable stacks work just like regular stacks – with Push(), Pop(), and Peek() methods – except that instead of mutating the original instance, Push() and Pop() return a new, modified, instance.
IStack<int> myStack = empty; myStack = myStack.Push(1).Push(2).Push(3); while (!myStack.IsEmpty) { Console.WriteLine(myStack.Peek()); myStack = myStack.Pop(); }

Each implementation of this interface would supply a singleton empty instance; since they are immutable; there is no need to have more than one empty instance. Thus, there is no need for a constructor. Since Pop() needs to return the new stack, it cannot return the removed item; therefore, Peek() is the only way to get the item.

The naive implementation of this interface would use a list, and copy the list when creating a new stack:

public class NaiveStack<T> : IStack<T> {
    private readonly ReadOnlyCollection<T> items;
    private NaiveStack(IList<T> items) {
        this.items = new ReadOnlyCollection<T>(items);
    }

    public static readonly NaiveStack<T> Empty 
        = new NaiveStack<T>(new T[0]);

    public IStack<T> Push(T element) {
        var list = new List<T>(items);
        list.Add(element);
        return new NaiveStack<T>(list);
    }

    public IStack<T> Pop() {
        if (IsEmpty)
            throw new InvalidOperationException("Stack is empty");
        var list = new List<T>(items);
        list.RemoveAt(list.Count - 1);
        return new NaiveStack<T>(list);
    }

    public T Peek() { return items.Last(); }
    public bool IsEmpty { 
        get { return items.Count == 0; } 
    }
}




The problem with this approach is that each mutation requires an O(n) copy to create the list behind the new instance. This makesPush() and Pop() awfully slow, and vastly increases the memory footprint until the intermediate instances can be GCd.



To solve these problems, we can design the stack as a persistent data structure. Instead of copying anything when pushing on to a stack, we cab make the new stack instance hold only the newly added item, and maintain a reference to the previous instance storing the rest of the items. Popping from the stack can then simply return the previous instance. Basically, the stack becomes an immutable single-linked list.

public abstract class PersistentStack<T> : IStack<T> {
    public static readonly PersistentStack<T> Empty = new EmptyNode();

    public IStack<T> Push(T element) {
        return new LinkNode(this, element);
    }

    private class EmptyNode : PersistentStack<T> {
        public override IStack<T> Pop() {
            throw new InvalidOperationException("Stack is empty");
        }
        public override T Peek() { 
            throw new InvalidOperationException("Stack is empty");
        }
        public override bool IsEmpty { get { return true; } }
    }

    private class LinkNode : PersistentStack<T> {
        readonly IStack<T> previous;
        readonly T element;

        public LinkNode(IStack<T> previous, T element) {
            this.previous = previous;
            this.element = element;
        }

        public override IStack<T> Pop() {
            return previous;
        }
        public override T Peek() { return element; }
        public override bool IsEmpty { get { return false; } }
    }
    public abstract IStack<T> Pop();
    public abstract T Peek();
    public abstract bool IsEmpty { get; }
}

In this implementation, the empty and non-empty nodes are different enough that I decided to use polymorphism rather than ifstatements. The PersistentStack<T> type contains the only common logic (Push()); everything else is implement by the two concrete classes.

Here, the empty stack truly is a singleton; only one instance will ever be created for each element type. It can only be used as a starting point to create new stacks; the other methods simply throw exceptions. It also serves as the final node in the chain for all non-empty stacks.

Pushing onto any stack (empty or not) returns a new node that holds the new item and points to the previous stack; popping a non-empty stack simply returns that reference.

Like other linked lists, this approach implements both Push() and Pop() in O(1) in both memory and time.

http://blog.slaks.net/2013-06-28/covariant-immutable-stack/
Java: Immutable Stack
class Stack<T> implements IStack<T> {
private T head;
private IStack<T> tail;
public Stack(final T head, final IStack<T> tail) {
this.head = head;
this.tail = tail;
}
public static <U> IStack<U> empty(final Class<U> type) { return new EmptyStack<U>(); }

public boolean isEmpty() { return false; }

public T peek() { return this.head; }

public IStack<T> pop() { return this.tail; }

public IStack<T> push(T value) { return new Stack<T>(value, this); }

public Iterator<T> iterator() { return new StackIterator<T>(this); }
private static class StackIterator<U> implements Iterator<U> {
private IStack<U> stack;
public StackIterator(final IStack<U> stack) { this.stack = stack; }

public boolean hasNext() { return !this.stack.isEmpty(); }

public U next() {
U result = this.stack.peek();
this.stack = this.stack.pop();
return result;
}

public void remove() { }
}
private static class EmptyStack<U> implements IStack<U> {

public boolean isEmpty() { return true; }

public U peek() { throw new RuntimeException(“empty stack”); }

public IStack<U> pop() { throw new RuntimeException(“empty stack”); }

public IStack<U> push(U value) { return new Stack<U>(value, this); }

public Iterator<U> iterator() { return new StackIterator<U>(this); }
}
}

https://github.com/tunnelvisionlabs/java-immutable/blob/master/src/com/tvl/util/ImmutableLinkedStack.java
public final class ImmutableLinkedStack<T> implements ImmutableStack<T> {

    /**
     * The singleton empty stack.
     */
    private static final ImmutableLinkedStack<?> EMPTY_STACK = new ImmutableLinkedStack<Object>();

    /**
     * The element on the top of the stack.
     */
    private final T head;

    /**
     * A stack that contains the rest of the elements (under the top element);
     */
    private final ImmutableLinkedStack<T> tail;

    /**
     * Initializes a new instance of the {@link ImmutableLinkedStack} class that acts as the empty stack.
     */
    private ImmutableLinkedStack() {
        head = null;
        tail = null;
    }

    /**
     * Initializes a new instance of the {@link ImmutableLinkedStack} class.
     *
     * @param head The head element on the stack.
     * @param tail The rest of the elements on the stack.
     */
    private ImmutableLinkedStack(T head, ImmutableLinkedStack<T> tail) {
        Requires.notNull(tail, "tail");

        this.head = head;
        this.tail = tail;
    }

    /**
     * Return an empty collection.
     *
     * @param <T> The type of items stored by the collection.
     * @return The immutable collection.
     */
    public static <T> ImmutableLinkedStack<T> create() {
        return empty();
    }

    /**
     * Creates a new immutable collection pre-filled with the specified item.
     *
     * @param <T> The type of items stored by the collection.
     * @param item The item to pre-populate.
     * @return The immutable collection.
     */
    public static <T> ImmutableLinkedStack<T> create(T item) {
        return ImmutableLinkedStack.<T>empty().push(item);
    }

    /**
     * Creates a new immutable collection pre-filled with the specified items.
     *
     * @param <T> The type of items stored by the collection.
     * @param items The items to pre-populate.
     * @return The immutable collection.
     */
    public static <T> ImmutableLinkedStack<T> create(T... items) {
        Requires.notNull(items, "items");

        ImmutableLinkedStack<T> stack = empty();
        for (T item : items) {
            stack = stack.push(item);
        }

        return stack;
    }

    /**
     * Creates a new immutable collection pre-filled with the specified items.
     *
     * @param <T> The type of items stored by the collection.
     * @param items The items to pre-populate.
     * @return The immutable collection.
     */
    public static <T> ImmutableLinkedStack<T> createAll(Iterable<? extends T> items) {
        Requires.notNull(items, "items");

        ImmutableLinkedStack<T> stack = empty();
        for (T item : items) {
            stack = stack.push(item);
        }

        return stack;
    }

    /**
     * Gets the empty stack, upon which all stacks are built.
     *
     * @param <T> The type of element stored by the stack.
     * @return The empty stack.
     */
    public static <T> ImmutableLinkedStack<T> empty() {
        @SuppressWarnings(Suppressions.UNCHECKED_SAFE)
        ImmutableLinkedStack<T> result = (ImmutableLinkedStack<T>)EMPTY_STACK;
        return result;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isEmpty() {
        return tail == null;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public ImmutableLinkedStack<T> clear() {
        return empty();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public ImmutableLinkedStack<T> push(T value) {
        return new ImmutableLinkedStack<T>(value, this);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public ImmutableLinkedStack<T> pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return tail;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return head;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Iterator<T> iterator() {
        return new Itr<T>(this);
    }

    /**
     * Reverses the order of the stack.
     *
     * @return The reversed stack.
     */
    ImmutableLinkedStack<T> reverse() {
        ImmutableLinkedStack<T> result = clear();
        for (ImmutableLinkedStack<T> f = this; !f.isEmpty(); f = f.pop()) {
            result = result.push(f.peek());
        }

        return result;
    }

    private static final class Itr<T> implements Iterator<T> {

        /**
         * The original stack being enumerated.
         */
        private final ImmutableLinkedStack<T> originalStack; // no need this.
        /**
         * The remaining stack not yet enumerated.
         */
        private ImmutableLinkedStack<T> remainingStack;

        /**
         * Initializes a new instance of the {@link Itr} class.
         *
         * @param originalStack The stack to enumerate.
         */
        public Itr(ImmutableLinkedStack<T> originalStack) {
            this.originalStack = originalStack;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public boolean hasNext() {
            if (remainingStack == null) {
                return !originalStack.isEmpty();
            }

            return !remainingStack.isEmpty();
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public T next() {
            if (remainingStack == null) {
                remainingStack = originalStack;
            }

            if (remainingStack.isEmpty()) {
                throw new NoSuchElementException();
            }

            T result = remainingStack.peek();
            remainingStack = remainingStack.pop();
            return result;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
http://cs.gmu.edu/~pammann/332/assigns/code/ImmutableStack.java
No need Map<Object, ImmutableStack> map.
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));
   }
}

http://blog.csdn.net/shoulinjun/article/details/31760103

有趣的函数式数据结构《一》----不可变栈

什么是不可变？往栈中插入一个元素，原来的栈保持不变，返回一个新的栈（已插入新的元素）。

push, pop，getMax 等操作都要求在 常数时间内完成。

可能读者会产生疑惑，既然要返回一个新的栈，是不是就必须先拷贝一份原来的栈，然后在新的栈中插入元素。

但是这样复杂度就是线性的，如何能够在常数时间内完成呢？？

这里，就是immutable DATA STRUCTRUE 的强大。。

本文给出一个C++ 的实现版本，基本理想是利用内存共享，以及均摊时间的思想。

下图给出了实现的核心思想。

三个链表[1,2,3], [1,2,4], [1,2,5]共用节点1,2

这是因为一个节点可以有多个前驱节点指向它本身。。而栈的特性：仅仅在链表的头部插入删除的性质保证了节点的共享。

Read full article from Immutability, part 2: Creating a simple immutable stack – SLaks.Blog