Changeset 1042:d450a02728d0 in lemon-main

Timestamp:

03/19/10 18:23:47 (15 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Bidirectional iterator support for radixSort() (#362)

File:

• lemon/radix_sort.h (modified) (6 diffs)

lemon/radix_sort.h

@@ -35 +35 @@
   namespace _radix_sort_bits {
 
+    template <typename Iterator>
+    bool unitRange(Iterator first, Iterator last) {
+      ++first;
+      return first == last;
+    }
+
     template <typename Value>
     struct Identity {
@@ -61 +67 @@
       std::iter_swap(first, last);
       ++first;
-      if (!(first < last)) {
-        return first;
-      }
       while (true) {
         while (!(functor(*first) & mask)) {
@@ -72 +75 @@
           --last;
         }
-        if (!(first < last)) {
+        if (unitRange(last, first)) {
           return first;
         }
@@ -98 +101 @@
       std::iter_swap(first, last);
       ++first;
-      if (!(first < last)) {
-        return first;
-      }
       while (true) {
         while (functor(*first) < 0) {
@@ -109 +109 @@
           --last;
         }
-        if (!(first < last)) {
+        if (unitRange(last, first)) {
           return first;
         }
@@ -120 +120 @@
     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;