aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_minmax.h
blob: 2f4bba0e7cc082ed46edb5eb3603b078a74ef995 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___ALGORITHM_RANGES_MINMAX_H
#define _LIBCPP___ALGORITHM_RANGES_MINMAX_H

#include <__algorithm/min_max_result.h>
#include <__algorithm/minmax_element.h>
#include <__assert>
#include <__concepts/copyable.h>
#include <__config>
#include <__functional/identity.h>
#include <__functional/invoke.h>
#include <__functional/ranges_operations.h>
#include <__iterator/concepts.h>
#include <__iterator/projected.h>
#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__utility/forward.h>
#include <__utility/move.h>
#include <initializer_list>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

_LIBCPP_PUSH_MACROS
#include <__undef_macros>

_LIBCPP_BEGIN_NAMESPACE_STD

namespace ranges {
template <class _T1>
using minmax_result = min_max_result<_T1>;

namespace __minmax {
struct __fn {
  template <class _Type, class _Proj = identity,
            indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
  _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<const _Type&>
  operator()(const _Type& __a, const _Type& __b, _Comp __comp = {}, _Proj __proj = {}) const {
    if (std::invoke(__comp, std::invoke(__proj, __b), std::invoke(__proj, __a)))
      return {__b, __a};
    return {__a, __b};
  }

  template <copyable _Type, class _Proj = identity,
            indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
  _LIBCPP_HIDE_FROM_ABI constexpr
  ranges::minmax_result<_Type> operator()(initializer_list<_Type> __il, _Comp __comp = {}, _Proj __proj = {}) const {
    _LIBCPP_ASSERT(__il.begin() != __il.end(), "initializer_list has to contain at least one element");
    auto __iters = std::__minmax_element_impl(__il.begin(), __il.end(), __comp, __proj);
    return ranges::minmax_result<_Type> { *__iters.first, *__iters.second };
  }

  template <input_range _Range, class _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>*>
  _LIBCPP_HIDE_FROM_ABI constexpr
  ranges::minmax_result<range_value_t<_Range>> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
    auto __first = ranges::begin(__r);
    auto __last = ranges::end(__r);
    using _ValueT = range_value_t<_Range>;

    _LIBCPP_ASSERT(__first != __last, "range has to contain at least one element");

    if constexpr (forward_range<_Range>) {
      auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj);
      return {*__result.first, *__result.second};
    } else {
      // input_iterators can't be copied, so the implementation for input_iterators has to store
      // the values instead of a pointer to the correct values
      auto __less = [&](auto&& __a, auto&& __b) -> bool {
        return std::invoke(__comp, std::invoke(__proj, std::forward<decltype(__a)>(__a)),
                                   std::invoke(__proj, std::forward<decltype(__b)>(__b)));
      };

      ranges::minmax_result<_ValueT> __result = {*__first, __result.min};
      if (__first == __last || ++__first == __last)
        return __result;

      if (__less(*__first, __result.min))
        __result.min = *__first;
      else
        __result.max = *__first;

      while (++__first != __last) {
        _ValueT __i = *__first;
        if (++__first == __last) {
          if (__less(__i, __result.min))
            __result.min = __i;
          else if (!__less(__i, __result.max))
            __result.max = __i;
          return __result;
        }

        if (__less(*__first, __i)) {
          if (__less(*__first, __result.min))
            __result.min = *__first;
          if (!__less(__i, __result.max))
            __result.max = std::move(__i);
        } else {
          if (__less(__i, __result.min))
            __result.min = std::move(__i);
          if (!__less(*__first, __result.max))
            __result.max = *__first;
        }
      }
      return __result;
    }
  }
};
} // namespace __minmax

inline namespace __cpo {
  inline constexpr auto minmax = __minmax::__fn{};
} // namespace __cpo
} // namespace ranges

_LIBCPP_END_NAMESPACE_STD

_LIBCPP_POP_MACROS

#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

#endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H