---
--- 一个基于最小堆的定时器实现
--- Created by colin.
---
local setmetatable = setmetatable
local tunpack = table.unpack
local xpcall = xpcall
local traceback = debug.traceback

---@class TimerNode 时间结点
---@field time number 超时的时间点
---@field period number 周期触发的间隔，为0表示没有周期触发
---@field callback fun(node: TimerNode, ...) 超时回调
---@field args any[] 回调函数的参数，在schedule可以传入自定义参数
---@field index number 跟踪当前结点的堆索引

---@class Timer 定时器
---@field heap TimerNode[]
local MHTimer = {}

local TimerMT = {
    __index = MHTimer,
    __len = function(t)
        return #t.heap
    end,
}

---向上移动结点
---@param heap TimerNode[] 最小堆
---@param index number 开始比较的索引
---@param node TimerNode 将占坑的结点
local function _heap_shift_up(heap, index, node)
    local parent = index // 2
    while parent >= 1 and heap[parent].time > node.time do
        heap[index] = heap[parent]
        heap[index].index = index
        index = parent
        parent = index // 2
    end
    heap[index] = node
    heap[index].index = index
end

---向下移动结点
---@param heap TimerNode[] 最小堆
---@param index number 开始比较的索引
---@param node TimerNode 将占坑的结点
local function _heap_shift_down(heap, index, node)
    local size = #heap + 1
    local child = index * 2 + 1
    while child <= size do
        if child == size or heap[child].time > heap[child-1].time then
            child = child - 1
        end  -- 取值较小的孩子比较
        if node.time > heap[child].time then
            heap[index] = heap[child]
            heap[index].index = index
            index = child
            child = index * 2 + 1
        else
            break
        end
    end
    heap[index] = node
    heap[index].index = index
end

---增加最小堆元素
---@param heap TimerNode[]
---@param node TimerNode
local function _heap_add(heap, node)
    _heap_shift_up(heap, #heap + 1, node)
end

---删除最小堆元素
---@param heap TimerNode[]
---@param node TimerNode
local function _heap_remove(heap, node)
    if node.index > 0 then
        local sz = #heap
        local lastnode = heap[sz]
        heap[sz] = nil
        if node ~= lastnode then
            local parent = node.index // 2
            if parent >= 1 and heap[parent].time > lastnode.time then
                _heap_shift_up(heap, node.index, lastnode)
            else
                _heap_shift_down(heap, node.index, lastnode)
            end
        end
        node.index = 0
    end
end

---调整元素的位置， 由于元素的时间点变化，要将其调整至合适的位置
---@param heap TimerNode[]
---@param node TimerNode
local function _head_adjust(heap, node)
    if node.index > 0 then
        local parent = node.index // 2
        if parent >= 1 and heap[parent].time > node.time then
            _heap_shift_up(heap, node.index, node)
        else
            _heap_shift_down(heap, node.index, node)
        end
    end
end

---创建一个Timer
function MHTimer.new()
    return setmetatable({
        heap = {},
    }, TimerMT)
end

---更新时间点，触发超时事件，外部要不断调用该函数，并传入当前时间点
---@param time number 时间点
function MHTimer:tick(time)
    local heap = self.heap
    ---@type TimerNode
    local node
    while #heap > 0 do
        node = heap[1]
        if time >= node.time then   -- timeout
            if node.callback then
                local ok, err = xpcall(node.callback, traceback, node, tunpack(node.args))
                if not ok then
                    print(err)
                end
            end
            if node.period > 0 then
                node.time = node.time + node.period
                _head_adjust(heap, node)
            else
                _heap_remove(heap, node)
            end
        else
            break
        end
    end
end

---增加调度事件
---@param first number 首次发生的时间点，注意不是间隔
---@param period number 周期性触发的间隔，如果为0表示没有周期性触发
---@param callback fun(node: TimerNode, ...) 触发时的回调函数，以及附加的任意参数
---@return TimerNode 返回结点
function MHTimer:schedule(first, period, callback, ...)
    ---@type TimerNode
    local node = {
        time = first,
        period = period or 0,
        callback = callback,
        args = {...},
        index = 0,
    }
    _heap_add(self.heap, node)
    return node
end

---删除调试事件
---@param node TimerNode
function MHTimer:unschedule(node)
    _heap_remove(self.heap, node)
end

return MHTimer