Our second attempt left us with two indexes (items to rows and parents to children) and an array of the root nodes for the tree. Our next task is to figure out how we can efficiently take these things and build a tree out of them. I emphasize efficiently, because we’ve already discussed the perils of the most obvious solution: recursion. Instead, we’ll do our best to implement the solution iteratively.
We know we need a way to list an item, its first child, it’s first child’s child, et cetera, in a depth-first approach. That is, we want to go down as many levels as we can before listing a second item. As we finish a level, we need to pop back up to the previous level and move on to the second, then the third, and so on. I can hear the CompSci crowd saying “Aha!” at that one. Yep, we’ll need a stack. For the non-CompSci among you, we need a place to keep track of all the items we still need to work on. Luckily, ColdFusion arrays can provide exactly what we need with the ArrayAppend, ArrayPrepend, and ArrayDeleteAt functions.
Even better, we already have an array with a list of items we need to work on: RootItems. But here’s where we need to make a decision. We can either treat the end or the beginning of the array as the top of the stack. While it may seem more logical to use the end of the array, it’ll make the code profoundly easier to read if we use the beginning. You’ll see why later, but this works out well since the first item on our stack is the first item we want to work with. Enough talk, let’s code.
First we’ll need to pop the current item off the top of the stack:
<cfloop condition="ArrayLen(RootItems) GT 0"> <cfset ThisID=RootItems> <cfset ArrayDeleteAt(RootItems, 1)>
For now, let’s just output the name of the item. We’ll change this to do something more interesting later. Of course, we may be looking at a parent node, so we need to make sure the item exists before we try to display it.
<cfif StructKeyExists(RowFromID, ThisID)> <cfset RowID=RowFromID[ThisID]> <cfoutput>#Stuff.Name[RowID]#<br /></cfoutput> </cfif>
Look to see if we have any children:
<cfif StructKeyExists(ChildrenFromID, ThisID)> <cfset ChildrenIDs=ChildrenFromID[ThisID]>
Then push any children onto the stack. We need to do this backwards so that the first child ends up on the top of the stack. Alternatively, we could have pushed them into the index backwards to begin with, but it’s pretty much the same thing, and this looks more deliberate.
<cfloop from="#ArrayLen(ChildrenIDs)#" to="1" step="-1" index="i"> <cfset ArrayPrepend(RootItems, ChildrenIDs[i])>
That’s it. Close it up and finish it off:
</cfloop> </cfif> </cfloop>
That’ll do for the basics of what we want. We should now have a list that is in the correct order, and since we should (hopefully) hit each point in the tree only once we’re still at linear, O(n), time. Of course, there’s still quite a bit to add to make it sturdier and prettier, but we’ll save that for next time.
- Well, I presume it would be the most obvious solution to the folks who started off on classic procedural languages. For those of you who are cutting your programming teeth with ColdFusion … move along, nothing to see here.