From: Brian H. <bh...@sp...> - 2003-03-11 19:44:18
Attachments:
bitset.ml
bitset.mli
|
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. Brian |
From: Blair Z. <bl...@or...> - 2003-03-13 18:13:33
|
Brian Hurt wrote: > > 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. Brian, Because this module is O(1), maybe BitVector would be a better name, as suggested by another poster on this list when we discussed the MutableList? Best, Blair -- Blair Zajac <bl...@or...> Plots of your system's performance - http://www.orcaware.com/orca/ |
From: Brian H. <bri...@ql...> - 2003-03-13 19:12:50
|
On Thu, 13 Mar 2003, Blair Zajac wrote: > Because this module is O(1), maybe BitVector would be a better name, > as suggested by another poster on this list when we discussed the > MutableList? > I don't have a problem with this name either. Again, I didn't spend much time thinking about names. Brian |
From: Nicolas C. <war...@fr...> - 2003-03-17 01:10:01
|
> 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 |
From: Brian H. <bri...@ql...> - 2003-03-17 17:19:24
|
This library is undergoing some severe redesign. Once I stopped looking at it as a 'set of small integers' and started looking at it as an 'array of bits', the requirements of the library shifted in my mind. For example, it should be possible to use the Bitvector library to implement elliptic curve cryptography (maybe not in the most efficient manner, but still). So routines like sub (returning a subsection of the array) and rotates and shifts also need to be added. Also, to implement EC crypto, you need a precise bitlength- no more rounding up to the next whole int. I was hopping to have something to distribute today, but it didn't happen. On Sun, 16 Mar 2003, Nicolas Cannasse wrote: > - 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' OK. Your first example is why I named things the way I did (well, that and old, bad, C habits). > - 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 :) Point. There isn't even a performance advantage :-) > - 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'm actually moving in the other direction, towards have specific bit sizes. Bitarray might be a better name. The reason for having specific sizes (in bits) is to have defined behavior on shifts. Does doing a shift left expand the bit array? I'll add an expand function, tho. > - I don't agree with your compare and equals implementations, since I would > say the bitsets [0] and [0 ; 0; 0 ] are equals ! Comparing bit arrays with different lengths is a tricky thing to define. > - 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 ? Probably. Consider it done. > - a new function toggle for bit toogle ( 0 -> 1 || 1 -> 0 ) Already done. Although I'm calling it negate. So the three fundemental opertations are set, clear, and negate. I'm going to drop the lists, but add set/clear/negate range functions (because these can be signifigantly speed up over calling the fundamental functions). I'll get a new .mli together and (hopefully) post it tomorrow. Brian |