Re: [Ocaml-lib-devel] Third Library: Bitset

[Nicolas C. <war...@fr...>]

> Third and last library being submitted for comment: Bitset.
>
> This library implements sets of small non-negative integers as a bitset.
> The big advantage of this implementation is O(1) adding, removing, or
> testing for membership.

Few remarks :
- (same remarks about the code look as for ExtList )
- the functions and types are all started with  bitset_ ( C like notation,
without namespace )
   instead of doing :
            open BitSet;;
            let b = bitset_empty 10 in
            bitset_add b 1;
    it's better to use the module system :
            let b = BitSet.empty 10 in
            BitSet.add b 1;
    this is more like 'ocaml style'
- the functions add_list and remove_list are useless, since :
            bitset_add_list b l  == List.iter (bitset_add b) l
            ( perhaps it's convenient for you to have it available, but we
can't add a  "_list version of all functions for all the modules we're
writting :)
- about the design itself, it looks good, but perhaps it would be good to
create an empty bitset with a default size (that's what you're doing), and
then having it growing automaticly when needed ( right now you're relying on
array bounds check, you need to do checks by hand - if the user turn them
off - and raise a BitSet specific exception )
- I don't agree with your compare and equals implementations, since I would
say the bitsets [0] and [0 ; 0; 0 ] are equals !
- wouldn't it better to replace bitset_first_member + bitset_next_member +
bitset_to_list by two functions BitSet.map and BitSet.iter that are more in
the functionnal way of doing things ?
- a new function toggle for bit toogle ( 0 -> 1  || 1 -> 0 )

My proposal interface

----bitVector.mli ( V maj for BitVector module )

type t

(** theses two are only needed if you're not resizing the array dynamicaly
**)
exception Invalid_bit_index of int
val size : t -> int

val empty : int -> t
val is_empty : t -> bool
val clone : t -> t
val add : t -> int -> unit (* raise Invalid_bit_index *)
val remove : t -> int -> unit (* raise Invalid_bit_index *)
val toggle : t -> int -> unit (* raise Invalid_bit_index *)
val contains : t -> int -> bool
val compare : t -> t -> int
val equals : t -> t -> bool
val iter : (int -> unit) -> t -> unit
val map : (int -> 'a) -> t -> 'a list

Nicolas Cannasse