| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // UNSUPPORTED: c++03, c++11, c++14, c++17 |
| |
| // <algorithm> |
| |
| // template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, |
| // class Proj = identity> |
| // requires sortable<I, Comp, Proj> |
| // I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 |
| // |
| // template<random_access_range R, class Comp = ranges::less, class Proj = identity> |
| // requires sortable<iterator_t<R>, Comp, Proj> |
| // borrowed_iterator_t<R> |
| // ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 |
| |
| #include <algorithm> |
| #include <array> |
| #include <concepts> |
| #include <functional> |
| #include <ranges> |
| |
| #include "almost_satisfies_types.h" |
| #include "boolean_testable.h" |
| #include "test_iterators.h" |
| |
| // SFINAE tests. |
| |
| using BadComparator = ComparatorNotCopyable<int*>; |
| static_assert(!std::sortable<int*, BadComparator>); |
| |
| template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less> |
| concept HasStableSortIt = requires(Iter first, Sent last, Comp comp) { std::ranges::stable_sort(first, last, comp); }; |
| |
| static_assert(HasStableSortIt<int*>); |
| static_assert(!HasStableSortIt<RandomAccessIteratorNotDerivedFrom>); |
| static_assert(!HasStableSortIt<RandomAccessIteratorBadIndex>); |
| static_assert(!HasStableSortIt<int*, SentinelForNotSemiregular>); |
| static_assert(!HasStableSortIt<int*, SentinelForNotWeaklyEqualityComparableWith>); |
| static_assert(!HasStableSortIt<int*, int*, BadComparator>); |
| static_assert(!HasStableSortIt<const int*>); // Doesn't satisfy `sortable`. |
| |
| template <class Range, class Comp = std::ranges::less> |
| concept HasStableSortR = requires(Range range, Comp comp) { std::ranges::stable_sort(range, comp); }; |
| |
| static_assert(HasStableSortR<UncheckedRange<int*>>); |
| static_assert(!HasStableSortR<RandomAccessRangeNotDerivedFrom>); |
| static_assert(!HasStableSortR<RandomAccessRangeBadIndex>); |
| static_assert(!HasStableSortR<UncheckedRange<int*, SentinelForNotSemiregular>>); |
| static_assert(!HasStableSortR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>); |
| static_assert(!HasStableSortR<UncheckedRange<int*>, BadComparator>); |
| static_assert(!HasStableSortR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`. |
| |
| template <class Iter, class Sent, std::size_t N> |
| void test_one(std::array<int, N> input, std::array<int, N> expected) { |
| { // (iterator, sentinel) overload. |
| auto sorted = input; |
| auto b = Iter(sorted.data()); |
| auto e = Sent(Iter(sorted.data() + sorted.size())); |
| |
| std::same_as<Iter> decltype(auto) last = std::ranges::stable_sort(b, e); |
| assert(sorted == expected); |
| assert(base(last) == sorted.data() + sorted.size()); |
| } |
| |
| { // (range) overload. |
| auto sorted = input; |
| auto b = Iter(sorted.data()); |
| auto e = Sent(Iter(sorted.data() + sorted.size())); |
| auto range = std::ranges::subrange(b, e); |
| |
| std::same_as<Iter> decltype(auto) last = std::ranges::stable_sort(range); |
| assert(sorted == expected); |
| assert(base(last) == sorted.data() + sorted.size()); |
| } |
| } |
| |
| template <class Iter, class Sent> |
| void test_iterators_2() { |
| // Empty sequence. |
| test_one<Iter, Sent, 0>({}, {}); |
| // 1-element sequence. |
| test_one<Iter, Sent, 1>({1}, {1}); |
| // 2-element sequence. |
| test_one<Iter, Sent, 2>({2, 1}, {1, 2}); |
| // 3-element sequence. |
| test_one<Iter, Sent, 3>({2, 1, 3}, {1, 2, 3}); |
| // Longer sequence. |
| test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, {1, 2, 3, 4, 5, 6, 8, 11}); |
| // Longer sequence with duplicates. |
| test_one<Iter, Sent, 7>({2, 1, 3, 6, 2, 8, 6}, {1, 2, 2, 3, 6, 6, 8}); |
| // All elements are the same. |
| test_one<Iter, Sent, 3>({1, 1, 1}, {1, 1, 1}); |
| // Already sorted. |
| test_one<Iter, Sent, 5>({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}); |
| // Reverse-sorted. |
| test_one<Iter, Sent, 5>({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}); |
| // Repeating pattern. |
| test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, {1, 1, 1, 2, 2, 2}); |
| } |
| |
| template <class Iter> |
| void test_iterators_1() { |
| test_iterators_2<Iter, Iter>(); |
| test_iterators_2<Iter, sentinel_wrapper<Iter>>(); |
| } |
| |
| void test_iterators() { |
| test_iterators_1<random_access_iterator<int*>>(); |
| test_iterators_1<contiguous_iterator<int*>>(); |
| test_iterators_1<int*>(); |
| } |
| |
| void test() { |
| test_iterators(); |
| |
| struct OrderedValue { |
| int value; |
| double original_order; |
| bool operator==(const OrderedValue&) const = default; |
| auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; } |
| }; |
| |
| { // The sort is stable (equivalent elements remain in the same order). |
| using V = OrderedValue; |
| using Array = std::array<V, 20>; |
| Array orig_in = { |
| V{10, 10.1}, {12, 12.1}, {3, 3.1}, {5, 5.1}, {3, 3.2}, {3, 3.3}, {11, 11.1}, {12, 12.2}, {4, 4.1}, {4, 4.2}, |
| {4, 4.3}, {1, 1.1}, {6, 6.1}, {3, 3.4}, {10, 10.2}, {8, 8.1}, {12, 12.3}, {1, 1.2}, {1, 1.3}, {5, 5.2} |
| }; |
| Array expected = { |
| V{1, 1.1}, {1, 1.2}, {1, 1.3}, |
| {3, 3.1}, {3, 3.2}, {3, 3.3}, {3, 3.4}, |
| {4, 4.1}, {4, 4.2}, {4, 4.3}, |
| {5, 5.1}, {5, 5.2}, |
| {6, 6.1}, |
| {8, 8.1}, |
| {10, 10.1}, {10, 10.2}, |
| {11, 11.1}, |
| {12, 12.1}, {12, 12.2}, {12, 12.3} |
| }; |
| |
| { |
| auto in = orig_in; |
| auto last = std::ranges::stable_sort(in.begin(), in.end()); |
| assert(in == expected); |
| assert(last == in.end()); |
| } |
| |
| { |
| auto in = orig_in; |
| auto last = std::ranges::stable_sort(in); |
| assert(in == expected); |
| assert(last == in.end()); |
| } |
| } |
| |
| { // A custom comparator works and is stable. |
| using V = OrderedValue; |
| using Array = std::array<V, 11>; |
| |
| Array orig_in = { |
| V{1, 1.1}, {2, 2.1}, {2, 2.2}, {3, 3.1}, {2, 2.3}, {3, 3.2}, {4, 4.1}, {5, 5.1}, {2, 2.4}, {5, 5.2}, {1, 1.2} |
| }; |
| Array expected = { |
| V{5, 5.1}, {5, 5.2}, |
| {4, 4.1}, |
| {3, 3.1}, {3, 3.2}, |
| {2, 2.1}, {2, 2.2}, {2, 2.3}, {2, 2.4}, |
| {1, 1.1}, {1, 1.2} |
| }; |
| |
| { |
| auto in = orig_in; |
| auto last = std::ranges::stable_sort(in.begin(), in.end(), std::greater{}); |
| assert(in == expected); |
| assert(last == in.end()); |
| } |
| |
| { |
| auto in = orig_in; |
| auto last = std::ranges::stable_sort(in, std::greater{}); |
| assert(in == expected); |
| assert(last == in.end()); |
| } |
| } |
| |
| { // A custom projection works. |
| struct A { |
| int a; |
| bool operator==(const A&) const = default; |
| }; |
| |
| { |
| std::array in = {A{2}, A{3}, A{1}}; |
| auto last = std::ranges::stable_sort(in.begin(), in.end(), {}, &A::a); |
| assert((in == std::array{A{1}, A{2}, A{3}})); |
| assert(last == in.end()); |
| } |
| |
| { |
| std::array in = {A{2}, A{3}, A{1}}; |
| auto last = std::ranges::stable_sort(in, {}, &A::a); |
| assert((in == std::array{A{1}, A{2}, A{3}})); |
| assert(last == in.end()); |
| } |
| } |
| |
| { // `std::invoke` is used in the implementation. |
| struct S { |
| int i; |
| S(int i_) : i(i_) {} |
| |
| bool comparator(const S& rhs) const { return i < rhs.i; } |
| const S& projection() const { return *this; } |
| |
| bool operator==(const S&) const = default; |
| }; |
| |
| { |
| std::array in = {S{2}, S{3}, S{1}}; |
| auto last = std::ranges::stable_sort(in.begin(), in.end(), &S::comparator, &S::projection); |
| assert((in == std::array{S{1}, S{2}, S{3}})); |
| assert(last == in.end()); |
| } |
| |
| { |
| std::array in = {S{2}, S{3}, S{1}}; |
| auto last = std::ranges::stable_sort(in, &S::comparator, &S::projection); |
| assert((in == std::array{S{1}, S{2}, S{3}})); |
| assert(last == in.end()); |
| } |
| } |
| |
| { // The comparator can return any type that's convertible to `bool`. |
| { |
| std::array in = {2, 1, 3}; |
| auto last = std::ranges::stable_sort(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; }); |
| assert((in == std::array{1, 2, 3})); |
| assert(last == in.end()); |
| } |
| |
| { |
| std::array in = {2, 1, 3}; |
| auto last = std::ranges::stable_sort(in, [](int i, int j) { return BooleanTestable{i < j}; }); |
| assert((in == std::array{1, 2, 3})); |
| assert(last == in.end()); |
| } |
| } |
| |
| { // `std::ranges::dangling` is returned. |
| [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result = |
| std::ranges::stable_sort(std::array{1, 2, 3}); |
| } |
| |
| // TODO: Enable the tests once the implementation switched to use iter_move/iter_swap |
| /* |
| { // ProxyIterator |
| { |
| std::array in = {2, 1, 3}; |
| ProxyRange proxy{in}; |
| |
| std::ranges::stable_sort(proxy.begin(), proxy.end(), [](auto i, auto j) { return i.data < j.data; }); |
| assert((in == std::array{1, 2, 3})); |
| } |
| |
| { |
| std::array in = {2, 1, 3}; |
| ProxyRange proxy{in}; |
| std::ranges::stable_sort(proxy, [](auto i, auto j) { return i.data < j.data; }); |
| assert((in == std::array{1, 2, 3})); |
| } |
| } |
| */ |
| } |
| |
| int main(int, char**) { |
| test(); |
| // Note: `stable_sort` is not `constexpr`. |
| |
| return 0; |
| } |