Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class AmortizedConstantTimeImmutableQueue<T> : IImmutableQueue<T>
{
public bool IsEmpty => throw new NotImplementedException();
bool IImmutableQueue<T>.IsEmpty => throw new NotImplementedException();
public static AmortizedConstantTimeImmutableQueue<T> Empty =>
new AmortizedConstantTimeImmutableQueue<T>(0, ImmutableStack<T>.Empty, 0, ImmutableStack<T>.Empty, ImmutableStack<Lazy<ImmutableStack<T>>>.Empty);
private ImmutableStack<T> Front;
private int FrontLength;
private int BackLength;
private ImmutableStack<T> Back;
private ImmutableStack<Lazy<ImmutableStack<T>>> ReversingImmutableStacks;
public AmortizedConstantTimeImmutableQueue
(int frontLength, ImmutableStack<T> front, int backLength, ImmutableStack<T> back, ImmutableStack<Lazy<ImmutableStack<T>>> reversingImmutableStacks)
{
FrontLength = frontLength;
Front = front;
BackLength = backLength;
Back = back;
ReversingImmutableStacks = reversingImmutableStacks;
}
public AmortizedConstantTimeImmutableQueue<T> Clear()
{
throw new NotImplementedException();
}
public AmortizedConstantTimeImmutableQueue<T> Dequeue()
{
var newFrontLength = FrontLength;
var newFront = Front;
var newBackLength = BackLength;
var newBack = Back;
var newRevs = ReversingImmutableStacks;
if (Back.IsEmpty)
{
newBack = ReversingImmutableStacks.Peek().Value;
newRevs = ReversingImmutableStacks.Pop();
}
newBack = newBack.Pop();
newBackLength--;
if (newFrontLength > newBackLength)
{
newRevs = newRevs.Push(new Lazy<ImmutableStack<T>>(() => Reverse(Front)));
newBackLength += newFrontLength;
newFront = ImmutableStack<T>.Empty;
newFrontLength = 0;
}
return new AmortizedConstantTimeImmutableQueue<T>(newFrontLength, newFront, newBackLength, newBack, newRevs);
}
public AmortizedConstantTimeImmutableQueue<T> Enqueue(T value)
{
var newFrontLength = FrontLength;
var newFront = Front;
var newBackLength = BackLength;
var newBack = Back;
var newRevs = ReversingImmutableStacks;
newFront = newFront.Push(value);
newFrontLength++;
if (newFrontLength > newBackLength)
{
newRevs = newRevs.Push(new Lazy<ImmutableStack<T>>(() => Reverse(Front)));
newBackLength += newFrontLength;
newFront = ImmutableStack<T>.Empty;
newFrontLength = 0;
}
return new AmortizedConstantTimeImmutableQueue<T>(newFrontLength, newFront, newBackLength, newBack, newRevs);
}
internal ImmutableStack<T> Reverse(ImmutableStack<T> f)
{
var r = ImmutableStack<T>.Empty;
for (; !f.IsEmpty; f = f.Pop())
{
r = r.Push(f.Peek());
}
return r;
}
public T Peek()
{
throw new NotImplementedException();
}
public IEnumerator<T> GetEnumerator()
{
throw new NotImplementedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
IImmutableQueue<T> IImmutableQueue<T>.Clear()
{
throw new NotImplementedException();
}
IImmutableQueue<T> IImmutableQueue<T>.Dequeue()
{
throw new NotImplementedException();
}
IImmutableQueue<T> IImmutableQueue<T>.Enqueue(T value)
{
throw new NotImplementedException();
}
T IImmutableQueue<T>.Peek()
{
throw new NotImplementedException();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
throw new NotImplementedException();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment