[m-dev.] Re: sparse bitsets

[Ralph Becket]

Zoltan Somogyi, Thursday, 14 December 2006:
> 
> I have designed a data structure that I expect will provide the algorithmic
> complexity we need. I attach the description for your comments. I am starting
> work on the algorithms.

The data structure looks fine to me, although I had to do some thinking
to be sure I understood it.  Can I suggest the following change to the
documentation describing the tree:

	Level 0 nodes are leaf nodes.

	A leaf node is isomorphic to a bitmap of bits_per_int bits.

	Level k > 0 nodes are interior nodes.

	An interior node of level k + 1 has 2 ^ bits_per_level children
	of level k.

	If a node at level k is isomorphic to a bitmap of b bits, then
	a node at level k + 1 is isomorphic to the bitmap of
	b * 2 ^ bits_per_level bits formed from the concatenation of
	its child nodes.

	A node at level k, therefore, is isomorphic to a bitmap of
	bits_per_int * 2 ^ (k * bits_per_level) bits.

-- Ralph

> I am also seeking feedback on the name.

bitmap_tree?

-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------