Re: [Ocaml-lib-devel] BitSet

[Prakash C. <Pra...@im...>]

Nicolas Cannasse wrote:
> Thanks,

You're welcome :)

> The CVS have been updated with your changes. To answer more precisely
> to your questions :
> - we could actualy use ints as 16 bits values if we add the API to 
> extract them from strings, but we don't :)

Why not to add this API ? It might also be useful in to improve other 
data structures. And why only 16 bits and not 32 ?

> - I disabled the "deprecated" on "clone", having both copy and clone
> is okay.

Doesn't matter, it was only a suggestion to avoid too much duplicate 
functions.

> - we can't use Pervasives.compare because bitsets might be of
> different sizes but are actually the same integer

I didn't want to say that Pervasives.compare should be used directly. I 
suggested something like that :

(************************************************************)
let extend t old_size new_size =
   let b = bcreate new_size in
   bblit !t 0 b 0 old_size;
   bfill b old_size (new_size - old_size) 0;
   b

let compare t1 t2 =
   let size1 , size2 = blen !t1 , blen !t2 in
   if size1 < size2 then
     Pervasives.compare (extend t1 size1 size2) !t2
   else if size1 > size2 then
     Pervasives.compare !t1 (extend t2 size2 size1)
   else
     Pervasives.compare !t1 !t2
(************************************************************)

And the function 'extend' can be used in both 'set' and 'toggle' :

(************************************************************)
let set t x =
   if x < 0 then error "set";
   let pos , delta = x lsr log_int_size , x land int_size in
   let size = blen !t in
   if pos >= size then t := extend t size (pos+1);
   bset !t pos ((bget !t pos) lor (1 lsl delta))

let toggle t x =
   if x < 0 then error "toggle";
   let pos , delta = x lsr log_int_size , x land int_size in
   let size = blen !t in
   if pos >= size then t := extend t size (pos+1);
   bset !t pos ((bget !t pos) lxor (1 lsl delta))
(************************************************************)


Bye,

-- 
Prakash