-- Kinetic tournaments in lua
-- Bo Gotthardt, bogp@diku.dk

--[[
The tournament is a binary tree with the leaf nodes representing the points, and the internal nodes representing the outcome of comparisons between these points. This means that a node will always have 0 or 2 children.
Points are represented by their name (name), starting position (y) and velocity (v). This can be visualized over time as the line y(t) = v*t+y.
A node has a point (value), left and right subtrees (left and right), parent node (parent) and a search key (key)
An event is always the time at which it happens (t), and then either the node whose certificate fails (fail), or the name of a point that has been updated (update) and its new velocity( v).
]]

KineticTournament = {
	q = {}, -- Event queue
	t = 0, -- Current time
	tournament = nil,-- Tournament structure
	reportMax = nil-- Function to call when reporting a new maximum
}
-- Lua OO with metatables
KineticTournamentMeta = {}
KineticTournamentMeta.__index = KineticTournament

-- Build a kinetic tournament
-- Points is the set of points to build it over, report is an optional function to call when the maximum changes
function KineticTournament:new(points, report)
	-- Sort the points so we can use this ordering later
	table.sort(points, function(a,b) return a.name < b.name end)
	-- Lua OO again
	local obj = {}
	setmetatable(obj,KineticTournamentMeta) 
	obj.tournament = obj:buildTree(points)
	if report then
		obj.reportMax = report
		obj.reportMax(obj.tournament.value)
	end
	return obj
end

