algorithm.hpp

#ifndef ENTT_CORE_ALGORITHM_HPP
#define ENTT_CORE_ALGORITHM_HPP
 
#include "../stl/algorithm.hpp"
#include "../stl/concepts.hpp"
#include "../stl/cstddef.hpp"
#include "../stl/functional.hpp"
#include "../stl/iterator.hpp"
#include "../stl/utility.hpp"
#include "../stl/vector.hpp"
 
namespace entt {

struct std_sort {
    template<typename Compare = stl::less<>, typename... Args>
    void operator()(stl::random_access_iterator auto first, stl::random_access_iterator auto last, Compare compare = Compare{}, Args &&...args) const {
        stl::sort(stl::forward<Args>(args)..., stl::move(first), stl::move(last), stl::move(compare));
    }
};

struct insertion_sort {
    template<typename Compare = stl::less<>>
    void operator()(stl::random_access_iterator auto first, stl::random_access_iterator auto last, Compare compare = Compare{}) const {
        if(first < last) {
            for(auto it = first + 1; it < last; ++it) {
                auto value = stl::move(*it);
                auto pre = it;
 
                // NOLINTBEGIN(cppcoreguidelines-pro-bounds-pointer-arithmetic)
                for(; pre > first && compare(value, *(pre - 1)); --pre) {
                    *pre = stl::move(*(pre - 1));
                }
                // NOLINTEND(cppcoreguidelines-pro-bounds-pointer-arithmetic)
 
                *pre = stl::move(value);
            }
        }
    }
};

template<stl::size_t Bit, stl::size_t N>
requires ((N % Bit) == 0) // The maximum number of bits to sort must be a multiple of the number of bits processed per pass
struct radix_sort {
    template<stl::random_access_iterator It, typename Getter = stl::identity>
    void operator()(It first, It last, Getter getter = Getter{}) const {
        if(first < last) {
            constexpr auto passes = N / Bit;
 
            using value_type = stl::iterator_traits<It>::value_type;
            using difference_type = stl::iterator_traits<It>::difference_type;
            stl::vector<value_type> aux(static_cast<stl::size_t>(stl::distance(first, last)));
 
            auto part = [getter = stl::move(getter)](auto from, auto to, auto out, auto start) {
                constexpr auto mask = (1 << Bit) - 1;
                constexpr auto buckets = 1 << Bit;
 
                // NOLINTNEXTLINE(cppcoreguidelines-avoid-c-arrays, modernize-avoid-c-arrays, misc-const-correctness)
                stl::size_t count[buckets]{};
 
                for(auto it = from; it != to; ++it) {
                    ++count[(getter(*it) >> start) & mask];
                }
 
                // NOLINTNEXTLINE(cppcoreguidelines-avoid-c-arrays, modernize-avoid-c-arrays)
                stl::size_t index[buckets]{};
 
                for(stl::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
                    index[pos + 1u] = index[pos] + count[pos];
                }
 
                for(auto it = from; it != to; ++it) {
                    const auto pos = index[(getter(*it) >> start) & mask]++;
                    out[static_cast<difference_type>(pos)] = stl::move(*it);
                }
            };
 
            for(stl::size_t pass = 0; pass < (passes & ~1u); pass += 2) {
                part(first, last, aux.begin(), pass * Bit);
                part(aux.begin(), aux.end(), first, (pass + 1) * Bit);
            }
 
            if constexpr(passes & 1) {
                part(first, last, aux.begin(), (passes - 1) * Bit);
                stl::move(aux.begin(), aux.end(), first);
            }
        }
    }
};
 
} // namespace entt
 
#endif