While doing Advent of Code, when I tried to use StaticBitSet, I was surprised it was missing a function to determine if one StaticBitSet is the subset of another.
My solution required to check if a pair of sets were either a subset of one or the other. I.E. given sets a, b: a ⊂ b or b ⊂ a.
Using existing StaticBitSet functionality, I implemented this as:
const a: std.StaticBitSet...
const b: std.StaticBitSet...
var ab_intersection = a;
ab_intersection.setIntersection(b);
const either_subset_of = ab_intersection.mask == a.mask or
ab_intersection.mask == b.mask;
The next day I set out to see how difficult it would be to make a contribution to std.StaticBitSet to add subsetOf. It turns out the process is pretty simple and the actual experience was amazing.
The std is well organized and zig test lib/std/bit_set.zig just works.
I was able hammer out a complete pull request with full documentation and tests.
I decided to add a series of pure functions:
fn eql(self: Self, other: Self) bool
fn subsetOf(self: Self, other: Self) bool
fn supersetOf(self: Self, other: Self) bool
fn complement(self: Self) Self
fn unionWith(self: Self, other: Self) Self
fn intersectWith(self: Self, other: Self) Self
fn xorWith(self: Self, other: Self) Self
fn differenceWith(self: Self, other: Self) Self
Aside: I couldn't use the fn name
unionas that is a keyword. For consistency I decided to appendWithfor all the set operators.
Since std.StaticBitSet is comptime, there are far fewer edge cases to handle. In other languages to implement eql one would need to ensure the bit_length of the two sets are the same, but since bit_length is comptime if one tried to write std.StaticBitSet(1).initFull().eql(std.StaticBitSet(2).initFull()), one would get a compiler error instead of a run-time error!
With these new functions, my original subset problem is simplified down to:
const a: std.StaticBitSet...
const b: std.StaticBitSet...
const either_subset_of = a.subsetOf(b) or b.subsetOf(a);
Top comments (2)
Nice post, and glad to know that contributing to std is such a smooth experience.
Just a small nitpick: do you really need to compute the set intersection twice to perform the required test? It seems to me that computing it once and than comparing with both a and b could be enough.
Good point. I blindly inlined the implementation of
subsetOf, but you are right. I'll fix it.