I'm currently dealing with a GraphQL API where I need to have a map (key-value dictionary) I can paginate. Basically I get a key cursor which is where I want to start iterating, and I want to get the next values, ordered by key.
HashMap is not suited for the task as keys aren't ordered, but BTreeMap is perfect. Only problem, I cannot get the position of a key in the map.
Here is an example to make it clearer:
// K implements Ord + Eq + Hash + Clone, let's use 'char' here
// V implements nothing
let mut map = ImaginaryMap::<char, i32>::new();
map.insert('a', 1);
map.insert('b', 2);
map.insert('c', 3);
// Let's suppose we have a cursor (which is a key from the map)
let cursor: K = 'b';
// I want to find which position the key occupies (e.g. if it's the first key in order, the second, the third, etc.)
// Here, this will return 1 (0 being the very first key)
let pos: Option<usize> = map.find_key_pos(&cursor);
// And then I can iterate in order
let iter = map.values().skip(pos.unwrap());
Are you aware of any structure that does this? I also checked IndexMap but it uses the keys' insertion order instead of their sorting order.
Seems like it could! I have a question though: why doesn't Cursor implement Iterator?
The API I'm using requires to make an iterator, I can write my own struct wrapping Cursor but I'm curious as to why it isn't an iterator type itself.
Could BTreeMap::range(cursor..) be a solution? That works on stable. For example (playground):
use std::collections::BTreeMap;
fn main() {
// K implements Ord + Eq + Hash + Clone, let's use 'char' here
// V implements nothing
let mut map = BTreeMap::<char, i32>::new();
map.insert('a', 1);
map.insert('b', 2);
map.insert('c', 3);
// Let's suppose we have a cursor (which is a key from the map)
let cursor = 'b';
map.range(cursor..).for_each(|(key, value)| {
eprintln!("{key}: {value}");
});
}
Btw the proper name of a search tree where you can obtain the index of an entry in O(log n) is "order-statistics tree". In this case though something like range should be much better.