Struct tst::TSTMap

pub struct TSTMap<Value> {
    // some fields omitted
}

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

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::TSTMap;

let mut m = TSTMap::new();

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

// iterate
for (key, value) in m.iter() {
    println!("{}: {}", key, value);
}
assert_eq!(Some(&1), m.get("first"));
assert_eq!(5, 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);
}

// get sum by wildcard iterator
assert_eq!(-12, m.wildcard_iter(".irst").fold(0, |sum, (_, val)| sum + val));

Root struct for TSTMap, which holds root and size.

Methods

impl<Value> TSTMap<Value>

fn new() -> Self

Constructs a new, empty TSTMap<Value>.

Examples

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

fn len(&self) -> usize

Returns the number of elements in the container.

Examples

use tst::TSTMap;

let mut m = TSTMap::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, value: Value) -> Option<Value>

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::TSTMap;

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

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

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

Examples

use tst::TSTMap;

let mut count: TSTMap<usize> = TSTMap::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<Value>

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

Examples

use tst::TSTMap;

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

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

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

Examples

use tst::TSTMap;

let mut m = TSTMap::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 Value>

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

Examples

use tst::TSTMap;

let mut m = TSTMap::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 TSTMap contains a value for the specified key.

Examples

use tst::TSTMap;

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

fn is_empty(&self) -> bool

Returns true if the TSTMap contains no elements.

Examples

use tst::TSTMap;

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

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

fn clear(&mut self)

Clears the TSTMap.

Examples

use tst::TSTMap;

let mut m = TSTMap::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<Value>

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

Examples

use tst::TSTMap;

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

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

fn wildcard_iter_mut(&mut self, pat: &str) -> WildCardIterMut<Value>

An mutable iterator returning all nodes matching wildcard pattern.

Examples

use tst::TSTMap;

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

for (k, v) in m.wildcard_iter_mut(".") {
    *v += 10;
}
assert_eq!(11, m["a"]);
assert_eq!(12, m["b"]);
assert_eq!(13, m["c"]);

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

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

Examples

use tst::TSTMap;
let mut m = TSTMap::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<Value>

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

Examples

use tst::TSTMap;
let mut m = TSTMap::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<Value>

Gets an iterator over the entries of the TSTMap.

Examples

use tst::TSTMap;

let mut m = TSTMap::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<Value>

Gets a mutable iterator over the entries of the TSTMap.

Examples

use tst::TSTMap;

let mut m = TSTMap::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<Value>

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

Examples

use tst::TSTMap;

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

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

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

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

Examples

use tst::TSTMap;

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

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

impl<'x, Value: 'x> TSTMap<Value>

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

Method returns longest prefix in the TSTMap

Examples

use tst::TSTMap;
let mut m = TSTMap::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"));

Trait Implementations

impl<Value: Eq> Eq for TSTMap<Value>

impl<Value: PartialEq> PartialEq for TSTMap<Value>

fn eq(&self, __arg_0: &TSTMap<Value>) -> bool

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

fn ne(&self, __arg_0: &TSTMap<Value>) -> bool

This method tests for !=.

impl<Value: Clone> Clone for TSTMap<Value>

fn clone(&self) -> TSTMap<Value>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Value> IntoIterator for TSTMap<Value>

type Item = (String, Value)

The type of the elements being iterated over.

type IntoIter = IntoIter<Value>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<Value>

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

Examples

use tst::TSTMap;

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

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

impl<'x, Value> FromIterator<(&'x str, Value)> for TSTMap<Value>

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

Creates a value from an iterator.

impl<'x, Value> Extend<(&'x str, Value)> for TSTMap<Value>

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

Extends a collection with the contents of an iterator.

impl<'x, Value> Index<&'x str> for TSTMap<Value>

type Output = Value

The returned type after indexing

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

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

impl<'x, Value> IndexMut<&'x str> for TSTMap<Value>

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

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

impl<Value> Drop for TSTMap<Value>

fn drop(&mut self)

A method called when the value goes out of scope.

impl<Value: Debug> Debug for TSTMap<Value>

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

Formats the value using the given formatter.