utility.h

#pragma once
#include "gaia/config/config.h"
 
#include <cstdint>
#include <cstdio>
#include <tuple>
#include <type_traits>
#include <utility>
 
#if GAIA_PLATFORM_WINDOWS
  #include <malloc.h>
#else
  #include <alloca.h>
#endif
 
#include "gaia/core/iterator.h"
 
namespace gaia {
  constexpr uint32_t BadIndex = uint32_t(-1);
 
#if GAIA_COMPILER_MSVC || GAIA_PLATFORM_WINDOWS
  #define GAIA_STRCPY(var, max_len, text)                                                                              \
    strncpy_s((var), (text), (max_len));                                                                               \
    (var)[(max_len) - 1] = 0;
  #define GAIA_STRFMT(var, max_len, fmt, ...) sprintf_s((var), (max_len), fmt, __VA_ARGS__)
  #define GAIA_STRLEN(var, max_len) strnlen_s((var), (max_len))
#else
  #define GAIA_STRCPY(var, max_len, text)                                                                              \
    {                                                                                                                  \
      strncpy((var), (text), (max_len));                                                                               \
      (var)[(max_len) - 1] = 0;                                                                                        \
    }
  #define GAIA_STRFMT(var, max_len, fmt, ...) snprintf((var), (max_len), fmt, __VA_ARGS__)
  #define GAIA_STRLEN(var, max_len) strnlen((var), (max_len))
#endif
 
  namespace core {
    template <typename C>
    struct fixed_capacity: std::integral_constant<uint32_t, 0> {};
 
    namespace detail {
      template <class T>
      struct rem_rp {
        using type = std::remove_reference_t<std::remove_pointer_t<T>>;
      };
 
      template <typename T>
      struct is_mut:
          std::bool_constant<
              !std::is_const_v<typename rem_rp<T>::type> &&
              (std::is_pointer<T>::value || std::is_reference<T>::value)> {};
 
      template <typename Type, typename SizeProbe = size_t>
      struct is_complete: std::false_type {};
 
      template <typename T>
      struct is_complete<T, decltype(sizeof(T))>: std::true_type {};
 
      template <typename C>
      constexpr auto size(C& c) noexcept -> decltype(c.size()) {
        return c.size();
      }
      template <typename C>
      constexpr auto size(const C& c) noexcept -> decltype(c.size()) {
        return c.size();
      }
      template <typename T, auto N>
      constexpr auto size(const T (&)[N]) noexcept {
        return N;
      }
 
      template <typename C>
      constexpr auto data(C& c) noexcept -> decltype(c.data()) {
        return c.data();
      }
      template <typename C>
      constexpr auto data(const C& c) noexcept -> decltype(c.data()) {
        return c.data();
      }
      template <typename T, auto N>
      constexpr T* data(T (&array)[N]) noexcept {
        return array;
      }
    } // namespace detail
 
    struct zero_t {
      explicit constexpr zero_t() = default;
    };
 
    inline constexpr zero_t zero{};
 
    template <typename T>
    using rem_rp_t = typename detail::rem_rp<T>::type;
 
    template <typename T>
    inline constexpr bool is_mut_v = detail::is_mut<T>::value;
 
    template <typename T>
    using raw_t = typename std::decay_t<std::remove_pointer_t<T>>;
 
    template <typename T>
    inline constexpr bool is_raw_v = std::is_same_v<T, raw_t<T>> && !std::is_array_v<T>;
 
    template <typename T>
    inline constexpr bool is_complete_v = detail::is_complete<T>::value;
 
    template <typename T>
    constexpr T* addressof(T& obj) noexcept {
      return &obj;
    }
 
    template <typename T>
    const T* addressof(const T&&) = delete;
 
    template <typename T>
    constexpr bool check_alignment(const T* ptr) noexcept {
      return (reinterpret_cast<uintptr_t>(ptr)) % alignof(T) == 0;
    }
 
    template <typename T>
    struct lock_scope {
      T& m_ctx;
 
      lock_scope(T& ctx): m_ctx(ctx) {
        ctx.lock();
      }
      ~lock_scope() {
        m_ctx.unlock();
      }
 
      lock_scope(const lock_scope&) = delete;
      lock_scope& operator=(const lock_scope&) = delete;
      lock_scope(lock_scope&&) = delete;
      lock_scope& operator=(lock_scope&&) = delete;
    };
 
    //----------------------------------------------------------------------
    // Container identification
    //----------------------------------------------------------------------
 
    template <typename T, typename Probe = void>
    struct has_data_size: std::false_type {};
 
    template <typename T>
    struct has_data_size<
        T, std::void_t< //
               decltype(detail::data(std::declval<T>())), //
               decltype(detail::size(std::declval<T>())) //
               >>: std::true_type {};
 
    template <typename T, typename Probe = void>
    struct has_size_begin_end: std::false_type {};
 
    template <typename T>
    struct has_size_begin_end<
        T, std::void_t< //
               decltype(std::declval<T>().begin()), //
               decltype(std::declval<T>().end()), //
               decltype(detail::size(std::declval<T>())) //
               >>: std::true_type {};
 
    //----------------------------------------------------------------------
    // Bit-byte conversion
    //----------------------------------------------------------------------
 
    template <typename T>
    constexpr T as_bits(T value) {
      static_assert(std::is_integral_v<T>);
      return value * (T)8;
    }
 
    template <typename T>
    constexpr T as_bytes(T value) {
      static_assert(std::is_integral_v<T>);
      return value / (T)8;
    }
 
    //----------------------------------------------------------------------
    // Memory size helpers
    //----------------------------------------------------------------------
 
    template <typename T>
    constexpr uint32_t count_bits(T number) {
      uint32_t bits_needed = 0;
      while (number > 0U) {
        number >>= 1U;
        ++bits_needed;
      }
      return bits_needed;
    }
 
    template <typename T>
    constexpr bool is_pow2(T number) {
      static_assert(std::is_integral<T>::value, "is_pow2 must be used with integer types");
 
      return (number & (number - 1)) == 0;
    }
 
    template <typename T>
    constexpr T closest_pow2(T number) {
      static_assert(std::is_integral<T>::value, "closest_pow2 must be used with integer types");
 
      if (is_pow2(number))
        return number;
 
      // Collapse all bits below the highest set bit
      number |= number >> 1;
      number |= number >> 2;
      number |= number >> 4;
      if constexpr (sizeof(T) > 1)
        number |= number >> 8;
      if constexpr (sizeof(T) > 2)
        number |= number >> 16;
      if constexpr (sizeof(T) > 4)
        number |= number >> 32;
 
      // The result is now one less than the next power of two, so shift back
      return number - (number >> 1);
    }
 
    //----------------------------------------------------------------------
    // Element construction / destruction
    //----------------------------------------------------------------------
 
