jmcomets/panoradix

A generic map and a set, both backed by a Radix tree.

panoradix

My take on implementing a Radix tree, for usage when large data mappings with slices as indices.

Documentation

What's in this repo?

• RadixMap, a key-value map.
• RadixSet, a set of keys.

Both are backed by a Radix tree.

Any slice of elements that are Ord + Eq + Clone can be used as keys, as well as str that are taken as byte slices. Any lookups are done using a &[T] and iteration will yield an owned Vec<T> each time (for str it will yield String items).

Further extension of keys is possible but not recommended since the keys are arguably always a [T]. If you really want to do this, have a look at the ExtensibleKey trait.

Examples

Insert / Lookup

let mut map: RadixMap<str, i32> = RadixMap::new();
map.insert("a", 0);
map.insert("ac", 1);

assert_eq!(map.get("a"), Some(&0));
assert_eq!(map.get("ac"), Some(&1));
assert_eq!(map.get("ab"), None);

Removal

let v = vec!["foo", "bar", "baz"];
let mut set: RadixSet<str> = RadixSet::from_iter(v);

set.remove("bar");
assert!(!set.contains("bar"));
assert!(set.contains("baz"));

Completion

let v = vec!["foo", "bar", "baz"];
let set: RadixSet<str> = RadixSet::from_iter(v);

assert_eq!(set.find("ba").collect::<Vec<_>>(), vec!["bar", "baz"]);

Contributing

I try to maintain a list of things that need to be worked on over here. Issues / PRs are always welcome!

panoradix's Issues

`len` method for RadixSet and RadixMap

RadixSet and RadixMap have no len methods. The Rust standard library's HashSet and HashMap have len methods, so it is probably a reasonable interface.

It looks like your radix tree implementation uses trees from tree.rs, which don't keep track of their length, so you would have to do a tree traversal (O(n)) to determine the length of a tree. If len would indeed be O(n), it could be called something else, like count_len() to indicate that it is not O(1)

Alternatively, tree could be declared as

pub struct Tree<K, V> {
    node: Node<K, V>,
    len: usize,
}

instead of the current pub type Tree<K, V> = Node<K, V>. Of course, this would require updating len on insert and remove. This would be similar to the standard library's Vec, declared as

pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

I'm not really sure if these are reasonable solutions, but it struck me as strange that RadixSet doesn't have a len method when I first tried to use it.

just to be clear, this is not a blocking issue, as

let mut set = RadixSet::new();
...
let len = set.iter().count();

works for now

Broken Links in Docs.rs

on https://docs.rs/panoradix/0.6.6/panoradix/trait.RadixKey.html,
the sentence A key that can be inserted in both RadixSet and RadixMap. contains two broken links to RadixSet and RadixMap.

Unfortunately, linking is currently only supported in nightly https://doc.rust-lang.org/rustdoc/unstable-features.html rust-lang/rfcs#1946