[m-dev.] for review: use bitsets in quantification

[Fergus Henderson]

On 03-Nov-2000, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> 
> +insert(sparse_bitset(Set), Elem) =
> +		sparse_bitset(insert_2(Set, enum__to_int(Elem))).
> +
> +:- func insert_2(bitset_impl, int) = bitset_impl.
> +
> +insert_2([], Index) = [make_bitset_elem(Offset, Bits)] :-
> +	bits_for_index(Index, Offset, Bits).	
> +insert_2(Set0, Index) = Set :-
> +	Set0 = [Data0 | Rest],
> +	Offset0 = Data0 ^ offset,
> +	( Index < Offset0 ->
> +		bits_for_index(Index, Offset, Bits),
> +		Set = [make_bitset_elem(Offset, Bits) | Set0]
> +	; BitToSet = Index - Offset0, BitToSet < bits_per_int ->
> +		Bits = set_bit(Data0 ^ bits, BitToSet),
> +		Set = [make_bitset_elem(Offset0, Bits) | Rest]
> +	;
> +		Set = [Data0 | insert_2(Rest, Index)]
> +	).

It would probably be more efficient to check if the bit is already set,
and if so return Set = Set0, avoiding two memory allocations.
i.e. instead of

		Bits = set_bit(Data0 ^ bits, BitToSet),
		Set = [make_bitset_elem(Offset0, Bits) | Rest]

you could have

		( get_bit(Data0^bits, BitToSet) \= 0 ->
			Set = Set0
		;
			Bits = set_bit(Data0 ^ bits, BitToSet),
			Set = [make_bitset_elem(Offset0, Bits) | Rest]
		)

-- 
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
--------------------------------------------------------------------------