Module: collections.trie

Source: ./collections/trie.reef

Overview

collections/trie — Trie[V], a string-keyed prefix tree.

Collections 0.9.2 / D13. ONE generic trie replaces IntTrie and StringTrie, which were the same algorithm written twice and differed only in value type.

Keys are STRINGS by nature here — a trie walks a key character by character — so Trie takes no Hash bound. That is what distinguishes it from collections.hashmap: it answers prefix questions (has_prefix, longest_prefix) that a hash map cannot.

ASCII 0-127 children table, flat node pool.

Usage: import collections.trie import core.option as option let t = trie.create:int t.insert("hello", 1) match t.lookup("hello") Option_Some(v) => println("${v}") end Option_None() => println("missing") end end match

THE NODE POOL GROWS. The typed predecessors had a fixed pool and insert_int silently no-opped once it was exhausted — the key simply was not there afterwards, with no error. insert() grows the pool instead, so try_insert() now fails ONLY on invalid input (an empty key or a non-ASCII character), never on capacity.

Factories: createV -> Trie[V], 256-node pool create_with_capacityV -> Trie[V]; nodes < 1 clamps to 1

Methods: insert(key, value) - proc; grows the pool try_insert(key, value) - Result[bool, Error]; Ok(true) new, Ok(false) updated, Err on bad input lookup(key): option.Option[V] has(key) -> bool has_prefix(prefix) -> bool - empty prefix matches everything longest_prefix(s) -> string - longest stored key that prefixes s len() / is_empty()

Types

Trie

Fields:

Functions

fn max_char(): int

ASCII range: 0-127

fn nil_node(): int

Sentinel for "no child"

fn default_pool_cap(): int

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

Character code at index. str.length is O(1) since BUG-147, so callers walking a key pay O(n), not O(n^2).

fn create(): Trie[V]

fn create_with_capacity(nodes: int): Trie[V]

nodes < 1 clamps to 1 (BUG-062): the pool doubles, and doubling from 0 stays 0.

Generated by reefc doc