Nested Set Trees Objects

Nested Set Trees Objects

The NST library objects

There are three NST library objects:

NestedSetTreeTable
NestedSetTree
Node

NestedSetTreeTable

The first object you need to create is the NestedSetTreeTable object. You must create one for each table that will hold nested set data. These may be stored in the application scope.

The object requires the following parameters when created:

Parameter	Requirement	Description
datasourceName	Mandatory	The datasource name.
datasourceUsername	Optional	The datasource user name. Default is empty string.
datasourcePassword	Optional	The datasource password. Default is empty string.
table	Mandatory	The name of the NST table.
treeId	Optional	The name of the NST table Tree Id column. Default value is "treeId".
id	Optional	The name of the NST table Id column. Default value is "id".
left	Optional	The name of the NST table left column. Default value is "lft".
right	Optional	The name of the NST table right column. Default value is "rgt".

Example of creating the nested set tree table object:

Or you can use the simpler version if you use the default column names:

The NestedSetTreeTable has the following functions available:

Function	Description
getNestedSetTree(treeId)	Returns a NestedSetTree object with the specified Tree Id. The treeId parameter is optional and defaults to the value 0. You can use this value if you do not plan to use multiple trees within your table. This function does not access the database.
deleteAllTrees()	Deletes all trees from the database.

NestedSetTree

The main object you need to use is the NestedSetTree. This object contains all of the functions you need to manipulate you tree. You create NestedSetTree object from the NestedSetTreeTable:

Or if your table is only expected to contain one tree:

The following examples will use a simple private function nst() as an alias to the NestedSetTree object:

Node

The Node object is created whenever you read a record from the NestedSetTree. For example:

A Node has many functions available, the basic node oriented functions are:

Function	Description
getTree()	Returns the NestedSetTree associated with the node.
getTreeId()	Returns the Tree Id of the node.
getId()	Returns Id of the node.
getLeft()	Returns Left value of the node.
getRight()	Returns Right value of the node.
setTree(tree)	Sets the NestedSetTree of the node.
setId(id)	Sets the Id of the node.
setLeft(left)	Sets the Left value of the node.
setRight(right)	Sets the Right value of the node.
reload()	Updates the nodes left and right values from the database.
invalidate()	Sets a node's left and right values to 0 which represent an invalid node.
toStruct()	Returns a struct value containing the treeId, id, left and right values.
toStringValue()	Returns a string representation of the node using the format {treeId,nodeId,left,right}.

Creating the root node of a new tree

Nested set trees need to have a top level root node which is the parent of all other nodes. When you have no nodes in your tree, then you can use the following code to create your first record.

If you are converting an existing data table to use the NST model, then see "Creating a NST for existing data" below.

To create a new root node in the NST, use the NestedSetTree newRoot() function

Function	Description
newRoot(id)	Creates a new root node and returns a Node object.

Example code:

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftransaction>


<cfquery result="q" ... >
   insert into category
   (
      parentCategoryId,
      categoryName
   )
   values
   (
      <cfqueryparam cfsqltype="cf_sql_integer" value="0">,
      <cfqueryparam cfsqltype="cf_sql_varchar" value="#categoryName#">
   )
</cfquery>
<cfset categoryId = q.IDENTITYCOL>


nst().newRoot(categoryId)>

</cftransaction>
</cflock>

Retrieving nodes from the tree

The NestedSetTree object provides the following functions to retrieve nodes.

These functions always return a node. When you have the result node, you should test if the node is valid.

NestedSetTree Function	Description
root()	Returns the root node of the tree.
getNode(id)	Returns a node with the specified id.
firstChild(node)	Returns the first child of the specified node.
lastChild(node)	Returns the last child of the specified node.
prevSibling(node)	Returns the previous sibling of the specified node.
nextSibling(node)	Returns the next sibling of the specified node.
ancestor(node)	Returns the parent of the specified node.

The Node object has the following functions to retrieve nodes.

Node Function	Description
firstChild()	Returns the node's first child.
lastChild()	Returns the node's last child.
prevSibling()	Returns the node's previous sibling.
nextSibling()	Returns the node's next sibling.
ancestor()	Returns the node's parent.

Testing for a valid node

Use isValidNode() to test if a node is valid. An invalid node is essentially equivalent to receiving a null or undefined value.

On a NestedSetTree use:

NestedSetTree Function	Description
isValidNode(node)	Returns true if the specified node is valid.

On a Node use:

Node Function	Description
isValidNode()	Returns true if the node is valid.

Querying for nodes in the tree

The following functions return a true or false value.

For the NestedSetTree:

