///|
/// 创建一个新的空斐波那契堆
pub fn[A, K] new(compare : (K, K) -> Int) -> FibHeap[A, K] {
  FibHeap::{ size: 0, min: Node::Nil, roots: 0, compare }
}

///|
/// 检查堆是否为空
pub fn[A, K] is_empty(self : FibHeap[A, K]) -> Bool {
  self.size == 0
}

///|
/// 获取堆中元素数量
pub fn[A, K] size(self : FibHeap[A, K]) -> Int {
  self.size
}

///|
/// 从数组创建斐波那契堆
pub fn[A : Eq, K : Eq] from_array(
  arr : Array[A],
  keys : Array[K],
  compare : (K, K) -> Int,
) -> FibHeap[A, K] {
  let heap = new(compare)
  let len = @cmp.minimum(arr.length(), keys.length())
  for i in 0.. Unit {
  match (heap.min, node) {
    (Node::Nil, Node::Cons(..) as n) =>
      // 空堆，节点成为唯一的根
      make_singleton(n)
    (Node::Cons(..) as min, Node::Cons(..) as n) => {
      // 插入到最小节点和其右侧节点之间
      let right = get_right(min)
      connect_right(min, n)
      connect_right(n, right)
    }
    _ => () // 至少有一个是 Nil，不做任何操作
  }
  heap.roots += 1
}

///| 从根链表中移除节点
pub fn[A : Eq, K : Eq] remove_from_root_list(
  heap : FibHeap[A, K],
  node : Node[A, K],
) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as n => {
      if get_right(n) == n {
        heap.min = Node::Nil
      } else {
        let left = get_left(n)
        let right = get_right(n)
        match (left, right) {
          (Node::Cons(..) as l, Node::Cons(..) as r) => {
            l.right = r
            r.left = l
          }
          _ => ()
        }
        if heap.min == n {
          heap.min = right
        }
      }
      heap.roots -= 1
    }
  }
}

///| 比较两个节点的键值
pub fn[A, K] is_less(
  heap : FibHeap[A, K],
  a : Node[A, K],
  b : Node[A, K],
) -> Bool {
  match (a, b) {
    (Node::Cons(..) as node_a, Node::Cons(..) as node_b) =>
      (heap.compare)(node_a.key, node_b.key) < 0
    _ => false
  }
}

///|
pub fn[A : Eq, K : Eq] add_children_to_root_list(
  heap : FibHeap[A, K],
  parent : Node[A, K],
) -> Unit {
  match parent {
    Node::Nil => ()
    Node::Cons(..) as p => {
      let child = get_child(p)
      match child {
        Node::Nil => ()
        Node::Cons(..) as first_child => {
          let children = Array::new()
          let mut curr = first_child
          let mut count = 0
          let max_count = p.degree + 2 // 安全上限，防止死循环

          // 使用do-while逻辑：先处理第一个节点，然后循环直到回到起点
          while true {
            children.push(curr)
            curr = get_right(curr)
            count += 1

            // 安全检查：防止无限循环
            if count > max_count || curr == first_child {
              break
            }
          }
          for i in 0.. {
                child_node.parent = Node::Nil
                reset_mark(child_node)
                add_to_root_list(heap, child_node)
              }
              Node::Nil => ()
            }
          }
        }
      }
      clear_children(p)
    }
  }
}

///| 将子节点链接到父节点
pub fn[A : Eq, K : Eq] link(
  heap : FibHeap[A, K],
  child : Node[A, K],
  parent : Node[A, K],
) -> Unit {
  match (parent, child) {
    (Node::Cons(..) as p, Node::Cons(..) as c) => {
      // 从根链表中移除child
      remove_from_root_list(heap, c)

      // 将child添加为parent的子节点
      add_child(p, c)
    }
    _ => () // 至少有一个是 Nil，不做任何操作
  }
}

