|
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;
}
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
I'm Computer Scientist, one of the founders of Signum Software, and the lead developer behind Signum Framework.
www.signumframework.com
I love programming in C#, Linq, Compilers, Algorithms, Functional Programming, Computer Graphics, Maths...