Module:Sandbox/KickahaOta/QueryDistances: Difference between revisions
Jump to navigation
Jump to search
KickahaOta (talk | contribs) (In progress) |
KickahaOta (talk | contribs) (Solid progress!) |
||
Line 4: | Line 4: | ||
local m_tablecalc = {} | local m_tablecalc = {} | ||
function m_tablecalc.computedistance(query_results, args) | function m_tablecalc.computedistance(query_results, args) | ||
Line 22: | Line 19: | ||
-- connected to that row will have a distance value of 1; the rows connected to those rows will have a distance value | -- 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.) | -- 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 | -- 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. | -- 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 | -- 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: A copy of query_results, where we'll eventually insert the computed distances into each row. | ||
-- calculables: A table containing the indexes of rows in calcResults where we now know the distance for that row, but we | -- 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 | -- 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. | -- a single index -- the index of the row identified by originrowid. | ||
local calc_results = {} | local calc_results = {} | ||
local calc_results_id_map = {} | |||
local calculables = {} | local calculables = {} | ||
for i, row in ipairs(query_results) do | for i, row in ipairs(query_results) do | ||
calc_results[i] = row | calc_results[i] = row | ||
local rowid = calc_results[i][args.idfield] | |||
if rowid == nil then | |||
error("No idfield") | error("No idfield") | ||
end | end | ||
if | 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 | calc_results[i][args.distancefield] = 0 | ||
table.insert(calculables, i) | table.insert(calculables, i) | ||
Line 56: | Line 66: | ||
end | end | ||
-- Now we start processing by grabbing the next row from the queue | |||
while #calculables > 0 do | |||
local idx = table.remove(calculables, 1) | |||
return calc_results | 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 | end | ||
function m_tablecalc.testquery() | function m_tablecalc.testquery(test) | ||
local results = m_cargo.query( | local results = m_cargo.query( | ||
{'passive_skills'}, | {'passive_skills'}, | ||
Line 73: | Line 117: | ||
connectionidsdelimiter=",", | connectionidsdelimiter=",", | ||
originrowid="AscendancyBerserkerStart", | originrowid="AscendancyBerserkerStart", | ||
distancefield="distance" | distancefield="distance", | ||
test = test or false | |||
} | } | ||
local calc_results = m_tablecalc.computedistance(results, calc_args) | local calc_results = m_tablecalc.computedistance(results, calc_args) |
Revision as of 04:06, 16 December 2021
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")
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