git.sesse.net Git - casparcg/blob - dependencies64/boost/boost/graph/mesh_graph_generator.hpp

   1 // Copyright 2004, 2005 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Nick Edmonds
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
  10 #define BOOST_GRAPH_MESH_GENERATOR_HPP
  11
  12 #include <iterator>
  13 #include <utility>
  14 #include <boost/assert.hpp>
  15 #include <boost/graph/graph_traits.hpp>
  16 #include <boost/type_traits/is_base_and_derived.hpp>
  17 #include <boost/type_traits/is_same.hpp>
  18
  19 namespace boost {
  20
  21   template<typename Graph>
  22   class mesh_iterator
  23   {
  24     typedef typename graph_traits<Graph>::directed_category directed_category;
  25     typedef typename graph_traits<Graph>::vertices_size_type
  26       vertices_size_type;
  27
  28     BOOST_STATIC_CONSTANT
  29       (bool,
  30        is_undirected = (is_base_and_derived<undirected_tag,
  31                                             directed_category>::value
  32                         || is_same<undirected_tag, directed_category>::value));
  33
  34   public:
  35     typedef std::input_iterator_tag iterator_category;
  36     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
  37     typedef const value_type& reference;
  38     typedef const value_type* pointer;
  39     typedef void difference_type;
  40
  41     mesh_iterator()
  42       : x(0), y(0), done(true) { }
  43
  44     // Vertices are numbered in row-major order
  45     // Assumes directed
  46     mesh_iterator(vertices_size_type x, vertices_size_type y,
  47                   bool toroidal = true)
  48       : x(x), y(y), n(x*y), source(0), target(1), current(0,1),
  49         toroidal(toroidal), done(false)
  50     { BOOST_ASSERT(x > 1 && y > 1); }
  51
  52     reference operator*() const { return current; }
  53     pointer operator->() const { return &current; }
  54
  55     mesh_iterator& operator++()
  56     {
  57       if (is_undirected) {
  58         if (!toroidal) {
  59           if (target == source + 1)
  60             if (source < x * (y - 1))
  61               target = source + x;
  62             else {
  63               source++;
  64               target = (source % x) < x - 1 ? source + 1 : source + x;
  65               if (target > n)
  66                 done = true;
  67             }
  68           else if (target == source + x) {
  69             source++;
  70             target = (source % x) < x - 1 ? source + 1 : source + x;
  71           }
  72         } else {
  73           if (target == source + 1 || target == source - (source % x))
  74             target = (source + x) % n;
  75           else if (target == (source + x) % n) {
  76             if (source == n - 1)
  77               done = true;
  78             else {
  79               source++;
  80               target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
  81             }
  82           }
  83         }
  84       } else { // Directed
  85         if ( !toroidal ) {
  86           if (target == source - x)
  87             target = source % x > 0 ? source - 1 : source + 1;
  88           else if (target == source - 1)
  89             if ((source % x) < (x - 1))
  90               target = source + 1;
  91             else if (source < x * (y - 1))
  92               target = source + x;
  93             else {
  94               done = true;
  95             }
  96           else if (target == source + 1)
  97             if (source < x * (y - 1))
  98               target = source + x;
  99             else {
 100               source++;
 101               target = source - x;
 102             }
 103           else if (target == source + x) {
 104             source++;
 105             target = (source >= x) ? source - x : source - 1;
 106           }
 107         } else {
 108           if (source == n - 1 && target == (source + x) % n)
 109             done = true;
 110           else if (target == source - 1 || target == source + x - 1)
 111             target = (source + x) % n;
 112           else if (target == source + 1 || target == source - (source % x))
 113             target = (source - x + n) % n;
 114           else if (target == (source - x + n) % n)
 115             target = (source % x > 0) ? source - 1 : source + x - 1;
 116           else if (target == (source + x) % n) {
 117             source++;
 118             target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
 119           }
 120         }
 121       }
 122
 123       current.first = source;
 124       current.second = target;
 125
 126       return *this;
 127     }
 128
 129     mesh_iterator operator++(int)
 130     {
 131       mesh_iterator temp(*this);
 132       ++(*this);
 133       return temp;
 134     }
 135
 136     bool operator==(const mesh_iterator& other) const
 137     {
 138       return done == other.done;
 139     }
 140
 141     bool operator!=(const mesh_iterator& other) const
 142     { return !(*this == other); }
 143
 144   private:
 145
 146     vertices_size_type x,y;
 147     vertices_size_type n;
 148     vertices_size_type source;
 149     vertices_size_type target;
 150     value_type current;
 151     bool toroidal;
 152     bool done;
 153   };
 154
 155
 156 } // end namespace boost
 157
 158 #endif // BOOST_GRAPH_MESH_GENERATOR_HPP