fakestd.h

Go to the documentation of this file.

/* *****************************************************************************
 * kblib is a general utility library for C++14 and C++17, intended to provide
 * performant high-level abstractions and more expressive ways to do simple
 * things.
 *
 * Copyright (c) 2021 killerbee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef KBLIB_FAKESTD_H
#define KBLIB_FAKESTD_H
 
#include "tdecl.h"
 
#include <array>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
 
#if __has_include("gsl/pointers")
#  include "gsl/pointers"
#endif
 
#ifndef KBLIB_FAKESTD
#  define KBLIB_FAKESTD (__cplusplus < 201703L)
#endif
 
namespace kblib {
 
template <bool B, typename T = void>
using enable_if_t = typename std::enable_if<B, T>::type;
 
template <typename T>
using decay_t = typename std::decay<T>::type;
 
template <typename T>
using remove_cvref_t =
    typename std::remove_reference<typename std::remove_cv<T>::type>::type;
 
template <bool v>
using bool_constant = std::integral_constant<bool, v>;
 
#if __cpp_lib_constexpr_functional
using std::invoke;
#else
 
#  if __cpp_lib_apply
 
template <typename F, typename... Args>
constexpr auto invoke(F&& f, Args&&... args) noexcept(noexcept(std::apply(
    std::forward<F>(f), std::forward_as_tuple(std::forward<Args>(args)...))))
    -> decltype(auto) {
   return std::apply(std::forward<F>(f),
                     std::forward_as_tuple(std::forward<Args>(args)...));
}
 
#  else
 
namespace detail {
 
   template <
       typename F, typename... Args,
       enable_if_t<not std::is_member_pointer<decay_t<F>>::value, int> = 0>
   constexpr auto do_invoke(F&& f, Args&&... args) noexcept(noexcept(
       std::forward<F>(f)(std::forward<Args>(args)...))) -> decltype(auto) {
      return std::forward<F>(f)(std::forward<Args>(args)...);
   }
 
   template <typename F, typename Object, typename... Args,
             enable_if_t<not std::is_pointer<decay_t<Object>>::value
                             and std::is_member_function_pointer<F>::value,
                         int> = 0>
   constexpr auto do_invoke(F f, Object&& obj, Args&&... args) noexcept(
       noexcept((obj.*f)(std::forward<Args>(args)...))) -> decltype(auto) {
      return (obj.*f)(std::forward<Args>(args)...);
   }
 
   template <typename F, typename Pointer, typename... Args,
             enable_if_t<std::is_pointer<Pointer>::value
                             and std::is_member_function_pointer<F>::value,
                         int> = 0>
   constexpr auto do_invoke(F f, Pointer ptr, Args&&... args) noexcept(
       noexcept((ptr->*f)(std::forward<Args>(args)...))) -> decltype(auto) {
      return (ptr->*f)(std::forward<Args>(args)...);
   }
 
   template <typename Member, typename Object,
             enable_if_t<not std::is_pointer<decay_t<Object>>::value
                             and std::is_member_object_pointer<Member>::value,
                         int> = 0>
   constexpr auto do_invoke(Member mem, Object&& obj) noexcept
       -> decltype(auto) {
      return std::forward<Object>(obj).*mem;
   }
 
   template <typename Member, typename Pointer,
             enable_if_t<std::is_pointer<Pointer>::value
                             and std::is_member_object_pointer<Member>::value,
                         int> = 0>
   constexpr auto do_invoke(Member mem, Pointer ptr) noexcept
       -> decltype(auto) {
      return ptr.*mem;
   }
} // namespace detail
 
template <typename F, typename... Args>
constexpr auto invoke(F&& f, Args&&... args) noexcept(noexcept(
    detail::do_invoke(std::forward<F>(f), std::forward<Args>(args)...)))
    -> decltype(auto) {
   return detail::do_invoke(std::forward<F>(f), std::forward<Args>(args)...);
}
 
#  endif // __cpp_lib_apply
#endif    // __cpp_lib_constexpr_functional
 
#if KBLIB_FAKESTD
namespace fakestd { // C++14 implementation of C++17 void_t, invoke_result,
                    // (partially) is_invocable, and is_nothrow_swappable
   using std::swap;
 
   namespace detail {
 
      template <typename AlwaysVoid, typename, typename...>
      struct invoke_result {};
      template <typename F, typename... Args>
      struct invoke_result<decltype(void(invoke(std::declval<F>(),
                                                std::declval<Args>()...))),
                           F, Args...> {
         using type
             = decltype(invoke(std::declval<F>(), std::declval<Args>()...));
      };
   } // namespace detail
   template <class F, class... ArgTypes>
   struct invoke_result : detail::invoke_result<void, F, ArgTypes...> {};
 
   template <typename F, typename... ArgTypes>
   using invoke_result_t = typename invoke_result<F, ArgTypes...>::type;
 
   template <typename... Ts>
   struct make_void {
      typedef void type;
   };
   template <typename... Ts>
   using void_t = typename make_void<Ts...>::type;
 
   namespace detail {
      // ALL generic swap overloads MUST already have a declaration available at
      // this point.
 
      struct nat {
         nat() = delete;
         nat(const nat&) = delete;
         nat& operator=(const nat&) = delete;
         ~nat() = delete;
      };
 
      struct two {
         char lx[2];
      };
 
      struct is_referenceable_impl {
         template <class Tp>
         static Tp& test(int);
         template <class Tp>
         static two test(...);
      };
 
      template <class Tp>
      struct is_referenceable
          : std::integral_constant<
                bool,
                not std::is_same<decltype(is_referenceable_impl::test<Tp>(0)),
                                 two>::value> {};
 
      template <class Tp, class Up = Tp,
                bool NotVoid
                = not std::is_void<Tp>::value and not std::is_void<Up>::value>
      struct swappable_with {
         template <class LHS, class RHS>
         static decltype(swap(std::declval<LHS>(), std::declval<RHS>()))
         test_swap(int);
         template <class, class>
         static nat test_swap(long);
 
         // Extra parens are needed for the C++03 definition of decltype.
         using swap1 = decltype((test_swap<Tp, Up>(0)));
         using swap2 = decltype((test_swap<Up, Tp>(0)));
 
         static const bool value = not std::is_same<swap1, nat>::value
                                   and not std::is_same<swap2, nat>::value;
      };
 
      template <class Tp, class Up>
      struct swappable_with<Tp, Up, false> : std::false_type {};
 
      template <class Tp, class Up = Tp,
                bool Swappable = swappable_with<Tp, Up>::value>
      struct nothrow_swappable_with {
         static const bool value = noexcept(
             swap(std::declval<Tp>(),
                  std::declval<Up>()))and noexcept(swap(std::declval<Up>(),
                                                        std::declval<Tp>()));
      };
 
      template <class Tp, class Up>
      struct nothrow_swappable_with<Tp, Up, false> : std::false_type {};
 
   } // namespace detail
 
   template <class Tp>
   struct is_swappable
       : public std::integral_constant<bool,
                                       detail::swappable_with<Tp&>::value> {};
 
   template <class Tp>
   struct is_nothrow_swappable
       : public std::integral_constant<
             bool, detail::nothrow_swappable_with<Tp&>::value> {};
 
#  if KBLIB_USE_CXX17
 
   template <class Tp, class Up>
   struct is_swappable_with
       : public std::integral_constant<bool,
                                       detail::swappable_with<Tp, Up>::value> {
   };
 
   template <class Tp>
   struct is_swappable
       : public std::conditional<
             detail::is_referenceable<Tp>::value,
             is_swappable_with<typename std::add_lvalue_reference<Tp>::type,
                               typename std::add_lvalue_reference<Tp>::type>,
             std::false_type>::type {};
 
   template <class Tp, class Up>
   struct is_nothrow_swappable_with
       : public integral_constant<
             bool, detail::nothrow_swappable_with<Tp, Up>::value> {};
 
   template <class Tp>
   struct is_nothrow_swappable
       : public conditional<
             detail::is_referenceable<Tp>::value,
             is_nothrow_swappable_with<typename add_lvalue_reference<Tp>::type,
                                       typename add_lvalue_reference<Tp>::type>,
             false_type>::type {};
 
   template <class Tp, class Up>
   constexpr bool is_swappable_with_v = is_swappable_with<Tp, Up>::value;
 
   template <class Tp>
   constexpr bool is_swappable_v = is_swappable<Tp>::value;
 
   template <class Tp, class Up>
   constexpr bool is_nothrow_swappable_with_v
       = is_nothrow_swappable_with<Tp, Up>::value;
 
   template <class Tp>
   constexpr bool is_nothrow_swappable_v = is_nothrow_swappable<Tp>::value;
 
#  endif
 
   namespace detail {
      template <typename F>
      struct not_fn_t {
         constexpr explicit not_fn_t(F&& f)
             : fd(std::forward<F>(f)) {}
         constexpr not_fn_t(const not_fn_t&) = default;
         constexpr not_fn_t(not_fn_t&&) = default;
 
         template <class... Args>
         constexpr auto operator()(Args&&... args) & -> decltype(
             not std::declval<invoke_result_t<std::decay_t<F>&, Args...>>()) {
            return not invoke(fd, std::forward<Args>(args)...);
         }
 
         template <class... Args>
         constexpr auto operator()(Args&&... args) const& -> decltype(
             not std::declval<
                 invoke_result_t<std::decay_t<F> const&, Args...>>()) {
            return not invoke(std::move(fd), std::forward<Args>(args)...);
         }
 
         std::decay_t<F> fd;
      };
   } // namespace detail
 
   template <typename F>
   auto not_fn(F&& f) -> detail::not_fn_t<F> {
      return detail::not_fn_t<F>(std::forward<F>(f));
   }
 
   struct in_place_t {
      explicit in_place_t() = default;
   };
   static constexpr in_place_t in_place{};
 
   template <class ForwardIt>
   constexpr auto max_element(ForwardIt first, ForwardIt last) -> ForwardIt {
      if (first == last)
         return last;
 
      ForwardIt largest = first;
      ++first;
      for (; first != last; ++first) {
         if (*largest < *first) {
            largest = first;
         }
      }
      return largest;
   }
 
   template <class ForwardIt, class Compare>
   constexpr auto max_element(ForwardIt first, ForwardIt last, Compare comp)
       -> ForwardIt {
      if (first == last)
         return last;
 
      ForwardIt largest = first;
      ++first;
      for (; first != last; ++first) {
         if (comp(*largest, *first)) {
            largest = first;
         }
      }
      return largest;
   }
 
   template <class C>
   constexpr auto size(const C& c) -> decltype(c.size()) {
      return c.size();
   }
 
   template <class T, std::size_t N>
   constexpr auto size(const T (&)[N]) noexcept -> std::size_t {
      return N;
   }
 
   // Adapted from libstdc++ code, licensed under GPL
 
   namespace detail {
      // invokable
      template <class Ret, class Fp, class... Args>
      struct invokable_r {
         template <class XFp, class... XArgs>
         static auto try_call(int)
             -> decltype(kblib::invoke(std::declval<XFp>(),
                                       std::declval<XArgs>()...));
         template <class XFp, class... XArgs>
         static auto try_call(...) -> detail::nat;
 
         using Result = decltype(try_call<Fp, Args...>(0));
 
         using type = typename std::conditional<
             not std::is_same<Result, detail::nat>::value,
             typename std::conditional<std::is_void<Ret>::value, std::true_type,
                                       std::is_convertible<Result, Ret>>::type,
             std::false_type>::type;
         static const bool value = type::value;
      };
      template <class Fp, class... Args>
      using invokable = invokable_r<void, Fp, Args...>;
 
      template <bool IsInvokable, bool IsCVVoid, class Ret, class Fp,
                class... Args>
      struct nothrow_invokable_r_imp {
         static const bool value = false;
      };
 
      template <class Ret, class Fp, class... Args>
      struct nothrow_invokable_r_imp<true, false, Ret, Fp, Args...> {
         using ThisT = nothrow_invokable_r_imp;
 
         template <class Tp>
         static void test_noexcept(Tp) noexcept;
 
         static const bool value = noexcept(ThisT::test_noexcept<Ret>(
             kblib::invoke(std::declval<Fp>(), std::declval<Args>()...)));
      };
 
      template <class Ret, class Fp, class... Args>
      struct nothrow_invokable_r_imp<true, true, Ret, Fp, Args...> {
         static const bool value = noexcept(
             kblib::invoke(std::declval<Fp>(), std::declval<Args>()...));
      };
 
      template <class Ret, class Fp, class... Args>
      using nothrow_invokable_r
          = nothrow_invokable_r_imp<invokable_r<Ret, Fp, Args...>::value,
                                    std::is_void<Ret>::value, Ret, Fp, Args...>;
 
      template <class Fp, class... Args>
      using nothrow_invokable
          = nothrow_invokable_r_imp<invokable<Fp, Args...>::value, true, void,
                                    Fp, Args...>;
 
      template <class Fp, class... Args>
      struct invoke_of
          : public std::enable_if<
                invokable<Fp, Args...>::value,
                typename invokable_r<void, Fp, Args...>::Result> {};
   } // namespace detail
 
   // is_invocable
 
   template <class Fn, class... Args>
   struct is_invocable
       : std::integral_constant<bool, detail::invokable<Fn, Args...>::value> {};
 
   template <class Ret, class Fn, class... Args>
   struct is_invocable_r
       : std::integral_constant<bool,
                                detail::invokable_r<Ret, Fn, Args...>::value> {
   };
 
   template <class Fn, class... Args>
   constexpr bool is_invocable_v = is_invocable<Fn, Args...>::value;
 
   template <class Ret, class Fn, class... Args>
   constexpr bool is_invocable_r_v = is_invocable_r<Ret, Fn, Args...>::value;
 
   // is_nothrow_invocable
 
   template <class Fn, class... Args>
   struct is_nothrow_invocable
       : std::integral_constant<bool,
                                detail::nothrow_invokable<Fn, Args...>::value> {
   };
 
   template <class Ret, class Fn, class... Args>
   struct is_nothrow_invocable_r
       : std::integral_constant<
             bool, detail::nothrow_invokable_r<Ret, Fn, Args...>::value> {};
 
   template <class Fn, class... Args>
   constexpr bool is_nothrow_invocable_v
       = is_nothrow_invocable<Fn, Args...>::value;
 
   template <class Ret, class Fn, class... Args>
   constexpr bool is_nothrow_invocable_r_v
       = is_nothrow_invocable_r<Ret, Fn, Args...>::value;
 
} // namespace fakestd
#else
namespace fakestd = std;
#endif
 
using fakestd::is_invocable;
using fakestd::is_invocable_v;
 
using fakestd::is_invocable_r;
using fakestd::is_invocable_r_v;
 
using fakestd::is_nothrow_invocable;
using fakestd::is_nothrow_invocable_v;
 
using fakestd::is_nothrow_invocable_r;
using fakestd::is_nothrow_invocable_r_v;
 
template <typename... Ts>
struct meta_type {};
 
template <typename T>
struct meta_type<T> {
   using type = T;
};
 
template <typename... Ts>
using meta_type_t = typename meta_type<Ts...>::type;
 
template <bool>
struct void_if {};
 
template <>
struct void_if<true> : meta_type<void> {};
template <bool b>
using void_if_t = typename void_if<b>::type;
 
using fakestd::void_t;
 
// metafunction_success:
// SFINAE detector for a ::type member type
template <typename T, typename = void>
struct metafunction_success : std::false_type {};
 
template <typename T>
struct metafunction_success<T, void_t<typename T::type>> : std::true_type {};
 
template <typename... T>
struct is_callable : metafunction_success<fakestd::invoke_result<T...>> {};
 
template <typename T>
using metafunction_value_t
    = std::integral_constant<decltype(T::value), T::value>;
 
template <bool V, typename T>
struct return_assert {};
 
template <typename T>
struct return_assert<true, T> : meta_type<T> {};
 
template <bool V, typename T>
using return_assert_t = typename return_assert<V, T>::type;
 
namespace detail {
 
   template <typename F, typename Arg, typename = void>
   struct apply_impl {
      template <std::size_t... Is>
      constexpr static auto do_apply(F&& f, Arg&& arg) noexcept(
          noexcept(kblib::invoke(std::forward<F>(f),
                                 std::get<Is>(std::forward<Arg>(arg))...)))
          -> decltype(auto) {
         return kblib::invoke(std::forward<F>(f),
                              std::get<Is>(std::forward<Arg>(arg))...);
      }
   };
 
} // namespace detail
 
template <typename F, typename Arg>
constexpr auto apply(F&& f, Arg&& arg) noexcept(
    noexcept(detail::apply_impl<F, Arg>::do_apply(
        std::forward<F>(f), std::forward<Arg>(arg),
        std::index_sequence<std::tuple_size<Arg>::value>{})))
    -> decltype(auto) {
   return detail::apply_impl<F, Arg>::do_apply(
       std::forward<F>(f), std::forward<Arg>(arg),
       std::index_sequence<std::tuple_size<Arg>::value>{});
}
 
template <typename T>
KBLIB_NODISCARD auto to_unique(gsl::owner<T*> p) -> std::unique_ptr<T> {
   return std::unique_ptr<T>(p);
}
template <typename T, typename D>
KBLIB_NODISCARD auto to_unique(gsl::owner<T*> p, D&& d)
    -> std::unique_ptr<T, D> {
   return std::unique_ptr<T, D>(p, d);
}
 
template <typename I>
KBLIB_NODISCARD constexpr auto to_unsigned(I x) -> std::make_unsigned_t<I> {
   return static_cast<std::make_unsigned_t<I>>(x);
}
template <typename I>
KBLIB_NODISCARD constexpr auto to_signed(I x) -> std::make_signed_t<I> {
   return static_cast<std::make_signed_t<I>>(x);
}
 
template <typename A, typename F>
KBLIB_NODISCARD constexpr auto signed_cast(F x)
    -> enable_if_t<std::is_integral<A>::value and std::is_integral<F>::value
                       and std::is_signed<A>::value,
                   std::make_signed_t<F>> {
   return to_signed(x);
}
 
template <typename A, typename F>
KBLIB_NODISCARD constexpr auto signed_cast(F x)
    -> enable_if_t<std::is_integral<A>::value and std::is_integral<F>::value
                       and std::is_unsigned<A>::value,
                   std::make_unsigned_t<F>> {
   return to_unsigned(x);
}
 
template <typename T>
struct has_member_swap {
 private:
   using yes = char (&)[1];
   using no = char (&)[2];
 
   template <typename C>
   static auto check(decltype(&C::swap)) -> yes;
   template <typename>
   static auto check(...) -> no;
 
 public:
   constexpr static bool value = sizeof(check<T>(nullptr)) == sizeof(yes);
};
 
template <typename T, typename = void>
struct is_tuple_like : std::false_type {};
 
template <typename T>
struct is_tuple_like<T, void_t<typename std::tuple_element<0, T>::type>>
    : std::true_type {};
 
namespace detail {
 
   template <typename... Ts>
   constexpr auto ignore(Ts&&... /*unused*/) noexcept -> void {}
 
   template <typename T, std::size_t... Is>
   constexpr auto
   swap_tuple_impl(T& a, T& b, std::index_sequence<Is...> /*unused*/) noexcept(
       noexcept(ignore(((void)swap(std::get<Is>(a), std::get<Is>(b)), 0)...)))
       -> void {
      ignore(((void)swap(std::get<Is>(a), std::get<Is>(b)), 0)...);
   }
 
} // namespace detail
 
