21#ifndef RANGES_V3_ALGORITHM_HEAP_ALGORITHM_HPP
22#define RANGES_V3_ALGORITHM_HEAP_ALGORITHM_HPP
40#include <range/v3/utility/static_const.hpp>
42#include <range/v3/detail/prologue.hpp>
49 struct is_heap_until_n_fn
51 template(
typename I,
typename C =
less,
typename P = identity)(
52 requires random_access_iterator<I> AND
53 indirect_strict_weak_order<C, projected<I, P>>)
54 constexpr I operator()(I
const begin_,
55 iter_difference_t<I>
const n_,
59 RANGES_EXPECT(0 <= n_);
60 iter_difference_t<I> p = 0, c = 1;
79 RANGES_INLINE_VARIABLE(is_heap_until_n_fn, is_heap_until_n)
83 template(
typename I,
typename C =
less,
typename P = identity)(
84 requires random_access_iterator<I> AND
85 indirect_strict_weak_order<C, projected<I, P>>)
86 constexpr bool operator()(I first,
87 iter_difference_t<I> n,
91 return is_heap_until_n(first, n, std::move(pred), std::move(proj)) ==
96 RANGES_INLINE_VARIABLE(is_heap_n_fn, is_heap_n)
102 RANGES_FUNC_BEGIN(is_heap_until)
105 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
106 requires random_access_iterator<I> AND sentinel_for<S, I> AND
107 indirect_strict_weak_order<C, projected<I, P>>)
108 constexpr I RANGES_FUNC(is_heap_until)(I
first, S last, C pred = C{}, P proj = P{})
110 return detail::is_heap_until_n(std::move(first),
111 distance(first, last),
117 template(
typename Rng,
typename C =
less,
typename P = identity)(
118 requires random_access_range<Rng> AND
119 indirect_strict_weak_order<C, projected<iterator_t<Rng>, P>>)
120 constexpr borrowed_iterator_t<Rng>
121 RANGES_FUNC(is_heap_until)(Rng && rng, C pred = C{}, P proj = P{})
123 return detail::is_heap_until_n(
124 begin(rng), distance(rng), std::move(pred), std::move(proj));
127 RANGES_FUNC_END(is_heap_until)
131 using ranges::is_heap_until;
134 RANGES_FUNC_BEGIN(is_heap)
137 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
138 requires random_access_iterator<I> AND sentinel_for<S, I> AND
139 indirect_strict_weak_order<C, projected<I, P>>)
140 constexpr bool RANGES_FUNC(is_heap)(I
first, S last, C pred = C{}, P proj = P{})
142 return detail::is_heap_n(std::move(first),
143 distance(first, last),
149 template(
typename Rng,
typename C =
less,
typename P = identity)(
150 requires random_access_range<Rng> AND
151 indirect_strict_weak_order<C, projected<iterator_t<Rng>, P>>)
152 constexpr bool RANGES_FUNC(is_heap)(Rng && rng, C pred = C{}, P proj = P{})
154 return detail::is_heap_n(
155 begin(rng), distance(rng), std::move(pred), std::move(proj));
158 RANGES_FUNC_END(is_heap)
162 using ranges::is_heap;
171 template<
typename I,
typename C = less,
typename P =
identity>
172 constexpr void operator()(I first,
173 iter_difference_t<I> len,
179 I last =
first + len;
184 iter_value_t<I> v = iter_move(last);
187 *last = iter_move(i);
194 *last = std::move(v);
200 RANGES_INLINE_VARIABLE(sift_up_n_fn, sift_up_n)
202 struct sift_down_n_fn
204 template<
typename I,
typename C = less,
typename P =
identity>
205 constexpr void operator()(I first,
206 iter_difference_t<I> len,
213 auto child = start -
first;
215 if(len < 2 || (len - 2) / 2 < child)
218 child = 2 * child + 1;
219 I child_i =
first + child;
221 if((child + 1) < len &&
234 iter_value_t<I> top = iter_move(start);
238 *start = iter_move(child_i);
241 if((len - 2) / 2 < child)
245 child = 2 * child + 1;
246 child_i =
first + child;
248 if((child + 1) < len &&
258 *start = std::move(top);
262 RANGES_INLINE_VARIABLE(sift_down_n_fn, sift_down_n)
268 RANGES_FUNC_BEGIN(push_heap)
271 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
272 requires random_access_iterator<I> AND sentinel_for<S, I> AND
274 constexpr I RANGES_FUNC(push_heap)(I
first, S last, C pred = C{}, P proj = P{})
276 auto n = distance(first, last);
277 detail::sift_up_n(first, n, std::move(pred), std::move(proj));
282 template(
typename Rng,
typename C =
less,
typename P = identity)(
283 requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
284 constexpr borrowed_iterator_t<Rng>
285 RANGES_FUNC(push_heap)(Rng && rng, C pred = C{}, P proj = P{})
287 iterator_t<Rng>
first = ranges::begin(rng);
288 auto n = distance(rng);
289 detail::sift_up_n(first, n, std::move(pred), std::move(proj));
293 RANGES_FUNC_END(push_heap)
297 using ranges::push_heap;
306 template(
typename I,
typename C =
less,
typename P = identity)(
307 requires random_access_iterator<I> AND sortable<I, C, P>)
308 constexpr void operator()(I first,
309 iter_difference_t<I> len,
315 ranges::iter_swap(first, first + (len - 1));
317 first, len - 1, first, std::move(pred), std::move(proj));
322 RANGES_INLINE_VARIABLE(pop_heap_n_fn, pop_heap_n)
328 RANGES_FUNC_BEGIN(pop_heap)
331 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
332 requires random_access_iterator<I> AND sentinel_for<S, I> AND
334 constexpr I RANGES_FUNC(pop_heap)(I
first, S last, C pred = C{}, P proj = P{})
336 auto n = distance(first, last);
337 detail::pop_heap_n(first, n, std::move(pred), std::move(proj));
342 template(
typename Rng,
typename C =
less,
typename P = identity)(
343 requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
344 constexpr borrowed_iterator_t<Rng>
345 RANGES_FUNC(pop_heap)(Rng && rng, C pred = C{}, P proj = P{})
347 iterator_t<Rng>
first = ranges::begin(rng);
348 auto n = distance(rng);
349 detail::pop_heap_n(first, n, std::move(pred), std::move(proj));
353 RANGES_FUNC_END(pop_heap)
357 using ranges::pop_heap;
360 RANGES_FUNC_BEGIN(make_heap)
363 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
364 requires random_access_iterator<I> AND sentinel_for<S, I> AND
366 constexpr I RANGES_FUNC(make_heap)(I
first, S last, C pred = C{}, P proj = P{})
368 iter_difference_t<I>
const n = distance(first, last);
371 for(
auto start = (n - 2) / 2; start >= 0; --start)
373 first, n, first + start, ranges::ref(pred), ranges::ref(proj));
378 template(
typename Rng,
typename C =
less,
typename P = identity)(
379 requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
380 constexpr borrowed_iterator_t<Rng>
381 RANGES_FUNC(make_heap)(Rng && rng, C pred = C{}, P proj = P{})
383 iterator_t<Rng>
first = ranges::begin(rng);
384 auto const n = distance(rng);
387 for(
auto start = (n - 2) / 2; start >= 0; --start)
389 first, n, first + start, ranges::ref(pred), ranges::ref(proj));
393 RANGES_FUNC_END(make_heap)
397 using ranges::make_heap;
400 RANGES_FUNC_BEGIN(sort_heap)
402 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
403 requires random_access_iterator<I> AND sentinel_for<S, I> AND
405 constexpr I RANGES_FUNC(sort_heap)(I
first, S last, C pred = C{}, P proj = P{})
407 iter_difference_t<I>
const n = distance(first, last);
408 for(
auto i = n; i > 1; --i)
409 detail::pop_heap_n(first, i, ranges::ref(pred), ranges::ref(proj));
413 template(
typename Rng,
typename C =
less,
typename P = identity)(
414 requires random_access_range<Rng &> AND sortable<iterator_t<Rng>, C, P>)
415 constexpr borrowed_iterator_t<Rng>
416 RANGES_FUNC(sort_heap)(Rng && rng, C pred = C{}, P proj = P{})
418 iterator_t<Rng>
first = ranges::begin(rng);
419 auto const n = distance(rng);
420 for(
auto i = n; i > 1; --i)
421 detail::pop_heap_n(first, i, ranges::ref(pred), ranges::ref(proj));
425 RANGES_FUNC_END(sort_heap)
429 using ranges::sort_heap;
434#include <range/v3/detail/epilogue.hpp>
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition meta.hpp:255