Position_to_index_overlay.h

Go to the documentation of this file.

/*    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):       Hannah Schreiber
 *
 *    Copyright (C) 2022 Inria
 *
 *    Modification(s):
 *      - YYYY/MM Author: Description of the modification
 */

 
#ifndef PM_POS_TO_ID_TRANSLATION_H
#define PM_POS_TO_ID_TRANSLATION_H
 
#include <stdexcept>
#include <vector>
#include <utility>    //std::swap, std::move & std::exchange
#include <algorithm>  //std::transform
 
#include <gudhi/Debug_utils.h>
 
namespace Gudhi {
namespace persistence_matrix {

template <class Underlying_matrix, class Master_matrix>
class Position_to_index_overlay
{
 public:
  using Index = typename Master_matrix::Index;         
  using ID_index = typename Master_matrix::ID_index;   
  using Pos_index = typename Master_matrix::Pos_index; 
  using Dimension = typename Master_matrix::Dimension; 
  using Field_operators = typename Master_matrix::Field_operators;
  using Field_element = typename Master_matrix::Element;                     
  using Boundary = typename Master_matrix::Boundary;                         
  using Column = typename Master_matrix::Column;                             
  using Row = typename Master_matrix::Row;                                   
  using Bar = typename Master_matrix::Bar;                                   
  using Barcode = typename Master_matrix::Barcode;                           
  using Cycle = typename Master_matrix::Cycle;                               
  using Entry_representative = typename Master_matrix::Entry_representative; 
  using Entry_constructor = typename Master_matrix::Entry_constructor;       
  using Column_settings = typename Master_matrix::Column_settings;           

  Position_to_index_overlay(Column_settings* colSettings);
  template <class Boundary_range = Boundary>
  Position_to_index_overlay(const std::vector<Boundary_range>& orderedBoundaries, Column_settings* colSettings);
  Position_to_index_overlay(unsigned int numberOfColumns, Column_settings* colSettings);
  template <typename BirthComparatorFunction, typename DeathComparatorFunction>
  Position_to_index_overlay(Column_settings* colSettings,
                            const BirthComparatorFunction& birthComparator,
                            const DeathComparatorFunction& deathComparator);
  template <typename BirthComparatorFunction, typename DeathComparatorFunction, class Boundary_range>
  Position_to_index_overlay(const std::vector<Boundary_range>& orderedBoundaries,
                            Column_settings* colSettings,
                            const BirthComparatorFunction& birthComparator,
                            const DeathComparatorFunction& deathComparator);
  template <typename BirthComparatorFunction, typename DeathComparatorFunction>
  Position_to_index_overlay(unsigned int numberOfColumns,
                            Column_settings* colSettings,
                            const BirthComparatorFunction& birthComparator,
                            const DeathComparatorFunction& deathComparator);
  Position_to_index_overlay(const Position_to_index_overlay& matrixToCopy, Column_settings* colSettings = nullptr);
  Position_to_index_overlay(Position_to_index_overlay&& other) noexcept;
 
  ~Position_to_index_overlay() = default;

  template <class Boundary_range = Boundary>
  void insert_boundary(const Boundary_range& boundary,
                       Dimension dim = Master_matrix::template get_null_value<Dimension>());
  template <class Boundary_range = Boundary>
  void insert_boundary(ID_index cellIndex,
                       const Boundary_range& boundary,
                       Dimension dim = Master_matrix::template get_null_value<Dimension>());
  template <class Boundary_range = Boundary>
  void insert_maximal_cell(Index columnIndex,
                           const Boundary_range& boundary,
                           Dimension dim = Master_matrix::template get_null_value<Dimension>());
  template <class Boundary_range = Boundary>
  void insert_maximal_cell(Index columnIndex,
                           ID_index cellIndex,
                           const Boundary_range& boundary,
                           Dimension dim = Master_matrix::template get_null_value<Dimension>());

  Column& get_column(Pos_index position);
  const Column& get_column(Pos_index position) const;
  Row& get_row(ID_index rowIndex);
  const Row& get_row(ID_index rowIndex) const;
  void erase_empty_row(ID_index rowIndex);
  void remove_maximal_cell(Pos_index position);
  void remove_last();

  Dimension get_max_dimension() const;
  Index get_number_of_columns() const;
  Dimension get_column_dimension(Pos_index position) const;

