Struct ternary_tree::Tst

pub struct Tst<T> { /* fields omitted */ }

A Tst is a ternary tree structure which stores key value pairs and roughly behave like a map, but allowing more flexible ways to find and iterate over values.

See the module documentation for example usage and motivation.

Methods

impl<T> Tst<T>

pub fn new() -> Self

Constructs a new, empty Tst. The key is always a string slice and one needs only to provide a value type. The following code creates an empty tree which stores bool values

let mut map: Tst<bool> = Tst::new();

Although most of the time, type inference and some context allow to simply write

let mut map = Tst::new();

And the exact value type is guessed properly.

pub fn insert(&mut self, key: &str, value: T) -> Option<T>

Insertkey and value pairs in the tree, returning any value previously associated with key.

let mut map = Tst::new();
assert_eq!(map.len(), 0);

let old_value = map.insert("foo", "🍄🍄");
assert_eq!(old_value, None);
assert_eq!(map.len(), 1);

Because key represents a node path to value in the tree, an empty key is meaningless, and its associated value cannot be stored in the tree. In such a case, value is given back by insert :

assert_eq!(map.len(), 0);

let this_value = map.insert("", "woups");
assert_eq!(this_value, Some("woups"));
assert_eq!(map.len(), 0);

Another consequence of key representing a path in the tree is that key is not consumed on insert : key is only borrowed by the tree which needs to iterate over it, but does not need to store it. Thus once insertion is done, key is given back to the caller.

pub fn get(&self, key: &str) -> Option<&T>

Returns an immutable reference to the value associated with key, or None.

map.insert("foo", "🍄🍄");

let v = map.get("foo");
assert_eq!(v, Some(&"🍄🍄"));

pub fn get_mut(&mut self, key: &str) -> Option<&mut T>

Returns an mutable reference to the value associated with key, or None.

map.insert("foo", "🍄".to_string());

if let Some(v) = map.get_mut("foo") {
    v.push('🍄');
}

let v = map.get("foo");
assert_eq!(v, Some(&"🍄🍄".to_string()));

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

Removes the value associated with key from the tree, and returns it. Does nothing if no values is associated with key, and returns None.

map.insert("foo", "🍄🍄".to_string());

let v = map.remove("foo");
assert_eq!(v, Some("🍄🍄".to_string()));

let v = map.remove("foo");
assert_eq!(v, None);

pub fn len(&self) -> usize

Returns the number of values stored in the tree.

let mut map = Tst::new();
assert_eq!(map.len(), 0);

map.insert("foo", "🍄🍄");
assert_eq!(map.len(), 1);

pub fn stat(&self) -> Stats

Walks the tree, gathers various metrics about nodes, keys and values, and returns a Stats structure to sum it up.

let mut map = Tst::new();
assert_eq!(map.len(), 0);

map.insert("foo", "🍄🍄");
assert_eq!(map.len(), 1);

let stats = map.stat();
assert_eq!(stats.count.nodes, 3);

See Stats for a detailed description of available fields.

pub fn clear(&mut self)

Deletes every node and value stored in the tree.

let mut map = Tst::new();
assert_eq!(map.len(), 0);

map.insert("foo", "🍄🍄");
assert_eq!(map.len(), 1);

map.clear();
assert_eq!(map.len(), 0);

pub fn visit_values<C>(&self, callback: C) where
    C: FnMut(&T), 

Recursively walks the tree and calls callback closure on each immutable value. Values are found in alphabetical order of keys. See also the iter method which produces the same sequence of values in a non-recursive way.

let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];

let mut v = Vec::new();
map.visit_values(|s| v.push(s.clone()));
assert_eq!(v, ["🐟", "㵅", "🍄🍄"]);

pub fn visit_values_mut<C>(&mut self, callback: C) where
    C: FnMut(&mut T), 

Recursively walks the tree and calls callback closure on each mutable value. The same as visit_values, except the _mut version works on mutable values, and does not have an iterator counterpart.

