SegmentComputerUtils.h

#pragma once

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

#define SegmentComputerUtils_RECURSES

#if !defined SegmentComputerUtils_h

#define SegmentComputerUtils_h


#include "DGtal/base/Circulator.h"

namespace DGtal
{

// Categories
   struct ForwardSegmentComputer{}; 
   struct BidirectionalSegmentComputer{}; 
   struct DynamicSegmentComputer{}; 
   struct DynamicBidirectionalSegmentComputer{}; 



//default
template <typename SC>
struct SegmentComputerTraits {
    typedef  ForwardSegmentComputer Category;
//    typedef DynamicBidirectionalSegmentComputer Category; 
//    typedef BidirectionalSegmentComputer Category;   
};



// Useful functions for segment computers


template<typename IC>
IC getMiddleIterator(const IC& itb, const IC& ite, RandomAccessCategory)
{
//how to compute this with circulators ?
//return itb + ((ite-itb)/2);  
//does not work  
  return getMiddleIterator(itb, ite, BidirectionalCategory() ); 
}

template<typename IC>
IC getMiddleIterator(const IC& itb, const IC& ite, BidirectionalCategory)
{
  IC b( itb ); 
  IC f( ite ); 
  bool flag = true; 
  while (b != f) {
    if (flag) {
      --f;
      flag = false; 
    } else {
      ++b; 
      flag = true; 
    } 
  }
  return b;   
}

template<typename IC>
IC getMiddleIterator(const IC& itb, const IC& ite, ForwardCategory)
{
  IC i( itb ); 

  unsigned int c = 0; 
  while (i != ite) {
    ++i; 
    ++c;
  } 
  unsigned int k = c/2;

  c = 0; 
  i = itb; 
  while (c != k) {
    ++i; 
    ++c;
  } 

  return i;   
}
template<typename IC>
IC getMiddleIterator(const IC& itb, const IC& ite) {
  typedef typename IteratorCirculatorTraits<IC>::Category Category; 
  return getMiddleIterator(itb, ite, Category() ); 
} 



template <typename SC>
void maximalExtension(SC& s, const typename SC::ConstIterator& end, IteratorType ) {
  //stop if s.end() == end
  while ( (s.end() != end)
       && (s.extendForward()) ) {}
}

template <typename SC>
void maximalExtension(SC& s, const typename SC::ConstIterator& /*end*/, CirculatorType ) 
{
  //stop if the segment is the whole range
  const typename SC::ConstIterator newEnd( s.begin() ); 
  while ( (s.extendForward())
    && (s.end() != newEnd) ) {}
}
template <typename SC>
void maximalExtension(SC& s, const typename SC::ConstIterator& end) {
  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type; 
  maximalExtension( s, end, Type() ); 
}


template <typename SC>
void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin, IteratorType ) {
  //extend one more time if s.begin() == begin
  while ( (s.begin() != begin)
       && (s.extendBackward()) ) {}
  if (s.begin() == begin) s.extendBackward();
}

template <typename SC>
void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin, CirculatorType ) {
  //stop if the segment is the whole range
  const typename SC::ConstIterator newBegin( s.end() ); 
  while ( (s.extendBackward())
       && (s.begin() != newBegin) ) {}
}

template <typename SC>
void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin) {
  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type; 
  oppositeEndMaximalExtension( s, begin, Type() ); 
}



template <typename SC>
bool maximalSymmetricExtension(SC& s, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  IteratorType ) {

  bool flagOk = true; 
  bool flagForward = true; 
  //while the extension is possible 
  //at the front and (then) at the back
  while (flagOk)  {
    if (flagForward) {
      flagForward = false; 
      if ( s.end() != end ) flagOk = s.extendForward();
      else flagOk = false; 
    } else {
      flagForward = true; 
      if ( s.begin() != begin ) flagOk = s.extendBackward();
      else flagOk = false; 
    } 
  }
  //extend one more time if s.begin() == begin
  if (s.begin() != begin ) {
    if (s.extendBackward()) return !s.extendForward(); 
    else return false; 
  } else {
    return !flagForward; 
  }

}

template <typename SC>
bool maximalSymmetricExtension(SC& s, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  CirculatorType ) {

  bool flagOk = true; 
  bool flagForward = true; 
  //while the extensions are possible and
  //the segment does not correspond to the whole range
  while ( (flagOk) && ( s.end() != s.begin() ) )  {
    if (flagForward) {
      flagForward = false; 
      flagOk = s.extendForward(); 
    } else {
      flagForward = true; 
      flagOk = s.extendBackward(); 
    } 
  }
  return !flagForward; 
}

template <typename SC>
bool maximalSymmetricExtension(SC& s, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end) {

  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type; 
  return maximalSymmetricExtension( s, begin, end, Type() ); 

}


template <typename SC>
void maximalRetraction(SC& s, const typename SC::ConstIterator& end) 
{
  if ( isNotEmpty<typename SC::ConstIterator>(s.end(),end) ) {
    while ( (! s.isExtendableForward() ) 
          &&(s.retractForward() ) )  {}  
  } else {
    while ( s.retractForward() ) {} 
  }
}

