package coffee.liz.ecs

import kotlin.reflect.KClass

/**
 * World implementation that executes systems in dependency order using a DAG.
 */
class DAGWorld(systems: List<System>) : World {
    private val entities = mutableSetOf<Entity>()
    private val componentCache = mutableMapOf<KClass<out Component>, MutableSet<Entity>>()
    private val systemExecutionOrder: List<System>
    private var nextEntityId = 0

    init {
        systemExecutionOrder = buildExecutionOrder(systems)
    }

    override fun createEntity(): Entity {
        val entity = Entity(nextEntityId++)
        entities.add(entity)
        return entity
    }

    override fun destroyEntity(entity: Entity) {
        // Remove from all component caches
        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()

        // Start with entities that have the first component type
        val firstType = componentTypes[0]
        val candidates = componentCache[firstType] ?: return emptySet()

        // Filter to entities that have all component types
        return candidates.filter { entity ->
            entity.hasAll(*componentTypes)
        }.toSet()
    }

    override fun update(deltaTime: Float) {
        // Update component cache based on current entity state
        updateComponentCache()

        // Execute systems in dependency order
        systemExecutionOrder.forEach { system ->
            system.update(this, deltaTime)
        }
    }

    /**
     * Rebuild the component cache based on current entity components.
     * Call this after components have been added/removed from entities.
     */
    private fun updateComponentCache() {
        componentCache.clear()
        entities.forEach { entity ->
            entity.componentTypes().forEach { componentType ->
                componentCache.getOrPut(componentType) { mutableSetOf() }.add(entity)
            }
        }
    }

    /**
     * Build a topologically sorted execution order from system dependencies.
     * Uses Kahn's algorithm for topological sorting.
     */
    private fun buildExecutionOrder(systems: List<System>): List<System> {
        if (systems.isEmpty()) return emptyList()

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

        // 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>>()
        val result = mutableListOf<System>()

        // Add all systems with no dependencies to queue
        inDegree.forEach { (systemClass, degree) ->
            if (degree == 0) {
                queue.add(systemClass)
            }
        }

        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)
                }
            }
        }

        // Check for cycles
        if (result.size != systems.size) {
            throw IllegalArgumentException("Circular dependency detected in systems")
        }

        return result
    }
}