YiPriorityQueue.h

Go to the documentation of this file.

// © You i Labs Inc. 2000-2017. All rights reserved.
#ifndef _YI_PRIORITY_QUEUE_H_
#define _YI_PRIORITY_QUEUE_H_

#include "framework/YiPredef.h"

enum YI_PRIORITY_QUEUE_PRIORITY
{
    YI_PRIORITY_QUEUE_HIGHEST = 2,
    YI_PRIORITY_QUEUE_HIGH = 1,
    YI_PRIORITY_QUEUE_NORMAL = 0,
    YI_PRIORITY_QUEUE_LOW = -1,
    YI_PRIORITY_QUEUE_LOWEST = -2,

    YI_PRIORITY_QUEUE_DEFAULT = YI_PRIORITY_QUEUE_NORMAL
};

template<typename YI_PRIORITY_QUEUE_ITEM, class YI_PRIORITY_QUEUE_ALLOCATOR = std::allocator<std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> > >
class CYIPriorityQueue
{
public:
    typedef std::list<std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>, YI_PRIORITY_QUEUE_ALLOCATOR> YI_PRIORITY_QUEUE_CLASS;
    typedef typename YI_PRIORITY_QUEUE_CLASS::iterator iterator;
    typedef typename YI_PRIORITY_QUEUE_CLASS::const_iterator const_iterator;
    typedef typename YI_PRIORITY_QUEUE_CLASS::reverse_iterator reverse_iterator ;
    typedef typename YI_PRIORITY_QUEUE_CLASS::const_reverse_iterator const_reverse_iterator ;

    CYIPriorityQueue()
    {
    }

    virtual ~CYIPriorityQueue()
    {
    }

    /*******************************************************************************************
     * Iterators
     *******************************************************************************************/

    iterator Begin()
    {
        return m_priorityQueue.begin();
    }

    const_iterator Begin() const
    {
        return m_priorityQueue.begin();
    }

    reverse_iterator ReverseBegin()
    {
        return m_priorityQueue.rbegin();
    }

    const_reverse_iterator ReverseBegin() const
    {
        return m_priorityQueue.rbegin();
    }

    iterator End()
    {
        return m_priorityQueue.end();
    }

    const_iterator End() const
    {
        return m_priorityQueue.end();
    }

    reverse_iterator ReverseEnd()
    {
        return m_priorityQueue.rend();
    }

    const_reverse_iterator ReverseEnd() const
    {
        return m_priorityQueue.rend();
    }

    /*******************************************************************************************
     * Capacity
     *******************************************************************************************/

