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