Struct tst::tst::TST

pub struct TST<V> {
    // some fields omitted
}

Symbol table with string keys, implemented using a ternary search trie (TST).

There is character on each node of the trie, value and links for children. Each node has 3 children: smaller (lt), equal (eq), larger (gt). It could be used as associative array for strings as keys. Also it provides extra features, like getting all keys, values with common prefix.

Examples

use tst::tst::TST;

let mut m = TST::new();

m.insert("first", 1);
m.insert("second", 2);
m.insert("firstthird", 3);
m.insert("firstsecond", 12);

for (key, value) in m.iter() {
    println!("{}: {}", key, value);
}
assert_eq!(Some(&1), m.get("first"));
assert_eq!(4, m.len());

// calculating longest prefix
assert_eq!("firstsecond", m.longest_prefix("firstsecondthird"));

// get values with common prefix
for (key, value) in m.prefix_iter("first") {
    println!("{}: {}", key, value);
}

Root struct for TST, which holds root and size.

Methods

impl<V> TST<V>

fn new() -> TST<V>

Constructs a new, empty TST<V>.

Examples

use tst::tst::TST;
let mut t: TST<i64> = TST::new();

fn len(&self) -> usize

Returns the number of elements in the container.

Examples

use tst::tst::TST;

let mut m = TST::new();
assert_eq!(0, m.len());
m.insert("ab", 2);
m.insert("x", 1);
assert_eq!(2, m.len());

fn insert(&mut self, key: &str, val: V) -> Option<V>

Inserts an element at key key with value val.

Panics

Panics if key is empty or more then 2000 symbols(because of reccursion).

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("SOmeWOrd", 2);
m.insert("SOmeOtherWOrd", 4);
assert_eq!(2, m.len());

fn entry(&mut self, key: &str) -> Entry<V>

Gets the given key's corresponding entry in the TST for in-place manipulation.

Examples

use tst::tst::TST;

let mut count: TST<usize> = TST::new();

for x in vec!["abc","bad","abd","cdddd","abc","bade"] {
    *count.entry(x).or_insert(0) += 1;
}

assert_eq!(2, count["abc"]);
assert_eq!(1, count["abd"]);

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

Removes a key from the TST, returning the value at the key if the key was previously in the TST.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("abc", 100);
assert_eq!(Some(100), m.remove("abc"));
assert_eq!(None, m.remove("abc"));

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

Returns a reference to the value corresponding to the key or None.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("first", 13);
assert_eq!(Some(&13), m.get("first"));
assert_eq!(None, m.get("second"));

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

Returns a mutable reference to the value corresponding to the key.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("first", 13);
if let Some(x) = m.get_mut("first") {
    *x = -13;
}
assert_eq!(-13, m["first"]);

fn contains_key(&self, key: &str) -> bool

Returns true if the TST contains a value for the specified key.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("abc", 1);
assert!(!m.contains_key("ab"));
assert!(m.contains_key("abc"))

fn is_empty(&self) -> bool

Returns true if the TST contains no elements.

Examples

use tst::tst::TST;

let mut m = TST::new();
assert!(m.is_empty());

m.insert("abc", 1);
assert!(!m.is_empty());

fn clear(&mut self)

Clears the TST.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("abc", 1);
m.insert("abd", 100);
m.clear();

assert!(m.is_empty());
assert_eq!(None, m.get("abc"));

fn wildcard_iter(&self, pat: &str) -> WildCardIter<V>

An iterator returning all nodes matching wildcard pattern. Iterator element type is (String, V)

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("a", 1);
m.insert("b", 2);
m.insert("c", 3);

for (k, v) in m.wildcard_iter(".") {
    println!("{} -> {}", k, v);
}

fn longest_prefix<'a>(&self, pref: &'a str) -> &'a str

Method returns longest prefix in the TST

Examples

use tst::tst::TST;
let mut m = TST::new();
m.insert("abc", 1);
m.insert("abcd", 1);
m.insert("abce", 1);
m.insert("abca", 1);
m.insert("zxd", 1);
m.insert("add", 1);
m.insert("abcdef", 1);

