lemon/radix_sort.h
changeset 2486 0c498f2239a8
parent 2478 bf783151bc92
child 2553 bfced05fa852
equal deleted inserted replaced
12:c770654b5678 13:67fa94eea8a9
   135 
   135 
   136     Value mask;
   136     Value mask;
   137     int max_digit;
   137     int max_digit;
   138     Iterator it;
   138     Iterator it;
   139 
   139 
   140     mask = 0; max_digit = 0;
   140     mask = ~0; max_digit = 0;
   141     for (it = first; it != cut; ++it) {
   141     for (it = first; it != cut; ++it) {
   142       while ((mask | functor(*it)) != ~0) {
   142       while ((mask & functor(*it)) != mask) {
   143 	++max_digit;
       
   144 	mask <<= 1; 
       
   145 	mask |= 1;
       
   146       }
       
   147     }
       
   148     radixIntroSort(first, cut, functor, 1 << max_digit);
       
   149 
       
   150     mask = ~0; max_digit = 0;
       
   151     for (it = cut; it != last; ++it) {
       
   152       while (mask & functor(*it)) {
       
   153 	++max_digit;
   143 	++max_digit;
   154 	mask <<= 1;
   144 	mask <<= 1;
   155       }
   145       }
   156     }
   146     }
       
   147     radixIntroSort(first, cut, functor, 1 << max_digit);
       
   148 
       
   149     mask = 0; max_digit = 0;
       
   150     for (it = cut; it != last; ++it) {
       
   151       while ((mask | functor(*it)) != mask) {
       
   152 	++max_digit;
       
   153 	mask <<= 1; mask |= 1;
       
   154       }
       
   155     }
   157     radixIntroSort(cut, last, functor, 1 << max_digit);
   156     radixIntroSort(cut, last, functor, 1 << max_digit);
   158   }
   157   }
   159 
   158 
   160   template <typename Value, typename Iterator, typename Functor>
   159   template <typename Value, typename Iterator, typename Functor>
   161   void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
   160   void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
   162 
   161 
   163     Value mask = ~0;
   162     Value mask = 0;
   164     int max_digit = 0;
   163     int max_digit = 0;
   165 
   164 
   166     Iterator it;
   165     Iterator it;
   167     for (it = first; it != last; ++it) {
   166     for (it = first; it != last; ++it) {
   168       while (mask & functor(*it)) {
   167       while ((mask | functor(*it)) != mask) {
   169 	++max_digit;
   168 	++max_digit;
   170 	mask <<= 1;
   169 	mask <<= 1; mask |= 1;
   171       }
   170       }
   172     }
   171     }
   173     radixIntroSort(first, last, functor, 1 << max_digit);
   172     radixIntroSort(first, last, functor, 1 << max_digit);
   174   }
   173   }
   175 
   174