/daten/ahuesgen/projects/vhist/code/vhistlib/include/vhistdifflib/dijkstra.h

/* $HEADERS
 $Id: dijkstra.h 2179 2011-06-24 09:03:24Z ahuesgen $
 */

#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include <QSharedPointer>
#include <QList>

#include "../shared/misc_defines.h"

#include "priorityqueue.h"
#include <QtDebug>


namespace vhist
{

// T = Node/Path Type. Must provide methods:
//   bool reachedGoal() // true if node is a goal node
//   void expand(PriorityQueue<QSharedPointer<T> >& m_queue) // expands the node
template<class T>
class VHIST_EXTERN Dijkstra
{
    private:
        PriorityQueue<QSharedPointer<T> > m_queue;

    public:
        Dijkstra();
        ~Dijkstra();

    public:
        QSharedPointer<T> findPath(QSharedPointer<T> startNode);
        QList<QSharedPointer<T> > findPaths(QSharedPointer<T> startNode,
                int numPaths);
};

} // namespace vhist



template<class T>
vhist::Dijkstra<T>::Dijkstra()
{
}


template<class T>
vhist::Dijkstra<T>::~Dijkstra()
{
}


template<class T>
QSharedPointer<T> vhist::Dijkstra<T>::findPath(QSharedPointer<T> startNode)
{
    QList<QSharedPointer<T> > goals = findPaths(startNode, 1);
    if (goals.size() > 0)
        return goals.at(0);
    else
        return QSharedPointer<T>(NULL);
}


template<class T>
QList<QSharedPointer<T> > vhist::Dijkstra<T>::findPaths(
        QSharedPointer<T> startNode, int numPaths)
{
    QList<QSharedPointer<T> > goals;

    m_queue.push(startNode, 0);
    int i = 0;
    while (!m_queue.isEmpty())
    {
        ++i;
        QSharedPointer<T> curNode = m_queue.pop();
        if (curNode->reachedGoal())
        {
            qDebug() << "FINISHED";
            qDebug() << i << "nodes expanded";
            curNode->printMe();

            goals.append(curNode);
            if (goals.size() >= numPaths)
                return goals;
        }
        else
            curNode->expand(m_queue);
    }

    return goals;
}

#endif // DIJKSTRA_H