-- Recursively builds the binary tree
function KineticTournament:buildTree(points)
		local node = {}
		-- #points is the number of points (length of the list)
		if #points > 1 then
			-- Internal node
			local a, b = self:listSplit(points)
			node.left  = self:buildTree(a)
			node.left.parent = node
			node.right = self:buildTree(b)
			node.right.parent = node
			-- Set the value of this node to be the maximum of it's two children
			self:updateNodeValue(node)
			-- Set the search key  to the first (= lowest since it's sorted) element in the right set
			node.key = b[1].name
			return node
		elseif #points == 1 then
			-- Leaf node
			-- The first element is 1, not 0
			node.value = points[1]
			return node
		else
			-- Empty node
			return nil
		end
	end

-- Spilt a list into two smaller lists
function KineticTournament:listSplit(list)
	local a = {}
	local b = {}
	for k,v in pairs(list) do 
		-- The first half goes in a, the second half in b
		if k <= math.floor(#list/2) then
			table.insert(a, v)
		else
			table.insert(b, v)
		end
	end
	
	return a, b
end


-- Process events in the event queue
function KineticTournament:run()
	-- As long as there are events to process
	print("t" .. self.t .. ": Starting simulation")
	while #self.q > 0 do
		-- Advance time to the earliest event (or stay at the current time if more events here)
		local event = self:eventQueuePop()
		if event.t < self.t then
			error("Events out of order")
		end
		self.t = event.t
		
		if event.fail then
			-- Certificate failure event
			-- Since the certificate failed, check which child node is the new maximum
			local changed = self:updateNodeValue(event.fail)
			
			-- If the value of this node changed,  the value of its parent node might change as well
			-- This happens recursively if needed, since if the parent node changes it will add a new event to the queue with t = the current t, which will get processed here again
			if changed and event.fail.parent then
				self:updateNodeValue(event.fail.parent)
			end
		elseif event.update then
			-- Point velocity update event
			local node = self:findNode(event.update)
			
			-- We don't store all the previous velocities, instead we pretend the new velocity has been there from the start
			-- This means we need to recompute the starting y, so that the current y remains unaffected
			local currenty = node.value.v*self.t+node.value.y
			local newstarty = currenty-(event.v*self.t)
			
			node.value.y = newstarty
			node.value.v = event.v
			
			-- The value of this node changed,  the value of its parent node might change as well
			if node.parent then
				self:updateNodeValue(node.parent)
			end
		end
	end
	print("t" .. self.t .. ": Simulation done")
end

-- Updates the value of an internal node
function KineticTournament:updateNodeValue(node)
	-- Internal nodes represent a comparison between value of it's two children points, resulting in the maxumum value
	-- The comparison between two points might fail later, computing when is the same as computing the intersection between the two lines the points can be visualized as
	-- Since we only use first degree polynomials this "root finding" is the same as line intersection
	local x, y = intersect(node.left.value.v, node.left.value.y, node.right.value.v, node.right.value.y)
	local lefty  = node.left.value.v*self.t+node.left.value.y
	local righty = node.right.value.v*self.t+node.right.value.y
	local oldvalue = node.value
	local symbol
	
	if lefty > righty then
		node.value = node.left.value
		symbol = " > "
	elseif lefty < righty then
		node.value = node.right.value
		symbol = " < "
	else
		--They are equally large right now, so pick the one that will be larger later
		if node.left.value.v > node.right.value.v then
			node.value = node.left.value
			symbol = " > "
		elseif node.left.value.v < node.right.value.v then
			node.value = node.right.value
			symbol = " < "
		else
			node.value = node.right.value
			symbol = " == "
		end
	end
	
	-- If the comparison will fail at a later time, we need to remember it in the event queue
	if x and x > self.t then
		self:eventQueueAdd({t = x, fail = node})
		print("t" .. self.t .. ": Certificate: " .. node.left.value.name .. symbol .. node.right.value.name .. ". Fails at t = " .. x)
	else
		-- The certificate will never fail, so don't bother recording it
		print("t" .. self.t .. ": Certificate: " .. node.left.value.name .. symbol .. node.right.value.name .. ". Fails at t = never")
	end
	
	-- If the value changed and this is the root node, we have a new maximum
	if oldvalue ~= node.value and not node.parent and self.reportMax then
		self.reportMax(node.value)
	end
	
	return oldvalue ~= node.value
end

-- Find the leaf node with a specific name
function KineticTournament:findNode(name)
	function findNode2(node, name)
		if not node.left and not node.right then
			-- We've found the correct leaf node
			return node
		elseif node.key > name then
			return findNode2(node.left, name)
		else
			return findNode2(node.right,name)
		end
	end

	return findNode2(self.tournament, name)
end

-- Add or pop an event to/from the event queue
function KineticTournament:eventQueueAdd(new)
	-- Ought to be a real priority (on t) queue structure, and not just a list, but this will work too
	table.insert(self.q, new)
	table.sort(self.q, function(a,b) return a.t < b.t end)
end
function KineticTournament:eventQueuePop()
	return table.remove(self.q, 1)
end

-- Find the intersection between two lines given as y = a1x+b1 and y = a2x+b2
function intersect(a1, b1, a2, b2)
	if a1 == a2 then
		return nil
	else
		local x = (b2-b1)/(a1-a2)
		local y = a1*x+b1
		return x, y
	end
end

-- Some test data
function test()
	print("Testing KineticTournamentClass")
	print("\nTest 1:")
	points = {{name="A", y=1, v=2},{name="B", y=2, v=1},{name="C", y=3, v=1},{name="D", y=4, v=1}}
	tour = KineticTournament:new(points, function(a) print("New maximum: "..a.name) end)
	tour:eventQueueAdd({t = 5, update = "B", v = 3})
	tour:run()

	print("\nTest 2:")
	points2 = {{name="Aa", y=1, v=5},{name="Bb", y=2, v=1},{name="Cc", y=6, v=1},{name="Dd", y=1, v=1}}
	tour2 = KineticTournament:new(points2, function(a) print("New maximum: "..a.name) end)
	tour2:run()

	print("\nTest 3:")
	points3 = {{name="A", y=1, v=2},{name="B", y=2, v=1},{name="C", y=3, v=1},{name="D", y=4, v=1}}
	tour3 = KineticTournament:new(points3, function(a) print("New maximum: "..a.name) end)
	tour3:eventQueueAdd({t = 6, update = "B", v = 3})
	tour3:eventQueueAdd({t = 12, update = "C", v = 4})
	tour3:eventQueueAdd({t = 24, update = "D", v = 4.02})
	tour3:eventQueueAdd({t = 2000, update = "A", v = 4.04})
	tour3:run()
end

test()