tiny.simd.BitSet4096

1pub fn BitSet4096(comptime size: usize) type {2    requireCapacity(size);3    if (size > 4096) @compileError("BitSet4096 supports at most 4096 bits");4    const word_count = wordsFor(size);56    return struct {7        nonzero: BitSet64 = .{},8        words: [word_count]BitSet64 = @as([word_count]BitSet64, @splat(.{})),910        const Self = @This();11        pub const capacity: usize = size;12        pub const max_size: usize = capacity;1314        pub fn maxSize(_: *const Self) usize {15            return max_size;16        }1718        pub fn set(self: *Self, index: usize) void {19            std.debug.assert(index < max_size);20            const word_index = wordIndex(index);21            self.words[word_index].set(bitIndex(index));22            self.nonzero.set(word_index);23            std.debug.assert(self.get(index));24        }2526        pub fn setNonzeroBitsFrom64(self: *Self, bits: u64) void {27            const valid = bits & validBits(@min(max_size, 64));28            std.debug.assert(valid == bits);29            self.words[0].setNonzeroBitsFrom64(valid);30            if (valid != 0) self.nonzero.set(0);31        }3233        pub fn clear(self: *Self, index: usize) void {34            std.debug.assert(index < max_size);35            const word_index = wordIndex(index);36            self.words[word_index].clear(bitIndex(index));37            if (!self.words[word_index].any()) self.nonzero.clear(word_index);38            std.debug.assert(!self.get(index));39        }4041        pub fn get(self: *const Self, index: usize) bool {42            std.debug.assert(index < max_size);43            return self.words[wordIndex(index)].get(bitIndex(index));44        }4546        pub fn any(self: *const Self) bool {47            return self.nonzero.any();48        }4950        pub fn all(self: *const Self) bool {51            if (self.nonzero.count() != word_count) return false;52            return self.count() == max_size;53        }5455        pub fn first(self: *const Self) usize {56            std.debug.assert(self.any());57            const word_index = self.nonzero.first();58            return word_index * 64 + self.words[word_index].first();59        }6061        pub fn first0(self: *const Self) usize {62            std.debug.assert(!self.all());63            for (&self.words, 0..) |*word, word_index| {64                if (!word.all()) {65                    const index = word_index * 64 + word.first0();66                    std.debug.assert(index < max_size);67                    return index;68                }69            }70            unreachable;71        }7273        pub fn get64(self: *const Self) u64 {74            return self.words[0].get64();75        }7677        pub fn foreach(self: *const Self, function: anytype) void {78            var remaining_words = self.nonzero.get64();79            while (remaining_words != 0) {80                const word_index = firstBit(remaining_words);81                remaining_words &= remaining_words - 1;82                visitWord(self.words[word_index].get64(), word_index * 64, function);83            }84        }8586        pub fn count(self: *const Self) usize {87            var total: usize = 0;88            var remaining_words = self.nonzero.get64();89            while (remaining_words != 0) {90                const word_index = firstBit(remaining_words);91                remaining_words &= remaining_words - 1;92                total += self.words[word_index].count();93            }94            std.debug.assert(total <= max_size);95            return total;96        }97    };98}

1pub const BitSet4096 = bitset.BitSet4096;