container implementation in D

deque.d

module deque;

import core.exception : RangeError;

struct Deque(T)
{
private:

    T[] deque;
    size_t begin, end; // inclusive lower and exclusive upper bound

    pure void check_emptiness()
    {
        if (empty)
        {
            throw new RangeError("Deque is empty");
        }
    }

public:

    pure @property bool empty()
    {
        return begin == end;
    }

    pure @property size_t length()
    {
        return end - begin;
    }

    pure T front()
    {
        check_emptiness();
        return deque[begin];
    }

    pure T back()
    {
        check_emptiness();
        return deque[end - 1];
    }

    T popReturnFront()
    {
        T pop = front();
        begin += 1;
        return pop;
    }

    void popFront()
    {
        check_emptiness();
        begin += 1;
    }

    T popReturnBack()
    {
        T pop = back();
        end -= 1;
        return pop;
    }

    void popBack()
    {
        check_emptiness();
        end -= 1;
    }

    void pushFront(T value)
    {
        if (begin == 0)
        {
            balance();
        }
        begin -= 1;
        deque[begin] = value;
    }

    void pushBack(T value)
    {
        if (end == deque.length)
        {
            balance();
        }
        deque[end] = value;
        end += 1;
    }

    void balance()
    {
        debug
        {
            import std.stdio;
            writef("deque: balance (%d, %d, %d) -> ", begin, end, deque.length);
        }
        auto count = end - begin;
        T[] empty_part;
        empty_part.length = (count >> 1) + 1;
        deque = empty_part ~ deque[begin..end].dup ~ empty_part;
        begin = empty_part.length;
        end = begin + count;
        debug
        {
            import std.stdio;
            writefln("(%d, %d, %d)", begin, end, deque.length);
        }
    }

    void reduce()
    {
        deque = deque[begin..end].dup;
        end -= begin;
        begin = 0;
    }

}

queue.d

module queue;

import core.exception : RangeError;

struct Queue(T)
{
private:

    T[] queue;
    size_t begin, end;

    pure void check_emptiness()
    {
        if (empty)
        {
            throw new RangeError("Queue is empty");
        }
    }

    void check_half_emptiness()
    {
        if (queue.length / 2 < begin)
        {
            debug 
            {
                import std.stdio;
                writefln("queue: move %d / %d", length(), queue.length);
            }
            auto l = queue.length;
            queue = queue[begin..end].dup;
            queue.length = l;
            end -= begin;
            begin = 0;
        }
    }

public:

    pure @property bool empty()
    {
        return begin == end;
    }

    pure @property size_t length()
    {
        return end - begin;
    }

    pure T front()
    {
        check_emptiness();
        return queue[begin];
    }

    void popFront()
    {
        begin += 1;
        check_half_emptiness();
    }

    T pop()
    {
        check_emptiness();
        T pop = queue[begin];
        begin += 1;
        check_half_emptiness();
        return pop;
    }

    alias push put;

    void push(T value)
    {
        if (queue.length <= end)
        {
            debug 
            {
                import std.stdio;
                writefln("queue: expand %d -> %d", queue.length, queue.length * 2 + 1);
            }
            queue.length = queue.length * 2 + 1;
        }
        queue[end] = value;
        end += 1;
    }

    void reduce()
    {
        queue = queue[begin..end].dup;
        end -= begin;
        begin = 0;
    }
}

stack.d

module stack;

import core.exception : RangeError;

struct Stack(T)
{
private:

    T[] stack;
    size_t count;

    pure void check_emptiness()
    {
        if (empty)
        {
            throw new RangeError("Stack is empty");
        }
    }

public:

    pure @property bool empty()
    {
        return count == 0;
    }

    pure @property size_t length()
    {
        return count;
    }

    alias top front;

    pure T top()
    {
        check_emptiness();
        return stack[count - 1];
    }

    T pop()
    {
        popFront();
        return stack[count];
    }

    alias push put;

    pure void popFront()
    {
        check_emptiness();
        count -= 1;
    }

    void push(T value)
    {
        if (count == stack.length)
        {
            debug
            {
                import std.stdio;
                writefln("stack: expand %d -> %d", stack.length, stack.length * 2 + 1);
            }
            stack.length = stack.length * 2 + 1;
        }
        stack[count] = value;
        count += 1;
    }

    void reduce()
    {
        stack.length = count;
    }
}