"""
算法管理器
管理各种路径规划算法的注册、配置、执行和性能分析
"""

import time
import json
from typing import Dict, List, Tuple, Any, Callable, Optional
from collections import defaultdict

class AlgorithmManager:
    """
    算法管理器
    管理各种路径规划算法的注册、配置、执行和性能分析
    """
    
    def __init__(self):
        """初始化算法管理器"""
        self.algorithms: Dict[str, Callable] = {}
        self.algorithm_parameters: Dict[str, Dict[str, Any]] = {}
        self.algorithm_descriptions: Dict[str, str] = {}
        self.stats: Dict[str, Any] = {
            'total_tests': 0,
            'successful_tests': 0,
            'failed_tests': 0,
            'total_time': 0.0,
            'algorithm_usage': defaultdict(int)
        }
        
        # 算法性能缓存
        self.performance_cache: Dict[str, List[Dict[str, Any]]] = defaultdict(list)
        
        # 注册内置算法
        self._register_builtin_algorithms()
        
    def _register_builtin_algorithms(self):
        """注册内置算法"""
        from ..algorithms import astar, dijkstra, bfs, dfs, jps
        self.algorithms['astar'] = astar.AStar
        self.algorithms['dijkstra'] = dijkstra.Dijkstra
        self.algorithms['bfs'] = bfs.BFS
        self.algorithms['dfs'] = dfs.DFS
        self.algorithms['jps'] = jps.JPS
        
        # 设置算法描述
        self.algorithm_descriptions['astar'] = "A*算法是一种启发式搜索算法，结合了Dijkstra算法的准确性和贪心最佳优先搜索的效率，保证找到最优解"
        self.algorithm_descriptions['dijkstra'] = "Dijkstra算法是一种用于计算单源最短路径的经典算法，保证找到最短路径"
        self.algorithm_descriptions['bfs'] = "广度优先搜索算法，保证找到最短路径（在无权图中）"
        self.algorithm_descriptions['dfs'] = "深度优先搜索算法，不保证找到最短路径，但可能更快找到任意路径"
        self.algorithm_descriptions['jps'] = "Jump Point Search是一种优化的A*算法，专门用于网格地图，比传统A*更快"
        
        # 设置默认参数
        self.algorithm_parameters['astar'] = {
            'heuristic': 'manhattan',
            'weight': 1.0
        }
        self.algorithm_parameters['dijkstra'] = {}
        self.algorithm_parameters['bfs'] = {}
        self.algorithm_parameters['dfs'] = {
            'depth_limit': 1000
        }
        self.algorithm_parameters['jps'] = {
            'heuristic': 'manhattan'
        }
        
    def add_algorithm(self, name: str, algorithm_class: Callable, description: str = ""):
        """
        添加新算法
        
        Args:
            name: 算法名称
            algorithm_class: 算法类
            description: 算法描述
        """
        self.algorithms[name] = algorithm_class
        self.algorithm_parameters[name] = {}
        self.algorithm_descriptions[name] = description
        print(f"✓ 算法 '{name}' 已添加")
        
    def remove_algorithm(self, name: str):
        """
        移除算法
        
        Args:
            name: 算法名称
        """
        if name in self.algorithms:
            del self.algorithms[name]
        if name in self.algorithm_parameters:
            del self.algorithm_parameters[name]
        if name in self.algorithm_descriptions:
            del self.algorithm_descriptions[name]
        if name in self.stats['algorithm_usage']:
            del self.stats['algorithm_usage'][name]
        print(f"✓ 算法 '{name}' 已移除")
            
    def get_available_algorithms(self) -> List[str]:
        """
        获取可用算法列表
        
        Returns:
            算法名称列表
        """
        return list(self.algorithms.keys())
        
    def get_algorithm_description(self, algorithm: str) -> str:
        """
        获取算法描述
        
        Args:
            algorithm: 算法名称
            
        Returns:
            算法描述
        """
        return self.algorithm_descriptions.get(algorithm, "无描述")
        
    def set_algorithm_parameter(self, algorithm: str, parameter: str, value: Any):
        """
        设置算法参数
        
        Args:
            algorithm: 算法名称
            parameter: 参数名称
            value: 参数值
        """
        if algorithm in self.algorithm_parameters:
            self.algorithm_parameters[algorithm][parameter] = value
            print(f"✓ 算法 '{algorithm}' 参数 '{parameter}' 已设置为 {value}")
            
    def get_algorithm_parameters(self, algorithm: str) -> Dict[str, Any]:
        """
        获取算法参数
        
        Args:
            algorithm: 算法名称
            
        Returns:
            算法参数字典
        """
        return self.algorithm_parameters.get(algorithm, {}).copy()
        
    def find_path(self, algorithm: str, grid: List[List[int]], start: Tuple[int, int], goal: Tuple[int, int]) -> Tuple[Optional[List[Tuple[int, int]]], Dict[str, Any]]:
        """
        查找路径
        
        Args:
            algorithm: 算法名称
            grid: 网格地图
            start: 起点
            goal: 终点
            
        Returns:
            (路径, 统计信息) 元组
        """
        if algorithm not in self.algorithms:
            return None, {'error': f'算法 {algorithm} 未找到'}
            
        try:
            # 更新统计信息
            self.stats['total_tests'] += 1
            self.stats['algorithm_usage'][algorithm] += 1
            
            # 记录开始时间
            start_time = time.time()
            
            # 创建算法实例
            algo_class = self.algorithms[algorithm]
            algo_instance = algo_class()
            
            # 设置参数
            if algorithm in self.algorithm_parameters:
                for param, value in self.algorithm_parameters[algorithm].items():
                    if hasattr(algo_instance, param):
                        setattr(algo_instance, param, value)
                        
            # 执行路径查找
            path = algo_instance.find_path(grid, start, goal)
            
            # 记录结束时间
            end_time = time.time()
            elapsed_time = end_time - start_time
            
            # 更新统计信息
            self.stats['total_time'] += elapsed_time
            if path:
                self.stats['successful_tests'] += 1
            else:
                self.stats['failed_tests'] += 1
                
            # 收集算法统计信息
            algorithm_stats = {}
            if hasattr(algo_instance, 'get_stats'):
                algorithm_stats = algo_instance.get_stats()
                
            # 合并统计信息
            stats = {
                'time_taken': elapsed_time,
                'success': path is not None,
                'path_length': len(path) if path else 0,
                'algorithm': algorithm
            }
            stats.update(algorithm_stats)
            
            # 缓存性能数据
            self._cache_performance_data(algorithm, stats)
            
            return path, stats
            
        except Exception as e:
            self.stats['failed_tests'] += 1
            error_stats = {
                'error': str(e), 
                'time_taken': 0,
                'success': False,
                'path_length': 0,
                'algorithm': algorithm
            }
            self._cache_performance_data(algorithm, error_stats)
            return None, error_stats
            
    def _cache_performance_data(self, algorithm: str, stats: Dict[str, Any]):
        """
        缓存性能数据
        
        Args:
            algorithm: 算法名称
            stats: 统计信息
        """
        self.performance_cache[algorithm].append(stats)
        # 限制缓存大小
        if len(self.performance_cache[algorithm]) > 1000:
            self.performance_cache[algorithm] = self.performance_cache[algorithm][-1000:]
            
    def get_stats(self) -> Dict[str, Any]:
        """
        获取统计信息
        
        Returns:
            统计信息字典
        """
        stats = self.stats.copy()
        if self.stats['total_tests'] > 0:
            stats['average_time'] = self.stats['total_time'] / self.stats['total_tests']
            stats['success_rate'] = self.stats['successful_tests'] / self.stats['total_tests']
        else:
            stats['average_time'] = 0
            stats['success_rate'] = 0
        return stats
        
    def reset_stats(self):
        """重置统计信息"""
        self.stats = {
            'total_tests': 0,
            'successful_tests': 0,
            'failed_tests': 0,
            'total_time': 0.0,
            'algorithm_usage': defaultdict(int)
        }
        self.performance_cache.clear()
        print("✓ 统计信息已重置")
        
    def generate_report(self) -> Dict[str, Any]:
        """
        生成报告
        
        Returns:
            报告字典
        """
        stats = self.get_stats()
        report = {
            'timestamp': time.time(),
            'algorithms': self.get_available_algorithms(),
            'algorithm_descriptions': {algo: self.get_algorithm_description(algo) 
                                     for algo in self.get_available_algorithms()},
            'stats': stats,
            'total_tests': stats.get('total_tests', 0),
            'success_rate': stats.get('success_rate', 0),
            'algorithm_usage': dict(self.stats['algorithm_usage']),
            'performance_summary': self._generate_performance_summary()
        }
        return report
        
    def _generate_performance_summary(self) -> Dict[str, Dict[str, float]]:
        """
        生成性能摘要
        
        Returns:
            性能摘要字典
        """
        summary = {}
        for algorithm in self.algorithms.keys():
            if algorithm in self.performance_cache and self.performance_cache[algorithm]:
                performances = self.performance_cache[algorithm]
                avg_time = sum(p.get('time_taken', 0) for p in performances) / len(performances)
                avg_path_length = sum(p.get('path_length', 0) for p in performances) / len(performances)
                success_count = sum(1 for p in performances if p.get('success', False))
                success_rate = success_count / len(performances) if performances else 0
                
                summary[algorithm] = {
                    'average_time': avg_time,
                    'average_path_length': avg_path_length,
                    'success_rate': success_rate,
                    'test_count': len(performances)
                }
        return summary
        
    def export_report(self, filepath: str) -> bool:
        """
        导出报告到文件
        
        Args:
            filepath: 文件路径
            
        Returns:
            是否导出成功
        """
        try:
            report = self.generate_report()
            
            # 转换不可序列化的对象
            serializable_report = self._make_serializable(report)
            
            with open(filepath, 'w', encoding='utf-8') as f:
                json.dump(serializable_report, f, indent=2, ensure_ascii=False)
                
            print(f"✓ 报告已导出到: {filepath}")
            return True
        except Exception as e:
            print(f"✗ 导出报告失败: {e}")
            return False
            
    def _make_serializable(self, obj):
        """将对象转换为可序列化的格式"""
        if isinstance(obj, dict):
            return {key: self._make_serializable(value) for key, value in obj.items()}
        elif isinstance(obj, (list, tuple)):
            return [self._make_serializable(item) for item in obj]
        elif isinstance(obj, (int, float, str, bool)) or obj is None:
            return obj
        else:
            return str(obj)
            
    def batch_test(self, algorithms: List[str], test_cases: List[Dict]) -> Dict[str, List[Dict]]:
        """
        批量测试
        
        Args:
            algorithms: 算法列表
            test_cases: 测试用例列表
            
        Returns:
            测试结果字典
        """
        print(f"✓ 开始批量测试 {len(algorithms)} 个算法，{len(test_cases)} 个测试用例")
        results = {algorithm: [] for algorithm in algorithms}
        
        for i, test_case in enumerate(test_cases):
            print(f"  测试进度: {i+1}/{len(test_cases)}")
            grid = test_case['grid']
            start = test_case['start']
            goal = test_case['goal']
            
            for algorithm in algorithms:
                path, stats = self.find_path(algorithm, grid, start, goal)
                results[algorithm].append({
                    'test_case': test_case.get('name', f'unnamed_{i}'),
                    'path': path,
                    'stats': stats
                })
                
        print("✓ 批量测试完成")
        return results
        
    def compare_algorithms(self, algorithms: List[str], grid: List[List[int]], 
                          start: Tuple[int, int], goal: Tuple[int, int]) -> Dict[str, Dict[str, Any]]:
        """
        比较算法性能
        
        Args:
            algorithms: 算法列表
            grid: 网格地图
            start: 起点
            goal: 终点
            
        Returns:
            比较结果字典
        """
        print(f"✓ 比较 {len(algorithms)} 个算法")
        results = {}
        
        for algorithm in algorithms:
            if algorithm in self.algorithms:
                path, stats = self.find_path(algorithm, grid, start, goal)
                results[algorithm] = {
                    'path': path,
                    'stats': stats,
                    'description': self.get_algorithm_description(algorithm)
                }
                
        return results
        
    def get_algorithm_complexity(self, algorithm: str) -> str:
        """
        获取算法复杂度信息
        
        Args:
            algorithm: 算法名称
            
        Returns:
            复杂度信息
        """
        complexity_info = {
            'astar': '时间复杂度: O(b^d), 空间复杂度: O(b^d) (b为分支因子, d为搜索深度)',
            'dijkstra': '时间复杂度: O(V^2) 或 O(E + V log V) (使用优先队列), 空间复杂度: O(V)',
            'bfs': '时间复杂度: O(V + E), 空间复杂度: O(V)',
            'dfs': '时间复杂度: O(V + E), 空间复杂度: O(V)',
            'jps': '时间复杂度: 比A*快数倍, 具体取决于地图结构, 空间复杂度: O(b^d)'
        }
        return complexity_info.get(algorithm, '未知复杂度')
        
    def get_cached_performance_data(self, algorithm: str) -> List[Dict[str, Any]]:
        """
        获取缓存的性能数据
        
        Args:
            algorithm: 算法名称
            
        Returns:
            性能数据列表
        """
        return self.performance_cache.get(algorithm, []).copy()
        
    def clear_performance_cache(self):
        """清除性能缓存"""
        self.performance_cache.clear()
        print("✓ 性能缓存已清除")
        
    def get_algorithm_recommendation(self, grid_size: Tuple[int, int], 
                                   obstacle_density: float, 
                                   optimality_required: bool = True) -> str:
        """
        根据场景特点推荐算法
        
        Args:
            grid_size: 网格尺寸 (行数, 列数)
            obstacle_density: 障碍物密度 (0-1)
            optimality_required: 是否要求最优解
            
        Returns:
            推荐的算法名称
        """
        rows, cols = grid_size
        total_cells = rows * cols
        
        # 根据场景特点推荐算法
        if total_cells > 10000:  # 大型地图
            if optimality_required:
                return 'jps'  # JPS在大型地图上性能更好
            else:
                return 'dfs'  # 如果不要求最优解，DFS可能更快
        elif obstacle_density > 0.5:  # 高障碍物密度
            if optimality_required:
                return 'astar'  # A*在复杂环境中表现稳定
            else:
                return 'bfs'  # BFS在高障碍物环境中可能更快
        else:  # 小型或中等地图，低障碍物密度
            if optimality_required:
                return 'astar'  # A*是通用的最佳选择
            else:
                return 'bfs'  # BFS简单高效
                
    def validate_grid(self, grid: List[List[int]]) -> Dict[str, Any]:
        """
        验证网格数据
        
        Args:
            grid: 网格数据
            
        Returns:
            验证结果
        """
        if not grid:
            return {'valid': False, 'error': '网格为空'}
            
        rows = len(grid)
        cols = len(grid[0]) if rows > 0 else 0
        
        if rows == 0 or cols == 0:
            return {'valid': False, 'error': '网格尺寸为0'}
            
        # 检查数据类型
        for r in range(rows):
            if len(grid[r]) != cols:
                return {'valid': False, 'error': f'第{r}行列数不一致'}
            for c in range(cols):
                if not isinstance(grid[r][c], int) or grid[r][c] not in [0, 1]:
                    return {'valid': False, 'error': f'位置({r},{c})的数据无效'}
                    
        return {'valid': True, 'rows': rows, 'cols': cols}