Trie

verbora-trie is a prefix tree keyed by UTF-16 code units. It answers four questions about a set of strings: is this exact string stored?, which stored strings start with this prefix?, which stored strings are prefixes of this string?, and where does the longest stored prefix of this string end? The whole crate is one type, Trie, plus the two iterators it hands out.

One asymmetry is worth knowing up front: on a case-insensitive trie, keys_with_prefix never folds its argument — see keys_with_prefix never folds case.

Specification status. add_string, add_strings, size, contains, keys_with_prefix, find_matches_on_path and find_prefix are documented and test-pinned, interleaved mutation/query sequences included. cargo test -p verbora-trie runs 33 unit tests and 9 doctests.

When to use it

Autocomplete and typeahead. iter_keys_with_prefix streams completions in the trie's defined child order (see Child enumeration order) and stops when you stop.
Longest-match tokenization and dictionary segmentation. find_prefix and find_prefix_lengths give you the split point of the longest stored word that prefixes the input, in one linear walk.
Membership over a large, static string set where the strings share prefixes. Node sharing means a dictionary of inflected forms costs far less than one entry per word.
Deterministic, reproducible enumeration order. Children are visited by a fixed rule, so results are exactly reproducible across runs — which matters for golden-file tests and snapshot diffs.

When not to use it

You only need set membership. A HashSet<String> is simpler and has a better constant factor when you never query by prefix.
You need to remove entries. There is no remove, no delete, and no clear. See Removing words for the rebuild pattern.
You need fuzzy matching. A trie is exact-prefix only. For edit distance and phonetic similarity, see Distance.
Your keys are not prefix-structured (UUIDs, hashes, random identifiers). Every node then has one child and the trie degenerates into a linked list with worse locality than a hash table.
The set changes constantly and must shrink. Rebuilding is the only way to drop a word, which is O(total input) each time.

Quick example

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    trie.add_strings(["and", "their", "they", "them"]);

    assert!(trie.contains("they"));
    assert!(!trie.contains("the")); // a prefix is not a word

    // Children are visited in insertion order, not sorted order.
    assert_eq!(trie.keys_with_prefix("the"), ["their", "they", "them"]);
    assert_eq!(trie.find_matches_on_path("theyre"), ["they"]);
    assert_eq!(trie.find_prefix_lengths("theyre"), (Some(4), 2));
}

That ["their", "they", "them"] is not a typo and not a sort — see Child enumeration order.

Construction

Constructor	Folds case?
`Trie::new()`	❌
`Trie::default()`	❌
`Trie::with_case_sensitivity(true)`	❌
`Trie::with_case_sensitivity(false)`	✅
`Trie::case_insensitive()`	✅
`["a", "ab"].into_iter().collect::<Trie>()`	❌

The default is case-sensitive. is_case_sensitive() reports which mode a trie is in. FromIterator and Extend are implemented for any IntoIterator whose items are AsRef<str>; both build (or extend) a case-sensitive trie, so for the folding variant construct with Trie::case_insensitive() and use add_strings.

rust

use verbora_trie::Trie;

fn main() {
    assert!(Trie::new().is_case_sensitive());
    assert!(!Trie::case_insensitive().is_case_sensitive());

    let mut t = Trie::new();
    assert_eq!(t.get_size(), 1); // the root always exists
    t.add_string("hi");
    assert_eq!(t.get_size(), 3);
}

`reserve`

reserve(additional) reserves capacity for additional more nodes, not words. A trie needs roughly one node per distinct prefix, counted in UTF-16 code units; the total UTF-16 length of the input is a safe upper bound.

rust

use verbora_trie::Trie;

fn bulk_load(words: &[String]) -> Trie {
    let mut trie = Trie::new();
    let upper_bound: usize = words.iter().map(|w| w.encode_utf16().count()).sum();
    trie.reserve(upper_bound + 1);
    trie.add_strings(words.iter().map(String::as_str));
    trie
}

