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.
36 template <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
66 template <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 
92 template <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 
112 template <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