/* Copyright (c) 2018
   Charles Jordan (Hokkaido University, Sapporo, Japan),
   Michael Joswig, Lars Kastner (Technische Universitaet Berlin, Germany)

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 3, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
-----------------------------------------------------------------------------
*/

#ifndef RANDOM_BFS_HH
#define RANDOM_BFS_HH

#include <cstdlib>
#include <unordered_set>

template<typename Node>
void randomized_bfs(const Node& initial) {
   std::unordered_set<Node> queue, seen;
   queue.insert(initial);
   int i = 0;
   int mod = 1;
   while(queue.size() > 0){
      if(i % mod == 0){
         if(i %(100*mod) == 0){
            mod *= 10;
         }
         std::cout << i << " " << queue.size() << std::endl;
      }
      auto it = queue.begin();
      int pos = rand()%(queue.size());
      for(int k=0; k<pos; k++) it++;
      const Node current(*it);
      queue.erase(it);
      seen.insert(current);
      for(const auto& neighbor: current.get_all_neighbors(i)){
         auto search = seen.find(neighbor);
         if (search == seen.end()) {
            auto searchInner = queue.find(neighbor);
            if(searchInner == queue.end()){
               queue.insert(neighbor);
            }
         }
      }
      i++;
   }
   std::cout << "Total triangulations: " << seen.size() << std::endl;
}


#endif
