Loading [MathJax]/extensions/TeX/AMSmath.js
All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
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 #if BOOST_VERSION >= 105600
19 # include <boost/container/static_vector.hpp>
20 #endif
21 
22 #include <vector>
23 
24 namespace Gudhi {
25 
26 /* \addtogroup simplex_tree
27  * Iterators and range types for the Simplex_tree.
28  * @{
29  */
30 
31 /* \brief Iterator over the vertices of a simplex
32  * in a SimplexTree.
33  *
34  * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/
35 template<class SimplexTree>
36 class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
37  Simplex_tree_simplex_vertex_iterator<SimplexTree>,
38  typename SimplexTree::Vertex_handle const, boost::forward_traversal_tag,
39  typename SimplexTree::Vertex_handle const> {
40  public:
41  typedef typename SimplexTree::Simplex_handle Simplex_handle;
42  typedef typename SimplexTree::Siblings Siblings;
43  typedef typename SimplexTree::Vertex_handle Vertex_handle;
44 
45  explicit Simplex_tree_simplex_vertex_iterator(SimplexTree * st)
46  : // any end() iterator
47  sib_(nullptr),
48  v_(st->null_vertex()) {
49  }
50 
51  Simplex_tree_simplex_vertex_iterator(SimplexTree * st, Simplex_handle sh)
52  : sib_(st->self_siblings(sh)),
53  v_(sh->first) {
54  }
55 
56  private:
57  friend class boost::iterator_core_access;
58 
59  bool equal(Simplex_tree_simplex_vertex_iterator const &other) const {
60  return sib_ == other.sib_ && v_ == other.v_;
61  }
62 
63  Vertex_handle const& dereference() const {
64  return v_;
65  }
66 
67  void increment() {
68  v_ = sib_->parent();
69  sib_ = sib_->oncles();
70  }
71 
72  Siblings * sib_;
73  Vertex_handle v_;
74 };
75 
76 /*---------------------------------------------------------------------------*/
77 /* \brief Iterator over the simplices of the boundary of a
78  * simplex.
79  *
80  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
81 template<class SimplexTree>
82 class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
83  Simplex_tree_boundary_simplex_iterator<SimplexTree>,
84  typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
85  public:
86  typedef typename SimplexTree::Simplex_handle Simplex_handle;
87  typedef typename SimplexTree::Vertex_handle Vertex_handle;
88  typedef typename SimplexTree::Siblings Siblings;
89 
90 // any end() iterator
91  explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
92  : last_(st->null_vertex()),
93  next_(st->null_vertex()),
94  sib_(nullptr),
95  sh_(st->null_simplex()),
96  st_(st) {
97  }
98 
99  template<class SimplexHandle>
100  Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh)
101  : last_(sh->first),
102  next_(st->null_vertex()),
103  sib_(nullptr),
104  sh_(st->null_simplex()),
105  st_(st) {
106  // Only check once at the beginning instead of for every increment, as this is expensive.
108  GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
109  Siblings * sib = st->self_siblings(sh);
110  next_ = sib->parent();
111  sib_ = sib->oncles();
112  if (sib_ != nullptr) {
113  if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
114  // Only relevant for edges
115  sh_ = sib_->members_.begin()+next_;
116  else
117  sh_ = sib_->find(next_);
118  }
119  }
120 
121  private:
122  friend class boost::iterator_core_access;
123 // valid when iterating along the SAME boundary.
124  bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
125  return sh_ == other.sh_;
126  }
127 
128  Simplex_handle const& dereference() const {
129  assert(sh_ != st_->null_simplex());
130  return sh_;
131  }
132 
133  void increment() {
134  if (sib_ == nullptr) {
135  sh_ = st_->null_simplex();
136  return;
137  }
138 
139  Siblings * for_sib = sib_;
140  Siblings * new_sib = sib_->oncles();
141  auto rit = suffix_.rbegin();
142  if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
143  // We reached the root, use a short-cut to find a vertex.
144  if (rit == suffix_.rend()) {
145  // Segment, this vertex is the last boundary simplex
146  sh_ = for_sib->members_.begin()+last_;
147  sib_ = nullptr;
148  return;
149  } else {
150  // Dim >= 2, initial step of the descent
151  sh_ = for_sib->members_.begin()+*rit;
152  for_sib = sh_->second.children();
153  ++rit;
154  }
155  }
156  for (; rit != suffix_.rend(); ++rit) {
157  sh_ = for_sib->find(*rit);
158  for_sib = sh_->second.children();
159  }
160  sh_ = for_sib->find(last_); // sh_ points to the right simplex now
161  suffix_.push_back(next_);
162  next_ = sib_->parent();
163  sib_ = new_sib;
164  }
165 
166  // Most of the storage should be moved to the range, iterators should be light.
167  Vertex_handle last_; // last vertex of the simplex
168  Vertex_handle next_; // next vertex to push in suffix_
169 #if BOOST_VERSION >= 105600
170  // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
171  // as it would not fit on the biggest hard-drive.
172  boost::container::static_vector<Vertex_handle, 40> suffix_;
173  // static_vector still has some overhead compared to a trivial hand-made
174  // version using std::aligned_storage, or compared to making suffix_ static.
175 #else
176  std::vector<Vertex_handle> suffix_;
177 #endif
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_
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree...
Definition: Simplex_tree.h:123
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:60
Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:830
static constexpr bool contiguous_vertices
If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1, without any hole.
Definition: SimplexTreeOptions.h:29
Definition: SimplicialComplexForAlpha.h:14
Siblings * root()
Definition: Simplex_tree.h:839
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:571
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
GUDHI  Version 3.1.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Feb 7 2020 16:35:36 for GUDHI by Doxygen 1.8.13