// Concepts and traits for use with iterators -*- C++ -*-

// Copyright (C) 2019-2025 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/iterator_concepts.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{iterator}
 */

#ifndef _ITERATOR_CONCEPTS_H
#define _ITERATOR_CONCEPTS_H 1

#ifdef _GLIBCXX_SYSHDR
#pragma GCC system_header
#endif

#if __cplusplus >= 202002L
#include <concepts>
#include <bits/ptr_traits.h>	// to_address
#include <bits/ranges_cmp.h>	// identity, ranges::less

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic" // __int128

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /** A sentinel type that can be used to check for the end of a range.
   *
   * For some iterator types the past-the-end sentinel value is independent
   * of the underlying sequence, and a default sentinel can be used with them.
   * For example, a `std::counted_iterator` keeps a count of how many elements
   * remain, and so checking for the past-the-end value only requires checking
   * if that count has reached zero. A past-the-end `std::istream_iterator` is
   * equal to the default-constructed value, which can be easily checked.
   *
   * Comparing iterators of these types to `std::default_sentinel` is a
   * convenient way to check if the end has been reached.
   *
   * @since C++20
   */
  struct default_sentinel_t { };

  /// A default sentinel value.
  inline constexpr default_sentinel_t default_sentinel{};

#if __cpp_lib_concepts
  struct input_iterator_tag;
  struct output_iterator_tag;
  struct forward_iterator_tag;
  struct bidirectional_iterator_tag;
  struct random_access_iterator_tag;
  struct contiguous_iterator_tag;

  template<typename _Iterator>
    struct iterator_traits;

  template<typename _Tp> requires is_object_v<_Tp>
    struct iterator_traits<_Tp*>;

  template<typename _Iterator, typename>
    struct __iterator_traits;

  namespace __detail
  {
    template<typename _Tp>
      using __with_ref = _Tp&;

    template<typename _Tp>
      concept __can_reference = requires { typename __with_ref<_Tp>; };

    template<typename _Tp>
      concept __dereferenceable = requires(_Tp& __t)
	{
	  { *__t } -> __can_reference;
	};
  } // namespace __detail

  template<__detail::__dereferenceable _Tp>
    using iter_reference_t = decltype(*std::declval<_Tp&>());

  namespace ranges
  {
    /// @cond undocumented
    // Implementation of std::ranges::iter_move, [iterator.cust.move].
    namespace __imove
    {
      void iter_move() = delete;

      // Satisfied if _Tp is a class or enumeration type and iter_move
      // can be found by argument-dependent lookup.
      template<typename _Tp>
	concept __adl_imove
	  = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>)
	      && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); };

      struct _IterMove
      {
      private:
	// The type returned by dereferencing a value of type _Tp.
	// Unlike iter_reference_t this preserves the value category of _Tp.
	template<typename _Tp>
	  using __iter_ref_t = decltype(*std::declval<_Tp>());

	template<typename _Tp>
	  struct __result
	  { using type = __iter_ref_t<_Tp>; };

	// Use iter_move(E) if that works.
	template<typename _Tp>
	  requires __adl_imove<_Tp>
	  struct __result<_Tp>
	  { using type = decltype(iter_move(std::declval<_Tp>())); };

	// Otherwise, if *E is an lvalue, use std::move(*E).
	template<typename _Tp>
	  requires (!__adl_imove<_Tp>)
	    && is_lvalue_reference_v<__iter_ref_t<_Tp>>
	  struct __result<_Tp>
	  {
	    // Instead of decltype(std::move(*E)) we define the type as the
	    // return type of std::move, i.e. remove_reference_t<iter_ref>&&.
	    // N.B. the use of decltype(declval<X>()) instead of just X&& is
	    // needed for function reference types, see PR libstdc++/119469.
	    using type
	      = decltype(std::declval<remove_reference_t<__iter_ref_t<_Tp>>>());
	  };

	template<typename _Tp>
	  static constexpr bool
	  _S_noexcept()
	  {
	    if constexpr (__adl_imove<_Tp>)
	      return noexcept(iter_move(std::declval<_Tp>()));
	    else
	      return noexcept(*std::declval<_Tp>());
	  }

      public:
	// The result type of iter_move(std::declval<_Tp>())
	template<typename _Tp>
	  using __type = typename __result<_Tp>::type;

	template<typename _Tp>
	  requires __adl_imove<_Tp> || requires { typename __iter_ref_t<_Tp>; }
	  [[nodiscard]]
	  constexpr __type<_Tp>
	  operator()(_Tp&& __e) const
	  noexcept(_S_noexcept<_Tp>())
	  {
	    if constexpr (__adl_imove<_Tp>)
	      return iter_move(static_cast<_Tp&&>(__e));
	    else if constexpr (is_lvalue_reference_v<__iter_ref_t<_Tp>>)
	      return std::move(*static_cast<_Tp&&>(__e));
	    else
	      return *static_cast<_Tp&&>(__e);
	  }
      };
    } // namespace __imove
    /// @endcond

    inline namespace _Cpo {
      inline constexpr __imove::_IterMove iter_move{};
    }
  } // namespace ranges

  /// The result type of ranges::iter_move(std::declval<_Tp&>())
  template<__detail::__dereferenceable _Tp>
    requires __detail::__can_reference<ranges::__imove::_IterMove::__type<_Tp&>>
    using iter_rvalue_reference_t = ranges::__imove::_IterMove::__type<_Tp&>;

  template<typename> struct incrementable_traits { };

  template<typename _Tp> requires is_object_v<_Tp>
    struct incrementable_traits<_Tp*>
    { using difference_type = ptrdiff_t; };

  template<typename _Iter>
    struct incrementable_traits<const _Iter>
    : incrementable_traits<_Iter> { };

  template<typename _Tp> requires requires { typename _Tp::difference_type; }
    struct incrementable_traits<_Tp>
    { using difference_type = typename _Tp::difference_type; };

  template<typename _Tp>
    requires (!requires { typename _Tp::difference_type; }
	      && requires(const _Tp& __a, const _Tp& __b)
	      { { __a - __b } -> integral; })
    struct incrementable_traits<_Tp>
    {
      using difference_type
	= make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>;
    };