pub fn visit_complete_values<C>(&self, key_prefix: &str, callback: C) where
    C: FnMut(&T), 

Recursively walks the tree and calls callback closure on each immutable value whose key begins with key_prefix. Values are found in alphabetical order of keys. See also the iter_complete method which produces the same sequence of values in a non-recursive way.

let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];

let mut v = Vec::new();
map.visit_complete_values("ba", |s| v.push(s.clone()));
assert_eq!(v, ["🐟", "㵅"]);

Some key is not a prefix of itself. In the previous example, visit_complete_values called with foo prefix would find no value :

let mut v = Vec::new();
map.visit_complete_values("foo", |s| v.push(s.clone()));
assert_eq!(v.is_empty(), true);

If key_prefix is empty, visit_complete_values behaves as visit_values, and all values are found.

pub fn visit_complete_values_mut<C>(&mut self, key_prefix: &str, callback: C) where
    C: FnMut(&mut T), 

Recursively walks the tree and calls callback closure on each mutable value whose key begins with key_prefix. The same as visit_complete_values, except the _mut version works on mutable values, and does not have an iterator counterpart.

pub fn visit_neighbor_values<C>(&self, key: &str, range: usize, callback: C) where
    C: FnMut(&T), 

Recursively walks the tree and calls callback closure on each immutable value whose key is close to key. A key is considered close to key within a Hamming distance of range from key. Values are found in alphabetical order of keys. See also the iter_neighbor method which produces the same sequence of values in a non-recursive way.

let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];

let mut v = Vec::new();
map.visit_neighbor_values("bar", 1, |s| v.push(s.clone()));
assert_eq!(v, ["🐟", "㵅"]);

An empty key is allowed, and with a distance of n, it will find all values whose key length is up to n. In the previous example visit_neighbor_values called with "" key and distance 3 would find all value whose key length is ≤ 3 :

let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];

let mut v = Vec::new();
map.visit_neighbor_values("", 3, |s| v.push(s.clone()));
assert_eq!(v, ["🐟", "㵅", "🍄"]);

pub fn visit_neighbor_values_mut<C>(
    &mut self,
    key: &str,
    range: usize,
    callback: C
) where
    C: FnMut(&mut T), 

Recursively walks the tree and calls callback closure on each mutable value whose key is close to key (Hamming distance of range). The same as visit_neighbor_values, except the _mut version works on mutable values, and does not have an iterator counterpart.

pub fn visit_crossword_values<C>(&self, pattern: &str, joker: char, callback: C) where
    C: FnMut(&T), 

Recursively walks the tree and calls callback closure on each immutable value whose key matches pattern. pattern is a string slice where each joker character stands for any character (would be a . with no repeater in a POSIX regexp). Values are found in alphabetical order of keys. See also the iter_crossword method which produces the same sequence of values in a non-recursive way.

let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];

let mut v = Vec::new();
map.visit_crossword_values("?a?", '?', |s| v.push(s.clone()));
assert_eq!(v, ["🐟", "㵅"]);

A pattern of n joker characters will find all values whose key length is exactly n :

let mut v = Vec::new();
let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];

map.visit_crossword_values("???", '?', |s| v.push(s.clone()));
assert_eq!(v, ["🐟", "㵅"]);

An empty pattern is meaningless, and does not find any value.

pub fn visit_crossword_values_mut<C>(
    &mut self,
    pattern: &str,
    joker: char,
    callback: C
) where
    C: FnMut(&mut T), 

Recursively walks the tree and calls callback closure on each mutable value whose key matches pattern with joker characters. The same as visit_crossword_values, except the _mut version works on mutable values, and does not have an iterator counterpart.

pub fn pretty_print(&self, writer: &mut dyn Write)