template <typename SC>
void oppositeEndMaximalRetraction(SC& s, const typename SC::ConstIterator& begin) 
{
  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) ) {
    while ( (! s.isExtendableBackward() ) 
          &&(s.retractBackward() ) ) {}  
  } else {
    while ( s.retractBackward() ) {} 
  }
}



template <typename SC>
void longestSegment(SC& s, 
                   const typename SC::ConstIterator& i,
                   const typename SC::ConstIterator& end, 
                   IteratorType )
 {
  if (i != end) {
    s.init(i);
    maximalExtension(s, end, IteratorType() );
  }
}

template <typename SC>
void longestSegment(SC& s, 
                   const typename SC::ConstIterator& i, 
                   const typename SC::ConstIterator& end,
                   CirculatorType ) 
{
  s.init(i);
  maximalExtension(s, end, CirculatorType() );
}

template <typename SC>
void longestSegment(SC& s, 
                   const typename SC::ConstIterator& i, 
                   const typename SC::ConstIterator& end) 
{
  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type; 
  longestSegment( s, i, end, Type() ); 
}



template <typename SC>
void firstMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::ForwardSegmentComputer ) 
{

  typedef typename SC::ConstIterator ConstIterator; 
  typedef typename SC::Reverse ReverseSegmentComputer; 
  typedef typename ReverseSegmentComputer::ConstIterator ConstReverseIterator; 

  if ( isNotEmpty<ConstIterator>(i,end) ) {

    //backward extension
    ConstIterator it( i ); ++it; 
    ConstReverseIterator rit( it );
    ConstReverseIterator rend( begin );
    ReverseSegmentComputer r( s.getReverse() ); 
    longestSegment(r, rit, rend);

    //forward extension
    ConstIterator it2( r.end().base() );
    longestSegment(s, it2, end);

  }

}

template <typename SC>
void firstMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::BidirectionalSegmentComputer) 
{
  s.init(i);

  oppositeEndMaximalExtension(s, begin);
  maximalExtension(s, end);
}

template <typename SC>
void firstMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicSegmentComputer) 
{
  firstMaximalSegment(s,i,begin,end,DGtal::ForwardSegmentComputer() );
}

template <typename SC>
void firstMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicBidirectionalSegmentComputer) 
{
  firstMaximalSegment(s,i,begin,end,DGtal::BidirectionalSegmentComputer() );
}

template <typename SC>
void firstMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end ) 
{
  firstMaximalSegment<SC>(s, i, begin, end, 
typename DGtal::SegmentComputerTraits<SC>::Category() );
}


template <typename SC>
void mostCenteredMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::ForwardSegmentComputer ) 
{

  typedef typename SC::ConstIterator ConstIterator; 
  typedef typename SC::Reverse ReverseSegmentComputer; 
  typedef typename ReverseSegmentComputer::ConstIterator ConstReverseIterator; 

 //get the first maximal segment passing through i

  firstMaximalSegment( s, i, begin, end, DGtal::ForwardSegmentComputer() );

 //get the next maximal segment while i is not at the middle of 
 //the current maximal segment. 

  ConstIterator k( s.begin() ); 
  while ( k != i ) {

    if ( isNotEmpty<ConstIterator>(s.end(),end) ) {

      //backward extension
      ConstIterator it( s.end() ); ++it; 
      ConstReverseIterator rit( it );
      ConstReverseIterator rend( s.begin() );
      ReverseSegmentComputer r( s.getReverse() ); 
      longestSegment(r, rit, rend);
      ConstIterator newBegin = r.end().base(); 
      ASSERT( newBegin != s.begin() );

      while ( ( k != getMiddleIterator(newBegin, s.end() ) )
            &&( k != i ) ) {
        ++k; 
      }
      if ( k != i ) {
   
        //get the next maximal segment
        longestSegment(s, newBegin, end);  

      }

    } else {
      k = i; 
    }
  }
}

template <typename SC>
void mostCenteredMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::BidirectionalSegmentComputer) 
{
  
  if ( (isNotEmpty(i,end)) || (isNotEmpty(i,begin)) ) { 

    s.init(i);

    //symmetric extension
    if ( (isNotEmpty(i,end)) && (isNotEmpty(i,begin)) ) { 
      maximalSymmetricExtension(s, begin, end); 
    }

  //forward extension
  maximalExtension(s, end);
      
  //backward extension
  oppositeEndMaximalExtension(s, begin);

  }

}

template <typename SC>
void mostCenteredMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicSegmentComputer) 
{
  mostCenteredMaximalSegment(s,i,begin,end,DGtal::ForwardSegmentComputer() );
}

template <typename SC>
void mostCenteredMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicBidirectionalSegmentComputer) 
{
  mostCenteredMaximalSegment(s,i,begin,end,DGtal::BidirectionalSegmentComputer() );
}

template <typename SC>
void mostCenteredMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end ) 
{
   mostCenteredMaximalSegment<SC>(s, i, begin, end, 
typename DGtal::SegmentComputerTraits<SC>::Category() );
}


