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

SimNetwork_SIMULATION = true

if not SimNetwork_DATA		then dofile("data.lua")	end
if not SimNetwork_BALANCE	then dofile("balance.lua")	end

INITIAL_CAPITAL		= 1000		-- Player's initial balance
START_DELTA		= 128		-- Used by Ford-Fulkerson for faster
					-- augmenting path finding
Sim = {}
SimMt = {__index = Sim}

function Sim:init()
	local newSim = {
		balance = INITIAL_CAPITAL,	-- player's balance
		satisfaction = 100,		-- customer satisfaction
		
		customers = nil,		-- pointers to gObjects of
		routers = nil,			-- game elements. Actual elements
		cables = nil,			-- are stored in Scene.map, these
						-- are just pointers to them
	}
	
	setmetatable(newSim, SimMt)
	
	return newSim
end

function Sim:setLogicData(pCustomers, pRouters, pCables)
	self.customers = pCustomers
	self.routers = pRouters
	self.cables = pCables
end

function Sim:getBalance()
	return self.balance
end

function Sim:getSatisfaction()
	return self.satisfaction
end

function Sim:negotiate(monthlyFee, customer)
end

function Sim:getUnitCost(unitType)
	if CABLES[unitType] ~= nil then
		return CABLES[unitType].c
	elseif ROUTERS[unitType] ~= nil then
		return ROUTERS[unitType].c
	else
		return nil
	end
	
end

function Sim:canPurchase(cost)
	if self.balance >= cost then
		return true
	else
		return false
	end
end

function Sim:purchase(cost)
	if self.balance < cost then
		return false
	else
		self.balance = self.balance - cost
		-- update balance bar
		update_balance(self.balance)
		if gameScene.state ~= SCENE_STATE.demolish then
			--play sound
			E.play_sound(moneySound)
		end
		return true
	end
end

function Sim:begin()
	update_balance(self.balance)
	update_overallCustSatisfaction(self.satisfaction)
end

--------------------------------------------------------------------------------
-- Function:	Sim:getCableEnds()
-- Inputs:	theCable: O object of type cable
-- Returns:	2 O objects: the two ends of the given cable, or nil if not found
function Sim:getCableEnds(theCable)
	
	-- search for cable reference in customers
	for x, aCustomer in self.customers do
		local link = aCustomer.o:getLink()
		if link ~= nil then
			if link.cable == theCable then
				return aCustomer.o, link.destination
			end
		end
	end
	
	for x, router in self.routers do
		for y, link in router.o:getLinks() do
			if link.cable == theCable then
				return router.o, link.destination
			end
		end
	end
	
	return nil
end

--------------------------------------------------------------------------------
-- Function:	Sim:removeElement()
-- Inputs:	o: O object
-- Returns:	none
function Sim:removeElement(o)
	local index = nil
	if o:getElementType() == "cable" then
		index = searchTable(self.cables, "o", o)
		
		-- determine the two ends of the cable
		local element1, element2 = self:getCableEnds(o)
		
		-- remove the cable from their list of connections
		element1:removeCable(o)
		element2:removeCable(o)
		table.remove(self.cables, index)
		
	elseif o:getElementType() == "router" then
		index = searchTable(self.routers, "o", o)
		table.remove(self.routers, index)
	elseif o:getElementType() == "customer" then
		index = searchTable(self.customers, "o", o)
		table.remove(self.customers, index)
	end
end
--------------------------------------------------------------------------------
-- Class:	FlowGraph
-- Represents the flow network graph
FlowGraph = {}
FlowGraphMt = {__index = FlowGraph}

--------------------------------------------------------------------------------
-- Function FlowGraph:new()
-- Inputs:	sourceNode:	game entity of customer being simulated
-- Returns:	FlowGraph instance
function FlowGraph:new(sourceNode)

	local graph = {
		source = {vertex = sourceNode, outgoing = {}},
		sink = {vertex = nil, outgoing = {}, name = "Hey, I'm the sink!"},
		nodes = {}
	}
	setmetatable(graph, FlowGraphMt)
	return graph
end

function FlowGraph:getNodes()
	return self.nodes
end

function FlowGraph:getSource()
	return self.source
end

function FlowGraph:getSink()
	return self.sink
end

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

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

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