KBLIB_UNUSED struct {
   template <typename T, enable_if_t<not has_member_swap<T>::value
                                         and not is_tuple_like<T>::value,
                                     int> = 0>
   KBLIB_UNUSED constexpr auto operator()(T& a, T& b) const
       noexcept(std::is_nothrow_move_constructible<T>::value and
                    std::is_nothrow_move_assignable<T>::value) -> void {
      auto tmp = std::move(a);
      a = std::move(b);
      b = std::move(tmp);
      return;
   }
 
   template <typename T, enable_if_t<has_member_swap<T>::value, int> = 0>
   KBLIB_UNUSED constexpr auto operator()(T& a, T& b) const
       noexcept(noexcept(a.swap(b))) -> void {
      a.swap(b);
      return;
   }
 
   template <typename T, std::size_t N>
   KBLIB_UNUSED constexpr auto operator()(T (&a)[N], T (&b)[N]) const
       noexcept(std::is_nothrow_move_constructible<T>::value and
                    std::is_nothrow_move_assignable<T>::value) -> void {
      for (std::size_t i = 0; i < N; ++i) {
         swap(a[i], b[i]);
      }
   }
 
   template <typename T, enable_if_t<is_tuple_like<T>::value
                                         and not has_member_swap<T>::value,
                                     std::size_t>
                             N
                         = std::tuple_size<T>::value>
   KBLIB_UNUSED constexpr auto operator()(T& a, T& b) const noexcept(noexcept(
       detail::swap_tuple_impl(a, b, std::make_index_sequence<N>{}))) -> void {
      detail::swap_tuple_impl(a, b, std::make_index_sequence<N>{});
   }
} KBLIB_CONSTANT swap;
 
