Views on my Modified Preorder Tree Classes

[mkrz]

Mmh, what I did in this case was to insert the menu items one by one in the order I wanted them. (sometimes alphabetical, sometimes by relevance). That way, they would be automatically ordered on output. That may or may not be appropriate to your situation (depending on how many documents you have and wether they will be inserted alphabetically). Maybe you could write a function that traverses a branch, looks at the beginning letters of the documents and inserts the document at the right point?

One crucial function that was missing in this thread's outcome and in the great third-party script for tree management that I used (see above posts) was the ability to insert an item at a specific point in a branch. What the management script did up to now was to always insert an item at the end of the branch. If you wanted to change something, you would have to delete and rebuild that whole branch. That made the whiole thing nearly useless for me, because it was nearly unmanageable.

I wracked my brain for a while and extended the script with that specific function, plus the ability to move a whole branch to a specific point at the same level. I can post it if you're interested.

[mrjhman]

That would be great... thanks! Your class looks great thus far and I'd be interested in the additional function.

I'd really like to see a way to sort the results at each level... I'm going to give it some more thought. I'd imagine I could load up an array with the results and then sort the array at each level but I rather complete the sorting in the sql query.

[mkrz]

That would be great... thanks! Your class looks great thus far and I'd be interested in the additional function.

Mmh, maybe I should clarify: I use a twofold solution: For storing items, I use the script by Maxim Poltarak (http://dev.e-taller.net/dbtree/) (see attached file (modified by me), and for outputting the items, I use my own script.

What I did now was to extend Maxim's script so that I can insert an item after any given item.

The additional function looks like this:

// FUNCTION ADDED. MK
// Inserts a record into the table with nested sets
// $ID : ID of the element after which the new element is to be inserted
// $data : array with data to be inserted: array(<field_name> => <field_value>)
// Returns : true on success, or false on error
    function insertAtSameLevel($ID, $data) {
        if(!(list($leftId, $rightId, $level) = $this->getNodeInfo($ID))) trigger_error("phpDbTree error: ".$this->db->error(), E_USER_ERROR);

        // preparing data to be inserted
        if(sizeof($data)) {
            $fld_names = implode(',', array_keys($data)).',';
            $fld_values = '\''.implode('\',\'', array_values($data)).'\',';
        }
        $fld_names .= $this->left.','.$this->right.','.$this->level;
        $fld_values .= ($rightId+1).','.($rightId+2).','.($level);

        // creating a place for the record being inserted
        if($ID) {
            $this->sql = 'UPDATE IGNORE '.$this->table.' SET '
                . $this->left.'=IF('.$this->left.'>'.$rightId.','.$this->left.'+2,'.$this->left.'),'
                . $this->right.'=IF('.$this->right.'>'.$rightId.','.$this->right.'+2,'.$this->right.')'
                . 'WHERE '.$this->right.'>'.$rightId;
            if(!($this->db->query($this->sql))) trigger_error("phpDbTree error: ".$this->db->error(), E_USER_ERROR);
        }

        // inserting new record
        $this->sql = 'INSERT INTO '.$this->table.'('.$fld_names.') VALUES('.$fld_values.')';
        if(!($this->db->query($this->sql))) trigger_error("phpDbTree error: ".$this->db->error(), E_USER_ERROR);

        return $this->db->insert_id();
    } 

As I just found out, I didn't implement the function to move a branch to another "anchor point" at the same level. I meant to, and prepared everything for it, but found it too daunting for the time being.

I'd really like to see a way to sort the results at each level... I'm going to give it some more thought. I'd imagine I could load up an array with the results and then sort the array at each level.

Yes, I think that would be possible. If you look at the writer class I posted in one of the earlier (at least I think I did), I load everything into an array and do a lot of stuff with it. Why not sort every branch then?

But, as I said: I don't do any sorting on output in my case. Instead I store every item manually at the right place in the tree. This is because in my menu, some sub branches are sorted alphabetically, some by relevance and so forth. There is no general rule, and that's why I store them manually and do no sorting on output (except by their Left value).

Hope this helps.

[mkrz]

I sent Maxim (a.k.a. su1d over here), the author of the script I mentioned, an Email yesterday. Guess what: Today he put a new version online that includes the function I added. Now that's quick! You can find it at http://dev.e-taller.net/dbtree/ . It's version 1.4.

One other thing I noted: In his script, Maxim uses another way to assign left and right values inside of a branch than that described in the sitepoint article. This got me stumped for a little while, but then I realized that his way of doing it is much easier to handle, because it makes it easier to insert items afterwards.

[fbronx]

Is there a cross-database version of this dbtree code? The code doesn't work on a PostgreSQL database.

[Version0-00e]

Have you looked over at www.phpclasses.org by any chance? I've not yet found a Postgre library for an hierarchal tree using the Modified PreOrder Traversal approach

[su1d]

fbronx,
real databases don't need this kind of libraries at all, because you're supposed to use stored procedures and triggers.

[Super Phil]

Dragging this up 2 months later, because its still useful

I worked on my queries today, shrunk everything down to one. This is just for getting parts of the tree. The storing two queries isnt horribly elegant, but this way theres no full table scans. I still have to work on redoing my insert/movement stuff, but thats a different class.

<?php
require_once 'global.php';

class NodeReader
{
    var $table;
    var $DB;
    var $sql = array();
    var $fields;
    var $sql_choice = 'normal';
    var $parent = array(1,1);

    function NodeReader(&$Connection, $table)
    {
        $this->table = $table;
        $this->Connection =& $Connection;
    }


    function set_parent($parent)
    {
        // ugly
        $this->parent = array(
            ('parent.' . $parent[0]),
            is_int($parent[1]) ?
                $parent[1] :
                '\'' . $parent[1] . '\''
            );
        $this->sql_choice = 'parent';
        unset($parent);
        return true;
    }

    function set_fields($fields)
    {
        $this->fields = ', nodes.' . implode(', nodes.', $fields);
        return true;
    }
    function set_sql()
    {
        // we use different SQLs for optimz reasons
        $this->sql['parent'] = '
            SELECT SQL_CACHE
                nodes.id,
                nodes.right_id,
                nodes.left_id,
                nodes.level,
                nodes.title,
                REPEAT(\'&nbsp;\', nodes.level-1) html_level_spaces
                ' . $this->fields . '
            FROM
                data nodes FORCE INDEX (left_id),
                data parent
            WHERE
                nodes.level < ? AND
                nodes.left_id >= parent.left_id AND
                nodes.right_id <= parent.right_id AND
                ' . $this->parent[0] . ' = ?
            ORDER BY
                nodes.left_id;';


        $this->sql['normal'] = '
            SELECT SQL_CACHE
                nodes.id,
                nodes.right_id,
                nodes.left_id,
                nodes.level,
                nodes.title,
                REPEAT(\'&nbsp;\', nodes.level-1) html_level_spaces
                ' . $this->fields . '
            FROM
                data nodes FORCE INDEX (left_id)
            WHERE
                nodes.level < ?
            ORDER BY
                nodes.left_id;';
    }

    function &get_tree($dig_level = 5)
    {
        // set sql
        // we do this now instead of in constructor
        // in case set_sql changed $parent
        $this->set_sql();

        // set up the query
        $RetrievalStmt =& $this->Connection->query($this->sql[$this->sql_choice]);
        $RetrievalStmt->bind_int(1, $dig_level);

        // if using parent query, bind the search
        if($this->sql_choice === 'parent')
            $RetrievalStmt->bind(2, $this->parent[1]);

        $TreeIterator =& $RetrievalStmt->execute();

        unset($RetrievalStmt);
        return $TreeIterator;

    }

    function get_node()
    {

    }

}

$Favorites =& new NodeReader($Connection, 'data');
$Favorites->set_parent(array('id', 4));
$Favorites->set_fields(array('cat', 'dog'));

$x =& $Favorites->get_tree(5);
while($i =& $x->next())
{
    echo "$i[html_level_spaces] $i[title] ($i[id]) ($i[cat])<br />";
}

?>

[petesmc]

Thought I'd post some of my code to see if you're interested:

class CategoryController extends Container {

    var $Categories;
    var $fCategories;
    
    function listCategories() {
    
        unset($this->Categories);
    
        $sql = "SELECT CID, CategoryName, SID FROM categories ORDER By SID, CategoryName";
        $myQuery = $this->DB->query($sql);
        
        $c = new Category($this->DB);
        unset($this->Categories);
        while ($result = $myQuery->getRows()) {
            extract($result);
            $c->CID = $CID;
            $c->SID = $SID;
            $c->CategoryName = $CategoryName;
            
            $this->Categories[] = $c;
            $c->clear();
        }
    }
    
    function formatList() {
            
        $category = $this->Categories;
        unset($this->fCategories);
        $lastCID[] = "0";
        $a = 0;
        $i = 0;
        $index = 0;
                
        $newCat = new Category($this->DB);
        while ($index <= count($category)) {
            

            unset($z);
            foreach ($category as $c) {
                $z[] = $c->SID;
            }

            $match = array_search($lastCID[$a],$z);
            if($match === FALSE) {
                if(($lastCID[$a] == "0") || ($a < 0)) {
                    break;
                }
                $a--;
        
            } else {

                $a++;
                $lastCID[$a] = $category[$match]->CID;

                // Set New
                
                $newCat->CategoryName = $category[$match]->CategoryName;
                $newCat->CID = $category[$match]->CID;
                $newCat->SID = $category[$match]->SID;
                $newCat->CategoryLevel = $a - 1;
                $newCat->ArticleCount = 0;
                $this->fCategories[$index] = $newCat;
                
                $newCat->clear();
                // Delete Old
                $category[$match]->CategoryName = '';
                $category[$match]->CID = '';
                $category[$match]->SID = '';

                $index++;
            }
        
            $i++;
        
        }
            
    }
    
        function deleteCategoryChain($fCID) {
        
        $this->listCategories();
        $this->formatList();
        
        $deleteList;
        $level = 0;
        $found = false;
        
        foreach ($this->fCategories as $c) {

            
            if ($found == false) {
                if ($c->CID == $fCID) {
                    $deleteList[] = $c->CID;
                    $level = $c->CategoryLevel;
                    $found = true;
                }
            } else {
            
                if($c->CategoryLevel > $level) {
                    $deleteList[] = $c->CID;
                } else {
                    break;
                }
            }
        }
        echo implode(', ', $deleteList);
        $sql = "DELETE FROM categories WHERE CID IN (" . implode(', ', $deleteList) . ")";
        echo $sql;
        $myQuery = $this->DB->query($sql);
        
    }

    function deleteCategory($oCategory) {
    
        $sql = "DELETE FROM categories WHERE CID=" . $oCategory->CID;
        $myQuery = $this->DB->query($sql);
        
        $sqla = "UPDATE categories SET SID=" . $oCategory->SID . " WHERE SID=" . $oCategory->CID;
        $myQuerya = $this->DB->query($sqla);        

    }
    
    function newCategory($oCategory) {
    
        $oCategory->slashes();
    
        $sql = "INSERT INTO categories SET " . 
        "CategoryName='" . $oCategory->CategoryName . "', " .
        "SID=" . $oCategory->SID . ", " .
        "CategoryDescription='" . $oCategory->CategoryDescription . "'";
        
        $myQuery = $this->DB->query($sql);
    }
    

    
    function getBreadCrumb($oCategory) {
        
        
        foreach ($this->fCategories as $cz) {
            $z[] = $cz->CID;
        }
        
        $match = array_search($oCategory->CID, $z);
        
        $level = $this->fCategories[$match]->CategoryLevel;
        $trail[] = $this->fCategories[$match];

        
        for ($i = $match; $i >= 0; $i--) {
            if ($this->fCategories[$i]->CategoryLevel < $level) {
                $trail[] = $this->fCategories[$i];
                $level = $this->fCategories[$i]->CategoryLevel;                
            }    
        
        }
        $trail = array_reverse($trail);
        return $trail;        
    }
    
    
    
}



class Category extends Container {

    var $CID;
    var $SID;
    var $CategoryName;
    var $CategoryDescription;
    var $CategoryLevel;
    var $ArticleCount;
    
    function getCategory($fCID) {
    
        $sql = "SELECT * FROM categories WHERE CID=" . $fCID;
        $myQuery = $this->DB->query($sql);
        
        $result = $myQuery->getRows();
        extract($result);
        
        $this->CID = $CID;
        $this->SID = $SID;
        $this->CategoryName = $CategoryName;
        $this->CategoryDescription = $CategoryDescription;
        
    }
    

} 

The formatList() gets an array of the categories in Linear order like:

Main
-Sub
--Sub sub
-Sub2
--Sub Sub 2
-- sub sub 3

[pht]

Hey

Reading your postings and thinking next...

Could someone tell me advantage of nested set over next table schema:

DB:cats
cat_id
cat_title
cat_path
cat_level

where cat_path is a "dot" separated list of parents (1.12.2)

Adding a category is simple. No need to update any other rows. Deleting is also easy

1) delete WHERE cat_path = '1.12.2' + '.cat_id'
2) delete WHERE cat_path LIKE '1.12.2' + '.cat_id%'

Getting categories is also easy, just like deleting, but moving or copying category with all subcategories is tricky for me (however moving only category and closest childs is trivial).

That's why i'm asking an advice. Would you prefer nested sets over this method? Performance on bigger scale tables?

(Presuming 9 999 999 rows and depth of 30 we get the length of the cat_path string -> 29*dots + 30*7 = 240 characters. So it will suite to varchar(255))

Thanks,
Marko

[Super Phil]

While thats an easier method to understand, I think it will be easier to retrieve a node, parents,a nd children in SQL . MPTT is just a between; getting the parents in one querie on yours would be a bit trickier.

[pht]

Well i like more about simple methods, if it's also efficient...

Is there some theory references to these three methods? I can find something about

a) Modified preorder tree traversal
b) Adjacency list
c) ?

