#pragma once

#ifndef _XUTILITY_

#define _XUTILITY_

#include <yvals.h>

#if _STL_COMPILER_PREPROCESSOR

#include <climits>

#include <cstdlib>

#include <cstring>

#include <utility>

#pragma pack(push, _CRT_PACKING)

#pragma warning(push, _STL_WARNING_LEVEL)

#pragma warning(disable : _STL_DISABLED_WARNINGS)

_STL_DISABLE_CLANG_WARNINGS

#pragma push_macro("new")

#undef new

#if (defined(_M_IX86) || defined(_M_X64)) && !defined(_M_CEE_PURE) && !defined(_M_HYBRID)

#ifndef _USE_STD_VECTOR_ALGORITHMS

#define _USE_STD_VECTOR_ALGORITHMS 1

#endif // _USE_STD_VECTOR_ALGORITHMS

#else // ^^^ arch supports vector algorithms / no support for vector algorithms vvv

#ifndef _USE_STD_VECTOR_ALGORITHMS

#define _USE_STD_VECTOR_ALGORITHMS 0

#elif _USE_STD_VECTOR_ALGORITHMS

#error Vector algorithms are not supported on this architecture, but _USE_STD_VECTOR_ALGORITHMS is set.

#endif // _USE_STD_VECTOR_ALGORITHMS

#endif // ^^^ no support for vector algorithms ^^^

#ifdef __CUDACC__

#define _CONSTEXPR_BIT_CAST inline

#else // ^^^ workaround ^^^ / vvv no workaround vvv

#define _CONSTEXPR_BIT_CAST constexpr

#endif // ^^^ no workaround ^^^

#if _USE_STD_VECTOR_ALGORITHMS

_EXTERN_C

__declspec(noalias) void __cdecl __std_reverse_trivially_swappable_1(void* _First, void* _Last) noexcept;

__declspec(noalias) void __cdecl __std_reverse_trivially_swappable_2(void* _First, void* _Last) noexcept;

__declspec(noalias) void __cdecl __std_reverse_trivially_swappable_4(void* _First, void* _Last) noexcept;

__declspec(noalias) void __cdecl __std_reverse_trivially_swappable_8(void* _First, void* _Last) noexcept;

__declspec(noalias) void __cdecl __std_swap_ranges_trivially_swappable_noalias(

void* _First1, void* _Last1, void* _First2) noexcept;

_END_EXTERN_C

#endif // _USE_STD_VECTOR_ALGORITHMS

_STD_BEGIN

template <class _To, class _From,

enable_if_t<conjunction_v<bool_constant<sizeof(_To) == sizeof(_From)>, is_trivially_copyable<_To>,

is_trivially_copyable<_From>>,

int> = 0>

_NODISCARD _CONSTEXPR_BIT_CAST _To _Bit_cast(const _From& _Val) noexcept {

#ifdef __CUDACC__

_To _To_obj; // assumes default-init

_CSTD memcpy(_STD addressof(_To_obj), _STD addressof(_Val), sizeof(_To));

return _To_obj;

#else // ^^^ workaround ^^^ / vvv no workaround vvv

return __builtin_bit_cast(_To, _Val);

#endif // ^^^ no workaround ^^^

}

template <class _Ty>

struct _Get_first_parameter;

template <template <class, class...> class _Ty, class _First, class... _Rest>

struct _Get_first_parameter<_Ty<_First, _Rest...>> { // given _Ty<_First, _Rest...>, extract _First

using type = _First;

};

template <class _Newfirst, class _Ty>

struct _Replace_first_parameter;

template <class _Newfirst, template <class, class...> class _Ty, class _First, class... _Rest>

struct _Replace_first_parameter<_Newfirst, _Ty<_First, _Rest...>> { // given _Ty<_First, _Rest...>, replace _First

using type = _Ty<_Newfirst, _Rest...>;

};

template <class _Ty, class = void>

struct _Get_element_type {

using type = typename _Get_first_parameter<_Ty>::type;

};

template <class _Ty>

struct _Get_element_type<_Ty, void_t<typename _Ty::element_type>> {

using type = typename _Ty::element_type;

};

template <class _Ty, class = void>

struct _Get_ptr_difference_type {

using type = ptrdiff_t;

};

template <class _Ty>

struct _Get_ptr_difference_type<_Ty, void_t<typename _Ty::difference_type>> {

using type = typename _Ty::difference_type;

};

template <class _Ty, class _Other, class = void>

struct _Get_rebind_alias {

using type = typename _Replace_first_parameter<_Other, _Ty>::type;

};

template <class _Ty, class _Other>