template <typename T, typename U = T>
KBLIB_NODISCARD constexpr auto exchange(T& obj, U&& new_value) -> T {
   T old_value = std::move(obj);
   obj = std::forward<U>(new_value);
   return old_value;
}
 
#if KBLIB_USE_CXX17
 
namespace detail {
 
   template <typename T>
   constexpr std::intmax_t max_val = std::numeric_limits<T>::max();
 
   KBLIB_NODISCARD constexpr auto msb(std::uintmax_t x) -> std::uintmax_t {
      x |= (x >> 1u);
      x |= (x >> 2u);
      x |= (x >> 4u);
      x |= (x >> 8u);
      x |= (x >> 16u);
      x |= (x >> 32u);
      return (x & ~(x >> 1u));
   }
 
   template <typename Num>
   KBLIB_NODISCARD constexpr auto msb_possible() -> Num {
      return static_cast<Num>(typename std::make_unsigned<Num>::type{1}
                              << (std::numeric_limits<Num>::digits - 1u));
   }
 
   template <class... Args>
   struct type_list {
      template <std::size_t N>
      using type = typename std::tuple_element<N, std::tuple<Args...>>::type;
   };
 
   template <auto K, typename V>
   struct type_map_el {
      constexpr static auto key = K;
      using value = V;
   };
 
