columnar/adts/
art.rs

1//! Adaptive Radix Trees (https://db.in.tum.de/~leis/papers/ART.pdf).
2//!
3//! This ADT represents an unordered collection of byte sequences as a tree.
4//! Like a trie, the paths down the tree correspond to byte sequences, and 
5//! the membership of a byte sequence is determined by the a viable path.
6use alloc::boxed::Box;
7
8/// An ART node exists in the context of a sequence of bytes, and indicates
9/// the possible options based on the next byte in the sequence.
10pub enum ArtNode {
11    /// Some of the bytes continue to further nodes, but many do not.
12    Some(Box<[(u8, ArtNode)]>),
13    /// Many of the bytes continue to further nodes, although some may not.
14    /// If a node is `None`, it didn't actually go anywhere.
15    /// The representation exists to be more economical than the `Some` variant.
16    /// This is especially true if the associated `ArtNode` size is small, which
17    /// it is not in this case, but will be once we flatten it.
18    Many(Box<[ArtNode; 256]>),
19    /// Indicates that there are no branching points for the next few bytes,
20    /// after which the next node is provided.
21    Path(Box<[u8]>, Box<ArtNode>),
22    /// Nothing to see here.
23    None,
24}
25
26/// A mock-up of what you would store for each `ArtNode` above, when columnar.
27pub enum ArtIdx {
28    Some(usize),
29    Many(usize),
30    Path(usize),
31    None,
32}
33
34
35pub struct ArtNodes {
36    // pub inner: Results<Results< , >, Results< , >>,
37}
columnar/adts/art.rs

columnar/adts/
art.rs
