GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 208 / 0 / 208
Functions: 100.0% 24 / 0 / 24
Branches: 97.9% 183 / 0 / 187
src/ds/dq/p/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 depq_impl_ {
11 3249841 CEXP int hib_(u32 i) NE { return std::bit_width(i) - 1; }
12 3249792 CEXP bool is_minni(u32 l) NE { return (hib_(l) & 1) == 0; }
13 13 CEXP bool is_mini(u32 i) NE { return is_minni(i + 1); }
14 7662359 CEXP u32 gpidx_(u32 i) NE { return (i - 3) / 4; }
15 29971309 CEXP u32 pidx_(u32 i) NE { return (i - 1) / 2; }
16 4838117 CEXP u32 ch1idx_(u32 i) NE { return (i * 2) + 1; }
17 30904121 CEXP u32 gchls_idx_(u32 i) NE { return (i * 4) + 6; }
18 template <class I, class C>
19 604540 CEXP u32 s_dec_(I b, u32 l, u32 ch1, u32 gch1, C&& c) NE {
20
6/6
✓ Branch 0 taken 468067 times.
✓ Branch 1 taken 136473 times.
✓ Branch 2 taken 453188 times.
✓ Branch 3 taken 14879 times.
✓ Branch 7 taken 230461 times.
✓ Branch 8 taken 222727 times.
 604540 if (cu32 ch2 = ch1 + 1; gch1 >= l) return ch1 + (ch2 != l && c(b[ch2], b[ch1]));
21
2/2
✓ Branch 0 taken 43841 times.
✓ Branch 1 taken 92632 times.
 136473 else if (cu32 gch2 = gch1 + 1; gch2 == l) {
22
2/2
✓ Branch 3 taken 39924 times.
✓ Branch 4 taken 3917 times.
 43841 retif_((c(b[gch1], b[ch2])), gch1, ch2);
23
2/2
✓ Branch 3 taken 47405 times.
✓ Branch 4 taken 45227 times.
 92632 } else if (cu32 gchm = gch1 + !!c(b[gch2], b[gch1]), gch3 = gch2 + 1; gch3 == l) {
24
2/2
✓ Branch 3 taken 46061 times.
✓ Branch 4 taken 1344 times.
 47405 retif_((c(b[gchm], b[ch2])), gchm, ch2);
25
2/2
✓ Branch 3 taken 23575 times.
✓ Branch 4 taken 21652 times.
 45227 } else retif_((c(b[gchm], b[gch3])), gchm, gch3);
26 }
27 template <class I, class C>
28 977863 CEXP u32 l_dec_(I b, u32 l, u32 ch1, u32 gch1, C&& c) NE {
29
12/12
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 0 taken 897462 times.
✓ Branch 1 taken 28415 times.
✓ Branch 2 taken 858734 times.
✓ Branch 3 taken 38728 times.
✓ Branch 7 taken 435391 times.
✓ Branch 8 taken 423343 times.
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 0 taken 32892 times.
✓ Branch 1 taken 19094 times.
✓ Branch 2 taken 32890 times.
✓ Branch 3 taken 2 times.
✓ Branch 7 taken 17722 times.
✓ Branch 8 taken 15168 times.
 977863 if (cu32 ch2 = ch1 + 1; gch1 >= l) return ch1 + (ch2 != l && c(b[ch1], b[ch2]));
30
4/4
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 0 taken 9916 times.
✓ Branch 1 taken 18499 times.
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 0 taken 5870 times.
✓ Branch 1 taken 13224 times.
 47509 else if (cu32 gch2 = gch1 + 1; gch2 == l) {
31
4/4
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 7952 times.
✓ Branch 4 taken 1964 times.
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 5841 times.
✓ Branch 4 taken 29 times.
 15786 retif_((c(b[ch2], b[gch1])), gch1, ch2);
32
4/4
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 9936 times.
✓ Branch 4 taken 8563 times.
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 6593 times.
✓ Branch 4 taken 6631 times.
 31723 } else if (cu32 gchm = gch1 + !!c(b[gch1], b[gch2]), gch3 = gch2 + 1; gch3 == l) {
33
4/4
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 9306 times.
✓ Branch 4 taken 630 times.
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 6592 times.
✓ Branch 4 taken 1 time.
 16529 retif_((c(b[ch2], b[gchm])), gchm, ch2);
34
4/4
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 4300 times.
✓ Branch 4 taken 4263 times.
unsigned int tifa_libs::depq_impl_::l_dec_<__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> > >, unsigned int, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 3366 times.
✓ Branch 4 taken 3265 times.
 15194 } else retif_((c(b[gchm], b[gch3])), gch3, gchm);
35 }
36 template <class I, class C>
37 2277821 CEXP void pdmin_(I b, TPN std::iterator_traits<I>::value_type v, u32 i, u32 l, C&& c) NE {
38 13912036 for (;;)
39
2/2
✓ Branch 1 taken 14159131 times.
✓ Branch 2 taken 2030726 times.
 16189857 if (cu32 gch_lst = gchls_idx_(i); gch_lst < l) {
40 14159131 auto it = b + gch_lst;
41 14159131 u32 h1m = gch_lst - 2 - !!c(it[-3], it[-2]),
42 14159131 h2m = gch_lst - !!c(it[-1], it[0]),
43
2/2
✓ Branch 3 taken 7085016 times.
✓ Branch 4 taken 7074115 times.
 14159131 s = c(b[h2m], b[h1m]) ? h2m : h1m;
44
2/2
✓ Branch 2 taken 247095 times.
✓ Branch 3 taken 13912036 times.
 14159131 if (!c(b[s], v)) break;
45 13912036 b[i] = std::move(b[s]);
46
2/2
✓ Branch 3 taken 612787 times.
✓ Branch 4 taken 13299249 times.
 13912036 if (cu32 p = pidx_(i = s); c(b[p], v)) swap(b[p], v);
47 } else {
48 2030726 u32 ch1 = ch1idx_(i);
49
2/2
✓ Branch 0 taken 1426186 times.
✓ Branch 1 taken 604540 times.
 2030726 if (ch1 >= l) break;
50 604540 u32 gch1 = gch_lst - 3, s = s_dec_(b, l, ch1, gch1, c);
51
2/2
✓ Branch 2 taken 309158 times.
✓ Branch 3 taken 295382 times.
 604540 if (!c(b[s], v)) break;
52
2/2
✓ Branch 3 taken 242325 times.
✓ Branch 4 taken 53057 times.
 295382 if (b[i] = std::move(b[s]); (i = s) < gch1) break;
53
2/2
✓ Branch 3 taken 4148 times.
✓ Branch 4 taken 48909 times.
 53057 if (cu32 p = pidx_(i); c(b[p], v)) b[i] = std::move(b[p]), i = p;
54 53057 break;
55 }
56 2277821 b[i] = std::move(v);
57 2277821 }
58 template <class I, class C>
59 4 CEXP void pdmin_1ch_(I b, u32 i, C&& c) NE {
60
2/2
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 2 times.
 4 if (cu32 ch = ch1idx_(i); c(b[ch], b[i])) swap(b[i], b[ch]);
61 4 }
62 template <class I, class C>
63 48902 CEXP void pdmin_1lvl_(I b, u32 i, C&& c) NE {
64
2/2
✓ Branch 7 taken 32699 times.
✓ Branch 8 taken 16203 times.
 48902 if (cu32 ch1 = ch1idx_(i), chs = ch1 + !!c(b[ch1 + 1], b[ch1]); c(b[chs], b[i])) swap(b[i], b[chs]);
65 48902 }
66 template <class I, class C>
67 1976430 CEXP void pdmax_(I b, TPN std::iterator_traits<I>::value_type v, u32 i, u32 l, C&& c) NE {
68 12737834 for (;;)
69
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 1 taken 8291311 times.
✓ Branch 2 taken 1089417 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 1 taken 464699 times.
✓ Branch 2 taken 322690 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 1 taken 4151448 times.
✓ Branch 2 taken 394699 times.
 14714264 if (cu32 gch_lst = gchls_idx_(i); gch_lst < l) {
70 12907458 auto it = b + gch_lst;
71 12907458 u32 h1m = gch_lst - 2 - !!c(it[-2], it[-3]),
72 12907458 h2m = gch_lst - !!c(it[0], it[-1]),
73
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 4101466 times.
✓ Branch 4 taken 4189845 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 232054 times.
✓ Branch 4 taken 232645 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 2105153 times.
✓ Branch 4 taken 2046295 times.
 12907458 s = c(b[h1m], b[h2m]) ? h2m : h1m;
74
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 2 taken 36306 times.
✓ Branch 3 taken 8255005 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 2 taken 27136 times.
✓ Branch 3 taken 437563 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 2 taken 106182 times.
✓ Branch 3 taken 4045266 times.
 12907458 if (!c(v, b[s])) break;
75 12737834 b[i] = std::move(b[s]);
76
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 272003 times.
✓ Branch 4 taken 7983002 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 57693 times.
✓ Branch 4 taken 379870 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 172185 times.
✓ Branch 4 taken 3873081 times.
 12737834 if (cu32 p = pidx_(i = s); c(v, b[p])) swap(b[p], v);
77 } else {
78 1806806 cu32 ch1 = ch1idx_(i);
79
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 0 taken 458462 times.
✓ Branch 1 taken 630955 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 0 taken 27768 times.
✓ Branch 1 taken 294922 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 0 taken 342713 times.
✓ Branch 1 taken 51986 times.
 1806806 if (ch1 >= l) break;
80 977863 cu32 gch1 = gch_lst - 3, s = l_dec_(b, l, ch1, gch1, c);
81
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 2 taken 181624 times.
✓ Branch 3 taken 449331 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 2 taken 83567 times.
✓ Branch 3 taken 211355 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 2 taken 31006 times.
✓ Branch 3 taken 20980 times.
 977863 if (!c(v, b[s])) break;
82
6/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 438521 times.
✓ Branch 4 taken 10810 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✓ Branch 3 taken 211351 times.
✓ Branch 4 taken 4 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 13191 times.
✓ Branch 4 taken 7789 times.
 681666 if (b[i] = std::move(b[s]); (i = s) < gch1) break;
83
5/6
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 1810 times.
✓ Branch 4 taken 9000 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >::value_type, unsigned int, unsigned int, std::less<void>&):
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
void tifa_libs::depq_impl_::pdmax_<__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> > >, std::iterator_traits<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >::value_type, unsigned int, unsigned int, std::less<void>&&):
✓ Branch 3 taken 37 times.
✓ Branch 4 taken 7752 times.
 18603 if (cu32 p = pidx_(i); c(v, b[p])) b[i] = std::move(b[p]), i = p;
84 18603 break;
85 }
86 1976430 b[i] = std::move(v);
87 1976430 }
88 template <class I, class C>
89 9 CEXP void pdmax_1ch_(I b, u32 i, C&& c) NE {
90
2/2
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 4 times.
 9 if (cu32 ch = ch1idx_(i); c(b[i], b[ch])) swap(b[i], b[ch]);
91 9 }
92 template <class I, class C>
93 951670 CEXP void pdmax_1lvl_(I b, u32 i, C&& c) NE {
94 951670 cu32 ch1 = ch1idx_(i), chb = ch1 + !!c(b[ch1], b[ch1 + 1]);
95
2/2
✓ Branch 3 taken 634828 times.
✓ Branch 4 taken 316842 times.
 951670 if (c(b[i], b[chb])) swap(b[i], b[chb]);
96 951670 }
97 } // namespace depq_impl_
98
99 template <class I, class C = std::less<>>
100 CEXP bool is_minmax_heap(I begin, I end, C&& comp = C{}) NE {
101 cu32 l = u32(end - begin);
102 auto f = [](u32 i, auto cf) NE {
103 cu32 ch1 = depq_impl_::ch1idx_(i), ch2 = ch1 + 1,
104 gch1 = depq_impl_::ch1idx_(ch1),
105 gch2 = gch1 + 1,
106 gch3 = depq_impl_::ch1idx_(ch2),
107 gch4 = gch3 + 1;
108 return cf(ch1) && cf(ch2) && cf(gch1) && cf(gch2) && cf(gch3) && cf(gch4);
109 };
110 flt_ (u32, i, 0, l)
111 if (depq_impl_::is_mini(i)) {
112 if (!f(i, [&](u32 c) { return c >= l || !comp(begin[c], begin[i]); })) return false;
113 } else if (!f(i, [&](u32 c) { return c >= l || !comp(begin[i], begin[c]); })) return false;
114 return true;
115 }
116 template <common_range R, class C = std::less<>>
117 CEXP bool is_minmax_heap(R CR r, C&& comp = C{}) NE { return is_minmax_heap(begin(r), end(r), std::forward<C>(comp)); }
118 template <class I, class C = std::less<>>
119 3249779 void push_minmax_heap(I begin, I end, C&& comp = C{}) NE {
120 3249779 cu32 len = u32(end - begin), parent = depq_impl_::pidx_(len - 1);
121 3249779 u32 idx = len - 1;
122 3249779 TPN std::iterator_traits<I>::value_type value = std::move(end[-1]);
123
4/4
void tifa_libs::push_minmax_heap<__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 1605276 times.
✓ Branch 2 taken 143345 times.
void tifa_libs::push_minmax_heap<__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 349876 times.
✓ Branch 2 taken 1151282 times.
 3249779 if (depq_impl_::is_minni(len)) {
124
4/4
void tifa_libs::push_minmax_heap<__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 1604620 times.
✓ Branch 1 taken 656 times.
void tifa_libs::push_minmax_heap<__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 349872 times.
✓ Branch 1 taken 4 times.
 1955152 if (idx == 0) static_cast<void>(0);
125
4/4
void tifa_libs::push_minmax_heap<__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 302960 times.
✓ Branch 3 taken 1301660 times.
void tifa_libs::push_minmax_heap<__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 134876 times.
✓ Branch 3 taken 214996 times.
 1954492 else if (comp(begin[parent], value)) {
126 437836 begin[idx] = std::move(begin[parent]), idx = parent;
127 437836 goto push_up_max;
128 } else {
129 2597727 for (;;) {
130
4/4
void tifa_libs::push_minmax_heap<__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 3 taken 2339047 times.
✓ Branch 4 taken 1104218 times.
void tifa_libs::push_minmax_heap<__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 3 taken 200713 times.
✓ Branch 4 taken 470405 times.
 4114383 if (cu32 gp = depq_impl_::gpidx_(idx); comp(value, begin[gp])) begin[idx] = std::move(begin[gp]), idx = gp;
131 1574623 else break;
132 2858699 push_up_min:
133
4/4
void tifa_libs::push_minmax_heap<__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 260967 times.
✓ Branch 1 taken 2141605 times.
void tifa_libs::push_minmax_heap<__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 5 times.
✓ Branch 1 taken 456122 times.
 2858699 if (!idx) break;
134 }
135 }
136
4/4
void tifa_libs::push_minmax_heap<__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 63525 times.
✓ Branch 3 taken 79820 times.
void tifa_libs::push_minmax_heap<__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 255414 times.
✓ Branch 3 taken 895868 times.
 1294627 } else if (comp(value, begin[parent])) {
137 318939 begin[idx] = std::move(begin[parent]), idx = parent;
138 318939 goto push_up_min;
139 } else
140 975688 push_up_max:
141
4/4
void tifa_libs::push_minmax_heap<__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 1474763 times.
✓ Branch 1 taken 179738 times.
void tifa_libs::push_minmax_heap<__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 2073213 times.
✓ Branch 1 taken 83627 times.
 3811341 while (idx > 2)
142
4/4
void tifa_libs::push_minmax_heap<__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 3 taken 1271721 times.
✓ Branch 4 taken 203042 times.
void tifa_libs::push_minmax_heap<__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 3 taken 1126096 times.
✓ Branch 4 taken 947117 times.
 3547976 if (cu32 gp = depq_impl_::gpidx_(idx); comp(begin[gp], value)) begin[idx] = std::move(begin[gp]), idx = gp;
143 1150159 else break;
144 3249779 begin[idx] = std::move(value);
145 3249779 }
146 template <common_range R, class C = std::less<>>
147 CEXP bool push_minmax_heap(R CR r, C&& comp = C{}) NE { return push_minmax_heap(begin(r), end(r), std::forward<C>(comp)); }
148 template <class I, class C = std::less<>>
149 1627386 CEXP void pop_minmax_heap_min(I begin, I end, C&& comp = C{}) NE {
150
2/2
✓ Branch 1 taken 322 times.
✓ Branch 2 taken 1627064 times.
 1627386 if (cu32 l = u32(end - begin) - 1; l == 0) return;
151 1627064 else depq_impl_::pdmin_(begin, std::exchange(end[-1], std::move(begin[0])), 0, l, comp);
152 }
153 template <common_range R, class C = std::less<>>
154 CEXP bool pop_minmax_heap_min(R CR r, C&& comp = C{}) NE { return pop_minmax_heap_min(begin(r), end(r), std::forward<C>(comp)); }
155 template <class I, class C = std::less<>>
156 1627222 CEXP void pop_minmax_heap_max(I begin, I end, C&& comp = C{}) NE {
157 1627222 cu32 l = u32(end - begin) - 1;
158
4/4
void tifa_libs::pop_minmax_heap_max<__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 616 times.
✓ Branch 1 taken 1125723 times.
void tifa_libs::pop_minmax_heap_max<__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 2 times.
✓ Branch 1 taken 500881 times.
 1627222 if (l <= 1) return;
159 1626604 cu32 idx = 1 + !!comp(begin[1], begin[2]);
160 1626604 depq_impl_::pdmax_(begin, std::exchange(end[-1], std::move(begin[idx])), idx, l, std::forward<C>(comp));
161 }
162 template <common_range R, class C = std::less<>>
163 CEXP bool pop_minmax_heap_max(R CR r, C&& comp = C{}) NE { return pop_minmax_heap_max(begin(r), end(r), std::forward<C>(comp)); }
164 template <class I, class C = std::less<>>
165 18 CEXP void make_minmax_heap(I begin, I end, C&& comp = C{}) NE {
166 18 cu32 l = u32(end - begin);
167 18 u32 idx = l / 2;
168
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 17 times.
 18 if (idx == 0) return;
169
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 4 times.
 17 if ((l & 1) == 0) {
170
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 9 times.
 13 if (--idx; depq_impl_::is_mini(idx)) depq_impl_::pdmin_1ch_(begin, idx, comp);
171 9 else depq_impl_::pdmax_1ch_(begin, idx, comp);
172
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 if (idx == 0) return;
173 }
174
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 1 time.
 17 if (l != 4) {
175 32 for (cu32 lidx_ngch = l / 4;;) {
176 32 const auto hib = depq_impl_::hib_(idx);
177 32 cu32 loplim = max(lidx_ngch, (1_u32 << hib) - 1);
178
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (--idx; hib & 1)
179 951654 for (;; --idx) {
180
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 951654 times.
 951670 if (depq_impl_::pdmax_1lvl_(begin, idx, comp); idx == loplim) break;
181 }
182 else {
183 48886 for (;; --idx) {
184
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 48886 times.
 48902 if (depq_impl_::pdmin_1lvl_(begin, idx, comp); idx == loplim) break;
185 }
186
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (idx == 0) return;
187 }
188
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (idx == lidx_ngch) break;
189 }
190 }
191 17 const auto hib = depq_impl_::hib_(idx);
192
2/3
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 17 switch (u32 loplim = (1_u32 << hib) - 1; hib & 1)
193 for (;;) {
194 88 case 0:
195 for (;;) {
196 650757 --idx;
197 650757 depq_impl_::pdmin_(begin, std::move(begin[idx]), idx, l, comp);
198
2/2
✓ Branch 0 taken 99 times.
✓ Branch 1 taken 650658 times.
 650757 if (idx == loplim) break;
199 }
200
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 82 times.
 99 if (idx == 0) return;
201 82 loplim /= 2;
202 [[fallthrough]];
203 88 case 1:
204 for (;;) {
205 349826 --idx;
206 349826 depq_impl_::pdmax_(begin, std::move(begin[idx]), idx, l, comp);
207
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 349738 times.
 349826 if (idx == loplim) break;
208 }
209 88 loplim /= 2;
210 }
211 }
212 template <common_range R, class C = std::less<>>
213 CEXP bool make_minmax_heap(R CR r, C&& comp = C{}) NE { return make_minmax_heap(begin(r), end(r), std::forward<C>(comp)); }
214
215 } // namespace tifa_libs
216