Gaia-ECS v1.0.0
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 {
40 namespace detail {
43 template <class T>
44 struct rem_rp {
46 using type = std::remove_reference_t<std::remove_pointer_t<T>>;
47 };
48
51 template <typename T>
52 struct is_mut:
53 std::bool_constant<
54 !std::is_const_v<typename rem_rp<T>::type> &&
55 (std::is_pointer<T>::value || std::is_reference<T>::value)> {};
56
60 template <typename Type, typename SizeProbe = size_t>
61 struct is_complete: std::false_type {};
62
65 template <typename T>
66 struct is_complete<T, decltype(sizeof(T))>: std::true_type {};
67
72 template <typename C>
73 constexpr auto size(C& c) noexcept -> decltype(c.size()) {
74 return c.size();
75 }
80 template <typename C>
81 constexpr auto size(const C& c) noexcept -> decltype(c.size()) {
82 return c.size();
83 }
88 template <typename T, auto N>
89 constexpr auto size(const T (&)[N]) noexcept {
90 return N;
91 }
92
97 template <typename C>
98 constexpr auto data(C& c) noexcept -> decltype(c.data()) {
99 return c.data();
100 }
105 template <typename C>
106 constexpr auto data(const C& c) noexcept -> decltype(c.data()) {
107 return c.data();
108 }
114 template <typename T, auto N>
115 constexpr T* data(T (&array)[N]) noexcept {
116 return array;
117 }
122 template <typename E>
123 constexpr const E* data(std::initializer_list<E> il) noexcept {
124 return il.begin();
125 }
126 } // namespace detail
128
130 struct zero_t {
131 explicit constexpr zero_t() = default;
132 };
133
135 inline constexpr zero_t zero{};
136
139 template <typename T>
140 using rem_rp_t = typename detail::rem_rp<T>::type;
141
144 template <typename T>
145 inline constexpr bool is_mut_v = detail::is_mut<T>::value;
146
149 template <typename T>
150 using raw_t = typename std::decay_t<std::remove_pointer_t<T>>;
151
154 template <typename T>
155 inline constexpr bool is_raw_v = std::is_same_v<T, raw_t<T>> && !std::is_array_v<T>;
156
159 template <typename T>
160 inline constexpr bool is_complete_v = detail::is_complete<T>::value;
161
166 template <typename T>
167 constexpr T* addressof(T& obj) noexcept {
168 return &obj;
169 }
170
173 template <typename T>
174 const T* addressof(const T&&) = delete;
175
180 template <typename T>
181 constexpr bool check_alignment(const T* ptr) noexcept {
182 return (reinterpret_cast<uintptr_t>(ptr)) % alignof(T) == 0;
183 }
184
187 template <typename T>
188 struct lock_scope {
190 T& m_ctx;
191
194 lock_scope(T& ctx): m_ctx(ctx) {
195 ctx.lock();
196 }
198 ~lock_scope() {
199 m_ctx.unlock();
200 }
201
203 lock_scope(const lock_scope&) = delete;
205 lock_scope& operator=(const lock_scope&) = delete;
207 lock_scope(lock_scope&&) = delete;
209 lock_scope& operator=(lock_scope&&) = delete;
210 };
211
212 //----------------------------------------------------------------------
213 // Container identification
214 //----------------------------------------------------------------------
215
219 template <typename T, typename Probe = void>
220 struct has_data_size: std::false_type {};
221
224 template <typename T>
225 struct has_data_size<
226 T, std::void_t< //
227 decltype(detail::data(std::declval<T>())), //
228 decltype(detail::size(std::declval<T>())) //
229 >>: std::true_type {};
230
234 template <typename T, typename Probe = void>
235 struct has_size_begin_end: std::false_type {};
236
239 template <typename T>
240 struct has_size_begin_end<
241 T, std::void_t< //
242 decltype(std::declval<T>().begin()), //
243 decltype(std::declval<T>().end()), //
244 decltype(detail::size(std::declval<T>())) //
245 >>: std::true_type {};
246
247 //----------------------------------------------------------------------
248 // Bit-byte conversion
249 //----------------------------------------------------------------------
250
255 template <typename T>
256 constexpr T as_bits(T value) {
257 static_assert(std::is_integral_v<T>);
258 return value * (T)8;
259 }
260
265 template <typename T>
266 constexpr T as_bytes(T value) {
267 static_assert(std::is_integral_v<T>);
268 return value / (T)8;
269 }
270
271 //----------------------------------------------------------------------
272 // Memory size helpers
273 //----------------------------------------------------------------------
274
279 template <typename T>
280 constexpr uint32_t count_bits(T number) {
281 uint32_t bits_needed = 0;
282 while (number > 0U) {
283 number >>= 1U;
284 ++bits_needed;
285 }
286 return bits_needed;
287 }
288
293 template <typename T>
294 constexpr bool is_pow2(T number) {
295 static_assert(std::is_integral<T>::value, "is_pow2 must be used with integer types");
296
297 return (number & (number - 1)) == 0;
298 }
299
304 template <typename T>
305 constexpr T closest_pow2(T number) {
306 static_assert(std::is_integral<T>::value, "closest_pow2 must be used with integer types");
307
308 if (is_pow2(number))
309 return number;
310
311 // Collapse all bits below the highest set bit
312 number |= number >> 1;
313 number |= number >> 2;
314 number |= number >> 4;
315 if constexpr (sizeof(T) > 1)
316 number |= number >> 8;
317 if constexpr (sizeof(T) > 2)
318 number |= number >> 16;
319 if constexpr (sizeof(T) > 4)
320 number |= number >> 32;
321
322 // The result is now one less than the next power of two, so shift back
323 return number - (number >> 1);
324 }
325
326 //----------------------------------------------------------------------
327 // Element construction / destruction
328 //----------------------------------------------------------------------
329
333 template <typename T>
334 void call_ctor_raw(T* pData) {
335 GAIA_ASSERT(pData != nullptr);
336 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T;
337 }
338
343 template <typename T>
344 void call_ctor_raw_n(T* pData, size_t cnt) {
345 GAIA_ASSERT(pData != nullptr);
346 for (size_t i = 0; i < cnt; ++i) {
347 auto* ptr = pData + i;
348 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T;
349 }
350 }
351
355 template <typename T>
356 void call_ctor_val(T* pData) {
357 GAIA_ASSERT(pData != nullptr);
358 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T();
359 }
360
365 template <typename T>
366 void call_ctor_val_n(T* pData, size_t cnt) {
367 GAIA_ASSERT(pData != nullptr);
368 for (size_t i = 0; i < cnt; ++i) {
369 auto* ptr = pData + i;
370 (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T();
371 }
372 }
373
378 template <typename T>
379 void call_ctor([[maybe_unused]] T* pData) {
380 GAIA_ASSERT(pData != nullptr);
381 if constexpr (!std::is_trivially_constructible_v<T>) {
382 (void)::new (pData) T();
383 }
384 }
385
390 template <typename T>
391 void call_ctor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
392 GAIA_ASSERT(pData != nullptr);
393 if constexpr (!std::is_trivially_constructible_v<T>) {
394 for (size_t i = 0; i < cnt; ++i)
395 (void)::new (pData + i) T();
396 }
397 }
398
404 template <typename T, typename... Args>
405 void call_ctor(T* pData, Args&&... args) {
406 GAIA_ASSERT(pData != nullptr);
407 if constexpr (std::is_constructible_v<T, Args...>)
408 (void)::new (pData) T(GAIA_FWD(args)...);
409 else
410 (void)::new (pData) T{GAIA_FWD(args)...};
411 }
412
417 template <typename T>
418 void call_dtor([[maybe_unused]] T* pData) {
419 GAIA_ASSERT(pData != nullptr);
420 if constexpr (!std::is_trivially_destructible_v<T>) {
421 pData->~T();
422 }
423 }
424
429 template <typename T>
430 void call_dtor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
431 GAIA_ASSERT(pData != nullptr);
432 if constexpr (!std::is_trivially_destructible_v<T>) {
433 for (size_t i = 0; i < cnt; ++i)
434 pData[i].~T();
435 }
436 }
437
438 //----------------------------------------------------------------------
439 // Element swapping
440 //----------------------------------------------------------------------
441
446 template <typename T>
447 constexpr void swap(T& left, T& right) {
448 T tmp = GAIA_MOV(left);
449 left = GAIA_MOV(right);
450 right = GAIA_MOV(tmp);
451 }
452
460 template <typename T, typename TCmpFunc>
461 constexpr void swap_if(T* c, size_t lhs, size_t rhs, TCmpFunc cmpFunc) noexcept {
462 if (!cmpFunc(c[lhs], c[rhs]))
463 core::swap(c[lhs], c[rhs]);
464 }
465
472 template <typename T, typename TCmpFunc>
473 constexpr void swap_if(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
474 if (!cmpFunc(lhs, rhs))
475 core::swap(lhs, rhs);
476 }
477
484 template <typename T, typename TCmpFunc>
485 constexpr void swap_if_not(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
486 if (cmpFunc(lhs, rhs))
487 core::swap(lhs, rhs);
488 }
489
499 template <typename T, typename TCmpFunc, typename TSwapFunc>
500 constexpr void try_swap_if(T* c, uint32_t lhs, uint32_t rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
501 if (!cmpFunc(c[lhs], c[rhs]))
502 swapFunc(lhs, rhs);
503 }
504
514 template <typename C, typename TCmpFunc, typename TSwapFunc>
515 constexpr void try_swap_if(
516 C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
517 if (!cmpFunc(c[lhs], c[rhs]))
518 swapFunc(lhs, rhs);
519 }
520
530 template <typename C, typename TCmpFunc, typename TSwapFunc>
531 constexpr void try_swap_if_not(
532 C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
533 if (cmpFunc(c[lhs], c[rhs]))
534 swapFunc(lhs, rhs);
535 }
536
537 //----------------------------------------------------------------------
538 // Value filling
539 //----------------------------------------------------------------------
540
547 template <class ForwardIt, class T>
548 constexpr void fill(ForwardIt first, ForwardIt last, const T& value) {
549 for (; first != last; ++first) {
550 *first = value;
551 }
552 }
553
554 //----------------------------------------------------------------------
555 // Value range checking
556 //----------------------------------------------------------------------
557
563 template <class T>
564 constexpr const T& get_min(const T& a, const T& b) {
565 return (b < a) ? b : a;
566 }
567
573 template <class T>
574 constexpr const T& get_max(const T& a, const T& b) {
575 return (b > a) ? b : a;
576 }
577
578 //----------------------------------------------------------------------
579 // Checking if a template arg is unique among the rest
580 //----------------------------------------------------------------------
581
584 template <typename... Types>
585 inline constexpr auto is_unique = std::true_type{};
586
590 template <typename T, typename... Rest>
591 inline constexpr auto is_unique<T, Rest...> =
592 std::bool_constant<(!std::is_same_v<T, Rest> && ...) && is_unique<Rest...>>{};
593
595 namespace detail {
598 template <typename T>
599 struct type_identity {
601 using type = T;
602 };
603 } // namespace detail
605
609 template <typename T, typename... Ts>
610 struct unique: detail::type_identity<T> {}; // TODO: In C++20 we could use std::type_identity
611
616 template <typename... Ts, typename U, typename... Us>
617 struct unique<std::tuple<Ts...>, U, Us...>:
618 std::conditional_t<
619 (std::is_same_v<U, Ts> || ...), unique<std::tuple<Ts...>, Us...>, unique<std::tuple<Ts..., U>, Us...>> {};
620
623 template <typename... Ts>
624 using unique_tuple = typename unique<std::tuple<>, Ts...>::type;
625
626 //----------------------------------------------------------------------
627 // Calculating total size of all types of tuple
628 //----------------------------------------------------------------------
629
634 template <typename... Args>
635 constexpr unsigned get_args_size(std::tuple<Args...> const& tuple) {
636 (void)tuple;
637 return (sizeof(Args) + ...);
638 }
639
640 //----------------------------------------------------------------------
641 // Function arguments type checks
642 //----------------------------------------------------------------------
643
646 template <typename... Type>
647 struct func_type_list {};
648
654 template <typename Class, typename Ret, typename... Args>
655 func_type_list<Args...> func_args(Ret (Class::*)(Args...) const);
656
657 //----------------------------------------------------------------------
658 // Member function checks
659 //----------------------------------------------------------------------
660
661#if __cpp_concepts
662 #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name) \
663 template <typename T, typename... Args> \
664 concept has_mfunc_check_##function_name = requires(T&& t, Args&&... args) { t.function_name(GAIA_FWD(args)...); }; \
665 \
666 template <typename T, typename... Args> \
667 struct has_func_##function_name { \
668 static constexpr bool value = has_mfunc_check_##function_name<T, Args...>; \
669 }
670#else
672 namespace detail {
678 template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
679 struct member_func_checker {
681 using value_t = std::false_type;
683 using type = Default;
684 };
685
690 template <class Default, template <class...> class Op, class... Args>
691 struct member_func_checker<Default, std::void_t<Op<Args...>>, Op, Args...> {
693 using value_t = std::true_type;
695 using type = Op<Args...>;
696 };
697
699 struct member_func_none {
700 ~member_func_none() = delete;
701 member_func_none(member_func_none const&) = delete;
702 member_func_none(member_func_none&&) = delete;
703 void operator=(member_func_none const&) = delete;
704 void operator=(member_func_none&&) = delete;
705 };
706 } // namespace detail
708
712 template <template <class...> class Op, typename... Args>
713 using has_mfunc = typename detail::member_func_checker<detail::member_func_none, void, Op, Args...>::value_t;
714
715 #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name) \
716 template <typename T, typename... Args> \
717 using has_mfunc_check_##function_name = decltype(std::declval<T>().function_name(std::declval<Args>()...)); \
718 \
719 template <typename T, typename... Args> \
720 struct has_func_##function_name { \
721 static constexpr bool value = gaia::core::has_mfunc<has_mfunc_check_##function_name, T, Args...>::value; \
722 }
723#endif
724
726 GAIA_DEFINE_HAS_MEMBER_FUNC(find);
727 GAIA_DEFINE_HAS_MEMBER_FUNC(find_if);
728 GAIA_DEFINE_HAS_MEMBER_FUNC(find_if_not);
730
731 //----------------------------------------------------------------------
732 // Special function checks
733 //----------------------------------------------------------------------
734
736 namespace detail {
740 template <typename T>
741 constexpr auto has_mfunc_equals_check(int)
742 -> decltype(std::declval<T>().operator==(std::declval<T>()), std::true_type{});
747 template <typename T, typename... Args>
748 constexpr std::false_type has_mfunc_equals_check(...);
749
753 template <typename T>
754 constexpr auto has_ffunc_equals_check(int)
755 -> decltype(operator==(std::declval<T>(), std::declval<T>()), std::true_type{});
760 template <typename T, typename... Args>
761 constexpr std::false_type has_ffunc_equals_check(...);
762 } // namespace detail
764
767 template <typename T>
768 struct has_func_equals {
770 static constexpr bool value = decltype(detail::has_mfunc_equals_check<T>(0))::value;
771 };
772
775 template <typename T>
776 struct has_ffunc_equals {
778 static constexpr bool value = decltype(detail::has_ffunc_equals_check<T>(0))::value;
779 };
780
781 //----------------------------------------------------------------------
782 // Type helpers
783 //----------------------------------------------------------------------
784
787 template <typename... Type>
788 struct type_list {
790 using types = type_list;
792 static constexpr auto size = sizeof...(Type);
793 };
794
798 template <typename TypesA, typename TypesB>
799 struct type_list_concat;
800
804 template <typename... TypesA, typename... TypesB>
805 struct type_list_concat<type_list<TypesA...>, type_list<TypesB...>> {
807 using type = type_list<TypesA..., TypesB...>;
808 };
809
810 //----------------------------------------------------------------------
811 // Looping
812 //----------------------------------------------------------------------
813
815 namespace detail {
822 template <auto FirstIdx, auto Iters, typename Func, auto... Is>
823 constexpr void each_impl(Func func, std::integer_sequence<decltype(Iters), Is...> /*no_name*/) {
824 if constexpr ((std::is_invocable_v<Func&&, std::integral_constant<decltype(Is), Is>> && ...))
825 (func(std::integral_constant<decltype(Is), FirstIdx + Is>{}), ...);
826 else
827 (((void)Is, func()), ...);
828 }
829
836 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
837 void each_tuple_impl(Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
838 if constexpr (
839 (std::is_invocable_v<
840 Func&&, decltype(std::tuple_element_t<FirstIdx + Is, Tuple>{}),
841 std::integral_constant<decltype(FirstIdx), Is>> &&
842 ...))
843 // func(Args&& arg, uint32_t idx)
844 (func(
845 std::tuple_element_t<FirstIdx + Is, Tuple>{},
846 std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}),
847 ...);
848 else
849 // func(Args&& arg)
850 (func(std::tuple_element_t<FirstIdx + Is, Tuple>{}), ...);
851 }
852
860 template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
861 void each_tuple_impl(Tuple&& tuple, Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
862 if constexpr (
863 (std::is_invocable_v<
864 Func&&, decltype(std::get<FirstIdx + Is>(tuple)), std::integral_constant<decltype(FirstIdx), Is>> &&
865 ...))
866 // func(Args&& arg, uint32_t idx)
867 (func(std::get<FirstIdx + Is>(tuple), std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}), ...);
868 else
869 // func(Args&& arg)
870 (func(std::get<FirstIdx + Is>(tuple)), ...);
871 }
872 } // namespace detail
874
891 template <auto Iters, typename Func>
892 constexpr void each(Func func) {
893 using TIters = decltype(Iters);
894 constexpr TIters First = 0;
895 detail::each_impl<First, Iters, Func>(func, std::make_integer_sequence<TIters, Iters>());
896 }
897
916 template <auto FirstIdx, auto LastIdx, typename Func>
917 constexpr void each_ext(Func func) {
918 static_assert(LastIdx >= FirstIdx);
919 const auto Iters = LastIdx - FirstIdx;
920 detail::each_impl<FirstIdx, Iters, Func>(func, std::make_integer_sequence<decltype(Iters), Iters>());
921 }
922
942 template <auto FirstIdx, auto LastIdx, auto Inc, typename Func>
943 constexpr void each_ext(Func func) {
944 if constexpr (FirstIdx < LastIdx) {
945 if constexpr (std::is_invocable_v<Func&&, std::integral_constant<decltype(FirstIdx), FirstIdx>>)
946 func(std::integral_constant<decltype(FirstIdx), FirstIdx>());
947 else
948 func();
949
950 each_ext<FirstIdx + Inc, LastIdx, Inc>(func);
951 }
952 }
953
968 template <typename Func, typename... Args>
969 constexpr void each_pack(Func func, Args&&... args) {
970 (func(GAIA_FWD(args)), ...);
971 }
972
990 template <typename Tuple, typename Func>
991 constexpr void each_tuple(Tuple&& tuple, Func func) {
992 using TTSize = uint32_t;
993 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
994 detail::each_tuple_impl<(TTSize)0>(GAIA_FWD(tuple), func, std::make_integer_sequence<TTSize, TSize>{});
995 }
996
1015 template <typename Tuple, typename Func>
1016 constexpr void each_tuple(Func func) {
1017 using TTSize = uint32_t;
1018 constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
1019 detail::each_tuple_impl<(TTSize)0, Tuple>(func, std::make_integer_sequence<TTSize, TSize>{});
1020 }
1021
1041 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
1042 constexpr void each_tuple_ext(Tuple&& tuple, Func func) {
1043 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
1044 static_assert(LastIdx >= FirstIdx);
1045 static_assert(LastIdx <= TSize);
1046 constexpr auto Iters = LastIdx - FirstIdx;
1047 detail::each_tuple_impl<FirstIdx>(GAIA_FWD(tuple), func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
1048 }
1049
1070 template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
1071 constexpr void each_tuple_ext(Func func) {
1072 constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
1073 static_assert(LastIdx >= FirstIdx);
1074 static_assert(LastIdx <= TSize);
1075 constexpr auto Iters = LastIdx - FirstIdx;
1076 detail::each_tuple_impl<FirstIdx, Tuple>(func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
1077 }
1078
1086 template <typename InputIt, typename Func>
1087 constexpr Func each(InputIt first, InputIt last, Func func) {
1088 for (; first != last; ++first)
1089 func(*first);
1090 return func;
1091 }
1092
1099 template <typename C, typename Func>
1100 constexpr auto each(const C& arr, Func func) {
1101 return each(arr.begin(), arr.end(), func);
1102 }
1103
1104 //----------------------------------------------------------------------
1105 // Lookups
1106 //----------------------------------------------------------------------
1107
1115 template <typename InputIt, typename T>
1116 constexpr InputIt find(InputIt first, InputIt last, const T& value) {
1117 if constexpr (std::is_pointer_v<InputIt>) {
1118 auto size = distance(first, last);
1119 for (decltype(size) i = 0; i < size; ++i) {
1120 if (first[i] == value)
1121 return &first[i];
1122 }
1123 } else if constexpr (is_random_iter_v<InputIt>) {
1124 auto size = distance(first, last);
1125 for (decltype(size) i = 0; i < size; ++i) {
1126 if (*(first[i]) == value)
1127 return first[i];
1128 }
1129 } else {
1130 for (; first != last; ++first) {
1131 if (*first == value)
1132 return first;
1133 }
1134 }
1135 return last;
1136 }
1137
1144 template <typename C, typename V>
1145 constexpr auto find(const C& arr, const V& item) {
1146 if constexpr (has_func_find<C>::value)
1147 return arr.find(item);
1148 else
1149 return core::find(arr.begin(), arr.end(), item);
1150 }
1151
1159 template <typename InputIt, typename Func>
1160 constexpr InputIt find_if(InputIt first, InputIt last, Func func) {
1161 if constexpr (std::is_pointer_v<InputIt>) {
1162 auto size = distance(first, last);
1163 for (decltype(size) i = 0; i < size; ++i) {
1164 if (func(first[i]))
1165 return &first[i];
1166 }
1167 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
1168 auto size = distance(first, last);
1169 for (decltype(size) i = 0; i < size; ++i) {
1170 if (func(*(first[i])))
1171 return first[i];
1172 }
1173 } else {
1174 for (; first != last; ++first) {
1175 if (func(*first))
1176 return first;
1177 }
1178 }
1179 return last;
1180 }
1181
1188 template <typename UnaryPredicate, typename C>
1189 constexpr auto find_if(const C& arr, UnaryPredicate predicate) {
1190 if constexpr (has_func_find_if<C, UnaryPredicate>::value)
1191 return arr.find_id(predicate);
1192 else
1193 return core::find_if(arr.begin(), arr.end(), predicate);
1194 }
1195
1203 template <typename InputIt, typename Func>
1204 constexpr InputIt find_if_not(InputIt first, InputIt last, Func func) {
1205 if constexpr (std::is_pointer_v<InputIt>) {
1206 auto size = distance(first, last);
1207 for (decltype(size) i = 0; i < size; ++i) {
1208 if (!func(first[i]))
1209 return &first[i];
1210 }
1211 } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
1212 auto size = distance(first, last);
1213 for (decltype(size) i = 0; i < size; ++i) {
1214 if (!func(*(first[i])))
1215 return first[i];
1216 }
1217 } else {
1218 for (; first != last; ++first) {
1219 if (!func(*first))
1220 return first;
1221 }
1222 }
1223 return last;
1224 }
1225
1232 template <typename UnaryPredicate, typename C>
1233 constexpr auto find_if_not(const C& arr, UnaryPredicate predicate) {
1234 if constexpr (has_func_find_if_not<C, UnaryPredicate>::value)
1235 return arr.find_if_not(predicate);
1236 else
1237 return core::find_if_not(arr.begin(), arr.end(), predicate);
1238 }
1239
1240 //----------------------------------------------------------------------
1241
1248 template <typename C, typename V>
1249 constexpr bool has(const C& arr, const V& item) {
1250 const auto it = find(arr, item);
1251 return it != arr.end();
1252 }
1253
1260 template <typename UnaryPredicate, typename C>
1261 constexpr bool has_if(const C& arr, UnaryPredicate predicate) {
1262 const auto it = find_if(arr, predicate);
1263 return it != arr.end();
1264 }
1265
1266 //----------------------------------------------------------------------
1267
1273 template <typename C>
1274 constexpr auto get_index(const C& arr, typename C::const_reference item) {
1275 const auto it = find(arr, item);
1276 if (it == arr.end())
1277 return BadIndex;
1278
1279 return (decltype(BadIndex))core::distance(arr.begin(), it);
1280 }
1281
1288 template <typename C>
1289 constexpr auto get_index_unsafe(const C& arr, typename C::const_reference item) {
1290 return (decltype(BadIndex))core::distance(arr.begin(), find(arr, item));
1291 }
1292
1299 template <typename UnaryPredicate, typename C>
1300 constexpr auto get_index_if(const C& arr, UnaryPredicate predicate) {
1301 const auto it = find_if(arr, predicate);
1302 if (it == arr.end())
1303 return BadIndex;
1304
1305 return (decltype(BadIndex))core::distance(arr.begin(), it);
1306 }
1307
1315 template <typename UnaryPredicate, typename C>
1316 constexpr auto get_index_if_unsafe(const C& arr, UnaryPredicate predicate) {
1317 return (decltype(BadIndex))core::distance(arr.begin(), find_if(arr, predicate));
1318 }
1319
1320 //----------------------------------------------------------------------
1321 // Erasure
1322 //----------------------------------------------------------------------
1323
1332 template <typename C>
1333 void swap_erase_unsafe(C& arr, typename C::size_type idx) {
1334 GAIA_ASSERT(idx < arr.size());
1335
1336 if (idx + 1 != arr.size())
1337 arr[idx] = arr[arr.size() - 1];
1338
1339 arr.pop_back();
1340 }
1341
1349 template <typename C>
1350 void swap_erase(C& arr, typename C::size_type idx) {
1351 if (idx >= arr.size())
1352 return;
1353
1354 if (idx + 1 != arr.size())
1355 arr[idx] = arr[arr.size() - 1];
1356
1357 arr.pop_back();
1358 }
1359
1360 //----------------------------------------------------------------------
1361 // Comparison
1362 //----------------------------------------------------------------------
1363
1366 template <typename T>
1367 struct equal_to {
1372 constexpr bool operator()(const T& lhs, const T& rhs) const {
1373 return lhs == rhs;
1374 }
1375 };
1376
1379 template <typename T>
1380 struct is_smaller {
1385 constexpr bool operator()(const T& lhs, const T& rhs) const {
1386 return lhs < rhs;
1387 }
1388 };
1389
1392 template <typename T>
1393 struct is_smaller_or_equal {
1398 constexpr bool operator()(const T& lhs, const T& rhs) const {
1399 return lhs <= rhs;
1400 }
1401 };
1402
1405 template <typename T>
1406 struct is_greater {
1411 constexpr bool operator()(const T& lhs, const T& rhs) const {
1412 return lhs > rhs;
1413 }
1414 };
1415
1416 //----------------------------------------------------------------------
1417 // Sorting
1418 //----------------------------------------------------------------------
1419
1421 namespace detail {
1431 template <typename Container, typename TCmpFunc>
1432 int sort_median_of_three(Container& arr, int low, int mid, int high, TCmpFunc cmpFunc) {
1433 if (cmpFunc(arr[(uint32_t)low], arr[(uint32_t)mid])) {
1434 if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)high]))
1435 return mid;
1436 return cmpFunc(arr[(uint32_t)low], arr[(uint32_t)high]) ? high : low;
1437 }
1438
1439 if (cmpFunc(arr[(uint32_t)low], arr[(uint32_t)high]))
1440 return low;
1441 return cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)high]) ? high : mid;
1442 }
1443
1452 template <typename Container, typename TCmpFunc>
1453 int sort_choose_pivot(Container& arr, int low, int high, TCmpFunc cmpFunc) {
1454 const int size = high - low + 1;
1455 const int mid = low + (size >> 1);
1456 if (size > 1024) {
1457 const int step = size >> 3;
1458 const int lowMed = sort_median_of_three(arr, low, low + step, low + step + step, cmpFunc);
1459 const int midMed = sort_median_of_three(arr, mid - step, mid, mid + step, cmpFunc);
1460 const int highMed = sort_median_of_three(arr, high - step - step, high - step, high, cmpFunc);
1461 return sort_median_of_three(arr, lowMed, midMed, highMed, cmpFunc);
1462 }
1463
1464 return sort_median_of_three(arr, low, mid, high, cmpFunc);
1465 }
1466
1476 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1477 void insertion_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1478 for (int i = low + 1; i <= high; ++i) {
1479 for (int j = i; j > low && cmpFunc(arr[(uint32_t)j], arr[(uint32_t)(j - 1)]); --j)
1480 swapFunc((uint32_t)(j - 1), (uint32_t)j);
1481 }
1482 }
1483
1493 template <typename Container, typename TCmpFunc>
1494 void insertion_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc) {
1495 for (int i = low + 1; i <= high; ++i) {
1496 if (cmpFunc(arr[(uint32_t)i], arr[(uint32_t)(i - 1)])) {
1497 auto tmp = GAIA_MOV(arr[(uint32_t)i]);
1498 int j = i;
1499 do {
1500 arr[(uint32_t)j] = GAIA_MOV(arr[(uint32_t)(j - 1)]);
1501 --j;
1502 } while (j > low && cmpFunc(tmp, arr[(uint32_t)(j - 1)]));
1503 arr[(uint32_t)j] = GAIA_MOV(tmp);
1504 }
1505 }
1506 }
1507
1518 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1519 void sort_order_three(Container& arr, int lhs, int mid, int rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1520 if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)lhs]))
1521 swapFunc((uint32_t)lhs, (uint32_t)mid);
1522 if (cmpFunc(arr[(uint32_t)rhs], arr[(uint32_t)mid])) {
1523 swapFunc((uint32_t)mid, (uint32_t)rhs);
1524 if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)lhs]))
1525 swapFunc((uint32_t)lhs, (uint32_t)mid);
1526 }
1527 }
1528
1539 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1540 void sort_prepare_pivot_first(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1541 constexpr int NintherThreshold = 128;
1542 const int size = high - low + 1;
1543 const int mid = low + (size >> 1);
1544
1545 if (size > NintherThreshold) {
1546 sort_order_three(arr, low, mid, high, cmpFunc, swapFunc);
1547 sort_order_three(arr, low + 1, mid - 1, high - 1, cmpFunc, swapFunc);
1548 sort_order_three(arr, low + 2, mid + 1, high - 2, cmpFunc, swapFunc);
1549 sort_order_three(arr, mid - 1, mid, mid + 1, cmpFunc, swapFunc);
1550 swapFunc((uint32_t)low, (uint32_t)mid);
1551 } else {
1552 sort_order_three(arr, mid, low, high, cmpFunc, swapFunc);
1553 }
1554 }
1555
1566 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1567 int quick_sort_partition_pivot_first(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1568 const int begin = low;
1569 int first = low;
1570 int last = high + 1;
1571 const int end = last;
1572 auto pivot = GAIA_MOV(arr[(uint32_t)first]);
1573
1574 do {
1575 ++first;
1576 } while (first != end && cmpFunc(arr[(uint32_t)first], pivot));
1577
1578 if (begin == first - 1) {
1579 while (first < last && !cmpFunc(arr[(uint32_t)(--last)], pivot)) {
1580 }
1581 } else {
1582 do {
1583 --last;
1584 } while (!cmpFunc(arr[(uint32_t)last], pivot));
1585 }
1586
1587 while (first < last) {
1588 swapFunc((uint32_t)first, (uint32_t)last);
1589 do {
1590 ++first;
1591 } while (cmpFunc(arr[(uint32_t)first], pivot));
1592 do {
1593 --last;
1594 } while (!cmpFunc(arr[(uint32_t)last], pivot));
1595 }
1596
1597 const int pivotPos = first - 1;
1598 if (begin != pivotPos)
1599 arr[(uint32_t)begin] = GAIA_MOV(arr[(uint32_t)pivotPos]);
1600 arr[(uint32_t)pivotPos] = GAIA_MOV(pivot);
1601 return pivotPos;
1602 }
1603
1613 template <typename T, typename TCmpFunc, typename TSwapFunc>
1614 bool try_sorted_or_reversed(T* beg, uint32_t n, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1615 if (n <= 1)
1616 return true;
1617
1618 bool sorted = true;
1619 for (uint32_t i = 1; i < n; ++i) {
1620 if (cmpFunc(beg[i], beg[i - 1])) {
1621 sorted = false;
1622 break;
1623 }
1624 }
1625 if (sorted)
1626 return true;
1627
1628 bool reversed = true;
1629 for (uint32_t i = 1; i < n; ++i) {
1630 if (cmpFunc(beg[i - 1], beg[i])) {
1631 reversed = false;
1632 break;
1633 }
1634 }
1635 if (!reversed)
1636 return false;
1637
1638 for (uint32_t i = 0, j = n - 1; i < j; ++i, --j)
1639 swapFunc(i, j);
1640 return true;
1641 }
1642
1653 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1654 int quick_sort_partition_hoare(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1655 const int pivotIdx = sort_choose_pivot(arr, low, high, cmpFunc);
1656 const auto pivot = arr[(uint32_t)pivotIdx];
1657
1658 int i = low - 1;
1659 int j = high + 1;
1660
1661 while (true) {
1662 do {
1663 ++i;
1664 } while (cmpFunc(arr[(uint32_t)i], pivot));
1665
1666 do {
1667 --j;
1668 } while (cmpFunc(pivot, arr[(uint32_t)j]));
1669
1670 if (i >= j)
1671 return j;
1672
1673 swapFunc((uint32_t)i, (uint32_t)j);
1674 }
1675 }
1676
1687 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1688 void heap_sift_down(Container& arr, int low, int root, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1689 while (true) {
1690 const int left = low + ((root - low) << 1) + 1;
1691 if (left > high)
1692 return;
1693
1694 int child = left;
1695 const int right = left + 1;
1696 if (right <= high && cmpFunc(arr[(uint32_t)child], arr[(uint32_t)right]))
1697 child = right;
1698
1699 if (!cmpFunc(arr[(uint32_t)root], arr[(uint32_t)child]))
1700 return;
1701
1702 swapFunc((uint32_t)root, (uint32_t)child);
1703 root = child;
1704 }
1705 }
1706
1716 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1717 void heap_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
1718 for (int start = low + ((high - low - 1) >> 1); start >= low; --start)
1719 heap_sift_down(arr, low, start, high, cmpFunc, swapFunc);
1720
1721 for (int end = high; end > low; --end) {
1722 swapFunc((uint32_t)low, (uint32_t)end);
1723 heap_sift_down(arr, low, low, end - 1, cmpFunc, swapFunc);
1724 }
1725 }
1726
1730 inline uint32_t sort_depth_limit(uint32_t n) {
1731 uint32_t depth = 0;
1732 while (n > 1) {
1733 ++depth;
1734 n >>= 1;
1735 }
1736 return depth * 2;
1737 }
1738
1749 template <typename Container, typename TCmpFunc, typename TSwapFunc>
1750 void
1751 quick_sort_impl(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc, uint32_t depthLimit) {
1752 constexpr int InsertionSortThreshold = 24;
1753
1754 while (high - low > InsertionSortThreshold) {
1755 if (depthLimit == 0) {
1756 heap_sort_range(arr, low, high, cmpFunc, swapFunc);
1757 return;
1758 }
1759 --depthLimit;
1760
1761 const int split = quick_sort_partition_hoare(arr, low, high, cmpFunc, swapFunc);
1762 const int leftSize = split - low + 1;
1763 const int rightSize = high - split;
1764
1765 if (leftSize < rightSize) {
1766 quick_sort_impl(arr, low, split, cmpFunc, swapFunc, depthLimit);
1767 low = split + 1;
1768 } else {
1769 quick_sort_impl(arr, split + 1, high, cmpFunc, swapFunc, depthLimit);
1770 high = split;
1771 }
1772 }
1773
1774 if (low < high)
1775 insertion_sort_range(arr, low, high, cmpFunc, swapFunc);
1776 }
1777
1788 template <typename Container, typename TCmpFunc>
1789 void quick_sort_impl(Container& arr, int low, int high, TCmpFunc cmpFunc, uint32_t depthLimit) {
1790 constexpr int InsertionSortThreshold = 24;
1791 auto swapFunc = [&arr](uint32_t a, uint32_t b) {
1792 core::swap(arr[a], arr[b]);
1793 };
1794
1795 while (high - low > InsertionSortThreshold) {
1796 if (depthLimit == 0) {
1797 heap_sort_range(arr, low, high, cmpFunc, swapFunc);
1798 return;
1799 }
1800 --depthLimit;
1801
1802 sort_prepare_pivot_first(arr, low, high, cmpFunc, swapFunc);
1803 const int pivot = quick_sort_partition_pivot_first(arr, low, high, cmpFunc, swapFunc);
1804 const int leftSize = pivot - low;
1805 const int rightSize = high - pivot;
1806
1807 if (leftSize < rightSize) {
1808 quick_sort_impl(arr, low, pivot - 1, cmpFunc, depthLimit);
1809 low = pivot + 1;
1810 } else {
1811 quick_sort_impl(arr, pivot + 1, high, cmpFunc, depthLimit);
1812 high = pivot - 1;
1813 }
1814 }
1815
1816 if (low < high)
1817 insertion_sort_range(arr, low, high, cmpFunc);
1818 }
1819
1827 template <typename T, typename TCmpFunc>
1828 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc) {
1829 const auto n = (uint32_t)(end - beg);
1830 if (n <= 1) {
1831 // Nothing to sort with just one item
1832 } else if (n == 2) {
1833 swap_if(beg, 0, 1, cmpFunc);
1834 } else if (n == 3) {
1835 swap_if(beg, 1, 2, cmpFunc);
1836 swap_if(beg, 0, 2, cmpFunc);
1837 swap_if(beg, 0, 1, cmpFunc);
1838 } else if (n == 4) {
1839 swap_if(beg, 0, 1, cmpFunc);
1840 swap_if(beg, 2, 3, cmpFunc);
1841
1842 swap_if(beg, 0, 2, cmpFunc);
1843 swap_if(beg, 1, 3, cmpFunc);
1844
1845 swap_if(beg, 1, 2, cmpFunc);
1846 } else if (n == 5) {
1847 swap_if(beg, 0, 1, cmpFunc);
1848 swap_if(beg, 3, 4, cmpFunc);
1849
1850 swap_if(beg, 2, 4, cmpFunc);
1851
1852 swap_if(beg, 2, 3, cmpFunc);
1853 swap_if(beg, 1, 4, cmpFunc);
1854
1855 swap_if(beg, 0, 3, cmpFunc);
1856
1857 swap_if(beg, 0, 2, cmpFunc);
1858 swap_if(beg, 1, 3, cmpFunc);
1859
1860 swap_if(beg, 1, 2, cmpFunc);
1861 } else if (n == 6) {
1862 swap_if(beg, 1, 2, cmpFunc);
1863 swap_if(beg, 4, 5, cmpFunc);
1864
1865 swap_if(beg, 0, 2, cmpFunc);
1866 swap_if(beg, 3, 5, cmpFunc);
1867
1868 swap_if(beg, 0, 1, cmpFunc);
1869 swap_if(beg, 3, 4, cmpFunc);
1870 swap_if(beg, 2, 5, cmpFunc);
1871
1872 swap_if(beg, 0, 3, cmpFunc);
1873 swap_if(beg, 1, 4, cmpFunc);
1874
1875 swap_if(beg, 2, 4, cmpFunc);
1876 swap_if(beg, 1, 3, cmpFunc);
1877
1878 swap_if(beg, 2, 3, cmpFunc);
1879 } else if (n == 7) {
1880 swap_if(beg, 1, 2, cmpFunc);
1881 swap_if(beg, 3, 4, cmpFunc);
1882 swap_if(beg, 5, 6, cmpFunc);
1883
1884 swap_if(beg, 0, 2, cmpFunc);
1885 swap_if(beg, 3, 5, cmpFunc);
1886 swap_if(beg, 4, 6, cmpFunc);
1887
1888 swap_if(beg, 0, 1, cmpFunc);
1889 swap_if(beg, 4, 5, cmpFunc);
1890 swap_if(beg, 2, 6, cmpFunc);
1891
1892 swap_if(beg, 0, 4, cmpFunc);
1893 swap_if(beg, 1, 5, cmpFunc);
1894
1895 swap_if(beg, 0, 3, cmpFunc);
1896 swap_if(beg, 2, 5, cmpFunc);
1897
1898 swap_if(beg, 1, 3, cmpFunc);
1899 swap_if(beg, 2, 4, cmpFunc);
1900
1901 swap_if(beg, 2, 3, cmpFunc);
1902 } else if (n == 8) {
1903 swap_if(beg, 0, 1, cmpFunc);
1904 swap_if(beg, 2, 3, cmpFunc);
1905 swap_if(beg, 4, 5, cmpFunc);
1906 swap_if(beg, 6, 7, cmpFunc);
1907
1908 swap_if(beg, 0, 2, cmpFunc);
1909 swap_if(beg, 1, 3, cmpFunc);
1910 swap_if(beg, 4, 6, cmpFunc);
1911 swap_if(beg, 5, 7, cmpFunc);
1912
1913 swap_if(beg, 1, 2, cmpFunc);
1914 swap_if(beg, 5, 6, cmpFunc);
1915 swap_if(beg, 0, 4, cmpFunc);
1916 swap_if(beg, 3, 7, cmpFunc);
1917
1918 swap_if(beg, 1, 5, cmpFunc);
1919 swap_if(beg, 2, 6, cmpFunc);
1920
1921 swap_if(beg, 1, 4, cmpFunc);
1922 swap_if(beg, 3, 6, cmpFunc);
1923
1924 swap_if(beg, 2, 4, cmpFunc);
1925 swap_if(beg, 3, 5, cmpFunc);
1926
1927 swap_if(beg, 3, 4, cmpFunc);
1928 } else if (n == 9) {
1929 swap_if(beg, 0, 1, cmpFunc);
1930 swap_if(beg, 3, 4, cmpFunc);
1931 swap_if(beg, 6, 7, cmpFunc);
1932 swap_if(beg, 1, 2, cmpFunc);
1933 swap_if(beg, 4, 5, cmpFunc);
1934 swap_if(beg, 7, 8, cmpFunc);
1935 swap_if(beg, 0, 1, cmpFunc);
1936 swap_if(beg, 3, 4, cmpFunc);
1937 swap_if(beg, 6, 7, cmpFunc);
1938 swap_if(beg, 0, 3, cmpFunc);
1939 swap_if(beg, 3, 6, cmpFunc);
1940 swap_if(beg, 0, 3, cmpFunc);
1941 swap_if(beg, 1, 4, cmpFunc);
1942 swap_if(beg, 4, 7, cmpFunc);
1943 swap_if(beg, 1, 4, cmpFunc);
1944 swap_if(beg, 2, 5, cmpFunc);
1945 swap_if(beg, 5, 8, cmpFunc);
1946 swap_if(beg, 2, 5, cmpFunc);
1947 swap_if(beg, 1, 3, cmpFunc);
1948 swap_if(beg, 5, 7, cmpFunc);
1949 swap_if(beg, 2, 6, cmpFunc);
1950 swap_if(beg, 4, 6, cmpFunc);
1951 swap_if(beg, 2, 4, cmpFunc);
1952 swap_if(beg, 2, 3, cmpFunc);
1953 swap_if(beg, 5, 6, cmpFunc);
1954 } else if (n == 10) {
1955 swap_if(beg, 0, 8, cmpFunc);
1956 swap_if(beg, 1, 9, cmpFunc);
1957 swap_if(beg, 2, 7, cmpFunc);
1958 swap_if(beg, 3, 6, cmpFunc);
1959 swap_if(beg, 4, 5, cmpFunc);
1960
1961 swap_if(beg, 0, 2, cmpFunc);
1962 swap_if(beg, 1, 3, cmpFunc);
1963 swap_if(beg, 4, 8, cmpFunc);
1964 swap_if(beg, 5, 7, cmpFunc);
1965 swap_if(beg, 6, 9, cmpFunc);
1966
1967 swap_if(beg, 0, 4, cmpFunc);
1968 swap_if(beg, 1, 5, cmpFunc);
1969 swap_if(beg, 2, 6, cmpFunc);
1970 swap_if(beg, 3, 7, cmpFunc);
1971
1972 swap_if(beg, 0, 1, cmpFunc);
1973 swap_if(beg, 2, 3, cmpFunc);
1974 swap_if(beg, 4, 6, cmpFunc);
1975 swap_if(beg, 5, 9, cmpFunc);
1976 swap_if(beg, 7, 8, cmpFunc);
1977
1978 swap_if(beg, 1, 2, cmpFunc);
1979 swap_if(beg, 3, 5, cmpFunc);
1980 swap_if(beg, 6, 7, cmpFunc);
1981 swap_if(beg, 8, 9, cmpFunc);
1982
1983 swap_if(beg, 2, 4, cmpFunc);
1984 swap_if(beg, 3, 6, cmpFunc);
1985 swap_if(beg, 5, 8, cmpFunc);
1986
1987 swap_if(beg, 1, 2, cmpFunc);
1988 swap_if(beg, 3, 4, cmpFunc);
1989 swap_if(beg, 5, 6, cmpFunc);
1990 swap_if(beg, 7, 8, cmpFunc);
1991 } else if (n == 11) {
1992 swap_if(beg, 0, 9, cmpFunc);
1993 swap_if(beg, 1, 6, cmpFunc);
1994 swap_if(beg, 2, 4, cmpFunc);
1995 swap_if(beg, 3, 7, cmpFunc);
1996 swap_if(beg, 5, 8, cmpFunc);
1997 swap_if(beg, 0, 1, cmpFunc);
1998 swap_if(beg, 3, 5, cmpFunc);
1999 swap_if(beg, 4, 10, cmpFunc);
2000 swap_if(beg, 6, 9, cmpFunc);
2001 swap_if(beg, 7, 8, cmpFunc);
2002 swap_if(beg, 1, 3, cmpFunc);
2003 swap_if(beg, 2, 5, cmpFunc);
2004 swap_if(beg, 4, 7, cmpFunc);
2005 swap_if(beg, 8, 10, cmpFunc);
2006 swap_if(beg, 0, 4, cmpFunc);
2007 swap_if(beg, 1, 2, cmpFunc);
2008 swap_if(beg, 3, 7, cmpFunc);
2009 swap_if(beg, 5, 9, cmpFunc);
2010 swap_if(beg, 6, 8, cmpFunc);
2011 swap_if(beg, 0, 1, cmpFunc);
2012 swap_if(beg, 2, 6, cmpFunc);
2013 swap_if(beg, 4, 5, cmpFunc);
2014 swap_if(beg, 7, 8, cmpFunc);
2015 swap_if(beg, 9, 10, cmpFunc);
2016 swap_if(beg, 2, 4, cmpFunc);
2017 swap_if(beg, 3, 6, cmpFunc);
2018 swap_if(beg, 5, 7, cmpFunc);
2019 swap_if(beg, 8, 9, cmpFunc);
2020 swap_if(beg, 1, 2, cmpFunc);
2021 swap_if(beg, 3, 4, cmpFunc);
2022 swap_if(beg, 5, 6, cmpFunc);
2023 swap_if(beg, 7, 8, cmpFunc);
2024 swap_if(beg, 2, 3, cmpFunc);
2025 swap_if(beg, 4, 5, cmpFunc);
2026 swap_if(beg, 6, 7, cmpFunc);
2027 } else if (n == 12) {
2028 swap_if(beg, 0, 8, cmpFunc);
2029 swap_if(beg, 1, 7, cmpFunc);
2030 swap_if(beg, 2, 6, cmpFunc);
2031 swap_if(beg, 3, 11, cmpFunc);
2032 swap_if(beg, 4, 10, cmpFunc);
2033 swap_if(beg, 5, 9, cmpFunc);
2034 swap_if(beg, 0, 1, cmpFunc);
2035 swap_if(beg, 2, 5, cmpFunc);
2036 swap_if(beg, 3, 4, cmpFunc);
2037 swap_if(beg, 6, 9, cmpFunc);
2038 swap_if(beg, 7, 8, cmpFunc);
2039 swap_if(beg, 10, 11, cmpFunc);
2040 swap_if(beg, 0, 2, cmpFunc);
2041 swap_if(beg, 1, 6, cmpFunc);
2042 swap_if(beg, 5, 10, cmpFunc);
2043 swap_if(beg, 9, 11, cmpFunc);
2044 swap_if(beg, 0, 3, cmpFunc);
2045 swap_if(beg, 1, 2, cmpFunc);
2046 swap_if(beg, 4, 6, cmpFunc);
2047 swap_if(beg, 5, 7, cmpFunc);
2048 swap_if(beg, 8, 11, cmpFunc);
2049 swap_if(beg, 9, 10, cmpFunc);
2050 swap_if(beg, 1, 4, cmpFunc);
2051 swap_if(beg, 3, 5, cmpFunc);
2052 swap_if(beg, 6, 8, cmpFunc);
2053 swap_if(beg, 7, 10, cmpFunc);
2054 swap_if(beg, 1, 3, cmpFunc);
2055 swap_if(beg, 2, 5, cmpFunc);
2056 swap_if(beg, 6, 9, cmpFunc);
2057 swap_if(beg, 8, 10, cmpFunc);
2058 swap_if(beg, 2, 3, cmpFunc);
2059 swap_if(beg, 4, 5, cmpFunc);
2060 swap_if(beg, 6, 7, cmpFunc);
2061 swap_if(beg, 8, 9, cmpFunc);
2062 swap_if(beg, 4, 6, cmpFunc);
2063 swap_if(beg, 5, 7, cmpFunc);
2064 swap_if(beg, 3, 4, cmpFunc);
2065 swap_if(beg, 5, 6, cmpFunc);
2066 swap_if(beg, 7, 8, cmpFunc);
2067 } else if (n == 13) {
2068 swap_if(beg, 0, 12, cmpFunc);
2069 swap_if(beg, 1, 10, cmpFunc);
2070 swap_if(beg, 2, 9, cmpFunc);
2071 swap_if(beg, 3, 7, cmpFunc);
2072 swap_if(beg, 5, 11, cmpFunc);
2073 swap_if(beg, 6, 8, cmpFunc);
2074 swap_if(beg, 1, 6, cmpFunc);
2075 swap_if(beg, 2, 3, cmpFunc);
2076 swap_if(beg, 4, 11, cmpFunc);
2077 swap_if(beg, 7, 9, cmpFunc);
2078 swap_if(beg, 8, 10, cmpFunc);
2079 swap_if(beg, 0, 4, cmpFunc);
2080 swap_if(beg, 1, 2, cmpFunc);
2081 swap_if(beg, 3, 6, cmpFunc);
2082 swap_if(beg, 7, 8, cmpFunc);
2083 swap_if(beg, 9, 10, cmpFunc);
2084 swap_if(beg, 11, 12, cmpFunc);
2085 swap_if(beg, 4, 6, cmpFunc);
2086 swap_if(beg, 5, 9, cmpFunc);
2087 swap_if(beg, 8, 11, cmpFunc);
2088 swap_if(beg, 10, 12, cmpFunc);
2089 swap_if(beg, 0, 5, cmpFunc);
2090 swap_if(beg, 3, 8, cmpFunc);
2091 swap_if(beg, 4, 7, cmpFunc);
2092 swap_if(beg, 6, 11, cmpFunc);
2093 swap_if(beg, 9, 10, cmpFunc);
2094 swap_if(beg, 0, 1, cmpFunc);
2095 swap_if(beg, 2, 5, cmpFunc);
2096 swap_if(beg, 6, 9, cmpFunc);
2097 swap_if(beg, 7, 8, cmpFunc);
2098 swap_if(beg, 10, 11, cmpFunc);
2099 swap_if(beg, 1, 3, cmpFunc);
2100 swap_if(beg, 2, 4, cmpFunc);
2101 swap_if(beg, 5, 6, cmpFunc);
2102 swap_if(beg, 9, 10, cmpFunc);
2103 swap_if(beg, 1, 2, cmpFunc);
2104 swap_if(beg, 3, 4, cmpFunc);
2105 swap_if(beg, 5, 7, cmpFunc);
2106 swap_if(beg, 6, 8, cmpFunc);
2107 swap_if(beg, 2, 3, cmpFunc);
2108 swap_if(beg, 4, 5, cmpFunc);
2109 swap_if(beg, 6, 7, cmpFunc);
2110 swap_if(beg, 8, 9, cmpFunc);
2111 swap_if(beg, 3, 4, cmpFunc);
2112 swap_if(beg, 5, 6, cmpFunc);
2113 } else if (n == 14) {
2114 swap_if(beg, 0, 1, cmpFunc);
2115 swap_if(beg, 2, 3, cmpFunc);
2116 swap_if(beg, 4, 5, cmpFunc);
2117 swap_if(beg, 6, 7, cmpFunc);
2118 swap_if(beg, 8, 9, cmpFunc);
2119 swap_if(beg, 10, 11, cmpFunc);
2120 swap_if(beg, 12, 13, cmpFunc);
2121 swap_if(beg, 0, 2, cmpFunc);
2122 swap_if(beg, 1, 3, cmpFunc);
2123 swap_if(beg, 4, 8, cmpFunc);
2124 swap_if(beg, 5, 9, cmpFunc);
2125 swap_if(beg, 10, 12, cmpFunc);
2126 swap_if(beg, 11, 13, cmpFunc);
2127 swap_if(beg, 0, 4, cmpFunc);
2128 swap_if(beg, 1, 2, cmpFunc);
2129 swap_if(beg, 3, 7, cmpFunc);
2130 swap_if(beg, 5, 8, cmpFunc);
2131 swap_if(beg, 6, 10, cmpFunc);
2132 swap_if(beg, 9, 13, cmpFunc);
2133 swap_if(beg, 11, 12, cmpFunc);
2134 swap_if(beg, 0, 6, cmpFunc);
2135 swap_if(beg, 1, 5, cmpFunc);
2136 swap_if(beg, 3, 9, cmpFunc);
2137 swap_if(beg, 4, 10, cmpFunc);
2138 swap_if(beg, 7, 13, cmpFunc);
2139 swap_if(beg, 8, 12, cmpFunc);
2140 swap_if(beg, 2, 10, cmpFunc);
2141 swap_if(beg, 3, 11, cmpFunc);
2142 swap_if(beg, 4, 6, cmpFunc);
2143 swap_if(beg, 7, 9, cmpFunc);
2144 swap_if(beg, 1, 3, cmpFunc);
2145 swap_if(beg, 2, 8, cmpFunc);
2146 swap_if(beg, 5, 11, cmpFunc);
2147 swap_if(beg, 6, 7, cmpFunc);
2148 swap_if(beg, 10, 12, cmpFunc);
2149 swap_if(beg, 1, 4, cmpFunc);
2150 swap_if(beg, 2, 6, cmpFunc);
2151 swap_if(beg, 3, 5, cmpFunc);
2152 swap_if(beg, 7, 11, cmpFunc);
2153 swap_if(beg, 8, 10, cmpFunc);
2154 swap_if(beg, 9, 12, cmpFunc);
2155 swap_if(beg, 2, 4, cmpFunc);
2156 swap_if(beg, 3, 6, cmpFunc);
2157 swap_if(beg, 5, 8, cmpFunc);
2158 swap_if(beg, 7, 10, cmpFunc);
2159 swap_if(beg, 9, 11, cmpFunc);
2160 swap_if(beg, 3, 4, cmpFunc);
2161 swap_if(beg, 5, 6, cmpFunc);
2162 swap_if(beg, 7, 8, cmpFunc);
2163 swap_if(beg, 9, 10, cmpFunc);
2164 swap_if(beg, 6, 7, cmpFunc);
2165 } else if (n == 15) {
2166 swap_if(beg, 1, 2, cmpFunc);
2167 swap_if(beg, 3, 10, cmpFunc);
2168 swap_if(beg, 4, 14, cmpFunc);
2169 swap_if(beg, 5, 8, cmpFunc);
2170 swap_if(beg, 6, 13, cmpFunc);
2171 swap_if(beg, 7, 12, cmpFunc);
2172 swap_if(beg, 9, 11, cmpFunc);
2173 swap_if(beg, 0, 14, cmpFunc);
2174 swap_if(beg, 1, 5, cmpFunc);
2175 swap_if(beg, 2, 8, cmpFunc);
2176 swap_if(beg, 3, 7, cmpFunc);
2177 swap_if(beg, 6, 9, cmpFunc);
2178 swap_if(beg, 10, 12, cmpFunc);
2179 swap_if(beg, 11, 13, cmpFunc);
2180 swap_if(beg, 0, 7, cmpFunc);
2181 swap_if(beg, 1, 6, cmpFunc);
2182 swap_if(beg, 2, 9, cmpFunc);
2183 swap_if(beg, 4, 10, cmpFunc);
2184 swap_if(beg, 5, 11, cmpFunc);
2185 swap_if(beg, 8, 13, cmpFunc);
2186 swap_if(beg, 12, 14, cmpFunc);
2187 swap_if(beg, 0, 6, cmpFunc);
2188 swap_if(beg, 2, 4, cmpFunc);
2189 swap_if(beg, 3, 5, cmpFunc);
2190 swap_if(beg, 7, 11, cmpFunc);
2191 swap_if(beg, 8, 10, cmpFunc);
2192 swap_if(beg, 9, 12, cmpFunc);
2193 swap_if(beg, 13, 14, cmpFunc);
2194 swap_if(beg, 0, 3, cmpFunc);
2195 swap_if(beg, 1, 2, cmpFunc);
2196 swap_if(beg, 4, 7, cmpFunc);
2197 swap_if(beg, 5, 9, cmpFunc);
2198 swap_if(beg, 6, 8, cmpFunc);
2199 swap_if(beg, 10, 11, cmpFunc);
2200 swap_if(beg, 12, 13, cmpFunc);
2201 swap_if(beg, 0, 1, cmpFunc);
2202 swap_if(beg, 2, 3, cmpFunc);
2203 swap_if(beg, 4, 6, cmpFunc);
2204 swap_if(beg, 7, 9, cmpFunc);
2205 swap_if(beg, 10, 12, cmpFunc);
2206 swap_if(beg, 11, 13, cmpFunc);
2207 swap_if(beg, 1, 2, cmpFunc);
2208 swap_if(beg, 3, 5, cmpFunc);
2209 swap_if(beg, 8, 10, cmpFunc);
2210 swap_if(beg, 11, 12, cmpFunc);
2211 swap_if(beg, 3, 4, cmpFunc);
2212 swap_if(beg, 5, 6, cmpFunc);
2213 swap_if(beg, 7, 8, cmpFunc);
2214 swap_if(beg, 9, 10, cmpFunc);
2215 swap_if(beg, 2, 3, cmpFunc);
2216 swap_if(beg, 4, 5, cmpFunc);
2217 swap_if(beg, 6, 7, cmpFunc);
2218 swap_if(beg, 8, 9, cmpFunc);
2219 swap_if(beg, 10, 11, cmpFunc);
2220 swap_if(beg, 5, 6, cmpFunc);
2221 swap_if(beg, 7, 8, cmpFunc);
2222 } else if (n == 16) {
2223 swap_if(beg, 0, 13, cmpFunc);
2224 swap_if(beg, 1, 12, cmpFunc);
2225 swap_if(beg, 2, 15, cmpFunc);
2226 swap_if(beg, 3, 14, cmpFunc);
2227 swap_if(beg, 4, 8, cmpFunc);
2228 swap_if(beg, 5, 6, cmpFunc);
2229 swap_if(beg, 7, 11, cmpFunc);
2230 swap_if(beg, 9, 10, cmpFunc);
2231 swap_if(beg, 0, 5, cmpFunc);
2232 swap_if(beg, 1, 7, cmpFunc);
2233 swap_if(beg, 2, 9, cmpFunc);
2234 swap_if(beg, 3, 4, cmpFunc);
2235 swap_if(beg, 6, 13, cmpFunc);
2236 swap_if(beg, 8, 14, cmpFunc);
2237 swap_if(beg, 10, 15, cmpFunc);
2238 swap_if(beg, 11, 12, cmpFunc);
2239 swap_if(beg, 0, 1, cmpFunc);
2240 swap_if(beg, 2, 3, cmpFunc);
2241 swap_if(beg, 4, 5, cmpFunc);
2242 swap_if(beg, 6, 8, cmpFunc);
2243 swap_if(beg, 7, 9, cmpFunc);
2244 swap_if(beg, 10, 11, cmpFunc);
2245 swap_if(beg, 12, 13, cmpFunc);
2246 swap_if(beg, 14, 15, cmpFunc);
2247 swap_if(beg, 0, 2, cmpFunc);
2248 swap_if(beg, 1, 3, cmpFunc);
2249 swap_if(beg, 4, 10, cmpFunc);
2250 swap_if(beg, 5, 11, cmpFunc);
2251 swap_if(beg, 6, 7, cmpFunc);
2252 swap_if(beg, 8, 9, cmpFunc);
2253 swap_if(beg, 12, 14, cmpFunc);
2254 swap_if(beg, 13, 15, cmpFunc);
2255 swap_if(beg, 1, 2, cmpFunc);
2256 swap_if(beg, 3, 12, cmpFunc);
2257 swap_if(beg, 4, 6, cmpFunc);
2258 swap_if(beg, 5, 7, cmpFunc);
2259 swap_if(beg, 8, 10, cmpFunc);
2260 swap_if(beg, 9, 11, cmpFunc);
2261 swap_if(beg, 13, 14, cmpFunc);
2262 swap_if(beg, 1, 4, cmpFunc);
2263 swap_if(beg, 2, 6, cmpFunc);
2264 swap_if(beg, 5, 8, cmpFunc);
2265 swap_if(beg, 7, 10, cmpFunc);
2266 swap_if(beg, 9, 13, cmpFunc);
2267 swap_if(beg, 11, 14, cmpFunc);
2268 swap_if(beg, 2, 4, cmpFunc);
2269 swap_if(beg, 3, 6, cmpFunc);
2270 swap_if(beg, 9, 12, cmpFunc);
2271 swap_if(beg, 11, 13, cmpFunc);
2272 swap_if(beg, 3, 5, cmpFunc);
2273 swap_if(beg, 6, 8, cmpFunc);
2274 swap_if(beg, 7, 9, cmpFunc);
2275 swap_if(beg, 10, 12, cmpFunc);
2276 swap_if(beg, 3, 4, cmpFunc);
2277 swap_if(beg, 5, 6, cmpFunc);
2278 swap_if(beg, 7, 8, cmpFunc);
2279 swap_if(beg, 9, 10, cmpFunc);
2280 swap_if(beg, 11, 12, cmpFunc);
2281 swap_if(beg, 6, 7, cmpFunc);
2282 swap_if(beg, 8, 9, cmpFunc);
2283 } else if (n == 17) {
2284 swap_if(beg, 0, 11, cmpFunc);
2285 swap_if(beg, 1, 15, cmpFunc);
2286 swap_if(beg, 2, 10, cmpFunc);
2287 swap_if(beg, 3, 5, cmpFunc);
2288 swap_if(beg, 4, 6, cmpFunc);
2289 swap_if(beg, 8, 12, cmpFunc);
2290 swap_if(beg, 9, 16, cmpFunc);
2291 swap_if(beg, 13, 14, cmpFunc);
2292 swap_if(beg, 0, 6, cmpFunc);
2293 swap_if(beg, 1, 13, cmpFunc);
2294 swap_if(beg, 2, 8, cmpFunc);
2295 swap_if(beg, 4, 14, cmpFunc);
2296 swap_if(beg, 5, 15, cmpFunc);
2297 swap_if(beg, 7, 11, cmpFunc);
2298 swap_if(beg, 0, 8, cmpFunc);
2299 swap_if(beg, 3, 7, cmpFunc);
2300 swap_if(beg, 4, 9, cmpFunc);
2301 swap_if(beg, 6, 16, cmpFunc);
2302 swap_if(beg, 10, 11, cmpFunc);
2303 swap_if(beg, 12, 14, cmpFunc);
2304 swap_if(beg, 0, 2, cmpFunc);
2305 swap_if(beg, 1, 4, cmpFunc);
2306 swap_if(beg, 5, 6, cmpFunc);
2307 swap_if(beg, 7, 13, cmpFunc);
2308 swap_if(beg, 8, 9, cmpFunc);
2309 swap_if(beg, 10, 12, cmpFunc);
2310 swap_if(beg, 11, 14, cmpFunc);
2311 swap_if(beg, 15, 16, cmpFunc);
2312 swap_if(beg, 0, 3, cmpFunc);
2313 swap_if(beg, 2, 5, cmpFunc);
2314 swap_if(beg, 6, 11, cmpFunc);
2315 swap_if(beg, 7, 10, cmpFunc);
2316 swap_if(beg, 9, 13, cmpFunc);
2317 swap_if(beg, 12, 15, cmpFunc);
2318 swap_if(beg, 14, 16, cmpFunc);
2319 swap_if(beg, 0, 1, cmpFunc);
2320 swap_if(beg, 3, 4, cmpFunc);
2321 swap_if(beg, 5, 10, cmpFunc);
2322 swap_if(beg, 6, 9, cmpFunc);
2323 swap_if(beg, 7, 8, cmpFunc);
2324 swap_if(beg, 11, 15, cmpFunc);
2325 swap_if(beg, 13, 14, cmpFunc);
2326 swap_if(beg, 1, 2, cmpFunc);
2327 swap_if(beg, 3, 7, cmpFunc);
2328 swap_if(beg, 4, 8, cmpFunc);
2329 swap_if(beg, 6, 12, cmpFunc);
2330 swap_if(beg, 11, 13, cmpFunc);
2331 swap_if(beg, 14, 15, cmpFunc);
2332 swap_if(beg, 1, 3, cmpFunc);
2333 swap_if(beg, 2, 7, cmpFunc);
2334 swap_if(beg, 4, 5, cmpFunc);
2335 swap_if(beg, 9, 11, cmpFunc);
2336 swap_if(beg, 10, 12, cmpFunc);
2337 swap_if(beg, 13, 14, cmpFunc);
2338 swap_if(beg, 2, 3, cmpFunc);
2339 swap_if(beg, 4, 6, cmpFunc);
2340 swap_if(beg, 5, 7, cmpFunc);
2341 swap_if(beg, 8, 10, cmpFunc);
2342 swap_if(beg, 3, 4, cmpFunc);
2343 swap_if(beg, 6, 8, cmpFunc);
2344 swap_if(beg, 7, 9, cmpFunc);
2345 swap_if(beg, 10, 12, cmpFunc);
2346 swap_if(beg, 5, 6, cmpFunc);
2347 swap_if(beg, 7, 8, cmpFunc);
2348 swap_if(beg, 9, 10, cmpFunc);
2349 swap_if(beg, 11, 12, cmpFunc);
2350 swap_if(beg, 4, 5, cmpFunc);
2351 swap_if(beg, 6, 7, cmpFunc);
2352 swap_if(beg, 8, 9, cmpFunc);
2353 swap_if(beg, 10, 11, cmpFunc);
2354 swap_if(beg, 12, 13, cmpFunc);
2355 } else if (n <= 32) {
2356 insertion_sort_range(beg, 0, (int)n - 1, cmpFunc, [beg](uint32_t lhs, uint32_t rhs) {
2357 core::swap(beg[lhs], beg[rhs]);
2358 });
2359 }
2360
2361 return n <= 32;
2362 }
2363
2373 template <typename T, typename TCmpFunc, typename TSwapFunc>
2374 bool sort_nwk(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2375 const auto n = (uint32_t)(end - beg);
2376 if (n <= 1) {
2377 // Nothing to sort with just one item
2378 } else if (n == 2) {
2379 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2380 } else if (n == 3) {
2381 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2382 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2383 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2384 } else if (n == 4) {
2385 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2386 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2387
2388 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2389 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2390
2391 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2392 } else if (n == 5) {
2393 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2394 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2395
2396 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2397
2398 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2399 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2400
2401 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2402
2403 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2404 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2405
2406 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2407 } else if (n == 6) {
2408 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2409 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2410
2411 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2412 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2413
2414 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2415 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2416 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2417
2418 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2419 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2420
2421 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2422 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2423
2424 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2425 } else if (n == 7) {
2426 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2427 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2428 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2429
2430 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2431 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2432 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2433
2434 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2435 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2436 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2437
2438 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2439 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2440
2441 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2442 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2443
2444 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2445 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2446
2447 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2448 } else if (n == 8) {
2449 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2450 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2451 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2452 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2453
2454 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2455 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2456 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2457 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2458
2459 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2460 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2461 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2462 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2463
2464 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2465 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2466
2467 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2468 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2469
2470 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2471 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2472
2473 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2474 } else if (n == 9) {
2475 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2476 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2477 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2478 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2479 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2480 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2481 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2482 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2483 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2484 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2485 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2486 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2487 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2488 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2489 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2490 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2491 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2492 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2493 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2494 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2495 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2496 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2497 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2498 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2499 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2500 } else if (n == 10) {
2501 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
2502 try_swap_if(beg, 1, 9, cmpFunc, swapFunc);
2503 try_swap_if(beg, 2, 7, cmpFunc, swapFunc);
2504 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2505 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2506
2507 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2508 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2509 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2510 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2511 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2512
2513 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2514 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2515 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2516 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2517
2518 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2519 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2520 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2521 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2522 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2523
2524 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2525 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2526 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2527 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2528
2529 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2530 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2531 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2532
2533 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2534 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2535 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2536 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2537 } else if (n == 11) {
2538 try_swap_if(beg, 0, 9, cmpFunc, swapFunc);
2539 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2540 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2541 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2542 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2543 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2544 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2545 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2546 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2547 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2548 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2549 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2550 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2551 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2552 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2553 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2554 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2555 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2556 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2557 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2558 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2559 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2560 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2561 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2562 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2563 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2564 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2565 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2566 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2567 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2568 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2569 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2570 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2571 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2572 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2573 } else if (n == 12) {
2574 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
2575 try_swap_if(beg, 1, 7, cmpFunc, swapFunc);
2576 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2577 try_swap_if(beg, 3, 11, cmpFunc, swapFunc);
2578 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2579 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2580 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2581 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2582 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2583 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2584 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2585 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2586 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2587 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2588 try_swap_if(beg, 5, 10, cmpFunc, swapFunc);
2589 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2590 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2591 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2592 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2593 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2594 try_swap_if(beg, 8, 11, cmpFunc, swapFunc);
2595 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2596 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2597 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2598 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2599 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2600 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2601 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2602 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2603 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2604 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2605 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2606 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2607 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2608 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2609 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2610 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2611 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2612 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2613 } else if (n == 13) {
2614 try_swap_if(beg, 0, 12, cmpFunc, swapFunc);
2615 try_swap_if(beg, 1, 10, cmpFunc, swapFunc);
2616 try_swap_if(beg, 2, 9, cmpFunc, swapFunc);
2617 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2618 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2619 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2620 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2621 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2622 try_swap_if(beg, 4, 11, cmpFunc, swapFunc);
2623 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2624 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2625 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2626 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2627 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2628 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2629 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2630 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2631 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2632 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2633 try_swap_if(beg, 8, 11, cmpFunc, swapFunc);
2634 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2635 try_swap_if(beg, 0, 5, cmpFunc, swapFunc);
2636 try_swap_if(beg, 3, 8, cmpFunc, swapFunc);
2637 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2638 try_swap_if(beg, 6, 11, cmpFunc, swapFunc);
2639 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2640 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2641 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2642 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2643 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2644 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2645 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2646 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2647 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2648 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2649 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2650 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2651 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2652 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2653 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2654 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2655 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2656 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2657 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2658 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2659 } else if (n == 14) {
2660 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2661 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2662 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2663 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2664 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2665 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2666 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2667 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2668 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2669 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2670 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2671 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2672 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2673 try_swap_if(beg, 0, 4, cmpFunc, swapFunc);
2674 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2675 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2676 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2677 try_swap_if(beg, 6, 10, cmpFunc, swapFunc);
2678 try_swap_if(beg, 9, 13, cmpFunc, swapFunc);
2679 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2680 try_swap_if(beg, 0, 6, cmpFunc, swapFunc);
2681 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2682 try_swap_if(beg, 3, 9, cmpFunc, swapFunc);
2683 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2684 try_swap_if(beg, 7, 13, cmpFunc, swapFunc);
2685 try_swap_if(beg, 8, 12, cmpFunc, swapFunc);
2686 try_swap_if(beg, 2, 10, cmpFunc, swapFunc);
2687 try_swap_if(beg, 3, 11, cmpFunc, swapFunc);
2688 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2689 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2690 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2691 try_swap_if(beg, 2, 8, cmpFunc, swapFunc);
2692 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2693 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2694 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2695 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2696 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2697 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2698 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2699 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2700 try_swap_if(beg, 9, 12, cmpFunc, swapFunc);
2701 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2702 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2703 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2704 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2705 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2706 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2707 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2708 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2709 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2710 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2711 } else if (n == 15) {
2712 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2713 try_swap_if(beg, 3, 10, cmpFunc, swapFunc);
2714 try_swap_if(beg, 4, 14, cmpFunc, swapFunc);
2715 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2716 try_swap_if(beg, 6, 13, cmpFunc, swapFunc);
2717 try_swap_if(beg, 7, 12, cmpFunc, swapFunc);
2718 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2719 try_swap_if(beg, 0, 14, cmpFunc, swapFunc);
2720 try_swap_if(beg, 1, 5, cmpFunc, swapFunc);
2721 try_swap_if(beg, 2, 8, cmpFunc, swapFunc);
2722 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2723 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2724 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2725 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2726 try_swap_if(beg, 0, 7, cmpFunc, swapFunc);
2727 try_swap_if(beg, 1, 6, cmpFunc, swapFunc);
2728 try_swap_if(beg, 2, 9, cmpFunc, swapFunc);
2729 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2730 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2731 try_swap_if(beg, 8, 13, cmpFunc, swapFunc);
2732 try_swap_if(beg, 12, 14, cmpFunc, swapFunc);
2733 try_swap_if(beg, 0, 6, cmpFunc, swapFunc);
2734 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2735 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2736 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2737 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2738 try_swap_if(beg, 9, 12, cmpFunc, swapFunc);
2739 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2740 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2741 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2742 try_swap_if(beg, 4, 7, cmpFunc, swapFunc);
2743 try_swap_if(beg, 5, 9, cmpFunc, swapFunc);
2744 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2745 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2746 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2747 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2748 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2749 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2750 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2751 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2752 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2753 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2754 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2755 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2756 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2757 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2758 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2759 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2760 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2761 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2762 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2763 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2764 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2765 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2766 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2767 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2768 } else if (n == 16) {
2769 try_swap_if(beg, 0, 13, cmpFunc, swapFunc);
2770 try_swap_if(beg, 1, 12, cmpFunc, swapFunc);
2771 try_swap_if(beg, 2, 15, cmpFunc, swapFunc);
2772 try_swap_if(beg, 3, 14, cmpFunc, swapFunc);
2773 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2774 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2775 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2776 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2777 try_swap_if(beg, 0, 5, cmpFunc, swapFunc);
2778 try_swap_if(beg, 1, 7, cmpFunc, swapFunc);
2779 try_swap_if(beg, 2, 9, cmpFunc, swapFunc);
2780 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2781 try_swap_if(beg, 6, 13, cmpFunc, swapFunc);
2782 try_swap_if(beg, 8, 14, cmpFunc, swapFunc);
2783 try_swap_if(beg, 10, 15, cmpFunc, swapFunc);
2784 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2785 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2786 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2787 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2788 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2789 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2790 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2791 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2792 try_swap_if(beg, 14, 15, cmpFunc, swapFunc);
2793 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2794 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2795 try_swap_if(beg, 4, 10, cmpFunc, swapFunc);
2796 try_swap_if(beg, 5, 11, cmpFunc, swapFunc);
2797 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2798 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2799 try_swap_if(beg, 12, 14, cmpFunc, swapFunc);
2800 try_swap_if(beg, 13, 15, cmpFunc, swapFunc);
2801 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2802 try_swap_if(beg, 3, 12, cmpFunc, swapFunc);
2803 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2804 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2805 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2806 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2807 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2808 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2809 try_swap_if(beg, 2, 6, cmpFunc, swapFunc);
2810 try_swap_if(beg, 5, 8, cmpFunc, swapFunc);
2811 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2812 try_swap_if(beg, 9, 13, cmpFunc, swapFunc);
2813 try_swap_if(beg, 11, 14, cmpFunc, swapFunc);
2814 try_swap_if(beg, 2, 4, cmpFunc, swapFunc);
2815 try_swap_if(beg, 3, 6, cmpFunc, swapFunc);
2816 try_swap_if(beg, 9, 12, cmpFunc, swapFunc);
2817 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2818 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2819 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2820 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2821 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2822 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2823 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2824 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2825 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2826 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2827 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2828 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2829 } else if (n == 17) {
2830 try_swap_if(beg, 0, 11, cmpFunc, swapFunc);
2831 try_swap_if(beg, 1, 15, cmpFunc, swapFunc);
2832 try_swap_if(beg, 2, 10, cmpFunc, swapFunc);
2833 try_swap_if(beg, 3, 5, cmpFunc, swapFunc);
2834 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2835 try_swap_if(beg, 8, 12, cmpFunc, swapFunc);
2836 try_swap_if(beg, 9, 16, cmpFunc, swapFunc);
2837 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2838 try_swap_if(beg, 0, 6, cmpFunc, swapFunc);
2839 try_swap_if(beg, 1, 13, cmpFunc, swapFunc);
2840 try_swap_if(beg, 2, 8, cmpFunc, swapFunc);
2841 try_swap_if(beg, 4, 14, cmpFunc, swapFunc);
2842 try_swap_if(beg, 5, 15, cmpFunc, swapFunc);
2843 try_swap_if(beg, 7, 11, cmpFunc, swapFunc);
2844 try_swap_if(beg, 0, 8, cmpFunc, swapFunc);
2845 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2846 try_swap_if(beg, 4, 9, cmpFunc, swapFunc);
2847 try_swap_if(beg, 6, 16, cmpFunc, swapFunc);
2848 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2849 try_swap_if(beg, 12, 14, cmpFunc, swapFunc);
2850 try_swap_if(beg, 0, 2, cmpFunc, swapFunc);
2851 try_swap_if(beg, 1, 4, cmpFunc, swapFunc);
2852 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2853 try_swap_if(beg, 7, 13, cmpFunc, swapFunc);
2854 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2855 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2856 try_swap_if(beg, 11, 14, cmpFunc, swapFunc);
2857 try_swap_if(beg, 15, 16, cmpFunc, swapFunc);
2858 try_swap_if(beg, 0, 3, cmpFunc, swapFunc);
2859 try_swap_if(beg, 2, 5, cmpFunc, swapFunc);
2860 try_swap_if(beg, 6, 11, cmpFunc, swapFunc);
2861 try_swap_if(beg, 7, 10, cmpFunc, swapFunc);
2862 try_swap_if(beg, 9, 13, cmpFunc, swapFunc);
2863 try_swap_if(beg, 12, 15, cmpFunc, swapFunc);
2864 try_swap_if(beg, 14, 16, cmpFunc, swapFunc);
2865 try_swap_if(beg, 0, 1, cmpFunc, swapFunc);
2866 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2867 try_swap_if(beg, 5, 10, cmpFunc, swapFunc);
2868 try_swap_if(beg, 6, 9, cmpFunc, swapFunc);
2869 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2870 try_swap_if(beg, 11, 15, cmpFunc, swapFunc);
2871 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2872 try_swap_if(beg, 1, 2, cmpFunc, swapFunc);
2873 try_swap_if(beg, 3, 7, cmpFunc, swapFunc);
2874 try_swap_if(beg, 4, 8, cmpFunc, swapFunc);
2875 try_swap_if(beg, 6, 12, cmpFunc, swapFunc);
2876 try_swap_if(beg, 11, 13, cmpFunc, swapFunc);
2877 try_swap_if(beg, 14, 15, cmpFunc, swapFunc);
2878 try_swap_if(beg, 1, 3, cmpFunc, swapFunc);
2879 try_swap_if(beg, 2, 7, cmpFunc, swapFunc);
2880 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2881 try_swap_if(beg, 9, 11, cmpFunc, swapFunc);
2882 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2883 try_swap_if(beg, 13, 14, cmpFunc, swapFunc);
2884 try_swap_if(beg, 2, 3, cmpFunc, swapFunc);
2885 try_swap_if(beg, 4, 6, cmpFunc, swapFunc);
2886 try_swap_if(beg, 5, 7, cmpFunc, swapFunc);
2887 try_swap_if(beg, 8, 10, cmpFunc, swapFunc);
2888 try_swap_if(beg, 3, 4, cmpFunc, swapFunc);
2889 try_swap_if(beg, 6, 8, cmpFunc, swapFunc);
2890 try_swap_if(beg, 7, 9, cmpFunc, swapFunc);
2891 try_swap_if(beg, 10, 12, cmpFunc, swapFunc);
2892 try_swap_if(beg, 5, 6, cmpFunc, swapFunc);
2893 try_swap_if(beg, 7, 8, cmpFunc, swapFunc);
2894 try_swap_if(beg, 9, 10, cmpFunc, swapFunc);
2895 try_swap_if(beg, 11, 12, cmpFunc, swapFunc);
2896 try_swap_if(beg, 4, 5, cmpFunc, swapFunc);
2897 try_swap_if(beg, 6, 7, cmpFunc, swapFunc);
2898 try_swap_if(beg, 8, 9, cmpFunc, swapFunc);
2899 try_swap_if(beg, 10, 11, cmpFunc, swapFunc);
2900 try_swap_if(beg, 12, 13, cmpFunc, swapFunc);
2901 } else if (n <= 32) {
2902 insertion_sort_range(beg, 0, (int)n - 1, cmpFunc, swapFunc);
2903 }
2904
2905 return n <= 32;
2906 }
2907 } // namespace detail
2909
2911 template <typename Container, typename TCmpFunc, typename TSwapFunc>
2912 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc);
2913
2921 template <typename Container, typename TCmpFunc>
2922 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc) {
2923 if (low >= high)
2924 return;
2925 detail::quick_sort_impl(arr, low, high, cmpFunc, detail::sort_depth_limit((uint32_t)(high - low + 1)));
2926 }
2927
2937 template <typename Container, typename TCmpFunc, typename TSwapFunc>
2938 void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2939 if (low >= high)
2940 return;
2941 detail::quick_sort_impl(arr, low, high, cmpFunc, swapFunc, detail::sort_depth_limit((uint32_t)(high - low + 1)));
2942 }
2943
2953 template <typename T, typename TCmpFunc>
2954 void sort(T* beg, T* end, TCmpFunc cmpFunc) {
2955 const auto n = (uintptr_t)(end - beg);
2956 if (detail::try_sorted_or_reversed(beg, (uint32_t)n, cmpFunc, [beg](uint32_t lhs, uint32_t rhs) {
2957 core::swap(beg[lhs], beg[rhs]);
2958 }))
2959 return;
2960 if (detail::sort_nwk(beg, end, cmpFunc))
2961 return;
2962
2963 quick_sort(beg, 0, (int)n - 1, cmpFunc);
2964 }
2965
2971 template <typename C, typename TCmpFunc>
2972 void sort(C& c, TCmpFunc cmpFunc) {
2973 sort(c.begin(), c.end(), cmpFunc);
2974 }
2975
2988 template <typename T, typename TCmpFunc, typename TSwapFunc>
2989 void sort(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
2990 const auto n = (uintptr_t)(end - beg);
2991 if (detail::try_sorted_or_reversed(beg, (uint32_t)n, cmpFunc, swapFunc))
2992 return;
2993 if (detail::sort_nwk(beg, end, cmpFunc, swapFunc))
2994 return;
2995
2996 quick_sort(beg, 0, (int)n - 1, cmpFunc, swapFunc);
2997 }
2998
3006 template <typename C, typename TCmpFunc, typename TSwapFunc>
3007 void sort(C& c, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
3008 sort(c.begin(), c.end(), cmpFunc, swapFunc);
3009 }
3010 } // namespace core
3011} // namespace gaia
gaia::core::equal_to
Equality comparison functor using operator==.
Definition utility.h:1367
gaia::core::equal_to::operator()
constexpr bool operator()(const T &lhs, const T &rhs) const
Compares two values for equality.
Definition utility.h:1372
gaia::core::func_type_list
Lightweight carrier for a function argument type pack.
Definition utility.h:647
gaia::core::has_data_size
Detects containers exposing both data() and size().
Definition utility.h:220
gaia::core::has_ffunc_equals
Detects whether T supports a free operator==.
Definition utility.h:776
gaia::core::has_ffunc_equals::value
static constexpr bool value
True when the free equality operator probe succeeds.
Definition utility.h:778
gaia::core::has_func_equals
Detects whether T defines operator== as a member function.
Definition utility.h:768
gaia::core::has_func_equals::value
static constexpr bool value
True when the member equality operator probe succeeds.
Definition utility.h:770
gaia::core::has_size_begin_end
Detects containers exposing begin(), end(), and size().
Definition utility.h:235
gaia::core::is_greater
Strict weak ordering functor using operator>.
Definition utility.h:1406
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:1411
gaia::core::is_smaller_or_equal
Comparison functor using operator<=.
Definition utility.h:1393
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:1398
gaia::core::is_smaller
Strict weak ordering functor using operator<.
Definition utility.h:1380
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:1385
gaia::core::lock_scope
RAII helper that calls lock() on construction and unlock() on destruction.
Definition utility.h:188
gaia::core::lock_scope::m_ctx
T & m_ctx
Guarded lockable object.
Definition utility.h:190
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:194
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:198
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:799
gaia::core::type_list
Compile-time list of types.
Definition utility.h:788
gaia::core::type_list::size
static constexpr auto size
Number of stored types.
Definition utility.h:792
gaia::core::unique
Builds a tuple type from the first occurrence of each type in a parameter pack.
Definition utility.h:610
gaia::core::zero_t
Tag type used to request zero-initialization in APIs that accept marker objects.
Definition utility.h:130