1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
10#define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
11
12#include <__algorithm/min.h>
13#include <__algorithm/three_way_comp_ref_type.h>
14#include <__compare/compare_three_way.h>
15#include <__compare/ordering.h>
16#include <__concepts/arithmetic.h>
17#include <__config>
18#include <__iterator/iterator_traits.h>
19#include <__type_traits/common_type.h>
20#include <__type_traits/is_copy_constructible.h>
21#include <__utility/move.h>
22
23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
24#  pragma GCC system_header
25#endif
26
27_LIBCPP_PUSH_MACROS
28#include <__undef_macros>
29
30_LIBCPP_BEGIN_NAMESPACE_STD
31
32#if _LIBCPP_STD_VER >= 20
33
34// Fast path for random access iterators which computes the number of loop iterations up-front and
35// then skips the iterator comparisons inside the loop.
36template <class _InputIterator1, class _InputIterator2, class _Cmp>
37_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(
38    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
39    -> decltype(__comp(*__first1, *__first2)) {
40  static_assert(
41      signed_integral<__iter_diff_t<_InputIterator1>>, "Using a non-integral difference_type is undefined behavior.");
42  static_assert(
43      signed_integral<__iter_diff_t<_InputIterator2>>, "Using a non-integral difference_type is undefined behavior.");
44
45  using _Len1   = __iter_diff_t<_InputIterator1>;
46  using _Len2   = __iter_diff_t<_InputIterator2>;
47  using _Common = common_type_t<_Len1, _Len2>;
48
49  _Len1 __len1      = __last1 - __first1;
50  _Len2 __len2      = __last2 - __first2;
51  _Common __min_len = std::min<_Common>(__len1, __len2);
52
53  for (_Common __i = 0; __i < __min_len; ++__i) {
54    auto __c = __comp(*__first1, *__first2);
55    if (__c != 0) {
56      return __c;
57    }
58    ++__first1;
59    ++__first2;
60  }
61
62  return __len1 <=> __len2;
63}
64
65// Unoptimized implementation which compares the iterators against the end in every loop iteration
66template <class _InputIterator1, class _InputIterator2, class _Cmp>
67_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_slow_path(
68    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
69    -> decltype(__comp(*__first1, *__first2)) {
70  while (true) {
71    bool __exhausted1 = __first1 == __last1;
72    bool __exhausted2 = __first2 == __last2;
73
74    if (__exhausted1 || __exhausted2) {
75      if (!__exhausted1)
76        return strong_ordering::greater;
77      if (!__exhausted2)
78        return strong_ordering::less;
79      return strong_ordering::equal;
80    }
81
82    auto __c = __comp(*__first1, *__first2);
83    if (__c != 0) {
84      return __c;
85    }
86
87    ++__first1;
88    ++__first2;
89  }
90}
91
92template <class _InputIterator1, class _InputIterator2, class _Cmp>
93_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
94    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp __comp)
95    -> decltype(__comp(*__first1, *__first2)) {
96  static_assert(__comparison_category<decltype(__comp(*__first1, *__first2))>,
97                "The comparator passed to lexicographical_compare_three_way must return a comparison category type.");
98  static_assert(std::is_copy_constructible_v<_InputIterator1>, "Iterators must be copy constructible.");
99  static_assert(std::is_copy_constructible_v<_InputIterator2>, "Iterators must be copy constructible.");
100  __three_way_comp_ref_type<_Cmp> __wrapped_comp_ref(__comp);
101  if constexpr (__has_random_access_iterator_category<_InputIterator1>::value &&
102                __has_random_access_iterator_category<_InputIterator2>::value) {
103    return std::__lexicographical_compare_three_way_fast_path(
104        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
105  } else {
106    // Unoptimized implementation which compares the iterators against the end in every loop iteration
107    return std::__lexicographical_compare_three_way_slow_path(
108        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
109  }
110}
111
112template <class _InputIterator1, class _InputIterator2>
113_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
114    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
115  return std::lexicographical_compare_three_way(
116      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::compare_three_way());
117}
118
119#endif // _LIBCPP_STD_VER >= 20
120
121_LIBCPP_END_NAMESPACE_STD
122
123_LIBCPP_POP_MACROS
124
125#endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
126