Trie.

export type Step = {
	/**
	 * walk: follow a child that exists. miss: the child is not there. create: add a node.
	 * mark or unmark: a word ends here, or no longer does. visit: look at a node while
	 * completing. emit: report a word. prune: delete a node no word uses.
	 */
	kind: 'walk' | 'miss' | 'create' | 'mark' | 'unmark' | 'visit' | 'emit' | 'prune';
	/** The characters from the root to the node involved. */
	path: string;
};

type Node = { children: Map<string, Node>; end: boolean };
const newNode = (): Node => ({ children: new Map(), end: false });
const byCodePoint = (a: string, b: string) => a.codePointAt(0)! - b.codePointAt(0)!;

// A trie stores words one character per level, from a shared root. Words that start the same
// share the same first nodes, so everything starting with a prefix hangs below one node: walk
// down the prefix, then read what is below. The walk costs the prefix's length, however many
// other words the trie holds.
export class Trie {
	#root = newNode();
	#size = 0;
	#nodes = 0;

	// Returns false when the word was already there.
	insert(word: string, steps?: Step[]): boolean {
		let at = this.#root;
		let path = '';
		for (const ch of word) {
			path += ch;
			let next = at.children.get(ch);
			if (next) steps?.push({ kind: 'walk', path });
			else {
				next = newNode();
				at.children.set(ch, next);
				this.#nodes++;
				steps?.push({ kind: 'create', path });
			}
			at = next;
		}
		if (at.end) return false;
		at.end = true;
		this.#size++;
		steps?.push({ kind: 'mark', path: word });
		return true;
	}

	has(word: string, steps?: Step[]): boolean {
		return this.#walk(word, steps)?.end ?? false;
	}

	hasPrefix(prefix: string, steps?: Step[]): boolean {
		return this.#walk(prefix, steps) !== null;
	}

	/** Words that start with the prefix, in character order, shorter first, up to `limit`. */
	complete(prefix: string, limit: number, steps?: Step[]): string[] {
		if (!Number.isInteger(limit) || limit < 1 || limit > 10_000)
			throw new RangeError('limit must be a whole number from 1 to 10000');
		const found: string[] = [];
		const visit = (at: Node, path: string): boolean => {
			steps?.push({ kind: 'visit', path });
			if (at.end) {
				found.push(path);
				steps?.push({ kind: 'emit', path });
				if (found.length === limit) return true;
			}
			for (const ch of [...at.children.keys()].sort(byCodePoint))
				if (visit(at.children.get(ch)!, path + ch)) return true;
			return false;
		};
		const start = this.#walk(prefix, steps);
		if (start) visit(start, prefix);
		return found;
	}

	// Remove a word, then delete the nodes only it used, from its last character back toward
	// the root, stopping at a node that ends another word or leads to one. Returns false when
	// the word was not there.
	remove(word: string, steps?: Step[]): boolean {
		const trail: { parent: Node; ch: string; child: Node; path: string }[] = [];
		let at = this.#root;
		let path = '';
		for (const ch of word) {
			path += ch;
			const next = at.children.get(ch);
			if (!next) {
				steps?.push({ kind: 'miss', path });
				return false;
			}
			steps?.push({ kind: 'walk', path });
			trail.push({ parent: at, ch, child: next, path });
			at = next;
		}
		if (!at.end) return false;
		at.end = false;
		this.#size--;
		steps?.push({ kind: 'unmark', path: word });
		for (const { parent, ch, child, path: pruned } of trail.reverse()) {
			if (child.end || child.children.size > 0) break;
			parent.children.delete(ch);
			this.#nodes--;
			steps?.push({ kind: 'prune', path: pruned });
		}
		return true;
	}

	/** Every word, in character order. */
	words(): string[] {
		const found: string[] = [];
		const collect = (at: Node, path: string) => {
			if (at.end) found.push(path);
			for (const ch of [...at.children.keys()].sort(byCodePoint))
				collect(at.children.get(ch)!, path + ch);
		};
		collect(this.#root, '');
		return found;
	}

	get size(): number {
		return this.#size;
	}

	/** Nodes below the root: one per distinct prefix of the words. */
	get nodeCount(): number {
		return this.#nodes;
	}

	#walk(prefix: string, steps?: Step[]): Node | null {
		let at = this.#root;
		let path = '';
		for (const ch of prefix) {
			path += ch;
			const next = at.children.get(ch);
			if (!next) {
				steps?.push({ kind: 'miss', path });
				return null;
			}
			steps?.push({ kind: 'walk', path });
			at = next;
		}
		return at;
	}
}

