--
--
-- Original file Downloaded from
-- https://github.com/chen0040/lua-graph
--
-- Original Algorithm described in
-- https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

	--[[ This algorithm has been modified by Mark DiVecchio April 2020 to
	support the concept of a double vertex graph as described in the
	paper: 2005 Jun 22 - Selecting sets of disjoint paths in a railway graph - V.S. Jaddoe - Universiteit van Amsterdam
	--]]
	
local IndexedMinPQ = {}
IndexedMinPQ.__index = IndexedMinPQ

function IndexedMinPQ.create(comparator)
    local s = {}
    setmetatable(s, IndexedMinPQ)

    if comparator == nil then
        comparator = function(a1, a2) return a1 - a2 end
    end

    s.keys = {}
    s.pq = {}
    s.qp = {}
    s.N = 0
    s.comparator = comparator
    return s;
end
	
function IndexedMinPQ:dump(func)	-- mcd apply 'func' to the queue
	return "pq : " .. func(self.pq)
	end
	
function IndexedMinPQ:less(a1, a2)
    return self.comparator(a1, a2) < 0
end

function IndexedMinPQ:exchange(a, i, j)
    local temp = a[i]
    a[i] = a[j]
    a[j] = temp
end

function IndexedMinPQ:add_with_priority(index, key)
    self.keys[index] = key
    self.N = self.N + 1
    self.pq[self.N] = index
    self.qp[index] = self.N

    self:swim(self.N)
end

function IndexedMinPQ:swim(k)
    while k > 1 do
        local parent = math.floor(k / 2)
        if self:less(self.keys[self.pq[k]], self.keys[self.pq[parent]]) then
            self:exchange(self.pq, k, parent)
            self.qp[self.pq[k]] = k
            self.qp[self.pq[parent]] = parent
        else
            break
        end
    end

end

function IndexedMinPQ:minKey()
    return self.keys[self.pq[1]]
end

function IndexedMinPQ:fetchMin()
	--print("pq : " .. dumpx(self.pq));
    return self.pq[1]
end

function IndexedMinPQ:removeMin()
    if self.N == 0 then
        return nil
    end

    local key = self.keys[self.pq[1]]
    self:exchange(self.pq, 1, self.N)
    self.qp[self.pq[1]]=1
    self.qp[self.pq[self.N]]= self.N
    self.N = self.N - 1

    self:sink(1)

    return key
end

function IndexedMinPQ:sink(k)
    while k * 2 <= self.N do
        local child = k * 2
        if child < self.N and self:less(self.keys[self.pq[child+1]], self.keys[self.pq[child]]) then
            child = child + 1
        end

        if self:less(self.keys[self.pq[child]], self.keys[self.pq[k]]) then
            self:exchange(self.pq, child, k)
            self.qp[self.pq[child]] = child
            self.qp[self.pq[k]] = k
        else
            break
        end
    end
end

function IndexedMinPQ:decrease_priority(index, key)
    if self:less(key, self.keys[index]) then
        local position = self.qp[index]
        self.keys[index] = key
        self:swim(position)
    end
end

function IndexedMinPQ:contains(index)
    return self.keys[index] ~= nil
end

function IndexedMinPQ:size()
    return self.N
end

function IndexedMinPQ:isEmpty()
	--print("self.N = " .. self.N)
	--print("pq : " .. dumpx(self.pq));
    return self.N == 0
end

return IndexedMinPQ

