GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 93 / 0 / 93
Functions: 100.0% 18 / 0 / 18
Branches: 97.2% 70 / 0 / 72
src/ds/kdtree/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../util/alias/others/lib.hpp"
4 #include "../../util/traits/math/lib.hpp"
5 #include "../bt_trv/lib.hpp"
6
7 namespace tifa_libs {
8
9 template <class T, auto op, arithm_c Coord = i32, u32 K = 2, bool remove_empty_node = false>
10 class kdtree {
11 static_assert(K);
12 struct TIFA;
13
14 public:
15 using point = arr<Coord, K>;
16
17 private:
18 using pointer = TIFA*;
19 using const_pointer = const TIFA*;
20 struct TIFA {
21 // NOLINTNEXTLINE(modernize-avoid-c-arrays)
22 pointer ch[2];
23 T sum, val;
24 point min, max, coord;
25 template <u32 k>
26 requires /**/ (k < K)
27 1246717544 static CEXP bool cmp(const_pointer l, const_pointer r) { return l->coord[k] < r->coord[k]; }
28 };
29
30 const T E;
31 cu32 B;
32 u32 cnt{0};
33
34 1376420 CEXP pointer newnode(cT_(point) p, cT_(T) val) {
35 1376420 pointer x = alloc.allocate(1);
36 1376420 x->ch[0] = x->ch[1] = nullptr, x->sum = x->val = val;
37
2/2
✓ Branch 4 taken 2752840 times.
✓ Branch 5 taken 1376420 times.
 4129260 flt_ (u32, i, 0, K) x->min[i] = x->max[i] = x->coord[i] = p[i];
38 1376420 return x;
39 }
40 51467690 CEXP void pushup(pointer x) NE {
41 51467690 auto [l, r] = x->ch;
42 51467690 x->sum = x->val;
43
2/2
✓ Branch 0 taken 38359287 times.
✓ Branch 1 taken 13108403 times.
 51467690 if (l) {
44 38359287 x->sum = op(x->sum, l->sum);
45
2/2
✓ Branch 4 taken 76718574 times.
✓ Branch 5 taken 38359287 times.
 115077861 flt_ (u32, i, 0, K) x->max[i] = max(l->max[i], x->max[i]);
46
2/2
✓ Branch 4 taken 76718574 times.
✓ Branch 5 taken 38359287 times.
 115077861 flt_ (u32, i, 0, K) x->min[i] = min(l->min[i], x->min[i]);
47 }
48
2/2
✓ Branch 0 taken 33272374 times.
✓ Branch 1 taken 18195316 times.
 51467690 if (r) {
49 33272374 x->sum = op(x->sum, r->sum);
50
2/2
✓ Branch 4 taken 66544748 times.
✓ Branch 5 taken 33272374 times.
 99817122 flt_ (u32, i, 0, K) x->max[i] = max(r->max[i], x->max[i]);
51
2/2
✓ Branch 4 taken 66544748 times.
✓ Branch 5 taken 33272374 times.
 99817122 flt_ (u32, i, 0, K) x->min[i] = min(r->min[i], x->min[i]);
52 }
53 51467690 }
54
55 template <u32 k>
56 requires /**/ (k < K)
57 59154452 CEXP void build(pointer& x, vec<pointer>& h, u32 l, u32 r) NE {
58
4/4
void tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::build<0u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::vector<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*> >&, unsigned int, unsigned int):
✓ Branch 0 taken 11827013 times.
✓ Branch 1 taken 15775813 times.
void tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::build<1u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::vector<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*> >&, unsigned int, unsigned int):
✓ Branch 0 taken 17750439 times.
✓ Branch 1 taken 13801187 times.
 59154452 if (l >= r) return;
59 29577000 u32 mid = l + (r - l) / 2;
60 29577000 nth_element(begin(h) + l, begin(h) + mid, begin(h) + r, TIFA::template cmp<k>);
61 29577000 x = h[mid], x->sum = x->val;
62
4/4
void tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::build<0u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::vector<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*> >&, unsigned int, unsigned int):
✓ Branch 3 taken 31551626 times.
✓ Branch 4 taken 15775813 times.
void tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::build<1u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::vector<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*> >&, unsigned int, unsigned int):
✓ Branch 3 taken 27602374 times.
✓ Branch 4 taken 13801187 times.
 88731000 flt_ (u32, i, 0, K) x->min[i] = x->max[i] = x->coord[i];
