#ifndef MARCI_BFS_HH

 #define MARCI_BFS_HH

 #include <queue>

 #include <marci_graph_traits.hh>

 #include <marci_property_vector.hh>

 namespace marci {

   template <typename graph_type>

   struct bfs {

     typedef typename graph_traits<graph_type>::node_iterator node_iterator;

     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;

     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;

     graph_type& G;

     node_iterator s;

     node_property_vector<graph_type, bool> reached;

     node_property_vector<graph_type, edge_iterator> pred;

     node_property_vector<graph_type, int> dist;

     std::queue<node_iterator> bfs_queue;

     bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 

       bfs_queue.push(s); 

       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) 

 	reached.put(i, false);

       reached.put(s, true);

       dist.put(s, 0); 

     }

     void run() {

       while (!bfs_queue.empty()) {

 	node_iterator v=bfs_queue.front();

 	out_edge_iterator e=G.first_out_edge(v);

 	bfs_queue.pop();

 	for( ; e.is_valid(); ++e) {

 	  node_iterator w=G.head(e);

 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;

 	  if (!reached.get(w)) {

 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;

 	    bfs_queue.push(w);

 	    dist.put(w, dist.get(v)+1);

 	    pred.put(w, e);

 	    reached.put(w, true);

 	  } else {

 	    std::cout << G.id(w) << " is already reached" << std::endl;

 	  }

 	}

       }

     }

   };

   template <typename graph_type> 

   struct bfs_visitor {

     typedef typename graph_traits<graph_type>::node_iterator node_iterator;

     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;

     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;

     graph_type& G;

     bfs_visitor(graph_type& _G) : G(_G) { }

     void at_previously_reached(out_edge_iterator& e) { 

       //node_iterator v=G.tail(e);

       node_iterator w=G.head(e);

       std::cout << G.id(w) << " is already reached" << std::endl;

    }

     void at_newly_reached(out_edge_iterator& e) { 

       //node_iterator v=G.tail(e);

       node_iterator w=G.head(e);

       std::cout << G.id(w) << " is newly reached :-)" << std::endl;

     }

   };

   template <typename graph_type, typename reached_type, typename visitor_type>

   struct bfs_iterator {

     typedef typename graph_traits<graph_type>::node_iterator node_iterator;

     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;

     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;

     graph_type& G;

     std::queue<out_edge_iterator>& bfs_queue;

     reached_type& reached;

     visitor_type& visitor;

     void process() {

       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

       if (bfs_queue.empty()) return;

       out_edge_iterator e=bfs_queue.front();

       //node_iterator v=G.tail(e);

       node_iterator w=G.head(e);

       if (!reached.get(w)) {

 	visitor.at_newly_reached(e);

 	bfs_queue.push(G.first_out_edge(w));

 	reached.put(w, true);

       } else {

 	visitor.at_previously_reached(e);

       }

     }

     bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 

       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

       is_valid();

     }

     bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { 

       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

       //if (bfs_queue.empty()) return *this;

       if (!is_valid()) return *this;

       ++(bfs_queue.front());

       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

       is_valid();

       return *this;

     }

     //void next() { 

     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

     //  if (bfs_queue.empty()) return;

     //  ++(bfs_queue.front());

     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

     //}

     bool is_valid() { 

       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

       if (bfs_queue.empty()) return false; else return true;

     }

     //bool finished() { 

     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

     //  if (bfs_queue.empty()) return true; else return false;

     //}

     operator edge_iterator () { return bfs_queue.front(); }

   };

   template <typename graph_type, typename reached_type>

   struct bfs_iterator1 {

     typedef typename graph_traits<graph_type>::node_iterator node_iterator;

     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;

     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;

     graph_type& G;

     std::queue<out_edge_iterator>& bfs_queue;

     reached_type& reached;

     bool newly_reached;

     bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 

       is_valid();

       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 

 	out_edge_iterator e=bfs_queue.front();

 	node_iterator w=G.head(e);

 	if (!reached.get(w)) {

 	  bfs_queue.push(G.first_out_edge(w));

 	  reached.put(w, true);

 	  newly_reached=true;

 	} else {

 	  newly_reached=false;

 	}

       }

     }

     bfs_iterator1<graph_type, reached_type>& operator++() { 

       if (!is_valid()) return *this;

       ++(bfs_queue.front());

       is_valid();

       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 

 	out_edge_iterator e=bfs_queue.front();

 	node_iterator w=G.head(e);

 	if (!reached.get(w)) {

 	  bfs_queue.push(G.first_out_edge(w));

 	  reached.put(w, true);

 	  newly_reached=true;

 	} else {

 	  newly_reached=false;

 	}

       }

       return *this;

     }

     bool is_valid() { 

       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 

       if (bfs_queue.empty()) return false; else return true;

     }

     operator edge_iterator () { return bfs_queue.front(); }

     bool is_newly_reached() { return newly_reached; }

   };

 } // namespace marci

 #endif //MARCI_BFS_HH