CombinatorialDSS.h

#pragma once

#if defined(CombinatorialDSS_RECURSES)
#error Recursive header files inclusion detected in CombinatorialDSS.h
#else // defined(CombinatorialDSS_RECURSES)

#define CombinatorialDSS_RECURSES

#if !defined CombinatorialDSS_h

#define CombinatorialDSS_h

// Inclusions
#include <iostream>
#include "DGtal/base/Common.h"
#include "DGtal/geometry/curves/FreemanChain.h"
#include "DGtal/base/OrderedAlphabet.h"

namespace DGtal
{



  // template class CombinatorialDSS
  template <typename TConstIterator, typename TInteger>
    class CombinatorialDSS  
  {

    // ----------------------- Types ------------------------------
    public :
      //Required type
      BOOST_CONCEPT_ASSERT(( CInteger<TInteger> ) );
      typedef TConstIterator ConstIterator;
      typedef TInteger Integer;

      //Required types
      typedef FreemanChain<TInteger> FreemanChainCode;
      typedef CombinatorialDSS<ConstIterator, Integer> Self;
      typedef CombinatorialDSS<ConstIterator, Integer> Reverse;

      //2D points and 2D vectors
      typedef DGtal::PointVector<2,Integer> Point;
      typedef DGtal::PointVector<2,Integer> Vector;


      typedef typename iterator_traits<ConstIterator>::value_type Code;
      typedef int Size;
      typedef int Index;

      //The basic steps associate to the codes are given by a function `f: Code -> Vector` 
      typedef Vector (*DisplacementFct) (Code);


    private :
      template < class TIterator, class iterator_type = typename iterator_traits<TIterator>::iterator_category >
      class CodeHandler
        {
        public :
          CodeHandler()
            { }
          void init( const TIterator & it ) 
            { 
              myIter = it;
            }

          Code getCode( Index n ) const
            {
              return myCodes[ n ];
            }

          Code getCode( Index n )
            {
              while ( n >= myCodes.size() )
                {
                  myCodes.push_back( *myIter );
                  ++myIter;
                }
              return myCodes[ n ];
            }

        private :
          vector<Code> myCodes;
          TIterator myIter;
        };

      template < class TIterator >
      class CodeHandler< TIterator, bidirectional_iterator_tag > 
        {
        public :
          CodeHandler()
            {
            }
          void init( const TIterator & it ) 
            { 
              myFirst = it;
              myLast = it;
            }

          Code getCode( Index n ) const
            {
              return ( n >= 0 ) ? myPosCodes[ n ] : myNegCodes[ 1-n ];
            }

          Code getCode( Index n )
            {
              Code c;
              if ( n<0 )
                {
                  unsigned int i = 1-n;
                  while ( i >= myNegCodes.size() )
                    {
                      --myFirst;
                      myNegCodes.push_back( *myFirst );
                    }
                  c = myNegCodes[ n ];
                }
              else
                {
                  unsigned int i = n;
                  while ( i >= myPosCodes.size() )
                    {
                      myPosCodes.push_back( *myLast );
                      ++myLast;
                    }
                  c =  myPosCodes[ n ];
                }
              return c;
            }

        private :
          vector<Code> myPosCodes;
          vector<Code> myNegCodes;
          TIterator myFirst;
          TIterator myLast;
        };

      template < class TIterator>
        class CodeHandler<TIterator, random_access_iterator_tag >
          {
          public :
            CodeHandler()
              { }

            void init ( const TIterator & it ) 
            { 
              myIter = it;
            }

            Code getCode( Index n ) const
              {
                return myIter[ n ];
              }

            Code getCode ( Index n )
              {
                return myIter[ n ];
              }

          private :
            TIterator myIter;
          };


    public :

      struct ConstPointIterator
        {

          typedef bidirectional_iterator_tag iterator_category;
          typedef Point value_type;
          typedef Index difference_type;
          typedef Point * pointer;
          typedef Point & reference;

          const CombinatorialDSS * myDSS;
          Index i;
          Point p;

          ConstPointIterator( )
          {}

          ConstPointIterator( const CombinatorialDSS * dss, Index ind, Point pt ) :
            myDSS(dss), i(ind), p(pt) 
          {}

          ~ConstPointIterator() {}
            
          bool operator==( const ConstPointIterator other) const
            {
              return i == other.i;
            }
          bool operator!=( const ConstPointIterator other) const
            {
              return i != other.i;
            }

          Index operator-( const ConstPointIterator other) const
            {
              return i - other.i;
            }


          ConstPointIterator& operator=( const ConstPointIterator & other)
            {
              i = other.i;
              myDSS = other.myDSS;
              p = other.p;
              return *this;
            }

          Point operator*() const
            {
              return p;
            }

          // pre-increment ++i
          ConstPointIterator& operator++()
            {
              next();
              return *this;
            }

          // post-increment
          ConstPointIterator operator++( int )
            {
              ConstPointIterator it = *this;
              next();
              return it;
            }


          // pre-decrement --i
          ConstPointIterator& operator--()
            {
              prev();
              return *this;
            }

