RE: [PHP] "Nested Set Model" or "modified preorder tree traversal" [SOLVED]
| From: | Daevid Vincent | Date: | Thu, 02 Mar 2006 08:06:40 +0000 |
| Subject: | RE: [PHP] "Nested Set Model" or "modified preorder tree traversal" [SOLVED] | ||
| References: | 1 | Groups: | php.db |
| Request: | Send a blank email to php-db+get-41369@lists.php.net to get a copy of this message | ||
UGH!!!!!! LAME! This list does not allow attachments apparently. *sigh*.
Sorry, here it is as a giant "paste" then...
------------------------------------->8 snip
8<--------------------------------
<?php
/*
# This is all pretty much copy/paste code from this URL:
# http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
here are some other references:
http://www.sitepoint.com/article/hierarchical-data-database
http://www.zend.com/zend/tut/tutorial-ferrara2.php?article=tutorial-ferrara2
&id=3453&open=1&anc=0&view=1
http://simon.incutio.com/archive/2003/06/19/storingTrees
http://istherelifeafter.com/joecelko.html
http://www.codeproject.com/cs/database/Trees_in_SQL_databases.asp
and here's an ASP technique that looks interesting
http://www.4guysfromrolla.com/webtech/101202-1.shtml
and it appears that Rails already has acts_as_nested_set:
http://www.nabble.com/acts_as_tree-with-Modified-Preorder-Traversal--t929560
.html
*/
require_once('../includes/db.inc.php');
//TODO: [dv] There needs to be a function to MOVE a category to another
spot.
// especially since we have a way to delete and move
children up.
// This could be a hybrid of insert_category_after() I
think.
/**
* Delete a category (and optionally all of it's children) from the tree
*
* @access public
* @return void
* @param mixed $category the string name or category ID of the
category to delete.
* @param boolean $deleteChildren (false) otherwise move all the
subcategories up to the level of the deleted category
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.1
* @date 03/01/06
*/
function delete_category($category = null, $deleteChildren = false)
{
if (is_null($category)) return false;
SQL_QUERY('LOCK TABLE categories WRITE');
if (is_leaf_node($category))
{
$sth = SQL_QUERY("SELECT @myLeft := lft, @myRight := rgt,
@myWidth := rgt - lft + 1 FROM categories
WHERE ".(
(is_numeric($category)) ? "id = '".$category."'" : "name =
'".SQL_ESCAPE($category)."'" )." LIMIT 1");
if ($sth && SQL_NUM_ROWS($sth) == 1)
{
SQL_QUERY("DELETE FROM categories WHERE lft BETWEEN
@myLeft AND @myRight");
SQL_QUERY('UPDATE categories SET rgt = rgt -
@myWidth WHERE rgt > @myRight');
SQL_QUERY('UPDATE categories SET lft = lft -
@myWidth WHERE lft > @myRight');
}
}
else
{
if ($deleteChildren) //just delete the little bastards
{
$sth = SQL_QUERY("SELECT @myLeft := lft, @myRight :=
rgt, @myWidth := rgt - lft + 1 FROM categories
WHERE ".(
(is_numeric($category)) ? "id = '".$category."'" : "name =
'".SQL_ESCAPE($category)."'" )." LIMIT 1");
if ($sth && SQL_NUM_ROWS($sth) == 1)
{
SQL_QUERY("DELETE FROM categories WHERE lft
BETWEEN @myLeft AND @myRight");
SQL_QUERY('UPDATE categories SET rgt = rgt -
@myWidth WHERE rgt > @myRight');
SQL_QUERY('UPDATE categories SET lft = lft -
@myWidth WHERE lft > @myRight');
}
}
else //move them up to the level of the deleted category
{
$sth = SQL_QUERY("SELECT @myLeft := lft, @myRight :=
rgt, @myWidth := rgt - lft + 1 FROM categories
WHERE ".(
(is_numeric($category)) ? "id = '".$category."'" : "name =
'".SQL_ESCAPE($category)."'" )." LIMIT 1");
if ($sth && SQL_NUM_ROWS($sth) == 1)
{
SQL_QUERY("DELETE FROM categories WHERE lft
= @myLeft");
SQL_QUERY('UPDATE categories SET rgt = rgt -
1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight');
SQL_QUERY('UPDATE categories SET rgt = rgt -
2 WHERE rgt > @myRight');
SQL_QUERY('UPDATE categories SET lft = lft -
2 WHERE lft > @myRight');
}
}
}
SQL_QUERY('UNLOCK TABLES');
}
/**
* Inserts a new category to the right of an existing category
*
* @access public
* @return integer ID of the newely inserted category or false.
* @param string $newname the name of the new category.
* @param mixed $leftnode the name or ID of the immediate left
category in the sibline tree heirarchy.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.1
* @date 02/27/06
*/
function insert_category_after($newname = null, $leftnode = null)
{
//global $OPTION;
//$OPTION['debug'] = true;
if (is_null($newname) || is_null($leftnode)) return false;
if (is_numeric($leftnode) && $leftnode < 1) return false;
SQL_QUERY('LOCK TABLE categories WRITE');
if (is_leaf_node($leftnode))
{
$sth = SQL_QUERY("SELECT @myLeft := lft FROM categories
WHERE ".(
(is_numeric($leftnode)) ? "id = '".$leftnode."'" : "name =
'".SQL_ESCAPE($leftnode)."'" )." LIMIT 1");
if ($sth && SQL_NUM_ROWS($sth) == 1)
{
SQL_QUERY('UPDATE categories SET rgt = rgt + 2 WHERE
rgt > @myLeft');
SQL_QUERY('UPDATE categories SET lft = lft + 2 WHERE
lft > @myLeft');
SQL_QUERY("INSERT INTO categories(name, lft, rgt)
VALUES('".SQL_ESCAPE($newname)."', @myLeft + 1, @myLeft + 2)");
$id = SQL_INSERT_ID();
}
}
else
{
$sth = SQL_QUERY("SELECT @myRight := rgt FROM categories
WHERE ".(
(is_numeric($leftnode)) ? "id = '".$leftnode."'" : "name =
'".SQL_ESCAPE($leftnode)."'" )." LIMIT 1");
if ($sth && SQL_NUM_ROWS($sth) == 1)
{
SQL_QUERY('UPDATE categories SET rgt = rgt + 2 WHERE
rgt > @myRight');
SQL_QUERY('UPDATE categories SET lft = lft + 2 WHERE
lft > @myRight');
SQL_QUERY("INSERT INTO categories(name, lft, rgt)
VALUES('".SQL_ESCAPE($newname)."', @myRight + 1, @myRight + 2)");
$id = SQL_INSERT_ID();
}
}
SQL_QUERY('UNLOCK TABLES');
//$OPTION['debug'] = false;
return ($id > 0) ? $id : false;
}
/**
* Shows a tally of the number of products in each category
*
* @access public
* @return array
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
*/
function get_category_product_tally()
{
return SQL_QUERY_ARRAY_PAIR("SELECT parent.name,
COUNT(products.name)
FROM
categories AS node, categories AS parent, products
WHERE
node.lft BETWEEN parent.lft AND parent.rgt
AND node.id = products.category_id
GROUP BY
parent.name
ORDER BY
node.lft");
}
/**
* Returns an array of all the categories defined
*
* @access public
* @return array
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
*/
function get_categories()
{
return SQL_QUERY_ARRAY_PAIR("SELECT id, name FROM categories ORDER
BY name");
}
/**
* Returns an array of all the categories in the tree starting from a given
category
*
* @access public
* @return array
* @param string $name the name of the category to start with.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
*/
function get_category_tree($name = null)
{
if (is_null($name)) return false;
return SQL_QUERY_ARRAY_PAIR("SELECT node.id, node.name
FROM
categories AS node, categories AS parent
WHERE
node.lft BETWEEN parent.lft AND parent.rgt
AND parent.name = '".SQL_ESCAPE($name)."'
ORDER BY
node.lft");
}
/**
* Show the path of categories to a given node.
*
* @access public
* @return array
* @param mixed $category the string name of the category or its ID to
start with.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
*/
function get_path($category = 1)
{
return SQL_QUERY_ARRAY_PAIR("SELECT parent.id, parent.name
FROM
categories AS node, categories AS parent
WHERE
node.lft BETWEEN parent.lft AND parent.rgt
AND ".(
(is_numeric($category)) ? "node.id = '".$category."'" :
"node.name =
'".SQL_ESCAPE($category)."'" )."
ORDER BY
node.lft");
}
/**
* Show the products of that category, as well as list its immediate
sub-categories,
* but not the entire tree of categories beneath it.
*
* @access public
* @return array
* @param mixed $category the string name of the category or its ID to
start with.
* @param boolean $showParent (false) Show the parent node.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
*/
function get_subcategories($category = 1, $showParent = false)
{
return SQL_QUERY_ARRAY_PAIR("
SELECT node.id, node.name,
(COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM categories AS node,
categories AS parent,
categories AS sub_parent,
(
SELECT node.id, node.name,
(COUNT(parent.name) - 1) AS depth
FROM categories AS node,
categories AS parent
WHERE node.lft BETWEEN
parent.lft AND parent.rgt
AND ".(
(is_numeric($category)) ? "node.id = '".$category."'" :
"node.name =
'".SQL_ESCAPE($category)."'" )."
GROUP BY node.name
ORDER BY node.lft
)AS sub_tree
WHERE node.lft BETWEEN parent.lft AND
parent.rgt
AND node.lft BETWEEN sub_parent.lft
AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth ".( ($showParent) ? '<=' :
'=')." 1
ORDER BY node.lft");
}
/**
* Returns an array of all the category names in the tree and their depths
*
* @access public
* @return array
* @param string $name the name of the category to start with.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
*/
function get_depths($name = null)
{
if (is_null($name))
{
return SQL_QUERY_ARRAY_PAIR("SELECT node.name,
(COUNT(parent.name) - 1) AS depth
FROM
categories AS node, categories AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft");
}
else
{
return SQL_QUERY_ARRAY_PAIR("
SELECT node.name,
(COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM categories AS node,
categories AS parent,
categories AS sub_parent,
(
SELECT node.name,
(COUNT(parent.name) - 1) AS depth
FROM categories AS
node,
categories AS parent
WHERE node.lft
BETWEEN parent.lft AND parent.rgt
AND node.name =
'".SQL_ESCAPE($name)."'
GROUP BY node.name
ORDER BY node.lft
)AS sub_tree
WHERE node.lft BETWEEN parent.lft
AND parent.rgt
AND node.lft BETWEEN
sub_parent.lft AND sub_parent.rgt
AND sub_parent.name =
sub_tree.name
GROUP BY node.name
ORDER BY node.lft");
}
}
/**
* Returns an array of all the leaf nodes
*
* @access public
* @return array
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
* @see is_leaf_node()
*/
function get_leaf_nodes()
{
return SQL_QUERY_ARRAY_PAIR('SELECT id, name FROM categories WHERE
rgt = lft + 1');
}
/**
* Returns boolean if category is a leaf node
*
* @access public
* @return boolean
* @param mixed $category the string name of the category or its ID.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.0
* @date 02/23/06
* @see get_leaf_nodes()
*/
function is_leaf_node($category = null)
{
if (!is_null($category))
{
if ($sth = SQL_QUERY("SELECT id, name FROM categories WHERE
rgt = lft + 1
AND ".( (is_numeric($category)) ? "id = '".$category."'" :
"name =
'".SQL_ESCAPE($category)."'" )))
return (SQL_NUM_ROWS($sth) == 1);
}
return false;
}
/**
* Rename a category
*
* @access public
* @return false if invalid input
* @param mixed $category the string name of the category or its ID.
* @param string $newname the name of the new category.
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.1
* @date 03/01/06
*/
function rename_category($category = null, $newname = null)
{
if (is_null($category) || is_null($newname)) return false;
SQL_QUERY("UPDATE categories SET name = '".SQL_ESCAPE($newname)."'
WHERE ".( (is_numeric($category)) ? "id = '".$category."'" :
"name =
'".SQL_ESCAPE($category)."'" )." LIMIT 1", true);
}
/**
* Prints out the tree with indentations in a very basic textual way
*
* @access public
* @return void
* @param integer $id the $id of the node to highlite
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.1
* @date 02/27/06
* @see print_nested_tree_html()
*/
function print_nested_tree_txt($id = 1)
{
$sth = SQL_QUERY("SELECT node.id as id, CONCAT( REPEAT( ' ',
(COUNT(parent.name) - 1) ), node.name) AS name
FROM categories AS node, categories
AS parent
WHERE node.lft BETWEEN parent.lft
AND parent.rgt
GROUP BY node.name
ORDER BY node.lft");
if ($sth)
{
print "\n";
while($row = SQL_ASSOC_ARRAY($sth))
print (($row['id'] == $id) ? '['.$row['name'].']' :
$row['name']) . "\n";
}
}
/**
* Prints out the tree with indentations in a nice HTML way with hyperlinks
and highlight current category
*
* @access public
* @return void
* @param integer $id the $id of the node to highlite
* @author Daevid Vincent [daevid@daevid.com]
* @version 1.1
* @date 02/27/06
* @see print_nested_tree_txt()
*/
function print_nested_tree_html($id = 1)
{
$sth = SQL_QUERY("SELECT node.id as id, node.name AS name,
(COUNT(parent.name) - 1) as indent
FROM categories AS node, categories
AS parent
WHERE node.lft BETWEEN parent.lft
AND parent.rgt
GROUP BY node.name
ORDER BY node.lft");
if ($sth)
while($row = SQL_ASSOC_ARRAY($sth))
echo ($row['id'] == $id)
?
"<font class='category_highlite'>".
str_repeat(' ', $row['indent']) . $row['name'] .
'</font>'
:
str_repeat(' ',
$row['indent'])."<a
href='?cid=".$row['id']."'>".$row['name'].'</a>'
."<br>\n";
}
?>
------------------------------------->8 snip
8<--------------------------------
> -----Original Message-----
> From: Daevid Vincent [mailto:daevid@daevid.com]
> Sent: Wednesday, March 01, 2006 9:46 PM
> To: 'Php-Db'
> Subject: [PHP-DB] RE: [PHP] "Nested Set Model" or "modified
> preorder tree traversal" [SOLVED]
>
> Since I couldn't find any short and sweet drop in code for
> this, I made my
> own. Here it is in case anyone else finds it helpful. Should be pretty
> straight forward. I use my own mysql wrapper functions, but
> you can pretty
> much figure out what they do and S&R your own.
>
> Hopefully this works as an attachement.
>
> D.Vin
>
> > -----Original Message-----
> > From: Daevid Vincent [mailto:daevid@daevid.com]
> > Sent: Wednesday, February 22, 2006 12:42 PM
> > To: 'Curt Zirzow'; php-general@lists.php.net
> > Subject: RE: [PHP] "Nested Set Model" or "modified preorder
> > tree traversal"
> >
> > Peter Brawley on the mySQL list pointed me at:
> >
> > http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
> >
> > Which uses mySQL 5's procedures and such.
> > I haven't implemented this yet, but it appears to be what I
> > wanted for the
> > most part.
> >
> > > -----Original Message-----
> > > From: Curt Zirzow [mailto:czirzow@gmail.com]
> > > Sent: Tuesday, February 21, 2006 10:58 PM
> > > To: php-general@lists.php.net
> > > Subject: Re: [PHP] "Nested Set Model" or "modified preorder
> > > tree traversal"
> > >
> > > On Tue, Feb 21, 2006 at 09:38:53PM -0800, Daevid Vincent wrote:
> > > > I've been searching the web for the past few hours trying
> > > to find a simple
> > > > drop-in class or functions to implement "Nested Set Model"
> > > or "modified
> > > > preorder tree traversal".
> > >
> > > I actually fell in love of this method of doing trees when I
> > > discovered it about a year ago, when researching a fast way to do
> > > a parent child retrieval.
> > >
> > > >
> > > > I've found several tutorials and related links:
> > > >
> > > >
> > >
> p22g~À *¸Ö“#ªŒ
> http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
> > > > ¤`žE
> > > > =Bñ}¯Ohttp://www.sitepoint.com/article/hierarchical-data-database
> > > >
> > > >
> > >
> > > http://www.zend.com/zend/tut/tutorial-ferrara2.php?article=tut
> > > orial-ferrara2
> > > > &id=3453&open=1&anc=0&view=1
> > > >
> > > > http://simon.incutio.com/archive/2003/06/19/storingTrees
> > > > http://istherelifeafter.com/joecelko.html
> > > >
> >
> > http://www.codeproject.com/cs/database/Trees_in_SQL_databases.asp
> > >
> > > oh i have to add some of these to my list, i didn't have a couple
> > > of them.
> > >
> > > >
> > > > I even found some outdated PEAR DB_NestedSet class from
> > > 2003 that seemed way
> > > > to overly complicated. And some other PHP4_Mysql3MPTTA
> > > class on PHP Classes
> > > > that was equally complicated and written for ancient PHP4
> > > and mySQL 3!!
> > >
> > > yeah, i kind of got that feeling with the PEAR class as well, i
> > > think it was designed that way to be as flexible as possible. I'm
> > > not familiar with the other class, i tend to avoid anything from
> > > PHP Classes.
> > >
> > > >
> > > > Hasn't anyone else done this before (recently)?
> > > > Did everyone just write their own code every time?
> > > > Anyone have some easy to use code that allows for:
> > > > Add, delete, update/rename, select, show tree, bread crumb
> > > display, etc.
> > >
> > > It would be nice to have a tool to manage the functionality. There
> > > will always be the issue with any common tool that is built for
> > > this purpose is how do you relate the table that defines
> the nested
> > > with the table that actually holds the data.
> > >
> > > I believe that why the PEAR and other classes you came across
> > > seemed to be overly complicated. I have found that it is
> easier to
> > > write my own management (as awful as that sounds) for the job at
> > > hand.
>
>
>