Horizon
Loading...
Searching...
No Matches
heap_algorithm.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13//===----------------------------------------------------------------------===//
14//
15// The LLVM Compiler Infrastructure
16//
17// This file is dual licensed under the MIT and the University of Illinois Open
18// Source Licenses. See LICENSE.TXT for details.
19//
20//===----------------------------------------------------------------------===//
21#ifndef RANGES_V3_ALGORITHM_HEAP_ALGORITHM_HPP
22#define RANGES_V3_ALGORITHM_HEAP_ALGORITHM_HPP
23
24#include <functional>
25
26#include <meta/meta.hpp>
27
29
40#include <range/v3/utility/static_const.hpp>
41
42#include <range/v3/detail/prologue.hpp>
43
44namespace ranges
45{
47 namespace detail
48 {
49 struct is_heap_until_n_fn
50 {
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_,
56 C pred = C{},
57 P proj = P{}) const
58 {
59 RANGES_EXPECT(0 <= n_);
60 iter_difference_t<I> p = 0, c = 1;
61 I pp = begin_;
62 while(c < n_)
63 {
64 I cp = begin_ + c;
65 if(invoke(pred, invoke(proj, *pp), invoke(proj, *cp)))
66 return cp;
67 ++c;
68 ++cp;
69 if(c == n_ || invoke(pred, invoke(proj, *pp), invoke(proj, *cp)))
70 return cp;
71 ++p;
72 ++pp;
73 c = 2 * p + 1;
74 }
75 return begin_ + n_;
76 }
77 };
78
79 RANGES_INLINE_VARIABLE(is_heap_until_n_fn, is_heap_until_n)
80
81 struct is_heap_n_fn
82 {
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,
88 C pred = C{},
89 P proj = P{}) const
90 {
91 return is_heap_until_n(first, n, std::move(pred), std::move(proj)) ==
92 first + n;
93 }
94 };
95
96 RANGES_INLINE_VARIABLE(is_heap_n_fn, is_heap_n)
97 } // namespace detail
99
102 RANGES_FUNC_BEGIN(is_heap_until)
103
104
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{})
109 {
110 return detail::is_heap_until_n(std::move(first),
111 distance(first, last),
112 std::move(pred),
113 std::move(proj));
114 }
115
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{})
122 {
123 return detail::is_heap_until_n(
124 begin(rng), distance(rng), std::move(pred), std::move(proj));
125 }
126
127 RANGES_FUNC_END(is_heap_until)
128
129 namespace cpp20
130 {
131 using ranges::is_heap_until;
132 }
133
134 RANGES_FUNC_BEGIN(is_heap)
135
136
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{}) //
141 {
142 return detail::is_heap_n(std::move(first),
143 distance(first, last),
144 std::move(pred),
145 std::move(proj));
146 }
147
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{}) //
153 {
154 return detail::is_heap_n(
155 begin(rng), distance(rng), std::move(pred), std::move(proj));
156 }
157
158 RANGES_FUNC_END(is_heap)
159
160 namespace cpp20
161 {
162 using ranges::is_heap;
163 }
165
167 namespace detail
168 {
169 struct sift_up_n_fn
170 {
171 template<typename I, typename C = less, typename P = identity>
172 constexpr void operator()(I first,
173 iter_difference_t<I> len,
174 C pred = C{},
175 P proj = P{}) const
176 {
177 if(len > 1)
178 {
179 I last = first + len;
180 len = (len - 2) / 2;
181 I i = first + len;
182 if(invoke(pred, invoke(proj, *i), invoke(proj, *--last)))
183 {
184 iter_value_t<I> v = iter_move(last);
185 do
186 {
187 *last = iter_move(i);
188 last = i;
189 if(len == 0)
190 break;
191 len = (len - 1) / 2;
192 i = first + len;
193 } while(invoke(pred, invoke(proj, *i), invoke(proj, v)));
194 *last = std::move(v);
195 }
196 }
197 }
198 };
199
200 RANGES_INLINE_VARIABLE(sift_up_n_fn, sift_up_n)
201
202 struct sift_down_n_fn
203 {
204 template<typename I, typename C = less, typename P = identity>
205 constexpr void operator()(I first,
206 iter_difference_t<I> len,
207 I start,
208 C pred = C{},
209 P proj = P{}) const
210 {
211 // left-child of start is at 2 * start + 1
212 // right-child of start is at 2 * start + 2
213 auto child = start - first;
214
215 if(len < 2 || (len - 2) / 2 < child)
216 return;
217
218 child = 2 * child + 1;
219 I child_i = first + child;
220
221 if((child + 1) < len &&
222 invoke(pred, invoke(proj, *child_i), invoke(proj, *(child_i + 1))))
223 {
224 // right-child exists and is greater than left-child
225 ++child_i;
226 ++child;
227 }
228
229 // check if we are in heap-order
230 if(invoke(pred, invoke(proj, *child_i), invoke(proj, *start)))
231 // we are, start is larger than it's largest child
232 return;
233
234 iter_value_t<I> top = iter_move(start);
235 do
236 {
237 // we are not in heap-order, swap the parent with it's largest child
238 *start = iter_move(child_i);
239 start = child_i;
240
241 if((len - 2) / 2 < child)
242 break;
243
244 // recompute the child based off of the updated parent
245 child = 2 * child + 1;
246 child_i = first + child;
247
248 if((child + 1) < len &&
249 invoke(pred, invoke(proj, *child_i), invoke(proj, *(child_i + 1))))
250 {
251 // right-child exists and is greater than left-child
252 ++child_i;
253 ++child;
254 }
255
256 // check if we are in heap-order
257 } while(!invoke(pred, invoke(proj, *child_i), invoke(proj, top)));
258 *start = std::move(top);
259 }
260 };
261
262 RANGES_INLINE_VARIABLE(sift_down_n_fn, sift_down_n)
263 } // namespace detail
265
268 RANGES_FUNC_BEGIN(push_heap)
269
270
271 template(typename I, typename S, typename C = less, typename P = identity)(
272 requires random_access_iterator<I> AND sentinel_for<S, I> AND
273 sortable<I, C, P>)
274 constexpr I RANGES_FUNC(push_heap)(I first, S last, C pred = C{}, P proj = P{})
275 {
276 auto n = distance(first, last);
277 detail::sift_up_n(first, n, std::move(pred), std::move(proj));
278 return first + n;
279 }
280
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{}) //
286 {
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));
290 return first + n;
291 }
292
293 RANGES_FUNC_END(push_heap)
294
295 namespace cpp20
296 {
297 using ranges::push_heap;
298 }
300
302 namespace detail
303 {
304 struct pop_heap_n_fn
305 {
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,
310 C pred = C{},
311 P proj = P{}) const
312 {
313 if(len > 1)
314 {
315 ranges::iter_swap(first, first + (len - 1));
316 detail::sift_down_n(
317 first, len - 1, first, std::move(pred), std::move(proj));
318 }
319 }
320 };
321
322 RANGES_INLINE_VARIABLE(pop_heap_n_fn, pop_heap_n)
323 } // namespace detail
325
328 RANGES_FUNC_BEGIN(pop_heap)
329
330
331 template(typename I, typename S, typename C = less, typename P = identity)(
332 requires random_access_iterator<I> AND sentinel_for<S, I> AND
333 sortable<I, C, P>)
334 constexpr I RANGES_FUNC(pop_heap)(I first, S last, C pred = C{}, P proj = P{})
335 {
336 auto n = distance(first, last);
337 detail::pop_heap_n(first, n, std::move(pred), std::move(proj));
338 return first + n;
339 }
340
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{})
346 {
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));
350 return first + n;
351 }
352
353 RANGES_FUNC_END(pop_heap)
354
355 namespace cpp20
356 {
357 using ranges::pop_heap;
358 }
359
360 RANGES_FUNC_BEGIN(make_heap)
361
362
363 template(typename I, typename S, typename C = less, typename P = identity)(
364 requires random_access_iterator<I> AND sentinel_for<S, I> AND
365 sortable<I, C, P>)
366 constexpr I RANGES_FUNC(make_heap)(I first, S last, C pred = C{}, P proj = P{})
367 {
368 iter_difference_t<I> const n = distance(first, last);
369 if(n > 1)
370 // start from the first parent, there is no need to consider children
371 for(auto start = (n - 2) / 2; start >= 0; --start)
372 detail::sift_down_n(
373 first, n, first + start, ranges::ref(pred), ranges::ref(proj));
374 return first + n;
375 }
376
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{})
382 {
383 iterator_t<Rng> first = ranges::begin(rng);
384 auto const n = distance(rng);
385 if(n > 1)
386 // start from the first parent, there is no need to consider children
387 for(auto start = (n - 2) / 2; start >= 0; --start)
388 detail::sift_down_n(
389 first, n, first + start, ranges::ref(pred), ranges::ref(proj));
390 return first + n;
391 }
392
393 RANGES_FUNC_END(make_heap)
394
395 namespace cpp20
396 {
397 using ranges::make_heap;
398 }
399
400 RANGES_FUNC_BEGIN(sort_heap)
401
402 template(typename I, typename S, typename C = less, typename P = identity)(
403 requires random_access_iterator<I> AND sentinel_for<S, I> AND
404 sortable<I, C, P>)
405 constexpr I RANGES_FUNC(sort_heap)(I first, S last, C pred = C{}, P proj = P{})
406 {
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));
410 return first + n;
411 }
412
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{})
417 {
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));
422 return first + n;
423 }
424
425 RANGES_FUNC_END(sort_heap)
426
427 namespace cpp20
428 {
429 using ranges::sort_heap;
430 }
432} // namespace ranges
433
434#include <range/v3/detail/epilogue.hpp>
435
436#endif
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
Tiny meta-programming library.