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 // any end() iterator
89  explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
90  : last_(st->null_vertex()),
91  next_(st->null_vertex()),
92  sib_(nullptr),
93  sh_(st->null_simplex()),
94  st_(st) {
95  }
96 
97  template<class SimplexHandle>
98  Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh)
99  : last_(sh->first),
100  next_(st->null_vertex()),
101  sib_(nullptr),
102  sh_(st->null_simplex()),
103  st_(st) {
104  // Only check once at the beginning instead of for every increment, as this is expensive.
106  GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
107  Siblings * sib = st->self_siblings(sh);
108  next_ = sib->parent();
109  sib_ = sib->oncles();
110  if (sib_ != nullptr) {
111  if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
112  // Only relevant for edges
113  sh_ = sib_->members_.begin()+next_;
114  else
115  sh_ = sib_->find(next_);
116  }
117  }
118 
119  private:
120  friend class boost::iterator_core_access;
121 // valid when iterating along the SAME boundary.
122  bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
123  return sh_ == other.sh_;
124  }
125 
126  Simplex_handle const& dereference() const {
127  assert(sh_ != st_->null_simplex());
128  return sh_;
129  }
130 
131  void increment() {
132  if (sib_ == nullptr) {
133  sh_ = st_->null_simplex();
134  return;
135  }
136 
137  Siblings * for_sib = sib_;
138  Siblings * new_sib = sib_->oncles();
139  auto rit = suffix_.rbegin();
140  if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
141  // We reached the root, use a short-cut to find a vertex.
142  if (rit == suffix_.rend()) {
143  // Segment, this vertex is the last boundary simplex
144  sh_ = for_sib->members_.begin()+last_;
145  sib_ = nullptr;
146  return;
147  } else {
148  // Dim >= 2, initial step of the descent
149  sh_ = for_sib->members_.begin()+*rit;
150  for_sib = sh_->second.children();
151  ++rit;
152  }
153  }
154  for (; rit != suffix_.rend(); ++rit) {
155  sh_ = for_sib->find(*rit);
156  for_sib = sh_->second.children();
157  }
158  sh_ = for_sib->find(last_); // sh_ points to the right simplex now
159  suffix_.push_back(next_);
160  next_ = sib_->parent();
161  sib_ = new_sib;
162  }
163 
164  // Most of the storage should be moved to the range, iterators should be light.
165  Vertex_handle last_; // last vertex of the simplex
166  Vertex_handle next_; // next vertex to push in suffix_
167  // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
168  // as it would not fit on the biggest hard-drive.
169  boost::container::static_vector<Vertex_handle, 40> suffix_;
170  // static_vector still has some overhead compared to a trivial hand-made
171  // version using std::aligned_storage, or compared to making suffix_ static.
172  Siblings * sib_; // where the next search will start from
173  Simplex_handle sh_; // current Simplex_handle in the boundary
174  SimplexTree * st_; // simplex containing the simplicial complex
175 };
176 /*---------------------------------------------------------------------------*/
177 /* \brief Iterator over the simplices of a simplicial complex.
178  *
179  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
180 template<class SimplexTree>
181 class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
182  Simplex_tree_complex_simplex_iterator<SimplexTree>,
183  typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
184  public:
185  typedef typename SimplexTree::Simplex_handle Simplex_handle;
186  typedef typename SimplexTree::Siblings Siblings;
187  typedef typename SimplexTree::Vertex_handle Vertex_handle;
188 
189 // any end() iterator
190  Simplex_tree_complex_simplex_iterator()
191  : sib_(nullptr),
192  st_(nullptr) {
193  }
194 
195  explicit Simplex_tree_complex_simplex_iterator(SimplexTree * st)
196  : sib_(nullptr),
197  st_(st) {
198  if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
199  st_ = nullptr;
200  } else {
201  sh_ = st->root()->members().begin();
202  sib_ = st->root();
203  while (st->has_children(sh_)) {
204  sib_ = sh_->second.children();
205  sh_ = sib_->members().begin();
206  }
207  }
208  }
209  private:
210  friend class boost::iterator_core_access;
211 
212 // valid when iterating along the SAME boundary.
213  bool equal(Simplex_tree_complex_simplex_iterator const& other) const {
214  if (other.st_ == nullptr) {
215  return (st_ == nullptr);
216  }
217  if (st_ == nullptr) {
218  return false;
219  }
220  return (&(sh_->second) == &(other.sh_->second));
221  }
222 
223  Simplex_handle const& dereference() const {
224  return sh_;
225  }
226 
227 // Depth first traversal.
228  void increment() {
229  ++sh_;
230  if (sh_ == sib_->members().end()) {
231  if (sib_->oncles() == nullptr) {
232  st_ = nullptr;
233  return;
234  } // reach the end
235  sh_ = sib_->oncles()->members().find(sib_->parent());
236  sib_ = sib_->oncles();
237  return;
238  }
239  while (st_->has_children(sh_)) {
240  sib_ = sh_->second.children();
241  sh_ = sib_->members().begin();
242  }
243  }
244 
245  Simplex_handle sh_;
246  Siblings * sib_;
247  SimplexTree * st_;
248 };
249 
250 /* \brief Iterator over the simplices of the skeleton of a given
251  * dimension of the simplicial complex.
252  *
253  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
254 template<class SimplexTree>
255 class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
256  Simplex_tree_skeleton_simplex_iterator<SimplexTree>,
257  typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
258  public:
259  typedef typename SimplexTree::Simplex_handle Simplex_handle;
260  typedef typename SimplexTree::Siblings Siblings;
261  typedef typename SimplexTree::Vertex_handle Vertex_handle;
262 
263 // any end() iterator
264  Simplex_tree_skeleton_simplex_iterator()
265  : sib_(nullptr),
266  st_(nullptr),
267  dim_skel_(0),
268  curr_dim_(0) {
269  }
270 
271  Simplex_tree_skeleton_simplex_iterator(SimplexTree * st, int dim_skel)
272  : sib_(nullptr),
273  st_(st),
274  dim_skel_(dim_skel),
275  curr_dim_(0) {
276  if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
277  st_ = nullptr;
278  } else {
279  sh_ = st->root()->members().begin();
280  sib_ = st->root();
281  while (st->has_children(sh_) && curr_dim_ < dim_skel_) {
282  sib_ = sh_->second.children();
283  sh_ = sib_->members().begin();
284  ++curr_dim_;
285  }
286  }
287  }
288  private:
289  friend class boost::iterator_core_access;
290 
291 // valid when iterating along the SAME boundary.
292  bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const {
293  if (other.st_ == nullptr) {
294  return (st_ == nullptr);
295  }
296  if (st_ == nullptr) {
297  return false;
298  }
299  return (&(sh_->second) == &(other.sh_->second));
300  }
301 
302  Simplex_handle const& dereference() const {
303  return sh_;
304  }
305 
306 // Depth first traversal of the skeleton.
307  void increment() {
308  ++sh_;
309  if (sh_ == sib_->members().end()) {
310  if (sib_->oncles() == nullptr) {
311  st_ = nullptr;
312  return;
313  } // reach the end
314  sh_ = sib_->oncles()->members().find(sib_->parent());
315  sib_ = sib_->oncles();
316  --curr_dim_;
317  return;
318  }
319  while (st_->has_children(sh_) && curr_dim_ < dim_skel_) {
320  sib_ = sh_->second.children();
321  sh_ = sib_->members().begin();
322  ++curr_dim_;
323  }
324  }
325 
326  Simplex_handle sh_;
327  Siblings * sib_;
328  SimplexTree * st_;
329  int dim_skel_;
330  int curr_dim_;
331 };
332 
333 /* @} */ // end addtogroup simplex_tree
334 } // namespace Gudhi
335 
336 #endif // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
Gudhi::Simplex_tree::has_children
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
Gudhi::Simplex_tree::Simplex_handle
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:149
VertexHandle
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
SimplexTreeOptions::contiguous_vertices
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
Gudhi::Simplex_tree::self_siblings
static Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:856
Gudhi::Simplex_tree::root
Siblings * root()
Definition: Simplex_tree.h:865
Gudhi::Simplex_tree
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:75
GUDHI  Version 3.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Oct 30 2020 17:07:14 for GUDHI by Doxygen 1.8.18