You're no longer on crates.io. Probably should either get back on there or remove that part from documentation.

just to be sure if it's me or just a current limitation of the library,

when trying to create Trie<String, ()> , i then get

src/main.rs:122:11: 122:26 error: type &radix_trie::Trie<collections::string::String, ()> does not implement any method in scope named get_node
src/main.rs:122 words.get_node(value).and_then(|node| node.is_leaf()).or(false)

and I don't see what i could be doing wrong in my code ?

Hey,
I have pretty good result from this crate but I need the value to be mutable. Is it possible ?
pub fn get_ancestor_value_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>

I'm looking at your traversal traits, and attempting to write a struct that visits all the immediate children of a node and adds their values. However, given that the children field is private, I can't figure out how to make my struct traverse the child nodes. Is there something in the current interface that allows this, or would I have to change the actual crate code?

My RefTraversal code right now (Trie essentially stored as <&str, u32>):

struct GetChildren;
impl<'a, K: Debug + TrieKey + 'a> RefTraversal<'a, K, u32> for GetChildren {
    type Input = &'a Trie<K, u32>;
    type Output = u32;

    fn default_result() -> Self::Output { 0u32 }

    fn child_match_fn(trie: &'a Trie<K, u32>, input: Self::Input, nv: NibbleVec) -> Self::Output {
        // Children code goes here
        Self::run(&input, &input, nv);
        trie.value().unwrap_or(&0u32).clone()
    }

    fn action_fn(trie: &'a Trie<K, u32>, intermediate: Self::Output, bucket: usize) -> Self::Output {
        intermediate + trie.value().unwrap_or(&0u32)
    }
}

To demonstrate the issue I made the following change the prefix test case in the test module:

