Posts Tagged ‘tree’
Tree Rendering in Client-Side, No Recursion
Monday, February 7th, 2011I once built a nested message board (using ASP & VBScript, bah). In order to print all messages, nested, I created a recursive function that queries the DB for all messages of a certain parent, prints the messages and calls the same function itself with parent ID of the current message. That was a disaster to the server, as a single page could execute about 100 queries.
I decided to move the rendering logic to the client side, since SEO wasn’t such a big of a deal for this, and the load time was critical. So at first I queried the messages I wanted (I could do this in one query thanks to the DB structure), I pushed the data to JavaScript, as a flat, unordered array of objects, using JSON:
var treeData=[
{ "id":1, "parentId":null, "title":"1" },
{ "id":2, "parentId":1, "title":"1.1" },
{ "id":3, "parentId":null, "title":"2" },
{ "id":4, "parentId":1, "title":"1.2" },
{ "id":5, "parentId":1, "title":"1.3" },
{ "id":6, "parentId":4, "title":"1.2.1" },
{ "id":7, "parentId":4, "title":"1.2.2" },
{ "id":8, "parentId":4, "title":"1.2.3" },
{ "id":9, "parentId":null, "title":"3" },
{ "id":10, "parentId":9, "title":"3.1" },
{ "id":11, "parentId":10, "title":"3.1.1" },
{ "id":12, "parentId":11, "title":"3.1.1.1" },
{ "id":13, "parentId":11, "title":"3.1.1.2" },
{ "id":14, "parentId":11, "title":"3.1.1.3" },
{ "id":15, "parentId":13, "title":"3.1.1.2.1" }
];
The first approach to print this, nested, is using a recursive function in JavaScript, that, on every call needs to find the child messages based on their parentId, and actually mimic the server behavior (loop on root messages, query child messages, print, recursively).
But a way cooler approach, is to utilize the DOM itself for nesting, and to utilize a hash table indexer to store and find messages based on their id.
After creating all elements for all messages, a hash table (associative array, or just a JavaScript “object”) can be used to store a node based on its id, so when we want to find it, we can just use nodesById[someNodeId]:
var nodesById={};
for (var i=0;i<nodeCollection.length;i++) {
nodesById[nodeCollection[i].data.id]=nodeCollection[i];
}
Then, the magic of having all elements nested happens when looping on all nodes. Each node has a parent_id except root nodes. We need to find the parent of current node in the nodesById object, by using nodesById[nodeParentId], and append the current node to its parent we found. Root nodes appended to a root container.
for (var i=0;i<nodeCollection.length;i++) {
var node=nodeCollection[i];
var parentElement=node.data.parentId ? nodesById[node.data.parentId].getChildrenElement() : rootNodeItemsContainer;
parentElement.appendChild(node.element);
}
That way, we utilize the DOM for native nesting, without a recursion, and a simple single loop. The array doesn’t even have to be ordered, and no worries about requesting a node when its parent isn’t exist, as all of the elements are already created before.
The Entire Code
Inline Recursion in ASP.NET Template to Print a Tree’s Node List
Tuesday, September 14th, 2010Here’s a neat & clean way to perform a recursion in ASP.NET, inside the .aspx/.ascx file. Suitable for ASP.NET MVC as well as WebForms.
No <asp:Repeater> + OnItemDataBound event, TreeView or concatenating strings recursively in the code behind involved.
Data Structure and Recursive Data Sample
public class NodeList : List<Node> {
}
public class Node {
public string Name { get; set; }
public NodeList Children { get; set; }
}
public class Repository {
public static NodeList GetNodes() {
return new NodeList {
new Node { Name = "1",
Children = new NodeList {
new Node { Name = "1.1" },
new Node { Name = "1.2",
Children = new NodeList {
new Node { Name = "1.2.1" }
}
},
new Node { Name = "1.3" },
new Node { Name = "1.4" },
}
},
new Node { Name = "2",
Children = new NodeList {
new Node { Name = "2.1" }
}
},
new Node { Name = "3" }
};
}
}
The Recursive Function
<%
Action<NodeList, int> printNodesRecursively = null;
printNodesRecursively = (NodeList nodeList, int depth) => {
if (nodeList==null || nodeList.Count==0) return;
%>
<ul class="node-list depth-<%=depth%>">
<%
foreach (Node node in nodeList) {
%>
<li>
<%=node.Name%>
<%printNodesRecursively(node.Children, depth + 1);%>
</li>
<%
}
%>
</ul>
<%
};
NodeList nodes = Repository.GetNodes(); // Or ViewData use for ASP.NET MVC
printNodesRecursively(nodes, 0);
%>
Notice: The printNodesRecursively function is declared with the value of null at first. Otherwise, the compiler says that the inner printNodesRecursively call is made on an unassigned variable.
This will basically print a <ul> with an <li> for each node, and inside each <li>, another <ul> with its children, recursively.
Notice the extra “depth” which indicates the current depth level in the tree inside the printNodesRecursively function. In this example it adds a special class to each level.
The Output
<ul class="node-list depth-0"> <li>1 <ul class="node-list depth-1"> <li>1.1</li> <li>1.2 <ul class="node-list depth-2"> <li>1.2.1</li> </ul> </li> <li>1.3</li> <li>1.4</li> </ul> </li> <li>2 <ul class="node-list depth-1"> <li>2.1</li> </ul> </li> <li>3</li> </ul>
(Code re-indented manually :) )