Simplex_tree.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):
 *      - 2023/02 Vincent Rouvreau: Add de/serialize methods for pickle feature
 *      - 2023/07 Clément Maria: Option to link all simplex tree nodes with same label in an intrusive list
 *      - 2023/05 Clément Maria: Edge insertion method for flag complexes
 *      - 2023/05 Hannah Schreiber: Factorization of expansion methods
 *      - 2023/08 Hannah Schreiber (& Clément Maria): Add possibility of stable simplex handles.
 *      - 2024/08 Hannah Schreiber: Generalization of the notion of filtration values.
 *      - 2024/08 Hannah Schreiber: Addition of customizable copy constructor.
 *      - 2024/08 Marc Glisse: Allow storing custom data in simplices.
 *      - 2024/10 Hannah Schreiber: Const version of the Simplex_tree
 *      - 2025/02 Hannah Schreiber (& David Loiseaux): Insertion strategies for `insert_simplex_and_subfaces`
 *      - 2025/03 Hannah Schreiber (& David Loiseaux): Add number_of_parameters_ member
 *      - YYYY/MM Author: Description of the modification
 */
 
#ifndef SIMPLEX_TREE_H_
#define SIMPLEX_TREE_H_
 
#include <gudhi/Simplex_tree/simplex_tree_options.h>
#include <gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h>
#include <gudhi/Simplex_tree/Simplex_tree_siblings.h>
#include <gudhi/Simplex_tree/Simplex_tree_iterators.h>
#include <gudhi/Simplex_tree/Simplex_tree_star_simplex_iterators.h>
#include <gudhi/Simplex_tree/filtration_value_utils.h>  // for de/serialize + empty_filtration_value
#include <gudhi/Simplex_tree/hooks_simplex_base.h>
 
#include <gudhi/reader_utils.h>
#include <gudhi/graph_simplicial_complex.h>
#include <gudhi/Debug_utils.h>
 
#include <boost/container/map.hpp>
#include <boost/container/flat_map.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/size.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/range/adaptors.hpp>
 
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/parent_from_member.hpp>
 
#ifdef GUDHI_USE_TBB
#include <tbb/parallel_sort.h>
#endif
 
#include <cstddef>
#include <cstdint>  // std::uint8_t
#include <utility>  // for std::move
#include <vector>
#include <functional>  // for greater<>
#include <stdexcept>
#include <limits>  // Inf
#include <initializer_list>
#include <algorithm>  // for std::max
#include <iterator>  // for std::distance
#include <type_traits>  // for std::conditional
#include <unordered_map>
#include <iterator>  // for std::prev
 
namespace Gudhi {


enum class Extended_simplex_type {UP, DOWN, EXTRA};

 
template<typename SimplexTreeOptions = Simplex_tree_options_default>
class Simplex_tree {
 public:
  typedef SimplexTreeOptions Options;
  typedef typename Options::Indexing_tag Indexing_tag;
  typedef typename Options::Filtration_value Filtration_value;
  typedef typename Options::Simplex_key Simplex_key;
  typedef typename Get_simplex_data_type<Options>::type Simplex_data;
  typedef typename Options::Vertex_handle Vertex_handle;
 
  /* Type of node in the simplex tree. */
  typedef Simplex_tree_node_explicit_storage<Simplex_tree> Node;
  /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */
  // Note: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a
  // flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and
  // Simplex_key next to each other).
  typedef typename boost::container::flat_map<Vertex_handle, Node> flat_map;
  //Dictionary::iterator remain valid under insertions and deletions,
  //necessary e.g. when computing oscillating rips zigzag filtrations.
  typedef typename boost::container::map<Vertex_handle, Node> map;
  typedef typename std::conditional<Options::stable_simplex_handles,
                                    map,
                                    flat_map>::type Dictionary;

  typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings;
 
  struct Key_simplex_base_real {
    Key_simplex_base_real() : key_(-1) {}
    Key_simplex_base_real(Simplex_key k) : key_(k) {}
    void assign_key(Simplex_key k) { key_ = k; }
    Simplex_key key() const { return key_; }
   private:
    Simplex_key key_;
  };
  struct Key_simplex_base_dummy {
    Key_simplex_base_dummy() {}
    // Undefined so it will not link
    void assign_key(Simplex_key);
    Simplex_key key() const;
  };
 
  struct Extended_filtration_data {
    Filtration_value minval;
    Filtration_value maxval;
    Extended_filtration_data() {}
 
    Extended_filtration_data(const Filtration_value& vmin, const Filtration_value& vmax)
        : minval(vmin), maxval(vmax)
    {}
  };
  typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type
      Key_simplex_base;
 
  struct Filtration_simplex_base_real {
    Filtration_simplex_base_real() : filt_() {}
    Filtration_simplex_base_real(Filtration_value f) : filt_(f) {}
    void assign_filtration(const Filtration_value& f) { filt_ = f; }
    const Filtration_value& filtration() const { return filt_; }
    Filtration_value& filtration() { return filt_; }
 
    static const Filtration_value& get_infinity() { return inf_; }
    static const Filtration_value& get_minus_infinity() { return minus_inf_; }
 
   private:
    Filtration_value filt_;
 
    inline static const Filtration_value inf_ = std::numeric_limits<Filtration_value>::has_infinity
                                                    ? std::numeric_limits<Filtration_value>::infinity()
                                                    : std::numeric_limits<Filtration_value>::max();
    inline static const Filtration_value minus_inf_ = std::numeric_limits<Filtration_value>::has_infinity
                                                          ? -std::numeric_limits<Filtration_value>::infinity()
                                                          : std::numeric_limits<Filtration_value>::lowest();
  };
 
  struct Filtration_simplex_base_dummy {
    Filtration_simplex_base_dummy() {}
    Filtration_simplex_base_dummy(Filtration_value GUDHI_CHECK_code(f)) {
      GUDHI_CHECK(f == null_, "filtration value specified in the constructor for a complex that does not store them");
    }
    void assign_filtration(const Filtration_value& GUDHI_CHECK_code(f)) {
      GUDHI_CHECK(f == null_, "filtration value assigned for a complex that does not store them");
    }
    const Filtration_value& filtration() const { return null_; }
 
   private:
    inline static const Filtration_value null_{Gudhi::simplex_tree::empty_filtration_value};
  };
  typedef typename std::conditional<Options::store_filtration, Filtration_simplex_base_real,
    Filtration_simplex_base_dummy>::type Filtration_simplex_base;
 
 public:
  typedef typename Dictionary::const_iterator Simplex_handle;
 
 private:
  typedef typename Dictionary::iterator Dictionary_it;
  typedef typename Dictionary::const_iterator Dictionary_const_it;
  typedef typename Dictionary_it::value_type Dit_value_t;
 
  struct return_first {
    Vertex_handle operator()(const Dit_value_t& p_sh) const {
      return p_sh.first;
    }
  };
 
 private:
  using Optimized_star_simplex_iterator = Simplex_tree_optimized_star_simplex_iterator<Simplex_tree>;
  using Optimized_star_simplex_range = boost::iterator_range<Optimized_star_simplex_iterator>;
 
  class Fast_cofaces_predicate {
    Simplex_tree const* st_;
    int codim_;
    int dim_;
   public:
    Fast_cofaces_predicate(Simplex_tree const* st, int codim, int dim)
      : st_(st), codim_(codim), dim_(codim + dim) {}
    bool operator()( const Simplex_handle iter ) const {
      if (codim_ == 0)
        // Always true for a star
        return true;
      // Specific coface case
      return dim_ == st_->dimension(iter);
    }
  };
 
  // WARNING: this is safe only because boost::filtered_range is containing a copy of begin and end iterator.
  // This would not be safe if it was containing a pointer to a range (maybe the case for std::views)
  using Optimized_cofaces_simplex_filtered_range = boost::filtered_range<Fast_cofaces_predicate,
                                                                         Optimized_star_simplex_range>;
 

  static constexpr int max_dimension() { return 40; }
 public:

  typedef boost::transform_iterator<return_first, Dictionary_const_it> Complex_vertex_iterator;
  typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
  typedef Simplex_tree_simplex_vertex_iterator<Simplex_tree> Simplex_vertex_iterator;
  typedef boost::iterator_range<Simplex_vertex_iterator> Simplex_vertex_range;
  typedef typename std::conditional<Options::link_nodes_by_label,
                                    Optimized_cofaces_simplex_filtered_range,  // faster implementation
                                    std::vector<Simplex_handle>>::type Cofaces_simplex_range;

  using Static_vertex_vector = boost::container::static_vector<Vertex_handle, max_dimension()>;

  typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Boundary_simplex_iterator;
  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
  typedef Simplex_tree_boundary_opposite_vertex_simplex_iterator<Simplex_tree> Boundary_opposite_vertex_simplex_iterator;
  typedef boost::iterator_range<Boundary_opposite_vertex_simplex_iterator> Boundary_opposite_vertex_simplex_range;
  typedef Simplex_tree_complex_simplex_iterator<Simplex_tree> Complex_simplex_iterator;
  typedef boost::iterator_range<Complex_simplex_iterator> Complex_simplex_range;
  typedef Simplex_tree_skeleton_simplex_iterator<Simplex_tree> Skeleton_simplex_iterator;
  typedef boost::iterator_range<Skeleton_simplex_iterator> Skeleton_simplex_range;
  typedef Simplex_tree_dimension_simplex_iterator<Simplex_tree> Dimension_simplex_iterator;
  typedef boost::iterator_range<Dimension_simplex_iterator> Dimension_simplex_range;
  typedef std::vector<Simplex_handle> Filtration_simplex_range;
  typedef typename Filtration_simplex_range::const_iterator Filtration_simplex_iterator;
 
  /* @} */  // end name range and iterator types

  Complex_vertex_range complex_vertex_range() const {
    return Complex_vertex_range(boost::make_transform_iterator(root_.members_.begin(), return_first()),
                                boost::make_transform_iterator(root_.members_.end(), return_first()));
  }

  Complex_simplex_range complex_simplex_range() const {
    return Complex_simplex_range(Complex_simplex_iterator(this),
                                 Complex_simplex_iterator());
  }

  Skeleton_simplex_range skeleton_simplex_range(int dim) const {
    return Skeleton_simplex_range(Skeleton_simplex_iterator(this, dim),
                                  Skeleton_simplex_iterator());
  }

  Dimension_simplex_range dimension_simplex_range(int dim) const {
    return Dimension_simplex_range(Dimension_simplex_iterator(this, dim),
                                   Dimension_simplex_iterator());
  }

  Filtration_simplex_range const& filtration_simplex_range(Indexing_tag = Indexing_tag()) const {
    maybe_initialize_filtration();
    return filtration_vect_;
  }

  Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const {
    GUDHI_CHECK(sh != null_simplex(), "empty simplex");
    return Simplex_vertex_range(Simplex_vertex_iterator(this, sh),
                                Simplex_vertex_iterator(this));
  }