fn main() {
    let words = vec![String::from("alpha"), String::from("beta")];
    assert_eq!(bulk_load(&words).keys_with_prefix(""), ["alpha", "beta"]);
}

Reserving up front removes the arena's growth reallocations from a bulk load. add_strings already reserves the iterator's size_hint().0 — one node per item, a lower bound — which skips the first few doublings but not the rest.

Insertion

Careful. add_string returns true when the string was already present — the opposite of HashSet::insert, which returns true when the value is new. If you want "did I insert something?", negate it: let inserted = !trie.add_string(w);

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    assert!(!trie.add_string("test")); // false: it was NOT already there
    assert!(trie.add_string("test")); // true: it WAS already a word

    // The empty string is a word that creates no node.
    assert!(!trie.add_string(""));
    assert!(trie.contains(""));
    assert_eq!(trie.get_size(), 5); // root + t + e + s + t
}

Adding the empty string marks the root as a word. It creates no node, so get_size() does not change — but contains("") becomes true, "" becomes the first result of keys_with_prefix("") and of every find_matches_on_path, and find_prefix starts returning Some("") instead of None for total misses.

add_strings<I>(list) takes any IntoIterator whose items are AsRef<str>. It reserves size_hint().0 nodes and then calls add_string per item, so the return values are discarded. There is no batch or parallel insertion API: add_string needs &mut self and mutates shared arena state, so building a trie is inherently single-threaded — see Sharing a trie across threads for what can be parallelised.

Choosing the right API

The query surface has three lazy/materialised pairs, plus two decisions that are easy to get wrong.

Comparison table

"Folds" means on a case-insensitive trie — a case-sensitive trie never folds anything. "Allocations" assumes the folding step had nothing to do.

API	Answers	Lazy	Output	Folds	Allocations
`contains(s)`	is `s` a stored word?	n/a	`bool`	✅	none, unless folding rewrites `s`
`get_size()`	how many nodes?	n/a	`usize`	n/a	none — O(1)
`keys_with_prefix(p)`	all words under `p`	❌	`Vec<String>`	❌ never	one `Vec` + one `String` per key
`iter_keys_with_prefix(p)`	all words under `p`	✅	`KeysWithPrefix` → `String`	❌ never	one path buffer + one stack; one `String` per key yielded
`keys()`	all words	✅	`KeysWithPrefix` → `String`	n/a	as above
`find_matches_on_path(s)`	stored words that prefix `s`	❌	`Vec<Cow<'a, str>>`	✅	one `Vec`; items borrow `s`
`iter_matches_on_path(s)`	stored words that prefix `s`	✅	`MatchesOnPath` → `Cow<'a, str>`	✅	none on a case-sensitive trie
`find_prefix(s)`	longest stored prefix + remainder	n/a	`(Option<Cow>, Cow)`	✅	none in the common case; see below
`find_prefix_lengths(s)`	the same split, in code units	n/a	`(Option<usize>, usize)`	✅	none

Two columns deserve a second look:

"Folds" is ❌ never for the keys_with_prefix family, even on a case-insensitive trie — see keys_with_prefix never folds case.
find_prefix allocates in two situations: when folding actually rewrites the search string, and when the walk stops between the halves of a surrogate pair. find_prefix_lengths allocates in the first situation only, and stays exact in the second.

Which one

Your question	Use
Is this exact string stored?	`contains()`
How big is the structure?	`get_size()` — nodes, not words, O(1)
Which stored words start with mine, and I need to keep them all?	`keys_with_prefix()` → `Vec<String>`
…only the first N, or I stop on a condition?	`iter_keys_with_prefix().take(N)`
…only "does anything start with this?"	`iter_keys_with_prefix().next().is_some()`
Every word in the trie	`keys()` — lazy, same as `iter_keys_with_prefix("")`
Which stored words are prefixes of mine, all of them, shortest first?	`find_matches_on_path()` → `Vec<Cow<str>>`
…only the shortest, or the first few?	`iter_matches_on_path().next()` / `.take(n)`
…only the longest?	`find_prefix().0` — one walk, no iterator
Where does the longest stored prefix end, as text?	`find_prefix()` → `(Option<Cow>, Cow)`
…as offsets, exactly, with no allocation?	`find_prefix_lengths()` → `(Option<usize>, usize)`

