Zig NEWS

Pyrolistical
Pyrolistical

Posted on • Updated on

New pure fns in StaticBitSet

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;
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Aside: I couldn't use the fn name union as that is a keyword. For consistency I decided to append With for 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);
Enter fullscreen mode Exit fullscreen mode

Oldest comments (2)

Collapse
 
bassfault profile image
bassfault

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.

Collapse
 
pyrolistical profile image
Pyrolistical

Good point. I blindly inlined the implementation of subsetOf, but you are right. I'll fix it.