  void add_to(Pos_index sourcePosition, Pos_index targetPosition);
  void multiply_target_and_add_to(Pos_index sourcePosition, const Field_element& coefficient, Pos_index targetPosition);
  void multiply_source_and_add_to(const Field_element& coefficient, Pos_index sourcePosition, Pos_index targetPosition);

  bool is_zero_entry(Pos_index position, ID_index rowIndex) const;
  bool is_zero_column(Pos_index position);

  Pos_index get_column_with_pivot(ID_index cellIndex) const;  // assumes that pivot exists
  ID_index get_pivot(Pos_index position);

  void reset(Column_settings* colSettings)
  {
    matrix_.reset(colSettings);
    positionToIndex_.clear();
    nextPosition_ = 0;
    nextIndex_ = 0;
  }

  Position_to_index_overlay& operator=(const Position_to_index_overlay& other) = default;
  Position_to_index_overlay& operator=(Position_to_index_overlay&& other) noexcept = default;

  friend void swap(Position_to_index_overlay& matrix1, Position_to_index_overlay& matrix2) noexcept
  {
    swap(matrix1.matrix_, matrix2.matrix_);
    matrix1.positionToIndex_.swap(matrix2.positionToIndex_);
    std::swap(matrix1.nextPosition_, matrix2.nextPosition_);
    std::swap(matrix1.nextIndex_, matrix2.nextIndex_);
  }
 
  void print();  // for debug
 
  // access to optional methods

  const Barcode& get_current_barcode() const;

  void update_all_representative_cycles(Dimension dim = Master_matrix::template get_null_value<Dimension>());
  void update_representative_cycle(const Bar& bar);
  const std::vector<Cycle>& get_all_representative_cycles() const;
  const Cycle& get_representative_cycle(const Bar& bar) const;

  bool vine_swap_with_z_eq_1_case(Pos_index position);
  bool vine_swap(Pos_index position);
 
 private:
  Underlying_matrix matrix_;           
  std::vector<Index> positionToIndex_; 
  Pos_index nextPosition_;             
  Index nextIndex_;                    
 
  template <bool dir>
  void _move_column(Pos_index start, Pos_index end);
};
 
template <class Underlying_matrix, class Master_matrix>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    Column_settings* colSettings)
    : matrix_(colSettings), nextPosition_(0), nextIndex_(0)
{}
 
template <class Underlying_matrix, class Master_matrix>
template <class Boundary_range>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    const std::vector<Boundary_range>& orderedBoundaries,
    Column_settings* colSettings)
    : matrix_(orderedBoundaries, colSettings),
      positionToIndex_(orderedBoundaries.size()),
      nextPosition_(orderedBoundaries.size()),
      nextIndex_(orderedBoundaries.size())
{
  for (Index i = 0; i < orderedBoundaries.size(); i++) {
    positionToIndex_[i] = i;
  }
}
 
template <class Underlying_matrix, class Master_matrix>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    unsigned int numberOfColumns,
    Column_settings* colSettings)
    : matrix_(numberOfColumns, colSettings), positionToIndex_(numberOfColumns), nextPosition_(0), nextIndex_(0)
{}
 
template <class Underlying_matrix, class Master_matrix>
template <typename BirthComparatorFunction, typename DeathComparatorFunction>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    Column_settings* colSettings,
    const BirthComparatorFunction& birthComparator,
    const DeathComparatorFunction& deathComparator)
    : matrix_(colSettings, birthComparator, deathComparator), nextPosition_(0), nextIndex_(0)
{}
 
template <class Underlying_matrix, class Master_matrix>
template <typename BirthComparatorFunction, typename DeathComparatorFunction, class Boundary_range>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    const std::vector<Boundary_range>& orderedBoundaries,
    Column_settings* colSettings,
    const BirthComparatorFunction& birthComparator,
    const DeathComparatorFunction& deathComparator)
    : matrix_(orderedBoundaries, colSettings, birthComparator, deathComparator),
      positionToIndex_(orderedBoundaries.size()),
      nextPosition_(orderedBoundaries.size()),
      nextIndex_(orderedBoundaries.size())
{
  for (Index i = 0; i < orderedBoundaries.size(); i++) {
    positionToIndex_[i] = i;
  }
}
 
template <class Underlying_matrix, class Master_matrix>
template <typename BirthComparatorFunction, typename DeathComparatorFunction>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    unsigned int numberOfColumns,
    Column_settings* colSettings,
    const BirthComparatorFunction& birthComparator,
    const DeathComparatorFunction& deathComparator)
    : matrix_(numberOfColumns, colSettings, birthComparator, deathComparator),
      positionToIndex_(numberOfColumns),
      nextPosition_(0),
      nextIndex_(0)
{}
 