///| 剪切操作：将节点从父节点分离并添加到根链表
pub fn[A : Eq, K : Eq] cut(
  heap : FibHeap[A, K],
  node : Node[A, K],
  parent : Node[A, K],
) -> Unit {
  match (node, parent) {
    (Node::Cons(..) as n, Node::Cons(..) as p) => {
      // 从父节点的子链表中移除
      if get_right(n) == n {
        // 唯一的子节点
        p.child = Node::Nil
      } else {
        // 将左右节点连接起来
        let left = get_left(n)
        let right = get_right(n)
        connect_right(left, right)

        // 如果移除的是父节点的直接子节点，需要更新child引用
        if p.child == n {
          p.child = right
        }
      }
      p.degree -= 1

      // 添加到根链表
      add_to_root_list(heap, n)
      n.parent = Node::Nil
      reset_mark(n)
    }
    _ => () // 至少有一个是 Nil，不做任何操作
  }
}

///| 级联剪切：处理被标记的节点
pub fn[A : Eq, K : Eq] cascading_cut(
  heap : FibHeap[A, K],
  node : Node[A, K],
) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as n => {
      let parent = get_parent(n)
      match parent {
        Node::Nil => () // 根节点，不需要处理
        Node::Cons(..) as p =>
          if !is_marked(n) {
            // 第一次失去子节点，标记它
            mark_node(n)
          } else {
            // 已经被标记，执行剪切并对父节点进行级联剪切
            cut(heap, n, p)
            cascading_cut(heap, p)
          }
      }
    }
  }
}

///| 合并根链表中具有相同度数的树
pub fn[A : Eq, K : Eq] consolidate(heap : FibHeap[A, K]) -> Unit {
  if heap.size == 0 || heap.min == Node::Nil {
    return
  }

  // 创建度数数组
  let max_degree = @math.log2(heap.size.to_double()).ceil().to_int() + 1
  let degree_array = Array::makei(max_degree, _ => Node::Nil)

  // 收集所有根节点到数组中，防止在处理过程中链表结构改变导致循环出错
  let root_nodes = Array::new(capacity=heap.roots)
  let start = heap.min
  let mut current = start
  let mut counter = 0

  // 安全地收集所有根节点
  while counter < heap.roots {
    root_nodes.push(current)
    current = get_right(current)
    counter += 1

    // 安全检查，防止无限循环
    if counter > heap.size {
      break // 紧急退出
    }
  }

  // 清空根链表
  heap.min = Node::Nil
  heap.roots = 0

  // 处理收集到的每个根节点
  for i in 0.. {
        degree = n.degree

        // 确保节点的左右指针指向自身（成为单节点循环链表）
        n.left = n
        n.right = n

        // 合并相同度数的树
        while degree < degree_array.length() &&
              degree_array[degree] != Node::Nil {
          let mut same_degree = degree_array[degree]

          // 确保node是键值较小的那个
          if is_less(heap, same_degree, node) {
            let temp = node
            node = same_degree
            same_degree = temp
          }

          // 将same_degree作为node的子节点
          match (node, same_degree) {
            (Node::Cons(..) as parent, Node::Cons(..) as child) => {
              // 设置父子关系
              child.parent = parent
              reset_mark(child)

              // 添加到子链表
              if parent.child == Node::Nil {
                parent.child = child
                child.left = child
                child.right = child
              } else {
                let first_child = parent.child
                match first_child {
                  Node::Cons(..) as fc => {
                    let right = fc.right
                    child.right = right
                    child.left = fc
                    fc.right = child
                    match right {
                      Node::Cons(..) as r => r.left = child
                      Node::Nil => () // 不应该发生
                    }
                  }
                  Node::Nil => () // 不应该发生
                }
              }
              parent.degree += 1
            }
            _ => () // 不应该发生
          }

          // 清除度数槽，继续检查下一个度数
          degree_array[degree] = Node::Nil
          degree += 1
        }

        // 将处理后的节点放入对应度数槽
        if degree < degree_array.length() {
          degree_array[degree] = node
        }
      }
      Node::Nil => () // 不应该发生
    }
  }

  // 重建根链表
  for i in 0.. Node[A, K] {
  // 使用辅助函数创建新节点
  let node = create_node(value, key)

  // 将新节点添加到根链表
  if self.min == Node::Nil {
    // 堆为空
    self.min = node
    self.roots = 1
  } else {
    // 添加到根链表
    add_to_root_list(self, node)

    // 更新最小节点
    if is_less(self, node, self.min) {
      self.min = node
    }
  }
  self.size += 1
  node
}

