1 // Copyright (c) The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #ifndef LIMENKA_UTIL_BITSET_H
6 #define LIMENKA_UTIL_BITSET_H
7 8 #include <util/check.h>
9 10 #include <array>
11 #include <bit>
12 #include <cstdint>
13 #include <limits>
14 #include <type_traits>
15 16 /* This file provides data types similar to std::bitset, but adds the following functionality:
17 *
18 * - Efficient iteration over all set bits (compatible with range-based for loops).
19 * - Efficient search for the first and last set bit (First() and Last()).
20 * - Efficient set subtraction: (a - b) implements "a and not b".
21 * - Efficient non-strict subset/superset testing: IsSubsetOf() and IsSupersetOf().
22 * - Efficient set overlap testing: a.Overlaps(b)
23 * - Efficient construction of set containing 0..N-1 (S::Fill).
24 * - Efficient construction of a single set (S::Singleton).
25 * - Construction from initializer lists.
26 *
27 * Other differences:
28 * - BitSet<N> is a bitset that supports at least N elements, but may support more (Size() reports
29 * the actual number). Because the actual number is unpredictable, there are no operations that
30 * affect all positions (like std::bitset's operator~, flip(), or all()).
31 * - Various other unimplemented features.
32 */
33 34 namespace bitset_detail {
35 36 /** Count the number of bits set in an unsigned integer type. */
37 template<typename I>
38 unsigned inline constexpr PopCount(I v)
39 {
40 static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
41 constexpr auto BITS = std::numeric_limits<I>::digits;
42 // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
43 // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
44 if constexpr (BITS <= 32) {
45 v -= (v >> 1) & 0x55555555;
46 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
47 v = (v + (v >> 4)) & 0x0f0f0f0f;
48 if constexpr (BITS > 8) v += v >> 8;
49 if constexpr (BITS > 16) v += v >> 16;
50 return v & 0x3f;
51 } else {
52 static_assert(BITS <= 64);
53 v -= (v >> 1) & 0x5555555555555555;
54 v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
55 v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
56 return (v * uint64_t{0x0101010101010101}) >> 56;
57 }
58 }
59 60 /** A bitset implementation backed by a single integer of type I. */
61 template<typename I>
62 class IntBitSet
63 {
64 // Only binary, unsigned, integer, types allowed.
65 static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
66 /** The maximum number of bits this bitset supports. */
67 static constexpr unsigned MAX_SIZE = std::numeric_limits<I>::digits;
68 /** Integer whose bits represent this bitset. */
69 I m_val;
70 /** Internal constructor with a given integer as contents. */
71 IntBitSet(I val) noexcept : m_val{val} {}
72 /** Dummy type to return using end(). Only used for comparing with Iterator. */
73 class IteratorEnd
74 {
75 friend class IntBitSet;
76 constexpr IteratorEnd() = default;
77 public:
78 constexpr IteratorEnd(const IteratorEnd&) = default;
79 };
80 /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
81 class Iterator
82 {
83 friend class IntBitSet;
84 I m_val; /**< The original integer's remaining bits. */
85 unsigned m_pos; /** Last reported 1 position (if m_pos != 0). */
86 constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
87 {
88 if (m_val != 0) m_pos = std::countr_zero(m_val);
89 }
90 public:
91 /** Do not allow external code to construct an Iterator. */
92 Iterator() = delete;
93 // Copying is allowed.
94 constexpr Iterator(const Iterator&) noexcept = default;
95 constexpr Iterator& operator=(const Iterator&) noexcept = default;
96 /** Test whether we are done (can only compare with IteratorEnd). */
97 constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
98 {
99 return a.m_val == 0;
100 }
101 /** Progress to the next 1 bit (only if != IteratorEnd). */
102 constexpr Iterator& operator++() noexcept
103 {
104 Assume(m_val != 0);
105 m_val &= m_val - I{1U};
106 if (m_val != 0) m_pos = std::countr_zero(m_val);
107 return *this;
108 }
109 /** Get the current bit position (only if != IteratorEnd). */
110 constexpr unsigned operator*() const noexcept
111 {
112 Assume(m_val != 0);
113 return m_pos;
114 }
115 };
116 117 public:
118 /** Construct an all-zero bitset. */
119 constexpr IntBitSet() noexcept : m_val{0} {}
120 /** Copy construct a bitset. */
121 constexpr IntBitSet(const IntBitSet&) noexcept = default;
122 /** Construct from a list of values. */
123 constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
124 {
125 for (auto pos : ilist) Set(pos);
126 }
127 /** Copy assign a bitset. */
128 constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
129 /** Assign from a list of positions (which will be made true, all others false). */
130 constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
131 {
132 m_val = 0;
133 for (auto pos : ilist) Set(pos);
134 return *this;
135 }
136 /** Construct a bitset with the singleton i. */
137 static constexpr IntBitSet Singleton(unsigned i) noexcept
138 {
139 Assume(i < MAX_SIZE);
140 return IntBitSet(I(1U) << i);
141 }
142 /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
143 static constexpr IntBitSet Fill(unsigned count) noexcept
144 {
145 IntBitSet ret;
146 Assume(count <= MAX_SIZE);
147 if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
148 return ret;
149 }
150 /** Set a bit to 1. */
151 constexpr void Set(unsigned pos) noexcept
152 {
153 Assume(pos < MAX_SIZE);
154 m_val |= I{1U} << pos;
155 }
156 /** Set a bit to the specified value. */
157 constexpr void Set(unsigned pos, bool val) noexcept
158 {
159 Assume(pos < MAX_SIZE);
160 m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
161 }
162 /** Set a bit to 0. */
163 constexpr void Reset(unsigned pos) noexcept
164 {
165 Assume(pos < MAX_SIZE);
166 m_val &= ~I(I{1U} << pos);
167 }
168 /** Retrieve a bit at the given position. */
169 constexpr bool operator[](unsigned pos) const noexcept
170 {
171 Assume(pos < MAX_SIZE);
172 return (m_val >> pos) & 1U;
173 }
174 /** Compute the number of 1 bits in the bitset. */
175 constexpr unsigned Count() const noexcept { return PopCount(m_val); }
176 /** Return the number of bits that this object holds. */
177 static constexpr unsigned Size() noexcept { return MAX_SIZE; }
178 /** Check if all bits are 0. */
179 constexpr bool None() const noexcept { return m_val == 0; }
180 /** Check if any bits are 1. */
181 constexpr bool Any() const noexcept { return !None(); }
182 /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
183 constexpr Iterator begin() const noexcept { return Iterator(m_val); }
184 /** Return a dummy object to compare Iterators with. */
185 constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
186 /** Find the first element (requires Any()). */
187 constexpr unsigned First() const noexcept
188 {
189 Assume(m_val != 0);
190 return std::countr_zero(m_val);
191 }
192 /** Find the last element (requires Any()). */
193 constexpr unsigned Last() const noexcept
194 {
195 Assume(m_val != 0);
196 return std::bit_width(m_val) - 1;
197 }
198 /** Set this object's bits to be the binary AND between respective bits from this and a. */
199 constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
200 /** Set this object's bits to be the binary OR between respective bits from this and a. */
201 constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
202 /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
203 constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
204 /** Set this object's bits to be the binary XOR between respective bits from this as a. */
205 constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
206 /** Check if the intersection between two sets is non-empty. */
207 constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }
208 /** Return an object with the binary AND between respective bits from a and b. */
209 friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
210 /** Return an object with the binary OR between respective bits from a and b. */
211 friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
212 /** Return an object with the binary AND NOT between respective bits from a and b. */
213 friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
214 /** Return an object with the binary XOR between respective bits from a and b. */
215 friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
216 /** Check if bitset a and bitset b are identical. */
217 friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
218 /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
219 constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
220 /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
221 constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
222 /** Swap two bitsets. */
223 friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
224 };
225 226 /** A bitset implementation backed by N integers of type I. */
227 template<typename I, unsigned N>
228 class MultiIntBitSet
229 {
230 // Only binary, unsigned, integer, types allowed.
231 static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
232 // Cannot be empty.
233 static_assert(N > 0);
234 /** The number of bits per integer. */
235 static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
236 /** Number of elements this set type supports. */
237 static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
238 // No overflow allowed here.
239 static_assert(MAX_SIZE / LIMB_BITS == N);
240 /** Array whose member integers store the bits of the set. */
241 std::array<I, N> m_val;
242 /** Dummy type to return using end(). Only used for comparing with Iterator. */
243 class IteratorEnd
244 {
245 friend class MultiIntBitSet;
246 constexpr IteratorEnd() = default;
247 public:
248 constexpr IteratorEnd(const IteratorEnd&) = default;
249 };
250 /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
251 class Iterator
252 {
253 friend class MultiIntBitSet;
254 const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */
255 I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */
256 unsigned m_pos; /**< The last reported position. */
257 unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */
258 constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
259 {
260 do {
261 m_val = (*m_ptr)[m_idx];
262 if (m_val) {
263 m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
264 break;
265 }
266 ++m_idx;
267 } while(m_idx < N);
268 }
269 270 public:
271 /** Do not allow external code to construct an Iterator. */
272 Iterator() = delete;
273 // Copying is allowed.
274 constexpr Iterator(const Iterator&) noexcept = default;
275 constexpr Iterator& operator=(const Iterator&) noexcept = default;
276 /** Test whether we are done (can only compare with IteratorEnd). */
277 friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
278 {
279 return a.m_idx == N;
280 }
281 /** Progress to the next 1 bit (only if != IteratorEnd). */
282 constexpr Iterator& operator++() noexcept
283 {
284 Assume(m_idx < N);
285 m_val &= m_val - I{1U};
286 if (m_val == 0) {
287 while (true) {
288 ++m_idx;
289 if (m_idx == N) break;
290 m_val = (*m_ptr)[m_idx];
291 if (m_val) {
292 m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
293 break;
294 }
295 }
296 } else {
297 m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
298 }
299 return *this;
300 }
301 /** Get the current bit position (only if != IteratorEnd). */
302 constexpr unsigned operator*() const noexcept
303 {
304 Assume(m_idx < N);
305 return m_pos;
306 }
307 };
308 309 public:
310 /** Construct an all-zero bitset. */
311 constexpr MultiIntBitSet() noexcept : m_val{} {}
312 /** Copy construct a bitset. */
313 constexpr MultiIntBitSet(const MultiIntBitSet&) noexcept = default;
314 /** Copy assign a bitset. */
315 constexpr MultiIntBitSet& operator=(const MultiIntBitSet&) noexcept = default;
316 /** Set a bit to 1. */
317 void constexpr Set(unsigned pos) noexcept
318 {
319 Assume(pos < MAX_SIZE);
320 m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
321 }
322 /** Set a bit to the specified value. */
323 void constexpr Set(unsigned pos, bool val) noexcept
324 {
325 Assume(pos < MAX_SIZE);
326 m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
327 (I{val} << (pos % LIMB_BITS));
328 }
329 /** Construct a bitset from a list of values. */
330 constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
331 {
332 for (auto pos : ilist) Set(pos);
333 }
334 /** Set a bitset to a list of values. */
335 constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
336 {
337 m_val.fill(0);
338 for (auto pos : ilist) Set(pos);
339 return *this;
340 }
341 /** Set a bit to 0. */
342 void constexpr Reset(unsigned pos) noexcept
343 {
344 Assume(pos < MAX_SIZE);
345 m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
346 }
347 /** Retrieve a bit at the given position. */
348 bool constexpr operator[](unsigned pos) const noexcept
349 {
350 Assume(pos < MAX_SIZE);
351 return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
352 }
353 /** Construct a bitset with the singleton pos. */
354 static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
355 {
356 Assume(pos < MAX_SIZE);
357 MultiIntBitSet ret;
358 ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
359 return ret;
360 }
361 /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
362 static constexpr MultiIntBitSet Fill(unsigned count) noexcept
363 {
364 Assume(count <= MAX_SIZE);
365 MultiIntBitSet ret;
366 if (count) {
367 unsigned i = 0;
368 while (count > LIMB_BITS) {
369 ret.m_val[i++] = I(~I{0});
370 count -= LIMB_BITS;
371 }
372 ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
373 }
374 return ret;
375 }
376 /** Return the number of bits that this object holds. */
377 static constexpr unsigned Size() noexcept { return MAX_SIZE; }
378 /** Compute the number of 1 bits in the bitset. */
379 unsigned constexpr Count() const noexcept
380 {
381 unsigned ret{0};
382 for (I v : m_val) ret += PopCount(v);
383 return ret;
384 }
385 /** Check if all bits are 0. */
386 bool constexpr None() const noexcept
387 {
388 for (auto v : m_val) {
389 if (v != 0) return false;
390 }
391 return true;
392 }
393 /** Check if any bits are 1. */
394 bool constexpr Any() const noexcept { return !None(); }
395 /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
396 Iterator constexpr begin() const noexcept { return Iterator(m_val); }
397 /** Return a dummy object to compare Iterators with. */
398 IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
399 /** Find the first element (requires Any()). */
400 unsigned constexpr First() const noexcept
401 {
402 unsigned p = 0;
403 while (m_val[p] == 0) {
404 ++p;
405 Assume(p < N);
406 }
407 return std::countr_zero(m_val[p]) + p * LIMB_BITS;
408 }
409 /** Find the last element (requires Any()). */
410 unsigned constexpr Last() const noexcept
411 {
412 unsigned p = N - 1;
413 while (m_val[p] == 0) {
414 Assume(p > 0);
415 --p;
416 }
417 return std::bit_width(m_val[p]) - 1 + p * LIMB_BITS;
418 }
419 /** Set this object's bits to be the binary OR between respective bits from this and a. */
420 constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
421 {
422 for (unsigned i = 0; i < N; ++i) {
423 m_val[i] |= a.m_val[i];
424 }
425 return *this;
426 }
427 /** Set this object's bits to be the binary AND between respective bits from this and a. */
428 constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
429 {
430 for (unsigned i = 0; i < N; ++i) {
431 m_val[i] &= a.m_val[i];
432 }
433 return *this;
434 }
435 /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
436 constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
437 {
438 for (unsigned i = 0; i < N; ++i) {
439 m_val[i] &= ~a.m_val[i];
440 }
441 return *this;
442 }
443 /** Set this object's bits to be the binary XOR between respective bits from this and a. */
444 constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
445 {
446 for (unsigned i = 0; i < N; ++i) {
447 m_val[i] ^= a.m_val[i];
448 }
449 return *this;
450 }
451 /** Check whether the intersection between two sets is non-empty. */
452 constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
453 {
454 for (unsigned i = 0; i < N; ++i) {
455 if (m_val[i] & a.m_val[i]) return true;
456 }
457 return false;
458 }
459 /** Return an object with the binary AND between respective bits from a and b. */
460 friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
461 {
462 MultiIntBitSet r;
463 for (unsigned i = 0; i < N; ++i) {
464 r.m_val[i] = a.m_val[i] & b.m_val[i];
465 }
466 return r;
467 }
468 /** Return an object with the binary OR between respective bits from a and b. */
469 friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
470 {
471 MultiIntBitSet r;
472 for (unsigned i = 0; i < N; ++i) {
473 r.m_val[i] = a.m_val[i] | b.m_val[i];
474 }
475 return r;
476 }
477 /** Return an object with the binary AND NOT between respective bits from a and b. */
478 friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
479 {
480 MultiIntBitSet r;
481 for (unsigned i = 0; i < N; ++i) {
482 r.m_val[i] = a.m_val[i] & ~b.m_val[i];
483 }
484 return r;
485 }
486 /** Return an object with the binary XOR between respective bits from a and b. */
487 friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
488 {
489 MultiIntBitSet r;
490 for (unsigned i = 0; i < N; ++i) {
491 r.m_val[i] = a.m_val[i] ^ b.m_val[i];
492 }
493 return r;
494 }
495 /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
496 constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
497 {
498 for (unsigned i = 0; i < N; ++i) {
499 if (a.m_val[i] & ~m_val[i]) return false;
500 }
501 return true;
502 }
503 /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
504 constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
505 {
506 for (unsigned i = 0; i < N; ++i) {
507 if (m_val[i] & ~a.m_val[i]) return false;
508 }
509 return true;
510 }
511 /** Check if bitset a and bitset b are identical. */
512 friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
513 /** Swap two bitsets. */
514 friend constexpr void swap(MultiIntBitSet& a, MultiIntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
515 };
516 517 } // namespace bitset_detail
518 519 // BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
520 // of bits. Use IntBitSet up to 32-bit, or up to 64-bit on 64-bit platforms; above that, use a
521 // MultiIntBitSet of size_t.
522 template<unsigned BITS>
523 using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
524 std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
525 bitset_detail::MultiIntBitSet<size_t, (BITS + std::numeric_limits<size_t>::digits - 1) / std::numeric_limits<size_t>::digits>>>;
526 527 #endif // LIMENKA_UTIL_BITSET_H
528