15:32:20:rust_radix_trie(remove-bug *) $ git diff src/test.rs
diff --git a/src/test.rs b/src/test.rs
index 9caae9b..e85977e 100644
--- a/src/test.rs
+++ b/src/test.rs
@@ -450,7 +450,9 @@ fn test_get_raw_descendant_borrow() {
 #[test]
 fn test_prefix() {
     let mut t = Trie::<u8, ()>::new();
+    t.remove(&0xf1);
     t.insert(0xf1, ());
+    t.remove(&0xf2);
     t.insert(0xf2, ());
     println!("{:#?}", t);
     assert_eq!(t.prefix(), [].as_ref());

Afterwards I get this failure:

15:27:25:rust_radix_trie(remove-bug *) $ RUST_BACKTRACE=1 cargo test test_prefix
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running target/debug/deps/radix_trie-2113ab568ed5b82e

running 1 test
test test::test_prefix ... FAILED

failures:

---- test::test_prefix stdout ----
Trie {
    length: 2,
    node: TrieNode {
        key: NibbleVec [],
        key_value: None,
        child_count: 1,
        children: [
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            Some(
                TrieNode {
                    key: NibbleVec [15, 2],
                    key_value: Some(
                        KeyValue {
                            key: 242,
                            value: (),
                        },
                    ),
                    child_count: 0,
                    children: [
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                    ],
                },
            ),
        ],
    },
}
thread 'test::test_prefix' panicked at 'assertion failed: `(left == right)`
  left: `NibbleVec [15, 2]`,
 right: `[15]`', src/test.rs:460:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:208
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:474
   5: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:381
   6: std::panicking::begin_panic_fmt
             at src/libstd/panicking.rs:336
   7: radix_trie::test::test_prefix
             at src/test.rs:460
   8: radix_trie::test::test_prefix::{{closure}}
             at src/test.rs:451
   9: core::ops::function::FnOnce::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libcore/ops/function.rs:231
  10: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/liballoc/boxed.rs:704
  11: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:85
  12: test::run_test::run_test_inner::{{closure}}
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:272
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panic.rs:394
             at src/libtest/lib.rs:1468


failures:
    test::test_prefix

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 48 filtered out

error: test failed, to rerun pass '--lib'

Next, I added a call to check_trie_integrity like this:

diff --git a/src/test.rs b/src/test.rs
index 9caae9b..f775775 100644
--- a/src/test.rs
+++ b/src/test.rs
@@ -450,8 +450,11 @@ fn test_get_raw_descendant_borrow() {
 #[test]
 fn test_prefix() {
     let mut t = Trie::<u8, ()>::new();
+    t.remove(&0xf1);
     t.insert(0xf1, ());
+    t.remove(&0xf2);
     t.insert(0xf2, ());
+    assert!(t.check_integrity());
     println!("{:#?}", t);
     assert_eq!(t.prefix(), [].as_ref());
     let first = t.children().next().unwrap();

The resulting test failure looks like this:

15:28:44:rust_radix_trie(remove-bug *) $ RUST_BACKTRACE=1 cargo test test_prefix
   Compiling radix_trie v0.1.4 (/home/kelly/repos/rust_radix_trie)
    Finished dev [unoptimized + debuginfo] target(s) in 1.02s
     Running target/debug/deps/radix_trie-2113ab568ed5b82e

running 1 test
test test::test_prefix ... FAILED

failures:

---- test::test_prefix stdout ----
thread 'test::test_prefix' panicked at 'assertion failed: t.check_integrity()', src/test.rs:457:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:208
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:474
   5: std::panicking::begin_panic
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:408
   6: radix_trie::test::test_prefix
             at src/test.rs:457
   7: radix_trie::test::test_prefix::{{closure}}
             at src/test.rs:451
   8: core::ops::function::FnOnce::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libcore/ops/function.rs:231
   9: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/liballoc/boxed.rs:704
  10: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:85
  11: test::run_test::run_test_inner::{{closure}}
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:272
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panic.rs:394
             at src/libtest/lib.rs:1468


failures:
    test::test_prefix

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 48 filtered out

error: test failed, to rerun pass '--lib'

So it seems that attempting to remove a key from the trie that doesn't exist in this manner has negative effect on the trie integrity.

I made the following change to the traversal module and it resolves the issue and all the tests pass (including my modifications):

15:29:03:rust_radix_trie(remove-bug *) $ git diff src/traversal.rs
diff --git a/src/traversal.rs b/src/traversal.rs
index 3395338..4a6a183 100644
--- a/src/traversal.rs
+++ b/src/traversal.rs
@@ -182,7 +182,10 @@ where
                 KeyMatch::SecondPrefix => {
                     let depth = child.key.len();
                     rec_remove(trie, child, bucket, key, depth, &nv)
-                }
+                },
+                KeyMatch::Partial(idx) => {
+                    rec_remove(trie, child, bucket, key, idx, &nv)
+                },
                 _ => None,
             }
         }

15:30:41:rust_radix_trie(remove-bug *) $ cargo test
   Compiling radix_trie v0.1.4 (/home/kelly/repos/rust_radix_trie)
    Finished dev [unoptimized + debuginfo] target(s) in 0.99s
     Running target/debug/deps/radix_trie-2113ab568ed5b82e

running 49 tests
test qc_test::subtrie_mut_get ... ok
test test::ancestor_key ... ok
test test::child_subtrie_keys ... ok
test test::empty_key ... ok
test test::from_iter ... ok
test test::get_ancestor_bug ... ok
test test::get_nonexistant ... ok
test test::get_prefix_bug ... ok
test test::get_raw_descendant ... ok
test test::insert ... ok
test test::insert_replace ... ok
test test::int_keys ... ok
test test::iter ... ok
test test::map_with_default ... ok
test test::nearest_ancestor ... ok
test test::nearest_ancestor_no_child_fn ... ok
test test::nearest_ancestor_root ... ok
test test::raw_ancestor ... ok
test test::raw_ancestor_prefix ... ok
test test::raw_descendant_prefix ... ok
test test::remove ... ok
test test::remove_non_existent ... ok
test test::remove_simple ... ok
test test::root_replace_bug ... ok
test test::subtrie ... ok
test test::subtrie_insert ... ok
test test::subtrie_len ... ok
test test::subtrie_lifetime ... ok
test test::subtrie_mut_lifetime ... ok
test test::subtrie_nonexistant ... ok
test test::subtrie_string ... ok
test test::test_get_ancestor_borrow ... ok
test test::test_get_ancestor_value_borrow ... ok
test test::test_get_borrow ... ok
test test::test_get_mut_borrow ... ok
test test::test_get_raw_ancestor_borrow ... ok
test test::test_get_raw_descendant_borrow ... ok
test test::test_prefix ... ok
test test::test_remove_borrow ... ok
test test::test_subtrie_borrow ... ok
test test::test_subtrie_mut_borrow ... ok
test test::unicode ... ok
test qc_test::subtrie_get ... ok
test qc_test::subtrie ... ok
test qc_test::values_iter ... ok
test qc_test::keys_iter ... ok
test qc_test::remove_non_existent ... ok
test qc_test::insert_all_remove_all ... ok
test qc_test::subtrie_insert ... ok

test result: ok. 49 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests radix_trie

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

I don't know if that's a good fix or not, but I just noticed from adding dbg statements that the problem happened in rec_remove when the result of the match_keys call was KeyMatch::Partial.

the crate trust-dns-client depends on radix_trie and it uses nibble_vec, when using nibble_vec 0.0.4, there is no problem.

after updating nibble_vec to 0.0.5 and run cargo check, it reports

    Checking nibble_vec v0.0.5
   Compiling learn v0.1.0 (/home/sherlock/Documents/program/rust/learn)
    Checking radix_trie v0.1.6
error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/iter.rs:87:13
   |
87 |     prefix: NibbleVec,
   |             ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:354:46
    |
354 |     ExtendKey(&'a TrieNode<K, V>, usize, &'a NibbleVec),
    |                                              ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/trie_node.rs:10:14
   |
10 |     pub key: NibbleVec,
   |              ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/lib.rs:60:13
   |
60 |     prefix: NibbleVec,
   |             ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/lib.rs:67:13
   |
67 |     prefix: NibbleVec,
   |             ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/iter.rs:92:21
   |
92 |     pub fn new(key: NibbleVec, node: &'a TrieNode<K, V>) -> Self {
   |                     ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/keys.rs:49:45
   |
49 | pub fn match_keys(start_idx: usize, first: &NibbleVec, second: &NibbleVec) -> KeyMatch {
   |                                             ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/keys.rs:49:65
   |
49 | pub fn match_keys(start_idx: usize, first: &NibbleVec, second: &NibbleVec) -> KeyMatch {
   |                                                                 ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/keys.rs:28:25
   |
28 |     fn encode(&self) -> NibbleVec {
   |                         ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/subtrie.rs:24:14
   |
24 |     prefix: &NibbleVec,
   |              ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/subtrie.rs:110:56
    |
110 | fn stripped(mut key: NibbleVec, prefix: &NibbleVec) -> NibbleVec {
    |                                                        ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/subtrie.rs:110:22
    |
110 | fn stripped(mut key: NibbleVec, prefix: &NibbleVec) -> NibbleVec {
    |                      ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/subtrie.rs:110:42
    |
110 | fn stripped(mut key: NibbleVec, prefix: &NibbleVec) -> NibbleVec {
    |                                          ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:92:13
   |
92 |     mut nv: NibbleVec,
   |             ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:215:10
    |
215 |     nv: &NibbleVec,
    |          ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:269:10
    |
269 |     nv: &NibbleVec,
    |          ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:312:10
    |
312 |     nv: &NibbleVec,
    |          ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:359:10
    |
359 |     nv: &NibbleVec,
    |          ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:53:51
   |
53 |         fn $name<'a, K, V>(trie: $trie_type, nv: &NibbleVec) -> Option<$trie_type> {
   |                                                   ^^^^^^^^^ expected 1 type argument
...
85 | get_func!(name: iterative_get, trie_type: &'a TrieNode<K, V>, mutability: );
   | ---------------------------------------------------------------------------- in this macro invocation
   |
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:53:51
   |
53 |         fn $name<'a, K, V>(trie: $trie_type, nv: &NibbleVec) -> Option<$trie_type> {
   |                                                   ^^^^^^^^^ expected 1 type argument
...
86 | get_func!(name: iterative_get_mut, trie_type: &'a mut TrieNode<K, V>, mutability: mut);
   | --------------------------------------------------------------------------------------- in this macro invocation
   |
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:14:28
   |
14 |     pub fn get(&self, nv: &NibbleVec) -> Option<&TrieNode<K, V>> {
   |                            ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:18:36
   |
18 |     pub fn get_mut(&mut self, nv: &NibbleVec) -> Option<&mut TrieNode<K, V>> {
   |                                    ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:22:52
   |
22 |     pub fn insert(&mut self, key: K, value: V, nv: NibbleVec) -> Option<V> {
   |                                                    ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:34:37
   |
34 |     pub fn get_ancestor(&self, nv: &NibbleVec) -> Option<(&TrieNode<K, V>, usize)> {
   |                                     ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:38:41
   |
38 |     pub fn get_raw_ancestor(&self, nv: &NibbleVec) -> (&TrieNode<K, V>, usize) {
   |                                         ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/traversal.rs:42:50
   |
42 |     pub fn get_raw_descendant<'a>(&'a self, nv: &NibbleVec) -> Option<DescendantResult<'a, K, V>> {
   |                                                  ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/trie_common.rs:53:28
   |
53 |     fn prefix(self) -> &'a NibbleVec {
   |                            ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/trie_node.rs:53:42
   |
53 |     pub fn with_key_value(key_fragments: NibbleVec, key: K, value: V) -> TrieNode<K, V> {
   |                                          ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/trie_node.rs:217:38
    |
217 |     pub fn as_subtrie(&self, prefix: NibbleVec) -> SubTrie<K, V> {
    |                                      ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/trie_node.rs:226:17
    |
226 |         prefix: NibbleVec,
    |                 ^^^^^^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
   --> /home/sherlock/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.6/src/trie_node.rs:239:54
    |
239 |     pub fn check_integrity_recursive(&self, prefix: &NibbleVec) -> (bool, usize) {
    |                                                      ^^^^^^^^^ expected 1 type argument

error: aborting due to 31 previous errors

For more information about this error, try `rustc --explain E0107`.
error: could not compile `radix_trie`.

To learn more, run the command again with --verbose.

My use case is I have http routes like /a /b in the trie, and there are some dynamic routes like /z/* where I want to find the handler for /z and then do something with /*.

Right now you can

1. Look up a value by exact match
2. Look up the nearest ancestor, but without the ability to know if it's an exact match

The lookup seems like it keeps track of how much is left of the key while traversing the trie, so if that could be returned somehow the user could at least check if the remaining key length is 0, if not recover the utf8 suffix.

If the nodes stored parent nodes one could potentially walk back up the subtrie and concatenate prefixes to get a full utf8 prefix, and use the lengths to slice the suffix.

I'm not sure what other use cases there are here, so I'm not sure how much information would need to be returned in the general case, or what the interface should look like.

Is there an alternative way to achieve my use case with the current library?

The Documentation link on crates.io points to the old documentation hosted on github pages that no longer exists.

I've found 3 in the past day. Really needs QuickCheck tests.

The idea:
The most natural thing for the prefix implementation is Vec<T>. The Trie is currently implemented through serialization of the key value into Vec<u8>.
Could be great if Vec<T> was usable as 'plain' key, without making it into Vec<u8>, probably with some limitations to T. Such limitations could probably be some kind of TrieKeyItem trait, meaning that a type can be a single item of a key making TrieKey into TrieKey<Item=Something>.
This brings alot of convenience and univerality to the datastructure. Strings, for example could be stored as bytes or unicode symbols depending of user needs.
The Vec<u8> in this case could be made into some external thing and only be used for types that could not be easily converted into corresponding vector implementation.

It seems to me that first step could be to "just" convert u8 to some internal generic type, probably not seen to user, but being replaced to Item type when the Vec(Iterable?, Indexable?) has been provided as a key.

The fallback:
In the case the idea below is impossible(in the context of this library of course), we could probably try implementing TrieKey for Vec<T: TrieKey> at least. That will probably require some unneeded computation when converting from/into such vectors but will still be very useful.

Hi,

I'm a bit confused as to how this is supposed to be used.

My example is as follows:

I have many entries (sentences/paragraphs etc.)

given an arbitrary prefix, I would like to retrieve all relevant matches from the trie.

For example:

Trie construction by these phrases

1. Hello I am happy
2. Hello I am sad
3. Hello I am afraid
4. Hello you are sad
5. Hello you are happy

If I understand correctly the trie would compress along these lines

                                                                   │ compressed�
         ┌─────────────────────────►   Hello                       │
         │                              │   │                      │    │
         │                              │   │                      │    │
         │                              │   │          ◄───────────┘    │
         │ ┌─────────────────────► I ◄──┘   └──► You                    │
compressed │                        │              │          ◄─────────┘
                                    │              └──► are
           │                        ▼                     ▼  │
           └───────────────────►  a�m�│                  sad └──────►  happy
                                     ┌┤
                                 │   ▼│
                        happy◄───┘ sad└─────►afraid

Now given a partial phrase such as:
Hello I

I would like to be able to retrieve the results for 1,2,3 (since they share the prefix Hello I)

Can you point me in how to achieve this?

Thanks!

It will be great if this lib can expose c ffi so that other managed language can create wrapper that maps byte array to object reference address

Pretty sure the action part of the traversal traits is killing performance by disabling tail call optimisation. So far experiments to make the remove traversal tail-recursive have been unsuccessful, and it's tempting to resort to unsafe code.

map_with_default calls self.get_mut and self.insert; both of these functions encode the key as the first thing they do : this means that mis-heavy workloads encode the key twice as often as there are actual API calls made to the trie.

related to #32 but distinct i think since they need to be fixed separately.

like it has been done in sequence trie

today i tried to implement them by adding a property "parent" (Option on a pointer of the parent trie node) to the TrieNode , so that the iterator would not need to keep a stack of the trie node he's traversing, but I didn't get it to compile (because of borrowed value being moved when setting the parent attribute )

Now that I think about it, the stack solution may not be that slower , and it will not need to add one more attribute for every single trienode.

I wish the radius_trie would provide a feature to get the values for all prefix matches.

    let mut trie = Trie::new();
    trie.insert("/a/c", "/a/c");
    trie.insert("/a/b/", "/a/b/");
    trie.insert("/a/b/c", "/a/b/c");
    assert_eq!(vec!["/a/b/", "/a/b/c"], trie.get_ancestor_values("/a/b/c"));

It's tail recursive now, which is better, but I think it could still be faster.

The note for action_fn on line 78 of rust_radix_trie/src/traversal.rs says:

#[doc = "Note: this function isn't called in a `RefTraversal`/`RefTraversalMut`."]
#[allow(unused)]
fn action_fn...

The usage of it on line 111:

if_else!($with_action, Self::action_fn(trie, intermediate, bucket), intermediate)

And the definitions of the traversals on line 117:

make_traversal_trait!(name: Traversal, trie_type: &Trie<K, V>, with_action: true, mutability: );
make_traversal_trait!(name: RefTraversal, trie_type: &'a Trie<K, V>, with_action: true, mutability: );

make_traversal_trait!(name: TraversalMut, trie_type: &mut Trie<K, V>, with_action: true, mutability: mut);
make_traversal_trait!(name: RefTraversalMut, trie_type: &'a mut Trie<K, V>, with_action: false, mutability: mut);

The inconsistent part seems to be that with_action for RefTraversal is true instead of false.

Hey! I've been wondering if this library supports multithreading in rust.
Thanks! :)

Is there some way to get the prefix of a subtrie and convert it back to the original data type?

I get a panic when I try to run the following minimal test case with radix_trie 0.1.3:

extern crate radix_trie;
use radix_trie::Trie;

fn main() {
    let mut trie : Trie<String,bool> = Trie::new();
    trie.insert("token_rst".to_owned(), true);

    println!("{:?}", trie.remove("syntax")); // this line crashes
}

thread 'main' panicked at 'attempted access beyond vector end. len is 12, index is 18', /home/thomas/.cargo/registry/src/github.com-1ecc6299db9ec823/nibble_vec-0.0.4/src/lib.rs:74:13
[...]
  7: nibble_vec::NibbleVec::get
             at /home/thomas/.cargo/registry/src/github.com-1ecc6299db9ec823/nibble_vec-0.0.4/src/lib.rs:74
   8: radix_trie::traversal::rec_remove
             at /home/thomas/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.3/src/traversal.rs:197
   9: radix_trie::traversal::recursive_remove
             at /home/thomas/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.3/src/traversal.rs:169
  10: radix_trie::traversal::<impl radix_trie::trie_node::TrieNode<K, V>>::remove
             at /home/thomas/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.3/src/traversal.rs:27
  11: radix_trie::trie::<impl radix_trie::Trie<K, V>>::remove
             at /homtioe/thomas/.cargo/registry/src/github.com-1ecc6299db9ec823/radix_trie-0.1.3/src/trie.rs:54
  12: trie_bug::main
             at src/main.rs:8

This is specifically triggered by the combination of the values token_rst and syntax.
As far as I understand the documentation and by trying other values , a simple None should be returned as result of removing the non-existant value.

I tried to debug this but can't figure out yet why this combination of insert/remove crashes.

See the HashMap docs.

it's 1:30 am so i just put the ticket here. But actually for my chinese parsing tool I still use from sequence trie a method that is not yet in radix trie, the "get_node" to know if there is at least a key starting with that string (and longer than it) (i don't need to know how man

It'd be nice to be able do lookups with &str keys in a Trie<String, V>.

Created appveyorer CI in PR: #42 please let me know your concerns

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); 
}

thread '<main>' panicked at 'assertion failed: `(left == right)` (left: `0`, right: `1`)',

I think this occurs whenever the root node goes from having 2 children to having only 1 child. Trie::delete_node() tries to replace the root node with its only child, but Trie::remove() ignores the DeleteAction that would make this work.

In problem #45 the question of key storage was raised. To reduce the size of the tree in memory, this is a good optimization.

I was thinking about looking into using string-interner to look into #47 and poke around with a few other optimizations, do you have a standard way to benchmark the changes or should I add benchmarking stuff?

If you do something like this, everything goes badly wrong:

trie.get_ancestor(key1).insert(key2, value);

The node returned by get_ancestor has the beginning of its binary key-representation missing. For some k with representation [k1, k2, ... ki, ... ], the key_fragments stored at the node will only be [ki, ...], leading to incorrect inserts/gets/removes. At the moment inserts and removes are impossible because none of the methods return a mutable trie, but gets are broken and we could fix everything by doing something like this:

struct SubTrie<K, V> {
  prefix: NibbleVec,
  trie: &Trie<K, V>
}
// plus a corresponding mutable version.

Due to OsStrings not losslessly converting to UTF-8 (and therefore bytes) on Windows (see SO, Rust docs), we are currently missing an implementation of TrieKey for Path/PathBuf.

One solution might be to use the OsStr::to_string_lossy function.

Get, insert and remove all follow the same traversal pattern which I think could be captured in a higher-order function.

the example code has this:

    // This is a bit of a hack that relies on knowing the binary representation of
    // strings... "abd" works, but "abz" doesn't...
    let ab_sum = t.get_raw_ancestor(&"abd").children().fold(0, |acc, c| {
        println!("Iterating over child with value: {:?}", c.value());
        acc + *c.value().unwrap_or(&0)
    });

I tried it, indeed, "abz" doesn't work. Why? What can be done to fix this?

I want to use radix_trie to improve the memory efficiency of storing a large number of Unix file paths. Here's a sample of some of the input.

/usr/share/applications/cadence.desktop
/usr/share/applications/catarina.desktop
/usr/share/applications/catia.desktop
/usr/share/applications/claudia-launcher.desktop
/usr/share/applications/claudia.desktop
/usr/share/cadence
/usr/share/cadence/icons
/usr/share/cadence/icons/claudia-hicolor
/usr/share/cadence/icons/claudia-hicolor/16x16
/usr/share/cadence/icons/claudia-hicolor/16x16/apps
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/arctican_plugins.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/ardour.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/aria.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/arpage.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/azr3.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_BME700.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_aks.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_arp2600.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_axxe.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_bassmaker.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_bit99.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_bitone.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_cs80.png
/usr/share/cadence/icons/claudia-hicolor/16x16/apps/bristol_dx.png

This ought to be a near-ideal case for a Radix Trie because each path is near certain to share a prefix (a fairly long prefix, usually) with other paths. But that's not what I see when I run an experiment -- the Radix Trie requires 4x more memory to store the strings than a normal Vec. 3.73 gigabytes vs 925 megabytes.

Experiment code here: https://github.com/dralley/radix_trie_test

[dalley@thinkpad radix_trie_test]$ /usr/bin/time -v target/release/radix_test 
7223777
	Command being timed: "target/release/radix_test"
	User time (seconds): 6.24
	System time (seconds): 1.00
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:07.27
        ... snip ...
	Maximum resident set size (kbytes): 3734400
        ... snip ...
[dalley@thinkpad radix_trie_test]$ /usr/bin/time -v target/release/vec_test 
8568961
	Command being timed: "target/release/vec_test"
	User time (seconds): 0.97
	System time (seconds): 0.34
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.32
        ... snip ...
	Maximum resident set size (kbytes): 924672
	... snip ...

At the moment, Trie doesn't implement Clone trait. That makes it difficult to use within other structs.

the trait `std::clone::Clone` is not implemented for `radix_trie::Trie<std::string::String, std::string::String>`

still for my parsing tool, i need to know if the current string is a terminal one (i.e regardless of which character i add at the end , i'm sure i can't make any longer word)
with sequence trie, i implemented it on my side simply by doing

fn is_unique_match(words: &SequenceTrie<u8, ()>, value: &String) -> bool {

    if words.get(value.as_ref()).is_none() {
        return false;
    }

    words.get_node(value.as_ref()).map_or(
        false,
        |node| {
            let mut values = node.values();
            // we discard current value
            let _ = values.next();
            // and we check if there's a second
            match values.next() {
                Some(_) => false,
                None => true
            }

        }
    )

I guess looking to the internal of Radix tree, it's actually simpler as it just need to check that all the children are None (or child count is 0)

as it may be more specific, if you think it does not belong to the library i'm fine with it.

I was going over the insert method of the Trie struct and subsequently the implementation of iterative_insert. Finally I ended up on the with_key_value associated method of the TrieNode

It looks like this:

and the TrieNode struct itself:

Question

Why does the TrieNode store the KeyValue pair and not just the value? I would imagined the key fragments in the NibbleVec represent the key. Doesn't storing the full key defeat the purpose of the trie?

I could be missing something, hence this question 🙂

From Wikipedia:

• Find predecessor: Locates the largest string less than a given string, by lexicographic order.
• Find successor: Locates the smallest string greater than a given string, by lexicographic order.

At the moment we have more of a <= behaviour for get_ancestor, and get_raw_descendant is just.. weird.

Before we release to crates.io, we need to add some more tests for the subtrie stuff and the child iterators.

Very sure this is from my lack of understanding of a radix tree...but can someone tell me why the second test fails pls. Thanks in advance.

    #[test]
    fn test_example() {
        let mut t = Trie::new();
        t.insert("/1", "1");
        t.insert("/1/1.1", "1.1");
        t.insert("/1/1.2", "1.2");
        t.insert("/1/1.3", "1.3");
        // t.insert("/2", "2");
        let v: Vec<&str> = t
            .get_raw_ancestor("")
            .children()
            .map(|s| *s.value().unwrap())
            .collect();

        let mut iter = v.iter();
        assert!(*iter.next().unwrap() == "1");
        assert!(iter.next().is_none());
    }
    #[test]
    fn test_example_fails() {
        let mut t = Trie::new();
        t.insert("/1", "1");
        t.insert("/1/1.1", "1.1");
        t.insert("/1/1.2", "1.2");
        t.insert("/1/1.3", "1.3");
        t.insert("/2", "2"); // <- uncommented
        let v: Vec<&str> = t
            .get_raw_ancestor("")
            .children()
            .map(|s| *s.value().unwrap()) //<-panics
            .collect();

        let mut iter = v.iter();
        assert!(*iter.next().unwrap() == "1");
        assert!(*iter.next().unwrap() == "2");
        assert!(iter.next().is_none());
    }

I'm not sure if this falls outside of the normal usecase, but currently there doesn't seem to be a way to merge two tries, the way there is with maps via the extend trait.

I'm currently trying deserializing multiple toml files(containing snippets) to a single trie. Currently my options for updating an existing data structure are to store every key, value pair in separate files (which I've implemented) and add them one by one, or to store groups of key, value pairs in a single file and use extend to update the DS

I'm pretty new to rust but I would like to help out with this, if you could give me some idea of how and where to implement this, I would appreciate it