Radix Trie Traversal Function

uber.rs

fn uber<K, V, Key, Value, Output,
             RootFn, NoChildFn, FullMatchFn, PartialMatchFn, FirstPrefixFn>
(
    trie: &mut Trie<K, V>,
    key: Key,
    value: Value,
    mut key_fragments: NibbleVec,
    root_fn: RootFn,
    no_child_fn: NoChildFn,
    full_match_fn: FullMatchFn,
    partial_match_fn: PartialMatchFn,
    first_prefix_fn: FirstPrefixFn,
    action_fn: fn(&mut Trie<K, V>, Output, usize) -> Output
) -> Output
where
    RootFn: Fn(&mut Trie<K, V>, Key, Value) -> Output,
    NoChildFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec, usize) -> Output,
    FullMatchFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec) -> Output,
    PartialMatchFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec, usize) -> Output,
    FirstPrefixFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec) -> Output
{
    use keys::{KeyMatch, match_keys};
    if key_fragments.len() == 0 {
        return root_fn(trie, key, value);
    }

    let bucket = key_fragments.get(0) as usize;

    let intermediate = match trie.children[bucket] {
        None => return no_child_fn(trie, key, value, key_fragments, bucket),
        Some(ref mut child) => {
            match match_keys(&key_fragments, &child.key) {
                KeyMatch::Full => full_match_fn(child, key, value, key_fragments),
                KeyMatch::Partial(idx) => partial_match_fn(child, key, value, key_fragments, idx),
                KeyMatch::FirstPrefix => first_prefix_fn(child, key, value, key_fragments),
                // Split the key and recurse.
                KeyMatch::SecondPrefix => {
                    let new_key = key_fragments.split(child.key.len());
                    uber(child, key, value, new_key, root_fn,
                         no_child_fn, full_match_fn, partial_match_fn, first_prefix_fn, action_fn)
                }
            }
        }
    };

    action_fn(trie, intermediate, bucket)
}

fn no_op<K, V>(trie: &mut Trie<K, V>, key: K, value: V) -> Option<V> where K: TrieKey {
    let encoding = NibbleVec::from_byte_vec(key.encode());

    fn action_fn<K, V>(_: &mut Trie<K, V>, x: Option<V>, _: usize) -> Option<V> { x }

    uber(
        trie, key, value, encoding,
        |_, _, _| None,
        |_, _, _, _, _| None,
        |_, _, _, _| None,
        |_, _, _, _, _| None,
        |_, _, _, _| None,
        action_fn
    )
}