local Rx = require 'Rx'

--------------------------------------------------------------------------------

local priorityQueuePrototype = {

    _items = false,
    _length = 0

}

--------------------------------------------------------------------------------

function priorityQueuePrototype:__init()

    self._items = {}

end

--------------------------------------------------------------------------------

local function isHigherPriority(self, left, right)

    local leftValue = self._items[left].value
    local rightValue = self._items[right].value

    return leftValue < rightValue

end

--------------------------------------------------------------------------------

local function percolate(self, index)

    assert(index >= 1 and index <= self._length)
        -- NOTE: RxJS does a quiet return here. I was unable to generate a test
        -- case that reached this line. If you encounter this assert, please let
        -- me know. [scouten]

    local parent = math.floor(index / 2)

    if parent < 1 or parent == index then
        return
    end

    if isHigherPriority(self, index, parent) then
        local temp = self._items[index]
        self._items[index] = self._items[parent]
        self._items[parent] = temp
        percolate(self, parent)
    end

end

--------------------------------------------------------------------------------

local function heapify(self, index)

    index = tonumber(index) or 1

    if index > self._length or index < 1 then return end
        -- Working around a possible bug in luacov here: If we break this out
        -- into separate lines, the "return" statement isn't seen as covered.

    local left = 2 * index
    local right = 2 * index + 1
    local first = index

    if left <= self._length and isHigherPriority(self, left, first) then
        first = left
    end

    if right <= self._length and isHigherPriority(self, right, first) then
        first = right
    end

    if first ~= index then
        local temp = self._items[index]
        self._items[index] = self._items[first]
        self._items[first] = temp
        heapify(self, first)
    end

end

--------------------------------------------------------------------------------

function priorityQueuePrototype:peek()

    return self._items[1] and self._items[1].value

end

--------------------------------------------------------------------------------

function priorityQueuePrototype:removeAt(index)

    local oldLength = self._length
    local newLength = oldLength - 1
    self._length = newLength

    if newLength > 0 then
        self._items[index] = self._items[oldLength]
    else
        -- reclaim space by freeing items
        self._items = {}
    end
    self._items[oldLength] = nil

    heapify(self)

end

--------------------------------------------------------------------------------

function priorityQueuePrototype:dequeue()

    local result = self:peek()
    self:removeAt(1)
    return result

end

--------------------------------------------------------------------------------

local idCounter = 0

--------------------------------------------------------------------------------

function priorityQueuePrototype:enqueue(item)

    local index = self._length + 1
    self._length = index

    idCounter = idCounter + 1

    self._items[index] = { id = idCounter, value = item }

    percolate(self, index)

end

--------------------------------------------------------------------------------

function priorityQueuePrototype:remove(item)

    for i, nextItem in ipairs(self._items) do

        if nextItem.value == item then
            self:removeAt(i)
            return true
        end

    end

    return false

end

--------------------------------------------------------------------------------

function priorityQueuePrototype:length()

    return self._length

end

--------------------------------------------------------------------------------

return Rx.Class('Rx.internals.PriorityQueue', priorityQueuePrototype)
