]>
Commit | Line | Data |
---|---|---|
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 |