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