Struct Trie 

pub struct Trie { /* private fields */ }

Implementations

impl Trie

pub fn new() -> Self

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

Insert a word into the trie, with no corresponding data.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word1");
assert_eq!(vec![String::from("word1")], trie.get_all());

pub fn remove(&mut self, word: &str)

Removes a word from the trie. If the word is a prefix to some word, some word isn’t removed from the trie.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word");
trie.insert("wording");

trie.remove("word");
assert_eq!(vec![String::from("wording")], trie.get("word").unwrap());

trie.remove("wording");
assert_eq!(Vec::<String>::new(), trie.get_all());

pub fn remove_prefix(&mut self, prefix: &str)

Removes every word that begins with ‘prefix’. Not including the word ‘prefix’ if it’s present.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("eat");
trie.insert("eats");
trie.insert("eating");
trie.insert("eatings");
trie.insert("ea");

trie.remove_prefix("ea");

assert_eq!(vec![String::from("ea")], trie.get_all());

pub fn get(&self, query: &str) -> Option<Vec<String>>

Returns an option enum with a vector of owned strings representing all found words that begin with ‘query’. If the word ‘query’ doesn’t exist, None is returned.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word1");
trie.insert("word2");

let all_correct_words = vec![String::from("word1"), String::from("word2")];
let mut found_words = trie.get("word").unwrap();
found_words.sort();
assert_eq!(all_correct_words, found_words);

pub fn get_longest(&self) -> Vec<String>

Returns the vector of longest words found in the trie.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("shortwrd");
trie.insert("verylongword");
trie.insert("somelongword");

let longest_words = vec![String::from("somelongword"), String::from("verylongword")];
let mut found_words = trie.get_longest();
found_words.sort();
assert_eq!(longest_words, found_words);

pub fn get_shortest(&self) -> Vec<String>

Returns the vector of shortest words found in the trie.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("shortwrd");
trie.insert("rlyshort");
trie.insert("verylongword");

let shortest_word = vec![String::from("rlyshort"), String::from("shortwrd")];
let mut found_words = trie.get_shortest();
found_words.sort();
assert_eq!(shortest_word, found_words);

pub fn len(&self) -> usize

Returns the number of words in the trie.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word1");
trie.insert("word2");
trie.insert("word3");
trie.insert("word4");
assert_eq!(4, trie.len());

trie.remove("word1");
assert_eq!(3, trie.len());

trie.remove_prefix("w");
assert_eq!(0, trie.len());

pub fn len_prefix(&self, prefix: &str) -> usize

Returns the number of words that start with ‘prefix’. If the sequence ‘prefix’ is not found, None is returned.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word1");
trie.insert("word2");
trie.insert("word3");
trie.insert("word4");
trie.insert("word");
assert_eq!(4, trie.len_prefix("word"));

pub fn get_all(&self) -> Vec<String>

Returns an option enum with a vector of owned strings representing all words in the trie. Order is not guaranteed.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word1");
trie.insert("word2");
trie.insert("word3");
trie.insert("word4");
trie.insert("word5");

let all_words = vec![
    String::from("word1"), String::from("word2"), String::from("word3"),
    String::from("word4"), String::from("word5")
];

let mut found_words = trie.get_all();
found_words.sort();

assert_eq!(all_words, found_words);

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

Returns true if the trie contains ‘query’ as a word.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word");
assert!(trie.contains("word"));
assert!(!trie.contains("notfound"));

pub fn is_empty(&self) -> bool

Returns true if no words are in the trie.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word");
trie.remove("word");

assert!(trie.is_empty());

pub fn clear(&mut self)

Removes all words from the trie.

Examples

use basic_trie::Trie;
let mut trie = Trie::new();

trie.insert("word1");
trie.insert("word2");
trie.insert("word3");
trie.insert("word4");

trie.clear();
assert!(trie.is_empty());
assert_eq!(0, trie.len());

Trait Implementations

impl Add for Trie

fn add(self, rhs: Self) -> Self::Output

Operation + merges two tries, leaving out duplicate words. The smaller trie is always added to the larger one for efficiency.

Examples

use basic_trie::Trie;
let mut trie_1 = Trie::new();
trie_1.insert("word1");
trie_1.insert("word2");
trie_1.insert("word");

let mut trie_2 = Trie::new();
trie_2.insert("word3");
trie_2.insert("word");

let mut correct = Trie::new();
correct.insert("word");
correct.insert("word1");
correct.insert("word2");
correct.insert("word3");

let trie_3 = trie_1 + trie_2;

assert_eq!(trie_3, correct);

type Output = Trie

The resulting type after applying the + operator.

impl AddAssign for Trie

fn add_assign(&mut self, rhs: Self)

Operation += merges two tries, leaving out duplicate words.

Examples

use basic_trie::Trie;
let mut trie_1 = Trie::new();
trie_1.insert("word1");
trie_1.insert("word2");
trie_1.insert("word");

let mut trie_2 = Trie::new();
trie_2.insert("word3");
trie_2.insert("word");

let mut correct = Trie::new();
correct.insert("word");
correct.insert("word1");
correct.insert("word2");
correct.insert("word3");

trie_1 += trie_2;

assert_eq!(trie_1, correct);

impl Clone for Trie

fn clone(&self) -> Trie

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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 PartialEq for Trie

fn eq(&self, other: &Self) -> bool

Examples

use basic_trie::Trie;
let mut trie_1 = Trie::new();
trie_1.insert("test");

let mut trie_2 = Trie::new();
trie_2.insert("test");

assert_eq!(trie_1, trie_2);

trie_2.insert("test2");

assert_ne!(trie_1, trie_2);

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.