///| 查看最小键值元素
pub fn[A, K] peek_min(self : FibHeap[A, K]) -> (A, K)? {
  match self.min {
    Node::Nil => None
    Node::Cons(..) as cons_node => Some((cons_node.content, cons_node.key))
  }
}

///| 提取最小键值元素
pub fn[A : Eq, K : Eq] extract_min(self : FibHeap[A, K]) -> (A, K)? {
  if self.min == Node::Nil {
    return None
  }

  // 获取最小节点
  let min_node = self.min

  // 先保存要返回的值
  let result = match min_node {
    Node::Nil => return None
    Node::Cons(..) as cons_node => (cons_node.content, cons_node.key)
  }

  // 如果有子节点，将它们添加到根链表
  match min_node {
    Node::Cons(..) as min => {
      // 使用数组收集所有子节点，避免在修改过程中遍历链表
      let children = Array::new()
      let child = min.child
      match child {
        Node::Nil => ()
        Node::Cons(..) as first_child => {
          let mut curr = first_child
          let count = min.degree

          // 收集所有子节点
          for _ in 0.. {
                // 重置父节点和标记
                child_node.parent = Node::Nil
                reset_mark(child_node)

                // 确保节点形成单独的循环
                child_node.left = child_node
                child_node.right = child_node

                // 添加到根链表
                add_to_root_list(self, child_node)
              }
              Node::Nil => () // 不应该发生
            }
          }
        }
      }
    }
    Node::Nil => () // 不应该发生
  }

  // 从根链表中移除最小节点
  remove_from_list(min_node)
  self.roots -= 1

  // 如果根链表为空，设置min为空
  if self.roots == 0 {
    self.min = Node::Nil
  } else {
    // 查找新的最小节点 - 从右侧节点开始
    let next = get_right(min_node)
    self.min = next
    let mut current = next
    let mut counter = 0
    while counter < self.roots {
      if is_less(self, current, self.min) {
        self.min = current
      }
      current = get_right(current)
      counter += 1

      // 安全检查
      if counter > self.size {
        break
      }
    }
  }

  // 更新堆大小
  self.size -= 1

  // 合并具有相同度数的树
  if self.roots > 1 {
    consolidate(self)
  }

  // 返回保存的结果
  Some(result)
}

///| 减小节点的键值
pub fn[A : Eq, K : Eq] decrease_key(
  self : FibHeap[A, K],
  node : Node[A, K],
  new_key : K,
) -> Bool {
  match node {
    Node::Nil => false
    Node::Cons(..) as cons_node => {
      // 检查新键是否更小
      if (self.compare)(new_key, cons_node.key) >= 0 {
        // 新键值不小于当前键值
        return false
      }
      // 提取节点的值
      let value = cons_node.content

      // 删除旧节点
      if self.delete(node) {
        // 插入具有相同值但新键的节点
        ignore(self.insert(value, new_key))
        return true
      }
      false
    }
  }
}

///| 删除节点（不依赖极小值）
pub fn[A : Eq, K : Eq] delete(self : FibHeap[A, K], node : Node[A, K]) -> Bool {
  match node {
    Node::Nil => false
    Node::Cons(..) as cons_node => {
      // 如果节点有父节点，从父节点剪切出来
      let parent = get_parent(cons_node)
      if parent != Node::Nil {
        match parent {
          Node::Cons(..) as p => {
            // 从父节点的子链表中移除
            if p.child == cons_node {
              if get_right(cons_node) == cons_node {
                // 唯一的子节点
                p.child = Node::Nil
              } else {
                p.child = get_right(cons_node)
              }
            }
            // 断开左右连接
            remove_from_list(cons_node)
            // 减少父节点的度数
            p.degree -= 1

            // 将被删除节点的子节点添加到根链表
            add_children_to_root_list(self, cons_node)
          }
          Node::Nil => () // 不应该发生
        }
        self.size -= 1
      } else if self.min == node {
        // 是根节点且是最小节点
        ignore(self.extract_min())
        return true // extract_min已经处理了size减法
      } else {
        // 是根节点但不是最小节点
        remove_from_root_list(self, node)
        add_children_to_root_list(self, node)
        self.size -= 1
      }
      true
    }
  }
}

