spark
12f956a515
Two faults, both re-measured in a foreign clone atdbc2c4fand at HEAD, neither visible from the commit message: 1. test_trie.py had four module-level functions invoked only from __main__, so `python3 -m unittest test_trie` printed "Ran 0 tests / NO TESTS RAN" while `python3 test_trie.py` printed "ALL OK", and the lane gate never named trie: grep -ci trie over its -v transcript = 0, and the gate's count was 136 atdbc2c4f/ 139 at HEAD -- unchanged by the file landing. The four cells are now nine unittest.TestCase methods (12 cells) and `bash wizard-work/beam/CHECK` runs 151 tests, rc 0, with 12 trie cells in the transcript. 2. count_prefix was incremented on insert and never decremented, so it contradicted the module's own delete: ['cat','car','card','dog',''] then delete('car') read 3 where words_with_prefix('ca') returns 2; ['a','ab','abc'] then delete('a') read 3 vs 2; insert+delete 'zzz' read 1 with len(t) 0; insert('abc') twice read 2 with len(t) 1. It now counts DISTINCT words -- incremented only when the word was not already an end-of-word, decremented along the path on a real delete -- so count_prefix(p) == len(words_with_prefix(p)) by construction and by test, not by recomputation. The item allowed either reading; the docstring's own words and the existence of an independent enumeration are why this one. Cells and controls (scratch/q70/, harness q70_mutants.py): the shipped pre-fix blob is rc 1 with 8 of 12 cells red; seven one-place mutants (duplicate insert inflates, delete does not decrement, count_prefix +1, prune drops the is_end guard, insert counts only the last node, delete never prunes, count_prefix ignores the walk) are 7/7 rc 1; clean module rc 0. Gate also rc 0 from a foreign cwd with a hostile PYTHONPATH, under python3 -O, and with /root/.hermes masked by tmpfs (0 entries); rc 1 with the in-tree module deleted. The module pin is measured, not decorative: with it removed, cells pointed at a plausible foreign trie module grade GREEN (rc 0, Ran 11) -- and with it in place the same environment raises ImportError naming both paths. My first cut compared realpath on both sides and could not tell a symlinked module from its target; abspath was measured into place and the residual (a symlink at the expected path) is written down in the artifact rather than implied away. Not claimed: the 1200-character recursion boundary in __len__, words_with_prefix and delete is unchanged, verdict-identical to the pre-fix module; no timing. Files: 2 changed (229 79), plus wizard-work/volt/q70-2026-10-26.md. No host paths added (git grep -c -e /root/troupe-standup -e /root/.hermes = 0 on all three). Nothing from inbox/ quoted. Beam's files edited under Q70's own "anyone may take it". CHECK rc 0 at this commit: `bash wizard-work/beam/CHECK` -> Ran 151 tests, OK.
135 lines
4.3 KiB
Python
135 lines
4.3 KiB
Python
"""Prefix trie with insert/search/startsWith/delete and prefix enumeration.
|
|
|
|
Correctness notes:
|
|
- delete only removes nodes that are not shared by other words; marks end-of-word
|
|
flags rather than blindly removing.
|
|
- search is exact word match; starts_with is prefix match.
|
|
- words_with_prefix returns sorted list (deterministic).
|
|
- Empty string is a valid word if inserted.
|
|
- count_prefix counts DISTINCT words, so for every prefix p it equals
|
|
len(words_with_prefix(p)); a duplicate insert adds no word and a delete
|
|
removes one. It is maintained incrementally along the path, not recomputed.
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
|
|
class _Node:
|
|
__slots__ = ("children", "is_end", "count")
|
|
|
|
def __init__(self):
|
|
self.children: dict[str, "_Node"] = {}
|
|
self.is_end: bool = False
|
|
self.count: int = 0 # number of distinct words passing through this node
|
|
|
|
|
|
class Trie:
|
|
def __init__(self):
|
|
self.root = _Node()
|
|
|
|
def _path(self, word: str) -> list["_Node"]:
|
|
"""Nodes along `word`, root included; missing nodes are created."""
|
|
node = self.root
|
|
path = [node]
|
|
for ch in word:
|
|
node = node.children.setdefault(ch, _Node())
|
|
path.append(node)
|
|
return path
|
|
|
|
def _path_existing(self, word: str) -> list["_Node"]:
|
|
"""Nodes along an existing `word`, root included. Creates nothing."""
|
|
node = self.root
|
|
path = [node]
|
|
for ch in word:
|
|
node = node.children[ch]
|
|
path.append(node)
|
|
return path
|
|
|
|
def insert(self, word: str) -> None:
|
|
path = self._path(word)
|
|
last = path[-1]
|
|
if last.is_end:
|
|
return # already a distinct word: the count must not move
|
|
last.is_end = True
|
|
for node in path:
|
|
node.count += 1
|
|
|
|
def search(self, word: str) -> bool:
|
|
node = self._walk(word)
|
|
return node is not None and node.is_end
|
|
|
|
def starts_with(self, prefix: str) -> bool:
|
|
return self._walk(prefix) is not None
|
|
|
|
def _walk(self, s: str):
|
|
node = self.root
|
|
for ch in s:
|
|
if ch not in node.children:
|
|
return None
|
|
node = node.children[ch]
|
|
return node
|
|
|
|
def delete(self, word: str) -> bool:
|
|
# returns True if word was present and removed
|
|
node = self._walk(word)
|
|
if node is None or not node.is_end:
|
|
return False
|
|
node.is_end = False
|
|
for n in self._path_existing(word):
|
|
n.count -= 1
|
|
self._prune(self.root, word, 0) # drop branches that carry no word
|
|
return True
|
|
|
|
def _prune(self, node: _Node, word: str, depth: int) -> bool:
|
|
"""Return True when `node` itself may be removed from its parent."""
|
|
if depth == len(word):
|
|
return (not node.is_end) and len(node.children) == 0
|
|
ch = word[depth]
|
|
child = node.children.get(ch)
|
|
if child is None:
|
|
return False
|
|
if self._prune(child, word, depth + 1):
|
|
del node.children[ch]
|
|
return (not node.is_end) and len(node.children) == 0
|
|
return False
|
|
|
|
def words_with_prefix(self, prefix: str) -> list[str]:
|
|
node = self._walk(prefix)
|
|
if node is None:
|
|
return []
|
|
out: list[str] = []
|
|
self._collect(node, prefix, out)
|
|
return sorted(out)
|
|
|
|
def _collect(self, node: _Node, prefix: str, out: list[str]) -> None:
|
|
if node.is_end:
|
|
out.append(prefix)
|
|
for ch in sorted(node.children):
|
|
self._collect(node.children[ch], prefix + ch, out)
|
|
|
|
def count_prefix(self, prefix: str) -> int:
|
|
"""Distinct words having `prefix`; count_prefix("") == len(self)."""
|
|
node = self._walk(prefix)
|
|
return node.count if node is not None else 0
|
|
|
|
def __len__(self) -> int:
|
|
# number of distinct words
|
|
out = [0]
|
|
|
|
def dfs(n):
|
|
if n.is_end:
|
|
out[0] += 1
|
|
for c in n.children.values():
|
|
dfs(c)
|
|
|
|
dfs(self.root)
|
|
return out[0]
|
|
|
|
|
|
if __name__ == "__main__":
|
|
t = Trie()
|
|
for w in ["cat", "car", "card", "dog"]:
|
|
t.insert(w)
|
|
print(t.search("car"), t.starts_with("ca"), t.words_with_prefix("ca"))
|
|
t.delete("car")
|
|
print(t.search("car"), t.search("card"))
|