PHP RecursiveIteratorIterator et les ensembles imbriqués

Question

J'ai un ensemble d'objets dans une hiérarchie. Il y a un nœud "racine" supérieur et qui a des nœuds enfants, qui ont à leur tour des nœuds enfants, etc. J'essaie de sauvegarder cette structure dans une DB en utilisant le modèle de jeu imbriqué, où chaque "côté" de chaque nœud est numéroté pour définir la hiérarchie, comme dans Managing Hierarchical Data in MySQL:

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

Mon problème calcule la gauche et à droite. J'utilise généralement RecursiveIteratorIterator pour itérer sur la hiérarchie, mais je ne peux pas calculer comment calculer les nombres sans recourir à une fonction récursive qui analyse une variable d'index par référence.

Des idées?

Il est probablement inutile, mais c'est le code (incorrect) J'ai actuellement:

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

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

Comme vous pouvez le voir, cela donnerait quelque chose comme ceci:

Node 
    Node 
    Node 

gauche et valeurs de droite:

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

Quand ils devraient être:

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

Answer 1

j'ai tout compris, voici la 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; 
} 

Ceci est h sur la version simplifiée de mon code réel, comme il vient stocke les " côté "valeurs dans un tableau séparé, mais il démontre le principe.

L'idée de base est que vous stockez tous les nœuds parents (suivis par la valeur de profondeur) dans un tableau, et que vous écrivez uniquement les valeurs «gauches» dans votre boucle. Ensuite, lorsque la profondeur diminue, cela signifie que vous avez remonté la hiérarchie, donc le tableau des parents est épissé pour supprimer ceux qui ne sont plus pertinents, et ils sont bouclés (en sens inverse) en définissant les «bonnes» valeurs. Enfin, vous devez faire une boucle sur les parents restants à la fin.

Answer 2

Il n'est pas possible de résoudre ce problème sans récursion. Vous avez besoin de quelque chose comme ce qui suit:

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 
}