Struct mytrie::Trie

pub struct Trie(_);

A prefix tree

A trie is able to store char sequences and iterate over those with a common prefix.

It saves common prefixes only once, enabling fast iteration over all suffixes belonging to a prefix.

Create an empty trie and insert something:

use mytrie::Trie;

let mut trie = Trie::default();
trie.insert("Hello World!");
trie.remove("Hello World!").unwrap();

Implementations

impl Trie

pub fn from(content: impl IntoIterator<Item = impl AsRef<str>>) -> Self

Initialize a trie from a set of strings.

Example:

use mytrie::Trie;

let trie = Trie::from(["Hello", "world"]);

pub fn insert(&mut self, content: &str)

Adds a string to the trie

Example:

use mytrie::Trie;

let mut trie = Trie::default();
trie.insert("…");

pub fn iter_suffixes<'a>(
    &'a self,
    prefix: &str
) -> impl Iterator<Item = String> + 'a

Iterate all suffixes that follow this prefix

The order of iteration is arbitrary.

Example:

use mytrie::Trie;

let trie = Trie::from(["Hallo", "Hallöchen"]);
let mut suffixes: Vec<String> = trie.iter_suffixes("Hall").collect();

suffixes.sort();
assert_eq!(suffixes, ["o", "öchen"]);

pub fn iter_content<'a>(
    &'a self,
    prefix: &'a str
) -> impl Iterator<Item = String> + 'a

Iterate all strings in the trie with this prefix

The order of iteration is arbitrary.

Example:

use mytrie::Trie;

let trie = Trie::from(["Hallo", "Hallöchen", "Tschüs"]);
let mut content: Vec<String> = trie.iter_content("Hall").collect();

content.sort();
assert_eq!(content, ["Hallo", "Hallöchen"]);

pub fn remove(&mut self, content: &str) -> Option<()>

Remove a string from the trie

On successful removal, Some(()) is returned. If content was not present, None is returned.

Example:

use mytrie::Trie;

let mut trie = Trie::from(["Hallo", "Hallöchen"]);
trie.remove("Hallo").unwrap();

pub fn contains_prefix(&self, prefix: &str) -> bool

Checks if something with this prefix is in the trie

Example:

use mytrie::Trie;

let trie = Trie::from(["Hallo", "Hallöchen", "Tschüs", "Hallo Welt"]);
assert!(trie.contains_prefix("Hall"));
assert!(trie.contains_prefix("Hallo"));
assert!(!trie.contains_prefix("ABC"));
assert!(trie.contains_prefix(""));

pub fn contains(&self, content: &str) -> bool

Checks if the specified string was inserted into the trie Example:

use mytrie::Trie;

let trie = Trie::from(["Hallo"]);
assert!(!trie.contains("Hall"));
assert!(trie.contains("Hallo"));

pub fn is_empty(&self) -> bool

Returns true if the trie contains no content

Example:

use mytrie::Trie;

let mut trie = Trie::default();
assert!(trie.is_empty());
trie.insert("");
assert!(!trie.is_empty());

pub fn remove_suffixes(&mut self, prefix: &str) -> Option<Self>

Remove everything that follows this suffix

If a subtree was deleted, returns it. This will be another trie, containing all those removed strings minus the prefix.

An example for clarification:

use mytrie::Trie;

let mut trie = Trie::from(["Hallo", "Hallöchen", "Tschüs"]);
let removed: Trie = trie.remove_suffixes("Hal").unwrap();
let mut removed: Vec<String> = removed.iter_content("").collect();
removed.sort();

assert_eq!(removed, vec!["lo", "löchen"]);

Trait Implementations

impl Debug for Trie

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

Formats the value using the given formatter.

impl Default for Trie

fn default() -> Trie

Returns the “default value” for a type.

impl<S> FromIterator<S> for Triewhere
    S: AsRef<str>,

fn from_iter<T>(string_iter: T) -> Triewhere
    T: IntoIterator<Item = S>,

Creates a value from an iterator.