struct _Get_rebind_alias<_Ty, _Other, void_t<typename _Ty::template rebind<_Other>>> {

using type = typename _Ty::template rebind<_Other>;

};

template <class _Iter>

_NODISCARD constexpr void* _Voidify_iter(_Iter _It) noexcept {

if constexpr (is_pointer_v<_Iter>) {

return const_cast<void*>(static_cast<const volatile void*>(_It));

} else {

return const_cast<void*>(static_cast<const volatile void*>(_STD addressof(*_It)));

}

}

#if _HAS_CXX20

template <class _Ty, class... _Types,

class = void_t<decltype(::new (_STD declval<void*>()) _Ty(_STD declval<_Types>()...))>>

constexpr _Ty* construct_at(_Ty* const _Location, _Types&&... _Args) noexcept(

noexcept(::new (_Voidify_iter(_Location)) _Ty(_STD forward<_Types>(_Args)...))) /* strengthened */ {

return ::new (_Voidify_iter(_Location)) _Ty(_STD forward<_Types>(_Args)...);

}

#endif // _HAS_CXX20

template <class _Ty, class... _Types>

_CONSTEXPR20 void _Construct_in_place(_Ty& _Obj, _Types&&... _Args) noexcept(

is_nothrow_constructible_v<_Ty, _Types...>) {

#if _HAS_CXX20

if (_STD is_constant_evaluated()) {

_STD construct_at(_STD addressof(_Obj), _STD forward<_Types>(_Args)...);

} else

#endif // _HAS_CXX20

{

::new (_Voidify_iter(_STD addressof(_Obj))) _Ty(_STD forward<_Types>(_Args)...);

}

}

template <class _Ty>

void _Default_construct_in_place(_Ty& _Obj) noexcept(is_nothrow_default_constructible_v<_Ty>) {

::new (_Voidify_iter(_STD addressof(_Obj))) _Ty;

}

template <class _Ty>

struct pointer_traits {

using pointer = _Ty;

using element_type = typename _Get_element_type<_Ty>::type;

using difference_type = typename _Get_ptr_difference_type<_Ty>::type;

template <class _Other>

using rebind = typename _Get_rebind_alias<_Ty, _Other>::type;

using _Reftype = conditional_t<is_void_v<element_type>, char, element_type>&;

_NODISCARD static pointer pointer_to(_Reftype _Val) noexcept(noexcept(_Ty::pointer_to(_Val))) /* strengthened */ {

return _Ty::pointer_to(_Val);

}

};

template <class _Ty>

struct pointer_traits<_Ty*> {

using pointer = _Ty*;

using element_type = _Ty;

using difference_type = ptrdiff_t;

template <class _Other>

using rebind = _Other*;

using _Reftype = conditional_t<is_void_v<_Ty>, char, _Ty>&;

_NODISCARD static _CONSTEXPR20 pointer pointer_to(_Reftype _Val) noexcept {

return _STD addressof(_Val);

}

};

#if _HAS_CXX20

template <class _Ty, class = void>

inline constexpr bool _Has_to_address_v = false; // determines whether _Ptr has pointer_traits<_Ptr>::to_address(p)

template <class _Ty>

inline constexpr bool

_Has_to_address_v<_Ty, void_t<decltype(pointer_traits<_Ty>::to_address(_STD declval<const _Ty&>()))>> = true;

template <class _Ty>

_NODISCARD constexpr _Ty* to_address(_Ty* const _Val) noexcept {

static_assert(!is_function_v<_Ty>,

"N4810 20.10.4 [pointer.conversion]/2: The program is ill-formed if T is a function type.");

return _Val;

}

template <class _Ptr>

_NODISCARD constexpr auto to_address(const _Ptr& _Val) noexcept {

if constexpr (_Has_to_address_v<_Ptr>) {

return pointer_traits<_Ptr>::to_address(_Val);

} else {

return _STD to_address(_Val.operator->()); // plain pointer overload must come first

}

}

struct identity {

template <class _Ty>

_NODISCARD constexpr _Ty&& operator()(_Ty&& _Left) const noexcept {

return _STD forward<_Ty>(_Left);

}

using is_transparent = int;

};

#endif // _HAS_CXX20

template <class _Fx>

struct _Ref_fn { // pass function object by value as a reference

template <class... _Args>

constexpr decltype(auto) operator()(_Args&&... _Vals) { // forward function call operator

if constexpr (is_member_pointer_v<_Fx>) {

return _STD invoke(_Fn, _STD forward<_Args>(_Vals)...);

} else {

return _Fn(_STD forward<_Args>(_Vals)...);

}

}

_Fx& _Fn;

};