Dump the tree in writer using dot language of Graphviz tools. A checked box "☑" denotes a node which stores a value (it corresponds to the last character of a key). An empty box "☐" means that the node has no value. Mostly used for documentation and debugging purpose. See the module documentation for an example.

Important traits for TstIterator<'a, T>

impl<'a, T> Iterator for TstIterator<'a, T> type Item = &'a T;

pub fn iter(&self) -> TstIterator<T>

Create a double-ended iterator which successively returns all values of the tree. Values are immutable, and are found in alphabetical order of keys by next, and in the opposite order by next_back. Methods current_key and current_key_back regenerate the key associated with the last value returned by next and next_back. See also the visit_value_mut method which produces the same sequence of mutable values.

let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];

let mut it = map.iter();

let first_value = it.next();
let last_value = it.next_back();

let first_key = it.current_key();
let last_key = it.current_key_back();

assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
assert_eq!((last_key, last_value), ("foo".to_string(), Some(&"🍄🍄")));

Important traits for TstCompleteIterator<'a, T>

impl<'a, T> Iterator for TstCompleteIterator<'a, T> type Item = &'a T;

pub fn iter_complete(&self, prefix: &str) -> TstCompleteIterator<T>

Create a double-ended iterator which successively returns all values whose key begins with prefix. Values are immutable, and are found in alphabetical order of keys by next, and in the opposite order by next_back. Methods current_key and current_key_back regenerate the key associated with the last value returned by next and next_back. See also the visit_complete_value_mut method which produces the same sequence of mutable values.

let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];

let mut it = map.iter_complete("b");

let first_value = it.next();
let last_value = it.next_back();

let first_key = it.current_key();
let last_key = it.current_key_back();

assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
assert_eq!((last_key, last_value), ("baz".to_string(), Some(&"㵅")));

Important traits for TstNeighborIterator<'a, 'b, T>

impl<'a, 'b, T> Iterator for TstNeighborIterator<'a, 'b, T> type Item = &'a T;

pub fn iter_neighbor<'a, 'b>(
    &'a self,
    key: &'b str,
    range: usize
) -> TstNeighborIterator<'a, 'b, T>

Create a double-ended iterator which successively returns all values whose key is close to key. A key is considered close to key within a Hamming distance of range from key. An empty key is allowed, and with a range of n, it will find all values whose key length is up to n. Values are immutable, and are found in alphabetical order of keys by next, and in the opposite order by next_back. Methods current_key and current_key_back regenerate the key associated with the last value returned by next and next_back. See also the visit_neighbor_value_mut method which produces the same sequence of mutable values.

let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];

let mut it = map.iter_neighbor("bar", 1);

let first_value = it.next();
let last_value = it.next_back();

let first_key = it.current_key();
let last_key = it.current_key_back();

assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
assert_eq!((last_key, last_value), ("baz".to_string(), Some(&"㵅")));

Important traits for TstCrosswordIterator<'a, 'b, T>

impl<'a, 'b, T> Iterator for TstCrosswordIterator<'a, 'b, T> type Item = &'a T;

pub fn iter_crossword<'a, 'b>(
    &'a self,
    pattern: &'b str,
    joker: char
) -> TstCrosswordIterator<'a, 'b, T>

Create a double-ended iterator which successively returns all values whose key matches pattern. pattern is a string slice where each joker character stands for any character (would be a . with no repeater in a POSIX regexp). Values are immutable, and are found in alphabetical order of keys by next, and in the opposite order by next_back. Methods current_key and current_key_back regenerate the key associated with the last value returned by next and next_back.See also the visit_crossword_value_mut method which produces the same sequence of mutable values.

let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];

let mut it = map.iter_crossword("?a?", '?');

let first_value = it.next();
let last_value = it.next_back();

let first_key = it.current_key();
let last_key = it.current_key_back();

assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
assert_eq!((last_key, last_value), ("baz".to_string(), Some(&"㵅")));

Trait Implementations

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

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = TstIterator<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.