Created
February 20, 2021 11:45
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<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 ;'>→</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