Reordering nested sets using PHP and Javascript
The adjancency method
Representing a tree of nodes, for example product categories, in a relational database is not hard. The most common way of doing it is to store a parentid with each node. This is also known as the adjacency list model. It is sometimes also referred to as the recursive model. Whatever the name it is easy to grasp. It is very simple to insert and move nodes around but it is not an optimal solution if you often select the whole tree from the database for displaying on a web page as you need to recursively select all children of nodes.
The nested set model
A much better solution is the nested set model. In this model trees are represented as nested sets. Instead of using a parentid you have a left and right value for each node expressing the relationship to other nodes. A tree of nodes can look like this.
34 | +--36 | | | +--46 | | | +--47 | +--38 | +--39
The same data can be viewed more graphically as nested sets. This is also the way they are stored in the database. Notice how the left and right values are numbered in order from the outermost left to the outermost right.
id:34 +----------------------------------------------------+ | id:36 id:38 | | +------------------------+ +--------------+ | | | id:46 id:47 | | id:39 | | | | +-----+ +-----+ | | +------+ | | 1| 2| 3| |4 5| |6 |7 8| 9| |10 |11 |12 | | +-----+ +-----+ | | +------+ | | | +------------------------+ +--------------+ | +----------------------------------------------------+
In the database this is stored as in the following table.
+----+-----+-----+ | id | lft | rgt | +----+-----+-----+ | 34 | 1 | 12 | | 36 | 2 | 7 | | 46 | 3 | 4 | | 47 | 5 | 6 | | 38 | 8 | 11 | | 39 | 9 | 10 | +----+-----+-----+
This allow you to select the full tree with only one select statement. Normally you select the full list of nodes including the depth of each node as shown below in the small table containing id and depth. It is then easy to loop over the data in PHP to produce a nice tree in HTML/CSS.
The data below can be displayed as the the tree on right. The depth is in parenthesis.
+----+-------+ 34 (0) | id | depth | | +----+-------+ +--36 (1) | 34 | 0 | | | | 36 | 1 | | +--46 (2) | 46 | 2 | | | | 47 | 2 | | +--47 (2) | 38 | 1 | | | 39 | 2 | +--38 (1) +----+-------+ | +--39 (2)
Here is a more thorough article on how you use MySQL with nested sets.
On to the problem
Last night I was working on an application that display a full tree where the user must be able to to drag and drop nodes to reorder the tree. The problem is that it is much more difficult to insert or reorder the tree using the nested set model.
For the actual html I produced nested ordered lists using the OL and LI html element so that it was easy to use with the excellent MooTree script based on MooTools. (It does seem to have trouble with the latest version of MooTools though.) After reordering the structure it was easy to extract the tree list including the depth of each node. I sent this to the PHP backend to be handled there. The text data I sent to the PHP backend then look like below.
34,0 36,1 46,2 47,2 38,1 39,2
As you can see it looks exactly like the data I selected from the database previously. So I had to create a function in PHP that took this indata and produced a list of nodes with the correct left and right values. This list is then looped over to update all the nodes in the database.
function depth2nestedset($data)
{
$lines = explode("\n", $data);
$rows = array();
$stack = array();
$lft = 0; // Left value
$rgt = 0; // Right value
$plvl = -1; // Previous node level
foreach($lines as $line) {
list($id, $lvl) = explode(',', $line);
// Skip empty/faulty lines
if (trim($id) == '') {
continue();
}
if ($lvl > $plvl) {
$lft++;
$rgt = 0;
array_push($stack, $id);
}
else if ($lvl == $plvl) {
$pid = array_pop($stack);
$rows[$pid][2] = $rows[$pid][1] + 1;
$lft = $lft + 2;
$rgt = 0;
array_push($stack, $id);
}
else {
$lft = $lft + ($plvl - $lvl) + 2;
$diff = $plvl - $lvl + 1;
for($n = 0; $n < $diff; $n++) {
$pid = array_pop($stack);
$rows[$pid][2] = $lft - $diff + $n;
}
array_push($stack, $id);
}
$rows[$id] = array($id, $lft, $rgt);
$plvl = $lvl;
}
$plvl++;
$cnt = count($rows) * 2;
$leftovers = count($stack);
for($n = 0; $n < $leftovers; $n++) {
$pid = array_pop($stack);
$rows[$pid][2] = $cnt - $plvl-- + $n;
}
return $rows;
}
The resulting associated array that is returned looks like below.
Array ( [34] => Array ( [0] => 34 [1] => 1 [2] => 12 ) [36] => Array ( [0] => 36 [1] => 2 [2] => 7 ) [46] => Array ( [0] => 46 [1] => 3 [2] => 4 ) [47] => Array ( [0] => 47 [1] => 5 [2] => 6 ) [38] => Array ( [0] => 38 [1] => 8 [2] => 11 ) [39] => Array ( [0] => 39 [1] => 9 [2] => 10 ) )
That makes the circle complete. From left/right values in the database to a node tree based on depths that is easy to manipulate in html and then back to left/right values. Hopefully this makes sense. Do you have a better solution or more examples on applications that do this I would love to hear about it.
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.
Comments
8 Responses to “Reordering nested sets using PHP and Javascript”Trackbacks
Check out what others are saying about this post...-
[...] • http://www.zapatec.com/website/main/products/prod3/demo.jsp • http://www.dotvoid.com/2007/09/reordering-nested-sets-using-php-and-javascript/ • Drag and drop using Ext JS with the CakePHP Tree Behavior • [...]
Hia,
we had a similar problem some time ago, and we went for the same algorithm. We support adding, moving and removing nodes. Took us some time to get it all right.. especially moving a branch (with children) from anywhere in a tree to another place in the same tree, or place it in a new one. I spent some time looking for alternate solutions, but I ended up on this one.
Hi,
The adjacency list model and the nested set model aren’t the only one, a less popular one is using the path enumeration model which extends the adjacency list model in a very practical way. You may find more info on my post about hierarchical data in MySQL which summaries the 3 models.
Using the path enumeration model you should be able to easily extract the depth of a node counting the number (-1) of ‘/’ in the path.
Regards,
Patrick Allaert
This function is not working correctly. At least with 4th level menu..
For easy moving of record up and down on the same level in a nested tree, i have method in my nestedTree class which does it correctly. I haven’t added possibility to move given id to different parent.
Someone might be interested …
http://knowledge.drun.net/viewtopic.php?id=37
The last part of the function:
$plvl++;
$cnt = count($rows) * 2;
$leftovers = count($stack);
for($n = 0; $n < $leftovers; $n++) {
$pid = array_pop($stack);
$rows[$pid][2] = $cnt – $plvl– + $n;
}
is not creating the correct rgt values.
Amended code to this:
$plvl++;
$cnt = count($rows) * 2;
$leftovers = count($stack);
for( $n = 0; $n < $leftovers; $n++) {
$pid = array_pop($stack);
$plvl–;
$rows[$pid][2] = $cnt – $plvl + $n;
$cnt–;
}
and seems to work for me.
Thanks for sharing! I haven’t tested it but I’ll make a note to on testing it as soon as possible. Oh – I amended the code in your amendment and removed your third comment on how to amend your amendment to not confuse people