/* This file is part of the Gudhi Library. The Gudhi library
* (Geometric Understanding in Higher Dimensions) is a generic C++
* library for computational topology.
*
* Author(s): Pawel Dlotko
*
* Copyright (C) 2015 INRIA Sophia-Saclay (France)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
#pragma once
#include
#include "Bitmap_cubical_complex_base.h"
#include "Bitmap_cubical_complex_periodic_boundary_conditions_base.h"
namespace Gudhi
{
namespace Cubical_complex
{
//global variable, was used just for debugging.
const bool globalDbg = false;
template class is_before_in_filtration;
template
class Bitmap_cubical_complex : public T
{
public:
//*********************************************//
//Typedefs and typenames
//*********************************************//
typedef size_t Simplex_key;
typedef typename T::filtration_type Filtration_value;
typedef Simplex_key Simplex_handle;
//*********************************************//
//Constructors
//*********************************************//
//Over here we need to definie various input types. I am proposing the following ones:
//Perseus style
//H5 files? TODO
//binary files with little endiangs / big endians? TODO
//constructor from a vector of elements of a type T. TODO
/**
* Constructor form a Perseus-style file.
**/
Bitmap_cubical_complex( const char* perseus_style_file ):
T(perseus_style_file),key_associated_to_simplex(this->total_number_of_cells+1)
{
//clock_t begin = clock();
if ( globalDbg ){cerr << "Bitmap_cubical_complex( const char* perseus_style_file )\n";}
for ( size_t i = 0 ; i != this->total_number_of_cells ; ++i )
{
this->key_associated_to_simplex[i] = i;
}
//we initialize this only once, in each constructor, when the bitmap is constructed.
//If the user decide to change some elements of the bitmap, then this procedure need
//to be called again.
this->initialize_simplex_associated_to_key();
//cerr << "Time of running Bitmap_cubical_complex( const char* perseus_style_file ) constructor : " << double(clock() - begin) / CLOCKS_PER_SEC << endl;
}
/**
* Constructor that requires vector of elements of type unsigned, which gives number of top dimensional cells
* in the following directions and vector of element of a type T
* with filtration on top dimensional cells.
**/
Bitmap_cubical_complex( const std::vector& dimensions , const std::vector& top_dimensional_cells ):
T(dimensions,top_dimensional_cells),
key_associated_to_simplex(this->total_number_of_cells+1)
{
for ( size_t i = 0 ; i != this->total_number_of_cells ; ++i )
{
this->key_associated_to_simplex[i] = i;
}
//we initialize this only once, in each constructor, when the bitmap is constructed.
//If the user decide to change some elements of the bitmap, then this procedure need
//to be called again.
this->initialize_simplex_associated_to_key();
}
/**
* Constructor that requires vector of elements of type unsigned, which gives number of top dimensional cells
* in the following directions and vector of element of a type T::filtration_type
* with filtration on top dimensional cells. The last parameter of the constructor is a vector of bools of a length equal to the dimension of cubical complex.
* If the position i on this vector is true, then we impose periodic boundary conditions in this direction.
**/
Bitmap_cubical_complex( const std::vector& dimensions , const std::vector& top_dimensional_cells , std::vector< bool > directions_in_which_periodic_b_cond_are_to_be_imposed ):
T(dimensions,top_dimensional_cells,directions_in_which_periodic_b_cond_are_to_be_imposed),
key_associated_to_simplex(this->total_number_of_cells+1)
{
for ( size_t i = 0 ; i != this->total_number_of_cells ; ++i )
{
this->key_associated_to_simplex[i] = i;
}
//we initialize this only once, in each constructor, when the bitmap is constructed.
//If the user decide to change some elements of the bitmap, then this procedure need
//to be called again.
this->initialize_simplex_associated_to_key();
}
//*********************************************//
//Other 'easy' functions
//*********************************************//
/**
* Returns number of all cubes in the complex.
**/
size_t num_simplices()const
{
return this->total_number_of_cells;
}
/**
* Returns a Simplex_handle to a cube that do not exist in this complex.
**/
static Simplex_handle null_simplex()
{
if ( globalDbg ){cerr << "Simplex_handle null_simplex()\n";}
return std::numeric_limits::max();
}
/**
* Returns dimension of the complex.
**/
inline size_t dimension()const
{
return this->sizes.size();
}
/**
* Return dimension of a cell pointed by the Simplex_handle.
**/
inline unsigned dimension(Simplex_handle sh)const
{
if ( globalDbg ){cerr << "unsigned dimension(const Simplex_handle& sh)\n";}
if ( sh != std::numeric_limits::max() ) return this->get_dimension_of_a_cell( sh );
return -1;
}
/**
* Return the filtration of a cell pointed by the Simplex_handle.
**/
typename T::filtration_type filtration(Simplex_handle sh)
{
if ( globalDbg ){cerr << "T::filtration_type filtration(const Simplex_handle& sh)\n";}
//Returns the filtration value of a simplex.
if ( sh != std::numeric_limits::max() ) return this->data[sh];
return std::numeric_limits::max();
}
/**
* Return a key which is not a key of any cube in the considered data structure.
**/
static Simplex_key null_key()
{
if ( globalDbg ){cerr << "Simplex_key null_key()\n";}
return std::numeric_limits::max();
}
/**
* Return the key of a cube pointed by the Simplex_handle.
**/
Simplex_key key(Simplex_handle sh)const
{
if ( globalDbg ){cerr << "Simplex_key key(const Simplex_handle& sh)\n";}
if ( sh != std::numeric_limits::max() )
{
return this->key_associated_to_simplex[sh];
}
return this->null_key();
}
/**
* Return the Simplex_handle given the key of the cube.
**/
Simplex_handle simplex(Simplex_key key)
{
if ( globalDbg ){cerr << "Simplex_handle simplex(Simplex_key key)\n";}
if ( key != std::numeric_limits::max() )
{
return this->simplex_associated_to_key[ key ];
}
return null_simplex();
}
/**
* Assign key to a cube pointed by the Simplex_handle
**/
void assign_key(Simplex_handle sh, Simplex_key key)
{
if ( globalDbg ){cerr << "void assign_key(Simplex_handle& sh, Simplex_key key)\n";}
if ( key == std::numeric_limits::max() ) return;
this->key_associated_to_simplex[sh] = key;
this->simplex_associated_to_key[key] = sh;
}
/**
* Function called from a constructor. It is needed for Filtration_simplex_iterator to work.
**/
void initialize_simplex_associated_to_key();
//*********************************************//
//Iterators
//*********************************************//
/**
* Boundary_simplex_range class provides ranges for boundary iterators.
**/
typedef typename std::vector< Simplex_handle >::iterator Boundary_simplex_iterator;
typedef typename std::vector< Simplex_handle > Boundary_simplex_range;
/**
* Filtration_simplex_iterator class provides an iterator though the whole structure in the order of filtration.
* Secondary criteria for filtration are:
* (1) Dimension of a cube (lower dimensional comes first).
* (2) Position in the data structure (the ones that are earlies in the data structure comes first).
**/
class Filtration_simplex_range;
class Filtration_simplex_iterator : std::iterator< std::input_iterator_tag, Simplex_handle >
{
//Iterator over all simplices of the complex in the order of the indexing scheme.
//'value_type' must be 'Simplex_handle'.
public:
Filtration_simplex_iterator( Bitmap_cubical_complex* b ):b(b),position(0){};
Filtration_simplex_iterator():b(NULL){};
Filtration_simplex_iterator operator++()
{
if ( globalDbg ){cerr << "Filtration_simplex_iterator operator++\n";}
++this->position;
return (*this);
}
Filtration_simplex_iterator operator++(int)
{
Filtration_simplex_iterator result = *this;
++(*this);
return result;
}
Filtration_simplex_iterator operator =( const Filtration_simplex_iterator& rhs )
{
if ( globalDbg ){cerr << "Filtration_simplex_iterator operator =\n";}
this->b = rhs.b;
this->position = rhs.position;
}
bool operator == ( const Filtration_simplex_iterator& rhs )const
{
if ( globalDbg ){cerr << "bool operator == ( const Filtration_simplex_iterator& rhs )\n";}
return ( this->position == rhs.position );
}
bool operator != ( const Filtration_simplex_iterator& rhs )const
{
if ( globalDbg ){cerr << "bool operator != ( const Filtration_simplex_iterator& rhs )\n";}
return !(*this == rhs);
}
Simplex_handle operator*()
{
if ( globalDbg ){cerr << "Simplex_handle operator*()\n";}
return this->b->simplex_associated_to_key[ this->position ];
}
friend class Filtration_simplex_range;
private:
Bitmap_cubical_complex* b;
size_t position;
};
/**
* Filtration_simplex_range provides the ranges for Filtration_simplex_iterator.
**/
class Filtration_simplex_range
{
//Range over the simplices of the complex in the order of the filtration.
//.begin() and .end() return type Filtration_simplex_iterator.
public:
typedef Filtration_simplex_iterator const_iterator;
typedef Filtration_simplex_iterator iterator;
Filtration_simplex_range(Bitmap_cubical_complex* b):b(b){};
Filtration_simplex_iterator begin()
{
if ( globalDbg ){cerr << "Filtration_simplex_iterator begin() \n";}
return Filtration_simplex_iterator( this->b );
}
Filtration_simplex_iterator end()
{
if ( globalDbg ){cerr << "Filtration_simplex_iterator end()\n";}
Filtration_simplex_iterator it( this->b );
it.position = this->b->simplex_associated_to_key.size();
return it;
}
private:
Bitmap_cubical_complex* b;
};
//*********************************************//
//Methods to access iterators from the container:
/**
* boundary_simplex_range creates an object of a Boundary_simplex_range class
* that provides ranges for the Boundary_simplex_iterator.
**/
Boundary_simplex_range boundary_simplex_range(Simplex_handle sh)
{
/*
std::vector< size_t > bdry = this->get_boundary_of_a_cell(sh);
Boundary_simplex_range result( bdry.size() );
for ( size_t i = 0 ; i != bdry.size() ; ++i )
{
result[i] = this->simplex_associated_to_key[ bdry[i] ];
}
return result;
*/
return this->get_boundary_of_a_cell(sh);
}
/**
* filtration_simplex_range creates an object of a Filtration_simplex_range class
* that provides ranges for the Filtration_simplex_iterator.
**/
Filtration_simplex_range filtration_simplex_range()
{
if ( globalDbg ){cerr << "Filtration_simplex_range filtration_simplex_range()\n";}
//Returns a range over the simplices of the complex in the order of the filtration
return Filtration_simplex_range(this);
}
//*********************************************//
//*********************************************//
//Elements which are in Gudhi now, but I (and in all the cases I asked also Marc) do not understand why they are there.
//TODO -- the file IndexingTag.h in the Gudhi library contains an empty structure, so
//I understand that this is something that was planned (for simplicial maps?)
//but was never finished. The only idea I have here is to use the same empty structure from
//IndexingTag.h file, but only if the compiler needs it. If the compiler
//do not need it, then I would rather not add here elements which I do not understand.
//typedef Indexing_tag
/**
* Function needed for compatibility with Gudhi. Not useful for other purposes.
**/
std::pair endpoints( Simplex_handle sh )
{
std::vector< size_t > bdry = this->get_boundary_of_a_cell( sh );
if ( globalDbg )
{
cerr << "std::pair endpoints( Simplex_handle sh )\n";
cerr << "bdry.size() : " << bdry.size() << endl;
}
//this method returns two first elements from the boundary of sh.
if ( bdry.size() < 2 )
throw("Error in endpoints in Bitmap_cubical_complex class. The cell have less than two elements in the boundary.");
return std::make_pair( bdry[0] , bdry[1] );
}
/**
* Class needed for compatibility with Gudhi. Not useful for other purposes.
**/
class Skeleton_simplex_range;
class Skeleton_simplex_iterator : std::iterator< std::input_iterator_tag, Simplex_handle >
{
//Iterator over all simplices of the complex in the order of the indexing scheme.
//'value_type' must be 'Simplex_handle'.
public:
Skeleton_simplex_iterator ( Bitmap_cubical_complex* b , size_t d ):b(b),dimension(d)
{
if ( globalDbg ){cerr << "Skeleton_simplex_iterator ( Bitmap_cubical_complex* b , size_t d )\n";}
//find the position of the first simplex of a dimension d
this->position = 0;
while (
(this->position != b->data.size()) &&
( this->b->get_dimension_of_a_cell( this->position ) != this->dimension )
)
{
++this->position;
}
};
Skeleton_simplex_iterator ():b(NULL),dimension(0){};
Skeleton_simplex_iterator operator++()
{
if ( globalDbg ){cerr << "Skeleton_simplex_iterator operator++()\n";}
//increment the position as long as you did not get to the next element of the dimension dimension.
++this->position;
while (
(this->position != this->b->data.size()) &&
( this->b->get_dimension_of_a_cell( this->position ) != this->dimension )
)
{
++this->position;
}
return (*this);
}
Skeleton_simplex_iterator operator++(int)
{
Skeleton_simplex_iterator result = *this;
++(*this);
return result;
}
Skeleton_simplex_iterator operator =( const Skeleton_simplex_iterator& rhs )
{
if ( globalDbg ){cerr << "Skeleton_simplex_iterator operator =\n";}
this->b = rhs.b;
this->position = rhs.position;
}
bool operator == ( const Skeleton_simplex_iterator& rhs )const
{
if ( globalDbg ){cerr << "bool operator ==\n";}
return ( this->position == rhs.position );
}
bool operator != ( const Skeleton_simplex_iterator& rhs )const
{
if ( globalDbg ){cerr << "bool operator != ( const Skeleton_simplex_iterator& rhs )\n";}
return !(*this == rhs);
}
Simplex_handle operator*()
{
if ( globalDbg ){cerr << "Simplex_handle operator*() \n";}
return this->position;
}
friend class Skeleton_simplex_range;
private:
Bitmap_cubical_complex* b;
size_t position;
unsigned dimension;
};
/**
* Class needed for compatibility with Gudhi. Not useful for other purposes.
**/
class Skeleton_simplex_range
{
//Range over the simplices of the complex in the order of the filtration.
//.begin() and .end() return type Filtration_simplex_iterator.
public:
typedef Skeleton_simplex_iterator const_iterator;
typedef Skeleton_simplex_iterator iterator;
Skeleton_simplex_range(Bitmap_cubical_complex* b , unsigned dimension):b(b),dimension(dimension){};
Skeleton_simplex_iterator begin()
{
if ( globalDbg ){cerr << "Skeleton_simplex_iterator begin()\n";}
return Skeleton_simplex_iterator( this->b , this->dimension );
}
Skeleton_simplex_iterator end()
{
if ( globalDbg ){cerr << "Skeleton_simplex_iterator end()\n";}
Skeleton_simplex_iterator it( this->b , this->dimension );
it.position = this->b->data.size();
return it;
}
private:
Bitmap_cubical_complex* b;
unsigned dimension;
};
/**
* Function needed for compatibility with Gudhi. Not useful for other purposes.
**/
Skeleton_simplex_range skeleton_simplex_range( unsigned dimension )
{
if ( globalDbg ){cerr << "Skeleton_simplex_range skeleton_simplex_range( unsigned dimension )\n";}
return Skeleton_simplex_range( this , dimension );
}
friend class is_before_in_filtration;
protected:
std::vector< size_t > key_associated_to_simplex;
std::vector< size_t > simplex_associated_to_key;
};//Bitmap_cubical_complex
template
void Bitmap_cubical_complex::initialize_simplex_associated_to_key()
{
if ( globalDbg )
{
cerr << "void Bitmap_cubical_complex::initialize_elements_ordered_according_to_filtration() \n";
}
this->simplex_associated_to_key = std::vector( this->data.size() );
std::iota (std::begin(simplex_associated_to_key), std::end(simplex_associated_to_key), 0);
std::sort( simplex_associated_to_key.begin() ,
simplex_associated_to_key.end() ,
is_before_in_filtration(this) );
//we still need to deal here with a key_associated_to_simplex:
for ( size_t i = 0 ; i != simplex_associated_to_key.size() ; ++i )
{
this->key_associated_to_simplex[ simplex_associated_to_key[i] ] = i;
}
}
template
class is_before_in_filtration
{
public:
explicit is_before_in_filtration(Bitmap_cubical_complex * CC)
: CC_(CC) { }
bool operator()( const typename Bitmap_cubical_complex::Simplex_handle sh1, const typename Bitmap_cubical_complex::Simplex_handle sh2) const
{
// Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
typename T::filtration_type fil1 = CC_->data[sh1];
typename T::filtration_type fil2 = CC_->data[sh2];
if ( fil1 != fil2 )
{
return fil1 < fil2;
}
//in this case they are on the same filtration level, so the dimension decide.
size_t dim1 = CC_->get_dimension_of_a_cell(sh1);
size_t dim2 = CC_->get_dimension_of_a_cell(sh2);
if ( dim1 != dim2 )
{
return dim1 < dim2;
}
//in this case both filtration and dimensions of the considered cubes are the same. To have stable sort, we simply compare their positions in the bitmap:
return sh1 < sh2;
}
protected:
Bitmap_cubical_complex* CC_;
};
//****************************************************************************************************************//
//****************************************************************************************************************//
//****************************************************************************************************************//
//****************************************************************************************************************//
}
}