RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 * This file is a part of LEMON, a generic C++ optimization library.

        return val;

    Iterator radixSortPartition(Iterator first, Iterator last,

                                Functor functor, Value mask) {

        ++first;

        return first;

        --last;

        return first;

        return first;

        while (!(functor(*first) & mask)) {

          ++first;

        }

        --last;

        while (functor(*last) & mask) {

          --last;

        }

        if (!(first < last)) {

          return first;

        }

        std::iter_swap(first, last);

        ++first;

    Iterator radixSortSignPartition(Iterator first, Iterator last,

                                    Functor functor) {

        ++first;

        return first;

        --last;

        return first;

        return first;

        while (functor(*first) < 0) {

          ++first;

        }

        --last;

        while (functor(*last) >= 0) {

          --last;

        }

        if (!(first < last)) {

          return first;

        }

        std::iter_swap(first, last);

        ++first;

    void radixIntroSort(Iterator first, Iterator last,

                        Functor functor, Value mask) {

        Iterator cut = radixSortPartition(first, last, functor, mask);

        mask >>= 1;

        radixIntroSort(first, cut, functor, mask);

        first = cut;

        while ((mask & functor(*it)) != mask) {

          ++max_digit;

          mask <<= 1;

        }

        while ((mask | functor(*it)) != mask) {

          ++max_digit;

          mask <<= 1; mask |= 1;

        }

        while ((mask | functor(*it)) != mask) {

          ++max_digit;

          mask <<= 1; mask |= 1;

        }

    template <typename Value,

              bool sign = std::numeric_limits<Value>::is_signed >

        radixSignedSort<Value>(first, last, functor);

        radixUnsignedSort<Value>(first, last, functor);

  /// The \c radixSort sorts an STL compatible range into ascending

  /// order.  The radix sort algorithm can sort items which are mapped

  /// to integers with an adaptable unary function \c functor and the

  /// order will be ascending according to these mapped values.

  /// It is also possible to use a normal function instead

  /// of the functor object. If the functor is not given it will use

  /// the identity function instead.

  ///

  /// This is a special quick sort algorithm where the pivot

  /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.

  /// Therefore, the time complexity of the

  /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,

  /// additional space, where \c c is the maximal value and \c n is the

  /// number of the items in the container.

  ///

  /// \sa counterSort()

    void counterIntroSort(Key *first, Key *last, Key *target,

                          int byte, Functor functor) {

      const int size =

        unsigned(std::numeric_limits<unsigned char>::max()) + 1;

        counter[i] = 0;

        ++counter[valueByte(functor(*first), byte)];

        ++first;

        prev = num;

        num += counter[i];

        counter[i] = prev;

        target[counter[valueByte(functor(*it), byte)]++] = *it;

        ++it;

    void signedCounterIntroSort(Key *first, Key *last, Key *target,

                                int byte, Functor functor) {

      const int size =

        unsigned(std::numeric_limits<unsigned char>::max()) + 1;

        counter[i] = 0;

        counter[valueByte(functor(*first), byte)]++;

        ++first;

        prev = num;

        num += counter[i];

        counter[i] = prev;

        prev = num;

        num += counter[i];

        counter[i] = prev;

        target[counter[valueByte(functor(*it), byte)]++] = *it;

        ++it;

        bool dir = true;

        std::copy(first, last, buffer);

        for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {

          if (dir) {

            counterIntroSort(buffer, buffer + length, buffer + length,

                             i, functor);

          } else {

            counterIntroSort(buffer + length, buffer + 2 * length, buffer,

                             i, functor);

          }

          dir = !dir;

        }

        if (dir) {

          signedCounterIntroSort(buffer, buffer + length, buffer + length,

                                 sizeof(Value) - 1, functor);

          std::copy(buffer + length, buffer + 2 * length, first);

        }        else {

          signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,

                                 sizeof(Value) - 1, functor);

          std::copy(buffer, buffer + length, first);

        }

        allocator.deallocate(buffer, 2 * length);

        throw;

        bool dir = true;

        std::copy(first, last, buffer);

        for (int i = 0; i < int(sizeof(Value)); ++i) {

          if (dir) {

            counterIntroSort(buffer, buffer + length,

                             buffer + length, i, functor);

          } else {

            counterIntroSort(buffer + length, buffer + 2 * length,

                             buffer, i, functor);

          }

          dir = !dir;

        }

        if (dir) {

          std::copy(buffer, buffer + length, first);

        }        else {

          std::copy(buffer + length, buffer + 2 * length, first);

        }

        allocator.deallocate(buffer, 2 * length);

        throw;

    template <typename Value,

              bool sign = std::numeric_limits<Value>::is_signed >

        counterSignedSort<Value>(first, last, functor);

        counterUnsignedSort<Value>(first, last, functor);

  /// \brief Sorts the STL compatible range into ascending order in a stable

  /// way.

  /// This function sorts an STL compatible range into ascending

  /// order according to an integer mapping in the same as radixSort() does.

  /// This sorting algorithm is stable, i.e. the order of two equal

  /// element remains the same after the sorting.

  ///

  /// This sort algorithm  use a radix forward sort on the

  /// byte-by-byte. First, it counts how many times a byte value occurs

  /// in the container, then it copies the corresponding items to

  /// another container in asceding order in \c O(n) time.

  /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and

  /// it uses \f$ O(n) \f$, additional space, where \c c is the

  /// maximal value and \c n is the number of the items in the

  /// container.

  /// \sa radixSort()

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 * This file is a part of LEMON, a generic C++ optimization library.

  }

  }

  checkRadixSort();