But cannot find anything detailed about the third method, maybe because i don't know the name of the method...

[timo.heil]

Hi! Have been reading through all the posts; I've created a associative multidimensional array which has been retrieved from my local file system (representing the folder structure. I would like to store this strucutre in a SQL table using tree traversal. Which function/algorithm is used to create the appropriate left/right values from the multidimensional array?

Many thanks
-timo.

[Dr Livingston]

c) ?

Is this what your looking for?

http://fungus.teststation.com/~jon/t...eeHandling.htm

For simple hierarchies I think the Adjacency List is ideal where you know there aren't going to be a lot of depth, otherwise implement another method. Remember to cache the resultsets you have if possible.

For example, serialise the whole lot based on an ID, such as the PK

Petesmc,

Would you be willing to post more script with some examples of use? I'd appreciate it if you could, thanks.

[Super Phil]

Is this what your looking for?

http://fungus.teststation.com/~jon/t...eeHandling.htm

For simple hierarchies I think the Adjacency List is ideal where you know there aren't going to be a lot of depth, otherwise implement another method. Remember to cache the resultsets you have if possible.

For example, serialise the whole lot based on an ID, such as the PK

Petesmc,

Would you be willing to post more script with some examples of use? I'd appreciate it if you could, thanks.

Killer Link.

