search

michaelsproul / rust_radix_trie

Fast generic radix trie implemented in Rust
https://docs.rs/radix_trie/
MIT License
188 stars 33 forks source link

Carry out the delete action at the root node. #12

Closed dwrensha closed 9 years ago

dwrensha commented 9 years ago

I think this fixes #11.

dwrensha commented 9 years ago

Hmm. Apparently this doesn't work. It fails on this program:

extern crate radix_trie;

use radix_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    trie.insert("a", ());
    trie.insert("p", ());
    trie.remove(&"a");
    assert_eq!(trie.len(), 1);
    trie.remove(&"p");
    assert_eq!(trie.len(), 0);
}
michaelsproul commented 9 years ago

Thanks for finding this bug and submitting this patch!

I ended up fixing the problem by never having a Replace action returned for the root. The root needs somewhat special handling in the current model as it isn't reached in a recursive traversal of child nodes. I think your patch didn't quite work because it changed the assumption that the root's key is always [], which is relied upon in several places.