Triesort

export interface StringSortEvent {
	text: string;
	highlight?: number;
	writes?: Record<number, string>;
	suffixOrder?: number[];
}

export class StringTrace {
	readonly events: StringSortEvent[] = [];

	constructor(readonly values: string[]) {}

	note(text: string, highlight?: number) {
		this.events.push({ text, highlight });
	}

	write(index: number, value: string) {
		this.values[index] = value;
		this.events.push({
			text: `Write “${value}” at index ${index}`,
			highlight: index,
			writes: { [index]: value }
		});
	}
}

type TrieNode = { terminal: string[]; children: Map<string, TrieNode> };

function compareChars(left: string, right: string) {
	return (left.codePointAt(0) as number) - (right.codePointAt(0) as number);
}

function compareStrings(left: string, right: string) {
	const a = Array.from(left);
	const b = Array.from(right);
	for (let index = 0; index < Math.min(a.length, b.length); index++) {
		const difference = compareChars(a[index], b[index]);
		if (difference !== 0) return difference;
	}
	return a.length - b.length;
}

export function trieSort(trace: StringTrace) {
	const root: TrieNode = { terminal: [], children: new Map() };
	for (let index = 0; index < trace.values.length; index++) {
		const value = trace.values[index];
		let node = root;
		for (const character of value) {
			let child = node.children.get(character);
			if (!child) {
				child = { terminal: [], children: new Map() };
				node.children.set(character, child);
			}
			node = child;
			trace.note(`Follow trie edge “${character}” for “${value}”`, index);
		}
		node.terminal.push(value);
		trace.note(`Mark “${value}” as a complete trie key`, index);
	}
	let output = 0;
	function visit(node: TrieNode) {
		for (const value of node.terminal) trace.write(output++, value);
		for (const character of [...node.children.keys()].sort(compareChars)) {
			visit(node.children.get(character) as TrieNode);
		}
	}
	visit(root);
}

type BurstNode = {
	depth: number;
	bucket: string[] | null;
	terminal: string[];
	children: Map<string, BurstNode>;
};

/** Burst threshold remains small so the split is visible with short inputs. */
export function burstSort(trace: StringTrace, threshold = 4) {
	const root: BurstNode = { depth: 0, bucket: [], terminal: [], children: new Map() };
	function child(node: BurstNode, character: string) {
		let result = node.children.get(character);
		if (!result) {
			result = { depth: node.depth + 1, bucket: [], terminal: [], children: new Map() };
			node.children.set(character, result);
		}
		return result;
	}
	function insert(node: BurstNode, value: string) {
		if (node.bucket !== null) {
			node.bucket.push(value);
			trace.note(`Place “${value}” in depth-${node.depth} burst bucket`);
			if (node.bucket.length > threshold) {
				const pending = node.bucket;
				node.bucket = null;
				trace.note(`Burst bucket at character depth ${node.depth}`);
				for (const entry of pending) insert(node, entry);
			}
			return;
		}
		const characters = Array.from(value);
		if (node.depth >= characters.length) {
			node.terminal.push(value);
			return;
		}
		insert(child(node, characters[node.depth]), value);
	}
	for (const value of [...trace.values]) insert(root, value);
	let output = 0;
	function visit(node: BurstNode) {
		for (const value of node.terminal) trace.write(output++, value);
		if (node.bucket) {
			// Insertion sort keeps equal strings in their arrival order.
			for (let index = 1; index < node.bucket.length; index++) {
				const value = node.bucket[index];
				let position = index;
				while (position > 0 && compareStrings(node.bucket[position - 1], value) > 0) {
					trace.note(`Compare “${node.bucket[position - 1]}” and “${value}” inside bucket`);
					node.bucket[position] = node.bucket[position - 1];
					position--;
				}
				node.bucket[position] = value;
			}
			for (const value of node.bucket) trace.write(output++, value);
		}
		for (const character of [...node.children.keys()].sort(compareChars)) {
			visit(node.children.get(character) as BurstNode);
		}
	}
	visit(root);
}