#data-structure #radix-tree

panoradix

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

19 releases

Uses old Rust 2015

0.6.8 Jan 31, 2020
0.6.6 Oct 5, 2019
0.6.5 Aug 20, 2017
0.6.3 Jul 1, 2017

#829 in Data structures

Download history 23/week @ 2022-12-01 24/week @ 2022-12-08 12/week @ 2022-12-15 22/week @ 2022-12-22 15/week @ 2022-12-29 8/week @ 2023-01-05 17/week @ 2023-01-12 31/week @ 2023-01-19 18/week @ 2023-01-26 15/week @ 2023-02-02 60/week @ 2023-02-09 74/week @ 2023-02-16 2/week @ 2023-02-23 2/week @ 2023-03-02 8/week @ 2023-03-09 42/week @ 2023-03-16

76 downloads per month

MIT license

425KB
814 lines

panoradix

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

Travis badge crates.io badge

Documentation

What's in this repo?

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!

No runtime deps