    template <typename T>
    void call_ctor_raw(T* pData) {
      GAIA_ASSERT(pData != nullptr);
      (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T;
    }
 
    template <typename T>
    void call_ctor_raw_n(T* pData, size_t cnt) {
      GAIA_ASSERT(pData != nullptr);
      for (size_t i = 0; i < cnt; ++i) {
        auto* ptr = pData + i;
        (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T;
      }
    }
 
    template <typename T>
    void call_ctor_val(T* pData) {
      GAIA_ASSERT(pData != nullptr);
      (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*pData)))) T();
    }
 
    template <typename T>
    void call_ctor_val_n(T* pData, size_t cnt) {
      GAIA_ASSERT(pData != nullptr);
      for (size_t i = 0; i < cnt; ++i) {
        auto* ptr = pData + i;
        (void)::new (const_cast<void*>(static_cast<const volatile void*>(core::addressof(*ptr)))) T();
      }
    }
 
    template <typename T>
    void call_ctor([[maybe_unused]] T* pData) {
      GAIA_ASSERT(pData != nullptr);
      if constexpr (!std::is_trivially_constructible_v<T>) {
        (void)::new (pData) T();
      }
    }
 
    template <typename T>
    void call_ctor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
      GAIA_ASSERT(pData != nullptr);
      if constexpr (!std::is_trivially_constructible_v<T>) {
        for (size_t i = 0; i < cnt; ++i)
          (void)::new (pData + i) T();
      }
    }
 
    template <typename T, typename... Args>
    void call_ctor(T* pData, Args&&... args) {
      GAIA_ASSERT(pData != nullptr);
      if constexpr (std::is_constructible_v<T, Args...>)
        (void)::new (pData) T(GAIA_FWD(args)...);
      else
        (void)::new (pData) T{GAIA_FWD(args)...};
    }
 
    template <typename T>
    void call_dtor([[maybe_unused]] T* pData) {
      GAIA_ASSERT(pData != nullptr);
      if constexpr (!std::is_trivially_destructible_v<T>) {
        pData->~T();
      }
    }
 
    template <typename T>
    void call_dtor_n([[maybe_unused]] T* pData, [[maybe_unused]] size_t cnt) {
      GAIA_ASSERT(pData != nullptr);
      if constexpr (!std::is_trivially_destructible_v<T>) {
        for (size_t i = 0; i < cnt; ++i)
          pData[i].~T();
      }
    }
 
    //----------------------------------------------------------------------
    // Element swapping
    //----------------------------------------------------------------------
 
    template <typename T>
    constexpr void swap(T& left, T& right) {
      T tmp = GAIA_MOV(left);
      left = GAIA_MOV(right);
      right = GAIA_MOV(tmp);
    }
 
    template <typename T, typename TCmpFunc>
    constexpr void swap_if(T* c, size_t lhs, size_t rhs, TCmpFunc cmpFunc) noexcept {
      if (!cmpFunc(c[lhs], c[rhs]))
        core::swap(c[lhs], c[rhs]);
    }
 
    template <typename T, typename TCmpFunc>
    constexpr void swap_if(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
      if (!cmpFunc(lhs, rhs))
        core::swap(lhs, rhs);
    }
 
    template <typename T, typename TCmpFunc>
    constexpr void swap_if_not(T& lhs, T& rhs, TCmpFunc cmpFunc) noexcept {
      if (cmpFunc(lhs, rhs))
        core::swap(lhs, rhs);
    }
 
    template <typename T, typename TCmpFunc, typename TSwapFunc>
    constexpr void try_swap_if(T* c, uint32_t lhs, uint32_t rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
      if (!cmpFunc(c[lhs], c[rhs]))
        swapFunc(lhs, rhs);
    }
 
    template <typename C, typename TCmpFunc, typename TSwapFunc>
    constexpr void try_swap_if(
        C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
      if (!cmpFunc(c[lhs], c[rhs]))
        swapFunc(lhs, rhs);
    }
 
    template <typename C, typename TCmpFunc, typename TSwapFunc>
    constexpr void try_swap_if_not(
        C& c, typename C::size_type lhs, typename C::size_type rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) noexcept {
      if (cmpFunc(c[lhs], c[rhs]))
        swapFunc(lhs, rhs);
    }
 
    //----------------------------------------------------------------------
    // Value filling
    //----------------------------------------------------------------------
 
    template <class ForwardIt, class T>
    constexpr void fill(ForwardIt first, ForwardIt last, const T& value) {
      for (; first != last; ++first) {
        *first = value;
      }
    }
 
    //----------------------------------------------------------------------
    // Value range checking
    //----------------------------------------------------------------------
 
    template <class T>
    constexpr const T& get_min(const T& a, const T& b) {
      return (b < a) ? b : a;
    }
 
    template <class T>
    constexpr const T& get_max(const T& a, const T& b) {
      return (b > a) ? b : a;
    }
 
    //----------------------------------------------------------------------
    // Checking if a template arg is unique among the rest
    //----------------------------------------------------------------------
 
    template <typename... Types>
    inline constexpr auto is_unique = std::true_type{};
 
    template <typename T, typename... Rest>
    inline constexpr auto is_unique<T, Rest...> =
        std::bool_constant<(!std::is_same_v<T, Rest> && ...) && is_unique<Rest...>>{};
 
    namespace detail {
      template <typename T>
      struct type_identity {
        using type = T;
      };
    } // namespace detail
 
    template <typename T, typename... Ts>
    struct unique: detail::type_identity<T> {}; // TODO: In C++20 we could use std::type_identity
 
    template <typename... Ts, typename U, typename... Us>
    struct unique<std::tuple<Ts...>, U, Us...>:
        std::conditional_t<
            (std::is_same_v<U, Ts> || ...), unique<std::tuple<Ts...>, Us...>, unique<std::tuple<Ts..., U>, Us...>> {};
 
    template <typename... Ts>
    using unique_tuple = typename unique<std::tuple<>, Ts...>::type;
 
    //----------------------------------------------------------------------
    // Calculating total size of all types of tuple
    //----------------------------------------------------------------------
 
    template <typename... Args>
    constexpr unsigned get_args_size(std::tuple<Args...> const& tuple) {
      (void)tuple;
      return (sizeof(Args) + ...);
    }
 
    //----------------------------------------------------------------------
    // Function arguments type checks
    //----------------------------------------------------------------------
 
    template <typename... Type>
    struct func_type_list {};
 
    template <typename Class, typename Ret, typename... Args>
    func_type_list<Args...> func_args(Ret (Class::*)(Args...) const);
 
    //----------------------------------------------------------------------
    // Member function checks
    //----------------------------------------------------------------------
 
