// -*- c++ -*-

 #ifndef HUGO_BFS_ITERATOR_H

 #define HUGO_BFS_ITERATOR_H

 #include <queue>

 #include <stack>

 #include <utility>

 namespace hugo {

   template <typename Graph, /*typename OutEdgeIt,*/ 

 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   class BfsIterator {

   protected:

     typedef typename Graph::Node Node;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     const Graph* graph;

     std::queue<Node> bfs_queue;

     ReachedMap& reached;

     bool b_node_newly_reached;

     OutEdgeIt actual_edge;

     bool own_reached_map;

   public:

     BfsIterator(const Graph& _graph, ReachedMap& _reached) : 

       graph(&_graph), reached(_reached), 

       own_reached_map(false) { }

     BfsIterator(const Graph& _graph) : 

       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 

       own_reached_map(true) { }

     ~BfsIterator() { if (own_reached_map) delete &reached; }

     void pushAndSetReached(Node s) { 

       reached.set(s, true);

       if (bfs_queue.empty()) {

 	bfs_queue.push(s);

 	graph->first(actual_edge, s);

 	if (graph->valid(actual_edge)) { 

 	  Node w=graph->bNode(actual_edge);

 	  if (!reached[w]) {

 	    bfs_queue.push(w);

 	    reached.set(w, true);

 	    b_node_newly_reached=true;

 	  } else {

 	    b_node_newly_reached=false;

 	  }

 	} 

       } else {

 	bfs_queue.push(s);

       }

     }

     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 

     operator++() { 

       if (graph->valid(actual_edge)) { 

 	graph->next(actual_edge);

 	if (graph->valid(actual_edge)) {

 	  Node w=graph->bNode(actual_edge);

 	  if (!reached[w]) {

 	    bfs_queue.push(w);

 	    reached.set(w, true);

 	    b_node_newly_reached=true;

 	  } else {

 	    b_node_newly_reached=false;

 	  }

 	}

       } else {

 	bfs_queue.pop(); 

 	if (!bfs_queue.empty()) {

 	  graph->first(actual_edge, bfs_queue.front());

 	  if (graph->valid(actual_edge)) {

 	    Node w=graph->bNode(actual_edge);

 	    if (!reached[w]) {

 	      bfs_queue.push(w);

 	      reached.set(w, true);

 	      b_node_newly_reached=true;

 	    } else {

 	      b_node_newly_reached=false;

 	    }

 	  }

 	}

       }

       return *this;

     }

     bool finished() const { return bfs_queue.empty(); }

     operator OutEdgeIt () const { return actual_edge; }

     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

     Node aNode() const { return bfs_queue.front(); }

     Node bNode() const { return graph->bNode(actual_edge); }

     const ReachedMap& getReachedMap() const { return reached; }

     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }

   };  

   template <typename Graph, /*typename OutEdgeIt,*/ 

 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   class DfsIterator {

   protected:

     typedef typename Graph::Node Node;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     const Graph* graph;

     std::stack<OutEdgeIt> dfs_stack;

     bool b_node_newly_reached;

     OutEdgeIt actual_edge;

     Node actual_node;

     ReachedMap& reached;

     bool own_reached_map;

   public:

     DfsIterator(const Graph& _graph, ReachedMap& _reached) : 

       graph(&_graph), reached(_reached), 

       own_reached_map(false) { }

     DfsIterator(const Graph& _graph) : 

       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 

       own_reached_map(true) { }

     ~DfsIterator() { if (own_reached_map) delete &reached; }

     void pushAndSetReached(Node s) { 

       actual_node=s;

       reached.set(s, true);

       OutEdgeIt e;

       graph->first(e, s);

       dfs_stack.push(e); 

     }

     DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 

     operator++() { 

       actual_edge=dfs_stack.top();

       //actual_node=G.aNode(actual_edge);

       if (graph->valid(actual_edge)/*.valid()*/) { 

 	Node w=graph->bNode(actual_edge);

 	actual_node=w;

 	if (!reached[w]) {

 	  OutEdgeIt e;

 	  graph->first(e, w);

 	  dfs_stack.push(e);

 	  reached.set(w, true);

 	  b_node_newly_reached=true;

 	} else {

 	  actual_node=graph->aNode(actual_edge);

 	  graph->next(dfs_stack.top());

 	  b_node_newly_reached=false;

 	}

       } else {

 	//actual_node=G.aNode(dfs_stack.top());

 	dfs_stack.pop();

       }

       return *this;

     }

     bool finished() const { return dfs_stack.empty(); }

     operator OutEdgeIt () const { return actual_edge; }

     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

     Node aNode() const { return actual_node; /*FIXME*/}

     Node bNode() const { return graph->bNode(actual_edge); }

     const ReachedMap& getReachedMap() const { return reached; }

     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }

   };

 } // namespace hugo

 #endif //HUGO_BFS_ITERATOR_H