Lua — как отсортировать таблицу по цепочке создания ценности

Я ищу метод сортировки таблицы Lua по цепочке значений. Скажем, таблица:

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

Должно превратиться в это после сортировки:

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

Это не по существу с одинаковыми именами, они могут отличаться. Я хотел сделать сравнение чисел после "контрольной точки", но оказалось, что мне приходится работать с такими динамическими вещами (уже отсортированными так, как я хочу):

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

Спасибо.


sorting lua lua-table chain
person Gallardo994    schedule 18.04.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

То, что вы описываете, называется топологической сортировкой. Однако, поскольку это ограниченный случай, нам не нужно реализовывать полный алгоритм топологической сортировки:

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

Применение:

local sorted = sort_list(vals)
person Tim Cooper    schedule 18.04.2015