Skip List Sort

import { treeGraph } from './graph';
import type { NumericTrace } from './trace';
import type { GraphSnapshot } from './types';

type BinaryNode = {
	id: string;
	value: number;
	count: number;
	left: BinaryNode | null;
	right: BinaryNode | null;
};

function binarySnapshot(root: BinaryNode | null): GraphSnapshot {
	return treeGraph(root, {
		id: (node) => node.id,
		value: (node) => node.value,
		left: (node) => node.left,
		right: (node) => node.right,
		label: (node) => (node.count > 1 ? `×${node.count}` : undefined)
	});
}

function emitInOrder(trace: NumericTrace, root: BinaryNode | null) {
	let output = 0;
	function visit(node: BinaryNode | null) {
		if (!node) return;
		visit(node.left);
		for (let i = 0; i < node.count; i++) {
			trace.focus(`Visit tree node ${node.value}`, [node.id]);
			trace.write(output++, node.value);
		}
		visit(node.right);
	}
	visit(root);
}

export function splaySort(trace: NumericTrace) {
	function rotateRight(root: BinaryNode) {
		const child = root.left as BinaryNode;
		root.left = child.right;
		child.right = root;
		trace.note(`Rotate ${child.value} above ${root.value}`);
		return child;
	}
	function rotateLeft(root: BinaryNode) {
		const child = root.right as BinaryNode;
		root.right = child.left;
		child.left = root;
		trace.note(`Rotate ${child.value} above ${root.value}`);
		return child;
	}
	function splay(root: BinaryNode | null, value: number): BinaryNode | null {
		if (!root || root.value === value) return root;
		if (value < root.value) {
			if (!root.left) return root;
			if (value < root.left.value) {
				root.left.left = splay(root.left.left, value);
				root = rotateRight(root);
			} else if (value > root.left.value) {
				root.left.right = splay(root.left.right, value);
				if (root.left.right) root.left = rotateLeft(root.left);
			}
			return root.left ? rotateRight(root) : root;
		}
		if (!root.right) return root;
		if (value > root.right.value) {
			root.right.right = splay(root.right.right, value);
			root = rotateLeft(root);
		} else if (value < root.right.value) {
			root.right.left = splay(root.right.left, value);
			if (root.right.left) root.right = rotateRight(root.right);
		}
		return root.right ? rotateLeft(root) : root;
	}
	let root: BinaryNode | null = null;
	for (const [inputIndex, value] of [...trace.array].entries()) {
		root = splay(root, value);
		if (!root) {
			root = { id: `splay-${inputIndex}`, value, count: 1, left: null, right: null };
		} else if (root.value === value) {
			root.count++;
		} else {
			const node: BinaryNode = {
				id: `splay-${inputIndex}`,
				value,
				count: 1,
				left: null,
				right: null
			};
			if (value < root.value) {
				node.left = root.left;
				root.left = null;
				node.right = root;
			} else {
				node.right = root.right;
				root.right = null;
				node.left = root;
			}
			root = node;
		}
		trace.structure(`Insert ${value} into splay tree`, () => binarySnapshot(root), [root.id]);
	}
	emitInOrder(trace, root);
}

type TreapNode = BinaryNode & { priority: number };

export function treapSort(trace: NumericTrace) {
	function rotateRight(root: TreapNode): TreapNode {
		const child = root.left as TreapNode;
		root.left = child.right;
		child.right = root;
		trace.note(`Treap rotate right at ${root.value}`);
		return child;
	}
	function rotateLeft(root: TreapNode): TreapNode {
		const child = root.right as TreapNode;
		root.right = child.left;
		child.left = root;
		trace.note(`Treap rotate left at ${root.value}`);
		return child;
	}
	function insert(root: TreapNode | null, value: number, id: string): TreapNode {
		if (!root) return { id, value, priority: Math.random(), count: 1, left: null, right: null };
		if (value === root.value) {
			root.count++;
		} else if (value < root.value) {
			root.left = insert(root.left as TreapNode | null, value, id);
			if ((root.left as TreapNode).priority < root.priority) root = rotateRight(root);
		} else {
			root.right = insert(root.right as TreapNode | null, value, id);
			if ((root.right as TreapNode).priority < root.priority) root = rotateLeft(root);
		}
		return root;
	}
	let root: TreapNode | null = null;
	for (const [inputIndex, value] of [...trace.array].entries()) {
		root = insert(root, value, `treap-${inputIndex}`);
		trace.structure(
			`Insert ${value} with randomized heap priority`,
			() =>
				treeGraph(root, {
					id: (node) => node.id,
					value: (node) => node.value,
					left: (node) => node.left as TreapNode | null,
					right: (node) => node.right as TreapNode | null,
					label: (node) => (node.count > 1 ? `×${node.count}` : `p=${node.priority.toFixed(2)}`)
				}),
			[root.id]
		);
	}
	emitInOrder(trace, root);
}