  template<class SimplexHandle>
  Boundary_simplex_range boundary_simplex_range(SimplexHandle sh) const {
    return Boundary_simplex_range(Boundary_simplex_iterator(this, sh),
                                  Boundary_simplex_iterator(this));
  }

  template<class SimplexHandle>
  Boundary_opposite_vertex_simplex_range boundary_opposite_vertex_simplex_range(SimplexHandle sh) const {
    return Boundary_opposite_vertex_simplex_range(Boundary_opposite_vertex_simplex_iterator(this, sh),
                                                  Boundary_opposite_vertex_simplex_iterator(this));
  }
  // end range and iterator methods

  Simplex_tree()
      : null_vertex_(-1),
        root_(nullptr, null_vertex_),
        number_of_parameters_(1),
        filtration_vect_(),
        dimension_(-1),
        dimension_to_be_lowered_(false) {}

  template<typename OtherSimplexTreeOptions, typename F>
  Simplex_tree(const Simplex_tree<OtherSimplexTreeOptions>& complex_source, F&& translate_filtration_value) {
#ifdef DEBUG_TRACES
    std::clog << "Simplex_tree custom copy constructor" << std::endl;
#endif  // DEBUG_TRACES
    copy_from(complex_source, translate_filtration_value);
  }

  Simplex_tree(const Simplex_tree& complex_source) {
#ifdef DEBUG_TRACES
    std::clog << "Simplex_tree copy constructor" << std::endl;
#endif  // DEBUG_TRACES
    copy_from(complex_source);
  }

  Simplex_tree(Simplex_tree && complex_source) {
#ifdef DEBUG_TRACES
    std::clog << "Simplex_tree move constructor" << std::endl;
#endif  // DEBUG_TRACES
    move_from(complex_source);
  }

  ~Simplex_tree() {
    root_members_recursive_deletion();
  }

  Simplex_tree& operator= (const Simplex_tree& complex_source) {
#ifdef DEBUG_TRACES
    std::clog << "Simplex_tree copy assignment" << std::endl;
#endif  // DEBUG_TRACES
    // Self-assignment detection
    if (&complex_source != this) {
      // We start by deleting root_ if not empty
      root_members_recursive_deletion();
 
      copy_from(complex_source);
    }
    return *this;
  }

  Simplex_tree& operator=(Simplex_tree&& complex_source) {
#ifdef DEBUG_TRACES
    std::clog << "Simplex_tree move assignment" << std::endl;
#endif  // DEBUG_TRACES
    // Self-assignment detection
    if (&complex_source != this) {
      // root_ deletion in case it was not empty
      root_members_recursive_deletion();
 
      move_from(complex_source);
    }
    return *this;
  }
  // end constructor/destructor
 
 private:
  // Copy from complex_source to "this"
  void copy_from(const Simplex_tree& complex_source) {
    null_vertex_ = complex_source.null_vertex_;
    filtration_vect_.clear();
    number_of_parameters_ = complex_source.number_of_parameters_;
    dimension_ = complex_source.dimension_;
    dimension_to_be_lowered_ = complex_source.dimension_to_be_lowered_;
    auto root_source = complex_source.root_;
 
    // root members copy
    root_.members() =
        Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end());
    // Needs to reassign children
    for (auto& map_el : root_.members()) {
      map_el.second.assign_children(&root_);
    }
    // Specific for optional data
    if constexpr (!std::is_same_v<Simplex_data, No_simplex_data>) {
      auto dst_iter = root_.members().begin();
      auto src_iter = root_source.members().begin();
 
      while(dst_iter != root_.members().end() || src_iter != root_source.members().end()) {
        dst_iter->second.data() = src_iter->second.data();
        dst_iter++;
        src_iter++;
      }
      // Check in debug mode members data were copied
      assert(dst_iter == root_.members().end());
      assert(src_iter == root_source.members().end());
    }
    rec_copy<Options::store_key, true>(
        &root_, &root_source, [](const Filtration_value& fil) -> const Filtration_value& { return fil; });
  }
 
  // Copy from complex_source to "this"
  template<typename OtherSimplexTreeOptions, typename F>
  void copy_from(const Simplex_tree<OtherSimplexTreeOptions>& complex_source, F&& translate_filtration_value) {
    null_vertex_ = complex_source.null_vertex_;
    filtration_vect_.clear();
    number_of_parameters_ = complex_source.number_of_parameters_;
    dimension_ = complex_source.dimension_;
    dimension_to_be_lowered_ = complex_source.dimension_to_be_lowered_;
    auto root_source = complex_source.root_;
 
    // root members copy
    if constexpr (!Options::stable_simplex_handles) root_.members().reserve(root_source.size());
    for (auto& p : root_source.members()){
      if constexpr (Options::store_key && OtherSimplexTreeOptions::store_key) {
        root_.members().try_emplace(
            root_.members().end(), p.first, &root_, translate_filtration_value(p.second.filtration()), p.second.key());
      } else {
        root_.members().try_emplace(
            root_.members().end(), p.first, &root_, translate_filtration_value(p.second.filtration()));
      }
    }
 
    rec_copy<OtherSimplexTreeOptions::store_key, false>(&root_, &root_source, translate_filtration_value);
  }

