raddix.hxx

Go to the documentation of this file.

/*===========================================================================================================
 *
 * HUC - Hurna Core
 *
 * Copyright (c) Michael Jeulin-Lagarrigue
 *
 *  Licensed under the MIT License, you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is
 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and limitations under the License.
 *
 * The above copyright notice and this permission notice shall be included in all copies or
 * substantial portions of the Software.
 *
 *=========================================================================================================*/
#ifndef MODULE_SORT_RADDIX_HXX
#define MODULE_SORT_RADDIX_HXX

// STD includes
#include <queue>
#include <vector>

namespace huc
{
  namespace sort
  {
    template <typename IT>
    void RaddixSort(const IT& begin, const IT& end, unsigned int base = 10)
    {
      if (std::distance(begin, end) < 2)
        return;

      // Create a bucket for each possible value of a digit
      std::vector<std::queue<typename std::iterator_traits<IT>::value_type>> buckets(base);

      // For all possible digit
      for (size_t powBase = 1;
           powBase < std::numeric_limits<typename std::iterator_traits<IT>::value_type>::max();
           powBase *= base)
      {
        // Push each number into the bucket of its digit value
        for (auto it = begin; it != end; ++it)
          buckets[static_cast<int>(*it / powBase) % base].push(*it);

        // Dequeu back all the values
        auto itSrc = begin;
        for (auto it = buckets.begin(); it != buckets.end(); ++it)
          while (!it->empty())
          {
            *(itSrc++) = it->front();
            it->pop();
          }
      }
    }
  }
}

#endif // MODULE_SORT_RADDIX_HXX