Skip to content

Instantly share code, notes, and snippets.

@bennadel
Created February 20, 2021 11:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bennadel/dc7545506b5bb26bb608a8050c848898 to your computer and use it in GitHub Desktop.
Save bennadel/dc7545506b5bb26bb608a8050c848898 to your computer and use it in GitHub Desktop.
Finding All Unique Paths In A Tree Structure In Lucee CFML 5.3.7.47
<cfscript>
// Setup our Tree for demonstration purposes. Each node in this tree is named based
// on its depth and its order at a particular depth.
tree = xmlParse("
<a1>
<b1>
<c1>
<d1 />
<d2 />
<d3 />
</c1>
</b1>
<b2 />
<b3>
<c2 />
</b3>
<b4>
<c3>
<d4>
<e1 />
<e2>
<f1>
<g1>
<h1>
<i1>
<j1 />
</i1>
</h1>
</g1>
</f1>
</e2>
<e3 />
</d4>
<d5 />
</c3>
</b4>
<b5 />
</a1>
");
printTreePaths( tree );
// ------------------------------------------------------------------------------- //
// ------------------------------------------------------------------------------- //
/**
* I perform a depth-first traversal of the given XML document, printing out the set
* of unique paths to every leaf-node.
*
* @tree I am the XML Document being walked.
*/
public void function printTreePaths( required xml tree ) {
// The "recursive" nature of this tree traversal will be powered by this queue so
// that we don't have to create a deep recursive call-stack. As each node is
// visited, its child-nodes will be PREPENDED to the queue for further traversal.
// Each node will be stored along with its depth so that we know how to "reset"
// the path as we move from node to node.
// --
// ASIDE: "Prepending" nodes creates a depth-first traversal while "Appending"
// nodes creates a breadth-first traversal.
var queue = [{
node: tree.xmlRoot,
depth: 1
}];
var paths = [];
var path = [];
// Continue pulling nodes OFF THE FRONT of the queue until we have visited the
// entire tree (depth-first).
while ( queue.isDefined( 1 ) ) {
var queueItem = arrayShift( queue );
var node = queueItem.node;
var depth = queueItem.depth;
// As we move to each node, we may be moving BACK UP in the tree depth. The
// size of this jump in depth will change based on the tree structure. As
// such, we have to "trim" the current path back to what it was ABOVE THIS
// NODE so that we then add this next as the LAST ITEM in the current path.
arrayTrimTo( path, ( depth - 1 ) )
.append( node )
;
// If there are any child nodes, queue them up for further exploration.
if ( node.xmlChildren.len() ) {
node.xmlChildren.each(
( childNode, i ) => {
// NOTE: All child-nodes are at the same depth in the tree.
var newQueueItem = {
node: childNode,
depth: ( depth + 1 )
};
queue.insertAt( i, newQueueItem );
}
);
// If this node has no children, it is a LEAF NODE; which means, it's the
// terminal node in the current path. As such, we can store a copy of the
// current path into the set of all collected paths.
} else {
paths.append( path.slice( 1 ) );
}
}
// At this point, we've collected all of the paths in the tree structure. But,
// that paths consist of complex XML data-structures. We need to map them onto
// simple node-name representations.
var delimiter = " <span style='color: deeppink ;'>&rarr;</span> "
for ( var path in paths ) {
var stringifiedPath = arrayPluck( path, "xmlName" )
.toList( delimiter )
;
echo( stringifiedPath & "<br />" );
}
}
// ------------------------------------------------------------------------------- //
// ------------------------------------------------------------------------------- //
// CAUTION: The following array functions may MUTATE the original array, which only
// "works" as expected in Lucee CFML because arrays are PASSED BY REFERENCE. If your
// runtime passes arrays by VALUE, none of this will work.
public array function arrayPluck(
required array values,
required string propertyName
) {
var propertyValues = values.map(
( value ) => {
return( value[ propertyName ] );
}
);
return( propertyValues );
}
/**
* I remove the first value in the array and return it.
*
* @values I am the array being mutated.
*/
public any function arrayShift( required array values ) {
var firstValue = values.first();
values.deleteAt( 1 );
return( firstValue );
}
/**
* I reduce the size of the array until it is less-than-or-equal-to the given length.
*
* @values I am the array being mutated.
* @length I am the length to which the array is being trimmed.
*/
public array function arrayTrimTo(
required array values,
required numeric length
) {
for ( var i = values.len() ; i > length ; i-- ) {
values.deleteAt( i );
}
return( values );
}
</cfscript>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment