BinaryHeap.hpp

Go to the documentation of this file.

/*--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants 
Licensee a limited, non-exclusive, non-transferable, royalty-free license 
(without the right to sublicense) to use the API solely for the purpose of 
Licensee's internal development efforts to develop applications for which 
the API was provided.
 
The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: Base
File: BinaryHeap
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/Buffer.h>
namespace NDEVR
{
    /**--------------------------------------------------------------------------------------------------
    \brief  A heap data structure that takes the form of a binary tree which is a common way of 
        implementing priority queues.
     *-----------------------------------------------------------------------------------------------**/
    template<class t_comp_type, class t_value_type, bool t_is_min>
    class BinaryHeap
    {
    public:
        explicit BinaryHeap(uint04 size)
            : m_values(size)
        {}
        void insert(t_comp_type comparison, t_value_type value)
        {
            const uint04 length = m_values.size();
            m_values.add({ value, comparison });
            bubbleUp(length);
        }
        [[nodiscard]] const Buffer<std::pair<t_value_type, t_comp_type>>& values() const
        {
            return m_values;
        }
 
        [[nodiscard]] Buffer<std::pair<t_value_type, t_comp_type>>& values() 
        {
            return m_values;
        }
        [[nodiscard]] t_comp_type extremeComp() const
        {
            return m_values[0].second;
        }
        [[nodiscard]] t_value_type extremeValue() const
        {
            return m_values[0].first;
        }
        void clear() 
        {
            m_values.clear();
        }
        [[nodiscard]] uint04 size() const
        {
            return m_values.size();
        }
        const Buffer<std::pair<t_value_type, t_comp_type>>& getAll() const
        {
            return m_values;
        }
        [[nodiscard]] Buffer<std::pair<t_value_type, t_comp_type>> sortedValues() const
        {
            BinaryHeap heap = *this;
            Buffer<std::pair<t_value_type, t_comp_type>> sorted_values(m_values.size());
            sorted_values.setSize(m_values.size());
            uint04 size = m_values.size();
            for (uint04 i = size - 1; !IsInvalid(i); --i)
            {
                sorted_values[i] = heap.m_values[0];
                heap.deleteExtreme();
            }
            return sorted_values;
        }
        [[nodiscard]] Buffer<t_value_type> sortedIndices() const
        {
            BinaryHeap heap = *this;
            Buffer<t_value_type> sorted_values(m_values.size());
            sorted_values.setSize(m_values.size());
            uint04 size = m_values.size();
            for (uint04 i = size - 1; !IsInvalid(i); --i)
            {
                sorted_values[i] = heap.m_values[0].first;
                heap.deleteExtreme();
            }
            return sorted_values;
        }
        [[nodiscard]] t_value_type replaceExtreme(t_comp_type comparison, t_value_type value) const
        {
            t_value_type extreme = m_values[0];
            m_values[0].first = value;
            m_values[0].second = comparison;
            return extreme;
        }
        [[nodiscard]] t_value_type popExtreme()
        {
            t_value_type extreme = m_values[0].first;
            deleteExtreme();
            return extreme;
        }
        void deleteExtreme()
        {
            m_values[0] = m_values.last();
            m_values.removeLast();
            bubbleDown(0);
        }
    private:
        void bubbleDown(uint04 index)
        {
            const uint04 length = m_values.size();
            for (;;)
            {
                uint04 left_child_index  = (index << 1) + 1U;
                uint04 right_child_index = (index << 1) + 2U;
 
                if (left_child_index >= length)
                    return; //index is a leaf
 
                uint04 min_index = index;
 
                if (Compare(m_values[index].second, m_values[left_child_index].second))
                    min_index = left_child_index;
 
                if ((right_child_index < length) && Compare(m_values[min_index].second, m_values[right_child_index].second))
                    min_index = right_child_index;
 
                if (min_index != index)
                {
                    //need to swap
                    m_values.swapIndices(index, min_index);
                    index = min_index;
                }
                else
                    return;
            }
        }
        void bubbleUp(uint04 index)
        {
            for (;;)
            {
                if (index == 0)
                    return;
                uint04 parent_index = ((index - 1) >> 1);
                if (Compare(m_values[parent_index].second, m_values[index].second))
                {
                    m_values.swapIndices(index, parent_index);
                    index = parent_index;
                }
                else
                    return;
            }
        }
        static bool Compare(t_comp_type a, t_comp_type b) 
        {
            if constexpr (t_is_min)
                return a > b;
            else
                return a < b;
        }
    
    private:
        Buffer<std::pair<t_value_type, t_comp_type>, uint04, ObjectAllocator<true>> m_values;
    };
 
    template<class t_comp_type, class t_value_type>
    using MinHeap = BinaryHeap<t_comp_type, t_value_type, true>;
 
    template<class t_comp_type, class t_value_type>
    using MaxHeap = BinaryHeap<t_comp_type, t_value_type, false>;
}