-- -----------------------------------------------------------------------------
-- SimNetwork
-- simulation.lua
-- Simulation Engine
-- -----------------------------------------------------------------------------

SimNetwork_SIMULATION = true

if not SimNetwork_DATA		then dofile("data.lua")	end
--if not SimNetwork_SCENE	then dofile("scene.lua")	end

INITIAL_CAPITAL		= 1000		-- Player's initial balance
Sim = {}
SimMt = {__index = Sim}

function Sim:init()
	local newSim = {
		balance = INITIAL_CAPITAL,	-- player's balance
		satisfaction = 100,		-- customer satisfaction
	}
	
	setmetatable(newSim, SimMt)
	return newSim
end

function Sim:getBalance()
	return self.balance
end

function Sim:getSatisfaction()
	return self.satisfaction
end


function Sim:negotiate(monthlyFee, customer)
end

function Sim:calculateCost(elementType, length)

	if	elementType == "cable1" or
		elementType == "cable10" or
		elementType == "cable100"
	then
		-- cable cost is proportional to its length
		return CABLES[elementType].c * math.floor(length)
	else
		-- router cost per unit
		return ROUTERS[elementType].c
	end
end

--------------------------------------------------------------------------------
-- Class:	FlowGraph
-- Represents the flow network graph
FlowGraph = {}
FlowGraphMt = {__index = FlowGraph}

function FlowGraph:new(sourceNode)

	local graph = {
		source = {vertex = sourceNode, outgoing = {}},
		sink = nil,
		nodes = {}
	}
	setmetatable(graph, FlowGraphMt)
	return graph
end

function FlowGraph:addNode(gameElement)
	table.insert(self.nodes, {vertex = gameELement, outgoing = {}})
	return table.getn(self.nodes)
end

function FlowGraph:getNode(gameElement)
	for key, node in self.nodes do
		if gameElement == node.vertex then
			return node
		end
	end
	return nil
end

function FlowGraph:getEdges(node)
	return node.edges
end

function FlowGraph:addOutgoingEdge(outElement, inElement, connection)

	-- see if out node already exist in flow graph
	local outN = self:getNode(outElement)
	local inN = self:getNode(inElement)
	
	if outN == nil then
		outN = self.nodes[self:addNode(outElement)]
	end
		
	if inN == nil then
		inN = self.nodes[self:addNode(inElement)]
	end
	
	-- now add outgoing edge
	table.insert(inN.outgoing, {
		destination = outN,
		capacity = connection:getBandwidth(),
		flow = 0
	})
end

function FlowGraph:addEdge2Sink(gameElement)
	local node = self:getNode(gameElement)
	if node ~= nil then
		table.insert(node.outgoing, {
			destination = sink,
			capacity = INFINITY,
			flow = 0,
		})
	end
end

--------------------------------------------------------------------------------
-- Function:	FlowGraph:BuildResidualGrpah()
-- Builds residual graph corresponding to current flow. For information on
-- residual graph, please see Wikipedia article on the Ford-Fulkerson algorithm
function FlowGraph:BuildResidualGraph()

	for key, x in self.nodes do
		-- remove previous residual edges of all nodes
		x.residual = {}
	end
	
	-- construct residual graph
	for a, node in self.nodes do
		node.residual = {}
		for b, edge in self:getEdges(node) do
			local forward = edge.capacity - edge.flow
			local backward = edge.flow
			
			-- add forward res. edge from current node to destination
			if forward > 0 then
				table.insert(node.residual, {
					destination = edge.destination,
					label = forward,
					t = "forward"		-- type of res. edge
				})
			end
				
			-- add backward edge from destination to current node
			if backward > 0 then
				table.insert(edge.destination.residual, {
					destination = edge,
					label = backward,
					t = "backward"		-- type of res. edge
				})
			end
		end --for edges
	end --for nodes
			
end

--------------------------------------------------------------------------------
-- Function FlowGraph:FindPath()
-- Inputs:	currentP: current path
--------------------------------------------------------------------------------
function FlowGraph:FindPath(b, source, destination, currentP)
	-- do BFS
	if s.discovered then
		return nil
	end
	
	--[[
	for key, resEdge in node.residual do
		if resEdge.labal >= b then
			local subPath = 
			local p = self:FindPath(b, resEdge.destination, destination, 
	end
	--]]
	
end

--------------------------------------------------------------------------------
-- Function:	FlowGraph:FindAugmentingPath()
-- Inputs:	b: minimum bottleneck to accept in augmenting path
-- Returns:	Augmenting path, or nil for no path
-- Algorithm tries to find source-sink path with minimum bottle-neck not
-- exceeding b.
--------------------------------------------------------------------------------
function FlowGraph:FindAugmentingPath(b)
	for x, node in self:getNodes() do
		node.discovered = false
	end
	
	-- do BFS

		if not (node.discovered) then
			
			-- add all descendants nodes to queue
			for key, resEdge in node.residual do
				local res
				if node.residual.label >= b then
					res = self:FindAugmentingPath(
					flowGraph:addOutgoingEdge(node, conn.element, conn.cable)
				table.insert(queue, conn.element)
			end --for
		end --if
	end --while
end

--------------------------------------------------------------------------------
-- Function:	FlowGraph:Ford_Fulkerson 
-- implementation of Ford-Fulkerson algorithm for determining the minimum cut,
-- max flow
function FlowGraph:Ford_Fulkerson()

end
	
--------------------------------------------------------------------------------
-- Function:	Sim:constructFlowGraph()
-- Inputs:	customer: a game logic entity
-- Return:	flowGraph: instance of FlowGraph
function Sim:constructFlowGraph(customer)

	local flowGraph = FlowGraph:new(customer)
	local queue = {}
	
	for key, cus in customers do
		cus.discovered = false
	end
	
	for key, router in routers do
		router.discovered = false
	end
	
	-- add source node to queue
	table.insert(queue, customer)
	
	-- do BFS
	while queue ~= {} do
		-- pop 1st node from queue
		local node = table.remove(queue)
		
		if not (node.discovered) then
			
			-- add all descendants nodes to queue
			for key, conn in node.connections do
				flowGraph:addOutgoingEdge(node, conn.element, conn.cable)
				table.insert(queue, conn.element)
			end --for
		end --if
	end --while
	
	-- link customer's peer to sink
	for key, peer in customer.peers do
		flowGraph:addEdge2Sink(peer)
	end
	
	return flowGraph
end