   template <typename Key, typename Comp, typename... Vals>
   struct type_map {
      using types = type_list<Vals...>;
      template <std::size_t I>
      using element = typename types::template type<I>;
 
      template <Key key, std::size_t I = 0>
      KBLIB_NODISCARD constexpr static auto get() noexcept -> auto {
         static_assert(I < sizeof...(Vals), "key not found");
         if constexpr (Comp{}(key, element<I>::key)) {
            return tag<typename element<I>::value>{};
         } else {
            return get<key, I + 1>();
         }
      }
 
      template <Key key, typename Default = void, std::size_t I = 0>
      KBLIB_NODISCARD constexpr static auto get_default() noexcept -> auto {
         if constexpr (I == sizeof...(Vals)) {
            return Default();
         } else if constexpr (Comp{}(key, element<I>::key)) {
            return tag<typename element<I>::value>{};
         } else {
            return get<key, I + 1>();
         }
      }
   };
 
   template <typename N>
   using make_smap_el
       = type_map_el<static_cast<std::intmax_t>(msb_possible<N>()), N>;
 
   template <typename T>
   struct next_larger_signed {
      static_assert(max_val<T> < max_val<std::intmax_t>,
                    "Cannot safely promote intmax_t.");
      struct false_compare {
         template <typename U>
         constexpr auto operator()(U, U) noexcept -> bool {
            return true;
         }
      };
 
