✏️ Editing: ranges_algo.h Read Only

// Core algorithmic facilities -*- C++ -*-

// Copyright (C) 2020-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library 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, or (at your option)
// any later version.

// This library 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file bits/ranges_algo.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{algorithm}
 */

#ifndef _RANGES_ALGO_H
#define _RANGES_ALGO_H 1

#if __cplusplus > 201703L

#include <bits/ranges_algobase.h>
#include <bits/ranges_util.h>
#include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator

#if __cpp_lib_concepts
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace ranges
{
  namespace __detail
  {
    template<typename _Comp, typename _Proj>
      constexpr auto
      __make_comp_proj(_Comp& __comp, _Proj& __proj)
      {
	return [&] (auto&& __lhs, auto&& __rhs) -> bool {
	  using _TL = decltype(__lhs);
	  using _TR = decltype(__rhs);
	  return std::__invoke(__comp,
			       std::__invoke(__proj, std::forward<_TL>(__lhs)),
			       std::__invoke(__proj, std::forward<_TR>(__rhs)));
	};
      }

template<typename _Pred, typename _Proj>
      constexpr auto
      __make_pred_proj(_Pred& __pred, _Proj& __proj)
      {
	return [&] <typename _Tp> (_Tp&& __arg) -> bool {
	  return std::__invoke(__pred,
			       std::__invoke(__proj, std::forward<_Tp>(__arg)));
	};
      }
  } // namespace __detail

struct __all_of_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    return false;
	return true;
      }

template<input_range _Range, typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      constexpr bool
      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __all_of_fn all_of{};

struct __any_of_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    return true;
	return false;
      }

inline constexpr __any_of_fn any_of{};

struct __none_of_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    return false;
	return true;
      }

inline constexpr __none_of_fn none_of{};

template<typename _Iter, typename _Fp>
    struct in_fun_result
    {
      [[no_unique_address]] _Iter in;
      [[no_unique_address]] _Fp fun;

template<typename _Iter2, typename _F2p>
	requires convertible_to<const _Iter&, _Iter2>
	  && convertible_to<const _Fp&, _F2p>
	constexpr
	operator in_fun_result<_Iter2, _F2p>() const &
	{ return {in, fun}; }

template<typename _Iter2, typename _F2p>
	requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
	constexpr
	operator in_fun_result<_Iter2, _F2p>() &&
	{ return {std::move(in), std::move(fun)}; }
    };

template<typename _Iter, typename _Fp>
    using for_each_result = in_fun_result<_Iter, _Fp>;

struct __for_each_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
      constexpr for_each_result<_Iter, _Fun>
      operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  std::__invoke(__f, std::__invoke(__proj, *__first));
	return { std::move(__first), std::move(__f) };
      }

template<input_range _Range, typename _Proj = identity,
	     indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
	       _Fun>
      constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
      operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__f), std::move(__proj));
      }
  };

inline constexpr __for_each_fn for_each{};

template<typename _Iter, typename _Fp>
    using for_each_n_result = in_fun_result<_Iter, _Fp>;

struct __for_each_n_fn
  {
    template<input_iterator _Iter, typename _Proj = identity,
	     indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
      constexpr for_each_n_result<_Iter, _Fun>
      operator()(_Iter __first, iter_difference_t<_Iter> __n,
		 _Fun __f, _Proj __proj = {}) const
      {
	if constexpr (random_access_iterator<_Iter>)
	  {
	    if (__n <= 0)
	      return {std::move(__first), std::move(__f)};
	    auto __last = __first + __n;
	    return ranges::for_each(std::move(__first), std::move(__last),
				    std::move(__f), std::move(__proj));
	  }
	else
	  {
	    while (__n-- > 0)
	      {
		std::__invoke(__f, std::__invoke(__proj, *__first));
		++__first;
	      }
	    return {std::move(__first), std::move(__f)};
	  }
      }
  };

inline constexpr __for_each_n_fn for_each_n{};

// find, find_if and find_if_not are defined in <bits/ranges_util.h>.

struct __find_first_of_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     typename _Pred = ranges::equal_to,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
      constexpr _Iter1
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	for (; __first1 != __last1; ++__first1)
	  for (auto __iter = __first2; __iter != __last2; ++__iter)
	    if (std::__invoke(__pred,
			      std::__invoke(__proj1, *__first1),
			      std::__invoke(__proj2, *__iter)))
	      return __first1;
	return __first1;
      }

template<input_range _Range1, forward_range _Range2,
	     typename _Pred = ranges::equal_to,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
				     _Pred, _Proj1, _Proj2>
      constexpr borrowed_iterator_t<_Range1>
      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__pred),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __find_first_of_fn find_first_of{};

struct __count_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity>
      requires indirect_binary_predicate<ranges::equal_to,
					 projected<_Iter, _Proj>,
					 const _Tp*>
      constexpr iter_difference_t<_Iter>
      operator()(_Iter __first, _Sent __last,
		 const _Tp& __value, _Proj __proj = {}) const
      {
	iter_difference_t<_Iter> __n = 0;
	for (; __first != __last; ++__first)
	  if (std::__invoke(__proj, *__first) == __value)
	    ++__n;
	return __n;
      }

template<input_range _Range, typename _Tp, typename _Proj = identity>
      requires indirect_binary_predicate<ranges::equal_to,
					 projected<iterator_t<_Range>, _Proj>,
					 const _Tp*>
      constexpr range_difference_t<_Range>
      operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       __value, std::move(__proj));
      }
  };

inline constexpr __count_fn count{};

struct __count_if_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr iter_difference_t<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	iter_difference_t<_Iter> __n = 0;
	for (; __first != __last; ++__first)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    ++__n;
	return __n;
      }

template<input_range _Range,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      constexpr range_difference_t<_Range>
      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __count_if_fn count_if{};

// in_in_result, mismatch and search are defined in <bits/ranges_util.h>.

struct __search_n_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
	     typename _Pred = ranges::equal_to, typename _Proj = identity>
      requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
		 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
      {
	if (__count <= 0)
	  return {__first, __first};

auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) -> bool {
	    return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
	};
	if (__count == 1)
	  {
	    __first = ranges::find_if(std::move(__first), __last,
				      std::move(__value_comp),
				      std::move(__proj));
	    if (__first == __last)
	      return {__first, __first};
	    else
	      {
		auto __end = __first;
		return {__first, ++__end};
	      }
	  }

if constexpr (sized_sentinel_for<_Sent, _Iter>
		      && random_access_iterator<_Iter>)
	  {
	    auto __tail_size = __last - __first;
	    auto __remainder = __count;

while (__remainder <= __tail_size)
	      {
		__first += __remainder;
		__tail_size -= __remainder;
		auto __backtrack = __first;
		while (__value_comp(std::__invoke(__proj, *--__backtrack)))
		  {
		    if (--__remainder == 0)
		      return {__first - __count, __first};
		  }
		__remainder = __count + 1 - (__first - __backtrack);
	      }
	    auto __i = __first + __tail_size;
	    return {__i, __i};
	  }
	else
	  {
	    __first = ranges::find_if(__first, __last, __value_comp, __proj);
	    while (__first != __last)
	      {
		auto __n = __count;
		auto __i = __first;
		++__i;
		while (__i != __last && __n != 1
		       && __value_comp(std::__invoke(__proj, *__i)))
		  {
		    ++__i;
		    --__n;
		  }
		if (__n == 1)
		  return {__first, __i};
		if (__i == __last)
		  return {__i, __i};
		__first = ranges::find_if(++__i, __last, __value_comp, __proj);
	      }
	    return {__first, __first};
	  }
      }

template<forward_range _Range, typename _Tp,
	     typename _Pred = ranges::equal_to, typename _Proj = identity>
      requires indirectly_comparable<iterator_t<_Range>, const _Tp*,
				     _Pred, _Proj>
      constexpr borrowed_subrange_t<_Range>
      operator()(_Range&& __r, range_difference_t<_Range> __count,
	       const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__count), __value,
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __search_n_fn search_n{};

struct __find_end_fn
  {
    template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     typename _Pred = ranges::equal_to,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
      constexpr subrange<_Iter1>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	if constexpr (bidirectional_iterator<_Iter1>
		      && bidirectional_iterator<_Iter2>)
	  {
	    auto __i1 = ranges::next(__first1, __last1);
	    auto __i2 = ranges::next(__first2, __last2);
	    auto __rresult
	      = ranges::search(reverse_iterator<_Iter1>{__i1},
			       reverse_iterator<_Iter1>{__first1},
			       reverse_iterator<_Iter2>{__i2},
			       reverse_iterator<_Iter2>{__first2},
			       std::move(__pred),
			       std::move(__proj1), std::move(__proj2));
	    auto __result_first = ranges::end(__rresult).base();
	    auto __result_last = ranges::begin(__rresult).base();
	    if (__result_last == __first1)
	      return {__i1, __i1};
	    else
	      return {__result_first, __result_last};
	  }
	else
	  {
	    auto __i = ranges::next(__first1, __last1);
	    if (__first2 == __last2)
	      return {__i, __i};

auto __result_begin = __i;
	    auto __result_end = __i;
	    for (;;)
	      {
		auto __new_range = ranges::search(__first1, __last1,
						  __first2, __last2,
						  __pred, __proj1, __proj2);
		auto __new_result_begin = ranges::begin(__new_range);
		auto __new_result_end = ranges::end(__new_range);
		if (__new_result_begin == __last1)
		  return {__result_begin, __result_end};
		else
		  {
		    __result_begin = __new_result_begin;
		    __result_end = __new_result_end;
		    __first1 = __result_begin;
		    ++__first1;
		  }
	      }
	  }
      }

