// -*-mode: c++; -*-

#ifndef _BFS_H_

#define _BFS_H_

#include <queue>

#include <graph.h>

namespace NEGRO 

{

  using namespace std;

  //   template <typename G,typename> class bfs_T

  //   {

  //     typedef G Graph;

  //     typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell

  //     typedef Graph::NodeIterator NodeIterator;

  //     class bfs_node_D 

  //     {

  //       EdgeIterator Tree;

  //       int Dist;

  //       int Priority;

  //     }

  //   }

  //     //    template <bfs_T<G>>

  //     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)

  //   template <class G>

  //   class bfs_maps_T

  //   {

  //     typedef visited; //node->bool (RW)

  //     typedef tree;    //node->EdgeIterator (W)

  //     typedef dist;   //node->int (W)

  //     typedef priority; //node->int (W)

  //   };

  //   Nem jo! Osszeakad a masik Put-tal

  //   class do_nothing_map {};

  //   template <typename V,typename T>

  //   void Put(const do_nothing_map &p,const V &v,const T &t) {}

  struct do_nothing_map {

    template <typename V,typename T>

    static void Put(V v,T t) {}

  };

  template <typename I,typename C, typename T, T C::*M>

  class class_element_map {

  public:

    typedef T value_type;

    static void Put(const I &i, const T &t) {(*i).*M=t;}

    static T Get(const I i) {return (*i).*M;}

    T &operator[](I i) {return (*i).*M;}

  };

  /* 

     template <typename C,typename I,typename T, T C::*M>

     void Put(class_element_map<C,T,M> p,I i, T t)

     {

     i->*M=t;   

     };

  */

  template <typename P,typename I,typename T>

  inline void Put(P &p,const I &i, const T &t)

  {

    p.Put(i,t);   

  };

  template <typename P,typename I>

  inline typename P::value_type Get(const P &p,const I &i)

  {

    return p.Get(i);   

  };

  /*

    template <typename G,typename T, typename G::EdgeType::*M>

    T Get(edge_element_map p,G::EdgeIterator i)

    {

    return i->*M;

    };

  */

  /* 

     template <class G>

     class default_bfs_maps

     {

     public:

     typedef typename G::NodeType NodeType;

     class_element_map<typename G::NodeIterator,

     typename G::NodeType,

     bool,&NodeType::isVis> visited; //node->bool (RW)

     do_nothing_map tree;   //node->EdgeIterator (W)

     do_nothing_map dist;   //node->int (W)

     do_nothing_map priority; //node->int (W)

     };

  */

  template<class G>

  struct bfs_node_data 

  {

    bool visited;

    typename G::EdgeIterator tree;

    int dist;

    int priority;

  };

  template <class G>

  class bfs_static_maps

  {

  public:

    typedef typename G::NodeType NodeType;

    /*    class_element_map<typename G::NodeIterator,

	  typename G::NodeType,

	  bfs_node_data<G>,&NT::D> n_d; //node-> data

    */

    class 

    {

    public:

      bfs_node_data<G> NodeType::*d;

      typedef bool value_type;

      void Put(typename G::NodeIterator &i, const value_type &t)

      {((*i).*d).visited=t;}

      value_type Get(const typename G::NodeIterator &i) const

      {return ((*i).*d).visited;}

    } visited;

    class 

    {

    public:

      bfs_node_data<G> NodeType::*d;

      typedef typename G::EdgeIterator value_type;

      void Put(typename G::NodeIterator &i, const value_type &t)

      {((*i).*d).tree=t;}

      value_type Get(const typename G::NodeIterator &i) const

      {return ((*i).*d).tree;}

    } tree;

    class 

    {

    public:

      bfs_node_data<G> NodeType::*d;

      typedef int value_type;

      void Put(typename G::NodeIterator &i, const value_type &t)

      {((*i).*d).dist=t;}

      value_type Get(const typename G::NodeIterator &i) const

      {return ((*i).*d).dist;}

    } dist;

    class 

    {

    public:

      bfs_node_data<G> NodeType::*d;

      typedef int value_type;

      void Put(typename G::NodeIterator &i,  const value_type &t)

      {((*i).*d).priority=t;}

      value_type Get(const typename G::NodeIterator &i) const

      {return ((*i).*d).priority;}

    } priority;

    //do_nothing_map tree;   //node->EdgeIterator (W)

    //    do_nothing_map dist;   //node->int (W)

