Enum adapton::catalog::collections::trie::Trie

pub enum Trie<X> {
    Nil(BS),
    Leaf(BS, X),
    Bin(BS, Box<Trie<X>>, Box<Trie<X>>),
    Root(Meta, Box<Trie<X>>),
    Name(Name, Box<Trie<X>>),
    Art(Art<Trie<X>>),
}

Probablistically Balanced Trie Rough implementation of probabilistic tries from OOPSLA 2015 paper.

See also: Tries in OCaml

Variants

Nil(BS)

Leaf(BS, X)

Bin(BS, Box<Trie<X>>, Box<Trie<X>>)

Root(Meta, Box<Trie<X>>)

Name(Name, Box<Trie<X>>)

Art(Art<Trie<X>>)

Trait Implementations

impl<X: Clone> Clone for Trie<X>

fn clone(&self) -> Trie<X>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<X: Debug> Debug for Trie<X>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<X: Eq> Eq for Trie<X>

impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> Hash for Trie<X>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<X: PartialEq> PartialEq<Trie<X>> for Trie<X>

fn eq(&self, other: &Trie<X>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Trie<X>) -> bool

This method tests for !=.

impl<X> StructuralEq for Trie<X>

impl<X> StructuralPartialEq for Trie<X>

impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> TrieElim<X> for Trie<X>

fn find(trie: &Self, elt: &X, i: i64) -> Option<X>

fn is_empty(trie: &Self) -> bool

fn split_atomic(trie: Self) -> Self

fn elim<Res, NilC, LeafC, BinC, RootC, NameC>(
    trie: Self,
    nil: NilC,
    leaf: LeafC,
    bin: BinC,
    root: RootC,
    name: NameC
) -> Res where
    NilC: FnOnce(BS) -> Res,
    LeafC: FnOnce(BS, X) -> Res,
    BinC: FnOnce(BS, Self, Self) -> Res,
    RootC: FnOnce(Meta, Self) -> Res,
    NameC: FnOnce(Name, Self) -> Res, 

fn elim_arg<Arg, Res, NilC, LeafC, BinC, RootC, NameC>(
    trie: Self,
    arg: Arg,
    nil: NilC,
    leaf: LeafC,
    bin: BinC,
    root: RootC,
    name: NameC
) -> Res where
    NilC: FnOnce(BS, Arg) -> Res,
    LeafC: FnOnce(BS, X, Arg) -> Res,
    BinC: FnOnce(BS, Self, Self, Arg) -> Res,
    RootC: FnOnce(Meta, Self, Arg) -> Res,
    NameC: FnOnce(Name, Self, Arg) -> Res, 

fn elim_ref<Res, NilC, LeafC, BinC, RootC, NameC>(
    trie: &Self,
    nil: NilC,
    leaf: LeafC,
    bin: BinC,
    root: RootC,
    name: NameC
) -> Res where
    NilC: FnOnce(&BS) -> Res,
    LeafC: FnOnce(&BS, &X) -> Res,
    BinC: FnOnce(&BS, &Self, &Self) -> Res,
    RootC: FnOnce(&Meta, &Self) -> Res,
    NameC: FnOnce(&Name, &Self) -> Res, 

impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> TrieIntro<X> for Trie<X>

fn nil(bs: BS) -> Self

fn leaf(bs: BS, x: X) -> Self

fn bin(bs: BS, l: Self, r: Self) -> Self

fn root(meta: Meta, trie: Self) -> Self

fn name(nm: Name, trie: Self) -> Self

fn art(art: Art<Self>) -> Self

fn empty(meta: Meta) -> Self

fn singleton(meta: Meta, nm: Name, elt: X) -> Self

fn extend(nm: Name, trie: Self, elt: X) -> Self