Index: libcxx/include/algorithm =================================================================== --- libcxx/include/algorithm +++ libcxx/include/algorithm @@ -615,6 +615,17 @@ lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); +template + constexpr auto + lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2); + +template + constexpr auto + lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2, Compare comp) + -> decltype(comp(*first1, *first2)); + template bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); @@ -647,6 +658,10 @@ #include #include +#ifndef _LIBCPP_HAS_NO_SPACESHIP_OPERATOR +#include +#endif // _LIBCPP_HAS_NO_SPACESHIP_OPERATOR + #include <__debug> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -5608,6 +5623,30 @@ typename iterator_traits<_InputIterator2>::value_type>()); } +// lexicographical_compare_three_way +#ifndef _LIBCPP_HAS_NO_SPACESHIP_OPERATOR +template +constexpr auto lexicographical_compare_three_way(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _Compare __comp) -> decltype(__comp(*__first1, *__first2)) +{ + for (; __first1 != __last1 && __first2 != __last2; void(++__first1), void(++__first2)) + if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0) + return __cmp; + return __first1 != __last1 ? strong_ordering::greater : + __first2 != __last2 ? strong_ordering::less : + strong_ordering::equal; +} + +template +constexpr auto lexicographical_compare_three_way(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2) +{ + return _VSTD::lexicographical_compare_three_way(__first1, __last1, __first2, __last2, + compare_three_way()); +} +#endif // _LIBCPP_HAS_NO_SPACESHIP_OPERATOR + // next_permutation template Index: libcxx/include/compare =================================================================== --- libcxx/include/compare +++ libcxx/include/compare @@ -48,7 +48,6 @@ #include <__config> #include -#include #ifndef _LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER #pragma GCC system_header @@ -618,10 +617,10 @@ template constexpr _ClassifyCompCategory -__compute_comp_type(std::array<_ClassifyCompCategory, _Size> __types) { - std::array __seen = {}; - for (auto __type : __types) - ++__seen[__type]; +__compute_comp_type(const _ClassifyCompCategory* __types) { + int __seen[_CCC_Size] = {}; + for (size_t __i = 0; __i < _Size; ++__i) + ++__seen[__types[__i]]; if (__seen[_None]) return _None; if (__seen[_WeakEq]) @@ -640,9 +639,9 @@ template constexpr auto __get_comp_type() { using _CCC = _ClassifyCompCategory; - constexpr array<_CCC, sizeof...(_Ts)> __type_kinds{{__comp_detail::__type_to_enum<_Ts>()...}}; + constexpr _CCC __type_kinds[sizeof...(_Ts)] = {__comp_detail::__type_to_enum<_Ts>()...}; constexpr _CCC _Cat = sizeof...(_Ts) == 0 ? _StrongOrd - : __compute_comp_type(__type_kinds); + : __compute_comp_type(__type_kinds); if constexpr (_Cat == _None) return void(); else if constexpr (_Cat == _WeakEq) Index: libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp @@ -0,0 +1,126 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template +// constexpr auto +// lexicographical_compare(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2); + +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" + +TEST_CONSTEXPR bool test_constexpr() { + std::array ia{1, 2, 3}; + std::array ib{1, 3, 5, 2, 4, 6}; + + const auto ia_less_ib = std::lexicographical_compare_three_way( + std::begin(ia), std::end(ia), std::begin(ib), std::end(ib)); + const auto ib_equal_ib = std::lexicographical_compare_three_way( + std::begin(ib), std::end(ib), std::begin(ib), std::end(ib)); + const auto ib_greater_ia = std::lexicographical_compare_three_way( + std::begin(ib), std::end(ib), std::begin(ia), std::end(ia)); + return ia_less_ib == std::strong_ordering::less && + ib_greater_ia == std::strong_ordering::greater && + ib_equal_ib == std::strong_ordering::equal; +} + +template +void test_less(std::array& a, std::array& b) { + assert(std::lexicographical_compare_three_way( + Iter1(b.begin()), Iter1(b.end() - 1), Iter2(a.begin()), + Iter2(a.end())) == std::strong_ordering::less); + + assert(std::lexicographical_compare_three_way( + Iter1(b.begin()), Iter1(b.end()), Iter2(a.begin()), + Iter2(a.end())) == std::strong_ordering::less); + + assert(std::lexicographical_compare_three_way( + Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin() + 1), + Iter2(b.end())) == std::strong_ordering::less); +} + +template +void test_equal(R& a, R& b) { + assert(std::lexicographical_compare_three_way( + Iter1(b.begin()), Iter1(b.end()), Iter2(a.begin()), + Iter2(a.end())) == std::strong_ordering::equal); +} + +template +void test_greater(std::array& a, std::array& b) { + assert(std::lexicographical_compare_three_way( + Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin()), + Iter2(b.end() - 1)) == std::strong_ordering::greater); + + assert(std::lexicographical_compare_three_way( + Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin()), + Iter2(b.end())) == std::strong_ordering::greater); + + assert(std::lexicographical_compare_three_way( + Iter1(b.begin() + 1), Iter1(b.end()), Iter2(a.begin()), + Iter2(a.end())) == std::strong_ordering::greater); +} + +template +void test() { + std::array a{1, 2, 3, 4}; + std::array b{1, 2, 3}; + + test_less(a, b); + test_equal(a, a); + test_equal(b, b); + test_greater(a, b); +} + +int main(int, char**) { + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + test, const int*>(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + test, const int*>(); + + test, input_iterator >(); + test, forward_iterator >(); + test, + bidirectional_iterator >(); + test, + random_access_iterator >(); + test, const int*>(); + + test, input_iterator >(); + test, forward_iterator >(); + test, + bidirectional_iterator >(); + test, + random_access_iterator >(); + test, const int*>(); + + test >(); + test >(); + test >(); + test >(); + test(); + + static_assert(test_constexpr()); + + return 0; +} Index: libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp @@ -0,0 +1,108 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template +// constexpr auto +// lexicographical_compare_three_way(Iter1 first1, Iter1 last1, +// Iter2 first2, Iter2 last2, Compare comp) +// -> decltype(comp(*first1, *first2)); + +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" + +// "simulates" use of std::greater in lex.comparison comp test +auto comp = [](int x, int y) { + return static_cast(y <=> x); +}; + +TEST_CONSTEXPR bool test_constexpr() { + int ia[] = {1, 2, 3}; + int ib[] = {1, 3, 5, 2, 4, 6}; + + return std::lexicographical_compare_three_way( + std::begin(ia), std::end(ia), std::begin(ib), std::end(ib), + comp) == std::weak_ordering::greater && + std::lexicographical_compare_three_way( + std::begin(ib), std::end(ib), std::begin(ia), std::end(ia), + comp) == std::weak_ordering::less; +} + +template +void test() { + int ia[] = {1, 2, 3, 4}; + const unsigned sa = sizeof(ia) / sizeof(ia[0]); + int ib[] = {1, 2, 3}; + + // range ib is shorter than ia; all values are the same. + assert(std::lexicographical_compare_three_way( + Iter1(ia), Iter1(ia + sa), Iter2(ib), Iter2(ib + 2), comp) == + std::weak_ordering::greater); + assert(std::lexicographical_compare_three_way( + Iter1(ib), Iter1(ib + 2), Iter2(ia), Iter2(ia + sa), comp) == + std::weak_ordering::less); + assert(std::lexicographical_compare_three_way( + Iter1(ia), Iter1(ia + sa), Iter2(ib), Iter2(ib + 3), comp) == + std::weak_ordering::greater); + assert(std::lexicographical_compare_three_way( + Iter1(ib), Iter1(ib + 3), Iter2(ia), Iter2(ia + sa), comp) == + std::weak_ordering::less); + + // range ib starts with a greater value than ia. + assert(std::lexicographical_compare_three_way( + Iter1(ia), Iter1(ia + sa), Iter2(ib + 1), Iter2(ib + 3), comp) == + std::weak_ordering::greater); + assert(std::lexicographical_compare_three_way( + Iter1(ib + 1), Iter1(ib + 3), Iter2(ia), Iter2(ia + sa), comp) == + std::weak_ordering::less); +} + +int main(int, char**) { + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + test, const int*>(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + test, const int*>(); + + test, input_iterator >(); + test, forward_iterator >(); + test, + bidirectional_iterator >(); + test, + random_access_iterator >(); + test, const int*>(); + + test, input_iterator >(); + test, forward_iterator >(); + test, + bidirectional_iterator >(); + test, + random_access_iterator >(); + test, const int*>(); + + test >(); + test >(); + test >(); + test >(); + test(); + + static_assert(test_constexpr()); + + return 0; +}