Last time, we gave up on trying to get our data out of the database in a structured way and settled for just getting it out sorted alphabetically. Now we’ll get into the juicy stuff: doing the sort in ColdFusion.
Before we start on the code, let’s stop and think about what we’re doing. Obviously, we need a place to start. We know from our test data that the first thing on our list should be “Coding”. But how can we make the code see that?
Wrong Answer #1: Look for anything with a ParentID of “0”. What makes “0” special? We could assume that the tree always starts at “0”. But then we’re screwed if someone doesn’t start their list with “0”. And what if instead of starting the list off with “0”, they set the ParentID to NULL?
Wrong Answer #2: Look for anything with a ParentID of NULL, or “0”, or the lowest ParentID we can find. This is a slightly more convoluted version of the first wrong answer. Sure, you’re likely to catch more lists this way, but are you really gaining anything? We already know that we can’t trust IDs for ordering, so we really shouldn’t use the lowest ParentID, either.
So what are we left with?
Best Guess: Start with items that have parents that we can’t find. Logically, there should be at least one item in the list with a ParentID that we can’t match to an ItemID. So, if we go though the list and find any items that have parents that we can’t find, they should be top-level items. (I’ve also seen lists that set the root item’s ParentID to its own ItemID, but we can special-case that.)
Let’s get some of this in code. Assume that we’ve already run the query and called it “Stuff”. We’ll start off by looping over the query to build an index of where (which row number) each item (by ID) is within the query. We can then find the root elements by seeing where the holes are in that index.
<cfset RowFromID=StructNew()> <cfloop query="Stuff"> <cfset RowFromID[ItemID]=CurrentRow>
</cfloop> <cfset RootItems=ArrayNew(1)> <cfloop query="Stuff"> <cfif NOT StructKeyExists(RowFromID, ParentID)> <cfset ArrayAppend(RootItems, ItemID)> </cfif> </cfloop>
RootItems array, we now have all of the ItemIDs for the items for which we can’t find the parent. Since our query was sorted alphabetically when we ran it, the array is already in the right order.
Next, we’ll see what we can do with this.