63 29577000 build<(k + 1) % K>(x->ch[0], h, l, mid), build<(k + 1) % K>(x->ch[1], h, mid + 1, r);
64 29577000 pushup(x);
65 }
66 452 CEXP void rebuild(pointer& x) NE {
67 452 vec<pointer> h;
68 59154904 auto flatten = [&](auto&& f, pointer& x) -> void {
69
2/2
✓ Branch 0 taken 29577452 times.
✓ Branch 1 taken 29577000 times.
 59154452 if (!x) return;
70 if CEXP (remove_empty_node) {
71 auto _ = x->val == E;
72 if (!_) h.push_back(x);
73 f(f, x->ch[0]), f(f, x->ch[1]);
74 if (_) alloc.deallocate(x, 1);
75 29577000 } else h.push_back(x), f(f, x->ch[0]), f(f, x->ch[1]);
76 29577000 x = nullptr;
77 };
78 452 flatten(flatten, x), build<0>(x, h, 0, (u32)h.size());
79 452 }
80
81 template <bool use_set, u32 k>
82 requires /**/ (k < K)
83 23267110 CEXP bool ins_set_(pointer& x, cT_(point) p, cT_(T) val) NE {
84
4/4
bool tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::ins_set_<false, 0u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::array<int, 2ul>, long):
✓ Branch 0 taken 640739 times.
✓ Branch 1 taken 11320500 times.
bool tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::ins_set_<false, 1u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::array<int, 2ul>, long):
✓ Branch 0 taken 735681 times.
✓ Branch 1 taken 10570190 times.
 23267110 if (!x) {
85 1376420 x = newnode(p, val);
86 1376420 return true;
87 }
88 bool f;
89
4/4
bool tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::ins_set_<false, 0u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::array<int, 2ul>, long):
✓ Branch 1 taken 14629 times.
✓ Branch 2 taken 11305871 times.
bool tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::ins_set_<false, 1u>(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*&, std::array<int, 2ul>, long):
✓ Branch 1 taken 12215 times.
✓ Branch 2 taken 10557975 times.
 21890690 if (p == x->coord) {
90 26844 f = false;
91 26844 if CEXP (!use_set) x->val = op(x->val, val), x->sum = op(x->sum, val);
92 else {
93 x->val = val, x->sum = val;
94 if (x->ch[0]) x->sum = op(x->sum, x->ch[0]->sum);
95 if (x->ch[1]) x->sum = op(x->sum, x->ch[1]->sum);
96 }
97 21863846 } else f = ins_set_<use_set, (k + 1) % K>(x->ch[p[k] >= x->coord[k]], p, val);
98 21890690 pushup(x);
99 21890690 return f;
100 }
101
102 453410841 CEXP bool check_range(const_pointer x, cT_(point) L, cT_(point) R) CNE {
103
2/2
✓ Branch 0 taken 764759353 times.
✓ Branch 1 taken 139539936 times.
 904299289 flt_ (u32, i, 0, K)
104
6/6
✓ Branch 2 taken 604988806 times.
✓ Branch 3 taken 159770547 times.
✓ Branch 6 taken 154100358 times.
✓ Branch 7 taken 450888448 times.
✓ Branch 8 taken 313870905 times.
✓ Branch 9 taken 450888448 times.
 764759353 if (x->min[i] < L[i] || R[i] < x->max[i]) return false;
105 139539936 return true;
106 }
107 313870905 CEXP bool check_point(const_pointer x, cT_(point) L, cT_(point) R) CNE {
108
2/2
✓ Branch 0 taken 556623997 times.
✓ Branch 1 taken 150388388 times.
 707012385 flt_ (u32, i, 0, K)
109
6/6
✓ Branch 2 taken 479357970 times.
✓ Branch 3 taken 77266027 times.
✓ Branch 6 taken 86216490 times.
✓ Branch 7 taken 393141480 times.
✓ Branch 8 taken 163482517 times.
✓ Branch 9 taken 393141480 times.
 556623997 if (x->coord[i] < L[i] || R[i] < x->coord[i]) return false;
110 150388388 return true;
111 }
112 627741810 CEXP bool check(const_pointer x, cT_(point) L, cT_(point) R) CNE {
113
2/2
✓ Branch 0 taken 20485518 times.
✓ Branch 1 taken 607256292 times.
 627741810 if (!x) return false;
114
2/2
✓ Branch 0 taken 1149349520 times.
✓ Branch 1 taken 452848644 times.
 1602198164 flt_ (u32, i, 0, K)
115
6/6
✓ Branch 2 taken 1073579966 times.
✓ Branch 3 taken 75769554 times.
✓ Branch 6 taken 78638094 times.
✓ Branch 7 taken 994941872 times.
✓ Branch 8 taken 154407648 times.
✓ Branch 9 taken 994941872 times.
 1149349520 if (R[i] < x->min[i] || x->max[i] < L[i]) return false;
116 452848644 return true;
117 }
118 453410841 CEXP void query_(const_pointer x, cT_(point) L, cT_(point) R, T& ans) CNE {
119
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 453410841 times.
 453410841 if (!x) return;
120
2/2
✓ Branch 1 taken 139539936 times.
✓ Branch 2 taken 313870905 times.
 453410841 if (check_range(x, L, R)) {
121 139539936 ans = op(ans, x->sum);
122 139539936 return;
123 }
124
2/2
✓ Branch 1 taken 150388388 times.
✓ Branch 2 taken 163482517 times.
 313870905 if (check_point(x, L, R)) ans = op(ans, x->val);
125
2/2
✓ Branch 1 taken 233688038 times.
✓ Branch 2 taken 80182867 times.
 313870905 if (check(x->ch[0], L, R)) query_(x->ch[0], L, R, ans);
126
2/2
✓ Branch 1 taken 219160606 times.
✓ Branch 2 taken 94710299 times.
 313870905 if (check(x->ch[1], L, R)) query_(x->ch[1], L, R, ans);
127 }
128
129 public:
130 pointer root{nullptr};
131
132 // threshold = $O\left(\sqrt{n\log n}\right)$
133
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 18 times.
 18 CEXPE kdtree(u32 rebuild_threshold, cT_(T) e = T{}) NE : E{e}, B{rebuild_threshold} { assert(rebuild_threshold > 1); }
134 kdtree(kdtree CR) = delete;
135 kdtree& operator=(kdtree CR) = delete;
136 18 CEXP ~kdtree() NE { dealloc_subtree(root, alloc); }
137
138 1403264 CEXP void insert(cT_(point) coord, cT_(T) val) NE {
139
2/2
✓ Branch 1 taken 452 times.
✓ Branch 2 taken 1402812 times.
 1403264 if ((cnt += ins_set_<false, 0>(root, coord, val)) == B) cnt = 0, rebuild(root);
140 1403264 }
141 CEXP void set(cT_(point) coord, cT_(T) val) NE {
142 if ((cnt += ins_set_<true, 0>(root, coord, val)) == B) cnt = 0, rebuild(root);
143 }
144 //! [L, R]
145 562197 CEXP T query(cT_(point) L, cT_(point) R) CNE {
146 562197 T ans{E};
147 562197 query_(root, L, R, ans);
148 562197 return ans;
149 }
150
151 private:
152 alc<TIFA> alloc;
153 };
154
155 } // namespace tifa_libs
156