[m-dev.] Re: sparse bitsets
Ralph Becket
rafe at csse.unimelb.edu.au
Fri Dec 15 10:52:37 AEDT 2006
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
--------------------------------------------------------------------------
More information about the developers
mailing list