GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 93.7% 119 / 0 / 127
Functions: 100.0% 44 / 0 / 44
Branches: 67.3% 70 / 0 / 104
src/ds/dbitset/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../bit/parity/lib.hpp"
4 #include "../../util/traits/math/lib.hpp"
5 #include "../../util/traits/others/lib.hpp"
6
7 namespace tifa_libs {
8
9 struct dbitset {
10 using word_t = u64;
11 static CEXP u32 word_width = 64;
12
13 protected:
14 u64 sz;
15 vec<word_t> data;
16
17 104824816 static CEXP auto idx_word(u64 n) NE { return u32(n / word_width); }
18 105090223 static CEXP auto idx_bit(u64 n) NE { return (u32)n % word_width; }
19 225 static CEXP auto word_count(u64 n) NE { return idx_word(n) + !!idx_bit(n); }
20 38259186 static CEXP auto mask_bit(u64 n) NE { return 1_u64 << idx_bit(n); }
21 253071 static CEXP u64 mask_outrange(u64 n) NE {
22
2/2
✓ Branch 1 taken 253013 times.
✓ Branch 2 taken 58 times.
 253071 if (!idx_bit(n)) return 0;
23 58 return -1_u64 << idx_bit(n);
24 }
25
26 16 CEXP void lsh_(umost64_c auto n) NE {
27
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
 16 if (data.empty()) {
28 ✗ bit_resize(n);
29 ✗ return;
30 }
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (!n) return;
32 16 const auto pre = data.size();
33 16 cu32 w = idx_word(n), ofs = idx_bit(n);
34 16 data.resize(data.size() + w);
35
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (!ofs)
36 ✗ for (auto i = pre - 1; ~i; --i) data[i + w] = data[i];
37 else {
38 16 cu32 cofs = word_width - ofs;
39
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
 16 for (auto i = pre - 1; i; --i) data[i + w] = data[i] << ofs | data[i - 1] >> cofs;
40 16 data[w] = data[0] << ofs;
41 }
42 16 fill(begin(data), begin(data) + w, 0), sz += n;
43 }
44 16 CEXP void rsh_(umost64_c auto n) NE {
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (n >= sz) {
46 ✗ sz = 0, data.clear();
47 ✗ return;
48 }
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (!n) return;
50 16 cu32 w = idx_word(n), ofs = idx_bit(n);
51 16 cu32 lim = word_size() - w - 1;
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (!ofs)
53 ✗ flt_ (u32, i, 0, lim + 1) data[i] = data[i + w];
54 else {
55 16 cu32 cofs = word_width - ofs;
56
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
 16 flt_ (u32, i, 0, lim) data[i] = data[i + w] >> ofs | data[i + w + 1] << cofs;
57 16 data[lim] = data.back() >> ofs;
58 }
59 16 data.resize(data.size() - w), sz -= n;
60 }
61
62 public:
63 187 CEXPE dbitset(usz n, bool val = false) NE { bit_resize(n, val); }
64 CEXP dbitset(usz n, int_c auto val) NE { from_integer(val, n); }
65 template <class F>
66 requires requires(F f) { { f() } -> std::same_as<word_t>; }
67 38 CEXP dbitset(usz n, F&& gen) NE { set(std::forward<F>(gen), n); }
68 CEXP dbitset(strnv s, usz pos = 0, usz n = -1_usz, chr zero = '0', chr one = '1') NE { set(s, pos, n, zero, one); }
69
70 CEXP dbitset& from_integer(int_c auto val, usz n = -1_usz) NE {
71 const auto nbits = min({n, sizeof(val) * 8});
72 if (bit_resize(nbits); val && !data.empty()) {
73 if CEXP (sizeof(val) * 8 <= word_width) data[0] = (word_t)val & ~mask_outrange(sz);
74 else {
75 for (u32 i = 0; i < data.size() && val; val >>= word_width, ++i) data[i] = (word_t)val;
76 data.back() &= ~mask_outrange(sz);
77 }
78 }
79 return *this;
80 }
81 CEXP dbitset& set(strnv s, usz pos = 0, usz n = -1_usz, chr = '0', chr one = '1') NE {
82 const auto nbits = min({sz, n, s.size() - pos});
83 bit_resize(nbits);
84 for (usz i = nbits; i; --i)
85 if (s[pos + nbits - i] == one) set(i - 1);
86 return *this;
87 }
88 template <class F>
89 requires requires(F f) { { f() } -> std::same_as<word_t>; }
90 38 CEXP dbitset& set(F&& gen, usz n) NE {
91 38 bit_resize(n);
92
2/2
✓ Branch 1 taken 37 times.
✓ Branch 2 taken 1 time.
 38 if (!data.empty())
93
2/2
✓ Branch 6 taken 148650 times.
✓ Branch 7 taken 37 times.
 148687 for (auto& i : data) i = gen();
94 38 return *this;
95 }
96
97
3/4
✓ Branch 0 taken 10262 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1511 times.
✓ Branch 4 taken 8751 times.
 10262 friend CEXP bool operator==(dbitset CR l, dbitset CR r) NE { return l.sz == r.sz && l.data == r.data; }
98
99 555 ND CEXP u64 find_first() CNE {
100
2/2
✓ Branch 1 taken 552 times.
✓ Branch 2 taken 36 times.
 588 flt_ (u32, i, 0, word_size())
101
2/2
✓ Branch 1 taken 519 times.
✓ Branch 2 taken 33 times.
 552 if (data[i]) return i * 64_u64 + (u32)std::countr_zero(data[i]);
102 36 return sz;
103 }
104 66565612 ND CEXP u64 find_next(u64 prev) CNE {
105
2/2
✓ Branch 0 taken 283 times.
✓ Branch 1 taken 66565329 times.
 66565612 if (++prev >= sz) return sz;
106 66565329 size_t i = idx_word(prev);
107
2/2
✓ Branch 3 taken 65528250 times.
✓ Branch 4 taken 1037079 times.
 66565329 if (const word_t _ = data[i] & -1_u64 << idx_bit(prev); _) return i * word_width + (u32)std::countr_zero(_);
108
2/2
✓ Branch 1 taken 1036836 times.
✓ Branch 2 taken 243 times.
 1037079 for (++i; i < word_size(); ++i)
109
1/2
✓ Branch 1 taken 1036836 times.
✗ Branch 2 not taken.
 1036836 if (data[i]) return i * word_width + (u32)std::countr_zero(data[i]);
110 243 return sz;
111 }
112
113 297296 CEXP auto& raw() NE { return data; }
114 28712197 ND CEXP word_t CR getword(usz n) CNE { return data[idx_word(n)]; }
115 9547033 CEXP word_t& getword(usz n) NE { return data[idx_word(n)]; }
116 28712197 CEXP bool operator[](usz n) CNE { return getword(n) & mask_bit(n); }
117
118 12318 ND CEXP bool all() CNE {
119
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 12318 times.
 12318 if (data.empty()) return false;
120
2/2
✓ Branch 2 taken 12318 times.
✓ Branch 3 taken 4 times.
 12322 flt_ (u32, i, 0, (u32)data.size() - !!idx_bit(sz))
121
2/2
✓ Branch 1 taken 12314 times.
✓ Branch 2 taken 4 times.
 12318 if (~data[i]) return false;
122
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
 4 if (idx_bit(sz)) return (data.back() & ~mask_outrange(sz)) == ~mask_outrange(sz);
123 4 return true;
124 }
125 45216 ND CEXP bool any() CNE {
126
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 45216 times.
 45216 if (data.empty()) return false;
127
2/2
✓ Branch 5 taken 45216 times.
✓ Branch 6 taken 1241 times.
 46457 for (auto i : data)
128
2/2
✓ Branch 0 taken 43975 times.
✓ Branch 1 taken 1241 times.
 45216 if (i) return true;
129 1241 return false;
130 }
131 22683 ND CEXP bool none() CNE {
132
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 22683 times.
 22683 if (data.empty()) return false;
133 22683 return !any();
134 }
135 322490 ND CEXP u64 count() CNE {
136 322490 u64 ans = 0;
137
2/2
✓ Branch 6 taken 322490 times.
✓ Branch 7 taken 322490 times.
 644980 for (const auto i : data) ans += (u32)std::popcount(i);
138 322490 return ans;
139 }
140 75 ND CEXP bool parity() CNE {
141 75 bool ans = false;
142
2/2
✓ Branch 6 taken 297311 times.
✓ Branch 7 taken 75 times.
 297386 for (const auto i : data) ans ^= ::tifa_libs::parity(i);
143 75 return ans;
144 }
145
146 4755043 ND CEXP u64 CR size() CNE { return sz; }
147 1290342 ND CEXP u32 word_size() CNE { return (u32)data.size(); }
148 225 CEXP void bit_resize(usz n, bool val = false) NE {
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 225 times.
 225 data.resize(word_count(sz = n), val ? -1_u64 : 0);
150
2/6
✗ Branch 0 not taken.
✓ Branch 1 taken 225 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 225 times.
 225 if (val && !data.empty()) data.back() &= ~mask_outrange(sz);
151 225 }
152
153 #define OP__(op) \
154 CEXP dbitset& operator op## = (dbitset CR r)NE { \
155 if (r.sz > sz) data.resize(r.word_size()), sz = r.sz; \
156 if (data.empty()) return *this; \
157 flt_ (u32, i, 0, r.word_size()) data[i] op## = r.data[i]; \
158 data.back() &= ~mask_outrange(sz); \
159 return *this; \
160 } \
161 CEXP dbitset operator op(dbitset CR r) CNE { return dbitset(*this) op## = r; }
162
4/6
✗ Branch 0 not taken.
✓ Branch 1 taken 251675 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 251675 times.
✓ Branch 10 taken 251675 times.
✓ Branch 11 taken 251675 times.
 754662 OP__(&)
163
4/6
✗ Branch 0 not taken.
✓ Branch 1 taken 642 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 642 times.
✓ Branch 10 taken 642 times.
✓ Branch 11 taken 642 times.
 1298 OP__(|)
164
4/6
✗ Branch 0 not taken.
✓ Branch 1 taken 375 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 375 times.
✓ Branch 10 taken 375 times.
✓ Branch 11 taken 375 times.
 764 OP__(^)
165 #undef OP__
166 379 CEXP dbitset operator~() CNE { return dbitset(*this).flip(); }
167 16 CEXP dbitset& operator<<=(imost64_c auto n) NE {
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (n < 0) [[unlikely]]
169 ✗ rsh_((to_uint_t<decltype(n)>)-n);
170 16 else lsh_((to_uint_t<decltype(n)>)n);
171 16 return *this;
172 }
173 16 CEXP dbitset operator<<(imost64_c auto n) CNE { return dbitset(*this) <<= n; }
174 16 CEXP dbitset& operator>>=(imost64_c auto n) NE {
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (n < 0) [[unlikely]]
176 ✗ lsh_((to_uint_t<decltype(n)>)-n);
177 16 else rsh_((to_uint_t<decltype(n)>)n);
178 16 return *this;
179 }
180 16 CEXP dbitset operator>>(imost64_c auto n) CNE { return dbitset(*this) >>= n; }
181
182 CEXP dbitset& set() NE {
183 fill(data, -1_u64);
184 if (!data.empty()) data.back() &= ~mask_outrange(sz);
185 return *this;
186 }
187 9524016 CEXP dbitset& set(usz pos, bool val = true) NE {
188
2/2
✓ Branch 0 taken 4766335 times.
✓ Branch 1 taken 4757681 times.
 9524016 if (val) getword(pos) |= mask_bit(pos);
189 4757681 else return reset(pos);
190 4766335 return *this;
191 }
192 CEXP dbitset& reset() NE {
193 fill(data, 0);
194 return *this;
195 }
196 4768994 CEXP dbitset& reset(usz pos) NE {
197 4768994 getword(pos) &= ~mask_bit(pos);
198 4768994 return *this;
199 }
200 379 CEXP dbitset& flip() NE {
201
2/2
✓ Branch 5 taken 379 times.
✓ Branch 6 taken 379 times.
 758 for (auto& i : data) i = ~i;
202
1/2
✓ Branch 1 taken 379 times.
✗ Branch 2 not taken.
 379 if (!data.empty()) data.back() &= ~mask_outrange(sz);
203 379 return *this;
204 }
205 11660 CEXP dbitset& flip(usz pos) NE {
206 11660 getword(pos) ^= mask_bit(pos);
207 11660 return *this;
208 }
209
210 555 ND CEXP strn to_string(chr zero = '0', chr one = '1') CNE {
211 555 strn ans(sz, zero);
212
1/2
✓ Branch 0 taken 555 times.
✗ Branch 1 not taken.
 555 if (zero != one) [[likely]]
213
2/2
✓ Branch 3 taken 57056369 times.
✓ Branch 4 taken 555 times.
 57056924 for (auto n = find_first(); n < sz; n = find_next(n)) ans[sz - n - 1] = one;
214 555 return ans;
215 }
216 template <int_c T>
217 22650 ND CEXP T to_integer() CNE {
218 if CEXP (sizeof(T) * 8 <= word_width) {
219
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 22650 times.
 22650 retif_((data.empty()) [[unlikely]], (T)0, (T)data[0]);
220 } else {
221 retif_((data.empty()) [[unlikely]], (T)0);
222 retif_((data.size() > 1), (T)data[1] << word_width | (T)data[0], (T)data[0]);
223 }
224 }
225 ND CEXP auto to_u32() CNE { return to_integer<u32>(); }
226 22650 ND CEXP auto to_u64() CNE { return to_integer<u64>(); }
227 ND CEXP auto to_ulong() CNE { return to_integer<unsigned long>(); }
228 ND CEXP auto to_ullong() CNE { return to_integer<unsigned long long>(); }
229
230 friend auto& operator>>(istream_c auto& is, dbitset& b) NE {
231 strn s;
232 (is >> s), b.set(s);
233 return is;
234 }
235 90 friend auto& operator<<(ostream_c auto& os, dbitset CR b) NE { return os << b.to_string(); }
236 };
237
238 } // namespace tifa_libs
239