#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
  // __int128 is incrementable even if !integral<__int128>
  template<>
    struct incrementable_traits<__int128>
    { using difference_type = __int128; };

  template<>
    struct incrementable_traits<unsigned __int128>
    { using difference_type = __int128; };
#endif

  namespace __detail
  {
    // An iterator such that iterator_traits<_Iter> names a specialization
    // generated from the primary template.
    template<typename _Iter>
      concept __primary_traits_iter
	= __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>);

    template<typename _Iter, typename _Tp>
      struct __iter_traits_impl
      { using type = iterator_traits<_Iter>; };

    template<typename _Iter, typename _Tp>
      requires __primary_traits_iter<_Iter>
      struct __iter_traits_impl<_Iter, _Tp>
      { using type = _Tp; };

    // ITER_TRAITS
    template<typename _Iter, typename _Tp = _Iter>
      using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type;

    template<typename _Tp>
      using __iter_diff_t = typename
	__iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type;
  } // namespace __detail

  template<typename _Tp>
    using iter_difference_t = __detail::__iter_diff_t<remove_cvref_t<_Tp>>;

  namespace __detail
  {
    template<typename> struct __cond_value_type { };

    template<typename _Tp> requires is_object_v<_Tp>
      struct __cond_value_type<_Tp>
      { using value_type = remove_cv_t<_Tp>; };

    template<typename _Tp>
      concept __has_member_value_type
	= requires { typename _Tp::value_type; };

    template<typename _Tp>
      concept __has_member_element_type
	= requires { typename _Tp::element_type; };

  } // namespace __detail

  template<typename> struct indirectly_readable_traits { };

  template<typename _Tp>
    struct indirectly_readable_traits<_Tp*>
    : __detail::__cond_value_type<_Tp>
    { };

  template<typename _Iter> requires is_array_v<_Iter>
    struct indirectly_readable_traits<_Iter>
    { using value_type = remove_cv_t<remove_extent_t<_Iter>>; };

  template<typename _Iter>
    struct indirectly_readable_traits<const _Iter>
    : indirectly_readable_traits<_Iter>
    { };

  template<__detail::__has_member_value_type _Tp>
    struct indirectly_readable_traits<_Tp>
    : __detail::__cond_value_type<typename _Tp::value_type>
    { };

  template<__detail::__has_member_element_type _Tp>
    struct indirectly_readable_traits<_Tp>
    : __detail::__cond_value_type<typename _Tp::element_type>
    { };

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 3446. indirectly_readable_traits ambiguity for types with both [...]
  template<__detail::__has_member_value_type _Tp>
    requires __detail::__has_member_element_type<_Tp>
    && same_as<remove_cv_t<typename _Tp::element_type>,
	       remove_cv_t<typename _Tp::value_type>>
    struct indirectly_readable_traits<_Tp>
    : __detail::__cond_value_type<typename _Tp::value_type>
    { };

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 3541. indirectly_readable_traits should be SFINAE-friendly for all types
  template<__detail::__has_member_value_type _Tp>
    requires __detail::__has_member_element_type<_Tp>
    struct indirectly_readable_traits<_Tp>
    { };

  namespace __detail
  {
    template<typename _Tp>
      using __iter_value_t = typename
	__iter_traits<_Tp, indirectly_readable_traits<_Tp>>::value_type;
  } // namespace __detail

  template<typename _Tp>
    using iter_value_t = __detail::__iter_value_t<remove_cvref_t<_Tp>>;

  namespace __detail
  {
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 3420. cpp17-iterator should check [type] looks like an iterator first
    template<typename _Iter>
      concept __cpp17_iterator = requires(_Iter __it)
	{
	  { *__it } -> __can_reference;
	  { ++__it } -> same_as<_Iter&>;
	  { *__it++ } -> __can_reference;
	} && copyable<_Iter>;

    template<typename _Iter>
      concept __cpp17_input_iterator = __cpp17_iterator<_Iter>
	&& equality_comparable<_Iter>
	&& requires(_Iter __it)
	{
	  typename incrementable_traits<_Iter>::difference_type;
	  typename indirectly_readable_traits<_Iter>::value_type;
	  typename common_reference_t<iter_reference_t<_Iter>&&,
		   typename indirectly_readable_traits<_Iter>::value_type&>;
	  typename common_reference_t<decltype(*__it++)&&,
		   typename indirectly_readable_traits<_Iter>::value_type&>;
	  requires signed_integral<
	    typename incrementable_traits<_Iter>::difference_type>;
	};

    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 3798. Rvalue reference and iterator_category
    template<typename _Iter>
      concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter>
	&& constructible_from<_Iter>
	&& is_reference_v<iter_reference_t<_Iter>>
	&& same_as<remove_cvref_t<iter_reference_t<_Iter>>,
		   typename indirectly_readable_traits<_Iter>::value_type>
	&& requires(_Iter __it)
	{
	  {  __it++ } -> convertible_to<const _Iter&>;
	  { *__it++ } -> same_as<iter_reference_t<_Iter>>;
	};

    template<typename _Iter>
      concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter>
	&& requires(_Iter __it)
	{
	  {  --__it } -> same_as<_Iter&>;
	  {  __it-- } -> convertible_to<const _Iter&>;
	  { *__it-- } -> same_as<iter_reference_t<_Iter>>;
	};

    template<typename _Iter>
      concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter>
	&& totally_ordered<_Iter>
	&& requires(_Iter __it,
		    typename incrementable_traits<_Iter>::difference_type __n)
	{
	  { __it += __n } -> same_as<_Iter&>;
	  { __it -= __n } -> same_as<_Iter&>;
	  { __it +  __n } -> same_as<_Iter>;
	  { __n +  __it } -> same_as<_Iter>;
	  { __it -  __n } -> same_as<_Iter>;
	  { __it -  __it } -> same_as<decltype(__n)>;
	  {  __it[__n]  } -> convertible_to<iter_reference_t<_Iter>>;
	};

    template<typename _Iter>
      concept __iter_with_nested_types = requires {
	typename _Iter::iterator_category;
	typename _Iter::value_type;
	typename _Iter::difference_type;
	typename _Iter::reference;
      };

    template<typename _Iter>
      concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>;

    template<typename _Iter>
      concept __iter_without_category
	= !requires { typename _Iter::iterator_category; };

  } // namespace __detail

  template<typename _Iterator>
    requires __detail::__iter_with_nested_types<_Iterator>
    struct __iterator_traits<_Iterator, void>
    {
    private:
      template<typename _Iter>
	struct __ptr
	{ using type = void; };

      template<typename _Iter> requires requires { typename _Iter::pointer; }
	struct __ptr<_Iter>
	{ using type = typename _Iter::pointer; };

    public:
      using iterator_category = typename _Iterator::iterator_category;
      using value_type	      = typename _Iterator::value_type;
      using difference_type   = typename _Iterator::difference_type;
      using pointer	      = typename __ptr<_Iterator>::type;
      using reference	      = typename _Iterator::reference;
    };

  template<typename _Iterator>
    requires __detail::__iter_without_nested_types<_Iterator>
	      && __detail::__cpp17_input_iterator<_Iterator>
    struct __iterator_traits<_Iterator, void>
    {
    private:
      template<typename _Iter>
	struct __cat
	{ using type = input_iterator_tag; };

      template<typename _Iter>
	requires requires { typename _Iter::iterator_category; }
	struct __cat<_Iter>
	{ using type = typename _Iter::iterator_category; };

      template<typename _Iter>
	requires __detail::__iter_without_category<_Iter>
		  && __detail::__cpp17_randacc_iterator<_Iter>
	struct __cat<_Iter>
	{ using type = random_access_iterator_tag; };

      template<typename _Iter>
	requires __detail::__iter_without_category<_Iter>
		  && __detail::__cpp17_bidi_iterator<_Iter>
	struct __cat<_Iter>
	{ using type = bidirectional_iterator_tag; };

      template<typename _Iter>
	requires __detail::__iter_without_category<_Iter>
		  && __detail::__cpp17_fwd_iterator<_Iter>
	struct __cat<_Iter>
	{ using type = forward_iterator_tag; };

      template<typename _Iter>
	struct __ptr
	{ using type = void; };

      template<typename _Iter> requires requires { typename _Iter::pointer; }
	struct __ptr<_Iter>
	{ using type = typename _Iter::pointer; };

      template<typename _Iter>
	requires (!requires { typename _Iter::pointer; }
	    && requires(_Iter& __it) { __it.operator->(); })
	struct __ptr<_Iter>
	{ using type = decltype(std::declval<_Iter&>().operator->()); };

      template<typename _Iter>
	struct __ref
	{ using type = iter_reference_t<_Iter>; };

      template<typename _Iter> requires requires { typename _Iter::reference; }
	struct __ref<_Iter>
	{ using type = typename _Iter::reference; };

    public:
      using iterator_category = typename __cat<_Iterator>::type;
      using value_type
	= typename indirectly_readable_traits<_Iterator>::value_type;
      using difference_type
	= typename incrementable_traits<_Iterator>::difference_type;
      using pointer	      = typename __ptr<_Iterator>::type;
      using reference	      = typename __ref<_Iterator>::type;
    };

  template<typename _Iterator>
    requires __detail::__iter_without_nested_types<_Iterator>
	      && __detail::__cpp17_iterator<_Iterator>
    struct __iterator_traits<_Iterator, void>
    {
    private:
      template<typename _Iter>
	struct __diff
	{ using type = void; };

      template<typename _Iter>
	requires requires
	{ typename incrementable_traits<_Iter>::difference_type; }
	struct __diff<_Iter>
	{
	  using type = typename incrementable_traits<_Iter>::difference_type;
	};

    public:
      using iterator_category = output_iterator_tag;
      using value_type	      = void;
      using difference_type   = typename __diff<_Iterator>::type;
      using pointer	      = void;
      using reference	      = void;
    };

  namespace __detail
  {
    template<typename _Iter>
      struct __iter_concept_impl;

    // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid.
    template<typename _Iter>
      requires requires { typename __iter_traits<_Iter>::iterator_concept; }
      struct __iter_concept_impl<_Iter>
      { using type = typename __iter_traits<_Iter>::iterator_concept; };

    // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid.
    template<typename _Iter>
      requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
	  && requires { typename __iter_traits<_Iter>::iterator_category; })
      struct __iter_concept_impl<_Iter>
      { using type = typename __iter_traits<_Iter>::iterator_category; };

    // Otherwise, random_access_tag if iterator_traits<I> is not specialized.
    template<typename _Iter>
      requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
	  && !requires { typename __iter_traits<_Iter>::iterator_category; }
	  && __primary_traits_iter<_Iter>)
      struct __iter_concept_impl<_Iter>
      { using type = random_access_iterator_tag; };

    // Otherwise, there is no ITER_CONCEPT(I) type.
    template<typename _Iter>
      struct __iter_concept_impl
      { };

    // ITER_CONCEPT
    template<typename _Iter>
      using __iter_concept = typename __iter_concept_impl<_Iter>::type;

  template<typename _In>
    concept __indirectly_readable_impl = requires
      {
	typename iter_value_t<_In>;
	typename iter_reference_t<_In>;
	typename iter_rvalue_reference_t<_In>;
	requires same_as<iter_reference_t<const _In>,
			 iter_reference_t<_In>>;
	requires same_as<iter_rvalue_reference_t<const _In>,
			 iter_rvalue_reference_t<_In>>;
      }
      && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&>
      && common_reference_with<iter_reference_t<_In>&&,
			      iter_rvalue_reference_t<_In>&&>
      && common_reference_with<iter_rvalue_reference_t<_In>&&,
			       const iter_value_t<_In>&>;

  } // namespace __detail

  /// Requirements for types that are readable by applying operator*.
  template<typename _In>
    concept indirectly_readable
      = __detail::__indirectly_readable_impl<remove_cvref_t<_In>>;

  namespace __detail
  {
    template<typename _Tp>
      struct __indirect_value
      { using type = iter_value_t<_Tp>&; };

    // __indirect_value<projected<_Iter, _Proj>> is defined later.
  } // namespace __detail

  template<typename _Tp>
    using __indirect_value_t = typename __detail::__indirect_value<_Tp>::type;

  template<indirectly_readable _Tp>
    using iter_common_reference_t
      = common_reference_t<iter_reference_t<_Tp>, __indirect_value_t<_Tp>>;

  /// Requirements for writing a value into an iterator's referenced object.
  template<typename _Out, typename _Tp>
    concept indirectly_writable = requires(_Out&& __o, _Tp&& __t)
      {
	*__o = std::forward<_Tp>(__t);
	*std::forward<_Out>(__o) = std::forward<_Tp>(__t);
	const_cast<const iter_reference_t<_Out>&&>(*__o)
	  = std::forward<_Tp>(__t);
	const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o))
	  = std::forward<_Tp>(__t);
      };

  namespace ranges::__detail
  {
    class __max_diff_type;
    class __max_size_type;

    __extension__
    template<typename _Tp>
      concept __is_signed_int128
#if __SIZEOF_INT128__
	= same_as<_Tp, __int128>;
#else
	= false;
#endif

    __extension__
    template<typename _Tp>
      concept __is_unsigned_int128
#if __SIZEOF_INT128__
	= same_as<_Tp, unsigned __int128>;
#else
	= false;
#endif

    template<typename _Tp>
      concept __cv_bool = same_as<const volatile _Tp, const volatile bool>;

    template<typename _Tp>
      concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>;

    template<typename _Tp>
      concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>;

    template<typename _Tp>
      concept __is_integer_like = __integral_nonbool<_Tp>
	|| __is_int128<_Tp>
	|| same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>;

    template<typename _Tp>
      concept __is_signed_integer_like = signed_integral<_Tp>
	|| __is_signed_int128<_Tp>
	|| same_as<_Tp, __max_diff_type>;

  } // namespace ranges::__detail

  namespace __detail { using ranges::__detail::__is_signed_integer_like; }

  /// Requirements on types that can be incremented with ++.
  template<typename _Iter>
    concept weakly_incrementable = movable<_Iter>
      && requires(_Iter __i)
      {
	typename iter_difference_t<_Iter>;
	requires __detail::__is_signed_integer_like<iter_difference_t<_Iter>>;
	{ ++__i } -> same_as<_Iter&>;
	__i++;
      };

  template<typename _Iter>
    concept incrementable = regular<_Iter> && weakly_incrementable<_Iter>
      && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; };

  template<typename _Iter>
    concept input_or_output_iterator
      = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
	&& weakly_incrementable<_Iter>;

  template<typename _Sent, typename _Iter>
    concept sentinel_for = semiregular<_Sent>
      && input_or_output_iterator<_Iter>
      && __detail::__weakly_eq_cmp_with<_Sent, _Iter>;

  template<typename _Sent, typename _Iter>
    inline constexpr bool disable_sized_sentinel_for = false;

  template<typename _Sent, typename _Iter>
    concept sized_sentinel_for = sentinel_for<_Sent, _Iter>
    && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>>
    && requires(const _Iter& __i, const _Sent& __s)
    {
      { __s - __i } -> same_as<iter_difference_t<_Iter>>;
      { __i - __s } -> same_as<iter_difference_t<_Iter>>;
    };

  template<typename _Iter>
    concept input_iterator = input_or_output_iterator<_Iter>
      && indirectly_readable<_Iter>
      && requires { typename __detail::__iter_concept<_Iter>; }
      && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>;

  template<typename _Iter, typename _Tp>
    concept output_iterator = input_or_output_iterator<_Iter>
      && indirectly_writable<_Iter, _Tp>
      && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); };

  template<typename _Iter>
    concept forward_iterator = input_iterator<_Iter>
      && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag>
      && incrementable<_Iter> && sentinel_for<_Iter, _Iter>;

  template<typename _Iter>
    concept bidirectional_iterator = forward_iterator<_Iter>
      && derived_from<__detail::__iter_concept<_Iter>,
		      bidirectional_iterator_tag>
      && requires(_Iter __i)
      {
	{ --__i } -> same_as<_Iter&>;
	{ __i-- } -> same_as<_Iter>;
      };

  template<typename _Iter>
    concept random_access_iterator = bidirectional_iterator<_Iter>
      && derived_from<__detail::__iter_concept<_Iter>,
		      random_access_iterator_tag>
      && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter>
      && requires(_Iter __i, const _Iter __j,
		  const iter_difference_t<_Iter> __n)
      {
	{ __i += __n } -> same_as<_Iter&>;
	{ __j +  __n } -> same_as<_Iter>;
	{ __n +  __j } -> same_as<_Iter>;
	{ __i -= __n } -> same_as<_Iter&>;
	{ __j -  __n } -> same_as<_Iter>;
	{  __j[__n]  } -> same_as<iter_reference_t<_Iter>>;
      };

  template<typename _Iter>
    concept contiguous_iterator = random_access_iterator<_Iter>
      && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag>
      && is_lvalue_reference_v<iter_reference_t<_Iter>>
      && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>>
      && requires(const _Iter& __i)
      {
	{ std::to_address(__i) }
	  -> same_as<add_pointer_t<iter_reference_t<_Iter>>>;
      };

  // [indirectcallable], indirect callable requirements

  // [indirectcallable.indirectinvocable], indirect callables

  template<typename _Fn, typename _Iter>
    concept indirectly_unary_invocable = indirectly_readable<_Iter>
      && copy_constructible<_Fn> && invocable<_Fn&, __indirect_value_t<_Iter>>
      && invocable<_Fn&, iter_reference_t<_Iter>>
      && common_reference_with<invoke_result_t<_Fn&, __indirect_value_t<_Iter>>,
			       invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;

  template<typename _Fn, typename _Iter>
    concept indirectly_regular_unary_invocable = indirectly_readable<_Iter>
      && copy_constructible<_Fn>
      && regular_invocable<_Fn&, __indirect_value_t<_Iter>>
      && regular_invocable<_Fn&, iter_reference_t<_Iter>>
      && common_reference_with<invoke_result_t<_Fn&, __indirect_value_t<_Iter>>,
			       invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;

  template<typename _Fn, typename _Iter>
    concept indirect_unary_predicate = indirectly_readable<_Iter>
      && copy_constructible<_Fn> && predicate<_Fn&, __indirect_value_t<_Iter>>
      && predicate<_Fn&, iter_reference_t<_Iter>>;

  template<typename _Fn, typename _I1, typename _I2>
    concept indirect_binary_predicate
      = indirectly_readable<_I1> && indirectly_readable<_I2>
      && copy_constructible<_Fn>
      && predicate<_Fn&, __indirect_value_t<_I1>, __indirect_value_t<_I2>>
      && predicate<_Fn&, __indirect_value_t<_I1>, iter_reference_t<_I2>>
      && predicate<_Fn&, iter_reference_t<_I1>, __indirect_value_t<_I2>>
      && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>;

  template<typename _Fn, typename _I1, typename _I2 = _I1>
    concept indirect_equivalence_relation
      = indirectly_readable<_I1> && indirectly_readable<_I2>
      && copy_constructible<_Fn>
      && equivalence_relation<_Fn&, __indirect_value_t<_I1>, __indirect_value_t<_I2>>
      && equivalence_relation<_Fn&, __indirect_value_t<_I1>, iter_reference_t<_I2>>
      && equivalence_relation<_Fn&, iter_reference_t<_I1>, __indirect_value_t<_I2>>
      && equivalence_relation<_Fn&, iter_reference_t<_I1>,
			      iter_reference_t<_I2>>;

  template<typename _Fn, typename _I1, typename _I2 = _I1>
    concept indirect_strict_weak_order
      = indirectly_readable<_I1> && indirectly_readable<_I2>
      && copy_constructible<_Fn>
      && strict_weak_order<_Fn&, __indirect_value_t<_I1>, __indirect_value_t<_I2>>
      && strict_weak_order<_Fn&, __indirect_value_t<_I1>, iter_reference_t<_I2>>
      && strict_weak_order<_Fn&, iter_reference_t<_I1>, __indirect_value_t<_I2>>
      && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>;

  template<typename _Fn, typename... _Is>
    requires (indirectly_readable<_Is> && ...)
      && invocable<_Fn, iter_reference_t<_Is>...>
    using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Is>...>;

  namespace __detail
  {
    template<typename _Iter, typename _Proj>
      struct __projected
      {
	struct __type
	{
	  using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
	  indirect_result_t<_Proj&, _Iter> operator*() const; // not defined

	  // These are used to identify and obtain the template arguments of a
	  // specialization of the 'projected' alias template below.
	  using __projected_Iter = _Iter;
	  using __projected_Proj = _Proj;
	};
      };

    template<weakly_incrementable _Iter, typename _Proj>
      struct __projected<_Iter, _Proj>
      {
	struct __type
	{
	  using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
	  using difference_type = iter_difference_t<_Iter>;
	  indirect_result_t<_Proj&, _Iter> operator*() const; // not defined

	  using __projected_Iter = _Iter;
	  using __projected_Proj = _Proj;
	};
      };
  } // namespace __detail

  /// [projected], projected
  template<indirectly_readable _Iter,
	   indirectly_regular_unary_invocable<_Iter> _Proj>
    using projected = typename __detail::__projected<_Iter, _Proj>::__type;

  // Matches specializations of the 'projected' alias template.
  template<typename _Tp>
    requires same_as<_Tp, projected<typename _Tp::__projected_Iter,
				    typename _Tp::__projected_Proj>>
    struct __detail::__indirect_value<_Tp>
    {
      using _Iter = typename _Tp::__projected_Iter;
      using _Proj = typename _Tp::__projected_Proj;
      using type = invoke_result_t<_Proj&, __indirect_value_t<_Iter>>;
    };

