Simplex_tree_iterators.h

/*    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):
 *      - 2022/04 Vincent Rouvreau: Add Simplex_tree_boundary_opposite_vertex_simplex_iterator for alpha and cech purpose
 *      - 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 <utility>  // for std::pair
 
namespace Gudhi {


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 const* sib_;
  Vertex_handle v_;
};
 
/*---------------------------------------------------------------------------*/
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:
  using Simplex_handle = typename SimplexTree::Simplex_handle;
  using Vertex_handle = typename SimplexTree::Vertex_handle;
  using Siblings = typename SimplexTree::Siblings;
  using Static_vertex_vector = typename SimplexTree::Static_vertex_vector;
 
// any end() iterator
  explicit Simplex_tree_boundary_simplex_iterator(SimplexTree const* 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 const* 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 constexpr (SimplexTree::Options::contiguous_vertices)
      GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
    Siblings const* sib = st->self_siblings(sh);
    next_ = sib->parent();
    sib_ = sib->oncles();
    if (sib_ != nullptr) {
      if constexpr (SimplexTree::Options::contiguous_vertices &&
                    !SimplexTree::Options::stable_simplex_handles)
      {
        if (sib_->oncles() == nullptr)  // Only relevant for edges
          sh_ = sib_->members_.begin() + next_;
        else
          sh_ = sib_->find(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 const* for_sib = sib_;
    Siblings const* new_sib = sib_->oncles();
    auto rit = suffix_.rbegin();
    if constexpr (SimplexTree::Options::contiguous_vertices && !SimplexTree::Options::stable_simplex_handles) {
      if (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_
  Static_vertex_vector suffix_;
  Siblings const* sib_;  // where the next search will start from
  Simplex_handle sh_;  // current Simplex_handle in the boundary
  SimplexTree const* st_;  // simplex containing the simplicial complex
};

template<class SimplexTree>
class Simplex_tree_boundary_opposite_vertex_simplex_iterator : public boost::iterator_facade<
    Simplex_tree_boundary_opposite_vertex_simplex_iterator<SimplexTree>,
    std::pair<typename SimplexTree::Simplex_handle, typename SimplexTree::Vertex_handle> const, boost::forward_traversal_tag> {
 public:
  using Simplex_handle = typename SimplexTree::Simplex_handle;
  using Vertex_handle = typename SimplexTree::Vertex_handle;
  using Siblings = typename SimplexTree::Siblings;
  using Static_vertex_vector = typename SimplexTree::Static_vertex_vector;
 
  // any end() iterator
  explicit Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree const* st)
      : last_(st->null_vertex()),
        next_(st->null_vertex()),
        sib_(nullptr),
        baov_(st->null_simplex(), st->null_vertex()),
        st_(st)  {
  }
 
  template<class SimplexHandle>
  Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree const* st, SimplexHandle sh)
      : last_(sh->first),
        next_(st->null_vertex()),
        sib_(nullptr),
        baov_(st->null_simplex(), sh->first),
        st_(st) {
    // Only check once at the beginning instead of for every increment, as this is expensive.
    if constexpr (SimplexTree::Options::contiguous_vertices)
      GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
    Siblings const* sib = st->self_siblings(sh);
    next_ = sib->parent();
    sib_ = sib->oncles();
    if (sib_ != nullptr) {
      if constexpr (SimplexTree::Options::contiguous_vertices &&
                    !SimplexTree::Options::stable_simplex_handles) {
        if (sib_->oncles() == nullptr)
          // Only relevant for edges
          baov_.first = sib_->members_.begin() + next_;
        else
          baov_.first = sib_->find(next_);
      } else {
        baov_.first = sib_->find(next_);
      }
    }
  }
 
 private:
  friend class boost::iterator_core_access;
 
  // valid when iterating along the SAME boundary.
  bool equal(Simplex_tree_boundary_opposite_vertex_simplex_iterator const& other) const {
    return (baov_.first == other.baov_.first);
  }
 
  std::pair<Simplex_handle, Vertex_handle> const& dereference() const {
   return baov_;
  }
 
  void increment() {
    if (sib_ == nullptr) {
      baov_.first = st_->null_simplex();
      return;  // ------>>
    }
    Siblings const* for_sib = sib_;
    Siblings const* new_sib = sib_->oncles();
    auto rit = suffix_.rbegin();
    if constexpr (SimplexTree::Options::contiguous_vertices && !SimplexTree::Options::stable_simplex_handles) {
      if (new_sib == nullptr) {
        // We reached the root, use a short-cut to find a vertex.
        if (rit == suffix_.rend()) {
          baov_.second = baov_.first->first;
          // Segment, this vertex is the last boundary simplex
          baov_.first = for_sib->members_.begin() + last_;
          sib_ = nullptr;
          return;
        } else {
          // Dim >= 2, initial step of the descent
          baov_.first = for_sib->members_.begin() + *rit;
          for_sib = baov_.first->second.children();
          ++rit;
        }
      }
    }
 
    for (; rit != suffix_.rend(); ++rit) {
      baov_.first = for_sib->find(*rit);
      for_sib = baov_.first->second.children();
    }
    baov_.first = for_sib->find(last_);  // baov_.first points to the right simplex now
    suffix_.push_back(next_);
    next_ = sib_->parent();
    sib_ = new_sib;
    baov_.second = suffix_.back();
  }
 
  // 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_
  Static_vertex_vector suffix_;
  Siblings const* sib_;  // where the next search will start from
  std::pair<Simplex_handle, Vertex_handle> baov_;  // a pair containing the current Simplex_handle in the boundary and its opposite vertex
  SimplexTree const* st_;  // simplex containing the simplicial complex
};
 
/*---------------------------------------------------------------------------*/
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 const* 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 const* sib_;
  SimplexTree const* st_;
};

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 const* 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 const* sib_;
  SimplexTree const* st_;
  int dim_skel_;
  int curr_dim_;
};

template<class SimplexTree>
class Simplex_tree_dimension_simplex_iterator : public boost::iterator_facade<
    Simplex_tree_dimension_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_dimension_simplex_iterator()
      : sib_(nullptr),
        st_(nullptr),
        dim_(0),
        curr_dim_(0) {
  }
 
  Simplex_tree_dimension_simplex_iterator(SimplexTree const* st, int dim)
      : sib_(nullptr),
        st_(st),
        dim_(dim),
        curr_dim_(0) {
    if (st == nullptr || st->root() == nullptr || st->root()->members().empty() ||
        st->upper_bound_dimension() < dim || dim < 0) {
      st_ = nullptr;
    } else {
      sh_ = st->root()->members().begin();
      sib_ = st->root();
      until_leaf_or_dim();
      // if we reached a leaf that does not respect the required dimension - call increment
      if (curr_dim_ != dim_)
        increment();
    }
  }
 private:
  friend class boost::iterator_core_access;
 
// valid when iterating along the SAME boundary.
  bool equal(Simplex_tree_dimension_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_;
  }
 
  void until_leaf_or_dim() {
    while (st_->has_children(sh_) && curr_dim_ != dim_) {
      sib_ = sh_->second.children();
      sh_ = sib_->members().begin();
      ++curr_dim_;
    }
#ifdef DEBUG_TRACES
    std::clog << "Simplex_tree::dimension_simplex_range until_leaf_or_dim reached (";
    for (auto vertex : st_->simplex_vertex_range(sh_)) {
      std::clog << vertex << ",";
    }
    std::clog << ")\n";
#endif  // DEBUG_TRACES
  }
  // Depth first traversal of the tree structure. Returns when reaching a simplex with a given dimension
  void increment() {
    ++sh_;
    while (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_;
      ++sh_;
      until_leaf_or_dim();
    }
    // It seems we do it twice here, but necessary when coming from the constructor
    until_leaf_or_dim();
    // if we reached a leaf that does not respect the dimension - recall increment
    if (curr_dim_ != dim_)
      increment();
  }
 
  Simplex_handle sh_;
  Siblings const* sib_;
  SimplexTree const* st_;
  int dim_;
  int curr_dim_;
};
  // end addtogroup simplex_tree
 
}  // namespace Gudhi
 
#endif  // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_