-- ----------------------------------------------------------------------------
kClosePoi = "close poi"
-- ----------------------------------------------------------------------------
function dijkstra(g, s)

	assert(g)
	
	if (g.cache == nil) then
		g.cache = {}
	end
	
	-- cache!
	if (g.cache[s]) then
		return g.cache[s]
	end

	local infinity = 100000
	local dist = {}
	local previous = {}

	-- initializiations
	assert(g.nodes)	
	for i, node in ipairs(g.nodes) do
		-- unknown distance function from source to v
		dist[node] = infinity			
		-- previous node in optimal path from source	
		previous[node] = nil	
		-- check
		if (g.neighbors[node] == nil) then
			print("WARNING: missing neighbor entry for layout: " .. node:name())
		end
	end
	-- distance from source to source
	dist[s] = 0
	
	local q = {}
	for i, node in ipairs(g.nodes) do
		table.insert(q, node)
	end
	
	-- all nodes in the graph are unoptimized - thus are in q
	while (#q > 0) do
		-- u is vertex in Q with smallest dist[]
		local u = nil
		local uMin = math.huge
		local uPosition = nil
		for i, node in ipairs(q) do
			assert(node)
			if (dist[node] < uMin) then
				u = node
				uMin = dist[node]	
				uPosition = i		
			end					
		end
		assert(u)
		
		if (dist[u] == infinity) then
			-- all remaining nodes are inaccessible
			break
		end
		
		table.remove(q, uPosition)

		assert(g.neighbors)
		assert(g.neighbors[u])
		for i, v in ipairs(g.neighbors[u]) do
			alt = dist[u] + 1
			if (alt < dist[v]) then
				dist[v] = alt
				previous[v] = u
			end		
		end
	end
	
	-- store in cache
	g.cache[s] = previous
	
	-- return
	return previous

end
-- ----------------------------------------------------------------------------
function dijkstraChecks(graph, sourceLayout, targetLayout)
	assert(sourceLayout)
	assert(targetLayout)
	
	local sourceInGraph = false
	for i, node in pairs(graph.nodes) do
		if (node == sourceLayout) then
			sourceInGraph = true
			break
		end
	end
	
	local targetInGraph = false
	for i, node in pairs(graph.nodes) do
		if (node == targetLayout) then
			targetInGraph = true
			break
		end
	end
		
	assert(sourceInGraph, "WARNING: missing entry in nodes: " .. sourceLayout:name())
	assert(targetInGraph, "WARNING: missing entry in nodes: " .. targetLayout:name())
	assert(graph.neighbors[sourceLayout], "WARNING: missing entry in neighbors: " .. sourceLayout:name())
	assert(graph.neighbors[targetLayout], "WARNING: missing entry in neighbors: " .. targetLayout:name())	
	
	return true
end
-- ----------------------------------------------------------------------------
-- WARNING:
-- the first element of the result is NOT sourceLayout!
-- the last element of the result is targetLayout
function dijkstraConstructLayoutPath(sourceLayout, targetLayout)
	assert(sourceLayout)
	assert(targetLayout)
	assert(dijkstraChecks(graph, sourceLayout, targetLayout))
		
	-- if we are in the target layout, we return
	-- a path of size 0
	if (sourceLayout == targetLayout) then
		return {}
	end
	
	local previous = dijkstra(graph, sourceLayout)
	
	local s = {}
	local u = targetLayout
	while (previous[u]) do
		table.insert(s, 1, u)
		u = previous[u]	
	end

	return s
end
-- ----------------------------------------------------------------------------
function dijkstraConstructObjectPath(sourceLayout, targetLayout)
	assert(sourceLayout)
	assert(targetLayout)
	assert(dijkstraChecks(graph, sourceLayout, targetLayout))
	local layoutPath = dijkstraConstructLayoutPath(sourceLayout, targetLayout)
	
	-- layoutPath does not contain sourceLayout as its first element
	-- to simplify our search, insert it
	table.insert(layoutPath, 1, sourceLayout)	
	
	local objectPath = {}
	for i = 1, #layoutPath-1 do
		-- find the object that needs to be clicked to get from
		-- layoutPath[i] to layoutPath[i+1]
		assert(layoutPath[i])
		assert(layoutPath[i+1])
		local sourceLayout = layoutPath[i]
		local targetLayout = layoutPath[i+1]
		local found = false
		
		if (not found) then
			-- check if we have to click a poi
			-- check on active pois
			for object, props in pairs(sourceLayout.mPOIs) do		
				if (props.target == targetLayout) then		
					if (object:isActive()) then
						table.insert(objectPath, object)
						found = true
						break
					end
				end
			end
		end
		
		if (not found) then
			-- check if we have to click a poi
			-- accept any
			for object, props in pairs(sourceLayout.mPOIs) do		
				if (props.target == targetLayout) then		
					table.insert(objectPath, object)
					found = true
					break
				end
			end		
		end
		
		if (not found) then
			-- check if we have to click an exit
			-- check on active exits
			for object, props in pairs(sourceLayout.mExits) do
				if (props.target == targetLayout) then
					if (object:isActive()) then
						table.insert(objectPath, object)
						found = true
						break
					end
				end			
			end			
		end
		
		if (not found) then
			-- check if we have to click an exit
			-- accept any
			for object, props in pairs(sourceLayout.mExits) do
				if (props.target == targetLayout) then
					table.insert(objectPath, object)
					found = true
					break
				end			
			end			
		end		
		
		if (not found) then
			-- check if we're in a poi, then we have to close it
			if (sourceLayout:isPOI()) then
				table.insert(objectPath, kClosePoi)
				found = true
			end
		end
		
		if (not found) then
			-- there is no way to get there!
			return nil
		end
		
	end
	
	return objectPath

end
-- ----------------------------------------------------------------------------
function dijkstraConstructPathToLayout(sourceLayout, targetLayout)

	return dijkstraConstructObjectPath(sourceLayout, targetLayout)

end
-- ----------------------------------------------------------------------------
function dijkstraConstructActivePathToLayout(sourceLayout, targetLayout)

	local objectPath = dijkstraConstructObjectPath(sourceLayout, targetLayout)
	
	for i = 1, #objectPath do
		local object = objectPath[i]
		if (type(object) ~= "string") then	
			assert(object)
			assert(object.type)
			assert(object.type == kObject, "ERROR: it's a: " .. object.type)
			if (not object:isActive()) then
				return nil
			end
		end	
	end	
	
	return objectPath	

end

-- ----------------------------------------------------------------------------
function dijkstraConstructPathToObject(sourceLayout, object)

	local targetLayout = object:getLayout()
	local objectPath = dijkstraConstructObjectPath(sourceLayout, targetLayout)
	return objectPath
	
end
-- ----------------------------------------------------------------------------
function dijkstraConstructActivePathToObject(sourceLayout, object)

	local targetLayout = object:getLayout()
	local objectPath = dijkstraConstructObjectPath(sourceLayout, targetLayout)

	for i = 1, #objectPath do
		local object = objectPath[i]
		if (type(object) ~= "string") then		
			assert(object)
			assert(object.type)
			assert(object.type == kObject, "ERROR: it's a: " .. object.type)
			if (not object:isActive()) then
				return nil
			end
		end	
	end
	
	return objectPath

end