      using ints_map = type_map<
          std::intmax_t, std::less<>, make_smap_el<std::int_least8_t>,
          make_smap_el<std::int_least16_t>, make_smap_el<std::int_least32_t>,
          make_smap_el<std::int_least64_t>, make_smap_el<std::intmax_t>>;
 
      using type = typename decltype(
          ints_map::template get_default<max_val<T> + 1>())::type;
   };
 
   template <typename N, bool = std::is_signed<N>::value>
   struct filter_signed;
 
   template <typename N>
   struct filter_signed<N, true> {
      using type = N;
   };
 
   template <typename N>
   using filter_signed_t = typename filter_signed<N>::type;
 
   template <typename N, bool = std::is_unsigned<N>::value>
   struct filter_unsigned;
 
   template <typename N>
   struct filter_unsigned<N, true> {
      using type = N;
   };
 
   template <typename N>
   using filter_unsigned_t = typename filter_unsigned<N>::type;
 
} // namespace detail
 
template <typename N, typename = void>
struct safe_signed;
 
template <typename N>
struct safe_signed<N, std::enable_if_t<std::is_integral<N>::value, void>> {
   using type = std::conditional_t<
       std::is_signed<N>::value, N,
       typename detail::next_larger_signed<std::make_signed_t<N>>::type>;
};
 
