✓ Uses Rust 2018 edition
|0.1.1||Feb 18, 2019|
|0.1.0||Feb 16, 2019|
#332 in Data structures
A work-in-progress implementation of an ART Tree.
Although the original ART paper only considers ASCII strings as keys, therefore
\0 as string terminator, the idea can be extended to UTF-8 by using
0xff as string terminator. Of course, you can use any terminator if you're
inserting raw bytes.
By default, you should use
for_utf8() if you're using
Terminator customization is why each lookup/insertion/deletion method returns a
Result<.., KeyContainsTerminator>; each method is also accompanied by a
equivalent unchecked version.
Although the original ART paper uses 4 different types of nodes (4, 16, 48 and 256 children), you may not want the node types used for sparser tries or the intermediate node types (for whatever reason). Each node type, other than the final trie node of 256 children, may be disabled by building without its feature flag enabled:
cargo build --features "node4" # only use the smallest node, fallback to Node256 cargo build --features "node4 node16" # disable Node48 cargo build --features "node16" # only use the intermediate node with SIMD search
SIMD should be enabled by default (if you system supports it). To explicitly
disable SIMD, build with the feature
let mut map = Trie::for_utf8(); map.insert(b"a", 0).unwrap(); map.insert(b"ac", 1).unwrap(); assert_eq!(map.get(b"a").unwrap(), Some(&0)); assert_eq!(map.get(b"ac").unwrap(), Some(&1)); assert_eq!(map.get(b"ab").unwrap(), None);
- Refactor insert/update child, removing duplication & extra find after insertion
- Path Compression