Struct TSTMap 

pub struct TSTMap<Value> { /* private fields */ }

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.

Implementations

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

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

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

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

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

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

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

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

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

fn drop(&mut self)

Executes the destructor for this type.

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.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

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> 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<Value> IntoIterator for TSTMap<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();

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?

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

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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

impl<Value> StructuralPartialEq for TSTMap<Value>