summaryrefslogtreecommitdiffstats
path: root/deps/include/entt/core/algorithm.hpp
diff options
context:
space:
mode:
authoruntodesu <kirill@untode.su>2025-06-28 01:59:49 +0500
committeruntodesu <kirill@untode.su>2025-06-28 01:59:49 +0500
commit61e5bcef2629e2d68b805a956a96fff264d4f74d (patch)
treebca3a94bac79d34e3c0db57c77604f5a823ecbda /deps/include/entt/core/algorithm.hpp
parent88c01588aa0830e219eaa62588839e4d1e2883ce (diff)
downloadvoxelius-61e5bcef2629e2d68b805a956a96fff264d4f74d.tar.bz2
voxelius-61e5bcef2629e2d68b805a956a96fff264d4f74d.zip
Restructure dependencies and update to C++20
- Nuked static_assert from almost everywhere in the project - Nuked binary dependency support. Might add one later though - Separated dependency headers into a separate include subdirectory - Grafted a thirdpartylegalnotices.txt generator from RITEG - Pushed development snapshot version to 2126 (26th week of 2025)
Diffstat (limited to 'deps/include/entt/core/algorithm.hpp')
-rw-r--r--deps/include/entt/core/algorithm.hpp143
1 files changed, 0 insertions, 143 deletions
diff --git a/deps/include/entt/core/algorithm.hpp b/deps/include/entt/core/algorithm.hpp
deleted file mode 100644
index 35bdf94..0000000
--- a/deps/include/entt/core/algorithm.hpp
+++ /dev/null
@@ -1,143 +0,0 @@
-#ifndef ENTT_CORE_ALGORITHM_HPP
-#define ENTT_CORE_ALGORITHM_HPP
-
-#include <algorithm>
-#include <functional>
-#include <iterator>
-#include <utility>
-#include <vector>
-#include "utility.hpp"
-
-namespace entt {
-
-/**
- * @brief Function object to wrap `std::sort` in a class type.
- *
- * Unfortunately, `std::sort` cannot be passed as template argument to a class
- * template or a function template.<br/>
- * This class fills the gap by wrapping some flavors of `std::sort` in a
- * function object.
- */
-struct std_sort {
- /**
- * @brief Sorts the elements in a range.
- *
- * Sorts the elements in a range using the given binary comparison function.
- *
- * @tparam It Type of random access iterator.
- * @tparam Compare Type of comparison function object.
- * @tparam Args Types of arguments to forward to the sort function.
- * @param first An iterator to the first element of the range to sort.
- * @param last An iterator past the last element of the range to sort.
- * @param compare A valid comparison function object.
- * @param args Arguments to forward to the sort function, if any.
- */
- template<typename It, typename Compare = std::less<>, typename... Args>
- void operator()(It first, It last, Compare compare = Compare{}, Args &&...args) const {
- std::sort(std::forward<Args>(args)..., std::move(first), std::move(last), std::move(compare));
- }
-};
-
-/*! @brief Function object for performing insertion sort. */
-struct insertion_sort {
- /**
- * @brief Sorts the elements in a range.
- *
- * Sorts the elements in a range using the given binary comparison function.
- *
- * @tparam It Type of random access iterator.
- * @tparam Compare Type of comparison function object.
- * @param first An iterator to the first element of the range to sort.
- * @param last An iterator past the last element of the range to sort.
- * @param compare A valid comparison function object.
- */
- template<typename It, typename Compare = std::less<>>
- void operator()(It first, It last, Compare compare = Compare{}) const {
- if(first < last) {
- for(auto it = first + 1; it < last; ++it) {
- auto value = std::move(*it);
- auto pre = it;
-
- // NOLINTBEGIN(cppcoreguidelines-pro-bounds-pointer-arithmetic)
- for(; pre > first && compare(value, *(pre - 1)); --pre) {
- *pre = std::move(*(pre - 1));
- }
- // NOLINTEND(cppcoreguidelines-pro-bounds-pointer-arithmetic)
-
- *pre = std::move(value);
- }
- }
- }
-};
-
-/**
- * @brief Function object for performing LSD radix sort.
- * @tparam Bit Number of bits processed per pass.
- * @tparam N Maximum number of bits to sort.
- */
-template<std::size_t Bit, std::size_t N>
-struct radix_sort {
- static_assert((N % Bit) == 0, "The maximum number of bits to sort must be a multiple of the number of bits processed per pass");
-
- /**
- * @brief Sorts the elements in a range.
- *
- * Sorts the elements in a range using the given _getter_ to access the
- * actual data to be sorted.
- *
- * This implementation is inspired by the online book
- * [Physically Based Rendering](http://www.pbr-book.org/3ed-2018/Primitives_and_Intersection_Acceleration/Bounding_Volume_Hierarchies.html#RadixSort).
- *
- * @tparam It Type of random access iterator.
- * @tparam Getter Type of _getter_ function object.
- * @param first An iterator to the first element of the range to sort.
- * @param last An iterator past the last element of the range to sort.
- * @param getter A valid _getter_ function object.
- */
- template<typename It, typename Getter = identity>
- void operator()(It first, It last, Getter getter = Getter{}) const {
- if(first < last) {
- constexpr auto passes = N / Bit;
-
- using value_type = typename std::iterator_traits<It>::value_type;
- std::vector<value_type> aux(std::distance(first, last));
-
- auto part = [getter = std::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)
- std::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)
- std::size_t index[buckets]{};
-
- for(std::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
- index[pos + 1u] = index[pos] + count[pos];
- }
-
- for(auto it = from; it != to; ++it) {
- out[index[(getter(*it) >> start) & mask]++] = std::move(*it);
- }
- };
-
- for(std::size_t pass = 0; pass < (passes & ~1); 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);
- std::move(aux.begin(), aux.end(), first);
- }
- }
- }
-};
-
-} // namespace entt
-
-#endif