NestedSetTree Function	Description
hasAncestor(node)	Returns true if the node has a parent.
hasPrevSibling(node)	Returns true if the node has a previous sibling
hasNextSibling(node)	Returns true if the node has a next sibling.
hasChildren(node)	Returns true if the node has children.
isRoot(node)	Returns true if the node is a root node.
isLeaf(node)	Returns true if the node is a leaf node.
isChild(node1,node2)	Returns true, if 'node1' is a direct child or in the subtree of 'node2'
isChildOrEqual(node1,node2)	Returns true, if 'node1' is a direct child or in the subtree of 'node2' or is the same node as 'node2'
isEqual(node1,node2)	Returns true if 'node1' and 'node2' are the same node.

For the Node use:

Node Function	Description
hasAncestor()	Returns true if the node has a parent.
hasPrevSibling()	Returns true if the node has a previous sibling
hasNextSibling()	Returns true if the node has a next sibling.
hasChildren()	Returns true if the node has children.
isRoot()	Returns true if the node is a root node.
isLeaf()	Returns true if the node is a leaf node.
isChild(node)	Returns true, if the node is a direct child or in the subtree of 'node'
isChildOrEqual(node)	Returns true, if the node is a direct child or in the subtree of 'node' or is the same node as 'node'
isEqual(node)	Returns true if the node is the same as the 'node' parameter.

Adding new nodes

The following functions are provided to add nodes to a tree.

NestedSetTree Function	Description
newFirstChild(node,id)	Creates a new node before all other children.
newLastChild(node,id)	Creates a new node after all other children.
newPrevSibling(node,id)	Creates a new node before the current node.
newNextSibling(node,id)	Creates a new node after the current node.

For Node objects use:

Node Function	Description
newFirstChild(id)	Creates a new node before all other children.
newLastChild(id)	Creates a new node after all other children.
newPrevSibling(id)	Creates a new node before the current node.
newNextSibling(id)	Creates a new node after the current node.

Example code to add new children

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>


<cfquery result="q" ... >
   insert into category
   (
      parentCategoryId,
      categoryName
   )
   values
   (
      <cfqueryparam cfsqltype="cf_sql_integer" value="#parentCategoryId#">,
      <cfqueryparam cfsqltype="cf_sql_varchar" value="#categoryName#">
   )
</cfquery>
<cfset categoryId = q.IDENTITYCOL>


<cfset nst().newLastChild(parentCategoryId, categoryId)>

</cftransaction>
<cfcatch>

</cfcatch>
</cftry>
</cflock>

Deleting nodes

The NestedSetTree object provides the following delete functions:

NestedSetTree Function	Description
delete(node)	Deletes the specified node.
deleteTree()	Deletes all nodes in the tree.

The Node object provides just a single function:

Node Function	Description
delete()	Deletes the node.

Example code to delete a node:

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>


<cfset node = nst().getNode(categoryId)>


<cfquery ... >
   delete cat
   from
      category cat
      inner join categoryNST nst on cat.categoryId = nst.categoryId
   where
      nst.lft >= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.getLeft()#">
      and
      nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.getRight()#">
</cfquery>


<cfset nst().delete(categoryId)>

</cftransaction>
<cfcatch>

</cfcatch>
</cftry>
</cflock>

Moving nodes

The following functions are available to move nodes within your tree:

NestedSetTree Function	Description
moveToNextSibling(src,dst)	Moves the node 'src' and all its children (subtree) so that it is the next sibling of 'dst'.
moveToPrevSibling(src,dst)	Moves the node 'src' and all its children (subtree) so that it is the prev sibling of 'dst'.
moveToFirstChild(src,dst)	Moves the node 'src' and all its children (subtree) so that it is the first child of 'dst'.
moveToLastChild(src,dst)	Moves the node 'src' and all its children (subtree) so that it is the last child of 'dst'.

And for the Node:

Node Function	Description
moveToNextSibling(dst)	Moves the node and all its children (subtree) so that it is the next sibling of 'dst'.
moveToPrevSibling(dst)	Moves the node and all its children (subtree) so that it is the prev sibling of 'dst'.
moveToFirstChild(dst)	Moves the node and all its children (subtree) so that it is the first child of 'dst'.
moveToLastChild(dst)	Moves the node and all its children (subtree) so that it is the last child of 'dst'.

Note that in these examples, the sort order of the nodes is managed by the NST rather than the primary data table (via a 'sort' column) so we will only need to update the NST table.

Moving a node 'up'

Example code to move a node up/left within the same parent.

Moving a node 'down'

Example code to move a node down/right within the same parent.

Moving a node to another branch in the tree

Note that nodes may only be moved to either parent or sibling nodes, so we need to ensure the move is permitted.


<cfset var moveAllowed = false>
<cftry>
<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
   <cfset moveAllowed = not nst().isChildOrEqual(dstId,srcId)>
</cflock>
<cfcatch>

</cfcatch>
</cftry>

<cfif not moveAllowed>
   <cfreturn>
