// -*- mode:C++ -*-

#include <hugo/smart_graph.h>
#include <hugo/maps.h>
#include <vector>

using namespace hugo;

struct _BFS_DEFAULT_VIS {};
struct _BFS_CUSTOM_VIS {};

template<class GT,class VT,class DVT,class PNT,class PET,class PT >
class _BFS 
{
 public:
  typedef GT Graph;
  typedef VT Visited;
  typedef PNT PredNode;
  typedef PET PredEdge;
  typedef PT Priority;
  //  typedef QDT QueueData;
  
  typedef typename Graph::Node Node;
  typedef typename Graph::OutEdgeIt OutEdgeIt;

  typedef DVT DefaultVisitedTag;
  
  const Graph &_graph;

  Node _source;
  
  Visited *_visited;
  PredNode _predNode;
  PredEdge _predEdge;
  Priority _priority;

  _BFS(const Graph &g,
       Node s,
       Visited *v,
       PredNode &pn,
       PredEdge &pe,
       Priority &pr) :_graph(g), _source(s),
		     _visited(v), 
		     _predNode(pn), _predEdge(pe), _priority(pr) { }

  
  int run(const _BFS_CUSTOM_VIS &) 
  {
    using namespace std;
    
    int N=_graph.nodeNum();
    vector<Node> Q(N);
    int Qh=0;
    int Qt=0;
    
    for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))
      _visited->set(n,false);

    Q[Qh++]=_source;
    _visited->set(_source,true);
    do {
      Node m;
      Node n=Q[Qt++];
      for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))
	if(!(*_visited)[m=_graph.head(e)]) {
	  Q[Qh++]=m;
	  _visited->set(m,true);
	  _predNode.set(m,n);
	  _predEdge.set(m,e);	  
	}
    } while(Qt!=Qh);

    return 1; //Why return 1?
  }
  int run(const _BFS_DEFAULT_VIS &) 
  {
    _visited= new Visited(_graph);
    int r = run(_BFS_CUSTOM_VIS());
    delete _visited;
    return r;
  }
  int run() { return run(DefaultVisitedTag());}

  template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
  setVisitMap(T &t)
  {
    return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
      (_graph,_source,&t,_predNode,_predEdge,_priority);
  }

  template<class T>
  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority>
  setPredNodeMap(T &t)
  {
    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority>
      (_graph,_source,
       _visited,
       t,_predEdge,_priority);
  }

  template<class T>
  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority>
  setPredEdgeMap(T &t)
  {
    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority>
      (_graph,_source,
       _visited,
      _predNode,t,_priority);
  }

  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
  setNothing()
  {
    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
      (_graph,_source,
       _visited,
       _predNode,_predEdge,_priority);
  }
};


template<class G>
_BFS<G,
     typename G::template NodeMap<bool>,
     _BFS_DEFAULT_VIS,
     NullMap<typename G::Node,typename G::Node>,
     NullMap<typename G::Node,typename G::Edge>,
     NullMap<typename G::Node,int> >
bfs(const G &g,typename G::Node s)
{
  //  typename G::template NodeMap<bool> v(g);

  return _BFS < G,
    typename G::template NodeMap<bool>,
    _BFS_DEFAULT_VIS,
     NullMap<typename G::Node,typename G::Node>,
     NullMap<typename G::Node,typename G::Edge>,
    NullMap<typename G::Node,int> >
    (g,s,
     (typename G::template NodeMap<bool>*)(NULL),
     *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
     *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
     *((NullMap<typename G::Node,int> *)(NULL))
     );
}


int main()
{
  SmartGraph G;
  SmartGraph::NodeIt n(G);
  SmartGraph::NodeMap<SmartGraph::Node> m(G);
  SmartGraph::NodeMap<SmartGraph::Edge> em(G);
  
  bfs(G,n).run();
  bfs(G,n).setPredNodeMap(m).run();
  bfs(G,n).setPredNodeMap(m).setPredEdgeMap(em).run();

}