#if __cpp_concepts
  #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name)                                                                   \
    template <typename T, typename... Args>                                                                            \
    concept has_mfunc_check_##function_name = requires(T&& t, Args&&... args) { t.function_name(GAIA_FWD(args)...); }; \
                                                                                                                       \
    template <typename T, typename... Args>                                                                            \
    struct has_func_##function_name {                                                                                  \
      static constexpr bool value = has_mfunc_check_##function_name<T, Args...>;                                       \
    }
#else
    namespace detail {
      template <class Default, class AlwaysVoid, template <class...> class Op, class... Args>
      struct member_func_checker {
        using value_t = std::false_type;
        using type = Default;
      };
 
      template <class Default, template <class...> class Op, class... Args>
      struct member_func_checker<Default, std::void_t<Op<Args...>>, Op, Args...> {
        using value_t = std::true_type;
        using type = Op<Args...>;
      };
 
      struct member_func_none {
        ~member_func_none() = delete;
        member_func_none(member_func_none const&) = delete;
        member_func_none(member_func_none&&) = delete;
        void operator=(member_func_none const&) = delete;
        void operator=(member_func_none&&) = delete;
      };
    } // namespace detail
 
    template <template <class...> class Op, typename... Args>
    using has_mfunc = typename detail::member_func_checker<detail::member_func_none, void, Op, Args...>::value_t;
 
  #define GAIA_DEFINE_HAS_MEMBER_FUNC(function_name)                                                                   \
    template <typename T, typename... Args>                                                                            \
    using has_mfunc_check_##function_name = decltype(std::declval<T>().function_name(std::declval<Args>()...));        \
                                                                                                                       \
    template <typename T, typename... Args>                                                                            \
    struct has_func_##function_name {                                                                                  \
      static constexpr bool value = gaia::core::has_mfunc<has_mfunc_check_##function_name, T, Args...>::value;         \
    }
