lemon/radix_sort.h
changeset 1053 1c978b5bcc65
parent 559 c5fd2d996909
child 1092 dceba191c00d
equal deleted inserted replaced
4:a1eda04674f1 5:1e6b18134a31
    32 
    32 
    33 namespace lemon {
    33 namespace lemon {
    34 
    34 
    35   namespace _radix_sort_bits {
    35   namespace _radix_sort_bits {
    36 
    36 
       
    37     template <typename Iterator>
       
    38     bool unitRange(Iterator first, Iterator last) {
       
    39       ++first;
       
    40       return first == last;
       
    41     }
       
    42 
    37     template <typename Value>
    43     template <typename Value>
    38     struct Identity {
    44     struct Identity {
    39       const Value& operator()(const Value& val) {
    45       const Value& operator()(const Value& val) {
    40         return val;
    46         return val;
    41       }
    47       }
    58       if (first == last) {
    64       if (first == last) {
    59         return first;
    65         return first;
    60       }
    66       }
    61       std::iter_swap(first, last);
    67       std::iter_swap(first, last);
    62       ++first;
    68       ++first;
    63       if (!(first < last)) {
       
    64         return first;
       
    65       }
       
    66       while (true) {
    69       while (true) {
    67         while (!(functor(*first) & mask)) {
    70         while (!(functor(*first) & mask)) {
    68           ++first;
    71           ++first;
    69         }
    72         }
    70         --last;
    73         --last;
    71         while (functor(*last) & mask) {
    74         while (functor(*last) & mask) {
    72           --last;
    75           --last;
    73         }
    76         }
    74         if (!(first < last)) {
    77         if (unitRange(last, first)) {
    75           return first;
    78           return first;
    76         }
    79         }
    77         std::iter_swap(first, last);
    80         std::iter_swap(first, last);
    78         ++first;
    81         ++first;
    79       }
    82       }
    95       if (first == last) {
    98       if (first == last) {
    96         return first;
    99         return first;
    97       }
   100       }
    98       std::iter_swap(first, last);
   101       std::iter_swap(first, last);
    99       ++first;
   102       ++first;
   100       if (!(first < last)) {
       
   101         return first;
       
   102       }
       
   103       while (true) {
   103       while (true) {
   104         while (functor(*first) < 0) {
   104         while (functor(*first) < 0) {
   105           ++first;
   105           ++first;
   106         }
   106         }
   107         --last;
   107         --last;
   108         while (functor(*last) >= 0) {
   108         while (functor(*last) >= 0) {
   109           --last;
   109           --last;
   110         }
   110         }
   111         if (!(first < last)) {
   111         if (unitRange(last, first)) {
   112           return first;
   112           return first;
   113         }
   113         }
   114         std::iter_swap(first, last);
   114         std::iter_swap(first, last);
   115         ++first;
   115         ++first;
   116       }
   116       }
   117     }
   117     }
   118 
   118 
   119     template <typename Value, typename Iterator, typename Functor>
   119     template <typename Value, typename Iterator, typename Functor>
   120     void radixIntroSort(Iterator first, Iterator last,
   120     void radixIntroSort(Iterator first, Iterator last,
   121                         Functor functor, Value mask) {
   121                         Functor functor, Value mask) {
   122       while (mask != 0 && last - first > 1) {
   122       while (mask != 0 && first != last && !unitRange(first, last)) {
   123         Iterator cut = radixSortPartition(first, last, functor, mask);
   123         Iterator cut = radixSortPartition(first, last, functor, mask);
   124         mask >>= 1;
   124         mask >>= 1;
   125         radixIntroSort(first, cut, functor, mask);
   125         radixIntroSort(first, cut, functor, mask);
   126         first = cut;
   126         first = cut;
   127       }
   127       }