SOLVED [Tables: Value instead of reference (Tree iterator function)]

SOLVED
:man_facepalming: moment, I realized that because the iterate function isn’t being run asynchronously I can just add the value to the table, run the iterate function, then remove the added value. (I don’t need to get a new/value table in this case.)

I am still curious about strong and weak tables, so if anyone recommends an article about that I’ll mark it as the solution.

Context

I have written a function that iterates over tree structured tables that look like this:

{
	A = {
		A1 = {};
		A2 = {};
	};
	B = {
		B1 = {
			B1A = {};
		};
		B2 = {};
	};
}

A visual representation would look like this:
89324

For each item in the tree, an inputted function is run with two parameters: the name of the current node and an array representing the parent nodes.

For example, for item "B1A" the function would get the tuple ("B1A", {"B1", "B"}).

Here is the complete code:

local treeIterate
--[[
(tree : Tree, func : function)

Runs func on every memeber of a tree-like table. The inputted function gets two parameters: the current string and an array of previous strings
]]
do
	local function cloneAppendToContext(append, context)
		local newContext = {append}
		for _, contextValue in ipairs(context) do
			table.insert(newContext, 2, contextValue)
		end
		return newContext
	end

	treeIterate = function(tree, func)
		local function iterate(dict, context)
			for key, value in pairs(dict) do
				func(key, context)

				-- (Edit)
				--iterate(value, cloneAppendToContext(key, context))
				-- SOLUTION:
				table.insert(context, 1, key)
				iterate(value, context)
				table.remove(context, 1)
			end
		end

		iterate(tree, {})
	end 
end

TreeIterateScript.rbxl (34.6 KB)

Example Usage

Code:

treeIterate({
	A = {
		A1 = {};
		A2 = {};
	};
	B = {
		B1 = {
			B1A = {};
		};
		B2 = {};
	};
}, function(key, context)
	print("Parent of "..key.." is "..(context[1] or ""))
end)

Output:

Parent of A is
Parent of A1 is A
Parent of A2 is A
Parent of B is
Parent of B2 is B
Parent of B1 is B
Parent of B1A is B1

Questions

My problem is that I want the context table to behave like a value instead of a reference, so that I can append an item to the context and pass it to the iterate function, but then have context remain unchanged for the next iteration of the for loop.

I am curious if there is a better way to do this than my cloneAppendToContext function, which simply creates a new table and iterates through the old one inserting the values. Maybe there is a way to do this with metatables? Would that be efficient for such a short lasting table?

If cloning the table is the only way, I’m also wondering if something like table.pack(key, table.unpack(context)) is better or if the type conversion is killer for performance.

On a slightly different note, does anyone know if it is bad to declare a function inside of another function? Should I put the func variable as a parameter and move that outside the scope of the function?

If anyone has some good articles or anything related to this I would really appreciate those.

Thanks a bunch :smiley: :wave:

I’m having trouble understanding what’s the use of the treeIterate; it’s not even returning anything.

1 Like

I use tree iterate to run a function on all the nodes/elements in a tree.

It’s sort of like the for loop below:

local dict = {
	["Pie"] = "awesome";
	["Pizza"] = "great";
	["Cake"] = "just okay";
}

local func = function(key, value)
	print(key.." is "..value..".")
end

for key, value in pairs(dict) do
	func(key, value)
end
Output
  Pizza is great.
  Cake is just okay.
  Pie is awesome.

But instead it’s in this format, with the loop inside a general function.

local dict = {
	["Pie"] = "awesome";
	["Pizza"] = "great";
	["Cake"] = "just okay";
}

local func = function(key, value)
	print(key.." is "..value..".")
end

local function iterate(dict, func)
	for key, value in pairs(dict) do
		func(key, value)
	end
end

iterate(dict, func)
Output
  Pizza is great.
  Cake is just okay.
  Pie is awesome.

So in a similar way:

local dict = {
	A = {
		A1 = {};
		A2 = {};
	};
	B = {
		B1 = {
			B1A = {};
		};
		B2 = {};
	};
}

local func = function(key, context)
	print("Parent of "..key.." is "..(context[1] or ""))
end

local function treeIterate(dict, func)
	-- The function goes here
end

treeIterate(dict, func)
Output
  Parent of A is
  Parent of A1 is A
  Parent of A2 is A
  Parent of B is
  Parent of B2 is B
  Parent of B1 is B
  Parent of B1A is B1

See how that iterates over every node/element in the table?