#endif
 
    GAIA_DEFINE_HAS_MEMBER_FUNC(find);
    GAIA_DEFINE_HAS_MEMBER_FUNC(find_if);
    GAIA_DEFINE_HAS_MEMBER_FUNC(find_if_not);
 
    //----------------------------------------------------------------------
    // Special function checks
    //----------------------------------------------------------------------
 
    namespace detail {
      template <typename T>
      constexpr auto has_mfunc_equals_check(int)
          -> decltype(std::declval<T>().operator==(std::declval<T>()), std::true_type{});
      template <typename T, typename... Args>
      constexpr std::false_type has_mfunc_equals_check(...);
 
      template <typename T>
      constexpr auto has_ffunc_equals_check(int)
          -> decltype(operator==(std::declval<T>(), std::declval<T>()), std::true_type{});
      template <typename T, typename... Args>
      constexpr std::false_type has_ffunc_equals_check(...);
    } // namespace detail
 
    template <typename T>
    struct has_func_equals {
      static constexpr bool value = decltype(detail::has_mfunc_equals_check<T>(0))::value;
    };
 
    template <typename T>
    struct has_ffunc_equals {
      static constexpr bool value = decltype(detail::has_ffunc_equals_check<T>(0))::value;
    };
 
    //----------------------------------------------------------------------
    // Type helpers
    //----------------------------------------------------------------------
 
    template <typename... Type>
    struct type_list {
      using types = type_list;
      static constexpr auto size = sizeof...(Type);
    };
 
    template <typename TypesA, typename TypesB>
    struct type_list_concat;
 
    template <typename... TypesA, typename... TypesB>
    struct type_list_concat<type_list<TypesA...>, type_list<TypesB...>> {
      using type = type_list<TypesA..., TypesB...>;
    };
 
    //----------------------------------------------------------------------
    // Looping
    //----------------------------------------------------------------------
 
    namespace detail {
      template <auto FirstIdx, auto Iters, typename Func, auto... Is>
      constexpr void each_impl(Func func, std::integer_sequence<decltype(Iters), Is...> /*no_name*/) {
        if constexpr ((std::is_invocable_v<Func&&, std::integral_constant<decltype(Is), Is>> && ...))
          (func(std::integral_constant<decltype(Is), FirstIdx + Is>{}), ...);
        else
          (((void)Is, func()), ...);
      }
 
      template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
      void each_tuple_impl(Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
        if constexpr (
            (std::is_invocable_v<
                 Func&&, decltype(std::tuple_element_t<FirstIdx + Is, Tuple>{}),
                 std::integral_constant<decltype(FirstIdx), Is>> &&
             ...))
          // func(Args&& arg, uint32_t idx)
          (func(
               std::tuple_element_t<FirstIdx + Is, Tuple>{},
               std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}),
           ...);
        else
          // func(Args&& arg)
          (func(std::tuple_element_t<FirstIdx + Is, Tuple>{}), ...);
      }
 
      template <auto FirstIdx, typename Tuple, typename Func, auto... Is>
      void each_tuple_impl(Tuple&& tuple, Func func, std::integer_sequence<decltype(FirstIdx), Is...> /*no_name*/) {
        if constexpr (
            (std::is_invocable_v<
                 Func&&, decltype(std::get<FirstIdx + Is>(tuple)), std::integral_constant<decltype(FirstIdx), Is>> &&
             ...))
          // func(Args&& arg, uint32_t idx)
          (func(std::get<FirstIdx + Is>(tuple), std::integral_constant<decltype(FirstIdx), FirstIdx + Is>{}), ...);
        else
          // func(Args&& arg)
          (func(std::get<FirstIdx + Is>(tuple)), ...);
      }
    } // namespace detail
 
    template <auto Iters, typename Func>
    constexpr void each(Func func) {
      using TIters = decltype(Iters);
      constexpr TIters First = 0;
      detail::each_impl<First, Iters, Func>(func, std::make_integer_sequence<TIters, Iters>());
    }
 
    template <auto FirstIdx, auto LastIdx, typename Func>
    constexpr void each_ext(Func func) {
      static_assert(LastIdx >= FirstIdx);
      const auto Iters = LastIdx - FirstIdx;
      detail::each_impl<FirstIdx, Iters, Func>(func, std::make_integer_sequence<decltype(Iters), Iters>());
    }
 
    template <auto FirstIdx, auto LastIdx, auto Inc, typename Func>
    constexpr void each_ext(Func func) {
      if constexpr (FirstIdx < LastIdx) {
        if constexpr (std::is_invocable_v<Func&&, std::integral_constant<decltype(FirstIdx), FirstIdx>>)
          func(std::integral_constant<decltype(FirstIdx), FirstIdx>());
        else
          func();
 
        each_ext<FirstIdx + Inc, LastIdx, Inc>(func);
      }
    }
 
    template <typename Func, typename... Args>
    constexpr void each_pack(Func func, Args&&... args) {
      (func(GAIA_FWD(args)), ...);
    }
 
    template <typename Tuple, typename Func>
    constexpr void each_tuple(Tuple&& tuple, Func func) {
      using TTSize = uint32_t;
      constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
      detail::each_tuple_impl<(TTSize)0>(GAIA_FWD(tuple), func, std::make_integer_sequence<TTSize, TSize>{});
    }
 
    template <typename Tuple, typename Func>
    constexpr void each_tuple(Func func) {
      using TTSize = uint32_t;
      constexpr auto TSize = (TTSize)std::tuple_size<std::remove_reference_t<Tuple>>::value;
      detail::each_tuple_impl<(TTSize)0, Tuple>(func, std::make_integer_sequence<TTSize, TSize>{});
    }
 
    template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
    constexpr void each_tuple_ext(Tuple&& tuple, Func func) {
      constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
      static_assert(LastIdx >= FirstIdx);
      static_assert(LastIdx <= TSize);
      constexpr auto Iters = LastIdx - FirstIdx;
      detail::each_tuple_impl<FirstIdx>(GAIA_FWD(tuple), func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
    }
 
    template <auto FirstIdx, auto LastIdx, typename Tuple, typename Func>
    constexpr void each_tuple_ext(Func func) {
      constexpr auto TSize = std::tuple_size<std::remove_reference_t<Tuple>>::value;
      static_assert(LastIdx >= FirstIdx);
      static_assert(LastIdx <= TSize);
      constexpr auto Iters = LastIdx - FirstIdx;
      detail::each_tuple_impl<FirstIdx, Tuple>(func, std::make_integer_sequence<decltype(FirstIdx), Iters>{});
    }
 
    template <typename InputIt, typename Func>
    constexpr Func each(InputIt first, InputIt last, Func func) {
      for (; first != last; ++first)
        func(*first);
      return func;
    }
 
    template <typename C, typename Func>
    constexpr auto each(const C& arr, Func func) {
      return each(arr.begin(), arr.end(), func);
    }
 
    //----------------------------------------------------------------------
    // Lookups
    //----------------------------------------------------------------------
 
    template <typename InputIt, typename T>
    constexpr InputIt find(InputIt first, InputIt last, const T& value) {
      if constexpr (std::is_pointer_v<InputIt>) {
        auto size = distance(first, last);
        auto it = first;
        for (decltype(size) i = 0; i < size; ++i, ++it) {
          if (*it == value)
            return it;
        }
      } else if constexpr (is_random_iter_v<InputIt>) {
        auto size = distance(first, last);
        auto it = first;
        for (decltype(size) i = 0; i < size; ++i, ++it) {
          if (*it == value)
            return it;
        }
      } else {
        for (; first != last; ++first) {
          if (*first == value)
            return first;
        }
      }
      return last;
    }
 
    template <typename C, typename V>
    constexpr auto find(const C& arr, const V& item) {
      if constexpr (has_func_find<C>::value)
        return arr.find(item);
      else
        return core::find(arr.begin(), arr.end(), item);
    }
 
    template <typename InputIt, typename Func>
    constexpr InputIt find_if(InputIt first, InputIt last, Func func) {
      if constexpr (std::is_pointer_v<InputIt>) {
        auto size = distance(first, last);
        auto it = first;
        for (decltype(size) i = 0; i < size; ++i, ++it) {
          if (func(*it))
            return it;
        }
      } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
        auto size = distance(first, last);
        auto it = first;
        for (decltype(size) i = 0; i < size; ++i, ++it) {
          if (func(*it))
            return it;
        }
      } else {
        for (; first != last; ++first) {
          if (func(*first))
            return first;
        }
      }
      return last;
    }
 
    template <typename UnaryPredicate, typename C>
    constexpr auto find_if(const C& arr, UnaryPredicate predicate) {
      if constexpr (has_func_find_if<C, UnaryPredicate>::value)
        return arr.find_id(predicate);
      else
        return core::find_if(arr.begin(), arr.end(), predicate);
    }
 
    template <typename InputIt, typename Func>
    constexpr InputIt find_if_not(InputIt first, InputIt last, Func func) {
      if constexpr (std::is_pointer_v<InputIt>) {
        auto size = distance(first, last);
        auto it = first;
        for (decltype(size) i = 0; i < size; ++i, ++it) {
          if (!func(*it))
            return it;
        }
      } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
        auto size = distance(first, last);
        auto it = first;
        for (decltype(size) i = 0; i < size; ++i, ++it) {
          if (!func(*it))
            return it;
        }
      } else {
        for (; first != last; ++first) {
          if (!func(*first))
            return first;
        }
      }
      return last;
    }
 
    template <typename UnaryPredicate, typename C>
    constexpr auto find_if_not(const C& arr, UnaryPredicate predicate) {
      if constexpr (has_func_find_if_not<C, UnaryPredicate>::value)
        return arr.find_if_not(predicate);
      else
        return core::find_if_not(arr.begin(), arr.end(), predicate);
    }
 
    //----------------------------------------------------------------------
 
    template <typename C, typename V>
    constexpr bool has(const C& arr, const V& item) {
      const auto it = find(arr, item);
      return it != arr.end();
    }
 
    template <typename UnaryPredicate, typename C>
    constexpr bool has_if(const C& arr, UnaryPredicate predicate) {
      const auto it = find_if(arr, predicate);
      return it != arr.end();
    }
 
    //----------------------------------------------------------------------
 
    template <typename C>
    constexpr auto get_index(const C& arr, typename C::const_reference item) {
      const auto it = find(arr, item);
      if (it == arr.end())
        return BadIndex;
 
      return (decltype(BadIndex))core::distance(arr.begin(), it);
    }
 
    template <typename C>
    constexpr auto get_index_unsafe(const C& arr, typename C::const_reference item) {
      return (decltype(BadIndex))core::distance(arr.begin(), find(arr, item));
    }
 
    template <typename UnaryPredicate, typename C>
    constexpr auto get_index_if(const C& arr, UnaryPredicate predicate) {
      const auto it = find_if(arr, predicate);
      if (it == arr.end())
        return BadIndex;
 
      return (decltype(BadIndex))core::distance(arr.begin(), it);
    }
 
    template <typename UnaryPredicate, typename C>
    constexpr auto get_index_if_unsafe(const C& arr, UnaryPredicate predicate) {
      return (decltype(BadIndex))core::distance(arr.begin(), find_if(arr, predicate));
    }
 
    //----------------------------------------------------------------------
    // Erasure
    //----------------------------------------------------------------------
 
    template <typename C>
    void swap_erase_unsafe(C& arr, typename C::size_type idx) {
      GAIA_ASSERT(idx < arr.size());
 
      if (idx + 1 != arr.size())
        arr[idx] = arr[arr.size() - 1];
 
      arr.pop_back();
    }
 
    template <typename C>
    void swap_erase(C& arr, typename C::size_type idx) {
      if (idx >= arr.size())
        return;
 
      if (idx + 1 != arr.size())
        arr[idx] = arr[arr.size() - 1];
 
      arr.pop_back();
    }
 
    //----------------------------------------------------------------------
    // Comparison
    //----------------------------------------------------------------------
 
    template <typename T>
    struct equal_to {
      constexpr bool operator()(const T& lhs, const T& rhs) const {
        return lhs == rhs;
      }
    };
 
    template <typename T>
    struct is_smaller {
      constexpr bool operator()(const T& lhs, const T& rhs) const {
        return lhs < rhs;
      }
    };
 
    template <typename T>
    struct is_smaller_or_equal {
      constexpr bool operator()(const T& lhs, const T& rhs) const {
        return lhs <= rhs;
      }
    };
 
    template <typename T>
    struct is_greater {
      constexpr bool operator()(const T& lhs, const T& rhs) const {
        return lhs > rhs;
      }
    };
 
    //----------------------------------------------------------------------
    // Sorting
    //----------------------------------------------------------------------
 
    namespace detail {
      template <typename Container, typename TCmpFunc>
      int sort_median_of_three(Container& arr, int low, int mid, int high, TCmpFunc cmpFunc) {
        if (cmpFunc(arr[(uint32_t)low], arr[(uint32_t)mid])) {
          if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)high]))
            return mid;
          return cmpFunc(arr[(uint32_t)low], arr[(uint32_t)high]) ? high : low;
        }
 
        if (cmpFunc(arr[(uint32_t)low], arr[(uint32_t)high]))
          return low;
        return cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)high]) ? high : mid;
      }
 
      template <typename Container, typename TCmpFunc>
      int sort_choose_pivot(Container& arr, int low, int high, TCmpFunc cmpFunc) {
        const int size = high - low + 1;
        const int mid = low + (size >> 1);
        if (size > 1024) {
          const int step = size >> 3;
          const int lowMed = sort_median_of_three(arr, low, low + step, low + step + step, cmpFunc);
          const int midMed = sort_median_of_three(arr, mid - step, mid, mid + step, cmpFunc);
          const int highMed = sort_median_of_three(arr, high - step - step, high - step, high, cmpFunc);
          return sort_median_of_three(arr, lowMed, midMed, highMed, cmpFunc);
        }
 
        return sort_median_of_three(arr, low, mid, high, cmpFunc);
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      void insertion_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        for (int i = low + 1; i <= high; ++i) {
          for (int j = i; j > low && cmpFunc(arr[(uint32_t)j], arr[(uint32_t)(j - 1)]); --j)
            swapFunc((uint32_t)(j - 1), (uint32_t)j);
        }
      }
 
      template <typename Container, typename TCmpFunc>
      void insertion_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc) {
        for (int i = low + 1; i <= high; ++i) {
          if (cmpFunc(arr[(uint32_t)i], arr[(uint32_t)(i - 1)])) {
            auto tmp = GAIA_MOV(arr[(uint32_t)i]);
            int j = i;
            do {
              arr[(uint32_t)j] = GAIA_MOV(arr[(uint32_t)(j - 1)]);
              --j;
            } while (j > low && cmpFunc(tmp, arr[(uint32_t)(j - 1)]));
            arr[(uint32_t)j] = GAIA_MOV(tmp);
          }
        }
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      void sort_order_three(Container& arr, int lhs, int mid, int rhs, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)lhs]))
          swapFunc((uint32_t)lhs, (uint32_t)mid);
        if (cmpFunc(arr[(uint32_t)rhs], arr[(uint32_t)mid])) {
          swapFunc((uint32_t)mid, (uint32_t)rhs);
          if (cmpFunc(arr[(uint32_t)mid], arr[(uint32_t)lhs]))
            swapFunc((uint32_t)lhs, (uint32_t)mid);
        }
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      void sort_prepare_pivot_first(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        constexpr int NintherThreshold = 128;
        const int size = high - low + 1;
        const int mid = low + (size >> 1);
 
        if (size > NintherThreshold) {
          sort_order_three(arr, low, mid, high, cmpFunc, swapFunc);
          sort_order_three(arr, low + 1, mid - 1, high - 1, cmpFunc, swapFunc);
          sort_order_three(arr, low + 2, mid + 1, high - 2, cmpFunc, swapFunc);
          sort_order_three(arr, mid - 1, mid, mid + 1, cmpFunc, swapFunc);
          swapFunc((uint32_t)low, (uint32_t)mid);
        } else {
          sort_order_three(arr, mid, low, high, cmpFunc, swapFunc);
        }
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      int quick_sort_partition_pivot_first(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        const int begin = low;
        int first = low;
        int last = high + 1;
        const int end = last;
        auto pivot = GAIA_MOV(arr[(uint32_t)first]);
 
        do {
          ++first;
        } while (first != end && cmpFunc(arr[(uint32_t)first], pivot));
 
        if (begin == first - 1) {
          while (first < last && !cmpFunc(arr[(uint32_t)(--last)], pivot)) {
          }
        } else {
          do {
            --last;
          } while (!cmpFunc(arr[(uint32_t)last], pivot));
        }
 
        while (first < last) {
          swapFunc((uint32_t)first, (uint32_t)last);
          do {
            ++first;
          } while (cmpFunc(arr[(uint32_t)first], pivot));
          do {
            --last;
          } while (!cmpFunc(arr[(uint32_t)last], pivot));
        }
 
        const int pivotPos = first - 1;
        if (begin != pivotPos)
          arr[(uint32_t)begin] = GAIA_MOV(arr[(uint32_t)pivotPos]);
        arr[(uint32_t)pivotPos] = GAIA_MOV(pivot);
        return pivotPos;
      }
 
      template <typename T, typename TCmpFunc, typename TSwapFunc>
      bool try_sorted_or_reversed(T* beg, uint32_t n, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        if (n <= 1)
          return true;
 
        bool sorted = true;
        for (uint32_t i = 1; i < n; ++i) {
          if (cmpFunc(beg[i], beg[i - 1])) {
            sorted = false;
            break;
          }
        }
        if (sorted)
          return true;
 
        bool reversed = true;
        for (uint32_t i = 1; i < n; ++i) {
          if (cmpFunc(beg[i - 1], beg[i])) {
            reversed = false;
            break;
          }
        }
        if (!reversed)
          return false;
 
        for (uint32_t i = 0, j = n - 1; i < j; ++i, --j)
          swapFunc(i, j);
        return true;
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      int quick_sort_partition_hoare(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        const int pivotIdx = sort_choose_pivot(arr, low, high, cmpFunc);
        const auto pivot = arr[(uint32_t)pivotIdx];
 
        int i = low - 1;
        int j = high + 1;
 
        while (true) {
          do {
            ++i;
          } while (cmpFunc(arr[(uint32_t)i], pivot));
 
          do {
            --j;
          } while (cmpFunc(pivot, arr[(uint32_t)j]));
 
          if (i >= j)
            return j;
 
          swapFunc((uint32_t)i, (uint32_t)j);
        }
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      void heap_sift_down(Container& arr, int low, int root, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        while (true) {
          const int left = low + ((root - low) << 1) + 1;
          if (left > high)
            return;
 
          int child = left;
          const int right = left + 1;
          if (right <= high && cmpFunc(arr[(uint32_t)child], arr[(uint32_t)right]))
            child = right;
 
          if (!cmpFunc(arr[(uint32_t)root], arr[(uint32_t)child]))
            return;
 
          swapFunc((uint32_t)root, (uint32_t)child);
          root = child;
        }
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      void heap_sort_range(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        for (int start = low + ((high - low - 1) >> 1); start >= low; --start)
          heap_sift_down(arr, low, start, high, cmpFunc, swapFunc);
 
        for (int end = high; end > low; --end) {
          swapFunc((uint32_t)low, (uint32_t)end);
          heap_sift_down(arr, low, low, end - 1, cmpFunc, swapFunc);
        }
      }
 
      inline uint32_t sort_depth_limit(uint32_t n) {
        uint32_t depth = 0;
        while (n > 1) {
          ++depth;
          n >>= 1;
        }
        return depth * 2;
      }
 
      template <typename Container, typename TCmpFunc, typename TSwapFunc>
      void
      quick_sort_impl(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc, uint32_t depthLimit) {
        constexpr int InsertionSortThreshold = 24;
 
        while (high - low > InsertionSortThreshold) {
          if (depthLimit == 0) {
            heap_sort_range(arr, low, high, cmpFunc, swapFunc);
            return;
          }
          --depthLimit;
 
          const int split = quick_sort_partition_hoare(arr, low, high, cmpFunc, swapFunc);
          const int leftSize = split - low + 1;
          const int rightSize = high - split;
 
          if (leftSize < rightSize) {
            quick_sort_impl(arr, low, split, cmpFunc, swapFunc, depthLimit);
            low = split + 1;
          } else {
            quick_sort_impl(arr, split + 1, high, cmpFunc, swapFunc, depthLimit);
            high = split;
          }
        }
 
        if (low < high)
          insertion_sort_range(arr, low, high, cmpFunc, swapFunc);
      }
 
      template <typename Container, typename TCmpFunc>
      void quick_sort_impl(Container& arr, int low, int high, TCmpFunc cmpFunc, uint32_t depthLimit) {
        constexpr int InsertionSortThreshold = 24;
        auto swapFunc = [&arr](uint32_t a, uint32_t b) {
          core::swap(arr[a], arr[b]);
        };
 
        while (high - low > InsertionSortThreshold) {
          if (depthLimit == 0) {
            heap_sort_range(arr, low, high, cmpFunc, swapFunc);
            return;
          }
          --depthLimit;
 
          sort_prepare_pivot_first(arr, low, high, cmpFunc, swapFunc);
          const int pivot = quick_sort_partition_pivot_first(arr, low, high, cmpFunc, swapFunc);
          const int leftSize = pivot - low;
          const int rightSize = high - pivot;
 
          if (leftSize < rightSize) {
            quick_sort_impl(arr, low, pivot - 1, cmpFunc, depthLimit);
            low = pivot + 1;
          } else {
            quick_sort_impl(arr, pivot + 1, high, cmpFunc, depthLimit);
            high = pivot - 1;
          }
        }
 
        if (low < high)
          insertion_sort_range(arr, low, high, cmpFunc);
      }
 
      inline constexpr uint32_t SortNetworkMaxN = 17;
      inline constexpr uint32_t SortSmallMaxN = 32;
 
      template <uint32_t N>
      struct sort_network;
      template <>
      struct sort_network<2> {
        static constexpr uint8_t pairs[][2] = {{0, 1}};
      };
      template <>
      struct sort_network<3> {
        static constexpr uint8_t pairs[][2] = {{1, 2}, {0, 2}, {0, 1}};
      };
      template <>
      struct sort_network<4> {
        static constexpr uint8_t pairs[][2] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {1, 2}};
      };
      template <>
      struct sort_network<5> {
        static constexpr uint8_t pairs[][2] = {{0, 1}, {3, 4}, {2, 4}, {2, 3}, {1, 4}, {0, 3}, {0, 2}, {1, 3}, {1, 2}};
      };
      template <>
      struct sort_network<6> {
        static constexpr uint8_t pairs[][2] = {{1, 2}, {4, 5}, {0, 2}, {3, 5}, {0, 1}, {3, 4},
                                               {2, 5}, {0, 3}, {1, 4}, {2, 4}, {1, 3}, {2, 3}};
      };
      template <>
      struct sort_network<7> {
        static constexpr uint8_t pairs[][2] = {{1, 2}, {3, 4}, {5, 6}, {0, 2}, {3, 5}, {4, 6}, {0, 1}, {4, 5},
                                               {2, 6}, {0, 4}, {1, 5}, {0, 3}, {2, 5}, {1, 3}, {2, 4}, {2, 3}};
      };
      template <>
      struct sort_network<8> {
        static constexpr uint8_t pairs[][2] = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {0, 2}, {1, 3}, {4, 6},
                                               {5, 7}, {1, 2}, {5, 6}, {0, 4}, {3, 7}, {1, 5}, {2, 6},
                                               {1, 4}, {3, 6}, {2, 4}, {3, 5}, {3, 4}};
      };
      template <>
      struct sort_network<9> {
        static constexpr uint8_t pairs[][2] = {{0, 1}, {3, 4}, {6, 7}, {1, 2}, {4, 5}, {7, 8}, {0, 1}, {3, 4}, {6, 7},
                                               {0, 3}, {3, 6}, {0, 3}, {1, 4}, {4, 7}, {1, 4}, {2, 5}, {5, 8}, {2, 5},
                                               {1, 3}, {5, 7}, {2, 6}, {4, 6}, {2, 4}, {2, 3}, {5, 6}};
      };
      template <>
      struct sort_network<10> {
        static constexpr uint8_t pairs[][2] = {{0, 8}, {1, 9}, {2, 7}, {3, 5}, {4, 6}, {0, 2}, {1, 4}, {5, 8},
                                               {7, 9}, {0, 3}, {2, 4}, {5, 7}, {6, 9}, {0, 1}, {3, 6}, {8, 9},
                                               {1, 5}, {2, 3}, {4, 8}, {6, 7}, {1, 2}, {3, 5}, {4, 6}, {7, 8},
                                               {2, 3}, {4, 5}, {6, 7}, {3, 4}, {5, 6}};
      };
      template <>
      struct sort_network<11> {
        static constexpr uint8_t pairs[][2] = {
            {0, 9}, {1, 6},  {2, 4}, {3, 7}, {5, 8}, {0, 1}, {3, 5}, {4, 10}, {6, 9}, {7, 8}, {1, 3}, {2, 5},
            {4, 7}, {8, 10}, {0, 4}, {1, 2}, {3, 7}, {5, 9}, {6, 8}, {0, 1},  {2, 6}, {4, 5}, {7, 8}, {9, 10},
            {2, 4}, {3, 6},  {5, 7}, {8, 9}, {1, 2}, {3, 4}, {5, 6}, {7, 8},  {2, 3}, {4, 5}, {6, 7}};
      };
      template <>
      struct sort_network<12> {
        static constexpr uint8_t pairs[][2] = {{0, 8}, {1, 7},  {2, 6}, {3, 11},  {4, 10}, {5, 9},  {0, 1},  {2, 5},
                                               {3, 4}, {6, 9},  {7, 8}, {10, 11}, {0, 2},  {1, 6},  {5, 10}, {9, 11},
                                               {0, 3}, {1, 2},  {4, 6}, {5, 7},   {8, 11}, {9, 10}, {1, 4},  {3, 5},
                                               {6, 8}, {7, 10}, {1, 3}, {2, 5},   {6, 9},  {8, 10}, {2, 3},  {4, 5},
                                               {6, 7}, {8, 9},  {4, 6}, {5, 7},   {3, 4},  {5, 6},  {7, 8}};
      };
      template <>
      struct sort_network<13> {
        static constexpr uint8_t pairs[][2] = {
            {0, 12}, {1, 10}, {2, 9}, {3, 7},  {5, 11},  {6, 8}, {1, 6},   {2, 3},  {4, 11},  {7, 9}, {8, 10}, {0, 4},
            {1, 2},  {3, 6},  {7, 8}, {9, 10}, {11, 12}, {4, 6}, {5, 9},   {8, 11}, {10, 12}, {0, 5}, {3, 8},  {4, 7},
            {6, 11}, {9, 10}, {0, 1}, {2, 5},  {6, 9},   {7, 8}, {10, 11}, {1, 3},  {2, 4},   {5, 6}, {9, 10}, {1, 2},
            {3, 4},  {5, 7},  {6, 8}, {2, 3},  {4, 5},   {6, 7}, {8, 9},   {3, 4},  {5, 6}};
      };
      template <>
      struct sort_network<14> {
        static constexpr uint8_t pairs[][2] = {
            {0, 1},   {2, 3},   {4, 5},  {6, 7},  {8, 9},  {10, 11}, {12, 13}, {0, 2},  {1, 3},   {4, 8}, {5, 9},
            {10, 12}, {11, 13}, {0, 4},  {1, 2},  {3, 7},  {5, 8},   {6, 10},  {9, 13}, {11, 12}, {0, 6}, {1, 5},
            {3, 9},   {4, 10},  {7, 13}, {8, 12}, {2, 10}, {3, 11},  {4, 6},   {7, 9},  {1, 3},   {2, 8}, {5, 11},
            {6, 7},   {10, 12}, {1, 4},  {2, 6},  {3, 5},  {7, 11},  {8, 10},  {9, 12}, {2, 4},   {3, 6}, {5, 8},
            {7, 10},  {9, 11},  {3, 4},  {5, 6},  {7, 8},  {9, 10},  {6, 7}};
      };
      template <>
      struct sort_network<15> {
        static constexpr uint8_t pairs[][2] = {
            {1, 2},   {3, 10}, {4, 14},  {5, 8},   {6, 13},  {7, 12}, {9, 11}, {0, 14},  {1, 5},  {2, 8},
            {3, 7},   {6, 9},  {10, 12}, {11, 13}, {0, 7},   {1, 6},  {2, 9},  {4, 10},  {5, 11}, {8, 13},
            {12, 14}, {0, 6},  {2, 4},   {3, 5},   {7, 11},  {8, 10}, {9, 12}, {13, 14}, {0, 3},  {1, 2},
            {4, 7},   {5, 9},  {6, 8},   {10, 11}, {12, 13}, {0, 1},  {2, 3},  {4, 6},   {7, 9},  {10, 12},
            {11, 13}, {1, 2},  {3, 5},   {8, 10},  {11, 12}, {3, 4},  {5, 6},  {7, 8},   {9, 10}, {2, 3},
            {4, 5},   {6, 7},  {8, 9},   {10, 11}, {5, 6},   {7, 8}};
      };
      template <>
      struct sort_network<16> {
        static constexpr uint8_t pairs[][2] = {
            {0, 13},  {1, 12},  {2, 15},  {3, 14},  {4, 8},   {5, 6},   {7, 11}, {9, 10},  {0, 5},   {1, 7},
            {2, 9},   {3, 4},   {6, 13},  {8, 14},  {10, 15}, {11, 12}, {0, 1},  {2, 3},   {4, 5},   {6, 8},
            {7, 9},   {10, 11}, {12, 13}, {14, 15}, {0, 2},   {1, 3},   {4, 10}, {5, 11},  {6, 7},   {8, 9},
            {12, 14}, {13, 15}, {1, 2},   {3, 12},  {4, 6},   {5, 7},   {8, 10}, {9, 11},  {13, 14}, {1, 4},
            {2, 6},   {5, 8},   {7, 10},  {9, 13},  {11, 14}, {2, 4},   {3, 6},  {9, 12},  {11, 13}, {3, 5},
            {6, 8},   {7, 9},   {10, 12}, {3, 4},   {5, 6},   {7, 8},   {9, 10}, {11, 12}, {6, 7},   {8, 9}};
      };
      template <>
      struct sort_network<17> {
        static constexpr uint8_t pairs[][2] = {
            {0, 11},  {1, 15},  {2, 10},  {3, 5},  {4, 6},   {8, 12},  {9, 16},  {13, 14}, {0, 6},
            {1, 13},  {2, 8},   {4, 14},  {5, 15}, {7, 11},  {0, 8},   {3, 7},   {4, 9},   {6, 16},
            {10, 11}, {12, 14}, {0, 2},   {1, 4},  {5, 6},   {7, 13},  {8, 9},   {10, 12}, {11, 14},
            {15, 16}, {0, 3},   {2, 5},   {6, 11}, {7, 10},  {9, 13},  {12, 15}, {14, 16}, {0, 1},
            {3, 4},   {5, 10},  {6, 9},   {7, 8},  {11, 15}, {13, 14}, {1, 2},   {3, 7},   {4, 8},
            {6, 12},  {11, 13}, {14, 15}, {1, 3},  {2, 7},   {4, 5},   {9, 11},  {10, 12}, {13, 14},
            {2, 3},   {4, 6},   {5, 7},   {8, 10}, {3, 4},   {6, 8},   {7, 9},   {10, 12}, {5, 6},
            {7, 8},   {9, 10},  {11, 12}, {4, 5},  {6, 7},   {8, 9},   {10, 11}, {12, 13}};
      };
 
      template <uint32_t N, typename TCompareExchange, size_t... I>
      void sort_network_run(TCompareExchange& cex, std::index_sequence<I...>) {
        (cex(sort_network<N>::pairs[I][0], sort_network<N>::pairs[I][1]), ...);
      }
 
      template <uint32_t N, uint32_t Last, typename TCompareExchange>
      void sort_network_dispatch(uint32_t n, TCompareExchange& cex) {
        if (n == N) {
          constexpr size_t Pairs = sizeof(sort_network<N>::pairs) / sizeof(sort_network<N>::pairs[0]);
          sort_network_run<N>(cex, std::make_index_sequence<Pairs>{});
          return;
        }
        if constexpr (N < Last)
          sort_network_dispatch<N + 1, Last>(n, cex);
      }
 
      template <typename T>
      inline constexpr bool sort_uses_network = std::is_trivially_copyable_v<T> && sizeof(T) <= 8;
 
      template <typename T, typename TCmpFunc>
      struct sort_cex_select {
        T* beg;
        TCmpFunc& cmpFunc;
 
        void operator()(uint32_t lhs, uint32_t rhs) const {
          const T a = beg[lhs];
          const T b = beg[rhs];
          const bool swap = cmpFunc(b, a);
          beg[lhs] = swap ? b : a;
          beg[rhs] = swap ? a : b;
        }
      };
 
      template <typename T, typename TCmpFunc, typename TSwapFunc>
      struct sort_cex_swap {
        T* beg;
        TCmpFunc& cmpFunc;
        TSwapFunc& swapFunc;
 
        void operator()(uint32_t lhs, uint32_t rhs) const {
          if (cmpFunc(beg[rhs], beg[lhs]))
            swapFunc(lhs, rhs);
        }
      };
 
      template <uint32_t MaxN, typename T, typename TCmpFunc>
      bool sort_small(T* beg, uint32_t n, TCmpFunc& cmpFunc) {
        if constexpr (MaxN > SortSmallMaxN) {
          if (n > SortSmallMaxN)
            return false;
        }
 
        if constexpr (sort_uses_network<T>) {
          constexpr uint32_t Last = MaxN < SortNetworkMaxN ? MaxN : SortNetworkMaxN;
          if constexpr (Last >= 2) {
            if (n <= Last) {
              sort_cex_select<T, TCmpFunc> cex{beg, cmpFunc};
              sort_network_dispatch<2, Last>(n, cex);
              return true;
            }
          }
        }
 
        T* arr = beg;
        insertion_sort_range(arr, 0, (int)n - 1, cmpFunc);
        return true;
      }
 
      template <uint32_t MaxN, typename T, typename TCmpFunc, typename TSwapFunc>
      bool sort_small(T* beg, uint32_t n, TCmpFunc& cmpFunc, TSwapFunc& swapFunc) {
        if constexpr (MaxN > SortSmallMaxN) {
          if (n > SortSmallMaxN)
            return false;
        }
 
        constexpr uint32_t Last = MaxN < SortNetworkMaxN ? MaxN : SortNetworkMaxN;
        if constexpr (Last >= 2) {
          if (n <= Last) {
            sort_cex_swap<T, TCmpFunc, TSwapFunc> cex{beg, cmpFunc, swapFunc};
            sort_network_dispatch<2, Last>(n, cex);
            return true;
          }
        }
 
        insertion_sort_range(beg, 0, (int)n - 1, cmpFunc, swapFunc);
        return true;
      }
    } // namespace detail
 
    template <typename Container, typename TCmpFunc, typename TSwapFunc>
    void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc);
 
    template <typename Container, typename TCmpFunc>
    void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc) {
      if (low >= high)
        return;
      detail::quick_sort_impl(arr, low, high, cmpFunc, detail::sort_depth_limit((uint32_t)(high - low + 1)));
    }
 
    template <typename Container, typename TCmpFunc, typename TSwapFunc>
    void quick_sort(Container& arr, int low, int high, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
      if (low >= high)
        return;
      detail::quick_sort_impl(arr, low, high, cmpFunc, swapFunc, detail::sort_depth_limit((uint32_t)(high - low + 1)));
    }
 
    namespace detail {
      template <uint32_t MaxN, typename T, typename TCmpFunc>
      void sort_bounded(T* beg, T* end, TCmpFunc cmpFunc) {
        const auto n = (uint32_t)(end - beg);
        if (try_sorted_or_reversed(beg, n, cmpFunc, [beg](uint32_t lhs, uint32_t rhs) {
              core::swap(beg[lhs], beg[rhs]);
            }))
          return;
        if (sort_small<MaxN>(beg, n, cmpFunc))
          return;
 
        if constexpr (MaxN > SortSmallMaxN)
          core::quick_sort(beg, 0, (int)n - 1, cmpFunc);
      }
 
      template <uint32_t MaxN, typename T, typename TCmpFunc, typename TSwapFunc>
      void sort_bounded(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
        const auto n = (uint32_t)(end - beg);
        if (try_sorted_or_reversed(beg, n, cmpFunc, swapFunc))
          return;
        if (sort_small<MaxN>(beg, n, cmpFunc, swapFunc))
          return;
 
        if constexpr (MaxN > SortSmallMaxN)
          core::quick_sort(beg, 0, (int)n - 1, cmpFunc, swapFunc);
      }
    } // namespace detail
 
    template <uint32_t MaxN = (uint32_t)-1, typename T, typename TCmpFunc>
    void sort(T* beg, T* end, TCmpFunc cmpFunc) {
      GAIA_ASSERT((uintptr_t)(end - beg) <= MaxN);
      detail::sort_bounded<MaxN>(beg, end, cmpFunc);
    }
 
    template <typename C, typename TCmpFunc>
    void sort(C& c, TCmpFunc cmpFunc) {
      constexpr uint32_t Cap = fixed_capacity<std::remove_cv_t<C>>::value;
      detail::sort_bounded<Cap != 0 ? Cap : (uint32_t)-1>(c.begin(), c.end(), cmpFunc);
    }
 
    template <uint32_t MaxN = (uint32_t)-1, typename T, typename TCmpFunc, typename TSwapFunc>
    void sort(T* beg, T* end, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
      GAIA_ASSERT((uintptr_t)(end - beg) <= MaxN);
      detail::sort_bounded<MaxN>(beg, end, cmpFunc, swapFunc);
    }
 
    template <typename C, typename TCmpFunc, typename TSwapFunc>
    void sort(C& c, TCmpFunc cmpFunc, TSwapFunc swapFunc) {
      constexpr uint32_t Cap = fixed_capacity<std::remove_cv_t<C>>::value;
      detail::sort_bounded<Cap != 0 ? Cap : (uint32_t)-1>(c.begin(), c.end(), cmpFunc, swapFunc);
    }
  } // namespace core
} // namespace gaia