Re: tree structure class

At 18:13 11-10-2001, Wolfram Kriesing wrote:

is there some class which represents a tree structure in php, that is saved in the db? if not i have written one which, if interested, i would like to commit to pear so here is what i have

..

i am still working on performance optimization tell me if interested for pear

I'm interested, but there is a better (much faster) way to use trees in an SQL database using the 'nested-set model'. It's on my to-do list to create a simpler PHP 'api' to use this nested-set model, maybe you would like to take a look at it and implement it? - Arjan (sending this again, this mail did nog get thru the first time?) Articles I found by Celko that invented(?) the nested-set model: http://www.dbmsmag.com/9603d06.html http://www.intelligententerprise.com/001020/celko.shtml Other nested-set related information: http://www.secretagents.com/training/index.cfm?page_id=5 http://research.calacademy.org/taf/proceedings/ballew/ Most of the queries of the above articles and presentations summed up (mySQL compatible): /* Tables and data for these examples */ CREATE TABLE Personnel ( emp char(10) NOT NULL DEFAULT '' , salary decimal(8,2) NOT NULL DEFAULT '0.00' , lft int(11) NOT NULL DEFAULT '0' , rgt int(11) NOT NULL DEFAULT '0' , PRIMARY KEY (emp) ); INSERT INTO Personnel VALUES("Albert","1000.00","1","28"); INSERT INTO Personnel VALUES("Bert","900.00","2","5"); INSERT INTO Personnel VALUES("Charles","900.00","6","19"); INSERT INTO Personnel VALUES("Diane","900.00","20","27"); INSERT INTO Personnel VALUES("Edward","750.00","3","4"); INSERT INTO Personnel VALUES("Fred","800.00","7","16"); INSERT INTO Personnel VALUES("George","750.00","17","18"); INSERT INTO Personnel VALUES("Heidi","800.00","21","26"); INSERT INTO Personnel VALUES("Igor","500.00","8","9"); INSERT INTO Personnel VALUES("Jim","100.00","10","15"); INSERT INTO Personnel VALUES("Kathy","100.00","22","23"); INSERT INTO Personnel VALUES("Larry","100.00","24","25"); INSERT INTO Personnel VALUES("Mary","100.00","11","12"); INSERT INTO Personnel VALUES("Ned","100.00","13","14"); /* Depth of tree */ SELECT P1.emp, COUNT(*) AS level FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt GROUP BY P1.emp; /* Indenting tree (this is the best of it all:) */ SELECT COUNT(P2.emp) AS indentation, P1.emp FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt GROUP BY P1.emp ORDER BY P1.lft; /* All leafs (childless nodes) */ SELECT P.emp FROM Personnel AS P WHERE P.lft = (P.rgt - 1) ORDER BY P.lft; /* All parents of 'Diane' */ SELECT P1.emp, (P1.rgt - P1.lft) AS size, ((P1.rgt - P1.lft)-1)/2 AS siblings FROM Personnel AS P1, Personnel AS P2 WHERE P2.lft BETWEEN P1.lft AND P1.rgt AND P2.emp = 'Diane' /* All childs of 'Diane' */ SELECT P1.emp, (P1.rgt - P1.lft) AS size, ((P1.rgt - P1.lft)-1)/2 AS siblings FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt AND P2.emp = 'Diane'; /* All childs of 'Diane' */ SELECT P1.emp, (P1.rgt - P1.lft) AS size, ((P1.rgt - P1.lft)-1)/2 AS siblings FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt AND P2.emp = 'Diane'; /* Heritage of 'Larry' (ascendency from root to node) */ SELECT P1.emp FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft <= P2.lft AND P1.rgt >= P2.rgt AND P2.emp = 'Larry' -------------------------- Arjan Wekking a.wekking@synantics.nl -------------------------- http://www.synantics.nl/ -------------------------- Synantics B.V. phone +31 (0)78 6 144 211

fax    +31 (0)78 6 144 939

adress Postbus 537

       3300 AM Dordrecht

e-mail info@synantics.nl --------------------------