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;
  
  namespace functions {
    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 >& );
  } // namespace functions


  // 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 > ));

    friend Self& DGtal::functions::operator|=<>( Self&, const Self& );
    friend Self& DGtal::functions::operator&=<>( Self&, const Self& );
    friend Self& DGtal::functions::operator^=<>( Self&, const Self& );
    friend Self& DGtal::functions::operator-=<>( Self&, const Self& );
    friend Self  DGtal::functions::operator| <>( const Self&, const Self& );
    friend Self  DGtal::functions::operator& <>( const Self&, const Self& );
    friend Self  DGtal::functions::operator^ <>( const Self&, const Self& );
    friend Self  DGtal::functions::operator- <>( const Self&, const Self& );
    friend Self  DGtal::functions::operator~ <>( const Self& );
    friend Self  DGtal::functions::operator* <>( const Self& );
    friend bool  DGtal::functions::operator==<>( const Self&, const Self& );
    friend bool  DGtal::functions::operator!=<>( const Self&, const Self& );
    friend bool  DGtal::functions::operator<=<>( const Self&, const Self& );
    friend bool  DGtal::functions::operator>=<>( const Self&, const Self& );

    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 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:

    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( Dimension d, const Cell& 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;

    // ------------------------- Private Datas --------------------------------
  private:

    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)