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), (size_t)-1); \
24 (void)max_len
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 ((std::is_invocable_v<
565 Func&&, decltype(std::tuple_element_t<FirstIdx + Is, Tuple>{}),
566 std::integral_constant<decltype(FirstIdx), Is>> &&
567 ...))
568 // func(Args&& arg, uint32_t idx)
569 (func(
570 std::tuple_element_t<FirstIdx + Is, Tuple>{},
571 std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}),
572 ...);
573 else
574 // func(Args&& arg)
575 (func(std::tuple_element_t<FirstIdx + Is, Tuple>{}), ...);
576 }
577
578 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
579 void each_tuple_impl(Tuple&& tuple, Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
580 if constexpr ((std::is_invocable_v<
581 Func&&, decltype(std::get<FirstIdx + Is>(tuple)),
582 std::integral_constant<decltype(FirstIdx), Is>> &&
583 ...))
584 // func(Args&& arg, uint32_t idx)
585 (func(std::get<FirstIdx + Is>(tuple), std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}), ...);
586 else
587 // func(Args&& arg)
588 (func(std::get<FirstIdx + Is>(tuple)), ...);
589 }
590 } // namespace detail
591
605 template <auto Iters, typename Func>
606 constexpr void each(Func func) {
607 using TIters = decltype(Iters);
608 constexpr TIters First = 0;
609 detail::each_impl<First, Iters, Func>(func, std::make_integer_sequence<TIters, Iters>());
610 }
611
626 template <auto FirstIdx, auto LastIdx, typename Func>
627 constexpr void each_ext(Func func) {
628 static_assert(LastIdx >= FirstIdx);
629 const auto Iters = LastIdx - FirstIdx;
630 detail::each_impl<FirstIdx, Iters, Func>(func, std::make_integer_sequence<decltype(Iters), Iters>());
631 }
632
648 template <auto FirstIdx, auto LastIdx, auto Inc, typename Func>
649 constexpr void each_ext(Func func) {
650 if constexpr (FirstIdx < LastIdx) {
651 if constexpr (std::is_invocable_v<Func&&, std::integral_constant<decltype(FirstIdx), FirstIdx>>)
652 func(std::integral_constant<decltype(FirstIdx), FirstIdx>());
653 else
654 func();
655
656 each_ext<FirstIdx + Inc, LastIdx, Inc>(func);
657 }
658 }
659
670 template <typename Func, typename... Args>
671 constexpr void each_pack(Func func, Args&&... args) {
672 (func(GAIA_FWD(args)), ...);
673 }
674
688 template <typename Tuple, typename Func>
689 constexpr void each_tuple(Tuple&& tuple, Func func) {
690 using TTSize = uint32_t;
691 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
692 detail::each_tuple_impl<(TTSize)0>(GAIA_FWD(tuple), func, std::make_integer_sequence<TTSize, TSize>{});
693 }
694
710 template <typename Tuple, typename Func>
711 constexpr void each_tuple(Func func) {
712 using TTSize = uint32_t;
713 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
714 detail::each_tuple_impl<(TTSize)0, Tuple>(func, std::make_integer_sequence<TTSize, TSize>{});
715 }
716
730 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
731 constexpr void each_tuple_ext(Tuple&& tuple, Func func) {
732 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
733 static_assert(LastIdx >= FirstIdx);
734 static_assert(LastIdx <= TSize);
735 constexpr auto Iters = LastIdx - FirstIdx;
736 detail::each_tuple_impl<FirstIdx>(GAIA_FWD(tuple), func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
737 }
738
754 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
755 constexpr void each_tuple_ext(Func func) {
756 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
757 static_assert(LastIdx >= FirstIdx);
758 static_assert(LastIdx <= TSize);
759 constexpr auto Iters = LastIdx - FirstIdx;
760 detail::each_tuple_impl<FirstIdx, Tuple>(func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
761 }
762
763 template <typename InputIt, typename Func>
764 constexpr Func each(InputIt first, InputIt last, Func func) {
765 for (; first != last; ++first)
766 func(*first);
767 return func;
768 }
769
770 template <typename C, typename Func>
771 constexpr auto each(const C& arr, Func func) {
772 return each(arr.begin(), arr.end(), func);
773 }
774
775 //----------------------------------------------------------------------
776 // Lookups
777 //----------------------------------------------------------------------
778
779 template <typename InputIt, typename T>
780 constexpr InputIt find(InputIt first, InputIt last, const T& value) {
781 if constexpr (std::is_pointer_v<InputIt>) {
782 auto size = distance(first, last);
783 for (decltype(size) i = 0; i < size; ++i) {
784 if (first[i] == value)
785 return &first[i];
786 }
787 } else if constexpr (is_random_iter_v<InputIt>) {
788 auto size = distance(first, last);
789 for (decltype(size) i = 0; i < size; ++i) {
790 if (*(first[i]) == value)
791 return first[i];
792 }
793 } else {
794 for (; first != last; ++first) {
795 if (*first == value)
796 return first;
797 }
798 }
799 return last;
800 }
801
802 template <typename C, typename V>
803 constexpr auto find(const C& arr, const V& item) {
804 if constexpr (has_func_find<C>::value)
805 return arr.find(item);
806 else
807 return core::find(arr.begin(), arr.end(), item);
808 }
809
810 template <typename InputIt, typename Func>
811 constexpr InputIt find_if(InputIt first, InputIt last, Func func) {
812 if constexpr (std::is_pointer_v<InputIt>) {
813 auto size = distance(first, last);
814 for (decltype(size) i = 0; i < size; ++i) {
815 if (func(first[i]))
816 return &first[i];
817 }
818 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
819 auto size = distance(first, last);
820 for (decltype(size) i = 0; i < size; ++i) {
821 if (func(*(first[i])))
822 return first[i];
823 }
824 } else {
825 for (; first != last; ++first) {
826 if (func(*first))
827 return first;
828 }
829 }
830 return last;
831 }
832
833 template <typename UnaryPredicate, typename C>
834 constexpr auto find_if(const C& arr, UnaryPredicate predicate) {
835 if constexpr (has_func_find_if<C, UnaryPredicate>::value)
836 return arr.find_id(predicate);
837 else
838 return core::find_if(arr.begin(), arr.end(), predicate);
839 }
840
841 template <typename InputIt, typename Func>
842 constexpr InputIt find_if_not(InputIt first, InputIt last, Func func) {
843 if constexpr (std::is_pointer_v<InputIt>) {
844 auto size = distance(first, last);
845 for (decltype(size) i = 0; i < size; ++i) {
846 if (!func(first[i]))
847 return &first[i];
848 }
849 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
850 auto size = distance(first, last);
851 for (decltype(size) i = 0; i < size; ++i) {
852 if (!func(*(first[i])))
853 return first[i];
854 }
855 } else {
856 for (; first != last; ++first) {
857 if (!func(*first))
858 return first;
859 }
860 }
861 return last;
862 }
863
864 template <typename UnaryPredicate, typename C>
865 constexpr auto find_if_not(const C& arr, UnaryPredicate predicate) {
866 if constexpr (has_func_find_if_not<C, UnaryPredicate>::value)
867 return arr.find_if_not(predicate);
868 else
869 return core::find_if_not(arr.begin(), arr.end(), predicate);
870 }
871
872 //----------------------------------------------------------------------
873
874 template <typename C, typename V>
875 constexpr bool has(const C& arr, const V& item) {
876 const auto it = find(arr, item);
877 return it != arr.end();
878 }
879
880 template <typename UnaryPredicate, typename C>
881 constexpr bool has_if(const C& arr, UnaryPredicate predicate) {
882 const auto it = find_if(arr, predicate);
883 return it != arr.end();
884 }
885
886 //----------------------------------------------------------------------
887
888 template <typename C>
889 constexpr auto get_index(const C& arr, typename C::const_reference item) {
890 const auto it = find(arr, item);
891 if (it == arr.end())
892 return BadIndex;
893
894 return (decltype(BadIndex))core::distance(arr.begin(), it);
895 }
896
897 template <typename C>
898 constexpr auto get_index_unsafe(const C& arr, typename C::const_reference item) {
899 return (decltype(BadIndex))core::distance(arr.begin(), find(arr, item));
900 }
901
902 template <typename UnaryPredicate, typename C>
903 constexpr auto get_index_if(const C& arr, UnaryPredicate predicate) {
904 const auto it = find_if(arr, predicate);
905 if (it == arr.end())
906 return BadIndex;
907
908 return (decltype(BadIndex))core::distance(arr.begin(), it);
909 }
910
911 template <typename UnaryPredicate, typename C>
912 constexpr auto get_index_if_unsafe(const C& arr, UnaryPredicate predicate) {
913 return (decltype(BadIndex))core::distance(arr.begin(), find_if(arr, predicate));
914 }
915
916 //----------------------------------------------------------------------
917 // Erasure
918 //----------------------------------------------------------------------
919
927 template <typename C>
928 void swap_erase_unsafe(C& arr, typename C::size_type idx) {
929 GAIA_ASSERT(idx < arr.size());
930
931 if (idx + 1 != arr.size())
932 arr[idx] = arr[arr.size() - 1];
933
934 arr.pop_back();
935 }
936
942 // to sort the array.
943 template <typename C>
944 void swap_erase(C& arr, typename C::size_type idx) {
945 if (idx >= arr.size())
946 return;
947
948 if (idx + 1 != arr.size())
949 arr[idx] = arr[arr.size() - 1];
950
951 arr.pop_back();
952 }
953
954 //----------------------------------------------------------------------
955 // Comparison
956 //----------------------------------------------------------------------
957
958 template <typename T>
959 struct equal_to {
960 constexpr bool operator()(const T& lhs, const T& rhs) const {
961 return lhs == rhs;
962 }
963 };
964
965 template <typename T>
966 struct is_smaller {
967 constexpr bool operator()(const T& lhs, const T& rhs) const {
968 return lhs < rhs;
969 }
970 };
971
972 template <typename T>
973 struct is_smaller_or_equal {
974 constexpr bool operator()(const T& lhs, const T& rhs) const {
975 return lhs <= rhs;
976 }
977 };
978
979 template <typename T>
980 struct is_greater {
981 constexpr bool operator()(const T& lhs, const T& rhs) const {
982 return lhs > rhs;
983 }
984 };
985
986 //----------------------------------------------------------------------
987 // Sorting
988 //----------------------------------------------------------------------
989
990 namespace detail {
991 template <typename Container, typename TCmpFunc>
992 int quick_sort_partition(Container& arr, int low, int high, TCmpFunc cmpFunc) {
993 const auto& pivot = arr[(uint32_t)high];
994 int i = low - 1;
995 for (int j = low; j <= high - 1; ++j) {
996 if (cmpFunc(arr[(uint32_t)j], pivot))
997 core::swap(arr[(uint32_t)++i], arr[(uint32_t)j]);
998 }
999 core::swap(arr[(uint32_t)++i], arr[(uint32_t)high]);
1000 return i;
1001 }
1002
1003 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1004 int quick_sort_partition(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1005 const auto& pivot = arr[(uint32_t)high];
1006 int i = low - 1;
1007 for (int j = low; j <= high - 1; ++j) {
1008 if (cmpFunc(arr[(uint32_t)j], pivot))
1009 swapFunc((uint32_t)++i, (uint32_t)j);
1010 }
1011 swapFunc((uint32_t)++i, (uint32_t)high);
1012 return i;
1013 }
1014
1015 template <typename T, typename TCmpFunc>
1016 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc) {
1017 const auto n = (uint32_t)(end - beg);
1018 if (n <= 1) {
1019 // Nothing to sort with just one item
1020 } else if (n == 2) {
1021 swap_if(beg, 0, 1, cmpFunc);
1022 } else if (n == 3) {
1023 swap_if(beg, 1, 2, cmpFunc);
1024 swap_if(beg, 0, 2, cmpFunc);
1025 swap_if(beg, 0, 1, cmpFunc);
1026 } else if (n == 4) {
1027 swap_if(beg, 0, 1, cmpFunc);
1028 swap_if(beg, 2, 3, cmpFunc);
1029
1030 swap_if(beg, 0, 2, cmpFunc);
1031 swap_if(beg, 1, 3, cmpFunc);
1032
1033 swap_if(beg, 1, 2, cmpFunc);
1034 } else if (n == 5) {
1035 swap_if(beg, 0, 1, cmpFunc);
1036 swap_if(beg, 3, 4, cmpFunc);
1037
1038 swap_if(beg, 2, 4, cmpFunc);
1039
1040 swap_if(beg, 2, 3, cmpFunc);
1041 swap_if(beg, 1, 4, cmpFunc);
1042
1043 swap_if(beg, 0, 3, cmpFunc);
1044
1045 swap_if(beg, 0, 2, cmpFunc);
1046 swap_if(beg, 1, 3, cmpFunc);
1047
1048 swap_if(beg, 1, 2, cmpFunc);
1049 } else if (n == 6) {
1050 swap_if(beg, 1, 2, cmpFunc);
1051 swap_if(beg, 4, 5, cmpFunc);
1052
1053 swap_if(beg, 0, 2, cmpFunc);
1054 swap_if(beg, 3, 5, cmpFunc);
1055
1056 swap_if(beg, 0, 1, cmpFunc);
1057 swap_if(beg, 3, 4, cmpFunc);
1058 swap_if(beg, 2, 5, cmpFunc);
1059
1060 swap_if(beg, 0, 3, cmpFunc);
1061 swap_if(beg, 1, 4, cmpFunc);
1062
1063 swap_if(beg, 2, 4, cmpFunc);
1064 swap_if(beg, 1, 3, cmpFunc);
1065
1066 swap_if(beg, 2, 3, cmpFunc);
1067 } else if (n == 7) {
1068 swap_if(beg, 1, 2, cmpFunc);
1069 swap_if(beg, 3, 4, cmpFunc);
1070 swap_if(beg, 5, 6, cmpFunc);
1071
1072 swap_if(beg, 0, 2, cmpFunc);
1073 swap_if(beg, 3, 5, cmpFunc);
1074 swap_if(beg, 4, 6, cmpFunc);
1075
1076 swap_if(beg, 0, 1, cmpFunc);
1077 swap_if(beg, 4, 5, cmpFunc);
1078 swap_if(beg, 2, 6, cmpFunc);
1079
1080 swap_if(beg, 0, 4, cmpFunc);
1081 swap_if(beg, 1, 5, cmpFunc);
1082
1083 swap_if(beg, 0, 3, cmpFunc);
1084 swap_if(beg, 2, 5, cmpFunc);
1085
1086 swap_if(beg, 1, 3, cmpFunc);
1087 swap_if(beg, 2, 4, cmpFunc);
1088
1089 swap_if(beg, 2, 3, cmpFunc);
1090 } else if (n == 8) {
1091 swap_if(beg, 0, 1, cmpFunc);
1092 swap_if(beg, 2, 3, cmpFunc);
1093 swap_if(beg, 4, 5, cmpFunc);
1094 swap_if(beg, 6, 7, cmpFunc);
1095
1096 swap_if(beg, 0, 2, cmpFunc);
1097 swap_if(beg, 1, 3, cmpFunc);
1098 swap_if(beg, 4, 6, cmpFunc);
1099 swap_if(beg, 5, 7, cmpFunc);
1100
1101 swap_if(beg, 1, 2, cmpFunc);
1102 swap_if(beg, 5, 6, cmpFunc);
1103 swap_if(beg, 0, 4, cmpFunc);
1104 swap_if(beg, 3, 7, cmpFunc);
1105
1106 swap_if(beg, 1, 5, cmpFunc);
1107 swap_if(beg, 2, 6, cmpFunc);
1108
1109 swap_if(beg, 1, 4, cmpFunc);
1110 swap_if(beg, 3, 6, cmpFunc);
1111
1112 swap_if(beg, 2, 4, cmpFunc);
1113 swap_if(beg, 3, 5, cmpFunc);
1114
1115 swap_if(beg, 3, 4, cmpFunc);
1116 } else if (n == 9) {
1117 swap_if(beg, 0, 1, cmpFunc);
1118 swap_if(beg, 3, 4, cmpFunc);
1119 swap_if(beg, 6, 7, cmpFunc);
1120 swap_if(beg, 1, 2, cmpFunc);
1121 swap_if(beg, 4, 5, cmpFunc);
1122 swap_if(beg, 7, 8, cmpFunc);
1123 swap_if(beg, 0, 1, cmpFunc);
1124 swap_if(beg, 3, 4, cmpFunc);
1125 swap_if(beg, 6, 7, cmpFunc);
1126 swap_if(beg, 0, 3, cmpFunc);
1127 swap_if(beg, 3, 6, cmpFunc);
1128 swap_if(beg, 0, 3, cmpFunc);
1129 swap_if(beg, 1, 4, cmpFunc);
1130 swap_if(beg, 4, 7, cmpFunc);
1131 swap_if(beg, 1, 4, cmpFunc);
1132 swap_if(beg, 2, 5, cmpFunc);
1133 swap_if(beg, 5, 8, cmpFunc);
1134 swap_if(beg, 2, 5, cmpFunc);
1135 swap_if(beg, 1, 3, cmpFunc);
1136 swap_if(beg, 5, 7, cmpFunc);
1137 swap_if(beg, 2, 6, cmpFunc);
1138 swap_if(beg, 4, 6, cmpFunc);
1139 swap_if(beg, 2, 4, cmpFunc);
1140 swap_if(beg, 2, 3, cmpFunc);
1141 swap_if(beg, 5, 6, cmpFunc);
1142 } else if (n == 10) {
1143 swap_if(beg, 0, 8, cmpFunc);
1144 swap_if(beg, 1, 9, cmpFunc);
1145 swap_if(beg, 2, 7, cmpFunc);
1146 swap_if(beg, 3, 6, cmpFunc);
1147 swap_if(beg, 4, 5, cmpFunc);
1148
1149 swap_if(beg, 0, 2, cmpFunc);
1150 swap_if(beg, 1, 3, cmpFunc);
1151 swap_if(beg, 4, 8, cmpFunc);
1152 swap_if(beg, 5, 7, cmpFunc);
1153 swap_if(beg, 6, 9, cmpFunc);
1154
1155 swap_if(beg, 0, 4, cmpFunc);
1156 swap_if(beg, 1, 5, cmpFunc);
1157 swap_if(beg, 2, 6, cmpFunc);
1158 swap_if(beg, 3, 7, cmpFunc);
1159
1160 swap_if(beg, 0, 1, cmpFunc);
1161 swap_if(beg, 2, 3, cmpFunc);
1162 swap_if(beg, 4, 6, cmpFunc);
1163 swap_if(beg, 5, 9, cmpFunc);
1164 swap_if(beg, 7, 8, cmpFunc);
1165
1166 swap_if(beg, 1, 2, cmpFunc);
1167 swap_if(beg, 3, 5, cmpFunc);
1168 swap_if(beg, 6, 7, cmpFunc);
1169 swap_if(beg, 8, 9, cmpFunc);
1170
1171 swap_if(beg, 2, 4, cmpFunc);
1172 swap_if(beg, 3, 6, cmpFunc);
1173 swap_if(beg, 5, 8, cmpFunc);
1174
1175 swap_if(beg, 1, 2, cmpFunc);
1176 swap_if(beg, 3, 4, cmpFunc);
1177 swap_if(beg, 5, 6, cmpFunc);
1178 swap_if(beg, 7, 8, cmpFunc);
1179 } else if (n <= 32) {
1180 for (uint32_t i = 0; i < n - 1; ++i)
1181 for (uint32_t j = 0; j < n - i - 1; ++j)
1182 swap_if(beg, j, j + 1, cmpFunc);
1183 }
1184
1185 return n <= 32;
1186 }
1187
1188 template <typename T, typename TCmpFunc, typename TSwapFunc>
1189 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1190 const auto n = (uint32_t)(end - beg);
1191 if (n <= 1) {
1192 // Nothing to sort with just one item
1193 } else if (n == 2) {
1194 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1195 } else if (n == 3) {
1196 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1197 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1198 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1199 } else if (n == 4) {
1200 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1201 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1202
1203 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1204 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1205
1206 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1207 } else if (n == 5) {
1208 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1209 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1210
1211 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1212
1213 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1214 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1215
1216 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1217
1218 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1219 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1220
1221 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1222 } else if (n == 6) {
1223 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1224 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1225
1226 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1227 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1228
1229 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1230 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1231 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1232
1233 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1234 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1235
1236 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1237 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1238
1239 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1240 } else if (n == 7) {
1241 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1242 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1243 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1244
1245 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1246 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1247 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1248
1249 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1250 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1251 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1252
1253 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
1254 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
1255
1256 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1257 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1258
1259 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1260 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1261
1262 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1263 } else if (n == 8) {
1264 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1265 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1266 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1267 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1268
1269 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1270 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1271 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1272 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
1273
1274 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1275 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1276 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
1277 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
1278
1279 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
1280 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1281
1282 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1283 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1284
1285 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1286 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1287
1288 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1289 } else if (n == 9) {
1290 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1291 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1292 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1293 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1294 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1295 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
1296 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1297 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1298 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1299 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1300 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1301 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
1302 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1303 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
1304 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
1305 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1306 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
1307 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
1308 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1309 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
1310 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1311 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1312 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1313 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1314 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1315 } else if (n == 10) {
1316 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
1317 try_swap_if(beg, 1, 9, cmpFunc, swapFunc);
1318 try_swap_if(beg, 2, 7, cmpFunc, swapFunc);
1319 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1320 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
1321
1322 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
1323 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
1324 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
1325 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
1326 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
1327
1328 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
1329 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
1330 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
1331 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
1332
1333 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
1334 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
1335 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
1336 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
1337 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
1338
1339 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1340 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
1341 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
1342 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
1343
1344 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
1345 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
1346 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
1347
1348 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
1349 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
1350 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
1351 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
1352 } else if (n <= 32) {
1353 for (uint32_t i = 0; i < n - 1; ++i)
1354 for (uint32_t j = 0; j < n - i - 1; ++j)
1355 try_swap_if(beg, j, j + 1, cmpFunc, swapFunc);
1356 }
1357
1358 return n <= 32;
1359 }
1360 } // namespace detail
1361
1362 template <typename Container, typename TCmpFunc>
1363 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc) {
1364 if (low >= high)
1365 return;
1366 auto pos = detail::quick_sort_partition(arr, low, high, cmpFunc);
1367 quick_sort(arr, low, pos - 1, cmpFunc);
1368 quick_sort(arr, pos + 1, high, cmpFunc);
1369 }
1370
1371 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1372 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1373 if (low >= high)
1374 return;
1375 auto pos = detail::quick_sort_partition(arr, low, high, cmpFunc, swapFunc);
1376 quick_sort(arr, low, pos - 1, cmpFunc, swapFunc);
1377 quick_sort(arr, pos + 1, high, cmpFunc, swapFunc);
1378 }
1379
1394 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1395 void
1396 quick_sort_stack(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc, uint32_t maxStackSize) {
1397 GAIA_ASSERT(high < (int)arr.size() && "quick_sort_stack: 'high' has to be smaller than the container size.");
1398 GAIA_ASSERT(
1399 (uint32_t)arr.size() <= maxStackSize && "quick_sort_stack: used with too large input array. Stack overflow.");
1400
1401 struct Range {
1402 int low, high;
1403 };
1404
1405 auto* stack = (Range*)alloca(sizeof(Range) * maxStackSize);
1406 GAIA_ASSERT(stack != nullptr && "quick_sort_stack: failed to allocate stack memory.");
1407 uint32_t sp = 0; // stack pointer
1408 stack[sp++] = {low, high};
1409
1410 auto median_of_three = [&](int a, int b, int c) {
1411 if (cmpFunc(arr[a], arr[b])) {
1412 if (cmpFunc(arr[b], arr[c]))
1413 return b;
1414 if (cmpFunc(arr[a], arr[c]))
1415 return c;
1416 return a;
1417 }
1418
1419 if (cmpFunc(arr[a], arr[c]))
1420 return a;
1421 if (cmpFunc(arr[b], arr[c]))
1422 return c;
1423 return b;
1424 };
1425
1426 while (sp > 0) {
1427 const Range r = stack[--sp];
1428 if (r.low >= r.high)
1429 continue;
1430
1431 // Use optimized sort for small partitions
1432 const auto size = r.high - r.low + 1;
1433 if (size <= 32) {
1434 auto* base = &arr[r.low];
1435 detail::sort_nwk(base, base + size, cmpFunc, [&](uint32_t i, uint32_t j) {
1436 swapFunc(r.low + i, r.low + j);
1437 });
1438 continue;
1439 }
1440
1441 // Median-of-three pivot selection
1442 int mid = r.low + ((r.high - r.low) >> 1);
1443 int pivotIdx = median_of_three(r.low, mid, r.high);
1444 swapFunc(pivotIdx, r.high);
1445
1446 const auto& pivot = arr[r.high];
1447 int i = r.low - 1;
1448 for (int j = r.low; j < r.high; ++j) {
1449 if (cmpFunc(arr[j], pivot))
1450 swapFunc(++i, j);
1451 }
1452 swapFunc(++i, r.high);
1453
1454 // Push smaller partition first to reduce max stack usage
1455 if (i - 1 - r.low > r.high - (i + 1)) {
1456 if (r.low < i - 1)
1457 stack[sp++] = {r.low, i - 1};
1458 if (i + 1 < r.high)
1459 stack[sp++] = {i + 1, r.high};
1460 } else {
1461 if (i + 1 < r.high)
1462 stack[sp++] = {i + 1, r.high};
1463 if (r.low < i - 1)
1464 stack[sp++] = {r.low, i - 1};
1465 }
1466 }
1467 }
1468
1482 template <typename Container, typename TCmpFunc>
1483 void quick_sort_stack(Container& arr, int low, int high, TCmpFunc cmpFunc, uint32_t maxStackSize) {
1484 quick_sort_stack(
1485 arr, low, high, cmpFunc,
1486 [&arr](uint32_t a, uint32_t b) {
1487 core::swap(arr[a], arr[b]);
1488 },
1489 maxStackSize);
1490 }
1491
1501 template <typename T, typename TCmpFunc>
1502 void sort(T* beg, T* end, TCmpFunc cmpFunc) {
1503 const auto n = (uintptr_t)(end - beg);
1504 if (detail::sort_nwk(beg, end, cmpFunc))
1505 return;
1506
1507 quick_sort(beg, 0, (int)n - 1, cmpFunc);
1508 }
1509
1510 template <typename C, typename TCmpFunc>
1511 void sort(C& c, TCmpFunc cmpFunc) {
1512 sort(c.begin(), c.end(), cmpFunc);
1513 }
1514
1527 template <typename T, typename TCmpFunc, typename TSwapFunc>
1528 void sort(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1529 const auto n = (uintptr_t)(end - beg);
1530 if (detail::sort_nwk(beg, end, cmpFunc, swapFunc))
1531 return;
1532
1533 quick_sort(beg, 0, (int)n - 1, cmpFunc, swapFunc);
1534 }
1535
1536 template <typename C, typename TCmpFunc, typename TSwapFunc>
1537 void sort(C& c, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1538 sort(c.begin(), c.end(), cmpFunc, swapFunc);
1539 }
1540 } // namespace core
1541} // 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:959
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:980
gaia::core::is_smaller_or_equal
Definition utility.h:973
gaia::core::is_smaller
Definition utility.h:966
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