template<forward_range _Range1, forward_range _Range2,
	     typename _Pred = ranges::equal_to,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
				     _Pred, _Proj1, _Proj2>
      constexpr borrowed_subrange_t<_Range1>
      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__pred),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __find_end_fn find_end{};

struct __adjacent_find_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_binary_predicate<projected<_Iter, _Proj>,
				       projected<_Iter, _Proj>> _Pred
	       = ranges::equal_to>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return __first;
	auto __next = __first;
	for (; ++__next != __last; __first = __next)
	  {
	    if (std::__invoke(__pred,
			      std::__invoke(__proj, *__first),
			      std::__invoke(__proj, *__next)))
	      return __first;
	  }
	return __next;
      }

template<forward_range _Range, typename _Proj = identity,
	     indirect_binary_predicate<
	       projected<iterator_t<_Range>, _Proj>,
	       projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __adjacent_find_fn adjacent_find{};

struct __is_permutation_fn
  {
    template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     typename _Proj1 = identity, typename _Proj2 = identity,
	     indirect_equivalence_relation<projected<_Iter1, _Proj1>,
					   projected<_Iter2, _Proj2>> _Pred
	       = ranges::equal_to>
      constexpr bool
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	constexpr bool __sized_iters
	  = (sized_sentinel_for<_Sent1, _Iter1>
	     && sized_sentinel_for<_Sent2, _Iter2>);
	if constexpr (__sized_iters)
	  {
	    auto __d1 = ranges::distance(__first1, __last1);
	    auto __d2 = ranges::distance(__first2, __last2);
	    if (__d1 != __d2)
	      return false;
	  }

// Efficiently compare identical prefixes:  O(N) if sequences
	// have the same elements in the same order.
	for (; __first1 != __last1 && __first2 != __last2;
	     ++__first1, (void)++__first2)
	  if (!(bool)std::__invoke(__pred,
				   std::__invoke(__proj1, *__first1),
				   std::__invoke(__proj2, *__first2)))
	      break;

if constexpr (__sized_iters)
	  {
	    if (__first1 == __last1)
	      return true;
	  }
	else
	  {
	    auto __d1 = ranges::distance(__first1, __last1);
	    auto __d2 = ranges::distance(__first2, __last2);
	    if (__d1 == 0 && __d2 == 0)
	      return true;
	    if (__d1 != __d2)
	      return false;
	  }

for (auto __scan = __first1; __scan != __last1; ++__scan)
	  {
	    auto&& __proj_scan = std::__invoke(__proj1, *__scan);
	    auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool {
	      return std::__invoke(__pred, __proj_scan,
				   std::forward<_Tp>(__arg));
	    };
	    if (__scan != ranges::find_if(__first1, __scan,
					  __comp_scan, __proj1))
	      continue; // We've seen this one before.

auto __matches = ranges::count_if(__first2, __last2,
					      __comp_scan, __proj2);
	    if (__matches == 0
		|| ranges::count_if(__scan, __last1,
				    __comp_scan, __proj1) != __matches)
	      return false;
	  }
	return true;
      }

template<forward_range _Range1, forward_range _Range2,
	     typename _Proj1 = identity, typename _Proj2 = identity,
	     indirect_equivalence_relation<
	       projected<iterator_t<_Range1>, _Proj1>,
	       projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
      constexpr bool
      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__pred),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __is_permutation_fn is_permutation{};

template<typename _Iter, typename _Out>
    using copy_if_result = in_out_result<_Iter, _Out>;

struct __copy_if_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out, typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      requires indirectly_copyable<_Iter, _Out>
      constexpr copy_if_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result,
		 _Pred __pred, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    {
	      *__result = *__first;
	      ++__result;
	    }
	return {std::move(__first), std::move(__result)};
      }

template<input_range _Range, weakly_incrementable _Out,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
      constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result,
		 _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __copy_if_fn copy_if{};

template<typename _Iter1, typename _Iter2>
    using swap_ranges_result = in_in_result<_Iter1, _Iter2>;

struct __swap_ranges_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
      requires indirectly_swappable<_Iter1, _Iter2>
      constexpr swap_ranges_result<_Iter1, _Iter2>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2) const
      {
	for (; __first1 != __last1 && __first2 != __last2;
	     ++__first1, (void)++__first2)
	  ranges::iter_swap(__first1, __first2);
	return {std::move(__first1), std::move(__first2)};
      }

template<input_range _Range1, input_range _Range2>
      requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
      constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
				   borrowed_iterator_t<_Range2>>
      operator()(_Range1&& __r1, _Range2&& __r2) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2));
      }
  };

inline constexpr __swap_ranges_fn swap_ranges{};

template<typename _Iter, typename _Out>
    using unary_transform_result = in_out_result<_Iter, _Out>;

template<typename _Iter1, typename _Iter2, typename _Out>
    struct in_in_out_result
    {
      [[no_unique_address]] _Iter1 in1;
      [[no_unique_address]] _Iter2 in2;
      [[no_unique_address]] _Out  out;

template<typename _IIter1, typename _IIter2, typename _OOut>
	requires convertible_to<const _Iter1&, _IIter1>
	  && convertible_to<const _Iter2&, _IIter2>
	  && convertible_to<const _Out&, _OOut>
	constexpr
	operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
	{ return {in1, in2, out}; }

template<typename _IIter1, typename _IIter2, typename _OOut>
	requires convertible_to<_Iter1, _IIter1>
	  && convertible_to<_Iter2, _IIter2>
	  && convertible_to<_Out, _OOut>
	constexpr
	operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
	{ return {std::move(in1), std::move(in2), std::move(out)}; }
    };

template<typename _Iter1, typename _Iter2, typename _Out>
    using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;

struct __transform_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out,
	     copy_constructible _Fp, typename _Proj = identity>
      requires indirectly_writable<_Out,
				   indirect_result_t<_Fp&,
				     projected<_Iter, _Proj>>>
      constexpr unary_transform_result<_Iter, _Out>
      operator()(_Iter __first1, _Sent __last1, _Out __result,
		 _Fp __op, _Proj __proj = {}) const
      {
	for (; __first1 != __last1; ++__first1, (void)++__result)
	  *__result = std::__invoke(__op, std::__invoke(__proj, *__first1));
	return {std::move(__first1), std::move(__result)};
      }

template<input_range _Range, weakly_incrementable _Out,
	     copy_constructible _Fp, typename _Proj = identity>
      requires indirectly_writable<_Out,
				   indirect_result_t<_Fp&,
				     projected<iterator_t<_Range>, _Proj>>>
      constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result),
		       std::move(__op), std::move(__proj));
      }

template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     weakly_incrementable _Out, copy_constructible _Fp,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_writable<_Out,
				   indirect_result_t<_Fp&,
				     projected<_Iter1, _Proj1>,
				     projected<_Iter2, _Proj2>>>
      constexpr binary_transform_result<_Iter1, _Iter2, _Out>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2,
		 _Out __result, _Fp __binary_op,
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	for (; __first1 != __last1 && __first2 != __last2;
	     ++__first1, (void)++__first2, ++__result)
	  *__result = std::__invoke(__binary_op,
				    std::__invoke(__proj1, *__first1),
				    std::__invoke(__proj2, *__first2));
	return {std::move(__first1), std::move(__first2), std::move(__result)};
      }

template<input_range _Range1, input_range _Range2,
	     weakly_incrementable _Out, copy_constructible _Fp,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_writable<_Out,
				   indirect_result_t<_Fp&,
				     projected<iterator_t<_Range1>, _Proj1>,
				     projected<iterator_t<_Range2>, _Proj2>>>
      constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
					borrowed_iterator_t<_Range2>, _Out>
      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__result), std::move(__binary_op),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __transform_fn transform{};

struct __replace_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp1, typename _Tp2, typename _Proj = identity>
      requires indirectly_writable<_Iter, const _Tp2&>
	&& indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
				     const _Tp1*>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 const _Tp1& __old_value, const _Tp2& __new_value,
		 _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (std::__invoke(__proj, *__first) == __old_value)
	    *__first = __new_value;
	return __first;
      }

