1 // Copyright 2004, 2005 The Trustees of Indiana University.
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)
7 // Authors: Nick Edmonds
9 #ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
10 #define BOOST_GRAPH_MESH_GENERATOR_HPP
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>
21 template<typename Graph>
24 typedef typename graph_traits<Graph>::directed_category directed_category;
25 typedef typename graph_traits<Graph>::vertices_size_type
30 is_undirected = (is_base_and_derived<undirected_tag,
31 directed_category>::value
32 || is_same<undirected_tag, directed_category>::value));
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;
42 : x(0), y(0), done(true) { }
44 // Vertices are numbered in row-major order
46 mesh_iterator(vertices_size_type x, vertices_size_type y,
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); }
52 reference operator*() const { return current; }
53 pointer operator->() const { return ¤t; }
55 mesh_iterator& operator++()
59 if (target == source + 1)
60 if (source < x * (y - 1))
64 target = (source % x) < x - 1 ? source + 1 : source + x;
68 else if (target == source + x) {
70 target = (source % x) < x - 1 ? source + 1 : source + x;
73 if (target == source + 1 || target == source - (source % x))
74 target = (source + x) % n;
75 else if (target == (source + x) % n) {
80 target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
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))
91 else if (source < x * (y - 1))
96 else if (target == source + 1)
97 if (source < x * (y - 1))
103 else if (target == source + x) {
105 target = (source >= x) ? source - x : source - 1;
108 if (source == n - 1 && target == (source + x) % n)
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) {
118 target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
123 current.first = source;
124 current.second = target;
129 mesh_iterator operator++(int)
131 mesh_iterator temp(*this);
136 bool operator==(const mesh_iterator& other) const
138 return done == other.done;
141 bool operator!=(const mesh_iterator& other) const
142 { return !(*this == other); }
146 vertices_size_type x,y;
147 vertices_size_type n;
148 vertices_size_type source;
149 vertices_size_type target;
156 } // end namespace boost
158 #endif // BOOST_GRAPH_MESH_GENERATOR_HPP