// -*-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-tel

 //   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(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());

   };

 }

 #endif