[−][src]Struct ternary_tree::Tst
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>
[src]
pub fn new() -> Self
[src]
Create 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 properly guessed.
pub fn insert(&mut self, key: &str, value: T) -> Option<T>
[src]
Inserts key
and value
pair 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 by 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>
[src]
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>
[src]
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>
[src]
Removes the value associated with key
from the tree, and returns it. Does nothing if no value 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
[src]
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
[src]
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)
[src]
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),
[src]
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),
[src]
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),
[src]
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 stored in the tree are found.
pub fn visit_complete_values_mut<C>(&mut self, key_prefix: &str, callback: C) where
C: FnMut(&mut T),
[src]
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),
[src]
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 range
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 range 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),
[src]
&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),
[src]
C: FnMut(&T),
Recursively walks the tree and calls callback
closure on each immutable value whose key matches
pattern
. The pattern
is a string slice where each joker
character stands for any character. 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),
[src]
&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)
[src]
Dump the tree in writer
using the 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>pub fn iter(&self) -> TstIterator<T>
[src]
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
or 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>pub fn iter_complete(&self, prefix: &str) -> TstCompleteIterator<T>
[src]
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
or 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>pub fn iter_neighbor<'a, 'b>(
&'a self,
key: &'b str,
range: usize
) -> TstNeighborIterator<'a, 'b, T>
[src]
&'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
or 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>pub fn iter_crossword<'a, 'b>(
&'a self,
pattern: &'b str,
joker: char
) -> TstCrosswordIterator<'a, 'b, T>
[src]
&'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
. The pattern
is a string slice where each
joker
character stands for any character. A pattern
of n joker
characters will find all values
whose key length is exactly 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
or 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>
[src]
Auto Trait Implementations
impl<T> RefUnwindSafe for Tst<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T> Send for Tst<T> where
T: Send,
T: Send,
impl<T> Sync for Tst<T> where
T: Sync,
T: Sync,
impl<T> Unpin for Tst<T>
impl<T> UnwindSafe for Tst<T> where
T: UnwindSafe,
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,