// Copyright 2004 The Trustees of Indiana University.

 // Distributed under the Boost Software License, Version 1.0.

 // (See accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //  Authors: Douglas Gregor

 //           Andrew Lumsdaine

 #ifndef BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP

 #define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP

 #include <iterator>

 #include <utility>

 #include <boost/random/uniform_01.hpp>

 #include <boost/random/uniform_int.hpp>

 namespace boost {

   // Assumes undirected

   template<typename RandomGenerator, typename Graph>

   class small_world_iterator

   {

     typedef typename graph_traits<Graph>::vertices_size_type 

       vertices_size_type;

   public:

     typedef std::input_iterator_tag iterator_category;

     typedef std::pair<vertices_size_type, vertices_size_type> value_type;

     typedef const value_type& reference;

     typedef const value_type* pointer;

     typedef void difference_type;

     small_world_iterator() : gen(0) {}

     small_world_iterator(RandomGenerator& gen, vertices_size_type n, 

                          vertices_size_type k, double prob = 0.0, 

                          bool allow_self_loops = false) 

       : gen(&gen), n(n), k(k), prob(prob), source(0), 

         target(allow_self_loops? 0 : 1), 

         allow_self_loops(allow_self_loops), 

         current(0, allow_self_loops? 0 : 1)

     { }

     reference operator*() const { return current; }

     pointer operator->() const { return &current; }

     small_world_iterator& operator++()

     { 

       target = (target + 1) % n;

       if (target == (source + k/2 + 1) % n) {

         ++source;

         if (allow_self_loops) target = source;

         else target = (source + 1) % n;

       }

       current.first = source;

       uniform_01<RandomGenerator, double> rand01(*gen);

       uniform_int<vertices_size_type> rand_vertex_gen(0, n-1);

       double x = rand01();

       *gen = rand01.base(); // GRRRR

       if (x < prob) {

         vertices_size_type lower = (source + n - k/2) % n;

         vertices_size_type upper = (source + k/2) % n;

         do {

           current.second = rand_vertex_gen(*gen);

         } while (current.second >= lower && current.second <= upper

                  || (upper < lower 

                      && (current.second >= lower || current.second <= upper)));

       } else {

         current.second = target;

       }

       return *this;

     }

     small_world_iterator operator++(int)

     {

       small_world_iterator temp(*this);

       ++(*this);

       return temp;

     }

     bool operator==(const small_world_iterator& other) const

     {

       if (!gen && other.gen) return other == *this;

       else if (gen && !other.gen) return source == n;

       else if (!gen && !other.gen) return true;

       return source == other.source && target == other.target;

     }

     bool operator!=(const small_world_iterator& other) const

     { return !(*this == other); }

   private:

     void next()

     {

       uniform_int<vertices_size_type> rand_vertex(0, n-1);

       current.first = rand_vertex(*gen);

       do {

         current.second = rand_vertex(*gen);

       } while (current.first == current.second && !allow_self_loops);

     }

     RandomGenerator* gen;

     vertices_size_type n;

     vertices_size_type k;

     double prob;

     vertices_size_type source;

     vertices_size_type target;

     bool allow_self_loops;

     value_type current;

   };

 } // end namespace boost

 #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP