public interface IDeque<T> { T PeekLeft(); T PeekRight(); IDeque<T> EnqueueLeft(T value); IDeque<T> EnqueueRight(T value); IDeque<T> DequeueLeft(); IDeque<T> DequeueRight(); bool IsEmpty { get; } }
public sealed class Deque<T> : IDeque<T> { private sealed class EmptyDeque : IDeque<T> { public bool IsEmpty { get { return true; } } public IDeque<T> EnqueueLeft(T value) { return new SingleDeque(value); } public IDeque<T> EnqueueRight(T value) { return new SingleDeque(value); } public IDeque<T> DequeueLeft() { throw new Exception("empty deque"); } public IDeque<T> DequeueRight() { throw new Exception("empty deque"); } public T PeekLeft () { throw new Exception("empty deque"); } public T PeekRight () { throw new Exception("empty deque"); } } private sealed class SingleDeque : IDeque<T> { public SingleDeque(T t) { item = t; } private readonly T item; public bool IsEmpty { get { return false; } } public IDeque<T> EnqueueLeft(T value) { return new Deque<T>(new One(value), Deque<Dequelette>.Empty, new One(item)); } public IDeque<T> EnqueueRight(T value) { return new Deque<T>(new One(item), Deque<Dequelette>.Empty, new One(value)); } public IDeque<T> DequeueLeft() { return Empty; } public IDeque<T> DequeueRight() { return Empty; } public T PeekLeft () { return item; } public T PeekRight () { return item; } }
private abstract class Dequelette { public abstract int Size { get; } public virtual bool Full { get { return false; } } public abstract T PeekLeft(); public abstract T PeekRight(); public abstract Dequelette EnqueueLeft(T t); public abstract Dequelette EnqueueRight(T t); public abstract Dequelette DequeueLeft(); public abstract Dequelette DequeueRight(); } private class One : Dequelette { public One(T t1) { v1 = t1; } public override int Size { get { return 1; } } public override T PeekLeft() { return v1; } public override T PeekRight() { return v1; } public override Dequelette EnqueueLeft(T t) { return new Two(t, v1); } public override Dequelette EnqueueRight(T t) { return new Two(v1, t); } public override Dequelette DequeueLeft() {throw new Exception("Impossible"); } public override Dequelette DequeueRight() {throw new Exception("Impossible"); } private readonly T v1; } private class Two : Dequelette { public Two(T t1, T t2) { v1 = t1; v2 = t2; } public override int Size { get { return 2; } } public override T PeekLeft() { return v1; } public override T PeekRight() { return v2; } public override Dequelette EnqueueLeft(T t) { return new Three(t, v1, v2); } public override Dequelette EnqueueRight(T t) { return new Three(v1, v2, t); } public override Dequelette DequeueLeft() { return new One(v2); } public override Dequelette DequeueRight() { return new One(v1); } private readonly T v1; private readonly T v2; } private class Three : Dequelette { public Three(T t1, T t2, T t3) { v1 = t1; v2 = t2; v3 = t3; } public override int Size { get { return 3; } } public override T PeekLeft() { return v1; } public override T PeekRight() { return v3; } public override Dequelette EnqueueLeft(T t) { return new Four(t, v1, v2, v3); } public override Dequelette EnqueueRight(T t) { return new Four(v1, v2, v3, t); } public override Dequelette DequeueLeft() { return new Two(v2, v3); } public override Dequelette DequeueRight() { return new Two(v1, v2); } private readonly T v1; private readonly T v2; private readonly T v3; } private class Four : Dequelette { public Four(T t1, T t2, T t3, T t4) { v1 = t1; v2 = t2; v3 = t3; v4 = t4; } public override int Size { get { return 4; } } public override bool Full { get { return true; } } public override T PeekLeft() { return v1; } public override T PeekRight() { return v4; } public override Dequelette EnqueueLeft(T t) {throw new Exception("Impossible"); } public override Dequelette EnqueueRight(T t) {throw new Exception("Impossible"); } public override Dequelette DequeueLeft() { return new Three(v2, v3, v4); } public override Dequelette DequeueRight() { return new Three(v1, v2, v3); } private readonly T v1; private readonly T v2; private readonly T v3; private readonly T v4; }
private static readonly IDeque<T> empty = new EmptyDeque(); public static IDeque<T> Empty { get { return empty; } }
public bool IsEmpty { get { return false; } }
private Deque(Dequelette left, IDeque<Dequelette> middle, Dequelette right) { this.left = left; this.middle = middle; this.right = right; }
private readonly Dequelette left; private readonly IDeque<Dequelette> middle; private readonly Dequelette right;
public IDeque<T> EnqueueLeft(T value) { if (!left.Full) return new Deque<T>(left.EnqueueLeft(value), middle, right); return new Deque<T>( new Two(value, left.PeekLeft()), middle.EnqueueLeft(left.DequeueLeft()), right); } public IDeque<T> EnqueueRight(T value) { if (!right.Full) return new Deque<T>(left, middle, right.EnqueueRight(value)); return new Deque<T>( left, middle.EnqueueRight(right.DequeueRight()), new Two(right.PeekRight(), value)); } public IDeque<T> DequeueLeft() { if (left.Size > 1) return new Deque<T>(left.DequeueLeft(), middle, right); if (!middle.IsEmpty) return new Deque<T>(middle.PeekLeft(), middle.DequeueLeft(), right); if (right.Size > 1) return new Deque<T>(new One(right.PeekLeft()), middle, right.DequeueLeft()); return new SingleDeque(right.PeekLeft()); } public IDeque<T> DequeueRight() { if (right.Size > 1) return new Deque<T>(left, middle, right.DequeueRight()); if (!middle.IsEmpty) return new Deque<T>(left, middle.DequeueRight(), middle.PeekRight()); if (left.Size > 1) return new Deque<T>(left.DequeueRight(), middle, new One(left.PeekRight())); return new SingleDeque(left.PeekRight()); } public T PeekLeft () { return left.PeekLeft(); } public T PeekRight () { return right.PeekRight(); } }
At long last, let's get to that double-ended queue. Sorry for leaving you in suspense! Last time we came
At long last, let's get to that double-ended queue. Sorry for leaving you in suspense! Last time
Wow, a recursively defined generic type... I can feel it, my mind is more expanded now :)
To get a better understanding of this I thought I'd try out the code. I can't figure out how to initialize an instance of it, it lacks a public constructor. I feel like I've missed something obvious.
Could you provide a code example that uses this?
IDeque<int> d1 = Deque<int>.Empty; // Empty Deque
IDeque<int> d2 = d1.EnqueueLeft(1); // Now we have two deques, d1, which is empty, and d2 which has one element
...
Thanks for the quick response. I was expecting to get a class instance not an interface instance. If felt wrong to me, I know realize I have a bit of a class bias. You don't need direct class access, only interface access. Thank you for the excellent code, it's really gotten me thinking.
While trying to understand this, I reached a point where I thought the deque would be limited to 12 items. Now, I see that it's not limited because the middle deque is not a Dequelette, but a IDeque<Dequelette>. A deque of deque's!
I think I'll have to read all your posts on immutability now... :P