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 {
20 constexpr uint32_t BadIndex = uint32_t(-1);
21
22#if GAIA_COMPILER_MSVC || GAIA_PLATFORM_WINDOWS
23 #define GAIA_STRCPY(var, max_len, text) \
24 strncpy_s((var), (text), (max_len)); \
25 (var)[(max_len) - 1] = 0;
26 #define GAIA_STRFMT(var, max_len, fmt, ...) sprintf_s((var), (max_len), fmt, __VA_ARGS__)
27 #define GAIA_STRLEN(var, max_len) strnlen_s((var), (max_len))
28#else
29 #define GAIA_STRCPY(var, max_len, text) \
30 { \
31 strncpy((var), (text), (max_len)); \
32 (var)[(max_len) - 1] = 0; \
33 }
34 #define GAIA_STRFMT(var, max_len, fmt, ...) snprintf((var), (max_len), fmt, __VA_ARGS__)
35 #define GAIA_STRLEN(var, max_len) strnlen((var), (max_len))
36#endif
37
38 namespace core {
39 namespace detail {
42 template <class T>
43 struct rem_rp {
45 using type = std::remove_reference_t<std::remove_pointer_t<T>>;
46 };
47
50 template <typename T>
51 struct is_mut:
52 std::bool_constant<
53 !std::is_const_v<typename rem_rp<T>::type> &&
54 (std::is_pointer<T>::value || std::is_reference<T>::value)> {};
55
59 template <typename Type, typename SizeProbe = size_t>
60 struct is_complete: std::false_type {};
61
64 template <typename T>
65 struct is_complete<T, decltype(sizeof(T))>: std::true_type {};
66
71 template <typename C>
72 constexpr auto size(C& c) noexcept -> decltype(c.size()) {
73 return c.size();
74 }
79 template <typename C>
80 constexpr auto size(const C& c) noexcept -> decltype(c.size()) {
81 return c.size();
82 }
87 template <typename T, auto N>
88 constexpr auto size(const T (&)[N]) noexcept {
89 return N;
90 }
91
96 template <typename C>
97 constexpr auto data(C& c) noexcept -> decltype(c.data()) {
98 return c.data();
99 }
104 template <typename C>
105 constexpr auto data(const C& c) noexcept -> decltype(c.data()) {
106 return c.data();
107 }
113 template <typename T, auto N>
114 constexpr T* data(T (&array)[N]) noexcept {
115 return array;
116 }
121 template <typename E>
122 constexpr const E* data(std::initializer_list<E> il) noexcept {
123 return il.begin();
124 }
125 } // namespace detail
126
128 struct zero_t {
130 explicit constexpr zero_t() = default;
131 };
133 inline constexpr zero_t zero{};
134
137 template <typename T>
138 using rem_rp_t = typename detail::rem_rp<T>::type;
139
142 template <typename T>
143 inline constexpr bool is_mut_v = detail::is_mut<T>::value;
144
147 template <typename T>
148 using raw_t = typename std::decay_t<std::remove_pointer_t<T>>;
149
152 template <typename T>
153 inline constexpr bool is_raw_v = std::is_same_v<T, raw_t<T>> && !std::is_array_v<T>;
154
157 template <typename T>
158 inline constexpr bool is_complete_v = detail::is_complete<T>::value;
159
164 template <typename T>
165 constexpr T* addressof(T& obj) noexcept {
166 return &obj;
167 }
168
171 template <typename T>
172 const T* addressof(const T&&) = delete;
173
178 template <typename T>
179 constexpr bool check_alignment(const T* ptr) noexcept {
180 return (reinterpret_cast<uintptr_t>(ptr)) % alignof(T) == 0;
181 }
182
185 template <typename T>
186 struct lock_scope {
188 T& m_ctx;
189
192 lock_scope(T& ctx): m_ctx(ctx) {
193 ctx.lock();
194 }
196 ~lock_scope() {
197 m_ctx.unlock();
198 }
199
201 lock_scope(const lock_scope&) = delete;
203 lock_scope& operator=(const lock_scope&) = delete;
205 lock_scope(lock_scope&&) = delete;
207 lock_scope& operator=(lock_scope&&) = delete;
208 };
209
210 //----------------------------------------------------------------------
211 // Container identification
212 //----------------------------------------------------------------------
213
217 template <typename T, typename Probe = void>
218 struct has_data_size: std::false_type {};
219
222 template <typename T>
223 struct has_data_size<
224 T, std::void_t< //
225 decltype(detail::data(std::declval<T>())), //
226 decltype(detail::size(std::declval<T>())) //
227 >>: std::true_type {};
228
232 template <typename T, typename Probe = void>
233 struct has_size_begin_end: std::false_type {};
234
237 template <typename T>
238 struct has_size_begin_end<
239 T, std::void_t< //
240 decltype(std::declval<T>().begin()), //
241 decltype(std::declval<T>().end()), //
242 decltype(detail::size(std::declval<T>())) //
243 >>: std::true_type {};
244
245 //----------------------------------------------------------------------
246 // Bit-byte conversion
247 //----------------------------------------------------------------------
248
253 template <typename T>
254 constexpr T as_bits(T value) {
255 static_assert(std::is_integral_v<T>);
256 return value * (T)8;
257 }
258
263 template <typename T>
264 constexpr T as_bytes(T value) {
265 static_assert(std::is_integral_v<T>);
266 return value / (T)8;
267 }
268
269 //----------------------------------------------------------------------
270 // Memory size helpers
271 //----------------------------------------------------------------------
272
277 template <typename T>
278 constexpr uint32_t count_bits(T number) {
279 uint32_t bits_needed = 0;
280 while (number > 0U) {
281 number >>= 1U;
282 ++bits_needed;
283 }
284 return bits_needed;
285 }
286
291 template <typename T>
292 constexpr bool is_pow2(T number) {
293 static_assert(std::is_integral<T>::value, "is_pow2 must be used with integer types");
294
295 return (number & (number - 1)) == 0;
296 }
297
302 template <typename T>
303 constexpr T closest_pow2(T number) {
304 static_assert(std::is_integral<T>::value, "closest_pow2 must be used with integer types");
305
306 if (is_pow2(number))
307 return number;
308
309 // Collapse all bits below the highest set bit
310 number |= number >> 1;
311 number |= number >> 2;
312 number |= number >> 4;
313 if constexpr (sizeof(T) > 1)
314 number |= number >> 8;
315 if constexpr (sizeof(T) > 2)
316 number |= number >> 16;
317 if constexpr (sizeof(T) > 4)
318 number |= number >> 32;
319
320 // The result is now one less than the next power of two, so shift back
321 return number - (number >> 1);
322 }
323
324 //----------------------------------------------------------------------
325 // Element construction / destruction
326 //----------------------------------------------------------------------
327
331 template <typename T>
332 void call_ctor_raw(T* pData) {
333 GAIA_ASSERT(pData != nullptr);
334 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T;
335 }
336
341 template <typename T>
342 void call_ctor_raw_n(T* pData, size_t cnt) {
343 GAIA_ASSERT(pData != nullptr);
344 for (size_t i = 0; i < cnt; ++i) {
345 auto* ptr = pData + i;
346 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T;
347 }
348 }
349
353 template <typename T>
354 void call_ctor_val(T* pData) {
355 GAIA_ASSERT(pData != nullptr);
356 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T();
357 }
358
363 template <typename T>
364 void call_ctor_val_n(T* pData, size_t cnt) {
365 GAIA_ASSERT(pData != nullptr);
366 for (size_t i = 0; i < cnt; ++i) {
367 auto* ptr = pData + i;
368 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T();
369 }
370 }
371
376 template <typename T>
377 void call_ctor([[maybe_unused]] T* pData) {
378 GAIA_ASSERT(pData != nullptr);
379 if constexpr (!std::is_trivially_constructible_v<T>) {
380 (void)::new (pData) T();
381 }
382 }
383
388 template <typename T>
389 void call_ctor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
390 GAIA_ASSERT(pData != nullptr);
391 if constexpr (!std::is_trivially_constructible_v<T>) {
392 for (size_t i = 0; i < cnt; ++i)
393 (void)::new (pData + i) T();
394 }
395 }
396
402 template <typename T, typename... Args>
403 void call_ctor(T* pData, Args&&... args) {
404 GAIA_ASSERT(pData != nullptr);
405 if constexpr (std::is_constructible_v<T, Args...>)
406 (void)::new (pData) T(GAIA_FWD(args)...);
407 else
408 (void)::new (pData) T{GAIA_FWD(args)...};
409 }
410
415 template <typename T>
416 void call_dtor([[maybe_unused]] T* pData) {
417 GAIA_ASSERT(pData != nullptr);
418 if constexpr (!std::is_trivially_destructible_v<T>) {
419 pData->~T();
420 }
421 }
422
427 template <typename T>
428 void call_dtor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
429 GAIA_ASSERT(pData != nullptr);
430 if constexpr (!std::is_trivially_destructible_v<T>) {
431 for (size_t i = 0; i < cnt; ++i)
432 pData[i].~T();
433 }
434 }
435
436 //----------------------------------------------------------------------
437 // Element swapping
438 //----------------------------------------------------------------------
439
444 template <typename T>
445 constexpr void swap(T& left, T& right) {
446 T tmp = GAIA_MOV(left);
447 left = GAIA_MOV(right);
448 right = GAIA_MOV(tmp);
449 }
450
458 template <typename T, typename TCmpFunc>
459 constexpr void swap_if(T* c, size_t lhs, size_t rhs, TCmpFunc cmpFunc) noexcept {
460 if (!cmpFunc(c[lhs], c[rhs]))
461 core::swap(c[lhs], c[rhs]);
462 }
463
470 template <typename T, typename TCmpFunc>
471 constexpr void swap_if(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
472 if (!cmpFunc(lhs, rhs))
473 core::swap(lhs, rhs);
474 }
475
482 template <typename T, typename TCmpFunc>
483 constexpr void swap_if_not(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
484 if (cmpFunc(lhs, rhs))
485 core::swap(lhs, rhs);
486 }
487
497 template <typename T, typename TCmpFunc, typename TSwapFunc>
498 constexpr void try_swap_if(T* c, uint32_t lhs, uint32_t rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
499 if (!cmpFunc(c[lhs], c[rhs]))
500 swapFunc(lhs, rhs);
501 }
502
512 template <typename C, typename TCmpFunc, typename TSwapFunc>
513 constexpr void try_swap_if(
514 C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
515 if (!cmpFunc(c[lhs], c[rhs]))
516 swapFunc(lhs, rhs);
517 }
518
528 template <typename C, typename TCmpFunc, typename TSwapFunc>
529 constexpr void try_swap_if_not(
530 C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
531 if (cmpFunc(c[lhs], c[rhs]))
532 swapFunc(lhs, rhs);
533 }
534
535 //----------------------------------------------------------------------
536 // Value filling
537 //----------------------------------------------------------------------
538
545 template <class ForwardIt, class T>
546 constexpr void fill(ForwardIt first, ForwardIt last, const T& value) {
547 for (; first != last; ++first) {
548 *first = value;
549 }
550 }
551
552 //----------------------------------------------------------------------
553 // Value range checking
554 //----------------------------------------------------------------------
555
561 template <class T>
562 constexpr const T& get_min(const T& a, const T& b) {
563 return (b < a) ? b : a;
564 }
565
571 template <class T>
572 constexpr const T& get_max(const T& a, const T& b) {
573 return (b > a) ? b : a;
574 }
575
576 //----------------------------------------------------------------------
577 // Checking if a template arg is unique among the rest
578 //----------------------------------------------------------------------
579
582 template <typename... Types>
583 inline constexpr auto is_unique = std::true_type{};
584
588 template <typename T, typename... Rest>
589 inline constexpr auto is_unique<T, Rest...> =
590 std::bool_constant<(!std::is_same_v<T, Rest> && ...) && is_unique<Rest...>>{};
591
592 namespace detail {
595 template <typename T>
596 struct type_identity {
598 using type = T;
599 };
600 } // namespace detail
601
605 template <typename T, typename... Ts>
606 struct unique: detail::type_identity<T> {}; // TODO: In C++20 we could use std::type_identity
607
612 template <typename... Ts, typename U, typename... Us>
613 struct unique<std::tuple<Ts...>, U, Us...>:
614 std::conditional_t<
615 (std::is_same_v<U, Ts> || ...), unique<std::tuple<Ts...>, Us...>, unique<std::tuple<Ts..., U>, Us...>> {};
616
619 template <typename... Ts>
620 using unique_tuple = typename unique<std::tuple<>, Ts...>::type;
621
622 //----------------------------------------------------------------------
623 // Calculating total size of all types of tuple
624 //----------------------------------------------------------------------
625
630 template <typename... Args>
631 constexpr unsigned get_args_size(std::tuple<Args...> const& tuple) {
632 (void)tuple;
633 return (sizeof(Args) + ...);
634 }
635
636 //----------------------------------------------------------------------
637 // Function arguments type checks
638 //----------------------------------------------------------------------
639
642 template <typename... Type>
643 struct func_type_list {};
644
650 template <typename Class, typename Ret, typename... Args>
651 func_type_list<Args...> func_args(Ret (Class::*)(Args...) const);
652
653 //----------------------------------------------------------------------
654 // Member function checks
655 //----------------------------------------------------------------------
656
657#if __cpp_concepts
658 #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name) \
659 template <typename T, typename... Args> \
660 concept has_mfunc_check_##function_name = requires(T&& t, Args&&... args) { t.function_name(GAIA_FWD(args)...); }; \
661 \
662 template <typename T, typename... Args> \
663 struct has_func_##function_name { \
664 static constexpr bool value = has_mfunc_check_##function_name<T, Args...>; \
665 }
666#else
667 namespace detail {
673 template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
674 struct member_func_checker {
676 using value_t = std::false_type;
678 using type = Default;
679 };
680
685 template <class Default, template <class...> class Op, class... Args>
686 struct member_func_checker<Default, std::void_t<Op<Args...>>, Op, Args...> {
688 using value_t = std::true_type;
690 using type = Op<Args...>;
691 };
692
694 struct member_func_none {
695 ~member_func_none() = delete;
696 member_func_none(member_func_none const&) = delete;
697 member_func_none(member_func_none&&) = delete;
698 void operator=(member_func_none const&) = delete;
699 void operator=(member_func_none&&) = delete;
700 };
701 } // namespace detail
702
706 template <template <class...> class Op, typename... Args>
707 using has_mfunc = typename detail::member_func_checker<detail::member_func_none, void, Op, Args...>::value_t;
708
709 #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name) \
710 template <typename T, typename... Args> \
711 using has_mfunc_check_##function_name = decltype(std::declval<T>().function_name(std::declval<Args>()...)); \
712 \
713 template <typename T, typename... Args> \
714 struct has_func_##function_name { \
715 static constexpr bool value = gaia::core::has_mfunc<has_mfunc_check_##function_name, T, Args...>::value; \
716 }
717#endif
718
719 GAIA_DEFINE_HAS_MEMBER_FUNC(find);
720 GAIA_DEFINE_HAS_MEMBER_FUNC(find_if);
721 GAIA_DEFINE_HAS_MEMBER_FUNC(find_if_not);
722
723 //----------------------------------------------------------------------
724 // Special function checks
725 //----------------------------------------------------------------------
726
727 namespace detail {
731 template <typename T>
732 constexpr auto has_mfunc_equals_check(int)
733 -> decltype(std::declval<T>().operator==(std::declval<T>()), std::true_type{});
738 template <typename T, typename... Args>
739 constexpr std::false_type has_mfunc_equals_check(...);
740
744 template <typename T>
745 constexpr auto has_ffunc_equals_check(int)
746 -> decltype(operator==(std::declval<T>(), std::declval<T>()), std::true_type{});
751 template <typename T, typename... Args>
752 constexpr std::false_type has_ffunc_equals_check(...);
753 } // namespace detail
754
757 template <typename T>
758 struct has_func_equals {
760 static constexpr bool value = decltype(detail::has_mfunc_equals_check<T>(0))::value;
761 };
762
765 template <typename T>
766 struct has_ffunc_equals {
768 static constexpr bool value = decltype(detail::has_ffunc_equals_check<T>(0))::value;
769 };
770
771 //----------------------------------------------------------------------
772 // Type helpers
773 //----------------------------------------------------------------------
774
777 template <typename... Type>
778 struct type_list {
780 using types = type_list;
782 static constexpr auto size = sizeof...(Type);
783 };
784
788 template <typename TypesA, typename TypesB>
789 struct type_list_concat;
790
794 template <typename... TypesA, typename... TypesB>
795 struct type_list_concat<type_list<TypesA...>, type_list<TypesB...>> {
797 using type = type_list<TypesA..., TypesB...>;
798 };
799
800 //----------------------------------------------------------------------
801 // Looping
802 //----------------------------------------------------------------------
803
804 namespace detail {
811 template <auto FirstIdx, auto Iters, typename Func, auto... Is>
812 constexpr void each_impl(Func func, std::integer_sequence<decltype(Iters), Is...> /*no_name*/) {
813 if constexpr ((std::is_invocable_v<Func&&, std::integral_constant<decltype(Is), Is>> && ...))
814 (func(std::integral_constant<decltype(Is), FirstIdx + Is>{}), ...);
815 else
816 (((void)Is, func()), ...);
817 }
818
825 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
826 void each_tuple_impl(Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
827 if constexpr (
828 (std::is_invocable_v<
829 Func&&, decltype(std::tuple_element_t<FirstIdx + Is, Tuple>{}),
830 std::integral_constant<decltype(FirstIdx), Is>> &&
831 ...))
832 // func(Args&& arg, uint32_t idx)
833 (func(
834 std::tuple_element_t<FirstIdx + Is, Tuple>{},
835 std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}),
836 ...);
837 else
838 // func(Args&& arg)
839 (func(std::tuple_element_t<FirstIdx + Is, Tuple>{}), ...);
840 }
841
849 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
850 void each_tuple_impl(Tuple&& tuple, Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
851 if constexpr (
852 (std::is_invocable_v<
853 Func&&, decltype(std::get<FirstIdx + Is>(tuple)), std::integral_constant<decltype(FirstIdx), Is>> &&
854 ...))
855 // func(Args&& arg, uint32_t idx)
856 (func(std::get<FirstIdx + Is>(tuple), std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}), ...);
857 else
858 // func(Args&& arg)
859 (func(std::get<FirstIdx + Is>(tuple)), ...);
860 }
861 } // namespace detail
862
879 template <auto Iters, typename Func>
880 constexpr void each(Func func) {
881 using TIters = decltype(Iters);
882 constexpr TIters First = 0;
883 detail::each_impl<First, Iters, Func>(func, std::make_integer_sequence<TIters, Iters>());
884 }
885
904 template <auto FirstIdx, auto LastIdx, typename Func>
905 constexpr void each_ext(Func func) {
906 static_assert(LastIdx >= FirstIdx);
907 const auto Iters = LastIdx - FirstIdx;
908 detail::each_impl<FirstIdx, Iters, Func>(func, std::make_integer_sequence<decltype(Iters), Iters>());
909 }
910
930 template <auto FirstIdx, auto LastIdx, auto Inc, typename Func>
931 constexpr void each_ext(Func func) {
932 if constexpr (FirstIdx < LastIdx) {
933 if constexpr (std::is_invocable_v<Func&&, std::integral_constant<decltype(FirstIdx), FirstIdx>>)
934 func(std::integral_constant<decltype(FirstIdx), FirstIdx>());
935 else
936 func();
937
938 each_ext<FirstIdx + Inc, LastIdx, Inc>(func);
939 }
940 }
941
956 template <typename Func, typename... Args>
957 constexpr void each_pack(Func func, Args&&... args) {
958 (func(GAIA_FWD(args)), ...);
959 }
960
978 template <typename Tuple, typename Func>
979 constexpr void each_tuple(Tuple&& tuple, Func func) {
980 using TTSize = uint32_t;
981 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
982 detail::each_tuple_impl<(TTSize)0>(GAIA_FWD(tuple), func, std::make_integer_sequence<TTSize, TSize>{});
983 }
984
1003 template <typename Tuple, typename Func>
1004 constexpr void each_tuple(Func func) {
1005 using TTSize = uint32_t;
1006 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
1007 detail::each_tuple_impl<(TTSize)0, Tuple>(func, std::make_integer_sequence<TTSize, TSize>{});
1008 }
1009
1029 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
1030 constexpr void each_tuple_ext(Tuple&& tuple, Func func) {
1031 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
1032 static_assert(LastIdx >= FirstIdx);
1033 static_assert(LastIdx <= TSize);
1034 constexpr auto Iters = LastIdx - FirstIdx;
1035 detail::each_tuple_impl<FirstIdx>(GAIA_FWD(tuple), func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
1036 }
1037
1058 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
1059 constexpr void each_tuple_ext(Func func) {
1060 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
1061 static_assert(LastIdx >= FirstIdx);
1062 static_assert(LastIdx <= TSize);
1063 constexpr auto Iters = LastIdx - FirstIdx;
1064 detail::each_tuple_impl<FirstIdx, Tuple>(func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
1065 }
1066
1074 template <typename InputIt, typename Func>
1075 constexpr Func each(InputIt first, InputIt last, Func func) {
1076 for (; first != last; ++first)
1077 func(*first);
1078 return func;
1079 }
1080
1087 template <typename C, typename Func>
1088 constexpr auto each(const C& arr, Func func) {
1089 return each(arr.begin(), arr.end(), func);
1090 }
1091
1092 //----------------------------------------------------------------------
1093 // Lookups
1094 //----------------------------------------------------------------------
1095
1103 template <typename InputIt, typename T>
1104 constexpr InputIt find(InputIt first, InputIt last, const T& value) {
1105 if constexpr (std::is_pointer_v<InputIt>) {
1106 auto size = distance(first, last);
1107 for (decltype(size) i = 0; i < size; ++i) {
1108 if (first[i] == value)
1109 return &first[i];
1110 }
1111 } else if constexpr (is_random_iter_v<InputIt>) {
1112 auto size = distance(first, last);
1113 for (decltype(size) i = 0; i < size; ++i) {
1114 if (*(first[i]) == value)
1115 return first[i];
1116 }
1117 } else {
1118 for (; first != last; ++first) {
1119 if (*first == value)
1120 return first;
1121 }
1122 }
1123 return last;
1124 }
1125
1132 template <typename C, typename V>
1133 constexpr auto find(const C& arr, const V& item) {
1134 if constexpr (has_func_find<C>::value)
1135 return arr.find(item);
1136 else
1137 return core::find(arr.begin(), arr.end(), item);
1138 }
1139
1147 template <typename InputIt, typename Func>
1148 constexpr InputIt find_if(InputIt first, InputIt last, Func func) {
1149 if constexpr (std::is_pointer_v<InputIt>) {
1150 auto size = distance(first, last);
1151 for (decltype(size) i = 0; i < size; ++i) {
1152 if (func(first[i]))
1153 return &first[i];
1154 }
1155 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
1156 auto size = distance(first, last);
1157 for (decltype(size) i = 0; i < size; ++i) {
1158 if (func(*(first[i])))
1159 return first[i];
1160 }
1161 } else {
1162 for (; first != last; ++first) {
1163 if (func(*first))
1164 return first;
1165 }
1166 }
1167 return last;
1168 }
1169
1176 template <typename UnaryPredicate, typename C>
1177 constexpr auto find_if(const C& arr, UnaryPredicate predicate) {
1178 if constexpr (has_func_find_if<C, UnaryPredicate>::value)
1179 return arr.find_id(predicate);
1180 else
1181 return core::find_if(arr.begin(), arr.end(), predicate);
1182 }
1183
1191 template <typename InputIt, typename Func>
1192 constexpr InputIt find_if_not(InputIt first, InputIt last, Func func) {
1193 if constexpr (std::is_pointer_v<InputIt>) {
1194 auto size = distance(first, last);
1195 for (decltype(size) i = 0; i < size; ++i) {
1196 if (!func(first[i]))
1197 return &first[i];
1198 }
1199 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
1200 auto size = distance(first, last);
1201 for (decltype(size) i = 0; i < size; ++i) {
1202 if (!func(*(first[i])))
1203 return first[i];
1204 }
1205 } else {
1206 for (; first != last; ++first) {
1207 if (!func(*first))
1208 return first;
1209 }
1210 }
1211 return last;
1212 }
1213
1220 template <typename UnaryPredicate, typename C>
1221 constexpr auto find_if_not(const C& arr, UnaryPredicate predicate) {
1222 if constexpr (has_func_find_if_not<C, UnaryPredicate>::value)
1223 return arr.find_if_not(predicate);
1224 else
1225 return core::find_if_not(arr.begin(), arr.end(), predicate);
1226 }
1227
1228 //----------------------------------------------------------------------
1229
1236 template <typename C, typename V>
1237 constexpr bool has(const C& arr, const V& item) {
1238 const auto it = find(arr, item);
1239 return it != arr.end();
1240 }
1241
1248 template <typename UnaryPredicate, typename C>
1249 constexpr bool has_if(const C& arr, UnaryPredicate predicate) {
1250 const auto it = find_if(arr, predicate);
1251 return it != arr.end();
1252 }
1253
1254 //----------------------------------------------------------------------
1255
1261 template <typename C>
1262 constexpr auto get_index(const C& arr, typename C::const_reference item) {
1263 const auto it = find(arr, item);
1264 if (it == arr.end())
1265 return BadIndex;
1266
1267 return (decltype(BadIndex))core::distance(arr.begin(), it);
1268 }
1269
1276 template <typename C>
1277 constexpr auto get_index_unsafe(const C& arr, typename C::const_reference item) {
1278 return (decltype(BadIndex))core::distance(arr.begin(), find(arr, item));
1279 }
1280
1287 template <typename UnaryPredicate, typename C>
1288 constexpr auto get_index_if(const C& arr, UnaryPredicate predicate) {
1289 const auto it = find_if(arr, predicate);
1290 if (it == arr.end())
1291 return BadIndex;
1292
1293 return (decltype(BadIndex))core::distance(arr.begin(), it);
1294 }
1295
1303 template <typename UnaryPredicate, typename C>
1304 constexpr auto get_index_if_unsafe(const C& arr, UnaryPredicate predicate) {
1305 return (decltype(BadIndex))core::distance(arr.begin(), find_if(arr, predicate));
1306 }
1307
1308 //----------------------------------------------------------------------
1309 // Erasure
1310 //----------------------------------------------------------------------
1311
1320 template <typename C>
1321 void swap_erase_unsafe(C& arr, typename C::size_type idx) {
1322 GAIA_ASSERT(idx < arr.size());
1323
1324 if (idx + 1 != arr.size())
1325 arr[idx] = arr[arr.size() - 1];
1326
1327 arr.pop_back();
1328 }
1329
1337 template <typename C>
1338 void swap_erase(C& arr, typename C::size_type idx) {
1339 if (idx >= arr.size())
1340 return;
1341
1342 if (idx + 1 != arr.size())
1343 arr[idx] = arr[arr.size() - 1];
1344
1345 arr.pop_back();
1346 }
1347
1348 //----------------------------------------------------------------------
1349 // Comparison
1350 //----------------------------------------------------------------------
1351
1354 template <typename T>
1355 struct equal_to {
1360 constexpr bool operator()(const T& lhs, const T& rhs) const {
1361 return lhs == rhs;
1362 }
1363 };
1364
1367 template <typename T>
1368 struct is_smaller {
1373 constexpr bool operator()(const T& lhs, const T& rhs) const {
1374 return lhs < rhs;
1375 }
1376 };
1377
1380 template <typename T>
1381 struct is_smaller_or_equal {
1386 constexpr bool operator()(const T& lhs, const T& rhs) const {
1387 return lhs <= rhs;
1388 }
1389 };
1390
1393 template <typename T>
1394 struct is_greater {
1399 constexpr bool operator()(const T& lhs, const T& rhs) const {
1400 return lhs > rhs;
1401 }
1402 };
1403
1404 //----------------------------------------------------------------------
1405 // Sorting
1406 //----------------------------------------------------------------------
1407
1408 namespace detail {
1418 template <typename Container, typename TCmpFunc>
1419 int sort_median_of_three(Container& arr, int low, int mid, int high, TCmpFunc cmpFunc) {
1420 if (cmpFunc(arr[(uint32_t)low], arr[(uint32_t)mid])) {
1421 if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)high]))
1422 return mid;
1423 return cmpFunc(arr[(uint32_t)low], arr[(uint32_t)high]) ? high : low;
1424 }
1425
1426 if (cmpFunc(arr[(uint32_t)low], arr[(uint32_t)high]))
1427 return low;
1428 return cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)high]) ? high : mid;
1429 }
1430
1439 template <typename Container, typename TCmpFunc>
1440 int sort_choose_pivot(Container& arr, int low, int high, TCmpFunc cmpFunc) {
1441 const int size = high - low + 1;
1442 const int mid = low + (size >> 1);
1443 if (size > 1024) {
1444 const int step = size >> 3;
1445 const int lowMed = sort_median_of_three(arr, low, low + step, low + step + step, cmpFunc);
1446 const int midMed = sort_median_of_three(arr, mid - step, mid, mid + step, cmpFunc);
1447 const int highMed = sort_median_of_three(arr, high - step - step, high - step, high, cmpFunc);
1448 return sort_median_of_three(arr, lowMed, midMed, highMed, cmpFunc);
1449 }
1450
1451 return sort_median_of_three(arr, low, mid, high, cmpFunc);
1452 }
1453
1463 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1464 void insertion_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1465 for (int i = low + 1; i <= high; ++i) {
1466 for (int j = i; j > low && cmpFunc(arr[(uint32_t)j], arr[(uint32_t)(j - 1)]); --j)
1467 swapFunc((uint32_t)(j - 1), (uint32_t)j);
1468 }
1469 }
1470
1480 template <typename Container, typename TCmpFunc>
1481 void insertion_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc) {
1482 for (int i = low + 1; i <= high; ++i) {
1483 if (cmpFunc(arr[(uint32_t)i], arr[(uint32_t)(i - 1)])) {
1484 auto tmp = GAIA_MOV(arr[(uint32_t)i]);
1485 int j = i;
1486 do {
1487 arr[(uint32_t)j] = GAIA_MOV(arr[(uint32_t)(j - 1)]);
1488 --j;
1489 } while (j > low && cmpFunc(tmp, arr[(uint32_t)(j - 1)]));
1490 arr[(uint32_t)j] = GAIA_MOV(tmp);
1491 }
1492 }
1493 }
1494
1505 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1506 void sort_order_three(Container& arr, int lhs, int mid, int rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1507 if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)lhs]))
1508 swapFunc((uint32_t)lhs, (uint32_t)mid);
1509 if (cmpFunc(arr[(uint32_t)rhs], arr[(uint32_t)mid])) {
1510 swapFunc((uint32_t)mid, (uint32_t)rhs);
1511 if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)lhs]))
1512 swapFunc((uint32_t)lhs, (uint32_t)mid);
1513 }
1514 }
1515
1526 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1527 void sort_prepare_pivot_first(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1528 constexpr int NintherThreshold = 128;
1529 const int size = high - low + 1;
1530 const int mid = low + (size >> 1);
1531
1532 if (size > NintherThreshold) {
1533 sort_order_three(arr, low, mid, high, cmpFunc, swapFunc);
1534 sort_order_three(arr, low + 1, mid - 1, high - 1, cmpFunc, swapFunc);
1535 sort_order_three(arr, low + 2, mid + 1, high - 2, cmpFunc, swapFunc);
1536 sort_order_three(arr, mid - 1, mid, mid + 1, cmpFunc, swapFunc);
1537 swapFunc((uint32_t)low, (uint32_t)mid);
1538 } else {
1539 sort_order_three(arr, mid, low, high, cmpFunc, swapFunc);
1540 }
1541 }
1542
1553 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1554 int quick_sort_partition_pivot_first(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1555 const int begin = low;
1556 int first = low;
1557 int last = high + 1;
1558 const int end = last;
1559 auto pivot = GAIA_MOV(arr[(uint32_t)first]);
1560
1561 do {
1562 ++first;
1563 } while (first != end && cmpFunc(arr[(uint32_t)first], pivot));
1564
1565 if (begin == first - 1) {
1566 while (first < last && !cmpFunc(arr[(uint32_t)(--last)], pivot)) {
1567 }
1568 } else {
1569 do {
1570 --last;
1571 } while (!cmpFunc(arr[(uint32_t)last], pivot));
1572 }
1573
1574 while (first < last) {
1575 swapFunc((uint32_t)first, (uint32_t)last);
1576 do {
1577 ++first;
1578 } while (cmpFunc(arr[(uint32_t)first], pivot));
1579 do {
1580 --last;
1581 } while (!cmpFunc(arr[(uint32_t)last], pivot));
1582 }
1583
1584 const int pivotPos = first - 1;
1585 if (begin != pivotPos)
1586 arr[(uint32_t)begin] = GAIA_MOV(arr[(uint32_t)pivotPos]);
1587 arr[(uint32_t)pivotPos] = GAIA_MOV(pivot);
1588 return pivotPos;
1589 }
1590
1600 template <typename T, typename TCmpFunc, typename TSwapFunc>
1601 bool try_sorted_or_reversed(T* beg, uint32_t n, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1602 if (n <= 1)
1603 return true;
1604
1605 bool sorted = true;
1606 for (uint32_t i = 1; i < n; ++i) {
1607 if (cmpFunc(beg[i], beg[i - 1])) {
1608 sorted = false;
1609 break;
1610 }
1611 }
1612 if (sorted)
1613 return true;
1614
1615 bool reversed = true;
1616 for (uint32_t i = 1; i < n; ++i) {
1617 if (cmpFunc(beg[i - 1], beg[i])) {
1618 reversed = false;
1619 break;
1620 }
1621 }
1622 if (!reversed)
1623 return false;
1624
1625 for (uint32_t i = 0, j = n - 1; i < j; ++i, --j)
1626 swapFunc(i, j);
1627 return true;
1628 }
1629
1640 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1641 int quick_sort_partition_hoare(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1642 const int pivotIdx = sort_choose_pivot(arr, low, high, cmpFunc);
1643 const auto pivot = arr[(uint32_t)pivotIdx];
1644
1645 int i = low - 1;
1646 int j = high + 1;
1647
1648 while (true) {
1649 do {
1650 ++i;
1651 } while (cmpFunc(arr[(uint32_t)i], pivot));
1652
1653 do {
1654 --j;
1655 } while (cmpFunc(pivot, arr[(uint32_t)j]));
1656
1657 if (i >= j)
1658 return j;
1659
1660 swapFunc((uint32_t)i, (uint32_t)j);
1661 }
1662 }
1663
1674 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1675 void heap_sift_down(Container& arr, int low, int root, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1676 while (true) {
1677 const int left = low + ((root - low) << 1) + 1;
1678 if (left > high)
1679 return;
1680
1681 int child = left;
1682 const int right = left + 1;
1683 if (right <= high && cmpFunc(arr[(uint32_t)child], arr[(uint32_t)right]))
1684 child = right;
1685
1686 if (!cmpFunc(arr[(uint32_t)root], arr[(uint32_t)child]))
1687 return;
1688
1689 swapFunc((uint32_t)root, (uint32_t)child);
1690 root = child;
1691 }
1692 }
1693
1703 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1704 void heap_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1705 for (int start = low + ((high - low - 1) >> 1); start >= low; --start)
1706 heap_sift_down(arr, low, start, high, cmpFunc, swapFunc);
1707
1708 for (int end = high; end > low; --end) {
1709 swapFunc((uint32_t)low, (uint32_t)end);
1710 heap_sift_down(arr, low, low, end - 1, cmpFunc, swapFunc);
1711 }
1712 }
1713
1717 inline uint32_t sort_depth_limit(uint32_t n) {
1718 uint32_t depth = 0;
1719 while (n > 1) {
1720 ++depth;
1721 n >>= 1;
1722 }
1723 return depth * 2;
1724 }
1725
1736 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1737 void
1738 quick_sort_impl(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc, uint32_t depthLimit) {
1739 constexpr int InsertionSortThreshold = 24;
1740
1741 while (high - low > InsertionSortThreshold) {
1742 if (depthLimit == 0) {
1743 heap_sort_range(arr, low, high, cmpFunc, swapFunc);
1744 return;
1745 }
1746 --depthLimit;
1747
1748 const int split = quick_sort_partition_hoare(arr, low, high, cmpFunc, swapFunc);
1749 const int leftSize = split - low + 1;
1750 const int rightSize = high - split;
1751
1752 if (leftSize < rightSize) {
1753 quick_sort_impl(arr, low, split, cmpFunc, swapFunc, depthLimit);
1754 low = split + 1;
1755 } else {
1756 quick_sort_impl(arr, split + 1, high, cmpFunc, swapFunc, depthLimit);
1757 high = split;
1758 }
1759 }
1760
1761 if (low < high)
1762 insertion_sort_range(arr, low, high, cmpFunc, swapFunc);
1763 }
1764
1775 template <typename Container, typename TCmpFunc>
1776 void quick_sort_impl(Container& arr, int low, int high, TCmpFunc cmpFunc, uint32_t depthLimit) {
1777 constexpr int InsertionSortThreshold = 24;
1778 auto swapFunc = [&arr](uint32_t a, uint32_t b) {
1779 core::swap(arr[a], arr[b]);
1780 };
1781
1782 while (high - low > InsertionSortThreshold) {
1783 if (depthLimit == 0) {
1784 heap_sort_range(arr, low, high, cmpFunc, swapFunc);
1785 return;
1786 }
1787 --depthLimit;
1788
1789 sort_prepare_pivot_first(arr, low, high, cmpFunc, swapFunc);
1790 const int pivot = quick_sort_partition_pivot_first(arr, low, high, cmpFunc, swapFunc);
1791 const int leftSize = pivot - low;
1792 const int rightSize = high - pivot;
1793
1794 if (leftSize < rightSize) {
1795 quick_sort_impl(arr, low, pivot - 1, cmpFunc, depthLimit);
1796 low = pivot + 1;
1797 } else {
1798 quick_sort_impl(arr, pivot + 1, high, cmpFunc, depthLimit);
1799 high = pivot - 1;
1800 }
1801 }
1802
1803 if (low < high)
1804 insertion_sort_range(arr, low, high, cmpFunc);
1805 }
1806
1814 template <typename T, typename TCmpFunc>
1815 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc) {
1816 const auto n = (uint32_t)(end - beg);
1817 if (n <= 1) {
1818 // Nothing to sort with just one item
1819 } else if (n == 2) {
1820 swap_if(beg, 0, 1, cmpFunc);
1821 } else if (n == 3) {
1822 swap_if(beg, 1, 2, cmpFunc);
1823 swap_if(beg, 0, 2, cmpFunc);
1824 swap_if(beg, 0, 1, cmpFunc);
1825 } else if (n == 4) {
1826 swap_if(beg, 0, 1, cmpFunc);
1827 swap_if(beg, 2, 3, cmpFunc);
1828
1829 swap_if(beg, 0, 2, cmpFunc);
1830 swap_if(beg, 1, 3, cmpFunc);
1831
1832 swap_if(beg, 1, 2, cmpFunc);
1833 } else if (n == 5) {
1834 swap_if(beg, 0, 1, cmpFunc);
1835 swap_if(beg, 3, 4, cmpFunc);
1836
1837 swap_if(beg, 2, 4, cmpFunc);
1838
1839 swap_if(beg, 2, 3, cmpFunc);
1840 swap_if(beg, 1, 4, cmpFunc);
1841
1842 swap_if(beg, 0, 3, cmpFunc);
1843
1844 swap_if(beg, 0, 2, cmpFunc);
1845 swap_if(beg, 1, 3, cmpFunc);
1846
1847 swap_if(beg, 1, 2, cmpFunc);
1848 } else if (n == 6) {
1849 swap_if(beg, 1, 2, cmpFunc);
1850 swap_if(beg, 4, 5, cmpFunc);
1851
1852 swap_if(beg, 0, 2, cmpFunc);
1853 swap_if(beg, 3, 5, cmpFunc);
1854
1855 swap_if(beg, 0, 1, cmpFunc);
1856 swap_if(beg, 3, 4, cmpFunc);
1857 swap_if(beg, 2, 5, cmpFunc);
1858
1859 swap_if(beg, 0, 3, cmpFunc);
1860 swap_if(beg, 1, 4, cmpFunc);
1861
1862 swap_if(beg, 2, 4, cmpFunc);
1863 swap_if(beg, 1, 3, cmpFunc);
1864
1865 swap_if(beg, 2, 3, cmpFunc);
1866 } else if (n == 7) {
1867 swap_if(beg, 1, 2, cmpFunc);
1868 swap_if(beg, 3, 4, cmpFunc);
1869 swap_if(beg, 5, 6, cmpFunc);
1870
1871 swap_if(beg, 0, 2, cmpFunc);
1872 swap_if(beg, 3, 5, cmpFunc);
1873 swap_if(beg, 4, 6, cmpFunc);
1874
1875 swap_if(beg, 0, 1, cmpFunc);
1876 swap_if(beg, 4, 5, cmpFunc);
1877 swap_if(beg, 2, 6, cmpFunc);
1878
1879 swap_if(beg, 0, 4, cmpFunc);
1880 swap_if(beg, 1, 5, cmpFunc);
1881
1882 swap_if(beg, 0, 3, cmpFunc);
1883 swap_if(beg, 2, 5, cmpFunc);
1884
1885 swap_if(beg, 1, 3, cmpFunc);
1886 swap_if(beg, 2, 4, cmpFunc);
1887
1888 swap_if(beg, 2, 3, cmpFunc);
1889 } else if (n == 8) {
1890 swap_if(beg, 0, 1, cmpFunc);
1891 swap_if(beg, 2, 3, cmpFunc);
1892 swap_if(beg, 4, 5, cmpFunc);
1893 swap_if(beg, 6, 7, cmpFunc);
1894
1895 swap_if(beg, 0, 2, cmpFunc);
1896 swap_if(beg, 1, 3, cmpFunc);
1897 swap_if(beg, 4, 6, cmpFunc);
1898 swap_if(beg, 5, 7, cmpFunc);
1899
1900 swap_if(beg, 1, 2, cmpFunc);
1901 swap_if(beg, 5, 6, cmpFunc);
1902 swap_if(beg, 0, 4, cmpFunc);
1903 swap_if(beg, 3, 7, cmpFunc);
1904
1905 swap_if(beg, 1, 5, cmpFunc);
1906 swap_if(beg, 2, 6, cmpFunc);
1907
1908 swap_if(beg, 1, 4, cmpFunc);
1909 swap_if(beg, 3, 6, cmpFunc);
1910
1911 swap_if(beg, 2, 4, cmpFunc);
1912 swap_if(beg, 3, 5, cmpFunc);
1913
1914 swap_if(beg, 3, 4, cmpFunc);
1915 } else if (n == 9) {
1916 swap_if(beg, 0, 1, cmpFunc);
1917 swap_if(beg, 3, 4, cmpFunc);
1918 swap_if(beg, 6, 7, cmpFunc);
1919 swap_if(beg, 1, 2, cmpFunc);
1920 swap_if(beg, 4, 5, cmpFunc);
1921 swap_if(beg, 7, 8, cmpFunc);
1922 swap_if(beg, 0, 1, cmpFunc);
1923 swap_if(beg, 3, 4, cmpFunc);
1924 swap_if(beg, 6, 7, cmpFunc);
1925 swap_if(beg, 0, 3, cmpFunc);
1926 swap_if(beg, 3, 6, cmpFunc);
1927 swap_if(beg, 0, 3, cmpFunc);
1928 swap_if(beg, 1, 4, cmpFunc);
1929 swap_if(beg, 4, 7, cmpFunc);
1930 swap_if(beg, 1, 4, cmpFunc);
1931 swap_if(beg, 2, 5, cmpFunc);
1932 swap_if(beg, 5, 8, cmpFunc);
1933 swap_if(beg, 2, 5, cmpFunc);
1934 swap_if(beg, 1, 3, cmpFunc);
1935 swap_if(beg, 5, 7, cmpFunc);
1936 swap_if(beg, 2, 6, cmpFunc);
1937 swap_if(beg, 4, 6, cmpFunc);
1938 swap_if(beg, 2, 4, cmpFunc);
1939 swap_if(beg, 2, 3, cmpFunc);
1940 swap_if(beg, 5, 6, cmpFunc);
1941 } else if (n == 10) {
1942 swap_if(beg, 0, 8, cmpFunc);
1943 swap_if(beg, 1, 9, cmpFunc);
1944 swap_if(beg, 2, 7, cmpFunc);
1945 swap_if(beg, 3, 6, cmpFunc);
1946 swap_if(beg, 4, 5, cmpFunc);
1947
1948 swap_if(beg, 0, 2, cmpFunc);
1949 swap_if(beg, 1, 3, cmpFunc);
1950 swap_if(beg, 4, 8, cmpFunc);
1951 swap_if(beg, 5, 7, cmpFunc);
1952 swap_if(beg, 6, 9, cmpFunc);
1953
1954 swap_if(beg, 0, 4, cmpFunc);
1955 swap_if(beg, 1, 5, cmpFunc);
1956 swap_if(beg, 2, 6, cmpFunc);
1957 swap_if(beg, 3, 7, cmpFunc);
1958
1959 swap_if(beg, 0, 1, cmpFunc);
1960 swap_if(beg, 2, 3, cmpFunc);
1961 swap_if(beg, 4, 6, cmpFunc);
1962 swap_if(beg, 5, 9, cmpFunc);
1963 swap_if(beg, 7, 8, cmpFunc);
1964
1965 swap_if(beg, 1, 2, cmpFunc);
1966 swap_if(beg, 3, 5, cmpFunc);
1967 swap_if(beg, 6, 7, cmpFunc);
1968 swap_if(beg, 8, 9, cmpFunc);
1969
1970 swap_if(beg, 2, 4, cmpFunc);
1971 swap_if(beg, 3, 6, cmpFunc);
1972 swap_if(beg, 5, 8, cmpFunc);
1973
1974 swap_if(beg, 1, 2, cmpFunc);
1975 swap_if(beg, 3, 4, cmpFunc);
1976 swap_if(beg, 5, 6, cmpFunc);
1977 swap_if(beg, 7, 8, cmpFunc);
1978 } else if (n == 11) {
1979 swap_if(beg, 0, 9, cmpFunc);
1980 swap_if(beg, 1, 6, cmpFunc);
1981 swap_if(beg, 2, 4, cmpFunc);
1982 swap_if(beg, 3, 7, cmpFunc);
1983 swap_if(beg, 5, 8, cmpFunc);
1984 swap_if(beg, 0, 1, cmpFunc);
1985 swap_if(beg, 3, 5, cmpFunc);
1986 swap_if(beg, 4, 10, cmpFunc);
1987 swap_if(beg, 6, 9, cmpFunc);
1988 swap_if(beg, 7, 8, cmpFunc);
1989 swap_if(beg, 1, 3, cmpFunc);
1990 swap_if(beg, 2, 5, cmpFunc);
1991 swap_if(beg, 4, 7, cmpFunc);
1992 swap_if(beg, 8, 10, cmpFunc);
1993 swap_if(beg, 0, 4, cmpFunc);
1994 swap_if(beg, 1, 2, cmpFunc);
1995 swap_if(beg, 3, 7, cmpFunc);
1996 swap_if(beg, 5, 9, cmpFunc);
1997 swap_if(beg, 6, 8, cmpFunc);
1998 swap_if(beg, 0, 1, cmpFunc);
1999 swap_if(beg, 2, 6, cmpFunc);
2000 swap_if(beg, 4, 5, cmpFunc);
2001 swap_if(beg, 7, 8, cmpFunc);
2002 swap_if(beg, 9, 10, cmpFunc);
2003 swap_if(beg, 2, 4, cmpFunc);
2004 swap_if(beg, 3, 6, cmpFunc);
2005 swap_if(beg, 5, 7, cmpFunc);
2006 swap_if(beg, 8, 9, cmpFunc);
2007 swap_if(beg, 1, 2, cmpFunc);
2008 swap_if(beg, 3, 4, cmpFunc);
2009 swap_if(beg, 5, 6, cmpFunc);
2010 swap_if(beg, 7, 8, cmpFunc);
2011 swap_if(beg, 2, 3, cmpFunc);
2012 swap_if(beg, 4, 5, cmpFunc);
2013 swap_if(beg, 6, 7, cmpFunc);
2014 } else if (n == 12) {
2015 swap_if(beg, 0, 8, cmpFunc);
2016 swap_if(beg, 1, 7, cmpFunc);
2017 swap_if(beg, 2, 6, cmpFunc);
2018 swap_if(beg, 3, 11, cmpFunc);
2019 swap_if(beg, 4, 10, cmpFunc);
2020 swap_if(beg, 5, 9, cmpFunc);
2021 swap_if(beg, 0, 1, cmpFunc);
2022 swap_if(beg, 2, 5, cmpFunc);
2023 swap_if(beg, 3, 4, cmpFunc);
2024 swap_if(beg, 6, 9, cmpFunc);
2025 swap_if(beg, 7, 8, cmpFunc);
2026 swap_if(beg, 10, 11, cmpFunc);
2027 swap_if(beg, 0, 2, cmpFunc);
2028 swap_if(beg, 1, 6, cmpFunc);
2029 swap_if(beg, 5, 10, cmpFunc);
2030 swap_if(beg, 9, 11, cmpFunc);
2031 swap_if(beg, 0, 3, cmpFunc);
2032 swap_if(beg, 1, 2, cmpFunc);
2033 swap_if(beg, 4, 6, cmpFunc);
2034 swap_if(beg, 5, 7, cmpFunc);
2035 swap_if(beg, 8, 11, cmpFunc);
2036 swap_if(beg, 9, 10, cmpFunc);
2037 swap_if(beg, 1, 4, cmpFunc);
2038 swap_if(beg, 3, 5, cmpFunc);
2039 swap_if(beg, 6, 8, cmpFunc);
2040 swap_if(beg, 7, 10, cmpFunc);
2041 swap_if(beg, 1, 3, cmpFunc);
2042 swap_if(beg, 2, 5, cmpFunc);
2043 swap_if(beg, 6, 9, cmpFunc);
2044 swap_if(beg, 8, 10, cmpFunc);
2045 swap_if(beg, 2, 3, cmpFunc);
2046 swap_if(beg, 4, 5, cmpFunc);
2047 swap_if(beg, 6, 7, cmpFunc);
2048 swap_if(beg, 8, 9, cmpFunc);
2049 swap_if(beg, 4, 6, cmpFunc);
2050 swap_if(beg, 5, 7, cmpFunc);
2051 swap_if(beg, 3, 4, cmpFunc);
2052 swap_if(beg, 5, 6, cmpFunc);
2053 swap_if(beg, 7, 8, cmpFunc);
2054 } else if (n == 13) {
2055 swap_if(beg, 0, 12, cmpFunc);
2056 swap_if(beg, 1, 10, cmpFunc);
2057 swap_if(beg, 2, 9, cmpFunc);
2058 swap_if(beg, 3, 7, cmpFunc);
2059 swap_if(beg, 5, 11, cmpFunc);
2060 swap_if(beg, 6, 8, cmpFunc);
2061 swap_if(beg, 1, 6, cmpFunc);
2062 swap_if(beg, 2, 3, cmpFunc);
2063 swap_if(beg, 4, 11, cmpFunc);
2064 swap_if(beg, 7, 9, cmpFunc);
2065 swap_if(beg, 8, 10, cmpFunc);
2066 swap_if(beg, 0, 4, cmpFunc);
2067 swap_if(beg, 1, 2, cmpFunc);
2068 swap_if(beg, 3, 6, cmpFunc);
2069 swap_if(beg, 7, 8, cmpFunc);
2070 swap_if(beg, 9, 10, cmpFunc);
2071 swap_if(beg, 11, 12, cmpFunc);
2072 swap_if(beg, 4, 6, cmpFunc);
2073 swap_if(beg, 5, 9, cmpFunc);
2074 swap_if(beg, 8, 11, cmpFunc);
2075 swap_if(beg, 10, 12, cmpFunc);
2076 swap_if(beg, 0, 5, cmpFunc);
2077 swap_if(beg, 3, 8, cmpFunc);
2078 swap_if(beg, 4, 7, cmpFunc);
2079 swap_if(beg, 6, 11, cmpFunc);
2080 swap_if(beg, 9, 10, cmpFunc);
2081 swap_if(beg, 0, 1, cmpFunc);
2082 swap_if(beg, 2, 5, cmpFunc);
2083 swap_if(beg, 6, 9, cmpFunc);
2084 swap_if(beg, 7, 8, cmpFunc);
2085 swap_if(beg, 10, 11, cmpFunc);
2086 swap_if(beg, 1, 3, cmpFunc);
2087 swap_if(beg, 2, 4, cmpFunc);
2088 swap_if(beg, 5, 6, cmpFunc);
2089 swap_if(beg, 9, 10, cmpFunc);
2090 swap_if(beg, 1, 2, cmpFunc);
2091 swap_if(beg, 3, 4, cmpFunc);
2092 swap_if(beg, 5, 7, cmpFunc);
2093 swap_if(beg, 6, 8, cmpFunc);
2094 swap_if(beg, 2, 3, cmpFunc);
2095 swap_if(beg, 4, 5, cmpFunc);
2096 swap_if(beg, 6, 7, cmpFunc);
2097 swap_if(beg, 8, 9, cmpFunc);
2098 swap_if(beg, 3, 4, cmpFunc);
2099 swap_if(beg, 5, 6, cmpFunc);
2100 } else if (n == 14) {
2101 swap_if(beg, 0, 1, cmpFunc);
2102 swap_if(beg, 2, 3, cmpFunc);
2103 swap_if(beg, 4, 5, cmpFunc);
2104 swap_if(beg, 6, 7, cmpFunc);
2105 swap_if(beg, 8, 9, cmpFunc);
2106 swap_if(beg, 10, 11, cmpFunc);
2107 swap_if(beg, 12, 13, cmpFunc);
2108 swap_if(beg, 0, 2, cmpFunc);
2109 swap_if(beg, 1, 3, cmpFunc);
2110 swap_if(beg, 4, 8, cmpFunc);
2111 swap_if(beg, 5, 9, cmpFunc);
2112 swap_if(beg, 10, 12, cmpFunc);
2113 swap_if(beg, 11, 13, cmpFunc);
2114 swap_if(beg, 0, 4, cmpFunc);
2115 swap_if(beg, 1, 2, cmpFunc);
2116 swap_if(beg, 3, 7, cmpFunc);
2117 swap_if(beg, 5, 8, cmpFunc);
2118 swap_if(beg, 6, 10, cmpFunc);
2119 swap_if(beg, 9, 13, cmpFunc);
2120 swap_if(beg, 11, 12, cmpFunc);
2121 swap_if(beg, 0, 6, cmpFunc);
2122 swap_if(beg, 1, 5, cmpFunc);
2123 swap_if(beg, 3, 9, cmpFunc);
2124 swap_if(beg, 4, 10, cmpFunc);
2125 swap_if(beg, 7, 13, cmpFunc);
2126 swap_if(beg, 8, 12, cmpFunc);
2127 swap_if(beg, 2, 10, cmpFunc);
2128 swap_if(beg, 3, 11, cmpFunc);
2129 swap_if(beg, 4, 6, cmpFunc);
2130 swap_if(beg, 7, 9, cmpFunc);
2131 swap_if(beg, 1, 3, cmpFunc);
2132 swap_if(beg, 2, 8, cmpFunc);
2133 swap_if(beg, 5, 11, cmpFunc);
2134 swap_if(beg, 6, 7, cmpFunc);
2135 swap_if(beg, 10, 12, cmpFunc);
2136 swap_if(beg, 1, 4, cmpFunc);
2137 swap_if(beg, 2, 6, cmpFunc);
2138 swap_if(beg, 3, 5, cmpFunc);
2139 swap_if(beg, 7, 11, cmpFunc);
2140 swap_if(beg, 8, 10, cmpFunc);
2141 swap_if(beg, 9, 12, cmpFunc);
2142 swap_if(beg, 2, 4, cmpFunc);
2143 swap_if(beg, 3, 6, cmpFunc);
2144 swap_if(beg, 5, 8, cmpFunc);
2145 swap_if(beg, 7, 10, cmpFunc);
2146 swap_if(beg, 9, 11, cmpFunc);
2147 swap_if(beg, 3, 4, cmpFunc);
2148 swap_if(beg, 5, 6, cmpFunc);
2149 swap_if(beg, 7, 8, cmpFunc);
2150 swap_if(beg, 9, 10, cmpFunc);
2151 swap_if(beg, 6, 7, cmpFunc);
2152 } else if (n == 15) {
2153 swap_if(beg, 1, 2, cmpFunc);
2154 swap_if(beg, 3, 10, cmpFunc);
2155 swap_if(beg, 4, 14, cmpFunc);
2156 swap_if(beg, 5, 8, cmpFunc);
2157 swap_if(beg, 6, 13, cmpFunc);
2158 swap_if(beg, 7, 12, cmpFunc);
2159 swap_if(beg, 9, 11, cmpFunc);
2160 swap_if(beg, 0, 14, cmpFunc);
2161 swap_if(beg, 1, 5, cmpFunc);
2162 swap_if(beg, 2, 8, cmpFunc);
2163 swap_if(beg, 3, 7, cmpFunc);
2164 swap_if(beg, 6, 9, cmpFunc);
2165 swap_if(beg, 10, 12, cmpFunc);
2166 swap_if(beg, 11, 13, cmpFunc);
2167 swap_if(beg, 0, 7, cmpFunc);
2168 swap_if(beg, 1, 6, cmpFunc);
2169 swap_if(beg, 2, 9, cmpFunc);
2170 swap_if(beg, 4, 10, cmpFunc);
2171 swap_if(beg, 5, 11, cmpFunc);
2172 swap_if(beg, 8, 13, cmpFunc);
2173 swap_if(beg, 12, 14, cmpFunc);
2174 swap_if(beg, 0, 6, cmpFunc);
2175 swap_if(beg, 2, 4, cmpFunc);
2176 swap_if(beg, 3, 5, cmpFunc);
2177 swap_if(beg, 7, 11, cmpFunc);
2178 swap_if(beg, 8, 10, cmpFunc);
2179 swap_if(beg, 9, 12, cmpFunc);
2180 swap_if(beg, 13, 14, cmpFunc);
2181 swap_if(beg, 0, 3, cmpFunc);
2182 swap_if(beg, 1, 2, cmpFunc);
2183 swap_if(beg, 4, 7, cmpFunc);
2184 swap_if(beg, 5, 9, cmpFunc);
2185 swap_if(beg, 6, 8, cmpFunc);
2186 swap_if(beg, 10, 11, cmpFunc);
2187 swap_if(beg, 12, 13, cmpFunc);
2188 swap_if(beg, 0, 1, cmpFunc);
2189 swap_if(beg, 2, 3, cmpFunc);
2190 swap_if(beg, 4, 6, cmpFunc);
2191 swap_if(beg, 7, 9, cmpFunc);
2192 swap_if(beg, 10, 12, cmpFunc);
2193 swap_if(beg, 11, 13, cmpFunc);
2194 swap_if(beg, 1, 2, cmpFunc);
2195 swap_if(beg, 3, 5, cmpFunc);
2196 swap_if(beg, 8, 10, cmpFunc);
2197 swap_if(beg, 11, 12, cmpFunc);
2198 swap_if(beg, 3, 4, cmpFunc);
2199 swap_if(beg, 5, 6, cmpFunc);
2200 swap_if(beg, 7, 8, cmpFunc);
2201 swap_if(beg, 9, 10, cmpFunc);
2202 swap_if(beg, 2, 3, cmpFunc);
2203 swap_if(beg, 4, 5, cmpFunc);
2204 swap_if(beg, 6, 7, cmpFunc);
2205 swap_if(beg, 8, 9, cmpFunc);
2206 swap_if(beg, 10, 11, cmpFunc);
2207 swap_if(beg, 5, 6, cmpFunc);
2208 swap_if(beg, 7, 8, cmpFunc);
2209 } else if (n == 16) {
2210 swap_if(beg, 0, 13, cmpFunc);
2211 swap_if(beg, 1, 12, cmpFunc);
2212 swap_if(beg, 2, 15, cmpFunc);
2213 swap_if(beg, 3, 14, cmpFunc);
2214 swap_if(beg, 4, 8, cmpFunc);
2215 swap_if(beg, 5, 6, cmpFunc);
2216 swap_if(beg, 7, 11, cmpFunc);
2217 swap_if(beg, 9, 10, cmpFunc);
2218 swap_if(beg, 0, 5, cmpFunc);
2219 swap_if(beg, 1, 7, cmpFunc);
2220 swap_if(beg, 2, 9, cmpFunc);
2221 swap_if(beg, 3, 4, cmpFunc);
2222 swap_if(beg, 6, 13, cmpFunc);
2223 swap_if(beg, 8, 14, cmpFunc);
2224 swap_if(beg, 10, 15, cmpFunc);
2225 swap_if(beg, 11, 12, cmpFunc);
2226 swap_if(beg, 0, 1, cmpFunc);
2227 swap_if(beg, 2, 3, cmpFunc);
2228 swap_if(beg, 4, 5, cmpFunc);
2229 swap_if(beg, 6, 8, cmpFunc);
2230 swap_if(beg, 7, 9, cmpFunc);
2231 swap_if(beg, 10, 11, cmpFunc);
2232 swap_if(beg, 12, 13, cmpFunc);
2233 swap_if(beg, 14, 15, cmpFunc);
2234 swap_if(beg, 0, 2, cmpFunc);
2235 swap_if(beg, 1, 3, cmpFunc);
2236 swap_if(beg, 4, 10, cmpFunc);
2237 swap_if(beg, 5, 11, cmpFunc);
2238 swap_if(beg, 6, 7, cmpFunc);
2239 swap_if(beg, 8, 9, cmpFunc);
2240 swap_if(beg, 12, 14, cmpFunc);
2241 swap_if(beg, 13, 15, cmpFunc);
2242 swap_if(beg, 1, 2, cmpFunc);
2243 swap_if(beg, 3, 12, cmpFunc);
2244 swap_if(beg, 4, 6, cmpFunc);
2245 swap_if(beg, 5, 7, cmpFunc);
2246 swap_if(beg, 8, 10, cmpFunc);
2247 swap_if(beg, 9, 11, cmpFunc);
2248 swap_if(beg, 13, 14, cmpFunc);
2249 swap_if(beg, 1, 4, cmpFunc);
2250 swap_if(beg, 2, 6, cmpFunc);
2251 swap_if(beg, 5, 8, cmpFunc);
2252 swap_if(beg, 7, 10, cmpFunc);
2253 swap_if(beg, 9, 13, cmpFunc);
2254 swap_if(beg, 11, 14, cmpFunc);
2255 swap_if(beg, 2, 4, cmpFunc);
2256 swap_if(beg, 3, 6, cmpFunc);
2257 swap_if(beg, 9, 12, cmpFunc);
2258 swap_if(beg, 11, 13, cmpFunc);
2259 swap_if(beg, 3, 5, cmpFunc);
2260 swap_if(beg, 6, 8, cmpFunc);
2261 swap_if(beg, 7, 9, cmpFunc);
2262 swap_if(beg, 10, 12, cmpFunc);
2263 swap_if(beg, 3, 4, cmpFunc);
2264 swap_if(beg, 5, 6, cmpFunc);
2265 swap_if(beg, 7, 8, cmpFunc);
2266 swap_if(beg, 9, 10, cmpFunc);
2267 swap_if(beg, 11, 12, cmpFunc);
2268 swap_if(beg, 6, 7, cmpFunc);
2269 swap_if(beg, 8, 9, cmpFunc);
2270 } else if (n == 17) {
2271 swap_if(beg, 0, 11, cmpFunc);
2272 swap_if(beg, 1, 15, cmpFunc);
2273 swap_if(beg, 2, 10, cmpFunc);
2274 swap_if(beg, 3, 5, cmpFunc);
2275 swap_if(beg, 4, 6, cmpFunc);
2276 swap_if(beg, 8, 12, cmpFunc);
2277 swap_if(beg, 9, 16, cmpFunc);
2278 swap_if(beg, 13, 14, cmpFunc);
2279 swap_if(beg, 0, 6, cmpFunc);
2280 swap_if(beg, 1, 13, cmpFunc);
2281 swap_if(beg, 2, 8, cmpFunc);
2282 swap_if(beg, 4, 14, cmpFunc);
2283 swap_if(beg, 5, 15, cmpFunc);
2284 swap_if(beg, 7, 11, cmpFunc);
2285 swap_if(beg, 0, 8, cmpFunc);
2286 swap_if(beg, 3, 7, cmpFunc);
2287 swap_if(beg, 4, 9, cmpFunc);
2288 swap_if(beg, 6, 16, cmpFunc);
2289 swap_if(beg, 10, 11, cmpFunc);
2290 swap_if(beg, 12, 14, cmpFunc);
2291 swap_if(beg, 0, 2, cmpFunc);
2292 swap_if(beg, 1, 4, cmpFunc);
2293 swap_if(beg, 5, 6, cmpFunc);
2294 swap_if(beg, 7, 13, cmpFunc);
2295 swap_if(beg, 8, 9, cmpFunc);
2296 swap_if(beg, 10, 12, cmpFunc);
2297 swap_if(beg, 11, 14, cmpFunc);
2298 swap_if(beg, 15, 16, cmpFunc);
2299 swap_if(beg, 0, 3, cmpFunc);
2300 swap_if(beg, 2, 5, cmpFunc);
2301 swap_if(beg, 6, 11, cmpFunc);
2302 swap_if(beg, 7, 10, cmpFunc);
2303 swap_if(beg, 9, 13, cmpFunc);
2304 swap_if(beg, 12, 15, cmpFunc);
2305 swap_if(beg, 14, 16, cmpFunc);
2306 swap_if(beg, 0, 1, cmpFunc);
2307 swap_if(beg, 3, 4, cmpFunc);
2308 swap_if(beg, 5, 10, cmpFunc);
2309 swap_if(beg, 6, 9, cmpFunc);
2310 swap_if(beg, 7, 8, cmpFunc);
2311 swap_if(beg, 11, 15, cmpFunc);
2312 swap_if(beg, 13, 14, cmpFunc);
2313 swap_if(beg, 1, 2, cmpFunc);
2314 swap_if(beg, 3, 7, cmpFunc);
2315 swap_if(beg, 4, 8, cmpFunc);
2316 swap_if(beg, 6, 12, cmpFunc);
2317 swap_if(beg, 11, 13, cmpFunc);
2318 swap_if(beg, 14, 15, cmpFunc);
2319 swap_if(beg, 1, 3, cmpFunc);
2320 swap_if(beg, 2, 7, cmpFunc);
2321 swap_if(beg, 4, 5, cmpFunc);
2322 swap_if(beg, 9, 11, cmpFunc);
2323 swap_if(beg, 10, 12, cmpFunc);
2324 swap_if(beg, 13, 14, cmpFunc);
2325 swap_if(beg, 2, 3, cmpFunc);
2326 swap_if(beg, 4, 6, cmpFunc);
2327 swap_if(beg, 5, 7, cmpFunc);
2328 swap_if(beg, 8, 10, cmpFunc);
2329 swap_if(beg, 3, 4, cmpFunc);
2330 swap_if(beg, 6, 8, cmpFunc);
2331 swap_if(beg, 7, 9, cmpFunc);
2332 swap_if(beg, 10, 12, cmpFunc);
2333 swap_if(beg, 5, 6, cmpFunc);
2334 swap_if(beg, 7, 8, cmpFunc);
2335 swap_if(beg, 9, 10, cmpFunc);
2336 swap_if(beg, 11, 12, cmpFunc);
2337 swap_if(beg, 4, 5, cmpFunc);
2338 swap_if(beg, 6, 7, cmpFunc);
2339 swap_if(beg, 8, 9, cmpFunc);
2340 swap_if(beg, 10, 11, cmpFunc);
2341 swap_if(beg, 12, 13, cmpFunc);
2342 } else if (n <= 32) {
2343 insertion_sort_range(beg, 0, (int)n - 1, cmpFunc, [beg](uint32_t lhs, uint32_t rhs) {
2344 core::swap(beg[lhs], beg[rhs]);
2345 });
2346 }
2347
2348 return n <= 32;
2349 }
2350
2360 template <typename T, typename TCmpFunc, typename TSwapFunc>
2361 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2362 const auto n = (uint32_t)(end - beg);
2363 if (n <= 1) {
2364 // Nothing to sort with just one item
2365 } else if (n == 2) {
2366 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2367 } else if (n == 3) {
2368 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2369 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2370 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2371 } else if (n == 4) {
2372 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2373 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2374
2375 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2376 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2377
2378 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2379 } else if (n == 5) {
2380 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2381 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2382
2383 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2384
2385 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2386 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2387
2388 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2389
2390 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2391 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2392
2393 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2394 } else if (n == 6) {
2395 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2396 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2397
2398 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2399 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2400
2401 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2402 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2403 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2404
2405 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2406 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2407
2408 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2409 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2410
2411 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2412 } else if (n == 7) {
2413 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2414 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2415 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2416
2417 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2418 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2419 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2420
2421 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2422 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2423 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2424
2425 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2426 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2427
2428 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2429 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2430
2431 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2432 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2433
2434 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2435 } else if (n == 8) {
2436 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2437 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2438 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2439 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2440
2441 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2442 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2443 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2444 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2445
2446 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2447 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2448 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2449 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2450
2451 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2452 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2453
2454 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2455 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2456
2457 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2458 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2459
2460 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2461 } else if (n == 9) {
2462 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2463 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2464 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2465 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2466 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2467 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2468 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2469 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2470 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2471 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2472 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2473 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2474 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2475 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2476 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2477 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2478 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2479 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2480 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2481 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2482 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2483 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2484 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2485 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2486 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2487 } else if (n == 10) {
2488 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
2489 try_swap_if(beg, 1, 9, cmpFunc, swapFunc);
2490 try_swap_if(beg, 2, 7, cmpFunc, swapFunc);
2491 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2492 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2493
2494 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2495 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2496 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2497 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2498 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2499
2500 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2501 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2502 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2503 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2504
2505 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2506 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2507 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2508 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2509 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2510
2511 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2512 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2513 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2514 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2515
2516 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2517 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2518 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2519
2520 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2521 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2522 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2523 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2524 } else if (n == 11) {
2525 try_swap_if(beg, 0, 9, cmpFunc, swapFunc);
2526 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2527 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2528 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2529 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2530 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2531 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2532 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2533 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2534 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2535 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2536 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2537 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2538 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2539 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2540 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2541 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2542 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2543 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2544 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2545 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2546 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2547 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2548 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2549 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2550 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2551 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2552 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2553 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2554 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2555 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2556 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2557 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2558 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2559 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2560 } else if (n == 12) {
2561 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
2562 try_swap_if(beg, 1, 7, cmpFunc, swapFunc);
2563 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2564 try_swap_if(beg, 3, 11, cmpFunc, swapFunc);
2565 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2566 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2567 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2568 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2569 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2570 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2571 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2572 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2573 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2574 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2575 try_swap_if(beg, 5, 10, cmpFunc, swapFunc);
2576 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2577 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2578 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2579 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2580 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2581 try_swap_if(beg, 8, 11, cmpFunc, swapFunc);
2582 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2583 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2584 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2585 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2586 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2587 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2588 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2589 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2590 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2591 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2592 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2593 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2594 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2595 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2596 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2597 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2598 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2599 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2600 } else if (n == 13) {
2601 try_swap_if(beg, 0, 12, cmpFunc, swapFunc);
2602 try_swap_if(beg, 1, 10, cmpFunc, swapFunc);
2603 try_swap_if(beg, 2, 9, cmpFunc, swapFunc);
2604 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2605 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2606 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2607 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2608 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2609 try_swap_if(beg, 4, 11, cmpFunc, swapFunc);
2610 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2611 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2612 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2613 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2614 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2615 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2616 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2617 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2618 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2619 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2620 try_swap_if(beg, 8, 11, cmpFunc, swapFunc);
2621 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2622 try_swap_if(beg, 0, 5, cmpFunc, swapFunc);
2623 try_swap_if(beg, 3, 8, cmpFunc, swapFunc);
2624 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2625 try_swap_if(beg, 6, 11, cmpFunc, swapFunc);
2626 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2627 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2628 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2629 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2630 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2631 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2632 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2633 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2634 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2635 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2636 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2637 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2638 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2639 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2640 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2641 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2642 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2643 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2644 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2645 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2646 } else if (n == 14) {
2647 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2648 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2649 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2650 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2651 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2652 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2653 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2654 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2655 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2656 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2657 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2658 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2659 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2660 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2661 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2662 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2663 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2664 try_swap_if(beg, 6, 10, cmpFunc, swapFunc);
2665 try_swap_if(beg, 9, 13, cmpFunc, swapFunc);
2666 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2667 try_swap_if(beg, 0, 6, cmpFunc, swapFunc);
2668 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2669 try_swap_if(beg, 3, 9, cmpFunc, swapFunc);
2670 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2671 try_swap_if(beg, 7, 13, cmpFunc, swapFunc);
2672 try_swap_if(beg, 8, 12, cmpFunc, swapFunc);
2673 try_swap_if(beg, 2, 10, cmpFunc, swapFunc);
2674 try_swap_if(beg, 3, 11, cmpFunc, swapFunc);
2675 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2676 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2677 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2678 try_swap_if(beg, 2, 8, cmpFunc, swapFunc);
2679 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2680 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2681 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2682 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2683 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2684 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2685 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2686 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2687 try_swap_if(beg, 9, 12, cmpFunc, swapFunc);
2688 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2689 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2690 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2691 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2692 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2693 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2694 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2695 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2696 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2697 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2698 } else if (n == 15) {
2699 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2700 try_swap_if(beg, 3, 10, cmpFunc, swapFunc);
2701 try_swap_if(beg, 4, 14, cmpFunc, swapFunc);
2702 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2703 try_swap_if(beg, 6, 13, cmpFunc, swapFunc);
2704 try_swap_if(beg, 7, 12, cmpFunc, swapFunc);
2705 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2706 try_swap_if(beg, 0, 14, cmpFunc, swapFunc);
2707 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2708 try_swap_if(beg, 2, 8, cmpFunc, swapFunc);
2709 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2710 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2711 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2712 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2713 try_swap_if(beg, 0, 7, cmpFunc, swapFunc);
2714 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2715 try_swap_if(beg, 2, 9, cmpFunc, swapFunc);
2716 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2717 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2718 try_swap_if(beg, 8, 13, cmpFunc, swapFunc);
2719 try_swap_if(beg, 12, 14, cmpFunc, swapFunc);
2720 try_swap_if(beg, 0, 6, cmpFunc, swapFunc);
2721 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2722 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2723 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2724 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2725 try_swap_if(beg, 9, 12, cmpFunc, swapFunc);
2726 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2727 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2728 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2729 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2730 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2731 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2732 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2733 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2734 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2735 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2736 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2737 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2738 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2739 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2740 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2741 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2742 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2743 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2744 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2745 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2746 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2747 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2748 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2749 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2750 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2751 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2752 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2753 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2754 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2755 } else if (n == 16) {
2756 try_swap_if(beg, 0, 13, cmpFunc, swapFunc);
2757 try_swap_if(beg, 1, 12, cmpFunc, swapFunc);
2758 try_swap_if(beg, 2, 15, cmpFunc, swapFunc);
2759 try_swap_if(beg, 3, 14, cmpFunc, swapFunc);
2760 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2761 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2762 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2763 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2764 try_swap_if(beg, 0, 5, cmpFunc, swapFunc);
2765 try_swap_if(beg, 1, 7, cmpFunc, swapFunc);
2766 try_swap_if(beg, 2, 9, cmpFunc, swapFunc);
2767 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2768 try_swap_if(beg, 6, 13, cmpFunc, swapFunc);
2769 try_swap_if(beg, 8, 14, cmpFunc, swapFunc);
2770 try_swap_if(beg, 10, 15, cmpFunc, swapFunc);
2771 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2772 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2773 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2774 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2775 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2776 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2777 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2778 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2779 try_swap_if(beg, 14, 15, cmpFunc, swapFunc);
2780 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2781 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2782 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2783 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2784 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2785 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2786 try_swap_if(beg, 12, 14, cmpFunc, swapFunc);
2787 try_swap_if(beg, 13, 15, cmpFunc, swapFunc);
2788 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2789 try_swap_if(beg, 3, 12, cmpFunc, swapFunc);
2790 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2791 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2792 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2793 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2794 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2795 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2796 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2797 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2798 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2799 try_swap_if(beg, 9, 13, cmpFunc, swapFunc);
2800 try_swap_if(beg, 11, 14, cmpFunc, swapFunc);
2801 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2802 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2803 try_swap_if(beg, 9, 12, cmpFunc, swapFunc);
2804 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2805 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2806 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2807 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2808 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2809 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2810 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2811 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2812 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2813 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2814 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2815 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2816 } else if (n == 17) {
2817 try_swap_if(beg, 0, 11, cmpFunc, swapFunc);
2818 try_swap_if(beg, 1, 15, cmpFunc, swapFunc);
2819 try_swap_if(beg, 2, 10, cmpFunc, swapFunc);
2820 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2821 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2822 try_swap_if(beg, 8, 12, cmpFunc, swapFunc);
2823 try_swap_if(beg, 9, 16, cmpFunc, swapFunc);
2824 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2825 try_swap_if(beg, 0, 6, cmpFunc, swapFunc);
2826 try_swap_if(beg, 1, 13, cmpFunc, swapFunc);
2827 try_swap_if(beg, 2, 8, cmpFunc, swapFunc);
2828 try_swap_if(beg, 4, 14, cmpFunc, swapFunc);
2829 try_swap_if(beg, 5, 15, cmpFunc, swapFunc);
2830 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2831 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
2832 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2833 try_swap_if(beg, 4, 9, cmpFunc, swapFunc);
2834 try_swap_if(beg, 6, 16, cmpFunc, swapFunc);
2835 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2836 try_swap_if(beg, 12, 14, cmpFunc, swapFunc);
2837 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2838 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2839 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2840 try_swap_if(beg, 7, 13, cmpFunc, swapFunc);
2841 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2842 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2843 try_swap_if(beg, 11, 14, cmpFunc, swapFunc);
2844 try_swap_if(beg, 15, 16, cmpFunc, swapFunc);
2845 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2846 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2847 try_swap_if(beg, 6, 11, cmpFunc, swapFunc);
2848 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2849 try_swap_if(beg, 9, 13, cmpFunc, swapFunc);
2850 try_swap_if(beg, 12, 15, cmpFunc, swapFunc);
2851 try_swap_if(beg, 14, 16, cmpFunc, swapFunc);
2852 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2853 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2854 try_swap_if(beg, 5, 10, cmpFunc, swapFunc);
2855 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2856 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2857 try_swap_if(beg, 11, 15, cmpFunc, swapFunc);
2858 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2859 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2860 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2861 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2862 try_swap_if(beg, 6, 12, cmpFunc, swapFunc);
2863 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2864 try_swap_if(beg, 14, 15, cmpFunc, swapFunc);
2865 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2866 try_swap_if(beg, 2, 7, cmpFunc, swapFunc);
2867 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2868 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2869 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2870 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2871 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2872 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2873 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2874 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2875 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2876 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2877 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2878 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2879 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2880 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2881 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2882 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2883 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2884 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2885 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2886 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2887 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2888 } else if (n <= 32) {
2889 insertion_sort_range(beg, 0, (int)n - 1, cmpFunc, swapFunc);
2890 }
2891
2892 return n <= 32;
2893 }
2894 } // namespace detail
2895
2897 template <typename Container, typename TCmpFunc, typename TSwapFunc>
2898 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc);
2899
2907 template <typename Container, typename TCmpFunc>
2908 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc) {
2909 if (low >= high)
2910 return;
2911 detail::quick_sort_impl(arr, low, high, cmpFunc, detail::sort_depth_limit((uint32_t)(high - low + 1)));
2912 }
2913
2923 template <typename Container, typename TCmpFunc, typename TSwapFunc>
2924 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2925 if (low >= high)
2926 return;
2927 detail::quick_sort_impl(arr, low, high, cmpFunc, swapFunc, detail::sort_depth_limit((uint32_t)(high - low + 1)));
2928 }
2929
2939 template <typename T, typename TCmpFunc>
2940 void sort(T* beg, T* end, TCmpFunc cmpFunc) {
2941 const auto n = (uintptr_t)(end - beg);
2942 if (detail::try_sorted_or_reversed(beg, (uint32_t)n, cmpFunc, [beg](uint32_t lhs, uint32_t rhs) {
2943 core::swap(beg[lhs], beg[rhs]);
2944 }))
2945 return;
2946 if (detail::sort_nwk(beg, end, cmpFunc))
2947 return;
2948
2949 quick_sort(beg, 0, (int)n - 1, cmpFunc);
2950 }
2951
2957 template <typename C, typename TCmpFunc>
2958 void sort(C& c, TCmpFunc cmpFunc) {
2959 sort(c.begin(), c.end(), cmpFunc);
2960 }
2961
2974 template <typename T, typename TCmpFunc, typename TSwapFunc>
2975 void sort(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2976 const auto n = (uintptr_t)(end - beg);
2977 if (detail::try_sorted_or_reversed(beg, (uint32_t)n, cmpFunc, swapFunc))
2978 return;
2979 if (detail::sort_nwk(beg, end, cmpFunc, swapFunc))
2980 return;
2981
2982 quick_sort(beg, 0, (int)n - 1, cmpFunc, swapFunc);
2983 }
2984
2992 template <typename C, typename TCmpFunc, typename TSwapFunc>
2993 void sort(C& c, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2994 sort(c.begin(), c.end(), cmpFunc, swapFunc);
2995 }
2996 } // namespace core
2997} // namespace gaia
gaia
Checks if endianess was detected correctly at compile-time.
Definition bitset.h:9
gaia::BadIndex
constexpr uint32_t BadIndex
Sentinel index value returned by helpers when a lookup fails.
Definition utility.h:20
gaia::core::detail::is_complete
False branch for incomplete-type detection.
Definition utility.h:60
gaia::core::detail::is_mut
Detects mutable pointer or reference types for internal forwarding traits.
Definition utility.h:54
gaia::core::detail::member_func_checker< Default, std::void_t< Op< Args... > >, Op, Args... >::type
Op< Args... > type
Successfully formed operation type.
Definition utility.h:690
gaia::core::detail::member_func_checker< Default, std::void_t< Op< Args... > >, Op, Args... >::value_t
std::true_type value_t
Probe result type.
Definition utility.h:688
gaia::core::detail::member_func_checker
False branch for member-function detection.
Definition utility.h:674
gaia::core::detail::member_func_checker::value_t
std::false_type value_t
Probe result type.
Definition utility.h:676
gaia::core::detail::member_func_checker::type
Default type
Fallback type returned when the probe fails.
Definition utility.h:678
gaia::core::detail::member_func_none
Sentinel type used when a member-function probe fails.
Definition utility.h:694
gaia::core::detail::rem_rp
Removes reference and pointer qualifiers for internal type traits.
Definition utility.h:43
gaia::core::detail::rem_rp::type
std::remove_reference_t< std::remove_pointer_t< T > > type
Type after removing reference and pointer qualifiers.
Definition utility.h:45
gaia::core::detail::type_identity
Carries T as a nested type alias.
Definition utility.h:596
gaia::core::detail::type_identity::type
T type
Carried type.
Definition utility.h:598
gaia::core::equal_to
Equality comparison functor using operator==.
Definition utility.h:1355
gaia::core::equal_to::operator()
constexpr bool operator()(const T &lhs, const T &rhs) const
Compares two values for equality.
Definition utility.h:1360
gaia::core::func_type_list
Lightweight carrier for a function argument type pack.
Definition utility.h:643
gaia::core::has_data_size
Detects containers exposing both data() and size().
Definition utility.h:218
gaia::core::has_ffunc_equals
Detects whether T supports a free operator==.
Definition utility.h:766
gaia::core::has_ffunc_equals::value
static constexpr bool value
True when the free equality operator probe succeeds.
Definition utility.h:768
gaia::core::has_func_equals
Detects whether T defines operator== as a member function.
Definition utility.h:758
gaia::core::has_func_equals::value
static constexpr bool value
True when the member equality operator probe succeeds.
Definition utility.h:760
gaia::core::has_size_begin_end
Detects containers exposing begin(), end(), and size().
Definition utility.h:233
gaia::core::is_greater
Strict weak ordering functor using operator>.
Definition utility.h:1394
gaia::core::is_greater::operator()
constexpr bool operator()(const T &lhs, const T &rhs) const
Compares whether the left value is greater than the right value.
Definition utility.h:1399
gaia::core::is_smaller_or_equal
Comparison functor using operator<=.
Definition utility.h:1381
gaia::core::is_smaller_or_equal::operator()
constexpr bool operator()(const T &lhs, const T &rhs) const
Compares whether the left value is smaller than or equal to the right value.
Definition utility.h:1386
gaia::core::is_smaller
Strict weak ordering functor using operator<.
Definition utility.h:1368
gaia::core::is_smaller::operator()
constexpr bool operator()(const T &lhs, const T &rhs) const
Compares whether the left value is smaller than the right value.
Definition utility.h:1373
gaia::core::lock_scope
RAII helper that calls lock() on construction and unlock() on destruction.
Definition utility.h:186
gaia::core::lock_scope::m_ctx
T & m_ctx
Guarded lockable object.
Definition utility.h:188
gaia::core::lock_scope::operator=
lock_scope & operator=(const lock_scope &)=delete
Copy assignment is disabled because the lock ownership is scoped.
gaia::core::lock_scope::lock_scope
lock_scope(lock_scope &&)=delete
Move construction is disabled because the lock ownership is scoped.
gaia::core::lock_scope::lock_scope
lock_scope(T &ctx)
Acquires the lock represented by ctx.
Definition utility.h:192
gaia::core::lock_scope::lock_scope
lock_scope(const lock_scope &)=delete
Copy construction is disabled because the lock ownership is scoped.
gaia::core::lock_scope::~lock_scope
~lock_scope()
Releases the guarded lock.
Definition utility.h:196
gaia::core::lock_scope::operator=
lock_scope & operator=(lock_scope &&)=delete
Move assignment is disabled because the lock ownership is scoped.
gaia::core::type_list_concat
Concatenates two type_list instances.
Definition utility.h:789
gaia::core::type_list
Compile-time list of types.
Definition utility.h:778
gaia::core::type_list::size
static constexpr auto size
Number of stored types.
Definition utility.h:782
gaia::core::unique
Builds a tuple type from the first occurrence of each type in a parameter pack.
Definition utility.h:606
gaia::core::zero_t
Tag type used to request zero-initialization in APIs that accept marker objects.
Definition utility.h:128
gaia::core::zero_t::zero_t
constexpr zero_t()=default
Creates the zero-initialization tag.