`keys_with_prefix` OWNED

Literally self.iter_keys_with_prefix(prefix).collect(): eager, walks the whole subtree, and allocates one Vec plus one String per key. Reach for it when the result is small and you want to hold on to it; reach for the iterator when it might not be.

`iter_keys_with_prefix` and `keys` LAZY

Lazy and depth-first, one key per next(). Working set is one reusable path String and one frame Vec, both O(depth), plus one String per key actually yielded. keys() is exactly iter_keys_with_prefix(""), and &trie implements IntoIterator with the same behaviour, so for word in &trie works. Both are FusedIterator.

Each item is an owned String because a stored word exists nowhere contiguously — it is spelled out one code unit per node — so it has to be materialised. What the iterator avoids is the result Vec and every key you never asked for.

rust

use verbora_trie::Trie;

fn suggest(trie: &Trie, prefix: &str, limit: usize) -> Vec<String> {
    trie.iter_keys_with_prefix(prefix).take(limit).collect()
}

fn main() {
    let mut trie = Trie::new();
    trie.add_strings((0..5_000).map(|i| format!("search{i:04}")));

    // Materialising: walks all 5,000 keys and allocates 5,001 Strings.
    assert_eq!(trie.keys_with_prefix("search").len(), 5_000);

    // Streaming: stops after 10 keys, allocates 10 Strings plus the path buffer.
    let page = suggest(&trie, "search", 10);
    assert_eq!((page.len(), page[0].as_str()), (10, "search0000"));

    // "Is there anything under this prefix?" needs exactly one key.
    assert!(trie.iter_keys_with_prefix("search1").next().is_some());
    assert!(trie.iter_keys_with_prefix("zzz").next().is_none());
}

Both paths do the same work per key; the difference is how many keys get visited. The existence check is the sharper version of the point: calling keys_with_prefix(p) and testing is_empty() builds the whole subtree only to throw it away.

`find_matches_on_path` and `iter_matches_on_path`

find_matches_on_path is eager — one linear walk of the search string, one Vec. iter_matches_on_path advances the walk one character per next() and allocates nothing on a case-sensitive trie. Results are cut from the search string (after folding), not rebuilt from the stored keys, which is why they can borrow. The number of matches is bounded by the length of the search string, so the eager Vec is small by construction — the lazy variant matters less here than for keys_with_prefix.

rust

use verbora_trie::Trie;
use std::borrow::Cow;

fn main() {
    let mut trie = Trie::new();
    trie.add_strings(["a", "ab", "bc", "cd", "abc"]);

    // All of them.
    let all: Vec<Cow<'_, str>> = trie.find_matches_on_path("abcd");
    assert_eq!(all, ["a", "ab", "abc"]);

    // Shortest only: one step of the walk.
    assert_eq!(trie.iter_matches_on_path("abcd").next().as_deref(), Some("a"));

    // Longest only: find_prefix answers it without an iterator at all.
    let (longest, rest) = trie.find_prefix("abcd");
    assert_eq!((longest.as_deref(), rest.as_ref()), (Some("abc"), "d"));
}

Note. Do not reach for .last() on iter_matches_on_path to get the longest match. It works, but it walks the whole string and yields every shorter match on the way. find_prefix(s).0 is the same answer from the same single walk, and find_prefix_lengths(s).0 is that answer without any allocation.

Like KeysWithPrefix, MatchesOnPath is a FusedIterator.

`find_prefix` UTF-16