template <class _Fn>

_INLINE_VAR constexpr bool _Pass_functor_by_value_v = conjunction_v<bool_constant<sizeof(_Fn) <= sizeof(void*)>,

is_trivially_copy_constructible<_Fn>, is_trivially_destructible<_Fn>>;

template <class _Fn, enable_if_t<_Pass_functor_by_value_v<_Fn>, int> = 0> // TRANSITION, if constexpr

constexpr _Fn _Pass_fn(_Fn _Val) { // pass functor by value

return _Val;

}

template <class _Fn, enable_if_t<!_Pass_functor_by_value_v<_Fn>, int> = 0>

constexpr _Ref_fn<_Fn> _Pass_fn(_Fn& _Val) { // pass functor by "reference"

return {_Val};

}

struct _Unused_parameter { // generic unused parameter struct

constexpr _Unused_parameter() noexcept = default;

template <class _Ty>

constexpr _Unused_parameter(_Ty&&) noexcept {}

};

using _Any_tag = _Unused_parameter; // generic fallback/default/"other" target for tag dispatch

template <class _Ty>

using _Algorithm_int_t = conditional_t<is_integral_v<_Ty>, _Ty, ptrdiff_t>;

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag : input_iterator_tag {};

struct bidirectional_iterator_tag : forward_iterator_tag {};

struct random_access_iterator_tag : bidirectional_iterator_tag {};

#ifdef __cpp_lib_concepts

struct contiguous_iterator_tag : random_access_iterator_tag {};

template <class _Ty>

using _With_reference = _Ty&;

template <class _Ty>

concept _Can_reference = requires { typename _With_reference<_Ty>; };

template <class _Ty>

concept _Dereferenceable = requires(_Ty& __t) {

{ *__t } -> _Can_reference;

};

template <class _Ty>

concept _Has_member_iterator_concept = requires {

typename _Ty::iterator_concept;

};

template <class _Ty>

concept _Has_member_iterator_category = requires {

typename _Ty::iterator_category;

};

template <class _Ty>

concept _Has_member_value_type = requires {

typename _Ty::value_type;

};

template <class _Ty>

concept _Has_member_element_type = requires {

typename _Ty::element_type;

};

template <class _Ty>

concept _Has_member_difference_type = requires {

typename _Ty::difference_type;

};

template <class _Ty>

concept _Has_member_pointer = requires {

typename _Ty::pointer;

};

template <class _Ty>

concept _Has_member_reference = requires {

typename _Ty::reference;

};

template <class>

struct incrementable_traits {};

template <class _Ty>

requires is_object_v<_Ty>

struct incrementable_traits<_Ty*> {

using difference_type = ptrdiff_t;

};

template <class _Ty>

struct incrementable_traits<const _Ty> : incrementable_traits<_Ty> {};

template <_Has_member_difference_type _Ty>

struct incrementable_traits<_Ty> {

using difference_type = typename _Ty::difference_type;

};

template <class _Ty>

concept _Can_difference = requires(const _Ty& __a, const _Ty& __b) {

{ __a - __b } -> integral;

};

template <class _Ty>

requires (!_Has_member_difference_type<_Ty> && _Can_difference<_Ty>)

struct incrementable_traits<_Ty> {

using difference_type = make_signed_t<decltype(_STD declval<_Ty>() - _STD declval<_Ty>())>;

};

template <class _Ty>

concept _Is_from_primary = _Same_impl<typename _Ty::_From_primary, _Ty>;

template <class>

struct iterator_traits;

template <class _Ty>

using iter_difference_t = typename conditional_t<_Is_from_primary<iterator_traits<remove_cvref_t<_Ty>>>,

incrementable_traits<remove_cvref_t<_Ty>>, iterator_traits<remove_cvref_t<_Ty>>>::difference_type;

template <class>

struct _Cond_value_type {};

template <class _Ty>

requires is_object_v<_Ty>

struct _Cond_value_type<_Ty> {

using value_type = remove_cv_t<_Ty>;

};

template <class>

struct indirectly_readable_traits {};

template <class _Ty>

struct indirectly_readable_traits<_Ty*> : _Cond_value_type<_Ty> {};

template <class _Ty>

requires is_array_v<_Ty>

struct indirectly_readable_traits<_Ty> {

using value_type = remove_cv_t<remove_extent_t<_Ty>>;

};

template <class _Ty>

struct indirectly_readable_traits<const _Ty> : indirectly_readable_traits<_Ty> {};

template <_Has_member_value_type _Ty>

struct indirectly_readable_traits<_Ty> : _Cond_value_type<typename _Ty::value_type> {};

