using Plugins.JNGame.Sync.Frame.AStar.Entity;

namespace Game.Plugins.JNGame.Sync.Frame.AStar.Util
{
    /// <summary>  
    /// 二叉堆实现。  
    /// 二叉堆非常适合于以能够快速获取F值最低的节点的方式对节点进行排序。  
    /// 也称为优先队列。  
    ///  
    /// 为了提高性能，这里实际上已经被重写为四叉堆，但原理相同。  
    ///  
    /// 参见：http://en.wikipedia.org/wiki/Binary_heap  
    /// 参见：https://en.wikipedia.org/wiki/D-ary_heap  
    /// </summary>  
    public class BinaryHeap {
        /// <summary>树中项目的数量</summary>  
        public int numberOfItems; // 定义了树中当前节点的数量  
  
        /// <summary>每次扩展树时，树至少会按此因子增长</summary>  
        public float growthFactor = 2; // 定义了树每次扩展时的增长因子，默认为2  
  
        /// <summary>  
        /// 树中每个节点的子节点数量。  
        /// 已经测试了不同的值，并经验性地发现4的性能最佳。  
        /// 参见：https://en.wikipedia.org/wiki/D-ary_heap  
        /// </summary>  
        const int D = 4; // 定义了树中每个节点的子节点数量，为4，这符合四叉堆（4-ary heap）的定义  
  
        /// <summary>  
        /// 当比较F值时，如果有相同的情况，则按G值对节点进行排序。  
        /// 禁用此功能将提高路径查找性能约2.5%，  
        /// 但可能会以不太理想的方式打破具有相同长度的路径之间的平衡（仅适用于网格图）。  
        /// </summary>  
        const bool SortGScores = true; // 定义了当F值相同时，是否按G值对节点进行排序，默认为true  
  
        public const ushort NotInHeap = 0xFFFF; // 定义了一个常量，表示节点不在堆中，使用ushort类型的最大值0xFFFF作为标识  
  
        /// <summary>堆的内部支持数组</summary>  
        private Tuple[] heap; // 定义了存储堆中节点的数组，类型为Tuple[]  
  
        /// <summary>如果堆中不包含任何元素，则为true</summary>  
        public bool isEmpty {  
            get {  
                return numberOfItems <= 0; // 定义了一个属性，用于判断堆是否为空，当numberOfItems小于等于0时，表示堆为空  
            }  
        }
        
        /// <summary>堆中的项</summary>  
        private struct Tuple {  
            // 堆中的元素，包含一个PathNode节点和一个F值  
            // PathNode是路径节点，通常包含位置、G值、H值等信息  
            // F值是A*算法中的关键值，通常是G值（从起点到当前节点的成本）和H值（从当前节点到目标的启发式估计成本）的和  
            public PathNode node;  
            public uint F;  
  
            // Tuple的构造函数，接受一个F值和一个PathNode节点作为参数  
            // 使用这些参数来初始化Tuple的F和node成员变量  
            public Tuple(uint f, PathNode node) {  
                this.F = f;  
                this.node = node;  
            }  
        }
        
        /// <summary>  
        /// 向上取整v，使得当它被D除时余数为1。  
        /// 即它是以n*D + 1的形式，其中n是任何非负整数。  
        /// </summary>  
        static int RoundUpToNextMultipleMod1(int v) {  
            // 我感觉有更优雅的方式来实现这个  
            // 使用取模和加法运算将v调整到满足条件的下一个整数  
            // 这里要确保v + (4 - ((v-1) % D)) % D的结果在除以D后余数为1  
            // 这是因为D为4，所以4 - ((v-1) % D)会确保余数为1  
            return v + (4 - ((v - 1) % D)) % D;  
        }  
  
        /// <summary>使用指定的初始容量创建一个新的堆</summary>  
        public BinaryHeap(int capacity) {  
            // 确保容量在除以D后余数为1  
            // 这允许我们始终保证在Remove方法中使用的索引  
            // 永远不会抛出越界异常  
            // 使用RoundUpToNextMultipleMod1方法来调整初始容量  
            capacity = RoundUpToNextMultipleMod1(capacity);  
  
            // 根据调整后的容量初始化堆数组  
            heap = new Tuple[capacity];  
            // 初始化堆中的项目数量为0  
            numberOfItems = 0;  
        }  
  
        /// <summary>从堆中移除所有元素</summary>  
        public void Clear() {  
            #if DECREASE_KEY  
                // 清除所有堆索引  
                // 这是为了避免出现错误  
                // 如果定义了DECREASE_KEY条件编译符号，则执行以下代码块  
                for (int i = 0; i < numberOfItems; i++) {  
                    // 将堆中每个元素的heapIndex设置为NotInHeap常量  
                    // 这有助于在堆操作中避免错误使用已删除的节点  
                    heap[i].node.heapIndex = NotInHeap;  
                }  
            #endif  
  
            // 将堆中的项目数量重置为0  
            numberOfItems = 0;  
        }
        