    //    do_nothing_map priority; //node->int (W)

    void SetDataField(const bfs_node_data<G> NodeType::*dd)

    {

      tree.d=visited.d=dist.d=priority.d=dd;

    }

    bfs_static_maps(const bfs_node_data<G> NodeType::*dd) 

    {

      PutDataField(dd);

    }

    bfs_static_maps(const bfs_static_maps<G> &B) 

    {

      tree.d=B.tree.d;visited.d=B.visited.d;

      dist.d=B.dist.d;priority.d=B.priority.d;

    }

  };

  template<typename I>

  struct BFS_Q

  {

    I n;

    int dist;

    //  BFS_Q() {}

    //  BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}

  };

  template<class G,class M>

  void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)

  {

    using namespace std;

    typedef BFS_Q<typename G::NodeIterator> Q_T;

    Q_T q;

    int pr=0;

    typename G::NodeIterator n,m;

    typename G::OutEdgeIterator e;

    int d;

    for(Gr.GetFirst(n);n.isValid();++n)

      Put(maps.visited,n,false);

    queue<Q_T> Q;

    q.n=start_node;

    q.dist=0;

    Q.push(q);

    Put(maps.visited,start_node,true);

    //      Put(maps::tree,start_node,?????);

    Put(maps.dist,start_node,0);

    Put(maps.priority,start_node,pr++);

    do {

      n=Q.front().n;d=Q.front().dist+1;

      Q.pop();

      for(Gr.GetFirst(e,n);e.isValid();++e)

	if(!Get(maps.visited,(m=e.Bnode()))) {

	  q.n=m;

	  q.dist=d;

	  Q.push(q);

	  Put(maps.visited,m,true);

	  Put(maps.tree,m,e);

	  Put(maps.dist,m,d);

	  Put(maps.priority,m,pr++);

	}

    } while(!Q.empty());

  };

  // bfs algorithm class

  template<class G>  //the default traits

  class default_bfs_T

  {

  public:

    typedef G Graph;

    typedef typename G::OutEdgeIterator SearchEdgeIterator;

    typedef typename G::NodeMap<bool> visited_map_t;

    typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;

    typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)

    typedef typename G::NodeMap<int> priority_map_t; //node->int (W)

};

  template<class T>

  class Bfs

  {

  public:

    typedef typename T::Graph Graph;

    typedef typename Graph::NodeIterator NodeIterator;

    typedef typename Graph::EdgeIterator EdgeIterator;

    typedef typename T::SearchEdgeIterator SearchEdgeIterator;

    typename T::visited_map_t visited_map;

    typename T::tree_map_t tree_map;

    typename T::dist_map_t dist_map;

    typename T::priority_map_t priority_map;

    struct bfs_queue_cont

    {

      NodeIterator n;

      int dist;

    };

    std::queue<bfs_queue_cont> bfs_queue;

    int priority;

    Graph *G;

    void SetG(Graph &Gr)

    {

      G=&Gr;

    }

    void Init()

    {

      //There must be a better way to do this:

      while(!bfs_queue.empty()) bfs_queue.pop();

      for(NodeIterator n(*G);n.isValid();++n)

	Put(visited_map,n,false);

      priority=0;

    }

    void AddStartNode(const NodeIterator &start_node,int dist=0)

    {

      bfs_queue_cont q;

      q.n=start_node;

      q.dist=dist;

      bfs_queue.push(q);

      Put(visited_map,start_node,true);

      //      Put(tree_map,start_node,?????);

      Put(dist_map,start_node,dist);

      Put(priority_map,start_node,priority++);    

    }

    void Init(const NodeIterator &start_node,int dist=0)

    {

      Init();

      AddStartNode(start_node,dist);

    }

    void Run() 

    {

      NodeIterator n,m;

      int d;

      bfs_queue_cont q;

      while(!(bfs_queue.empty()/* && other stop conditions */)) {

	n=bfs_queue.front().n;d=bfs_queue.front().dist+1;

	bfs_queue.pop();

	for(SearchEdgeIterator e(*G,n);e.isValid();++e)

	  if(!Get(visited_map,(m=e.Bnode()))) {

	    q.n=m;

	    q.dist=d;

	    bfs_queue.push(q);

	    Put(visited_map,m,true);

	    Put(tree_map,m,e);

	    Put(dist_map,m,d);

	    Put(priority_map,m,priority++);

	  }

      }

    }

  };

}

#endif