summaryrefslogtreecommitdiff
path: root/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
blob: ee64a277ffb2f53b1816fab53522ffda375935f2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
/*    This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
 *    See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
 *    Author(s):       Clément Maria
 *
 *    Copyright (C) 2014 Inria
 *
 *    Modification(s):
 *      - YYYY/MM Author: Description of the modification
 */

#ifndef SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
#define SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_

#include <gudhi/Debug_utils.h>

#include <boost/iterator/iterator_facade.hpp>
#include <boost/version.hpp>
#include <boost/container/static_vector.hpp>

#include <vector>

namespace Gudhi {

/* \addtogroup simplex_tree
 * Iterators and range types for the Simplex_tree.
 * @{
 */

/* \brief Iterator over the vertices of a simplex
 * in a SimplexTree.
 *
 * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/
template<class SimplexTree>
class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
    Simplex_tree_simplex_vertex_iterator<SimplexTree>,
    typename SimplexTree::Vertex_handle const, boost::forward_traversal_tag,
    typename SimplexTree::Vertex_handle const> {
 public:
  typedef typename SimplexTree::Simplex_handle Simplex_handle;
  typedef typename SimplexTree::Siblings Siblings;
  typedef typename SimplexTree::Vertex_handle Vertex_handle;

  explicit Simplex_tree_simplex_vertex_iterator(SimplexTree const* st)
      :  // any end() iterator
        sib_(nullptr),
        v_(st->null_vertex()) {
  }

  Simplex_tree_simplex_vertex_iterator(SimplexTree const* st, Simplex_handle sh)
      : sib_(st->self_siblings(sh)),
        v_(sh->first) {
  }

 private:
  friend class boost::iterator_core_access;

  bool equal(Simplex_tree_simplex_vertex_iterator const &other) const {
    return sib_ == other.sib_ && v_ == other.v_;
  }

  Vertex_handle const& dereference() const {
    return v_;
  }

  void increment() {
    v_ = sib_->parent();
    sib_ = sib_->oncles();
  }

  Siblings * sib_;
  Vertex_handle v_;
};

/*---------------------------------------------------------------------------*/
/* \brief Iterator over the simplices of the boundary of a
 *  simplex.
 *
 * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
template<class SimplexTree>
class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
    Simplex_tree_boundary_simplex_iterator<SimplexTree>,
    typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
 public:
  typedef typename SimplexTree::Simplex_handle Simplex_handle;
  typedef typename SimplexTree::Vertex_handle Vertex_handle;
  typedef typename SimplexTree::Siblings Siblings;

  // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is overwritten.
  Simplex_tree_boundary_simplex_iterator()
      : sib_(nullptr),
        st_(nullptr)  {
  }

// any end() iterator
  explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
      : last_(st->null_vertex()),
        next_(st->null_vertex()),
        sib_(nullptr),
        sh_(st->null_simplex()),
        st_(st)  {
  }

  template<class SimplexHandle>
  Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh)
      : last_(sh->first),
        next_(st->null_vertex()),
        sib_(nullptr),
        sh_(st->null_simplex()),
        st_(st) {
    // Only check once at the beginning instead of for every increment, as this is expensive.
    if (SimplexTree::Options::contiguous_vertices)
      GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
    Siblings * sib = st->self_siblings(sh);
    next_ = sib->parent();
    sib_ = sib->oncles();
    if (sib_ != nullptr) {
      if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
        // Only relevant for edges
        sh_ = sib_->members_.begin()+next_;
      else
        sh_ = sib_->find(next_);
    }
  }

 private:
  friend class boost::iterator_core_access;
// valid when iterating along the SAME boundary.
  bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
    return sh_ == other.sh_;
  }

  Simplex_handle const& dereference() const {
    assert(sh_ != st_->null_simplex());
    return sh_;
  }

  void increment() {
    if (sib_ == nullptr) {
      sh_ = st_->null_simplex();
      return;
    }

    Siblings * for_sib = sib_;
    Siblings * new_sib = sib_->oncles();
    auto rit = suffix_.rbegin();
    if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
      // We reached the root, use a short-cut to find a vertex.
      if (rit == suffix_.rend()) {
        // Segment, this vertex is the last boundary simplex
        sh_ = for_sib->members_.begin()+last_;
        sib_ = nullptr;
        return;
      } else {
        // Dim >= 2, initial step of the descent
        sh_ = for_sib->members_.begin()+*rit;
        for_sib = sh_->second.children();
        ++rit;
      }
    }
    for (; rit != suffix_.rend(); ++rit) {
      sh_ = for_sib->find(*rit);
      for_sib = sh_->second.children();
    }
    sh_ = for_sib->find(last_);  // sh_ points to the right simplex now
    suffix_.push_back(next_);
    next_ = sib_->parent();
    sib_ = new_sib;
  }

  // Most of the storage should be moved to the range, iterators should be light.
  Vertex_handle last_;  // last vertex of the simplex
  Vertex_handle next_;  // next vertex to push in suffix_
  // 40 seems a conservative bound on the dimension of a Simplex_tree for now,
  // as it would not fit on the biggest hard-drive.
  boost::container::static_vector<Vertex_handle, 40> suffix_;
  // static_vector still has some overhead compared to a trivial hand-made
  // version using std::aligned_storage, or compared to making suffix_ static.
  Siblings * sib_;  // where the next search will start from
  Simplex_handle sh_;  // current Simplex_handle in the boundary
  SimplexTree * st_;  // simplex containing the simplicial complex
};
/*---------------------------------------------------------------------------*/
/* \brief Iterator over the simplices of a simplicial complex.
 *
 * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
template<class SimplexTree>
class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
    Simplex_tree_complex_simplex_iterator<SimplexTree>,
    typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
 public:
  typedef typename SimplexTree::Simplex_handle Simplex_handle;
  typedef typename SimplexTree::Siblings Siblings;
  typedef typename SimplexTree::Vertex_handle Vertex_handle;

// any end() iterator
  Simplex_tree_complex_simplex_iterator()
      : sib_(nullptr),
        st_(nullptr) {
  }

  explicit Simplex_tree_complex_simplex_iterator(SimplexTree * st)
      : sib_(nullptr),
        st_(st) {
    if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
      st_ = nullptr;
    } else {
      sh_ = st->root()->members().begin();
      sib_ = st->root();
      while (st->has_children(sh_)) {
        sib_ = sh_->second.children();
        sh_ = sib_->members().begin();
      }
    }
  }
 private:
  friend class boost::iterator_core_access;

// valid when iterating along the SAME boundary.
  bool equal(Simplex_tree_complex_simplex_iterator const& other) const {
    if (other.st_ == nullptr) {
      return (st_ == nullptr);
    }
    if (st_ == nullptr) {
      return false;
    }
    return (&(sh_->second) == &(other.sh_->second));
  }

  Simplex_handle const& dereference() const {
    return sh_;
  }

// Depth first traversal.
  void increment() {
    ++sh_;
    if (sh_ == sib_->members().end()) {
      if (sib_->oncles() == nullptr) {
        st_ = nullptr;
        return;
      }  // reach the end
      sh_ = sib_->oncles()->members().find(sib_->parent());
      sib_ = sib_->oncles();
      return;
    }
    while (st_->has_children(sh_)) {
      sib_ = sh_->second.children();
      sh_ = sib_->members().begin();
    }
  }

  Simplex_handle sh_;
  Siblings * sib_;
  SimplexTree * st_;
};

/* \brief Iterator over the simplices of the skeleton of a given
 * dimension of the simplicial complex.
 *
 * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
template<class SimplexTree>
class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
    Simplex_tree_skeleton_simplex_iterator<SimplexTree>,
    typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
 public:
  typedef typename SimplexTree::Simplex_handle Simplex_handle;
  typedef typename SimplexTree::Siblings Siblings;
  typedef typename SimplexTree::Vertex_handle Vertex_handle;

// any end() iterator
  Simplex_tree_skeleton_simplex_iterator()
      : sib_(nullptr),
        st_(nullptr),
        dim_skel_(0),
        curr_dim_(0) {
  }

  Simplex_tree_skeleton_simplex_iterator(SimplexTree * st, int dim_skel)
      : sib_(nullptr),
        st_(st),
        dim_skel_(dim_skel),
        curr_dim_(0) {
    if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
      st_ = nullptr;
    } else {
      sh_ = st->root()->members().begin();
      sib_ = st->root();
      while (st->has_children(sh_) && curr_dim_ < dim_skel_) {
        sib_ = sh_->second.children();
        sh_ = sib_->members().begin();
        ++curr_dim_;
      }
    }
  }
 private:
  friend class boost::iterator_core_access;

// valid when iterating along the SAME boundary.
  bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const {
    if (other.st_ == nullptr) {
      return (st_ == nullptr);
    }
    if (st_ == nullptr) {
      return false;
    }
    return (&(sh_->second) == &(other.sh_->second));
  }

  Simplex_handle const& dereference() const {
    return sh_;
  }

// Depth first traversal of the skeleton.
  void increment() {
    ++sh_;
    if (sh_ == sib_->members().end()) {
      if (sib_->oncles() == nullptr) {
        st_ = nullptr;
        return;
      }  // reach the end
      sh_ = sib_->oncles()->members().find(sib_->parent());
      sib_ = sib_->oncles();
      --curr_dim_;
      return;
    }
    while (st_->has_children(sh_) && curr_dim_ < dim_skel_) {
      sib_ = sh_->second.children();
      sh_ = sib_->members().begin();
      ++curr_dim_;
    }
  }

  Simplex_handle sh_;
  Siblings * sib_;
  SimplexTree * st_;
  int dim_skel_;
  int curr_dim_;
};

/* @} */  // end addtogroup simplex_tree
}  // namespace Gudhi

#endif  // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_