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.extendFront()) ) {}
}
 
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.extendFront())
    && (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.extendBack()) ) {}
  if (s.begin() == begin) s.extendBack();
}
 
template <typename SC>
void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin, CirculatorType )
{
  boost::ignore_unused_variable_warning( begin );
  //stop if the segment is the whole range
  const typename SC::ConstIterator newBegin( s.end() ); 
  while ( (s.extendBack())
       && (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.extendFront();
      else flagOk = false; 
    } else {
      flagForward = true; 
      if ( s.begin() != begin ) flagOk = s.extendBack();
      else flagOk = false; 
    } 
  }
  //extend one more time if s.begin() == begin
  if (s.begin() != begin ) {
    if (s.extendBack()) return !s.extendFront(); 
    else return false; 
  } else {
    return !flagForward; 
  }
 
}
 
template <typename SC>
bool maximalSymmetricExtension(SC& s, 
                               const typename SC::ConstIterator& begin, 
                               const typename SC::ConstIterator& end, 
                               CirculatorType )
{
  boost::ignore_unused_variable_warning( begin );
  boost::ignore_unused_variable_warning( end );
 
  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.extendFront(); 
    } else {
      flagForward = true; 
      flagOk = s.extendBack(); 
    } 
  }
  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.isExtendableFront() ) 
          &&(s.retractBack() ) )  {}  
  } else {
    while ( s.retractBack() ) {} 
  }
}
 
template <typename SC>
void oppositeEndMaximalRetraction(SC& s, const typename SC::ConstIterator& begin) 
{
  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) ) {
    while ( (! s.isExtendableBack() ) 
          &&(s.retractFront() ) ) {}  
  } else {
    while ( s.retractFront() ) {} 
  }
}
 
 
 
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)