IterableBinaryHeap

//////////////////////////////////////////////////////////////////////
/// This file is subject to the terms and conditions defined in    ///
/// file 'LICENSE.txt', which is part of this source code package. ///
//////////////////////////////////////////////////////////////////////
module org.ghrum.utilities.container.iterable_binary_heap;

////////////////////////////////////////////////////////////////
/// IMPORT                                                   ///
////////////////////////////////////////////////////////////////
public import std.algorithm;
public import std.range;
public import std.exception;
public import std.typecons;
public import std.functional : binaryFun;

////////////////////////////////////////////////////////////////
/// \brief Node of a IterableBinaryHeap
////////////////////////////////////////////////////////////////
private struct IterableNode(T)
{
    ////////////////////////////////////////////////////////////
    ///!< Underlying container of the node
    ////////////////////////////////////////////////////////////
    T _container;

    ////////////////////////////////////////////////////////////
    ///!< Length of the node
    ////////////////////////////////////////////////////////////
    size_t _length;
}

////////////////////////////////////////////////////////////////
/// \brief Represent a binary heap that can be iterate
////////////////////////////////////////////////////////////////
public struct IterableBinaryHeap(T, alias op = "a < b")
    if (isRandomAccessRange!(T) || isRandomAccessRange!(typeof(T.init[]))) {
private:
    ////////////////////////////////////////////////////////////
    /// \brief The compare binary function
    ////////////////////////////////////////////////////////////
    alias binaryFun!(op) Compare;
public:
    ////////////////////////////////////////////////////////////
    /// \brief Constructor of a iterable binary heap
    ///
    /// \param container   The container to take ownership
    /// \param initialSize The initial size of the heap
    ////////////////////////////////////////////////////////////
    this(T container, size_t initialSize = size_t.max)
    {
        acquire(container, initialSize);
    }

    ////////////////////////////////////////////////////////////
    /// \brief Takes ownership of a container.
    ///
    /// \param container   The container to take ownership
    /// \param initialSize The initial size of the heap
    ////////////////////////////////////////////////////////////
    void acquire(T container, size_t initialSize = size_t.max)
    {
        _payload.refCountedStore.ensureInitialized();
        _payload._container = move(container);
        _payload._length = min(_payload._container.length, initialSize);

        if (_payload._length < 2)
        {
            return;
        }

        for (auto i = (_payload._length - 2) / 2;i > 0; --i)
            percolateDown(_payload._container, i, _payload._length);
    }

    ////////////////////////////////////////////////////////////
    /// \brief Takes ownership of a container assuming it was
    ///        already organized as a heap
    ///
    /// \param container   The container to take ownership
    /// \param initialSize The initial size of the heap
    ////////////////////////////////////////////////////////////
    void assume(T container, size_t initialSize = size_t.max)
    {
        _payload.refCountedStore.ensureInitialized();
        _payload._container = container;
        _payload._length = min(_payload._container.length, initialSize);
    }

    ////////////////////////////////////////////////////////////
    /// \brief Release the heap
    ///
    /// \return The portion of the heap from 0 ... length
    ////////////////////////////////////////////////////////////
    auto release()
    {
        if (_payload.refCountedStore.isInitialized)
        {
            auto result = _payload._container[0 .. _payload._length];
            _payload = _payload.init;
            return result;
        }
        else
            return typeof(_payload._container[0 .. _payload._length]).init;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Returns if the heap is empty
    ///
    /// \return True if the heap is empty
    ////////////////////////////////////////////////////////////
    @property
    bool empty() const
    {
        return !_payload._length;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Return a clone of this heap
    ///
    /// \return A clone of this heap
    ////////////////////////////////////////////////////////////
    @property
    IterableBinaryHeap dup()
    {
        IterableBinaryHeap!(T, op) result;
        if (_payload.refCountedStore.isInitialized)
        {
            result.assume(_payload._container.dup, _payload._length);
        }
        return result;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Return the capacity of the underlying buffer
    ///
    /// \return The capacity of the underlying buffer
    ////////////////////////////////////////////////////////////
    @property
    size_t capacity() const
    {
        if (!_payload.refCountedStore.isInitialized)
            return 0;

        static if (is(typeof(_payload._container.capacity) : size_t))
            return _payload._container.capacity;
        else
            return _payload._container.length;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Return a copy of the front item
    ///
    /// \return A copy of the front item
    ////////////////////////////////////////////////////////////
    @property
    ElementType!T front()
    in
    {
        enforce( !empty );
    }
    body
    {
        return _payload._container.front;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Clears the heap by deattaching the underlying
    ///        buffer
    ////////////////////////////////////////////////////////////
    void clear()
    {
        _payload = _payload.init;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Insert a new element into the heap
    ///
    /// \param item The item to insert to
    ////////////////////////////////////////////////////////////
    void insert(ElementType!T item)
    {
        static if (is(typeof(_payload._container.insertBack(item))))
        {
            _payload.refCountedStore.ensureInitialized();

            if (_payload._length == _payload._container.length)
                _payload._container.insertBack(item);
            else
                _payload._container[_payload._length] = item;
        }
        else
        {
            enforce(_payload._length < _payload._container.length,
                "Cannot grow a heap created over a range");
            _payload._container[_payload._length] = item;
        }

        for(size_t i = (_payload._length),
                   j = (_payload._length - 1) / 2; i; j = (i - 1) / 2)
        {
            if (!Compare(_payload._container[j], _payload._container[i]))
                break;

            swap(_payload._container, j, i);
            i = j;
        }
        ++_payload._length;
    }

    ////////////////////////////////////////////////////////////
    /// \brief Removes the largest element from the heap
    ////////////////////////////////////////////////////////////
    void removeFront()
    in
    {
        enforce( !empty );
    }
    body
    {
        if (_payload._length > 1)
        {
            auto p1 = moveFront(_payload._container[]);
            auto p2 = moveAt(_payload._container, _payload._length - 1);
            _payload._container.front = move(p2);
            _payload._container[_payload._length - 1] = move(p1);
        }
        --_payload._length;
        percolateDown(_payload._container, 0, _payload._length);
    }

    ////////////////////////////////////////////////////////////
    /// \brief Removes the largest element from the heap and
    ///        return a copy of it
    ///
    /// \return The copy of the removed item
    ////////////////////////////////////////////////////////////
    ElementType!T removeAny()
    {
        removeFront();
        return _payload._container[_payload._length];
    }

    ////////////////////////////////////////////////////////////
    /// \brief Replaces the largest element in the container
    ///
    /// \param item The new item to place the old item
    ////////////////////////////////////////////////////////////
    void replaceFront(ElementType!T item)
    in
    {
        assert( !empty );
    }
    body
    {
        _payload._container.front = item;
        percolateDown(_payload._container, 0, _payload._length);
    }

    ////////////////////////////////////////////////////////////
    /// \brief Returns the size of the underlying buffer
    ///
    /// \return The size of the underlying buffer
    ////////////////////////////////////////////////////////////
    @property
    size_t length() const
    {
        return _payload.refCountedStore.isInitialized ? _payload._length : 0;
    }

    int opApply(int delegate(ref ElementType!T) callback)
    {
        int result = 0;
        foreach(item; _payload._container)
        {
            result += callback(item);
        }
        return result;
    }
private:
    ////////////////////////////////////////////////////////////
    /// \brief Percolates the heap down such the heap property is
    ///        restored
    ///
    /// \param container The underlying buffer
    /// \param index     The index of the item
    /// \param length    The length of the buffer
    ////////////////////////////////////////////////////////////
    static void percolateDown(T container, size_t index, size_t length)
    {
        bool isDone = false;
        do
        {
            auto left  = index * 2 + 1;
            auto right = left + 1;

            if (right == length)
            {
                if (Compare(container[index], container[left]))
                    swap(container, index, left);
                isDone = true;
            }
            else if(right > length)
            {
                isDone = true;
            }
            else
            {
                auto largest = Compare(container[index], container[left])
                    ? (Compare(container[left], container[right])
                            ? right : left)
                    : (Compare(container[index], container[right])
                            ? right : index);
                if (largest != index)
                {
                    swap(container, index, largest);
                    index = largest;
                }
                else
                    isDone = true;
            }
        } while (!isDone);
    }

    ////////////////////////////////////////////////////////////
    /// \brief Swap index in a container
    ///
    /// \param container The underlying container
    /// \param index     The index within the container
    /// \param item      The item within the container
    ////////////////////////////////////////////////////////////
    static void swap(T container, size_t index, size_t item)
    {
        static if (is(typeof(container.moveAt(index))) ||
                  !is(typeof(swap(container[index], container[item]))))
        {
            auto p1 = container.moveAt(index);
            auto p2 = container.moveAt(item);
            container[index] = move(p2);
            container[item] = move(p1);
        }
        else
            swap(container[index], container[item]);
    }
private:
    ////////////////////////////////////////////////////////////
    ///!< Payload of the heap
    ////////////////////////////////////////////////////////////
    RefCounted!(IterableNode!(T), RefCountedAutoInitialize.no) _payload;
}