///| 合并两个斐波那契堆
pub fn[A : Eq, K : Eq] merge(
  self : FibHeap[A, K],
  other : FibHeap[A, K],
) -> Unit {
  // 如果other为空，不需要操作
  if other.min == Node::Nil {
    return
  }

  // 如果self为空，直接采用other
  if self.min == Node::Nil {
    self.min = other.min
    self.size = other.size
    self.roots = other.roots
    return
  }
    if self == other {
    // 合并自身，无操作
    return
  }

  // 连接两个根链表
  let selfMin = self.min
  let otherMin = other.min

  // 使用辅助函数连接两个链表
  let selfRight = get_right(selfMin)
  let otherRight = get_right(otherMin)
  connect_right(selfMin, otherRight)
  connect_right(otherMin, selfRight)

  // 更新最小节点
  if is_less(self, otherMin, selfMin) {
    self.min = otherMin
  }

  // 更新堆的大小和根节点数量
  self.size += other.size
  self.roots += other.roots
}

///| 初始化节点为独立节点（设置自循环指针）
pub fn[A, K] make_singleton(node : Node[A, K]) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as cons_node => {
      cons_node.left = cons_node // 使用已绑定的cons_node，而不是node
      cons_node.right = cons_node
      cons_node.parent = Node::Nil
      cons_node.child = Node::Nil
    }
  }
}

///| 安全地设置左右指针
pub fn[A, K] connect_right(node : Node[A, K], right_node : Node[A, K]) -> Unit {
  match (node, right_node) {
    (Node::Cons(..) as left, Node::Cons(..) as right) => {
      left.right = right
      right.left = left
    }
    _ => () // 至少有一个是 Nil，不做任何操作
  }
}

///| 将一个节点作为另一个节点的子节点
pub fn[A, K] add_child(parent : Node[A, K], child : Node[A, K]) -> Unit {
  match (parent, child) {
    (Node::Cons(..) as p, Node::Cons(..) as c) => {
      // 设置父子关系
      c.parent = p
      match p.child {
        Node::Nil => {
          // 父节点还没有子节点
          p.child = c
          make_singleton(c)
        }
        Node::Cons(..) as first_child => {
          // 添加到现有子链表
          let first_right = first_child.right
          connect_right(first_child, c)
          connect_right(c, first_right)
        }
      }

      // 增加父节点的degree
      p.degree += 1
    }
    _ => () // 至少有一个是 Nil，不做任何操作
  }
}

///| 重置节点的标记
pub fn[A, K] reset_mark(node : Node[A, K]) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as cons_node => cons_node.marked = false
  }
}

///| 设置节点的标记
pub fn[A, K] mark_node(node : Node[A, K]) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as cons_node => cons_node.marked = true
  }
}

///| 检查节点是否被标记
pub fn[A, K] is_marked(node : Node[A, K]) -> Bool {
  match node {
    Node::Nil => false
    Node::Cons(..) as cons_node => cons_node.marked
  }
}

///| 安全地获取节点的父节点
pub fn[A, K] get_parent(node : Node[A, K]) -> Node[A, K] {
  match node {
    Node::Nil => Node::Nil
    Node::Cons(..) as cons_node => cons_node.parent
  }
}

///| 安全地获取节点的子节点
pub fn[A, K] get_child(node : Node[A, K]) -> Node[A, K] {
  match node {
    Node::Nil => Node::Nil
    Node::Cons(..) as cons_node => cons_node.child
  }
}

///| 安全地获取节点的右兄弟
pub fn[A, K] get_right(node : Node[A, K]) -> Node[A, K] {
  match node {
    Node::Nil => Node::Nil
    Node::Cons(..) as cons_node => cons_node.right
  }
}

///| 安全地获取节点的左兄弟
pub fn[A, K] get_left(node : Node[A, K]) -> Node[A, K] {
  match node {
    Node::Nil => Node::Nil
    Node::Cons(..) as cons_node => cons_node.left
  }
}

///| 安全地获取节点的值和键
pub fn[A, K] get_value_and_key(node : Node[A, K]) -> (A, K)? {
  match node {
    Node::Nil => None
    Node::Cons(..) as cons_node => Some((cons_node.content, cons_node.key))
  }
}

