//===----------------------------------------------------------------------===//
//
// 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 Proj = identity,
// indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
// constexpr I is_heap_until(I first, S last, Comp comp = {}, Proj proj = {}); // Since C++20
//
// template<random_access_range R, class Proj = identity,
// indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
// constexpr borrowed_iterator_t<R>
// is_heap_until(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 "test_iterators.h"
// Test constraints of the (iterator, sentinel) overload.
// ======================================================
template <class Iter = int*, class Sent = int*, class Comp = std::ranges::less>
concept HasIsHeapUntilIter =
requires(Iter&& iter, Sent&& sent, Comp&& comp) {
std::ranges::is_heap_until(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp));
};
static_assert(HasIsHeapUntilIter<int*, int*, std::ranges::less>);
// !random_access_iterator<I>
static_assert(!HasIsHeapUntilIter<RandomAccessIteratorNotDerivedFrom>);
static_assert(!HasIsHeapUntilIter<RandomAccessIteratorBadIndex>);
// !sentinel_for<S, I>
static_assert(!HasIsHeapUntilIter<int*, SentinelForNotSemiregular>);
static_assert(!HasIsHeapUntilIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
struct NoComparator {};
// !indirect_strict_weak_order<Comp, projected<I, Proj>>
static_assert(!HasIsHeapUntilIter<NoComparator*, NoComparator*>);
// Test constraints of the (range) overload.
// =========================================
template <class Range, class Comp = std::ranges::less>
concept HasIsHeapUntilRange =
requires(Range&& range, Comp&& comp) {
std::ranges::is_heap_until(std::forward<Range>(range), std::forward<Comp>(comp));
};
template <class T>
using R = UncheckedRange<T>;
static_assert(HasIsHeapUntilRange<R<int*>>);
// !random_access_range<R>
static_assert(!HasIsHeapUntilRange<RandomAccessRangeNotDerivedFrom>);
static_assert(!HasIsHeapUntilRange<RandomAccessRangeBadIndex>);
// !indirect_strict_weak_order<Comp, projected<iterator_t<R>, Proj>>
static_assert(!HasIsHeapUntilRange<R<NoComparator*>>);
template <class Iter, class Sent, std::size_t N>
constexpr void test_one(std::array<int, N> input, std::size_t until_index) {
auto begin = Iter(input.data());
auto end = Sent(Iter(input.data() + input.size()));
{ // (iterator, sentinel) overload.
std::same_as<Iter> decltype(auto) result = std::ranges::is_heap_until(begin, end);
assert(base(result) == input.data() + until_index);
}
{ // (range) overload.
auto range = std::ranges::subrange(begin, end);
std::same_as<Iter> decltype(auto) result = std::ranges::is_heap_until(range);
assert(base(result) == input.data() + until_index);
}
}
template <class Iter, class Sent>
constexpr void test_iter_sent() {
// Empty sequence.
test_one<Iter, Sent, 0>({}, 0);
// 1-element sequence.
test_one<Iter, Sent>(std::array{1}, 1);
// 2-element sequence, a heap.
test_one<Iter, Sent>(std::array{2, 1}, 2);
// 2-element sequence, not a heap.
test_one<Iter, Sent>(std::array{1, 2}, 1);
// Longer sequence, a heap.
test_one<Iter, Sent>(std::array{8, 6, 7, 3, 4, 1, 5, 2}, 8);
// Longer sequence, not a heap.
test_one<Iter, Sent>(std::array{8, 6, 7, 3, 4, 1, 2, 5}, 7);
// Longer sequence with duplicates, a heap.
test_one<Iter, Sent>(std::array{8, 7, 5, 5, 6, 4, 1, 2, 3, 2}, 10);
// Longer sequence with duplicates, not a heap.
test_one<Iter, Sent>(std::array{7, 5, 5, 6, 4, 1, 2, 3, 2, 8}, 3);
// All elements are the same.
test_one<Iter, Sent>(std::array{1, 1, 1}, 3);
}
template <class Iter>
constexpr void test_iter() {
test_iter_sent<Iter, Iter>();
test_iter_sent<Iter, sentinel_wrapper<Iter>>();
}
constexpr void test_iterators() {
test_iter<random_access_iterator<int*>>();
test_iter<contiguous_iterator<int*>>();
test_iter<int*>();
test_iter<const int*>();
}
constexpr bool test() {
test_iterators();
{ // A custom comparator works.
std::ranges::less ls;
std::ranges::greater gt;
std::array in = {1, 3, 2, 5, 4, 7, 8, 6};
{ // (iterator, sentinel) overload.
auto result_default_comp = std::ranges::is_heap_until(in.begin(), in.end(), ls);
assert(result_default_comp == in.begin() + 1);
auto result_custom_comp = std::ranges::is_heap_until(in.begin(), in.end(), gt);
assert(result_custom_comp == in.end());
}
{ // (range) overload.
auto result_default_comp = std::ranges::is_heap_until(in, ls);
assert(result_default_comp == in.begin() + 1);
auto result_custom_comp = std::ranges::is_heap_until(in, gt);
assert(result_custom_comp == in.end());
}
}
{ // A custom projection works.
struct A {
int x;
constexpr auto operator<=>(const A&) const = default;
};
std::array in = {A{-8}, A{-6}, A{-7}, A{-3}, A{-4}, A{-1}, A{-5}, A{-2}};
auto negate = [](A a) { return a.x * -1; };
{ // (iterator, sentinel) overload.
auto result_default_comp = std::ranges::is_heap_until(in.begin(), in.end(), {});
assert(result_default_comp == in.begin() + 1);
auto result_custom_comp = std::ranges::is_heap_until(in.begin(), in.end(), {}, negate);
assert(result_custom_comp == in.end());
}
{ // (range) overload.
auto result_default_comp = std::ranges::is_heap_until(in, {});
assert(result_default_comp == in.begin() + 1);
auto result_custom_comp = std::ranges::is_heap_until(in, {}, negate);
assert(result_custom_comp == in.end());
}
}
return true;
}
int main(int, char**) {
test();
static_assert(test());
return 0;
}
Codebase Browser
llvm