Gaia-ECS v0.9.3
A simple and powerful entity component system
Loading...
Searching...
No Matches
utility.h
1#pragma once
2#include "gaia/config/config.h"
3
4#include <cstdint>
5#include <cstdio>
6#include <tuple>
7#include <type_traits>
8#include <utility>
9
10#if GAIA_PLATFORM_WINDOWS
11 #include <malloc.h>
12#else
13 #include <alloca.h>
14#endif
15
16#include "gaia/core/iterator.h"
17
18namespace gaia {
19 constexpr uint32_t BadIndex = uint32_t(-1);
20
21#if GAIA_COMPILER_MSVC || GAIA_PLATFORM_WINDOWS
22 #define GAIA_STRCPY(var, max_len, text) \
23 strncpy_s((var), (text), (max_len)); \
24 (var)[(max_len) - 1] = 0;
25 #define GAIA_STRFMT(var, max_len, fmt, ...) sprintf_s((var), (max_len), fmt, __VA_ARGS__)
26 #define GAIA_STRLEN(var, max_len) strnlen_s((var), (max_len))
27#else
28 #define GAIA_STRCPY(var, max_len, text) \
29 { \
30 strncpy((var), (text), (max_len)); \
31 (var)[(max_len) - 1] = 0; \
32 }
33 #define GAIA_STRFMT(var, max_len, fmt, ...) snprintf((var), (max_len), fmt, __VA_ARGS__)
34 #define GAIA_STRLEN(var, max_len) strnlen((var), (max_len))
35#endif
36
37 namespace core {
38 namespace detail {
39 template <class T>
40 struct rem_rp {
41 using type = std::remove_reference_t<std::remove_pointer_t<T>>;
42 };
43
44 template <typename T>
45 struct is_mut:
46 std::bool_constant<
47 !std::is_const_v<typename rem_rp<T>::type> &&
48 (std::is_pointer<T>::value || std::is_reference<T>::value)> {};
49
50 template <typename, typename = size_t>
51 struct is_complete: std::false_type {};
52
53 template <typename T>
54 struct is_complete<T, decltype(sizeof(T))>: std::true_type {};
55
56 template <typename C>
57 constexpr auto size(C& c) noexcept -> decltype(c.size()) {
58 return c.size();
59 }
60 template <typename C>
61 constexpr auto size(const C& c) noexcept -> decltype(c.size()) {
62 return c.size();
63 }
64 template <typename T, auto N>
65 constexpr auto size(const T (&)[N]) noexcept {
66 return N;
67 }
68
69 template <typename C>
70 constexpr auto data(C& c) noexcept -> decltype(c.data()) {
71 return c.data();
72 }
73 template <typename C>
74 constexpr auto data(const C& c) noexcept -> decltype(c.data()) {
75 return c.data();
76 }
77 template <typename T, auto N>
78 constexpr T* data(T (&array)[N]) noexcept {
79 return array;
80 }
81 template <typename E>
82 constexpr const E* data(std::initializer_list<E> il) noexcept {
83 return il.begin();
84 }
85 } // namespace detail
86
87 struct zero_t {
88 explicit constexpr zero_t() = default;
89 };
90 inline constexpr zero_t zero{};
91
92 template <typename T>
93 using rem_rp_t = typename detail::rem_rp<T>::type;
94
95 template <typename T>
96 inline constexpr bool is_mut_v = detail::is_mut<T>::value;
97
98 template <typename T>
99 using raw_t = typename std::decay_t<std::remove_pointer_t<T>>;
100
101 template <typename T>
102 inline constexpr bool is_raw_v = std::is_same_v<T, raw_t<T>> && !std::is_array_v<T>;
103
104 template <typename T>
105 inline constexpr bool is_complete_v = detail::is_complete<T>::value;
106
108 template <typename T>
109 constexpr T* addressof(T& obj) noexcept {
110 return &obj;
111 }
112
114 template <typename T>
115 const T* addressof(const T&&) = delete;
116
117 template <typename T>
118 constexpr bool check_alignment(const T* ptr) noexcept {
119 return (reinterpret_cast<uintptr_t>(ptr)) % alignof(T) == 0;
120 }
121
122 template <typename T>
123 struct lock_scope {
124 T& m_ctx;
125
126 lock_scope(T& ctx): m_ctx(ctx) {
127 ctx.lock();
128 }
129 ~lock_scope() {
130 m_ctx.unlock();
131 }
132
133 lock_scope(const lock_scope&) = delete;
134 lock_scope& operator=(const lock_scope&) = delete;
135 lock_scope(lock_scope&&) = delete;
136 lock_scope& operator=(lock_scope&&) = delete;
137 };
138
139 //----------------------------------------------------------------------
140 // Container identification
141 //----------------------------------------------------------------------
142
143 template <typename, typename = void>
144 struct has_data_size: std::false_type {};
145 template <typename T>
146 struct has_data_size<
147 T, std::void_t< //
148 decltype(detail::data(std::declval<T>())), //
149 decltype(detail::size(std::declval<T>())) //
150 >>: std::true_type {};
151
152 template <typename, typename = void>
153 struct has_size_begin_end: std::false_type {};
154 template <typename T>
155 struct has_size_begin_end<
156 T, std::void_t< //
157 decltype(std::declval<T>().begin()), //
158 decltype(std::declval<T>().end()), //
159 decltype(detail::size(std::declval<T>())) //
160 >>: std::true_type {};
161
162 //----------------------------------------------------------------------
163 // Bit-byte conversion
164 //----------------------------------------------------------------------
165
166 template <typename T>
167 constexpr T as_bits(T value) {
168 static_assert(std::is_integral_v<T>);
169 return value * (T)8;
170 }
171
172 template <typename T>
173 constexpr T as_bytes(T value) {
174 static_assert(std::is_integral_v<T>);
175 return value / (T)8;
176 }
177
178 //----------------------------------------------------------------------
179 // Memory size helpers
180 //----------------------------------------------------------------------
181
182 template <typename T>
183 constexpr uint32_t count_bits(T number) {
184 uint32_t bits_needed = 0;
185 while (number > 0U) {
186 number >>= 1U;
187 ++bits_needed;
188 }
189 return bits_needed;
190 }
191
192 template <typename T>
193 constexpr bool is_pow2(T number) {
194 static_assert(std::is_integral<T>::value, "is_pow2 must be used with integer types");
195
196 return (number & (number - 1)) == 0;
197 }
198
199 template <typename T>
200 constexpr T closest_pow2(T number) {
201 static_assert(std::is_integral<T>::value, "closest_pow2 must be used with integer types");
202
203 if (is_pow2(number))
204 return number;
205
206 // Collapse all bits below the highest set bit
207 number |= number >> 1;
208 number |= number >> 2;
209 number |= number >> 4;
210 if constexpr (sizeof(T) > 1)
211 number |= number >> 8;
212 if constexpr (sizeof(T) > 2)
213 number |= number >> 16;
214 if constexpr (sizeof(T) > 4)
215 number |= number >> 32;
216
217 // The result is now one less than the next power of two, so shift back
218 return number - (number >> 1);
219 }
220
221 //----------------------------------------------------------------------
222 // Element construction / destruction
223 //----------------------------------------------------------------------
224
228 template <typename T>
229 void call_ctor_raw(T* pData) {
230 GAIA_ASSERT(pData != nullptr);
231 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T;
232 }
233
238 template <typename T>
239 void call_ctor_raw_n(T* pData, size_t cnt) {
240 GAIA_ASSERT(pData != nullptr);
241 for (size_t i = 0; i < cnt; ++i) {
242 auto* ptr = pData + i;
243 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T;
244 }
245 }
246
250 template <typename T>
251 void call_ctor_val(T* pData) {
252 GAIA_ASSERT(pData != nullptr);
253 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T();
254 }
255
260 template <typename T>
261 void call_ctor_val_n(T* pData, size_t cnt) {
262 GAIA_ASSERT(pData != nullptr);
263 for (size_t i = 0; i < cnt; ++i) {
264 auto* ptr = pData + i;
265 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T();
266 }
267 }
268
273 template <typename T>
274 void call_ctor([[maybe_unused]] T* pData) {
275 GAIA_ASSERT(pData != nullptr);
276 if constexpr (!std::is_trivially_constructible_v<T>) {
277 (void)::new (pData) T();
278 }
279 }
280
285 template <typename T>
286 void call_ctor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
287 GAIA_ASSERT(pData != nullptr);
288 if constexpr (!std::is_trivially_constructible_v<T>) {
289 for (size_t i = 0; i < cnt; ++i)
290 (void)::new (pData + i) T();
291 }
292 }
293
294 template <typename T, typename... Args>
295 void call_ctor(T* pData, Args&&... args) {
296 GAIA_ASSERT(pData != nullptr);
297 if constexpr (std::is_constructible_v<T, Args...>)
298 (void)::new (pData) T(GAIA_FWD(args)...);
299 else
300 (void)::new (pData) T{GAIA_FWD(args)...};
301 }
302
307 template <typename T>
308 void call_dtor([[maybe_unused]] T* pData) {
309 GAIA_ASSERT(pData != nullptr);
310 if constexpr (!std::is_trivially_destructible_v<T>) {
311 pData->~T();
312 }
313 }
314
319 template <typename T>
320 void call_dtor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
321 GAIA_ASSERT(pData != nullptr);
322 if constexpr (!std::is_trivially_destructible_v<T>) {
323 for (size_t i = 0; i < cnt; ++i)
324 pData[i].~T();
325 }
326 }
327
328 //----------------------------------------------------------------------
329 // Element swapping
330 //----------------------------------------------------------------------
331
332 template <typename T>
333 constexpr void swap(T& left, T& right) {
334 T tmp = GAIA_MOV(left);
335 left = GAIA_MOV(right);
336 right = GAIA_MOV(tmp);
337 }
338
339 template <typename T, typename TCmpFunc>
340 constexpr void swap_if(T* c, size_t lhs, size_t rhs, TCmpFunc cmpFunc) noexcept {
341 if (!cmpFunc(c[lhs], c[rhs]))
342 core::swap(c[lhs], c[rhs]);
343 }
344
345 template <typename T, typename TCmpFunc>
346 constexpr void swap_if(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
347 if (!cmpFunc(lhs, rhs))
348 core::swap(lhs, rhs);
349 }
350
351 template <typename T, typename TCmpFunc>
352 constexpr void swap_if_not(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
353 if (cmpFunc(lhs, rhs))
354 core::swap(lhs, rhs);
355 }
356
357 template <typename T, typename TCmpFunc, typename TSwapFunc>
358 constexpr void try_swap_if(T* c, uint32_t lhs, uint32_t rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
359 if (!cmpFunc(c[lhs], c[rhs]))
360 swapFunc(lhs, rhs);
361 }
362
363 template <typename C, typename TCmpFunc, typename TSwapFunc>
364 constexpr void try_swap_if(
365 C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
366 if (!cmpFunc(c[lhs], c[rhs]))
367 swapFunc(lhs, rhs);
368 }
369
370 template <typename C, typename TCmpFunc, typename TSwapFunc>
371 constexpr void try_swap_if_not(
372 C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
373 if (cmpFunc(c[lhs], c[rhs]))
374 swapFunc(lhs, rhs);
375 }
376
377 //----------------------------------------------------------------------
378 // Value filling
379 //----------------------------------------------------------------------
380
381 template <class ForwardIt, class T>
382 constexpr void fill(ForwardIt first, ForwardIt last, const T& value) {
383 for (; first != last; ++first) {
384 *first = value;
385 }
386 }
387
388 //----------------------------------------------------------------------
389 // Value range checking
390 //----------------------------------------------------------------------
391
392 template <class T>
393 constexpr const T& get_min(const T& a, const T& b) {
394 return (b < a) ? b : a;
395 }
396
397 template <class T>
398 constexpr const T& get_max(const T& a, const T& b) {
399 return (b > a) ? b : a;
400 }
401
402 //----------------------------------------------------------------------
403 // Checking if a template arg is unique among the rest
404 //----------------------------------------------------------------------
405
406 template <typename...>
407 inline constexpr auto is_unique = std::true_type{};
408
409 template <typename T, typename... Rest>
410 inline constexpr auto is_unique<T, Rest...> =
411 std::bool_constant<(!std::is_same_v<T, Rest> && ...) && is_unique<Rest...>>{};
412
413 namespace detail {
414 template <typename T>
415 struct type_identity {
416 using type = T;
417 };
418 } // namespace detail
419
420 template <typename T, typename... Ts>
421 struct unique: detail::type_identity<T> {}; // TODO: In C++20 we could use std::type_identity
422
423 template <typename... Ts, typename U, typename... Us>
424 struct unique<std::tuple<Ts...>, U, Us...>:
425 std::conditional_t<
426 (std::is_same_v<U, Ts> || ...), unique<std::tuple<Ts...>, Us...>, unique<std::tuple<Ts..., U>, Us...>> {};
427
428 template <typename... Ts>
429 using unique_tuple = typename unique<std::tuple<>, Ts...>::type;
430
431 //----------------------------------------------------------------------
432 // Calculating total size of all types of tuple
433 //----------------------------------------------------------------------
434
435 template <typename... Args>
436 constexpr unsigned get_args_size(std::tuple<Args...> const& /*no_name*/) {
437 return (sizeof(Args) + ...);
438 }
439
440 //----------------------------------------------------------------------
441 // Function arguments type checks
442 //----------------------------------------------------------------------
443
444 template <typename... Type>
445 struct func_type_list {};
446
447 template <typename Class, typename Ret, typename... Args>
448 func_type_list<Args...> func_args(Ret (Class::*)(Args...) const);
449
450 //----------------------------------------------------------------------
451 // Member function checks
452 //----------------------------------------------------------------------
453
454#if __cpp_concepts
455 #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name) \
456 template <typename T, typename... Args> \
457 concept has_mfunc_check_##function_name = requires(T&& t, Args&&... args) { t.function_name(GAIA_FWD(args)...); }; \
458 \
459 template <typename T, typename... Args> \
460 struct has_func_##function_name { \
461 static constexpr bool value = has_mfunc_check_##function_name<T, Args...>; \
462 }
463#else
464 namespace detail {
465 template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
466 struct member_func_checker {
467 using value_t = std::false_type;
468 using type = Default;
469 };
470
471 template <class Default, template <class...> class Op, class... Args>
472 struct member_func_checker<Default, std::void_t<Op<Args...>>, Op, Args...> {
473 using value_t = std::true_type;
474 using type = Op<Args...>;
475 };
476
477 struct member_func_none {
478 ~member_func_none() = delete;
479 member_func_none(member_func_none const&) = delete;
480 member_func_none(member_func_none&&) = delete;
481 void operator=(member_func_none const&) = delete;
482 void operator=(member_func_none&&) = delete;
483 };
484 } // namespace detail
485
486 template <template <class...> class Op, typename... Args>
487 using has_mfunc = typename detail::member_func_checker<detail::member_func_none, void, Op, Args...>::value_t;
488
489 #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name) \
490 template <typename T, typename... Args> \
491 using has_mfunc_check_##function_name = decltype(std::declval<T>().function_name(std::declval<Args>()...)); \
492 \
493 template <typename T, typename... Args> \
494 struct has_func_##function_name { \
495 static constexpr bool value = gaia::core::has_mfunc<has_mfunc_check_##function_name, T, Args...>::value; \
496 }
497#endif
498
499 GAIA_DEFINE_HAS_MEMBER_FUNC(find);
500 GAIA_DEFINE_HAS_MEMBER_FUNC(find_if);
501 GAIA_DEFINE_HAS_MEMBER_FUNC(find_if_not);
502
503 //----------------------------------------------------------------------
504 // Special function checks
505 //----------------------------------------------------------------------
506
507 namespace detail {
508 template <typename T>
509 constexpr auto has_mfunc_equals_check(int)
510 -> decltype(std::declval<T>().operator==(std::declval<T>()), std::true_type{});
511 template <typename T, typename... Args>
512 constexpr std::false_type has_mfunc_equals_check(...);
513
514 template <typename T>
515 constexpr auto has_ffunc_equals_check(int)
516 -> decltype(operator==(std::declval<T>(), std::declval<T>()), std::true_type{});
517 template <typename T, typename... Args>
518 constexpr std::false_type has_ffunc_equals_check(...);
519 } // namespace detail
520
521 template <typename T>
522 struct has_func_equals {
523 static constexpr bool value = decltype(detail::has_mfunc_equals_check<T>(0))::value;
524 };
525
526 template <typename T>
527 struct has_ffunc_equals {
528 static constexpr bool value = decltype(detail::has_ffunc_equals_check<T>(0))::value;
529 };
530
531 //----------------------------------------------------------------------
532 // Type helpers
533 //----------------------------------------------------------------------
534
535 template <typename... Type>
536 struct type_list {
537 using types = type_list;
538 static constexpr auto size = sizeof...(Type);
539 };
540
541 template <typename TypesA, typename TypesB>
542 struct type_list_concat;
543
544 template <typename... TypesA, typename... TypesB>
545 struct type_list_concat<type_list<TypesA...>, type_list<TypesB...>> {
546 using type = type_list<TypesA..., TypesB...>;
547 };
548
549 //----------------------------------------------------------------------
550 // Looping
551 //----------------------------------------------------------------------
552
553 namespace detail {
554 template <auto FirstIdx, auto Iters, typename Func, auto... Is>
555 constexpr void each_impl(Func func, std::integer_sequence<decltype(Iters), Is...> /*no_name*/) {
556 if constexpr ((std::is_invocable_v<Func&&, std::integral_constant<decltype(Is), Is>> && ...))
557 (func(std::integral_constant<decltype(Is), FirstIdx + Is>{}), ...);
558 else
559 (((void)Is, func()), ...);
560 }
561
562 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
563 void each_tuple_impl(Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
564 if constexpr (
565 (std::is_invocable_v<
566 Func&&, decltype(std::tuple_element_t<FirstIdx + Is, Tuple>{}),
567 std::integral_constant<decltype(FirstIdx), Is>> &&
568 ...))
569 // func(Args&& arg, uint32_t idx)
570 (func(
571 std::tuple_element_t<FirstIdx + Is, Tuple>{},
572 std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}),
573 ...);
574 else
575 // func(Args&& arg)
576 (func(std::tuple_element_t<FirstIdx + Is, Tuple>{}), ...);
577 }
578
579 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
580 void each_tuple_impl(Tuple&& tuple, Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
581 if constexpr (
582 (std::is_invocable_v<
583 Func&&, decltype(std::get<FirstIdx + Is>(tuple)), std::integral_constant<decltype(FirstIdx), Is>> &&
584 ...))
585 // func(Args&& arg, uint32_t idx)
586 (func(std::get<FirstIdx + Is>(tuple), std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}), ...);
587 else
588 // func(Args&& arg)
589 (func(std::get<FirstIdx + Is>(tuple)), ...);
590 }
591 } // namespace detail
592
606 template <auto Iters, typename Func>
607 constexpr void each(Func func) {
608 using TIters = decltype(Iters);
609 constexpr TIters First = 0;
610 detail::each_impl<First, Iters, Func>(func, std::make_integer_sequence<TIters, Iters>());
611 }
612
627 template <auto FirstIdx, auto LastIdx, typename Func>
628 constexpr void each_ext(Func func) {
629 static_assert(LastIdx >= FirstIdx);
630 const auto Iters = LastIdx - FirstIdx;
631 detail::each_impl<FirstIdx, Iters, Func>(func, std::make_integer_sequence<decltype(Iters), Iters>());
632 }
633
649 template <auto FirstIdx, auto LastIdx, auto Inc, typename Func>
650 constexpr void each_ext(Func func) {
651 if constexpr (FirstIdx < LastIdx) {
652 if constexpr (std::is_invocable_v<Func&&, std::integral_constant<decltype(FirstIdx), FirstIdx>>)
653 func(std::integral_constant<decltype(FirstIdx), FirstIdx>());
654 else
655 func();
656
657 each_ext<FirstIdx + Inc, LastIdx, Inc>(func);
658 }
659 }
660
671 template <typename Func, typename... Args>
672 constexpr void each_pack(Func func, Args&&... args) {
673 (func(GAIA_FWD(args)), ...);
674 }
675
689 template <typename Tuple, typename Func>
690 constexpr void each_tuple(Tuple&& tuple, Func func) {
691 using TTSize = uint32_t;
692 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
693 detail::each_tuple_impl<(TTSize)0>(GAIA_FWD(tuple), func, std::make_integer_sequence<TTSize, TSize>{});
694 }
695
711 template <typename Tuple, typename Func>
712 constexpr void each_tuple(Func func) {
713 using TTSize = uint32_t;
714 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
715 detail::each_tuple_impl<(TTSize)0, Tuple>(func, std::make_integer_sequence<TTSize, TSize>{});
716 }
717
731 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
732 constexpr void each_tuple_ext(Tuple&& tuple, Func func) {
733 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
734 static_assert(LastIdx >= FirstIdx);
735 static_assert(LastIdx <= TSize);
736 constexpr auto Iters = LastIdx - FirstIdx;
737 detail::each_tuple_impl<FirstIdx>(GAIA_FWD(tuple), func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
738 }
739
755 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
756 constexpr void each_tuple_ext(Func func) {
757 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
758 static_assert(LastIdx >= FirstIdx);
759 static_assert(LastIdx <= TSize);
760 constexpr auto Iters = LastIdx - FirstIdx;
761 detail::each_tuple_impl<FirstIdx, Tuple>(func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
762 }
763
764 template <typename InputIt, typename Func>
765 constexpr Func each(InputIt first, InputIt last, Func func) {
766 for (; first != last; ++first)
767 func(*first);
768 return func;
769 }
770
771 template <typename C, typename Func>
772 constexpr auto each(const C& arr, Func func) {
773 return each(arr.begin(), arr.end(), func);
774 }
775
776 //----------------------------------------------------------------------
777 // Lookups
778 //----------------------------------------------------------------------
779
780 template <typename InputIt, typename T>
781 constexpr InputIt find(InputIt first, InputIt last, const T& value) {
782 if constexpr (std::is_pointer_v<InputIt>) {
783 auto size = distance(first, last);
784 for (decltype(size) i = 0; i < size; ++i) {
785 if (first[i] == value)
786 return &first[i];
787 }
788 } else if constexpr (is_random_iter_v<InputIt>) {
789 auto size = distance(first, last);
790 for (decltype(size) i = 0; i < size; ++i) {
791 if (*(first[i]) == value)
792 return first[i];
793 }
794 } else {
795 for (; first != last; ++first) {
796 if (*first == value)
797 return first;
798 }
799 }
800 return last;
801 }
802
803 template <typename C, typename V>
804 constexpr auto find(const C& arr, const V& item) {
805 if constexpr (has_func_find<C>::value)
806 return arr.find(item);
807 else
808 return core::find(arr.begin(), arr.end(), item);
809 }
810
811 template <typename InputIt, typename Func>
812 constexpr InputIt find_if(InputIt first, InputIt last, Func func) {
813 if constexpr (std::is_pointer_v<InputIt>) {
814 auto size = distance(first, last);
815 for (decltype(size) i = 0; i < size; ++i) {
816 if (func(first[i]))
817 return &first[i];
818 }
819 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
820 auto size = distance(first, last);
821 for (decltype(size) i = 0; i < size; ++i) {
822 if (func(*(first[i])))
823 return first[i];
824 }
825 } else {
826 for (; first != last; ++first) {
827 if (func(*first))
828 return first;
829 }
830 }
831 return last;
832 }
833
834 template <typename UnaryPredicate, typename C>
835 constexpr auto find_if(const C& arr, UnaryPredicate predicate) {
836 if constexpr (has_func_find_if<C, UnaryPredicate>::value)
837 return arr.find_id(predicate);
838 else
839 return core::find_if(arr.begin(), arr.end(), predicate);
840 }
841
842 template <typename InputIt, typename Func>
843 constexpr InputIt find_if_not(InputIt first, InputIt last, Func func) {
844 if constexpr (std::is_pointer_v<InputIt>) {
845 auto size = distance(first, last);
846 for (decltype(size) i = 0; i < size; ++i) {
847 if (!func(first[i]))
848 return &first[i];
849 }
850 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
851 auto size = distance(first, last);
852 for (decltype(size) i = 0; i < size; ++i) {
853 if (!func(*(first[i])))
854 return first[i];
855 }
856 } else {
857 for (; first != last; ++first) {
858 if (!func(*first))
859 return first;
860 }
861 }
862 return last;
863 }
864
865 template <typename UnaryPredicate, typename C>
866 constexpr auto find_if_not(const C& arr, UnaryPredicate predicate) {
867 if constexpr (has_func_find_if_not<C, UnaryPredicate>::value)
868 return arr.find_if_not(predicate);
869 else
870 return core::find_if_not(arr.begin(), arr.end(), predicate);
871 }
872
873 //----------------------------------------------------------------------
874
875 template <typename C, typename V>
876 constexpr bool has(const C& arr, const V& item) {
877 const auto it = find(arr, item);
878 return it != arr.end();
879 }
880
881 template <typename UnaryPredicate, typename C>
882 constexpr bool has_if(const C& arr, UnaryPredicate predicate) {
883 const auto it = find_if(arr, predicate);
884 return it != arr.end();
885 }
886
887 //----------------------------------------------------------------------
888
889 template <typename C>
890 constexpr auto get_index(const C& arr, typename C::const_reference item) {
891 const auto it = find(arr, item);
892 if (it == arr.end())
893 return BadIndex;
894
895 return (decltype(BadIndex))core::distance(arr.begin(), it);
896 }
897
898 template <typename C>
899 constexpr auto get_index_unsafe(const C& arr, typename C::const_reference item) {
900 return (decltype(BadIndex))core::distance(arr.begin(), find(arr, item));
901 }
902
903 template <typename UnaryPredicate, typename C>
904 constexpr auto get_index_if(const C& arr, UnaryPredicate predicate) {
905 const auto it = find_if(arr, predicate);
906 if (it == arr.end())
907 return BadIndex;
908
909 return (decltype(BadIndex))core::distance(arr.begin(), it);
910 }
911
912 template <typename UnaryPredicate, typename C>
913 constexpr auto get_index_if_unsafe(const C& arr, UnaryPredicate predicate) {
914 return (decltype(BadIndex))core::distance(arr.begin(), find_if(arr, predicate));
915 }
916
917 //----------------------------------------------------------------------
918 // Erasure
919 //----------------------------------------------------------------------
920
928 template <typename C>
929 void swap_erase_unsafe(C& arr, typename C::size_type idx) {
930 GAIA_ASSERT(idx < arr.size());
931
932 if (idx + 1 != arr.size())
933 arr[idx] = arr[arr.size() - 1];
934
935 arr.pop_back();
936 }
937
943 // to sort the array.
944 template <typename C>
945 void swap_erase(C& arr, typename C::size_type idx) {
946 if (idx >= arr.size())
947 return;
948
949 if (idx + 1 != arr.size())
950 arr[idx] = arr[arr.size() - 1];
951
952 arr.pop_back();
953 }
954
955 //----------------------------------------------------------------------
956 // Comparison
957 //----------------------------------------------------------------------
958
959 template <typename T>
960 struct equal_to {
961 constexpr bool operator()(const T& lhs, const T& rhs) const {
962 return lhs == rhs;
963 }
964 };
965
966 template <typename T>
967 struct is_smaller {
968 constexpr bool operator()(const T& lhs, const T& rhs) const {
969 return lhs < rhs;
970 }
971 };
972
973 template <typename T>
974 struct is_smaller_or_equal {
975 constexpr bool operator()(const T& lhs, const T& rhs) const {
976 return lhs <= rhs;
977 }
978 };
979
980 template <typename T>
981 struct is_greater {
982 constexpr bool operator()(const T& lhs, const T& rhs) const {
983 return lhs > rhs;
984 }
985 };
986
987 //----------------------------------------------------------------------
988 // Sorting
989 //----------------------------------------------------------------------
990
991 namespace detail {
992 template <typename Container, typename TCmpFunc>
993 int quick_sort_partition(Container& arr, int low, int high, TCmpFunc cmpFunc) {
994 const auto& pivot = arr[(uint32_t)high];
995 int i = low - 1;
996 for (int j = low; j <= high - 1; ++j) {
997 if (cmpFunc(arr[(uint32_t)j], pivot))
998 core::swap(arr[(uint32_t)++i], arr[(uint32_t)j]);
999 }
1000 core::swap(arr[(uint32_t)++i], arr[(uint32_t)high]);
1001 return i;
1002 }
1003
1004 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1005 int quick_sort_partition(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1006 const auto& pivot = arr[(uint32_t)high];
1007 int i = low - 1;
1008 for (int j = low; j <= high - 1; ++j) {
1009 if (cmpFunc(arr[(uint32_t)j], pivot))
1010 swapFunc((uint32_t)++i, (uint32_t)j);
1011 }
1012 swapFunc((uint32_t)++i, (uint32_t)high);
1013 return i;
1014 }
1015
1016 template <typename T, typename TCmpFunc>
1017 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc) {
1018 const auto n = (uint32_t)(end - beg);
1019 if (n <= 1) {
1020 // Nothing to sort with just one item
1021 } else if (n == 2) {
1022 swap_if(beg, 0, 1, cmpFunc);
1023 } else if (n == 3) {
1024 swap_if(beg, 1, 2, cmpFunc);
1025 swap_if(beg, 0, 2, cmpFunc);
1026 swap_if(beg, 0, 1, cmpFunc);
1027 } else if (n == 4) {
1028 swap_if(beg, 0, 1, cmpFunc);
1029 swap_if(beg, 2, 3, cmpFunc);
1030
1031 swap_if(beg, 0, 2, cmpFunc);
1032 swap_if(beg, 1, 3, cmpFunc);
1033
1034 swap_if(beg, 1, 2, cmpFunc);
1035 } else if (n == 5) {
1036 swap_if(beg, 0, 1, cmpFunc);
1037 swap_if(beg, 3, 4, cmpFunc);
1038
1039 swap_if(beg, 2, 4, cmpFunc);
1040
1041 swap_if(beg, 2, 3, cmpFunc);
1042 swap_if(beg, 1, 4, cmpFunc);
1043
1044 swap_if(beg, 0, 3, cmpFunc);
1045
1046 swap_if(beg, 0, 2, cmpFunc);
1047 swap_if(beg, 1, 3, cmpFunc);
1048
1049 swap_if(beg, 1, 2, cmpFunc);
1050 } else if (n == 6) {
1051 swap_if(beg, 1, 2, cmpFunc);
1052 swap_if(beg, 4, 5, cmpFunc);
1053
1054 swap_if(beg, 0, 2, cmpFunc);
1055 swap_if(beg, 3, 5, cmpFunc);
1056
1057 swap_if(beg, 0, 1, cmpFunc);
1058 swap_if(beg, 3, 4, cmpFunc);
1059 swap_if(beg, 2, 5, cmpFunc);
1060
1061 swap_if(beg, 0, 3, cmpFunc);
1062 swap_if(beg, 1, 4, cmpFunc);
1063
1064 swap_if(beg, 2, 4, cmpFunc);
1065 swap_if(beg, 1, 3, cmpFunc);
1066
1067 swap_if(beg, 2, 3, cmpFunc);
1068 } else if (n == 7) {
1069 swap_if(beg, 1, 2, cmpFunc);
1070 swap_if(beg, 3, 4, cmpFunc);
1071 swap_if(beg, 5, 6, cmpFunc);
1072
1073 swap_if(beg, 0, 2, cmpFunc);
1074 swap_if(beg, 3, 5, cmpFunc);
1075 swap_if(beg, 4, 6, cmpFunc);
1076
1077 swap_if(beg, 0, 1, cmpFunc);
1078 swap_if(beg, 4, 5, cmpFunc);
1079 swap_if(beg, 2, 6, cmpFunc);
1080
1081 swap_if(beg, 0, 4, cmpFunc);
1082 swap_if(beg, 1, 5, cmpFunc);
1083
1084 swap_if(beg, 0, 3, cmpFunc);
1085 swap_if(beg, 2, 5, cmpFunc);
1086
1087 swap_if(beg, 1, 3, cmpFunc);
1088 swap_if(beg, 2, 4, cmpFunc);
1089
1090 swap_if(beg, 2, 3, cmpFunc);
1091 } else if (n == 8) {
1092 swap_if(beg, 0, 1, cmpFunc);
1093 swap_if(beg, 2, 3, cmpFunc);
1094 swap_if(beg, 4, 5, cmpFunc);
1095 swap_if(beg, 6, 7, cmpFunc);
1096
1097 swap_if(beg, 0, 2, cmpFunc);
1098 swap_if(beg, 1, 3, cmpFunc);
1099 swap_if(beg, 4, 6, cmpFunc);
1100 swap_if(beg, 5, 7, cmpFunc);
1101
1102 swap_if(beg, 1, 2, cmpFunc);
1103 swap_if(beg, 5, 6, cmpFunc);
1104 swap_if(beg, 0, 4, cmpFunc);
1105 swap_if(beg, 3, 7, cmpFunc);
1106
1107 swap_if(beg, 1, 5, cmpFunc);
1108 swap_if(beg, 2, 6, cmpFunc);
1109
1110 swap_if(beg, 1, 4, cmpFunc);
1111 swap_if(beg, 3, 6, cmpFunc);
1112
1113 swap_if(beg, 2, 4, cmpFunc);
1114 swap_if(beg, 3, 5, cmpFunc);
1115
1116 swap_if(beg, 3, 4, cmpFunc);
1117 } else if (n == 9) {
1118 swap_if(beg, 0, 1, cmpFunc);
1119 swap_if(beg, 3, 4, cmpFunc);
1120 swap_if(beg, 6, 7, cmpFunc);
1121 swap_if(beg, 1, 2, cmpFunc);
1122 swap_if(beg, 4, 5, cmpFunc);
1123 swap_if(beg, 7, 8, cmpFunc);
1124 swap_if(beg, 0, 1, cmpFunc);
1125 swap_if(beg, 3, 4, cmpFunc);
1126 swap_if(beg, 6, 7, cmpFunc);
1127 swap_if(beg, 0, 3, cmpFunc);
1128 swap_if(beg, 3, 6, cmpFunc);
1129 swap_if(beg, 0, 3, cmpFunc);
1130 swap_if(beg, 1, 4, cmpFunc);
1131 swap_if(beg, 4, 7, cmpFunc);
1132 swap_if(beg, 1, 4, cmpFunc);
1133 swap_if(beg, 2, 5, cmpFunc);
1134 swap_if(beg, 5, 8, cmpFunc);
1135 swap_if(beg, 2, 5, cmpFunc);
1136 swap_if(beg, 1, 3, cmpFunc);
1137 swap_if(beg, 5, 7, cmpFunc);
1138 swap_if(beg, 2, 6, cmpFunc);
1139 swap_if(beg, 4, 6, cmpFunc);
1140 swap_if(beg, 2, 4, cmpFunc);
1141 swap_if(beg, 2, 3, cmpFunc);
1142 swap_if(beg, 5, 6, cmpFunc);
1143 } else if (n == 10) {
1144 swap_if(beg, 0, 8, cmpFunc);
1145 swap_if(beg, 1, 9, cmpFunc);
1146 swap_if(beg, 2, 7, cmpFunc);
1147 swap_if(beg, 3, 6, cmpFunc);
1148 swap_if(beg, 4, 5, cmpFunc);
1149
1150 swap_if(beg, 0, 2, cmpFunc);
1151 swap_if(beg, 1, 3, cmpFunc);
1152 swap_if(beg, 4, 8, cmpFunc);
1153 swap_if(beg, 5, 7, cmpFunc);
1154 swap_if(beg, 6, 9, cmpFunc);
1155
1156 swap_if(beg, 0, 4, cmpFunc);
1157 swap_if(beg, 1, 5, cmpFunc);
1158 swap_if(beg, 2, 6, cmpFunc);
1159 swap_if(beg, 3, 7, cmpFunc);
1160
1161 swap_if(beg, 0, 1, cmpFunc);
1162 swap_if(beg, 2, 3, cmpFunc);
1163 swap_if(beg, 4, 6, cmpFunc);
1164 swap_if(beg, 5, 9, cmpFunc);
1165 swap_if(beg, 7, 8, cmpFunc);
1166
1167 swap_if(beg, 1, 2, cmpFunc);
1168 swap_if(beg, 3, 5, cmpFunc);
1169 swap_if(beg, 6, 7, cmpFunc);
1170 swap_if(beg, 8, 9, cmpFunc);
1171
1172 swap_if(beg, 2, 4, cmpFunc);
1173 swap_if(beg, 3, 6, cmpFunc);
1174 swap_if(beg, 5, 8, cmpFunc);
1175
1176 swap_if(beg, 1, 2, cmpFunc);
1177 swap_if(beg, 3, 4, cmpFunc);
1178 swap_if(beg, 5, 6, cmpFunc);
1179 swap_if(beg, 7, 8, cmpFunc);
1180 } else if (n <= 32) {
1181 for (uint32_t i = 0; i < n - 1; ++i)
1182 for (uint32_t j = 0; j < n - i - 1; ++j)
1183 swap_if(beg, j, j + 1, cmpFunc);
1184 }
1185
1186 return n <= 32;
1187 }
1188
1189 template <typename T, typename TCmpFunc, typename TSwapFunc>
1190 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1191 const auto n = (uint32_t)(end - beg);
1192 if (n <= 1) {
1193 // Nothing to sort with just one item
1194 } else if (n == 2) {
1195 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1196 } else if (n == 3) {
1197 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1198 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1199 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1200 } else if (n == 4) {
1201 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1202 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1203
1204 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1205 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1206
1207 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1208 } else if (n == 5) {
1209 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1210 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1211
1212 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1213
1214 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1215 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1216
1217 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1218
1219 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1220 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1221
1222 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1223 } else if (n == 6) {
1224 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1225 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1226
1227 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1228 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1229
1230 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1231 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1232 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1233
1234 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1235 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1236
1237 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1238 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1239
1240 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1241 } else if (n == 7) {
1242 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1243 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1244 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1245
1246 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1247 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1248 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1249
1250 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1251 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1252 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1253
1254 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
1255 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
1256
1257 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1258 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1259
1260 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1261 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1262
1263 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1264 } else if (n == 8) {
1265 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1266 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1267 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1268 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1269
1270 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1271 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1272 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1273 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
1274
1275 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1276 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1277 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
1278 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
1279
1280 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
1281 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1282
1283 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1284 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1285
1286 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1287 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1288
1289 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1290 } else if (n == 9) {
1291 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1292 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1293 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1294 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1295 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1296 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
1297 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1298 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1299 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1300 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1301 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1302 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1303 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1304 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
1305 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1306 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1307 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
1308 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1309 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1310 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
1311 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1312 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1313 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1314 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1315 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1316 } else if (n == 10) {
1317 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
1318 try_swap_if(beg, 1, 9, cmpFunc, swapFunc);
1319 try_swap_if(beg, 2, 7, cmpFunc, swapFunc);
1320 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1321 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1322
1323 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1324 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1325 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
1326 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
1327 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
1328
1329 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
1330 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
1331 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1332 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
1333
1334 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1335 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1336 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1337 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
1338 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
1339
1340 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1341 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1342 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1343 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
1344
1345 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1346 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1347 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
1348
1349 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1350 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1351 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1352 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
1353 } else if (n <= 32) {
1354 for (uint32_t i = 0; i < n - 1; ++i)
1355 for (uint32_t j = 0; j < n - i - 1; ++j)
1356 try_swap_if(beg, j, j + 1, cmpFunc, swapFunc);
1357 }
1358
1359 return n <= 32;
1360 }
1361 } // namespace detail
1362
1363 template <typename Container, typename TCmpFunc>
1364 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc) {
1365 if (low >= high)
1366 return;
1367 auto pos = detail::quick_sort_partition(arr, low, high, cmpFunc);
1368 quick_sort(arr, low, pos - 1, cmpFunc);
1369 quick_sort(arr, pos + 1, high, cmpFunc);
1370 }
1371
1372 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1373 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1374 if (low >= high)
1375 return;
1376 auto pos = detail::quick_sort_partition(arr, low, high, cmpFunc, swapFunc);
1377 quick_sort(arr, low, pos - 1, cmpFunc, swapFunc);
1378 quick_sort(arr, pos + 1, high, cmpFunc, swapFunc);
1379 }
1380
1395 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1396 void
1397 quick_sort_stack(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc, uint32_t maxStackSize) {
1398 GAIA_ASSERT(high < (int)arr.size() && "quick_sort_stack: 'high' has to be smaller than the container size.");
1399 GAIA_ASSERT(
1400 (uint32_t)arr.size() <= maxStackSize && "quick_sort_stack: used with too large input array. Stack overflow.");
1401
1402 struct Range {
1403 int low, high;
1404 };
1405
1406 auto* stack = (Range*)alloca(sizeof(Range) * maxStackSize);
1407 GAIA_ASSERT(stack != nullptr && "quick_sort_stack: failed to allocate stack memory.");
1408 uint32_t sp = 0; // stack pointer
1409 stack[sp++] = {low, high};
1410
1411 auto median_of_three = [&](int a, int b, int c) {
1412 if (cmpFunc(arr[a], arr[b])) {
1413 if (cmpFunc(arr[b], arr[c]))
1414 return b;
1415 if (cmpFunc(arr[a], arr[c]))
1416 return c;
1417 return a;
1418 }
1419
1420 if (cmpFunc(arr[a], arr[c]))
1421 return a;
1422 if (cmpFunc(arr[b], arr[c]))
1423 return c;
1424 return b;
1425 };
1426
1427 while (sp > 0) {
1428 const Range r = stack[--sp];
1429 if (r.low >= r.high)
1430 continue;
1431
1432 // Use optimized sort for small partitions
1433 const auto size = r.high - r.low + 1;
1434 if (size <= 32) {
1435 auto* base = &arr[r.low];
1436 detail::sort_nwk(base, base + size, cmpFunc, [&](uint32_t i, uint32_t j) {
1437 swapFunc(r.low + i, r.low + j);
1438 });
1439 continue;
1440 }
1441
1442 // Median-of-three pivot selection
1443 int mid = r.low + ((r.high - r.low) >> 1);
1444 int pivotIdx = median_of_three(r.low, mid, r.high);
1445 swapFunc(pivotIdx, r.high);
1446
1447 const auto& pivot = arr[r.high];
1448 int i = r.low - 1;
1449 for (int j = r.low; j < r.high; ++j) {
1450 if (cmpFunc(arr[j], pivot))
1451 swapFunc(++i, j);
1452 }
1453 swapFunc(++i, r.high);
1454
1455 // Push smaller partition first to reduce max stack usage
1456 if (i - 1 - r.low > r.high - (i + 1)) {
1457 if (r.low < i - 1)
1458 stack[sp++] = {r.low, i - 1};
1459 if (i + 1 < r.high)
1460 stack[sp++] = {i + 1, r.high};
1461 } else {
1462 if (i + 1 < r.high)
1463 stack[sp++] = {i + 1, r.high};
1464 if (r.low < i - 1)
1465 stack[sp++] = {r.low, i - 1};
1466 }
1467 }
1468 }
1469
1483 template <typename Container, typename TCmpFunc>
1484 void quick_sort_stack(Container& arr, int low, int high, TCmpFunc cmpFunc, uint32_t maxStackSize) {
1485 quick_sort_stack(
1486 arr, low, high, cmpFunc,
1487 [&arr](uint32_t a, uint32_t b) {
1488 core::swap(arr[a], arr[b]);
1489 },
1490 maxStackSize);
1491 }
1492
1502 template <typename T, typename TCmpFunc>
1503 void sort(T* beg, T* end, TCmpFunc cmpFunc) {
1504 const auto n = (uintptr_t)(end - beg);
1505 if (detail::sort_nwk(beg, end, cmpFunc))
1506 return;
1507
1508 quick_sort(beg, 0, (int)n - 1, cmpFunc);
1509 }
1510
1511 template <typename C, typename TCmpFunc>
1512 void sort(C& c, TCmpFunc cmpFunc) {
1513 sort(c.begin(), c.end(), cmpFunc);
1514 }
1515
1528 template <typename T, typename TCmpFunc, typename TSwapFunc>
1529 void sort(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1530 const auto n = (uintptr_t)(end - beg);
1531 if (detail::sort_nwk(beg, end, cmpFunc, swapFunc))
1532 return;
1533
1534 quick_sort(beg, 0, (int)n - 1, cmpFunc, swapFunc);
1535 }
1536
1537 template <typename C, typename TCmpFunc, typename TSwapFunc>
1538 void sort(C& c, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1539 sort(c.begin(), c.end(), cmpFunc, swapFunc);
1540 }
1541 } // namespace core
1542} // namespace gaia
gaia
Checks if endianess was detected correctly at compile-time.
Definition bitset.h:9
gaia::core::detail::is_complete
Definition utility.h:51
gaia::core::detail::is_mut
Definition utility.h:48
gaia::core::detail::member_func_checker
Definition utility.h:466
gaia::core::detail::member_func_none
Definition utility.h:477
gaia::core::detail::rem_rp
Definition utility.h:40
gaia::core::detail::type_identity
Definition utility.h:415
gaia::core::equal_to
Definition utility.h:960
gaia::core::func_type_list
Definition utility.h:445
gaia::core::has_data_size
Definition utility.h:144
gaia::core::has_ffunc_equals
Definition utility.h:527
gaia::core::has_func_equals
Definition utility.h:522
gaia::core::has_size_begin_end
Definition utility.h:153
gaia::core::is_greater
Definition utility.h:981
gaia::core::is_smaller_or_equal
Definition utility.h:974
gaia::core::is_smaller
Definition utility.h:967
gaia::core::lock_scope
Definition utility.h:123
gaia::core::type_list_concat
Definition utility.h:542
gaia::core::type_list
Definition utility.h:536
gaia::core::unique
Definition utility.h:421
gaia::core::zero_t
Definition utility.h:87