type CartesianNode = {
	id: string;
	value: number;
	left: CartesianNode | null;
	right: CartesianNode | null;
};

export function cartesianTreeSort(trace: NumericTrace) {
	const stack: CartesianNode[] = [];
	for (const [inputIndex, value] of [...trace.array].entries()) {
		const node: CartesianNode = { id: `cart-${inputIndex}`, value, left: null, right: null };
		let last: CartesianNode | null = null;
		while (stack.length && stack[stack.length - 1].value > value) {
			last = stack.pop() as CartesianNode;
		}
		node.left = last;
		if (stack.length) stack[stack.length - 1].right = node;
		stack.push(node);
		trace.structure(
			`Add ${value} to the min Cartesian tree`,
			() =>
				treeGraph(stack[0], {
					id: (item) => item.id,
					value: (item) => item.value,
					left: (item) => item.left,
					right: (item) => item.right
				}),
			[node.id]
		);
	}
	if (!stack.length) return;
	const heap: CartesianNode[] = [];
	function push(node: CartesianNode) {
		heap.push(node);
		let index = heap.length - 1;
		while (index > 0) {
			const parent = Math.floor((index - 1) / 2);
			if (heap[parent].value <= heap[index].value) break;
			[heap[parent], heap[index]] = [heap[index], heap[parent]];
			index = parent;
		}
	}
	function pop() {
		const first = heap[0];
		const last = heap.pop() as CartesianNode;
		if (heap.length) {
			heap[0] = last;
			let index = 0;
			while (index * 2 + 1 < heap.length) {
				let child = index * 2 + 1;
				if (child + 1 < heap.length && heap[child + 1].value < heap[child].value) child++;
				if (heap[index].value <= heap[child].value) break;
				[heap[index], heap[child]] = [heap[child], heap[index]];
				index = child;
			}
		}
		return first;
	}
	push(stack[0]);
	for (let output = 0; heap.length; output++) {
		const node = pop();
		trace.focus(`Extract Cartesian tree minimum ${node.value}`, [node.id]);
		trace.write(output, node.value, `Extract Cartesian tree minimum ${node.value}`);
		if (node.left) push(node.left);
		if (node.right) push(node.right);
	}
}

type SkipNode = { id: string; value: number; next: Array<SkipNode | null> };

function skipListGraph(head: SkipNode, height: number): GraphSnapshot {
	const base: SkipNode[] = [];
	for (let node: SkipNode | null = head; node; node = node.next[0]) base.push(node);
	const positions = new Map(base.map((node, index) => [node.id, index]));
	const nodes: GraphSnapshot['nodes'] = [];
	const edges: GraphSnapshot['edges'] = [];
	for (const node of base) {
		for (let level = 0; level < node.next.length && level < height; level++) {
			const id = `${node.id}:${level}`;
			nodes.push({
				id,
				value: node.value,
				label: node.id === 'head' ? 'HEAD' : undefined,
				x: 56 + (positions.get(node.id) as number) * 82,
				y: 52 + (height - level - 1) * 74
			});
			const next = node.next[level];
			if (next) edges.push({ from: id, to: `${next.id}:${level}` });
			if (level > 0) edges.push({ from: id, to: `${node.id}:${level - 1}` });
		}
	}
	return {
		kind: 'skip-list',
		nodes,
		edges,
		width: Math.max(360, base.length * 82 + 56),
		height: Math.max(190, height * 74 + 70)
	};
}

export function skipListSort(trace: NumericTrace) {
	const maxLevel = Math.max(1, Math.ceil(Math.log2(trace.array.length + 1)) + 1);
	const head: SkipNode = { id: 'head', value: -Infinity, next: Array(maxLevel).fill(null) };
	let level = 1;
	for (const [inputIndex, value] of [...trace.array].entries()) {
		const update = Array<SkipNode>(maxLevel).fill(head);
		let cursor = head;
		for (let current = level - 1; current >= 0; current--) {
			while (cursor.next[current] && (cursor.next[current] as SkipNode).value <= value) {
				cursor = cursor.next[current] as SkipNode;
			}
			update[current] = cursor;
		}
		let height = 1;
		while (height < maxLevel && Math.random() < 0.5) height++;
		if (height > level) {
			for (let current = level; current < height; current++) update[current] = head;
			level = height;
		}
		const node: SkipNode = { id: `skip-${inputIndex}`, value, next: Array(height).fill(null) };
		for (let current = 0; current < height; current++) {
			node.next[current] = update[current].next[current];
			update[current].next[current] = node;
		}
		trace.structure(
			`Insert ${value} into skip list at height ${height}`,
			() => skipListGraph(head, level),
			[`${node.id}:0`]
		);
	}
	let cursor = head.next[0];
	let output = 0;
	while (cursor) {
		trace.focus(`Visit skip-list node ${cursor.value}`, [`${cursor.id}:0`]);
		trace.write(output++, cursor.value);
		cursor = cursor.next[0];
	}
}