Horizon
heap_algorithm.hpp
Go to the documentation of this file.
1 // 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 
28 #include <range/v3/range_fwd.hpp>
29 
40 #include <range/v3/utility/static_const.hpp>
41 
42 #include <range/v3/detail/prologue.hpp>
43 
44 namespace 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
CPP_concept sortable
\concept sortable
Definition: concepts.hpp:865
CPP_concept indirect_strict_weak_order
\concept indirect_strict_weak_order
Definition: concepts.hpp:689
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
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.