Changeset 2479:221cfaf118a6 in lemon-0.x for lemon/radix_sort.h

Timestamp:

09/28/07 14:42:14 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3318

Message:

Once again bug fix in significant bit calculation

File:

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

lemon/radix_sort.h

@@ -138 +138 @@
     Iterator it;
 
-    mask = 0; max_digit = 0;
+    mask = ~0; max_digit = 0;
     for (it = first; it != cut; ++it) {
-      while ((mask | functor(*it)) != ~0) {
-        ++max_digit;
-        mask <<= 1; 
-        mask |= 1;
-      }
-    }
-    radixIntroSort(first, cut, functor, 1 << max_digit);
-
-    mask = ~0; max_digit = 0;
-    for (it = cut; it != last; ++it) {
-      while (mask & functor(*it)) {
+      while ((mask & functor(*it)) != mask) {
         ++max_digit;
         mask <<= 1;
       }
     }
+    radixIntroSort(first, cut, functor, 1 << max_digit);
+
+    mask = 0; max_digit = 0;
+    for (it = cut; it != last; ++it) {
+      while ((mask | functor(*it)) != mask) {
+        ++max_digit;
+        mask <<= 1; mask |= 1;
+      }
+    }
     radixIntroSort(cut, last, functor, 1 << max_digit);
   }
@@ -161 +160 @@
   void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
 
-    Value mask = ~0;
+    Value mask = 0;
     int max_digit = 0;
 
     Iterator it;
     for (it = first; it != last; ++it) {
-      while (mask & functor(*it)) {
+      while ((mask | functor(*it)) != mask) {
         ++max_digit;
-        mask <<= 1;
+        mask <<= 1; mask |= 1;
       }
     }