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

  namespace marci {

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

  /// \c reached_map

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

  /// \ingroup galgs

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

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

  class BfsIterator {

  public:

    typedef RM ReachedMap;

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

    bool b_node_newly_reached;

    //OutEdgeIt actual_edge;

    Edge actual_edge;

    /// \e

    BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }

    /// RM have to be set before any bfs operation.

    BfsIterator<Graph, RM>& setReached(RM& _reached_map) {

      reached_map=&_reached_map;

    }

  public:

    /// In that constructor \c _reached_map 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_map) : 

      graph(&_graph), reached_map(&_reached_map) { }

    /// 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_map(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_map; }

    /// 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_map->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->head(actual_edge);

	  if (!(*reached_map)[w]) {

	    bfs_queue.push(w);

	    reached_map->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->head(actual_edge);

	  if (!(*reached_map)[w]) {

	    bfs_queue.push(w);

	    reached_map->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->head(actual_edge);

	    if (!(*reached_map)[w]) {

	      bfs_queue.push(w);

	      reached_map->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 tail() const { return bfs_queue.front(); }

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

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

    /// Guess what?

    /// \deprecated 

    const ReachedMap& reachedMap() const { return *reached_map; }

    /// Guess what?

    /// \deprecated 

    typename ReachedMap::ValueType reached(const Node& n) const { 

      return (*reached_map)[n]; 

    }

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

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

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

  /// PNM is a write node node-map and

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

  /// \ingroup galgs

  template <typename Graph, 

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

	    typename PM

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

	    typename PNM

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

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

  class Bfs : public BfsIterator<Graph, RM> {

    typedef BfsIterator<Graph, RM> Parent;

  public:

    typedef RM ReachedMap;

    typedef PM PredMap;

    typedef PNM PredNodeMap;

    typedef DM DistMap;

  protected:

    typedef typename Parent::Node Node;

    PredMap* pred_map;

    PredNodeMap* pred_node_map;

    DistMap* dist_map;

    /// \e

    Bfs<Graph, RM, PM, PNM, DM>

    (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }

    /// PM have to be set before any bfs operation.

    Bfs<Graph, RM, PM, PNM, DM>& 

    setPredMap(PredMap& _pred_map) {

      pred_map=&_pred_map;

    }

    /// PredNodeMap have to be set before any bfs operation.

    Bfs<Graph, RM, PM, PNM, DM>& 

    setPredNodeMap(PredNodeMap& _pred_node_map) {

      pred_node_map=&_pred_node_map;

    }

    /// DistMap have to be set before any bfs operation.

    Bfs<Graph, RM, PM, PNM, DM>& 

    setDistMap(DistMap& _dist_map) {

      dist_map=&_dist_map;

    }

  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, RM, PM, PNM, DM>

    (const Graph& _graph, ReachedMap& _reached_map, 

     PredMap& _pred_map, PredNodeMap& _pred_node_map, 

     DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map), 

      pred_map(&_pred_map), pred_node_map(&_pred_node_map), 

			   dist_map(&_dist_map) { }

    /// \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_map is set to be \c INVALID, 

    /// and dist_map to \c 0. 

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

    Bfs<Graph, RM, PM, PNM, DM>& push(Node s) { 

      if ((*(this->reached_map))[s]) {

	Parent::pushAndSetReached(s);

      } else {

	Parent::pushAndSetReached(s);

	pred_map->set(s, INVALID);

	pred_node_map->set(s, INVALID);

	dist_map->set(s, 0);

      }

      return *this;

    }

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

    Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {

      push(s);

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

      return *this;

    }

    /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a 

    /// newly reached node. 

    Bfs<Graph, RM, PM, PNM, DM>& operator++() {

      Parent::operator++();

      if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) 

      {

	pred_map->set(this->head(), this->actual_edge);

	pred_node_map->set(this->head(), this->tail());

	dist_map->set(this->head(), (*dist_map)[this->tail()]);

      }

      return *this;

    }

    /// Guess what?

    /// \deprecated 

    const PredMap& predMap() const { return *pred_map; }

    /// Guess what?

    /// \deprecated 

    typename PredMap::ValueType pred(const Node& n) const { 

      return (*pred_map)[n]; 

    }

    /// Guess what?

    /// \deprecated 

    const PredNodeMap& predNodeMap() const { return *pred_node_map; }

    /// Guess what?

    /// \deprecated 

    typename PredNodeMap::ValueType predNode(const Node& n) const { 

      return (*pred_node_map)[n]; 

    }

    /// Guess what?

    /// \deprecated

    const DistMap& distMap() const { return *dist_map; }

    /// Guess what?

    /// \deprecated 

    typename DistMap::ValueType dist(const Node& n) const { 

      return (*dist_map)[n]; 

    }

  };

//   template <typename Graph, 

// 	    typename RM=typename Graph::template NodeMap<bool>, 

// 	    typename PM

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

// 	    typename PredNodeMap

// 	    =typename Graph::template NodeMap<typename Graph::Node>, 

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

//     class BfsWizard : public Bfs<Graph> {

//     public:

//       typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;

//     protected:

//       typedef typename Parent::Node Node;

//       bool own_reached_map;

//       bool own_pred_map;

//       bool own_pred_node_map;

//       bool own_dist_map;

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       makeRreached() { 

// 	own_reached_map=true;

// 	reached=new ReachedMap(*graph, false);

//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       deleteReachedMap() { 

// 	own_reached_map=false;

// 	delete reached;

//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       makePM() { 

// 	own_pred_map=true;

// 	pred_map=new PM(*graph, INVALID);

//       }

//       BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>& 

//       deletePM() { 

// 	own_pred_map=false;

// 	delete pred_map;

//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       makePredNodeMap() { 

// 	own_pred_node_map=true;

// 	pred_node_map=new PredNodeMap(*graph, INVALID);

//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       deletePredNodeMap() { 

// 	own_pred_node_map=false;

// 	delete pred_node_map;

//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       makeDistMap() { 

// 	own_dist_map=true;

// 	dist_map=new DistMap(*graph, 0);

//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       deleteDistMap() { 

// 	own_dist_map=false;

// 	delete dist_map;

//       }

//     public:

//       /// User friendly Bfs class.

//       /// The maps which are not explicitly given by the user are 

//       /// constructed with false, INVALID, INVALID and 0 values.

//       /// For the user defined maps, the values are not modified, and 

//       /// the bfs is processed without any preset on maps. Therefore, 

//       /// the bfs will search only the nodes which are set false previously 

//       /// in reached, and in the nodes wich are not newly reached by the 

//       /// search, the map values are not modified.

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>

//       (const Graph& _graph) : 

// 	own_reached_map(false), 

// 	own_pred_map(false), 

// 	own_pred_node_map(false), 

// 	own_dist_map(false) { 

//       }

//       /// \e

//       ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() { 

// 	if (own_reached_map) deleteReachedMap();

// 	if (own_pred_map) deletePM();

// 	if (own_pred_node_map) deletePredNodeMap();

// 	if (own_dist_map) deleteDistMap();

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       setReachedMap(ReachedMap& _reached) {

// 	if (own_reached_map) deleteReachedMap();

// 	Parent::setReachedMap(_reached);

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       setPM(PM& _pred) {

// 	if (own_pred_map) deletePM();

// 	Parent::setPM(_pred);

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       setPredNodeMap(PredNodeMap& _pred_node) {

// 	if (own_pred_node_map) deletePredNodeMap();

// 	Parent::setPredNodeMap(_pred_node);

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       setDistMap(DistMap& _dist) {

// 	if (own_dist_map) deleteDistMap();

// 	Parent::setDistMap(_dist);

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       push(Node s) { 

// 	if (!reached) makeReachedMap();

// 	if (!pred_map) makePMMap();

// 	if (!pred_node_map) makePredNodeMap();

// 	if (!dist_map) makeDistMap();

// 	push(s);

// 	return *this;

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       operator++() { 

// 	if (!reached) makeRM();

// 	if (!pred_map) makePMMap();

// 	if (!pred_node_map) makePredNodeMap();

// 	if (!dist_map) makeDistMap();

// 	++(*this);

// 	return *this;

//       }

//       /// \e

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 

//       run(Node s) { 

// 	if (!reached) makeRM();

// 	if (!pred_map) makePMMap();

// 	if (!pred_node_map) makePredNodeMap();

// 	if (!dist_map) makeDistMap();

// 	run(s);

// 	return *this;

//       }

//     };

  /// 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->head(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->tail(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 tail() const { return actual_node; /*FIXME*/}

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

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

    Node head() const { return graph->head(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->head(), this->actual_edge);

      }

      return *this;

    }

    /// Guess what?

    /// \deprecated

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

  };

  } // namespace marci

} // namespace lemon

#endif //LEMON_BFS_DFS_H