GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 33 / 0 / 33
Functions: 100.0% 11 / 0 / 11
Branches: 100.0% 12 / 0 / 12
src/ds/heap/radix/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/others/lib.hpp"
4
5 namespace tifa_libs {
6
7 template <std::unsigned_integral K, class V, class C = std::less<K>>
8 class radix_heap {
9 static CEXP u32 B = sizeof(K) * 8;
10 static CEXP C comp{};
11 arr<vecp<K, V>, B + 1> vs;
12 arr<K, B + 1> ms;
13 u32 s{0};
14 K last{0};
15
16 public:
17 CEXP radix_heap() NE { fill(ms, K(-1)); }
18
19 930 ND CEXP u32 size() CNE { return s; }
20 12219573 ND CEXP bool empty() CNE { return !s; }
21 12172865 CEXP void emplace(K key, cT_(V) val) NE {
22 12172865 const K b = (K)std::bit_width(key ^ last);
23 12172865 ++s, vs[b].emplace_back(key, val), ms[b] = min(key, ms[b], comp);
24 12172865 }
25 24345646 CEXP std::pair<K, V> top() NE {
26
4/4
tifa_libs::radix_heap<unsigned int, unsigned int, std::less<unsigned int> >::top():
✓ Branch 1 taken 221541 times.
✓ Branch 2 taken 739189 times.
tifa_libs::radix_heap<unsigned long, unsigned int, std::less<unsigned long> >::top():
✓ Branch 1 taken 9885695 times.
✓ Branch 2 taken 13499221 times.
 24345646 if (!~ms[0]) {
27 206774503 cu32 idx = u32(find_if(ms, [](auto x) NE { return !!~x; }) - begin(ms));
28
4/4
auto tifa_libs::radix_heap<unsigned int, unsigned int, std::less<unsigned int> >::top()::{lambda(auto:1)#1}::operator()<unsigned int>(unsigned int) const:
✓ Branch 6 taken 2279649 times.
✓ Branch 7 taken 221541 times.
auto tifa_libs::radix_heap<unsigned long, unsigned int, std::less<unsigned long> >::top()::{lambda(auto:1)#1}::operator()<unsigned long>(unsigned long) const:
✓ Branch 6 taken 47424008 times.
✓ Branch 7 taken 9885695 times.
 59810893 for (last = ms[idx]; auto& p : vs[idx]) {
29 49703657 const K b = (K)std::bit_width(p.first ^ last);
30 49703657 vs[b].emplace_back(p), ms[b] = min(p.first, ms[b], comp);
31 }
32 10107236 vs[idx].clear(), ms[idx] = K(-1);
33 }
34 24345646 return vs[0].back();
35 }
36
37 12172823 CEXP void pop() NE {
38
4/4
tifa_libs::radix_heap<unsigned int, unsigned int, std::less<unsigned int> >::pop():
✓ Branch 5 taken 221661 times.
✓ Branch 6 taken 258704 times.
tifa_libs::radix_heap<unsigned long, unsigned int, std::less<unsigned long> >::pop():
✓ Branch 5 taken 9988037 times.
✓ Branch 6 taken 1704421 times.
 12172823 if (top(), --s, vs[0].pop_back(); vs[0].empty()) ms[0] = K(-1);
39 12172823 }
40 };
41
42 template <class K, class V>
43 using rheap = std::conditional_t<std::unsigned_integral<K>, radix_heap<K, V>, pqg<std::pair<K, V>>>;
44 template <class K, class V>
45 using rheapg = std::conditional_t<std::unsigned_integral<K>, radix_heap<K, V, std::greater<K>>, pq<std::pair<K, V>>>;
46
47 } // namespace tifa_libs
48