template <_Has_member_element_type _Ty>

struct indirectly_readable_traits<_Ty> : _Cond_value_type<typename _Ty::element_type> {};

template <_Has_member_value_type _Ty>

requires _Has_member_element_type<_Ty>

struct indirectly_readable_traits<_Ty> {};

template <_Has_member_value_type _Ty>

requires _Has_member_element_type<_Ty>

&& same_as<remove_cv_t<typename _Ty::value_type>, remove_cv_t<typename _Ty::element_type>>

struct indirectly_readable_traits<_Ty> : _Cond_value_type<typename _Ty::value_type> {};

template <class _Ty>

using iter_value_t = typename conditional_t<_Is_from_primary<iterator_traits<remove_cvref_t<_Ty>>>,

indirectly_readable_traits<remove_cvref_t<_Ty>>, iterator_traits<remove_cvref_t<_Ty>>>::value_type;

template <_Dereferenceable _Ty>

using iter_reference_t = decltype(*_STD declval<_Ty&>());

template <class>

struct _Iterator_traits_base {};

template <class _It>

concept _Has_iter_types = _Has_member_difference_type<_It> && _Has_member_value_type<_It> && _Has_member_reference<_It>

&& _Has_member_iterator_category<_It>;

template <bool _Has_member_typedef>

struct _Old_iter_traits_pointer {

template <class _It>

using _Apply = typename _It::pointer;

};

template <>

struct _Old_iter_traits_pointer<false> {

template <class>

using _Apply = void;

};

template <_Has_iter_types _It>

struct _Iterator_traits_base<_It> {

using iterator_category = typename _It::iterator_category;

using difference_type = typename _It::difference_type;

using value_type = typename _It::value_type;

using pointer = typename _Old_iter_traits_pointer<_Has_member_pointer<_It>>::template _Apply<_It>;

using reference = typename _It::reference;

};

template <bool _Has_member_typedef>

struct _Iter_traits_difference {

template <class _It>

using _Apply = typename incrementable_traits<_It>::difference_type;

};

template <>

struct _Iter_traits_difference<false> {

template <class>

using _Apply = void;

};

template <class _It>

concept _Cpp17_iterator =

requires(_It __i) {

{ *__i } -> _Can_reference;

{ ++__i } -> same_as<_It&>;

{ *__i++ } -> _Can_reference;

}

&& copyable<_It>;

template <class _It>

concept _Cpp17_input_iterator = _Cpp17_iterator<_It>

&& equality_comparable<_It>

&& _Has_member_difference_type<incrementable_traits<_It>>

&& _Has_member_value_type<indirectly_readable_traits<_It>>

&& requires(_It __i) {

typename common_reference_t<iter_reference_t<_It>&&, typename indirectly_readable_traits<_It>::value_type&>;

typename common_reference_t<decltype(*__i++)&&, typename indirectly_readable_traits<_It>::value_type&>;

requires signed_integral<typename incrementable_traits<_It>::difference_type>;

};

template <class _It>

requires (!_Has_iter_types<_It> && _Cpp17_iterator<_It> && !_Cpp17_input_iterator<_It>

// Implements the proposed resolution of LWG-3283:

&& (!requires { typename _It::iterator_category; }

|| derived_from<typename _It::iterator_category, output_iterator_tag>))

struct _Iterator_traits_base<_It> {

using iterator_category = output_iterator_tag;

using difference_type =

typename _Iter_traits_difference<_Has_member_difference_type<incrementable_traits<_It>>>::template _Apply<_It>;

using value_type = void;

using pointer = void;

using reference = void;

};

enum class _Itraits_pointer_strategy { _Use_void, _Use_member, _Use_decltype };

template <_Itraits_pointer_strategy>

struct _Iter_traits_pointer;

template <>

struct _Iter_traits_pointer<_Itraits_pointer_strategy::_Use_void> {

template <class>

using _Apply = void;

};

template <>

struct _Iter_traits_pointer<_Itraits_pointer_strategy::_Use_member> {

template <class _It>

using _Apply = typename _It::pointer;

};

template <>

struct _Iter_traits_pointer<_Itraits_pointer_strategy::_Use_decltype> {

template <class _It>

using _Apply = decltype(_STD declval<_It&>().operator->());

};

template <class _Ty>

concept _Has_member_arrow = requires(_Ty&& __t) {

static_cast<_Ty&&>(__t).operator->();

};

template <bool _Has_member_typedef>

struct _Iter_traits_reference {

template <class _It>

using _Apply = typename _It::reference;

};

template <>

struct _Iter_traits_reference<false> {

template <class _It>

using _Apply = iter_reference_t<_It>;

};

