circulararray.d

/++
Circular buffer implementation.

See_Also: http://en.wikipedia.org/wiki/Circular_buffer

Authors: Simen Endsjø <simendsjo@gmail.com>
Copyright: Simen Endsjø 2013
License: Boost 1.0 (http://www.boost.org/LICENSE_1_0.txt)
+/
module simendlib.circulararray;

import std.algorithm : chain, equal;
import std.exception : enforce;

debug import std.stdio;

/++
Two-way resizeable circular buffer.

Can be used as both a FIFO (first-in first-out) and FILO (first-in last-out)
structure. It's primarily meant as a FIFO structure as FILO is easy with
a regular array.

This makes it a good fit as both a queue and a deque.

See_Also:
  http://en.wikipedia.org/wiki/Circular_buffer
  http://en.wikipedia.org/wiki/Double-ended_queue

Wasted_space:
  It uses an empty slot internally to see when the array is empty and when it is
  full. This means that for short circular buffers where T.sizeof is large, there
  might be too much wasted space.

Using_as_FIFO_(Queue):
       pushBack, front, popFront
  $(BR)or
  $(BR)pushFront, back, popBack

Using_as_FILO_(Stack):
       pushFront, front, popFront
  $(BR)or
  $(BR)pushBack, back, popBack

Example:
---
auto buf = CircularBuffer!(int, len => 2*len)(2);
buf.pushBack(1);
buf.pushBack(2);
assert(buf.walk.equal([1, 2]);
buf.popFront();
assert(buf.walk.equal([2]);
buf.pushBack(3); // wrapped around
assert(buf.walk.equal([2, 3]);
buf.pushBack(4); // might reallocate if the underlying capacity is met
---

Params:
  T         = The element type
  newSizeDg = A "size_t delegate(size_t current_length)" that computes the new
              size of the underlying array when it needs to be resized due to
              pushing elements to the array. The result should always be
              greater than the length passed in, thus this method have to check
              for overflow.
+/
final class CircularArray(T, alias newSizeDg)
{
    /++
    Constructs a buffer with at least size capacity.
    +/
    this(size_t size) pure nothrow @safe
    {
        _buf = new T[size+1];
        useAllAvailableSpace(_buf);
    }

    @property
    {
        /++
        Returns the number of elements we can store.

        Note that this is 1 less than the underlying data used as we're using an
        empty slot interally.

        capacity-length will return the number of items we can store before we
        need a resize.
        +/
        size_t capacity() const pure nothrow @trusted
        {
            return _buf.capacity() - 1;
        }

        /// Returns number of elements in the buffer
        size_t length() const pure nothrow @safe
        {
            return _end < _start ? _end + _buf.length-_start : _end - _start;
        }

        /// True if there are no elements in the buffer
        bool empty() const pure nothrow @safe
        {
            return _start == _end;
        }

        /++
        Returns an element from the underlying buffer.

        Front will return the leftmost element, while back will return the
        rightmost element.

        If there is only one item in the list, both front and back will refer
        to the same element.

        Thows an exception if there are no items.
        Returns a reference to the item.
        +/
        auto ref front() const pure @safe
        {
            enforce(!empty);
            return _buf[_start];
        }

        /// ditto
        auto ref back() const pure @safe
        {
            enforce(!empty);
            return _buf[lastIndex];
        }

        /++
        Returns a range for traversing the underlying items

        This is not thread-safe. Any changes to the buffer while walking might
        yield unexpected results.

        To walk in reverse order, use std.algorithm.retro
        +/
        auto walk() @trusted // BUG: cannot be pure or nothrow because of chain
        {
            if(empty)
            {
                return chain(cast(T[])[], cast(T[])[]);
            }
            else if(_start < _end) // continous block of items
            {
                return chain(_buf[_start.._end], cast(T[])[]);
            }
            else // first part is last in the array
            {
                T[] pre  = _buf[_start..$];
                T[] post = _buf[0.._end];
                return chain(pre, post);
            }
            assert(false);
        }

    }

    /++
    Returns the element at index i.
    Throws an exception if i is out of bounds.
    +/
    auto ref opIndex(size_t i) pure @safe
    {
        enforce(i < length);
        immutable ri = (_start+i)%_buf.length;
        assert(ri >= 0 && ri < _buf.length);
        return _buf[ri];
    }

    /++
    Replace a value at index i.
    Throws an exception if i is out of bounds.
    +/
    void opIndexAssign(T value, size_t i) pure @safe
    {
        opIndex(i) = value;
    }

    /++
    Push an item to the buffer. The array is resized if necessary.

    pushFront is also called prepend. pushBack is also called append
    +/
    void pushFront(T value) pure nothrow @safe
    {
        if(length == capacity)
            resize();
        _start = _start == 0 ? _buf.length-1 : _start-1;
        _buf[_start] = value;
    }

    /// ditto
    void pushBack(T value) pure nothrow @safe
    {
        _buf[_end++] = value;
        if(empty || _end == _buf.length)
            resize();
    }

    /// Removes an element from the buffer
    void popFront() pure @safe
    {
        enforce(!empty);
        _buf[_start] = T.init;
        if(++_start == _buf.length)
            _start = 0;
    }

    /// ditto
    void popBack() pure @safe
    {
        enforce(!empty);
        _end = lastIndex;
        _buf[_end] = T.init;
    }

    /++
    Will resize the underlying array to the smallest possible size to fit all
    elements in the buffer.
    +/
    void compact() pure nothrow @safe
    {
        resize(length);
    }

    override string toString() @trusted
    {
        import std.conv : to;
        return walk.to!string();
    }

private:
    T[] _buf = void;
    // inclusive start index
    size_t _start;
    // exclusive end index
    size_t _end;

    static void useAllAvailableSpace(ref T[] buf) pure nothrow @trusted
    {
        // We need to move elements when extending the array, so there is no
        // reason not to use the entire memory segment we got. This reduces
        // copying.
        buf.length = buf.capacity();
    }

    // Returns the index of the last element
    size_t lastIndex() const pure nothrow @safe
    {
        assert(!empty, "Cannot get last element index. Array is empty.");
        return _end == 0 ? _buf.length - 1 : _end - 1;
    }

    void resize() pure nothrow @trusted
    {
        resize(newSizeDg(length));
    }

    void resize(size_t newSize) pure nothrow @trusted
    in
    {
        assert(newSize >= length,
                "Not enough room for elements in newly resized array.");
        assert(_buf.length == _buf.capacity,
                "Internal buffer doesn't use the existing capacity");
    }
    out
    {
        assert(_buf.length == _buf.capacity);
        assert(_buf.length >= newSize+1);
        assert(_start == 0);
        assert(_end == length);
    }
    body
    {
        // To avoid copying twice, we'll create a new array rather than just
        // adjusting the length.
        auto arr = new T[newSize+1];
        useAllAvailableSpace(arr);
        if(!empty)
        {
            if(_start < _end) // continous block of items
            {
                arr[0..this.length] = _buf[_start.._end][];
            }
            else // first part is last in the array
            {
                const pre = _buf[_start..$];
                arr[0..pre.length][] = pre[];
                arr[pre.length..this.length][] = _buf[0.._end][];
            }
        }
        _end = length;
        _start = 0;
        _buf = arr;
    }
}

unittest
{
    import std.array : array;

    auto buf = new CircularArray!(int, l => 2*l)(2);
    assert(buf.length == 0);
    assert(buf.capacity >= 2);
    assert(buf.walk.empty);

    buf.pushFront(1);
    assert(buf.length == 1);
    assert(buf.capacity >= 2);
    assert(buf.front == 1);
    assert(buf.back == 1);
    assert(buf.front is buf.back);
    assert(buf.walk.equal([1]));

    buf.pushFront(2);
    assert(buf.length == 2);
    assert(buf.front == 2);
    assert(buf.back == 1);
    assert(buf.walk.equal([2, 1]));

    buf.pushFront(3);
    assert(buf.walk.equal([3, 2, 1]));

    buf.pushBack(4);
    assert(buf.walk.equal([3, 2, 1, 4]));
    buf.popFront();
    assert(buf.walk.equal([2, 1, 4]));
    buf.popBack();
    assert(buf.walk.equal([2, 1]));
    buf.popBack();
    buf.popBack();
    assert(buf.empty);

    immutable oldCap = buf.capacity;
    buf.compact();
    assert(buf.capacity < oldCap);

    assert(buf.empty);
    assert(buf.length == 0);
    buf.pushBack(1);
    buf.pushBack(2);
    buf.pushBack(3);
    assert(buf[0] == 1);
    assert(buf[1] == 2);
    assert(buf[2] == 3);
    buf[0] = 10;
    buf[1] = 20;
    buf[2] = 30;
    assert(buf[0] == 10);
    assert(buf[1] == 20);
    assert(buf[2] == 30);
}