///| 安全地从链表中移除节点
pub fn[A : Eq, K : Eq] remove_from_list(node : Node[A, K]) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as cons_node => {
      if cons_node == cons_node.right {
        // 链表中只有这一个节点，不需要操作
        return
      }

      // 将左右节点连接起来
      match (cons_node.left, cons_node.right) {
        (Node::Cons(..) as left, Node::Cons(..) as right) => {
          left.right = right
          right.left = left
        }
        _ => () // 不应该发生
      }
    }
  }
}

///| 清除节点的所有子节点
pub fn[A, K] clear_children(node : Node[A, K]) -> Unit {
  match node {
    Node::Nil => ()
    Node::Cons(..) as cons_node => {
      cons_node.child = Node::Nil
      cons_node.degree = 0
    }
  }
}

///| 创建新节点
pub fn[A, K] create_node(value : A, key : K) -> Node[A, K] {
  let node = Node::Cons(
    content=value,
    key~,
    degree=0,
    marked=false,
    parent=Node::Nil,
    child=Node::Nil,
    left=Node::Nil, // 临时值
    right=Node::Nil, // 临时值
  )

  // 设置循环引用
  match node {
    Node::Nil => node // 不会发生
    Node::Cons(..) as cons_node => {
      cons_node.left = cons_node
      cons_node.right = cons_node
      cons_node
    }
  }
}

///| 按值查找节点，返回节点引用或 Node::Nil
pub fn[A : Eq, K : Eq] find_by_value(
  self : FibHeap[A, K],
  value : A,
) -> Node[A, K] {
  let mut count = 0
  let mut curr = self.min
  while count < self.roots && curr != Node::Nil {
    match curr {
      Node::Cons(..) as node => {
        if node.content == value {
          return curr
        }
        curr = get_right(curr)
        count += 1
      }
      Node::Nil => return Node::Nil
    }
  }
  Node::Nil
}

///| 按键查找节点，返回节点引用或 Node::Nil
pub fn[A : Eq, K : Eq] find_by_key(self : FibHeap[A, K], key : K) -> Node[A, K] {
  let mut count = 0
  let mut curr = self.min
  while count < self.roots && curr != Node::Nil {
    match curr {
      Node::Cons(..) as node => {
        if node.key == key {
          return curr
        }
        curr = get_right(curr)
        count += 1
      }
      Node::Nil => break
    }
  }
  Node::Nil
}

///| 清空堆，重置所有属性
pub fn[A, K] clear(self : FibHeap[A, K]) -> Unit {
  self.size = 0
  self.min = Node::Nil
  self.roots = 0
}

///|
pub fn[A : Eq, K : Eq] to_array(self : FibHeap[A, K]) -> Array[(A, K)] {
  let result = Array::new()
  let mut count = 0
  let mut curr = self.min
  while count < self.roots && curr != Node::Nil {
    match curr {
      Node::Cons(..) as node => {
        collect_node(node, result)
        curr = get_right(curr)
        count += 1
      }
      Node::Nil => break
    }
  }
  result
}

// 递归收集节点及其所有子节点

///|
pub fn[A : Eq, K : Eq] collect_node(
  node : Node[A, K],
  result : Array[(A, K)],
) -> Unit {
  match node {
    Node::Cons(..) as n => {
      result.push((n.content, n.key))
      let child = get_child(n)
      if child != Node::Nil {
        // 遍历子链表
        let mut curr = child
        let mut first = true
        while first || curr != child {
          collect_node(curr, result)
          curr = get_right(curr)
          first = false
        }
      }
    }
    Node::Nil => ()
  }
}

///| 支持堆的深拷贝，返回堆的完整副本
pub fn[A : Eq, K : Eq] clone(self : FibHeap[A, K]) -> FibHeap[A, K] {
  let new_heap = new(self.compare)
  let arr = self.to_array()
  for i in 0.. Unit {
  let len = @cmp.minimum(values.length(), keys.length())
  for i in 0.. Array[(A, K)] {
  let arr = self.to_array()
  arr.sort_by((a, b) => (self.compare)(a.1, b.1))
  arr
}