// Copyright 2025 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

///|

///|
pub(all) enum Node[A, K] {
  Nil
  Cons(
    content~ : A, // 节点值
    mut key~ : K, // 节点键(用于比较)
    mut degree~ : Int, // 子节点数量
    mut marked~ : Bool, // 是否标记(用于级联剪切)
    mut parent~ : Node[A, K], // 父节点
    mut child~ : Node[A, K], // 第一个子节点
    mut left~ : Node[A, K], // 左兄弟
    mut right~ : Node[A, K] // 右兄弟
  )
} derive(Show)

// 手动实现Eq trait，只比较节点身份而不是结构相等
// 这避免了循环引用导致的无限递归

///|
pub impl[A : Eq, K : Eq] Eq for Node[A, K] with op_equal(
  self : Node[A, K],
  other : Node[A, K],
) -> Bool {
  match (self, other) {
    (Node::Nil, Node::Nil) => true
    (Node::Cons(..) as a, Node::Cons(..) as b) =>
      // 比较引用相等性：比较内容和键值是否相同
      // 避免比较循环引用的字段(parent, child, left, right)
      a.content == b.content &&
      a.key == b.key &&
      a.degree == b.degree &&
      a.marked == b.marked
    _ => false
  }
}

///|
pub(all) struct FibHeap[A, K] {
  mut size : Int // 堆中节点总数
  mut min : Node[A, K] // 指向最小节点的引用
  mut roots : Int // 根链表中的节点数

  // 用于比较键的函数
  compare : (K, K) -> Int
} derive(Show)

///|
pub impl[A : Eq, K : Eq] Eq for FibHeap[A, K] with op_equal(
  self : FibHeap[A, K],
  other : FibHeap[A, K],
) -> Bool {
  self.size == other.size && self.roots == other.roots && self.min == other.min
  // compare 函数无法直接比较，只比较堆的状态
}