Struct tst::TSTMap

pub struct TSTMap<Value> { /* 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>

pub fn new() -> Self

Constructs a new, empty TSTMap<Value>.

Examples

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

pub 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());

pub 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());

pub 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"]);

pub 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"));

pub 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"));

pub 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"]);

pub 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"))

pub 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());

pub 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"));

Important traits for WildCardIter<'x, Value>

impl<'x, Value> Iterator for WildCardIter<'x, Value> type Item = (String, &'x Value);

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

An iterator returning all nodes matching wildcard pattern pat. 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);
}

Important traits for WildCardIterMut<'x, Value>

impl<'x, Value> Iterator for WildCardIterMut<'x, Value> type Item = (String, &'x mut Value);

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

An mutable iterator returning all nodes matching wildcard pattern pat.

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"]);

Important traits for Iter<'x, Value>

impl<'x, Value> Iterator for Iter<'x, Value> type Item = (String, &'x Value);

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

Method returns iterator over all values with common prefix pref 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);
}

Important traits for IterMut<'x, Value>

impl<'x, Value> Iterator for IterMut<'x, Value> type Item = (String, &'x mut Value);

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

Method returns mutable iterator over all values with common prefix pref 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"]);

Important traits for Iter<'x, Value>

impl<'x, Value> Iterator for Iter<'x, Value> type Item = (String, &'x Value);

pub 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));

Important traits for IterMut<'x, Value>

impl<'x, Value> Iterator for IterMut<'x, Value> type Item = (String, &'x mut Value);

pub 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"]);

Important traits for KeysIter<'x, Value>

impl<'x, Value: 'x> Iterator for KeysIter<'x, Value> type Item = String;

pub 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);
}

Important traits for ValuesIter<'x, Value>

impl<'x, Value: 'x> Iterator for ValuesIter<'x, Value> type Item = &'x Value;

pub 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>

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

Method returns longest prefix pref 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> 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?

Important traits for IntoIter<Value>

impl<Value> Iterator for IntoIter<Value> type Item = (String, Value);

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<Value: Eq> Eq for TSTMap<Value>

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<'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<Value> Drop for TSTMap<Value>

fn drop(&mut self)

Executes the destructor for this type.

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

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

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

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

This method tests for !=.

impl<Value> Default for TSTMap<Value>

fn default() -> Self

Constructs a new, empty TSTMap<Value>.

Examples

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

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

type Output = Value

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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

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

Performs the mutable indexing (container[index]) operation.

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<Value: Debug> Debug for TSTMap<Value>

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

Formats the value using the given formatter.