[petesmc]

Is this what your looking for?
Petesmc,

Would you be willing to post more script with some examples of use? I'd appreciate it if you could, thanks.

Sure. Here is an example of how I print out all the categories, in level structures:

<?php

$cc = new CategoryController($db);
$cc->listCategories();
$cc->formatList();
    
foreach ($cc->fCategories as $cz) {
    
    // Just formatting
    echo '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;';
    echo str_repeat("--", $cz->CategoryLevel);
    
    // Category Level=0 are the root Nodes. Just want to make them bold
    if($cz->CategoryLevel == 0) {
        echo '<br><b>' . $cz->CategoryName . '</b>' . CR;
    } else {
        echo $cz->CategoryName . CR;
    }
    
}

?>

And this is how I would get breadcrumbs:

<?php

$cc = new CategoryController($db);
$cc->listCategories();
$cc->formatList();

foreach ($cc->fCategories as $fcz) {
    if ($fcz->CID == $a->CID) {
        $trail = $cc->getBreadCrumb($fcz);
        break;
    }
}
?>

I'm sure the above one could become a lot more organised, however, it serves it's purpose quite nicely for me.

I'm using just a simple Name, ParentID (SID), CategoryID (CID), structure, where the root node(s) have a parent SID of -1.

Hope this helps,
-Peter