template <typename N>
using safe_signed_t = typename safe_signed<N>::type;
 
template <typename N>
KBLIB_NODISCARD constexpr auto signed_promote(N x) noexcept
    -> safe_signed_t<N> {
   return static_cast<safe_signed_t<N>>(x);
}
 
#endif
 
template <typename C, typename T,
          bool = std::is_const<typename std::remove_reference<C>::type>::value>
struct copy_const : meta_type<T> {};
 
template <typename C, typename T>
struct copy_const<C, T, true> : meta_type<const T> {};
 
template <typename C, typename T>
struct copy_const<C, T&, true> : meta_type<const T&> {};
 
template <typename C, typename T>
struct copy_const<C, T&&, true> : meta_type<const T&&> {};
 
template <typename C, typename V>
using copy_const_t = typename copy_const<C, V>::type;
 
template <typename T, typename = void>
struct value_detected : std::false_type {};
 
template <typename T>
struct value_detected<T, void_t<typename T::value_type>> : std::true_type {
   using type = typename T::value_type;
};
 
template <typename T>
constexpr bool value_detected_v = value_detected<T>::value;
template <typename T>
using value_detected_t = typename value_detected<T>::type;
 
template <typename T, typename = void>
struct key_detected : std::false_type {};
 
template <typename T>
struct key_detected<T, void_t<typename T::key_type>> : std::true_type {
   using type = typename T::key_type;
};
 
template <typename T>
constexpr bool key_detected_v = key_detected<T>::value;
template <typename T>
using key_detected_t = typename key_detected<T>::type;
 
template <typename T, typename = void>
struct mapped_detected : std::false_type {};
 
template <typename T>
struct mapped_detected<T, void_t<typename T::mapped_type>> : std::true_type {
   using type = typename T::mapped_type;
};
 
template <typename T>
constexpr bool mapped_detected_v = mapped_detected<T>::value;
template <typename T>
using mapped_detected_t = typename mapped_detected<T>::type;
 
template <typename T, typename = void>
struct hash_detected : std::false_type {};
 
template <typename T>
struct hash_detected<T, void_t<typename T::hasher>> : std::true_type {
   using type = typename T::hasher;
};
 
template <typename T>
constexpr bool hash_detected_v = hash_detected<T>::value;
template <typename T>
using hash_detected_t = typename hash_detected<T>::type;
 
template <typename Container, bool = key_detected_v<Container>,
          typename T = typename Container::value_type>
struct value_type_linear {};
 
template <typename Container>
struct value_type_linear<Container, false, typename Container::value_type>
    : meta_type<typename Container::value_type> {};
 
template <typename Container>
using value_type_linear_t = typename value_type_linear<Container>::type;
 
template <typename Container>
constexpr static bool is_linear_container_v
    = value_detected_v<Container> and not key_detected_v<Container>;
 
template <typename Container>
struct is_linear_container : bool_constant<is_linear_container_v<Container>> {};
 
template <typename Container, bool = key_detected_v<Container>,
          bool = mapped_detected_v<Container>>
struct key_type_setlike {};
 
template <typename Container>
struct key_type_setlike<Container, true, false>
    : meta_type<typename Container::key_type> {};
 
template <typename Container>
using key_type_setlike_t = typename key_type_setlike<Container>::type;
 
template <typename Container>
constexpr static bool is_setlike_v
    = (key_detected_v<
           Container> and value_detected_v<Container> and not mapped_detected_v<Container> and std::is_same<key_detected_t<Container>, value_detected_t<Container>>::value);
 
template <class InputIt1, class InputIt2>
KBLIB_NODISCARD constexpr auto equal(InputIt1 first1, InputIt1 last1,
                                     InputIt2 first2) -> bool {
   for (; first1 != last1; ++first1, ++first2) {
      if (not (*first1 == *first2)) {
         return false;
      }
   }
   return true;
}
 
template <typename InputIt1, typename InputIt2, typename BinaryPredicate,
          typename kblib::enable_if_t<
              not std::is_same<InputIt2, BinaryPredicate>::value, int> = 0>
KBLIB_NODISCARD constexpr auto equal(InputIt1 first1, InputIt1 last1,
                                     InputIt2 first2, BinaryPredicate p)
    -> bool {
   for (; first1 != last1; ++first1, ++first2) {
      if (not p(*first1, *first2)) {
         return false;
      }
   }
   return true;
}
template <class RandomIt1, class RandomIt2,
          typename kblib::enable_if_t<
              std::is_base_of<std::random_access_iterator_tag,
                              typename std::iterator_traits<
                                  RandomIt1>::iterator_category>::value
                  and std::is_base_of<std::random_access_iterator_tag,
                                      typename std::iterator_traits<
                                          RandomIt2>::iterator_category>::value,
              int> = 0>
