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 22 template < typename Graph > class mesh_iterator 23 { 24 typedef typename graph_traits< Graph >::directed_category directed_category; 25 typedef 26 typename graph_traits< Graph >::vertices_size_type vertices_size_type; 27 28 BOOST_STATIC_CONSTANT(bool, 29 is_undirected 30 = (is_base_and_derived< undirected_tag, directed_category >::value 31 || is_same< undirected_tag, directed_category >::value)); 32 33 public: 34 typedef std::input_iterator_tag iterator_category; 35 typedef std::pair< vertices_size_type, vertices_size_type > value_type; 36 typedef const value_type& reference; 37 typedef const value_type* pointer; 38 typedef void difference_type; 39 mesh_iterator()40 mesh_iterator() : x(0), y(0), done(true) {} 41 42 // Vertices are numbered in row-major order 43 // Assumes directed mesh_iterator(vertices_size_type x,vertices_size_type y,bool toroidal=true)44 mesh_iterator( 45 vertices_size_type x, vertices_size_type y, bool toroidal = true) 46 : x(x) 47 , y(y) 48 , n(x * y) 49 , source(0) 50 , target(1) 51 , current(0, 1) 52 , toroidal(toroidal) 53 , done(false) 54 { 55 BOOST_ASSERT(x > 1 && y > 1); 56 } 57 operator *() const58 reference operator*() const { return current; } operator ->() const59 pointer operator->() const { return ¤t; } 60 operator ++()61 mesh_iterator& operator++() 62 { 63 if (is_undirected) 64 { 65 if (!toroidal) 66 { 67 if (target == source + 1) 68 if (source < x * (y - 1)) 69 target = source + x; 70 else 71 { 72 source++; 73 target = (source % x) < x - 1 ? source + 1 : source + x; 74 if (target > n) 75 done = true; 76 } 77 else if (target == source + x) 78 { 79 source++; 80 target = (source % x) < x - 1 ? source + 1 : source + x; 81 } 82 } 83 else 84 { 85 if (target == source + 1 || target == source - (source % x)) 86 target = (source + x) % n; 87 else if (target == (source + x) % n) 88 { 89 if (source == n - 1) 90 done = true; 91 else 92 { 93 source++; 94 target = (source % x) < (x - 1) ? source + 1 95 : source - (source % x); 96 } 97 } 98 } 99 } 100 else 101 { // Directed 102 if (!toroidal) 103 { 104 if (target == source - x) 105 target = source % x > 0 ? source - 1 : source + 1; 106 else if (target == source - 1) 107 if ((source % x) < (x - 1)) 108 target = source + 1; 109 else if (source < x * (y - 1)) 110 target = source + x; 111 else 112 { 113 done = true; 114 } 115 else if (target == source + 1) 116 if (source < x * (y - 1)) 117 target = source + x; 118 else 119 { 120 source++; 121 target = source - x; 122 } 123 else if (target == source + x) 124 { 125 source++; 126 target = (source >= x) ? source - x : source - 1; 127 } 128 } 129 else 130 { 131 if (source == n - 1 && target == (source + x) % n) 132 done = true; 133 else if (target == source - 1 || target == source + x - 1) 134 target = (source + x) % n; 135 else if (target == source + 1 136 || target == source - (source % x)) 137 target = (source - x + n) % n; 138 else if (target == (source - x + n) % n) 139 target = (source % x > 0) ? source - 1 : source + x - 1; 140 else if (target == (source + x) % n) 141 { 142 source++; 143 target = (source % x) < (x - 1) ? source + 1 144 : source - (source % x); 145 } 146 } 147 } 148 149 current.first = source; 150 current.second = target; 151 152 return *this; 153 } 154 operator ++(int)155 mesh_iterator operator++(int) 156 { 157 mesh_iterator temp(*this); 158 ++(*this); 159 return temp; 160 } 161 operator ==(const mesh_iterator & other) const162 bool operator==(const mesh_iterator& other) const 163 { 164 return done == other.done; 165 } 166 operator !=(const mesh_iterator & other) const167 bool operator!=(const mesh_iterator& other) const 168 { 169 return !(*this == other); 170 } 171 172 private: 173 vertices_size_type x, y; 174 vertices_size_type n; 175 vertices_size_type source; 176 vertices_size_type target; 177 value_type current; 178 bool toroidal; 179 bool done; 180 }; 181 182 } // end namespace boost 183 184 #endif // BOOST_GRAPH_MESH_GENERATOR_HPP 185