    int32_t Count(YI_PRIORITY_QUEUE_PRIORITY ePriority) const
    {
        int32_t nCount = 0;
        const_iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end)
        {
            if((*it).first == ePriority)
            {
                ++nCount;
            }
            ++it;
        }
        return nCount;
    }

    int32_t Count(const YI_PRIORITY_QUEUE_ITEM &item) const
    {
        int32_t nCount = 0;
        const_iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end)
        {
            if((*it).second == item)
            {
                ++nCount;
            }
            ++it;
        }
        return nCount;
    }

    int32_t Count(const YI_PRIORITY_QUEUE_ITEM &item, YI_PRIORITY_QUEUE_PRIORITY ePriority) const
    {
        int32_t nCount = 0;
        const_iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end)
        {
            if(it->first == ePriority && it->second == item)
            {
                ++nCount;
            }
            ++it;
        }
        return nCount;
    }

    int32_t Count() const
    {
        return (int32_t)m_priorityQueue.size();
    }

    bool IsEmpty() const
    {
        return m_priorityQueue.empty();
    }

    /*******************************************************************************************
     * Element Access
     *******************************************************************************************/

    iterator Find(YI_PRIORITY_QUEUE_PRIORITY ePriority)
    {
        iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end && (*it).first != ePriority)
        {
            ++it;
        }
        return it;
    }

    const_iterator Find(YI_PRIORITY_QUEUE_PRIORITY ePriority) const
    {
        const_iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end && (*it).first != ePriority)
        {
            ++it;
        }
        return it;
    }

    iterator Find(const YI_PRIORITY_QUEUE_ITEM &item)
    {
        iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end && (*it).second != item)
        {
            ++it;
        }
        return it;
    }

    const_iterator Find(const YI_PRIORITY_QUEUE_ITEM &item) const
    {
        const_iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end && (*it).second != item)
        {
            ++it;
        }
        return it;
    }

    iterator Find(const YI_PRIORITY_QUEUE_ITEM &item, YI_PRIORITY_QUEUE_PRIORITY ePriority)
    {
        return std::find(m_priorityQueue.begin(), m_priorityQueue.end(), std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, item));
    }

    const_iterator Find(const YI_PRIORITY_QUEUE_ITEM &item, YI_PRIORITY_QUEUE_PRIORITY ePriority) const
    {
        return std::find(m_priorityQueue.begin(), m_priorityQueue.end(), std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, item));
    }

    template<class YI_PREDICATE>
    iterator Find(YI_PREDICATE predicate)
    {
        iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end)
        {
            const std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> &item = (*it);
            if(predicate(item.second, item.first))
            {
                break;
            }
            else
            {
                ++it;
            }
        }
        return it;
    }

    template<class YI_PREDICATE>
    const_iterator Find(YI_PREDICATE predicate) const
    {
        const_iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end)
        {
            const std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> &item = (*it);
            if(predicate(item.second, item.first))
            {
                break;
            }
            else
            {
                ++it;
            }
        }
        return it;
    }

    bool Contains(YI_PRIORITY_QUEUE_PRIORITY ePriority) const
    {
        return Find(ePriority) != m_priorityQueue.end();
    }

    bool Contains(const YI_PRIORITY_QUEUE_ITEM &item) const
    {
        return Find(item) != m_priorityQueue.end();
    }

    bool Contains(const YI_PRIORITY_QUEUE_ITEM &item, YI_PRIORITY_QUEUE_PRIORITY ePriority) const
    {
        return Find(item, ePriority) != m_priorityQueue.end();
    }

    template<class YI_PREDICATE>
    bool Contains(YI_PREDICATE predicate) const
    {
        return Find(predicate) != m_priorityQueue.end();
    }

    YI_PRIORITY_QUEUE_ITEM &Head()
    {
        return m_priorityQueue.front().second;
    }

    const YI_PRIORITY_QUEUE_ITEM &Head() const
    {
        return m_priorityQueue.front().second;
    }

    /*******************************************************************************************
     * Modifiers
     *******************************************************************************************/

    void Clear()
    {
        m_priorityQueue.clear();
    }

    YI_PRIORITY_QUEUE_ITEM Dequeue()
    {
        YI_PRIORITY_QUEUE_ITEM item(std::move(m_priorityQueue.front().second));
        m_priorityQueue.pop_front();
        return item;
    }
    
    void Enqueue(YI_PRIORITY_QUEUE_ITEM item, YI_PRIORITY_QUEUE_PRIORITY ePriority = YI_PRIORITY_QUEUE_DEFAULT)
    {
        iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end && (*it).first >= ePriority)
        {
            ++it;
        }

        if(it == end)
        {
            m_priorityQueue.push_back(std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, std::move(item)));
        }
        else
        {
            m_priorityQueue.insert(it, std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, std::move(item)));
        }
    }

    void Push(YI_PRIORITY_QUEUE_ITEM item, YI_PRIORITY_QUEUE_PRIORITY ePriority = YI_PRIORITY_QUEUE_DEFAULT)
    {
        iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end && (*it).first > ePriority)
        {
            ++it;
        }

        if(it == end)
        {
            m_priorityQueue.push_back(std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, std::move(item)));
        }
        else
        {
            m_priorityQueue.insert(it, std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, std::move(item)));
        }
    }

    iterator Remove(iterator it)
    {
        return m_priorityQueue.erase(it);
    }

    bool Remove(YI_PRIORITY_QUEUE_PRIORITY ePriority)
    {
        iterator it = Find(ePriority);
        bool bFound = it != m_priorityQueue.end();
        if(bFound)
        {
            m_priorityQueue.erase(it);
        }
        return bFound;
    }


    bool Remove(const YI_PRIORITY_QUEUE_ITEM &item)
    {
        iterator it = Find(item);
        bool bFound = it != m_priorityQueue.end();
        if(bFound)
        {
            m_priorityQueue.erase(it);
        }
        return bFound;
    }

    bool Remove(const YI_PRIORITY_QUEUE_ITEM &item, YI_PRIORITY_QUEUE_PRIORITY ePriority)
    {
        iterator it = Find(item, ePriority);
        bool bFound = it != m_priorityQueue.end();
        if(bFound)
        {
            m_priorityQueue.erase(it);
        }
        return bFound;
    }

    void RemoveAll(YI_PRIORITY_QUEUE_PRIORITY ePriority)
    {
        m_priorityQueue.remove_if(IsPriority(ePriority));
    }

    void RemoveAll(const YI_PRIORITY_QUEUE_ITEM &item)
    {
        m_priorityQueue.remove_if(IsItem(item));
    }

    void RemoveAll(const YI_PRIORITY_QUEUE_ITEM &item, YI_PRIORITY_QUEUE_PRIORITY ePriority)
    {
        m_priorityQueue.remove(std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM>(ePriority, item));
    }

    template<class YI_PREDICATE>
    void RemoveAll(YI_PREDICATE predicate)
    {
        iterator it(m_priorityQueue.begin()), end(m_priorityQueue.end());
        while(it != end)
        {
            std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> item = (*it);
            if(predicate(item.second, item.first))
            {
                it = Remove(it);
            }
            else
            {
                ++it;
            }
        }

    }

    void Merge(CYIPriorityQueue<YI_PRIORITY_QUEUE_ITEM, YI_PRIORITY_QUEUE_ALLOCATOR> &rOther)
    {
        m_priorityQueue.merge(rOther.m_priorityQueue, IsLessThan());
    }

    void Swap(CYIPriorityQueue<YI_PRIORITY_QUEUE_ITEM, YI_PRIORITY_QUEUE_ALLOCATOR> &rOther)
    {
        m_priorityQueue.swap(rOther.m_priorityQueue);
    }

