Trait differential_dataflow::trace::layers::Trie

pub trait Trie: Sized {
    type Item;
    type Cursor: Cursor<Self>;
    type MergeBuilder: MergeBuilder<Trie = Self>;
    type TupleBuilder: TupleBuilder<Trie = Self, Item = Self::Item>;
    fn keys(&self) -> usize;
    fn tuples(&self) -> usize;
    fn cursor_from(&self, lower: usize, upper: usize) -> Self::Cursor;

    fn cursor(&self) -> Self::Cursor { ... }
    fn merge(&self, other: &Self) -> Self { ... }
}

A collection of tuples, and types for building and enumerating them.

There are some implicit assumptions about the elements in trie-structured data, mostly that the items have some (key, val) structure. Perhaps we will nail these down better in the future and get a better name for the trait.

Associated Types

type Item

The type of item from which the type is constructed.

type Cursor: Cursor<Self>

The type of cursor used to navigate the type.

type MergeBuilder: MergeBuilder<Trie = Self>

The type used to merge instances of the type together.

type TupleBuilder: TupleBuilder<Trie = Self, Item = Self::Item>

The type used to assemble instances of the type from its Items.

Loading content...

Required methods

fn keys(&self) -> usize

The number of distinct keys, as distinct from the total number of tuples.

fn tuples(&self) -> usize

The total number of tuples in the collection.

fn cursor_from(&self, lower: usize, upper: usize) -> Self::Cursor

Returns a cursor over a range of data, commonly used by others to restrict navigation to sub-collections.

Loading content...

Provided methods

fn cursor(&self) -> Self::Cursor

Returns a cursor capable of navigating the collection.

fn merge(&self, other: &Self) -> Self

Merges two collections into a third.

Collections are allowed their own semantics for merging. For example, unordered collections simply collect values, whereas weighted collections accumulate weights and discard elements whose weights are zero.

Loading content...

Implementors

impl<K, L, O> Trie for OrderedLayer<K, L, O> where
    K: Ord + Clone,
    L: Trie,
    O: OrdOffset,
    <O as TryFrom<usize>>::Error: Debug,
    <O as TryInto<usize>>::Error: Debug, 

type Item = (K, L::Item)

type Cursor = OrderedCursor<L>

type MergeBuilder = OrderedBuilder<K, L::MergeBuilder, O>

type TupleBuilder = OrderedBuilder<K, L::TupleBuilder, O>

fn keys(&self) -> usize

fn tuples(&self) -> usize

fn cursor_from(&self, lower: usize, upper: usize) -> Self::Cursor

impl<K: Ord + Clone, R: Semigroup + Clone> Trie for OrderedLeaf<K, R>

type Item = (K, R)

type Cursor = OrderedLeafCursor

type MergeBuilder = OrderedLeafBuilder<K, R>

type TupleBuilder = OrderedLeafBuilder<K, R>

fn keys(&self) -> usize

fn tuples(&self) -> usize

fn cursor_from(&self, lower: usize, upper: usize) -> Self::Cursor

Loading content...