PartialEq implementation depends on capacity

[sitegui]

Hello,

Thanks a lot for the awesome lib :+1:

I've observed that PartialEq is derived automatically. But that means that sets with different capacities are always considered different, even when having the same "elements" (in the sense of the values obtained with ones()).

let a = FixedBitSet::with_capacity(0);
let b = FixedBitSet::with_capacity(1);

assert_ne!(a, b); // both are "empty", but considered different

Wouldn't it be better to consider sets that return the same values when iterated over with ones() as equal, regardless of their internal capacities? That would be more in line with how the standard library works, for Vec and other data structures.

This could arguably be a breaking change though, not sure the maintainers would be ok with this.

I'll be glad to work on a PR for this change if well received.

Best regards,

[bluss]

Well, that sounds problematic, but the ones definition just the same, since it privileges ones over zeros 😉. Who says it's not a set of zeros?

[sitegui]

Well, it can get a little philosophical... :)

But I guess there is some precedent to consider a FixedBitSet a set of ones. For example, for "zero" sets, there are no equivalents of:

1. clear(), to put all values to 1
2. with_capacity(), to create a set with no element
3. ones()
4. and maybe, most importantly, the methods intersection, union, difference, etc cannot be applied to "zero" sets.

[bluss]

I think it sounds ok, even though it's not a necessary change. What do you think @jrraymond ?

[jrraymond]

hmmm. I can see the argument for. Although I have reservations about making such a breaking change given that this is the first time a user has raised this issue in the ~3 years since bluss created petgraph.

[jrraymond]

It is reasonable to expect the capacity of a set is not semantically meaningful. With std::collections::HashSet or std::set (in C++), there is a difference between "capacity" and "size"; "size" has semantic meaning while "capacity" is an implementation detail exposed for performance reasons.

It is also reasonable to expect that the capacity/size (ie number of bits not number of ones) of a bit set is semantically meaningful, for example the C++ std library bitset the size is part of the type of the set.

[sitegui]

I hear the counter argument @jrraymond , I think it makes sense from the bitset point of view like you said. If the user (like in my case) wants a different semantics, they can implement PartialEq on their wrapping types.

Maybe the doc can just be clearer around this case, but I agree for most users that is irrelevant :D