Trait lattices::ght::colt::ColtForestNode
source · pub trait ColtForestNode: GeneralizedHashTrieNode {
type Force: GeneralizedHashTrieNode;
// Required methods
fn force(self) -> Option<Self::Force>;
fn force_drain(&mut self) -> Option<Self::Force>;
}Expand description
Data structure design for our COLT is unique.
In the paper, the COLT is an unbalanced trie that “grows upward” from leaves lazily
on access via the force method.
Unfortunately, unbalanced tries break our types: a node’s type to be defined via the
type of its children, recursively – meaning all paths need to be the same type (and length)!
To work around this, our COLT is a variadic list GHTs (a forest) of increasing height,
starting with a trie of height 0 and continuing until a trie of height |key| - 1.
Our force method does not add a node above a leaf L as in the paper. Instead
it takes L from the current trie and merges it into the next trie to the right which is 1 taller.
The following trait provides the behavior we need from the nodes in a COLT forest. Every
ColtForestNode is a GeneralizedHashTrieNode with some extra methods.
Required Associated Types§
sourcetype Force: GeneralizedHashTrieNode
type Force: GeneralizedHashTrieNode
result of forceing a node
Required Methods§
sourcefn force(self) -> Option<Self::Force>
fn force(self) -> Option<Self::Force>
Force the generation of a parent node, as in the Wang/Willsey/Suciu COLT structure, to be merged into the next trie to the right.
sourcefn force_drain(&mut self) -> Option<Self::Force>
fn force_drain(&mut self) -> Option<Self::Force>
Force the generation of a parent node but retain ref to this node