template <bool _Is_random>

struct _Iter_traits_category4 {

using type = random_access_iterator_tag;

};

template <>

struct _Iter_traits_category4<false> {

using type = bidirectional_iterator_tag;

};

template <class _It>

concept _Cpp17_random_delta = totally_ordered<_It>

&& requires(_It __i, typename incrementable_traits<_It>::difference_type __n) {

{ __i += __n } -> same_as<_It&>;

{ __i -= __n } -> same_as<_It&>;

{ __i + __n } -> same_as<_It>;

{ __n + __i } -> same_as<_It>;

{ __i - __n } -> same_as<_It>;

{ __i - __i } -> same_as<decltype(__n)>;

{ __i[__n] } -> convertible_to<iter_reference_t<_It>>;

};

template <bool _Is_bidi>

struct _Iter_traits_category3 {

template <class _It>

using _Apply = typename _Iter_traits_category4<_Cpp17_random_delta<_It>>::type;

};

template <>

struct _Iter_traits_category3<false> {

template <class>

using _Apply = forward_iterator_tag;

};

template <class _It>

concept _Cpp17_bidi_delta = requires(_It __i) {

{ --__i } -> same_as<_It&>;

{ __i-- } -> convertible_to<const _It&>;

requires same_as<decltype(*__i--), iter_reference_t<_It>>;

};

template <bool _Is_forward>

struct _Iter_traits_category2 {

template <class _It>

using _Apply = typename _Iter_traits_category3<_Cpp17_bidi_delta<_It>>::template _Apply<_It>;

};

template <>

struct _Iter_traits_category2<false> {

template <class>

using _Apply = input_iterator_tag;

};

template <class _It>

concept _Cpp17_forward_delta = constructible_from<_It> && is_lvalue_reference_v<iter_reference_t<_It>>

&& same_as<remove_cvref_t<iter_reference_t<_It>>, typename indirectly_readable_traits<_It>::value_type>

&& requires(_It __i) {

{ __i++ } -> convertible_to<const _It&>;

requires same_as<decltype(*__i++), iter_reference_t<_It>>;

};

template <bool _Has_member_typedef>

struct _Iter_traits_category {

template <class _It>

using _Apply = typename _It::iterator_category;

};

template <>

struct _Iter_traits_category<false> {

template <class _It>

using _Apply = typename _Iter_traits_category2<_Cpp17_forward_delta<_It>>::template _Apply<_It>;

};

template <class _It>

requires (!_Has_iter_types<_It> && _Cpp17_input_iterator<_It>)

struct _Iterator_traits_base<_It> {

using iterator_category = typename _Iter_traits_category<_Has_member_iterator_category<_It>>::template _Apply<_It>;

using difference_type = typename incrementable_traits<_It>::difference_type;

using value_type = typename indirectly_readable_traits<_It>::value_type;

using pointer = typename _Iter_traits_pointer<(

_Has_member_pointer<_It> ? _Itraits_pointer_strategy::_Use_member

: _Has_member_arrow<_It&> ? _Itraits_pointer_strategy::_Use_decltype

: _Itraits_pointer_strategy::_Use_void)>::template _Apply<_It>;

using reference = typename _Iter_traits_reference<_Has_member_reference<_It>>::template _Apply<_It>;

};

template <class _Ty>

struct iterator_traits : _Iterator_traits_base<_Ty> {

using _From_primary = iterator_traits;

};

template <class _Ty>

requires is_object_v<_Ty>

struct iterator_traits<_Ty*> {

using iterator_concept = contiguous_iterator_tag;

using iterator_category = random_access_iterator_tag;

using value_type = remove_cv_t<_Ty>;

using difference_type = ptrdiff_t;

using pointer = _Ty*;

using reference = _Ty&;

};