template <class Underlying_matrix, class Master_matrix>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    const Position_to_index_overlay& matrixToCopy,
    Column_settings* colSettings)
    : matrix_(matrixToCopy.matrix_, colSettings),
      positionToIndex_(matrixToCopy.positionToIndex_),
      nextPosition_(matrixToCopy.nextPosition_),
      nextIndex_(matrixToCopy.nextIndex_)
{}
 
template <class Underlying_matrix, class Master_matrix>
inline Position_to_index_overlay<Underlying_matrix, Master_matrix>::Position_to_index_overlay(
    Position_to_index_overlay&& other) noexcept
    : matrix_(std::move(other.matrix_)),
      positionToIndex_(std::move(other.positionToIndex_)),
      nextPosition_(std::exchange(other.nextPosition_, 0)),
      nextIndex_(std::exchange(other.nextIndex_, 0))
{}
 
template <class Underlying_matrix, class Master_matrix>
template <class Boundary_range>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::insert_boundary(const Boundary_range& boundary,
                                                                                         Dimension dim)
{
  if (positionToIndex_.size() <= nextPosition_) {
    positionToIndex_.resize((nextPosition_ * 2) + 1);
  }
 
  positionToIndex_[nextPosition_++] = nextIndex_++;
 
  matrix_.insert_boundary(boundary, dim);
}
 
template <class Underlying_matrix, class Master_matrix>
template <class Boundary_range>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::insert_boundary(ID_index cellIndex,
                                                                                         const Boundary_range& boundary,
                                                                                         Dimension dim)
{
  if (positionToIndex_.size() <= nextPosition_) {
    positionToIndex_.resize((nextPosition_ * 2) + 1);
  }
 
  positionToIndex_[nextPosition_++] = nextIndex_++;
 
  matrix_.insert_boundary(cellIndex, boundary, dim);
}
 
template <class Underlying_matrix, class Master_matrix>
template <class Boundary_range>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::insert_maximal_cell(
    Index columnIndex,
    const Boundary_range& boundary,
    Dimension dim)
{
  GUDHI_CHECK(columnIndex >= 0, std::invalid_argument("Indices have to be positive."));
 
  insert_boundary(boundary, dim);
 
  if (nextPosition_ == 1) return;
 
  // false = backward direction
  _move_column<false>(nextPosition_ - 1, columnIndex);
}
 
