/**
 * A Star 寻路优化 
 * 二叉堆优化
 * 
 * 二叉堆是一种完全二叉树，有两种类型：最大堆（大根堆）、最小堆（小根堆）
 * 因为A 星查找F值最小，所以这里使用最小堆，父节点比子节点小或相等 保证最小位在上方
 * 实际存储是以数组形式，但是逻辑层面是树型
 * 
 * 取出和删除都会改变原有的二叉堆
 * 
 * 取出最小值
 * 删除某一位
 * 查找某一位
*/

import AStarNode from "./AStarNode"

export default class BinaryHeap {

  // 二叉堆虽然是完全二叉树，但其本质还是由数组顺序存储
  _tree: Array<AStarNode>

  constructor() {
    // 初始化二叉堆
    this._tree = []
  }

  /**
   * 逻辑： 父节点下标为parentI 子节点下标为i
   *  直接将当前点插入到最后一位，
   *  与其父节点比较，如果小于其父节点就交换位置
   *  然后重复
   * 
  */
  insert(node: AStarNode) {
    let i, parentI;
    // 插入尾部
    this._tree.push(node)
    // 获取下标
    i = this._tree.length - 1

    // 重复执行 是否比其父节点小
    while (true) {
      // 那么如何求出父节点下标 (i - 1) / 2 有小数点直接舍去小数点位
      // parentI = Math.floor((i - 1) / 2) // 细节优化 
      parentI = (i - 1) >> 1
      // 比较大小
      if (this._tree[parentI] && node.f < this._tree[parentI].f) { // 条件成立 位置交换
        let temp = this._tree[parentI]
        this._tree[parentI] = node
        this._tree[i] = temp
        // 下标置换
        i = parentI

        // 下一轮
      } else { // 等于或者大于都不成立
        return
      }
    }
  }

  /**
   * 逻辑类似，
   *  但是是加入节点的反向过程，反向下沉
   *  删除根节点
   *  将尾部节点补到根节点处
   *  判断其是否符合最小堆规则，不符合就下沉 一个一个往上置换
   *  左孩子下标就是 2 * parent + 1  右孩子下标是2 * parent + 2
  */
  shift(): AStarNode {
    // 提前声明
    let parentI, node, lastNode, tree;
    // 获取引用
    tree = this._tree
    // 要被返回的F值最小的那个节点
    node = tree.shift()
    // 将最后一位补到根节点处
    lastNode = tree.pop()
    // 将尾部节点补到根节点处
    tree.unshift(lastNode)
    // 父节点下标初始化
    parentI = 0
    // 循环判断其是否小于其两个子节点中最小的那位
    while (true) {
      let leftI, rightI;
      // 求出左右孩子的下标
      // leftI = 2 * parentI + 1
      leftI = (parentI << 1) + 1
      rightI = leftI + 1

      // 首先有无这两个位置的节点
      if(leftI >= this._tree.length && rightI >= this._tree.length) {
        return node
      }

      // 对比两个子节点谁更小
      if (tree[rightI] == undefined || tree[leftI].f <= tree[rightI].f) { // 相等或者左子节点小 获取rightI 等于undefined 为什么不判断leftI呢，因为前面已经判断过了
        if (tree[parentI].f > tree[leftI].f) { // 置换条件，当前父节点大于最小的一位子节点
          // 通过中间变量执行上浮操作
          let temp = tree[parentI]
          tree[parentI] = tree[leftI]
          tree[leftI] = temp
          // 坐标转换
          parentI = leftI
          // 下一轮
          continue
        } else {
          return node
        }
      } else { // 右子节点小
        if (tree[parentI].f > tree[rightI].f) { // 置换条件，当前父节点大于最小的一位子节点
          // 通过中间变量执行上浮操作
          let temp = tree[parentI]
          tree[parentI] = tree[rightI]
          tree[rightI] = temp
          // 坐标转换
          parentI = rightI
          // 下一轮
          continue
        } else {
          return node
        }
      }

    }

    // 返回 保持和原数组方法一致
    return node
  }

  // 清空二叉堆
  clear() {
    // 直接丢弃原有数组，等待GC
    this._tree = []
  }

  // 返回二叉堆长度
  getLength(): number {
    return this._tree.length
  }
}


/**
 *          9
 *    30          32
 *  40  56      -10
 *
 *  0. [9, 30, 32, 40, 56]
 *  1. [56, 30, 32, 40]
 *  p = 0
 *  求出左右子节点索引
 *  l = 0 * 2 + 1    // 1
 *  r = l + 1        // 2
 *
 *  比对 30 <= 32  // true
 *     56 > 30 // true
 *      [30, 56, 32, 40] // p = 1
 * 
 *  求出左右子节点索引
 *  l = 1 * 2 + 1    // 3
 *  r = l + 1        // 4
 *  
 *  比对 40 <= undefined || r == undefined // true
 *    56 > 40 // true
 *      [30, 40, 32, 56] // p = 3
 * 
 *  求出左右子节点索引
 *  l = 1 * 2 + 1    // 7
 *  r = l + 1        // 8
 * 
 *  长度超出，直接返回
 * 
 * 
*/