Struct Trie

Source

pub struct Trie { /* private fields */ }

Expand description

A standard trie form that often provides the fastest queries.

Implementations§

Source §

impl Trie

Source

pub fn from_keys<I, K>(keys: I) -> Result<Self>
where I: IntoIterator<Item = K>, K: AsRef<str>,

Creates a new Trie from input keys.

Values in [0..n-1] will be associated with keys in the lexicographical order, where n is the number of keys.

§Arguments

keys: Sorted list of string keys.

§Errors

CrawdadError will be returned when

keys is empty,
keys contains empty strings,
keys contains duplicate keys,
the scale of keys exceeds the expected one, or
the scale of the resulting trie exceeds the expected one.

§Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(keys).unwrap();

assert_eq!(trie.num_elems(), 8);

Source

pub fn from_records<I, K>(records: I) -> Result<Self>
where I: IntoIterator<Item = (K, u32)>, K: AsRef<str>,

Creates a new Trie from input records.

§Arguments

records: Sorted list of key-value pairs.

§Errors

CrawdadError will be returned when

records is empty,
records contains empty strings,
records contains duplicate keys,
the scale of keys exceeds the expected one, or
the scale of the resulting trie exceeds the expected one.

§Examples

use crawdad::Trie;

let records = vec![("世界", 2), ("世界中", 3), ("国民", 2)];
let trie = Trie::from_records(records).unwrap();

assert_eq!(trie.num_elems(), 8);

Source

pub fn serialize_to_vec(&self) -> Vec<u8>

Serializes the data structure into a Vec.

§Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();
let bytes = trie.serialize_to_vec();

Source

pub fn deserialize_from_slice(source: &[u8]) -> (Self, &[u8])

Deserializes the data structure from a given byte slice.

§Arguments

source - A source byte slice.

§Returns

A tuple of the data structure and the slice not used for the deserialization.

§Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();

let bytes = trie.serialize_to_vec();
let (other, _) = Trie::deserialize_from_slice(&bytes);

assert_eq!(trie.io_bytes(), other.io_bytes());

Source

pub fn exact_match(&self, key: I) -> Option<u32>
where I: IntoIterator<Item = char>,

Returns a value associated with an input key if exists.

§Arguments

key: Search key.

§Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();

assert_eq!(trie.exact_match("世界中".chars()), Some(1));
assert_eq!(trie.exact_match("日本中".chars()), None);

Source

pub const fn common_prefix_search( &self, haystack: I, ) -> CommonPrefixSearchIter<'_, I> ⓘ

Returns an iterator for common prefix search.

The iterator reports all occurrences of keys starting from an input haystack, where an occurrence consists of its associated value and ending positoin in characters.

§Examples

You can find all occurrences of keys in a haystack by performing common prefix searches at all starting positions.

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();

let haystack: Vec<char> = "国民が世界中にて".chars().collect();
let mut matches = vec![];

for i in 0..haystack.len() {
    for (v, j) in trie.common_prefix_search(haystack[i..].iter().copied()) {
        matches.push((v, i..i + j));
    }
}

assert_eq!(
    matches,
    vec![(2, 0..2), (0, 3..5), (1, 3..6)]
);