Nested Sets - Recursion from space tabbed list

[Rafriend]

Hi all!

I hope someone out there can help! [img src=\"style_emoticons/[#EMO_DIR#]/unsure.gif\" style=\"vertical-align:middle\" emoid=\":unsure:\" border=\"0\" alt=\"unsure.gif\" /]

I've been trying all day to write some code that will take an array of categories and 'echo' out a representation of a nested sets table... I haven't managed it...

my array is as follows (changed spaces for undersores so forum will display):
[code]$array = array('Food, 'Fun Stuff', 'Health' , '__Dental', '____Oral Hygene', 'Other');[/code]
so this gives me:
[0] => Food
[1] => Fun Stuff
[2] => Health
[3] => __Dental
[4] => ____Oral Hygene
[5] => Other

I want to be able to write the output as:
| Category Name | Lft | Rgt |
xxxxxxxx xx xx ......(yes these should be inline)

I've been referring to [a href=\"http://www.sitepoint.com/article/hierarchical-data-database/3\" target=\"_blank\"]this code[/a] from an article on sitepoint.

[code]<?php
function rebuild_tree($parent, $left) {
   // the right value of this node is the left value + 1
   $right = $left+1;

   // get all children of this node
   $result = mysql_query('SELECT title FROM tree '.
                          'WHERE parent="'.$parent.'";');
   while ($row = mysql_fetch_array($result)) {
       // recursive execution of this function for each
       // child of this node
       // $right is the current right value, which is
       // incremented by the rebuild_tree function
       $right = rebuild_tree($row['title'], $right);
   }

   // we've got the left value, and now that we've processed
   // the children of this node we also know the right value
   mysql_query('UPDATE tree SET lft='.$left.', rgt='.
                $right.' WHERE title="'.$parent.'";');

   // return the right value of this node + 1
   return $right+1;
}
?>[/code]
This achieves these results with a database (adjacency list) as the input but I can't seem to get my head around how I would use an array like mine as an input instead.

I've already written a small function that checks whether the 'next' element in the array has more spaces than the current so therefore 'hasChild' but that's as far as i've got...

All attempts at writing the recursion has lead to bloated code and frustrating dead ends...

Any info, advice, questions or discussion would be appreciated!

Thanks

Robert

[ober]

Welcome to the forums.

You may want to help us out by explaining what the "Lft/Rgt" columns will contain.

[Rafriend]

Hi Ober!

Thanks for the fast response!

Sorry if I haven't been clear, I'm trying to achieve a Modified Preorder Tree Traversal output. The best explanation I've found of it is here:
[a href=\"http://www.sitepoint.com/article/hierarchical-data-database/2\" target=\"_blank\"]http://www.sitepoint.com/article/hierarchi...data-database/2[/a]

The Lft/Rgt will contain the data that will allow me to achieve the 'Nested Sets' model (see above link)

[ober]

I'm going to move this to PHP Help since I doubt the N00bs are going to be able to help and I honestly haven't worked with trees in a very long time and I won't be able to help you either. Hopefully some of our more experienced members will pick this up there. If it drifts, just bump it again.

[Rafriend]

Thanks Ober, wasn't sure where to post it initially

[Rafriend]

well, after another long day of trying I still haven't cracked this

I've got as far as getting Children processed properly but can't figure out what I have to do for getting Siblings into the equation:

Also, I realise that the code on the site point forum will only work with 1 parent top node, So Ive changed my array to contain 1 top level element that I call in order to start the process...

So far:

//haven't included the hasKids() function below - this just compares 2 lines in the array and returns true or false if the following line is indented more than the first (therefore "hasKids")


[code]    function rebuild_tree($index, $left) {
        
        global $inputLines;
global $tree_Array;
        
        $right = $left+1;
    
    while ($inputLines[$index]) {
        
        if(hasKids($index)) {
        $right = rebuild_tree($index+1, $right);
        }
        
        // write the data
        $tree_Array[] = "$inputLines[$index] lft:$left rgt:$right";
        
        // return the right value of this node + 1
        return $right+1;
        
        $index++;
    }
    }
    
    $inputLines = array('All', '  Games', '  Health', '    Alternative Medicine', '    Beauty & Style', '    Dental', '      Oral Hygene', '  Home', 'Other');    
    rebuild_tree(0, 1);
    print_r($tree_Array);[/code]
If anyone has any pointers I would love to hear them... so close but yet so far!... [img src=\"style_emoticons/[#EMO_DIR#]/huh.gif\" style=\"vertical-align:middle\" emoid=\":huh:\" border=\"0\" alt=\"huh.gif\" /]

btw, this is a diagram of the the result I want to achieve:

[img src=\"http://i2.sitepoint.com/graphics/sitepoint_numbering.gif\" border=\"0\" alt=\"IPB Image\" /]

[Rafriend]

if anyone's interested in trying it with the above diagram's data, here's an array declaration for it:
[code]$inputLines = array('Food', '  Fruit', '    Red', '      Cherry', '    Yellow', '      Banana', '  Meat', '    Beef', '    Pork'); [/code]

[trq]

Man... I was part way through writting a class to handle nested sets a few months ago, never finished it, quite a complicated little task. Heres where I got up too, not sure if it will help at all, but it might give you some ideas.

Im probably going to ditch it in favour of building it within postGres's PL/pgSQL procedural language instead pf php.
[code]
<?php

/**
* $Id: class.tree.php,v 1.9 2005/12/28 00:13:12 thorpe Exp $
*/

/**
* protect from direct access.
*/
if (!INIT) {
    exit();

}

/**
* the tree object.
*
* this is an intgrial part of the application and stores most of the data
* structure required for the application to run. it impliments a nested set
* hierarchy of trees.
*/
class tree
{

/**
* declare some local variables.
*/
private $db;
private $table;

/* {{{ CONSTRUCT / DECONSTRUCT */

/**
* connect to the database.
*/
function __construct($table=CHLOE_DBTREETABLE) {
    try {
        $this->table = $table;
        $this->db = pg_connect(CHLOE_DBCONN);

    } catch(exception $e) {
        throw new exception("connection to database failed : ".pg_last_error());

    }

}

/**
* close database connection.
*/
function __deconstruct() {
    pg_close($this->db);

}

/* }}} */
/* {{{ HELPERS */

/**
* a simple wrapper for the pg_fetch_object() function.
*/
public function getobject($resource) {
    return pg_fetch_object($resource);

}

/* }}} */
/* {{{ GET METHODS */

/**
* returns the entire tree structure (limited data). starting at the root node,
* and working its way around the outside of the tree.
* @returns result resource
*/
public function gettree() {
    $query = "
                SELECT id,parent,lbound,rbound,lvl,(data).name AS name
                FROM %s
                ORDER BY lbound;";

    if ($result = pg_query($this->db, sprintf($query, $this->table))) {
        return $result;

    }
    return 0;

}

/**
* returns the names of all nodes starting at root and
* leading to desired node. optionaly includes itself as last
* value returned.
*
* @param string name
* @optional bool self
* @returns result resource
*/
public function getpath($name, $self=FALSE) {
    if ($self) {
        $query = "
                    SELECT (data).name AS name
                    FROM %s
                    WHERE lbound <=
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    AND rbound >=
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    ORDER BY lvl;";

            } else {
                $query = "
                    SELECT (data).name AS name
                    FROM %s
                    WHERE lbound <
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    AND rbound >
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    ORDER BY lvl;";

    }

    if ($result = pg_query($this->db, sprintf($query, $this->table, $this->table, $name, $this->table, $name))) {
        return $result;

    }
    return 0;
}

/**
* returns the names of all nodes starting at $name and
* leading back to the root node. optionaly includes itself as
* first value returned.
*
* @param string name
* @optional bool self
* @returns result resource
*/
public function getpathtoroot($name, $self=FALSE) {
    if ($self) {
        $query = "
                    SELECT (data).name AS name
                    FROM %s
                    WHERE lbound <=
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    AND rbound >=
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    ORDER BY lvl DESC;";

    } else {
        $query = "
                    SELECT (data).name AS name
                    FROM %s
                    WHERE lbound <
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    AND rbound >
                        (
                            SELECT lbound
                            FROM %s
                            WHERE (data).name = '%s'
                        )
                    ORDER BY lvl DESC;";

    }

    if ($result = pg_query($this->db, sprintf($query, $this->table, $this->table, $name, $this->table, $name))) {
        return $result;

    }
    return 0;

}

/**
* retrieve a node object.
* the node object contains properties describing all
* of a node attributes, aswell as several helper methods.
* see class.node.php for more details.
*
* @param string $name
* @returns object node
*/
public function getnode($name) {
    try {
        $node = new node($name);

    } catch (exception $e)
        throw new exception("failed to created node object : "$e->getmessage());

    }

}

/**
* determines a nodes kind (or type).
*
* @param string name
* @returns string kind
*/
public function getkind($name) {
    $query = "
                SELECT (properties).kind AS kind
                FROM %s
                WHERE (data).name = '%s';";

    if ($result = pg_query($this->db, sprintf($query, $this->table, $name))) {
        $return = $this->getobject($result);
        return $return->kind;

    }
    return 0;

}

/**
* searches up the path (toward root) until it locates
* a node of kind.
*
* @param string $name
* @param string $kind
* @returns string $name
*/
public function getpreviousofkind($name, $kind) {
    $query = "
                SELECT (data).name AS name
                FROM %s
                WHERE lbound <
                    (
                        SELECT lbound
                        FROM %s
                        WHERE (data).name = '%s'
                    )
                AND rbound >
                    (
                        SELECT lbound
                        FROM %s
                        WHERE (data).name = '%s'
                    )
                AND (properties).kind = '%s'
                ORDER BY lvl DESC LIMIT 1;";

    if ($result = pg_query($this->db, sprintf($query, $this->table, $this->table, $name, $this->table, $name, $kind))) {
        $return = $this->getobject($result);
        return $return->name;

    }
    return 0;

}

/* }}} */
/* {{{ CREATION / DELETION / MOVEMENT METHODS */

public function addroot() {}
public function addnode() {}
public function addsibling() {}
public function deletenode() {}
public function movenode() {}

/* }}} */

}

?>
[/code]
Like I said, its probably not much good to anyone, and its far from complete, but it might give you an idea. I'll see if I can find the db structure and post that aswell.

I dont think the db structure will be of much use unless your using PostGres, but anyway...
[code]
/*
* this is the database setup file for the chloe framework / cms.
* this file will create the postgres database and related table
* structure required to run the framework.
* $Id: chloe.database.sql,v 1.7 2005/12/22 09:36:29 thorpe Exp $
*/

/* {{{ CUSTOM DATATYPES */

-- the actual data stored in the node.
CREATE TYPE nodedata AS (
    name                    VARCHAR(255),                -- the name given to the node.
    content                 TEXT,                       -- the actual data.
    description             VARCHAR(255)                -- a short description of the data.
);

-- permissions of the node.
CREATE TYPE nodepermissions AS (
    own                     INTEGER,                    -- the owner of the node.
    grp                     INTEGER,                    -- the group the node belongs to.
    string                  CHAR(10)                    -- the permission string (-wrxwrxwrx).
);

-- extra node properties.
CREATE TYPE nodeproperties AS (
    created                 TIMESTAMP,                  -- when node was created.
    moded                   TIMESTAMP,                  -- when node was last modified.
    active                  INTEGER,                    -- is node active? 0 / 1
    kind                    VARCHAR(80)                 -- what kind of node is it?
);
/* }}} */
/* {{{ SEQUENCES */

CREATE SEQUENCE tree_id_seq;
CREATE SEQUENCE nodekinds_id_seq;

/* }}} */
/* {{{ TABLE STRUCTURES */

-- holds the actual tree.
CREATE TABLE tree (
    id                      INTEGER DEFAULT nextval('tree_id_seq'),
    parent                  INTEGER NOT NULL,
    lbound                  INTEGER NOT NULL,
    rbound                  INTEGER NOT NULL,
    lvl                     INTEGER NOT NULL,
    rank                    INTEGER NOT NULL,
    data                    nodedata,
    permissions             nodepermissions,
    properties              nodeproperties
);

/* }}} */
/* {{{ DUMMY DATA */

INSERT INTO tree (parent,lbound,rbound,lvl,rank,data,permissions,properties) VALUES (0,1,12,0,1,('root',NULL,NULL),(1,1,'-wr-wr-wr-'),(NOW(),NOW(),1,'root'));
INSERT INTO tree (parent,lbound,rbound,lvl,rank,data,permissions,properties) VALUES (1,2,7,1,1,('home','singlepagearticle',NULL),(1,1,'-wr-wr-wr-'),(NOW(),NOW(),1,'handler'));
INSERT INTO tree (parent,lbound,rbound,lvl,rank,data,permissions,properties) VALUES (1,8,9,1,2,('about','singlepagearticle',NULL),(1,1,'-wr-wr-wr-'),(NOW(),NOW(),1,'handler'));
INSERT INTO tree (parent,lbound,rbound,lvl,rank,data,permissions,properties) VALUES (1,10,11,1,3,('contact','contactform',NULL),(1,1,'-wr-wr-wr-'),(NOW(),NOW(),1,'handler'));
INSERT INTO tree (parent,lbound,rbound,lvl,rank,data,permissions,properties) VALUES (2,3,4,2,1,('an-article','an article attached to home','an article'),(1,1,'-wr-wr-wr-'),(NOW(),NOW(),1,'data'));
INSERT INTO tree (parent,lbound,rbound,lvl,rank,data,permissions,properties) VALUES (2,5,6,2,2,('another-article','another article attached to home','an article'),(1,1,'-wr-wr-wr-'),(NOW(),NOW(),1,'data'));

/* }}} */
[/code]

[Rafriend]

thanks thorpe!

This little project has been driving me crazy, As it's my first attempt at writing a recursion based script I find my brain going to mush when I start thinking through the processes only to get lost on a bermuda triangle of thought...

I'll take a close look at your script and hope that it can shine some light on the matter. If I get anywhere I'll post it.

Robert