#if __glibcxx_algorithm_default_value_type // C++ >= 26
  template<indirectly_readable _Iter,
	   indirectly_regular_unary_invocable<_Iter> _Proj>
    using projected_value_t
	= remove_cvref_t<invoke_result_t<_Proj&, iter_value_t<_Iter>&>>;
#endif

  // [alg.req], common algorithm requirements

  /// [alg.req.ind.move], concept `indirectly_movable`

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

  template<typename _In, typename _Out>
    concept indirectly_movable_storable = indirectly_movable<_In, _Out>
      && indirectly_writable<_Out, iter_value_t<_In>>
      && movable<iter_value_t<_In>>
      && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>
      && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;

  /// [alg.req.ind.copy], concept `indirectly_copyable`
  template<typename _In, typename _Out>
    concept indirectly_copyable = indirectly_readable<_In>
      && indirectly_writable<_Out, iter_reference_t<_In>>;

  template<typename _In, typename _Out>
    concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>
      && indirectly_writable<_Out, iter_value_t<_In>&>
      && indirectly_writable<_Out, const iter_value_t<_In>&>
      && indirectly_writable<_Out, iter_value_t<_In>&&>
      && indirectly_writable<_Out, const iter_value_t<_In>&&>
      && copyable<iter_value_t<_In>>
      && constructible_from<iter_value_t<_In>, iter_reference_t<_In>>
      && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;