  template<bool store_key, bool copy_simplex_data, typename OtherSiblings, typename F>
  void rec_copy(Siblings *sib, OtherSiblings *sib_source, F&& translate_filtration_value) {
    auto sh_source = sib_source->members().begin();
    for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh, ++sh_source) {
      update_simplex_tree_after_node_insertion(sh);
      if (has_children(sh_source)) {
        Siblings * newsib = new Siblings(sib, sh_source->first);
        if constexpr (!Options::stable_simplex_handles) {
          newsib->members_.reserve(sh_source->second.children()->members().size());
        }
        for (auto & child : sh_source->second.children()->members()){
          Dictionary_it new_it{};
          if constexpr (store_key && Options::store_key) {
            new_it = newsib->members_.emplace_hint(
                newsib->members_.end(),
                child.first,
                Node(newsib, translate_filtration_value(child.second.filtration()), child.second.key()));
          } else {
            new_it = newsib->members_.emplace_hint(newsib->members_.end(),
                                          child.first,
                                          Node(newsib, translate_filtration_value(child.second.filtration())));
          }
          // Specific for optional data
          if constexpr (copy_simplex_data && !std::is_same_v<Simplex_data, No_simplex_data>) {
            new_it->second.data() = child.second.data();
          }
        }
        rec_copy<store_key, copy_simplex_data>(newsib, sh_source->second.children(), translate_filtration_value);
        sh->second.assign_children(newsib);
      }
    }
  }
 
  // Move from complex_source to "this"
  void move_from(Simplex_tree& complex_source) {
    null_vertex_ = std::move(complex_source.null_vertex_);
    root_ = std::move(complex_source.root_);
    filtration_vect_ = std::move(complex_source.filtration_vect_);
    number_of_parameters_ = std::exchange(complex_source.number_of_parameters_, 1);
    dimension_ = std::exchange(complex_source.dimension_, -1);
    dimension_to_be_lowered_ = std::exchange(complex_source.dimension_to_be_lowered_, false);
    if constexpr (Options::link_nodes_by_label) {
      nodes_label_to_list_.swap(complex_source.nodes_label_to_list_);
    }
    // Need to update root members (children->oncles and children need to point on the new root pointer)
    for (auto& map_el : root_.members()) {
      if (map_el.second.children() != &(complex_source.root_)) {
        // reset children->oncles with the moved root_ pointer value
        map_el.second.children()->oncles_ = &root_;
      } else {
        // if simplex is of dimension 0, oncles_ shall be nullptr
        GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr,
                    std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree"));
        // and children points on root_ - to be moved
        map_el.second.assign_children(&root_);
      }
    }
  }
 
  // delete all root_.members() recursively
  void root_members_recursive_deletion() {
    for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) {
      if (has_children(sh)) {
        rec_delete(sh->second.children());
      }
    }
    root_.members().clear();
  }
 
  // Recursive deletion
  void rec_delete(Siblings * sib) {
    for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
      if (has_children(sh)) {
        rec_delete(sh->second.children());
      }
    }
    delete sib;
  }
 
 public:
  template<typename> friend class Simplex_tree;

  template <class OtherSimplexTreeOptions>
  bool operator==(const Simplex_tree<OtherSimplexTreeOptions>& st2) const {
    if ((null_vertex_ != st2.null_vertex_) ||
        (dimension_ != st2.dimension_ && !dimension_to_be_lowered_ && !st2.dimension_to_be_lowered_) ||
        (number_of_parameters_ != st2.number_of_parameters_))
      return false;
    return rec_equal(&root_, &st2.root_);
  }

  template<class OtherSimplexTreeOptions>
  bool operator!=(const Simplex_tree<OtherSimplexTreeOptions>& st2) const {
    return (!(*this == st2));
  }
 
 private:
  template<class OtherSiblings>
  bool rec_equal(Siblings const* s1, OtherSiblings const* s2) const {
    if (s1->members().size() != s2->members().size())
      return false;
    auto sh2 = s2->members().begin();
    for (auto sh1 = s1->members().begin();
         (sh1 != s1->members().end() && sh2 != s2->members().end());
         ++sh1, ++sh2) {
      if (sh1->first != sh2->first || !(sh1->second.filtration() == sh2->second.filtration()))
        return false;
      if (has_children(sh1) != has_children(sh2))
        return false;
      // Recursivity on children only if both have children
      else if (has_children(sh1))
        if (!rec_equal(sh1->second.children(), sh2->second.children()))
          return false;
    }
    return true;
  }

  static const Filtration_value& filtration_(Simplex_handle sh) {
    GUDHI_CHECK (sh != null_simplex(), "null simplex");
    return sh->second.filtration();
  }
 
  // Transform a Dictionary_const_it into a Dictionary_it
  Dictionary_it _to_node_it(Simplex_handle sh) {
    return self_siblings(sh)->to_non_const_it(sh);
  }
 
 public:
  static Simplex_key key(Simplex_handle sh) {
    return sh->second.key();
  }

  Simplex_handle simplex(Simplex_key idx) const {
    return filtration_vect_[idx];
  }

  static const Filtration_value& filtration(Simplex_handle sh) {
    if (sh != null_simplex()) {
      return sh->second.filtration();
    } else {
      return Filtration_simplex_base_real::get_infinity();
    }
  }

  void assign_filtration(Simplex_handle sh, const Filtration_value& fv) {
    GUDHI_CHECK(sh != null_simplex(),
                std::invalid_argument("Simplex_tree::assign_filtration - cannot assign filtration on null_simplex"));
    _to_node_it(sh)->second.assign_filtration(fv);
  }

  static Simplex_handle null_simplex() {
    return Dictionary_const_it();
  }

  static Simplex_key null_key() {
    return -1;
  }

  Simplex_data& simplex_data(Simplex_handle sh) {
    GUDHI_CHECK(sh != null_simplex(),
                std::invalid_argument("Simplex_tree::simplex_data - no data associated to null_simplex"));
    return _to_node_it(sh)->second.data();
  }

  const Simplex_data& simplex_data(Simplex_handle sh) const {
    GUDHI_CHECK(sh != null_simplex(),
                std::invalid_argument("Simplex_tree::simplex_data - no data associated to null_simplex"));
    return sh->second.data();
  }

  Vertex_handle null_vertex() const {
    return null_vertex_;
  }

  size_t num_vertices() const {
    return root_.members_.size();
  }

  bool is_empty() const {
    return root_.members_.empty();
  }
 
 public:
  size_t num_simplices() const {
    return num_simplices(root());
  }
 
 private:
  size_t num_simplices(const Siblings * sib) const {
    auto sib_begin = sib->members().begin();
    auto sib_end = sib->members().end();
    size_t simplices_number = sib->members().size();
    for (auto sh = sib_begin; sh != sib_end; ++sh) {
      if (has_children(sh)) {
        simplices_number += num_simplices(sh->second.children());
      }
    }
    return simplices_number;
  }

  int dimension(Siblings const* curr_sib) const {
    int dim = -1;
    while (curr_sib != nullptr) {
      ++dim;
      curr_sib = curr_sib->oncles();
    }
    return dim;
  }
 
 public:
  std::vector<std::size_t> num_simplices_by_dimension() const {
    if (is_empty()) return {};
    // std::min in case the upper bound got crazy
    std::vector<std::size_t> res(std::min(upper_bound_dimension()+1, max_dimension()+1));
    auto fun = [&res](Simplex_handle, int dim) -> void { ++res[dim]; };
    for_each_simplex(fun);
    if (dimension_to_be_lowered_) {
      GUDHI_CHECK(res.front() != 0, std::logic_error("Bug in Gudhi: non-empty complex has no vertex"));
      while (res.back() == 0) res.pop_back();
      dimension_ = static_cast<int>(res.size()) - 1;
      dimension_to_be_lowered_ = false;
    } else {
      GUDHI_CHECK(res.back() != 0,
          std::logic_error("Bug in Gudhi: there is no simplex of dimension the dimension of the complex"));
    }
    return res;
  }

  int dimension(Simplex_handle sh) const {
    return dimension(self_siblings(sh));
  }

  int upper_bound_dimension() const {
    return dimension_;
  }

  int dimension() const {
    if (dimension_to_be_lowered_)
      lower_upper_bound_dimension();
    return dimension_;
  }

  int num_parameters() const {
    return number_of_parameters_;
  }

  void set_num_parameters(int new_number) {
    number_of_parameters_ = new_number;
  }

  auto euler_characteristic() const {
    using ssize_t = std::make_signed_t<std::size_t>;
 
    auto dimension_count = num_simplices_by_dimension();
    ssize_t euler = 0;
    ssize_t sign = 1;
    for (const ssize_t count : dimension_count) {
      euler += sign * count;
      sign = -sign;
    }
    return euler;
  }

  template<class SimplexHandle>
  bool has_children(SimplexHandle sh) const {
    // Here we rely on the root using null_vertex(), which cannot match any real vertex.
    return (sh->second.children()->parent() == sh->first);
  }
 
 private:
  friend class Simplex_tree_optimized_star_simplex_iterator<Simplex_tree>;

  Siblings const* children(Simplex_handle sh) const {
    GUDHI_CHECK(has_children(sh), std::invalid_argument("Simplex_tree::children - argument has no child"));
    return sh->second.children();
  }
 
 public:
  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
  Simplex_handle find(const InputVertexRange & s) const {
    auto first = std::begin(s);
    auto last = std::end(s);
 
    if (first == last)
      return null_simplex();  // ----->>
 
    // Copy before sorting
    std::vector<Vertex_handle> copy(first, last);
    std::sort(std::begin(copy), std::end(copy));
    return find_simplex(copy);
  }
 
 private:
  Simplex_handle find_simplex(const std::vector<Vertex_handle> & simplex) const {
    Siblings const* tmp_sib = &root_;
    Dictionary_const_it tmp_dit;
    auto vi = simplex.begin();
    if constexpr (Options::contiguous_vertices && !Options::stable_simplex_handles) {
      // Equivalent to the first iteration of the normal loop
      GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices");
      Vertex_handle v = *vi++;
      if(v < 0 || v >= static_cast<Vertex_handle>(root_.members_.size()))
        return null_simplex();
      tmp_dit = root_.members_.begin() + v;
      if (vi == simplex.end())
        return tmp_dit;
      if (!has_children(tmp_dit))
        return null_simplex();
      tmp_sib = tmp_dit->second.children();
    }
    for (;;) {
      tmp_dit = tmp_sib->members_.find(*vi++);
      if (tmp_dit == tmp_sib->members_.end())
        return null_simplex();
      if (vi == simplex.end())
        return tmp_dit;
      if (!has_children(tmp_dit))
        return null_simplex();
      tmp_sib = tmp_dit->second.children();
    }
  }

  Simplex_handle find_vertex(Vertex_handle v) const {
    if constexpr (Options::contiguous_vertices && !Options::stable_simplex_handles) {
      assert(contiguous_vertices());
      return root_.members_.begin() + v;
    } else {
      return root_.members_.find(v);
    }
  }
 
 public:
  bool contiguous_vertices() const {
    if (root_.members_.empty()) return true;
    if (root_.members_.begin()->first != 0) return false;
    if (std::prev(root_.members_.end())->first != static_cast<Vertex_handle>(root_.members_.size() - 1)) return false;
    return true;
  }
 
 private:
  template<bool update_fil, bool update_children, bool set_to_null, class Filt>
  std::pair<Dictionary_it, bool> insert_node_(Siblings *sib, Vertex_handle v, Filt&& filtration_value) {
    std::pair<Dictionary_it, bool> ins = sib->members_.try_emplace(v, sib, std::forward<Filt>(filtration_value));
 
    if constexpr (update_children){
      if (!(has_children(ins.first))) {
        ins.first->second.assign_children(new Siblings(sib, v));
      }
    }
 
    if (ins.second){
      // Only required when insertion is successful
      update_simplex_tree_after_node_insertion(ins.first);
      return ins;
    }
 
    if constexpr (Options::store_filtration && update_fil){
      if (unify_lifetimes(ins.first->second.filtration(), filtration_value)) return ins;
    }
 
    if constexpr (set_to_null){
      ins.first = Dictionary_it();
    }
 
    return ins;
  }
 
 protected:
  template <class RandomVertexHandleRange = std::initializer_list<Vertex_handle>>
  std::pair<Simplex_handle, bool> insert_simplex_raw(const RandomVertexHandleRange& simplex,
                                                     const Filtration_value& filtration) {
    Siblings * curr_sib = &root_;
    std::pair<Dictionary_it, bool> res_insert;
    auto vi = simplex.begin();
 
    for (; vi != std::prev(simplex.end()); ++vi) {
      GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
      res_insert = insert_node_<false, true, false>(curr_sib, *vi, filtration);
      curr_sib = res_insert.first->second.children();
    }
 
    GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
    res_insert = insert_node_<true, false, true>(curr_sib, *vi, filtration);
    if (res_insert.second){
      int dim = static_cast<int>(boost::size(simplex)) - 1;
      if (dim > dimension_) {
        // Update dimension if needed
        dimension_ = dim;
      }
    }
    return res_insert;
  }
 
 public:
  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
  std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex,
                                                 const Filtration_value& filtration = Filtration_value()) {
    auto first = std::begin(simplex);
    auto last = std::end(simplex);
 
    if (first == last)
      return std::pair<Simplex_handle, bool>(null_simplex(), true);  // ----->>
 
    // Copy before sorting
    std::vector<Vertex_handle> copy(first, last);
    std::sort(std::begin(copy), std::end(copy));
    return insert_simplex_raw(copy, filtration);
  }

  enum class Filtration_maintenance : std::uint8_t {
    LOWER_EXISTING,
    INCREASE_NEW,
    IGNORE_VALIDITY
  };
 
  // Retro-compatibility
  template <class InputVertexRange = std::initializer_list<Vertex_handle> >
  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& n_simplex,
                                                              const Filtration_value& filtration = Filtration_value())
  {
    return insert_simplex_and_subfaces(Filtration_maintenance::LOWER_EXISTING, n_simplex, filtration);
  }
 
  // possibility of different default values depending on chosen strategy
  template <class InputVertexRange = std::initializer_list<Vertex_handle>>
  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(Filtration_maintenance insertion_strategy,
                                                              const InputVertexRange& n_simplex)
  {
    auto get_default_value = [](Filtration_maintenance strategy) -> Filtration_value {
      switch (strategy) {
        case Filtration_maintenance::LOWER_EXISTING:
          return Filtration_simplex_base_real::get_infinity();
        case Filtration_maintenance::INCREASE_NEW:
          return Filtration_simplex_base_real::get_minus_infinity();
        case Filtration_maintenance::IGNORE_VALIDITY:
          return Filtration_value();
        default:
          throw std::invalid_argument("Given insertion strategy is not available.");
      }
    };
 
    return insert_simplex_and_subfaces(insertion_strategy, n_simplex, get_default_value(insertion_strategy));
  }
 
  // actual insertion method
  template <class InputVertexRange = std::initializer_list<Vertex_handle>>
  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(
      [[maybe_unused]] Filtration_maintenance insertion_strategy,
      const InputVertexRange& n_simplex,
      const Filtration_value& filtration)
 {
    auto first = std::begin(n_simplex);
    auto last = std::end(n_simplex);
 
    if (first == last) return {null_simplex(), true};  // FIXME: false would make more sense to me.
 
    thread_local std::vector<Vertex_handle> copy;
    copy.clear();
    copy.insert(copy.end(), first, last);
    std::sort(copy.begin(), copy.end());
    auto last_unique = std::unique(copy.begin(), copy.end());
    copy.erase(last_unique, copy.end());
    GUDHI_CHECK_code(for (Vertex_handle v : copy)
                         GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"););
    // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
    dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(copy.begin(), copy.end())) - 1);
 
    if constexpr (Options::store_filtration){
      switch (insertion_strategy) {
        case Filtration_maintenance::LOWER_EXISTING:
          return _rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
        case Filtration_maintenance::INCREASE_NEW:
          return _insert_simplex_and_subfaces_at_highest(root(), copy.begin(), copy.end(), filtration);
        case Filtration_maintenance::IGNORE_VALIDITY:
          return _insert_simplex_and_subfaces_forcing_filtration_value(root(), copy.begin(), copy.end(), filtration);
        default:
          throw std::invalid_argument("Given insertion strategy is not available.");
      }
    } else {
      // filtration values not stored, so no differences between the strategies
      return _rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
    }
  }
 
 private:
  // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
  template <class ForwardVertexIterator, bool update_fil = true>
  std::pair<Simplex_handle, bool> _rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
                                                                          ForwardVertexIterator first,
                                                                          ForwardVertexIterator last,
                                                                          const Filtration_value& filt) {
    // An alternative strategy would be:
    // - try to find the complete simplex, if found (and low filtration) exit
    // - insert all the vertices at once in sib
    // - loop over those (new or not) simplices, with a recursive call(++first, last)
    Vertex_handle vertex_one = *first;
 
    // insert_node_<bool update_fil, bool update_children, bool set_to_null>(sib, ...)
    // update_fil: if true, calls `unify_lifetimes` on the new and old filtration value of the node
    // update_children: if true, assign a child to the node if it did not have one
    // set_to_null: if true, sets returned iterator to null simplex
    
    if (++first == last) return insert_node_<update_fil, false, update_fil>(sib, vertex_one, filt);
 
    // TODO: have special code here, we know we are building the whole subtree from scratch.
    auto insertion_result = insert_node_<update_fil, true, false>(sib, vertex_one, filt);
 
    auto res = _rec_insert_simplex_and_subfaces_sorted<ForwardVertexIterator, update_fil>(
        insertion_result.first->second.children(), first, last, filt);
    // No need to continue if the full simplex was already there with a low enough filtration value.
    if (res.first != null_simplex())
      _rec_insert_simplex_and_subfaces_sorted<ForwardVertexIterator, update_fil>(sib, first, last, filt);
    return res;
  }
 
  bool _make_subfiltration_non_decreasing(Simplex_handle sh, const Filtration_value& filt) {
    Filtration_value& f = _to_node_it(sh)->second.filtration();
    bool changed = false;
    for (auto sh_b : boundary_simplex_range(sh)) {
      bool b_changed = true;
      // In this particular loop, only newly inserted faces and eventually (old) top faces can have the same value
      // than filt. This avoids going too much down the tree.
      if (filt == filtration(sh_b)) b_changed = _make_subfiltration_non_decreasing(sh_b, filt);
      // If the face did not change value after calling the recursion, than the intersection won't change f's value.
      if (b_changed) changed |= intersect_lifetimes(f, filtration(sh_b));
    }
    return changed;
  }
 
  template <class ForwardVertexIterator>
  std::pair<Simplex_handle, bool> _insert_simplex_and_subfaces_at_highest(Siblings* sib,
                                                                          ForwardVertexIterator first,
                                                                          ForwardVertexIterator last,
                                                                          const Filtration_value& filt) {
    auto res = _rec_insert_simplex_and_subfaces_sorted<ForwardVertexIterator, false>(sib, first, last, filt);
    if (res.second) {
      _make_subfiltration_non_decreasing(res.first, filt);
    } else {
      res.first = null_simplex();
    }
    return res;
  }
 
  template <class ForwardVertexIterator>
  std::pair<Simplex_handle, bool> _insert_simplex_and_subfaces_forcing_filtration_value(Siblings* sib,
                                                                                        ForwardVertexIterator first,
                                                                                        ForwardVertexIterator last,
                                                                                        const Filtration_value& filt) {
    auto res = _rec_insert_simplex_and_subfaces_sorted<ForwardVertexIterator, false>(sib, first, last, filt);
    if (!res.second) {
      res.first = null_simplex();
    }
    return res;
  }
 
 public:
  void assign_key(Simplex_handle sh, Simplex_key key) {
    _to_node_it(sh)->second.assign_key(key);
  }

  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) const {
    assert(dimension(sh) == 1);
    return { find_vertex(sh->first), find_vertex(self_siblings(sh)->parent()) };
  }

  template<class SimplexHandle>
  Siblings const* self_siblings(SimplexHandle sh) const {
    if (sh->second.children()->parent() == sh->first)
      return sh->second.children()->oncles();
    else
      return sh->second.children();
  }

  template<class SimplexHandle>
  Siblings* self_siblings(SimplexHandle sh) {
    // Scott Meyers in Effective C++ 3rd Edition. On page 23, Item 3: a non const method can safely call a const one
    // Doing it the other way is not safe
    return const_cast<Siblings*>(std::as_const(*this).self_siblings(sh));
  }
 
 public:
  Siblings* root() { return &root_; }

  const Siblings * root() const {
    return &root_;
  }

  void set_dimension(int dimension, bool exact=true) {
    dimension_to_be_lowered_ = !exact;
    dimension_ = dimension;
  }
 
 private:
  bool reverse_lexicographic_order(Simplex_handle sh1, Simplex_handle sh2) const {
    Simplex_vertex_range rg1 = simplex_vertex_range(sh1);
    Simplex_vertex_range rg2 = simplex_vertex_range(sh2);
    Simplex_vertex_iterator it1 = rg1.begin();
    Simplex_vertex_iterator it2 = rg2.begin();
    while (it1 != rg1.end() && it2 != rg2.end()) {
      if (*it1 == *it2) {
        ++it1;
        ++it2;
      } else {
        return *it1 < *it2;
      }
    }
    return ((it1 == rg1.end()) && (it2 != rg2.end()));
  }

  struct is_before_in_totally_ordered_filtration {
    explicit is_before_in_totally_ordered_filtration(Simplex_tree const* st)
        : st_(st) { }
 
    bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const {
      // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
      if (!(sh1->second.filtration() == sh2->second.filtration())) {
        return sh1->second.filtration() < sh2->second.filtration();
      }
      // is sh1 a proper subface of sh2
      return st_->reverse_lexicographic_order(sh1, sh2);
    }
 
    Simplex_tree const* st_;
  };
 
 public:
  void initialize_filtration(bool ignore_infinite_values = false) const {
    if (ignore_infinite_values){
      initialize_filtration(is_before_in_totally_ordered_filtration(this), [&](Simplex_handle sh) -> bool {
        return is_positive_infinity(filtration(sh));
      });
    } else {
      initialize_filtration(is_before_in_totally_ordered_filtration(this), [](Simplex_handle) -> bool {
        return false;
      });
    }
  }

  template<typename Comparator, typename Ignorer>
  void initialize_filtration(Comparator&& is_before_in_filtration, Ignorer&& ignore_simplex) const {
    filtration_vect_.clear();
    filtration_vect_.reserve(num_simplices());
    for (Simplex_handle sh : complex_simplex_range()) {
      if (ignore_simplex(sh)) continue;
      filtration_vect_.push_back(sh);
    }
 
#ifdef GUDHI_USE_TBB
    tbb::parallel_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration);
