/* Darstellung als Ajazenslisten */

#include <list>

template<class T>
bool element_of (std::list<T>& lst, T el)
{
  for (std::list<T>::iterator i = lst.begin (); i != lst.end (); ++i)
    {
      if (*i == el)
	return true;
    }
  return false;
}

template<class T>
void add_to_list (std::list<T>& lst, T el)
{
  if (!element_of (lst, el))
    lst.push_back (el);
}

template<class T, class W = double>
class GraphEdge
{
private:
  std::pair<T, T> p;
  W m_value;
public:
  GraphEdge (T& a, T& b)
    : p (a, b) {}

  T& first () { return p.first; }
  T& second () { return p.second; }
  W value () { return m_value; }
};

template<class T>
class GraphNode
{
private:
  std::list<std::pair<GraphNode*, float> > next;
  T data;
public:
  T& get () { return data; }
  
  void connect_with (GraphNode* node) {
    next.push_back (node);
  }
};

template<class T>
class Graph
{
private:
  std::list<GraphNode<T>*> nodes;
public:
  void add_node (GraphNode<T>* node) {
    nodes.push_back (node);
  }

  void add_edge (GraphEdge<T> edge) {
  }

  std::list<GraphNode<T>*>::iterator& begin () {
    return nodes.begin ();
  }
  std::list<GraphNode<T>*>::iterator& end () {
    return nodes.end ();
  }
};

template<class T>
GraphPath<T> find_path (GraphNode<T>* start, GraphNode<T>* stop)
{
  priorityqueue<GraphNode<T>*> open_nodes;
  open_nodes.push_back(start);
  
  while (!open_nodes.empty ())
    {
      
    }
}

/** A wrapper around a node which can hold all the extra information
    that is needed */
template<class T>
class DijkstraSearchNode
{
private:
  GraphNode<T>* node;
  GraphNode<T>* parent;
  bool is_finished;
  float distance;
  GraphNode<T>* parent;
public:
  DijkstraSearchNode (GraphNode<T>* n, GraphNode<T>* p) 
    : node (n),
      parent (p),
      is_finished (false),
      distance (0.0f)
  {
  }

  GraphNode<T>* get_node () {
    return node;
  }
};

template<class T>
class DijkstraSearch
{
private:
  Graph<T> graph;
  PriorityQueue<DijkstraSearchNode> open_nodes;
  std::list<GraphNode<T>*> closed_nodes;
  GraphPath<T> path;
  
public:
  DijkstraSearch (Graph<T> graph, GraphNode<T>* start, GraphNode<T>* finish)
  {
    open_nodes.push (DijkstraSearchNode(start, NULL));

    while (!open_nodes.empty ())
      {
	GraphNode<T>* current_node = open_nodes.top ();
	open_nodes.pop ();
	
	if (current_node == finish)
	  return; // Done, we have found a path

	for (std::list<GraphNode<T>*>::iterator i = current_node.successors.begin ();
	     i != current_node.successors.end (); ++i)
	  {
	    //

	    if (!node_is_finished(*i))
	      open_nodes.push (DijkstraSearchNode(*i, current_node));
	  }
	return; // No path found
      }
  }

  ~DijkstraSearch ()
  {
  }

  bool node_is_finished (GraphNode<T>* node)
  {
    return element_of (closed_nodes, node);
  }

  GraphPath<T> get_path ()
  {
    return path;
  }
};

// EOF //