Eric said he will write about an immutable queue implementation. I really like the way the immutable stack turned out, essentially using references between Stack<> objects to implement a linked list, but I couldn't figure out a similarly elegant way to do the same thing for Queue. Maybe people who are more clever will come up with something better, but I just had each Queue<> object contain a list of references to elements.
I wrote once in C# 2.0, using an array to store the elements. The code would be cleaner if I used a List<>, but then I would be harder to verify immutability.
class Queue<T> : IQueue<T>
{
public static readonly IQueue<T> Empty = new Queue<T>(new T[] { });
readonly T[] elements;
Queue(T[] elements)
{
this.elements = elements;
}
public bool IsEmpty { get { return this.elements.Length == 0; } }
public T Peek() { return this.elements[0]; }
public IQueue<T> Remove()
{
T[] newElements = new T[this.elements.Length - 1];
Array.Copy(this.elements, 1, newElements, 0, newElements.Length);
return new Queue<T>(newElements);
}
public IQueue<T> Add(T value)
{
T[] newElements = new T[this.elements.Length + 1];
Array.Copy(this.elements, newElements, this.elements.Length);
newElements[newElements.Length - 1] = value;
return new Queue<T>(newElements);
}
public IEnumerator<T> GetEnumerator()
{
for (IQueue<T> Queue = this; !Queue.IsEmpty; Queue = Queue.Remove())
yield return Queue.Peek();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}
Then I rewrote using C# 3.0, taking advantage of the rich support for sequences. The code is much simpler, but I think that's basically because the IEnumerable extension methods do pretty much what I did in my first attempt. But I'll take it. J
class Queue2<T> : IQueue<T>
{
readonly IEnumerable<T> elements;
public static IQueue<T> Empty = new Queue2<T>(new T[] { });
Queue2(IEnumerable<T> elements)
{
this.elements = elements;
}
IQueue<T> IQueue<T>.Add(T value)
{
return new Queue2<T>(this.elements.Concat(new T[] { value }));
}
IQueue<T> IQueue<T>.Remove()
{
return new Queue2<T>(this.elements.Skip(1));
}
T IQueue<T>.Peek()
{
return this.elements.First();
}
bool IQueue<T>.IsEmpty
{
get
{
return this.elements.Count() == 0;
}
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return this.elements.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.elements.GetEnumerator();
}
}
