Creating An Exploded View Of Flat Hierarchal Data Using Coldfusion

One of the things that I have been looking at lately is how to handle hierarchical data in an efficient way. One of the ideas that has made the most sense was to store the hierarchical information in a flat table structure with references to a parent item in each row.

In a very simplistic view of the data, we could look at the data as an associative array with some random data:

<cfscript>
flatTable = StructNew();

flatTable["1"] = "root";
flatTable["2"] = "1";
flatTable["3"] = "1";
flatTable["4"] = "1";
flatTable["5"] = "2";
flatTable["6"] = "5";
flatTable["7"] = "3";
flatTable["8"] = "3";
</cfscript>

This is a nice representation of my table as I can easily reference any member without worrying about the depth of the hierarchical structure. However, there may be times when I need to explode the structure into a more fleshed out structure. To accomplish this, there are several scenarios for parsing the structure.

Two that I found at CFLib.org work with queries and use multiple and nested loops. The functions makeTree and queryTreeSort still return back a flat structure, though with very helpful depth indicators.

There are other solutions involving recursion, stacks, flat tables, and tree traversal algorithms. There is a handy page covering these four ways to work with hierarchical data as well as some interesting reading in the comments.

These are good ways, but, while contemplating the problem, I kept thinking that there had to be an easier way - and I found one. Perhaps not the most efficient from a memory or processor utilization standpoint, but I did come up with a method that is much more straightforward and does not involve nested loops, recursion or anything hard to get one's head around.

Essentially, I looked at the problem as being easy to solve if I attacked in backwards. That is, if you start at root of the hierarchical tree, the node that contains all children, every step represents some degree of unknown. How many children does the next node have? And the one after that? If, instead, you begin with the fringe nodes, the ones that contain no children, there is no uncertainty; each node only has a one parent.

My first thought was to sort the struct by the parent value and then navigate up the tree, but where to put the items? Here's where it gets a little bit messy. Even in this simple example, maybe especially in this simple example, I need to translate my data a bit to accommodate my needs. In particular, I need to enable each node to be able to have children. This will give us the ability to store the information in an exploded structure.

So the first step I did was to convert each node into a structure with this handy function:

<cffunction name="newNode" returntype="Struct" >
<cfargument name="key" type="string" required="true" />
<cfargument name="value" type="string" required="true" />

<cfscript>
var tempStruct = StructNew();
tempStruct.label = arguments.key; // key
tempStruct.parent = arguments.value; // value
tempStruct.children = ArrayNew(1);
return tempStruct;
</cfscript>
</cffunction>

Creating a simple working structure gives a place to store our new nodes. Oh and we need to create a placeholder for the root structure as that is not explicitly represented in the flatTable structure:

<cfscript>
_working = StructNew()

_working["root"] = StructNew();
_working["root"].children = ArrayNew(1);

for (key in arguments.flatTable) {
_working["#key#"] = newNode(key,tree[key]);
}
</cfscript>

Now we need to sort the struct so we know where to start:

<cfscript>
sortedStruct = StructSort(arguments.flatTable,'textnocase');
</cfscript>

Now, all we need to do is to iterate over the list in reverse, add each node into its parent as we move along. When we get done, the root node will contain the nested structure of nodes.

<cfscript>
for (i=ArrayLen(sortedStruct); i>
0; i--) {
key = sortedStruct[i];
parent = arguments.flatTable["#sortedStruct[i]#"];

_working["#parent#"].children[ArrayLen(_working["#parent#"].children)+1] = _working["#key#"];
    
}    
</cfscript>

So for the above given input, you get the following:

And, as I hate it when such things are not available, here is all of the above in an abstracted function, well, two, actually:


<cffunction name="explodedView" returntype="struct">
<cfargument name="flatTable" type="struct" required="true" />
<cfset var _working = StructNew() />
<cfset var sortedStruct = StructNew() />

<cfscript>
// create the root level node
_working["root"] = StructNew();
_working["root"].children = ArrayNew(1);

for (key in arguments.flatTable) {
_working["#key#"] = newNode(key,arguments.flatTable[key]);
}
    
sortedStruct = StructSort(arguments.flatTable,'textnocase');

for (i=ArrayLen(sortedStruct); i>
0; i--) {
key = sortedStruct[i];
parent = arguments.flatTable["#sortedStruct[i]#"];
    
_working["#parent#"].children[ArrayLen(_working["#parent#"].children)+1] = _working["#key#"];
        
}    

return _working["root"];
</cfscript>
</cffunction>


<cffunction name="newNode" returntype="Struct" >
<cfargument name="key" type="string" required="true" />
<cfargument name="value" type="string" required="true" />

<cfscript>
var tempStruct = StructNew();
tempStruct.label = arguments.key; // key
tempStruct.parent = arguments.value; // value
tempStruct.children = ArrayNew(1);
return tempStruct;
</cfscript>
</cffunction>
Notice that we are only returning _working["root"]. The _working actually gets filled up with a lot of junk, but, at least in this case, the "root" node contains the full structure (and we can safely discard the rest).

Lastly, I'm not supposing this is ground breaking or earth shattering. Very likely someone has already gone this route before for better or worse. If you have links to earlier work, or anything related, please post them in the comments.

Comments (Comment Moderation is enabled. Your comment will not appear until approved.)
BlogCFC was created by Raymond Camden. This blog is running version 5.9.1.001. Contact Blog Owner