namespace ranges {

namespace _Iter_move {

void iter_move(); // Block unqualified name lookup

// clang-format off

template <class _Ty>

concept _Has_ADL = _Has_class_or_enum_type<_Ty> && requires(_Ty&& __t) {

iter_move(static_cast<_Ty&&>(__t));

};

template <class _Ty>

concept _Can_deref = requires(_Ty&& __t) {

*static_cast<_Ty&&>(__t);

};

class _Cpo {

private:

enum class _St { _None, _Custom, _Fallback };

template <class _Ty>

_NODISCARD static _CONSTEVAL _Choice_t<_St> _Choose() noexcept {

if constexpr (_Has_ADL<_Ty>) {

return {_St::_Custom, noexcept(iter_move(_STD declval<_Ty>()))};

} else if constexpr (_Can_deref<_Ty>) {

return {_St::_Fallback, noexcept(*_STD declval<_Ty>())};

} else {

return {_St::_None};

}

}

template <class _Ty>

static constexpr _Choice_t<_St> _Choice = _Choose<_Ty>();

public:

template <class _Ty>

requires (_Choice<_Ty>._Strategy != _St::_None)

_NODISCARD constexpr decltype(auto) operator()(_Ty&& _Val) const noexcept(_Choice<_Ty>._No_throw) {

constexpr _St _Strat = _Choice<_Ty>._Strategy;

if constexpr (_Strat == _St::_Custom) {

return iter_move(static_cast<_Ty&&>(_Val));

} else if constexpr (_Strat == _St::_Fallback) {

using _Ref = decltype(*static_cast<_Ty&&>(_Val));

if constexpr (is_lvalue_reference_v<_Ref>) {

return _STD move(*static_cast<_Ty&&>(_Val));

} else {

return *static_cast<_Ty&&>(_Val);

}

} else {

static_assert(_Always_false<_Ty>, "should be unreachable");

}

}

};

// clang-format on

} // namespace _Iter_move

inline namespace _Cpos {

inline constexpr _Iter_move::_Cpo iter_move;

}

} // namespace ranges

template <class _Ty>

requires _Dereferenceable<_Ty> && requires(_Ty& __t) {

{ _RANGES iter_move(__t) } -> _Can_reference;

}

using iter_rvalue_reference_t = decltype(_RANGES iter_move(_STD declval<_Ty&>()));

template <class _It>

concept _Indirectly_readable_impl = requires(const _It __i) {

typename iter_value_t<_It>;

typename iter_reference_t<_It>;

typename iter_rvalue_reference_t<_It>;

{ *__i } -> same_as<iter_reference_t<_It>>;

{ _RANGES iter_move(__i) } -> same_as<iter_rvalue_reference_t<_It>>;

} && common_reference_with<iter_reference_t<_It>&&, iter_value_t<_It>&>

&& common_reference_with<iter_reference_t<_It>&&, iter_rvalue_reference_t<_It>&&>

&& common_reference_with<iter_rvalue_reference_t<_It>&&, const iter_value_t<_It>&>;

template <class _It>

concept indirectly_readable = _Indirectly_readable_impl<remove_cvref_t<_It>>;

template <indirectly_readable _Ty>

using iter_common_reference_t = common_reference_t<iter_reference_t<_Ty>, iter_value_t<_Ty>&>;

template <class _It, class _Ty>

concept indirectly_writable = requires(_It&& __i, _Ty&& __t) {

*__i = static_cast<_Ty&&>(__t);

*static_cast<_It&&>(__i) = static_cast<_Ty&&>(__t);

const_cast<const iter_reference_t<_It>&&>(*__i) = static_cast<_Ty&&>(__t);

const_cast<const iter_reference_t<_It>&&>(*static_cast<_It&&>(__i)) = static_cast<_Ty&&>(__t);

};

template <class _Ty>

concept _Integer_like = _Is_nonbool_integral<remove_cv_t<_Ty>>;

template <class _Ty>

concept _Signed_integer_like = _Integer_like<_Ty> && static_cast<_Ty>(-1) < static_cast<_Ty>(0);

template <class _Ty>

using _Make_unsigned_like_t = make_unsigned_t<_Ty>;

template <_Integer_like _Ty>

_NODISCARD constexpr auto _To_unsigned_like(const _Ty _Value) noexcept {

return static_cast<_Make_unsigned_like_t<_Ty>>(_Value);

}

template <class _Ty>

using _Make_signed_like_t = make_signed_t<_Ty>;

template <_Integer_like _Ty>

_NODISCARD constexpr auto _To_signed_like(const _Ty _Value) noexcept {

return static_cast<_Make_signed_like_t<_Ty>>(_Value);

}

template <class _Ty>

concept weakly_incrementable = movable<_Ty> && requires(_Ty __i) {

typename iter_difference_t<_Ty>;

requires _Signed_integer_like<iter_difference_t<_Ty>>;

{ ++__i } -> same_as<_Ty&>;

__i++;

};

template <class _Ty>

concept incrementable = regular<_Ty> && weakly_incrementable<_Ty> && requires(_Ty __t) {

{ __t++ } -> same_as<_Ty>;

};

template <class _It>

concept input_or_output_iterator = requires(_It __i) {

{ *__i } -> _Can_reference;

requires weakly_incrementable<_It>;

};

template <class _Se, class _It>

concept sentinel_for = semiregular<_Se>

&& input_or_output_iterator<_It>

&& _Weakly_equality_comparable_with<_Se, _It>;