template<input_range _Range,
	     typename _Tp1, typename _Tp2, typename _Proj = identity>
      requires indirectly_writable<iterator_t<_Range>, const _Tp2&>
	&& indirect_binary_predicate<ranges::equal_to,
				     projected<iterator_t<_Range>, _Proj>,
				     const _Tp1*>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r,
		 const _Tp1& __old_value, const _Tp2& __new_value,
		 _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       __old_value, __new_value, std::move(__proj));
      }
  };

inline constexpr __replace_fn replace{};

struct __replace_if_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      requires indirectly_writable<_Iter, const _Tp&>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    *__first = __new_value;
	return std::move(__first);
      }

template<input_range _Range, typename _Tp, typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires indirectly_writable<iterator_t<_Range>, const _Tp&>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r,
		 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), __new_value, std::move(__proj));
      }
  };

inline constexpr __replace_if_fn replace_if{};

template<typename _Iter, typename _Out>
    using replace_copy_result = in_out_result<_Iter, _Out>;

struct __replace_copy_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp1, typename _Tp2, output_iterator<const _Tp2&> _Out,
	     typename _Proj = identity>
      requires indirectly_copyable<_Iter, _Out>
	&& indirect_binary_predicate<ranges::equal_to,
				     projected<_Iter, _Proj>, const _Tp1*>
      constexpr replace_copy_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result,
		 const _Tp1& __old_value, const _Tp2& __new_value,
		 _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first, (void)++__result)
	  if (std::__invoke(__proj, *__first) == __old_value)
	    *__result = __new_value;
	  else
	    *__result = *__first;
	return {std::move(__first), std::move(__result)};
      }

template<input_range _Range, typename _Tp1, typename _Tp2,
	     output_iterator<const _Tp2&> _Out, typename _Proj = identity>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
	&& indirect_binary_predicate<ranges::equal_to,
				     projected<iterator_t<_Range>, _Proj>,
				     const _Tp1*>
      constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result,
		 const _Tp1& __old_value, const _Tp2& __new_value,
		 _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result), __old_value,
		       __new_value, std::move(__proj));
      }
  };

inline constexpr __replace_copy_fn replace_copy{};

template<typename _Iter, typename _Out>
    using replace_copy_if_result = in_out_result<_Iter, _Out>;

struct __replace_copy_if_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, output_iterator<const _Tp&> _Out,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      requires indirectly_copyable<_Iter, _Out>
      constexpr replace_copy_if_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result,
		 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first, (void)++__result)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    *__result = __new_value;
	  else
	    *__result = *__first;
	return {std::move(__first), std::move(__result)};
      }

template<input_range _Range,
	     typename _Tp, output_iterator<const _Tp&> _Out,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
      constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result,
		 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result), std::move(__pred),
		       __new_value, std::move(__proj));
      }
  };

inline constexpr __replace_copy_if_fn replace_copy_if{};

struct __generate_n_fn
  {
    template<input_or_output_iterator _Out, copy_constructible _Fp>
      requires invocable<_Fp&>
	&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
      constexpr _Out
      operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const
      {
	for (; __n > 0; --__n, (void)++__first)
	  *__first = std::__invoke(__gen);
	return __first;
      }
  };

inline constexpr __generate_n_fn generate_n{};

struct __generate_fn
  {
    template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
	     copy_constructible _Fp>
      requires invocable<_Fp&>
	&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
      constexpr _Out
      operator()(_Out __first, _Sent __last, _Fp __gen) const
      {
	for (; __first != __last; ++__first)
	  *__first = std::__invoke(__gen);
	return __first;
      }

template<typename _Range, copy_constructible _Fp>
      requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Fp __gen) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen));
      }
  };

inline constexpr __generate_fn generate{};

struct __remove_if_fn
  {
    template<permutable _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	__first = ranges::find_if(__first, __last, __pred, __proj);
	if (__first == __last)
	  return {__first, __first};

auto __result = __first;
	++__first;
	for (; __first != __last; ++__first)
	  if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    {
	      *__result = std::move(*__first);
	      ++__result;
	    }

return {__result, __first};
      }

template<forward_range _Range, typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires permutable<iterator_t<_Range>>
      constexpr borrowed_subrange_t<_Range>
      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __remove_if_fn remove_if{};

struct __remove_fn
  {
    template<permutable _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity>
      requires indirect_binary_predicate<ranges::equal_to,
					 projected<_Iter, _Proj>,
					 const _Tp*>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Sent __last,
		 const _Tp& __value, _Proj __proj = {}) const
      {
	auto __pred = [&] (auto&& __arg) -> bool {
	  return std::forward<decltype(__arg)>(__arg) == __value;
	};
	return ranges::remove_if(__first, __last,
				 std::move(__pred), std::move(__proj));
      }

template<forward_range _Range, typename _Tp, typename _Proj = identity>
      requires permutable<iterator_t<_Range>>
	&& indirect_binary_predicate<ranges::equal_to,
				     projected<iterator_t<_Range>, _Proj>,
				     const _Tp*>
      constexpr borrowed_subrange_t<_Range>
      operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       __value, std::move(__proj));
      }
  };

inline constexpr __remove_fn remove{};

template<typename _Iter, typename _Out>
    using remove_copy_if_result = in_out_result<_Iter, _Out>;

struct __remove_copy_if_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out, typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      requires indirectly_copyable<_Iter, _Out>
      constexpr remove_copy_if_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result,
		 _Pred __pred, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    {
	      *__result = *__first;
	      ++__result;
	    }
	return {std::move(__first), std::move(__result)};
      }

template<input_range _Range, weakly_incrementable _Out,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
      constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result,
		 _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __remove_copy_if_fn remove_copy_if{};

template<typename _Iter, typename _Out>
    using remove_copy_result = in_out_result<_Iter, _Out>;

struct __remove_copy_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out, typename _Tp, typename _Proj = identity>
      requires indirectly_copyable<_Iter, _Out>
	&& indirect_binary_predicate<ranges::equal_to,
				     projected<_Iter, _Proj>,
				     const _Tp*>
      constexpr remove_copy_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result,
		 const _Tp& __value, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (!(std::__invoke(__proj, *__first) == __value))
	    {
	      *__result = *__first;
	      ++__result;
	    }
	return {std::move(__first), std::move(__result)};
      }

template<input_range _Range, weakly_incrementable _Out,
	     typename _Tp, typename _Proj = identity>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
	&& indirect_binary_predicate<ranges::equal_to,
				     projected<iterator_t<_Range>, _Proj>,
				     const _Tp*>
      constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result,
		 const _Tp& __value, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result), __value, std::move(__proj));
      }
  };

inline constexpr __remove_copy_fn remove_copy{};

struct __unique_fn
  {
    template<permutable _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_equivalence_relation<
	       projected<_Iter, _Proj>> _Comp = ranges::equal_to>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	__first = ranges::adjacent_find(__first, __last, __comp, __proj);
	if (__first == __last)
	  return {__first, __first};

auto __dest = __first;
	++__first;
	while (++__first != __last)
	  if (!std::__invoke(__comp,
			     std::__invoke(__proj, *__dest),
			     std::__invoke(__proj, *__first)))
	    *++__dest = std::move(*__first);
	return {++__dest, __first};
      }

template<forward_range _Range, typename _Proj = identity,
	     indirect_equivalence_relation<
	       projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
      requires permutable<iterator_t<_Range>>
      constexpr borrowed_subrange_t<_Range>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __unique_fn unique{};

namespace __detail
  {
    template<typename _Out, typename _Tp>
      concept __can_reread_output = input_iterator<_Out>
	&& same_as<_Tp, iter_value_t<_Out>>;
  }

template<typename _Iter, typename _Out>
    using unique_copy_result = in_out_result<_Iter, _Out>;

struct __unique_copy_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out, typename _Proj = identity,
	     indirect_equivalence_relation<
	       projected<_Iter, _Proj>> _Comp = ranges::equal_to>
      requires indirectly_copyable<_Iter, _Out>
	&& (forward_iterator<_Iter>
	    || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
	    || indirectly_copyable_storable<_Iter, _Out>)
      constexpr unique_copy_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return {std::move(__first), std::move(__result)};

// TODO: perform a closer comparison with reference implementations
	if constexpr (forward_iterator<_Iter>)
	  {
	    auto __next = __first;
	    *__result = *__next;
	    while (++__next != __last)
	      if (!std::__invoke(__comp,
				 std::__invoke(__proj, *__first),
				 std::__invoke(__proj, *__next)))
		{
		  __first = __next;
		  *++__result = *__first;
		}
	    return {__next, std::move(++__result)};
	  }
	else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
	  {
	    *__result = *__first;
	    while (++__first != __last)
	      if (!std::__invoke(__comp,
				 std::__invoke(__proj, *__result),
				 std::__invoke(__proj, *__first)))
		  *++__result = *__first;
	    return {std::move(__first), std::move(++__result)};
	  }
	else // indirectly_copyable_storable<_Iter, _Out>
	  {
	    auto __value = *__first;
	    *__result = __value;
	    while (++__first != __last)
	      {
		if (!(bool)std::__invoke(__comp,
					 std::__invoke(__proj, *__first),
					 std::__invoke(__proj, __value)))
		  {
		    __value = *__first;
		    *++__result = __value;
		  }
	      }
	    return {std::move(__first), std::move(++__result)};
	  }
      }

