Module:Sandbox/KickahaOta/QueryDistances
Jump to navigation
Jump to search
You might want to create a documentation page for this module.
Editors can experiment in this module's sandbox and testcases pages.
Please add categories to the /doc subpage. Subpages of this module.
Editors can experiment in this module's sandbox and testcases 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")
local paramtest = args or error("No args supplied")
paramtest = args.idfield or error("no idfield supplied")
paramtest = args.connectionidsfield or error("no connectionidsfield supplied")
paramtest = args.distancefield or error("no distancefield supplied")
paramtest = args.originrowid or error("no originidrow supplied")
args.maxdistance = args.maxdistance or 99
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
if test then mw.log(string.format("Warning: idfield not unique: idfield='%s', rowid='%s', previous rowid='%s'", args.idfield, rowid, calc_results_id_map[rowid])) end
else
calc_results_id_map[rowid] = i
end
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 = calc_results[idx][args.connectionidsfield]
if type(outgoing_ids) == "string" then
paramtest = args.connectionidsdelimiter or error("no connectionidsdelimiter supplied")
outgoing_ids = m_util.string.split(outgoing_ids, args.connectionidsdelimiter)
end
if type(outgoing_ids) ~= "table" then
error(string.format("Unexpected outgoing id data type '%s' in field '%s' for id '%s'", type(outgoing_ids), args.connectionidsfield, calc_results[idx][args.idfield]))
end
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.
local isbetter = false
if (connected_row_current_distance == nil) then
isbetter = true
if test then mw.log(string.format("Found first route to %s with distance %d", outgoing_id, distance_to_this + 1)) end
elseif (connected_row_current_distance > distance_to_this + 1) then
isbetter = true
if test then mw.log(string.format("Found better route to %s, reducing distance from %d to %d", outgoing_id, connected_row_current_distance, distance_to_this + 1)) end
else
if test then mw.log(string.format("Found route to %s with distance %d, but prior route has better distance %d", outgoing_id, distance_to_this + 1, connected_row_current_distance)) end
end
if isbetter then
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
end
end
end
end
return m_tablecalc.removeunneededrows(calc_results,args)
end
function m_tablecalc.removeunneededrows(calc_results,args)
calc_results = calc_results or error("No results table supplied")
local paramtest = args or error("No args supplied")
paramtest = args.distancefield or error("no distancefield supplied")
paramtest = args.idfield or error("no idfield specified")
test = args.test or false
local stripped_calc_results = {}
for i, row in ipairs(calc_results) do
if args.removenildistances and row[args.distancefield] == nil then
-- if test then mw.log(string.format("Removing row %s with nil distance", row[args.idfield] or tostring(i))) end
elseif (args.removeorigin or args.removezero) and row[args.distancefield] == 0 then
-- if test then mw.log(string.format("Removing row %s with zero distance", row[args.idfield] or tostring(i))) end
else
stripped_calc_results[#stripped_calc_results+1] = row
-- if test then mw.log(string.format("Keeping row %s with distance %d", row[args.idfield] or tostring(i), row[args.distancefield])) end
end
end
return stripped_calc_results
end
function m_tablecalc.testascendancy(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
function m_tablecalc.testwitch(test)
local results = m_cargo.query(
{'passive_skills'},
{'passive_skills.name', 'passive_skills.id', 'passive_skills.connections', 'passive_skills.ascendancy_class', 'CONCAT("")=distance'},
{where='id NOT LIKE "%jewel_slot%" AND connections HOLDS LIKE "%" AND (ascendancy_class="" OR ascendancy_class IS NULL)', order_by='passive_skills.id'}
)
local calc_args = {
idfield = "passive_skills.id",
connectionidsfield="passive_skills.connections",
connectionidsdelimiter=",",
originrowid="witch595",
distancefield="distance",
test = test or false,
maxdistance=10,
removenildistances=true,
removeorigin=true,
}
local calc_results = m_tablecalc.computedistance(results, calc_args)
return calc_results
end
return m_tablecalc