// -*- c++ -*-

 #ifndef LEMON_BFS_DFS_H

 #define LEMON_BFS_DFS_H

 /// \ingroup galgs

 /// \file

 /// \brief Bfs and dfs iterators.

 ///

 /// This file contains bfs and dfs iterator classes.

 ///

 // /// \author Marton Makai

 #include <queue>

 #include <stack>

 #include <utility>

 #include <lemon/invalid.h>

 namespace lemon {

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

   /// \c reached_map

   /// Reached have to be a read-write bool node-map.

   /// \ingroup galgs

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

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

   class BfsIterator {

   protected:

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     const Graph* graph;

     std::queue<Node> bfs_queue;

     ReachedMap& reached;

     bool b_node_newly_reached;

     Edge actual_edge;

     bool own_reached_map;

   public:

     /// In that constructor \c _reached have to be a reference 

     /// for a bool bode-map. The algorithm will search for the 

     /// initially \c false nodes 

     /// in a bfs order.

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

       graph(&_graph), reached(_reached), 

       own_reached_map(false) { }

     /// The same as above, but the map storing the reached nodes 

     /// is constructed dynamically to everywhere false.

     /// \deprecated

     BfsIterator(const Graph& _graph) : 

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

       own_reached_map(true) { }

     /// The map storing the reached nodes have to be destroyed if 

     /// it was constructed dynamically

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

     /// This method markes \c s reached.

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

     /// and the first out-edge is processed.

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

     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 

       reached.set(s, true);

       if (bfs_queue.empty()) {

 	bfs_queue.push(s);

 	actual_edge=OutEdgeIt(*graph, s);

 	//graph->first(actual_edge, s);

 	if (actual_edge!=INVALID) { 

 	  Node w=graph->target(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);

       }

       return *this;

     }

     /// 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 (actual_edge!=INVALID) { 

 	actual_edge=++OutEdgeIt(*graph, actual_edge);

 	//++actual_edge;

 	if (actual_edge!=INVALID) {

 	  Node w=graph->target(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()) {

 	  actual_edge=OutEdgeIt(*graph, bfs_queue.front());

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

 	  if (actual_edge!=INVALID) {

 	    Node w=graph->target(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;

     }

     /// Returns true iff the algorithm is finished.

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

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

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

     ///\bug Edge have to be in LEMON 0.2

     operator Edge() const { return actual_edge; }

     /// Returns if b-node has been reached just now.

     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

     /// Returns if a-node is examined.

     bool isANodeExamined() const { return actual_edge==INVALID; }

     /// Returns a-node of the actual edge, so does if the edge is invalid.

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

     /// \pre The actual edge have to be valid.

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

     /// Guess what?

     /// \deprecated 

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

     /// Guess what?

     /// \deprecated

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

   };

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

   /// \c reached_map

   /// Reached have to work as a read-write bool Node-map, 

   /// Pred is a write edge node-map and

   /// Dist is a read-write node-map of integral value, have to be. 

   /// \ingroup galgs

   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:

     /// The algorithm will search in a bfs order for 

     /// the nodes which are \c false initially. 

     /// The constructor makes no initial changes on the maps.

     Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : 

       BfsIterator<Graph, ReachedMap>(_graph, _reached), 

       pred(_pred), dist(_dist) { }

     /// \c 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 \c s was not marked previously, then 

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

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

     Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) { 

       if (this->reached[s]) {

 	Parent::pushAndSetReached(s);

       } else {

 	Parent::pushAndSetReached(s);

 	pred.set(s, INVALID);

 	dist.set(s, 0);

       }

       return *this;

     }

     /// A bfs is processed from \c s.

     Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {

       push(s);

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

       return *this;

     }

     /// Beside the bfs iteration, \c pred and \dist are saved in a 

     /// newly reached node. 

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

       Parent::operator++();

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

       {

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

 	dist.set(this->target(), dist[this->source()]);

       }

       return *this;

     }

     /// Guess what?

     /// \deprecated 

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

     /// Guess what?

     /// \deprecated

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

   };

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

   /// \c reached_map

   /// Reached have to be a read-write bool Node-map.

   /// \ingroup galgs

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

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

   class DfsIterator {

   protected:

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     const Graph* graph;

     std::stack<OutEdgeIt> dfs_stack;

     bool b_node_newly_reached;

     Edge actual_edge;

     Node actual_node;

     ReachedMap& reached;

     bool own_reached_map;

   public:

     /// In that constructor \c _reached have to be a reference 

     /// for a bool node-map. The algorithm will search in a dfs order for 

     /// the nodes which are \c false initially

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

       graph(&_graph), reached(_reached), 

       own_reached_map(false) { }

     /// The same as above, but the map of reached nodes is 

     /// constructed dynamically 

     /// to everywhere false.

     DfsIterator(const Graph& _graph) : 

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

       own_reached_map(true) { }

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

     /// This method markes s reached and first out-edge is processed.

     DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 

       actual_node=s;

       reached.set(s, true);

       OutEdgeIt e(*graph, s);

       //graph->first(e, s);

       dfs_stack.push(e); 

       return *this;

     }

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

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

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

     operator++() { 

       actual_edge=dfs_stack.top();

       if (actual_edge!=INVALID/*.valid()*/) { 

 	Node w=graph->target(actual_edge);

 	actual_node=w;

 	if (!reached[w]) {

 	  OutEdgeIt e(*graph, w);

 	  //graph->first(e, w);

 	  dfs_stack.push(e);

 	  reached.set(w, true);

 	  b_node_newly_reached=true;

 	} else {

 	  actual_node=graph->source(actual_edge);

 	  ++dfs_stack.top();

 	  b_node_newly_reached=false;

 	}

       } else {

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

 	dfs_stack.pop();

       }

       return *this;

     }

     /// Returns true iff the algorithm is finished.

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

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

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

     ///\bug Edge have to be in LEMON 0.2

     operator Edge() const { return actual_edge; }

     /// Returns if b-node has been reached just now.

     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

     /// Returns if a-node is examined.

     bool isANodeExamined() const { return actual_edge==INVALID; }

     /// Returns a-node of the actual edge, so does if the edge is invalid.

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

     /// Returns b-node of the actual edge. 

     /// \pre The actual edge have to be valid.

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

     /// Guess what?

     /// \deprecated

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

     /// Guess what?

     /// \deprecated

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

   };

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

   /// \c reached_map

   /// Reached is a read-write bool node-map, 

   /// Pred is a write node-map, have to be.

   /// \ingroup galgs

   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:

     /// The algorithm will search in a dfs order for 

     /// the nodes which are \c false initially. 

     /// The constructor makes no initial changes on the maps.

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

     /// \c 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 \c s was not marked previously, then 

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

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

     Dfs<Graph, ReachedMap, PredMap>& push(Node s) { 

       if (this->reached[s]) {

 	Parent::pushAndSetReached(s);

       } else {

 	Parent::pushAndSetReached(s);

 	pred.set(s, INVALID);

       }

       return *this;

     }

     /// A bfs is processed from \c s.

     Dfs<Graph, ReachedMap, PredMap>& run(Node s) {

       push(s);

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

       return *this;

     }

     /// Beside the dfs iteration, \c pred is saved in a 

     /// newly reached node. 

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

       Parent::operator++();

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

       {

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

       }

       return *this;

     }

     /// Guess what?

     /// \deprecated

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

   };

 } // namespace lemon

 #endif //LEMON_BFS_DFS_H