package coffee.liz.ecs

import kotlin.concurrent.atomics.AtomicInt
import kotlin.concurrent.atomics.ExperimentalAtomicApi
import kotlin.concurrent.atomics.incrementAndFetch
import kotlin.reflect.KClass
import kotlin.time.Duration

/**
 * [World] that updates in [System.dependencies] topological order.
 */
@OptIn(ExperimentalAtomicApi::class)
class DAGWorld<Outside>(
    systems: List<System<Outside>>,
) : World<Outside> {
    private val entities = mutableSetOf<Entity>()
    private val componentCache = mutableMapOf<KClass<out Component>, MutableSet<Entity>>()
    private val systemExecutionOrder: List<System<Outside>> = buildExecutionOrder(systems)
    private val nextEntityId = AtomicInt(0)

    override fun createEntity(): Entity =
        Entity(nextEntityId.incrementAndFetch())
            .also { entities.add(it) }

    override fun removeEntity(entity: Entity) {
        entity.componentTypes().forEach { componentType ->
            componentCache[componentType]?.remove(entity)
        }
        entities.remove(entity)
    }

    override fun query(vararg componentTypes: KClass<out Component>): Set<Entity> {
        if (componentTypes.isEmpty()) return entities.toSet()

        val firstType = componentTypes[0]
        val candidates = componentCache[firstType] ?: return emptySet()

        return candidates
            .filter { entity -> componentTypes.all { entity.has(it) } }
            .toSet()
    }

    override fun update(
        state: Outside,
        deltaTime: Duration,
    ) {
        refreshComponentCache()
        systemExecutionOrder.forEach { system ->
            system.update(this, state, deltaTime)
        }
    }

    private fun refreshComponentCache() {
        componentCache.clear()
        entities.forEach { entity ->
            entity.componentTypes().forEach { componentType ->
                componentCache.getOrPut(componentType) { mutableSetOf() }.add(entity)
            }
        }
    }

    private fun buildExecutionOrder(systems: List<System<Outside>>): List<System<Outside>> {
        if (systems.isEmpty()) return emptyList()

        val systemMap = systems.associateBy { it::class }
        val inDegree = mutableMapOf<KClass<out System<Outside>>, Int>()
        val adjacencyList = mutableMapOf<KClass<out System<Outside>>, MutableSet<KClass<out System<Outside>>>>()

        // Initialize graph
        systems.forEach { system ->
            val systemClass = system::class
            inDegree[systemClass] = 0
            adjacencyList[systemClass] = mutableSetOf()
        }

        // Build dependency graph (reversed - dependencies point to dependents)
        systems.forEach { system ->
            system.dependencies.forEach { dependency ->
                if (systemMap.containsKey(dependency)) {
                    adjacencyList[dependency]!!.add(system::class)
                    inDegree[system::class] = inDegree[system::class]!! + 1
                }
            }
        }

        // Kahn's algorithm
        val queue = ArrayDeque<KClass<out System<Outside>>>()
        val result = mutableListOf<System<Outside>>()

        queue.addAll(inDegree.filterValues { it == 0 }.keys)

        while (queue.isNotEmpty()) {
            val currentClass = queue.removeFirst()
            result.add(systemMap[currentClass]!!)

            // Process dependents
            adjacencyList[currentClass]?.forEach { dependent ->
                inDegree[dependent] = inDegree[dependent]!! - 1
                if (inDegree[dependent] == 0) {
                    queue.add(dependent)
                }
            }
        }

        if (result.size != systems.size) {
            error("Circular dependency detected in systems")
        }

        return result
    }
}