---@meta binaryheap

--------------------------------------------------------------------------------
-- Binary heap module
--------------------------------------------------------------------------------

---@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[] Sorted list of values
---@field payloads? P[] payload List, unique heap use
---@field reverse? table<P, integer> payload Mapping to location, unique heap uses
---@field swap binaryheap_swap<V, P> Swap two positions
---@field erase binaryheap_erase<V, P> Delete specified location
---@field lt binaryheap_compare<V> comparison function
local base_heap = {}

--- Adjusts the element at the specified position upward.
---@param pos integer location
function base_heap:bubbleUp(pos) end

--- Adjusts the element at the specified position downward.
---@param pos integer location
function base_heap:sinkDown(pos) end

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

--- Updates the value at the specified location.
---@param pos integer location
---@param newValue V new value
function plain_heap:update(pos, newValue) end

--- Removes the value at the specified position.
---@param pos integer location
---@return V? value The value to be removed; nil if the position is invalid
function plain_heap:remove(pos) end

--- Insert a value.
---@param value V value
function plain_heap:insert(value) end

--- Pop the top value of the heap.
---@return V? value The value at the top of the heap; nil when the heap is empty
function plain_heap:pop() end

--- Check the top value of the heap and do not remove it.
---@return V? value The value at the top of the heap; nil when the heap is empty
function plain_heap:peek() end

--- Returns the number of elements in the heap.
---@return integer count Number of elements
function plain_heap:size() end

---@class binaryheap_unique_heap<V, P>: binaryheap_base_heap<V, P>
---@field payloads P[] payload list
---@field reverse table<P, integer> payload mapping to location
local unique_heap = {}

--- Update the value corresponding to the specified payload.
---@param payload P payload
---@param newValue V new value
function unique_heap:update(payload, newValue) end

--- Insert a value and unique payload.
---@param value V sort value
---@param payload P unique payload
function unique_heap:insert(value, payload) end

--- Remove the item corresponding to the specified payload.
---@param payload P payload
---@return V? value The value to be removed; nil if not found
---@return P? payload Removed payload
function unique_heap:remove(payload) end

--- Pop the top item of the heap.
---@return P? payload Payload at the top of the heap; nil when the heap is empty
---@return V? value Top value of heap
function unique_heap:pop() end

--- View the top item of the heap without removing it.
---@return P? payload Payload at the top of the heap; nil when the heap is empty
---@return V? value Top value of heap
function unique_heap:peek() end

--- Check the top value of the heap and do not remove it.
---@return V? value The value at the top of the heap; nil when the heap is empty
function unique_heap:peekValue() end

--- Query the corresponding value by payload.
---@param payload P payload
---@return V? value Corresponding value; nil if not found
function unique_heap:valueByPayload(payload) end

--- Returns the number of elements in the heap.
---@return integer count Number of elements
function unique_heap:size() end

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

--- Create the underlying binary heap.
---
--- Normal scripts should use `minHeap`, `maxHeap`, `minUnique` or `maxUnique`.
---@generic V, P
---@param swap binaryheap_swap<V, P> Swap callbacks for two positions
---@param erase binaryheap_erase<V, P> Delete location callback
---@param lt binaryheap_compare<V> less than comparison function
---@return binaryheap_base_heap<V, P> heap underlying heap
function M.binaryHeap(swap, erase, lt) end

--- Create a normal min-heap with the smallest value at the top.
---@generic V
---@param lt? binaryheap_compare<V> Less than comparison function, defaults to `<`
---@return binaryheap_plain_heap<V> heap Ordinary heap
function M.minHeap(lt) end

--- Create a normal max-heap with the maximum value at the top.
---@generic V
---@param gt? binaryheap_compare<V> Greater than comparison function, default to `>`
---@return binaryheap_plain_heap<V> heap Ordinary heap
function M.maxHeap(gt) end

--- Create a min-heap with a unique payload.
---
--- Management functions use payload instead of position to locate elements.
---@generic V, P
---@param lt? binaryheap_compare<V> Less than comparison function, defaults to `<`
---@return binaryheap_unique_heap<V, P> heap unique heap
function M.minUnique(lt) end

--- Create the largest heap with a unique payload.
---
--- Management functions use payload instead of position to locate elements.
---@generic V, P
---@param gt? binaryheap_compare<V> Greater than comparison function, default to `>`
---@return binaryheap_unique_heap<V, P> heap unique heap
function M.maxUnique(gt) end

return M