namespace ranges
{
  /// @cond undocumented
  // Implementation of std::ranges::iter_swap, [iterator.cust.swap].
  namespace __iswap
  {
    template<typename _It1, typename _It2>
      void iter_swap(_It1, _It2) = delete;

    // Satisfied if _Tp and _Up are class or enumeration types and iter_swap
    // can be found by argument-dependent lookup.
    template<typename _Tp, typename _Up>
      concept __adl_iswap
	= (std::__detail::__class_or_enum<remove_reference_t<_Tp>>
	  || std::__detail::__class_or_enum<remove_reference_t<_Up>>)
	&& requires(_Tp&& __t, _Up&& __u) {
	  iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u));
	};

    template<typename _Xp, typename _Yp>
      constexpr iter_value_t<_Xp>
      __iter_exchange_move(_Xp&& __x, _Yp&& __y)
      noexcept(noexcept(iter_value_t<_Xp>(iter_move(__x)))
	       && noexcept(*__x = iter_move(__y)))
      {
	iter_value_t<_Xp> __old_value(iter_move(__x));
	*__x = iter_move(__y);
	return __old_value;
      }

    struct _IterSwap
    {
    private:
      template<typename _Tp, typename _Up>
	static constexpr bool
	_S_noexcept()
	{
	  if constexpr (__adl_iswap<_Tp, _Up>)
	    return noexcept(iter_swap(std::declval<_Tp>(),
				      std::declval<_Up>()));
	  else if constexpr (indirectly_readable<_Tp>
	      && indirectly_readable<_Up>
	      && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
	    return noexcept(ranges::swap(*std::declval<_Tp>(),
					 *std::declval<_Up>()));
	  else
	    return noexcept(*std::declval<_Tp>()
		= __iswap::__iter_exchange_move(std::declval<_Up>(),
						    std::declval<_Tp>()));
	}

    public:
      template<typename _Tp, typename _Up>
	requires __adl_iswap<_Tp, _Up>
	|| (indirectly_readable<remove_reference_t<_Tp>>
	    && indirectly_readable<remove_reference_t<_Up>>
	    && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
	|| (indirectly_movable_storable<_Tp, _Up>
	    && indirectly_movable_storable<_Up, _Tp>)
	constexpr void
	operator()(_Tp&& __e1, _Up&& __e2) const
	noexcept(_S_noexcept<_Tp, _Up>())
	{
	  if constexpr (__adl_iswap<_Tp, _Up>)
	    iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2));
	  else if constexpr (indirectly_readable<_Tp>
	      && indirectly_readable<_Up>
	      && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
	    ranges::swap(*__e1, *__e2);
	  else
	    *__e1 = __iswap::__iter_exchange_move(__e2, __e1);
	}
    };
  } // namespace __iswap
  /// @endcond

  inline namespace _Cpo {
    inline constexpr __iswap::_IterSwap iter_swap{};
  }

} // namespace ranges

  /// [alg.req.ind.swap], concept `indirectly_swappable`
  template<typename _I1, typename _I2 = _I1>
    concept indirectly_swappable
      = indirectly_readable<_I1> && indirectly_readable<_I2>
      && requires(const _I1 __i1, const _I2 __i2)
      {
	ranges::iter_swap(__i1, __i1);
	ranges::iter_swap(__i2, __i2);
	ranges::iter_swap(__i1, __i2);
	ranges::iter_swap(__i2, __i1);
      };

  /// [alg.req.ind.cmp], concept `indirectly_comparable`
  template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity,
	   typename _P2 = identity>
    concept indirectly_comparable
      = indirect_binary_predicate<_Rel, projected<_I1, _P1>,
				  projected<_I2, _P2>>;

  /// [alg.req.permutable], concept `permutable`
  template<typename _Iter>
    concept permutable = forward_iterator<_Iter>
      && indirectly_movable_storable<_Iter, _Iter>
      && indirectly_swappable<_Iter, _Iter>;

  /// [alg.req.mergeable], concept `mergeable`
  template<typename _I1, typename _I2, typename _Out,
	   typename _Rel = ranges::less, typename _P1 = identity,
	   typename _P2 = identity>
    concept mergeable = input_iterator<_I1> && input_iterator<_I2>
      && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out>
      && indirectly_copyable<_I2, _Out>
      && indirect_strict_weak_order<_Rel, projected<_I1, _P1>,
				    projected<_I2, _P2>>;

  /// [alg.req.sortable], concept `sortable`
  template<typename _Iter, typename _Rel = ranges::less,
	   typename _Proj = identity>
    concept sortable = permutable<_Iter>
      && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>;

  struct unreachable_sentinel_t
  {
    template<weakly_incrementable _It>
      friend constexpr bool
      operator==(unreachable_sentinel_t, const _It&) noexcept
      { return false; }
  };

  inline constexpr unreachable_sentinel_t unreachable_sentinel{};

  // This is the namespace for [range.access] CPOs.
  namespace ranges::__access
  {
    using std::__detail::__class_or_enum;

    struct _Decay_copy final
    {
      template<typename _Tp>
	constexpr decay_t<_Tp>
	operator()(_Tp&& __t) const
	noexcept(is_nothrow_convertible_v<_Tp, decay_t<_Tp>>)
	{ return std::forward<_Tp>(__t); }
    } inline constexpr __decay_copy{};

    template<typename _Tp>
      concept __member_begin = requires(_Tp& __t)
	{
	  { __decay_copy(__t.begin()) } -> input_or_output_iterator;
	};

    // Poison pill so that unqualified lookup doesn't find std::begin.
    void begin() = delete;

    template<typename _Tp>
      concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>>
	&& requires(_Tp& __t)
	{
	  { __decay_copy(begin(__t)) } -> input_or_output_iterator;
	};

    // Simplified version of std::ranges::begin that only supports lvalues,
    // for use by __range_iter_t below.
    template<typename _Tp>
      requires is_array_v<_Tp> || __member_begin<_Tp&> || __adl_begin<_Tp&>
      auto
      __begin(_Tp& __t)
      {
	if constexpr (is_array_v<_Tp>)
	  return __t + 0;
	else if constexpr (__member_begin<_Tp&>)
	  return __t.begin();
	else
	  return begin(__t);
      }
  } // namespace ranges::__access

  namespace __detail
  {
    // Implementation of std::ranges::iterator_t, without using ranges::begin.
    template<typename _Tp>
      using __range_iter_t
	= decltype(ranges::__access::__begin(std::declval<_Tp&>()));

  } // namespace __detail

#endif // C++20 library concepts
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#pragma GCC diagnostic pop
#endif // C++20
#endif // _ITERATOR_CONCEPTS_H