Nested Set Trees in ColdFusion (v0.2)
[This is an updated version of a previous entry on Nested Set Trees in ColdFusion.]
A common technique to manage hierarchical data in a relational database is to use an "Adjacency List" model, where you have both an ID column and a Parent ID column in a table. This is easy to understand and maintain but can be difficult or inefficient when you want to retrieve hierarchies of records.
The "Nested Set" model provides an alternative technique for managing this kind of data and is more efficient at reading a hierarchy but requires a little more work for inserts, updates, deletes and moves.
See the references below for some good links that describe the Nested Set model in more detail (or just try a search in Google).
This entry provides a library of ColdFusion code that you may like to use to help manage your hierarchical data using the nested set model.
About the Code
This code is based on a PHP/mysql implementation by Rolf Brugger (thanks Rolf!), so have a quick read through that page before getting started.
This code is also based around creating an additional "partner" table that is used with an existing data table.
The library should work in ColdFusion 6.1 and above and any common database but I have only tested in MS SQL Server.
Download the Code
You can download this code from RIAForge
This download file contains:
- /nstree - Directory containing a sample application
- /nstree/com/nstree/NestedSetTree.cfc - The base NST function library
- /nstree/com/nstree/ThreadSafeNestedSetTree.cfc - A thread safe version of the base function library
Getting Started
To get started, you will need to have a primary data table and a partner Nested Set Tree (NST) table. For this entry we will create a hierarchical set of categories.
The primary data table has the following structure:
Table: category
| Column Name | Column Type | Description |
| categoryId | int, PK | Unique primary key |
| parentCategoryId | int | Reference to parent category record |
| categoryName | varchar(50) | Category name |
Note that the parentCategoryId column is not required to use the NST library, but can be useful to maintain.
For each record in the primary category table you will need to maintain a partner record in a NST table. For convention the partner table will the same name as the primary table but with an "NST" suffix.
Table: categoryNST
| Column Name | Column Type | Description |
| categoryId | int, PK | Unique primary key |
| lft | int | Left index |
| rgt | int | Right index |
About Locking and Exceptions
All of the operations in the library need locking applied to prevent corruption of the partner table data. The ThreadSafeNestedSetTree.cfc component provides the locking required to ensure the partner table does not become corrupted in a multithreaded/multiuser environment. The NestedSetTree.cfc has no locking applied.
You will need to consider locking issues in your own code that manages the primary data table. The examples that follow will show how you might implement this.
The ThreadSafeNestedSetTree.cfc performs additional queries to ensure that operations are valid (such as checking a parent node exists before attempting to append children to it). Exceptions will be thrown if these preconditions are not met.
(Thanks Adam Cameron for raising this issue!)
Implementing Locking
The ThreadSafeNestedSetTree.cfc contains four lock related functions:
setLockName(name)
getLockName()
setLockTimeout(seconds)
getLockTimeout()
You can use these functions to set or retrieve the lock name and timeout being used by the library.
Generally, functions that read data use a READONLY lock. Functions that change data use an EXCLUSIVE lock.
In your code, you can use locking as follows.
name="#variables.nst.getLockName()#"
timeout="#variables.nst.getLockTimeout()#"
type="exclusive">
<!--- Your code plus calls to the library here --->
</cflock>
The default lock name is "NESTEDSETTREE-NSTTableName".
About Transactions
No transactions are implemented within the library. You should implement transactions in the code that uses the library.
Creating the NST library object
The library requires the following parameters when created:
| Parameter | Description |
| datasourceName | The datasource name |
| datasourceUsername | The datasource user name |
| datasourcePassword | The datasource password |
| table | The name of the NST table |
| id | The name of the NST table Id column |
| left | The name of the NST table left column |
| right | The name of the NST table right column |
Example of creating the library object:
"nstree",
"nstreeuser",
"nstreepass"
"categoryNST",
"categoryId",
"lft",
"rgt"
)>
These examples will use a simple private function for easy access to the library:
<cfreturn variables._nst>
</cffunction>
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 current records in your data table, 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 newRoot() function
| Function | Description |
| newRoot(id) | Creates a new root node. |
Example code:
<cftry>
<cftransaction>
<!--- Create the category record. --->
<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>
<!--- Update the NST. --->
nst().newRoot(categoryId)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>
Retrieving nodes from the tree
You can retrieve nodes using the following functions.
| Function | Description |
| root() | Returns the root node. |
| 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. |
These functions always return a node. When you have the result node, you should test if the node is valid.
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.
| Function | Description |
| isValidNode(node) | Returns true if the node is valid. |
Querying for nodes in the tree
The following functions return a true or false value:
| 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. |
Adding new nodes
The following functions are provided to add nodes to a tree.
| 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. |
Example code to add new children
<cftry>
<cftransaction>
<!--- Create the category record. --->
<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>
<!--- Update the NST. --->
<cfset nst().newLastChild(parentCategoryId, categoryId)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>
Deleting nodes
The NST library provides two delete functions
| Function | Description |
| delete(node) | Deletes the specified node. |
| deleteTree() | Deletes all nodes in the tree. |
Example code to delete a node:
<cftry>
<cftransaction>
<!--- Get the node to delete --->
<cfset node = nst().getNode(categoryId)>
<!--- Delete the category and all children. --->
<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.l#">
and
nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.r#">
</cfquery>
<!--- Then delete the NST record. --->
<cfset nst().delete(categoryId)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>
Moving nodes
The following functions are available to move nodes within your tree:
| 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'. |
Note that in these examples, the order of the nodes is managed by the NST rather than the primary data table (via a 'sort' column).
Moving a node 'up'
Example code to move a node up/left within the same parent.
<cflock name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
<cfset prevNode = nst().prevSibling(categoryId)>
<cfset nst().moveToPrevSibling(categoryId,prevNode.id)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>
Moving a node 'down'
Example code to move a node down/right within the same parent.
<cflock name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
<cfset nextNode = nst().nextSibling(categoryId)>
<cfset nst().moveToNextSibling(categoryId,nextNode.id)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>
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>
<!--- Handle errors (such as the src or dst nodes not existing --->
</cfcatch>
</cftry>
<cfif not moveAllowed>
<cfreturn>
</cfif>
<cflock name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
<!--- Change the node's parent in the primary table. --->
<cfquery ...>
update category
set parentCategoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#dstId#">
where categoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#srcId#">
</cfquery>
<!--- Move the node in the NST. --->
<cfset nst().moveToLastChild(srcId,dstId)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>
Querying the data
The library provides some functions to query the NST table:
| Function | Description |
| numChildren(node) | Returns a recursive 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. |
However, these functions are typically not very useful on their own as they do not provide data from the primary table.
A better technique is to understand how the NST model works and take advantage of this fact in your queries.
Getting the complete tree hierarchy
The 'left' column in the NST provides all we need to get a complete hierarchy of the tree.
<cfquery name="q" ...>
select
d.*,
nst.lft,
nst.rgt
from
category d
inner join categoryNST nst on d.categoryId = nst.categoryId
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.
<!--- Get the node. --->
<cfset node = nst().getNode(categoryId)>
<!--- Get the level --->
<cfquery name="q" ...>
select count(*) as level
from categoryNST
where
lft < #node.l#
and rgt > #node.r#
</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.
<cfquery name="q" ...>
select
d.*,
(
select count(*)
from categoryNST d2
where
d2.lft < nst.lft
and d2.rgt > nst.rgt
) as level,
nst.lft,
nst.rgt
from
category d
inner join categoryNST nst on d.categoryId = nst.categoryId
order by
nst.lft
</cfquery>
</cflock>
Getting a subtree with depth levels
<cfset node = nst().getNode(categoryId)>
<cfquery name="q" ...>
select
d.*,
(
select count(*)
from categoryNST d2
where
d2.lft < nst.lft
and d2.rgt > nst.rgt
) as level,
nst.lft,
nst.rgt
from
category d
inner join categoryNST nst on d.categoryId = nst.id
where
nst.lft >= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.l#">
and nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.r#">
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.
<cfquery name="q" ...>
select
c.*,
nstB.lft,
nstB.rgt
from
categoryNST nstA
cross join categoryNST nstB
inner join category c on nstB.categoryId = c.categoryId
where
nstA.lft between nstB.lft and nstB.rgt
and nstA.categoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#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 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:
<cfset nst().rebuildIndex("category","categoryId","parentCategoryId",rootNodeId)>
References
Nested Set Trees, a PHP/mysql implementation
http://www.edutech.ch/contribution/nstrees/index.php
Managing Hierarchical Data in MySQL
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
Storing Hierarchical Data in a Database
http://www.sitepoint.com/article/hierarchical-data-database
Using the Nested Set Data Model for Breadcrumb Links
http://www.developer.com/db/article.php/3517366
A Look at SQL Trees (Joe Celko)
http://www.dbmsmag.com/9603d06.html
category & categorynst?
For example, inserting records would become more complicated and less generic with one table. If you wanted to have "soft" deletes in your application, then the primary table could flag records as deleted, but the partner NST table could have actual deletes.
To get the best performance, a single table (with stored procedures for the NST insert/update operations) would perhaps be the best way to go, but separating out the NST table provides a bit more flexibility.
Been working it with OpenBD/MySQL. Had to do a few mods but it seems to be working so far with the exception of the following:
- Initial Create Node Fails to update the NST table, so I had to manually enter the 1st rgt / lft data. It worked fine after that (to create nodes in the proper hierarchy.)
- IDENTITYCOL (MS SQLServer) / GENERATED_KEY (MySQL) is not passed from OpenBD (for inserts) so I had to add the following to the createCategory Method within the cftransaction tags:
<cfquery name="q" datasource="#getDatasource().getName()#" username="#getDatasource().getUsername()#" password="#getDatasource().getPassword()#">
select max(categoryId) as IDENTITYCOL
from category
</cfquery>
Note: You could probably also do a switch/case to identify the database to dynamically determine they return variable as in: IDENTITYCOL (MS SQLServer) / GENERATED_KEY (MySQL) / Etc.
-The "Move To" dropdowns did not execute any action (could be work in progress...)
- Here are the tables for MySQL:
----------------------------------------------------------------------
CREATE TABLE `spifo`.`category` (
`categoryid` int(11) NOT NULL AUTO_INCREMENT,
`categoryName` varchar(50) DEFAULT NULL,
`parentCategoryId` int(10) unsigned DEFAULT NULL,
PRIMARY KEY (`categoryid`)
) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=utf8 ROW_FORMAT=COMPACT;
CREATE TABLE `spifo`.`categorynst` (
`categoryid` int(11) DEFAULT NULL,
`lft` int(11) DEFAULT NULL,
`rgt` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8 ROW_FORMAT=COMPACT;
----------------------------------------------------------------------
Remove the `spifo` from both create statements:
CREATE TABLE `spifo`.`categorynst`
Thanks.
Was it the creation of the root node that failed? I will see if I can set up the same environment and test.
The "Move To" code is dependent on jQuery adding an onchange event to each of the drop downs. Perhaps this did not work?
Thanks for the excellent feedback.
A. Yes
Q. The "Move To" code is dependent on jQuery adding an onchange event to each of the drop downs. Perhaps this did not work?
A. Got it to work! - I just had to modify it based on where I had it in the directory structure.
"Delete" is the only thing not working for me now...
Initially trying to troubleshoot why some things were not working, it became more of a challenge because of the try/catch statements. The catch statement was empty shielding the cf error from displaying to the browser - the click would just do nothing but return to the originating page. It would be nice to have a variable: isDebugMode = True|False; during the pre 1.0 version (maybe even in post 1.0 versions.)
* Fix creation of root node in demo app
Old code had a line:
nst().newRoot(cat.categoryId)>
New code changed this to:
<cfset nst().newRoot(cat.categoryId)>
Interesting that I did not get a CF error for this.
* Remove cftry/cfcatch from demo app.
These are not required for a single user demo. I may put them back in again later, but they should only catch the specific errors being thrown by the demo app rather than every error.
* Added mysql script to create demo tables.
Noticed a small issue from my original code (just for consistency:)
CHANGE:
`parentCategoryId` int(10) unsigned DEFAULT NULL,
TO:
`parentCategoryId` int(11) DEFAULT NULL,
in the MySQL Script. All the other INTs are 11 as well.
Great Job!
Thanks
Change:
delete category...
To:
delete from category...
Hi Mark, I have not tried the library with ExtJS yet, but from what I can see it should work fine.
The default lock name is changed from being a UUID to be based on the NST table name instead. The lock name is now the NST table name prefixed with "NESTEDSETTREE-".
This will provide safer usage if the library is not loaded in the application scope and no specific lock name is set.
Current:
.init("datasource","username","password","table","id","left","right")
.init("datasource","table","id")
Username and password are redundant if they are saved in the datasource setup, but obviously necessary if they are not.
Left and right could default to "lft" and "rgt" as stated in all of the documentation, and be overriden if needed. (I guess ID could have a default as well.)
Overall, it's been eally great to work with this CFC! Nested set trees are useful, but challenging to work with. This makes it really easy! :-)
.init("datasource","table","id","username","password","lft","rgt")
An alternative would be to require named parameters, then the order is unimportant:
.init(datasourceName="datasource",table="table",id="id")
But this seems to defeat the purpose of having a more succinct initialisation.
So I'm still considering how the initialisation is done, but it is good to have another perspective, thanks.
I thought about the named parameters too, but I came to the same conclusion as you.
Just throwing this all out there to ponder, overall I'm very pleased with how it's working! It's a very understandable implementation of Nested Set Trees. It's working great in static CFM pages. My next challenge is to see if I can get it to work with a Javascript tree control. (preferably a JQuery tree, but any would be a good step forward).
Thanks for your work on this project!
Dan
Vancouver, WA
I also need to use the NST query result to generate an unordered list.
I have update this post to include a section "Rendering nested set output as an unordered list".
I have also updated RIAForge (http://nstree.riaforge.org/) with a new version (v0.2.4) that includes a simple jquery treeview example as part of the demo.
I love your work and greatly appreciate the tremendous effort. This will save me loads of time.
I have a question concerning the possibility of multiple root nodes. I have a table called "catalog" and I've added a "catalogID" to the the "category" table. I basically want to have multiple collections of "tree roots". That way I can implement as many trees as I like with distinct features Whereby I can set the Maximum Category Levels per tree or select which View Template displays a particular category collection. Would implementing this cause problems? How much customization do you foresee is necessary for the core components? In my mind I know how I would normally handle this but I am concern about the left and right index values being corrupted.
Thanks,
Hussein
Yes, using a nested set tree model you are limited to a single root node per table (otherwise the left/right values from each separate tree will interfere with each other).
For your situation, perhaps you could still have a single top level root category node, but all of it's immediate child nodes are your "virtual" root nodes. You would then associate your distinct features against each virtual root node.
Thanks for the response. So basically what you are suggesting is that I make all my level 1 category nodes a catalog container. Right? If so I think this makes sense. This simplifies a lot of things; however I still need all the children of each catalog to know which catalog they belong to. Any suggestions would be appreciated.
How do I reference the Catalog/Virtual Root Node? Is it by ID or could It be referenced by a unique name? In my gateway component I could have a function called getCatalogByName() or getCatalogByID(). Can I achieve this with your NSTree component? I assume so. What would be the best approach? I am still learning to use your component so please bear with me a little. I promise I won’t ask so many questions after this. :)
Thanks,
Hussein
The best way to organise this (as I understand what you need) would be to have two tables:
- catalog
- catalogNST
The catalogNST table just has a catalogId, lft and rgt columns. This table is managed by the library.
The catalog table has catalogId, parentCatalogId, catalogName, plus any other fields you need.
To know which catalog container a child belongs to could be worked out with a query, but it might be easier to just keep a reference to the container catalog in every node. So add a containerCatalogId to the catalog table. So whenever you add a new catalog child record, you need to know in advance which container catalog it belongs to.
Your gateway functions getCatalogById() and getCatalogByName() would work very well. In both cases you would need to do a query that performs an inner join on your catalog and catalogNST tables, then has an appropriate where clause to get the records you need.
Hope that helps. Feel free to ask as many questions as you like!
This helps big time. Thanks for clearing up a few things in my mind. Very much appreciated.
Hussein
I have a small suggestion for true multiple and independent tree nodes. Consider creating a table called CategoryTree comprising of the following fields: CategoryTreeID, CategoryTreeName. Assign the "CategoryTreeID" as a foreign key to both Category and CategoryNST. When you do the regeneration of the CategoryNST values, let it filter in the where clause by CategoryTreeID and that I think should prevent the entire category structure from being recalculated, which to me would be an extra performance gain especially in large collections.
The plus with this is that you are allowed to have several applications using the same table, however only the respective root tree node would be visible to a particular app. Maybe a function like getTreeByID(1) or getTreeByName(‘products’) could do the trick.
In essence, if you are editing the “products” tree root, you still have all the same functions to move up or down tree branches and siblings. The only difference from what little I can interpret would be to include the CategoryTreeID in the where clause to ensure that other roots aren’t affected. This is just an idea that I’m throwing out there.
Thanks,
Hussein
I'm also doing a flex version of the NSTree UI using the AdvanceDataGrid, I have most of the functions working nicely. The only tough part left is the MoveTo feature. I thought this would have been easy but working with Hierarchical data in flex isn't always smooth sailing if ever (considering I am no flex guru). I will post an example when I've made some progress for some feedback, but in the meantime I would love some advice about the bug I am experiencing.
Thanks
Hussein
Great idea for supporting multiple trees within the same table, adding a "treeId" type column may work well. I have put some thought into this - couple of things to think through:
1. Needing to pass a new treeId parameter for each call, not sure I want this as base functionality. This would be worthwhile if multiple tree support in a single table was a common requirement/preference.
3. Possibly move to a more OO style to get around this (where each node is a real object rather than a struct). This would be very nice to use, but what would be the performance impact? Would possibly need to look into caching. May be a bit of work.
3. Locking should be fine as we could use named CF locks for each tree.
4. Need an index on the treeId column - easy to include as part of the NST db script.
Just a note that I don't see there being any performance gain in moving to this strategy as the number of records modified in each update would remain the same (just limited to the specific tree).
Thanks for the suggestion.
Kevan
What do you see in the select list? Is the list empty or are all nodes present, but just greyed out?
Looking forward to seeing your Flex app!
Demo changed so that it runs in a subdirectory or root directory.
(Dan, thanks for the suggestion)
Thanks for the feedback.
Re: MoveTo List
Yes the options are grayed out.
Re: Multiple Trees
On point one (1) I was thinking of passing the treeid on the init() method of the gateway that handles the tree functions. E.G.: ProductGateway could be extended with the CategoryGateway.
Re: Performance
If I created four virtual parent category groups in the current system and each group had an average of 200 sub categories, wouldn't all the left and right indexes for the entire tree be rebuilt every time you moved a single item?
If that is not true, my understanding of the inner workings of NSTree is somewhat flawed.
If this is true however, the performance improvement would be that the entire tree is not rebuilt, only the tree that the change was made on. This is more from an administrative point of view, but then this brings up the argument of one table vs multiple tables design. For something like categories I personally prefer one table to copy the data I need and cache it for data presentation usages. Where as others might prefer a different approach like using a different table for each category implementation.
Sorry, but I don't want to take up anymore of your time with this. Thanks for listening and I think your NSTree implementation is still awesome just the way it is.
Thanks Again,
Hussein
Found the problem, it is related to how CF7 handles nested loops differently to CF8. I will upload a fix shortly.
Short story is that subtree.lft and subtree.rgt need to be set to variables in the outer loop (say subtreeLft and subtreeRgt), and these variables should be referenced in the inner loop.
Re: Multiple Trees
Yes the treeId could be in the gateway, but imagine it would be provided by the NST library in some way. i.e. You would ask the NST library to create a new tree and it would return an id for that tree. I will put some more thought into this, but I am liking the idea quite a lot at this point.
Re: Performance
Hussein, you are absolutely correct! There would certainly be a performance gain using real multiple trees within one table compared to simulating multiple trees using the current library. I should remember to think before typing :)
Kevan
Fixed a CF7 bug in the demo for the "move to" drop down.
Change mssql demo script to work on MSSQL 2000 as well as MSSQL 2005.
http://nstree.riaforge.org/
Thanks for highlighting this - I completely overlooked the delete.
The can be handled as follows:
1) Get the node to delete from the NST
<cfset node = nst().getNode(arguments.categoryId)>
2) Delete the main table records (main record plus all children)
<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.l#">
and nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.r#">
</cfquery>
3) Delete the NST record
<cfset nst().delete(node)>
This should work in MSSQL but not sure about MySQL or others.
I will also amend the examples and demo.
Thanks!
Fixed delete node bug in the demo app.
http://nstree.riaforge.org/
Two: I want optional values, even if that means the extreme concept of building my own CFC handler. (Sure would prefer a community project though... but this is in Beta, not a gold release so doing something like that and moving to say .3 version with a warning seems appropriate.)
Three: I am looking at doing a forum app, that will have categories, and threads. Each time a post is made in one forum category it seems odd to reindex all the threads in other categories. I would like the thread table to include a "branch" ID... to allow the same table to be used more dynamically for this kind of thing.
I am using MySql but it looks fine to me. If I encounter any problems I will let you know.
On an aesthetic note for the "getNode()" properties, I think it would be cleaner to state the full name of the property versus the one letter thingy.
"node.l" vs node.left
or
node.leftIndex
or maybe
node.indexLeft
I know it is more typing but it immediately says to me what it represents.
I hope you don't think I am nitpicking :)
I just generally stay away from shorten or abbreviated terms with variables.
Thanks again,
Hussein
I got around this in flex easily since I had to convert the raw query into a hierarchical array before passing it to Flex anyway; I then set isFirst:boolean, isLast:boolean and indexPosition:Numeric properties for each child within its parent. The same could be done here too unless you have some really slick way of getting around this. Would love to see! :)
Re: Optional values
Can you expand on your idea here? Where would the optional values be used?
Re: Forum App
This is a great example of where multiple tree support would be required. I am looking into this as the moment.
Yes, node.left etc. is a much nicer syntax. Definitely worth reviewing.
The "move up" and "move down" error should be fixed in the current release.
To identify the first and last children of a node the first thought that comes to mind is:
firstChild.left = parentNode.left + 1
lastChild.right = parentNode.right - 1
I'll add something to the demo that uses this idea, but it requires some extra subqueries to look up the parent node details.
By optional values I mean the <cfargument> params. I realize this is a pain if someone has software already built on the platform... but having fixed required arguments for things like dbusername, dbpassword are not compliant with how most people use CF. In fact many developers don't even have access to that information! There are many shops that have coders and DBAs and hardware guys maintaining the web in three different layers. In those cases your tool is totally without use to the coders. (And occasionally some of those are my clients.)
Thanks. Since Dan's comments above I have been considering ways in which to supply default values. I am planning to make a change as follows:
Either
a) Supply all parameters implicitly:
init(dsName,dsUser,dsPass,nstTable,nstId,nstLeft,nstRight), or
b) Supply mandatory parameters explicitly:
init(datasource="dsName",nstTable="nstTable")
The parameters for the library initialisation would then be
datasourceName - required
datasourceUsername - optional, default=""
datasourcePassword - optional, default=""
nstTable - required
nstId - optional, default="id"
nstLeft - optional, default="lft"
nstRight - optional, default="rgt"
(What is the roadmap that you have set the version numbers on? Not getting to 1.0 can hurt a project very deeply.)
I have several enhancements planned but honestly had not considered a roadmap. Even though the overall scope of the project is relatively small, a roadmap may be worthwhile to at least gauge progress to 1.0.
In the meantime, some of the enhancements planned include:
* Multi-tree support
* Move to more OO style API
* General performance enhancements.
Thanks for the suggestion.
I hope you are in good shape.
I was wondering when you will be rolling out the next NSTree version with real Multi-Tree support and the likes. I am really excited about this next release as I plan on making it an integral part of most systems I build in the future.
Thanks,
Hussein
It should be ready within the next two weeks (all going well it may be ready this coming weekend).
The primary changes include multi-tree support and object nodes (rather than struct nodes) that you can use for some nicer syntax.
Rather than:
nst().newFirstChild(node,5)
you can use:
node.newFirstChild(5)
The previous syntax will continue to be available.
So, should have an update shortly!
Kevan