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