Returns the longest stored prefix, if any, paired with the unconsumed remainder of the search string. One linear walk; allocates nothing when nothing folds and the walk stops on a character boundary.

rust

use verbora_trie::Trie;
use std::borrow::Cow;

fn main() {
    let mut trie = Trie::new();
    trie.add_strings(["their", "and", "they"]);

    let (word, rest) = trie.find_prefix("theyre");
    assert_eq!((word.as_deref(), rest.as_ref()), (Some("they"), "re"));
    // Borrowed on a case-sensitive trie: no allocation.
    assert!(matches!(word, Some(Cow::Borrowed(_))));
    assert!(matches!(rest, Cow::Borrowed(_)));

    // The remainder is where the WALK died, not where the word ended.
    let mut partial = Trie::new();
    partial.add_strings(["their", "and"]);
    let (word, rest) = partial.find_prefix("theyre");
    assert_eq!((word, rest.as_ref()), (None, "yre")); // the walk got as far as "the"
}

Two details are easy to get wrong:

The remainder is what was left when the walk died, not what was left after the last word ended. The two coincide only when the walk stops exactly at the end of a stored word.
Some("") and None are different answers. A trie containing the empty string returns (Some(""), "zzz") for find_prefix("zzz"), so an if let Some(w) = … if !w.is_empty() guard silently treats a real match as a miss.

`find_prefix_lengths` ALLOCATION-FREE UTF-16

The same single walk with the string-building removed, returning (Option<usize>, usize). Prefer it whenever you do not need the two halves as strings — it is also the only one of the two that stays exact when the walk stops inside a surrogate pair, see the divergence below.

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    trie.add_strings(["their", "and", "they"]);
    assert_eq!(trie.find_prefix_lengths("theyre"), (Some(4), 2));
}

Careful. The lengths are UTF-16 code units, not bytes and not chars. They index a Rust &str only after you convert. For pure ASCII all three coincide, which is exactly what makes this easy to get wrong later.

Advanced usage

A Trie is a plain owned value — a Vec<Node> and a bool — so it is Send + Sync, and every query method takes &self. Build once, wrap in an Arc, then fan out.

rust

use verbora_trie::Trie;
use std::sync::Arc;

fn main() {
    fn assert_send_sync<T: Send + Sync>() {}
    assert_send_sync::<Trie>();

    let mut trie = Trie::new();
    trie.add_strings(["alpha", "beta", "gamma"]);
    let trie = Arc::new(trie);

    let handles: Vec<_> = ["alpha", "beta", "gamma"]
        .into_iter()
        .map(|word| {
            let trie = Arc::clone(&trie);
            std::thread::spawn(move || trie.contains(word))
        })
        .collect();

    for h in handles {
        assert!(h.join().unwrap());
    }
}

If the trie outlives the threads, std::thread::scope avoids the Arc entirely.

Note. verbora-trie ships no par_* API: query cost measures at ~67 ns, at or below typical rayon dispatch overhead, and construction cannot be parallelised at all because add_string takes &mut self and appends to one shared arena. Parallelising queries yourself, as above, is the supported route. See Parallelism.

Removing words

There is no remove, no delete and no clear. The pattern is to rebuild from keys(), which is lazy, so the old trie is streamed rather than materialised.

rust

use verbora_trie::Trie;

fn rebuild_without(trie: &Trie, drop: &str) -> Trie {
    let mut rebuilt = if trie.is_case_sensitive() {
        Trie::new()
    } else {
        Trie::case_insensitive()
    };
    // The rebuilt trie can never need more nodes than the original had.
    rebuilt.reserve(trie.get_size());
    rebuilt.add_strings(trie.keys().filter(|w| w != drop));
    rebuilt
}

fn main() {
    let mut trie = Trie::new();
    trie.add_strings(["alpha", "beta", "gamma"]);

    let smaller = rebuild_without(&trie, "beta");
    assert_eq!(smaller.keys_with_prefix(""), ["alpha", "gamma"]);
    assert!(smaller.get_size() < trie.get_size());
}

