Nested Set library (aka MPTT, aka Hierarchy DB Trees)

[eluser]Jon L[/eluser]
Hey everyone. Last year I found Thunder's Nested Set class, implemented as a model.
Thunder's original class was great, but there were a few things I felt were lacking.

Thunder's Nested Set thread

Some basic info before proceeding:
- This class implements Joe Celko's Nested Set data model, also known as MPTT or Modified Preorder Tree Traversal.
- Nested Sets are great for storing hierarchical data in a database.
- This data model is a better alternative to the Adjacency List model.

Changes:

* Now implemented as a Library as opposed to Model (but could easily be converted back if needed)
* PHP 4 support dropped
* CI db class & active record used as extensively as possible, replacing ALL manual SQL queries
* Table prefixes now supported
* Code cleanup (i.e. - single quotes now replace double quotes when possible)
* Added support for a "parent" column (i.e. - parent_id), enables a DBA to easily
see which child values belong to which parent values, gives ability to speedily
request immediate children only, etc. (plans in the future to expand on this)
* Multiple root nodes now supported. The original class assumed only 1 root node
existed in a table, now multiple roots can exist (or you can view the table itself
as the root node, with multiple direct children allowed)

Attempts were made to keep this class compatible with Thunder's original class,
and it is compatible in almost every way, EXCEPT for the following:

- getRoot no longer exists, now getRootNodes is required, which returns an array of nodes
- parent column is now expected to exist, default name is "parent_id", type should be integer

The library is attached to this post.

Example DB structure:

Code:

CREATE TABLE `nested_set_tree` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `lft` int(10) unsigned NOT NULL default '0',
  `rgt` int(10) unsigned NOT NULL default '0',
  `parent_id` int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (`id`),
  KEY `lft` (`lft`),
  KEY `rgt` (`rgt`),
  KEY `parent_id` (`parent_id`)
) ENGINE=MyISAM;

Example basic PHP usage:

Code:

<?php
class Example {
    public function __construct() {
        
        $this->load->library('nested_set');
        
        # If you are using nested_set in multiple locations, it's best to create a new instance
        
        # Using original instance
        $this->nested_set->setControlParams('nested_set_tree');
        
        # Using new instance
        $this->new_nested_set = new Nested_set();
        $this->new_nested_set->setControlParams('nested_set_tree2');
        
        # Alternatively, you can use the original $this->nested_set for multiple tables,
        # but you must call setControlParams before each separate table use
        
        $this->nested_set->setControlParams('nested_set_tree');
        $root_nodes1 = $this->nested_set->getRootNodes();
        
        $this->nested_set->setControlParams('nested_set_tree2');
        $root_nodes2 = $this->nested_set->getRootNodes();
      
    }
}
?>

I already have this class in use with Backend Pro. Had to modify Backend Pro of course, and also modified KHACL to use this class (as KHACL stores it's data using nested sets, but was managing the data itself, instead of using a dedicated class).
Works great so far.

Let me know if you have any questions/comments.

[eluser]antonumia[/eluser]
hello,

Have you updated this for 1.6/7?


anton

[eluser]tobben[/eluser]
There is a error at line 605:

Code:

public function getTreeNext($tree_handle) {

should be:

Code:

public function getTreeNext(&$tree_handle) {

...anyways, its seems to work well under 1.6/1.7.


There could probably be made some improvements. Additional helpers/methods.:

- Rendering out ol/ul of entire tree and/or sub-tree.
- Rendering out other types of important navigation elements, with easy steps. Ex. bredcrumbs etc.

[eluser]tobben[/eluser]
Though.. the AR-statements should be updated, since some of them are deprecated.

[eluser]tobben[/eluser]
There is also an error in function/method getSubTreeAsHTML, somewhere around line 691.

Code:

if(isset($nodes[0]) && !is_array($nodes[0])) {
            $nodes = array($nodes);
        }

Should be:

Code:

if(isset($nodes[0]) && !is_array($nodes[0])) {
            $nodes = array($this->getNodeFromId($nodes));
        }

[eluser]tobben[/eluser]
Actually.. here is quite a few errors, If im not mistaken.

[eluser]asylmottaket[/eluser]
Hi. I think this seems promising (as well as CodeIgniter itself). (Also thanks to Thunder for the first contribution)

I have one issue though: how to generate a valid unordered list/navigation menu. It's probably similar to this:

Code:

public function getSubTreeAsHTML($nodes, $fields = array()) {
        if(isset($nodes[0]) && !is_array($nodes[0])) {
            $nodes = array($nodes);
        }
    
        $retVal = '';
    
        foreach($nodes AS $node) {
    
            $tree_handle = $this->getTreePreorder($node);
        
            while($this->getTreeNext($tree_handle))
            {
                // print indentation
                $retVal .= (str_repeat(' ', $this->getTreeLevel($tree_handle)*4));

                // print requested fields
                $field = reset($fields);
                while($field){
                    $retVal .= $tree_handle['row'][$field] . "\n";
                    $field = next($fields);
                }
                $retVal .= "<br />\n";

            }
        }

        return $retVal;
    }

But other than that, I'm confused, so I would really appreciate any help!

Thanks,

Asylmottaket

[eluser]Jon L[/eluser]
I'm working with this class outside of CI, and I'm cleaning up any issues I find as I go along.
I'll be posting back an updated version in a week or so.

Cheers

[eluser]tmkajk[/eluser]
Hello Jon,
I was wondering if you had made any additional progress with this?


Regards,
Todd M. Kimball

[eluser]dirkpostma[/eluser]
Why did you convert it to a library? I think a model is much easier, or not? I mean, if I create a model for nested categories,

Code:

class Cat extends Model

, I tend to copy many methods of the nested set library that use the (same) methods in the library. E.g. concerning creation and moving of nodes. If the nested set library was actually a model, I could do

Code:

class Cat extends Nested_Set

, and I get many admin methods "for free". I don't see benefits of library, why did you make that choice?