All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
Loading...
Searching...
No Matches
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 * - 2022/04 Vincent Rouvreau: Add Simplex_tree_boundary_opposite_vertex_simplex_iterator for alpha and cech purpose
9 * - YYYY/MM Author: Description of the modification
10 */
11
12#ifndef SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
13#define SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
14
15#include <gudhi/Debug_utils.h>
16
17#include <boost/iterator/iterator_facade.hpp>
18#include <boost/container/static_vector.hpp>
19
20#include <vector>
21#include <utility> // for std::pair
22
23namespace Gudhi {
24
34template<class SimplexTree>
35class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
36 Simplex_tree_simplex_vertex_iterator<SimplexTree>,
37 typename SimplexTree::Vertex_handle const, boost::forward_traversal_tag,
38 typename SimplexTree::Vertex_handle const> {
39 public:
40 typedef typename SimplexTree::Simplex_handle Simplex_handle;
41 typedef typename SimplexTree::Siblings Siblings;
43
45 : // any end() iterator
46 sib_(nullptr),
47 v_(st->null_vertex()) {
48 }
49
50 Simplex_tree_simplex_vertex_iterator(SimplexTree const* st, Simplex_handle sh)
51 : sib_(st->self_siblings(sh)),
52 v_(sh->first) {
53 }
54
55 private:
56 friend class boost::iterator_core_access;
57
58 bool equal(Simplex_tree_simplex_vertex_iterator const &other) const {
59 return sib_ == other.sib_ && v_ == other.v_;
60 }
61
62 Vertex_handle const& dereference() const {
63 return v_;
64 }
65
66 void increment() {
67 v_ = sib_->parent();
68 sib_ = sib_->oncles();
69 }
70
71 Siblings * sib_;
73};
74
75/*---------------------------------------------------------------------------*/
80template<class SimplexTree>
81class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
82 Simplex_tree_boundary_simplex_iterator<SimplexTree>,
83 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
84 public:
85 typedef typename SimplexTree::Simplex_handle Simplex_handle;
87 typedef typename SimplexTree::Siblings Siblings;
88
89 // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is overwritten.
91 : sib_(nullptr),
92 st_(nullptr) {
93 }
94
95// any end() iterator
97 : last_(st->null_vertex()),
98 next_(st->null_vertex()),
99 sib_(nullptr),
100 sh_(st->null_simplex()),
101 st_(st) {
102 }
103
104 template<class SimplexHandle>
106 : last_(sh->first),
107 next_(st->null_vertex()),
108 sib_(nullptr),
109 sh_(st->null_simplex()),
110 st_(st) {
111 // Only check once at the beginning instead of for every increment, as this is expensive.
112 if (SimplexTree::Options::contiguous_vertices)
113 GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
114 Siblings * sib = st->self_siblings(sh);
115 next_ = sib->parent();
116 sib_ = sib->oncles();
117 if (sib_ != nullptr) {
118 if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
119 // Only relevant for edges
120 sh_ = sib_->members_.begin()+next_;
121 else
122 sh_ = sib_->find(next_);
123 }
124 }
125
126 private:
127 friend class boost::iterator_core_access;
128 // valid when iterating along the SAME boundary.
129 bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
130 return sh_ == other.sh_;
131 }
132
133 Simplex_handle const& dereference() const {
134 assert(sh_ != st_->null_simplex());
135 return sh_;
136 }
137
138 void increment() {
139 if (sib_ == nullptr) {
140 sh_ = st_->null_simplex();
141 return;
142 }
143
144 Siblings * for_sib = sib_;
145 Siblings * new_sib = sib_->oncles();
146 auto rit = suffix_.rbegin();
147 if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
148 // We reached the root, use a short-cut to find a vertex.
149 if (rit == suffix_.rend()) {
150 // Segment, this vertex is the last boundary simplex
151 sh_ = for_sib->members_.begin()+last_;
152 sib_ = nullptr;
153 return;
154 } else {
155 // Dim >= 2, initial step of the descent
156 sh_ = for_sib->members_.begin()+*rit;
157 for_sib = sh_->second.children();
158 ++rit;
159 }
160 }
161 for (; rit != suffix_.rend(); ++rit) {
162 sh_ = for_sib->find(*rit);
163 for_sib = sh_->second.children();
164 }
165 sh_ = for_sib->find(last_); // sh_ points to the right simplex now
166 suffix_.push_back(next_);
167 next_ = sib_->parent();
168 sib_ = new_sib;
169 }
170
171 // Most of the storage should be moved to the range, iterators should be light.
172 Vertex_handle last_; // last vertex of the simplex
173 Vertex_handle next_; // next vertex to push in suffix_
174 // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
175 // as it would not fit on the biggest hard-drive.
176 boost::container::static_vector<Vertex_handle, 40> suffix_;
177 // static_vector still has some overhead compared to a trivial hand-made
178 // version using std::aligned_storage, or compared to making suffix_ static.
179 Siblings * sib_; // where the next search will start from
180 Simplex_handle sh_; // current Simplex_handle in the boundary
181 SimplexTree * st_; // simplex containing the simplicial complex
182};
183
187template<class SimplexTree>
188class Simplex_tree_boundary_opposite_vertex_simplex_iterator : public boost::iterator_facade<
189 Simplex_tree_boundary_opposite_vertex_simplex_iterator<SimplexTree>,
190 std::pair<typename SimplexTree::Simplex_handle, typename SimplexTree::Vertex_handle> const, boost::forward_traversal_tag> {
191 public:
192 using Simplex_handle = typename SimplexTree::Simplex_handle;
193 using Vertex_handle = typename SimplexTree::Vertex_handle;
194 using Siblings = typename SimplexTree::Siblings;
195
196 // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is
197 // overwritten.
199 : sib_(nullptr),
200 st_(nullptr) {
201 }
202
203 // any end() iterator
205 : last_(st->null_vertex()),
206 next_(st->null_vertex()),
207 sib_(nullptr),
208 baov_(st->null_simplex(), st->null_vertex()),
209 st_(st) {
210 }
211
212 template<class SimplexHandle>
214 : last_(sh->first),
215 next_(st->null_vertex()),
216 sib_(nullptr),
217 baov_(st->null_simplex(), sh->first),
218 st_(st) {
219 // Only check once at the beginning instead of for every increment, as this is expensive.
220 if (SimplexTree::Options::contiguous_vertices)
221 GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
222 Siblings * sib = st->self_siblings(sh);
223 next_ = sib->parent();
224 sib_ = sib->oncles();
225 if (sib_ != nullptr) {
226 if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
227 // Only relevant for edges
228 baov_.first = sib_->members_.begin()+next_;
229 else
230 baov_.first = sib_->find(next_);
231 }
232 }
233
234 private:
235 friend class boost::iterator_core_access;
236
237 // valid when iterating along the SAME boundary.
238 bool equal(Simplex_tree_boundary_opposite_vertex_simplex_iterator const& other) const {
239 return (baov_.first == other.baov_.first);
240 }
241
242 std::pair<Simplex_handle, Vertex_handle> const& dereference() const {
243 return baov_;
244 }
245
246 void increment() {
247 if (sib_ == nullptr) {
248 baov_.first = st_->null_simplex();
249 return; // ------>>
250 }
251 Siblings * for_sib = sib_;
252 Siblings * new_sib = sib_->oncles();
253 auto rit = suffix_.rbegin();
254 if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
255 // We reached the root, use a short-cut to find a vertex.
256 if (rit == suffix_.rend()) {
257 baov_.second = baov_.first->first;
258 // Segment, this vertex is the last boundary simplex
259 baov_.first = for_sib->members_.begin()+last_;
260 sib_ = nullptr;
261 return;
262 } else {
263 // Dim >= 2, initial step of the descent
264 baov_.first = for_sib->members_.begin()+*rit;
265 for_sib = baov_.first->second.children();
266 ++rit;
267 }
268 }
269 for (; rit != suffix_.rend(); ++rit) {
270 baov_.first = for_sib->find(*rit);
271 for_sib = baov_.first->second.children();
272 }
273 baov_.first = for_sib->find(last_); // baov_.first points to the right simplex now
274 suffix_.push_back(next_);
275 next_ = sib_->parent();
276 sib_ = new_sib;
277 baov_.second = suffix_.back();
278 }
279
280 // Most of the storage should be moved to the range, iterators should be light.
281 Vertex_handle last_; // last vertex of the simplex
282 Vertex_handle next_; // next vertex to push in suffix_
283 // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
284 // as it would not fit on the biggest hard-drive.
285 boost::container::static_vector<Vertex_handle, 40> suffix_;
286 // static_vector still has some overhead compared to a trivial hand-made
287 // version using std::aligned_storage, or compared to making suffix_ static.
288 Siblings * sib_; // where the next search will start from
289 std::pair<Simplex_handle, Vertex_handle> baov_; // a pair containing the current Simplex_handle in the boundary and its opposite vertex
290 SimplexTree * st_; // simplex containing the simplicial complex
291};
292
293/*---------------------------------------------------------------------------*/
297template<class SimplexTree>
298class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
299 Simplex_tree_complex_simplex_iterator<SimplexTree>,
300 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
301 public:
302 typedef typename SimplexTree::Simplex_handle Simplex_handle;
303 typedef typename SimplexTree::Siblings Siblings;
305
306// any end() iterator
308 : sib_(nullptr),
309 st_(nullptr) {
310 }
311
313 : sib_(nullptr),
314 st_(st) {
315 if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
316 st_ = nullptr;
317 } else {
318 sh_ = st->root()->members().begin();
319 sib_ = st->root();
320 while (st->has_children(sh_)) {
321 sib_ = sh_->second.children();
322 sh_ = sib_->members().begin();
323 }
324 }
325 }
326 private:
327 friend class boost::iterator_core_access;
328
329// valid when iterating along the SAME boundary.
330 bool equal(Simplex_tree_complex_simplex_iterator const& other) const {
331 if (other.st_ == nullptr) {
332 return (st_ == nullptr);
333 }
334 if (st_ == nullptr) {
335 return false;
336 }
337 return (&(sh_->second) == &(other.sh_->second));
338 }
339
340 Simplex_handle const& dereference() const {
341 return sh_;
342 }
343
344// Depth first traversal.
345 void increment() {
346 ++sh_;
347 if (sh_ == sib_->members().end()) {
348 if (sib_->oncles() == nullptr) {
349 st_ = nullptr;
350 return;
351 } // reach the end
352 sh_ = sib_->oncles()->members().find(sib_->parent());
353 sib_ = sib_->oncles();
354 return;
355 }
356 while (st_->has_children(sh_)) {
357 sib_ = sh_->second.children();
358 sh_ = sib_->members().begin();
359 }
360 }
361
362 Simplex_handle sh_;
363 Siblings * sib_;
364 SimplexTree * st_;
365};
366
371template<class SimplexTree>
372class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
373 Simplex_tree_skeleton_simplex_iterator<SimplexTree>,
374 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
375 public:
376 typedef typename SimplexTree::Simplex_handle Simplex_handle;
377 typedef typename SimplexTree::Siblings Siblings;
379
380// any end() iterator
382 : sib_(nullptr),
383 st_(nullptr),
384 dim_skel_(0),
385 curr_dim_(0) {
386 }
387
389 : sib_(nullptr),
390 st_(st),
391 dim_skel_(dim_skel),
392 curr_dim_(0) {
393 if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
394 st_ = nullptr;
395 } else {
396 sh_ = st->root()->members().begin();
397 sib_ = st->root();
398 while (st->has_children(sh_) && curr_dim_ < dim_skel_) {
399 sib_ = sh_->second.children();
400 sh_ = sib_->members().begin();
401 ++curr_dim_;
402 }
403 }
404 }
405 private:
406 friend class boost::iterator_core_access;
407
408// valid when iterating along the SAME boundary.
409 bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const {
410 if (other.st_ == nullptr) {
411 return (st_ == nullptr);
412 }
413 if (st_ == nullptr) {
414 return false;
415 }
416 return (&(sh_->second) == &(other.sh_->second));
417 }
418
419 Simplex_handle const& dereference() const {
420 return sh_;
421 }
422
423// Depth first traversal of the skeleton.
424 void increment() {
425 ++sh_;
426 if (sh_ == sib_->members().end()) {
427 if (sib_->oncles() == nullptr) {
428 st_ = nullptr;
429 return;
430 } // reach the end
431 sh_ = sib_->oncles()->members().find(sib_->parent());
432 sib_ = sib_->oncles();
433 --curr_dim_;
434 return;
435 }
436 while (st_->has_children(sh_) && curr_dim_ < dim_skel_) {
437 sib_ = sh_->second.children();
438 sh_ = sib_->members().begin();
439 ++curr_dim_;
440 }
441 }
442
443 Simplex_handle sh_;
444 Siblings * sib_;
445 SimplexTree * st_;
446 int dim_skel_;
447 int curr_dim_;
448};
449 // end addtogroup simplex_tree
451
452} // namespace Gudhi
453
454#endif // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
Iterator over the simplices of the boundary of a simplex and their opposite vertices.
Definition: Simplex_tree_iterators.h:190
Iterator over the simplices of the boundary of a simplex.
Definition: Simplex_tree_iterators.h:83
Iterator over the simplices of a simplicial complex.
Definition: Simplex_tree_iterators.h:300
Iterator over the vertices of a simplex in a SimplexTree.
Definition: Simplex_tree_iterators.h:38
Iterator over the simplices of the skeleton of a given dimension of the simplicial complex.
Definition: Simplex_tree_iterators.h:374
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:83
static Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:893
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:156
Vertex_handle null_vertex() const
Returns a Vertex_handle different from all Vertex_handles associated to the vertices of the simplicia...
Definition: Simplex_tree.h:571
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:637
Simplex_tree_siblings< Simplex_tree, Dictionary > Siblings
Set of nodes sharing a same parent in the simplex tree.
Definition: Simplex_tree.h:109
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:98
Siblings * root()
Definition: Simplex_tree.h:902
static Simplex_handle null_simplex()
Returns a Simplex_handle different from all Simplex_handles associated to the simplices in the simpli...
Definition: Simplex_tree.h:560
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15