This is O(total stored text) and allocates a String per surviving word, so it is a maintenance operation, not something to do per request. If your workload needs frequent deletion, keep an auxiliary HashSet of tombstones and filter results, or rebuild on a schedule.

Three behaviors worth knowing

UTF-16 code-unit keying

UTF-16

Each node's child map is indexed by UTF-16 code units, not Unicode scalar values. A non-BMP character such as '😀' (U+1F600) is a surrogate pair, so it occupies two levels of the tree and get_size counts it twice.

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    trie.add_string("a👍");
    assert_eq!(trie.get_size(), 4); // root + 'a' + high surrogate + low surrogate

    let mut bmp = Trie::new();
    bmp.add_string("日本語");
    assert_eq!(bmp.get_size(), 4); // one node per BMP character
}

Everything user-visible stays correct — words round-trip, contains works, iteration reassembles surrogate pairs into proper chars — but node counts and walk failure points follow UTF-16. The one place this leaks into results is the find_prefix surrogate divergence.

Child enumeration order

A node's children are visited by a fixed rule: integer-index-like keys first, in ascending numeric order, then every other key in insertion order. Trie keys are single code units, so the only keys that qualify are the ASCII digits '0'–'9'.

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    trie.add_strings(["b1", "a1", "9x", "1x", "0x", "zz"]);
    assert_eq!(trie.keys_with_prefix(""), ["0x", "1x", "9x", "b1", "a1", "zz"]);
}

Read that carefully: 0x, 1x, 9x come first sorted, then b1, a1, zz in insertion order. Each node's child list is kept in this order on insertion, so iteration is a straight scan with no sorting at read time. Traversal is otherwise pre-order depth-first: a node's own word is emitted before its children, which is why "a" precedes "ab".

`keys_with_prefix` never folds case

Careful. On a case-insensitive trie, every method folds its argument except keys_with_prefix, iter_keys_with_prefix and keys. An upper-case prefix matches nothing, because every stored word was folded on the way in. This is specified behavior, pinned by the test suite.

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::case_insensitive();
    trie.add_strings(["thEIr", "And", "theY"]);

    // Every other method folds.
    assert!(trie.contains("THEIR"));
    assert_eq!(trie.find_matches_on_path("THEYRE"), ["they"]);
    assert_eq!(trie.find_prefix("ThEyRe").0.as_deref(), Some("they"));

    // keys_with_prefix does not.
    assert_eq!(trie.keys_with_prefix("th"), ["their", "they"]);
    assert!(trie.keys_with_prefix("TH").is_empty()); // not a typo

    // If you want folded semantics, fold the prefix yourself.
    let folded = "TH".to_lowercase();
    assert_eq!(trie.keys_with_prefix(&folded), ["their", "they"]);
}

str::to_lowercase is the same folding Trie applies internally when storing words, so folding the prefix yourself with it reproduces the trie's own case-insensitive matching.

The `find_prefix` surrogate divergence

Because the walk advances one code unit at a time, it can stop between the halves of a surrogate pair. The remainder would then begin with an unpaired low surrogate, which a Rust String cannot hold, so that single position is rendered as U+FFFD (�). Everything after it is intact, and the split point itself is exact.

rust

use verbora_trie::Trie;

fn main() {
    let mut trie = Trie::new();
    trie.add_string("a👍"); // U+1F44D = D83D DC4D

    // U+1F44C = D83D DC4C shares the high surrogate but not the low one, so the
    // walk consumes three of the four code units.
    let (word, rest) = trie.find_prefix("a👌");
    assert_eq!((word, rest.as_ref()), (None, "\u{FFFD}")); // rendered lossily
    assert_eq!(trie.find_prefix_lengths("a👌"), (None, 1)); // exact

    // A character differing in its FIRST half dies on a clean boundary.
    let (_, rest) = trie.find_prefix("a𝕳x");
    assert_eq!(rest, "𝕳x");
    assert_eq!(trie.find_prefix_lengths("a𝕳x"), (None, 3));
}

