Module:Sandbox/KickahaOta/QueryDistances

Module documentation[create] [purge]

You might want to create a documentation page for this module.
Editors can experiment in this module's sandbox (create | mirror) and testcases (edit | run) pages.
Please add categories to the /doc subpage. Subpages of this module.

local getArgs = require('Module:Arguments').getArgs
local m_util = require('Module:Util')
local m_cargo = require('Module:Cargo')

local m_tablecalc = {}

function m_tablecalc.computedistance(query_results, args)
	-- Takes 2 arguments:
	--   query_results - table returned from m_cargo.query
	--   args
	--     idfield - string; the name of the field containing a row's id for connection purposes (for example, "passive_skills.id")
	--     connectionidsfield - string: the name of the field containing the ids of the rows that a given row connects to
	--        (for example, "passive_skills.connections")
	--     connectionidsdelimiter - string; the delimeter separating ids in the connectiond id field (for example, ",")
	--     originrowid - string; the id of a row that should be used as the starting point of the calculation. (For example,
	--       "AscendancyBerserkerStart" to start at the starting node in the Berserker's Ascendancy tree.)
	--     distancefield - string; the name of the field that should hold each row's calculated distance from the starting
	--       point. (This will be an integer. The row identified by originrowid will have a distance value of 0; the rows
	--       connected to that row will have a distance value of 1; the rows connected to those rows will have a distance value
	--       of 2; and so on.)
	--     maxdistance - integer: The longest route we should calculate. For instance, if maxdistance = 10, then we will only
	--       calculate distances to rows that can be reached from the origin row through 10 or fewer connections. Any nodes 
	--       that can't be reached within this limit will wind up with the distance field set to nil.
	--     test - boolean; if true, does logging
	-- Returns: A table that is a copy of the table in query_results, except that each row will have the field identified by
	--   distancefield set to the calculated distance. The field will be created if it does not already exist in each row.

	query_results = query_results or error("No results table supplied")
	args = args or error("No args supplied")
	args.maxdistance = args.maxdistance or 999
	test = args.test or false

	-- Start by creating three tables:
	--   calc_results: A copy of query_results, where we'll eventually insert the computed distances into each row.
	--   calc_results_id_map: A table that maps each connection ID to the index of the row in calc_results with that ID. 
	--   calculables: A queue table containing the indexes of rows in calcResults where we now know the distance for that row, but we
	--     haven't yet used that knowledge to set the distances of the other rows connected to it. At first, this should contain
	--     a single index -- the index of the row identified by originrowid.
	
	local calc_results = {}
	local calc_results_id_map = {}
	local calculables = {}
	
	for i, row in ipairs(query_results) do
		calc_results[i] = row
		local rowid = calc_results[i][args.idfield]
		if rowid == nil then
			error("No idfield")
		end
		if calc_results_id_map[rowid] ~= nil then
			error("idfield not unique")
		end
		calc_results_id_map[rowid] = i
		if rowid == args.originrowid then
			calc_results[i][args.distancefield] = 0
			table.insert(calculables, i)
		else
			calc_results[i][args.distancefield] = nil
		end
	end
	
	if #calculables == 0 then
		error("Origin row not found")
	elseif #calculables > 1 then
		error("Multiple origin rows found")
	end
	
	-- Now we start processing by grabbing the next row from the queue
	while #calculables > 0 do
		local idx = table.remove(calculables, 1)
		local id = calc_results[idx][args.idfield]
		local distance_to_this=calc_results[idx][args.distancefield]
		
		if test then mw.log(string.format("Processing node %s with distance %d", id, distance_to_this)) end
		-- Check each connected node to see if our current node is the most efficient route we've found to that other node
		local outgoing_ids = m_util.string.split(calc_results[idx][args.connectionidsfield], args.connectionidsdelimiter)
		for _,outgoing_id in ipairs(outgoing_ids) do
			local idx_connected_row = calc_results_id_map[outgoing_id]
			if idx_connected_row == nil then
				if test then mw.log(string.format("Outgoing connection %s for row %s not found, ignoring", outgoing_id, calc_results[idx][args.idfield])) end
			else
				connected_row_current_distance = calc_results[idx_connected_row][args.distancefield]
				-- Does the connected node have no distance computed yet? Then the route through the current node is the first
				--   route we've found to the connected node; so by definition it's the most efficient we've found.
				-- Does the connected node have a distance computed that's higher than our current node's distance + 1? Then
				--   we've found a more efficient route than the previous one(s) we found, and we should update it.
				-- Does the connected node have a distance computed that's lower than that? Then we already found a more
				--   efficient route to that node, and we should leave it alone.
				if (connected_row_current_distance == nil) or (connected_row_current_distance > distance_to_this + 1) then
					if test then mw.log(string.format("Found route with distance %d to %s", distance_to_this + 1, outgoing_id)) end
					calc_results[idx_connected_row][args.distancefield] = distance_to_this + 1
					-- Add the connected node to the calculables queue, so that we (re)check the nodes connected to it
					if (distance_to_this + 1) < args.maxdistance then
						table.insert(calculables, idx_connected_row)
					else
						if test then mw.log(string.format("Not checking %s because maxdistance reached", outgoing_id)) end
					end
				else
					if test then mw.log(string.format("Keeping existing route with distance %d to %s", connected_row_current_distance, outgoing_id)) end
				end
			end
		end
	end

	return calc_results	
end

function m_tablecalc.testquery(test)
	local results = m_cargo.query(
		{'passive_skills'},
		{'passive_skills.name', 'passive_skills.id', 'passive_skills.connections', 'passive_skills.ascendancy_class', 'CONCAT("")=distance'},
		{where='passive_skills.ascendancy_class="Berserker"', order_by='passive_skills.id'}
	)
	local calc_args = {
		idfield = "passive_skills.id",
		connectionidsfield="passive_skills.connections",
		connectionidsdelimiter=",",
		originrowid="AscendancyBerserkerStart",
		distancefield="distance",
		test = test or false
	}
	local calc_results = m_tablecalc.computedistance(results, calc_args)
	return calc_results
end

return m_tablecalc