Walking Trees Backwards

[Randall Reetz]

Man i am going to post a question to this list and start a company based on the code people submit as examples.  You guys are impressive!

-----Original Message-----
From: "Alex Tweedly" <alex at tweedly.net>
To: "How to use Revolution" <use-revolution at lists.runrev.com>
Sent: 9/11/2008 6:21 PM
Subject: Re: Walking Trees Backwards

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
use-revolution at lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution