--[[
---------------------------------------------------------------------------
Remote Train Control Program for Windows

© Copyright 2020 by Mark DiVecchio

	This file is part of Remote Train Control.

	Remote Train Control is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	Remote Train Control is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Remote Train Control.  If not, see <http://www.gnu.org/licenses/>.

 Home Page : http://www.silogic.com/trains/RTC_Running.html
---------------------------------------------------------------------------]]
--
-- 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
	--]]

	--[[ from Wikipedia "A min-priority queue is an abstract data type that provides 
	3 basic operations : add_with_priority(), decrease_priority() and extract_min()."
	--]]
	
local Double_Vertex = {}
Double_Vertex.__index = Double_Vertex
	
function Double_Vertex.create()
    local s = {}
    setmetatable(s, Double_Vertex)

    s.edgeTo = {}
    s.source = -1
    s.marked = {}
    return s
end
--[[---------------------------------------------------------------------------------------]]
function dumpx(o)
   if type(o) == 'table' then
      local s = '{ '
      for k,v in pairs(o) do
         if type(k) ~= 'number' then k = '"'..k..'"' end
		 -- optional : print(k,v)
         s = s .. '['..k..'] = ' .. dumpx(v) .. ','
      end
      return s .. '} \n'	-- mcd
   else
      return tostring(o)
   end
end
--[[---------------------------------------------------------------------------------------]]
function Double_Vertex:run(G, s)
    self.edgeTo = {}
    self.cost = {}
    self.marked = {}
    self.source = s
	self.VertexNext = {};	-- need a vertex if true
	self.Reached = {};		-- vertex has been reached if true
	
    for i = 0, G:vertexCount()-1 do	-- initialize vertices
		-- for each vertex in G
        local v = G:vertexAt(i)
        self.marked[v] = false
        self.edgeTo[v] = -1			-- no edge yet
        self.cost[v] = math.huge	-- huge cost 
    end
	-- create vertex priority queue pq
    local pq = require('rtcgraphs.data.IndexedMinPQ').create()
    self.cost[s] = 0	-- initialize cost to 0 for source vertex
	self.VertexNext[s] = true;	-- need a vertex
	self.Reached[s] = true;	-- vertex has been reached
    pq:add_with_priority(s, self.cost[s])	-- add with priority source vertex and cost
	
	--[[ from Wikipedia "Instead of filling the priority queue with all nodes in 
	the initialization phase, it is also possible to initialize it to contain only 
	source; then, inside the if 'self.cost[w] > self.cost[v] + e.weight' block, the node must be inserted 
	if not already in the queue (instead of performing a decrease_priority operation)."
	--]]

    --while pq:isEmpty() == false do	-- original
    while not pq:isEmpty() do		-- while pq is not empty -- the main loop
		if (Debug() > 0) then
			print(pq:dump(dumpx))		-- dump the priority queue
		end
        local v = pq:fetchMin()		-- get best vertex
        pq:removeMin()				-- and remove it from pq
        self.marked[v] = true	-- mcd this is only place that marked[v] is set true
		if (Debug() > 5 ) then print("---- BEGIN isEmpty() LOOP ------ self.marked[" .. v .. "] = " .. tostring(self.marked[v]) .. " at start of while loop"); end
		--print("self.Reached " .. dumpx(self.Reached));
		local e;
        local adj_v = G:adj(v)
        for i=0,adj_v:size()-1 do	-- for each neighbor of vertex
			if (Debug() > 5 ) then print("--- BEGIN ADJACENT VERTEX LOOP --- : " .. i); end
            e = adj_v:get(i)
			--print(e.v .. " -> " .. e.w .. " weight = " .. e.weight .. " " .. " VertexNext = " .. tostring(self.VertexNext[e.v]));
			--print("self.Reached[" .. e.v .. "] = " .. tostring(self.Reached[e.v]));
			--print("self.Reached[" .. e.w .. "] = " .. tostring(self.Reached[e.w]));
			if (not self.marked[e.w]) then 
				if (self.VertexNext[e.v]) then
					-- vertex next
					if (e.weight == 0) then	-- got a vertex
						-- weight of zero indicates a double vertex
						if (Debug() > 1) then
							print("@Vertex : " .. e.v .. " -> " .. e.w .. " weight = " .. e.weight .. " VertexNext = " .. tostring(self.VertexNext[e.v]));						
						end
						self:relax(G, e, pq)
					end;
					else
					-- Edge next
					if (e.weight > 0) then	-- got an edge
						-- weight > 0 indicates an edge
						if (Debug() > 3) then
							print("***************self.Reached[" .. e.w .. "] = " .. tostring(self.Reached[e.w]));
							end
						if (not (self.Reached[e.w])) then
							self.Reached[G:othernode(e.w)] = true;	-- vertex has been reached
							if (Debug() > 3) then
								print("--------- node other(" .. e.w .. ") = " .. G:othernode(e.w));
								end
							if (Debug() > 1) then
								print("@Edge : " .. e.v .. " -> " .. e.w .. " weight = " .. e.weight .. " VertexNext = " .. tostring(self.VertexNext[e.v]));					
								end
							self:relax(G, e, pq)
						end
					end;
				end
			end
			if (Debug() > 5 ) then print("--- END ADJACENT VERTEX LOOP --- self.marked[" .. e.w .. "] = " .. tostring(self.marked[e.w])); end
			self.VertexNext[e.w] = not self.VertexNext[e.v]	-- on to next piece of route
        end		
    end
	if (Debug() > 5 ) then print("------ END isEmpty() LOOP ------"); end;
	--print("IndexedMinPQ created: s = " .. s .. " self.cost[s] = " .. self.cost[s])	-- mcd
	--print("self.marked : ".. dumpx(self.marked));	-- mcd
	--print("self.cost : " .. dumpx(self.cost));	-- mcd
	--print("self.edgeTo : " .. dumpx(self.edgeTo));	-- mcd
