ptrie 0.5.0

Generic trie implementation with a support of different key and value types, and common prefix search.
Documentation

PTrie is a versatile implementation of the trie data structure, tailored for efficient prefix searching within a collection of objects, such as strings, with no dependencies.

The structure is defined as Trie<K, V>, where K represents the type of keys in each node, and V is the type of the associated values.

💭 Motivation

The trie is particularly effective for operations involving common prefix identification and retrieval, making it a good choice for applications that require fast and efficient prefix-based search functionalities.

🚀 Usage

✨ Find prefixes

You can return all prefixes in the trie corresponding to a given string, sorted in ascending order of their length, or directly the longest prefix.

use ptrie::Trie;

let mut trie = Trie::new();

trie.insert("a".bytes(), "A");
trie.insert("ab".bytes(), "AB");
trie.insert("abc".bytes(), "ABC");
trie.insert("abcde".bytes(), "ABCDE");

let prefixes = trie.find_prefixes("abcd".bytes());
assert_eq!(prefixes, vec!["A", "AB", "ABC"]);

let longest = trie.find_longest_prefix("abcd".bytes());
assert_eq!(longest, Some("ABC"));

🔍 Find postfixes

You can also find all strings in the trie that begin with a specified prefix.

use ptrie::Trie;

let mut trie = Trie::new();

trie.insert("app".bytes(), "App");
trie.insert("apple".bytes(), "Apple");
trie.insert("applet".bytes(), "Applet");
trie.insert("apricot".bytes(), "Apricot");

let strings = trie.find_postfixes("app".bytes());
assert_eq!(strings, vec!["App", "Apple", "Applet"]);

🔑 Key-based Retrieval Functions

The crate provides functions to check for the existence of a key and to retrieve the associated value.

use ptrie::Trie;

let mut trie = Trie::new();
trie.insert("app".bytes(), "App");

assert!(trie.contains_key("app".bytes()));
assert!(!trie.contains_key("not_existing_key".bytes()));
assert_eq!(trie.get_value("app".bytes()), Some("App"));
assert_eq!(trie.get_value("none".bytes()), None);

🏷️ Features

The serde feature adds Serde Serialize and Deserialize traits to the Trie and TrieNode struct.

📜 License

MIT License