Use find_prefix_lengths if this matters to you. The divergence can only occur when two astral characters share a high surrogate and differ in the low one — within the same 1,024-code-point block. It cannot occur for BMP text of any script.

Performance characteristics

All nodes live in one flat Vec<Node> arena addressed by u32, so a trie is two allocations rather than one per node. Four consequences you can observe:

Property	What you observe
Flat arena, `u32` indices	No per-node allocation during a bulk load, and a descent touches consecutive cache lines instead of chasing pointers — see Cache locality
`get_size()` is `Vec::len`	O(1) instead of a full tree walk, so it is safe to call frequently
`SmallVec<[Child; 2]>` inline children	Nodes with one or two children — the overwhelming majority in a natural-language trie — keep their edges inside the node, so a child lookup is a linear scan of two contiguous 8-byte entries. `Node` is 32 bytes, exactly what a plain `Vec<Child>` would cost
Case folded once, at the entry point, and every operation is iterative	Case-insensitive operations stay linear in input length, and a 200,000-code-unit input is a loop rather than 200,000 stack frames (pinned by a unit test)

Measured

crates/verbora-trie/benches/trie.rs compares the arena against the closest faithful one-hash-map-per-node analogue, in both std's SipHash and rustc-hash's FxHash, over 20,000 words (32,000 for prefix_heavy).

Benchmark	arena	hashmap (Fx)	hashmap (Sip)
`build/random`	1.48 ms	25.1 ms	41.9 ms
`build/prefix_heavy`	2.18 ms	11.5 ms	15.2 ms
`contains_hit`	1.13 ms	1.20 ms	3.15 ms
`contains_miss`	1.26 ms	1.94 ms	3.51 ms
`get_size`	0.23 ns	1.87 ms	—

Build is roughly 17× faster than the fastest hash baseline, because the arena makes no per-node allocation. contains_hit is a near tie: at one or two children per node, scanning an inline array costs about what hashing a u16 does. The arena buys build cost and memory behaviour, not a lookup advantage.

Note. One machine's recordings. Treat the ratios as the durable part and re-run cargo bench -p verbora-trie for numbers that mean anything on your hardware. See Benchmarks.

Complexity

With m = length of the argument in UTF-16 code units and k = the number of children of a node:

Operation	Complexity
`add_string`	O(m · k) — one linear child scan per code unit, plus an ordered insert for new edges
`contains`	O(m · k)
`get_size`	O(1)
`find_prefix`, `find_prefix_lengths`	O(m · k)
`find_matches_on_path`	O(m · k); at most one result per character consumed, plus `""` if it was stored
`keys_with_prefix(p)`	O(len(p) · k + size of the subtree + total length of the results)
`iter_keys_with_prefix(p).take(n)`	O(len(p) · k + the part of the subtree needed for `n` keys)

k is one or two for the overwhelming majority of nodes in natural-language text, so the · k factor behaves as a small constant.

Allocation behaviour

The trie itself. One Vec<Node> arena, 32 bytes per node, grown by doubling unless you reserve, plus one heap allocation per node that acquires a third child. Node count equals the number of distinct prefixes across all stored words, measured in UTF-16 code units, plus one for the root.

Queries — assuming a case-sensitive trie, or a case-insensitive one whose argument is already folded:

Call	Allocates
`contains(s)`, `get_size()`, `find_prefix_lengths(s)`, `iter_matches_on_path(s)`	nothing
`find_prefix(s)`	nothing, unless the walk splits a surrogate pair (one `String` for the remainder)
`find_matches_on_path(s)`	one `Vec`; the items borrow `s`
`iter_keys_with_prefix(p)`	one path `String` and one frame `Vec` (both O(depth)), plus one `String` per key yielded
`keys_with_prefix(p)`	the above, plus one `Vec` grown by doubling

