Struct Trie 

pub struct Trie<V> { /* private fields */ }

A trie (prefix tree) data structure

Generic over the value type V. If no value is needed, use ().

Example

use polyglot_sql::trie::{Trie, TrieResult};

let mut trie = Trie::new();
trie.insert("cat", 1);
trie.insert("car", 2);

assert_eq!(trie.in_trie("cat"), (TrieResult::Exists, Some(&1)));
assert_eq!(trie.in_trie("ca").0, TrieResult::Prefix);
assert_eq!(trie.in_trie("dog").0, TrieResult::Failed);

Implementations

impl<V> Trie<V>

pub fn new() -> Self

Create a new empty trie

pub fn insert(&mut self, key: &str, value: V)

Insert a key-value pair into the trie

Arguments

• key - The key to insert (a string slice)
• value - The value to associate with the key

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

Get the value associated with a key

Returns None if the key doesn’t exist or only exists as a prefix.

pub fn in_trie(&self, key: &str) -> (TrieResult, Option<&V>)

Check if a key exists in the trie

Returns a tuple of (TrieResult, Option<&V>) where:

• TrieResult::Failed - key not found
• TrieResult::Prefix - key is a prefix of an existing key
• TrieResult::Exists - key exists in trie

When the result is Exists, the Option will contain the value.

pub fn in_trie_char(&self, ch: char) -> (TrieResult, Option<&Trie<V>>)

Check if a key exists in the trie, following one character at a time

This is useful for streaming/incremental matching. Returns:

• TrieResult::Failed - character not found from current position
• TrieResult::Prefix - character found, but not at end of a word
• TrieResult::Exists - character found and at end of a word

Also returns the subtrie at this position (if any).

pub fn get_child(&self, ch: char) -> Option<&Trie<V>>

Get the subtrie for a given character

pub fn has_value(&self) -> bool

Check if this node has a value (is a complete word)

pub fn value(&self) -> Option<&V>

Get the value at this node

pub fn is_empty(&self) -> bool

Check if the trie is empty

pub fn keys(&self) -> Vec<String>

Get all keys in the trie

Trait Implementations

impl<V: Clone> Clone for Trie<V>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<V: Debug> Debug for Trie<V>

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

Formats the value using the given formatter.

impl<V> Default for Trie<V>

fn default() -> Self

Returns the “default value” for a type.