1 files changed, 390 insertions, 0 deletions
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h
new file mode 100644
index 00000000..920f8cb6
--- /dev/null
+++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h
@@ -0,0 +1,390 @@
+/*    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):       David Salinas
+ *
+ *    Copyright (C) 2014 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_
+#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_
+
+#include <gudhi/Skeleton_blocker_link_complex.h>
+#include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h>
+#include <gudhi/Skeleton_blocker/internal/Trie.h>
+#include <gudhi/Debug_utils.h>
+
+#include <boost/iterator/iterator_facade.hpp>
+
+#include <memory>
+#include <list>
+#include <iostream>
+
+namespace Gudhi {
+
+namespace skeleton_blocker {
+
+/**
+ * Link may be Skeleton_blocker_link_complex<SkeletonBlockerComplex> to iterate over all
+ * simplices around a vertex OR
+ * Skeleton_blocker_superior_link_complex<SkeletonBlockerComplex> to iterate over all
+ * superior vertices around a vertex.
+ * The iteration is done by computing a trie with the link and doing a breadth-first traversal
+ * of the trie.
+ */
+template<typename SkeletonBlockerComplex, typename Link>
+class Simplex_around_vertex_iterator :
+public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link>
+, typename SkeletonBlockerComplex::Simplex
+, boost::forward_traversal_tag
+, typename SkeletonBlockerComplex::Simplex
+> {
+  friend class boost::iterator_core_access;
+  typedef SkeletonBlockerComplex Complex;
+  typedef typename Complex::Vertex_handle Vertex_handle;
+  typedef typename Complex::Edge_handle Edge_handle;
+  typedef typename Complex::Simplex Simplex;
+
+  // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion
+  typedef typename Link::Vertex_handle Link_vertex_handle;
+
+  typedef typename Gudhi::skeleton_blocker::Trie<Simplex> Trie;
+
+ private:
+  const Complex* complex;
+  Vertex_handle v;
+  std::shared_ptr<Link> link_v;
+  std::shared_ptr<Trie> trie;
+  // TODO(DS): use a deque instead
+  std::list<Trie*> nodes_to_be_seen;
+
+ public:
+  Simplex_around_vertex_iterator() : complex(0) { }
+
+  Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_) :
+      complex(complex_),
+      v(v_),
+      link_v(new Link(*complex_, v_)),
+      trie(new Trie(v_)) {
+    compute_trie_and_nodes_to_be_seen();
+  }
+
+  // TODO(DS): avoid useless copy
+  // TODO(DS): currently just work if copy begin iterator
+  Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other) :
+      complex(other.complex),
+      v(other.v),
+      link_v(other.link_v),
+      trie(other.trie),
+      nodes_to_be_seen(other.nodes_to_be_seen) {
+    if (!other.is_end()) {
+    }
+  }
+
+  /**
+   * returns an iterator to the end
+   */
+  Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_, bool end) :
+      complex(complex_),
+      v(v_) {
+    set_end();
+  }
+
+ private:
+  void compute_trie_and_nodes_to_be_seen() {
+    // once we go through every simplices passing through v0
+    // we remove v0. That way, it prevents from passing a lot of times
+    // though edges leaving v0.
+    // another solution would have been to provides an adjacency iterator
+    // to superior vertices that avoids lower ones.
+    while (!link_v->empty()) {
+      auto v0 = *(link_v->vertex_range().begin());
+      trie->add_child(build_trie(v0, trie.get()));
+      link_v->remove_vertex(v0);
+    }
+    nodes_to_be_seen.push_back(trie.get());
+  }
+
+  Trie* build_trie(Link_vertex_handle link_vh, Trie* parent) {
+    Trie* res = new Trie(parent_vertex(link_vh), parent);
+    for (Link_vertex_handle nv : link_v->vertex_range(link_vh)) {
+      if (link_vh < nv) {
+        Simplex simplex_node_plus_nv(res->simplex());
+        simplex_node_plus_nv.add_vertex(parent_vertex(nv));
+        if (complex->contains(simplex_node_plus_nv)) {
+          res->add_child(build_trie(nv, res));
+        }
+      }
+    }
+    return res;
+  }
+
+  bool is_node_in_complex(Trie* trie) {
+    return true;
+  }
+
+  Vertex_handle parent_vertex(Link_vertex_handle link_vh) const {
+    return complex->convert_handle_from_another_complex(*link_v, link_vh);
+  }
+
+ public:
+  friend std::ostream& operator<<(std::ostream& stream, const Simplex_around_vertex_iterator& savi) {
+    stream << savi.trie << std::endl;
+    stream << "(" << savi.nodes_to_be_seen.size() << ") nodes to see\n";
+    return stream;
+  }
+
+  bool equal(const Simplex_around_vertex_iterator& other) const {
+    bool same_complex = (complex == other.complex);
+    if (!same_complex)
+      return false;
+
+    if (!(v == other.v))
+      return false;
+
+    bool both_empty = nodes_to_be_seen.empty() && other.nodes_to_be_seen.empty();
+    if (both_empty)
+      return true;
+
+    bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty();
+
+    // one is empty the other is not
+    if (!both_non_empty) return false;
+
+    bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin()));
+    return same_node;
+  }
+
+  void increment() {
+    assert(!is_end());
+    Trie* first_node = nodes_to_be_seen.front();
+
+    nodes_to_be_seen.pop_front();
+
+    for (auto childs : first_node->childs) {
+      nodes_to_be_seen.push_back(childs.get());
+    }
+  }
+
+  Simplex dereference() const {
+    assert(!nodes_to_be_seen.empty());
+    Trie* first_node = nodes_to_be_seen.front();
+    return first_node->simplex();
+  }
+
+  Simplex get_trie_address() const {
+    assert(!nodes_to_be_seen.empty());
+    return nodes_to_be_seen.front();
+  }
+
+ private:
+  void set_end() {
+    nodes_to_be_seen.clear();
+  }
+
+  bool is_end() const {
+    return nodes_to_be_seen.empty();
+  }
+};
+
+template<typename SkeletonBlockerComplex>
+class Simplex_iterator :
+public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex>
+, typename SkeletonBlockerComplex::Simplex
+, boost::forward_traversal_tag
+, typename SkeletonBlockerComplex::Simplex
+> {
+  typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link;
+
+  friend class boost::iterator_core_access;
+
+  template<class SkBlDS> friend class Skeleton_blocker_complex;
+
+  typedef SkeletonBlockerComplex Complex;
+  typedef typename Complex::Vertex_handle Vertex_handle;
+  typedef typename Complex::Edge_handle Edge_handle;
+  typedef typename Complex::Simplex Simplex;
+  typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator;
+  typedef typename Link::Vertex_handle Link_vertex_handle;
+
+ private:
+  const Complex* complex_;
+  Complex_vertex_iterator current_vertex_;
+
+  typedef Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> SAVI;
+  SAVI current_simplex_around_current_vertex_;
+  SAVI simplices_around_current_vertex_end_;
+
+ public:
+  Simplex_iterator() : complex_(0) { }
+
+  Simplex_iterator(const Complex* complex) :
+      complex_(complex),
+      current_vertex_(complex->vertex_range().begin()),
+      current_simplex_around_current_vertex_(complex, *current_vertex_),
+      simplices_around_current_vertex_end_(complex, *current_vertex_, true) {
+    // should not be called if the complex is empty
+    assert(!complex->empty());
+  }
+
+ private:
+  Simplex_iterator(const Complex* complex, bool end) :
+      complex_(complex) {
+    set_end();
+  }
+
+ public:
+  Simplex_iterator(const Simplex_iterator& other)
+      :
+      complex_(other.complex_),
+      current_vertex_(other.current_vertex_),
+      current_simplex_around_current_vertex_(other.current_simplex_around_current_vertex_),
+      simplices_around_current_vertex_end_(other.simplices_around_current_vertex_end_) { }
+
+  friend Simplex_iterator make_begin_iterator(const Complex* complex) {
+    if (complex->empty())
+      return make_end_simplex_iterator(complex);
+    else
+      return Simplex_iterator(complex);
+  }
+
+  friend Simplex_iterator make_end_simplex_iterator(const Complex* complex) {
+    return Simplex_iterator(complex, true);
+  }
+
+  bool equal(const Simplex_iterator& other) const {
+    if (complex_ != other.complex_) return false;
+    if (current_vertex_ != other.current_vertex_) return false;
+    if (is_end() && other.is_end()) return true;
+    if (current_simplex_around_current_vertex_ != other.current_simplex_around_current_vertex_)
+      return false;
+    return true;
+  }
+
+  void increment() {
+    if (current_simplex_around_current_vertex_ != simplices_around_current_vertex_end_) {
+      current_simplex_around_current_vertex_.increment();
+      if (current_simplex_around_current_vertex_ == simplices_around_current_vertex_end_)
+        goto_next_vertex();
+    } else {
+      goto_next_vertex();
+    }
+  }
+
+  void goto_next_vertex() {
+    current_vertex_.increment();
+    if (!is_end()) {
+      current_simplex_around_current_vertex_ = SAVI(complex_, *current_vertex_);
+      simplices_around_current_vertex_end_ = SAVI(complex_, *current_vertex_, true);
+    }
+  }
+
+  Simplex dereference() const {
+    return current_simplex_around_current_vertex_.dereference();
+  }
+
+ private:
+  void set_end() {
+    current_vertex_ = complex_->vertex_range().end();
+  }
+
+  bool is_end() const {
+    return (current_vertex_ == complex_->vertex_range().end());
+  }
+};
+
+/**
+ * Iterator through the maximal faces of the coboundary of a simplex.
+ */
+template<typename SkeletonBlockerComplex, typename Link>
+class Simplex_coboundary_iterator :
+public boost::iterator_facade < Simplex_coboundary_iterator<SkeletonBlockerComplex, Link>
+, typename SkeletonBlockerComplex::Simplex, boost::forward_traversal_tag, typename SkeletonBlockerComplex::Simplex> {
+  friend class boost::iterator_core_access;
+  typedef SkeletonBlockerComplex Complex;
+  typedef typename Complex::Vertex_handle Vertex_handle;
+  typedef typename Complex::Edge_handle Edge_handle;
+  typedef typename Complex::Simplex Simplex;
+  typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator;
+
+  // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion
+  typedef typename Link::Vertex_handle Link_vertex_handle;
+
+ private:
+  const Complex* complex;
+  const Simplex& sigma;
+  std::shared_ptr<Link> link;
+  Complex_vertex_iterator current_vertex;
+  Complex_vertex_iterator link_vertex_end;
+
+ public:
+  Simplex_coboundary_iterator() : complex(0) { }
+
+  Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_) :
+      complex(complex_),
+      sigma(sigma_),
+      // need only vertices of the link hence the true flag
+      link(new Link(*complex_, sigma_, false, true)) {
+    auto link_vertex_range = link->vertex_range();
+    current_vertex = link_vertex_range.begin();
+    link_vertex_end = link_vertex_range.end();
+  }
+
+  Simplex_coboundary_iterator(const Simplex_coboundary_iterator& other) :
+      complex(other.complex),
+      sigma(other.sigma),
+      link(other.link),
+      current_vertex(other.current_vertex),
+      link_vertex_end(other.link_vertex_end) { }
+
+  // returns an iterator to the end
+  Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_, bool end) :
+      complex(complex_),
+      sigma(sigma_) {
+    // to represent an end iterator without having to build a useless link, we use
+    // the convection that link is not initialized.
+  }
+
+ private:
+  Vertex_handle parent_vertex(Link_vertex_handle link_vh) const {
+    return complex->convert_handle_from_another_complex(*link, link_vh);
+  }
+
+ public:
+  friend std::ostream& operator<<(std::ostream& stream, const Simplex_coboundary_iterator& sci) {
+    return stream;
+  }
+
+  // assume that iterator points to the same complex and comes from the same simplex
+  bool equal(const Simplex_coboundary_iterator& other) const {
+    assert(complex == other.complex && sigma == other.sigma);
+    if (is_end()) return other.is_end();
+    if (other.is_end()) return is_end();
+    return *current_vertex == *(other.current_vertex);
+  }
+
+  void increment() {
+    ++current_vertex;
+  }
+
+  Simplex dereference() const {
+    Simplex res(sigma);
+    res.add_vertex(parent_vertex(*current_vertex));
+    return res;
+  }
+
+ private:
+  bool is_end() const {
+    return !link || current_vertex == link_vertex_end;
+  }
+};
+
+}  // namespace skeleton_blocker
+
+namespace skbl = skeleton_blocker;
+
+}  // namespace Gudhi
+
+#endif  // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_