[thirdparty/gcc.git] / libstdc++-v3 / include / bits / ranges_util.h

// Utilities for representing and manipulating ranges -*- C++ -*-

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

#ifndef _RANGES_UTIL_H
#define _RANGES_UTIL_H 1

#if __cplusplus > 201703L
# include <bits/ranges_base.h>

#ifdef __cpp_lib_ranges
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace ranges
{
  // C++20 24.5 [range.utility] Range utilities

  namespace __detail
  {
    template<typename _Range>
      concept __simple_view = view<_Range> && range<const _Range>
	&& same_as<iterator_t<_Range>, iterator_t<const _Range>>
	&& same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;

    template<typename _It>
      concept __has_arrow = input_iterator<_It>
	&& (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });

    template<typename _Tp, typename _Up>
      concept __not_same_as
	= !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
  } // namespace __detail

  /// The ranges::view_interface class template
  template<typename _Derived>
    requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
    class view_interface : public view_base
    {
    private:
      constexpr _Derived& _M_derived() noexcept
      {
	static_assert(derived_from<_Derived, view_interface<_Derived>>);
	static_assert(view<_Derived>);
	return static_cast<_Derived&>(*this);
      }

      constexpr const _Derived& _M_derived() const noexcept
      {
	static_assert(derived_from<_Derived, view_interface<_Derived>>);
	static_assert(view<_Derived>);
	return static_cast<const _Derived&>(*this);
      }

    public:
      constexpr bool
      empty() requires forward_range<_Derived>
      { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }

      constexpr bool
      empty() const requires forward_range<const _Derived>
      { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }

      constexpr explicit
      operator bool() requires requires { ranges::empty(_M_derived()); }
      { return !ranges::empty(_M_derived()); }

      constexpr explicit
      operator bool() const requires requires { ranges::empty(_M_derived()); }
      { return !ranges::empty(_M_derived()); }

      constexpr auto
      data() requires contiguous_iterator<iterator_t<_Derived>>
      { return to_address(ranges::begin(_M_derived())); }

      constexpr auto
      data() const
      requires range<const _Derived>
	&& contiguous_iterator<iterator_t<const _Derived>>
      { return to_address(ranges::begin(_M_derived())); }

      constexpr auto
      size()
      requires forward_range<_Derived>
	&& sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
      { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }

      constexpr auto
      size() const
      requires forward_range<const _Derived>
	&& sized_sentinel_for<sentinel_t<const _Derived>,
			      iterator_t<const _Derived>>
      { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }

      constexpr decltype(auto)
      front() requires forward_range<_Derived>
      {
	__glibcxx_assert(!empty());
	return *ranges::begin(_M_derived());
      }

      constexpr decltype(auto)
      front() const requires forward_range<const _Derived>
      {
	__glibcxx_assert(!empty());
	return *ranges::begin(_M_derived());
      }

      constexpr decltype(auto)
      back()
      requires bidirectional_range<_Derived> && common_range<_Derived>
      {
	__glibcxx_assert(!empty());
	return *ranges::prev(ranges::end(_M_derived()));
      }

      constexpr decltype(auto)
      back() const
      requires bidirectional_range<const _Derived>
	&& common_range<const _Derived>
      {
	__glibcxx_assert(!empty());
	return *ranges::prev(ranges::end(_M_derived()));
      }

      template<random_access_range _Range = _Derived>
	constexpr decltype(auto)
	operator[](range_difference_t<_Range> __n)
	{ return ranges::begin(_M_derived())[__n]; }

      template<random_access_range _Range = const _Derived>
	constexpr decltype(auto)
	operator[](range_difference_t<_Range> __n) const
	{ return ranges::begin(_M_derived())[__n]; }
    };

  namespace __detail
  {
    template<class _From, class _To>
      concept __convertible_to_non_slicing = convertible_to<_From, _To>
	&& !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
	    && __not_same_as<remove_pointer_t<decay_t<_From>>,
			     remove_pointer_t<decay_t<_To>>>);

    template<typename _Tp>
      concept __pair_like
	= !is_reference_v<_Tp> && requires(_Tp __t)
	{
	  typename tuple_size<_Tp>::type;
	  requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
	  typename tuple_element_t<0, remove_const_t<_Tp>>;
	  typename tuple_element_t<1, remove_const_t<_Tp>>;
	  { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
	  { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
	};

    template<typename _Tp, typename _Up, typename _Vp>
      concept __pair_like_convertible_from
	= !range<_Tp> && __pair_like<_Tp>
	&& constructible_from<_Tp, _Up, _Vp>
	&& __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
	&& convertible_to<_Vp, tuple_element_t<1, _Tp>>;

    template<typename _Tp>
      concept __iterator_sentinel_pair
	= !range<_Tp> && __pair_like<_Tp>
	&& sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;

  } // namespace __detail

  enum class subrange_kind : bool { unsized, sized };

  /// The ranges::subrange class template
  template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
	   subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
	     ? subrange_kind::sized : subrange_kind::unsized>
    requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
    class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
    {
    private:
      // XXX: gcc complains when using constexpr here
      static const bool _S_store_size
	= _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;

      _It _M_begin = _It();
      [[no_unique_address]] _Sent _M_end = _Sent();

      template<typename, bool = _S_store_size>
	struct _Size
	{ };

      template<typename _Tp>
	struct _Size<_Tp, true>
	{ __detail::__make_unsigned_like_t<_Tp> _M_size; };

      [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};

    public:
      subrange() = default;

      constexpr
      subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
	requires (!_S_store_size)
      : _M_begin(std::move(__i)), _M_end(__s)
      { }

      constexpr
      subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
	       __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
	requires (_Kind == subrange_kind::sized)
      : _M_begin(std::move(__i)), _M_end(__s)
      {
	using __detail::__to_unsigned_like;
	__glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
	if constexpr (_S_store_size)
	  _M_size._M_size = __n;
      }

      template<__detail::__not_same_as<subrange> _Rng>
	requires borrowed_range<_Rng>
	  && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
	  && convertible_to<sentinel_t<_Rng>, _Sent>
	constexpr
	subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
	: subrange(__r, ranges::size(__r))
	{ }

      template<__detail::__not_same_as<subrange> _Rng>
	requires borrowed_range<_Rng>
	  && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
	  && convertible_to<sentinel_t<_Rng>, _Sent>
	constexpr
	subrange(_Rng&& __r) requires (!_S_store_size)
	: subrange{ranges::begin(__r), ranges::end(__r)}
	{ }

      template<borrowed_range _Rng>
	requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
	  && convertible_to<sentinel_t<_Rng>, _Sent>
	constexpr
	subrange(_Rng&& __r,
		 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
	requires (_Kind == subrange_kind::sized)
	: subrange{ranges::begin(__r), ranges::end(__r), __n}
	{ }

      template<__detail::__not_same_as<subrange> _PairLike>
	requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
							const _Sent&>
      constexpr
      operator _PairLike() const
      { return _PairLike(_M_begin, _M_end); }

      constexpr _It
      begin() const requires copyable<_It>
      { return _M_begin; }

      [[nodiscard]] constexpr _It
      begin() requires (!copyable<_It>)
      { return std::move(_M_begin); }

      constexpr _Sent end() const { return _M_end; }

      constexpr bool empty() const { return _M_begin == _M_end; }

      constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
      size() const requires (_Kind == subrange_kind::sized)
      {
	if constexpr (_S_store_size)
	  return _M_size._M_size;
	else
	  return __detail::__to_unsigned_like(_M_end - _M_begin);
      }

      [[nodiscard]] constexpr subrange
      next(iter_difference_t<_It> __n = 1) const &
	requires forward_iterator<_It>
      {
	auto __tmp = *this;
	__tmp.advance(__n);
	return __tmp;
      }

      [[nodiscard]] constexpr subrange
      next(iter_difference_t<_It> __n = 1) &&
      {
	advance(__n);
	return std::move(*this);
      }

      [[nodiscard]] constexpr subrange
      prev(iter_difference_t<_It> __n = 1) const
	requires bidirectional_iterator<_It>
      {
	auto __tmp = *this;
	__tmp.advance(-__n);
	return __tmp;
      }

      constexpr subrange&
      advance(iter_difference_t<_It> __n)
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 3433. subrange::advance(n) has UB when n < 0
	if constexpr (bidirectional_iterator<_It>)
	  if (__n < 0)
	    {
	      ranges::advance(_M_begin, __n);
	      if constexpr (_S_store_size)
		_M_size._M_size += __detail::__to_unsigned_like(-__n);
	      return *this;
	    }

	__glibcxx_assert(__n >= 0);
	auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
	if constexpr (_S_store_size)
	  _M_size._M_size -= __detail::__to_unsigned_like(__d);
	return *this;
      }
    };

  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
    subrange(_It, _Sent) -> subrange<_It, _Sent>;

  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
    subrange(_It, _Sent,
	     __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
      -> subrange<_It, _Sent, subrange_kind::sized>;

  template<__detail::__iterator_sentinel_pair _Pr>
    subrange(_Pr)
      -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;

  template<__detail::__iterator_sentinel_pair _Pr>
    subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
						     tuple_element_t<0, _Pr>>>)
      -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
		  subrange_kind::sized>;

  template<borrowed_range _Rng>
    subrange(_Rng&&)
      -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
		 (sized_range<_Rng>
		  || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
		 ? subrange_kind::sized : subrange_kind::unsized>;

  template<borrowed_range _Rng>
    subrange(_Rng&&,
	     __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
      -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;

  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
    requires (_Num < 2)
    constexpr auto
    get(const subrange<_It, _Sent, _Kind>& __r)
    {
      if constexpr (_Num == 0)
	return __r.begin();
      else
	return __r.end();
    }

  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
    requires (_Num < 2)
    constexpr auto
    get(subrange<_It, _Sent, _Kind>&& __r)
    {
      if constexpr (_Num == 0)
	return __r.begin();
      else
	return __r.end();
    }

  template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
	   subrange_kind _Kind>
    inline constexpr bool
      enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;

  template<range _Range>
    using borrowed_subrange_t = conditional_t<borrowed_range<_Range>,
					      subrange<iterator_t<_Range>>,
					      dangling>;

} // namespace ranges

  using ranges::get;

  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
    struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
    : integral_constant<size_t, 2>
    { };

  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
    struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
    { using type = _Iter; };

  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
    struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
    { using type = _Sent; };

  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
    struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
    { using type = _Iter; };

  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
    struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
    { using type = _Sent; };

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif // library concepts
#endif // C++20
#endif // _RANGES_UTIL_H
Commit	Line	Data
160061ac JW	1	// Utilities for representing and manipulating ranges -- C++ --
160061ac JW	2
99dee823	3	// Copyright (C) 2019-2021 Free Software Foundation, Inc.
160061ac JW	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 3, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
	24
	25	/** @file bits/ranges_util.h
	26	* This is an internal header file, included by other library headers.
	27	* Do not attempt to use it directly. @headername{ranges}
	28	*/
	29
	30	#ifndef _RANGES_UTIL_H
	31	#define _RANGES_UTIL_H 1
	32
	33	#if __cplusplus > 201703L
	34	# include <bits/ranges_base.h>
	35
	36	#ifdef __cpp_lib_ranges
	37	namespace std _GLIBCXX_VISIBILITY(default)
	38	{
	39	_GLIBCXX_BEGIN_NAMESPACE_VERSION
	40	namespace ranges
	41	{
	42	// C++20 24.5 [range.utility] Range utilities
	43
	44	namespace __detail
	45	{
	46	template<typename _Range>
	47	concept __simple_view = view<_Range> && range<const _Range>
	48	&& same_as<iterator_t<_Range>, iterator_t<const _Range>>
	49	&& same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
	50
	51	template<typename _It>
	52	concept __has_arrow = input_iterator<_It>
	53	&& (is_pointer_v<_It> \|\| requires(_It __it) { __it.operator->(); });
	54
	55	template<typename _Tp, typename _Up>
	56	concept __not_same_as
	57	= !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
	58	} // namespace __detail
	59
	60	/// The ranges::view_interface class template
	61	template<typename _Derived>
	62	requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
	63	class view_interface : public view_base
	64	{
	65	private:
	66	constexpr _Derived& _M_derived() noexcept
	67	{
68	static_assert(derived_from<_Derived, view_interface<_Derived>>);
69	static_assert(view<_Derived>);
70	return static_cast<_Derived&>(*this);
71	}
72
73	constexpr const _Derived& _M_derived() const noexcept
74	{
75	static_assert(derived_from<_Derived, view_interface<_Derived>>);
76	static_assert(view<_Derived>);
77	return static_cast<const _Derived&>(*this);
78	}
79
80	public:
81	constexpr bool
82	empty() requires forward_range<_Derived>
83	{ return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
84
85	constexpr bool
86	empty() const requires forward_range<const _Derived>
87	{ return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
88
89	constexpr explicit
90	operator bool() requires requires { ranges::empty(_M_derived()); }
91	{ return !ranges::empty(_M_derived()); }
92
93	constexpr explicit
94	operator bool() const requires requires { ranges::empty(_M_derived()); }
95	{ return !ranges::empty(_M_derived()); }
96
97	constexpr auto
98	data() requires contiguous_iterator<iterator_t<_Derived>>
99	{ return to_address(ranges::begin(_M_derived())); }
100
101	constexpr auto
102	data() const
103	requires range<const _Derived>
104	&& contiguous_iterator<iterator_t<const _Derived>>
105	{ return to_address(ranges::begin(_M_derived())); }
106
107	constexpr auto
108	size()
109	requires forward_range<_Derived>
110	&& sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
111	{ return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
112
113	constexpr auto
114	size() const
115	requires forward_range<const _Derived>
116	&& sized_sentinel_for<sentinel_t<const _Derived>,
117	iterator_t<const _Derived>>
118	{ return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
119
120	constexpr decltype(auto)
121	front() requires forward_range<_Derived>
122	{
123	__glibcxx_assert(!empty());
124	return *ranges::begin(_M_derived());
125	}
126
127	constexpr decltype(auto)
128	front() const requires forward_range<const _Derived>
129	{
130	__glibcxx_assert(!empty());
131	return *ranges::begin(_M_derived());
132	}
133
134	constexpr decltype(auto)
135	back()
136	requires bidirectional_range<_Derived> && common_range<_Derived>
137	{
138	__glibcxx_assert(!empty());
139	return *ranges::prev(ranges::end(_M_derived()));
140	}
141
142	constexpr decltype(auto)
143	back() const
144	requires bidirectional_range<const _Derived>
145	&& common_range<const _Derived>
146	{
147	__glibcxx_assert(!empty());
148	return *ranges::prev(ranges::end(_M_derived()));
149	}
150
151	template<random_access_range _Range = _Derived>
152	constexpr decltype(auto)
153	operator[](range_difference_t<_Range> __n)
154	{ return ranges::begin(_M_derived())[__n]; }
155
156	template<random_access_range _Range = const _Derived>
157	constexpr decltype(auto)
158	operator[](range_difference_t<_Range> __n) const
159	{ return ranges::begin(_M_derived())[__n]; }
160	};
161
162	namespace __detail
163	{
164	template<class _From, class _To>
165	concept __convertible_to_non_slicing = convertible_to<_From, _To>
166	&& !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
167	&& __not_same_as<remove_pointer_t<decay_t<_From>>,
168	remove_pointer_t<decay_t<_To>>>);
169
170	template<typename _Tp>
171	concept __pair_like
172	= !is_reference_v<_Tp> && requires(_Tp __t)
173	{
174	typename tuple_size<_Tp>::type;
175	requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
176	typename tuple_element_t<0, remove_const_t<_Tp>>;
177	typename tuple_element_t<1, remove_const_t<_Tp>>;
178	{ get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
179	{ get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
180	};
181
182	template<typename _Tp, typename _Up, typename _Vp>
183	concept __pair_like_convertible_from
184	= !range<_Tp> && __pair_like<_Tp>
185	&& constructible_from<_Tp, _Up, _Vp>
186	&& __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
187	&& convertible_to<_Vp, tuple_element_t<1, _Tp>>;
188
189	template<typename _Tp>
190	concept __iterator_sentinel_pair
191	= !range<_Tp> && __pair_like<_Tp>
192	&& sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
193
194	} // namespace __detail
195
196	enum class subrange_kind : bool { unsized, sized };
197
198	/// The ranges::subrange class template
199	template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
200	subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
201	? subrange_kind::sized : subrange_kind::unsized>
202	requires (_Kind == subrange_kind::sized \|\| !sized_sentinel_for<_Sent, _It>)
203	class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
204	{
205	private:
206	// XXX: gcc complains when using constexpr here
207	static const bool _S_store_size
208	= _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
209
210	_It _M_begin = _It();
620db4ca	211	[[no_unique_address]] _Sent _M_end = _Sent();
160061ac JW	212
	213	template<typename, bool = _S_store_size>
	214	struct _Size
	215	{ };
	216
	217	template<typename _Tp>
	218	struct _Size<_Tp, true>
	219	{ __detail::__make_unsigned_like_t<_Tp> _M_size; };
	220
	221	[[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
	222
	223	public:
	224	subrange() = default;
	225
	226	constexpr
	227	subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
	228	requires (!_S_store_size)
	229	: _M_begin(std::move(__i)), _M_end(__s)
	230	{ }
	231
	232	constexpr
	233	subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
	234	__detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
	235	requires (_Kind == subrange_kind::sized)
	236	: _M_begin(std::move(__i)), _M_end(__s)
	237	{
	238	using __detail::__to_unsigned_like;
	239	__glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
	240	if constexpr (_S_store_size)
	241	_M_size._M_size = __n;
	242	}
	243
	244	template<__detail::__not_same_as<subrange> _Rng>
	245	requires borrowed_range<_Rng>
	246	&& __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
	247	&& convertible_to<sentinel_t<_Rng>, _Sent>
	248	constexpr
	249	subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
a55cda89	250	: subrange(__r, ranges::size(__r))
160061ac JW	251	{ }
	252
	253	template<__detail::__not_same_as<subrange> _Rng>
	254	requires borrowed_range<_Rng>
	255	&& __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
	256	&& convertible_to<sentinel_t<_Rng>, _Sent>
	257	constexpr
	258	subrange(_Rng&& __r) requires (!_S_store_size)
	259	: subrange{ranges::begin(__r), ranges::end(__r)}
	260	{ }
	261
	262	template<borrowed_range _Rng>
	263	requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
	264	&& convertible_to<sentinel_t<_Rng>, _Sent>
	265	constexpr
	266	subrange(_Rng&& __r,
	267	__detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
	268	requires (_Kind == subrange_kind::sized)
	269	: subrange{ranges::begin(__r), ranges::end(__r), __n}
	270	{ }
	271
	272	template<__detail::__not_same_as<subrange> _PairLike>
	273	requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
	274	const _Sent&>
	275	constexpr
	276	operator _PairLike() const
	277	{ return _PairLike(_M_begin, _M_end); }
	278
	279	constexpr _It
	280	begin() const requires copyable<_It>
	281	{ return _M_begin; }
	282
	283	[[nodiscard]] constexpr _It
	284	begin() requires (!copyable<_It>)
	285	{ return std::move(_M_begin); }
	286
	287	constexpr _Sent end() const { return _M_end; }
	288
	289	constexpr bool empty() const { return _M_begin == _M_end; }
	290
	291	constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
	292	size() const requires (_Kind == subrange_kind::sized)
	293	{
	294	if constexpr (_S_store_size)
	295	return _M_size._M_size;
	296	else
	297	return __detail::__to_unsigned_like(_M_end - _M_begin);
	298	}
	299
	300	[[nodiscard]] constexpr subrange
	301	next(iter_difference_t<_It> __n = 1) const &
	302	requires forward_iterator<_It>
	303	{
	304	auto __tmp = *this;
	305	__tmp.advance(__n);
	306	return __tmp;
	307	}
	308
	309	[[nodiscard]] constexpr subrange
	310	next(iter_difference_t<_It> __n = 1) &&
	311	{
	312	advance(__n);
	313	return std::move(*this);
	314	}
315
316	[[nodiscard]] constexpr subrange
317	prev(iter_difference_t<_It> __n = 1) const
318	requires bidirectional_iterator<_It>
319	{
320	auto __tmp = *this;
321	__tmp.advance(-__n);
322	return __tmp;
323	}
324
325	constexpr subrange&
326	advance(iter_difference_t<_It> __n)
327	{
328	// _GLIBCXX_RESOLVE_LIB_DEFECTS
329	// 3433. subrange::advance(n) has UB when n < 0
330	if constexpr (bidirectional_iterator<_It>)
331	if (__n < 0)
332	{
333	ranges::advance(_M_begin, __n);
334	if constexpr (_S_store_size)
335	_M_size._M_size += __detail::__to_unsigned_like(-__n);
336	return *this;
337	}
338
339	__glibcxx_assert(__n >= 0);
340	auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
341	if constexpr (_S_store_size)
342	_M_size._M_size -= __detail::__to_unsigned_like(__d);
343	return *this;
344	}
345	};
346
347	template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
348	subrange(_It, _Sent) -> subrange<_It, _Sent>;
349
350	template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
351	subrange(_It, _Sent,
352	__detail::__make_unsigned_like_t<iter_difference_t<_It>>)
353	-> subrange<_It, _Sent, subrange_kind::sized>;
354
355	template<__detail::__iterator_sentinel_pair _Pr>
356	subrange(_Pr)
357	-> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
358
359	template<__detail::__iterator_sentinel_pair _Pr>
360	subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
361	tuple_element_t<0, _Pr>>>)
362	-> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
363	subrange_kind::sized>;
364
365	template<borrowed_range _Rng>
366	subrange(_Rng&&)
367	-> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
368	(sized_range<_Rng>
369	\|\| sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
370	? subrange_kind::sized : subrange_kind::unsized>;
371
372	template<borrowed_range _Rng>
373	subrange(_Rng&&,
374	__detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
375	-> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
376
377	template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
378	requires (_Num < 2)
379	constexpr auto
380	get(const subrange<_It, _Sent, _Kind>& __r)
381	{
382	if constexpr (_Num == 0)
383	return __r.begin();
384	else
385	return __r.end();
386	}
387
388	template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
389	requires (_Num < 2)
390	constexpr auto
391	get(subrange<_It, _Sent, _Kind>&& __r)
392	{
393	if constexpr (_Num == 0)
394	return __r.begin();
395	else
396	return __r.end();
397	}
398
399	template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
400	subrange_kind _Kind>
401	inline constexpr bool
402	enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
403
404	template<range _Range>
405	using borrowed_subrange_t = conditional_t<borrowed_range<_Range>,
406	subrange<iterator_t<_Range>>,
407	dangling>;
408
409	} // namespace ranges
410
411	using ranges::get;
412
a186ab67 JW	413	template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
	414	struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
	415	: integral_constant<size_t, 2>
	416	{ };
	417
	418	template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
	419	struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
	420	{ using type = _Iter; };
	421
	422	template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
	423	struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
	424	{ using type = _Sent; };
	425
	426	template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
	427	struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
	428	{ using type = _Iter; };
	429
	430	template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
	431	struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
	432	{ using type = _Sent; };
	433
160061ac JW	434	_GLIBCXX_END_NAMESPACE_VERSION
	435	} // namespace std
	436	#endif // library concepts
	437	#endif // C++20
	438	#endif // _RANGES_UTIL_H