Bidirectional iterator support for radixSort() (#362)
authorBalazs Dezso <deba@inf.elte.hu>
Fri, 19 Mar 2010 18:23:47 +0100
changeset 1042d450a02728d0
parent 1041 0b0327c9b3ef
child 1043 1bafdbd2fc46
Bidirectional iterator support for radixSort() (#362)
lemon/radix_sort.h
     1.1 --- a/lemon/radix_sort.h	Fri Mar 01 18:20:07 2013 +0100
     1.2 +++ b/lemon/radix_sort.h	Fri Mar 19 18:23:47 2010 +0100
     1.3 @@ -34,6 +34,12 @@
     1.4  
     1.5    namespace _radix_sort_bits {
     1.6  
     1.7 +    template <typename Iterator>
     1.8 +    bool unitRange(Iterator first, Iterator last) {
     1.9 +      ++first;
    1.10 +      return first == last;
    1.11 +    }
    1.12 +
    1.13      template <typename Value>
    1.14      struct Identity {
    1.15        const Value& operator()(const Value& val) {
    1.16 @@ -60,9 +66,6 @@
    1.17        }
    1.18        std::iter_swap(first, last);
    1.19        ++first;
    1.20 -      if (!(first < last)) {
    1.21 -        return first;
    1.22 -      }
    1.23        while (true) {
    1.24          while (!(functor(*first) & mask)) {
    1.25            ++first;
    1.26 @@ -71,7 +74,7 @@
    1.27          while (functor(*last) & mask) {
    1.28            --last;
    1.29          }
    1.30 -        if (!(first < last)) {
    1.31 +        if (unitRange(last, first)) {
    1.32            return first;
    1.33          }
    1.34          std::iter_swap(first, last);
    1.35 @@ -97,9 +100,6 @@
    1.36        }
    1.37        std::iter_swap(first, last);
    1.38        ++first;
    1.39 -      if (!(first < last)) {
    1.40 -        return first;
    1.41 -      }
    1.42        while (true) {
    1.43          while (functor(*first) < 0) {
    1.44            ++first;
    1.45 @@ -108,7 +108,7 @@
    1.46          while (functor(*last) >= 0) {
    1.47            --last;
    1.48          }
    1.49 -        if (!(first < last)) {
    1.50 +        if (unitRange(last, first)) {
    1.51            return first;
    1.52          }
    1.53          std::iter_swap(first, last);
    1.54 @@ -119,7 +119,7 @@
    1.55      template <typename Value, typename Iterator, typename Functor>
    1.56      void radixIntroSort(Iterator first, Iterator last,
    1.57                          Functor functor, Value mask) {
    1.58 -      while (mask != 0 && last - first > 1) {
    1.59 +      while (mask != 0 && first != last && !unitRange(first, last)) {
    1.60          Iterator cut = radixSortPartition(first, last, functor, mask);
    1.61          mask >>= 1;
    1.62          radixIntroSort(first, cut, functor, mask);