PHP RecursiveIteratorIterator and nested sets

Answer 1

It is not possible to solve this problem without recursion. You need something like the following:

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
}

Answer 2

I figured it out, here's the solution (simplifed):

$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 am over simplified version of my actual code, as it just stores the "side" values in a separate array, but it demonstrates the principle.

The basic idea is that you store all the parent nodes (tracked by the depth value) in an array, and only write the "left" values in your loop. Then, when the depth decreases it means you've gone back up the hierarchy, so the parents array is spliced to remove the ones that are no longer relevant, and they are looped over (in reverse) setting the "right" values. Finally, you have to loop over the remaining parents at the end.