Lua - comment trier une table par la chaîne de valeur

Question

Je cherche une méthode de tri d'une table Lua par sa chaîne de valeurs. Dites, la table:

local vals = { 
{ id = "checkpoint4" }, 
{ id = "checkpoint1", nextid = "checkpoint2" }, 
{ id = "checkpoint3", nextid = "checkpoint4" }, 
{ id = "checkpoint2", nextid = "checkpoint3" }, 
} 

Si transformer en ce tri après:

local vals = { 
{ id = "checkpoint1", nextid = "checkpoint2" }, 
{ id = "checkpoint2", nextid = "checkpoint3" }, 
{ id = "checkpoint3", nextid = "checkpoint4" }, 
{ id = "checkpoint4" }, 
} 

Ce n'est pas essentiellement avec les mêmes noms exacts, ils peuvent varier. Je voulais faire la comparaison des chiffres après « point de contrôle », mais il est avéré que je dois travailler avec des choses dynamiques comme celui-ci (déjà trié la façon dont je veux que ce soit):

local vals = { 
{ id = "checkpoint1", nextid = "cp" }, 
{ id = "cp", nextid = "chp" }, 
{ id = "chp", nextid = "mynextcheckpoint" }, 
{ id = "mynextcheckpoint"}, 
} 

Merci.

Answer 1

Ce que vous décrivez s'appelle topological sorting. Cependant, étant donné que cela est un cas restreint, nous ne devons pas mettre en œuvre un algorithme de tri topologique complet:

function sort_list(tbl) 
    local preceding = {} 
    local ending 
    local sorted = {} 
    for i, e in ipairs(tbl) do 
    if e.nextid == nil then 
     ending = e 
    else 
     preceding[e.nextid] = i 
    end 
    end 
    if ending == nil then 
    return nil, "no ending" 
    end 
    local j = #tbl 
    while ending ~= nil do 
    sorted[j] = ending 
    ending = tbl[preceding[ending.id]] 
    j = j - 1 
    end 
    if sorted[1] == nil then 
    return nil, "incomplete list" 
    end 
    return sorted 
end 

Utilisation:

local sorted = sort_list(vals) 

Answer 2

local id2val, tailsizes = {}, {} 
for _, val in ipairs(vals) do id2val[val.id] = val end 

local function tailsize(val) -- memoized calculation of tails sizes 
    if not tailsizes[val] then 
     tailsizes[val] = 0       -- cycle-proof 
     if val.nextid and id2val[val.nextid] then -- dangling nextid proof 
     tailsizes[val] = tailsize(id2val[val.nextid]) + 1 
     end 
    end 
    return tailsizes[val] 
end 

-- sorting according to tails sizes 
table.sort(vals, function(a,b) return tailsize(a) > tailsize(b) end)