[Dr Livingston]

Thanks, the examples will help

Another question, if you don't mind..? Have you tried to format the output using Unordered Lists? I find this difficult, having the ULs comply with the W3 formats.

[petesmc]

Do you mean like this:

<ul class="categoryList">

<?php
$cc = new CategoryController($db);
$cc->listCategories();
$cc->formatList();

$previousLevel = 1;
$listCount = 0;
$total = count($cc->fCategories);
$changed = false;
foreach ($cc->fCategories as $cz) {

    
    if ($cz->CategoryLevel != 0) {
        if ($cz->CategoryLevel == $previousLevel) {                
            echo '<li>' . $cz->CategoryName .CLRF;
        } elseif ($cz->CategoryLevel > $previousLevel) {
            $previousLevel++;
            echo '<ul class="categoryListDeep">' . CLRF;
            echo '<li>' . $cz->CategoryName . '</a> (' . CLRF;
        } elseif ($cz->CategoryLevel < $previousLevel) {
            $previousLevel--;
            echo '</ul>' . CLRF;
            echo '<li>' . $cz->CategoryName . CLRF;
        }
        $listCount++;
    }
}

?>
</ul>

[Dr Livingston]

Exactly

Thanks a lot, will help a lot.

[topsmith]

I used once PEAR:: DB_Nested_Set:
http://pear.php.net/package/DB_NestedSet