template<input_range _Range,
	     weakly_incrementable _Out, typename _Proj = identity,
	     indirect_equivalence_relation<
	       projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
	&& (forward_iterator<iterator_t<_Range>>
	    || __detail::__can_reread_output<_Out, range_value_t<_Range>>
	    || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
      constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __unique_copy_fn unique_copy{};

struct __reverse_fn
  {
    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
      requires permutable<_Iter>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last) const
      {
	auto __i = ranges::next(__first, __last);
	auto __tail = __i;

if constexpr (random_access_iterator<_Iter>)
	  {
	    if (__first != __last)
	      {
		--__tail;
		while (__first < __tail)
		  {
		    ranges::iter_swap(__first, __tail);
		    ++__first;
		    --__tail;
		  }
	      }
	    return __i;
	  }
	else
	  {
	    for (;;)
	      if (__first == __tail || __first == --__tail)
		break;
	      else
		{
		  ranges::iter_swap(__first, __tail);
		  ++__first;
		}
	    return __i;
	  }
      }

template<bidirectional_range _Range>
      requires permutable<iterator_t<_Range>>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r));
      }
  };

inline constexpr __reverse_fn reverse{};

template<typename _Iter, typename _Out>
    using reverse_copy_result = in_out_result<_Iter, _Out>;

struct __reverse_copy_fn
  {
    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out>
      requires indirectly_copyable<_Iter, _Out>
      constexpr reverse_copy_result<_Iter, _Out>
      operator()(_Iter __first, _Sent __last, _Out __result) const
      {
	auto __i = ranges::next(__first, __last);
	auto __tail = __i;
	while (__first != __tail)
	  {
	    --__tail;
	    *__result = *__tail;
	    ++__result;
	  }
	return {__i, std::move(__result)};
      }

template<bidirectional_range _Range, weakly_incrementable _Out>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
      constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, _Out __result) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__result));
      }
  };

inline constexpr __reverse_copy_fn reverse_copy{};

struct __rotate_fn
  {
    template<permutable _Iter, sentinel_for<_Iter> _Sent>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Iter __middle, _Sent __last) const
      {
	auto __lasti = ranges::next(__first, __last);
	if (__first == __middle)
	  return {__lasti, __lasti};
	if (__last == __middle)
	  return {std::move(__first), std::move(__lasti)};

if constexpr (random_access_iterator<_Iter>)
	  {
	    auto __n = __lasti - __first;
	    auto __k = __middle - __first;

if (__k == __n - __k)
	      {
		ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
		return {std::move(__middle), std::move(__lasti)};
	      }

auto __p = __first;
	    auto __ret = __first + (__lasti - __middle);

for (;;)
	      {
		if (__k < __n - __k)
		  {
		    // TODO: is_pod is deprecated, but this condition is
		    // consistent with the STL implementation.
		    if constexpr (__is_pod(iter_value_t<_Iter>))
		      if (__k == 1)
			{
			  auto __t = std::move(*__p);
			  ranges::move(__p + 1, __p + __n, __p);
			  *(__p + __n - 1) = std::move(__t);
			  return {std::move(__ret), std::move(__lasti)};
			}
		    auto __q = __p + __k;
		    for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
		      {
			ranges::iter_swap(__p, __q);
			++__p;
			++__q;
		      }
		    __n %= __k;
		    if (__n == 0)
		      return {std::move(__ret), std::move(__lasti)};
		    ranges::swap(__n, __k);
		    __k = __n - __k;
		  }
		else
		  {
		    __k = __n - __k;
		    // TODO: is_pod is deprecated, but this condition is
		    // consistent with the STL implementation.
		    if constexpr (__is_pod(iter_value_t<_Iter>))
		      if (__k == 1)
			{
			  auto __t = std::move(*(__p + __n - 1));
			  ranges::move_backward(__p, __p + __n - 1, __p + __n);
			  *__p = std::move(__t);
			  return {std::move(__ret), std::move(__lasti)};
			}
		    auto __q = __p + __n;
		    __p = __q - __k;
		    for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
		      {
			--__p;
			--__q;
			ranges::iter_swap(__p, __q);
		      }
		    __n %= __k;
		    if (__n == 0)
		      return {std::move(__ret), std::move(__lasti)};
		    std::swap(__n, __k);
		  }
	      }
	  }
	else if constexpr (bidirectional_iterator<_Iter>)
	  {
	    auto __tail = __lasti;

ranges::reverse(__first, __middle);
	    ranges::reverse(__middle, __tail);

while (__first != __middle && __middle != __tail)
	      {
		ranges::iter_swap(__first, --__tail);
		++__first;
	      }

if (__first == __middle)
	      {
		ranges::reverse(__middle, __tail);
		return {std::move(__tail), std::move(__lasti)};
	      }
	    else
	      {
		ranges::reverse(__first, __middle);
		return {std::move(__first), std::move(__lasti)};
	      }
	  }
	else
	  {
	    auto __first2 = __middle;
	    do
	      {
		ranges::iter_swap(__first, __first2);
		++__first;
		++__first2;
		if (__first == __middle)
		  __middle = __first2;
	      } while (__first2 != __last);

auto __ret = __first;

__first2 = __middle;

while (__first2 != __last)
	      {
		ranges::iter_swap(__first, __first2);
		++__first;
		++__first2;
		if (__first == __middle)
		  __middle = __first2;
		else if (__first2 == __last)
		  __first2 = __middle;
	      }
	    return {std::move(__ret), std::move(__lasti)};
	  }
      }

template<forward_range _Range>
      requires permutable<iterator_t<_Range>>
      constexpr borrowed_subrange_t<_Range>
      operator()(_Range&& __r, iterator_t<_Range> __middle) const
      {
	return (*this)(ranges::begin(__r), std::move(__middle),
		       ranges::end(__r));
      }
  };

inline constexpr __rotate_fn rotate{};

template<typename _Iter, typename _Out>
    using rotate_copy_result = in_out_result<_Iter, _Out>;

struct __rotate_copy_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out>
      requires indirectly_copyable<_Iter, _Out>
      constexpr rotate_copy_result<_Iter, _Out>
      operator()(_Iter __first, _Iter __middle, _Sent __last,
		 _Out __result) const
      {
	auto __copy1 = ranges::copy(__middle,
				    std::move(__last),
				    std::move(__result));
	auto __copy2 = ranges::copy(std::move(__first),
				    std::move(__middle),
				    std::move(__copy1.out));
	return { std::move(__copy1.in), std::move(__copy2.out) };
      }

template<forward_range _Range, weakly_incrementable _Out>
      requires indirectly_copyable<iterator_t<_Range>, _Out>
      constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
      operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
      {
	return (*this)(ranges::begin(__r), std::move(__middle),
		       ranges::end(__r), std::move(__result));
      }
  };

inline constexpr __rotate_copy_fn rotate_copy{};

struct __sample_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out, typename _Gen>
      requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
	&& indirectly_copyable<_Iter, _Out>
	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
      _Out
      operator()(_Iter __first, _Sent __last, _Out __out,
		 iter_difference_t<_Iter> __n, _Gen&& __g) const
      {
	if constexpr (forward_iterator<_Iter>)
	  {
	    // FIXME: Forwarding to std::sample here requires computing __lasti
	    // which may take linear time.
	    auto __lasti = ranges::next(__first, __last);
	    return _GLIBCXX_STD_A::
	      sample(std::move(__first), std::move(__lasti), std::move(__out),
		     __n, std::forward<_Gen>(__g));
	  }
	else
	  {
	    using __distrib_type
	      = uniform_int_distribution<iter_difference_t<_Iter>>;
	    using __param_type = typename __distrib_type::param_type;
	    __distrib_type __d{};
	    iter_difference_t<_Iter> __sample_sz = 0;
	    while (__first != __last && __sample_sz != __n)
	      {
		__out[__sample_sz++] = *__first;
		++__first;
	      }
	    for (auto __pop_sz = __sample_sz; __first != __last;
		++__first, (void) ++__pop_sz)
	      {
		const auto __k = __d(__g, __param_type{0, __pop_sz});
		if (__k < __n)
		  __out[__k] = *__first;
	      }
	    return __out + __sample_sz;
	  }
      }

template<input_range _Range, weakly_incrementable _Out, typename _Gen>
      requires (forward_range<_Range> || random_access_iterator<_Out>)
	&& indirectly_copyable<iterator_t<_Range>, _Out>
	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
      _Out
      operator()(_Range&& __r, _Out __out,
		 range_difference_t<_Range> __n, _Gen&& __g) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__out), __n,
		       std::forward<_Gen>(__g));
      }
  };