When folding does change the argument — a case-insensitive trie given upper-case input — one String copy is made up front and every Cow result derived from it becomes owned. So find_matches_on_path("THEYRE") on a folding trie allocates the folded copy plus one String per match, where the same call on a case-sensitive trie allocates only the Vec. Fold your inputs once at your own boundary if this is hot.

There is no _into variant and no caller-supplied output buffer anywhere in this crate; the only buffer reuse is internal to KeysWithPrefix, which pushes and truncates one path String for the whole traversal. See Allocation and Iterator vs. _into.

Unicode and language notes

Keys are UTF-16 code units. See UTF-16 code-unit keying. BMP characters — all of Latin, Greek, Cyrillic, Hebrew, Arabic, and the common CJK blocks — are one code unit and so one node. Emoji, historic scripts, and mathematical alphanumerics are two.
Iteration reassembles surrogate pairs, so keys() yields well-formed Strings even though the tree stores halves. The only place a half escapes is the find_prefix remainder.
Folding is str::to_lowercase (with a byte-wise fast path for ASCII that reaches the same answer). It handles every Unicode scalar value — including multi-character expansions such as 'İ' → "i̇" and the context-sensitive Greek final sigma — but applies neither Turkish nor Lithuanian locale rules. Folding can lengthen a word: 'İ' becomes two code points, so it occupies two nodes.
Folding is not normalization and not case-folding in the Unicode sense.'ß' has no single-character uppercase, so "straße" and "strasse" remain different words on a case-insensitive trie. Decomposed and precomposed forms of the same grapheme are different words too — normalize before inserting if that matters.
Nothing is trimmed or tokenized. Whitespace and punctuation are ordinary code units; " double " is a word with its spaces. Split text with Tokenizers first.

Common mistakes

Reading add_string's bool backwards. It returns true when the word was already stored, the opposite of HashSet::insert. Negate it for the HashSet sense: let inserted = !trie.add_string("word");

Expecting contains to match prefixes. contains is exact-word. With only "tested" stored, contains("test") is false; the prefix question is iter_keys_with_prefix("test").next().is_some().

Assuming get_size counts words. It counts nodes, root included — for ["a", "ab", "abc"] that is 4 nodes and 3 words.

Passing an upper-case prefix to keys_with_prefix on a case-insensitive trie. It silently returns nothing. See keys_with_prefix never folds case.

Treating Some("") as "no match" in find_prefix. If the empty string was added, the root is a word and every total miss returns Some(""), not None.

Sorting the output of keys_with_prefix. If you sort it you have thrown away the established order. Sort only when you want sorted output.

Building the whole result to check emptiness.keys_with_prefix(p).is_empty() walks the entire subtree; iter_keys_with_prefix(p).next().is_none() does not.

Calling find_prefix when you only need offsets. find_prefix_lengths is the same walk without the string building, and it is exact across surrogate pairs.

Looking for remove. There is none. See Removing words.

Choosing an API — the cross-crate version of the decision table above.
Iterator vs. _into — why the lazy variants exist and when they pay.
Allocation — what "allocation-free" means across Verbora.
Cache locality — the arena's other advantage.
Parallelism — what you can and cannot parallelise.
Performance overview · Benchmarks
Tokenizers — produce the strings you insert.
Distance — for fuzzy matching, which a trie cannot do.
Core traits — the shared vocabulary the rest of the workspace uses.
Recipes — end-to-end pipelines.

API reference

rust

// verbora_trie
pub struct Trie { /* private */ }
pub struct KeysWithPrefix<'t> { /* private */ }
pub struct MatchesOnPath<'t, 'a> { /* private */ }

