Module: collections.trie

Source: ./collections/trie.reef

Overview

collections/trie - Prefix Tree (Trie) Data Structure

A trie is a tree data structure for efficient prefix-based string lookup. Useful for keyword recognition in lexers, autocomplete, and IP routing.

Capacity: FIXED node pool (default 256 nodes via default_pool_cap). Does NOT auto-grow. Prefer try_insert_* which returns Result: Ok(true) = new key, Ok(false) = updated existing, Err = pool exhausted or invalid input. Legacy insert_* still no-ops on failure (compat). Suitable for fixed keyword tables sized under the pool limit.

Usage: import collections.trie

let t = trie.create_int() trie.insert_int(t, "if", 1) trie.insert_int(t, "int", 2) trie.insert_int(t, "import", 3)

print_int(option.unwrap_or(trie.lookup_int(t, "if"), 0)) // prints 1 print_int(option.unwrap_or(trie.lookup_int(t, "int"), 0)) // prints 2

// Prefix matching if trie.has_prefix_int(t, "im") println("Has prefix 'im'") end if

Implementation:

Flat node pool with index-based children references
O(m) lookup where m = string length
Memory-efficient for strings with common prefixes

Types

IntTrie

Node data stored in flat arrays (each array index is a node)

Fields:

Name	Type
`children`	`[int]`
`values`	`[int]`
`has_values`	`[bool]`
`node_count`	`int`
`node_cap`	`int`
`key_count`	`int`

StringTrie

Fields:

Name	Type
`children`	`[int]`
`values`	`[string]`
`has_values`	`[bool]`
`node_count`	`int`
`node_cap`	`int`
`key_count`	`int`

Functions

`fn max_char(): int`

Maximum ASCII character supported

`fn nil_node(): int`

Invalid node index (represents nil/null)

`fn default_pool_cap(): int`

Default node pool capacity

`fn char_code_at(s: string, idx: int): int`

Get char code from string at index

`fn create_int(): IntTrie`

`fn alloc_node_int(t: IntTrie): int`

Allocate a new node and return its index

`fn get_child_int(t: IntTrie, node: int, c: int): int`

Get child index for a node

`fn try_insert_int(t: IntTrie, key: string, value: int): result.Result[bool, error.Error]`

Result-shaped insert. Ok(true) = new key, Ok(false) = updated existing, Err = empty key, invalid char, or node pool exhausted.

`fn lookup_int(t: IntTrie, key: string): option.Option[int]`

`fn has_int(t: IntTrie, key: string): bool`

`fn has_prefix_int(t: IntTrie, prefix: string): bool`

`fn longest_prefix_int(t: IntTrie, s: string): string`

`fn count_int(t: IntTrie): int`

`fn is_empty_int(t: IntTrie): bool`

`fn create_string(): StringTrie`

`fn alloc_node_str(t: StringTrie): int`

`fn get_child_str(t: StringTrie, node: int, c: int): int`

`fn try_insert_str(t: StringTrie, key: string, value: string): result.Result[bool, error.Error]`

Result-shaped insert for string values. Same Ok/Err contract as try_insert_int.

`fn lookup_str(t: StringTrie, key: string): option.Option[string]`

`fn has_str(t: StringTrie, key: string): bool`

`fn has_prefix_str(t: StringTrie, prefix: string): bool`

`fn longest_prefix_str(t: StringTrie, s: string): string`

`fn count_str(t: StringTrie): int`

`fn is_empty_str(t: StringTrie): bool`

Procedures

`proc set_child_int(t: IntTrie, node: int, c: int, child: int)`

Set child for a node

`proc insert_int(t: IntTrie, key: string, value: int)`

Legacy insert — no-ops on failure (prefer try_insert_int).

`proc set_child_str(t: StringTrie, node: int, c: int, child: int)`

`proc insert_str(t: StringTrie, key: string, value: string)`

Legacy insert — no-ops on failure (prefer try_insert_str).

Generated by reefc doc