Re: [Ocaml-lib-devel] a bug in BitSet?

[Janne H. <ja...@hy...>]

On Sun, 19 Dec 2004, Bardur Arantsson wrote:
> Compare seems completely broken to me too, at least if one
> expects it to work like you suggest (which is IMHO the
> correct way).
>
> It doesn't seem to properly account for the two bitsets
> possibly being of different lengths, it just starts
> comparing at the MSB even if the difference between the
> lengths of the sets is more than a byte. It gets more
> complicated because you can't even use |t1|>|t2| as an
> indication that t1>t2, because there is AFAICT no
> guarantee that the leading bit (or even just one bit in
> the first byte of the representation!) is set.

I'll fix this one as well.

> If they're changed to behaving in a non-destructive way,
> then the names should *definitely* be changed. For the
> sake of consistency I would suggest using the same names
> as are used in the standard library's Set:
>
>     union, inter, diff

I will add non-destructive union, diff and inter and make the old ones use 
the new non-destructive ones.  They will make unite et al. just a little 
slower -- but I guess slower is better than unsafely reading past the 
arrays.

I wonder if anyone has any ideas about the Obj.magic trickery in BitSet? 
To me it seems that using string.[] with int_of_char would do the same 
thing.  Is it just an optimization?

I would assume that ocamlopt with proper inlining should be able to do 
pretty good job on it without the added trickery.

It would be nice to be able to compile ExtLib with bounds checking on, at 
least when running the test suite.

ciao,
janne