Trait GeneralizedHashTrieNode

pub trait GeneralizedHashTrieNode: Default {
    type Schema: VariadicExt + Eq + Hash + Clone + SplitBySuffix<Self::SuffixSchema>;
    type KeyType: VariadicExt + Eq + Hash + Clone;
    type ValType: VariadicExt + Eq + Hash + Clone;
    type Storage: VariadicCollection<Schema = Self::Schema> + Default + IntoIterator<Item = Self::Schema>;
    type SuffixSchema: VariadicExt + Eq + Hash + Clone;
    type Head: Eq + Hash + Clone;

    const HEIGHT: usize;

    // Required methods
    fn new_from(input: impl IntoIterator<Item = Self::Schema>) -> Self;
    fn merge_node(&mut self, other: Self) -> bool;
    fn insert(&mut self, row: Self::Schema) -> bool;
    fn contains<'a>(
        &'a self,
        row: <Self::Schema as VariadicExt>::AsRefVar<'a>,
    ) -> bool;
    fn recursive_iter(
        &self,
    ) -> impl Iterator<Item = <Self::Schema as VariadicExt>::AsRefVar<'_>>;
    fn find_containing_leaf(
        &self,
        row: <Self::Schema as VariadicExt>::AsRefVar<'_>,
    ) -> Option<&GhtLeaf<Self::Schema, Self::ValType, Self::Storage>>;
    fn into_iter(self) -> Option<impl Iterator<Item = Self::Schema>>;
    fn drain(&mut self) -> Option<impl Iterator<Item = Self::Schema>>;

    // Provided method
    fn height(&self) -> usize { ... }
}

The GeneralizedHashTrieNode trait captures the properties of nodes in a Ght.

The Ght, defined by Wang/Willsey/Suciu, is a hash-based trie for storing tuples. It is parameterized by an ordered schema [VariadicExt] of the relation stored in the trie. It is a tree of GhtInner nodes, with GhtLeaf nodes at the leaves. The trie is keyed on a prefix of the schema Self::KeyType, and the remaining columns Self::ValType are stored in the leaf. All leaf nodes use the same [Self::Storage] type to store the data.

Required Associated Constants

const HEIGHT: usize

The height of this node in the GhT. Leaf = 0.

Required Associated Types

type Schema: VariadicExt + Eq + Hash + Clone + SplitBySuffix<Self::SuffixSchema>

Schema variadic: the schema of the relation stored in this trie.

type KeyType: VariadicExt + Eq + Hash + Clone

The prefix of columns in Self::Schema that the trie is keyed on

type ValType: VariadicExt + Eq + Hash + Clone

The suffix of columns in Self::Schema that are not part of the trie keys

type Storage: VariadicCollection<Schema = Self::Schema> + Default + IntoIterator<Item = Self::Schema>

The type that holds the data in the leaves

type SuffixSchema: VariadicExt + Eq + Hash + Clone

SuffixSchema variadic: the suffix of Self::Schema from this node of the trie downward. The first entry in this variadic is of type Self::Head.

type Head: Eq + Hash + Clone

The first field in Self::SuffixSchema, and the key for the next node in the trie.

Required Methods

fn new_from(input: impl IntoIterator<Item = Self::Schema>) -> Self

Create a new Ght from the iterator.

fn merge_node(&mut self, other: Self) -> bool

Merge a matching Ght node into this node

fn insert(&mut self, row: Self::Schema) -> bool

Inserts an item into the hash trie.

fn contains<'a>( &'a self, row: <Self::Schema as VariadicExt>::AsRefVar<'a>, ) -> bool

Returns true if the (entire) row is found below in the trie, false otherwise. See GhtGet::get to look just for “head” keys in this node

fn recursive_iter( &self, ) -> impl Iterator<Item = <Self::Schema as VariadicExt>::AsRefVar<'_>>

Iterate through (entire) rows stored in this HashTrie.

fn find_containing_leaf( &self, row: <Self::Schema as VariadicExt>::AsRefVar<'_>, ) -> Option<&GhtLeaf<Self::Schema, Self::ValType, Self::Storage>>

return the leaf below that contains this row, or None if not found.

fn into_iter(self) -> Option<impl Iterator<Item = Self::Schema>>

into_iter for leaf elements, or None for inner nodes

fn drain(&mut self) -> Option<impl Iterator<Item = Self::Schema>>

pull all the data out of this trie node but retain the reference

Provided Methods

fn height(&self) -> usize

Report the height of this node. This is the length of path from this node to a leaf - 1. E.g. if we have GhtInner<GhtInner<GhtLeaf…>> the height is 2 This is a static property of the type of this node, so simply invokes the static method.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<Head, Node> GeneralizedHashTrieNode for GhtInner<Head, Node>

where Head: 'static + Hash + Eq + Clone, Node: 'static + GeneralizedHashTrieNode, Node::Schema: SplitBySuffix<(Head, Node::SuffixSchema)>,

const HEIGHT: usize

type Schema = <Node as GeneralizedHashTrieNode>::Schema

type KeyType = <Node as GeneralizedHashTrieNode>::KeyType

type ValType = <Node as GeneralizedHashTrieNode>::ValType

type Storage = <Node as GeneralizedHashTrieNode>::Storage

type SuffixSchema = (Head, <Node as GeneralizedHashTrieNode>::SuffixSchema)

type Head = Head

impl<Schema, Storage> GeneralizedHashTrieNode for GhtLeaf<Schema, (), Storage>

where Schema: 'static + Eq + VariadicExt + Hash + Clone + PartialEqVariadic, Storage: VariadicCollection<Schema = Schema> + Default + IntoIterator<Item = Schema>,

const HEIGHT: usize = 0usize

type Schema = Schema

type SuffixSchema = ()

type ValType = ()

type KeyType = Schema

type Head = ()

type Storage = Storage

impl<Schema, ValHead, ValRest, Storage> GeneralizedHashTrieNode for GhtLeaf<Schema, (ValHead, ValRest), Storage>

where Schema: 'static + Eq + VariadicExt + Hash + Clone + SplitBySuffix<(ValHead, ValRest)> + PartialEqVariadic, ValHead: Clone + Eq + Hash, (ValHead, ValRest): Clone + Eq + Hash + PartialEqVariadic, <Schema as SplitBySuffix<(ValHead, ValRest)>>::Prefix: Eq + Hash + Clone, Storage: VariadicCollection<Schema = Schema> + Default + IntoIterator<Item = Schema>,

const HEIGHT: usize = 0usize

type Schema = Schema

type SuffixSchema = (ValHead, ValRest)

type ValType = (ValHead, ValRest)

type KeyType = <Schema as SplitBySuffix<(ValHead, ValRest)>>::Prefix

type Head = ValHead

type Storage = Storage