]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
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: | |
7c673cae | 34 | typedef std::input_iterator_tag iterator_category; |
f67539c2 | 35 | typedef std::pair< vertices_size_type, vertices_size_type > value_type; |
7c673cae FG |
36 | typedef const value_type& reference; |
37 | typedef const value_type* pointer; | |
38 | typedef void difference_type; | |
39 | ||
f67539c2 | 40 | mesh_iterator() : x(0), y(0), done(true) {} |
7c673cae FG |
41 | |
42 | // Vertices are numbered in row-major order | |
43 | // Assumes directed | |
f67539c2 TL |
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 | } | |
7c673cae FG |
57 | |
58 | reference operator*() const { return current; } | |
59 | pointer operator->() const { return ¤t; } | |
f67539c2 | 60 | |
7c673cae FG |
61 | mesh_iterator& operator++() |
62 | { | |
f67539c2 TL |
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 | } | |
7c673cae | 82 | } |
f67539c2 TL |
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 | } | |
7c673cae | 98 | } |
7c673cae | 99 | } |
f67539c2 TL |
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 | } | |
7c673cae | 128 | } |
f67539c2 TL |
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 | } | |
7c673cae | 146 | } |
7c673cae | 147 | } |
7c673cae | 148 | |
f67539c2 TL |
149 | current.first = source; |
150 | current.second = target; | |
7c673cae | 151 | |
f67539c2 | 152 | return *this; |
7c673cae FG |
153 | } |
154 | ||
155 | mesh_iterator operator++(int) | |
156 | { | |
f67539c2 TL |
157 | mesh_iterator temp(*this); |
158 | ++(*this); | |
159 | return temp; | |
7c673cae FG |
160 | } |
161 | ||
162 | bool operator==(const mesh_iterator& other) const | |
163 | { | |
f67539c2 | 164 | return done == other.done; |
7c673cae FG |
165 | } |
166 | ||
167 | bool operator!=(const mesh_iterator& other) const | |
f67539c2 TL |
168 | { |
169 | return !(*this == other); | |
170 | } | |
7c673cae | 171 | |
f67539c2 TL |
172 | private: |
173 | vertices_size_type x, y; | |
7c673cae FG |
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; | |
f67539c2 | 180 | }; |
7c673cae FG |
181 | |
182 | } // end namespace boost | |
183 | ||
184 | #endif // BOOST_GRAPH_MESH_GENERATOR_HPP |