Encapsulating Deep Object-Graph Traversal Using A Visitor Function In Lucee CFML 5.3.6.61
The other day, in JavaScript, I wrote some code that required three nested for-loops in order to locate data for consumption. The JavaScript code looked something like this:
screens.forEach(
( screen ) => {
screen.conversations.forEach(
( conversation ) => {
conversation.comments.forEach(
( comment ) => {
doSomethingWith( screen, conversation, comment );
}
);
}
);
}
);
This is hella ugly; and, on some level, "feels wrong" in a way that I can't fully articulate. As such, I thought it would be a fun to try and figure out a way to encapsulate this nested looping using some sort of a "Visitor" Function. Meaning, create an algorithm that takes an object graph and an operator and then have it invoke said operator for each desired leaf-node within the graph.
A couple of months ago, I looked at depth-first vs. breadth-first traversal; and, how we can use a Closure to separate tree traversal from node consumption in Lucee CFML. But, in those posts, I was visiting all nodes within an object graph. And, in this post, I wanted to look at visiting only a set of desired nodes.
The algorithm that I came up with for this post is similar to the previous ones in that it uses a "stack" to keep track of where it is in the object graph (as opposed to messing around with recursion). But, the difference in this algorithm is that I also need to keep track of the ancestor nodes so that I can pass them to the "visitor" function.
Ultimately, what I want is to be able to call something like this, where I provide a root collection, a set of keys to traverse, and a callback that gets invoked with each instance of the key-values:
<cfscript>
deepEach(
screens,
[ "conversations", "comments" ],
( screen, conversation, comment ) => {
doSomethingWith( screen, conversation, comment );
}
);
</cfscript>
To experiment with this idea, I set up a static data-structure with Users, Projects, Screens, and Comments:
<cfscript>
users = [
{
id: 1,
name: "Terry",
projects: [
{
id: 12,
name: "Terry's Project",
screens: [
{
id: 13,
name: "Terry's Screen",
comments: [
{
id: 14,
name: "Terry's Comment"
},
{
id: 141,
name: "Terry's Second Comment"
}
]
},
{
id: 131,
name: "Terry's Second Screen",
comments: []
},
{
id: 132,
name: "Terry's Third Screen",
comments: []
},
{
id: 133,
name: "Terry's Fourth Screen",
comments: [
{
id: 142,
name: "Terry's Third Comment"
}
]
}
]
},
{
id: 121,
name: "Terry's Second Project",
screens: []
},
{
id: 122,
name: "Terry's Third Project",
screens: [
{
id: 134,
name: "Terry's Fifth Screen",
comments: [
{
id: 143,
name: "Terry's Fourth Comment"
}
]
}
]
}
]
},
{
id: 2,
name: "Arnold",
projects: [
{
id: 22,
name: "Arnold's Project",
screens: [
{
id: 23,
name: "Arnold's Screen",
comments: [
{
id: 24,
name: "Arnold's Comment"
}
]
},
{
id: 231,
name: "Arnold's Second Screen",
comments: []
},
{
id: 232,
name: "Arnold's Third Screen",
comments: [
{
id: 241,
name: "Arnold's Second Comment"
}
]
}
]
}
]
}
];
</cfscript>
As you can see, I have two users - Terry and Arnold - who each have a set of Projects, Screens, and Comments, each with a "name" property that helps me make sense of the eventual output.
Here's the algorithm that I came up with - in this demo, I'm going to use an increasingly-deep set of keys. This way, you can see how the existing of a leaf-node changes the behavior of the visitor:
<cfscript>
// Gives us the "users" collection.
include "./data.cfm";
// Traverse all of the leaf-nodes in "users".
deepEach(
users,
[],
( user ) => {
echo( "#user.name#" );
echo( "<br />" );
}
);
echo( "<br />" );
// Traverse all of the leaf-nodes in "users.projects".
deepEach(
users,
[ "projects" ],
( user, project ) => {
echo( "#user.name# -- #project.name#" );
echo( "<br />" );
}
);
echo( "<br />" );
// Traverse all of the leaf-nodes in "users.projects.screens".
deepEach(
users,
[ "projects", "screens" ],
( user, project, screen ) => {
echo( "#user.name# -- #project.name# -- #screen.name#" );
echo( "<br />" );
}
);
echo( "<br />" );
// Traverse all of the leaf-nodes in "users.projects.screens.comments".
deepEach(
users,
[ "projects", "screens", "comments" ],
( user, project, screen, comment ) => {
echo( "#user.name# -- #project.name# -- #screen.name# -- #comment.name#" );
echo( "<br />" );
}
);
// ------------------------------------------------------------------------------- //
// ------------------------------------------------------------------------------- //
/**
* I traverse the given object graph, staring at the root and walking down the given
* set of keys (object properties). The operator is invoked for every DEEP LEAF-NODE
* that is discovered during the traversal.
*
* @root I am the root collection being traversed.
* @keys I am the set of keys to traverse.
* @operator I am the operator to be invoked with the collection of ancestors.
*/
public array function deepEach(
required array root,
required array keys,
required function operator
) {
// In order to traverse an arbitrarily deep object graph, we're going to use a
// mutable stack to keep track of where we are without having to use recursion.
// As new collections are discovered, they are prepending to the front of the
// stack, along with the set (operator arguments) of ancestors that will be used
// to invoke the operator once we hit a "leaf node".
var stack = [
{
collection: [].merge( root ),
keys: [].merge( keys ),
operatorArguments: []
}
];
// Keep traversing the object graph while we have items on the stack.
while ( ! stack.isEmpty() ) {
var stackItem = stack[ 1 ];
var collection = stackItem.collection;
// If the stack item has an empty collection, the stack item has been fully
// traversed - let's remove it from the stack and continue on to the next
// pending item.
if ( collection.isEmpty() ) {
stack.deleteAt( 1 );
continue;
}
// At this point, we know that we have a node to visit within the stack
// collection. This node will be the next INVOKE ARGUMENT for our operator.
// Let's shift it off the collection and keep track of it for our subsequent
// invocations.
var nextNode = collection[ 1 ];
var nextArguments = stackItem.operatorArguments.merge( [ nextNode ] );
// Shift it off.
collection.deleteAt( 1 );
// If the stack item has no more keys to visit, then we are at a LEAF NODE.
// Which means, we now have all the arguments we need for our OPERATOR.
if ( stackItem.keys.isEmpty() ) {
operator( argumentCollection = nextArguments );
continue;
}
// At this point, we know that we have more keys to visit in this object-
// branch; which means, we aren't at a leaf node yet. Let's prepend an item
// to the stack and continue on with our DEPTH-FIRST traversal.
var tempKeys = stackItem.keys.slice( 1 );
var nextKey = tempKeys[ 1 ];
var nextKeys = tempKeys.deleteAt( 1 );
var nextCollection = [].merge( nextNode[ nextKey ] );
stack.prepend({
collection: nextCollection,
keys: nextKeys,
operatorArguments: nextArguments
});
}
return( root );
}
</cfscript>
As we visit each node within the object graph, we keep prepending items to the stack. And, as we move deeper into the graph, we keep a running aggregation of the ancestor nodes that will be used to invoke the operator (visitor function). Now, if we run this ColdFusion code in Lucee CFML, we get the following output:
As you can see, as we provide more "keys" in the deepEach() call, our visitor function is invoked on more nodes. However, also notice that our visitor function is only invoked when the entire key-chain can be found. Meaning, we never call the visitor function with null arguments.
Anyway, just a fun little code kata to kick off my Friday. I haven't blogged as much because I've been quite stressed. So, this is just me trying to kick-start my creative engine.
Want to use code from this post? Check out the license.
Reader Comments