COIN-OR::LEMON - Graph Library

Changeset 1210:d450a02728d0 in lemon


Ignore:
Timestamp:
03/19/10 18:23:47 (10 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Bidirectional iterator support for radixSort() (#362)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/radix_sort.h

    r606 r1210  
    3535  namespace _radix_sort_bits {
    3636
     37    template <typename Iterator>
     38    bool unitRange(Iterator first, Iterator last) {
     39      ++first;
     40      return first == last;
     41    }
     42
    3743    template <typename Value>
    3844    struct Identity {
     
    6167      std::iter_swap(first, last);
    6268      ++first;
    63       if (!(first < last)) {
    64         return first;
    65       }
    6669      while (true) {
    6770        while (!(functor(*first) & mask)) {
     
    7275          --last;
    7376        }
    74         if (!(first < last)) {
     77        if (unitRange(last, first)) {
    7578          return first;
    7679        }
     
    98101      std::iter_swap(first, last);
    99102      ++first;
    100       if (!(first < last)) {
    101         return first;
    102       }
    103103      while (true) {
    104104        while (functor(*first) < 0) {
     
    109109          --last;
    110110        }
    111         if (!(first < last)) {
     111        if (unitRange(last, first)) {
    112112          return first;
    113113        }
     
    120120    void radixIntroSort(Iterator first, Iterator last,
    121121                        Functor functor, Value mask) {
    122       while (mask != 0 && last - first > 1) {
     122      while (mask != 0 && first != last && !unitRange(first, last)) {
    123123        Iterator cut = radixSortPartition(first, last, functor, mask);
    124124        mask >>= 1;
Note: See TracChangeset for help on using the changeset viewer.