end

function Double_Vertex:relax(G, e, pq)
    local from = e:from()
    local to = e:to()
	--print("relax : from = " .. from .. " to = " .. to .. " self.marked[to] = " .. tostring(self.marked[to]))

    if self.marked[to] then
		--print("self.marked[" .. to .. "] = true");
        return
    end
	
    if self.cost[to] > self.cost[from] + e.weight then
        self.cost[to] = self.cost[from] + e.weight
        self.edgeTo[to] = e	-- put the edge into the edgeTo table
		if (Debug() > 1) then
			print("self.edgeTo[to] added : from = " .. from .. " to = " .. to .. " self.cost[from] = "  .. self.cost[from] .. " self.cost[to] = " ..
				self.cost[to] .. " weight = " .. e.weight)
			end
		if (Debug() > 5) then
			print("self.edgeTo : " .. dumpx(self.edgeTo));
			end
        if pq:contains(to) then
            pq:decrease_priority(to, self.cost[to])	-- next vertex in pq, just adjust the priority
        else
            pq:add_with_priority(to, self.cost[to])	-- next vertex not in pq, add it with priority
        end
    end
	--print("relaxed : from = " .. from .. " to = " .. to .. " self.cost[from] = "  .. self.cost[from] .. " self.cost[to] = " ..
	--	self.cost[to] .. " weight = " .. e.weight)

end

function Double_Vertex:hasPathTo(v)
    return self.marked[v]
end

function Double_Vertex:getPathLength(v)
    return self.cost[v]
end

function Double_Vertex:getPathTo(v)
    local stack = require('rtcgraphs.data.stack').create()
    local x = v	-- v is the target vertex
	--print("Double_Vertex:getPathTo() " .. self.source .. " -> " .. v);
    while x ~= self.source do	-- x is the target vertex, track back until you hit the source vertex
        local e = self.edgeTo[x]	-- get the edge to the target
		--print(" self.edgeTo[" .. x .. "] -> e:other[" .. x .. "] = " .. e:other(x));
		--print("path : " .. dumpx(stack:toList()));
        stack:push(e)	-- push the edge onto the stack
        x = e:other(x)	-- traverse from target to source
    end
    return stack:toList()
end


return Double_Vertex

