Trait lattices::ght::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 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 Associated Constants

const HEIGHT: usize

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

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.

Object Safety

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)>,

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

const HEIGHT: usize = _

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

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

type Schema = Schema

type SuffixSchema = ()

type ValType = ()

type KeyType = Schema

type Head = ()

type Storage = Storage

const HEIGHT: usize = 0usize

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>,

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

const HEIGHT: usize = 0usize