Ordered map.

export type Step = {
	/**
	 * right: move along a level to this node, whose key is still smaller. down: drop a level at
	 * this node, or at the head when `at` is null. found: the key is here. link or unlink: add
	 * or remove this node on one level. visit: read a node in key order.
	 */
	kind: 'right' | 'down' | 'found' | 'link' | 'unlink' | 'visit';
	at: number | null;
	level: number;
};

export type Entry<V> = { key: number; value: V };
type Node<V> = { key: number; value: V; next: (Node<V> | null)[] };

const MAX_LEVEL = 16;
const SEED = 2463534242;

function checkKey(key: number) {
	if (!Number.isSafeInteger(key)) throw new RangeError('key must be a safe integer');
}

// An ordered map keeps its keys sorted, so it can answer more than "what is stored here":
// the nearest key at or below a value, the nearest at or above, and every key in a range.
// This one is a skip list. Every key sits on the bottom level in order; about half also sit
// on the level above, a quarter on the next, and so on, decided by coin flips. A search runs
// along the top level while the next key is still smaller, then drops a level and repeats,
// skipping most keys on the way down.
export class SkipListMap<V> {
	#head: Node<V> = { key: 0, value: undefined as V, next: Array(MAX_LEVEL).fill(null) };
	#level = 1;
	#size = 0;
	// The coin: xorshift32 from a fixed seed, so every run, and the Go version, flips the same.
	#state = SEED;

	set(key: number, value: V, steps?: Step[]): boolean {
		checkKey(key);
		const { update, next } = this.#search(key, steps);
		if (next?.key === key) {
			steps?.push({ kind: 'found', at: key, level: 0 });
			next.value = value;
			return false;
		}
		const height = this.#randomHeight();
		this.#level = Math.max(this.#level, height);
		const node: Node<V> = { key, value, next: Array(height).fill(null) };
		for (let level = 0; level < height; level++) {
			node.next[level] = update[level].next[level];
			update[level].next[level] = node;
			steps?.push({ kind: 'link', at: key, level });
		}
		this.#size++;
		return true;
	}

	get(key: number, steps?: Step[]): V | undefined {
		checkKey(key);
		const { next } = this.#search(key, steps);
		if (next?.key !== key) return undefined;
		steps?.push({ kind: 'found', at: key, level: 0 });
		return next.value;
	}

