Simplex_tree_iterators.h
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Clément Maria
4 *
5 * Copyright (C) 2014 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
12#define SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
13
14#include <gudhi/Debug_utils.h>
15
16#include <boost/iterator/iterator_facade.hpp>
17#include <boost/version.hpp>
18#include <boost/container/static_vector.hpp>
19
20#include <vector>
21
22namespace Gudhi {
23
24/* \addtogroup simplex_tree
25 * Iterators and range types for the Simplex_tree.
26 * @{
27 */
28
29/* \brief Iterator over the vertices of a simplex
30 * in a SimplexTree.
31 *
32 * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/
33template<class SimplexTree>
34class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
35 Simplex_tree_simplex_vertex_iterator<SimplexTree>,
36 typename SimplexTree::Vertex_handle const, boost::forward_traversal_tag,
37 typename SimplexTree::Vertex_handle const> {
38 public:
39 typedef typename SimplexTree::Simplex_handle Simplex_handle;
40 typedef typename SimplexTree::Siblings Siblings;
42
43 explicit Simplex_tree_simplex_vertex_iterator(SimplexTree const* st)
44 : // any end() iterator
45 sib_(nullptr),
46 v_(st->null_vertex()) {
47 }
48
49 Simplex_tree_simplex_vertex_iterator(SimplexTree const* st, Simplex_handle sh)
50 : sib_(st->self_siblings(sh)),
51 v_(sh->first) {
52 }
53
54 private:
55 friend class boost::iterator_core_access;
56
57 bool equal(Simplex_tree_simplex_vertex_iterator const &other) const {
58 return sib_ == other.sib_ && v_ == other.v_;
59 }
60
61 Vertex_handle const& dereference() const {
62 return v_;
63 }
64
65 void increment() {
66 v_ = sib_->parent();
67 sib_ = sib_->oncles();
68 }
69
70 Siblings * sib_;
72};
73
74/*---------------------------------------------------------------------------*/
75/* \brief Iterator over the simplices of the boundary of a
76 * simplex.
77 *
78 * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
79template<class SimplexTree>
80class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
81 Simplex_tree_boundary_simplex_iterator<SimplexTree>,
82 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
83 public:
84 typedef typename SimplexTree::Simplex_handle Simplex_handle;
86 typedef typename SimplexTree::Siblings Siblings;
87
88 // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is overwritten.
89 Simplex_tree_boundary_simplex_iterator()
90 : sib_(nullptr),
91 st_(nullptr) {
92 }
93
94// any end() iterator
95 explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
96 : last_(st->null_vertex()),
97 next_(st->null_vertex()),
98 sib_(nullptr),
99 sh_(st->null_simplex()),
100 st_(st) {
101 }
102
103 template<class SimplexHandle>
104 Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh)
105 : last_(sh->first),
106 next_(st->null_vertex()),
107 sib_(nullptr),
108 sh_(st->null_simplex()),
109 st_(st) {
110 // Only check once at the beginning instead of for every increment, as this is expensive.
112 GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
113 Siblings * sib = st->self_siblings(sh);
114 next_ = sib->parent();
115 sib_ = sib->oncles();
116 if (sib_ != nullptr) {
117 if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
118 // Only relevant for edges
119 sh_ = sib_->members_.begin()+next_;
120 else
121 sh_ = sib_->find(next_);
122 }
123 }
124
125 private:
126 friend class boost::iterator_core_access;
127// valid when iterating along the SAME boundary.
128 bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
129 return sh_ == other.sh_;
130 }
131
132 Simplex_handle const& dereference() const {
133 assert(sh_ != st_->null_simplex());
134 return sh_;
135 }
136
137 void increment() {
138 if (sib_ == nullptr) {
139 sh_ = st_->null_simplex();
140 return;
141 }
142
143 Siblings * for_sib = sib_;
144 Siblings * new_sib = sib_->oncles();
145 auto rit = suffix_.rbegin();
146 if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
147 // We reached the root, use a short-cut to find a vertex.
148 if (rit == suffix_.rend()) {
149 // Segment, this vertex is the last boundary simplex
150 sh_ = for_sib->members_.begin()+last_;
151 sib_ = nullptr;
152 return;
153 } else {
154 // Dim >= 2, initial step of the descent
155 sh_ = for_sib->members_.begin()+*rit;
156 for_sib = sh_->second.children();
157 ++rit;
158 }
159 }
160 for (; rit != suffix_.rend(); ++rit) {
161 sh_ = for_sib->find(*rit);
162 for_sib = sh_->second.children();
163 }
164 sh_ = for_sib->find(last_); // sh_ points to the right simplex now
165 suffix_.push_back(next_);
166 next_ = sib_->parent();
167 sib_ = new_sib;
168 }
169
170 // Most of the storage should be moved to the range, iterators should be light.
171 Vertex_handle last_; // last vertex of the simplex
172 Vertex_handle next_; // next vertex to push in suffix_
173 // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
174 // as it would not fit on the biggest hard-drive.
175 boost::container::static_vector<Vertex_handle, 40> suffix_;
176 // static_vector still has some overhead compared to a trivial hand-made
177 // version using std::aligned_storage, or compared to making suffix_ static.
178 Siblings * sib_; // where the next search will start from
179 Simplex_handle sh_; // current Simplex_handle in the boundary
180 SimplexTree * st_; // simplex containing the simplicial complex
181};
182/*---------------------------------------------------------------------------*/
183/* \brief Iterator over the simplices of a simplicial complex.
184 *
185 * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
186template<class SimplexTree>
187class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
188 Simplex_tree_complex_simplex_iterator<SimplexTree>,
189 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
190 public:
191 typedef typename SimplexTree::Simplex_handle Simplex_handle;
192 typedef typename SimplexTree::Siblings Siblings;
194
195// any end() iterator
196 Simplex_tree_complex_simplex_iterator()
197 : sib_(nullptr),
198 st_(nullptr) {
199 }
200
201 explicit Simplex_tree_complex_simplex_iterator(SimplexTree * st)
202 : sib_(nullptr),
203 st_(st) {
204 if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
205 st_ = nullptr;
206 } else {
207 sh_ = st->root()->members().begin();
208 sib_ = st->root();
209 while (st->has_children(sh_)) {
210 sib_ = sh_->second.children();
211 sh_ = sib_->members().begin();
212 }
213 }
214 }
215 private:
216 friend class boost::iterator_core_access;
217
218// valid when iterating along the SAME boundary.
219 bool equal(Simplex_tree_complex_simplex_iterator const& other) const {
220 if (other.st_ == nullptr) {
221 return (st_ == nullptr);
222 }
223 if (st_ == nullptr) {
224 return false;
225 }
226 return (&(sh_->second) == &(other.sh_->second));
227 }
228
229 Simplex_handle const& dereference() const {
230 return sh_;
231 }
232
233// Depth first traversal.
234 void increment() {
235 ++sh_;
236 if (sh_ == sib_->members().end()) {
237 if (sib_->oncles() == nullptr) {
238 st_ = nullptr;
239 return;
240 } // reach the end
241 sh_ = sib_->oncles()->members().find(sib_->parent());
242 sib_ = sib_->oncles();
243 return;
244 }
245 while (st_->has_children(sh_)) {
246 sib_ = sh_->second.children();
247 sh_ = sib_->members().begin();
248 }
249 }
250
251 Simplex_handle sh_;
252 Siblings * sib_;
253 SimplexTree * st_;
254};
255
256/* \brief Iterator over the simplices of the skeleton of a given
257 * dimension of the simplicial complex.
258 *
259 * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
260template<class SimplexTree>
261class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
262 Simplex_tree_skeleton_simplex_iterator<SimplexTree>,
263 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
264 public:
265 typedef typename SimplexTree::Simplex_handle Simplex_handle;
266 typedef typename SimplexTree::Siblings Siblings;
268
269// any end() iterator
270 Simplex_tree_skeleton_simplex_iterator()
271 : sib_(nullptr),
272 st_(nullptr),
273 dim_skel_(0),
274 curr_dim_(0) {
275 }
276
277 Simplex_tree_skeleton_simplex_iterator(SimplexTree * st, int dim_skel)
278 : sib_(nullptr),
279 st_(st),
280 dim_skel_(dim_skel),
281 curr_dim_(0) {
282 if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
283 st_ = nullptr;
284 } else {
285 sh_ = st->root()->members().begin();
286 sib_ = st->root();
287 while (st->has_children(sh_) && curr_dim_ < dim_skel_) {
288 sib_ = sh_->second.children();
289 sh_ = sib_->members().begin();
290 ++curr_dim_;
291 }
292 }
293 }
294 private:
295 friend class boost::iterator_core_access;
296
297// valid when iterating along the SAME boundary.
298 bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const {
299 if (other.st_ == nullptr) {
300 return (st_ == nullptr);
301 }
302 if (st_ == nullptr) {
303 return false;
304 }
305 return (&(sh_->second) == &(other.sh_->second));
306 }
307
308 Simplex_handle const& dereference() const {
309 return sh_;
310 }
311
312// Depth first traversal of the skeleton.
313 void increment() {
314 ++sh_;
315 if (sh_ == sib_->members().end()) {
316 if (sib_->oncles() == nullptr) {
317 st_ = nullptr;
318 return;
319 } // reach the end
320 sh_ = sib_->oncles()->members().find(sib_->parent());
321 sib_ = sib_->oncles();
322 --curr_dim_;
323 return;
324 }
325 while (st_->has_children(sh_) && curr_dim_ < dim_skel_) {
326 sib_ = sh_->second.children();
327 sh_ = sib_->members().begin();
328 ++curr_dim_;
329 }
330 }
331
332 Simplex_handle sh_;
333 Siblings * sib_;
334 SimplexTree * st_;
335 int dim_skel_;
336 int curr_dim_;
337};
338
339/* @} */ // end addtogroup simplex_tree
340} // namespace Gudhi
341
342#endif // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:75
static Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:856
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:149
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:602
Siblings * root()
Definition: Simplex_tree.h:865
static constexpr bool contiguous_vertices
If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1,...
Definition: SimplexTreeOptions.h:29
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Aug 16 2022 14:01:50 for GUDHIdev by Doxygen 1.9.4