Feature Request: Stepwise SubTrie API

[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.

[Dan-wanna-M]

Is there a plan to complete this feature request? I would love to have the same API as well. I can also help if anything is missing/behaves in an undesired way.

[stefnotch]

@Dan-wanna-M From what I can gather, the owner of this repository is rarely available. Which I fully understand, life happens.

So I think for the time being, the most reasonable thing we could do would be: Properly implementing this API and submitting a PR.

• this includes writing tests and benchmarks
• if you like, we can fork this repo and work on that together
• and we can use the fork as a git dependency in cargo, for the projects where this API is needed

[Dan-wanna-M]

@stefnotch Sure, let's fork it. We can discuss the specific tests/benchmarks/etc in the forked repository or in this issue.

[stefnotch]

@Dan-wanna-M Sounds good. I invited you to the fork that I previously created as a collaborator. You should be able to do (almost) everything there.