// Step is one move. Kind is "walk" (follow a child that exists), "miss" (the child is not
// there), "create" (add a node), "mark" or "unmark" (a word ends here, or no longer does),
// "visit" (look at a node while completing), "emit" (report a word), or "prune" (delete a
// node no word uses). Path is the characters from the root to the node involved.
type Step struct {
	Kind string `json:"kind"`
	Path string `json:"path"`
}

type node struct {
	children map[rune]*node
	end      bool
}

func newNode() *node { return &node{children: map[rune]*node{}} }

func record(steps *[]Step, kind, path string) {
	if steps != nil {
		*steps = append(*steps, Step{kind, path})
	}
}

// Trie stores words one character per level, from a shared root. Words that start the
// same share the same first nodes, so everything starting with a prefix hangs below one
// node: walk down the prefix, then read what is below. The walk costs the prefix's length,
// however many other words the trie holds.
type Trie struct {
	root  *node
	size  int
	nodes int
}

func NewTrie() *Trie { return &Trie{root: newNode()} }

// Insert returns false when the word was already there.
func (t *Trie) Insert(word string, steps *[]Step) bool {
	at, path := t.root, ""
	for _, ch := range word {
		path += string(ch)
		next, ok := at.children[ch]
		if ok {
			record(steps, "walk", path)
		} else {
			next = newNode()
			at.children[ch] = next
			t.nodes++
			record(steps, "create", path)
		}
		at = next
	}
	if at.end {
		return false
	}
	at.end = true
	t.size++
	record(steps, "mark", word)
	return true
}

func (t *Trie) Has(word string, steps *[]Step) bool {
	at := t.walk(word, steps)
	return at != nil && at.end
}

func (t *Trie) HasPrefix(prefix string, steps *[]Step) bool {
	return t.walk(prefix, steps) != nil
}

// Complete returns words that start with the prefix, in character order, shorter first,
// up to limit.
func (t *Trie) Complete(prefix string, limit int, steps *[]Step) ([]string, error) {
	if limit < 1 || limit > 10_000 {
		return nil, errors.New("limit must be a whole number from 1 to 10000")
	}
	found := []string{}
	var visit func(at *node, path string) bool
	visit = func(at *node, path string) bool {
		record(steps, "visit", path)
		if at.end {
			found = append(found, path)
			record(steps, "emit", path)
			if len(found) == limit {
				return true
			}
		}
		for _, ch := range sortedKeys(at) {
			if visit(at.children[ch], path+string(ch)) {
				return true
			}
		}
		return false
	}
	if start := t.walk(prefix, steps); start != nil {
		visit(start, prefix)
	}
	return found, nil
}

// Remove removes a word, then deletes the nodes only it used, from its last character back
// toward the root, stopping at a node that ends another word or leads to one. It returns
// false when the word was not there.
func (t *Trie) Remove(word string, steps *[]Step) bool {
	type link struct {
		parent, child *node
		ch            rune
		path          string
	}
	var trail []link
	at, path := t.root, ""
	for _, ch := range word {
		path += string(ch)
		next, ok := at.children[ch]
		if !ok {
			record(steps, "miss", path)
			return false
		}
		record(steps, "walk", path)
		trail = append(trail, link{at, next, ch, path})
		at = next
	}
	if !at.end {
		return false
	}
	at.end = false
	t.size--
	record(steps, "unmark", word)
	for _, l := range slices.Backward(trail) {
		if l.child.end || len(l.child.children) > 0 {
			break
		}
		delete(l.parent.children, l.ch)
		t.nodes--
		record(steps, "prune", l.path)
	}
	return true
}

// Words returns every word, in character order.
func (t *Trie) Words() []string {
	found := []string{}
	var collect func(at *node, path string)
	collect = func(at *node, path string) {
		if at.end {
			found = append(found, path)
		}
		for _, ch := range sortedKeys(at) {
			collect(at.children[ch], path+string(ch))
		}
	}
	collect(t.root, "")
	return found
}

func (t *Trie) Size() int { return t.size }

// NodeCount counts nodes below the root: one per distinct prefix of the words.
func (t *Trie) NodeCount() int { return t.nodes }

func (t *Trie) walk(prefix string, steps *[]Step) *node {
	at, path := t.root, ""
	for _, ch := range prefix {
		path += string(ch)
		next, ok := at.children[ch]
		if !ok {
			record(steps, "miss", path)
			return nil
		}
		record(steps, "walk", path)
		at = next
	}
	return at
}

func sortedKeys(at *node) []rune {
	keys := make([]rune, 0, len(at.children))
	for ch := range at.children {
		keys = append(keys, ch)
	}
	slices.Sort(keys)
	return keys
}