Simplex_tree_iterators.h
1 /* This file is part of the Gudhi Library. The Gudhi library
2  * (Geometric Understanding in Higher Dimensions) is a generic C++
3  * library for computational topology.
4  *
5  * Author(s): ClĂ©ment Maria
6  *
7  * Copyright (C) 2014 Inria
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
24 #define SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
25 
26 #include <gudhi/Debug_utils.h>
27 
28 #include <boost/iterator/iterator_facade.hpp>
29 #include <boost/version.hpp>
30 #if BOOST_VERSION >= 105600
31 # include <boost/container/static_vector.hpp>
32 #endif
33 
34 #include <vector>
35 
36 namespace Gudhi {
37 
38 /* \addtogroup simplex_tree
39  * Iterators and range types for the Simplex_tree.
40  * @{
41  */
42 
43 /* \brief Iterator over the vertices of a simplex
44  * in a SimplexTree.
45  *
46  * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/
47 template<class SimplexTree>
48 class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
49  Simplex_tree_simplex_vertex_iterator<SimplexTree>,
50  typename SimplexTree::Vertex_handle const, boost::forward_traversal_tag,
51  typename SimplexTree::Vertex_handle const> {
52  public:
53  typedef typename SimplexTree::Simplex_handle Simplex_handle;
54  typedef typename SimplexTree::Siblings Siblings;
55  typedef typename SimplexTree::Vertex_handle Vertex_handle;
56 
57  explicit Simplex_tree_simplex_vertex_iterator(SimplexTree * st)
58  : // any end() iterator
59  sib_(nullptr),
60  v_(st->null_vertex()) {
61  }
62 
63  Simplex_tree_simplex_vertex_iterator(SimplexTree * st, Simplex_handle sh)
64  : sib_(st->self_siblings(sh)),
65  v_(sh->first) {
66  }
67 
68  private:
69  friend class boost::iterator_core_access;
70 
71  bool equal(Simplex_tree_simplex_vertex_iterator const &other) const {
72  return sib_ == other.sib_ && v_ == other.v_;
73  }
74 
75  Vertex_handle const& dereference() const {
76  return v_;
77  }
78 
79  void increment() {
80  v_ = sib_->parent();
81  sib_ = sib_->oncles();
82  }
83 
84  Siblings * sib_;
85  Vertex_handle v_;
86 };
87 
88 /*---------------------------------------------------------------------------*/
89 /* \brief Iterator over the simplices of the boundary of a
90  * simplex.
91  *
92  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
93 template<class SimplexTree>
94 class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
95  Simplex_tree_boundary_simplex_iterator<SimplexTree>,
96  typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
97  public:
98  typedef typename SimplexTree::Simplex_handle Simplex_handle;
99  typedef typename SimplexTree::Vertex_handle Vertex_handle;
100  typedef typename SimplexTree::Siblings Siblings;
101 
102 // any end() iterator
103  explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
104  : last_(st->null_vertex()),
105  next_(st->null_vertex()),
106  sib_(nullptr),
107  sh_(st->null_simplex()),
108  st_(st) {
109  }
110 
111  template<class SimplexHandle>
112  Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh)
113  : last_(sh->first),
114  next_(st->null_vertex()),
115  sib_(nullptr),
116  sh_(st->null_simplex()),
117  st_(st) {
118  // Only check once at the beginning instead of for every increment, as this is expensive.
120  GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
121  Siblings * sib = st->self_siblings(sh);
122  next_ = sib->parent();
123  sib_ = sib->oncles();
124  if (sib_ != nullptr) {
125  if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
126  // Only relevant for edges
127  sh_ = sib_->members_.begin()+next_;
128  else
129  sh_ = sib_->find(next_);
130  }
131  }
132 
133  private:
134  friend class boost::iterator_core_access;
135 // valid when iterating along the SAME boundary.
136  bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
137  return sh_ == other.sh_;
138  }
139 
140  Simplex_handle const& dereference() const {
141  assert(sh_ != st_->null_simplex());
142  return sh_;
143  }
144 
145  void increment() {
146  if (sib_ == nullptr) {
147  sh_ = st_->null_simplex();
148  return;
149  }
150 
151  Siblings * for_sib = sib_;
152  Siblings * new_sib = sib_->oncles();
153  auto rit = suffix_.rbegin();
154  if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
155  // We reached the root, use a short-cut to find a vertex.
156  if (rit == suffix_.rend()) {
157  // Segment, this vertex is the last boundary simplex
158  sh_ = for_sib->members_.begin()+last_;
159  sib_ = nullptr;
160  return;
161  } else {
162  // Dim >= 2, initial step of the descent
163  sh_ = for_sib->members_.begin()+*rit;
164  for_sib = sh_->second.children();
165  ++rit;
166  }
167  }
168  for (; rit != suffix_.rend(); ++rit) {
169  sh_ = for_sib->find(*rit);
170  for_sib = sh_->second.children();
171  }
172  sh_ = for_sib->find(last_); // sh_ points to the right simplex now
173  suffix_.push_back(next_);
174  next_ = sib_->parent();
175  sib_ = new_sib;
176  }
177 
178  // Most of the storage should be moved to the range, iterators should be light.
179  Vertex_handle last_; // last vertex of the simplex
180  Vertex_handle next_; // next vertex to push in suffix_
181 #if BOOST_VERSION >= 105600
182  // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
183  // as it would not fit on the biggest hard-drive.
184  boost::container::static_vector<Vertex_handle, 40> suffix_;
185  // static_vector still has some overhead compared to a trivial hand-made
186  // version using std::aligned_storage, or compared to making suffix_ static.
187 #else
188  std::vector<Vertex_handle> suffix_;
189 #endif
190  Siblings * sib_; // where the next search will start from
191  Simplex_handle sh_; // current Simplex_handle in the boundary
192  SimplexTree * st_; // simplex containing the simplicial complex
193 };
194 /*---------------------------------------------------------------------------*/
195 /* \brief Iterator over the simplices of a simplicial complex.
196  *
197  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
198 template<class SimplexTree>
199 class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
200  Simplex_tree_complex_simplex_iterator<SimplexTree>,
201  typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
202  public:
203  typedef typename SimplexTree::Simplex_handle Simplex_handle;
204  typedef typename SimplexTree::Siblings Siblings;
205  typedef typename SimplexTree::Vertex_handle Vertex_handle;
206 
207 // any end() iterator
208  Simplex_tree_complex_simplex_iterator()
209  : sib_(nullptr),
210  st_(nullptr) {
211  }
212 
213  explicit Simplex_tree_complex_simplex_iterator(SimplexTree * st)
214  : sib_(nullptr),
215  st_(st) {
216  if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
217  st_ = nullptr;
218  } else {
219  sh_ = st->root()->members().begin();
220  sib_ = st->root();
221  while (st->has_children(sh_)) {
222  sib_ = sh_->second.children();
223  sh_ = sib_->members().begin();
224  }
225  }
226  }
227  private:
228  friend class boost::iterator_core_access;
229 
230 // valid when iterating along the SAME boundary.
231  bool equal(Simplex_tree_complex_simplex_iterator const& other) const {
232  if (other.st_ == nullptr) {
233  return (st_ == nullptr);
234  }
235  if (st_ == nullptr) {
236  return false;
237  }
238  return (&(sh_->second) == &(other.sh_->second));
239  }
240 
241  Simplex_handle const& dereference() const {
242  return sh_;
243  }
244 
245 // Depth first traversal.
246  void increment() {
247  ++sh_;
248  if (sh_ == sib_->members().end()) {
249  if (sib_->oncles() == nullptr) {
250  st_ = nullptr;
251  return;
252  } // reach the end
253  sh_ = sib_->oncles()->members().find(sib_->parent());
254  sib_ = sib_->oncles();
255  return;
256  }
257  while (st_->has_children(sh_)) {
258  sib_ = sh_->second.children();
259  sh_ = sib_->members().begin();
260  }
261  }
262 
263  Simplex_handle sh_;
264  Siblings * sib_;
265  SimplexTree * st_;
266 };
267 
268 /* \brief Iterator over the simplices of the skeleton of a given
269  * dimension of the simplicial complex.
270  *
271  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
272 template<class SimplexTree>
273 class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
274  Simplex_tree_skeleton_simplex_iterator<SimplexTree>,
275  typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
276  public:
277  typedef typename SimplexTree::Simplex_handle Simplex_handle;
278  typedef typename SimplexTree::Siblings Siblings;
279  typedef typename SimplexTree::Vertex_handle Vertex_handle;
280 
281 // any end() iterator
282  Simplex_tree_skeleton_simplex_iterator()
283  : sib_(nullptr),
284  st_(nullptr),
285  dim_skel_(0),
286  curr_dim_(0) {
287  }
288 
289  Simplex_tree_skeleton_simplex_iterator(SimplexTree * st, int dim_skel)
290  : sib_(nullptr),
291  st_(st),
292  dim_skel_(dim_skel),
293  curr_dim_(0) {
294  if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
295  st_ = nullptr;
296  } else {
297  sh_ = st->root()->members().begin();
298  sib_ = st->root();
299  while (st->has_children(sh_) && curr_dim_ < dim_skel_) {
300  sib_ = sh_->second.children();
301  sh_ = sib_->members().begin();
302  ++curr_dim_;
303  }
304  }
305  }
306  private:
307  friend class boost::iterator_core_access;
308 
309 // valid when iterating along the SAME boundary.
310  bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const {
311  if (other.st_ == nullptr) {
312  return (st_ == nullptr);
313  }
314  if (st_ == nullptr) {
315  return false;
316  }
317  return (&(sh_->second) == &(other.sh_->second));
318  }
319 
320  Simplex_handle const& dereference() const {
321  return sh_;
322  }
323 
324 // Depth first traversal of the skeleton.
325  void increment() {
326  ++sh_;
327  if (sh_ == sib_->members().end()) {
328  if (sib_->oncles() == nullptr) {
329  st_ = nullptr;
330  return;
331  } // reach the end
332  sh_ = sib_->oncles()->members().find(sib_->parent());
333  sib_ = sib_->oncles();
334  --curr_dim_;
335  return;
336  }
337  while (st_->has_children(sh_) && curr_dim_ < dim_skel_) {
338  sib_ = sh_->second.children();
339  sh_ = sib_->members().begin();
340  ++curr_dim_;
341  }
342  }
343 
344  Simplex_handle sh_;
345  Siblings * sib_;
346  SimplexTree * st_;
347  int dim_skel_;
348  int curr_dim_;
349 };
350 
351 /* @} */ // end addtogroup simplex_tree
352 } // namespace Gudhi
353 
354 #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:135
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:72
Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:768
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:41
Definition: SimplicialComplexForAlpha.h:26
Siblings * root()
Definition: Simplex_tree.h:777
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:504
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:27
GUDHI  Version 2.2.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Tue Aug 21 2018 01:41:05 for GUDHI by Doxygen 1.8.13