// -*-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 G> void SetG(G &g) {}

   };

   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;

     //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}

     Bfs() {}

     void SetG(Graph &Gr)

     {

       G=&Gr;

       visited_map.SetG(Gr);

       tree_map.SetG(Gr);

       dist_map.SetG(Gr);

       priority_map.SetG(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