David Bovill wrote:
*Task*
I want to put an indented outline (more generally a tree structure) into an
array.
I suspect I've mis-understood your problem .... my "solution" seems so
straightforward that I may be missing some important part of the desired
data structure. So I'll re-state the problem in my own words, and then
give my attempt to solve it - and hopefully if there is something major
missing, that should be clear.
Input : an indented outline of text.
Output : a data structure which allows easy (quick, efficient, ....)
access to parent and children nodes of an arbitrary node, thereby making
it easy to write general (possibly recursive) functions and handlers.
[Aside - often recursion is a good tool to *think* about a problem, but
the implementation can be sequential .... ]
Data structure : 3 arrays, indexed by the line number (node number):
i, 'text' : the text of that node
i, 'parent' : the line number of its parent
i. 'children : a TAB-separated list of line numbers of its children.
Given this, it is easy to write the base functions needed to build
arbitrary tree-functions.
function getParent pArray, pNode
return pArray[pNode, 'Parent']
end getParent
function getChildren pArray, pNode
return pArray[pNode, 'Children']
end getChildren
for example - print out all immediate children ...
put getChildren(Data, thisnode) into tChildren
repeat for each item tChild in tChildren
put Data[tChild, 'Text'] & CR after field 'Output'
end repeat
So - a very simple data structure to build .... code is straightforward
if a little bit tricky
[Sorry - I have a stack ready to put on RevOline but RevOnline has
decided I need a new key to share stacks, so here is the code in-line ...]
(note - only tested a little bit)
function buildTree pInput
# given indented outline of a 'forest' (i.e. multiple rooted trees)
build the tree-like data structure
set the itemDel to TAB
put empty into lParents
put 0 into lCurNode # the top-level pseudo-node
put -1 into lCurDepth # -1 to allow for the top-level pseudo-node
put 0 into lCount
repeat for each line L in pInput
put getDepth(L) into tDepth
if tDepth < lCurDepth then
# we have popped back up 1 or more levels
put tDepth into lCurDepth
if tDepth = 0 then
put 0 into lCurNode
else
#put item tDepth+2 of lParents into lCurNode
put lCount into lCurNode
end if
else
if tDepth = lCurDepth then
# another node at the same level - no change needed
put lCount into lCurNode
else
if tDepth > lCurDepth+1 then # badly formed input !!
# should probably do something more extreme here
return empty
end if
# so we are here with a new increase in indent level
put lCurNode & TAB after lParents
end if
end if
put L into Data[lCount, 'text']
put item -1 of lParents into tParent
put tParent into Data[lCount, 'parent']
put lCount & TAB after Data[tParent, 'children']
put tDepth into lCurDepth
end repeat
return Data
end buildTree
Hope that does something like what you wanted,
-- Alex.
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