        /// <summary>  
        /// 根据索引获取堆中的节点  
        /// </summary>  
        /// <param name="i">节点的索引</param>  
        /// <returns>返回指定索引处的PathNode节点</returns>  
        internal PathNode GetNode(int i) {  
            return heap[i].node;  
        }  
  
        /// <summary>  
        /// 设置堆中指定索引位置的元素的F值  
        /// </summary>  
        /// <param name="i">元素的索引</param>  
        /// <param name="f">新的F值</param>  
        internal void SetF(int i, uint f) {  
            heap[i].F = f;  
        }  
  
        /// <summary>  
        /// 当当前数组过小时，扩展为更大的支持数组  
        /// </summary>  
        void Expand() {  
            // 65533 除以4余1，且略小于2的16次方（即65536）  
            // 计算新的数组大小，基于当前数组长度增长一定的比例，但不超过65533  
            // 同时确保新的大小是4的倍数加1，以满足四叉堆的特性  
            int newSize = System.Math.Max(heap.Length + 4, System.Math.Min(65533, (int)System.Math.Round(heap.Length * growthFactor)));  
  
            // 确保新大小除以D余数为1  
            // 这保证了在Remove方法中使用的索引永远不会超出数组边界  
            newSize = RoundUpToNextMultipleMod1(newSize);  
  
            // 检查堆是否过大  
            // 注意：大于此大小的堆不受支持，因为PathNode.heapIndex是ushort类型，  
            // 只能存储最大值到65535（NotInHeap = 65535保留）  
            if (newSize > (1 << 16) - 2) {  
                throw new System.Exception("Binary Heap Size really large (>65534). A heap size this large is probably the cause of pathfinding running in an infinite loop. ");  
            }  
  
            // 创建新的数组来存储扩展后的堆  
            var newHeap = new Tuple[newSize];  
            // 将旧堆的内容复制到新堆中  
            heap.CopyTo(newHeap, 0);  
              
            #if ASTARDEBUG  
                // 如果定义了ASTARDEBUG符号，则输出调试信息  
                UnityEngine.Debug.Log("Resizing binary heap to " + newSize);  
            #endif  
  
            // 更新堆的引用为新数组  
            heap = newHeap;  
        }
        
        /// <summary>  
        /// 将节点添加到堆中  
        /// </summary>  
        /// <param name="node">要添加的节点</param>  
        public void Add(PathNode node) {  
            // 如果传入的节点为null，则抛出参数为空的异常  
            if (node == null) throw new System.ArgumentNullException("node");  
          
        #if DECREASE_KEY  
            // 检查节点是否已经在堆中  
            // 如果节点已经在堆中，则减小其关键值并返回，不再重复添加  
            if (node.heapIndex != NotInHeap) {  
                DecreaseKey(heap[node.heapIndex], node.heapIndex);  
                return;  
            }  
        #endif  
          
            // 如果堆已满，则扩展堆的大小  
            if (numberOfItems == heap.Length) {  
                Expand();  
            }  
          
            // 将新节点添加到堆中，并设置其关键值  
            DecreaseKey(new Tuple(0, node), (ushort)numberOfItems);  
            // 更新堆中的元素数量  
            numberOfItems++;  
        }  
          
        /// <summary>  
        /// 减小节点的关键值，并在堆中进行上浮调整  
        /// </summary>  
        /// <param name="node">要调整关键值的节点</param>  
        /// <param name="index">节点在堆中的索引</param>  
        void DecreaseKey(Tuple node, ushort index) {  
            // 'obj'在逻辑上位于二叉堆的哪个位置  
            // （出于性能考虑，我们实际上并不立即将其存储在那里，直到我们知道最终的索引为止，  
            // 因为提前存储只会浪费CPU周期）  
            int bubbleIndex = index;  
          
            // 更新节点的F值，因为它自从被添加到堆中以来可能已经改变  
            uint nodeF = node.F = node.node.F;  
            uint nodeG = node.node.G;  
          
            // 上浮调整，直到节点满足二叉堆的性质  
            while (bubbleIndex != 0) {  
                // 泡泡节点的父节点  
                int parentIndex = (bubbleIndex - 1) / D;  
          
                // 如果当前节点的F值小于其父节点的F值，或者（如果SortGScores为真且F值相等），  
                // 当前节点的G值大于其父节点的G值，则交换这两个节点  
                if (nodeF < heap[parentIndex].F || (SortGScores && nodeF == heap[parentIndex].F && nodeG > heap[parentIndex].node.G)) {  
                    // 交换泡泡节点和其父节点  
                    // （实际上我们并不需要立即存储泡泡节点，直到我们知道最终索引为止，  
                    // 所以我们在循环之后执行此操作）  
                    heap[bubbleIndex] = heap[parentIndex];  
          
        #if DECREASE_KEY  
                    // 如果定义了DECREASE_KEY符号，则更新父节点的堆索引  
                    heap[bubbleIndex].node.heapIndex = (ushort)bubbleIndex;  
        #endif  
          
                    // 将泡泡索引更新为父节点的索引，继续上浮调整  
                    bubbleIndex = parentIndex;  
                } else {  
                    // 如果当前节点的F值不小于其父节点的F值（且如果SortGScores为真，G值也不大于其父节点），  
                    // 则停止上浮调整  
                    break;  
                }  
            }  
          
            // 将节点放置在最终的位置  
            heap[bubbleIndex] = node;  
          
        #if DECREASE_KEY  
            // 如果定义了DECREASE_KEY符号，则更新节点的堆索引  
            node.node.heapIndex = (ushort)bubbleIndex;  
        #endif  
        }