inline constexpr __sample_fn sample{};

#ifdef _GLIBCXX_USE_C99_STDINT_TR1
  struct __shuffle_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Gen>
      requires permutable<_Iter>
	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
      _Iter
      operator()(_Iter __first, _Sent __last, _Gen&& __g) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g));
	return __lasti;
      }

template<random_access_range _Range, typename _Gen>
      requires permutable<iterator_t<_Range>>
	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
      borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Gen&& __g) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::forward<_Gen>(__g));
      }
  };

inline constexpr __shuffle_fn shuffle{};
#endif

struct __push_heap_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::push_heap(__first, __lasti,
		       __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

template<random_access_range _Range,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __push_heap_fn push_heap{};

struct __pop_heap_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::pop_heap(__first, __lasti,
		      __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

inline constexpr __pop_heap_fn pop_heap{};

struct __make_heap_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::make_heap(__first, __lasti,
		       __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

inline constexpr __make_heap_fn make_heap{};

struct __sort_heap_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::sort_heap(__first, __lasti,
		       __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

inline constexpr __sort_heap_fn sort_heap{};

struct __is_heap_until_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
	iter_difference_t<_Iter> __parent = 0, __child = 1;
	for (; __child < __n; ++__child)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj, *(__first + __parent)),
			    std::__invoke(__proj, *(__first + __child))))
	    return __first + __child;
	  else if ((__child & 1) == 0)
	    ++__parent;

return __first + __n;
      }

template<random_access_range _Range,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __is_heap_until_fn is_heap_until{};

struct __is_heap_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (__last
		== ranges::is_heap_until(__first, __last,
					 std::move(__comp),
					 std::move(__proj)));
      }

template<random_access_range _Range,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __is_heap_fn is_heap{};

struct __sort_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	_GLIBCXX_STD_A::sort(std::move(__first), __lasti,
			     __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

inline constexpr __sort_fn sort{};

struct __stable_sort_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::stable_sort(std::move(__first), __lasti,
			 __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

template<random_access_range _Range,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __stable_sort_fn stable_sort{};

struct __partial_sort_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Iter __middle, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __middle)
	  return ranges::next(__first, __last);

ranges::make_heap(__first, __middle, __comp, __proj);
	auto __i = __middle;
	for (; __i != __last; ++__i)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj, *__i),
			    std::__invoke(__proj, *__first)))
	    {
	      ranges::pop_heap(__first, __middle, __comp, __proj);
	      ranges::iter_swap(__middle-1, __i);
	      ranges::push_heap(__first, __middle, __comp, __proj);
	    }
	ranges::sort_heap(__first, __middle, __comp, __proj);

return __i;
      }

template<random_access_range _Range,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, iterator_t<_Range> __middle,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), std::move(__middle),
		       ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __partial_sort_fn partial_sort{};

template<typename _Iter, typename _Out>
    using partial_sort_copy_result = in_out_result<_Iter, _Out>;

struct __partial_sort_copy_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_copyable<_Iter1, _Iter2>
	&& sortable<_Iter2, _Comp, _Proj2>
	&& indirect_strict_weak_order<_Comp,
				      projected<_Iter1, _Proj1>,
				      projected<_Iter2, _Proj2>>
      constexpr partial_sort_copy_result<_Iter1, _Iter2>
      operator()(_Iter1 __first, _Sent1 __last,
		 _Iter2 __result_first, _Sent2 __result_last,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	if (__result_first == __result_last)
	  {
	    // TODO: Eliminating the variable __lasti triggers an ICE.
	    auto __lasti = ranges::next(std::move(__first),
					std::move(__last));
	    return {std::move(__lasti), std::move(__result_first)};
	  }

auto __result_real_last = __result_first;
	while (__first != __last && __result_real_last != __result_last)
	  {
	    *__result_real_last = *__first;
	    ++__result_real_last;
	    ++__first;
	  }

ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
	for (; __first != __last; ++__first)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj1, *__first),
			    std::__invoke(__proj2, *__result_first)))
	    {
	      ranges::pop_heap(__result_first, __result_real_last,
			       __comp, __proj2);
	      *(__result_real_last-1) = *__first;
	      ranges::push_heap(__result_first, __result_real_last,
				__comp, __proj2);
	    }
	ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);

return {std::move(__first), std::move(__result_real_last)};
      }

template<input_range _Range1, random_access_range _Range2,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
	&& sortable<iterator_t<_Range2>, _Comp, _Proj2>
	&& indirect_strict_weak_order<_Comp,
				      projected<iterator_t<_Range1>, _Proj1>,
				      projected<iterator_t<_Range2>, _Proj2>>
      constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
					 borrowed_iterator_t<_Range2>>
      operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       ranges::begin(__out), ranges::end(__out),
		       std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __partial_sort_copy_fn partial_sort_copy{};

struct __is_sorted_until_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return __first;

auto __next = __first;
	for (++__next; __next != __last; __first = __next, (void)++__next)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj, *__next),
			    std::__invoke(__proj, *__first)))
	    return __next;
	return __next;
      }

template<forward_range _Range, typename _Proj = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __is_sorted_until_fn is_sorted_until{};

struct __is_sorted_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return true;

template<forward_range _Range, typename _Proj = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __is_sorted_fn is_sorted{};

struct __nth_element_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Iter __nth, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	_GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth),
				    __lasti,
				    __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

template<random_access_range _Range,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, iterator_t<_Range> __nth,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), std::move(__nth),
		       ranges::end(__r), std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __nth_element_fn nth_element{};

struct __lower_bound_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __len = ranges::distance(__first, __last);

template<forward_range _Range, typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*,
					projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r,
		 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       __value, std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __lower_bound_fn lower_bound{};

struct __upper_bound_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __len = ranges::distance(__first, __last);

while (__len > 0)
	  {
	    auto __half = __len / 2;
	    auto __middle = __first;
	    ranges::advance(__middle, __half);
	    if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
	      __len = __half;
	    else
	      {
		__first = __middle;
		++__first;
		__len = __len - __half - 1;
	      }
	  }
	return __first;
      }

inline constexpr __upper_bound_fn upper_bound{};

struct __equal_range_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Sent __last,
		 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __len = ranges::distance(__first, __last);

while (__len > 0)
	  {
	    auto __half = __len / 2;
	    auto __middle = __first;
	    ranges::advance(__middle, __half);
	    if (std::__invoke(__comp,
			      std::__invoke(__proj, *__middle),
			      __value))
	      {
		__first = __middle;
		++__first;
		__len = __len - __half - 1;
	      }
	    else if (std::__invoke(__comp,
				   __value,
				   std::__invoke(__proj, *__middle)))
	      __len = __half;
	    else
	      {
		auto __left
		  = ranges::lower_bound(__first, __middle,
					__value, __comp, __proj);
		ranges::advance(__first, __len);
		auto __right
		  = ranges::upper_bound(++__middle, __first,
					__value, __comp, __proj);
		return {__left, __right};
	      }
	  }
	return {__first, __first};
      }

template<forward_range _Range,
	     typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*,
					projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr borrowed_subrange_t<_Range>
      operator()(_Range&& __r, const _Tp& __value,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       __value, std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __equal_range_fn equal_range{};

struct __binary_search_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
	if (__i == __last)
	  return false;
	return !(bool)std::__invoke(__comp, __value,
				    std::__invoke(__proj, *__i));
      }

template<forward_range _Range,
	     typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<const _Tp*,
					projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {},
		 _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       __value, std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __binary_search_fn binary_search{};

struct __is_partitioned_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr bool
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	__first = ranges::find_if_not(std::move(__first), __last,
				      __pred, __proj);
	if (__first == __last)
	  return true;
	++__first;
	return ranges::none_of(std::move(__first), std::move(__last),
			       std::move(__pred), std::move(__proj));
      }

inline constexpr __is_partitioned_fn is_partitioned{};

struct __partition_fn
  {
    template<permutable _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr subrange<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	if constexpr (bidirectional_iterator<_Iter>)
	  {
	    auto __lasti = ranges::next(__first, __last);
	    auto __tail = __lasti;
	    for (;;)
	      {
		for (;;)
		  if (__first == __tail)
		    return {std::move(__first), std::move(__lasti)};
		  else if (std::__invoke(__pred,
					 std::__invoke(__proj, *__first)))
		    ++__first;
		  else
		    break;
		--__tail;
		for (;;)
		  if (__first == __tail)
		    return {std::move(__first), std::move(__lasti)};
		  else if (!(bool)std::__invoke(__pred,
						std::__invoke(__proj, *__tail)))
		    --__tail;
		  else
		    break;
		ranges::iter_swap(__first, __tail);
		++__first;
	      }
	  }
	else
	  {
	    if (__first == __last)
	      return {__first, __first};

while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	      if (++__first == __last)
		return {__first, __first};

auto __next = __first;
	    while (++__next != __last)
	      if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
		{
		  ranges::iter_swap(__first, __next);
		  ++__first;
		}

return {std::move(__first), std::move(__next)};
	  }
      }