#else
    std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration);
#endif
  }

  void maybe_initialize_filtration() const {
    if (filtration_vect_.empty()) {
      initialize_filtration();
    }
  }

  void clear_filtration() const {
    filtration_vect_.clear();
  }
 
 private:
  void rec_coface(std::vector<Vertex_handle> &vertices, Siblings const*curr_sib, int curr_nbVertices,
                  std::vector<Simplex_handle>& cofaces, bool star, int nbVertices) const {
    if (!(star || curr_nbVertices <= nbVertices))  // dimension of actual simplex <= nbVertices
      return;
    for (Simplex_handle simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) {
      if (vertices.empty()) {
        // If we reached the end of the vertices, and the simplex has more vertices than the given simplex
        // => we found a coface
 
        // Add a coface if we want the star or if the number of vertices of the current simplex matches with nbVertices
        bool addCoface = (star || curr_nbVertices == nbVertices);
        if (addCoface)
          cofaces.push_back(simplex);
        if ((!addCoface || star) && has_children(simplex))  // Rec call
          rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
      } else {
        if (simplex->first == vertices.back()) {
          // If curr_sib matches with the top vertex
          bool equalDim = (star || curr_nbVertices == nbVertices);  // dimension of actual simplex == nbVertices
          bool addCoface = vertices.size() == 1 && equalDim;
          if (addCoface)
            cofaces.push_back(simplex);
          if ((!addCoface || star) && has_children(simplex)) {
            // Rec call
            Vertex_handle tmp = vertices.back();
            vertices.pop_back();
            rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
            vertices.push_back(tmp);
          }
        } else if (simplex->first > vertices.back()) {
          return;
        } else {
          // (simplex->first < vertices.back()
          if (has_children(simplex))
            rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
        }
      }
    }
  }
 
 public:
  Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex) const {
    return cofaces_simplex_range(simplex, 0);
  }

  Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) const{
    // codimension must be positive or null integer
    assert(codimension >= 0);
 
    if constexpr (Options::link_nodes_by_label) {
      Simplex_vertex_range rg = simplex_vertex_range(simplex);
      Static_vertex_vector simp(rg.begin(), rg.end());
      // must be sorted in decreasing order
      assert(std::is_sorted(simp.begin(), simp.end(), std::greater<Vertex_handle>()));
      auto range = Optimized_star_simplex_range(Optimized_star_simplex_iterator(this, std::move(simp)),
                                                Optimized_star_simplex_iterator());
      // Lazy filtered range
      Fast_cofaces_predicate select(this, codimension, this->dimension(simplex));
      return boost::adaptors::filter(range, select);
    } else {
      Cofaces_simplex_range cofaces;
      Simplex_vertex_range rg = simplex_vertex_range(simplex);
      std::vector<Vertex_handle> copy(rg.begin(), rg.end());
      if (codimension + static_cast<int>(copy.size()) > dimension_ + 1 ||
          (codimension == 0 && static_cast<int>(copy.size()) > dimension_))  // n+codimension greater than dimension_
        return cofaces;
      // must be sorted in decreasing order
      assert(std::is_sorted(copy.begin(), copy.end(), std::greater<Vertex_handle>()));
      bool star = codimension == 0;
      rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int>(copy.size()));
      return cofaces;
    }
  }
 
 public:
  template<class OneSkeletonGraph>
  void insert_graph(const OneSkeletonGraph& skel_graph) {
    // the simplex tree must be empty
    assert(num_simplices() == 0);
 
    // is there a better way to let the compiler know that we don't mean Simplex_tree::num_vertices?
    using boost::num_vertices;
 
    if (num_vertices(skel_graph) == 0) {
      return;
    }
    if (num_edges(skel_graph) == 0) {
      dimension_ = 0;
    } else {
      dimension_ = 1;
    }
 
    if constexpr (!Options::stable_simplex_handles)
      root_.members_.reserve(num_vertices(skel_graph)); // probably useless in most cases
    auto verts = vertices(skel_graph) | boost::adaptors::transformed([&](auto v){
        return Dit_value_t(v, Node(&root_, get(vertex_filtration_t(), skel_graph, v))); });
    root_.members_.insert(boost::begin(verts), boost::end(verts));
    // This automatically sorts the vertices, the graph concept doesn't guarantee the order in which we iterate.
 
    for (Dictionary_it it = boost::begin(root_.members_); it != boost::end(root_.members_); it++) {
      update_simplex_tree_after_node_insertion(it);
    }
 
    std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator,
              typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = edges(skel_graph);
    // boost_edges.first is the equivalent to boost_edges.begin()
    // boost_edges.second is the equivalent to boost_edges.end()
    for (; boost_edges.first != boost_edges.second; boost_edges.first++) {
      auto edge = *(boost_edges.first);
      auto u = source(edge, skel_graph);
      auto v = target(edge, skel_graph);
      if (u == v) throw std::invalid_argument("Self-loops are not simplicial");
      // We cannot skip edges with the wrong orientation and expect them to
      // come a second time with the right orientation, that does not always
      // happen in practice. emplace() should be a NOP when an element with the
      // same key is already there, so seeing the same edge multiple times is
      // ok.
      // Should we actually forbid multiple edges? That would be consistent
      // with rejecting self-loops.
      if (v < u) std::swap(u, v);
      auto sh = _to_node_it(find_vertex(u));
      if (!has_children(sh)) {
        sh->second.assign_children(new Siblings(&root_, sh->first));
      }
 
      insert_node_<false, false, false>(sh->second.children(), v, get(edge_filtration_t(), skel_graph, edge));
    }
  }

  template <class VertexRange = std::initializer_list<Vertex_handle> >
  void insert_batch_vertices(VertexRange const& vertices, const Filtration_value& filt = Filtration_value()) {
    auto verts = vertices | boost::adaptors::transformed([&](auto v){
        return Dit_value_t(v, Node(&root_, filt)); });
    root_.members_.insert(boost::begin(verts), boost::end(verts));
    if (dimension_ < 0 && !root_.members_.empty()) dimension_ = 0;
    if constexpr (Options::link_nodes_by_label) {
      for (auto sh = root_.members().begin(); sh != root_.members().end(); sh++) {
        // update newly inserted simplex (the one that are not linked)
        if (!sh->second.list_max_vertex_hook_.is_linked())
          update_simplex_tree_after_node_insertion(sh);
      }
    }
  }

  void expansion(int max_dimension) {
    if (max_dimension <= 1) return;
    clear_filtration(); // Drop the cache.
    dimension_ = max_dimension;
    for (Dictionary_it root_it = root_.members_.begin();
         root_it != root_.members_.end(); ++root_it) {
      if (has_children(root_it)) {
        siblings_expansion(root_it->second.children(), max_dimension - 1);
      }
    }
    dimension_ = max_dimension - dimension_;
  }

  void insert_edge_as_flag(  Vertex_handle                   u
                           , Vertex_handle                   v
                           , const Filtration_value&      fil
                           , int                             dim_max
                           , std::vector<Simplex_handle>&    added_simplices)
  {
 
    static_assert(Options::link_nodes_by_label, "Options::link_nodes_by_label must be true");
 
    if (u == v) { // Are we inserting a vertex?
      auto res_ins = insert_node_<false, false, false>(&root_, u, fil);
      if (res_ins.second) { //if the vertex is not in the complex, insert it
        added_simplices.push_back(res_ins.first); //no more insert in root_.members()
        if (dimension_ == -1) dimension_ = 0;
      }
      return; //because the vertex is isolated, no more insertions.
    }
    // else, we are inserting an edge: ensure that u < v
    if (v < u) { std::swap(u,v); }
 
    //Note that we copy Simplex_handle (aka map iterators) in added_simplices
    //while we are still modifying the Simplex_tree. Insertions in siblings may
    //invalidate Simplex_handles; we take care of this fact by first doing all
    //insertion in a Sibling, then inserting all handles in added_simplices.
 
#ifdef GUDHI_DEBUG
    //check whether vertices u and v are in the tree. If not, return an error.
    auto sh_u = root_.members().find(u);
    GUDHI_CHECK(sh_u != root_.members().end() &&
          root_.members().find(v) != root_.members().end(),
          std::invalid_argument(
                  "Simplex_tree::insert_edge_as_flag - inserts an edge whose vertices are not in the complex")
                );
    GUDHI_CHECK(!has_children(sh_u) ||
          sh_u->second.children()->members().find(v) == sh_u->second.children()->members().end(),
          std::invalid_argument(
                  "Simplex_tree::insert_edge_as_flag - inserts an already existing edge")
                );
#endif
 
    // to update dimension
    const auto tmp_dim = dimension_;
    auto tmp_max_dim = dimension_;
 
    //for all siblings containing a Node labeled with u (including the root), run
    //compute_punctual_expansion
    //todo parallelize
    List_max_vertex* nodes_with_label_u = nodes_by_label(u);//all Nodes with u label
 
    GUDHI_CHECK(nodes_with_label_u != nullptr,
                "Simplex_tree::insert_edge_as_flag - cannot find the list of Nodes with label u");
 
    for (auto&& node_as_hook : *nodes_with_label_u)
    {
      Node& node_u = static_cast<Node&>(node_as_hook); //corresponding node, has label u
      Simplex_handle sh_u = simplex_handle_from_node(node_u);
      Siblings* sib_u = self_siblings(sh_u);
      if (sib_u->members().find(v) != sib_u->members().end()) { //v is the label of a sibling of node_u
        int curr_dim = dimension(sib_u);
        if (dim_max == -1 || curr_dim < dim_max){
          if (!has_children(sh_u)) {
            //then node_u was a leaf and now has a new child Node labeled v
            //the child v is created in compute_punctual_expansion
            node_u.assign_children(new Siblings(sib_u, u));
          }
          dimension_ = dim_max - curr_dim - 1;
          compute_punctual_expansion(
                v,
                node_u.children(),
                fil,
                dim_max - curr_dim - 1, //>= 0 if dim_max >= 0, <0 otherwise
                added_simplices );
          dimension_ = dim_max - dimension_;
          if (dimension_ > tmp_max_dim) tmp_max_dim = dimension_;
        }
      }
    }
    if (tmp_dim <= tmp_max_dim){
        dimension_ = tmp_max_dim;
        dimension_to_be_lowered_ = false;
    } else {
        dimension_ = tmp_dim;
    }
  }
 
 private:
  void compute_punctual_expansion(  Vertex_handle    v
                                  , Siblings *       sib
                                  , const Filtration_value& fil
                                  , int              k    //k == dim_max - dimension simplices in sib
                                  , std::vector<Simplex_handle>& added_simplices )
  { //insertion always succeeds because the edge {u,v} used to not be here.
    auto res_ins_v = sib->members().emplace(v, Node(sib,fil));
    added_simplices.push_back(res_ins_v.first); //no more insertion in sib
    update_simplex_tree_after_node_insertion(res_ins_v.first);
 
    if (k == 0) {   // reached the maximal dimension. if max_dim == -1, k is never equal to 0.
      dimension_ = 0;  // to keep track of the max height of the recursion tree
      return;
    }
 
    //create the subtree of new Node(v)
    create_local_expansion(  res_ins_v.first
                           , sib
                           , fil
                           , k
                           , added_simplices );
 
    //punctual expansion in nodes on the left of v, i.e. with label x < v
    for (auto sh = sib->members().begin(); sh != res_ins_v.first; ++sh)
    { //if v belongs to N^+(x), punctual expansion
      Simplex_handle root_sh = find_vertex(sh->first); //Node(x), x < v
      if (has_children(root_sh) &&
          root_sh->second.children()->members().find(v) != root_sh->second.children()->members().end())
      { //edge {x,v} is in the complex
        if (!has_children(sh)){
          sh->second.assign_children(new Siblings(sib, sh->first));
        }
        //insert v in the children of sh, and expand.
        compute_punctual_expansion(  v
                                   , sh->second.children()
                                   , fil
                                   , k-1
                                   , added_simplices );
      }
    }
  }

  void create_local_expansion(
        Dictionary_it             sh_v             //Node with label v which has just been inserted
      , Siblings                 *curr_sib         //Siblings containing the node sh_v
      , const Filtration_value&   fil_uv           //Fil value of the edge uv in the zz filtration
      , int                       k                //Stopping condition for recursion based on max dim
      , std::vector<Simplex_handle> &added_simplices) //range of all new simplices
  { //pick N^+(v)
    //intersect N^+(v) with labels y > v in curr_sib
    Dictionary_it next_it = sh_v;
    ++next_it;
 
    if (dimension_ > k) {
      dimension_ = k;   //to keep track of the max height of the recursion tree
    }
 
    create_expansion<true>(curr_sib, sh_v, next_it, fil_uv, k, &added_simplices);
  }
  //TODO boost::container::ordered_unique_range_t in the creation of a Siblings

  void siblings_expansion(
        Siblings                    * siblings  // must contain elements
      , const Filtration_value&    fil
      , int                           k         // == max_dim expansion - dimension curr siblings
      , std::vector<Simplex_handle> & added_simplices )
  {
    if (dimension_ > k) {
      dimension_ = k;   //to keep track of the max height of the recursion tree
    }
    if (k == 0) { return; } //max dimension
    Dictionary_it next = ++(siblings->members().begin());
 
    for (Dictionary_it s_h = siblings->members().begin();
         next != siblings->members().end(); ++s_h, ++next)
    { //find N^+(s_h)
      create_expansion<true>(siblings, s_h, next, fil, k, &added_simplices);
    }
  }

  void siblings_expansion(Siblings * siblings,  // must contain elements
                          int k) {
    if (k >= 0 && dimension_ > k) {
      dimension_ = k;
    }
    if (k == 0)
      return;
    Dictionary_it next = siblings->members().begin();
    ++next;
 
    for (Dictionary_it s_h = siblings->members().begin();
         s_h != siblings->members().end(); ++s_h, ++next)
    {
      create_expansion<false>(siblings, s_h, next, s_h->second.filtration(), k);
    }
  }

  template<bool force_filtration_value>
  void create_expansion(Siblings * siblings,
                        Dictionary_it& s_h,
                        Dictionary_it& next,
                        const Filtration_value& fil,
                        int k,
                        std::vector<Simplex_handle>* added_simplices = nullptr)
  {
    Simplex_handle root_sh = find_vertex(s_h->first);
    thread_local std::vector<std::pair<Vertex_handle, Node> > inter;
 
    if (!has_children(root_sh)) return;
 
    intersection<force_filtration_value>(
          inter,  // output intersection
          next,   // begin
          siblings->members().end(),  // end
          root_sh->second.children()->members().begin(),
          root_sh->second.children()->members().end(),
          fil);
    if (inter.size() != 0) {
      Siblings * new_sib = new Siblings(siblings,   // oncles
                                        s_h->first, // parent
                                        inter);     // boost::container::ordered_unique_range_t
      for (auto it = new_sib->members().begin(); it != new_sib->members().end(); ++it) {
        update_simplex_tree_after_node_insertion(it);
        if constexpr (force_filtration_value){
          //the way create_expansion is used, added_simplices != nullptr when force_filtration_value == true
          added_simplices->push_back(it);
        }
      }
      inter.clear();
      s_h->second.assign_children(new_sib);
      if constexpr (force_filtration_value){
        siblings_expansion(new_sib, fil, k - 1, *added_simplices);
      } else {
        siblings_expansion(new_sib, k - 1);
      }
    } else {
      // ensure the children property
      s_h->second.assign_children(siblings);
      inter.clear();
    }
  }

  template<bool force_filtration_value = false>
  static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection,
                           Dictionary_const_it begin1, Dictionary_const_it end1,
                           Dictionary_const_it begin2, Dictionary_const_it end2,
                           const Filtration_value& filtration_) {
    if (begin1 == end1 || begin2 == end2)
      return;  // ----->>
    while (true) {
      if (begin1->first == begin2->first) {
        if constexpr (force_filtration_value){
          intersection.emplace_back(begin1->first, Node(nullptr, filtration_));
        } else {
          Filtration_value filt = begin1->second.filtration();
          intersect_lifetimes(filt, begin2->second.filtration());
          intersect_lifetimes(filt, filtration_);
          intersection.emplace_back(begin1->first, Node(nullptr, filt));
        }
        if (++begin1 == end1 || ++begin2 == end2)
          return;  // ----->>
      } else if (begin1->first < begin2->first) {
        if (++begin1 == end1)
          return;
      } else /* begin1->first > begin2->first */ {
        if (++begin2 == end2)
          return;  // ----->>
      }
    }
  }
 
 public:
  template< typename Blocker >
  void expansion_with_blockers(int max_dim, Blocker block_simplex) {
    // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
    for (auto& simplex : boost::adaptors::reverse(root_.members())) {
      if (has_children(&simplex)) {
        siblings_expansion_with_blockers(simplex.second.children(), max_dim, max_dim - 1, block_simplex);
      }
    }
  }
 
 private:
  template< typename Blocker >
  void siblings_expansion_with_blockers(Siblings* siblings, int max_dim, int k, Blocker block_simplex) {
    if (dimension_ < max_dim - k) {
      dimension_ = max_dim - k;
    }
    if (k == 0)
      return;
    // No need to go deeper
    if (siblings->members().size() < 2)
      return;
    // Reverse loop starting before the last one for 'next' to be the last one
    for (auto simplex = std::next(siblings->members().rbegin()); simplex != siblings->members().rend(); simplex++) {
      std::vector<std::pair<Vertex_handle, Node> > intersection;
      for(auto next = siblings->members().rbegin(); next != simplex; next++) {
        bool to_be_inserted = true;
        Filtration_value filt = simplex->second.filtration();
        // If all the boundaries are present, 'next' needs to be inserted
        for (Simplex_handle border : boundary_simplex_range(simplex)) {
          Simplex_handle border_child = find_child(border, next->first);
          if (border_child == null_simplex()) {
            to_be_inserted=false;
            break;
          }
          intersect_lifetimes(filt, filtration(border_child));
        }
        if (to_be_inserted) {
          intersection.emplace_back(next->first, Node(nullptr, filt));
        }
      }
      if (intersection.size() != 0) {
        // Reverse the order to insert
        Siblings * new_sib = new Siblings(
              siblings,                                 // oncles
              simplex->first,                           // parent
              boost::adaptors::reverse(intersection));  // boost::container::ordered_unique_range_t
        simplex->second.assign_children(new_sib);
        std::vector<Vertex_handle> blocked_new_sib_vertex_list;
        // As all intersections are inserted, we can call the blocker function on all new_sib members
        for (auto new_sib_member = new_sib->members().begin();
             new_sib_member != new_sib->members().end();
             new_sib_member++) {
           update_simplex_tree_after_node_insertion(new_sib_member);
           bool blocker_result = block_simplex(new_sib_member);
           // new_sib member has been blocked by the blocker function
           // add it to the list to be removed - do not perform it while looping on it
           if (blocker_result) {
             blocked_new_sib_vertex_list.push_back(new_sib_member->first);
             // update data structures for all deleted simplices
             // can be done in the loop as part of another data structure
             update_simplex_tree_before_node_removal(new_sib_member);
           }
        }
        if (blocked_new_sib_vertex_list.size() == new_sib->members().size()) {
          // Specific case where all have to be deleted
          delete new_sib;
          // ensure the children property
          simplex->second.assign_children(siblings);
        } else {
          for (auto& blocked_new_sib_member : blocked_new_sib_vertex_list) {
            new_sib->members().erase(blocked_new_sib_member);
          }
          // ensure recursive call
          siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex);
        }
      } else {
        // ensure the children property
        simplex->second.assign_children(siblings);
      }
    }
  }

  Simplex_handle find_child(Simplex_handle sh, Vertex_handle vh) const {
    if (!has_children(sh))
      return null_simplex();
 
    Simplex_handle child = sh->second.children()->find(vh);
    // Specific case of boost::flat_map does not find, returns boost::flat_map::end()
    // in simplex tree we want a null_simplex()
    if (child == sh->second.children()->members().end())
      return null_simplex();
 
    return child;
  }
 
 public:
  void print_hasse(std::ostream& os) const {
    os << num_simplices() << " " << std::endl;
    // TODO: should use complex_simplex_range ?
    for (auto sh : filtration_simplex_range()) {
      os << dimension(sh) << " ";
      for (auto b_sh : boundary_simplex_range(sh)) {
        os << key(b_sh) << " ";
      }
      os << filtration(sh) << " \n";
    }
  }
 
 public:
  template<class Fun>
  void for_each_simplex(Fun&& fun) const {
    // Wrap callback so it always returns bool
    auto f = [&fun](Simplex_handle sh, int dim) -> bool {
      if constexpr (std::is_same_v<void, decltype(fun(sh, dim))>) {
        fun(sh, dim);
        return false;
      } else {
        return fun(sh, dim);
      }
    };
    if (!is_empty())
      rec_for_each_simplex(root(), 0, f);
  }
 
 private:
  template<class Fun>
  void rec_for_each_simplex(const Siblings* sib, int dim, Fun&& fun) const {
    Simplex_handle sh = sib->members().end();
    GUDHI_CHECK(sh != sib->members().begin(), "Bug in Gudhi: only the root siblings may be empty");
    do {
      --sh;
      if (!fun(sh, dim) && has_children(sh)) {
        rec_for_each_simplex(sh->second.children(), dim+1, fun);
      }
      // We could skip checking has_children for the first element of the iteration, we know it returns false.
    }
    while(sh != sib->members().begin());
  }
 
 public:
  bool make_filtration_non_decreasing() {
    bool modified = false;
    auto fun = [&modified, this](Simplex_handle sh, int dim) -> void {
      if (dim == 0) return;
 
      Filtration_value& current_filt = _to_node_it(sh)->second.filtration();
 
      // Find the maximum filtration value in the border and assigns it if it is greater than the current
      for (Simplex_handle b : boundary_simplex_range(sh)) {
        // considers NaN as the lowest possible value.
        // stores the filtration modification information
        modified |= intersect_lifetimes(current_filt, b->second.filtration());
      }
    };
    // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
    for_each_simplex(fun);
 
    if (modified)
      clear_filtration(); // Drop the cache.
    return modified;
  }
 
 public:
  void clear() {
    root_members_recursive_deletion();
    clear_filtration();
    dimension_ = -1;
    dimension_to_be_lowered_ = false;
    if constexpr (Options::link_nodes_by_label)
      nodes_label_to_list_.clear();
  }

  bool prune_above_filtration(const Filtration_value& filtration) {
    if (is_positive_infinity(filtration))
      return false;  // ---->>
    bool modified = rec_prune_above_filtration(root(), filtration);
    if(modified)
      clear_filtration(); // Drop the cache.
    return modified;
  }
 
 private:
  bool rec_prune_above_filtration(Siblings* sib, const Filtration_value& filt) {
    auto&& list = sib->members();
    bool modified = false;
    bool emptied = false;
    Simplex_handle last;
 
    auto to_remove = [this, filt](Dit_value_t& simplex) {
      //if filt and simplex.second.filtration() are non comparable, should return false.
      //if simplex.second.filtration() is NaN, should return true.
      if (filt < simplex.second.filtration() || !(simplex.second.filtration() == simplex.second.filtration())) {
        if (has_children(&simplex)) rec_delete(simplex.second.children());
        // dimension may need to be lowered
        dimension_to_be_lowered_ = true;
        return true;
      }
      return false;
    };
 
    //TODO: `if constexpr` replaceable by `std::erase_if` in C++20? Has a risk of additional runtime,
    //so to benchmark first.
    if constexpr (Options::stable_simplex_handles) {
      modified = false;
      for (auto sh = list.begin(); sh != list.end();) {
        if (to_remove(*sh)) {
          sh = list.erase(sh);
          modified = true;
        } else {
          ++sh;
        }
      }
      emptied = (list.empty() && sib != root());
    } else {
      last = std::remove_if(list.begin(), list.end(), to_remove);
      modified = (last != list.end());
      emptied = (last == list.begin() && sib != root());
    }
 
    if (emptied) {
      // Removing the whole siblings, parent becomes a leaf.
      sib->oncles()->members()[sib->parent()].assign_children(sib->oncles());
      delete sib;
      // dimension may need to be lowered
      dimension_to_be_lowered_ = true;
      return true;
    } else {
      // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones.
      if constexpr (!Options::stable_simplex_handles) list.erase(last, list.end());
      for (auto&& simplex : list)
        if (has_children(&simplex)) modified |= rec_prune_above_filtration(simplex.second.children(), filt);
    }
 
    return modified;
  }
 
 public:
  bool prune_above_dimension(int dimension) {
    if (dimension >= dimension_)
      return false;
 
    bool modified = false;
    if (dimension < 0) {
      if (num_vertices() > 0) {
        root_members_recursive_deletion();
        modified = true;
      }
      // Force dimension to -1, in case user calls `prune_above_dimension(-10)`
      dimension = -1;
    } else {
      modified = rec_prune_above_dimension(root(), dimension, 0);
    }
    if(modified) {
      // Thanks to `if (dimension >= dimension_)` and dimension forced to -1 `if (dimension < 0)`, we know the new dimension
      dimension_ = dimension;
      clear_filtration(); // Drop the cache.
    }
    return modified;
  }
 
 private:
  bool rec_prune_above_dimension(Siblings* sib, int dim, int actual_dim) {
    bool modified = false;
    auto&& list = sib->members();
 
    for (auto&& simplex : list)
      if (has_children(&simplex)) {
        if (actual_dim >= dim) {
          rec_delete(simplex.second.children());
          simplex.second.assign_children(sib);
          modified = true;
        } else {
          modified |= rec_prune_above_dimension(simplex.second.children(), dim, actual_dim + 1);
        }
      }
 
    return modified;
  }
 
 private:
  bool lower_upper_bound_dimension() const {
    // reset automatic detection to recompute
    dimension_to_be_lowered_ = false;
    int new_dimension = -1;
    // Browse the tree from the left to the right as higher dimension cells are more likely on the left part of the tree
    for (Simplex_handle sh : complex_simplex_range()) {
#ifdef DEBUG_TRACES
      for (auto vertex : simplex_vertex_range(sh)) {
        std::clog << " " << vertex;
      }
      std::clog << std::endl;
#endif  // DEBUG_TRACES
 
      int sh_dimension = dimension(sh);
      if (sh_dimension >= dimension_)
        // Stop browsing as soon as the dimension is reached, no need to go further
        return false;
      new_dimension = (std::max)(new_dimension, sh_dimension);
    }
    dimension_ = new_dimension;
    return true;
  }
 
 
 public:
  void remove_maximal_simplex(Simplex_handle sh) {
    // Guarantee the simplex has no children
    GUDHI_CHECK(!has_children(sh),
                std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children"));
 
    update_simplex_tree_before_node_removal(sh);
 
    // Simplex is a leaf, it means the child is the Siblings owning the leaf
    Dictionary_it nodeIt = _to_node_it(sh);
    Siblings* child = nodeIt->second.children();
 
    if ((child->size() > 1) || (child == root())) {
      // Not alone, just remove it from members
      // Special case when child is the root of the simplex tree, just remove it from members
      child->erase(nodeIt);
    } else {
      // Sibling is emptied : must be deleted, and its parent must point on his own Sibling
      child->oncles()->members().at(child->parent()).assign_children(child->oncles());
      delete child;
      // dimension may need to be lowered
      dimension_to_be_lowered_ = true;
    }
  }

  std::pair<Filtration_value, Extended_simplex_type> decode_extended_filtration(
      const Filtration_value& f,
      const Extended_filtration_data& efd) const
  {
    std::pair<Filtration_value, Extended_simplex_type> p;
    const Filtration_value& minval = efd.minval;
    const Filtration_value& maxval = efd.maxval;
    if (f >= -2 && f <= -1) {
      p.first = minval + (maxval - minval) * (f + 2);
      p.second = Extended_simplex_type::UP;
    } else if (f >= 1 && f <= 2) {
      p.first = minval - (maxval - minval) * (f - 2);
      p.second = Extended_simplex_type::DOWN;
    } else {
      p.first = std::numeric_limits<Filtration_value>::quiet_NaN();
      p.second = Extended_simplex_type::EXTRA;
    }
    return p;
  };
 
  //TODO: externalize this method and `decode_extended_filtration`
  Extended_filtration_data extend_filtration() {
    clear_filtration(); // Drop the cache.
 
    // Compute maximum and minimum of filtration values
    Vertex_handle maxvert = std::numeric_limits<Vertex_handle>::min();
    Filtration_value minval = Filtration_simplex_base_real::get_infinity();
    Filtration_value maxval = Filtration_simplex_base_real::get_minus_infinity();
    for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) {
      const Filtration_value& f = this->filtration(sh);
      minval = std::min(minval, f);
      maxval = std::max(maxval, f);
      maxvert = std::max(sh->first, maxvert);
    }
 
    GUDHI_CHECK(maxvert < std::numeric_limits<Vertex_handle>::max(), std::invalid_argument("Simplex_tree contains a vertex with the largest Vertex_handle"));
    maxvert++;
 
    Simplex_tree st_copy = *this;
 
    // Add point for coning the simplicial complex
    this->insert_simplex_raw({maxvert}, -3);
 
    Filtration_value scale = maxval-minval;
    if (scale != 0)
      scale = 1 / scale;
 
    // For each simplex
    std::vector<Vertex_handle> vr;
    for (auto sh_copy : st_copy.complex_simplex_range()) {
      auto&& simplex_range = st_copy.simplex_vertex_range(sh_copy);
      vr.assign(simplex_range.begin(), simplex_range.end());
      auto sh = this->find(vr);
 
      // Create cone on simplex
      vr.push_back(maxvert);
      if (this->dimension(sh) == 0) {
        const Filtration_value& v = this->filtration(sh);
        Filtration_value scaled_v = (v - minval) * scale;
        // Assign ascending value between -2 and -1 to vertex
        this->assign_filtration(sh, -2 + scaled_v);
        // Assign descending value between 1 and 2 to cone on vertex
        this->insert_simplex(vr, 2 - scaled_v);
      } else {
        // Assign value -3 to simplex and cone on simplex
        this->assign_filtration(sh, -3);
        this->insert_simplex(vr, -3);
      }
    }
 
    // Automatically assign good values for simplices
    this->make_filtration_non_decreasing();
 
    // Return the filtration data
    return Extended_filtration_data(minval, maxval);
  }

  Vertex_handle vertex_with_same_filtration(Simplex_handle sh) const {
    auto filt = filtration_(sh);
    for(auto v : simplex_vertex_range(sh))
      if(filtration_(find_vertex(v)) == filt)
        return v;
    return null_vertex();
  }

  Simplex_handle edge_with_same_filtration(Simplex_handle sh) const {
    // See issue #251 for potential speed improvements.
    auto&& vertices = simplex_vertex_range(sh); // vertices in decreasing order
    auto end = std::end(vertices);
    auto vi = std::begin(vertices);
    GUDHI_CHECK(vi != end, "empty simplex");
    auto v0 = *vi;
    ++vi;
    GUDHI_CHECK(vi != end, "simplex of dimension 0");
    if(std::next(vi) == end) return sh; // shortcut for dimension 1
    Static_vertex_vector suffix;
    suffix.push_back(v0);
    auto filt = filtration_(sh);
    do
    {
      Vertex_handle v = *vi;
      auto&& children1 = find_vertex(v)->second.children()->members_;
      for(auto w : suffix){
        // Can we take advantage of the fact that suffix is ordered?
        Simplex_handle s = children1.find(w);
        if(filtration_(s) == filt)
          return s;
      }
      suffix.push_back(v);
    }
    while(++vi != end);
    return null_simplex();
  }

  Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh) const {
    auto filt = filtration_(sh);
    // Naive implementation, it can be sped up.
    for(auto b : boundary_simplex_range(sh))
      if(filtration_(b) == filt)
        return minimal_simplex_with_same_filtration(b);
    return sh; // None of its faces has the same filtration.
  }
 
 public:
  // intrusive list of Nodes with same label using the hooks
  typedef boost::intrusive::member_hook<Hooks_simplex_base_link_nodes, typename Hooks_simplex_base_link_nodes::Member_hook_t,
                                        &Hooks_simplex_base_link_nodes::list_max_vertex_hook_>
      List_member_hook_t;
  // auto_unlink in Member_hook_t is incompatible with constant time size
  typedef boost::intrusive::list<Hooks_simplex_base_link_nodes, List_member_hook_t,
                                 boost::intrusive::constant_time_size<false>> List_max_vertex;
  // type of hooks stored in each Node, Node inherits from Hooks_simplex_base
  typedef typename std::conditional<Options::link_nodes_by_label, Hooks_simplex_base_link_nodes,
                                    Hooks_simplex_base_dummy>::type Hooks_simplex_base;

 private:
  // if Options::link_nodes_by_label is true, store the lists of Nodes with same label, empty otherwise.
  // unordered_map Vertex_handle v -> list of all Nodes with label v.
  std::unordered_map<Vertex_handle, List_max_vertex> nodes_label_to_list_;
 
  List_max_vertex* nodes_by_label(Vertex_handle v) {
    // Scott Meyers in Effective C++ 3rd Edition. On page 23, Item 3: a non const method can safely call a const one
    // Doing it the other way is not safe
    return const_cast<List_max_vertex*>(std::as_const(*this).nodes_by_label(v));
  }
 
  List_max_vertex const* nodes_by_label(Vertex_handle v) const {
    if constexpr (Options::link_nodes_by_label) {
      auto it_v = nodes_label_to_list_.find(v);
      if (it_v != nodes_label_to_list_.end()) {
        return &(it_v->second);
      } else {
        return nullptr;
      }
    }
    return nullptr;
  }

  static Simplex_handle simplex_handle_from_node(const Node& node) {
    if constexpr (Options::stable_simplex_handles){
      //Relies on the Dictionary type to be boost::container::map<Vertex_handle, Node>.
      //If the type changes or boost fundamentally changes something on the structure of their map,
      //a safer/more general but much slower version is:
      //   if (node.children()->parent() == label) {  // verifies if node is a leaf
      //     return children->oncles()->find(label);
      //   } else {
      //     return children->members().find(label);
      //   }
      //Requires an additional parameter "Vertex_handle label" which is the label of the node.
 
      Dictionary_const_it testIt = node.children()->members().begin();
      const Node* testNode = &testIt->second;
      auto testIIt = testIt.get();
      auto testPtr = testIIt.pointed_node();
      //distance between node and pointer to map pair in memory
      auto shift = (const char*)(testNode) - (const char*)(testPtr);
 
      //decltype(testPtr) = boost::intrusive::compact_rbtree_node<void*>*
      decltype(testPtr) sh_ptr = decltype(testPtr)((const char*)(&node) - shift);   //shifts from node to pointer
      //decltype(testIIt) =
      //boost::intrusive::tree_iterator<
      //  boost::intrusive::bhtraits<
      //    boost::container::base_node<
      //      std::pair<const int, Simplex_tree_node_explicit_storage<Simplex_tree>>,
      //      boost::container::dtl::intrusive_tree_hook<void*, boost::container::red_black_tree, true>, true>,
      //    boost::intrusive::rbtree_node_traits<void*, true>,
      //    boost::intrusive::normal_link,
      //    boost::intrusive::dft_tag,
      //    3>,
      //  false>
      decltype(testIIt) sh_ii;
      sh_ii = sh_ptr;           //creates ``subiterator'' from pointer
      Dictionary_const_it sh(sh_ii);  //creates iterator from subiterator
 
      return sh;
    } else {
      //node needs to be casted as non const, because a const pair* cannot be casted into a Simplex_handle
      return (Simplex_handle)(boost::intrusive::get_parent_from_member<Dit_value_t>(const_cast<Node*>(&node),
                                                                                    &Dit_value_t::second));
    }
  }
 
  // Give access to Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator and keep nodes_by_label and
  // simplex_handle_from_node private
  friend class Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator<Simplex_tree>;
 
 private:
  // update all extra data structures in the Simplex_tree. Must be called after all
  // simplex insertions.
  void update_simplex_tree_after_node_insertion(Simplex_handle sh) {
#ifdef DEBUG_TRACES
    std::clog << "update_simplex_tree_after_node_insertion" << std::endl;
#endif  // DEBUG_TRACES
    if constexpr (Options::link_nodes_by_label) {
      // Creates an entry with sh->first if not already in the map and insert sh->second at the end of the list
      nodes_label_to_list_[sh->first].push_back(_to_node_it(sh)->second);
    }
  }
 
  // update all extra data structures in the Simplex_tree. Must be called before
  // all simplex removals
  void update_simplex_tree_before_node_removal(Simplex_handle sh) {
#ifdef DEBUG_TRACES
    std::clog << "update_simplex_tree_before_node_removal" << std::endl;
#endif  // DEBUG_TRACES
    if constexpr (Options::link_nodes_by_label) {
      _to_node_it(sh)->second.unlink_hooks();  // remove from lists of same label Nodes
      if (nodes_label_to_list_[sh->first].empty())
        nodes_label_to_list_.erase(sh->first);
    }
  }
 
 public:
  void reset_filtration(const Filtration_value& filtration, int min_dim = 0) {
    rec_reset_filtration(&root_, filtration, min_dim);
    clear_filtration(); // Drop the cache.
  }
 
 private:
  void rec_reset_filtration(Siblings * sib, const Filtration_value& filt_value, int min_depth) {
    for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
      if (min_depth <= 0) {
        sh->second.assign_filtration(filt_value);
      }
      if (has_children(sh)) {
        rec_reset_filtration(sh->second.children(), filt_value, min_depth - 1);
      }
    }
  }
 
  std::size_t num_simplices_and_filtration_serialization_size(Siblings const* sib, std::size_t& fv_byte_size) const {
    using namespace Gudhi::simplex_tree;
 
    auto sib_begin = sib->members().begin();
    auto sib_end = sib->members().end();
    size_t simplices_number = sib->members().size();
    for (auto sh = sib_begin; sh != sib_end; ++sh) {
      if constexpr (SimplexTreeOptions::store_filtration)
        fv_byte_size += get_serialization_size_of(sh->second.filtration());
      if (has_children(sh)) {
        simplices_number += num_simplices_and_filtration_serialization_size(sh->second.children(), fv_byte_size);
      }
    }
    return simplices_number;
  }
 
 public:
  std::size_t get_serialization_size() const {
    const std::size_t version_byte_size = sizeof(std::int16_t);
    const std::size_t np_byte_size = sizeof(decltype(number_of_parameters_));
    const std::size_t vh_byte_size = sizeof(Vertex_handle);
    std::size_t fv_byte_size = 0;
    const std::size_t tree_size = num_simplices_and_filtration_serialization_size(&root_, fv_byte_size);
    const std::size_t buffer_byte_size =
        version_byte_size + np_byte_size + vh_byte_size + fv_byte_size + tree_size * 2 * vh_byte_size;
#ifdef DEBUG_TRACES
    std::clog << "Gudhi::simplex_tree::get_serialization_size - buffer size = " << buffer_byte_size << std::endl;
#endif  // DEBUG_TRACES
    return buffer_byte_size;
  }

  /* Let's take the following simplicial complex as example:         */
  /* (vertices are represented as letters to ease the understanding) */
  /*  o---o---o */
  /*  a   b\X/c */
  /*        o   */
  /*        d   */
  /* The simplex tree is: */
  /* a o  b o     c o   d o   */
  /*   |    |\      |         */
  /* b o  c o o d   o d       */
  /*        |                 */
  /*      d o                 */
  /* The serialization is (without filtration values that comes right after vertex handle value):                    */
  /* 04(number of vertices)0a 0b 0c 0d(list of vertices)01(number of [a] children)0b([a,b] simplex)                  */
  /* 00(number of [a,b] children)02(number of [b] children)0c 0d(list of [b] children)01(number of [b,c] children)   */
  /* 0d(list of [b,c] children)00(number of [b,c,d] children)00(number of [b,d] children)01(number of [c] children)  */
  /* 0d(list of [c] children)00(number of [b,d] children)00(number of [d] children)                                  */
  /* Without explanation and with filtration values:                                                                 */
  /* 04 0a F(a) 0b F(b) 0c F(c) 0d F(d) 01 0b F(a,b) 00 02 0c F(b,c) 0d F(b,d) 01 0d F(b,c,d) 00 00 01 0d F(c,d) 00 00 */
  void serialize(char* buffer, const std::size_t buffer_size) const {
    char* buffer_end = serialize_value_to_char_buffer(SERIALIZATION_VERSION, buffer);
    buffer_end = serialize_value_to_char_buffer(number_of_parameters_, buffer_end);
    buffer_end = rec_serialize(&root_, buffer_end);
    if (static_cast<std::size_t>(buffer_end - buffer) != buffer_size)
      throw std::invalid_argument("Serialization does not match end of buffer");
  }
 
 private:
  char* rec_serialize(Siblings const *sib, char* buffer) const {
    char* ptr = buffer;
    ptr = serialize_value_to_char_buffer(static_cast<Vertex_handle>(sib->members().size()), ptr);
#ifdef DEBUG_TRACES
    std::clog << "\n" << sib->members().size() << " : ";
#endif  // DEBUG_TRACES
    for (auto& map_el : sib->members()) {
      ptr = serialize_value_to_char_buffer(map_el.first, ptr); // Vertex
      if (Options::store_filtration)
        ptr = serialize_value_to_char_buffer(map_el.second.filtration(), ptr); // Filtration
#ifdef DEBUG_TRACES
      std::clog << " [ " << map_el.first << " | " << map_el.second.filtration() << " ] ";
#endif  // DEBUG_TRACES
    }
    for (auto& map_el : sib->members()) {
      if (has_children(&map_el)) {
        ptr = rec_serialize(map_el.second.children(), ptr);
      } else {
        ptr = serialize_value_to_char_buffer(static_cast<Vertex_handle>(0), ptr);
#ifdef DEBUG_TRACES
        std::cout << "\n0 : ";
#endif  // DEBUG_TRACES
      }
    }
    return ptr;
  }
 
 public:
  void deserialize(const char* buffer, const std::size_t buffer_size) {
    deserialize(buffer, buffer_size, [](Filtration_value& filtration, const char* ptr) {
      return deserialize_value_from_char_buffer(filtration, ptr);
    });
  }

  template <class F>
  void deserialize(const char* buffer, const std::size_t buffer_size, F&& deserialize_filtration_value) {
    GUDHI_CHECK(num_vertices() == 0, std::logic_error("Simplex_tree::deserialize - Simplex_tree must be empty"));
    const char* ptr = buffer;
    std::int16_t version;
    ptr = deserialize_value_from_char_buffer(version, ptr);
    if (version != SERIALIZATION_VERSION) {
      throw std::invalid_argument("The buffer comes from an non-compatible serialization version of the simplex tree.");
    }
    ptr = deserialize_value_from_char_buffer(number_of_parameters_, ptr);
    // Needs to read size before recursivity to manage new siblings for children
    Vertex_handle members_size;
    ptr = deserialize_value_from_char_buffer(members_size, ptr);
    ptr = rec_deserialize(&root_, members_size, ptr, 0, deserialize_filtration_value);
    if (static_cast<std::size_t>(ptr - buffer) != buffer_size) {
      throw std::invalid_argument("Deserialization does not match end of buffer");
    }
  }
 
 private:
  template <class F>
  const char* rec_deserialize(Siblings* sib,
                              Vertex_handle members_size,
                              const char* ptr,
                              int dim,
                              [[maybe_unused]] F&& deserialize_filtration_value)
  {
    // In case buffer is just a 0 char
    if (members_size > 0) {
      if constexpr (!Options::stable_simplex_handles) sib->members_.reserve(members_size);
      Vertex_handle vertex;
      // Set explicitly to zero to avoid false positive error raising in debug mode when store_filtration == false
      // and to force array like Filtration_value value to be empty.
      Filtration_value filtration(Gudhi::simplex_tree::empty_filtration_value);
      for (Vertex_handle idx = 0; idx < members_size; idx++) {
        ptr = deserialize_value_from_char_buffer(vertex, ptr);
        if constexpr (Options::store_filtration) {
          ptr = deserialize_filtration_value(filtration, ptr);
        }
        // Default is no children
        // If store_filtration is false, `filtration` is ignored.
        sib->members_.emplace_hint(sib->members_.end(), vertex, Node(sib, filtration));
      }
      Vertex_handle child_size;
      for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
        update_simplex_tree_after_node_insertion(sh);
        ptr = deserialize_value_from_char_buffer(child_size, ptr);
        if (child_size > 0) {
          Siblings* child = new Siblings(sib, sh->first);
          sh->second.assign_children(child);
          ptr = rec_deserialize(child, child_size, ptr, dim + 1, deserialize_filtration_value);
        }
      }
      if (dim > dimension_) {
        // Update dimension if needed
        dimension_ = dim;
      }
    }
    return ptr;
  }
 
 public:
  // Print a Simplex_tree in os.
  friend std::ostream& operator<<(std::ostream& os, const Simplex_tree& st) {
    st.for_each_simplex([&](Simplex_handle sh, int dim) {
      os << dim << " ";
      for (auto v : st.simplex_vertex_range(sh)) {
        os << v << " ";
      }
      // TODO(VR): why adding the key ?? not read ?? << "     " << st.key(sh) << " \n";
      os << st.filtration(sh) << "\n";
    });
    return os;
  }
 
  friend std::istream& operator>>(std::istream & is, Simplex_tree & st) {
    std::vector<Vertex_handle> simplex;
    Filtration_value fil;
    int max_dim = -1;
    while (read_simplex(is, simplex, fil)) {
      // read all simplices in the file as a list of vertices
      // Warning : simplex_size needs to be casted in int - Can be 0
      int dim = static_cast<int> (simplex.size() - 1);
      if (max_dim < dim) {
        max_dim = dim;
      }
      // insert every simplex in the simplex tree
      st.insert_simplex(simplex, fil);
      simplex.clear();
    }
    st.set_dimension(max_dim);
 
    return is;
  }
 
 private:
  Vertex_handle null_vertex_;
  Siblings root_;
  int number_of_parameters_;
 
  // all mutable as their content has no impact on the content of the simplex tree itself
  // they correspond to some kind of cache or helper attributes.
  mutable std::vector<Simplex_handle> filtration_vect_;
  mutable int dimension_;
  mutable bool dimension_to_be_lowered_;

  static constexpr std::int16_t SERIALIZATION_VERSION = 1;
};
  // end addtogroup simplex_tree
 
}  // namespace Gudhi
 
#endif  // SIMPLEX_TREE_H_