        /// <summary>  
        /// 从堆中移除并返回具有最低F分数的节点  
        /// </summary>  
        public PathNode Remove()
        {
            // 获取堆顶节点的节点对象  
            PathNode returnItem = heap[0].node;

#if DECREASE_KEY
            // 如果定义了DECREASE_KEY符号，则将堆顶节点的堆索引设置为NotInHeap  
            returnItem.heapIndex = NotInHeap;
#endif

            // 减少堆中元素的数量  
            numberOfItems--;

            // 如果堆为空，则直接返回堆顶节点  
            if (numberOfItems == 0) return returnItem;

            // 获取堆数组中最后一个元素  
            var swapItem = heap[numberOfItems];
            var swapItemG = swapItem.node.G;

            // 定义交换索引和父节点索引  
            int swapIndex = 0, parent;

            // 执行上浮操作  
            while (true)
            {
                // 设置父节点索引  
                parent = swapIndex;
                // 获取交换元素的F分数  
                uint swapF = swapItem.F;
                // 计算子节点的起始索引  
                int pd = parent * D + 1;

                // 确保子节点的索引在有效范围内  
                if (pd <= numberOfItems)
                {
                    // 预先加载所有子节点的F分数，减少数据依赖并提高性能  
                    uint f0 = heap[pd + 0].F;
                    uint f1 = heap[pd + 1].F;
                    uint f2 = heap[pd + 2].F;
                    uint f3 = heap[pd + 3].F;

                    // 常见的情况是节点的所有子节点都存在  
                    // 因此下面的每个if语句中的第一个比较都将被很好地预测，所以基本上是免费的  
                    // (我尝试优化了常见情况，但这对性能没有任何影响，只是代码变得更长，CPU的分支预测器非常强大)  

                    // 检查第一个子节点，如果其F分数更小，或者如果SortGScores为真且F分数相等但G分数更小，则更新交换元素  
                    if (pd + 0 < numberOfItems &&
                        (f0 < swapF || (SortGScores && f0 == swapF && heap[pd + 0].node.G < swapItemG)))
                    {
                        swapF = f0;
                        swapIndex = pd + 0;
                    }

                    // 检查第二个子节点，更新逻辑同上  
                    if (pd + 1 < numberOfItems && (f1 < swapF || (SortGScores && f1 == swapF &&
                                                                  heap[pd + 1].node.G < (swapIndex == parent
                                                                      ? swapItemG
                                                                      : heap[swapIndex].node.G))))
                    {
                        swapF = f1;
                        swapIndex = pd + 1;
                    }

                    // 检查第三个子节点，更新逻辑同上  
                    if (pd + 2 < numberOfItems && (f2 < swapF || (SortGScores && f2 == swapF &&
                                                                  heap[pd + 2].node.G < (swapIndex == parent
                                                                      ? swapItemG
                                                                      : heap[swapIndex].node.G))))
                    {
                        swapF = f2;
                        swapIndex = pd + 2;
                    }

                    // 检查第四个子节点（如果存在）的F分数是否小于当前交换索引指向的节点的F分数  
                    // 或者，如果SortGScores为真（表示需要根据G分数进行排序），且F分数相同  
                    // 那么，比较第四个子节点的G分数是否小于当前交换索引指向的节点的G分数  
                    // 如果是，则更新交换索引为第四个子节点的索引  
                    if (pd + 3 < numberOfItems && (f3 < swapF || (SortGScores && f3 == swapF &&
                                                                  heap[pd + 3].node.G < (swapIndex == parent
                                                                      ? swapItemG
                                                                      : heap[swapIndex].node.G))))
                    {
                        swapIndex = pd + 3; // 将交换索引更新为第四个子节点的索引  
                    }
                }

                // 如果父节点不是当前交换索引指向的节点（即存在更小的子节点）  
                // 则进行上浮操作，即将父节点与交换索引指向的节点（较小的子节点）交换位置  
                // 实际上这里并没有真正交换节点，而是通过局部变量保存交换的数据  
                // 直到我们找到最终的交换位置才进行赋值操作  
                if (parent != swapIndex)
                {
                    // 将父节点的数据复制到交换索引指向的节点位置  
                    heap[parent] = heap[swapIndex];

                    // 如果定义了DECREASE_KEY，则更新父节点在堆中的索引  
#if DECREASE_KEY
                    heap[parent].node.heapIndex = (ushort)parent;
#endif
                }
                else
                {
                    // 如果父节点已经是最小的子节点，则跳出循环，上浮过程结束  
                    break;
                }
            }

            // 将最初从堆顶移除的节点（swapItem）放置到最终的交换位置（swapIndex）  
            heap[swapIndex] = swapItem;

            // 如果定义了DECREASE_KEY，则更新该节点在堆中的索引  
#if DECREASE_KEY
            swapItem.node.heapIndex = (ushort)swapIndex;
#endif

            // 以下代码被注释掉了，可能是用于调试目的，用于验证堆结构的完整性  
            // Validate ();  

            // 返回从堆中移除的节点（即上浮操作后的堆顶节点）  
            return returnItem;
        }

