#ifndef __S34_LIST_SORT_H_
#define __S34_LIST_SORT_H_


namespace stx{


template <class BidirectionalIterator>
void comb_sort(BidirectionalIterator first,
          BidirectionalIterator last) 
{
  int gap = static_cast<int>(std::distance(first, last));
  if ( gap < 1 ) {
      return;
  }
  BidirectionalIterator first2 = last;
  bool swapped = false;
  do {
    int newgap = (gap*10+3)/13;
    if ( newgap < 1 ) newgap = 1;
    std::advance(first2, newgap-gap);
    gap = newgap;
    swapped = false;
    for ( BidirectionalIterator target1 = first, target2 = first2;
          target2 != last;
          ++target1, ++target2) {
      if ( *target2 < *target1 ) {
        std::iter_swap(target1, target2);
        swapped = true;
      }
    }
  } while ( (gap > 1) || swapped );
}

template <class BidirectionalIterator, class Predicate>
void comb_sort(BidirectionalIterator first,
          BidirectionalIterator last,
          Predicate pr) 
{
  int gap = static_cast<int>(std::distance(first, last));
  if ( gap < 1 ) {
      return;
  }
  BidirectionalIterator first2 = last;
  bool swapped = false;
  do {
    int newgap = (gap*10+3)/13;
    if ( newgap < 1 ) newgap = 1;
    std::advance(first2, newgap - gap);
    gap = newgap;
    swapped = false;
    for ( BidirectionalIterator target1 = first, target2 = first2;
          target2 != last;
          ++target1, ++target2) {
      if ( pr(*target2, *target1) ) {
        std::iter_swap(target1, target2);
        swapped = true;
      }
    }
  } while ( (gap > 1) || swapped );
}


}//end of stx namespace

#endif
