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

//   class do_nothing_map {};

//   template <typename V,typename T>

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

  struct do_nothing_map {

  template <typename V,typename T>

  static void Set(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 Set(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 Set(class_element_map<C,T,M> p,I i, T t)

     {

     i->*M=t;   

     };

  */

  template <typename P,typename I,typename T>

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

  {

    p.Set(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 Set(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 Set(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 Set(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 Set(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) 

    {

      SetDataField(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)

      Set(maps.visited,n,false);

    queue<Q_T> Q;

    q.n=start_node;

    q.dist=0;

    Q.push(q);

    Set(maps.visited,start_node,true);

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

    Set(maps.dist,start_node,0);

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

	  Set(maps.visited,m,true);

	  Set(maps.tree,m,e);

	  Set(maps.dist,m,d);

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

	}

    } while(!Q.empty());

  };

}

#endif