import { Point, Table } from '@backend/domain'

const SPACES = 2

type SpatialIndex = Map<string, Table[]>

export class TableGraph {
	tables: Table[]
	edges: Map<Table, Set<Table>>

	constructor(tables: Table[]) {
		this.tables = tables
		this.edges = new Map()
	}

	addEdge(from: Table, to: Table) {
		if (!this.edges.has(from)) {
			this.edges.set(from, new Set())
		}
		if (!this.edges.has(to)) {
			this.edges.set(to, new Set())
		}

		this.edges.get(from)!.add(to)
		this.edges.get(to)!.add(from)
	}

	getNeighbors(node: Table): Set<Table> | undefined {
		return this.edges.get(node)
	}

	getTableCombinations(tables: Table[]): Array<Table[]> {
		const result: Set<Table[]> = new Set()

		const visitedPaths = new Set<string>()

		const dfs = (currentPath: Table[]): void => {
			const lastTable = currentPath[currentPath.length - 1]
			const neighbors = this.edges.get(lastTable)

			// Stop recursion if no neighbors exist
			if (!neighbors || neighbors.size === 0) {
				return
			}

			for (const neighbor of neighbors) {
				// Ensure we don't revisit any tables in the current path (cycle prevention)
				if (!currentPath.includes(neighbor)) {
					const newPath = [...currentPath, neighbor]
					const pathKey = newPath
						.sort((a, b) => a.id.localeCompare(b.id))
						.map((table) => table.id)
						.join(',')

					if (!visitedPaths.has(pathKey)) {
						visitedPaths.add(pathKey)
						result.add(newPath)
					}

					dfs(newPath)
				}
			}
		}

		// Start DFS for each table
		for (const table of tables) {
			dfs([table])
		}

		return [...result]
	}
}

export class TableGraphBuilder {
	build(tables: Table[]): TableGraph {
		const graph = new TableGraph(tables)

		const spatialIndex = this.createSpatialIndex(graph.tables)

		this.addNeighbors(graph, spatialIndex, SPACES)

		return graph
	}

	private createSpatialIndex(tables: Table[]): SpatialIndex {
		const spatialIndex = new Map<string, Table[]>()

		for (const table of tables) {
			const positions = table.box.getAllPositions()

			for (const pos of positions) {
				const key = this.getKey(pos)
				if (spatialIndex.has(key)) spatialIndex.get(key)!.push(table)
				else spatialIndex.set(key, [table])
			}
		}

		return spatialIndex
	}

	private addNeighbors(graph: TableGraph, spatialIndex: SpatialIndex, maxDistance: number): void {
		for (const table of graph.tables) {
			const box = table.box

			// Cache to store checked nodes
			const checkedNodes = new Set<Table>()

			for (let y = box.top; y <= box.bottom + maxDistance; y++) {
				for (let x = box.left; x <= box.right + maxDistance; x++) {
					const key = this.getKey({ x, y })
					const overlappedNodes = spatialIndex.get(key)

					if (overlappedNodes === undefined) continue

					for (const overlappedNode of overlappedNodes) {
						if (overlappedNode !== table && !checkedNodes.has(overlappedNode)) {
							graph.addEdge(table, overlappedNode)
							checkedNodes.add(overlappedNode)
						}
					}
				}
			}
		}
	}

	private getKey(point: Point): string {
		return `${point.x},${point.y}`
	}
}