Signum Framework Tutorials Part 2 – Southwind Logic

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using Signum.Utilities.Properties;

namespace Signum.Utilities.DataStructures
{
    public class ImmutableStack<T>:IEnumerable<T>
    {
        private class ImmutableFullStack : ImmutableStack<T>
        {
            readonly T head;
            readonly ImmutableStack<T> tail;

            public ImmutableFullStack(T head, ImmutableStack<T> tail)
            {
                this.head = head;
                this.tail = tail;
            }

            public override bool IsEmpty { get { return false; } }
            public override T Peek() { return head; }
            public override ImmutableStack<T> Pop() { return tail; }
            public override ImmutableStack<T> Push(T value) { return new ImmutableFullStack(value, this); }

            public override IEnumerator<T> GetEnumerator()
            {
                for (ImmutableStack<T> stack = this; !stack.IsEmpty; stack = stack.Pop())
                    yield return stack.Peek();
            }

            public override string ToString()
            {
                return "[" + this.ToString(", ") + "]";
            }

        }

        public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>();

        private ImmutableStack(){}

        public virtual bool IsEmpty { get { return true; } }
        public virtual T Peek() { throw new InvalidOperationException("Empty Stack"); }
        public virtual ImmutableStack<T> Push(T value) { return new ImmutableFullStack(value, this); }
        public virtual ImmutableStack<T> Pop() { throw new InvalidOperationException("Empty Stack"); }
        public virtual IEnumerator<T> GetEnumerator() { yield break; }
        public override string ToString() { return "[]"; }

        IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }      
    }

    public static class ImmutableStackExtensions
    {
        public static ImmutableStack<T> Reverse<T>(this ImmutableStack<T> stack)
        {
            return Reverse(stack, ImmutableStack<T>.Empty);
        }

        public static ImmutableStack<T> Reverse<T>(this ImmutableStack<T> stack, ImmutableStack<T> initial)
        {
            ImmutableStack<T> r = initial;
            for (ImmutableStack<T> f = stack; !f.IsEmpty; f = f.Pop())
                r = r.Push(f.Peek());
            return r;
        }
    }
}