function FlowGraph:addOutgoingEdge(outLogicElement, inLogicElement, theCable)

	-- see if out node already exist in flow graph
	local outN = self:getNode(outLogicElement)
	local inN = self:getNode(inLogicElement)
	
	if outN == nil then
		outN = self.nodes[self:addNode(outLogicElement)]
	end	
		
	if inN == nil then
		inN = self.nodes[self:addNode(inLogicElement)]
	end
	
	-- now add outgoing edge
	table.insert(outN.outgoing, {
		destination = inN,
		capacity = theCable:getBandwidth(),
		flow = 0,
		cable = theCable	-- pointer to the cable that caused
					-- this flow graph edge to be added
		
	})
end

function FlowGraph:addEdge2Sink(logicElement, peerShare)
	local node = self:getNode(logicElement)
	if node == nil then
		node = self.nodes[self:addNode(logicElement)]
	end
	
	table.insert(node.outgoing, {
		destination = self.sink,
		capacity = peerShare,
		flow = 0,
	})
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()

	-- remove previous residual edges of all nodes
	print("** FlowGraph:buildResidualGraph()...")
	self.source.residual = {}
	self.sink.residual = {}
	
	for x, node in self:getNodes() do
		--print("\tReseting residual edges of node:", node.vertex:getElementType(), "out edges:", table.getn(node.outgoing))
		node.residual = {}
	end
	
	-- loop through nodes
	for i=1, 2 do
		local vertexSet
		if i == 1 then
			-- first iteration builds residual edges for source
			vertexSet = {self.source}
		else
			-- second iteration builds residual edges for other nodes
			vertexSet = self:getNodes()
		end
			
		for a, node in vertexSet do
			print("\tLooping over outgoing edges of node:", node.vertex:getName())
			-- loop through edges
			for b, edge in self:getEdges(node) do
				print("\t\tEdge of capacity:", edge.capacity)
				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
						flowEdge = edge		-- refrence to the flow edge that
									-- caused this residual edge
					})
				end
					
				-- add backward edge from destination to current node
				if backward > 0 then
					table.insert(edge.destination.residual, {
						destination = node,
						label = backward,
						t = "backward",		-- type of res. edge
						flowEdge = edge	
					})
				end
			end --for edges
		end --for vertexSet
	end --for i
			
end

--------------------------------------------------------------------------------
-- Function FlowGraph:findPath()
-- Inputs:	currentP: current path
--------------------------------------------------------------------------------
function FlowGraph:findPath(minB, curB, node, destination, currentP)
		
	if node.vertex ~= nil then
		print("** findPath, from:", node.vertex:getName(), "minB:", minB, ",curB:", curB)
	else
		print("** findPath, from: SINK")
	end

	if node == destination then
		return true, currentP, curB
	elseif node.vertex == nil then
		-- reached sink, but we're not simulating the path to sink
		print("** WARNING: findPath: reached sink but did not succeed!")
		return false, nil, nil
	elseif node.discovered then
		print("\tDiscovered node. Backtracking.")
		return false, nil, nil
	end
	
	node.discovered = true
	
	-- do DFS
	for x, resEdge in node.residual do
		-- make sure we select edges with label greater of equal to
		-- bottle-neck. This ensures that the Ford-Fulkerson algorithm
		-- advances at a much faster rate
		if resEdge.label >= minB then
			-- update minimum bottle neck
			if curB > resEdge.label then
				curB = resEdge.label
			end
			
			-- copy sub path: because we're using recursion, we need
			-- seperate copies
			local subPath = copyTable(currentP)
			
			-- insert a pointer to the residual edge we have followed
			table.insert(subPath, resEdge)
			
			if resEdge.destination ~= self.sink then
				if resEdge.destination.vertex == nil then
					print("** Opps, we're following an edge that does not have a name, it's not even the sink!")
					print("** I'm currently at:", node.vertex:getName(), ",Hostile residual edge is indexed at: ", x)
					print("Here are the fields in this node:")
					for key, value in resEdge.destination do
						print("\tkey:",key,",val:", value)
					end
					print("I'm giving up :(")
				end
				print("\tFollowing residual edge to: ", resEdge.destination.vertex:getName())
			else
				print("\tFollowing residual edge to: SINK")
			end
			
			table.insert(subPath, resEdge.destination)
			--[[
			if resEdge.destination == nil then
				-- sink
				table.insert(subPath, self.sink)
			else
				table.insert(subPath, resEdge.destination)
			end
			--]]
			
			local res, path, bottleNeck = self:findPath(minB, curB, resEdge.destination, destination, subPath)
			
			if res == true then
				-- we have reached a path, return it
				print("Found path with bottle neck:", curB)
				return true, path, bottleNeck
			end
			print("\t** Again at: ", node.vertex:getName())
			print("\tNo path, proceeding to try next residual edge.")
		end
		
	end
	
	print("\tCompleted all residual edge at: ", node.vertex:getName())
	
	return false, nil
