Linked list.

declare const handleType: unique symbol;
export type Handle<T> = Readonly<{ id: number; [handleType]: T }>;
export type Lookup<T> = { found: true; value: T } | { found: false };
export type LinkWrite = {
	node: number | null;
	field: 'head' | 'tail' | 'prev' | 'next';
	from: number | null;
	to: number | null;
};
export type Trace = { visits: number[]; writes: LinkWrite[] };
export type View<T> = {
	head: number | null;
	tail: number | null;
	size: number;
	nodes: { id: number; value: T; prev: number | null; next: number | null }[];
};
type Node<T> = { handle: Handle<T>; value: T; prev: Node<T> | null; next: Node<T> | null };
export class LinkedList<T> {
	#head: Node<T> | null = null;
	#tail: Node<T> | null = null;
	#size = 0;
	#nextId = 1;
	#nodes = new WeakMap<Handle<T>, Node<T>>();
	#trace: Trace = { visits: [], writes: [] };
	constructor(private readonly captureTrace = false) {}
	get size() {
		return this.#size;
	}
	front(): Handle<T> | null {
		return this.#head?.handle ?? null;
	}
	back(): Handle<T> | null {
		return this.#tail?.handle ?? null;
	}
	has(handle: Handle<T>): boolean {
		return this.#nodes.has(handle);
	}
	#begin() {
		this.#trace = { visits: [], writes: [] };
	}
	#record(
		node: Node<T> | null,
		field: LinkWrite['field'],
		from: Node<T> | null,
		to: Node<T> | null
	) {
		if (this.captureTrace && from !== to)
			this.#trace.writes.push({
				node: node?.handle.id ?? null,
				field,
				from: from?.handle.id ?? null,
				to: to?.handle.id ?? null
			});
	}
	#end(field: 'head' | 'tail', to: Node<T> | null) {
		this.#record(null, field, field === 'head' ? this.#head : this.#tail, to);
		if (field === 'head') this.#head = to;
		else this.#tail = to;
	}
	#link(node: Node<T>, field: 'prev' | 'next', to: Node<T> | null) {
		this.#record(node, field, node[field], to);
		node[field] = to;
	}
	#attach(node: Node<T>, after: Node<T> | null) {
		const next = after ? after.next : this.#head;
		this.#link(node, 'prev', after);
		this.#link(node, 'next', next);
		if (after) this.#link(after, 'next', node);
		else this.#end('head', node);
		if (next) this.#link(next, 'prev', node);
		else this.#end('tail', node);
	}
	#detach(node: Node<T>) {
		if (node.prev) this.#link(node.prev, 'next', node.next);
		else this.#end('head', node.next);
		if (node.next) this.#link(node.next, 'prev', node.prev);
		else this.#end('tail', node.prev);
	}
	insertAfter(after: Handle<T> | null, value: T): Handle<T> | null {
		this.#begin();
		const anchor = after === null ? null : this.#nodes.get(after);
		if (anchor === undefined) return null;
		const handle = Object.freeze({ id: this.#nextId++ }) as Handle<T>;
		const node: Node<T> = { handle, value, prev: null, next: null };
		this.#nodes.set(handle, node);
		this.#attach(node, anchor);
		this.#size++;
		return handle;
	}
	moveAfter(handle: Handle<T>, after: Handle<T> | null): 'moved' | 'unchanged' | 'invalid-handle' {
		this.#begin();
		const node = this.#nodes.get(handle);
		const anchor = after === null ? null : this.#nodes.get(after);
		if (!node || anchor === undefined) return 'invalid-handle';
		if (node === anchor || node.prev === anchor) return 'unchanged';
		this.#detach(node);
		this.#attach(node, anchor);
		return 'moved';
	}
	remove(handle: Handle<T>): Lookup<T> {
		this.#begin();
		const node = this.#nodes.get(handle);
		if (!node) return { found: false };
		this.#detach(node);
		this.#link(node, 'prev', null);
		this.#link(node, 'next', null);
		this.#nodes.delete(handle);
		this.#size--;
		return { found: true, value: node.value };
	}
	find(matches: (value: T) => boolean): Handle<T> | null {
		this.#begin();
		for (let node = this.#head; node; node = node.next) {
			if (this.captureTrace) this.#trace.visits.push(node.handle.id);
			if (matches(node.value)) return node.handle;
		}
		return null;
	}
	// Metadata and outer sequences are independent; arbitrary payloads are not deep-cloned.
	view(): View<T> {
		const nodes: View<T>['nodes'] = [];
		for (let node = this.#head; node; node = node.next)
			nodes.push({
				id: node.handle.id,
				value: node.value,
				prev: node.prev?.handle.id ?? null,
				next: node.next?.handle.id ?? null
			});
		return {
			head: this.#head?.handle.id ?? null,
			tail: this.#tail?.handle.id ?? null,
			size: this.#size,
			nodes
		};
	}
	reverseValues(): T[] {
		const values: T[] = [];
		for (let node = this.#tail; node; node = node.prev) values.push(node.value);
		return values;
	}
	trace(): Trace {
		return {
			visits: [...this.#trace.visits],
			writes: this.#trace.writes.map((write) => ({ ...write }))
		};
	}
}

type Handle[T any] struct {
	id   int
	node *node[T]
}

func (h *Handle[T]) ID() int { return h.id }

type node[T any] struct {
	handle     *Handle[T]
	value      T
	prev, next *node[T]
	owner      *LinkedList[T]
}
type LinkWrite struct {
	Node  *int   `json:"node"`
	Field string `json:"field"`
	From  *int   `json:"from"`
	To    *int   `json:"to"`
}
type Trace struct {
	Visits []int       `json:"visits"`
	Writes []LinkWrite `json:"writes"`
}
type NodeView[T any] struct {
	ID    int  `json:"id"`
	Value T    `json:"value"`
	Prev  *int `json:"prev"`
	Next  *int `json:"next"`
}
type View[T any] struct {
	Head  *int          `json:"head"`
	Tail  *int          `json:"tail"`
	Size  int           `json:"size"`
	Nodes []NodeView[T] `json:"nodes"`
}
type LinkedList[T any] struct {
	head, tail   *node[T]
	size, nextID int
	captureTrace bool
	trace        Trace
}

func NewList[T any](captureTrace bool) *LinkedList[T] {
	return &LinkedList[T]{captureTrace: captureTrace, trace: Trace{[]int{}, []LinkWrite{}}}
}
func (l *LinkedList[T]) Size() int { return l.size }
func (l *LinkedList[T]) Front() *Handle[T] {
	if l.head == nil {
		return nil
	}
	return l.head.handle
}
func (l *LinkedList[T]) Back() *Handle[T] {
	if l.tail == nil {
		return nil
	}
	return l.tail.handle
}
func (l *LinkedList[T]) Has(h *Handle[T]) bool {
	return h != nil && h.node != nil && h.node.owner == l && h.node.handle == h
}
func nodeID[T any](n *node[T]) *int {
	if n == nil {
		return nil
	}
	id := n.handle.id
	return &id
}
func (l *LinkedList[T]) begin() { l.trace = Trace{[]int{}, []LinkWrite{}} }
func (l *LinkedList[T]) record(n *node[T], field string, from, to *node[T]) {
	if l.captureTrace && from != to {
		l.trace.Writes = append(l.trace.Writes, LinkWrite{nodeID(n), field, nodeID(from), nodeID(to)})
	}
}
func (l *LinkedList[T]) end(field string, to *node[T]) {
	if field == "head" {
		l.record(nil, field, l.head, to)
		l.head = to
	} else {
		l.record(nil, field, l.tail, to)
		l.tail = to
	}
}
func (l *LinkedList[T]) link(n *node[T], field string, to *node[T]) {
	if field == "prev" {
		l.record(n, field, n.prev, to)
		n.prev = to
	} else {
		l.record(n, field, n.next, to)
		n.next = to
	}
}
func (l *LinkedList[T]) attach(n, after *node[T]) {
	next := l.head
	if after != nil {
		next = after.next
	}
	l.link(n, "prev", after)
	l.link(n, "next", next)
	if after != nil {
		l.link(after, "next", n)
	} else {
		l.end("head", n)
	}
	if next != nil {
		l.link(next, "prev", n)
	} else {
		l.end("tail", n)
	}
}
func (l *LinkedList[T]) detach(n *node[T]) {
	if n.prev != nil {
		l.link(n.prev, "next", n.next)
	} else {
		l.end("head", n.next)
	}
	if n.next != nil {
		l.link(n.next, "prev", n.prev)
	} else {
		l.end("tail", n.prev)
	}
}
func (l *LinkedList[T]) InsertAfter(after *Handle[T], value T) *Handle[T] {
	l.begin()
	var anchor *node[T]
	if after != nil {
		if !l.Has(after) {
			return nil
		}
		anchor = after.node
	}
	l.nextID++
	h := &Handle[T]{id: l.nextID}
	n := &node[T]{handle: h, value: value, owner: l}
	h.node = n
	l.attach(n, anchor)
	l.size++
	return h
}
func (l *LinkedList[T]) MoveAfter(h, after *Handle[T]) string {
	l.begin()
	if !l.Has(h) || (after != nil && !l.Has(after)) {
		return "invalid-handle"
	}
	var anchor *node[T]
	if after != nil {
		anchor = after.node
	}
	n := h.node
	if n == anchor || n.prev == anchor {
		return "unchanged"
	}
	l.detach(n)
	l.attach(n, anchor)
	return "moved"
}
func (l *LinkedList[T]) Remove(h *Handle[T]) (T, bool) {
	l.begin()
	var zero T
	if !l.Has(h) {
		return zero, false
	}
	n := h.node
	l.detach(n)
	l.link(n, "prev", nil)
	l.link(n, "next", nil)
	value := n.value
	n.value = zero
	n.owner = nil
	l.size--
	return value, true
}
func (l *LinkedList[T]) Find(matches func(T) bool) *Handle[T] {
	l.begin()
	for n := l.head; n != nil; n = n.next {
		if l.captureTrace {
			l.trace.Visits = append(l.trace.Visits, n.handle.id)
		}
		if matches(n.value) {
			return n.handle
		}
	}
	return nil
}
func (l *LinkedList[T]) View() View[T] {
	view := View[T]{nodeID(l.head), nodeID(l.tail), l.size, []NodeView[T]{}}
	for n := l.head; n != nil; n = n.next {
		view.Nodes = append(view.Nodes, NodeView[T]{n.handle.id, n.value, nodeID(n.prev), nodeID(n.next)})
	}
	return view
}
func (l *LinkedList[T]) ReverseValues() []T {
	values := []T{}
	for n := l.tail; n != nil; n = n.prev {
		values = append(values, n.value)
	}
	return values
}
func copyID(id *int) *int {
	if id == nil {
		return nil
	}
	value := *id
	return &value
}
func copyTrace(trace Trace) Trace {
	out := Trace{append([]int{}, trace.Visits...), []LinkWrite{}}
	for _, w := range trace.Writes {
		out.Writes = append(out.Writes, LinkWrite{copyID(w.Node), w.Field, copyID(w.From), copyID(w.To)})
	}
	return out
}
func (l *LinkedList[T]) Trace() Trace { return copyTrace(l.trace) }