Getting a table's value path

Headstackk · July 15, 2021, 5:53pm

I’m trying to create a code that prints a path of a non table value in a table, for an example:

local tbl = {
	Apple = 3;
	Banana = {
		foo = "E";
		test = {
			lol = "F";
		};
	};
};

And I want an output of:

{"Apple"}
{"Banana", "foo"}
{"Bannaa", "test", "lol"}

I tried using a simple table loop but it won’t work as expected since the path will be overrided when looping a new table, any solutions to this? I’d like to keep only looping the entire table once, but not looping the entire table again when creating a new path.

local path = {}
local function loop(loopTbl)
	for i,v in pairs (loopTbl) do
		table.insert(path, i)
		if type(v) == "table" then
			loop(v)
		else
			print(path)
		end
	end
end
loop(tbl)

7z99 · July 15, 2021, 7:23pm

I started writing a response awhile ago but decided to come back because this question interested me so I took a look into it.

Anyway, you’re able to do this with recursion. I had fun writing this:

local tbl = {
	Apple = 3;
	Banana = {
		foo = "E";
		test = {
			lol = "F";
		};
	};
};

local hierarchy = {} -- this is what we are going to store the hierarchy in

local function getHierarchy(value, tbl, attempt, level)
	local level = level or 1 -- this determines the index of the hierarchy table
	local found
	for i,v in pairs(tbl) do
		if type(v) ~= 'table' and v == value then -- if v isn't a table and v is equal to the value then we can set the idnex to the value'
			hierarchy[level] = i
			return true
		elseif type(v) == 'table' then -- if the v is a table then
			found = getHierarchy(value, v, attempt, level + 1) -- call the functiom with the index as the last index plus 1, pass the current table
			if found then
				hierarchy[level] = i -- if it's found, set the index to i
				return found -- return the found value, assuming this is calling itself (we don't really have any way to know)
			end
		end
	end
end

local found = getHierarchy('F', tbl)

print(hierarchy) -- [1] = 'Banana'; [2] = 'test'; [3] = 'lol'

You can do this as much as you want, with any level.

local tbl = { -- this is the base
	Apple = 3;
	Banana = {
		foo = "E";
		test = {
			lol = "F";
		};
		moreTest = {
			wow = {
				this = {
					can = {
						go = {
							really = {
								really = {
									really = {
										andIMean = {
											REALLY = {
												far = {
													down = {
														because = {
															of = {
																our = {
																	good = {
																		friend = {
																			recursion = ':)'
																		}
																	};
																	look = {
																		it = {
																			even = {
																				works = {
																					with = {
																						multiple = {
																							tables = ':O'
																						}
																					}
																				}
																			}
																		}
																	}
																}
															}
														}
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}	
		};
		moreMoreTest = {};
	};
};

--...

local found = getHierarchy(':O', tbl)
--[[
 ▼  {
                    [1] = "Banana",
                    [2] = "moreTest",
                    [3] = "wow",
                    [4] = "this",
                    [5] = "can",
                    [6] = "go",
                    [7] = "really",
                    [8] = "really",
                    [9] = "really",
                    [10] = "andIMean",
                    [11] = "REALLY",
                    [12] = "far",
                    [13] = "down",
                    [14] = "because",
                    [15] = "of",
                    [16] = "our",
                    [17] = "look",
                    [18] = "it",
                    [19] = "even",
                    [20] = "works",
                    [21] = "with",
                    [22] = "multiple",
                    [23] = "tables"
                 }  -  Edit
]]
--
local found = getHierarchy(':)', tbl)

print(hierarchy) 
--[[ ▼  {
                    [1] = "Banana",
                    [2] = "moreTest",
                    [3] = "wow",
                    [4] = "this",
                    [5] = "can",
                    [6] = "go",
                    [7] = "really",
                    [8] = "really",
                    [9] = "really",
                    [10] = "andIMean",
                    [11] = "REALLY",
                    [12] = "far",
                    [13] = "down",
                    [14] = "because",
                    [15] = "of",
                    [16] = "our",
                    [17] = "good",
                    [18] = "friend",
                    [19] = "recursion"
                 }  -  Edit
]]

D0RYU · July 15, 2021, 8:01pm

as this is very cool to see
it doesn’t output this

so I decided to take your function to make it achieve this!

local Table = {
	Apple = 3,
	Banana = {
		foo = "E",
		test = {
			lol = "F"
		}
	}
}

function GetAllTablePaths(Table)
	local function Hierarchy(Value1, Table1)
		local Hierarchy = {}
		local function GetHierarchy(Value2, Table2, Attempt, Level)
			local Level = Level or 1
			local Found = nil
			for i, v in pairs(Table2) do
				if type(v) ~= 'table' and v == Value2 then
					Hierarchy[Level] = i
					return true
				elseif type(v) == 'table' then
					Found = GetHierarchy(Value2, v, Attempt, Level + 1)
					if Found then
						Hierarchy[Level] = i
						return Found
					end
				end
			end
		end
		GetHierarchy(Value1, Table1)
		return Hierarchy	
	end
	local Paths = {}
	local function LoopTable(Table1)
		for i, v in pairs(Table1) do
			if type(v) == "table" then
				LoopTable(v)
			else
				table.insert(Paths, Hierarchy(v, Table))
			end
		end
	end
	LoopTable(Table)
	return Paths
end

print(GetAllTablePaths(Table))

now I know the variable names like Table, Table1, Table2 can obviously be different
but here is the output of print(GetAllTablePaths(Table))

EDIT1: I am 100% sure this can be improved and be more efficient, if anyone wants to improve this code please do so!
EDIT2: I fixed a small bug in the code

Jaycbee05 · July 16, 2021, 12:22am

I’m late to the party, but I think there might be another slight issue with your implementation . Because you are finding the value first–then going in reverse to ultimately find its path, issues would arrive when there are duplicate values present. Such as cases like:

local Table = {
	Banana = 'F',
	Orange = 'F'
}

It wouldn’t likely return what it’s supposed to because each time that Hierarchy function runs and encounters an 'F' it will assume that’s the same 'F' we wanted to find the path of (rather than being a different one that we haven’t found yet).

One might be able to fix this, as the Hierarchy function is building, by checking if the Hierarchy doesn’t exist already, but that would mean checking through each previous hierarchy each subsequent iteration of the source table. I don’t think that would scale well, so maybe instead one could remove all margin of possibility that the “same” value can be encountered twice altogether.

Here’s my implementation:

local function generate_tree(t)
	local hierarchy = {}

	local function next(t, trace) --//trace can be moved above(to upvalue)
		local depth = #trace
		for index, value in pairs(t) do
			if type(value) == 'table' then
				trace[depth+1] = index 
				next(value, trace)
			else
				local new_table = table.move(trace, 1, depth, 1, {})
				new_table[#new_table + 1] = index
				hierarchy[#hierarchy+1]  = new_table
			end
		end
	end

	next(t, {}); return hierarchy
end

The only difference here, is as we descended into the depths of recursion, we don’t return and also keep a variable on the stackframe, depth, so that later we can use it as an end point for a newly found non-table value. it’s so cases like this work (and can recursively):

local Table = {
	Banana = {lol = 'F'}, -- iterated first
	Orange = 'E' -- iterated second
}

D0RYU · July 16, 2021, 12:33am

it is fine if you are late
also I simply used @7z99’s function because I saw a way to use it
thank you for improving the existing code

this is definitly what I was thinking, since 7z99’s code was based on getting a value and if two values were the same it would mess up
and the fact that you made this go in order makes it even better

this is awesome

EDIT: I only have one problem with your code, you named the local function “next” when it is already a global variable

Jaycbee05 · July 16, 2021, 1:08am

I did indeed do this, but I don’t think it really affects much–other than syntax highlighting. As far as I know all that would happen is that the global next would get overshadowed by its local counterpart (with no run-time performance penalties). But of course, anyone could always just change it.