Struct rtrie::TernaryTrie

pub struct TernaryTrie<P = u32> where
    P: Priority,  { /* fields omitted */ }

A randomized ternary search trie.

This is a variant of the ternary search tree that uses randomization to ensure that the tree is (typically) balanced. See: Randomized Ternary Search Tries, Nicolai Diethelm:

https://arxiv.org/abs/1606.04042

Methods

impl<P> TernaryTrie<P> where
    P: Priority, 

fn new_with_prio<R>(rng: R) -> Self where
    R: Rng + 'static, 

Construct a trie. This constructor has a priority type parameter, This allows the user to specify the type of the priority. E.g. for smaller trees a narrow unsigned could suffice and saves memory.

fn contains<S>(&self, s: S) -> bool where
    S: IntoIterator<Item = char>, 

Returns true when a string is in the trie, or false otherwise.

Since a ternary trie cannot contain the empty string, this method will always return false for an empty string.

fn node_count(&self) -> usize

Returns the number of nodes in the trie.

fn insert<S>(&mut self, s: S) where
    S: IntoIterator<Item = char>, 

Insert a string into the trie.

Since a ternary tree cannot store empty strings, the insert method will panic when inserting an empty string.

fn iter<'a>(&'a self) -> Iter<'a, P>

Return an iterator over the strings in the trie.

fn prefix_iter<'a, S>(&'a self, prefix: S) -> Iter<'a, P> where
    S: IntoIterator<Item = char>, 

Iterate over the strings starting with the given prefix.

fn remove<S>(&mut self, s: S) where
    S: IntoIterator<Item = char>, 

Remove a string from the trie.

Since a ternary tree cannot store empty strings, the remove method will panic when attempting to insert an empty string.

impl TernaryTrie<u32>

fn new<R>(rng: R) -> Self where
    R: Rng + 'static, 

Construct a trie. The random number generator will be used to generate string priorities.

Trait Implementations

impl<'a, P> IntoIterator for &'a TernaryTrie<P> where
    P: Priority, 

type Item = String

The type of the elements being iterated over.

type IntoIter = Iter<'a, P>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.