assert_eq!("abcd", m.longest_prefix("abcde"));

fn prefix_iter(&self, pref: &str) -> Iter<V>

Method returns iterator over all values with common prefix in the TST

Examples

use tst::tst::TST;
let mut m = TST::new();
m.insert("abc", 1);
m.insert("abcd", 1);
m.insert("abce", 1);
m.insert("abca", 1);
m.insert("zxd", 1);
m.insert("add", 1);
m.insert("abcdef", 1);

for (key, value) in m.prefix_iter("abc") {
    println!("{}: {}", key, value);
}

let (first_key, first_value) = m.iter().next().unwrap();
assert_eq!((first_key, *first_value), ("abc".to_string(), 1));

fn prefix_iter_mut(&mut self, pref: &str) -> IterMut<V>

Method returns mutable iterator over all values with common prefix in the TST

Examples

use tst::tst::TST;
let mut m = TST::new();
m.insert("abc", 1);
m.insert("abcd", 1);
m.insert("abce", 1);
m.insert("abca", 1);
m.insert("zxd", 1);
m.insert("add", 1);
m.insert("abcdef", 1);

for (key, value) in m.prefix_iter_mut("abc") {
    *value += 100;
}
assert_eq!(101, m["abc"]);
assert_eq!(101, m["abcdef"]);

fn iter(&self) -> Iter<V>

Gets an iterator over the entries of the TST.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("abc", 1);
m.insert("bbc", 2);
m.insert("cccda", 3);

for (key, value) in m.iter() {
    println!("{}: {}", key, value);
}

let (first_key, first_value) = m.iter().next().unwrap();
assert_eq!((first_key, *first_value), ("abc".to_string(), 1));

fn iter_mut(&mut self) -> IterMut<V>

Gets a mutable iterator over the entries of the TST.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("a", 1);
m.insert("b", 2);
m.insert("c", 3);

for (key, value) in m.iter_mut() {
    if key != "a" {
        *value += 10;
    }
}
assert_eq!(1, m["a"]);
assert_eq!(12, m["b"]);

fn keys(&self) -> KeysIter<V>

An iterator visiting all keys in arbitrary order. Iterator element type is String

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("a", 1);
m.insert("b", 2);
m.insert("c", 3);

for key in m.keys() {
    println!("{}", key);
}

fn values(&self) -> ValuesIter<V>

An iterator visiting all values in arbitrary order. Iterator element type is &V

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("a", 1);
m.insert("b", 2);
m.insert("c", 3);

for value in m.values() {
    println!("{}", value);
}

Trait Implementations

impl<V: Eq> Eq for TST<V>

impl<V: PartialEq> PartialEq for TST<V>

fn eq(&self, __arg_0: &TST<V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, __arg_0: &TST<V>) -> bool

This method tests for !=.

impl<V: Clone> Clone for TST<V>

fn clone(&self) -> TST<V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<V> IntoIterator for TST<V>

type Item = (String, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<V>

Creates a consuming iterator, that is, one that moves each key-value pair out of the TST in arbitrary order. The TST cannot be used after calling this.

Examples

use tst::tst::TST;

let mut m = TST::new();
m.insert("a", 1);
m.insert("b", 2);
m.insert("c", 3);

let vec: Vec<(String, isize)> = m.into_iter().collect();

impl<'x, V> FromIterator<(&'x str, V)> for TST<V>

fn from_iter<I: IntoIterator<Item=(&'x str, V)>>(iter: I) -> TST<V>

Creates a value from an iterator.

impl<'x, V> Extend<(&'x str, V)> for TST<V>

fn extend<I: IntoIterator<Item=(&'x str, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl<'x, V> Index<&'x str> for TST<V>

type Output = V

The returned type after indexing

fn index(&self, idx: &str) -> &V

The method for the indexing (Foo[Bar]) operation

impl<'x, V> IndexMut<&'x str> for TST<V>

fn index_mut(&mut self, idx: &str) -> &mut V

The method for the indexing (Foo[Bar]) operation

impl<V: Debug> Debug for TST<V>

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

Formats the value using the given formatter.