Skip to content

Feature Request: Stepwise SubTrie API #40

@stefnotch

Description

@stefnotch

I'd love it if the SubTrie API were more efficient, and if it were a slightly lower level abstraction of what actually happens.

If I construct a Trie like

let mut trie = Trie::new();
let map_insert = |map: &mut Trie<Vec<u8>, u32>, key: &str, value: u32| {
    map.insert(key.as_bytes().to_vec(), value);
};
map_insert(&mut trie, "abc", 1);
map_insert(&mut trie, "abcd", 2);
map_insert(&mut trie, "abcde", 3);

Then I'd expect the following to be true

trie.subtrie(&"abc".as_bytes()[..]) == trie.subtrie(&"a".as_bytes()[..]).subtrie(&"b".as_bytes()[..]).subtrie(&"c".as_bytes()[..])

But the current subtrie API instead wants the entire prefix, over and over again.

I'd also enjoy it if there were a function akin to

trie.subtrie(&"abc".as_bytes()[..]).is_terminal()
// or 
trie.subtrie(&"abc".as_bytes()[..]).get_value() // returns an Option<V> with the value if this is a "terminal" node

My use case is parsing a stream, character by character. There, it's nice if I do not have to keep track of already parsed characters to satisfy the Trie API. Part of why I really want this is the fact that libraries like chumsky and combine very much prefer it when one does the parsing step with individual characters, and doesn't look back at what has already been parsed.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions