Leonine is an implementation of the Roaring Bitmaps data structure for efficient representation of sets of 32-bit values. For more information about leonine see the documentation or refer to the Roaring Bitmaps web-site for other implementations and publications about the data structure.
Please note: This is a work in progress and is not yet ready for use. When complete it will be released on Hackage.
The Roaring Bitmap structure divides the 32-bit keys into two 16-bit values. One, the high order bits, identifies a chunk within the map and the other, the low order bits, identifies a bit within the chunk.
There are two chunk representations:
-
A sparse chunk contains a
Word16for each bit present in the chunk. -
A dense chunk contains 4096
Word16s which contains exactly one bit for every possible bit which can be present in the chunk.
The structure will convert the representation of each chunk as bits are set and cleared from the map.