2 unstable releases

0.2.0 Dec 27, 2021
0.1.0 Sep 27, 2021

#1009 in Data structures

MIT license

98KB
2.5K SLoC

Crate API

The Adaptive Radix Tree

The radix tree based on The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases paper.

use art_tree::ByteString;
use art_tree::KeyBuilder;
use art_tree::Art;

pub fn art_example() {
    let mut art = Art::<u16, u16>::new();
    for i in 0..u8::MAX as u16 {
        assert!(art.insert(i, i), "{}", i);
        assert!(matches!(art.get(&i), Some(val) if val == &i));
    }
    for i in 0..u8::MAX as u16 {
        assert!(matches!(art.remove(&i), Some(val) if val == i));
    }
    let mut art = Art::<ByteString, u16>::new();
    for i in 0..u8::MAX as u16 {
        let key = KeyBuilder::new().append(i).append(ByteString::new("abc".to_string().as_bytes())).build();
        art.upsert(key.clone(), i + 1);
        assert!(matches!(art.get(&key), Some(val) if val == &(i + 1)));
    }
    let from_key = KeyBuilder::new().append(16u16).append(ByteString::new("abc".to_string().as_bytes())).build();
    let until_key = KeyBuilder::new().append(20u16).append(ByteString::new("abc".to_string().as_bytes())).build();
    assert_eq!(art.range(from_key..=until_key).count(), 5);
    assert_eq!(art.iter().count(), u8::MAX as usize);   
}

No runtime deps