Add the ability to return a Trie with a root prefix included

[michaelsproul]

Sorry it's been so long with no reply! I was hesitant to merge this because I'm not sure this is the most general solution... but I think it's pretty good and I may as well merge it for now. I'll have to check over it when I have time, but hopefully that shouldn't be too much longer!

[andrewcsmith]

This is one of those things where I'm not even sure how it works anymore. Luckily there's a test!

How could it be more general? I think it probably adds a little generality, maybe not ultimate generality, but then again that bridge can wait for the moment.

[michaelsproul]

How could it be more general? I think it probably adds a little generality, maybe not ultimate generality, but then again that bridge can wait for the moment.

I think there are few issues worth addressing:

• If we do this properly, then this version of get_node should supersede the old one (which is unsafe and really shouldn't exist). It should also supersede the private GetNodeMut traversal that is used to implement get_mut.
• All of the methods available on ordinary tries should be available on subtries. This makes me think that the core structure of the trie actually needs changing. I based this code on a radix trie in the standard library that had a struct for the root and a struct for internal nodes. I did away with the distinction for the sake of simplicity but it might be time to re-introduce it. Perhaps something like:

// Equivalent to the `Root` structure in your current code, but replacing the current top-level Trie.
struct Trie<K, V> {
  prefix: NibbleVec,
  node: TrieNode<K, V>
}

enum TrieNode<K, V> {
    key: NibbleVec,
    key_value: Option<Box<KeyValue<K, V>>>,
    length: usize,
    child_count: usize,
    children: [Option<Box<TrieNode<K, V>>>; BRANCH_FACTOR]
}

Now the problem with this is that the Root owns the node that it contains, but if we're returning a sub-trie, we might want to return a struct with an allocated NibbleVec and a borrowed trie node (as in the current set-up). One way to do this safely and without duplicating code everywhere might be to parameterise over things that can appear as nodes...

struct Trie<K, V, N> {
  prefix: NibbleVec,
  node: N
}

I dunno, seems like a right mess.

[andrewcsmith]

So, I'm just now returning to the project that uses this as a fairly integral component. Is there any reason we couldn't just do:

struct Trie<'a, K, V> {
    prefix: NibbleVec,
    node: Cow<'a, TrieNode<K, V>>
}

Seems to me like this would allow for returning a Trie that could contain a sub-trie, which would be borrowed initially but could optionally be written to.

[michaelsproul]

@andrewcsmith: Using a Cow looks like a good idea. I'm sorry I really haven't had any time to work on this crate recently, if you'd like to have a crack at implementing the changes we've discussed, I'll give you commit rights to the repo.

[andrewcsmith]

Sounds good. I'm doing some work on tangentially related stuff over the next month, so I'll see if I can work this fix into that.

[michaelsproul]

Hi @andrewcsmith, I have good news! I found some time to work on this, and I think I've solved the subtrie problem! I started off mainly trying to optimise the core get/insert/remove operations, ended up adding a distinct TrieNode struct, and then the SubTrie stuff kind of just fell out, at the cost of slightly more code.

The Traversal traits as they once were are dead, because the Trie now uses iteration for almost all its operations (and tail recursion for remove at the moment).

If you could try out the new subtrie API in your project and provide feedback that would be much appreciated :smile:. You can find it on this branch:

https://github.com/michaelsproul/rust_radix_trie/tree/new-stuff

(and this PR: https://github.com/michaelsproul/rust_radix_trie/pull/21)

The diff isn't particularly useful because of the extensive restructuring of almost everything.

Cheers,

Michael