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 
22 namespace 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.*/
33 template<class SimplexTree>
34 class 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_;
71  Vertex_handle v_;
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.*/
79 template<class SimplexTree>
80 class 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.*/
186 template<class SimplexTree>
187 class 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;
193  typedef typename SimplexTree::Vertex_handle Vertex_handle;
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.*/
260 template<class SimplexTree>
261 class 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;
267  typedef typename SimplexTree::Vertex_handle Vertex_handle;
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
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 Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:856
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
GUDHI  Version 3.4.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Oct 26 2021 14:06:04 for GUDHI by Doxygen 1.9.1