inline constexpr __partition_fn partition{};

struct __stable_partition_fn
  {
    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      requires permutable<_Iter>
      subrange<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	auto __middle
	  = std::stable_partition(std::move(__first), __lasti,
				  __detail::__make_pred_proj(__pred, __proj));
	return {std::move(__middle), std::move(__lasti)};
      }

template<bidirectional_range _Range, typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires permutable<iterator_t<_Range>>
      borrowed_subrange_t<_Range>
      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __stable_partition_fn stable_partition{};

template<typename _Iter, typename _Out1, typename _Out2>
    struct in_out_out_result
    {
      [[no_unique_address]] _Iter  in;
      [[no_unique_address]] _Out1 out1;
      [[no_unique_address]] _Out2 out2;

template<typename _IIter, typename _OOut1, typename _OOut2>
	requires convertible_to<const _Iter&, _IIter>
	  && convertible_to<const _Out1&, _OOut1>
	  && convertible_to<const _Out2&, _OOut2>
	constexpr
	operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
	{ return {in, out1, out2}; }

template<typename _IIter, typename _OOut1, typename _OOut2>
	requires convertible_to<_Iter, _IIter>
	  && convertible_to<_Out1, _OOut1>
	  && convertible_to<_Out2, _OOut2>
	constexpr
	operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
	{ return {std::move(in), std::move(out1), std::move(out2)}; }
    };

template<typename _Iter, typename _Out1, typename _Out2>
    using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;

struct __partition_copy_fn
  {
    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
	     weakly_incrementable _Out1, weakly_incrementable _Out2,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      requires indirectly_copyable<_Iter, _Out1>
	&& indirectly_copyable<_Iter, _Out2>
      constexpr partition_copy_result<_Iter, _Out1, _Out2>
      operator()(_Iter __first, _Sent __last,
		 _Out1 __out_true, _Out2 __out_false,
		 _Pred __pred, _Proj __proj = {}) const
      {
	for (; __first != __last; ++__first)
	  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
	    {
	      *__out_true = *__first;
	      ++__out_true;
	    }
	  else
	    {
	      *__out_false = *__first;
	      ++__out_false;
	    }

return {std::move(__first),
		std::move(__out_true), std::move(__out_false)};
      }

template<input_range _Range, weakly_incrementable _Out1,
	     weakly_incrementable _Out2,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      requires indirectly_copyable<iterator_t<_Range>, _Out1>
	&& indirectly_copyable<iterator_t<_Range>, _Out2>
      constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
      operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
		 _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__out_true), std::move(__out_false),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __partition_copy_fn partition_copy{};

struct __partition_point_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Pred __pred, _Proj __proj = {}) const
      {
	auto __len = ranges::distance(__first, __last);

while (__len > 0)
	  {
	    auto __half = __len / 2;
	    auto __middle = __first;
	    ranges::advance(__middle, __half);
	    if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
	      {
		__first = __middle;
		++__first;
		__len = __len - __half - 1;
	      }
	    else
	      __len = __half;
	  }
	return __first;
      }

template<forward_range _Range, typename _Proj = identity,
	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
	       _Pred>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__pred), std::move(__proj));
      }
  };

inline constexpr __partition_point_fn partition_point{};

template<typename _Iter1, typename _Iter2, typename _Out>
    using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;

struct __merge_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     weakly_incrementable _Out, typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
      constexpr merge_result<_Iter1, _Iter2, _Out>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	while (__first1 != __last1 && __first2 != __last2)
	  {
	    if (std::__invoke(__comp,
			      std::__invoke(__proj2, *__first2),
			      std::__invoke(__proj1, *__first1)))
	      {
		*__result = *__first2;
		++__first2;
	      }
	    else
	      {
		*__result = *__first1;
		++__first1;
	      }
	    ++__result;
	  }
	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
				    std::move(__result));
	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
				    std::move(__copy1.out));
	return { std::move(__copy1.in), std::move(__copy2.in),
		 std::move(__copy2.out) };
      }

template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
			 _Comp, _Proj1, _Proj2>
      constexpr merge_result<borrowed_iterator_t<_Range1>,
			     borrowed_iterator_t<_Range2>,
			     _Out>
      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__result), std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __merge_fn merge{};

struct __inplace_merge_fn
  {
    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less,
	     typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      _Iter
      operator()(_Iter __first, _Iter __middle, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __lasti = ranges::next(__first, __last);
	std::inplace_merge(std::move(__first), std::move(__middle), __lasti,
			   __detail::__make_comp_proj(__comp, __proj));
	return __lasti;
      }

template<bidirectional_range _Range,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      borrowed_iterator_t<_Range>
      operator()(_Range&& __r, iterator_t<_Range> __middle,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), std::move(__middle),
		       ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __inplace_merge_fn inplace_merge{};

struct __includes_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     typename _Proj1 = identity, typename _Proj2 = identity,
	     indirect_strict_weak_order<projected<_Iter1, _Proj1>,
					projected<_Iter2, _Proj2>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	while (__first1 != __last1 && __first2 != __last2)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj2, *__first2),
			    std::__invoke(__proj1, *__first1)))
	    return false;
	  else if (std::__invoke(__comp,
				 std::__invoke(__proj1, *__first1),
				 std::__invoke(__proj2, *__first2)))
	    ++__first1;
	  else
	    {
	      ++__first1;
	      ++__first2;
	    }

return __first2 == __last2;
      }

template<input_range _Range1, input_range _Range2,
	     typename _Proj1 = identity, typename _Proj2 = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
					projected<iterator_t<_Range2>, _Proj2>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __includes_fn includes{};

template<typename _Iter1, typename _Iter2, typename _Out>
    using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;

struct __set_union_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     weakly_incrementable _Out, typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
      constexpr set_union_result<_Iter1, _Iter2, _Out>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2,
		 _Out __result, _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	while (__first1 != __last1 && __first2 != __last2)
	  {
	    if (std::__invoke(__comp,
			      std::__invoke(__proj1, *__first1),
			      std::__invoke(__proj2, *__first2)))
	      {
		*__result = *__first1;
		++__first1;
	      }
	    else if (std::__invoke(__comp,
				   std::__invoke(__proj2, *__first2),
				   std::__invoke(__proj1, *__first1)))
	      {
		*__result = *__first2;
		++__first2;
	      }
	    else
	      {
		*__result = *__first1;
		++__first1;
		++__first2;
	      }
	    ++__result;
	  }
	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
				    std::move(__result));
	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
				    std::move(__copy1.out));
	return {std::move(__copy1.in), std::move(__copy2.in),
		std::move(__copy2.out)};
      }

template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
			 _Comp, _Proj1, _Proj2>
      constexpr set_union_result<borrowed_iterator_t<_Range1>,
				 borrowed_iterator_t<_Range2>, _Out>
      operator()(_Range1&& __r1, _Range2&& __r2,
		 _Out __result, _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__result), std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __set_union_fn set_union{};

template<typename _Iter1, typename _Iter2, typename _Out>
    using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;

struct __set_intersection_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     weakly_incrementable _Out, typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
      constexpr set_intersection_result<_Iter1, _Iter2, _Out>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	while (__first1 != __last1 && __first2 != __last2)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj1, *__first1),
			    std::__invoke(__proj2, *__first2)))
	    ++__first1;
	  else if (std::__invoke(__comp,
				 std::__invoke(__proj2, *__first2),
				 std::__invoke(__proj1, *__first1)))
	    ++__first2;
	  else
	    {
	      *__result = *__first1;
	      ++__first1;
	      ++__first2;
	      ++__result;
	    }
	// TODO: Eliminating these variables triggers an ICE.
	auto __last1i = ranges::next(std::move(__first1), std::move(__last1));
	auto __last2i = ranges::next(std::move(__first2), std::move(__last2));
	return {std::move(__last1i), std::move(__last2i), std::move(__result)};
      }

template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
			 _Comp, _Proj1, _Proj2>
      constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
					borrowed_iterator_t<_Range2>, _Out>
      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__result), std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __set_intersection_fn set_intersection{};

template<typename _Iter, typename _Out>
    using set_difference_result = in_out_result<_Iter, _Out>;

struct __set_difference_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     weakly_incrementable _Out, typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
      constexpr set_difference_result<_Iter1, _Out>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	while (__first1 != __last1 && __first2 != __last2)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj1, *__first1),
			    std::__invoke(__proj2, *__first2)))
	    {
	      *__result = *__first1;
	      ++__first1;
	      ++__result;
	    }
	  else if (std::__invoke(__comp,
				 std::__invoke(__proj2, *__first2),
				 std::__invoke(__proj1, *__first1)))
	    ++__first2;
	  else
	    {
	      ++__first1;
	      ++__first2;
	    }
	return ranges::copy(std::move(__first1), std::move(__last1),
			    std::move(__result));
      }