template <class _Se, class _It>

inline constexpr bool disable_sized_sentinel_for = false;

template <class _Se, class _It>

concept sized_sentinel_for = sentinel_for<_Se, _It>

&& !disable_sized_sentinel_for<remove_cv_t<_Se>, remove_cv_t<_It>>

&& requires(const _It& __i, const _Se& __s) {

{ __s - __i } -> same_as<iter_difference_t<_It>>;

{ __i - __s } -> same_as<iter_difference_t<_It>>;

};

template <bool _Iterator_category_present>

struct _Iter_concept_impl2 {

template <class _It, class _Traits>

using _Apply = typename _Traits::iterator_category;

};

template <>

struct _Iter_concept_impl2<false> {

// clang-format off

template <class _It, class _Traits>

requires _Is_from_primary<iterator_traits<_It>>

using _Apply = random_access_iterator_tag;

// clang-format on

};

template <bool _Iterator_concept_present>

struct _Iter_concept_impl1 {

template <class _It, class _Traits>

using _Apply = typename _Traits::iterator_concept;

};

template <>

struct _Iter_concept_impl1<false> {

template <class _It, class _Traits>

using _Apply = typename _Iter_concept_impl2<_Has_member_iterator_category<_Traits>>::template _Apply<_It, _Traits>;

};

template <class _It, class _Traits = conditional_t<_Is_from_primary<iterator_traits<_It>>, _It, iterator_traits<_It>>>

using _Iter_concept =

typename _Iter_concept_impl1<_Has_member_iterator_concept<_Traits>>::template _Apply<_It, _Traits>;

template <class _It>

concept input_iterator = input_or_output_iterator<_It> && indirectly_readable<_It>

&& requires { typename _Iter_concept<_It>; }

&& derived_from<_Iter_concept<_It>, input_iterator_tag>;

template <class _It, class _Ty>

concept output_iterator = input_or_output_iterator<_It> && indirectly_writable<_It, _Ty>

&& requires(_It __i, _Ty&& __t) {

*__i++ = static_cast<_Ty&&>(__t);

};

template <class _It>

concept forward_iterator = input_iterator<_It> && derived_from<_Iter_concept<_It>, forward_iterator_tag>

&& incrementable<_It> && sentinel_for<_It, _It>;

template <class _It>

concept bidirectional_iterator = forward_iterator<_It> && derived_from<_Iter_concept<_It>, bidirectional_iterator_tag>

&& requires(_It __i) {

{ --__i } -> same_as<_It&>;

{ __i-- } -> same_as<_It>;

};

template <class _It>

concept random_access_iterator = bidirectional_iterator<_It>

&& derived_from<_Iter_concept<_It>, random_access_iterator_tag> && totally_ordered<_It>

&& sized_sentinel_for<_It, _It> && requires(_It __i, const _It __j, const iter_difference_t<_It> __n) {

{ __i += __n } -> same_as<_It&>;

{ __j + __n } -> same_as<_It>;

{ __n + __j } -> same_as<_It>;

{ __i -= __n } -> same_as<_It&>;

{ __j - __n } -> same_as<_It>;

{ __j[__n] } -> same_as<iter_reference_t<_It>>;

};

template <class _It>

concept contiguous_iterator = random_access_iterator<_It>

&& derived_from<_Iter_concept<_It>, contiguous_iterator_tag>

&& is_lvalue_reference_v<iter_reference_t<_It>>

&& same_as<iter_value_t<_It>, remove_cvref_t<iter_reference_t<_It>>>