I use it to process data in a tree form. An example would be the hierarchy.

Hierarchy example
local workspace = game:GetService("Workspace")
local baseplate = workspace.Baseplate
local texture = baseplate.Texture
local spawnLocation = workspace.spawnLocation

local dict = {
	workspace = {
		baseplate = {
			texture = {};
		};
		spawnLocation = {}
	};
}

-- Sets the name of the instance to a name like W.B.T (Workspace > Baseplate > Texture)
local function coolName(instance, context)
	local name = ""
	for i = #context, 1, -1 do
		name ..= string.sub(context[i], 1,1).."."
	end
	name ..= string.sub(instance.Name, 1, 1)
	
	instance.Name = name
end


local function treeIterate(dict, func)
	-- The function goes here
end

treeIterate(dict, coolName)

Result:

  • Names Workspace "W", Baseplate "W.B", Texture "W.B.T", and SpawnLocation "W.S"

The reason it’s in a function and not just a for loop like the first code block is because I need to be able to do something called recursion, which is just calling a function from inside itself. This lets me process each branch of the tree in a similar repeating way.

Some languages have a built in way to iterate over data like this (or a way to customize how custom objects are iterated over) so in languages like python I could just use a for loop to do something like this. I could also create a function that returns an array I could iterate over with ipairs. I personally am satisfied my original solution though.

Generate array to be iterated over example
local dict = {
	A = {
		A1 = {};
		A2 = {};
	};
	B = {
		B1 = {
			B1A = {};
		};
		B2 = {};
	};
}

local function treeIterate(dict, func)
	-- The function goes here
end

-- Uses treeIterate to generate an array representing the nodes of a tree
local function generateArrayFromTreeNodes(tree)
	local array = {}
	local function add(key, context)
		table.insert(array, {key, context})
	end
	
	treeIterate(tree, add)
	
	return array
end

-- For loop can now iterate over all elements of the tree
for _, keyContextPair in ipairs(generateArrayFromTreeNodes(dict)) do
	local key = keyContextPair[1]
	local context = keyContextPair[2]
	print("Parent of "..key.." is "..(context[1] or ""))
end
Output
  Parent of A is
  Parent of A1 is A
  Parent of A2 is A
  Parent of B is
  Parent of B2 is B
  Parent of B1 is B
  Parent of B1A is B1

The reason it doesn’t return anything is because I only want it to preform an action. Similar to how print("Hello") only does an action and doesn’t return anything.

Is it similar to this:

local function SearchTree(table, name)
	for key, value in next, table do
		if (typeof(value) == "table") then
			SearchTree(value, key)
		end
		
		print(("%s is Parent of %s"):format(key, name))
	end
end

local dict = {
	A = {
		A1 = {};
		A2 = {};
	};
	B = {
		B1 = {
			B1A = {};
		};
		B2 = {};
	};
}

SearchTree(dict, "dict")
-- Result
  A1 is Parent of A - Script:41
  A2 is Parent of A - Script:41
  A is Parent of dict - Script:41
  B2 is Parent of B - Script:41
  B1A is Parent of B1 - Script:41
  B1 is Parent of B - Script:41
  B is Parent of dict - Script:41
1 Like

Yep! That code uses the exact same idea.

The only differences are that my code:

  • Assumes that the values of all the keys are tables
  • Has a function parameter that can be used to change the behavior
  • Stores a context value so the inputted function’s code can know where it is in the tree

Other than that, it’s the same idea.

That function should probably look like this:

local function SearchTree(table, name)
	for key, value in next, table do
		if key == name then
			return value
		elseif (typeof(value) == "table") then
			SearchTree(value, key)
		end
	end
end

Why would you need to return if key == name? Anyway, I’m guessing you already have solved it, you do you.

1 Like

I noticed that name wasn’t used. Search tree usually searches the tree for a key/name then returns the value associated with it.

Example:

local dict = {
	A = {
		A1 = {};
		A2 = {};
	};
	B = {
		B1 = {
			B1A = {};
		};
		B2 = {};
	};
}

local function SearchTree(table, name)
	for key, value in next, table do
		if key == name then
			return value
		elseif (typeof(value) == "table") then
			SearchTree(value, key)
		end
	end
end

print(SearchTree(dict, "B1"))

Output:

{B1A = {}} -- Found the children of B1. More interesting with trees that don't only end in tables

Edit:

Never mind then.

That’s not what I meant when I used the variable name SearchTree, in short DeepShearch.

1 Like