template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
			 _Comp, _Proj1, _Proj2>
      constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__result), std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __set_difference_fn set_difference{};

template<typename _Iter1, typename _Iter2, typename _Out>
    using set_symmetric_difference_result
      = in_in_out_result<_Iter1, _Iter2, _Out>;

struct __set_symmetric_difference_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     weakly_incrementable _Out, typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
      constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2,
		 _Out __result, _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	while (__first1 != __last1 && __first2 != __last2)
	  if (std::__invoke(__comp,
			    std::__invoke(__proj1, *__first1),
			    std::__invoke(__proj2, *__first2)))
	    {
	      *__result = *__first1;
	      ++__first1;
	      ++__result;
	    }
	  else if (std::__invoke(__comp,
				 std::__invoke(__proj2, *__first2),
				 std::__invoke(__proj1, *__first1)))
	    {
	      *__result = *__first2;
	      ++__first2;
	      ++__result;
	    }
	  else
	    {
	      ++__first1;
	      ++__first2;
	    }
	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
				    std::move(__result));
	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
				    std::move(__copy1.out));
	return {std::move(__copy1.in), std::move(__copy2.in),
		std::move(__copy2.out)};
      }

template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
	     typename _Comp = ranges::less,
	     typename _Proj1 = identity, typename _Proj2 = identity>
      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
			 _Comp, _Proj1, _Proj2>
      constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
						borrowed_iterator_t<_Range2>,
						_Out>
      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	return (*this)(ranges::begin(__r1), ranges::end(__r1),
		       ranges::begin(__r2), ranges::end(__r2),
		       std::move(__result), std::move(__comp),
		       std::move(__proj1), std::move(__proj2));
      }
  };

inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};