[bruin03]

I found a Modified Preorder Traversal Class here: http://www.aesthetic-theory.com/learn.php?mptt
Unfortunately, examples of the class weren't provided. I'm an OOP noob. Based on the class, could someone look at the class and tell me how to use it? I would really appreciate it. Thanks in advance!
//db structure

 CREATE TABLE `data` ( `id` MEDIUMINT UNSIGNED NOT NULL AUTO_INCREMENT, 
`title` VARCHAR(200) NOT NULL, 
`left_id` INT UNSIGNED NOT NULL, 
`right_id` INT UNSIGNED NOT NULL, 
`level` MEDIUMINT UNSIGNED NOT NULL, 
UNIQUE (`id`) );

class Tree

{

    var $data_array; // we'll store the data in this

    var $cnx; // our connection to the database



    // our constructer, we'll use it to connect to the database

    function Tree()

    {

        $cnx = mysql_connect(DB_HOST, DB_USERNAME, DB_PASSWORD) or die ('Unable to connect to database');

        mysql_select_db(DB_DATABASE, $cnx) or die ('Unable to select database');

    }



    /* this will display the data... we'll give it a few paramaters

     * parent: this will be an integer or false,

     *        if its an integer we will get all children,

     *        if its false we will get the entire tree

     * dig_levels: this will be an integer, or false

     *        represents the number of levels to dig BELOW PARENT for data.

     *        Examples, if its 3 and we get the entire tree, we'll get everything with a level <= 3

     *            (music,weezer,pinkerton BUT NOT elscorcho)

     *        ex: if its 2 and we have parent weezer (level:2) we'll get 2 + dig_level, or everything with a level <= 4

     * inc_parent: whether or not to include parent in result set

    */

    function get_data($parent = false, $dig_level = false, $include_parent = true)