	delete(key: number, steps?: Step[]): boolean {
		checkKey(key);
		const { update, next } = this.#search(key, steps);
		if (!next || next.key !== key) return false;
		steps?.push({ kind: 'found', at: key, level: 0 });
		for (let level = 0; level < next.next.length; level++) {
			update[level].next[level] = next.next[level];
			steps?.push({ kind: 'unlink', at: key, level });
		}
		while (this.#level > 1 && !this.#head.next[this.#level - 1]) this.#level--;
		this.#size--;
		return true;
	}

	/** The entry with the largest key at or below `key`, or null. */
	floor(key: number, steps?: Step[]): Entry<V> | null {
		checkKey(key);
		const { update, next } = this.#search(key, steps);
		if (next?.key === key) {
			steps?.push({ kind: 'found', at: key, level: 0 });
			return { key, value: next.value };
		}
		const below = update[0];
		return below === this.#head ? null : { key: below.key, value: below.value };
	}

	/** The entry with the smallest key at or above `key`, or null. */
	ceiling(key: number, steps?: Step[]): Entry<V> | null {
		checkKey(key);
		const { next } = this.#search(key, steps);
		if (!next) return null;
		if (next.key === key) steps?.push({ kind: 'found', at: key, level: 0 });
		return { key: next.key, value: next.value };
	}

	/** Up to `limit` entries with `from <= key < to`, in key order. */
	range(from: number, to: number, limit: number, steps?: Step[]): Entry<V>[] {
		checkKey(from);
		checkKey(to);
		if (!Number.isInteger(limit) || limit < 1 || limit > 10_000)
			throw new RangeError('limit must be a whole number from 1 to 10000');
		const found: Entry<V>[] = [];
		let node = this.#search(from, steps).next;
		for (; node && node.key < to && found.length < limit; node = node.next[0]) {
			steps?.push({ kind: 'visit', at: node.key, level: 0 });
			found.push({ key: node.key, value: node.value });
		}
		return found;
	}

	/** Every key in order with the height of its tower, for drawing. */
	towers(): { key: number; height: number }[] {
		const found: { key: number; height: number }[] = [];
		for (let node = this.#head.next[0]; node; node = node.next[0])
			found.push({ key: node.key, height: node.next.length });
		return found;
	}

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

	/** Levels in use: the tallest tower, and at least 1. */
	get levels(): number {
		return this.#level;
	}

	// From the top level down, move right while the next key is smaller. `update` remembers
	// the last node on each level, which is where a new node would be linked in.
	#search(key: number, steps?: Step[]) {
		const update: Node<V>[] = Array(MAX_LEVEL).fill(this.#head);
		let node = this.#head;
		for (let level = this.#level - 1; level >= 0; level--) {
			for (let next = node.next[level]; next && next.key < key; next = node.next[level]) {
				node = next;
				steps?.push({ kind: 'right', at: node.key, level });
			}
			update[level] = node;
			if (level > 0)
				steps?.push({ kind: 'down', at: node === this.#head ? null : node.key, level });
		}
		return { update, next: node.next[0] };
	}

	// Each head on the coin raises the tower one more level, so about half the keys reach
	// level 2, a quarter level 3, and so on.
	#randomHeight(): number {
		let height = 1;
		while (height < MAX_LEVEL && (this.#flip() & 1) === 1) height++;
		return height;
	}

	#flip(): number {
		let x = this.#state;
		x ^= x << 13;
		x ^= x >>> 17;
		x ^= x << 5;
		this.#state = x >>> 0;
		return this.#state;
	}
}

// Step is one move. Kind is "right" (move along a level to this node, whose key is still
// smaller), "down" (drop a level at this node, or at the head when Head is true), "found"
// (the key is here), "link" or "unlink" (add or remove this node on one level), or "visit"
// (read a node in key order).
type Step struct {
	Kind  string `json:"kind"`
	At    int    `json:"at"`
	Head  bool   `json:"head,omitempty"`
	Level int    `json:"level"`
}

type Entry[V any] struct {
	Key   int
	Value V
}

type Tower struct {
	Key, Height int
}

type node[V any] struct {
	key   int
	value V
	next  []*node[V]
}

const (
	maxLevel = 16
	seed     = 2463534242
)

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

// SkipMap is an ordered map: it keeps its keys sorted, so it can answer more than "what is
// stored here": the nearest key at or below a value, the nearest at or above, and every key
// in a range. It is a skip list. Every key sits on the bottom level in order; about half
// also sit on the level above, a quarter on the next, and so on, decided by coin flips. A
// search runs along the top level while the next key is still smaller, then drops a level
// and repeats, skipping most keys on the way down.
type SkipMap[V any] struct {
	head  *node[V]
	level int
	size  int
	// The coin: xorshift32 from a fixed seed, so every run, and the TypeScript version, flips the same.
	state uint32
}

func NewSkipMap[V any]() *SkipMap[V] {
	return &SkipMap[V]{head: &node[V]{next: make([]*node[V], maxLevel)}, level: 1, state: seed}
}

// Set returns false when the key was already there; its value is replaced.
func (m *SkipMap[V]) Set(key int, value V, steps *[]Step) bool {
	update, next := m.search(key, steps)
	if next != nil && next.key == key {
		record(steps, Step{Kind: "found", At: key})
		next.value = value
		return false
	}
	height := m.randomHeight()
	m.level = max(m.level, height)
	fresh := &node[V]{key: key, value: value, next: make([]*node[V], height)}
	for level := range height {
		fresh.next[level] = update[level].next[level]
		update[level].next[level] = fresh
		record(steps, Step{Kind: "link", At: key, Level: level})
	}
	m.size++
	return true
}

func (m *SkipMap[V]) Get(key int, steps *[]Step) (V, bool) {
	_, next := m.search(key, steps)
	if next == nil || next.key != key {
		var zero V
		return zero, false
	}
	record(steps, Step{Kind: "found", At: key})
	return next.value, true
}

func (m *SkipMap[V]) Delete(key int, steps *[]Step) bool {
	update, next := m.search(key, steps)
	if next == nil || next.key != key {
		return false
	}
	record(steps, Step{Kind: "found", At: key})
	for level := range next.next {
		update[level].next[level] = next.next[level]
		record(steps, Step{Kind: "unlink", At: key, Level: level})
	}
	for m.level > 1 && m.head.next[m.level-1] == nil {
		m.level--
	}
	m.size--
	return true
}

// Floor returns the entry with the largest key at or below key.
func (m *SkipMap[V]) Floor(key int, steps *[]Step) (Entry[V], bool) {
	update, next := m.search(key, steps)
	if next != nil && next.key == key {
		record(steps, Step{Kind: "found", At: key})
		return Entry[V]{key, next.value}, true
	}
	if below := update[0]; below != m.head {
		return Entry[V]{below.key, below.value}, true
	}
	return Entry[V]{}, false
}

// Ceiling returns the entry with the smallest key at or above key.
func (m *SkipMap[V]) Ceiling(key int, steps *[]Step) (Entry[V], bool) {
	_, next := m.search(key, steps)
	if next == nil {
		return Entry[V]{}, false
	}
	if next.key == key {
		record(steps, Step{Kind: "found", At: key})
	}
	return Entry[V]{next.key, next.value}, true
}

// Range returns up to limit entries with from <= key < to, in key order.
func (m *SkipMap[V]) Range(from, to, limit int, steps *[]Step) ([]Entry[V], error) {
	if limit < 1 || limit > 10_000 {
		return nil, errors.New("limit must be a whole number from 1 to 10000")
	}
	found := []Entry[V]{}
	_, n := m.search(from, steps)
	for ; n != nil && n.key < to && len(found) < limit; n = n.next[0] {
		record(steps, Step{Kind: "visit", At: n.key})
		found = append(found, Entry[V]{n.key, n.value})
	}
	return found, nil
}

// Towers lists every key in order with the height of its tower, for drawing.
func (m *SkipMap[V]) Towers() []Tower {
	found := []Tower{}
	for n := m.head.next[0]; n != nil; n = n.next[0] {
		found = append(found, Tower{n.key, len(n.next)})
	}
	return found
}

func (m *SkipMap[V]) Size() int { return m.size }

// Levels counts levels in use: the tallest tower, and at least 1.
func (m *SkipMap[V]) Levels() int { return m.level }

// search moves right on each level, from the top down, while the next key is smaller.
// update remembers the last node on each level, which is where a new node would be linked in.
func (m *SkipMap[V]) search(key int, steps *[]Step) ([maxLevel]*node[V], *node[V]) {
	var update [maxLevel]*node[V]
	for i := range update {
		update[i] = m.head
	}
	n := m.head
	for level := m.level - 1; level >= 0; level-- {
		for next := n.next[level]; next != nil && next.key < key; next = n.next[level] {
			n = next
			record(steps, Step{Kind: "right", At: n.key, Level: level})
		}
		update[level] = n
		if level > 0 {
			record(steps, Step{Kind: "down", At: n.key, Head: n == m.head, Level: level})
		}
	}
	return update, n.next[0]
}

// randomHeight raises the tower one more level for each head on the coin, so about half the
// keys reach level 2, a quarter level 3, and so on.
func (m *SkipMap[V]) randomHeight() int {
	height := 1
	for height < maxLevel && m.flip()&1 == 1 {
		height++
	}
	return height
}

func (m *SkipMap[V]) flip() uint32 {
	x := m.state
	x ^= x << 13
	x ^= x >> 17
	x ^= x << 5
	m.state = x
	return x
}