struct __min_fn
  {
    template<typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
	       _Comp = ranges::less>
      constexpr const _Tp&
      operator()(const _Tp& __a, const _Tp& __b,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (std::__invoke(__comp,
			  std::__invoke(__proj, __b),
			  std::__invoke(__proj, __a)))
	  return __b;
	else
	  return __a;
      }

template<copyable _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
	       _Comp = ranges::less>
      constexpr _Tp
      operator()(initializer_list<_Tp> __r,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::subrange(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __min_fn min{};

struct __max_fn
  {
    template<typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
	       _Comp = ranges::less>
      constexpr const _Tp&
      operator()(const _Tp& __a, const _Tp& __b,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (std::__invoke(__comp,
			  std::__invoke(__proj, __a),
			  std::__invoke(__proj, __b)))
	  return __b;
	else
	  return __a;
      }

inline constexpr __max_fn max{};

struct __clamp_fn
  {
    template<typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
	       = ranges::less>
      constexpr const _Tp&
      operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	__glibcxx_assert(!(std::__invoke(__comp,
					 std::__invoke(__proj, __hi),
					 std::__invoke(__proj, __lo))));
	auto&& __proj_val = std::__invoke(__proj, __val);
	if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
	  return __lo;
	else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
	  return __hi;
	else
	  return __val;
      }
  };

inline constexpr __clamp_fn clamp{};

template<typename _Tp>
    struct min_max_result
    {
      [[no_unique_address]] _Tp min;
      [[no_unique_address]] _Tp max;

template<typename _Tp2>
	requires convertible_to<const _Tp&, _Tp2>
	constexpr
	operator min_max_result<_Tp2>() const &
	{ return {min, max}; }

template<typename _Tp2>
	requires convertible_to<_Tp, _Tp2>
	constexpr
	operator min_max_result<_Tp2>() &&
	{ return {std::move(min), std::move(max)}; }
    };

template<typename _Tp>
    using minmax_result = min_max_result<_Tp>;

struct __minmax_fn
  {
    template<typename _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
	       _Comp = ranges::less>
      constexpr minmax_result<const _Tp&>
      operator()(const _Tp& __a, const _Tp& __b,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (std::__invoke(__comp,
			  std::__invoke(__proj, __b),
			  std::__invoke(__proj, __a)))
	  return {__b, __a};
	else
	  return {__a, __b};
      }

template<input_range _Range, typename _Proj = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
      constexpr minmax_result<range_value_t<_Range>>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __first = ranges::begin(__r);
	auto __last = ranges::end(__r);
	__glibcxx_assert(__first != __last);
	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
	minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
	if (++__first == __last)
	  return __result;
	else
	  {
	    // At this point __result.min == __result.max, so a single
	    // comparison with the next element suffices.
	    auto&& __val = *__first;
	    if (__comp_proj(__val, __result.min))
	      __result.min = std::forward<decltype(__val)>(__val);
	    else
	      __result.max = std::forward<decltype(__val)>(__val);
	  }
	while (++__first != __last)
	  {
	    // Now process two elements at a time so that we perform at most
	    // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
	    // iterations of this loop performs three comparisons).
	    range_value_t<_Range> __val1 = *__first;
	    if (++__first == __last)
	      {
		// N is odd; in this final iteration, we perform at most two
		// comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
		// which is not more than 3*N/2, as required.
		if (__comp_proj(__val1, __result.min))
		  __result.min = std::move(__val1);
		else if (!__comp_proj(__val1, __result.max))
		  __result.max = std::move(__val1);
		break;
	      }
	    auto&& __val2 = *__first;
	    if (!__comp_proj(__val2, __val1))
	      {
		if (__comp_proj(__val1, __result.min))
		  __result.min = std::move(__val1);
		if (!__comp_proj(__val2, __result.max))
		  __result.max = std::forward<decltype(__val2)>(__val2);
	      }
	    else
	      {
		if (__comp_proj(__val2, __result.min))
		  __result.min = std::forward<decltype(__val2)>(__val2);
		if (!__comp_proj(__val1, __result.max))
		  __result.max = std::move(__val1);
	      }
	  }
	return __result;
      }

template<copyable _Tp, typename _Proj = identity,
	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
	       _Comp = ranges::less>
      constexpr minmax_result<_Tp>
      operator()(initializer_list<_Tp> __r,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::subrange(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __minmax_fn minmax{};

struct __min_element_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return __first;

auto __i = __first;
	while (++__i != __last)
	  {
	    if (std::__invoke(__comp,
			      std::__invoke(__proj, *__i),
			      std::__invoke(__proj, *__first)))
	      __first = __i;
	  }
	return __first;
      }

inline constexpr __min_element_fn min_element{};

struct __max_element_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return __first;

auto __i = __first;
	while (++__i != __last)
	  {
	    if (std::__invoke(__comp,
			      std::__invoke(__proj, *__first),
			      std::__invoke(__proj, *__i)))
	      __first = __i;
	  }
	return __first;
      }

inline constexpr __max_element_fn max_element{};

template<typename _Iter>
    using minmax_element_result = min_max_result<_Iter>;

struct __minmax_element_fn
  {
    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Proj = identity,
	     indirect_strict_weak_order<projected<_Iter, _Proj>>
	       _Comp = ranges::less>
      constexpr minmax_element_result<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
	minmax_element_result<_Iter> __result = {__first, __first};
	if (__first == __last || ++__first == __last)
	  return __result;
	else
	  {
	    // At this point __result.min == __result.max, so a single
	    // comparison with the next element suffices.
	    if (__comp_proj(*__first, *__result.min))
	      __result.min = __first;
	    else
	      __result.max = __first;
	  }
	while (++__first != __last)
	  {
	    // Now process two elements at a time so that we perform at most
	    // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
	    // iterations of this loop performs three comparisons).
	    auto __prev = __first;
	    if (++__first == __last)
	      {
		// N is odd; in this final iteration, we perform at most two
		// comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
		// which is not more than 3*N/2, as required.
		if (__comp_proj(*__prev, *__result.min))
		  __result.min = __prev;
		else if (!__comp_proj(*__prev, *__result.max))
		  __result.max = __prev;
		break;
	      }
	    if (!__comp_proj(*__first, *__prev))
	      {
		if (__comp_proj(*__prev, *__result.min))
		  __result.min = __prev;
		if (!__comp_proj(*__first, *__result.max))
		  __result.max = __first;
	      }
	    else
	      {
		if (__comp_proj(*__first, *__result.min))
		  __result.min = __first;
		if (!__comp_proj(*__prev, *__result.max))
		  __result.max = __prev;
	      }
	  }
	return __result;
      }

template<forward_range _Range, typename _Proj = identity,
	     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
	       _Comp = ranges::less>
      constexpr minmax_element_result<borrowed_iterator_t<_Range>>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __minmax_element_fn minmax_element{};

struct __lexicographical_compare_fn
  {
    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
	     typename _Proj1 = identity, typename _Proj2 = identity,
	     indirect_strict_weak_order<projected<_Iter1, _Proj1>,
					projected<_Iter2, _Proj2>>
	       _Comp = ranges::less>
      constexpr bool
      operator()(_Iter1 __first1, _Sent1 __last1,
		 _Iter2 __first2, _Sent2 __last2,
		 _Comp __comp = {},
		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
      {
	if constexpr (__detail::__is_normal_iterator<_Iter1>
		      && same_as<_Iter1, _Sent1>)
	  return (*this)(__first1.base(), __last1.base(),
			 std::move(__first2), std::move(__last2),
			 std::move(__comp),
			 std::move(__proj1), std::move(__proj2));
	else if constexpr (__detail::__is_normal_iterator<_Iter2>
			   && same_as<_Iter2, _Sent2>)
	  return (*this)(std::move(__first1), std::move(__last1),
			 __first2.base(), __last2.base(),
			 std::move(__comp),
			 std::move(__proj1), std::move(__proj2));
	else
	  {
	    constexpr bool __sized_iters
	      = (sized_sentinel_for<_Sent1, _Iter1>
		 && sized_sentinel_for<_Sent2, _Iter2>);
	    if constexpr (__sized_iters)
	      {
		using _ValueType1 = iter_value_t<_Iter1>;
		using _ValueType2 = iter_value_t<_Iter2>;
		// This condition is consistent with the one in
		// __lexicographical_compare_aux in <bits/stl_algobase.h>.
		constexpr bool __use_memcmp
		  = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
		     && __ptr_to_nonvolatile<_Iter1>
		     && __ptr_to_nonvolatile<_Iter2>
		     && (is_same_v<_Comp, ranges::less>
			 || is_same_v<_Comp, ranges::greater>)
		     && is_same_v<_Proj1, identity>
		     && is_same_v<_Proj2, identity>);
		if constexpr (__use_memcmp)
		  {
		    const auto __d1 = __last1 - __first1;
		    const auto __d2 = __last2 - __first2;

if (const auto __len = std::min(__d1, __d2))
		      {
			const auto __c
			  = std::__memcmp(__first1, __first2, __len);
			if constexpr (is_same_v<_Comp, ranges::less>)
			  {
			    if (__c < 0)
			      return true;
			    if (__c > 0)
			      return false;
			  }
			else if constexpr (is_same_v<_Comp, ranges::greater>)
			  {
			    if (__c > 0)
			      return true;
			    if (__c < 0)
			      return false;
			  }
		      }
		    return __d1 < __d2;
		  }
	      }

for (; __first1 != __last1 && __first2 != __last2;
		 ++__first1, (void) ++__first2)
	      {
		if (std::__invoke(__comp,
				  std::__invoke(__proj1, *__first1),
				  std::__invoke(__proj2, *__first2)))
		  return true;
		if (std::__invoke(__comp,
				  std::__invoke(__proj2, *__first2),
				  std::__invoke(__proj1, *__first1)))
		  return false;
	      }
	    return __first1 == __last1 && __first2 != __last2;
	  }
      }

private:
    template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
      static constexpr bool __ptr_to_nonvolatile
	= is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
  };

inline constexpr __lexicographical_compare_fn lexicographical_compare;

template<typename _Iter>
    struct in_found_result
    {
      [[no_unique_address]] _Iter in;
      bool found;

template<typename _Iter2>
	requires convertible_to<const _Iter&, _Iter2>
	constexpr
	operator in_found_result<_Iter2>() const &
	{ return {in, found}; }

template<typename _Iter2>
	requires convertible_to<_Iter, _Iter2>
	constexpr
	operator in_found_result<_Iter2>() &&
	{ return {std::move(in), found}; }
    };

template<typename _Iter>
    using next_permutation_result = in_found_result<_Iter>;

struct __next_permutation_fn
  {
    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr next_permutation_result<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return {std::move(__first), false};

auto __i = __first;
	++__i;
	if (__i == __last)
	  return {std::move(__i), false};

auto __lasti = ranges::next(__first, __last);
	__i = __lasti;
	--__i;

for (;;)
	  {
	    auto __ii = __i;
	    --__i;
	    if (std::__invoke(__comp,
			      std::__invoke(__proj, *__i),
			      std::__invoke(__proj, *__ii)))
	      {
		auto __j = __lasti;
		while (!(bool)std::__invoke(__comp,
					    std::__invoke(__proj, *__i),
					    std::__invoke(__proj, *--__j)))
		  ;
		ranges::iter_swap(__i, __j);
		ranges::reverse(__ii, __last);
		return {std::move(__lasti), true};
	      }
	    if (__i == __first)
	      {
		ranges::reverse(__first, __last);
		return {std::move(__lasti), false};
	      }
	  }
      }

template<bidirectional_range _Range, typename _Comp = ranges::less,
	     typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      constexpr next_permutation_result<borrowed_iterator_t<_Range>>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __next_permutation_fn next_permutation{};

template<typename _Iter>
    using prev_permutation_result = in_found_result<_Iter>;

struct __prev_permutation_fn
  {
    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
	     typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr prev_permutation_result<_Iter>
      operator()(_Iter __first, _Sent __last,
		 _Comp __comp = {}, _Proj __proj = {}) const
      {
	if (__first == __last)
	  return {std::move(__first), false};

auto __i = __first;
	++__i;
	if (__i == __last)
	  return {std::move(__i), false};

auto __lasti = ranges::next(__first, __last);
	__i = __lasti;
	--__i;

for (;;)
	  {
	    auto __ii = __i;
	    --__i;
	    if (std::__invoke(__comp,
			      std::__invoke(__proj, *__ii),
			      std::__invoke(__proj, *__i)))
	      {
		auto __j = __lasti;
		while (!(bool)std::__invoke(__comp,
					    std::__invoke(__proj, *--__j),
					    std::__invoke(__proj, *__i)))
		  ;
		ranges::iter_swap(__i, __j);
		ranges::reverse(__ii, __last);
		return {std::move(__lasti), true};
	      }
	    if (__i == __first)
	      {
		ranges::reverse(__first, __last);
		return {std::move(__lasti), false};
	      }
	  }
      }

template<bidirectional_range _Range, typename _Comp = ranges::less,
	     typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
	return (*this)(ranges::begin(__r), ranges::end(__r),
		       std::move(__comp), std::move(__proj));
      }
  };

inline constexpr __prev_permutation_fn prev_permutation{};

} // namespace ranges

#define __cpp_lib_shift 201806L
  template<typename _ForwardIterator>
    constexpr _ForwardIterator
    shift_left(_ForwardIterator __first, _ForwardIterator __last,
	       typename iterator_traits<_ForwardIterator>::difference_type __n)
    {
      __glibcxx_assert(__n >= 0);
      if (__n == 0)
	return __last;

auto __mid = ranges::next(__first, __n, __last);
      if (__mid == __last)
	return __first;
      return std::move(std::move(__mid), std::move(__last), std::move(__first));
    }

template<typename _ForwardIterator>
    constexpr _ForwardIterator
    shift_right(_ForwardIterator __first, _ForwardIterator __last,
		typename iterator_traits<_ForwardIterator>::difference_type __n)
    {
      __glibcxx_assert(__n >= 0);
      if (__n == 0)
	return __first;

using _Cat
	= typename iterator_traits<_ForwardIterator>::iterator_category;
      if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
	{
	  auto __mid = ranges::next(__last, -__n, __first);
	  if (__mid == __first)
	    return __last;

return std::move_backward(std::move(__first), std::move(__mid),
				    std::move(__last));
	}
      else
	{
	  auto __result = ranges::next(__first, __n, __last);
	  if (__result == __last)
	    return __last;

auto __dest_head = __first, __dest_tail = __result;
	  while (__dest_head != __result)
	    {
	      if (__dest_tail == __last)
		{
		  // If we get here, then we must have
		  //     2*n >= distance(__first, __last)
		  // i.e. we are shifting out at least half of the range.  In
		  // this case we can safely perform the shift with a single
		  // move.
		  std::move(std::move(__first), std::move(__dest_head), __result);
		  return __result;
		}
	      ++__dest_head;
	      ++__dest_tail;
	    }

for (;;)
	    {
	      // At the start of each iteration of this outer loop, the range
	      // [__first, __result) contains those elements that after shifting
	      // the whole range right by __n, should end up in
	      // [__dest_head, __dest_tail) in order.

// The below inner loop swaps the elements of [__first, __result)
	      // and [__dest_head, __dest_tail), while simultaneously shifting
	      // the latter range by __n.
	      auto __cursor = __first;
	      while (__cursor != __result)
		{
		  if (__dest_tail == __last)
		    {
		      // At this point the ranges [__first, result) and
		      // [__dest_head, dest_tail) are disjoint, so we can safely
		      // move the remaining elements.
		      __dest_head = std::move(__cursor, __result,
					      std::move(__dest_head));
		      std::move(std::move(__first), std::move(__cursor),
				std::move(__dest_head));
		      return __result;
		    }
		  std::iter_swap(__cursor, __dest_head);
		  ++__dest_head;
		  ++__dest_tail;
		  ++__cursor;
		}
	    }
	}
    }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif // concepts
#endif // C++20
#endif // _RANGES_ALGO_H

🔐 Sid Gifari File Manager Pro