償却O(1)永続Queue.cs

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();
    }
}