Struct TrieTree

pub struct TrieTree<T> { /* private fields */ }

A TrieTree that supports the following functions:

• Insert values
• Remove values
• Traversal values
• Prefix lookup values
• Debug Struct

Implementations

impl<T> TrieTree<T>

pub fn count(&self) -> usize

return values count

impl<T> TrieTree<T>

where T: Hash + Eq,

pub fn new() -> Self

new Self

• use Self::default()

pub fn clear(&mut self)

clear all values

Examples

let mut tree = TrieTree::new();
assert_eq!(tree.count(), 0);
assert!(tree.insert("abc".chars()));
assert_eq!(tree.count(), 1);
assert!(tree.query("abc".chars()));
tree.clear();
assert_eq!(tree.count(), 0);
assert!(! tree.query("abc".chars()));
assert!(tree.insert("abc".chars()));

pub fn insert(&mut self, iter: impl IntoIterator<Item = T>) -> bool

insert values.

• return whether the insertion values was successful

Examples

let mut tree = TrieTree::new();
assert_eq!(tree.count(), 0);
assert!(tree.insert("abc".chars()));
assert_eq!(tree.count(), 1);
assert!(! tree.insert("abc".chars()));
assert_eq!(tree.count(), 1);

pub fn query<Q>(&self, iter: impl IntoIterator<Item = Q>) -> bool

where Q: Borrow<T>,

Whether the query values is in the tree Result list examples

query	data	result
abcd	abcd	true
abc	abcd	false
bcd	abcd	false
abcde	abcd	false

Examples

let mut tree = TrieTree::new();
assert!(tree.insert("abcd".chars()));
assert!(tree.query("abcd".chars()));
assert!(! tree.query("abc".chars()));
assert!(! tree.query("bcd".chars()));
assert!(! tree.query("abcde".chars()));

pub fn query_nostop<Q>(&self, iter: impl IntoIterator<Item = Q>) -> Option<bool>

where Q: Borrow<T>,

Whether the query values head is in the tree Result list examples

query	data	result
	abcd	Some(false)
abc	abcd	Some(false)
abcd	abcd	Some(true)
bcd	abcd	None
abcde	abcd	None

Examples

let mut tree = TrieTree::new();
assert_eq!(tree.query_nostop("".chars()),       Some(false));
assert!(tree.insert("abcd".chars()));
assert_eq!(tree.query_nostop("abc".chars()),    Some(false));
assert_eq!(tree.query_nostop("abcd".chars()),   Some(true));
assert_eq!(tree.query_nostop("bcd".chars()),    None);
assert_eq!(tree.query_nostop("abcde".chars()),  None);

pub fn query_iter<Q>( &self, iter: impl IntoIterator<Item = Q>, ) -> Option<Iter<'_, T>>

where Q: Borrow<T>,

Get the Iterator matching the prefix
If there is no matching value, return None

Examples

let mut tree = TrieTree::new();
assert!(tree.insert("abc".chars()));
assert!(tree.insert("ace".chars()));
assert!(tree.insert("bee".chars()));
let mut res: Vec<_> = tree.query_iter("a".chars()).unwrap().collect();
res.sort();
assert_eq!(res, vec![vec![&'b', &'c'], vec![&'c', &'e']]);

pub fn remove<Q>(&mut self, iter: impl IntoIterator<Item = Q>) -> bool

where Q: Borrow<T>,

remove values and clean up overhanging branches

Examples

let mut tree = TrieTree::new();
assert_eq!(tree.count(), 0);
assert!(tree.insert("abc".chars()));
assert_eq!(tree.count(), 1);
assert!(tree.query("abc".chars()));
assert!(tree.remove("abc".chars()));
assert!(! tree.remove("abc".chars()));
assert!(! tree.query("abc".chars()));
assert_eq!(tree.count(), 0);

pub fn iter(&self) -> Iter<'_, T>

get iterator

Examples

let tree = TrieTree::from_iter(["abc".chars(), "bcd".chars()]);
let mut items: Vec<Vec<&char>> = tree.iter().collect();
items.sort();
assert_eq!(items[0], [&'a', &'b', &'c']);
assert_eq!(items[1], [&'b', &'c', &'d']);

pub fn shrink_to_fit(&mut self)

Shrink each HashMap in the tree

Examples

let mut tree = TrieTree::from_iter(["abc".chars(), "bcd".chars()]);
tree.shrink_to_fit();

Trait Implementations

impl<T> AsRef<TrieTree<T>> for TrieTree<T>

fn as_ref(&self) -> &Self

Converts this type into a shared reference of the (usually inferred) input type.

impl<T> Clone for TrieTree<T>

where T: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for TrieTree<T>

where T: Hash + Eq + Debug,

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

Formats the value using the given formatter.

impl<T> Default for TrieTree<T>

where T: Hash + Eq,

fn default() -> Self

Returns the “default value” for a type.

impl<T, I> Extend<I> for TrieTree<T>

where T: Hash + Eq, I: IntoIterator<Item = T>,

fn extend<IntoIter: IntoIterator<Item = I>>(&mut self, iter: IntoIter)

Examples

let mut tree = TrieTree::new();
tree.extend([&[1, 2, 3][..], &[1, 2][..]]);
assert!(tree.query(&[1, 2, 3]));
assert!(tree.query(&[1, 2]));
assert!(! tree.query(&[1]));

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, I> FromIterator<I> for TrieTree<T>

where T: Hash + Eq, I: IntoIterator<Item = T>,

fn from_iter<IntoIter: IntoIterator<Item = I>>(iter: IntoIter) -> Self

Examples

let tree: TrieTree<_> = [[1, 2, 3], [1, 3, 5]].into_iter().collect();
assert!(tree.query([1, 2, 3]));
assert!(tree.query([1, 3, 5]));

impl<'a, T> IntoIterator for &'a TrieTree<T>

where T: Hash + Eq,

type Item = Vec<&'a T>

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> PartialEq for TrieTree<T>

where T: Hash + Eq,

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

Tests for self and other values to be equal, and is used by ==.

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

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

impl<T: Hash + Eq> Eq for TrieTree<T>