Feature request: index_of()?

[jrmoserbaltimore]

I've been looking all over for some kind of key-value store using a hierarchical bitmap, but all I've found are sets. I could make one myself, but I'd need some way to know the index of an element in the set.

For example:

let j = my_bitset.index_of(element);
let k = if j.is_some() {
    Some(my_data_vec[j.unwrap()])
} else {
    None
}

[tower120]

First of all, if you need map, there is https://github.com/tower120/hi_sparse_array - which is basically hi_sparse_bitset but with data at last level + bunch of other improvements. I think I need a month or two to make it crate-ready. But looks like most of the research/design-related issues are solved.

Second, what is index_of? DataBlocks, or nodes are not stored in level-container in order. (For performance reasons - so removing one node - would not require to move(or at least change node-indices) all other nodes in level-container)

[tower120]

Wait, I think I understand the closest thing you want. You want index of terminal SIMD-BitBlock. But at first, as-is, BitBlocks are not stored contiguously (but they could - that's design choice). And second - well that's block index, you still have to deal with bit inside of it.

These questions are addressed in https://github.com/tower120/hi_sparse_array - it's data structure and operation-interface specifically changed to support that. I hope to make hi_sparse_bitset just a special case of https://github.com/tower120/hi_sparse_array one day.

[jrmoserbaltimore]

If there are 73 numbers stored, 1 7 9 42 1893 40958 144938 etc., I want my_bitmap.index_of(1893) to return 4.

Didn't know there was hi_sparse_array, it didn't show up on Google or crates.io.

[tower120]

If there are 73 numbers stored, 1 7 9 42 1893 40958 144938 etc., I want my_bitmap.index_of(1893) to return 4.

As is, there is no such information in hi_sparse_bitset's data structure. At least I don't see how to retrive ordered index in O(1) time. If you see how to get it from this structure let me know. It looks like for this to achieve, each node should store cumulative number of elements stored in it. Then, by summing elements count of all nodes before requested (at each level), it is somehow possible to calculate ordered index of element.

Didn't know there was hi_sparse_array, it didn't show up on Google or crates.io.

It is still in development, it's not finished

[tower120]

Anyway, that will be highly inefficient even if it could be retrieved in O(1) time, since you'll have to keep you're my_data_vec sorted. This mean O(N) at each insert/remove.

[tower120]

Just wait for a month or so - I bet hi_sparse_array will do what you want to achieve.

[tower120]

If by any chance you still need hierarchical bitmap as MAP: https://crates.io/crates/hibit_tree . It is still somewhat unpolished. In doc department, at least.

It was renamed from previous hi_sparse_array to better reflect what it actually is.
Very unsure about naming in API, and ... everything in that project, thou.