[m-dev.] For review: bitmap module.

[Fergus Henderson]

On 01-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> % bitmap.m
> % Ralph Becket <rbeck at microsoft.com>
> % Thu Feb  1 14:38:31 GMT 2001
> % vim: ts=4 sw=4 et tw=0 wm=0 ff=unix ft=mercury
> %
> % Efficient bitmap implementation.
> %

There should be a copyright notice (also for hash_table.m).

The module is quite similar to the `sparse_bitset' module.
It might make more sense to name this one `bitset' or `dense_bitset'
rather than `bitmap'.

Also, it would be useful to provide set operations such as
union, intersection, etc.

> :- type bitmap.
> 
> :- mode bitmap_ui == array_ui.
> :- mode bitmap_di == array_di.
> :- mode bitmap_uo == array_uo.

You should also define `inst bitmap == array' and `inst uniq_bitmap ==
uniq_array'.  That is needed in case someone defines a type which
contains a bitmap and they want to define an inst for their type.

>     % set(BM, I), clear(BM, I) and flip(BM, I) set, clear and flip
>     % bit I in BM respectively.
>     %
> :- func set(bitmap, int) = bitmap.
> :- mode set(bitmap_di, in) = bitmap_uo is det.
> 
> :- func clear(bitmap, int) = bitmap.
> :- mode clear(bitmap_di, in) = bitmap_uo is det.
> 
> :- func flip(bitmap, int) = bitmap.
> :- mode flip(bitmap_di, in) = bitmap_uo is det.
> 
>     % is_set(BM, I) and is_clear(BM, I) succeed iff bit I in BM
>     % is set or clear respectively.
>     %
> :- pred is_set(bitmap, int).
> :- mode is_set(bitmap_ui, in) is semidet.
> :- mode is_set(in, in) is semidet.
> 
> :- pred is_clear(bitmap, int).
> :- mode is_clear(bitmap_ui, in) is semidet.
> :- mode is_clear(in, in) is semidet.

I suggest also providing

	:- func get(bitmap, int) = bool.

> %
> ----------------------------------------------------------------------------
> %
> %
> ----------------------------------------------------------------------------
> %

Use `%---...---%' rather than `% ---...--- %'.
And fix your mailer so that it doesn't wrap long lines.

> :- func num_ints_required(int) = int.
> 
> num_ints_required(N) = 1 + ((N + int__bits_per_int - 1) // int__bits_per_int).

You could use int__quot_bits_per_int there.

> :- func bitmask(int) = int.
> 
>     % NOTE: it would be nicer to use /\ with a bitmask here rather
>     % than rem.  Do modern back-ends do the decent thing here if
>     % int__bits_per_int is the expected power of two?
>     %
> bitmask(I) = 1 `unchecked_left_shift` (I `rem` int__bits_per_int).

I suggest defining int__rem_bits_per_int,
similar to the int__quot_bits_per_int used by sparse_bitset.m.

> %
> ----------------------------------------------------------------------------
> %
> 
> :- func int_offset(int) = int.
> 
> int_offset(I) = 1 + (I // int__bits_per_int).

Use `int__quot_bits_per_int' here.

Probably worth a comment to explain the `1 +'.
(You explained the reason at the definition of the bitmap
type, but I think it's probably worth mentioning again here.)
Or alternatively, just do what you said earlier:

>     % NOTE: is it worth declaring constants `size_index' and `data_offet'?

> set(BM, I) =
>     BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) \/ bitmask(I)
>  :-
>     ( if in_range(BM, I) then true else throw("bitmap__set: out of range")
> ).

You should write that as

    set(BM, I) =
	( if in_range(BM, I) then
	    BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) \/ bitmask(I)
	else
	    throw("bitmap__set: out of range")
	).

Otherwise with `--no-fully-strict'
the range check might get optimized away.

The double range check -- one for bitmap, one for array --
is unfortunate.  It may be worth unsafe versions of the
array indexing procedures, that omit the range checks,
and using them here.

> clear(BM, I) =
>     BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) /\ (\ bitmask(I))
>  :-
>     ( if in_range(BM, I) then true else throw("bitmap__clear: out of range")
> ).
> 
> flip(BM, I) =
>     BM ^ elem(int_offset(I)) := BM ^ elem(int_offset(I)) `xor` bitmask(I)
>  :-
>     ( if in_range(BM, I) then true else throw("bitmap__flip: out of range")
> ).

Likewise for these two.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------