//===----------------------------------------------------------------------===//
//
// 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<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
// class Proj = identity>
// requires sortable<I, Comp, Proj>
// I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); // Since C++20
//
// template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
// requires sortable<iterator_t<R>, Comp, Proj>
// borrowed_iterator_t<R>
// inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {},
// Proj proj = {}); // Since C++20
#include <algorithm>
#include <array>
#include <concepts>
#include <functional>
#include <ranges>
#include <type_traits>
#include "almost_satisfies_types.h"
#include "counting_predicates.h"
#include "counting_projection.h"
#include "test_iterators.h"
template < class Iter,
class Middle = Iter,
class Sent = sentinel_wrapper<std::remove_cvref_t<Iter>>,
class Comp = std::ranges::less,
class Proj = std::identity>
concept HasInplaceMergeIter =
requires(Iter&& iter, Middle&& mid, Sent&& sent, Comp&& comp, Proj&& proj) {
std::ranges::inplace_merge(
std::forward<Iter>(iter),
std::forward<Middle>(mid),
std::forward<Sent>(sent),
std::forward<Comp>(comp),
std::forward<Proj>(proj));
};
static_assert(HasInplaceMergeIter<int*, int*, int*>);
// !bidirectional_iterator<I>
static_assert(!HasInplaceMergeIter<BidirectionalIteratorNotDerivedFrom>);
static_assert(!HasInplaceMergeIter<cpp20_input_iterator<int*>>);
// !sentinel_for<S, I>
static_assert(!HasInplaceMergeIter<int*, int*, SentinelForNotSemiregular>);
static_assert(!HasInplaceMergeIter<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
// !sortable<I, Comp, Proj>
static_assert(!HasInplaceMergeIter<int*, int*, int*, ComparatorNotCopyable<int*>>);
static_assert(!HasInplaceMergeIter<const int*, const int*, const int*>);
template < class Range,
class Middle = std::ranges::iterator_t<Range>,
class Comp = std::ranges::less,
class Proj = std::identity>
concept HasInplaceMergeRange =
requires(Range&& r, Middle&& mid, Comp&& comp, Proj&& proj) {
std::ranges::inplace_merge(
std::forward<Range>(r), std::forward<Middle>(mid), std::forward<Comp>(comp), std::forward<Proj>(proj));
};
template <class T>
using R = UncheckedRange<T>;
static_assert(HasInplaceMergeRange<R<int*>, int*>);
// !bidirectional_range<R>
static_assert(!HasInplaceMergeRange<R<cpp20_input_iterator<int*>>>);
static_assert(!HasInplaceMergeRange<R<BidirectionalIteratorNotDecrementable>>);
// !sortable<iterator_t<R>, Comp, Proj>
static_assert(!HasInplaceMergeRange<R<int*>, int*, ComparatorNotCopyable<int*>>);
static_assert(!HasInplaceMergeIter<R<const int*>, const int*>);
template <class In, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
void testInplaceMergeImpl(std::array<int, N1> input, int midIdx, std::array<int, N2> expected) {
assert(std::is_sorted(input.begin(), input.begin() + midIdx));
assert(std::is_sorted(input.begin() + midIdx, input.end()));
assert(std::is_sorted(expected.begin(), expected.end()));
using Sent = SentWrapper<In>;
// iterator overload
{
auto in = input;
std::same_as<In> decltype(auto) result =
std::ranges::inplace_merge(In{in.data()}, In{in.data() + midIdx}, Sent{In{in.data() + in.size()}});
assert(std::ranges::equal(in, expected));
assert(base(result) == in.data() + in.size());
}
// range overload
{
auto in = input;
std::ranges::subrange r{In{in.data()}, Sent{In{in.data() + in.size()}}};
std::same_as<In> decltype(auto) result = std::ranges::inplace_merge(r, In{in.data() + midIdx});
assert(std::ranges::equal(in, expected));
assert(base(result) == in.data() + in.size());
}
}
template <class In, template <class> class SentWrapper>
void testImpl() {
// sorted range
{
std::array in{0, 1, 5, 6, 9, 10};
std::array expected = in;
testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
}
// [first, mid) is longer
{
std::array in{0, 5, 9, 15, 18, 22, 2, 4, 6, 10};
std::array expected = {0, 2, 4, 5, 6, 9, 10, 15, 18, 22};
testInplaceMergeImpl<In, SentWrapper>(in, 6, expected);
}
// [first, mid) is shorter
{
std::array in{0, 5, 9, 2, 4, 6, 10};
std::array expected = {0, 2, 4, 5, 6, 9, 10};
testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
}
// [first, mid) == [mid, last)
{
std::array in{0, 5, 9, 0, 5, 9};
std::array expected = {0, 0, 5, 5, 9, 9};
testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
}
// duplicates within each range
{
std::array in{1, 5, 5, 2, 9, 9, 9};
std::array expected = {1, 2, 5, 5, 9, 9, 9};
testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
}
// all the same
{
std::array in{5, 5, 5, 5, 5, 5, 5, 5};
std::array expected = in;
testInplaceMergeImpl<In, SentWrapper>(in, 5, expected);
}
// [first, mid) is empty (mid == begin)
{
std::array in{0, 1, 5, 6, 9, 10};
std::array expected = in;
testInplaceMergeImpl<In, SentWrapper>(in, 0, expected);
}
// [mid, last] is empty (mid == end)
{
std::array in{0, 1, 5, 6, 9, 10};
std::array expected = in;
testInplaceMergeImpl<In, SentWrapper>(in, 6, expected);
}
// both empty
{
std::array<int, 0> in{};
std::array expected = in;
testInplaceMergeImpl<In, SentWrapper>(in, 0, expected);
}
// mid == first + 1
{
std::array in{9, 2, 5, 7, 10};
std::array expected{2, 5, 7, 9, 10};
testInplaceMergeImpl<In, SentWrapper>(in, 1, expected);
}
// mid == last - 1
{
std::array in{2, 5, 7, 10, 9};
std::array expected{2, 5, 7, 9, 10};
testInplaceMergeImpl<In, SentWrapper>(in, 4, expected);
}
}
template < template <class> class SentWrapper>
void withAllPermutationsOfIter() {
testImpl<bidirectional_iterator<int*>, SentWrapper>();
testImpl<random_access_iterator<int*>, SentWrapper>();
testImpl<contiguous_iterator<int*>, SentWrapper>();
testImpl<int*, SentWrapper>();
}
bool test() {
withAllPermutationsOfIter<std::type_identity_t>();
withAllPermutationsOfIter<sentinel_wrapper>();
struct Data {
int data;
};
const auto equal = [](const Data& x, const Data& y) { return x.data == y.data; };
// Test custom comparator
{
std::array<Data, 4> input{{{4}, {8}, {2}, {5}}};
std::array<Data, 4> expected{{{2}, {4}, {5}, {8}}};
const auto comp = [](const Data& x, const Data& y) { return x.data < y.data; };
// iterator overload
{
auto in = input;
auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 2, in.end(), comp);
assert(std::ranges::equal(in, expected, equal));
assert(result == in.end());
}
// range overload
{
auto in = input;
auto result = std::ranges::inplace_merge(in, in.begin() + 2, comp);
assert(std::ranges::equal(in, expected, equal));
assert(result == in.end());
}
}
// Test custom projection
{
std::array<Data, 4> input{{{4}, {8}, {2}, {5}}};
std::array<Data, 4> expected{{{2}, {4}, {5}, {8}}};
const auto proj = &Data::data;
// iterator overload
{
auto in = input;
auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 2, in.end(), {}, proj);
assert(std::ranges::equal(in, expected, equal));
assert(result == in.end());
}
// range overload
{
auto in = input;
auto result = std::ranges::inplace_merge(in, in.begin() + 2, {}, proj);
assert(std::ranges::equal(in, expected, equal));
assert(result == in.end());
}
}
// Remarks: Stable.
{
struct IntAndID {
int data;
int id;
constexpr auto operator<=>(const IntAndID& rhs) const { return data <=> rhs.data; }
constexpr auto operator==(const IntAndID& rhs) const { return data == rhs.data; }
};
std::array<IntAndID, 6> input{{{0, 0}, {1, 0}, {2, 0}, {0, 1}, {1, 1}, {2, 1}}};
// iterator overload
{
auto in = input;
auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 3, in.end());
assert(std::ranges::equal(in, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
assert(std::ranges::equal(in, std::array{0, 1, 0, 1, 0, 1}, {}, &IntAndID::id));
assert(result == in.end());
}
// range overload
{
auto in = input;
auto result = std::ranges::inplace_merge(in, in.begin() + 3);
assert(std::ranges::equal(in, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
assert(std::ranges::equal(in, std::array{0, 1, 0, 1, 0, 1}, {}, &IntAndID::id));
assert(result == in.end());
}
}
// Complexity: Let N = last - first :
// - For the overloads with no ExecutionPolicy, and if enough
// additional memory is available, exactly N - 1 comparisons.
// - Otherwise, O(NlogN) comparisons.
// In either case, twice as many projections as comparisons.
{
std::array input{1, 2, 3, 3, 3, 7, 7, 2, 2, 5, 5, 6, 6};
std::array expected{1, 2, 2, 2, 3, 3, 3, 5, 5, 6, 6, 7, 7};
auto mid = 7;
// iterator overload
{
auto in = input;
int numberOfComp = 0;
int numberOfProj = 0;
auto result = std::ranges::inplace_merge(
in.begin(),
in.begin() + mid,
in.end(),
counting_predicate{std::ranges::less{}, numberOfComp},
counting_projection{numberOfProj});
assert(std::ranges::equal(in, expected));
assert(result == in.end());
// the spec specifies exactly N-1 comparison but we actually
// do not invoke as many times as specified
assert(numberOfComp <= static_cast<int>(in.size() - 1));
assert(numberOfProj <= 2 * numberOfComp);
}
// range overload
{
auto in = input;
int numberOfComp = 0;
int numberOfProj = 0;
auto result = std::ranges::inplace_merge(
in,
in.begin() + mid,
counting_predicate{std::ranges::less{}, numberOfComp},
counting_projection{numberOfProj});
assert(std::ranges::equal(in, expected));
assert(result == in.end());
assert(numberOfComp <= static_cast<int>(in.size() - 1));
assert(numberOfProj <= 2 * numberOfComp);
}
}
return true;
}
int main(int, char**) {
test();
// inplace_merge is not constexpr in the latest finished Standard (C++20)
return 0;
}
Codebase Browser
llvm