package plugin

import (
	"fmt"
	"sync"
)

// DependencyGraph 依赖图
type DependencyGraph struct {
	// nodes 存储所有节点（插件）
	nodes map[string]*depNode

	// mu 保护并发访问
	mu sync.RWMutex
}

// depNode 依赖图节点
type depNode struct {
	plugin       Plugin
	dependencies []string // 依赖的插件名称列表
	dependents   []string // 依赖此插件的插件名称列表
}

// NewDependencyGraph 创建依赖图
func NewDependencyGraph() *DependencyGraph {
	return &DependencyGraph{
		nodes: make(map[string]*depNode),
	}
}

// Add 添加插件到依赖图
func (g *DependencyGraph) Add(plugin Plugin) error {
	g.mu.Lock()
	defer g.mu.Unlock()

	name := plugin.Name()

	// 检查是否已存在
	if _, exists := g.nodes[name]; exists {
		return fmt.Errorf("plugin '%s' already in dependency graph", name)
	}

	// 创建节点
	node := &depNode{
		plugin:       plugin,
		dependencies: make([]string, 0),
		dependents:   make([]string, 0),
	}

	// 添加依赖关系
	for _, dep := range plugin.Dependencies() {
		if !dep.Optional {
			node.dependencies = append(node.dependencies, dep.Name)

			// 更新被依赖插件的 dependents 列表
			if depNode, exists := g.nodes[dep.Name]; exists {
				depNode.dependents = append(depNode.dependents, name)
			}
		}
	}

	// 检查循环依赖
	if g.hasCycleFrom(name, node.dependencies) {
		return fmt.Errorf("circular dependency detected for plugin '%s'", name)
	}

	g.nodes[name] = node

	return nil
}

// Remove 从依赖图移除插件
func (g *DependencyGraph) Remove(pluginName string) {
	g.mu.Lock()
	defer g.mu.Unlock()

	node, exists := g.nodes[pluginName]
	if !exists {
		return
	}

	// 从依赖的插件的 dependents 列表中移除
	for _, depName := range node.dependencies {
		if depNode, exists := g.nodes[depName]; exists {
			depNode.dependents = removeFromSlice(depNode.dependents, pluginName)
		}
	}

	// 从依赖此插件的插件的 dependencies 列表中移除
	for _, dependentName := range node.dependents {
		if dependentNode, exists := g.nodes[dependentName]; exists {
			dependentNode.dependencies = removeFromSlice(dependentNode.dependencies, pluginName)
		}
	}

	delete(g.nodes, pluginName)
}

// GetDependents 获取依赖指定插件的所有插件
func (g *DependencyGraph) GetDependents(pluginName string) []string {
	g.mu.RLock()
	defer g.mu.RUnlock()

	if node, exists := g.nodes[pluginName]; exists {
		result := make([]string, len(node.dependents))
		copy(result, node.dependents)
		return result
	}

	return nil
}

// GetLoadOrder 获取插件加载顺序（拓扑排序）
func (g *DependencyGraph) GetLoadOrder() []string {
	g.mu.RLock()
	defer g.mu.RUnlock()

	// 使用 Kahn 算法进行拓扑排序
	inDegree := make(map[string]int)
	for name, node := range g.nodes {
		inDegree[name] = len(node.dependencies)
	}

	// 找出所有入度为 0 的节点
	queue := make([]string, 0)
	for name, degree := range inDegree {
		if degree == 0 {
			queue = append(queue, name)
		}
	}

	result := make([]string, 0, len(g.nodes))

	for len(queue) > 0 {
		// 取出队首元素
		current := queue[0]
		queue = queue[1:]
		result = append(result, current)

		// 减少依赖此节点的所有节点的入度
		if node, exists := g.nodes[current]; exists {
			for _, dependent := range node.dependents {
				inDegree[dependent]--
				if inDegree[dependent] == 0 {
					queue = append(queue, dependent)
				}
			}
		}
	}

	return result
}

// hasCycleFrom 检查从指定节点开始是否存在循环依赖
func (g *DependencyGraph) hasCycleFrom(start string, dependencies []string) bool {
	visited := make(map[string]bool)
	recStack := make(map[string]bool)

	var dfs func(string) bool
	dfs = func(name string) bool {
		visited[name] = true
		recStack[name] = true

		// 获取依赖列表
		var deps []string
		if name == start {
			deps = dependencies
		} else if node, exists := g.nodes[name]; exists {
			deps = node.dependencies
		}

		for _, dep := range deps {
			if !visited[dep] {
				if dfs(dep) {
					return true
				}
			} else if recStack[dep] {
				return true
			}
		}

		recStack[name] = false
		return false
	}

	return dfs(start)
}

// removeFromSlice 从切片中移除指定元素
func removeFromSlice(slice []string, item string) []string {
	result := make([]string, 0, len(slice))
	for _, s := range slice {
		if s != item {
			result = append(result, s)
		}
	}
	return result
}