PHP RecursiveIteratorIterator and Nested Sets

Question

I have a set of objects in a hierarchy. There is the upper “root” node and having child nodes, which, in turn, have child nodes, etc. I am trying to save this structure to the database using a nested collection model, where each "side" of each node is numbered to define a hierarchy, as in Managing hierarchical data in MySQL :

alt text http://dev.mysql.com/tech-resources/articles/hierarchical-data-4.png

My problem is calculating left and right values. I usually use RecursiveIteratorIterator to iterate through the hierarchy, but I cannot decide how to calculate the numbers without resorting to a recursive function that parses the index variable by reference.

Any ideas?

This is probably useless, but this is the (incorrect) code that I currently have:

$iterator = new RecursiveIteratorIterator(
    new Node_List(array($root)),
    RecursiveIteratorIterator::SELF_FIRST);

$i = 0;     
foreach ($iterator as $node) {
    $node->left = ++$i;
    $node->right = ++$i;
}

As you can see, this will give something like this:

Node 
    Node 
    Node 

Left and right meanings:

Node (1, 2)
    Node (3, 4)
    Node (5, 6)

When should they be:

Node (1, 6)
    Node (2, 3)
    Node (4, 5)

Answer 1

I realized here is a solution (simplified):

$iterator = new RecursiveIteratorIterator(
    new Site_Node_List(array($root)),
    RecursiveIteratorIterator::SELF_FIRST);

$sides = array();
$s = 0;
$i = 0;
$parents = array();
foreach ($iterator as $item) {
    $js = array_splice($parents, $depth, count($parents), array($i));
    foreach (array_reverse($js) as $j) {
        $sides[$j]['right'] = ++$s;
    }
    $sides[$i]['left'] = ++$s;
    $i++;
}
foreach (array_reverse($parents) as $j) {
    $sides[$j]['right'] = ++$s;
}

This is a simplified version of my actual code, because it just stores the "side" values ​​in a separate array, but it demonstrates the principle.

, ( ) "" . , , , , , , , ( ), "" . , .

Answer 2

. - :

function tag_recursive($node, &$number) {
    $node->left = $number++;
    foreach ($node->children as &$child) {
        tag_recursive($child, $number);
    }
    $node->right = $number++;
}

function tag($node) {
    $number = 1;
    tag_recursive($node, $number);
    // $number is now highest id + 1
}