--[[
---------------------------------------------------------------------------
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
--
-- error fixed in addEdge by Mark DiVecchio April 2020

	--[[ This algorithm has been modified by Mark DiVecchio April 2020 to
	support the concept of a double vertex directed 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 graph = {}

graph.__index = graph

graph.Edge = {}
graph.Edge.__index = graph.Edge
graph.EdgeCount = 0;	-- Counts the number of edges created
graph.dv = {}			-- holds the other vertex in a double vertex

function graph.Edge.create(v, w, weight, BlockNo, position, TIU, AIU, Channel)
    local s = {}
    setmetatable(s, graph.Edge)

    if weight == nil then
        weight = 0	-- its a double vertex
    end
	
	if (weight == 0) then
		graph.dv[v] = w;
		graph.dv[w] = v;
	end
	
    s.v = v
    s.w = w
    s.weight = weight
	s.p = position;	-- position for switch tracks - true = normal, false = reverse
	s.TIU = TIU;
	s.AIU = AIU;
	s.Channel = Channel;
	s.BlockNo = BlockNo;

	graph.EdgeCount = graph.EdgeCount + 1;
    return s
end

function graph.Edge:from()
    return self.v
end

function graph.Edge:to()
    return self.w;
end

function graph.Edge:either()
    return self.v
end

function graph.Edge:control()
	return self.p, self.TIU, self.AIU, self.Channel, self.BlockNo;
	end
	
function graph.Edge:fetchWeight()
	return self.weight;
	end

function graph.Edge:changeWeight(weight)
	local oldweight = self.weight
	self.weight = weight
	return oldweight
	end

function graph.Edge:other(x)
    if x == self.v then
        return self.w
    else
        return self.v
    end

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'
   else
      return tostring(o)
   end
end
--[[---------------------------------------------------------------------------------------]]

function graph.create(V, directed)
    local g = {}
    setmetatable(g, graph)

    if directed == nil then
        directed = true
    end

    g.vertexList = require('rtcgraphs.data.list').create()
    g.adjList = {}
    for v = 0,V-1 do
        g.vertexList:add(v)
        g.adjList[v] = require('rtcgraphs.data.list').create()
    end
    g.directed = directed
    return g
end

function graph:vertexCount()
    return self.vertexList:size()
end

function graph:edgeCount()
    return self.EdgeCount
end

function graph:vertices()
    return self.vertexList
end

function graph:othernode(x)
	return self.dv[x]
end

function graph:dumpdv()
	return " dv = " .. dumpx(self.dv)
	end

function graph.createFromVertexList(vertices, directed)
    local g = {}
    setmetatable(g, graph)

    if directed == nil then
        directed = true
    end

    g.vertexList = vertices
    g.adjList = {}
    for i = 0,g.vertexList:size()-1 do
        local v = g.vertexList:get(i)
        g.adjList[v] = require('rtcgraphs.data.list').create()
    end
    g.directed = directed

    return g
end

function graph:addVertexIfNotExists(v)
    if self.vertexList:contains(v) then
        return false
    else
        self.vertexList:add(v)
        self.adjList[v] = require('rtcgraphs.data.list').create()
        return true
    end
end

function graph:removeVertex(v)
    if self.vertexList:contains(v) then
        self.vertexList:remove(v)
        self.adjList[v] = nil
        for i=0,self.vertexList:size()-1 do
            local w = self.vertexList:get(i)
            local adj_w = self.adjList[w]
            for k = 0,adj_w:size()-1 do
                local e = adj_w:get(k)
                if e:other(w) == v then
                    adj_w:removeAt(k)
                    break
                end

            end

        end

    end
end

function graph:containsVertex(v)
    return self.vertexList:contains(v)
end

function graph:adj(v)
    return self.adjList[v]
end

function graph:addUndirectedEdge(v, w, weight, BlockNo, position, TIU, AIU, Channel)	-- mcd
	if (weight == nil) then
		weight = 0
		end	
    local e = graph.Edge.create(v, w, weight, BlockNo, position, TIU, AIU, Channel)	-- mcd	
    self:addVertexIfNotExists(v)
    self:addVertexIfNotExists(w)
    --if self.directed then
    --    self.adjList[e:from()]:add(e)
    --else
        self.adjList[e:from()]:add(e)
		local ee = graph.Edge.create(w, v, weight, BlockNo, position, TIU, AIU, Channel)	-- mcd -- this line was missing in the original code
        self.adjList[e:to()]:add(ee)	-- mcd -- this line was different in the original code
    --end

end

function graph:addDoubleVertex(v, w)		-- mcd
    local e = graph.Edge.create(v, w, 0)	-- mcd	
    self:addVertexIfNotExists(v)
    self:addVertexIfNotExists(w)
    self.adjList[e:from()]:add(e)
	local ee = graph.Edge.create(w, v, 0)	-- mcd -- this line was missing in the original code
    self.adjList[e:to()]:add(ee)			-- mcd -- this line was different in the original code
end

function graph:addDirectedEdge(v, w, weight, BlockNo)	-- mcd
	if (weight == nil) then
		weight = 0
		end	
    local e = graph.Edge.create(v, w, weight, BlockNo)	-- mcd	
    self:addVertexIfNotExists(v)
    self:addVertexIfNotExists(w)
    self.adjList[e:from()]:add(e)
end

function graph:addSwitchTrackold(common, normal, reverse, TIU, AIU, Channel)
	local switchtrackweight = 1;
	self:addUndirectedEdge(common, normal, switchtrackweight, true, TIU, AIU, Channel)
	self:addUndirectedEdge(common, reverse, switchtrackweight, false, TIU, AIU, Channel)
end


function graph:addSwitchTrack(common, normal, reverse, Sw)
	local switchtrackweight = 1;
	self:addUndirectedEdge(common, normal, switchtrackweight, nil, true, Switches[Sw][TIU_NUMBER], Switches[Sw][AIU_NUMBER], Switches[Sw][CHAN_NUMBER])
	self:addUndirectedEdge(common, reverse, switchtrackweight, nil, false, Switches[Sw][TIU_NUMBER], Switches[Sw][AIU_NUMBER], Switches[Sw][CHAN_NUMBER])
end


function graph:reverse()
    local g = graph.createFromVertexList(self.vertexList, self.directed)
    for k=0,self:vertexCount()-1 do
        local v = self:vertexAt(k)
        local adj_v = self:adj(v)
        for i=0,adj_v:size()-1 do
            local e = adj_v:get(i)
            g:addEdge(e:to(), e:from(), e.weight)
        end

    end

    return g
end

function graph:vertexAt(i)
    return self.vertexList:get(i)
end

function graph:edges()
    local list = require('rtcgraphs.data.list').create()

    for i=0,self.vertexList:size()-1 do
        local v = self.vertexList:get(i)
        local adj_v = self:adj(v)
        for i=0,adj_v:size()-1 do
            local e = adj_v:get(i)
            local w = e:other(v)
            if self.directed == true or w > v then
                list:add(e)
            end

        end

    end

    return list
end

function graph:hasEdge(v, w)
    local adj_v = self:adj(v)
    for i=0,adj_v:size()-1 do
        local e = adj_v:get(i)
        if e:to() == w then
            return true
        end
    end
    return false
end

function graph:findEdge(v, w)
    local adj_v = self:adj(v)
    for i=0,adj_v:size()-1 do
        local e = adj_v:get(i)
        if e:to() == w then
            return e
        end
    end
    return nil
end

return graph

