Converting list of tables to hierarchy

[vopwn55]

I have a table, containing objects and a one-layer list of their children, that looks something like this:

Object1 = {"Child1"}
Child1 = {"Child2", "Child3"}
Child3 = {"Child4"}
OtherObject1 = {"OtherChild1", "OtherChild2"}
OtherChild1 = {"SomeOtherChild"}

How could I possibly convert it back to the original hierarchy?

Object1 = {
    Child1 = {
        Child2 = {},
        Child3 = {
            Child4 = {}
        }
    }
}
OtherObject1 = {
    OtherChild1 = {
        SomeOtherChild = {}
    },
    OtherChild2 = {}
}

I tried looping through all elements of the flat table and reassigning their children to elements in a new table but it made an even bigger mess. Could someone help?

[sonic_848 (killer)]

Idk what you’re asking… Do you just want to loop through all tables?

[vopwn55]

As I said in the post I have a table with elements and their children. How can I rearrange them back into their original hierarchy like the example

[YasuYoshida (Yasu)]

It’s a pretty simple task once you identify what you need to do. You just need to loop through the flat hierarchy and find which objects with children don’t have ancestors. If an object doesn’t have an ancestor, it must be at the top of the hierarchy. Once you’ve identified that an object has no ancestors, you can then do a recursive loop that gets its descendants.

Once you have that tree of descendants, you can then add it to the final table with the top ancestor as the key. That’s all there is to it.

local function createNonFlatHierarchy(flatHierarchy)
	local nonFlatHierarchy = {}

	local function getDescendantsForObject(object)
		local flatChildren = flatHierarchy[object]
		if flatChildren==nil then
			return {}
		end

		local objectChildren = {}
		for _,child in flatChildren do
			objectChildren[child] = getDescendantsForObject(child)
		end
		return objectChildren
	end

	-- checks if an object has an ancestor
	-- if it does not have one, then it must be the top of the hierarchy
	-- and it can be used to create a tree of descendants
	for object, children in flatHierarchy do
		local hasAncestor = false
		for otherObject, otherChildren in flatHierarchy do
			if otherObject==object then
				continue
			end
			if table.find(otherChildren, object) then
				hasAncestor = true
				break
			end
		end
		if not hasAncestor then
			nonFlatHierarchy[object] = getDescendantsForObject(object)
		end
	end

	return nonFlatHierarchy
end

local flatHierarchy = {
	Object1 = {"Child1"},
	Child1 = {"Child2", "Child3"},
	Child3 = {"Child4"},
	OtherObject1 = {"OtherChild1", "OtherChild2"},
	OtherChild1 = {"SomeOtherChild"},
}

local newHierarchy = createNonFlatHierarchy(flatHierarchy)
print(newHierarchy)

Running that piece of code would yield this result in the output widget:

▼ {
	["Object1"] =  ▼  {
		["Child1"] =  ▼  {
			["Child2"] = {},
			["Child3"] =  ▼  {
				["Child4"] = {}
			}
		}
	},
	["OtherObject1"] =  ▼  {
		["OtherChild1"] =  ▼  {
			["SomeOtherChild"] = {}
		},
		["OtherChild2"] = {}
	}
}

[vopwn55]

I can’t believe I never thought of that! But thank you so much for providing this piece of code and how it’s done