KBLIB_NODISCARD constexpr auto equal(RandomIt1 first1, RandomIt1 last1,
                                     RandomIt2 first2, RandomIt2 last2)
    -> bool {
   if (std::distance(first1, last1) == std::distance(first2, last2)) {
      return false;
   }
   for (; first1 != last1; ++first1, ++first2) {
      if (not (*first1 == *first2)) {
         return false;
      }
   }
   return true;
}
 
template <class RandomIt1, class RandomIt2, typename BinaryPredicate,
          typename kblib::enable_if_t<
              std::is_base_of<std::random_access_iterator_tag,
                              typename std::iterator_traits<
                                  RandomIt1>::iterator_category>::value
                  and std::is_base_of<std::random_access_iterator_tag,
                                      typename std::iterator_traits<
                                          RandomIt2>::iterator_category>::value,
              int> = 0>
KBLIB_NODISCARD constexpr auto equal(RandomIt1 first1, RandomIt1 last1,
                                     RandomIt2 first2, RandomIt2 last2,
                                     BinaryPredicate p) -> bool {
   if (std::distance(first1, last1) == std::distance(first2, last2)) {
      return false;
   }
   for (; first1 != last1; ++first1, ++first2) {
      if (not p(*first1, *first2)) {
         return false;
      }
   }
   return true;
}
template <
    class InputIt1, class InputIt2,
    typename kblib::enable_if_t<
        not std::is_base_of<
            std::random_access_iterator_tag,
            typename std::iterator_traits<InputIt1>::iterator_category>::value
            or not std::is_base_of<std::random_access_iterator_tag,
                                   typename std::iterator_traits<
                                       InputIt2>::iterator_category>::value,
        int> = 0>
KBLIB_NODISCARD constexpr auto equal(InputIt1 first1, InputIt1 last1,
                                     InputIt2 first2, InputIt2 last2) -> bool {
   for (; first1 != last1 and first2 != last2; ++first1, ++first2) {
      if (not (*first1 == *first2)) {
         return false;
      }
   }
   return (first1 == last1 and first2 == last2);
}
 
template <
    typename InputIt1, typename InputIt2, typename BinaryPredicate,
    typename kblib::enable_if_t<
        not std::is_base_of<
            std::random_access_iterator_tag,
            typename std::iterator_traits<InputIt1>::iterator_category>::value
            or not std::is_base_of<std::random_access_iterator_tag,
                                   typename std::iterator_traits<
                                       InputIt2>::iterator_category>::value,
        int> = 0>
KBLIB_NODISCARD constexpr auto equal(InputIt1 first1, InputIt1 last1,
                                     InputIt2 first2, InputIt2 last2,
                                     BinaryPredicate p) -> bool {
   for (; first1 != last1 and first2 != last2; ++first1, ++first2) {
      if (not p(*first1, *first2)) {
         return false;
      }
   }
   return (first1 == last1 and first2 == last2);
}
 
template <typename C>
KBLIB_NODISCARD constexpr auto size(const C& c) -> decltype(c.size()) {
   return c.size();
}
 
template <typename T, std::size_t N>
KBLIB_NODISCARD constexpr auto size(const T (&)[N]) noexcept -> std::size_t {
   return N;
}
 
template <class InputIt1, class InputIt2>
KBLIB_NODISCARD constexpr auto lexicographical_compare(InputIt1 first1,
                                                       InputIt1 last1,
                                                       InputIt2 first2,
                                                       InputIt2 last2) -> bool {
   for (; (first1 != last1) and (first2 != last2); ++first1, (void)++first2) {
      if (*first1 < *first2)
         return true;
      if (*first2 < *first1)
         return false;
   }
   return (first1 == last1) and (first2 != last2);
}
 
namespace detail {
   template <typename D, typename T, typename = void>
   struct pointer {
      using type = T*;
   };
 
   template <typename D, typename T>
   struct pointer<D, T, void_t<typename D::pointer>> {
      using type = typename D::pointer;
   };
 
} // namespace detail
 
constexpr struct in_place_agg_t {
} in_place_agg;
 
template <typename T>
class heap_value {
 public:
   using element_type = T;
   using pointer = T*;
   using const_pointer = const T*;
   using reference = T&;
   using const_reference = const T&;
 
   constexpr heap_value() noexcept
       : p{nullptr} {}
   constexpr heap_value(std::nullptr_t) noexcept
       : p{nullptr} {}
 
   template <typename... Args,
             enable_if_t<std::is_constructible<T, Args...>::value> = 0>
   heap_value(fakestd::in_place_t, Args&&... args)
       : p{new T(args...)} {}
   template <typename... Args,
             enable_if_t<std::is_constructible<T, Args...>::value> = 0>
   heap_value(in_place_agg_t, Args&&... args)
       : p{new T{args...}} {}
 
   heap_value(const heap_value& u)
       : p{(u.p ? (new T(*u.p)) : nullptr)} {}
   heap_value(heap_value&& u) noexcept
       : p{std::exchange(u.p, nullptr)} {}
 