</cfif>

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>


<cfquery ...>
   update category
   set parentCategoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#dstId#">
   where categoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#srcId#">
</cfquery>


<cfset nst().moveToLastChild(srcId,dstId)>

</cftransaction>
<cfcatch>

</cfcatch>
</cftry>
</cflock>

Querying the data

The library provides some functions to query the NST table:

NestedSetTree Function	Description
numChildren(node)	Returns a count of all children in the subtree of the node.
level(node)	Returns the node depth level, with the root level starting at 0.
getSubtree(node)	Returns the complete subtree of the specified node.
walkPreorder()	Returns the complete tree hierarchy.

And for the Node:

Node Function	Description
numChildren()	Returns a count of all children in the subtree of the node.
level()	Returns the node depth level, with the root level starting at 0.
getSubtree()	Returns the complete subtree of the specified node.

However, when querying the data you mostly want to also obtain data from your primary table:

Getting the complete tree hierarchy

The 'left' column in the NST provides all we need to get a complete hierarchy of the tree.

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfquery name="q" ...>
   select
      c.*,
      nst.lft,
      nst.rgt
   from
      category c
      inner join categoryNST nst on c.categoryId = nst.id
   order by
      nst.lft
</cfquery>
</cflock>

It is often useful to get the depth level of the nodes at the same time.

Getting the level of a node

First let's look at getting the depth of a single node.

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">


<cfset node = nst().getNode(categoryId)>


<cfquery name="q" ...>
   select count(*) as level
   from categoryNST
   where
      lft < #node.getLeft()#
      and rgt > #node.getRight()#
</cfquery>

</cflock>

<cfreturn q.level>

Getting the complete tree hierarchy with depth levels

Now we can combine the complete tree hierarchy and level queries together. The level query is included as a subquery.

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfquery name="q" ...>
   select
      c.*,
      (
         select count(*)
         from categoryNST c2
         where
            c2.lft < nst.lft
            and c2.rgt > nst.rgt
      ) as level,
      nst.lft,
      nst.rgt
   from
      category c
      inner join categoryNST nst on c.categoryId = nst.id
   order by
      nst.lft
</cfquery>
</cflock>

Getting a subtree with depth levels

If you only need to get a subtree (rather than the complete tree) with levels, then you may use code such as:

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfset node = nst().getNode(categoryId)>
<cfquery name="q" ...>
   select
      c.*,
      (
         select count(*)
         from categoryNST c2
         where
            c2.lft < nst.lft
            and c2.rgt > nst.rgt
      ) as level,
      nst.lft,
      nst.rgt
   from
      category c
      inner join categoryNST nst on c.categoryId = nst.id
   where
      nst.lft >= #node.getLeft()#
      and nst.rgt <= #node.getRight()#
   order by
      nst.lft
</cfquery>
</cflock>

Getting a breadcrumb record set

Use the following to get a query of the breadcrumb links for a node.

<cflock   name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfquery name="q" ...>
   select
      c.*,
      nstB.lft,
      nstB.rgt
   from
      categoryNST nstA
      cross join categoryNST nstB
      inner join category c on nstB.id = c.categoryId
   where
      nstA.lft between nstB.lft and nstB.rgt
      and nstA.id = #categoryId#
   order by
      nstB.lft
</cfquery>
</cflock>

Rendering nested set output as an unordered list

You can display a nested set query's output as nested unordered lists using the following code.

First you would need to execute a query that returned either the entire tree or a subtree plus corresponding depth levels (as described above).

In this example, the "treeQuery" query contains a "level" column and a "categoryName" column.

<cfset prevLevel = -1>
<cfset currLevel = -1>
<cfloop query="treeQuery">
   <cfset currLevel = level>
   <cfif currLevel gt prevLevel>
      <ul><li>#categoryName#
   <cfelseif currLevel lt prevLevel>
      <cfset tmp = prevLevel>
      <cfloop condition="tmp gt currLevel">

         </li></ul>
         <cfset tmp = tmp - 1>
      </cfloop>
      </li><li>#categoryName#
   <cfelse>
      </li><li>#categoryName#
   </cfif>
   <cfset prevLevel = level>
</cfloop>
<cfset tmp = currLevel>
<cfloop condition="tmp ge 0">
   </li></ul>
   <cfset tmp = tmp - 1>
</cfloop>

Creating a NST for existing data

If you have existing data that you want to convert to use the NST model, then the library provides a rebuildIndex() function to help you with this conversion:

This function has four parameters:

Parameter	Description
primaryTable	The name of your primary table
primaryTableId	The name of your primary table's primary key column (integer only)
primaryTableParentId	The name of your primary table's parent id column (integer only)
rootId	The id of the root record in your primary table. This is the start record for the conversion.

When run, all records in the NST table will be deleted and recreated.

Example usage: