CubicalComplex.h

 
#pragma once
 
#if defined(CubicalComplex_RECURSES)
#error Recursive header files inclusion detected in CubicalComplex.h
#else // defined(CubicalComplex_RECURSES)
#define CubicalComplex_RECURSES
 
#if !defined CubicalComplex_h
#define CubicalComplex_h
 
// Inclusions
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <boost/type_traits.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include "DGtal/base/Common.h"
#include "DGtal/base/ConstAlias.h"
#include "DGtal/base/Alias.h"
#include "DGtal/base/ContainerTraits.h"
#include "DGtal/base/CSTLAssociativeContainer.h"
#include "DGtal/topology/CCellularGridSpaceND.h"
 
namespace DGtal
{
 
  struct CubicalCellData {
    inline CubicalCellData() : data( 0 ) {}
    CubicalCellData( uint32_t d ) : data( d ) {}
    uint32_t data;
  };
 
  // Forward definitions.
  template < typename TKSpace, typename TCellContainer >
  class CubicalComplex;
 
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >&
  operator|=( CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >&
  operator&=( CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >&
  operator^=( CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >&
  operator-=( CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >
  operator| ( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >
  operator& ( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >
  operator^ ( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >
  operator- ( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
 
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >
  operator~ ( const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  CubicalComplex< TKSpace, TCellContainer >
  operator* ( const CubicalComplex< TKSpace, TCellContainer >& );
 
  template < typename TKSpace, typename TCellContainer >
  bool
  operator==( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  bool
  operator!=( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  bool
  operator<=( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
  template < typename TKSpace, typename TCellContainer >
  bool
  operator>=( const CubicalComplex< TKSpace, TCellContainer >&,
              const CubicalComplex< TKSpace, TCellContainer >& );
 
 
  // template class CubicalComplex
  template < typename TKSpace,
             typename TCellContainer = typename TKSpace::template CellMap< CubicalCellData >::Type >
  class CubicalComplex
  {
    // ----------------------- associated types ------------------------------
  public:
    typedef CubicalComplex< TKSpace, TCellContainer > Self;
 
    BOOST_CONCEPT_ASSERT(( concepts::CCellularGridSpaceND< TKSpace > ));
    BOOST_STATIC_ASSERT( IsPairAssociativeContainer< TCellContainer >::value );
 
    // JOL: Not used, because unordered_set and unordered_map do not pass
    // these concept checks.
    // BOOST_CONCEPT_ASSERT(( boost::AssociativeContainer< TCellContainer > ));
    // BOOST_CONCEPT_ASSERT(( boost::PairAssociativeContainer< TCellContainer > ));
    BOOST_CONCEPT_ASSERT(( concepts::CSTLAssociativeContainer< TCellContainer > ));
 
    template < typename K, typename C > 
    friend CubicalComplex<K,C>&
    DGtal::operator|=( CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>&
    DGtal::operator&=( CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>&
    DGtal::operator^=( CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>&
    DGtal::operator-=( CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>
    DGtal::operator| ( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>
    DGtal::operator& ( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>
    DGtal::operator^ ( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>
    DGtal::operator- ( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>
    DGtal::operator~ ( const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend CubicalComplex<K,C>
    DGtal::operator* ( const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend bool
    DGtal::operator==( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend bool
    DGtal::operator!=( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend bool
    DGtal::operator<=( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
    template < typename K, typename C > 
    friend bool
    DGtal::operator>=( const CubicalComplex<K,C>&, const CubicalComplex<K,C>& );
 
    typedef TKSpace                             KSpace;        
    typedef TCellContainer                      CellContainer; 
    typedef typename CellContainer::mapped_type Data;          
 
    BOOST_STATIC_ASSERT (( boost::is_base_of< CubicalCellData, Data >::value ));
    BOOST_STATIC_ASSERT (( boost::is_same< typename TKSpace::Cell, typename CellContainer::key_type >::value ));
 
 
    static const Dimension dimension = KSpace::dimension;
    typedef typename KSpace::Integer     Integer;     
    typedef typename KSpace::Cell        Cell;        
    typedef typename Cell::PreCell       PreCell;     
    typedef typename KSpace::Cells       Cells;       
    typedef typename KSpace::Space       Space;       
    typedef typename KSpace::Size        Size;        
    typedef typename KSpace::Point       Point;       
    typedef typename KSpace::DirIterator DirIterator; 
    typedef CellContainer                CellMap;     
    typedef typename CellMap::const_iterator CellMapConstIterator; 
    typedef typename CellMap::iterator   CellMapIterator;          
 
 
    enum CellType {
      Maximal ,
      Free    ,
      Any     
    };
 
    BOOST_STATIC_CONSTANT( uint32_t, REMOVED     = 0x10000000 );
    BOOST_STATIC_CONSTANT( uint32_t, COLLAPSIBLE = 0x20000000 );
    BOOST_STATIC_CONSTANT( uint32_t, FIXED       = 0x40000000 );
    BOOST_STATIC_CONSTANT( uint32_t, USER1       = 0x80000000 );
    BOOST_STATIC_CONSTANT( uint32_t, VALUE       = 0x0fffffff );
 
    // ----------------------- inner types ------------------------------------
 
    struct DefaultCellMapIteratorPriority {
 
      bool operator()( const CellMapIterator& it1, const CellMapIterator& it2 ) const
      {
        uint32_t v1 = it1->second.data & VALUE;
        uint32_t v2 = it2->second.data & VALUE;
        return ( v1 < v2 )
          || ( ( v1 == v2 ) && ( it1->first < it2->first ) );
      }
    };
 
    struct ConstIterator
      : public boost::iterator_facade< ConstIterator, Cell const,
                                       std::forward_iterator_tag >
    {
      friend class CubicalComplex;
 
      typedef boost::iterator_facade< ConstIterator, Cell const,
                                      std::forward_iterator_tag > Base;
      typedef ConstIterator                  Self;
      typedef typename Base::value_type      Value;
      typedef typename Base::pointer         Pointer;
      typedef typename Base::reference       Reference;
      typedef typename Base::difference_type DifferenceType;
 
      ConstIterator() : myCC( 0 ), myD( 0 ) {}
 
      ConstIterator( ConstAlias<CubicalComplex> cc, Dimension d )
        : myCC( &cc ), myD( d )
      {
        if ( myD <= myCC->dimension )
          {
            myIt    = myCC->begin( myD );
            myItEnd = myCC->end( myD );
            nextDimension();
          }
        else
          {
            myD     = myCC->dimension + 1;
            myIt    = myCC->end( myCC->dimension );
            myItEnd = myCC->end( myCC->dimension );
          }
      }
 
      ConstIterator( ConstAlias<CubicalComplex> cc, Dimension d,
                     CellMapConstIterator it )
        : myCC( &cc ), myD( d ), myIt( it )
      {
        ASSERT( d <= myCC->dimension );
        myItEnd = myCC->end( d );
        nextDimension();
      }
 
    private:
      friend class boost::iterator_core_access;
 
      void nextDimension()
      {
        while ( myIt == myItEnd )
          {
            if ( ++myD > myCC->dimension ) break;
            myIt    = myCC->begin( myD );
            myItEnd = myCC->end( myD );
          }
      }
 
      void increment()
      {
        ASSERT( myCC != 0 );
        ++myIt;
        nextDimension();
      }
 
      bool equal( const ConstIterator& other ) const
      {
        return ( myD == other.myD ) && ( myIt == other.myIt );
      }
 
      Cell const& dereference() const
      {
        return myIt->first;
      }
 
      Dimension dimension() const
      {
        return myD;
      }
 
    private:
      const CubicalComplex* myCC;
      Dimension myD;
      CellMapConstIterator myIt;
      CellMapConstIterator myItEnd;
    };
 
    struct Iterator
      : public boost::iterator_facade< Iterator, Cell const,
                                       std::forward_iterator_tag >
    {
      friend class CubicalComplex;
 
      typedef boost::iterator_facade< Iterator, Cell const,
                                      std::forward_iterator_tag > Base;
      typedef Iterator                       Self;
      typedef typename Base::value_type      Value;
      typedef typename Base::pointer         Pointer;
      typedef typename Base::reference       Reference;
      typedef typename Base::difference_type DifferenceType;
 
      Iterator() : myCC( 0 ), myD( 0 ) {}
 
      Iterator( Alias<CubicalComplex> cc, Dimension d )
        : myCC( &cc ), myD( d )
      {
        if ( myD <= myCC->dimension )
          {
            myIt    = myCC->begin( myD );
            myItEnd = myCC->end( myD );
            nextDimension();
          }
        else
          {
            myD     = myCC->dimension + 1;
            myIt    = myCC->end( myCC->dimension );
            myItEnd = myCC->end( myCC->dimension );
          }
      }
 
      Iterator( Alias<CubicalComplex> cc, Dimension d,
                CellMapIterator it )
        : myCC( &cc ), myD( d ), myIt( it )
      {
        ASSERT( d <= myCC->dimension );
        myItEnd = myCC->end( d );
        nextDimension();
      }
 
    private:
      friend class boost::iterator_core_access;
 
      void nextDimension()
      {
        while ( myIt == myItEnd )
          {
            if ( ++myD > myCC->dimension ) break;
            myIt    = myCC->begin( myD );
            myItEnd = myCC->end( myD );
          }
      }
 
      void increment()
      {
        ASSERT( myCC != 0 );
        ++myIt;
        nextDimension();
      }
 
      bool equal( const Iterator& other ) const
      {
        return ( myD == other.myD ) && ( myIt == other.myIt );
      }
 
      Cell const& dereference() const
      {
        return myIt->first;
      }
 
      Dimension dimension() const
      {
        return myD;
      }
 
    private:
      CubicalComplex* myCC;
      Dimension myD;
      CellMapIterator myIt;
      CellMapIterator myItEnd;
    };
 
    // ----------------------- STL inner types ------------------------------
  public:
 
    // Renaming for STL-type of iterator.
    typedef ConstIterator                           const_iterator;
    typedef Iterator                                iterator;
    typedef Cell                                    value_type;
    typedef Cell const&                             reference;
    typedef Cell const&                             const_reference;
    typedef typename CellContainer::size_type       size_type;
    typedef typename CellContainer::difference_type difference_type;
    typedef Cell const*                             pointer;
    typedef Cell const*                             const_pointer;
 
    // ----------------------- Standard services ------------------------------
  public:
 
    ~CubicalComplex();
 
  protected:
    CubicalComplex();
  public:
 
    CubicalComplex ( ConstAlias<KSpace> aK );
 
    CubicalComplex ( const CubicalComplex & other );
 
    template < typename TDigitalSet >
    void construct ( const TDigitalSet & set );
 
    CubicalComplex & operator= ( const CubicalComplex & other );
 
    void clear();
 
    void clear( Dimension d );
 
    void fillData( Data data = Data() );
 
    void fillData( Dimension d, Data data = Data() );
 
    Dimension dim() const;
 
    Dimension dim( const Cell& aCell ) const;
 
    Size nbCells( Dimension d ) const;
 
    Integer euler() const;
 
    const KSpace& space() const;
 
    // ---------- cell container operations ---------------
  public:
 
    const CellMap & getCells(const Dimension d) const ;
 
    CellMap & getCells(const Dimension d) ;
 
    ConstIterator begin() const;
 
    ConstIterator end() const;
 
    Iterator begin();
 
    Iterator end();
 
    Size count( const Cell& aCell ) const;
 
    Size size() const;
 
    Size max_size() const;
 
    bool empty() const;
 
    std::pair< ConstIterator, ConstIterator > equal_range( const Cell& aCell ) const;
 
    std::pair< Iterator, Iterator > equal_range( const Cell& aCell );
 
    void erase( Iterator position );
 
    Size erase( const Cell& aCell );
 
    void erase( Iterator first, Iterator last );
 
    ConstIterator find( const Cell& aCell ) const;
 
    Iterator find( const Cell& aCell );
 
    std::pair< Iterator, bool > insert( const Cell& aCell );
 
    Iterator insert( Iterator position, const Cell& aCell );
 
    template <class InputIterator>
    void insert( InputIterator first, InputIterator last );
 
    void swap( CubicalComplex& other );
 
    // ---------- enhanced container operations ---------------
  public:
 
    Data& operator[]( const Cell& aCell );
 
    bool operator()( const Cell& aCell ) const;
 
    void insertCell( const Cell& aCell, const Data& data = Data() );
 
    void insertCell( Dimension d, const Cell& aCell, const Data& data = Data() );
 
    template <typename CellConstIterator>
    void insertCells( CellConstIterator it, CellConstIterator itE, const Data& data = Data() );
 
    template <typename CellConstIterator>
    void insertCells( Dimension d, CellConstIterator it, CellConstIterator itE, const Data& data = Data() );
 
    bool belongs( const Cell& aCell ) const;
    bool belongs( const PreCell& aCell ) const;
 
    bool belongs( Dimension d, const Cell& aCell ) const;
    bool belongs( Dimension d, const PreCell& aCell ) const;
 
    Size eraseCell( const Cell& aCell );
 
    Size eraseCell( Dimension d, const Cell& aCell );
 
    void eraseCell( CellMapIterator it );
 
    void eraseCells( CellMapIterator it, CellMapIterator itE );
 
    template <typename CellConstIterator>
    Size eraseCells( CellConstIterator it, CellConstIterator itE );
 
    template <typename CellConstIterator>
    Size eraseCells( Dimension d, CellConstIterator it, CellConstIterator itE );
 
    template <typename CellOutputIterator>
    void faces( CellOutputIterator& outIt, const Cell& aCell,
                bool hintClosed = false ) const;
 
    template <typename CellOutputIterator>
    void directFaces( CellOutputIterator& outIt, const Cell& aCell,
                      bool hintClosed = false ) const;
 
    template <typename CellMapIteratorOutputIterator>
    void directFacesIterators( CellMapIteratorOutputIterator& outIt, const Cell& aCell );
 
    template <typename CellOutputIterator>
    void coFaces( CellOutputIterator& outIt, const Cell& aCell,
                  bool hintOpen = false ) const;
 
    template <typename CellOutputIterator>
    void directCoFaces( CellOutputIterator& outIt, const Cell& aCell,
                        bool hintOpen = false ) const;
 
    template <typename CellMapIteratorOutputIterator>
    void directCoFacesIterators( CellMapIteratorOutputIterator& outIt, const Cell& aCell );
 
    CellMapConstIterator begin( Dimension d ) const;
 
    CellMapConstIterator end( Dimension d ) const;
 
    CellMapIterator begin( Dimension d );
 
    CellMapIterator end( Dimension d );
 
    CellMapConstIterator findCell( const Cell& aCell ) const;
 
    CellMapConstIterator findCell( Dimension d, const Cell& aCell ) const;
 
    CellMapIterator findCell( const Cell& aCell );
 
    CellMapIterator findCell( Dimension d, const Cell& aCell );
 
    // ---------- local operations for extracting specific subcomplexes -------------
  public:
 
    Cells cellBoundary( const Cell& aCell, bool hintClosed = false ) const;
 
    Cells cellCoBoundary( const Cell& aCell, bool hintOpen = false ) const;
 
 
    // ---------------------- local properties --------------------------------------
  public:
    bool isCellInterior( const Cell& aCell ) const;
 
    bool isCellBoundary( const Cell& aCell ) const;
 
    CellType computeCellType( const Cell& c, CellMapIterator& it_cell_up,
                              Dimension n = dimension );
 
 
    // ----------------------- Standard subcomplexes --------------------------------
  public:
 
    CubicalComplex interior() const;
 
    CubicalComplex boundary( bool hintClosed = false ) const;
 
    void getInteriorAndBoundary( CubicalComplex& intcc,
                                 CubicalComplex& bdcc,
                                 bool hintClosed = false ) const;
 
    CubicalComplex closure( const CubicalComplex& S, bool hintClosed = false ) const;
 
    CubicalComplex star( const CubicalComplex& S, bool hintOpen = false ) const;
 
    CubicalComplex link( const CubicalComplex& S, bool hintClosed = false, bool hintOpen = false ) const;
 
    // ----------------------- global operations on complexes -----------------------
  public:
 
    void close();
 
    void close( Dimension k );
 
    void open();
 
    void open( Dimension k );
 
 
    // ----------------------- Interface --------------------------------------
  public:
 
    void selfDisplay ( std::ostream & out ) const;
 
    bool isValid() const;
 
    // --------------- CDrawableWithBoard2D realization ------------------
  public:
    std::string className() const;
 
    // ------------------------- Protected Datas ------------------------------
  protected:
 
    const KSpace* myKSpace;
 
    std::vector<CellMap> myCells;
 
 
    // ------------------------- Hidden services ------------------------------
  protected:
 
 
  private:
 
 
    // ------------------------- Internals ------------------------------------
  private:
 
 
  }; // end of class CubicalComplex
 
  template < typename TKSpace,
             typename TCellContainer >
  struct ContainerTraits< CubicalComplex< TKSpace, TCellContainer > >
  {
    //typedef typename ContainerTraits< TCellContainer >::Category Category;
    typedef SequenceCategory Category;
  };
 
 
  template <typename TKSpace, typename TCellContainer>
  std::ostream&
  operator<< ( std::ostream & out,
               const CubicalComplex<TKSpace, TCellContainer> & object );
 
} // namespace DGtal
 
 
// Includes inline functions.
#include "DGtal/topology/CubicalComplex.ih"
 
//                                                                           //
 
#endif // !defined CubicalComplex_h
 
#undef CubicalComplex_RECURSES
#endif // else defined(CubicalComplex_RECURSES)