---@meta binaryheap

--------------------------------------------------------------------------------
-- Binary heap 模块
--------------------------------------------------------------------------------

---@alias binaryheap_compare<V> fun(a:V, b:V):boolean
---@alias binaryheap_swap<V, P> fun(heap:binaryheap_base_heap<V, P>, idx1:integer, idx2:integer)
---@alias binaryheap_erase<V, P> fun(heap:binaryheap_base_heap<V, P>, pos:integer)

---@class binaryheap_base_heap<V, P>
---@field values V[] 排序值列表
---@field payloads? P[] payload 列表，unique heap 使用
---@field reverse? table<P, integer> payload 到位置的映射，unique heap 使用
---@field swap binaryheap_swap<V, P> 交换两个位置
---@field erase binaryheap_erase<V, P> 删除指定位置
---@field lt binaryheap_compare<V> 比较函数
local base_heap = {}

--- 将指定位置的元素向上调整。
---@param pos integer 位置
function base_heap:bubbleUp(pos) end

--- 将指定位置的元素向下调整。
---@param pos integer 位置
function base_heap:sinkDown(pos) end

---@class binaryheap_plain_heap<V>: binaryheap_base_heap<V, any>
local plain_heap = {}

--- 更新指定位置的值。
---@param pos integer 位置
---@param newValue V 新值
function plain_heap:update(pos, newValue) end

--- 移除指定位置的值。
---@param pos integer 位置
---@return V? value 被移除的值；位置无效时为 nil
function plain_heap:remove(pos) end

--- 插入一个值。
---@param value V 值
function plain_heap:insert(value) end

--- 弹出堆顶值。
---@return V? value 堆顶值；堆为空时为 nil
function plain_heap:pop() end

--- 查看堆顶值，不移除。
---@return V? value 堆顶值；堆为空时为 nil
function plain_heap:peek() end

--- 返回堆内元素数量。
---@return integer count 元素数量
function plain_heap:size() end

---@class binaryheap_unique_heap<V, P>: binaryheap_base_heap<V, P>
---@field payloads P[] payload 列表
---@field reverse table<P, integer> payload 到位置的映射
local unique_heap = {}

--- 更新指定 payload 对应的值。
---@param payload P payload
---@param newValue V 新值
function unique_heap:update(payload, newValue) end

--- 插入一个值和唯一 payload。
---@param value V 排序值
---@param payload P 唯一 payload
function unique_heap:insert(value, payload) end

--- 移除指定 payload 对应的项。
---@param payload P payload
---@return V? value 被移除的值；未找到时为 nil
---@return P? payload 被移除的 payload
function unique_heap:remove(payload) end

--- 弹出堆顶项。
---@return P? payload 堆顶 payload；堆为空时为 nil
---@return V? value 堆顶值
function unique_heap:pop() end

--- 查看堆顶项，不移除。
---@return P? payload 堆顶 payload；堆为空时为 nil
---@return V? value 堆顶值
function unique_heap:peek() end

--- 查看堆顶值，不移除。
---@return V? value 堆顶值；堆为空时为 nil
function unique_heap:peekValue() end

--- 按 payload 查询对应的值。
---@param payload P payload
---@return V? value 对应值；未找到时为 nil
function unique_heap:valueByPayload(payload) end

--- 返回堆内元素数量。
---@return integer count 元素数量
function unique_heap:size() end

---@class binaryheap*
---@type binaryheap*
local M = {}

--- 创建底层二叉堆。
---
--- 一般脚本应使用 `minHeap`、`maxHeap`、`minUnique` 或 `maxUnique`。
---@generic V, P
---@param swap binaryheap_swap<V, P> 交换两个位置的回调
---@param erase binaryheap_erase<V, P> 删除位置的回调
---@param lt binaryheap_compare<V> 小于比较函数
---@return binaryheap_base_heap<V, P> heap 底层 heap
function M.binaryHeap(swap, erase, lt) end

--- 创建普通最小堆，最小值位于堆顶。
---@generic V
---@param lt? binaryheap_compare<V> 小于比较函数，默认使用 `<`
---@return binaryheap_plain_heap<V> heap 普通 heap
function M.minHeap(lt) end

--- 创建普通最大堆，最大值位于堆顶。
---@generic V
---@param gt? binaryheap_compare<V> 大于比较函数，默认使用 `>`
---@return binaryheap_plain_heap<V> heap 普通 heap
function M.maxHeap(gt) end

--- 创建带唯一 payload 的最小堆。
---
--- 管理函数使用 payload 而不是位置来定位元素。
---@generic V, P
---@param lt? binaryheap_compare<V> 小于比较函数，默认使用 `<`
---@return binaryheap_unique_heap<V, P> heap unique heap
function M.minUnique(lt) end

--- 创建带唯一 payload 的最大堆。
---
--- 管理函数使用 payload 而不是位置来定位元素。
---@generic V, P
---@param gt? binaryheap_compare<V> 大于比较函数，默认使用 `>`
---@return binaryheap_unique_heap<V, P> heap unique heap
function M.maxUnique(gt) end

return M
