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.

toml [dependencies] radix_trie = "*"

Documentation

https://michaelsproul.github.io/rustradixtrie/

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.