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 ¤t; } |
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 |
159 | |