        // 验证方法  
        void Validate() {  
            // 遍历堆中的每个元素，从第二个元素开始（索引为1，因为数组通常从0开始）  
            for (int i = 1; i < numberOfItems; i++) {  
                // 计算当前元素的父节点的索引  
                int parentIndex = (i-1)/D;  
          
                // 检查当前元素的F值是否小于其父节点的F值  
                // 如果不满足这个条件，则抛出异常，表示堆的状态无效  
                if (heap[parentIndex].F > heap[i].F) {  
                    throw new System.Exception("在索引 " + i + " 处状态无效: 父节点索引 " + parentIndex + " ( " + heap[parentIndex].F + " > " + heap[i].F + " ) ");  
                }  
  
                // 如果定义了 DECREASE_KEY 符号（可能是编译时的条件编译符号），则执行下面的代码块  
#if DECREASE_KEY  
                // 检查当前节点的堆索引是否与其在数组中的索引一致  
                // 如果不一致，则抛出异常，表示堆的状态无效  
                if (heap[i].node.heapIndex != i) {  
                    throw new System.Exception("堆索引无效");  
                }  
#endif  
            }  
        }
        
        /// <summary>  
        /// 通过将所有项向下筛选来重建堆。  
        /// 通常在路径上的hTarget被更改后调用。  
        /// </summary>  
        public void Rebuild () {  
#if ASTARDEBUG  
            // 如果定义了ASTARDEBUG符号，则初始化一个变量来跟踪堆中的更改次数  
            int changes = 0;  
#endif  
  
            // 从堆的第二个元素开始遍历（索引为2，因为数组通常从0开始）  
            for (int i = 2; i < numberOfItems; i++) {  
                // 设置当前元素的索引为bubbleIndex  
                int bubbleIndex = i;  
                // 获取当前元素  
                var node = heap[i];  
                // 获取当前元素的F值  
                uint nodeF = node.F;  
          
                // 当bubbleIndex不是1时，继续循环（因为1是堆的根节点）  
                while (bubbleIndex != 1) {  
                    // 计算当前元素的父节点索引  
                    int parentIndex = bubbleIndex / D;  
  
                    // 如果当前元素的F值小于其父节点的F值，则交换它们的位置  
                    if (nodeF < heap[parentIndex].F) {  
                        // 将父节点移动到当前位置  
                        heap[bubbleIndex] = heap[parentIndex];  
#if DECREASE_KEY  
                // 如果定义了DECREASE_KEY符号，则更新父节点的堆索引  
                heap[bubbleIndex].node.heapIndex = (ushort)bubbleIndex;  
#endif  
  
                        // 将当前节点移动到父节点的位置  
                        heap[parentIndex] = node;  
#if DECREASE_KEY  
                // 如果定义了DECREASE_KEY符号，则更新当前节点的堆索引  
                heap[parentIndex].node.heapIndex = (ushort)parentIndex;  
#endif  
  
                        // 更新bubbleIndex为父节点的索引，继续向上筛选  
                        bubbleIndex = parentIndex;  
#if ASTARDEBUG  
                // 如果定义了ASTARDEBUG符号，则记录一次更改  
                changes++;  
#endif  
                    } else {  
                        // 如果当前元素的F值不小于其父节点的F值，则停止筛选  
                        break;  
                    }  
                }  
            }  
  
#if ASTARDEBUG  
            // 如果定义了ASTARDEBUG符号，则打印调试信息，显示重建堆过程中的更改次数  
            UnityEngine.Debug.Log("+++ Rebuilt Heap - " + changes + " changes +++");  
#endif  
        }
        
    }
}