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

    /// This method markes s reached.

    /// If the queue is empty, then s is pushed in the bfs queue 

    /// and the first OutEdgeIt is processed.

    /// If the queue is not empty, then s is simply pushed.

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

      }

    }

    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 

    /// its \c operator++() iterates on the edges in a bfs order.

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

    /// The conversion operator makes for converting the bfs-iterator 

    /// to an \c out-edge-iterator.

    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; }

  };  

  /// Bfs searches from s for the nodes wich are not marked in 

  /// \c reached_map

  /// Reached is a read-write bool-map, Pred is a write-nodemap 

  /// and dist is an rw-nodemap, have to be.

  template <typename Graph, 

	    typename ReachedMap=typename Graph::template NodeMap<bool>, 

	    typename PredMap

	    =typename Graph::template NodeMap<typename Graph::Edge>, 

	    typename DistMap=typename Graph::template NodeMap<int> > 

  class Bfs : public BfsIterator<Graph, ReachedMap> {

    typedef BfsIterator<Graph, ReachedMap> Parent;

  protected:

    typedef typename Parent::Node Node;

    PredMap& pred;

    DistMap& dist;

  public:

    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }

    /// s is marked to be reached and pushed in the bfs queue.

    /// If the queue is empty, then the first out-edge is processed.

    /// If s was not marked previously, then 

    /// in addition its pred is set to be INVALID, and dist to 0. 

    /// if s was marked previuosly, then it is simply pushed.

    void push(Node s) { 

      if (this->reached[s]) {

	Parent::pushAndSetReached(s);

      } else {

	Parent::pushAndSetReached(s);

	pred.set(s, INVALID);

	dist.set(s, 0);

      }

    }

    /// A bfs is processed from s.

    void run(Node s) {

      push(s);

      while (!this->finished()) this->operator++();

    }

    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {

      Parent::operator++();

      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 

      {

	pred.set(this->bNode(), this->actual_edge);

	dist.set(this->bNode(), dist[this->aNode()]);

      }

      return *this;

    }

    const PredMap& getPredMap() const { return pred; }

    const DistMap& getDistMap() const { return dist; }

  };

  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; }

  };

  /// Dfs searches from s for the nodes wich are not marked in 

  /// \c reached_map

  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.

  template <typename Graph, 

	    typename ReachedMap=typename Graph::template NodeMap<bool>, 

	    typename PredMap

	    =typename Graph::template NodeMap<typename Graph::Edge> > 

  class Dfs : public DfsIterator<Graph, ReachedMap> {

    typedef DfsIterator<Graph, ReachedMap> Parent;

  protected:

    typedef typename Parent::Node Node;

    PredMap& pred;

  public:

    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }

    /// s is marked to be reached and pushed in the bfs queue.

    /// If the queue is empty, then the first out-edge is processed.

    /// If s was not marked previously, then 

    /// in addition its pred is set to be INVALID. 

    /// if s was marked previuosly, then it is simply pushed.

    void push(Node s) { 

      if (this->reached[s]) {

	Parent::pushAndSetReached(s);

      } else {

	Parent::pushAndSetReached(s);

	pred.set(s, INVALID);

      }

    }

    /// A bfs is processed from s.

    void run(Node s) {

      push(s);

      while (!this->finished()) this->operator++();

    }

    Dfs<Graph, ReachedMap, PredMap> operator++() {

      Parent::operator++();

      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 

      {

	pred.set(this->bNode(), this->actual_edge);

      }

      return *this;

    }

    const PredMap& getPredMap() const { return pred; }

  };

} // namespace hugo

#endif //HUGO_BFS_ITERATOR_H