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 
23 namespace Gudhi {
24 
34 template<class SimplexTree>
35 class 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_;
72  Vertex_handle v_;
73 };
74 
75 /*---------------------------------------------------------------------------*/
80 template<class SimplexTree>
81 class 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.
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 
187 template<class SimplexTree>
188 class 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.
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 /*---------------------------------------------------------------------------*/
297 template<class SimplexTree>
298 class 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;
304  typedef typename SimplexTree::Vertex_handle Vertex_handle;
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 
371 template<class SimplexTree>
372 class 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;
378  typedef typename SimplexTree::Vertex_handle Vertex_handle;
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:79
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:152
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:567
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:628
Siblings * root()
Definition: Simplex_tree.h:891
Simplex_tree_siblings< Simplex_tree, Dictionary > Siblings
Set of nodes sharing a same parent in the simplex tree.
Definition: Simplex_tree.h:105
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:94
static Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:882
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:556
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