private:
    /* STL Predicate Functor */
    class IsPriority
    {
        YI_PRIORITY_QUEUE_PRIORITY m_priority;
    public:
        IsPriority(YI_PRIORITY_QUEUE_PRIORITY priority) : m_priority(priority)
        {
        }
        bool operator()(const std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> &rValue)
        {
            return m_priority == rValue.first;
        }
    };

    /* STL Predicate Functor */
    class IsItem
    {
        const YI_PRIORITY_QUEUE_ITEM &m_rItem;
    public:
        IsItem(const YI_PRIORITY_QUEUE_ITEM &rItem) : m_rItem(rItem)
        {
        }
        bool operator()(const std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> &rValue)
        {
            return m_rItem == rValue.second;
        }
    };

    /* STL Compare Functor */
    class IsLessThan
    {
    public:
        bool operator()(const std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> &rLHS, const std::pair<YI_PRIORITY_QUEUE_PRIORITY, YI_PRIORITY_QUEUE_ITEM> &rRHS)
        {
            // we use a "greater than" comparison because higher priority enum values are assigned higher numbers
            return rLHS.first > rRHS.first;
        }
    };

    YI_PRIORITY_QUEUE_CLASS m_priorityQueue;
};

#endif /* _YI_PRIORITY_QUEUE_H_ */