Rust Radix Trie
This is a Radix Trie implementation in Rust, building on the lessons learnt from
TrieMap and Sequence Trie.
You can read about my experience implementing this data structure here.
While I'm confident about the structure of the code, it hasn't been heavily tested and there may be some bugs. If you'd like to use this library please contribute some QuickCheck tests :)
Features
- Compressed nodes. Common key prefixes are stored only once.
- Trie-specific methods to look-up closest ancestors and descendants.
- Key Generic. Any type that can be serialised as a vector of bytes can be used as a key.
- Safe - no unsafe code.
Usage
Available on Crates.io as radix_trie.
[]
= "*"
Documentation
https://michaelsproul.github.io/rust_radix_trie/
To Do
- QuickCheck tests.
- Child iterator (easy).
- Optimise (make a
NibbleSlice, see paper). - Implement the Entry API?
License
MIT License. Copyright (c) Michael Sproul 2015.