   auto operator=(const heap_value& u) & -> heap_value& {
      if (this == &u) {
         return *this;
      } else if (not u) {
         p.reset();
      } else if (p) {
         *p = *u;
      } else {
         p.reset(new T(*u.p));
      }
      return *this;
   }
 
   auto operator=(heap_value&& u) & noexcept -> heap_value& {
      if (this == &u) {
         return *this;
      }
      p = std::exchange(u.p, nullptr);
      return *this;
   }
 
   auto operator=(const T& val) & -> heap_value& {
      if (this == &val) {
         return *this;
      }
      p.reset(new T(val));
   }
   auto operator=(T&& val) & -> heap_value& {
      if (this == &val) {
         return *this;
      }
      p.reset(new T(std::move(val)));
   }
 
   auto assign() & -> void { p.reset(new T()); }
   auto assign(const T& val) & -> void { p.reset(new T(val)); }
   auto assign(T&& val) & -> void { p.reset(new T(std::move(val))); }
   template <typename... Args>
   auto assign(fakestd::in_place_t, Args&&... args) -> void {
      p.reset(new T(std::forward<Args>(args)...));
   }
   template <typename... Args>
   auto assign(in_place_agg_t, Args&&... args) -> void {
      p.reset(new T{std::forward<Args>(args)...});
   }
 
   auto reset() noexcept -> void {
      p.reset();
      return;
   }
 
   KBLIB_NODISCARD explicit operator bool() const& noexcept {
      return p != nullptr;
   }
 
   constexpr auto swap(heap_value& other) noexcept -> void {
      kblib::swap(p, other.p);
   }
 
   KBLIB_NODISCARD auto get() & noexcept -> pointer { return p.get(); }
   KBLIB_NODISCARD auto get() const& noexcept -> const_pointer {
      return p.get();
   }
 
   KBLIB_NODISCARD auto value() & noexcept -> reference { return *p; }
   KBLIB_NODISCARD auto value() const& noexcept -> const_reference {
      return *p;
   }
   KBLIB_NODISCARD auto value() && noexcept -> T&& { return *p; }
   KBLIB_NODISCARD auto value() const&& noexcept -> const T&& { return *p; }
 
   KBLIB_NODISCARD auto operator*() & noexcept -> reference { return *p; }
   KBLIB_NODISCARD auto operator*() const& noexcept -> const_reference {
      return *p;
   }
   KBLIB_NODISCARD auto operator*() && noexcept -> T&& { return *p; }
   KBLIB_NODISCARD auto operator*() const&& noexcept -> const T&& { return *p; }
 
   KBLIB_NODISCARD auto operator->() & noexcept -> pointer { return p.get(); }
   KBLIB_NODISCARD auto operator->() const& noexcept -> const_pointer {
      return p.get();
   }
 
   ~heap_value() = default;
 
 private:
   std::unique_ptr<element_type> p;
};
 
template <typename T, typename D>
class heap_value2 : private std::unique_ptr<T, D> {
   using Base = std::unique_ptr<T, D>;
 
 public:
   using typename Base::deleter_type;
   using typename Base::element_type;
   using typename Base::pointer;
   using reference = decltype(*std::declval<pointer>());
   using const_reference = const element_type&;
 
   using Base::Base;
   using Base::operator=;
   heap_value2(const heap_value2& other);
   heap_value2& operator=(const heap_value2& other);
 
   using Base::release;
   using Base::reset;
   using Base::swap;
 
   using Base::get;
   using Base::get_deleter;
   using Base::operator bool;
 
   using Base::operator*;
   using Base::operator->;
 
   KBLIB_NODISCARD auto value() & noexcept -> reference { return **this; }
   KBLIB_NODISCARD auto value() const& noexcept -> const_reference {
      return **this;
   }
   KBLIB_NODISCARD auto value() && noexcept -> element_type&& { return **this; }
   KBLIB_NODISCARD auto value() const&& noexcept -> const element_type&& {
      return **this;
   }
 
   ~heap_value2() = default;
};
 
template <typename T, typename D>
class heap_value2<T[], D> : private std::unique_ptr<T[], D> {
   using Base = std::unique_ptr<T[], D>;
 
 public:
   using typename Base::deleter_type;
   using typename Base::element_type;
   using typename Base::pointer;
   using reference = element_type&;
   using const_reference = const element_type&;
 
   using Base::Base;
   using Base::operator=;
   heap_value2(const heap_value2& other);
   heap_value2& operator=(const heap_value2& other);
 
   using Base::release;
   using Base::reset;
   using Base::swap;
 
   using Base::get;
   using Base::get_deleter;
   using Base::operator bool;
 
   using Base::operator[];
 
   KBLIB_NODISCARD auto value() & noexcept -> reference { return **this; }
   KBLIB_NODISCARD auto value() const& noexcept -> const_reference {
      return **this;
   }
   KBLIB_NODISCARD auto value() && noexcept -> element_type&& { return **this; }
   KBLIB_NODISCARD auto value() const&& noexcept -> const element_type&& {
      return **this;
   }
 
   ~heap_value2() = default;
};
 
} // namespace kblib
 
#endif // KBLIB_FAKESTD_H