# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 1269019427 -3600
# Node ID d450a02728d02ddd70f59629ca1fbe000c2e0df3
# Parent  0b0327c9b3eff9c42a2d7792e0a68c107872929f
Bidirectional iterator support for radixSort() (#362)

diff -r 0b0327c9b3ef -r d450a02728d0 lemon/radix_sort.h
--- a/lemon/radix_sort.h	Fri Mar 01 18:20:07 2013 +0100
+++ b/lemon/radix_sort.h	Fri Mar 19 18:23:47 2010 +0100
@@ -34,6 +34,12 @@
 
   namespace _radix_sort_bits {
 
+    template <typename Iterator>
+    bool unitRange(Iterator first, Iterator last) {
+      ++first;
+      return first == last;
+    }
+
     template <typename Value>
     struct Identity {
       const Value& operator()(const Value& val) {
@@ -60,9 +66,6 @@
       }
       std::iter_swap(first, last);
       ++first;
-      if (!(first < last)) {
-        return first;
-      }
       while (true) {
         while (!(functor(*first) & mask)) {
           ++first;
@@ -71,7 +74,7 @@
         while (functor(*last) & mask) {
           --last;
         }
-        if (!(first < last)) {
+        if (unitRange(last, first)) {
           return first;
         }
         std::iter_swap(first, last);
@@ -97,9 +100,6 @@
       }
       std::iter_swap(first, last);
       ++first;
-      if (!(first < last)) {
-        return first;
-      }
       while (true) {
         while (functor(*first) < 0) {
           ++first;
@@ -108,7 +108,7 @@
         while (functor(*last) >= 0) {
           --last;
         }
-        if (!(first < last)) {
+        if (unitRange(last, first)) {
           return first;
         }
         std::iter_swap(first, last);
@@ -119,7 +119,7 @@
     template <typename Value, typename Iterator, typename Functor>
     void radixIntroSort(Iterator first, Iterator last,
                         Functor functor, Value mask) {
-      while (mask != 0 && last - first > 1) {
+      while (mask != 0 && first != last && !unitRange(first, last)) {
         Iterator cut = radixSortPartition(first, last, functor, mask);
         mask >>= 1;
         radixIntroSort(first, cut, functor, mask);