          // post-decrement
          ConstPointIterator operator--( int )
            {
              ConstPointIterator it = *this;
              prev();
              return it;
            }

          // Move to next position
          void next()
            {
              p += myDSS->myDisplacements( myDSS->getCode( i ) );
              ++i;
            }

          // Move to previous position
          void prev()
            {
              --i;
              p -= myDSS->myDisplacements( myDSS->getCode( i ) );
            }


          // Get a reference to the current Combinatorial DSS
          const CombinatorialDSS * getDSS() const
            {
              return myDSS;
            }


          // Get the index of the iterator
          Index getIndex() const
            {
              return i;
            }

        };




    // ----------------------- Standard services ------------------------------
    public:

      CombinatorialDSS();

      ~CombinatorialDSS();


      void init( const ConstIterator & it, 
                const Point & start = Point(0,0),
                Vector (*displacements) (Code) = defaultMoves );



      void init(const ConstPointIterator & i);

      void init(const FreemanChainCode & fc);

      void init(const typename FreemanChainCode::ConstIterator & it);

      // * Initialize from an array of codes.
      // * @param a pointer to an array of codes.
      // * @param the length of the code array.
      // * @param the start position in 'theCode'.
      // * @param the position of the starting point of the first code.
      // * @param a function that returns the displacement vector of the codes.
      // */
      //void init(const Code * theCode, Size codeLength, Index firstLetter, const
      //          Point & startPoint, Vector (*displacement) (Code) );

      CombinatorialDSS ( const Self & other );

      CombinatorialDSS & operator= ( const Self & other );

      Self getSelf( ) const;



      bool operator==( const Self & other ) const;

      bool operator!=( const Self & other ) const;


      Reverse getReverse() const;


      bool isExtendableForward();

      bool extendForward();

      bool extendBackward();

      bool isExtendableBackward();

      bool retractForward();

      bool retractBackward();

      void setPosition( const Point & p );


      void translate( const Vector & v );

      void getArithmeticalDescription( Integer &a, Integer &b, Integer
          &mu, Integer &omega) const;

      Integer getA() const;

      Integer getB() const;

      Integer getMu() const;

      Integer getOmega() const;


      Integer getRemainder(const Point & aPoint) const;

      void computeLeaningPoints( Point & uf, Point & ul, 
                                 Point & lf, Point & ll ) const;


      Point getUf() const;

      Point getUl() const;

      Point getLf() const;

      Point getLl() const;

      bool isValid() const;

      bool longestChristoffelPrefix(
          ConstIterator it,
          const OrderedAlphabet & aOA);

      
      // ----------------------- Accessors --------------------------------------
      
    public:

      Point getFirstPoint() const;

      Point getLastPoint() const;

      ConstPointIterator pointBegin() const;

      ConstPointIterator pointEnd() const;

      ConstIterator begin() const;

      ConstIterator end() const;






      // ----------------------- Interface --------------------------------------
    public:

      void selfDisplay ( std::ostream & out ) const;


    protected:
      // ------------------------- Protected Datas ------------------------------
      
      //const FreemanChainCode * myFC;

      CodeHandler<ConstIterator> myCodeHandler;

      ConstIterator myBegin;
      ConstIterator myEnd;

      Point myFirstPoint;
      Point myLastPoint;

      Index myFirstLetter;
      Index myLastLetter;


      unsigned int myNbRepeat;

      Index myPatternBegin;
      Index myPatternEnd;

      Size myLeftPatternLength;

      Index myNextBefore;
      Index myNextAfter;


      Vector (*myDisplacements) ( Code ) ;



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

      // ------------------------- Hidden services ------------------------------
    public:


      Code getSmallLetter() const;

      Code getBigLetter() const;

      Code getCode(Index pos);

      Code getCode(Index pos) const;

      Size mainPatternLength() const;

      Vector mainPatternVector() const;

      Size suffixLength() const;

      Size prefixLength() const;

      bool isUL ( Index pos ) const;

      bool nextIsLL ( Index pos ) const;

      bool previousIsLL ( Index pos ) const;

      bool isTrivial() const;

      Vector displacement( Code c ) const;



    
    private:
      // ------------------------- Internals ------------------------------------
    public :

      static Vector defaultMoves( Code c )
        {
          Integer x = ( c == '0' ) ? 1 : ( ( c == '2' ) ? -1 : 0 ) ;
          Integer y = ( c == '1' ) ? 1 : ( ( c == '3' ) ? -1 : 0 ) ;
          return Vector( x, y );
        }



  }; // end of class CombinatorialDSS


  template <typename T1, typename T2>
  std::ostream&
  operator<< ( std::ostream & out, const CombinatorialDSS<T1,T2> & object );



} // namespace DGtal


// Includes inline functions.
#include "DGtal/geometry/curves/CombinatorialDSS.ih"
//                                                                           //

#endif // !defined CombinatorialDSS_h

#undef CombinatorialDSS_RECURSES
#endif // else defined(CombinatorialDSS_RECURSES)