Adjacency list.

/**
 * One unit of work. For a list entry, `kind` is read, append, or remove; `owner` owns the
 * list, `list` says which one, and `value` is the node at `index`. For a matrix cell, `kind`
 * is read-cell, set-cell, or clear-cell; `owner` is the row, `value` the column, and `index`
 * the column's position.
 */
export type Step = {
	kind: 'read' | 'append' | 'remove' | 'read-cell' | 'set-cell' | 'clear-cell';
	list: 'out' | 'in' | 'cell';
	owner: string;
	index: number;
	value: string;
};

type Lists = { out: string[]; in: string[] };

// A directed graph as adjacency lists. Each node keeps the nodes its edges go to (out) and
// the nodes whose edges come to it (in), both in the order the edges were added. Keeping
// both costs a second entry per edge and buys incoming edges without scanning every list.
export class AdjacencyList {
	#lists = new Map<string, Lists>();
	#edges = 0;

	has(name: string): boolean {
		return this.#lists.has(name);
	}

	addNode(name: string): void {
		if (this.#lists.has(name)) throw new RangeError(`node ${name} already exists`);
		this.#lists.set(name, { out: [], in: [] });
	}

	hasEdge(from: string, to: string, steps?: Step[]): boolean {
		const [source] = this.#pair(from, to);
		return find(source.out, 'out', from, to, steps) >= 0;
	}

	// Returns false when the edge already exists.
	addEdge(from: string, to: string, steps?: Step[]): boolean {
		const [source, target] = this.#pair(from, to);
		if (find(source.out, 'out', from, to, steps) >= 0) return false;
		steps?.push({ kind: 'append', list: 'out', owner: from, index: source.out.length, value: to });
		source.out.push(to);
		steps?.push({ kind: 'append', list: 'in', owner: to, index: target.in.length, value: from });
		target.in.push(from);
		this.#edges++;
		return true;
	}

	// Returns false when there is no such edge.
	removeEdge(from: string, to: string, steps?: Step[]): boolean {
		const [source, target] = this.#pair(from, to);
		const at = find(source.out, 'out', from, to, steps);
		if (at < 0) return false;
		remove(source.out, 'out', from, at, steps);
		remove(target.in, 'in', to, find(target.in, 'in', to, from, steps), steps);
		this.#edges--;
		return true;
	}

	/** Where a node's edges go, in the order they were added. */
	neighbors(name: string, steps?: Step[]): string[] {
		return readAll(this.#get(name).out, 'out', name, steps);
	}

	/** Where a node's incoming edges come from, in the order they were added. */
	sources(name: string, steps?: Step[]): string[] {
		return readAll(this.#get(name).in, 'in', name, steps);
	}

	// Remove a node and every edge touching it. Its own two lists say exactly which other
	// lists mention it, so no other list is read. Returns how many edges were removed.
	removeNode(name: string, steps?: Step[]): number {
		const { out, in: into } = this.#get(name);
		let removed = 0;
		out.forEach((to, i) => {
			steps?.push({ kind: 'read', list: 'out', owner: name, index: i, value: to });
			removed++;
			if (to === name) return;
			const other = this.#lists.get(to)!.in;
			remove(other, 'in', to, find(other, 'in', to, name, steps), steps);
		});
		into.forEach((from, i) => {
			steps?.push({ kind: 'read', list: 'in', owner: name, index: i, value: from });
			if (from === name) return;
			removed++;
			const other = this.#lists.get(from)!.out;
			remove(other, 'out', from, find(other, 'out', from, name, steps), steps);
		});
		this.#lists.delete(name);
		this.#edges -= removed;
		return removed;
	}

	nodes(): string[] {
		return [...this.#lists.keys()];
	}

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

	#get(name: string): Lists {
		const lists = this.#lists.get(name);
		if (!lists) throw new RangeError(`unknown node ${name}`);
		return lists;
	}

	#pair(from: string, to: string): [Lists, Lists] {
		const source = this.#get(from);
		return [source, this.#get(to)];
	}
}

// Read a list from the front until `target` turns up. Returns its position, or -1.
function find(
	list: string[],
	which: 'out' | 'in',
	owner: string,
	target: string,
	steps?: Step[]
): number {
	for (let i = 0; i < list.length; i++) {
		steps?.push({ kind: 'read', list: which, owner, index: i, value: list[i] });
		if (list[i] === target) return i;
	}
	return -1;
}

function remove(list: string[], which: 'out' | 'in', owner: string, index: number, steps?: Step[]) {
	steps?.push({ kind: 'remove', list: which, owner, index, value: list[index] });
	list.splice(index, 1);
}

function readAll(list: string[], which: 'out' | 'in', owner: string, steps?: Step[]): string[] {
	list.forEach((value, index) => steps?.push({ kind: 'read', list: which, owner, index, value }));
	return [...list];
}

// The same graph as a matrix: one cell per ordered pair of nodes, set when the edge exists.
// Checking one edge reads one cell, but listing a node's edges reads its whole row or
// column, and adding a node copies every cell into a larger matrix.
export class AdjacencyMatrix {
	#index = new Map<string, number>();
	#names: string[] = [];
	#cells = new Uint8Array(0);
	#edges = 0;

	addNode(name: string): void {
		if (this.#index.has(name)) throw new RangeError(`node ${name} already exists`);
		const n = this.#names.length;
		const next = new Uint8Array((n + 1) * (n + 1));
		for (let row = 0; row < n; row++)
			next.set(this.#cells.subarray(row * n, row * n + n), row * (n + 1));
		this.#index.set(name, n);
		this.#names.push(name);
		this.#cells = next;
	}

	hasEdge(from: string, to: string, steps?: Step[]): boolean {
		const [row, column] = this.#pair(from, to);
		return this.#read(row, column, steps);
	}

	addEdge(from: string, to: string, steps?: Step[]): boolean {
		const [row, column] = this.#pair(from, to);
		if (this.#read(row, column, steps)) return false;
		this.#write(row, column, true, steps);
		this.#edges++;
		return true;
	}

	removeEdge(from: string, to: string, steps?: Step[]): boolean {
		const [row, column] = this.#pair(from, to);
		if (!this.#read(row, column, steps)) return false;
		this.#write(row, column, false, steps);
		this.#edges--;
		return true;
	}

	/** Where a node's edges go, in node order: every cell of its row is read. */
	neighbors(name: string, steps?: Step[]): string[] {
		const row = this.#at(name);
		return this.#names.filter((_, column) => this.#read(row, column, steps));
	}

	/** Where a node's incoming edges come from, in node order: every cell of its column is read. */
	sources(name: string, steps?: Step[]): string[] {
		const column = this.#at(name);
		return this.#names.filter((_, row) => this.#read(row, column, steps));
	}

	removeNode(name: string, steps?: Step[]): number {
		const at = this.#at(name);
		const n = this.#names.length;
		let removed = 0;
		for (let column = 0; column < n; column++)
			if (this.#read(at, column, steps)) {
				this.#write(at, column, false, steps);
				removed++;
			}
		for (let row = 0; row < n; row++)
			if (row !== at && this.#read(row, at, steps)) {
				this.#write(row, at, false, steps);
				removed++;
			}
		// Copy every other cell into a matrix one row and one column smaller.
		const next = new Uint8Array((n - 1) * (n - 1));
		let written = 0;
		for (let row = 0; row < n; row++)
			for (let column = 0; column < n; column++)
				if (row !== at && column !== at) next[written++] = this.#cells[row * n + column];
		this.#cells = next;
		this.#names.splice(at, 1);
		this.#index = new Map(this.#names.map((node, i) => [node, i]));
		this.#edges -= removed;
		return removed;
	}

	nodes(): string[] {
		return [...this.#names];
	}

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

	get cellCount(): number {
		return this.#names.length ** 2;
	}

	#at(name: string): number {
		const at = this.#index.get(name);
		if (at === undefined) throw new RangeError(`unknown node ${name}`);
		return at;
	}

	#pair(from: string, to: string): [number, number] {
		const row = this.#at(from);
		return [row, this.#at(to)];
	}

	#read(row: number, column: number, steps?: Step[]): boolean {
		const [owner, value] = [this.#names[row], this.#names[column]];
		steps?.push({ kind: 'read-cell', list: 'cell', owner, index: column, value });
		return this.#cells[row * this.#names.length + column] === 1;
	}

	#write(row: number, column: number, set: boolean, steps?: Step[]): void {
		const [owner, value] = [this.#names[row], this.#names[column]];
		const kind = set ? 'set-cell' : 'clear-cell';
		steps?.push({ kind, list: 'cell', owner, index: column, value });
		this.#cells[row * this.#names.length + column] = set ? 1 : 0;
	}
}

// Step is one unit of work. For a list entry, Kind is "read", "append", or "remove";
// Owner owns the list, List says which one ("out" or "in"), and Value is the node at
// Index. For a matrix cell, Kind is "read-cell", "set-cell", or "clear-cell"; List is
// "cell", Owner is the row, Value the column, and Index the column's position.
type Step struct {
	Kind  string `json:"kind"`
	List  string `json:"list"`
	Owner string `json:"owner"`
	Index int    `json:"index"`
	Value string `json:"value"`
}

func record(steps *[]Step, kind, list, owner string, index int, value string) {
	if steps != nil {
		*steps = append(*steps, Step{kind, list, owner, index, value})
	}
}

type lists struct{ out, in []string }

// AdjacencyList is a directed graph as adjacency lists. Each node keeps the nodes its
// edges go to (out) and the nodes whose edges come to it (in), both in the order the
// edges were added. Keeping both costs a second entry per edge and buys incoming edges
// without scanning every list.
type AdjacencyList struct {
	lists map[string]*lists
	order []string
	edges int
}

func NewAdjacencyList() *AdjacencyList {
	return &AdjacencyList{lists: map[string]*lists{}}
}

func (g *AdjacencyList) Has(name string) bool {
	_, ok := g.lists[name]
	return ok
}

func (g *AdjacencyList) AddNode(name string) error {
	if g.Has(name) {
		return fmt.Errorf("node %s already exists", name)
	}
	g.lists[name] = &lists{}
	g.order = append(g.order, name)
	return nil
}

func (g *AdjacencyList) HasEdge(from, to string, steps *[]Step) (bool, error) {
	source, _, err := g.pair(from, to)
	if err != nil {
		return false, err
	}
	return find(source.out, "out", from, to, steps) >= 0, nil
}

// AddEdge returns false when the edge already exists.
func (g *AdjacencyList) AddEdge(from, to string, steps *[]Step) (bool, error) {
	source, target, err := g.pair(from, to)
	if err != nil {
		return false, err
	}
	if find(source.out, "out", from, to, steps) >= 0 {
		return false, nil
	}
	record(steps, "append", "out", from, len(source.out), to)
	source.out = append(source.out, to)
	record(steps, "append", "in", to, len(target.in), from)
	target.in = append(target.in, from)
	g.edges++
	return true, nil
}

// RemoveEdge returns false when there is no such edge.
func (g *AdjacencyList) RemoveEdge(from, to string, steps *[]Step) (bool, error) {
	source, target, err := g.pair(from, to)
	if err != nil {
		return false, err
	}
	at := find(source.out, "out", from, to, steps)
	if at < 0 {
		return false, nil
	}
	source.out = remove(source.out, "out", from, at, steps)
	target.in = remove(target.in, "in", to, find(target.in, "in", to, from, steps), steps)
	g.edges--
	return true, nil
}

// Neighbors lists where a node's edges go, in the order they were added.
func (g *AdjacencyList) Neighbors(name string, steps *[]Step) ([]string, error) {
	node, err := g.get(name)
	if err != nil {
		return nil, err
	}
	return readAll(node.out, "out", name, steps), nil
}

// Sources lists where a node's incoming edges come from, in the order they were added.
func (g *AdjacencyList) Sources(name string, steps *[]Step) ([]string, error) {
	node, err := g.get(name)
	if err != nil {
		return nil, err
	}
	return readAll(node.in, "in", name, steps), nil
}

// RemoveNode removes a node and every edge touching it. Its own two lists say exactly
// which other lists mention it, so no other list is read. It returns how many edges
// were removed.
func (g *AdjacencyList) RemoveNode(name string, steps *[]Step) (int, error) {
	node, err := g.get(name)
	if err != nil {
		return 0, err
	}
	removed := 0
	for i, to := range node.out {
		record(steps, "read", "out", name, i, to)
		removed++
		if to == name {
			continue
		}
		other := g.lists[to]
		other.in = remove(other.in, "in", to, find(other.in, "in", to, name, steps), steps)
	}
	for i, from := range node.in {
		record(steps, "read", "in", name, i, from)
		if from == name {
			continue
		}
		removed++
		other := g.lists[from]
		other.out = remove(other.out, "out", from, find(other.out, "out", from, name, steps), steps)
	}
	delete(g.lists, name)
	g.order = slices.DeleteFunc(g.order, func(n string) bool { return n == name })
	g.edges -= removed
	return removed, nil
}

func (g *AdjacencyList) Nodes() []string { return slices.Clone(g.order) }
func (g *AdjacencyList) EdgeCount() int  { return g.edges }

func (g *AdjacencyList) get(name string) (*lists, error) {
	node, ok := g.lists[name]
	if !ok {
		return nil, fmt.Errorf("unknown node %s", name)
	}
	return node, nil
}

func (g *AdjacencyList) pair(from, to string) (*lists, *lists, error) {
	source, err := g.get(from)
	if err != nil {
		return nil, nil, err
	}
	target, err := g.get(to)
	if err != nil {
		return nil, nil, err
	}
	return source, target, nil
}

// find reads a list from the front until target turns up, and returns its position or -1.
func find(list []string, which, owner, target string, steps *[]Step) int {
	for i, value := range list {
		record(steps, "read", which, owner, i, value)
		if value == target {
			return i
		}
	}
	return -1
}

func remove(list []string, which, owner string, index int, steps *[]Step) []string {
	record(steps, "remove", which, owner, index, list[index])
	return slices.Delete(list, index, index+1)
}

func readAll(list []string, which, owner string, steps *[]Step) []string {
	for i, value := range list {
		record(steps, "read", which, owner, i, value)
	}
	return slices.Clone(list)
}

// AdjacencyMatrix is the same graph as a matrix: one cell per ordered pair of nodes,
// set when the edge exists. Checking one edge reads one cell, but listing a node's edges
// reads its whole row or column, and adding a node copies every cell into a larger matrix.
type AdjacencyMatrix struct {
	index map[string]int
	names []string
	cells []bool
	edges int
}

func NewAdjacencyMatrix() *AdjacencyMatrix {
	return &AdjacencyMatrix{index: map[string]int{}}
}

func (m *AdjacencyMatrix) AddNode(name string) error {
	if _, ok := m.index[name]; ok {
		return fmt.Errorf("node %s already exists", name)
	}
	n := len(m.names)
	next := make([]bool, (n+1)*(n+1))
	for row := range n {
		copy(next[row*(n+1):row*(n+1)+n], m.cells[row*n:row*n+n])
	}
	m.index[name] = n
	m.names = append(m.names, name)
	m.cells = next
	return nil
}

func (m *AdjacencyMatrix) HasEdge(from, to string, steps *[]Step) (bool, error) {
	row, column, err := m.pair(from, to)
	if err != nil {
		return false, err
	}
	return m.read(row, column, steps), nil
}

func (m *AdjacencyMatrix) AddEdge(from, to string, steps *[]Step) (bool, error) {
	row, column, err := m.pair(from, to)
	if err != nil || m.read(row, column, steps) {
		return false, err
	}
	m.write(row, column, true, steps)
	m.edges++
	return true, nil
}

func (m *AdjacencyMatrix) RemoveEdge(from, to string, steps *[]Step) (bool, error) {
	row, column, err := m.pair(from, to)
	if err != nil || !m.read(row, column, steps) {
		return false, err
	}
	m.write(row, column, false, steps)
	m.edges--
	return true, nil
}

// Neighbors lists where a node's edges go, in node order: every cell of its row is read.
func (m *AdjacencyMatrix) Neighbors(name string, steps *[]Step) ([]string, error) {
	row, err := m.at(name)
	if err != nil {
		return nil, err
	}
	found := []string{}
	for column, node := range m.names {
		if m.read(row, column, steps) {
			found = append(found, node)
		}
	}
	return found, nil
}

// Sources lists where a node's incoming edges come from, in node order: every cell of
// its column is read.
func (m *AdjacencyMatrix) Sources(name string, steps *[]Step) ([]string, error) {
	column, err := m.at(name)
	if err != nil {
		return nil, err
	}
	found := []string{}
	for row, node := range m.names {
		if m.read(row, column, steps) {
			found = append(found, node)
		}
	}
	return found, nil
}

func (m *AdjacencyMatrix) RemoveNode(name string, steps *[]Step) (int, error) {
	at, err := m.at(name)
	if err != nil {
		return 0, err
	}
	n := len(m.names)
	removed := 0
	for column := range n {
		if m.read(at, column, steps) {
			m.write(at, column, false, steps)
			removed++
		}
	}
	for row := range n {
		if row != at && m.read(row, at, steps) {
			m.write(row, at, false, steps)
			removed++
		}
	}
	// Copy every other cell into a matrix one row and one column smaller.
	next := make([]bool, 0, (n-1)*(n-1))
	for row := range n {
		for column := range n {
			if row != at && column != at {
				next = append(next, m.cells[row*n+column])
			}
		}
	}
	m.cells = next
	m.names = slices.Delete(m.names, at, at+1)
	m.index = map[string]int{}
	for i, node := range m.names {
		m.index[node] = i
	}
	m.edges -= removed
	return removed, nil
}

func (m *AdjacencyMatrix) Nodes() []string { return slices.Clone(m.names) }
func (m *AdjacencyMatrix) EdgeCount() int  { return m.edges }
func (m *AdjacencyMatrix) CellCount() int  { return len(m.names) * len(m.names) }

func (m *AdjacencyMatrix) at(name string) (int, error) {
	at, ok := m.index[name]
	if !ok {
		return 0, fmt.Errorf("unknown node %s", name)
	}
	return at, nil
}

func (m *AdjacencyMatrix) pair(from, to string) (int, int, error) {
	row, err := m.at(from)
	if err != nil {
		return 0, 0, err
	}
	column, err := m.at(to)
	return row, column, err
}

func (m *AdjacencyMatrix) read(row, column int, steps *[]Step) bool {
	record(steps, "read-cell", "cell", m.names[row], column, m.names[column])
	return m.cells[row*len(m.names)+column]
}

func (m *AdjacencyMatrix) write(row, column int, set bool, steps *[]Step) {
	kind := "clear-cell"
	if set {
		kind = "set-cell"
	}
	record(steps, kind, "cell", m.names[row], column, m.names[column])
	m.cells[row*len(m.names)+column] = set
}