master
1//! This file defines several variants of bit sets. A bit set
2//! is a densely stored set of integers with a known maximum,
3//! in which each integer gets a single bit. Bit sets have very
4//! fast presence checks, update operations, and union and intersection
5//! operations. However, if the number of possible items is very
6//! large and the number of actual items in a given set is usually
7//! small, they may be less memory efficient than an array set.
8//!
9//! There are five variants defined here:
10//!
11//! IntegerBitSet:
12//! A bit set with static size, which is backed by a single integer.
13//! This set is good for sets with a small size, but may generate
14//! inefficient code for larger sets, especially in debug mode.
15//!
16//! ArrayBitSet:
17//! A bit set with static size, which is backed by an array of usize.
18//! This set is good for sets with a larger size, but may use
19//! more bytes than necessary if your set is small.
20//!
21//! StaticBitSet:
22//! Picks either IntegerBitSet or ArrayBitSet depending on the requested
23//! size. The interfaces of these two types match exactly, except for fields.
24//!
25//! DynamicBitSet:
26//! A bit set with runtime-known size, backed by an allocated slice
27//! of usize.
28//!
29//! DynamicBitSetUnmanaged:
30//! A variant of DynamicBitSet which does not store a pointer to its
31//! allocator, in order to save space.
32
33const std = @import("std.zig");
34const assert = std.debug.assert;
35const Allocator = std.mem.Allocator;
36const builtin = @import("builtin");
37
38/// Returns the optimal static bit set type for the specified number
39/// of elements: either `IntegerBitSet` or `ArrayBitSet`,
40/// both of which fulfill the same interface.
41/// The returned type will perform no allocations,
42/// can be copied by value, and does not require deinitialization.
43pub fn StaticBitSet(comptime size: usize) type {
44 if (size <= @bitSizeOf(usize)) {
45 return IntegerBitSet(size);
46 } else {
47 return ArrayBitSet(usize, size);
48 }
49}
50
51/// A bit set with static size, which is backed by a single integer.
52/// This set is good for sets with a small size, but may generate
53/// inefficient code for larger sets, especially in debug mode.
54pub fn IntegerBitSet(comptime size: u16) type {
55 return packed struct {
56 const Self = @This();
57
58 // TODO: Make this a comptime field once those are fixed
59 /// The number of items in this bit set
60 pub const bit_length: usize = size;
61
62 /// The integer type used to represent a mask in this bit set
63 pub const MaskInt = std.meta.Int(.unsigned, size);
64
65 /// The integer type used to shift a mask in this bit set
66 pub const ShiftInt = std.math.Log2Int(MaskInt);
67
68 /// The bit mask, as a single integer
69 mask: MaskInt,
70
71 /// Creates a bit set with no elements present.
72 pub fn initEmpty() Self {
73 return .{ .mask = 0 };
74 }
75
76 /// Creates a bit set with all elements present.
77 pub fn initFull() Self {
78 return .{ .mask = ~@as(MaskInt, 0) };
79 }
80
81 /// Returns the number of bits in this bit set
82 pub inline fn capacity(self: Self) usize {
83 _ = self;
84 return bit_length;
85 }
86
87 /// Returns true if the bit at the specified index
88 /// is present in the set, false otherwise.
89 pub fn isSet(self: Self, index: usize) bool {
90 assert(index < bit_length);
91 return (self.mask & maskBit(index)) != 0;
92 }
93
94 /// Returns the total number of set bits in this bit set.
95 pub fn count(self: Self) usize {
96 return @popCount(self.mask);
97 }
98
99 /// Changes the value of the specified bit of the bit
100 /// set to match the passed boolean.
101 pub fn setValue(self: *Self, index: usize, value: bool) void {
102 assert(index < bit_length);
103 if (MaskInt == u0) return;
104 const bit = maskBit(index);
105 const new_bit = bit & std.math.boolMask(MaskInt, value);
106 self.mask = (self.mask & ~bit) | new_bit;
107 }
108
109 /// Adds a specific bit to the bit set
110 pub fn set(self: *Self, index: usize) void {
111 assert(index < bit_length);
112 self.mask |= maskBit(index);
113 }
114
115 /// Changes the value of all bits in the specified range to
116 /// match the passed boolean.
117 pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
118 assert(range.end <= bit_length);
119 assert(range.start <= range.end);
120 if (range.start == range.end) return;
121 if (MaskInt == u0) return;
122
123 const start_bit = @as(ShiftInt, @intCast(range.start));
124
125 var mask = std.math.boolMask(MaskInt, true) << start_bit;
126 if (range.end != bit_length) {
127 const end_bit = @as(ShiftInt, @intCast(range.end));
128 mask &= std.math.boolMask(MaskInt, true) >> @as(ShiftInt, @truncate(@as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit)));
129 }
130 self.mask &= ~mask;
131
132 mask = std.math.boolMask(MaskInt, value) << start_bit;
133 if (range.end != bit_length) {
134 const end_bit = @as(ShiftInt, @intCast(range.end));
135 mask &= std.math.boolMask(MaskInt, value) >> @as(ShiftInt, @truncate(@as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit)));
136 }
137 self.mask |= mask;
138 }
139
140 /// Removes a specific bit from the bit set
141 pub fn unset(self: *Self, index: usize) void {
142 assert(index < bit_length);
143 // Workaround for #7953
144 if (MaskInt == u0) return;
145 self.mask &= ~maskBit(index);
146 }
147
148 /// Flips a specific bit in the bit set
149 pub fn toggle(self: *Self, index: usize) void {
150 assert(index < bit_length);
151 self.mask ^= maskBit(index);
152 }
153
154 /// Flips all bits in this bit set which are present
155 /// in the toggles bit set.
156 pub fn toggleSet(self: *Self, toggles: Self) void {
157 self.mask ^= toggles.mask;
158 }
159
160 /// Flips every bit in the bit set.
161 pub fn toggleAll(self: *Self) void {
162 self.mask = ~self.mask;
163 }
164
165 /// Performs a union of two bit sets, and stores the
166 /// result in the first one. Bits in the result are
167 /// set if the corresponding bits were set in either input.
168 pub fn setUnion(self: *Self, other: Self) void {
169 self.mask |= other.mask;
170 }
171
172 /// Performs an intersection of two bit sets, and stores
173 /// the result in the first one. Bits in the result are
174 /// set if the corresponding bits were set in both inputs.
175 pub fn setIntersection(self: *Self, other: Self) void {
176 self.mask &= other.mask;
177 }
178
179 /// Finds the index of the first set bit.
180 /// If no bits are set, returns null.
181 pub fn findFirstSet(self: Self) ?usize {
182 const mask = self.mask;
183 if (mask == 0) return null;
184 return @ctz(mask);
185 }
186
187 /// Finds the index of the last set bit.
188 /// If no bits are set, returns null.
189 pub fn findLastSet(self: Self) ?usize {
190 const mask = self.mask;
191 if (mask == 0) return null;
192 return bit_length - @clz(mask) - 1;
193 }
194
195 /// Finds the index of the first set bit, and unsets it.
196 /// If no bits are set, returns null.
197 pub fn toggleFirstSet(self: *Self) ?usize {
198 const mask = self.mask;
199 if (mask == 0) return null;
200 const index = @ctz(mask);
201 self.mask = mask & (mask - 1);
202 return index;
203 }
204
205 /// Returns true iff every corresponding bit in both
206 /// bit sets are the same.
207 pub fn eql(self: Self, other: Self) bool {
208 return bit_length == 0 or self.mask == other.mask;
209 }
210
211 /// Returns true iff the first bit set is the subset
212 /// of the second one.
213 pub fn subsetOf(self: Self, other: Self) bool {
214 return self.intersectWith(other).eql(self);
215 }
216
217 /// Returns true iff the first bit set is the superset
218 /// of the second one.
219 pub fn supersetOf(self: Self, other: Self) bool {
220 return other.subsetOf(self);
221 }
222
223 /// Returns the complement bit sets. Bits in the result
224 /// are set if the corresponding bits were not set.
225 pub fn complement(self: Self) Self {
226 var result = self;
227 result.toggleAll();
228 return result;
229 }
230
231 /// Returns the union of two bit sets. Bits in the
232 /// result are set if the corresponding bits were set
233 /// in either input.
234 pub fn unionWith(self: Self, other: Self) Self {
235 var result = self;
236 result.setUnion(other);
237 return result;
238 }
239
240 /// Returns the intersection of two bit sets. Bits in
241 /// the result are set if the corresponding bits were
242 /// set in both inputs.
243 pub fn intersectWith(self: Self, other: Self) Self {
244 var result = self;
245 result.setIntersection(other);
246 return result;
247 }
248
249 /// Returns the xor of two bit sets. Bits in the
250 /// result are set if the corresponding bits were
251 /// not the same in both inputs.
252 pub fn xorWith(self: Self, other: Self) Self {
253 var result = self;
254 result.toggleSet(other);
255 return result;
256 }
257
258 /// Returns the difference of two bit sets. Bits in
259 /// the result are set if set in the first but not
260 /// set in the second set.
261 pub fn differenceWith(self: Self, other: Self) Self {
262 var result = self;
263 result.setIntersection(other.complement());
264 return result;
265 }
266
267 /// Iterates through the items in the set, according to the options.
268 /// The default options (.{}) will iterate indices of set bits in
269 /// ascending order. Modifications to the underlying bit set may
270 /// or may not be observed by the iterator.
271 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
272 return .{
273 .bits_remain = switch (options.kind) {
274 .set => self.mask,
275 .unset => ~self.mask,
276 },
277 };
278 }
279
280 pub fn Iterator(comptime options: IteratorOptions) type {
281 return SingleWordIterator(options.direction);
282 }
283
284 fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type {
285 return struct {
286 const IterSelf = @This();
287 // all bits which have not yet been iterated over
288 bits_remain: MaskInt,
289
290 /// Returns the index of the next unvisited set bit
291 /// in the bit set, in ascending order.
292 pub fn next(self: *IterSelf) ?usize {
293 if (self.bits_remain == 0) return null;
294
295 switch (direction) {
296 .forward => {
297 const next_index = @ctz(self.bits_remain);
298 self.bits_remain &= self.bits_remain - 1;
299 return next_index;
300 },
301 .reverse => {
302 const leading_zeroes = @clz(self.bits_remain);
303 const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes;
304 self.bits_remain &= (@as(MaskInt, 1) << @as(ShiftInt, @intCast(top_bit))) - 1;
305 return top_bit;
306 },
307 }
308 }
309 };
310 }
311
312 fn maskBit(index: usize) MaskInt {
313 if (MaskInt == u0) return 0;
314 return @as(MaskInt, 1) << @as(ShiftInt, @intCast(index));
315 }
316 fn boolMaskBit(index: usize, value: bool) MaskInt {
317 if (MaskInt == u0) return 0;
318 return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
319 }
320 };
321}
322
323/// A bit set with static size, which is backed by an array of usize.
324/// This set is good for sets with a larger size, but may use
325/// more bytes than necessary if your set is small.
326pub fn ArrayBitSet(comptime MaskIntType: type, comptime size: usize) type {
327 const mask_info: std.builtin.Type = @typeInfo(MaskIntType);
328
329 // Make sure the mask int is indeed an int
330 if (mask_info != .int) @compileError("ArrayBitSet can only operate on integer masks, but was passed " ++ @typeName(MaskIntType));
331
332 // It must also be unsigned.
333 if (mask_info.int.signedness != .unsigned) @compileError("ArrayBitSet requires an unsigned integer mask type, but was passed " ++ @typeName(MaskIntType));
334
335 // And it must not be empty.
336 if (MaskIntType == u0)
337 @compileError("ArrayBitSet requires a sized integer for its mask int. u0 does not work.");
338
339 const byte_size = std.mem.byte_size_in_bits;
340
341 // We use shift and truncate to decompose indices into mask indices and bit indices.
342 // This operation requires that the mask has an exact power of two number of bits.
343 if (!std.math.isPowerOfTwo(@bitSizeOf(MaskIntType))) {
344 var desired_bits = std.math.ceilPowerOfTwoAssert(usize, @bitSizeOf(MaskIntType));
345 if (desired_bits < byte_size) desired_bits = byte_size;
346 const FixedMaskType = std.meta.Int(.unsigned, desired_bits);
347 @compileError("ArrayBitSet was passed integer type " ++ @typeName(MaskIntType) ++
348 ", which is not a power of two. Please round this up to a power of two integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
349 }
350
351 // Make sure the integer has no padding bits.
352 // Those would be wasteful here and are probably a mistake by the user.
353 // This case may be hit with small powers of two, like u4.
354 if (@bitSizeOf(MaskIntType) != @sizeOf(MaskIntType) * byte_size) {
355 var desired_bits = @sizeOf(MaskIntType) * byte_size;
356 desired_bits = std.math.ceilPowerOfTwoAssert(usize, desired_bits);
357 const FixedMaskType = std.meta.Int(.unsigned, desired_bits);
358 @compileError("ArrayBitSet was passed integer type " ++ @typeName(MaskIntType) ++
359 ", which contains padding bits. Please round this up to an unpadded integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
360 }
361
362 return extern struct {
363 const Self = @This();
364
365 // TODO: Make this a comptime field once those are fixed
366 /// The number of items in this bit set
367 pub const bit_length: usize = size;
368
369 /// The integer type used to represent a mask in this bit set
370 pub const MaskInt = MaskIntType;
371
372 /// The integer type used to shift a mask in this bit set
373 pub const ShiftInt = std.math.Log2Int(MaskInt);
374
375 // bits in one mask
376 const mask_len = @bitSizeOf(MaskInt);
377 // total number of masks
378 const num_masks = (size + mask_len - 1) / mask_len;
379 // padding bits in the last mask (may be 0)
380 const last_pad_bits = mask_len * num_masks - size;
381 // Mask of valid bits in the last mask.
382 // All functions will ensure that the invalid
383 // bits in the last mask are zero.
384 pub const last_item_mask = ~@as(MaskInt, 0) >> last_pad_bits;
385
386 /// The bit masks, ordered with lower indices first.
387 /// Padding bits at the end are undefined.
388 masks: [num_masks]MaskInt,
389
390 /// Creates a bit set with no elements present.
391 pub fn initEmpty() Self {
392 return .{ .masks = [_]MaskInt{0} ** num_masks };
393 }
394
395 /// Creates a bit set with all elements present.
396 pub fn initFull() Self {
397 if (num_masks == 0) {
398 return .{ .masks = .{} };
399 } else {
400 return .{ .masks = [_]MaskInt{~@as(MaskInt, 0)} ** (num_masks - 1) ++ [_]MaskInt{last_item_mask} };
401 }
402 }
403
404 /// Returns the number of bits in this bit set
405 pub inline fn capacity(self: Self) usize {
406 _ = self;
407 return bit_length;
408 }
409
410 /// Returns true if the bit at the specified index
411 /// is present in the set, false otherwise.
412 pub fn isSet(self: Self, index: usize) bool {
413 assert(index < bit_length);
414 if (num_masks == 0) return false; // doesn't compile in this case
415 return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
416 }
417
418 /// Returns the total number of set bits in this bit set.
419 pub fn count(self: Self) usize {
420 var total: usize = 0;
421 for (self.masks) |mask| {
422 total += @popCount(mask);
423 }
424 return total;
425 }
426
427 /// Changes the value of the specified bit of the bit
428 /// set to match the passed boolean.
429 pub fn setValue(self: *Self, index: usize, value: bool) void {
430 assert(index < bit_length);
431 if (num_masks == 0) return; // doesn't compile in this case
432 const bit = maskBit(index);
433 const mask_index = maskIndex(index);
434 const new_bit = bit & std.math.boolMask(MaskInt, value);
435 self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
436 }
437
438 /// Adds a specific bit to the bit set
439 pub fn set(self: *Self, index: usize) void {
440 assert(index < bit_length);
441 if (num_masks == 0) return; // doesn't compile in this case
442 self.masks[maskIndex(index)] |= maskBit(index);
443 }
444
445 /// Changes the value of all bits in the specified range to
446 /// match the passed boolean.
447 pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
448 assert(range.end <= bit_length);
449 assert(range.start <= range.end);
450 if (range.start == range.end) return;
451 if (num_masks == 0) return;
452
453 const start_mask_index = maskIndex(range.start);
454 const start_bit = @as(ShiftInt, @truncate(range.start));
455
456 const end_mask_index = maskIndex(range.end);
457 const end_bit = @as(ShiftInt, @truncate(range.end));
458
459 if (start_mask_index == end_mask_index) {
460 var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
461 var mask2 = std.math.boolMask(MaskInt, true) >> (mask_len - 1) - (end_bit - 1);
462 self.masks[start_mask_index] &= ~(mask1 & mask2);
463
464 mask1 = std.math.boolMask(MaskInt, value) << start_bit;
465 mask2 = std.math.boolMask(MaskInt, value) >> (mask_len - 1) - (end_bit - 1);
466 self.masks[start_mask_index] |= mask1 & mask2;
467 } else {
468 var bulk_mask_index: usize = undefined;
469 if (start_bit > 0) {
470 self.masks[start_mask_index] =
471 (self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
472 (std.math.boolMask(MaskInt, value) << start_bit);
473 bulk_mask_index = start_mask_index + 1;
474 } else {
475 bulk_mask_index = start_mask_index;
476 }
477
478 while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
479 self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
480 }
481
482 if (end_bit > 0) {
483 self.masks[end_mask_index] =
484 (self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
485 (std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
486 }
487 }
488 }
489
490 /// Removes a specific bit from the bit set
491 pub fn unset(self: *Self, index: usize) void {
492 assert(index < bit_length);
493 if (num_masks == 0) return; // doesn't compile in this case
494 self.masks[maskIndex(index)] &= ~maskBit(index);
495 }
496
497 /// Flips a specific bit in the bit set
498 pub fn toggle(self: *Self, index: usize) void {
499 assert(index < bit_length);
500 if (num_masks == 0) return; // doesn't compile in this case
501 self.masks[maskIndex(index)] ^= maskBit(index);
502 }
503
504 /// Flips all bits in this bit set which are present
505 /// in the toggles bit set.
506 pub fn toggleSet(self: *Self, toggles: Self) void {
507 for (&self.masks, 0..) |*mask, i| {
508 mask.* ^= toggles.masks[i];
509 }
510 }
511
512 /// Flips every bit in the bit set.
513 pub fn toggleAll(self: *Self) void {
514 for (&self.masks) |*mask| {
515 mask.* = ~mask.*;
516 }
517
518 // Zero the padding bits
519 if (num_masks > 0) {
520 self.masks[num_masks - 1] &= last_item_mask;
521 }
522 }
523
524 /// Performs a union of two bit sets, and stores the
525 /// result in the first one. Bits in the result are
526 /// set if the corresponding bits were set in either input.
527 pub fn setUnion(self: *Self, other: Self) void {
528 for (&self.masks, 0..) |*mask, i| {
529 mask.* |= other.masks[i];
530 }
531 }
532
533 /// Performs an intersection of two bit sets, and stores
534 /// the result in the first one. Bits in the result are
535 /// set if the corresponding bits were set in both inputs.
536 pub fn setIntersection(self: *Self, other: Self) void {
537 for (&self.masks, 0..) |*mask, i| {
538 mask.* &= other.masks[i];
539 }
540 }
541
542 /// Finds the index of the first set bit.
543 /// If no bits are set, returns null.
544 pub fn findFirstSet(self: Self) ?usize {
545 var offset: usize = 0;
546 const mask = for (self.masks) |mask| {
547 if (mask != 0) break mask;
548 offset += @bitSizeOf(MaskInt);
549 } else return null;
550 return offset + @ctz(mask);
551 }
552
553 /// Finds the index of the last set bit.
554 /// If no bits are set, returns null.
555 pub fn findLastSet(self: Self) ?usize {
556 if (bit_length == 0) return null;
557 const bs = @bitSizeOf(MaskInt);
558 var len = bit_length / bs;
559 if (bit_length % bs != 0) len += 1;
560 var offset: usize = len * bs;
561 var idx: usize = len - 1;
562 while (self.masks[idx] == 0) : (idx -= 1) {
563 offset -= bs;
564 if (idx == 0) return null;
565 }
566 offset -= @clz(self.masks[idx]);
567 offset -= 1;
568 return offset;
569 }
570
571 /// Finds the index of the first set bit, and unsets it.
572 /// If no bits are set, returns null.
573 pub fn toggleFirstSet(self: *Self) ?usize {
574 var offset: usize = 0;
575 const mask = for (&self.masks) |*mask| {
576 if (mask.* != 0) break mask;
577 offset += @bitSizeOf(MaskInt);
578 } else return null;
579 const index = @ctz(mask.*);
580 mask.* &= (mask.* - 1);
581 return offset + index;
582 }
583
584 /// Returns true iff every corresponding bit in both
585 /// bit sets are the same.
586 pub fn eql(self: Self, other: Self) bool {
587 var i: usize = 0;
588 return while (i < num_masks) : (i += 1) {
589 if (self.masks[i] != other.masks[i]) {
590 break false;
591 }
592 } else true;
593 }
594
595 /// Returns true iff the first bit set is the subset
596 /// of the second one.
597 pub fn subsetOf(self: Self, other: Self) bool {
598 return self.intersectWith(other).eql(self);
599 }
600
601 /// Returns true iff the first bit set is the superset
602 /// of the second one.
603 pub fn supersetOf(self: Self, other: Self) bool {
604 return other.subsetOf(self);
605 }
606
607 /// Returns the complement bit sets. Bits in the result
608 /// are set if the corresponding bits were not set.
609 pub fn complement(self: Self) Self {
610 var result = self;
611 result.toggleAll();
612 return result;
613 }
614
615 /// Returns the union of two bit sets. Bits in the
616 /// result are set if the corresponding bits were set
617 /// in either input.
618 pub fn unionWith(self: Self, other: Self) Self {
619 var result = self;
620 result.setUnion(other);
621 return result;
622 }
623
624 /// Returns the intersection of two bit sets. Bits in
625 /// the result are set if the corresponding bits were
626 /// set in both inputs.
627 pub fn intersectWith(self: Self, other: Self) Self {
628 var result = self;
629 result.setIntersection(other);
630 return result;
631 }
632
633 /// Returns the xor of two bit sets. Bits in the
634 /// result are set if the corresponding bits were
635 /// not the same in both inputs.
636 pub fn xorWith(self: Self, other: Self) Self {
637 var result = self;
638 result.toggleSet(other);
639 return result;
640 }
641
642 /// Returns the difference of two bit sets. Bits in
643 /// the result are set if set in the first but not
644 /// set in the second set.
645 pub fn differenceWith(self: Self, other: Self) Self {
646 var result = self;
647 result.setIntersection(other.complement());
648 return result;
649 }
650
651 /// Iterates through the items in the set, according to the options.
652 /// The default options (.{}) will iterate indices of set bits in
653 /// ascending order. Modifications to the underlying bit set may
654 /// or may not be observed by the iterator.
655 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
656 return Iterator(options).init(&self.masks, last_item_mask);
657 }
658
659 pub fn Iterator(comptime options: IteratorOptions) type {
660 return BitSetIterator(MaskInt, options);
661 }
662
663 fn maskBit(index: usize) MaskInt {
664 return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index));
665 }
666 fn maskIndex(index: usize) usize {
667 return index >> @bitSizeOf(ShiftInt);
668 }
669 fn boolMaskBit(index: usize, value: bool) MaskInt {
670 return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
671 }
672 };
673}
674
675/// A bit set with runtime-known size, backed by an allocated slice
676/// of usize. The allocator must be tracked externally by the user.
677pub const DynamicBitSetUnmanaged = struct {
678 const Self = @This();
679
680 /// The integer type used to represent a mask in this bit set
681 pub const MaskInt = usize;
682
683 /// The integer type used to shift a mask in this bit set
684 pub const ShiftInt = std.math.Log2Int(MaskInt);
685
686 /// The number of valid items in this bit set
687 bit_length: usize = 0,
688
689 /// The bit masks, ordered with lower indices first.
690 /// Padding bits at the end must be zeroed.
691 masks: [*]MaskInt = empty_masks_ptr,
692 // This pointer is one usize after the actual allocation.
693 // That slot holds the size of the true allocation, which
694 // is needed by Zig's allocator interface in case a shrink
695 // fails.
696
697 // Don't modify this value. Ideally it would go in const data so
698 // modifications would cause a bus error, but the only way
699 // to discard a const qualifier is through intFromPtr, which
700 // cannot currently round trip at comptime.
701 var empty_masks_data = [_]MaskInt{ 0, undefined };
702 const empty_masks_ptr = empty_masks_data[1..2];
703
704 /// Creates a bit set with no elements present.
705 /// If bit_length is not zero, deinit must eventually be called.
706 pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
707 var self = Self{};
708 try self.resize(allocator, bit_length, false);
709 return self;
710 }
711
712 /// Creates a bit set with all elements present.
713 /// If bit_length is not zero, deinit must eventually be called.
714 pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
715 var self = Self{};
716 try self.resize(allocator, bit_length, true);
717 return self;
718 }
719
720 /// Resizes to a new bit_length. If the new length is larger
721 /// than the old length, fills any added bits with `fill`.
722 /// If new_len is not zero, deinit must eventually be called.
723 pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void {
724 const old_len = self.bit_length;
725
726 const old_masks = numMasks(old_len);
727 const new_masks = numMasks(new_len);
728
729 const old_allocation = (self.masks - 1)[0..(self.masks - 1)[0]];
730
731 if (new_masks == 0) {
732 assert(new_len == 0);
733 allocator.free(old_allocation);
734 self.masks = empty_masks_ptr;
735 self.bit_length = 0;
736 return;
737 }
738
739 if (old_allocation.len != new_masks + 1) realloc: {
740 // If realloc fails, it may mean one of two things.
741 // If we are growing, it means we are out of memory.
742 // If we are shrinking, it means the allocator doesn't
743 // want to move the allocation. This means we need to
744 // hold on to the extra 8 bytes required to be able to free
745 // this allocation properly.
746 const new_allocation = allocator.realloc(old_allocation, new_masks + 1) catch |err| {
747 if (new_masks + 1 > old_allocation.len) return err;
748 break :realloc;
749 };
750
751 new_allocation[0] = new_allocation.len;
752 self.masks = new_allocation.ptr + 1;
753 }
754
755 // If we increased in size, we need to set any new bits
756 // to the fill value.
757 if (new_len > old_len) {
758 // set the padding bits in the old last item to 1
759 if (fill and old_masks > 0) {
760 const old_padding_bits = old_masks * @bitSizeOf(MaskInt) - old_len;
761 const old_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(old_padding_bits));
762 self.masks[old_masks - 1] |= ~old_mask;
763 }
764
765 // fill in any new masks
766 if (new_masks > old_masks) {
767 const fill_value = std.math.boolMask(MaskInt, fill);
768 @memset(self.masks[old_masks..new_masks], fill_value);
769 }
770 }
771
772 // Zero out the padding bits
773 if (new_len > 0) {
774 const padding_bits = new_masks * @bitSizeOf(MaskInt) - new_len;
775 const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
776 self.masks[new_masks - 1] &= last_item_mask;
777 }
778
779 // And finally, save the new length.
780 self.bit_length = new_len;
781 }
782
783 /// Deinitializes the array and releases its memory.
784 /// The passed allocator must be the same one used for
785 /// init* or resize in the past.
786 pub fn deinit(self: *Self, allocator: Allocator) void {
787 self.resize(allocator, 0, false) catch unreachable;
788 }
789
790 /// Creates a duplicate of this bit set, using the new allocator.
791 pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
792 const num_masks = numMasks(self.bit_length);
793 var copy = Self{};
794 try copy.resize(new_allocator, self.bit_length, false);
795 @memcpy(copy.masks[0..num_masks], self.masks[0..num_masks]);
796 return copy;
797 }
798
799 /// Returns the number of bits in this bit set
800 pub inline fn capacity(self: Self) usize {
801 return self.bit_length;
802 }
803
804 /// Returns true if the bit at the specified index
805 /// is present in the set, false otherwise.
806 pub fn isSet(self: Self, index: usize) bool {
807 assert(index < self.bit_length);
808 return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
809 }
810
811 /// Returns the total number of set bits in this bit set.
812 pub fn count(self: Self) usize {
813 const num_masks = (self.bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
814 var total: usize = 0;
815 for (self.masks[0..num_masks]) |mask| {
816 // Note: This is where we depend on padding bits being zero
817 total += @popCount(mask);
818 }
819 return total;
820 }
821
822 /// Changes the value of the specified bit of the bit
823 /// set to match the passed boolean.
824 pub fn setValue(self: *Self, index: usize, value: bool) void {
825 assert(index < self.bit_length);
826 const bit = maskBit(index);
827 const mask_index = maskIndex(index);
828 const new_bit = bit & std.math.boolMask(MaskInt, value);
829 self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
830 }
831
832 /// Adds a specific bit to the bit set
833 pub fn set(self: *Self, index: usize) void {
834 assert(index < self.bit_length);
835 self.masks[maskIndex(index)] |= maskBit(index);
836 }
837
838 /// Changes the value of all bits in the specified range to
839 /// match the passed boolean.
840 pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
841 assert(range.end <= self.bit_length);
842 assert(range.start <= range.end);
843 if (range.start == range.end) return;
844
845 const start_mask_index = maskIndex(range.start);
846 const start_bit = @as(ShiftInt, @truncate(range.start));
847
848 const end_mask_index = maskIndex(range.end);
849 const end_bit = @as(ShiftInt, @truncate(range.end));
850
851 if (start_mask_index == end_mask_index) {
852 var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
853 var mask2 = std.math.boolMask(MaskInt, true) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1);
854 self.masks[start_mask_index] &= ~(mask1 & mask2);
855
856 mask1 = std.math.boolMask(MaskInt, value) << start_bit;
857 mask2 = std.math.boolMask(MaskInt, value) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1);
858 self.masks[start_mask_index] |= mask1 & mask2;
859 } else {
860 var bulk_mask_index: usize = undefined;
861 if (start_bit > 0) {
862 self.masks[start_mask_index] =
863 (self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
864 (std.math.boolMask(MaskInt, value) << start_bit);
865 bulk_mask_index = start_mask_index + 1;
866 } else {
867 bulk_mask_index = start_mask_index;
868 }
869
870 while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
871 self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
872 }
873
874 if (end_bit > 0) {
875 self.masks[end_mask_index] =
876 (self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
877 (std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
878 }
879 }
880 }
881
882 /// Removes a specific bit from the bit set
883 pub fn unset(self: *Self, index: usize) void {
884 assert(index < self.bit_length);
885 self.masks[maskIndex(index)] &= ~maskBit(index);
886 }
887
888 /// Set all bits to 0.
889 pub fn unsetAll(self: *Self) void {
890 const masks_len = numMasks(self.bit_length);
891 @memset(self.masks[0..masks_len], 0);
892 }
893
894 /// Set all bits to 1.
895 pub fn setAll(self: *Self) void {
896 const masks_len = numMasks(self.bit_length);
897 @memset(self.masks[0..masks_len], std.math.maxInt(MaskInt));
898 }
899
900 /// Flips a specific bit in the bit set
901 pub fn toggle(self: *Self, index: usize) void {
902 assert(index < self.bit_length);
903 self.masks[maskIndex(index)] ^= maskBit(index);
904 }
905
906 /// Flips all bits in this bit set which are present
907 /// in the toggles bit set. Both sets must have the
908 /// same bit_length.
909 pub fn toggleSet(self: *Self, toggles: Self) void {
910 assert(toggles.bit_length == self.bit_length);
911 const num_masks = numMasks(self.bit_length);
912 for (self.masks[0..num_masks], 0..) |*mask, i| {
913 mask.* ^= toggles.masks[i];
914 }
915 }
916
917 /// Flips every bit in the bit set.
918 pub fn toggleAll(self: *Self) void {
919 const bit_length = self.bit_length;
920 // avoid underflow if bit_length is zero
921 if (bit_length == 0) return;
922
923 const num_masks = numMasks(self.bit_length);
924 for (self.masks[0..num_masks]) |*mask| {
925 mask.* = ~mask.*;
926 }
927
928 const padding_bits = num_masks * @bitSizeOf(MaskInt) - bit_length;
929 const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
930 self.masks[num_masks - 1] &= last_item_mask;
931 }
932
933 /// Performs a union of two bit sets, and stores the
934 /// result in the first one. Bits in the result are
935 /// set if the corresponding bits were set in either input.
936 /// The two sets must both be the same bit_length.
937 pub fn setUnion(self: *Self, other: Self) void {
938 assert(other.bit_length == self.bit_length);
939 const num_masks = numMasks(self.bit_length);
940 for (self.masks[0..num_masks], 0..) |*mask, i| {
941 mask.* |= other.masks[i];
942 }
943 }
944
945 /// Performs an intersection of two bit sets, and stores
946 /// the result in the first one. Bits in the result are
947 /// set if the corresponding bits were set in both inputs.
948 /// The two sets must both be the same bit_length.
949 pub fn setIntersection(self: *Self, other: Self) void {
950 assert(other.bit_length == self.bit_length);
951 const num_masks = numMasks(self.bit_length);
952 for (self.masks[0..num_masks], 0..) |*mask, i| {
953 mask.* &= other.masks[i];
954 }
955 }
956
957 /// Finds the index of the first set bit.
958 /// If no bits are set, returns null.
959 pub fn findFirstSet(self: Self) ?usize {
960 var offset: usize = 0;
961 var mask = self.masks;
962 while (offset < self.bit_length) {
963 if (mask[0] != 0) break;
964 mask += 1;
965 offset += @bitSizeOf(MaskInt);
966 } else return null;
967 return offset + @ctz(mask[0]);
968 }
969
970 /// Finds the index of the last set bit.
971 /// If no bits are set, returns null.
972 pub fn findLastSet(self: Self) ?usize {
973 if (self.bit_length == 0) return null;
974 const bs = @bitSizeOf(MaskInt);
975 var len = self.bit_length / bs;
976 if (self.bit_length % bs != 0) len += 1;
977 var offset: usize = len * bs;
978 var idx: usize = len - 1;
979 while (self.masks[idx] == 0) : (idx -= 1) {
980 offset -= bs;
981 if (idx == 0) return null;
982 }
983 offset -= @clz(self.masks[idx]);
984 offset -= 1;
985 return offset;
986 }
987
988 /// Finds the index of the first set bit, and unsets it.
989 /// If no bits are set, returns null.
990 pub fn toggleFirstSet(self: *Self) ?usize {
991 var offset: usize = 0;
992 var mask = self.masks;
993 while (offset < self.bit_length) {
994 if (mask[0] != 0) break;
995 mask += 1;
996 offset += @bitSizeOf(MaskInt);
997 } else return null;
998 const index = @ctz(mask[0]);
999 mask[0] &= (mask[0] - 1);
1000 return offset + index;
1001 }
1002
1003 /// Returns true iff every corresponding bit in both
1004 /// bit sets are the same.
1005 pub fn eql(self: Self, other: Self) bool {
1006 if (self.bit_length != other.bit_length) {
1007 return false;
1008 }
1009 const num_masks = numMasks(self.bit_length);
1010 var i: usize = 0;
1011 return while (i < num_masks) : (i += 1) {
1012 if (self.masks[i] != other.masks[i]) {
1013 break false;
1014 }
1015 } else true;
1016 }
1017
1018 /// Returns true iff the first bit set is the subset
1019 /// of the second one.
1020 pub fn subsetOf(self: Self, other: Self) bool {
1021 if (self.bit_length != other.bit_length) {
1022 return false;
1023 }
1024 const num_masks = numMasks(self.bit_length);
1025 var i: usize = 0;
1026 return while (i < num_masks) : (i += 1) {
1027 if (self.masks[i] & other.masks[i] != self.masks[i]) {
1028 break false;
1029 }
1030 } else true;
1031 }
1032
1033 /// Returns true iff the first bit set is the superset
1034 /// of the second one.
1035 pub fn supersetOf(self: Self, other: Self) bool {
1036 if (self.bit_length != other.bit_length) {
1037 return false;
1038 }
1039 const num_masks = numMasks(self.bit_length);
1040 var i: usize = 0;
1041 return while (i < num_masks) : (i += 1) {
1042 if (self.masks[i] & other.masks[i] != other.masks[i]) {
1043 break false;
1044 }
1045 } else true;
1046 }
1047
1048 /// Iterates through the items in the set, according to the options.
1049 /// The default options (.{}) will iterate indices of set bits in
1050 /// ascending order. Modifications to the underlying bit set may
1051 /// or may not be observed by the iterator. Resizing the underlying
1052 /// bit set invalidates the iterator.
1053 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
1054 const num_masks = numMasks(self.bit_length);
1055 const padding_bits = num_masks * @bitSizeOf(MaskInt) - self.bit_length;
1056 const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
1057 return Iterator(options).init(self.masks[0..num_masks], last_item_mask);
1058 }
1059
1060 pub fn Iterator(comptime options: IteratorOptions) type {
1061 return BitSetIterator(MaskInt, options);
1062 }
1063
1064 fn maskBit(index: usize) MaskInt {
1065 return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index));
1066 }
1067 fn maskIndex(index: usize) usize {
1068 return index >> @bitSizeOf(ShiftInt);
1069 }
1070 fn boolMaskBit(index: usize, value: bool) MaskInt {
1071 return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
1072 }
1073 fn numMasks(bit_length: usize) usize {
1074 return (bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
1075 }
1076};
1077
1078/// A bit set with runtime-known size, backed by an allocated slice
1079/// of usize. Thin wrapper around DynamicBitSetUnmanaged which keeps
1080/// track of the allocator instance.
1081pub const DynamicBitSet = struct {
1082 const Self = @This();
1083
1084 /// The integer type used to represent a mask in this bit set
1085 pub const MaskInt = usize;
1086
1087 /// The integer type used to shift a mask in this bit set
1088 pub const ShiftInt = std.math.Log2Int(MaskInt);
1089
1090 allocator: Allocator,
1091 unmanaged: DynamicBitSetUnmanaged = .{},
1092
1093 /// Creates a bit set with no elements present.
1094 pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
1095 return Self{
1096 .unmanaged = try DynamicBitSetUnmanaged.initEmpty(allocator, bit_length),
1097 .allocator = allocator,
1098 };
1099 }
1100
1101 /// Creates a bit set with all elements present.
1102 pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
1103 return Self{
1104 .unmanaged = try DynamicBitSetUnmanaged.initFull(allocator, bit_length),
1105 .allocator = allocator,
1106 };
1107 }
1108
1109 /// Resizes to a new length. If the new length is larger
1110 /// than the old length, fills any added bits with `fill`.
1111 pub fn resize(self: *@This(), new_len: usize, fill: bool) !void {
1112 try self.unmanaged.resize(self.allocator, new_len, fill);
1113 }
1114
1115 /// Deinitializes the array and releases its memory.
1116 /// The passed allocator must be the same one used for
1117 /// init* or resize in the past.
1118 pub fn deinit(self: *Self) void {
1119 self.unmanaged.deinit(self.allocator);
1120 }
1121
1122 /// Creates a duplicate of this bit set, using the new allocator.
1123 pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
1124 return Self{
1125 .unmanaged = try self.unmanaged.clone(new_allocator),
1126 .allocator = new_allocator,
1127 };
1128 }
1129
1130 /// Returns the number of bits in this bit set
1131 pub inline fn capacity(self: Self) usize {
1132 return self.unmanaged.capacity();
1133 }
1134
1135 /// Returns true if the bit at the specified index
1136 /// is present in the set, false otherwise.
1137 pub fn isSet(self: Self, index: usize) bool {
1138 return self.unmanaged.isSet(index);
1139 }
1140
1141 /// Returns the total number of set bits in this bit set.
1142 pub fn count(self: Self) usize {
1143 return self.unmanaged.count();
1144 }
1145
1146 /// Changes the value of the specified bit of the bit
1147 /// set to match the passed boolean.
1148 pub fn setValue(self: *Self, index: usize, value: bool) void {
1149 self.unmanaged.setValue(index, value);
1150 }
1151
1152 /// Adds a specific bit to the bit set
1153 pub fn set(self: *Self, index: usize) void {
1154 self.unmanaged.set(index);
1155 }
1156
1157 /// Changes the value of all bits in the specified range to
1158 /// match the passed boolean.
1159 pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
1160 self.unmanaged.setRangeValue(range, value);
1161 }
1162
1163 /// Removes a specific bit from the bit set
1164 pub fn unset(self: *Self, index: usize) void {
1165 self.unmanaged.unset(index);
1166 }
1167
1168 /// Flips a specific bit in the bit set
1169 pub fn toggle(self: *Self, index: usize) void {
1170 self.unmanaged.toggle(index);
1171 }
1172
1173 /// Flips all bits in this bit set which are present
1174 /// in the toggles bit set. Both sets must have the
1175 /// same bit_length.
1176 pub fn toggleSet(self: *Self, toggles: Self) void {
1177 self.unmanaged.toggleSet(toggles.unmanaged);
1178 }
1179
1180 /// Flips every bit in the bit set.
1181 pub fn toggleAll(self: *Self) void {
1182 self.unmanaged.toggleAll();
1183 }
1184
1185 /// Performs a union of two bit sets, and stores the
1186 /// result in the first one. Bits in the result are
1187 /// set if the corresponding bits were set in either input.
1188 /// The two sets must both be the same bit_length.
1189 pub fn setUnion(self: *Self, other: Self) void {
1190 self.unmanaged.setUnion(other.unmanaged);
1191 }
1192
1193 /// Performs an intersection of two bit sets, and stores
1194 /// the result in the first one. Bits in the result are
1195 /// set if the corresponding bits were set in both inputs.
1196 /// The two sets must both be the same bit_length.
1197 pub fn setIntersection(self: *Self, other: Self) void {
1198 self.unmanaged.setIntersection(other.unmanaged);
1199 }
1200
1201 /// Finds the index of the first set bit.
1202 /// If no bits are set, returns null.
1203 pub fn findFirstSet(self: Self) ?usize {
1204 return self.unmanaged.findFirstSet();
1205 }
1206
1207 /// Finds the index of the last set bit.
1208 /// If no bits are set, returns null.
1209 pub fn findLastSet(self: Self) ?usize {
1210 return self.unmanaged.findLastSet();
1211 }
1212
1213 /// Finds the index of the first set bit, and unsets it.
1214 /// If no bits are set, returns null.
1215 pub fn toggleFirstSet(self: *Self) ?usize {
1216 return self.unmanaged.toggleFirstSet();
1217 }
1218
1219 /// Returns true iff every corresponding bit in both
1220 /// bit sets are the same.
1221 pub fn eql(self: Self, other: Self) bool {
1222 return self.unmanaged.eql(other.unmanaged);
1223 }
1224
1225 /// Iterates through the items in the set, according to the options.
1226 /// The default options (.{}) will iterate indices of set bits in
1227 /// ascending order. Modifications to the underlying bit set may
1228 /// or may not be observed by the iterator. Resizing the underlying
1229 /// bit set invalidates the iterator.
1230 pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
1231 return self.unmanaged.iterator(options);
1232 }
1233
1234 pub const Iterator = DynamicBitSetUnmanaged.Iterator;
1235};
1236
1237/// Options for configuring an iterator over a bit set
1238pub const IteratorOptions = struct {
1239 /// determines which bits should be visited
1240 kind: Type = .set,
1241 /// determines the order in which bit indices should be visited
1242 direction: Direction = .forward,
1243
1244 pub const Type = enum {
1245 /// visit indexes of set bits
1246 set,
1247 /// visit indexes of unset bits
1248 unset,
1249 };
1250
1251 pub const Direction = enum {
1252 /// visit indices in ascending order
1253 forward,
1254 /// visit indices in descending order.
1255 /// Note that this may be slightly more expensive than forward iteration.
1256 reverse,
1257 };
1258};
1259
1260// The iterator is reusable between several bit set types
1261fn BitSetIterator(comptime MaskInt: type, comptime options: IteratorOptions) type {
1262 const ShiftInt = std.math.Log2Int(MaskInt);
1263 const kind = options.kind;
1264 const direction = options.direction;
1265 return struct {
1266 const Self = @This();
1267
1268 // all bits which have not yet been iterated over
1269 bits_remain: MaskInt,
1270 // all words which have not yet been iterated over
1271 words_remain: []const MaskInt,
1272 // the offset of the current word
1273 bit_offset: usize,
1274 // the mask of the last word
1275 last_word_mask: MaskInt,
1276
1277 fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self {
1278 if (masks.len == 0) {
1279 return Self{
1280 .bits_remain = 0,
1281 .words_remain = &[_]MaskInt{},
1282 .last_word_mask = last_word_mask,
1283 .bit_offset = 0,
1284 };
1285 } else {
1286 var result = Self{
1287 .bits_remain = 0,
1288 .words_remain = masks,
1289 .last_word_mask = last_word_mask,
1290 .bit_offset = if (direction == .forward) 0 else (masks.len - 1) * @bitSizeOf(MaskInt),
1291 };
1292 result.nextWord(true);
1293 return result;
1294 }
1295 }
1296
1297 /// Returns the index of the next unvisited set bit
1298 /// in the bit set, in ascending order.
1299 pub fn next(self: *Self) ?usize {
1300 while (self.bits_remain == 0) {
1301 if (self.words_remain.len == 0) return null;
1302 self.nextWord(false);
1303 switch (direction) {
1304 .forward => self.bit_offset += @bitSizeOf(MaskInt),
1305 .reverse => self.bit_offset -= @bitSizeOf(MaskInt),
1306 }
1307 }
1308
1309 switch (direction) {
1310 .forward => {
1311 const next_index = @ctz(self.bits_remain) + self.bit_offset;
1312 self.bits_remain &= self.bits_remain - 1;
1313 return next_index;
1314 },
1315 .reverse => {
1316 const leading_zeroes = @clz(self.bits_remain);
1317 const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes;
1318 const no_top_bit_mask = (@as(MaskInt, 1) << @as(ShiftInt, @intCast(top_bit))) - 1;
1319 self.bits_remain &= no_top_bit_mask;
1320 return top_bit + self.bit_offset;
1321 },
1322 }
1323 }
1324
1325 // Load the next word. Don't call this if there
1326 // isn't a next word. If the next word is the
1327 // last word, mask off the padding bits so we
1328 // don't visit them.
1329 inline fn nextWord(self: *Self, comptime is_first_word: bool) void {
1330 var word = switch (direction) {
1331 .forward => self.words_remain[0],
1332 .reverse => self.words_remain[self.words_remain.len - 1],
1333 };
1334 switch (kind) {
1335 .set => {},
1336 .unset => {
1337 word = ~word;
1338 if ((direction == .reverse and is_first_word) or
1339 (direction == .forward and self.words_remain.len == 1))
1340 {
1341 word &= self.last_word_mask;
1342 }
1343 },
1344 }
1345 switch (direction) {
1346 .forward => self.words_remain = self.words_remain[1..],
1347 .reverse => self.words_remain.len -= 1,
1348 }
1349 self.bits_remain = word;
1350 }
1351 };
1352}
1353
1354/// A range of indices within a bitset.
1355pub const Range = struct {
1356 /// The index of the first bit of interest.
1357 start: usize,
1358 /// The index immediately after the last bit of interest.
1359 end: usize,
1360};
1361
1362// ---------------- Tests -----------------
1363
1364const testing = std.testing;
1365
1366fn testEql(empty: anytype, full: anytype, len: usize) !void {
1367 try testing.expect(empty.eql(empty));
1368 try testing.expect(full.eql(full));
1369 switch (len) {
1370 0 => {
1371 try testing.expect(empty.eql(full));
1372 try testing.expect(full.eql(empty));
1373 },
1374 else => {
1375 try testing.expect(!empty.eql(full));
1376 try testing.expect(!full.eql(empty));
1377 },
1378 }
1379}
1380
1381fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void {
1382 try testing.expect(empty.subsetOf(empty));
1383 try testing.expect(empty.subsetOf(full));
1384 try testing.expect(full.subsetOf(full));
1385 switch (len) {
1386 0 => {
1387 try testing.expect(even.subsetOf(odd));
1388 try testing.expect(odd.subsetOf(even));
1389 },
1390 1 => {
1391 try testing.expect(!even.subsetOf(odd));
1392 try testing.expect(odd.subsetOf(even));
1393 },
1394 else => {
1395 try testing.expect(!even.subsetOf(odd));
1396 try testing.expect(!odd.subsetOf(even));
1397 },
1398 }
1399}
1400
1401fn testSupersetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void {
1402 try testing.expect(full.supersetOf(full));
1403 try testing.expect(full.supersetOf(empty));
1404 try testing.expect(empty.supersetOf(empty));
1405 switch (len) {
1406 0 => {
1407 try testing.expect(even.supersetOf(odd));
1408 try testing.expect(odd.supersetOf(even));
1409 },
1410 1 => {
1411 try testing.expect(even.supersetOf(odd));
1412 try testing.expect(!odd.supersetOf(even));
1413 },
1414 else => {
1415 try testing.expect(!even.supersetOf(odd));
1416 try testing.expect(!odd.supersetOf(even));
1417 },
1418 }
1419}
1420
1421fn testBitSet(a: anytype, b: anytype, len: usize) !void {
1422 try testing.expectEqual(len, a.capacity());
1423 try testing.expectEqual(len, b.capacity());
1424
1425 {
1426 var i: usize = 0;
1427 while (i < len) : (i += 1) {
1428 a.setValue(i, i & 1 == 0);
1429 b.setValue(i, i & 2 == 0);
1430 }
1431 }
1432
1433 try testing.expectEqual((len + 1) / 2, a.count());
1434 try testing.expectEqual((len + 3) / 4 + (len + 2) / 4, b.count());
1435
1436 {
1437 var iter = a.iterator(.{});
1438 var i: usize = 0;
1439 while (i < len) : (i += 2) {
1440 try testing.expectEqual(@as(?usize, i), iter.next());
1441 }
1442 try testing.expectEqual(@as(?usize, null), iter.next());
1443 try testing.expectEqual(@as(?usize, null), iter.next());
1444 try testing.expectEqual(@as(?usize, null), iter.next());
1445 }
1446 a.toggleAll();
1447 {
1448 var iter = a.iterator(.{});
1449 var i: usize = 1;
1450 while (i < len) : (i += 2) {
1451 try testing.expectEqual(@as(?usize, i), iter.next());
1452 }
1453 try testing.expectEqual(@as(?usize, null), iter.next());
1454 try testing.expectEqual(@as(?usize, null), iter.next());
1455 try testing.expectEqual(@as(?usize, null), iter.next());
1456 }
1457
1458 {
1459 var iter = b.iterator(.{ .kind = .unset });
1460 var i: usize = 2;
1461 while (i < len) : (i += 4) {
1462 try testing.expectEqual(@as(?usize, i), iter.next());
1463 if (i + 1 < len) {
1464 try testing.expectEqual(@as(?usize, i + 1), iter.next());
1465 }
1466 }
1467 try testing.expectEqual(@as(?usize, null), iter.next());
1468 try testing.expectEqual(@as(?usize, null), iter.next());
1469 try testing.expectEqual(@as(?usize, null), iter.next());
1470 }
1471
1472 {
1473 var i: usize = 0;
1474 while (i < len) : (i += 1) {
1475 try testing.expectEqual(i & 1 != 0, a.isSet(i));
1476 try testing.expectEqual(i & 2 == 0, b.isSet(i));
1477 }
1478 }
1479
1480 a.setUnion(b.*);
1481 {
1482 var i: usize = 0;
1483 while (i < len) : (i += 1) {
1484 try testing.expectEqual(i & 1 != 0 or i & 2 == 0, a.isSet(i));
1485 try testing.expectEqual(i & 2 == 0, b.isSet(i));
1486 }
1487
1488 i = len;
1489 var set = a.iterator(.{ .direction = .reverse });
1490 var unset = a.iterator(.{ .kind = .unset, .direction = .reverse });
1491 while (i > 0) {
1492 i -= 1;
1493 if (i & 1 != 0 or i & 2 == 0) {
1494 try testing.expectEqual(@as(?usize, i), set.next());
1495 } else {
1496 try testing.expectEqual(@as(?usize, i), unset.next());
1497 }
1498 }
1499 try testing.expectEqual(@as(?usize, null), set.next());
1500 try testing.expectEqual(@as(?usize, null), set.next());
1501 try testing.expectEqual(@as(?usize, null), set.next());
1502 try testing.expectEqual(@as(?usize, null), unset.next());
1503 try testing.expectEqual(@as(?usize, null), unset.next());
1504 try testing.expectEqual(@as(?usize, null), unset.next());
1505 }
1506
1507 a.toggleSet(b.*);
1508 {
1509 try testing.expectEqual(len / 4, a.count());
1510
1511 var i: usize = 0;
1512 while (i < len) : (i += 1) {
1513 try testing.expectEqual(i & 1 != 0 and i & 2 != 0, a.isSet(i));
1514 try testing.expectEqual(i & 2 == 0, b.isSet(i));
1515 if (i & 1 == 0) {
1516 a.set(i);
1517 } else {
1518 a.unset(i);
1519 }
1520 }
1521 }
1522
1523 a.setIntersection(b.*);
1524 {
1525 try testing.expectEqual((len + 3) / 4, a.count());
1526
1527 var i: usize = 0;
1528 while (i < len) : (i += 1) {
1529 try testing.expectEqual(i & 1 == 0 and i & 2 == 0, a.isSet(i));
1530 try testing.expectEqual(i & 2 == 0, b.isSet(i));
1531 }
1532 }
1533
1534 a.toggleSet(a.*);
1535 {
1536 var iter = a.iterator(.{});
1537 try testing.expectEqual(@as(?usize, null), iter.next());
1538 try testing.expectEqual(@as(?usize, null), iter.next());
1539 try testing.expectEqual(@as(?usize, null), iter.next());
1540 try testing.expectEqual(@as(usize, 0), a.count());
1541 }
1542 {
1543 var iter = a.iterator(.{ .direction = .reverse });
1544 try testing.expectEqual(@as(?usize, null), iter.next());
1545 try testing.expectEqual(@as(?usize, null), iter.next());
1546 try testing.expectEqual(@as(?usize, null), iter.next());
1547 try testing.expectEqual(@as(usize, 0), a.count());
1548 }
1549
1550 const test_bits = [_]usize{
1551 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 22, 31, 32, 63, 64,
1552 66, 95, 127, 160, 192, 1000,
1553 };
1554 for (test_bits) |i| {
1555 if (i < a.capacity()) {
1556 a.set(i);
1557 }
1558 }
1559
1560 for (test_bits) |i| {
1561 if (i < a.capacity()) {
1562 try testing.expectEqual(@as(?usize, i), a.findFirstSet());
1563 try testing.expectEqual(@as(?usize, i), a.toggleFirstSet());
1564 }
1565 }
1566 try testing.expectEqual(@as(?usize, null), a.findFirstSet());
1567 try testing.expectEqual(@as(?usize, null), a.findLastSet());
1568 try testing.expectEqual(@as(?usize, null), a.toggleFirstSet());
1569 try testing.expectEqual(@as(?usize, null), a.findFirstSet());
1570 try testing.expectEqual(@as(?usize, null), a.findLastSet());
1571 try testing.expectEqual(@as(?usize, null), a.toggleFirstSet());
1572 try testing.expectEqual(@as(usize, 0), a.count());
1573
1574 a.setRangeValue(.{ .start = 0, .end = len }, false);
1575 try testing.expectEqual(@as(usize, 0), a.count());
1576
1577 a.setRangeValue(.{ .start = 0, .end = len }, true);
1578 try testing.expectEqual(len, a.count());
1579
1580 a.setRangeValue(.{ .start = 0, .end = len }, false);
1581 a.setRangeValue(.{ .start = 0, .end = 0 }, true);
1582 try testing.expectEqual(@as(usize, 0), a.count());
1583
1584 a.setRangeValue(.{ .start = len, .end = len }, true);
1585 try testing.expectEqual(@as(usize, 0), a.count());
1586
1587 if (len >= 1) {
1588 a.setRangeValue(.{ .start = 0, .end = len }, false);
1589 a.setRangeValue(.{ .start = 0, .end = 1 }, true);
1590 try testing.expectEqual(@as(usize, 1), a.count());
1591 try testing.expect(a.isSet(0));
1592
1593 a.setRangeValue(.{ .start = 0, .end = len }, false);
1594 a.setRangeValue(.{ .start = 0, .end = len - 1 }, true);
1595 try testing.expectEqual(len - 1, a.count());
1596 try testing.expect(!a.isSet(len - 1));
1597
1598 a.setRangeValue(.{ .start = 0, .end = len }, false);
1599 a.setRangeValue(.{ .start = 1, .end = len }, true);
1600 try testing.expectEqual(@as(usize, len - 1), a.count());
1601 try testing.expect(!a.isSet(0));
1602
1603 a.setRangeValue(.{ .start = 0, .end = len }, false);
1604 a.setRangeValue(.{ .start = len - 1, .end = len }, true);
1605 try testing.expectEqual(@as(usize, 1), a.count());
1606 try testing.expect(a.isSet(len - 1));
1607
1608 if (len >= 4) {
1609 a.setRangeValue(.{ .start = 0, .end = len }, false);
1610 a.setRangeValue(.{ .start = 1, .end = len - 2 }, true);
1611 try testing.expectEqual(@as(usize, len - 3), a.count());
1612 try testing.expect(!a.isSet(0));
1613 try testing.expect(a.isSet(1));
1614 try testing.expect(a.isSet(len - 3));
1615 try testing.expect(!a.isSet(len - 2));
1616 try testing.expect(!a.isSet(len - 1));
1617 }
1618 }
1619}
1620
1621fn fillEven(set: anytype, len: usize) void {
1622 var i: usize = 0;
1623 while (i < len) : (i += 1) {
1624 set.setValue(i, i & 1 == 0);
1625 }
1626}
1627
1628fn fillOdd(set: anytype, len: usize) void {
1629 var i: usize = 0;
1630 while (i < len) : (i += 1) {
1631 set.setValue(i, i & 1 == 1);
1632 }
1633}
1634
1635fn testPureBitSet(comptime Set: type) !void {
1636 const empty = Set.initEmpty();
1637 const full = Set.initFull();
1638
1639 const even = even: {
1640 var bit_set = Set.initEmpty();
1641 fillEven(&bit_set, Set.bit_length);
1642 break :even bit_set;
1643 };
1644
1645 const odd = odd: {
1646 var bit_set = Set.initEmpty();
1647 fillOdd(&bit_set, Set.bit_length);
1648 break :odd bit_set;
1649 };
1650
1651 try testSubsetOf(empty, full, even, odd, Set.bit_length);
1652 try testSupersetOf(empty, full, even, odd, Set.bit_length);
1653
1654 try testing.expect(empty.complement().eql(full));
1655 try testing.expect(full.complement().eql(empty));
1656 try testing.expect(even.complement().eql(odd));
1657 try testing.expect(odd.complement().eql(even));
1658
1659 try testing.expect(empty.unionWith(empty).eql(empty));
1660 try testing.expect(empty.unionWith(full).eql(full));
1661 try testing.expect(full.unionWith(full).eql(full));
1662 try testing.expect(full.unionWith(empty).eql(full));
1663 try testing.expect(even.unionWith(odd).eql(full));
1664 try testing.expect(odd.unionWith(even).eql(full));
1665
1666 try testing.expect(empty.intersectWith(empty).eql(empty));
1667 try testing.expect(empty.intersectWith(full).eql(empty));
1668 try testing.expect(full.intersectWith(full).eql(full));
1669 try testing.expect(full.intersectWith(empty).eql(empty));
1670 try testing.expect(even.intersectWith(odd).eql(empty));
1671 try testing.expect(odd.intersectWith(even).eql(empty));
1672
1673 try testing.expect(empty.xorWith(empty).eql(empty));
1674 try testing.expect(empty.xorWith(full).eql(full));
1675 try testing.expect(full.xorWith(full).eql(empty));
1676 try testing.expect(full.xorWith(empty).eql(full));
1677 try testing.expect(even.xorWith(odd).eql(full));
1678 try testing.expect(odd.xorWith(even).eql(full));
1679
1680 try testing.expect(empty.differenceWith(empty).eql(empty));
1681 try testing.expect(empty.differenceWith(full).eql(empty));
1682 try testing.expect(full.differenceWith(full).eql(empty));
1683 try testing.expect(full.differenceWith(empty).eql(full));
1684 try testing.expect(full.differenceWith(odd).eql(even));
1685 try testing.expect(full.differenceWith(even).eql(odd));
1686}
1687
1688fn testStaticBitSet(comptime Set: type) !void {
1689 var a = Set.initEmpty();
1690 var b = Set.initFull();
1691 try testing.expectEqual(@as(usize, 0), a.count());
1692 try testing.expectEqual(@as(usize, Set.bit_length), b.count());
1693
1694 try testEql(a, b, Set.bit_length);
1695 try testBitSet(&a, &b, Set.bit_length);
1696
1697 try testPureBitSet(Set);
1698}
1699
1700test IntegerBitSet {
1701 if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;
1702 if (comptime builtin.cpu.has(.riscv, .v) and builtin.zig_backend == .stage2_llvm) return error.SkipZigTest; // https://github.com/ziglang/zig/issues/24300
1703
1704 try testStaticBitSet(IntegerBitSet(0));
1705 try testStaticBitSet(IntegerBitSet(1));
1706 try testStaticBitSet(IntegerBitSet(2));
1707 try testStaticBitSet(IntegerBitSet(5));
1708 try testStaticBitSet(IntegerBitSet(8));
1709 try testStaticBitSet(IntegerBitSet(32));
1710 try testStaticBitSet(IntegerBitSet(64));
1711 try testStaticBitSet(IntegerBitSet(127));
1712}
1713
1714test ArrayBitSet {
1715 inline for (.{ 0, 1, 2, 31, 32, 33, 63, 64, 65, 254, 500, 3000 }) |size| {
1716 try testStaticBitSet(ArrayBitSet(u8, size));
1717 try testStaticBitSet(ArrayBitSet(u16, size));
1718 try testStaticBitSet(ArrayBitSet(u32, size));
1719 try testStaticBitSet(ArrayBitSet(u64, size));
1720 try testStaticBitSet(ArrayBitSet(u128, size));
1721 }
1722}
1723
1724test DynamicBitSetUnmanaged {
1725 const allocator = std.testing.allocator;
1726 var a = try DynamicBitSetUnmanaged.initEmpty(allocator, 300);
1727 try testing.expectEqual(@as(usize, 0), a.count());
1728 a.deinit(allocator);
1729
1730 a = try DynamicBitSetUnmanaged.initEmpty(allocator, 0);
1731 defer a.deinit(allocator);
1732 for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| {
1733 const old_len = a.capacity();
1734
1735 var empty = try a.clone(allocator);
1736 defer empty.deinit(allocator);
1737 try testing.expectEqual(old_len, empty.capacity());
1738 var i: usize = 0;
1739 while (i < old_len) : (i += 1) {
1740 try testing.expectEqual(a.isSet(i), empty.isSet(i));
1741 }
1742
1743 a.toggleSet(a); // zero a
1744 empty.toggleSet(empty);
1745
1746 try a.resize(allocator, size, true);
1747 try empty.resize(allocator, size, false);
1748
1749 if (size > old_len) {
1750 try testing.expectEqual(size - old_len, a.count());
1751 } else {
1752 try testing.expectEqual(@as(usize, 0), a.count());
1753 }
1754 try testing.expectEqual(@as(usize, 0), empty.count());
1755
1756 var full = try DynamicBitSetUnmanaged.initFull(allocator, size);
1757 defer full.deinit(allocator);
1758 try testing.expectEqual(@as(usize, size), full.count());
1759
1760 try testEql(empty, full, size);
1761 {
1762 var even = try DynamicBitSetUnmanaged.initEmpty(allocator, size);
1763 defer even.deinit(allocator);
1764 fillEven(&even, size);
1765
1766 var odd = try DynamicBitSetUnmanaged.initEmpty(allocator, size);
1767 defer odd.deinit(allocator);
1768 fillOdd(&odd, size);
1769
1770 try testSubsetOf(empty, full, even, odd, size);
1771 try testSupersetOf(empty, full, even, odd, size);
1772 }
1773 try testBitSet(&a, &full, size);
1774 }
1775}
1776
1777test DynamicBitSet {
1778 const allocator = std.testing.allocator;
1779 var a = try DynamicBitSet.initEmpty(allocator, 300);
1780 try testing.expectEqual(@as(usize, 0), a.count());
1781 a.deinit();
1782
1783 a = try DynamicBitSet.initEmpty(allocator, 0);
1784 defer a.deinit();
1785 for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| {
1786 const old_len = a.capacity();
1787
1788 var tmp = try a.clone(allocator);
1789 defer tmp.deinit();
1790 try testing.expectEqual(old_len, tmp.capacity());
1791 var i: usize = 0;
1792 while (i < old_len) : (i += 1) {
1793 try testing.expectEqual(a.isSet(i), tmp.isSet(i));
1794 }
1795
1796 a.toggleSet(a); // zero a
1797 tmp.toggleSet(tmp); // zero tmp
1798
1799 try a.resize(size, true);
1800 try tmp.resize(size, false);
1801
1802 if (size > old_len) {
1803 try testing.expectEqual(size - old_len, a.count());
1804 } else {
1805 try testing.expectEqual(@as(usize, 0), a.count());
1806 }
1807 try testing.expectEqual(@as(usize, 0), tmp.count());
1808
1809 var b = try DynamicBitSet.initFull(allocator, size);
1810 defer b.deinit();
1811 try testing.expectEqual(@as(usize, size), b.count());
1812
1813 try testEql(tmp, b, size);
1814 try testBitSet(&a, &b, size);
1815 }
1816}
1817
1818test StaticBitSet {
1819 try testing.expectEqual(IntegerBitSet(0), StaticBitSet(0));
1820 try testing.expectEqual(IntegerBitSet(5), StaticBitSet(5));
1821 try testing.expectEqual(IntegerBitSet(@bitSizeOf(usize)), StaticBitSet(@bitSizeOf(usize)));
1822 try testing.expectEqual(ArrayBitSet(usize, @bitSizeOf(usize) + 1), StaticBitSet(@bitSizeOf(usize) + 1));
1823 try testing.expectEqual(ArrayBitSet(usize, 500), StaticBitSet(500));
1824}