template <class Underlying_matrix, class Master_matrix>
template <class Boundary_range>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::insert_maximal_cell(
    Index columnIndex,
    ID_index cellIndex,
    const Boundary_range& boundary,
    Dimension dim)
{
  GUDHI_CHECK(columnIndex >= 0, std::invalid_argument("Indices have to be positive."));
 
  insert_boundary(cellIndex, boundary, dim);
 
  if (nextPosition_ == 1) return;
 
  // false = backward direction
  _move_column<false>(nextPosition_ - 1, columnIndex);
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Column&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_column(Pos_index position)
{
  return matrix_.get_column(positionToIndex_[position]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline const typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Column&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_column(Pos_index position) const
{
  return matrix_.get_column(positionToIndex_[position]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Row&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_row(ID_index rowIndex)
{
  return matrix_.get_row(rowIndex);
}
 
template <class Underlying_matrix, class Master_matrix>
inline const typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Row&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_row(ID_index rowIndex) const
{
  return matrix_.get_row(rowIndex);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::erase_empty_row(ID_index rowIndex)
{
  return matrix_.erase_empty_row(rowIndex);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::remove_maximal_cell(Pos_index position)
{
  --nextPosition_;
 
  // true = forward direction
  _move_column<true>(position, nextPosition_);
 
  matrix_._remove_last(positionToIndex_[nextPosition_]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::remove_last()
{
  --nextPosition_;
  if constexpr (Master_matrix::Option_list::has_vine_update) {
    std::vector<Index> columnsToSwap;
    matrix_.remove_maximal_cell(matrix_.get_pivot(positionToIndex_[nextPosition_]), columnsToSwap);
  } else {
    matrix_.remove_last();  // linear with vine updates, so it is better to use remove_maximal_cell
  }
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Dimension
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_max_dimension() const
{
  return matrix_.get_max_dimension();
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Index
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_number_of_columns() const
{
  return matrix_.get_number_of_columns();
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Dimension
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_column_dimension(Pos_index position) const
{
  return matrix_.get_column_dimension(positionToIndex_[position]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::add_to(Pos_index sourcePosition,
                                                                                Pos_index targetPosition)
{
  return matrix_.add_to(positionToIndex_[sourcePosition], positionToIndex_[targetPosition]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::multiply_target_and_add_to(
    Pos_index sourcePosition,
    const Field_element& coefficient,
    Pos_index targetPosition)
{
  return matrix_.multiply_target_and_add_to(
      positionToIndex_[sourcePosition], coefficient, positionToIndex_[targetPosition]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::multiply_source_and_add_to(
    const Field_element& coefficient,
    Pos_index sourcePosition,
    Pos_index targetPosition)
{
  return matrix_.multiply_source_and_add_to(
      coefficient, positionToIndex_[sourcePosition], positionToIndex_[targetPosition]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline bool Position_to_index_overlay<Underlying_matrix, Master_matrix>::is_zero_entry(Pos_index position,
                                                                                       ID_index rowIndex) const
{
  return matrix_.is_zero_entry(positionToIndex_[position], rowIndex);
}
 
template <class Underlying_matrix, class Master_matrix>
inline bool Position_to_index_overlay<Underlying_matrix, Master_matrix>::is_zero_column(Pos_index position)
{
  return matrix_.is_zero_column(positionToIndex_[position]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Pos_index
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_column_with_pivot(ID_index cellIndex) const
{
  Index id = matrix_.get_column_with_pivot(cellIndex);
  Pos_index i = 0;
  while (positionToIndex_[i] != id) ++i;
  return i;
}
 
template <class Underlying_matrix, class Master_matrix>
inline typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::ID_index
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_pivot(Pos_index position)
{
  return matrix_.get_pivot(positionToIndex_[position]);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::print()
{
  return matrix_.print();
}
 
template <class Underlying_matrix, class Master_matrix>
inline const typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Barcode&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_current_barcode() const
{
  return matrix_.get_current_barcode();
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::update_all_representative_cycles(Dimension dim)
{
  matrix_.update_all_representative_cycles(dim);
}
 
template <class Underlying_matrix, class Master_matrix>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::update_representative_cycle(const Bar& bar)
{
  matrix_.update_representative_cycle(bar);
}
 
template <class Underlying_matrix, class Master_matrix>
inline const std::vector<typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Cycle>&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_all_representative_cycles() const
{
  return matrix_.get_all_representative_cycles();
}
 
template <class Underlying_matrix, class Master_matrix>
inline const typename Position_to_index_overlay<Underlying_matrix, Master_matrix>::Cycle&
Position_to_index_overlay<Underlying_matrix, Master_matrix>::get_representative_cycle(const Bar& bar) const
{
  return matrix_.get_representative_cycle(bar);
}
 
template <class Underlying_matrix, class Master_matrix>
inline bool Position_to_index_overlay<Underlying_matrix, Master_matrix>::vine_swap_with_z_eq_1_case(Pos_index position)
{
  Index next = matrix_.vine_swap_with_z_eq_1_case(positionToIndex_[position], positionToIndex_[position + 1]);
  if (next == positionToIndex_[position]) {
    std::swap(positionToIndex_[position], positionToIndex_[position + 1]);
    return true;
  }
 
  return false;
}
 
template <class Underlying_matrix, class Master_matrix>
inline bool Position_to_index_overlay<Underlying_matrix, Master_matrix>::vine_swap(Pos_index position)
{
  Index next = matrix_.vine_swap(positionToIndex_[position], positionToIndex_[position + 1]);
  if (next == positionToIndex_[position]) {
    std::swap(positionToIndex_[position], positionToIndex_[position + 1]);
    return true;
  }
 
  return false;
}
 
template <class Underlying_matrix, class Master_matrix>
template <bool dir>
inline void Position_to_index_overlay<Underlying_matrix, Master_matrix>::_move_column(Pos_index start, Pos_index end)
{
  if constexpr (dir) {
    for (Pos_index p = start; p < end; ++p) {
      vine_swap(p);
    }
  } else {
    for (Pos_index p = start; p > end; --p) {
      vine_swap(p - 1);
    }
  }
}
 
}  // namespace persistence_matrix
}  // namespace Gudhi
 
#endif  // PM_POS_TO_ID_TRANSLATION_H