end

--------------------------------------------------------------------------------
-- Function:	FlowGraph:FindAugmentingPath()
-- Inputs:	minBottleNeck: 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(minBottleNeck, node, destination)
	
	print("findAugmentingPath, minB:",minBottleNeck)
	self.source.discovered = false
	for x, node in self:getNodes() do
		node.discovered = false
	end
	
	local res, path, bottleNeck = self:findPath(minBottleNeck, INFINITY, node, destination, {})
	return res, path, bottleNeck
end

--------------------------------------------------------------------------------
-- Function:	FlowGraph:augment()
-- Inputs:	path: returned from findAugmentingPath()
-- Returns:	none
-- Augments given augmenting path to increase the flow
--------------------------------------------------------------------------------
function FlowGraph:augment(path, bottleNeck)
	print("**** Augmenting path.")
	
	-- start from source
	local currentNode = self.source
	
	while table.getn(path) > 0 do
		-- pop reference residual edge
		local resEdge = table.remove(path, 1)
		local flowEdge = resEdge.flowEdge
		
		if resEdge.t == "forward" then
			-- forward edge: increase flow by bottle neck
			flowEdge.flow = flowEdge.flow + bottleNeck
		else
			-- backward edge: decrese flow
			flowEdge.flow = flowEdge.flow - bottleNeck
		end
	
		-- move to next node in path
		currentNode = table.remove(path, 1)
	end
end
--------------------------------------------------------------------------------
-- Function:	FlowGraph:Ford_Fulkerson 
-- implementation of Ford-Fulkerson algorithm for determining the minimum cut,
-- max flow
function FlowGraph:Ford_Fulkerson()
	
	self:buildResidualGraph()
	local delta = START_DELTA
	local res, path, bottleNeck = self:findAugmentingPath(delta, self.source, self.sink)
	
	-- while there's still an augmenting path
	while delta >= 1 do
	
		self:buildResidualGraph()
		local res, path, bottleNeck = self:findAugmentingPath(delta, self.source, self.sink)
		
		while res do
			self:augment(path, bottleNeck)
			self:buildResidualGraph()
			res, path, bottleNeck = self:findAugmentingPath(delta, self.source, self.sink)
		end
		
		delta = delta / 2
	end
		
end
	
--------------------------------------------------------------------------------
-- Function:	Sim:constructFlowGraph()
-- Inputs:	customer: a game logic entity
-- Return:	flowGraph: instance of FlowGraph representing flow network
-- from customer to his peer(s)
function Sim:constructFlowGraph(customer)

	local flowGraph = FlowGraph:new(customer)
	local queue = {}
	
	-- mark all customers and routers as not discovered
	for key, cus in self.customers do
		cus.o.discovered = false
	end
	
	for key, router in self.routers do
		router.o.discovered = false
	end
	
	-- add source node to queue
	table.insert(queue, customer)
	
	-- do BFS
	print("Starting BFS")
	while table.getn(queue) > 0 do
		-- pop 1st node from queue
		print("Poped 1 node")
		local node = table.remove(queue, 1)
		print("Node type:", node:getElementType())
		
		if not (node.discovered) then
			print("Number of links to node:", table.getn(node:getLinks()))
			
			-- add all descendants nodes to queue
			for x, link in node:getLinks() do
				print("  * Link to:", link.destination:getElementType())
				
				-- for each cable, add a two directed edges
				flowGraph:addOutgoingEdge(node, link.destination, link.cable)
				--flowGraph:addOutgoingEdge(link.destination, node, link.cable)
				table.insert(queue, link.destination)
			end --for
			node.discovered = true
		end --if
	end --while
	
	-- link customer's peer to sink
	for key, peer in customer:getPeers() do
		-- make sure we add peers to the flow graph
		if not flowGraph:getNode(peer) then
			flowGraph:addNode(peer)
		end
		-- connect peers to sink
		flowGraph:addEdge2Sink(peer, math.floor(customer:getCurrentBandwidth() / customer:getPeerCount()))
	end
	
	return flowGraph
end
