Tree walking API. "for _,sPath in subDir ("rom")" - ComputerCraft Forums (archive)

aaa #1

53 posts

Posted 24 January 2014 - 12:44 AM

Hi!

I recently played with algorithmics and iterators and made an API to walk through trees. Not actual trees of course, but trees like genealogic trees. For example, a table can be seen as a tree, as well as folders. Take a look there for further explanation.

tree API on pastebin : http://pastebin.com/ZFaWd9iH

With few coding, you can now walk through (=enumerate any node) any tree shaped structure.

tree.explistGen

Spoiler

syntax :


subValues = tree.explistGen(fSons, [isInode, [option]])

for _,v in subValues(root, order) do
	doStuff()
end

returns a pairs-like function, ie a function which, when applied to a tree, returns an "explist", which actually is a 3-uple of "iterator, base, initial element".

fSons must be a function that takes an internal node of the tree, and rreturns the list (table, numerical or not, keys don't matter) of its sons.
optional isInode is a function that tells wether a node is internal or not (may have children). Necessary when fSons errors on non internal nodes, or do not returns an empty table
option is either "nodes", "inodes" or "leaves". On "inodes", the iterator will only return the internal nodes, on "leaves", the terminal nodes. Default : "nodes".
order is either "pre", "post" or "bfs", which stands for pre-order, post-order and level-order (breadth-first search), that are the order of the walk (ref). Default : "pre"

example : subValues walk through any elements and sub elements and sub sub el… of a table


local fSons = function (t)
	return t
-- a table is already the set of its sons.
end
local isInode = function(t)
-- necessary since  fSons does not return a table when called on leaves.
	return type(t) == "table"
end

subValues = tree.explistGen(fSons, isInode)

Warning : the code above infinite loop on auto referring tables (could be fixed with a better fSons)

the first returned value is used for the walk, due to the way iterator work, so type


for _,v in subValues(myTable) do
...
end

(or anything that you won't use, "_" is just a convention)

other example : subDir : list any sub directories of one folder.


local fSons = function (sPath)
--nodes are absolute path (strings)
	local tSons = fs.list(sPath)
	for k,v in pairs(tSons) do
		tSons[k] = s..tSons[k]
	end
	-- I just transformed local into absolute
	return tSons
end

--isInode could have been useless, since [url="http://computercraft.info/wiki/Fs.list"]fs.list works consistantly on files[/url], however, we need it to enumerate only directories. What we need is exactly fs.isDir()

subDir = tree.explistGen(fSons, fs.isDir, "inode")

let say you have a folder "myhelp" with help documentation and want to have subdirectories, for readability, and you want to add the several paths to the help directories. Then just type :


for _,sPath in subDir("/myhelp") do
	help.setPath(help.path()..":"..sPath)
end

tree.explistGenOpt

Spoiler

syntax :


subValues = tree.explistGenOpt(fSons, [isInode])

for _,v in subValues(root, [order],[opt]) do
	doStuff()
end

Just in case you want put the option into the pairs-like function.
example :


local fSons = function (sPath)
	local tSons = fs.list(sPath)
	for k,v in pairs(tSons) do
		tSons[k] = s..tSons[k]
	end
	return tSons
end

subFiles_Folders = tree.explistGenOpt(fSons, fs.isDir)

then


for _,sPath in subFiles_Folders("/myhelp", nil,"inode") do
<block>
end

is equivalent to the previous


for _,sPath in subDir ("/myhelp") do
	<block>
end

The three other functions (tree.itNodes, tree.itInodes, tree.itLeaves) of the API are iterator generators (iterator = next-like function) :

Spoiler


(explistGen (fSons, fIsInode, "nodes"))(t,order)

is (almost) the same as


itNodes(fSons, fIsInode), order, {t}

Hope you enjoyed. Tell me if you want more examples like subDir

Edited on 23 January 2014 - 11:45 PM

robhol #2

175 posts

Posted 24 January 2014 - 01:32 AM

Not saying this to be mean, but what's the point when you can do the same in a 3-4 line recursive function?

aaa #3

53 posts

Posted 24 January 2014 - 01:53 AM

robhol, on 24 January 2014 - 01:32 AM said:
Not saying this to be mean, but what's the point when you can do the same in a 3-4 line recursive function?

nope, except, for my personal challenge of not using recursion. To be honest, I did'nt realized how appropriate recursion was :rolleyes:/> . But even using recursion,
However, if you ever looked at the textutils.serialize code, which also "just needs" to walk through a table (in a more complex way I do), You'd see that it is maybe not 3-4 lines you need, even using recursion.

Plus, I find the iterator packaging very sexy ;)/> (and educational), and I cannot figure out how to write it simpler.

Edited on 24 January 2014 - 12:54 AM

robhol #4

175 posts

Posted 24 January 2014 - 04:27 PM

Sure. Not trying to put things down. But yeah, it really is 3 lines, limited to lines with "algorithmic importance" and separating out any other logic.


function traverse(n) -- 1
  doWhatever(n)
  for k, c in pairs(n) do -- 2
	traverse(c) -- 3
  end
end

I expect table.serialize contains a bit of added logic, possibly accounting for cyclical references in tables and that sort of thing. This is the "general" shape of such an algorithm, though.

Edited on 24 January 2014 - 03:29 PM