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

[Bardur A. <oca...@sc...>]

On Sun, Dec 19, 2004 at 01:34:26PM +0200, Janne Hellsten wrote:

> 
> >Looks like all intersect, unite, and friends have serious flaws.
> >They have been posted on this list by some people, and I added them without
> >checking. Next time I will ;)
> 
> Yep, that's what I figured as well.  But decided I will point my 
> finger at only the ones that I have a tester ready :)
> 
> I am not yet 100% sure, but it also seems that BitSet.compare is broken. 
> According to the docs, it is not absolutely clear how the comparison 
> should be interpreted, but to me a sensible compare would work the same 
> way as forming a bignum of the bitset and comparing the bignums.

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.

> 
> Currently this does not appear to be the case.
> 
> >The functions themselves are not designed correctly, I would like to change
> >them from :
> >
> >val intersect : t -> t -> unit
> >
> >to :
> >
> >val intersect : t -> t -> t
> >
> >which will produce a new bitset. Sounds more logical to me in Ocaml world.
> >Any volunteer for implementation ?
> 
> Yes, this is one nitpick that I had in mind.  Is it possible to just go 
> and change the API on these?

I think the general concensus on this list is to avoid
gratuitous changes, but necessary changes for a
cleaner/better API are OK.

> 
> I also think that "union" would be a nicer name "unite" and "difference" 
> (or "subtract") instead of "differentiate".  In my mind differentiate 
> associates to calculating derivatives.

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

Cheers,
     
-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- I'm not evil, I'm... differently motivated!