&& requires(const _It& __i) {

{ _STD to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_It>>>;

};

template <class _Fn, class _It>

concept indirectly_unary_invocable = indirectly_readable<_It>

&& copy_constructible<_Fn>

&& invocable<_Fn&, iter_value_t<_It>&>

&& invocable<_Fn&, iter_reference_t<_It>>

&& invocable<_Fn&, iter_common_reference_t<_It>>

&& common_reference_with<

invoke_result_t<_Fn&, iter_value_t<_It>&>,

invoke_result_t<_Fn&, iter_reference_t<_It>>>;

template <class _Fn, class _It>

concept indirectly_regular_unary_invocable = indirectly_readable<_It>

&& copy_constructible<_Fn>

&& regular_invocable<_Fn&, iter_value_t<_It>&>

&& regular_invocable<_Fn&, iter_reference_t<_It>>

&& regular_invocable<_Fn&, iter_common_reference_t<_It>>

&& common_reference_with<

invoke_result_t<_Fn&, iter_value_t<_It>&>,

invoke_result_t<_Fn&, iter_reference_t<_It>>>;

template <class _Fn, class _It>

concept indirect_unary_predicate = indirectly_readable<_It>

&& copy_constructible<_Fn>

&& predicate<_Fn&, iter_value_t<_It>&>

&& predicate<_Fn&, iter_reference_t<_It>>

&& predicate<_Fn&, iter_common_reference_t<_It>>;

template <class _Fn, class _It1, class _It2>

concept indirect_binary_predicate = indirectly_readable<_It1>

&& indirectly_readable<_It2>

&& copy_constructible<_Fn>

&& predicate<_Fn&, iter_value_t<_It1>&, iter_value_t<_It2>&>

&& predicate<_Fn&, iter_value_t<_It1>&, iter_reference_t<_It2>>

&& predicate<_Fn&, iter_reference_t<_It1>, iter_value_t<_It2>&>

&& predicate<_Fn&, iter_reference_t<_It1>, iter_reference_t<_It2>>

&& predicate<_Fn&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;

template <class _Fn, class _It1, class _It2 = _It1>

concept indirect_equivalence_relation = indirectly_readable<_It1>

&& indirectly_readable<_It2>

&& copy_constructible<_Fn>

&& equivalence_relation<_Fn&, iter_value_t<_It1>&, iter_value_t<_It2>&>

&& equivalence_relation<_Fn&, iter_value_t<_It1>&, iter_reference_t<_It2>>

&& equivalence_relation<_Fn&, iter_reference_t<_It1>, iter_value_t<_It2>&>

&& equivalence_relation<_Fn&, iter_reference_t<_It1>, iter_reference_t<_It2>>

&& equivalence_relation<_Fn&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;

template <class _Fn, class _It1, class _It2 = _It1>

concept indirect_strict_weak_order = indirectly_readable<_It1>

&& indirectly_readable<_It2>

&& copy_constructible<_Fn>

&& strict_weak_order<_Fn&, iter_value_t<_It1>&, iter_value_t<_It2>&>

&& strict_weak_order<_Fn&, iter_value_t<_It1>&, iter_reference_t<_It2>>

&& strict_weak_order<_Fn&, iter_reference_t<_It1>, iter_value_t<_It2>&>

&& strict_weak_order<_Fn&, iter_reference_t<_It1>, iter_reference_t<_It2>>

&& strict_weak_order<_Fn&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;

template <class _Fn, class... _Its>

requires (indirectly_readable<_Its> && ...)

&& invocable<_Fn, iter_reference_t<_Its>...>

using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Its>...>;

#pragma warning(push)

#pragma warning(disable : 5046) // '%s': Symbol involving type with internal linkage not defined

#ifdef __clang__

#pragma clang diagnostic push

#pragma clang diagnostic ignored "-Wundefined-internal" // function '%s' has internal linkage but is not defined

#endif // __clang__

template <indirectly_readable _It, indirectly_regular_unary_invocable<_It> _Proj>

struct projected {

using value_type = remove_cvref_t<indirect_result_t<_Proj&, _It>>;

#if defined(__clang__) || defined(__EDG__)

indirect_result_t<_Proj&, _It> operator*() const;

#else // ^^^ no workaround / workaround vvv

indirect_result_t<_Proj&, _It> operator*() const {

_CSTD abort(); // TRANSITION, VSO-1308657

}

#endif // ^^^ workaround ^^^

};

#ifdef __clang__

#pragma clang diagnostic pop

#endif // __clang__

#pragma warning(pop)

template <weakly_incrementable _It, class _Proj>

struct incrementable_traits<projected<_It, _Proj>> {

using difference_type = iter_difference_t<_It>;

};

template <class _In, class _Out>

concept indirectly_movable = indirectly_readable<_In> && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;

template <class _In, class _Out>

concept indirectly_movable_storable = indirectly_movable<_In, _Out>

&& indirectly_writable<_Out, iter_value_t<_In>>

&& movable<iter_value_t<_In>>

&& constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>

&& assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In> >;

template <class _In, class _Out>

concept indirectly_copyable = indirectly_readable<_In> && indirectly_writable<_Out, iter_reference_t<_In>>;

template <class _In, class _Out>

concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>

&& indirectly_writable<_Out, iter_value_t<_In>&>

&& indirectly_writable<_Out, const iter_value_t<_In>&>

&& indirectly_writable<_Out, iter_value_t<_In>&&>

&& indirectly_writable<_Out, const iter_value_t<_In>&&>

&& copyable<iter_value_t<_In>>

&& constructible_from<iter_value_t<_In>, iter_reference_t<_In>>

&& assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;

namespace ranges {

namespace _Iter_swap {