template <typename SC>
void lastMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::ForwardSegmentComputer ) 
{

  typedef typename SC::ConstIterator ConstIterator; 
  typedef typename SC::Reverse ReverseSegmentComputer; 
  typedef typename ReverseSegmentComputer::ConstIterator ConstReverseIterator; 

  //forward extension
  ConstIterator j( i );
  longestSegment(s, j, end);

  //backward extension
  ConstIterator it( s.end() );
  ConstReverseIterator rit( it );
  ConstReverseIterator rend( begin );
  ReverseSegmentComputer r( s.getReverse() ); 
  longestSegment(r, rit, rend);

  //forward extension
  ConstIterator it2( r.end().base() );
  longestSegment(s, it2, end);
}

template <typename SC>
void lastMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  BidirectionalSegmentComputer) 
{
  s.init(i);

  maximalExtension(s, end);
  oppositeEndMaximalExtension(s, begin);
}

template <typename SC>
void lastMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicSegmentComputer) 
{
  lastMaximalSegment(s,i,begin,end,DGtal::ForwardSegmentComputer() );
}

template <typename SC>
void lastMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicBidirectionalSegmentComputer) 
{
  lastMaximalSegment(s,i,begin,end,DGtal::BidirectionalSegmentComputer() );
}

template <typename SC>
void lastMaximalSegment(SC& s, 
  const typename SC::ConstIterator& i, 
  const typename SC::ConstIterator& begin, 
  const typename SC::ConstIterator& end ) 
{
   lastMaximalSegment<SC>(s, i, begin, end, 
typename DGtal::SegmentComputerTraits<SC>::Category() );
}


template <typename SC>
void nextMaximalSegment(SC& s, 
  const typename SC::ConstIterator& end, 
  DGtal::ForwardSegmentComputer ) 
{
  firstMaximalSegment(s, s.end(), s.begin(), end, ForwardSegmentComputer() );
}

template <typename SC>
void nextMaximalSegment(SC& s, 
  const typename SC::ConstIterator& end, 
  DGtal::BidirectionalSegmentComputer) 
{
  firstMaximalSegment(s, s.end(), s.begin(), end, DGtal::BidirectionalSegmentComputer() );
}

template <typename SC>
void nextMaximalSegment(SC& s, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicSegmentComputer) 
{
  typedef typename SC::ConstIterator ConstIterator; 

  //rectract
  maximalRetraction(s, end); 

  //intersection test
  ConstIterator i( s.begin() ); ++i; 
  //if the intersection between the two 
  // consecutive maximal segments is empty 
  if ( i == s.end() ) {
    if ( isNotEmpty<ConstIterator>(i, end) ) {
      ++i; 
      s.init(i);  
    }
  }

  //extend
  maximalExtension(s, end);
}

template <typename SC>
void nextMaximalSegment(SC& s, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicBidirectionalSegmentComputer) 
{ 
  nextMaximalSegment(s, end, DGtal::DynamicSegmentComputer() ); 
}

template <typename SC>
void nextMaximalSegment(SC& s, 
  const typename SC::ConstIterator& end ) 
{
   nextMaximalSegment<SC>(s, end, 
typename DGtal::SegmentComputerTraits<SC>::Category() );
}


template <typename SC>
void previousMaximalSegment(SC& s, 
  const typename SC::ConstIterator& begin, 
  DGtal::ForwardSegmentComputer ) 
{
  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) )
    lastMaximalSegment(s, --s.begin(), begin, s.end(), DGtal::ForwardSegmentComputer() );
}

template <typename SC>
void previousMaximalSegment(SC& s, 
  const typename SC::ConstIterator& begin, 
  DGtal::BidirectionalSegmentComputer) 
{
  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) )
    lastMaximalSegment(s, --s.begin(), begin, s.end(), DGtal::BidirectionalSegmentComputer() );
}

template <typename SC>
void previousMaximalSegment(SC& s, 
  const typename SC::ConstIterator& begin, 
  DGtal::DynamicSegmentComputer) 
{

  typedef typename SC::ConstIterator ConstIterator; 

  //rectract
  oppositeEndMaximalRetraction(s, begin); 

  //intersection test
  ConstIterator i( s.end() ); --i; 
  //if the intersection between the two 
  // consecutive maximal segments is empty 
  if ( i == s.begin() ) {
    if ( isNotEmpty<ConstIterator>(i, begin) ) {
      --i; 
      s.init(i);  
    }
  }

  //extend
  oppositeEndMaximalExtension(s, begin);

}

template <typename SC>
void previousMaximalSegment(SC& s, 
  const typename SC::ConstIterator& end, 
  DGtal::DynamicBidirectionalSegmentComputer) 
{ 
  previousMaximalSegment(s, end, DGtal::DynamicSegmentComputer() ); 
}

template <typename SC>
void previousMaximalSegment(SC& s, 
  const typename SC::ConstIterator& begin ) 
{
  previousMaximalSegment(s, begin, 
typename DGtal::SegmentComputerTraits<SC>::Category() );
}

} // namespace DGtal



//                                                                           //

#endif // !defined SegmentComputerUtils_h

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