    {

        if($parent)

        {

            $sql = 'SELECT `right_id`, `left_id`, `level` FROM ' . DATA_TABLE . ' ';



            $where = 'WHERE `id`=' . $parent . ';';

            $parent_res = mysql_query($sql . $where) or die(mysql_error());

            unset($sql, $where);

            if($include_parent) {

                $lt = '<=';

                $gt = '>=';

            }

            else

            {

                $lt = '<';

                $gt = '>';

            }

            $parent_arr = mysql_fetch_array($parent_res);

            //$parent_right = $parent_arr[0];

            //$parent_left = $parent_arr[1];

            //$parent_nest = $parent_arr[2];

            $where = 'WHERE `left_id` ' . $gt . ' ' . $parent_arr[1] . ' AND `right_id` ' . $lt . ' ' . $parent_arr[0] . ' ';

            unset($parent_res);

        }

        if($dig_level)

        {

            $nest_limit = isset($parent_arr) ? $parent_arr[2] + $dig_level : $dig_level;

            $level_adjustment = $nest_limit - $dig_level; // we'll use this later

            if(isset($where))

            {

                $where .= 'AND `level` <= ' . $nest_limit . ' ';

            }

            else

            {

                $where = 'WHERE `level` <= ' . $nest_limit . ' ';

            }

        }

        $sql = 'SELECT * FROM `' . DATA_TABLE . '` ' . $where . 'ORDER BY `left_id` ASC';

        unset($where, $parent_arr);

        $raw_result = mysql_query($sql) or die(mysql_error());

        while($item = mysql_fetch_array($raw_result)) {

            $data[$item['id']]['title'] = $item['title'];

            $data[$item['id']]['left_id'] = $item['left_id'];

            $data[$item['id']]['right_id'] = $item['right_id'];

            $data[$item['id']]['level'] = $item['level'];

            $data[$item['id']]['relative_level'] = $item['level'] - $level_adjustment;

        }

        unset($raw_result);

        $this->data_array = $data;

        return $data;
    }

}

?>

[Ren]

Heres my method of rendering a <ol> from the nest set model

$categories is an iterator of categories in "left" order, category::$depth is how deep it is in the tree.

Uses relative depths to correctly close open tags.. (Well atleast it should

	echo '<ol>';
	unset($depth);
	foreach($categories as $category)
	{
		if (isset($depth))
			switch ($depth -= $category->depth)
			{
				case -1: echo '<ol>'; break;
				case 0:	echo '</li>'; break;
				case 1: echo '</ol></li>'; break;
				default: while($depth--)echo '</ol></li>'; break;
			}
		echo '<li>', htmlspecialchars($category->name);
		$depth = $category->depth;
	}
	while ($depth--)
		echo '</li></ol>';
	echo '</li></ol>';

[Ren]

Hey

Could someone tell me advantage of nested set over next table schema:

DB:cats
cat_id
cat_title
cat_path
cat_level

* Not sure all RDBMS use indexes with LIKE.

* Operations like getting the parent or ancestors seems tricky.

Edit:

Doh, parent is fairly trivial, just popping of a bit of the path

Getting the ancestors of a particular category can be quite important for rendering stuff like breadcrumbs. Can't think of "nice" method doing that with paths atm.

SELECT p.categoryID AS "categoryID", p.name AS name, p.depth AS depth
    FROM Categories AS p
    INNER JOIN Categories AS c ON c.left > p.left AND c.left < p.right
    WHERE c.categoryID = :categoryID ORDER BY p.left ASC

Is the nested set method, a simple bit of PHP to render..

    $categories = $selectedCategory->getAncestors();
    echo '<ol class="breadcrumb">';
    foreach($categories as $category)
        echo '<li>', SEP, '<a href="?categoryID=', htmlspecialchars($category->categoryID), '">', htmlspecialchars($category->name), '</a>', '</li>';

    echo '<li>', SEP, '<a href="?categoryID=', htmlspecialchars($selectedCategory->categoryID), '">', htmlspecialchars($selectedCategory->name), '</a>', '</li>';
    echo '</ol>';

[bruin03]

Heres my method of rendering a <ol> from the nest set model

$categories is an iterator of categories in "left" order, category::$depth is how deep it is in the tree.

Uses relative depths to correctly close open tags.. (Well atleast it should

	echo '<ol>';
	unset($depth);
	foreach($categories as $category)
	{
		if (isset($depth))
			switch ($depth -= $category->depth)
			{
				case -1: echo '<ol>'; break;
				case 0:	echo '</li>'; break;
				case 1: echo '</ol></li>'; break;
				default: while($depth--)echo '</ol></li>'; break;
			}
		echo '<li>', htmlspecialchars($category->name);
		$depth = $category->depth;
	}
	while ($depth--)
		echo '</li></ol>';
	echo '</li></ol>';

I've learnt quite a bit about classes, trees and MPTT since my last post. I just wanted to say that this bit of code for ordered lists and your code for unordered list was EXTREMELY useful! I'll definitely add it to my toolkit.

[[ArcanE]]

Anyone found a decent solution for moving tree nodes and their children up and down in the menu while maintaining the mptt database integrity yet?