pwil3058/gosets — Issue #1: Union Cardinality
Author: Kalthorn
Created: 2012-01-16 18:42:11+00:00
State: open

Peter,

Thanks for the bitset library, I think it will fit my needs perfectly. I have a question about the cardinality of unions though. I'm using the not-quite-latest weekly release of Go (12-22, I think the newest is 1-15).

When I compile your example file, main.go, and then run the result, the 'array' variable printed at the end has a length that I didn't expect. The length of the array is determined using setu.Cardinality() where 'setu' is the union of sets A and B. I added some additional printouts that you can see below.

Set A cardinality: 5
Set B cardinality: 4
...
Set U cardinality: 12 // printed right after creation of set U
...
{99, 1, 4, 6, 9} + {9999, 4, 6, 7} = {1, 4, 6, 7, 9, 99, 9999} // this is A + B = set U
...
Array length: 12
...
[99 9999 1 4 6 7 9 0 0 0 0 0]

As you can see, set U has only 7 values but the cardinality it reported as 12 so the final array has zeros padding the end. My question is if this is correct behavior. It is possible that the behavior is because of a small change I made to compile against the weekly release that I'm using. It would be time consuming to revert my Go installation back to 60.3 (or whatever the Release version is), which is why I haven't tested your output in its original environment.

Specifically, I had to edit your bitset.go file at line 102 to make use of the new built-in delete() function for removing items from maps. This happens inside the clearBit() method. I don't see union() making use of clearBit() at all though.