di 0.1.0
Loading...
Searching...
No Matches
is_heap_until.h
Go to the documentation of this file.
1#pragma once
2
9#include "di/util/move.h"
11
12namespace di::container {
13namespace detail {
14 struct IsHeapUntilFunction {
15 template<concepts::RandomAccessIterator It, concepts::SentinelFor<It> Sent, typename Proj = function::Identity,
16 concepts::IndirectStrictWeakOrder<meta::Projected<It, Proj>> Comp = function::Compare>
17 constexpr auto operator()(It it, Sent last, Comp comp = {}, Proj proj = {}) const -> It {
18 auto n = container::distance(it, last);
19 return is_heap_until_with_size(util::move(it), util::ref(comp), util::ref(proj), n);
20 }
21
22 template<concepts::RandomAccessContainer Con, typename Proj = function::Identity,
23 concepts::IndirectStrictWeakOrder<meta::Projected<meta::ContainerIterator<Con>, Proj>> Comp =
24 function::Compare>
25 constexpr auto operator()(Con&& container, Comp comp = {}, Proj proj = {}) const
27 return is_heap_until_with_size(container::begin(container), util::ref(comp), util::ref(proj),
28 container::distance(container));
29 }
30
31 private:
32 template<typename It, typename Comp, typename Proj, typename SSizeType>
33 constexpr static auto is_heap_until_with_size(It first, Comp comp, Proj proj, SSizeType n) -> It {
34 SSizeType parent = 0;
35 for (SSizeType child = 1; child != n; ++child) {
36 // If the parent is less than the child, the range is longer a max heap.
37 if (function::invoke(comp, function::invoke(proj, first[parent]),
38 function::invoke(proj, first[child])) < 0) {
39 return first + child;
40 }
41
42 // Increment the parent every other iteration.
43 if (child % 2 == 0) {
44 ++parent;
45 }
46 }
47 return first + n;
48 }
49 };
50}
51
52constexpr inline auto is_heap_until = detail::IsHeapUntilFunction {};
53}
54
55namespace di {
57}
constexpr auto first(concepts::detail::ConstantVector auto &vector, size_t count)
Definition vector_first.h:13
Definition sequence.h:12
constexpr auto is_heap_until
Definition is_heap_until.h:52
constexpr auto distance
Definition distance.h:44
constexpr auto begin
Definition begin.h:52
constexpr auto invoke
Definition invoke.h:100
Conditional< concepts::BorrowedContainer< Con >, ContainerIterator< Con >, container::Dangling > BorrowedIterator
Definition borrowed_iterator.h:11
constexpr auto ref
Definition reference_wrapper.h:98
Definition any_storable.h:9
constexpr auto proj
Definition proj.h:59