src/ds/heap/d_ary/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/num/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // Copyright Malte Skarupke 2020. | ||
| 8 | // Distributed under the Boost Software License, Version 1.0. | ||
| 9 | // (See http://www.boost.org/LICENSE_1_0.txt) | ||
| 10 | namespace d_ary_heap_impl_ { | ||
| 11 | template <int D> | ||
| 12 | 125282 | CEXP u32 ch1idx_(u32 i) NE { return i * D + 1; } | |
| 13 | template <int D> | ||
| 14 | 29232808 | CEXP u32 chls_idx_(u32 i) NE { return i * D + D; } | |
| 15 | template <int D> | ||
| 16 | CEXP u32 gchls_idx_(u32 i) NE { return i * (D * D) + (D * D + D); } | ||
| 17 | template <int D> | ||
| 18 | 24460039 | CEXP u32 pidx_(u32 i) NE { return (i - 1) / D; } | |
| 19 | template <int D> | ||
| 20 | 5 | CEXP u32 gpidx_(u32 i) NE { return (i - (D + 1)) / (D * D); } | |
| 21 | template <int D> | ||
| 22 | 5 | CEXP u32 idx_ngch_(u32 l) NE { return gpidx_<D>(l - 1) + 1; } | |
| 23 | template <int D, class I, class C> | ||
| 24 | CEXP I l_ch_(I it_ch1, C&& c) NE { | ||
| 25 | if CEXP (D == 1) return it_ch1; | ||
| 26 | else if CEXP (D == 2) return it_ch1 + !!c(it_ch1[0], it_ch1[1]); | ||
| 27 | else { | ||
| 28 | I hl1 = l_ch_<D / 2>(it_ch1, c), hl2 = l_ch_<D - D / 2>(it_ch1 + D / 2, c); | ||
| 29 | retif_((c(*hl1, *hl2)), hl2, hl1); | ||
| 30 | } | ||
| 31 | } | ||
| 32 | template <int D, class I, class C> | ||
| 33 | CEXP I l_ch_(I it_ch1, int num_ch, C&& c) NE { | ||
| 34 | if CEXP (D == 2) return it_ch1; | ||
| 35 | else if CEXP (D == 3) { | ||
| 36 | if (num_ch == 1) return it_ch1; | ||
| 37 | return it_ch1 + !!c(it_ch1[0], it_ch1[1]); | ||
| 38 | } else if CEXP (D == 4) { | ||
| 39 | switch (num_ch) { | ||
| 40 | case 1: return it_ch1; | ||
| 41 | case 2: return it_ch1 + !!c(it_ch1[0], it_ch1[1]); | ||
| 42 | default: | ||
| 43 | I largest = it_ch1 + !!c(it_ch1[0], it_ch1[1]); | ||
| 44 | retif_((c(*largest, it_ch1[2])), it_ch1 + 2, largest); | ||
| 45 | } | ||
| 46 | } else { | ||
| 47 | switch (num_ch) { | ||
| 48 | case 1: return it_ch1; | ||
| 49 | case 2: return it_ch1 + !!c(it_ch1[0], it_ch1[1]); | ||
| 50 | case 3: { | ||
| 51 | I l = it_ch1 + !!c(it_ch1[0], it_ch1[1]); | ||
| 52 | retif_((c(*l, it_ch1[2])), it_ch1 + 2, l); | ||
| 53 | } | ||
| 54 | case 4: { | ||
| 55 | I hl1 = it_ch1 + !!c(it_ch1[0], it_ch1[1]), | ||
| 56 | hl2 = it_ch1 + 2 + !!c(it_ch1[2], it_ch1[3]); | ||
| 57 | retif_((c(*hl1, *hl2)), hl2, hl1); | ||
| 58 | } | ||
| 59 | default: | ||
| 60 | int h = num_ch / 2; | ||
| 61 | I hl1 = l_ch_<D>(it_ch1, h, c), hl2 = l_ch_<D>(it_ch1 + h, num_ch - h, c); | ||
| 62 | retif_((c(*hl1, *hl2)), hl2, hl1); | ||
| 63 | } | ||
| 64 | } | ||
| 65 | } | ||
| 66 | } // namespace d_ary_heap_impl_ | ||
| 67 | |||
| 68 | template <int D, class I, class C = std::less<>> | ||
| 69 | 6 | CEXP void make_dary_heap(I begin, I end, C&& comp = C{}) NE { | |
| 70 | 6 | u32 len = u32(end - begin); | |
| 71 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
6 | if (len <= 1) return; |
| 72 | 6 | u32 idx = (len - 2) / D; | |
| 73 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 time.
|
6 | if (int num_ch_end = (len - 1) % D; num_ch_end) { |
| 74 | 5 | I chl = d_ary_heap_impl_::l_ch_<D>(begin + d_ary_heap_impl_::ch1idx_<D>(idx), num_ch_end, comp); | |
| 75 |
1/2✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
|
5 | if (comp(begin[idx], *chl)) swap(begin[idx], *chl); |
| 76 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if (idx == 0) return; |
| 77 | 5 | --idx; | |
| 78 | } | ||
| 79 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 time.
|
6 | if (idx > 0) |
| 80 | 125277 | for (u32 lidx_ngcd = d_ary_heap_impl_::idx_ngch_<D>(len);;) { | |
| 81 | 125277 | I ch = d_ary_heap_impl_::l_ch_<D>(begin + d_ary_heap_impl_::ch1idx_<D>(idx), comp); | |
| 82 |
2/2✓ Branch 3 taken 113940 times.
✓ Branch 4 taken 11337 times.
|
125277 | if (comp(begin[idx], *ch)) swap(begin[idx], *ch); |
| 83 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 125272 times.
|
125277 | if (idx-- == lidx_ngcd) break; |
| 84 | } | ||
| 85 | 125277 | for (;; --idx) { | |
| 86 | 125283 | TPN std::iterator_traits<I>::value_type value = std::move(begin[idx]); | |
| 87 | 125283 | u32 mdidx = idx; | |
| 88 | 345268 | for (;;) { | |
| 89 | 470551 | u32 idx_ch = d_ary_heap_impl_::chls_idx_<D>(mdidx), idx_ch1 = idx_ch - (D - 1); | |
| 90 | 470551 | I ch = begin; | |
| 91 |
2/2✓ Branch 0 taken 362265 times.
✓ Branch 1 taken 108286 times.
|
470551 | if (idx_ch < len) ch = d_ary_heap_impl_::l_ch_<D>(begin + idx_ch1, comp); |
| 92 |
2/2✓ Branch 0 taken 108281 times.
✓ Branch 1 taken 5 times.
|
108286 | else if (idx_ch1 >= len) break; |
| 93 | 5 | else ch = d_ary_heap_impl_::l_ch_<D>(begin + idx_ch1, int(len - idx_ch1), comp); | |
| 94 |
2/2✓ Branch 2 taken 17002 times.
✓ Branch 3 taken 345268 times.
|
362270 | if (!comp(value, *ch)) break; |
| 95 | 345268 | begin[mdidx] = std::move(*ch), mdidx = u32(ch - begin); | |
| 96 | } | ||
| 97 |
2/2✓ Branch 2 taken 6 times.
✓ Branch 3 taken 125277 times.
|
125283 | if (begin[mdidx] = std::move(value); idx == 0) break; |
| 98 | } | ||
| 99 | } | ||
| 100 | template <int D, common_range R, class C = std::less<>> | ||
| 101 | CEXP void make_dary_heap(R CR r, C&& comp = C{}) NE { return make_dary_heap<D>(begin(r), end(r), std::forward<C>(comp)); } | ||
| 102 | template <int D, class I, class C = std::less<>> | ||
| 103 | CEXP bool is_dary_heap(I begin, I end, C&& comp = C{}) NE { | ||
| 104 | flt_ (u32, i, 1, u32(end - begin)) | ||
| 105 | if (u32 p = d_ary_heap_impl_::pidx_<D>(i); comp(begin[p], begin[i])) return false; | ||
| 106 | return true; | ||
| 107 | } | ||
| 108 | template <int D, common_range R, class C = std::less<>> | ||
| 109 | CEXP void is_dary_heap(R CR r, C&& comp = C{}) NE { return is_dary_heap<D>(begin(r), end(r), std::forward<C>(comp)); } | ||
| 110 | template <int D, class I, class C = std::less<>> | ||
| 111 | 8791662 | CEXP void push_dary_heap(I begin, I end, C&& comp = C{}) NE { | |
| 112 | 8791662 | TPN std::iterator_traits<I>::value_type val = std::move(end[-1]); | |
| 113 | 8791662 | u32 idx = u32(end - begin) - 1; | |
| 114 |
12/12void tifa_libs::push_dary_heap<2, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 0 taken 5807542 times.
✓ Branch 1 taken 365668 times.
void tifa_libs::push_dary_heap<2, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 0 taken 4600717 times.
✓ Branch 1 taken 83612 times.
void tifa_libs::push_dary_heap<3, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 0 taken 4139995 times.
✓ Branch 1 taken 365668 times.
void tifa_libs::push_dary_heap<3, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 0 taken 3442492 times.
✓ Branch 1 taken 83612 times.
void tifa_libs::push_dary_heap<4, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 0 taken 3525643 times.
✓ Branch 1 taken 365668 times.
void tifa_libs::push_dary_heap<4, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 0 taken 2943650 times.
✓ Branch 1 taken 83612 times.
|
25807879 | while (idx > 0) { |
| 115 | 24460039 | u32 p = d_ary_heap_impl_::pidx_<D>(idx); | |
| 116 |
12/12void tifa_libs::push_dary_heap<2, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 1063728 times.
✓ Branch 3 taken 4743814 times.
void tifa_libs::push_dary_heap<2, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 1417546 times.
✓ Branch 3 taken 3183171 times.
void tifa_libs::push_dary_heap<3, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 1063728 times.
✓ Branch 3 taken 3076267 times.
void tifa_libs::push_dary_heap<3, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 1417546 times.
✓ Branch 3 taken 2024946 times.
void tifa_libs::push_dary_heap<4, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 1063728 times.
✓ Branch 3 taken 2461915 times.
void tifa_libs::push_dary_heap<4, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 1417546 times.
✓ Branch 3 taken 1526104 times.
|
24460039 | if (!comp(begin[p], val)) break; |
| 117 | 17016217 | begin[idx] = std::move(begin[p]), idx = p; | |
| 118 | } | ||
| 119 | 8791662 | begin[idx] = std::move(val); | |
| 120 | 8791662 | } | |
| 121 | template <int D, common_range R, class C = std::less<>> | ||
| 122 | CEXP void push_dary_heap(R CR r, C&& comp = C{}) NE { return push_dary_heap<D>(begin(r), end(r), std::forward<C>(comp)); } | ||
| 123 | template <int D, class I, class C = std::less<>> | ||
| 124 | 2649747 | CEXP void pop_dary_heap(I begin, I end, C&& comp = C{}) NE { | |
| 125 | 2649747 | u32 len = u32(end - begin) - 1; | |
| 126 | 2649747 | TPN std::iterator_traits<I>::value_type val = std::move(end[-1]); | |
| 127 | 2649747 | u32 idx = 0; | |
| 128 | 28762257 | for (end[-1] = std::move(begin[0]);;) { | |
| 129 |
12/12void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 1 taken 3451217 times.
✓ Branch 2 taken 344863 times.
void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 1 taken 8916148 times.
✓ Branch 2 taken 266388 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 1 taken 2265432 times.
✓ Branch 2 taken 353010 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 1 taken 5834654 times.
✓ Branch 2 taken 331569 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 1 taken 1816481 times.
✓ Branch 2 taken 361760 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 1 taken 4473904 times.
✓ Branch 2 taken 346831 times.
|
28762257 | if (u32 chls = d_ary_heap_impl_::chls_idx_<D>(idx), ch1 = chls - (D - 1); chls < len) { |
| 130 | 26757836 | I ch = d_ary_heap_impl_::l_ch_<D>(begin + ch1, comp); | |
| 131 |
12/12void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 37503 times.
✓ Branch 3 taken 3413714 times.
void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 234495 times.
✓ Branch 3 taken 8681653 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 29356 times.
✓ Branch 3 taken 2236076 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 169314 times.
✓ Branch 3 taken 5665340 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 20606 times.
✓ Branch 3 taken 1795875 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 154052 times.
✓ Branch 3 taken 4319852 times.
|
26757836 | if (!comp(val, *ch)) break; |
| 132 | 26112510 | begin[idx] = std::move(*ch), idx = u32(ch - begin); | |
| 133 |
12/12void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 0 taken 77619 times.
✓ Branch 1 taken 267244 times.
void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 0 taken 9244 times.
✓ Branch 1 taken 257144 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 0 taken 85870 times.
✓ Branch 1 taken 267140 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 0 taken 15946 times.
✓ Branch 1 taken 315623 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 0 taken 112891 times.
✓ Branch 1 taken 248869 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 0 taken 9790 times.
✓ Branch 1 taken 337041 times.
|
2004421 | } else if (ch1 < len) { |
| 134 | 311360 | I ch = d_ary_heap_impl_::l_ch_<D>(begin + ch1, int(len - ch1), comp); | |
| 135 |
12/12void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 7030 times.
✓ Branch 3 taken 70589 times.
void tifa_libs::pop_dary_heap<2, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 2416 times.
✓ Branch 3 taken 6828 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 13688 times.
✓ Branch 3 taken 72182 times.
void tifa_libs::pop_dary_heap<3, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 5317 times.
✓ Branch 3 taken 10629 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, std::less<void>&&):
✓ Branch 2 taken 19094 times.
✓ Branch 3 taken 93797 times.
void tifa_libs::pop_dary_heap<4, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void> >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::less<void>&&):
✓ Branch 2 taken 4339 times.
✓ Branch 3 taken 5451 times.
|
311360 | if (comp(val, *ch)) begin[idx] = std::move(*ch), idx = u32(ch - begin); |
| 136 | 311360 | break; | |
| 137 | 1693061 | } else break; | |
| 138 | } | ||
| 139 | 2649747 | begin[idx] = std::move(val); | |
| 140 | 2649747 | } | |
| 141 | template <int D, common_range R, class C = std::less<>> | ||
| 142 | CEXP void pop_dary_heap(R CR r, C&& comp = C{}) NE { return pop_dary_heap<D>(begin(r), end(r), std::forward<C>(comp)); } | ||
| 143 | |||
| 144 | } // namespace tifa_libs | ||
| 145 |