impl Trie {
    // Construction
    pub fn new() -> Self;                                   // case-sensitive
    pub fn case_insensitive() -> Self;
    pub fn with_case_sensitivity(case_sensitive: bool) -> Self;
    pub fn is_case_sensitive(&self) -> bool;
    pub fn reserve(&mut self, additional: usize);           // nodes, not words

    // Mutation
    pub fn add_string(&mut self, string: &str) -> bool;     // true = ALREADY present
    pub fn add_strings<I>(&mut self, list: I)
    where I: IntoIterator, I::Item: AsRef<str>;

    // Query
    pub fn contains(&self, string: &str) -> bool;
    pub fn get_size(&self) -> usize;                        // nodes, O(1)

    pub fn keys_with_prefix(&self, prefix: &str) -> Vec<String>;
    pub fn iter_keys_with_prefix(&self, prefix: &str) -> KeysWithPrefix<'_>;
    pub fn keys(&self) -> KeysWithPrefix<'_>;

    pub fn find_matches_on_path<'a>(&self, search: &'a str) -> Vec<Cow<'a, str>>;
    pub fn iter_matches_on_path<'a>(&self, search: &'a str) -> MatchesOnPath<'_, 'a>;

    pub fn find_prefix<'a>(&self, search: &'a str)
        -> (Option<Cow<'a, str>>, Cow<'a, str>);
    pub fn find_prefix_lengths(&self, search: &str) -> (Option<usize>, usize);
}

// Trait implementations
impl Default for Trie;                       // = Trie::new()
impl Clone for Trie;
impl Debug for Trie;
impl PartialEq for Trie;
impl Eq for Trie;
impl<S: AsRef<str>> Extend<S> for Trie;
impl<S: AsRef<str>> FromIterator<S> for Trie;    // case-sensitive
impl<'a> IntoIterator for &'a Trie;              // Item = String, IntoIter = KeysWithPrefix<'a>

impl Iterator for KeysWithPrefix<'_>;            // Item = String
impl FusedIterator for KeysWithPrefix<'_>;
impl Debug for KeysWithPrefix<'_>;

impl<'a> Iterator for MatchesOnPath<'_, 'a>;     // Item = Cow<'a, str>
impl FusedIterator for MatchesOnPath<'_, '_>;
impl Debug for MatchesOnPath<'_, '_>;

No remove, no clear, no batch API, no parallel API. Trie is Send + Sync.

Trie ​

When to use it ​

When not to use it ​

Quick example ​

Construction ​

reserve ​

Insertion ​

Choosing the right API ​

Comparison table ​

Which one ​

keys_with_prefix OWNED ​

iter_keys_with_prefix and keys LAZY ​

find_matches_on_path and iter_matches_on_path ​

find_prefix UTF-16 ​

find_prefix_lengths ALLOCATION-FREE UTF-16 ​

Advanced usage ​

Sharing a trie across threads ​

Removing words ​

Three behaviors worth knowing ​

UTF-16 code-unit keying ​

Child enumeration order ​

keys_with_prefix never folds case ​

The find_prefix surrogate divergence ​

Performance characteristics ​

Measured ​

Complexity ​

Allocation behaviour ​

Unicode and language notes ​

Common mistakes ​

Related ​

API reference ​

Trie

When to use it

When not to use it

Quick example

Construction

`reserve`

Insertion

Choosing the right API

Comparison table

Which one

`keys_with_prefix` OWNED

`iter_keys_with_prefix` and `keys` LAZY

`find_matches_on_path` and `iter_matches_on_path`

`find_prefix` UTF-16

`find_prefix_lengths` ALLOCATION-FREE UTF-16

Advanced usage

Sharing a trie across threads

Removing words

Three behaviors worth knowing

UTF-16 code-unit keying

Child enumeration order

`keys_with_prefix` never folds case

The `find_prefix` surrogate divergence

Performance characteristics

Measured

Complexity

Allocation behaviour

Unicode and language notes

Common mistakes

Related

API reference