PriorityList.hpp

#pragma once
#ifndef __H__OCULAR_UTILS_PRIORITY_LIST__H__
#define __H__OCULAR_UTILS_PRIORITY_LIST__H__

#include "Exceptions/Exception.hpp"
#include "Priority.hpp"

#include <utility>
#include <cstdint>

//------------------------------------------------------------------------------------------

namespace Ocular
{
    namespace Utils
    {
        template<typename T, std::size_t MAX_ELEMENTS>
        class PriorityList
        {
        public:

            PriorityList()
            {
                m_TrueSize = 0;
            }

            ~PriorityList()
            {

            }

            bool push(T const element, uint32_t priority)
            {
                bool retVal = false;

                if(m_TrueSize < MAX_ELEMENTS)
                {
                    retVal = add(element, priority);
                }

                return retVal;
            }

            bool pop()
            {
                bool retVal = false;

                if(m_TrueSize > 0)
                {
                    removeIndex(0);
                    retVal = true;
                }

                return retVal;
            }

            bool add(T const element, uint32_t priority)
            {
                bool result = false;

                if(m_TrueSize < MAX_ELEMENTS)
                {
                    insertElement(element, static_cast<uint32_t>(priority));
                    m_TrueSize++;
                    result = true;
                }

                return result;
            }

            void removeElement(T const element)
            {
                if(m_TrueSize > 0)
                {
                    std::size_t index = locateIndex(element);

                    if(index != MAX_ELEMENTS)
                    {
                        deleteElement(index);
                        m_TrueSize--;
                    }
                }
            }

            void removeIndex(uint32_t index)
            {
                if(index >= m_TrueSize)
                {
                    THROW_EXCEPTION("Index Out of Bounds");
                }

                deleteElement(index);
                m_TrueSize--;
            }

            T const get(std::size_t index) const
            {
                if(index >= m_TrueSize)
                {
                    THROW_EXCEPTION("Index Out of Bounds");
                }

                return m_Array[index].first;
            }

            std::size_t size() const
            {
                return m_TrueSize;
            }

            std::size_t maxSize() const
            {
                return MAX_ELEMENTS;
            }

            bool empty() const 
            {
                return (m_TrueSize == 0);
            }

            bool contains(T const element) const
            {
                std::size_t index = locateIndex(element);
                return (index != MAX_ELEMENTS);
            }

            void clear() 
            {
                while(size() > 0)
                {
                    removeIndex(0);
                }
            }

        protected:

            void insertElement(T const element, uint32_t const priority)
            {
                std::size_t index = findIndex(priority);

                shiftRight(index);
                m_Array[index] = std::pair<T, uint32_t>(element, priority);
            }

            void deleteElement(std::size_t const index)
            {
                //m_Array[index].first = 0;
                shiftLeft(index);
            }

            void shiftLeft(std::size_t const index)
            {
                // Effectively does the following (shiftLeft(3)):
                //
                //          [0][1][2][3][4][5][6][7][8][9]
                // Before:  [*][*][*][ ][*][*][*][*][ ][ ]
                //  After:  [*][*][*][*][*][*][*][ ][ ][ ]

                for(std::size_t i = index; i < m_TrueSize - 1; i++)
                {
                    m_Array[i] = m_Array[i + 1];
                }

                //m_Array[m_TrueSize - 1].first = 0;
            }

            void shiftRight(std::size_t const index)
            {
                // Effectively does the following (shiftRight(3)):
                //
                // Before:  [0][1][2][3][4][5][6][ ][ ][ ]
                //  After:  [0][1][2][ ][3][4][5][6][ ][ ]
                
                if(m_TrueSize != MAX_ELEMENTS)
                {
                    for(std::size_t i = m_TrueSize; i > index; i--)
                    {
                        m_Array[i] = m_Array[i - 1];
                    }

                    //m_Array[index].first = 0;
                }
            }

            std::size_t locateIndex(T const element) const
            {
                std::size_t index = MAX_ELEMENTS;

                for(std::size_t i = 0; i < m_TrueSize; i++)
                {
                    if(m_Array[i].first == element)
                    {
                        index = i;
                        break;
                    }
                }

                return index;
            }

            std::size_t findIndex(uint32_t const priority) const
            {
                // If the array is empty, return index 0
                if(m_TrueSize == 0) 
                {
                    return 0;
                }

                // Quick check to see if we should insert at the front
                // or at the back of the list.
                if(priority < m_Array[0].second)
                {
                    return 0;
                }
                else if(priority > m_Array[m_TrueSize - 1].second)
                {
                    return m_TrueSize;
                }

                return binaryFind(priority);
            }

            std::size_t binaryFind(uint32_t const priority) const
            {
                uint32_t upper = static_cast<uint32_t>(m_TrueSize);
                uint32_t index = static_cast<uint32_t>(m_TrueSize / 2);
                uint32_t increment = static_cast<uint32_t>(index / 2);

                // While this could be done in a while(true){}, we
                // place an upper bound on the potential number of
                // iterations to avoid any (unlikely) infinite loops.

                for( ; upper > 0; upper--, increment /= 2)
                {
                    if (increment == 0)
                    {
                        increment = 1;
                    }

                    if(m_Array[index].second == priority)
                    {
                        break;
                    }
                    else if (m_Array[index].second > priority)
                    {
                        // If we are at the front of the list we can not go any further
                        if(index == 0)
                        {
                            break;
                        }

                        index -= increment;
                    }
                    else
                    {
                        // If we are at the end of the list we can not go any further
                        if((index == m_TrueSize) || (index == MAX_ELEMENTS - 1))
                        {
                            break;
                        }

                        index += increment;
                    }
                }

                return index;
            }

        private:

            std::size_t m_TrueSize;    
            //std::array<std::pair<T, uint32_t>, MAX_ELEMENTS> m_Array;
            std::pair<T, std::size_t> m_Array[MAX_ELEMENTS] = {};
        };
    }
}
//------------------------------------------------------------------------------------------

#endif