priorityqueue.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005-2019 by the FIFE team                              *
 *   http://www.fifengine.net                                              *
 *   This file is part of FIFE.                                            *
 *                                                                         *
 *   FIFE is free software; you can redistribute it and/or                 *
 *   modify it under the terms of the GNU Lesser General Public            *
 *   License as published by the Free Software Foundation; either          *
 *   version 2.1 of the License, or (at your option) any later version.    *
 *                                                                         *
 *   This library is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
 *   Lesser General Public License for more details.                       *
 *                                                                         *
 *   You should have received a copy of the GNU Lesser General Public      *
 *   License along with this library; if not, write to the                 *
 *   Free Software Foundation, Inc.,                                       *
 *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA          *
 ***************************************************************************/

#ifndef FIFE_SOLVER_INDEXEDPQ_H
#define FIFE_SOLVER_INDEXEDPQ_H

#include <cassert>
#include <list>

namespace FIFE {

    template<typename index_type, typename priority_type>
    class PriorityQueue {
    public:
        enum Ordering {
            Ascending, 
            Descending 
        };

        typedef std::pair<index_type, priority_type> value_type;

        PriorityQueue(void) : m_ordering(Ascending) {
        }

        PriorityQueue(const Ordering ordering) : m_ordering(ordering) {
        }

        void pushElement(const value_type& element);

        void popElement(void);

        bool changeElementPriority(const index_type& index, const priority_type& newPriority);

        void clear(void);

        const value_type getPriorityElement(void) const {

            assert(!empty());

            return m_elements.front();

        }

        bool empty(void) const {
            return m_elements.empty();
        }

        size_t size(void) const {
            return m_elements.size();
        }
    private:
        typedef std::list<value_type> ElementList;
        typedef typename ElementList::iterator ElementListIt;
        typedef typename ElementList::const_iterator ElementListConstIt;

        //A list of valuetype pairs that represents the pq.
        ElementList m_elements;

        //The order to use when sorting the pq.
        Ordering    m_ordering;

        void orderUp(ElementListIt i);
        void orderUp(const value_type& entry);

        void orderDown(ElementListIt i);

        ElementListIt getElementIterator(const index_type& index) {

            for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i) {
                if(i->first == index) {
                    return i;
                }
            }

            return m_elements.end();

        }

        int32_t compare(const value_type& a, const value_type& b);
    };
}

template<typename index_type, typename priority_type>
void FIFE::PriorityQueue<index_type, priority_type>::pushElement(const value_type& element) {
    if(empty()) {
        m_elements.push_front(element);
    }
    else {
        orderUp(element);
    }
}

template<typename index_type, typename priority_type>
void FIFE::PriorityQueue<index_type, priority_type>::popElement(void) {

    if(!empty()) {
        m_elements.pop_front();
    }

}

template<typename index_type, typename priority_type>
bool FIFE::PriorityQueue<index_type, priority_type>::changeElementPriority(const index_type& index, const priority_type& newPriority) {

    ElementListIt i = getElementIterator(index);

    if(i == m_elements.end()) {
        return false;
    }

    int32_t compare_res = compare(value_type(index, newPriority), (*i));

    i->second = newPriority;

    if(compare_res > 0 &&  i != m_elements.begin()) {
        orderDown(i);
    } else if(compare_res < 0) {
        orderUp(i);
    }

    return true;

}

template<typename index_type, typename priority_type>
void FIFE::PriorityQueue<index_type, priority_type>::clear(void) {

    m_elements.clear();

}

template<typename index_type, typename priority_type>
void FIFE::PriorityQueue<index_type, priority_type>::orderUp(ElementListIt i) {

    assert(i != m_elements.end() && L"Invalid iterator passed to function");

    value_type vt = (*i);

    i = m_elements.erase(i);

    while(i != m_elements.end()) {

        if(compare(vt, (*i)) > 0) {

            m_elements.insert(i, vt);

            return;
        }

        ++i;
    }

    m_elements.push_back(vt);

}

template<class index_type, class priority_type>
void FIFE::PriorityQueue<index_type, priority_type>::orderUp(const value_type& val)
{
    for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i)
    {
        assert(val.first != i->first);

        if(compare(val, (*i)) > 0)
        {
            assert(val.first != i->first);

            m_elements.insert(i, val);

            return;
        }
    }

    m_elements.push_back(val);
}

template<typename index_type, typename priority_type>
void FIFE::PriorityQueue<index_type, priority_type>::orderDown(ElementListIt i) {

    assert(i != m_elements.end());

    value_type vt = (*i);

    i = m_elements.erase(i);

    if(i == m_elements.end()) {
        --i;
    }

    ElementListIt j = i;

    ++j;

    while(i != m_elements.begin()) {
        if(compare(vt, (*i)) < 0) {

            m_elements.insert(j, vt);

            return;
        }

        --i;
        --j;
    }

    m_elements.push_front(vt);
}

template<typename index_type, typename priority_type>
int32_t FIFE::PriorityQueue<index_type, priority_type>::compare(const value_type& a, const value_type& b) {

    if(m_ordering == Descending) {

        if(a.second > b.second) {
            return 1;
        } else if(b.second > a.second) {
            return -1;
        }

    } else {

        if(a.second < b.second) {
            return 1;
        } else if(b.second < a.second) {
            return -1;
        }
    }

    return 0;
}

#endif