Рекурсивный поиск с объектами Lua

В Lua у меня есть древовидная структура отношений между объектами, где объект может иметь несколько дочерних объектов, но только один родительский объект, т.е.

obj---obj1---obj2---objd3---obj4---obj5---obj6

Если я хочу знать «отдаленных» родителей obj6, а не только непосредственного родителя obj5, как я могу этого добиться? Мне просто нужен список родителей на два или более уровней выше текущего объекта, а API, с которым я работаю, имеет только свойство obj.parent.

Псевдокод также был бы полезен, чтобы направить меня в правильном направлении.


recursion lua pseudocode
person aethys    schedule 21.06.2012    source источник
comment
Что вы пробовали? Кажется, вы знаете, что вам нужно выполнить рекурсивный поиск, так что сделайте это.   -  person Nicol Bolas    schedule 21.06.2012

Ответы (2)


arrow_upward
2
arrow_downward

Ну, если ваш API поддерживает .parent, вы не можете сделать что-то вроде следующего? Я ржавый с Lua, но это должно дать начало.

local function GetAncestors(child)

    local ancestors = {};

    if child.parent then
        local i = 0;
        ancestors[0] = child.parent;
        while ancestors[i].parent do
            ancestors[i + 1] = ancestors[i].parent;
            i = i + 1;
        end
    end

    return ancestors;

end
person canon    schedule 21.06.2012
comment
Большое спасибо, это было именно то, что я пытался сделать. :) - person aethys; 22.06.2012
comment
Кстати, это должно дать вам запрошенное list of parents, из которого вы затем можете исключить любые поколения, которые хотите. Как я уже сказал, если у меня есть проблемы с логикой/синтаксисом, дайте мне знать. - person canon; 22.06.2012

arrow_upward
3
arrow_downward 

obj.parent               -- immediate parent (obj5)
obj.parent.parent        -- parent's parent (obj4)
obj.parent.parent.parent -- parent's parent's parent (obj3)

Так далее и тому подобное?

Если вы хотите избежать попыток ссылаться на несуществующего родителя, я предположил, что вы могли бы сделать что-то вроде:

function getAncestor(obj, depth)
   if not obj.parent then
      return nil
   elseif depth > 1 then
      return getAncestor(obj.parent, depth-1)
   end
   return obj.parent
end


-- get parent
obj = getAncestor(obj6)

-- get great great grandparent
obj = getAncestor(obj6, 3)
person Mud    schedule 21.06.2012