PHP RecursiveIteratorIterator et ensembles imbriqués

Question

J'ai un ensemble d'objets dans une hiérarchie. noeud Il y a un top « racine » et qui a des nœuds enfants, qui ont à leur tour des nœuds enfants, etc. Je suis en train de sauver cette structure dans un DB en utilisant le modèle de jeu imbriqué, où chaque « côté » de chaque noeud est numéroté pour définir la hiérarchie, comme dans Gestion des données hiérarchique dans MySQL :

_{(source: mysql.com )}

Mon problème calcule la gauche et à droite. J'utilise généralement RecursiveIteratorIterator itérer sur la hiérarchie, mais je ne peux pas travailler sur la façon de calculer les chiffres sans avoir recours à une fonction récursive qui analyse une variable d'index par référence.

Toutes les idées?

Il est probablement inutile, mais cela 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 

Les valeurs de gauche et de droite:

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

Quand ils doivent être:

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

Answer 1

Je me suis dit dehors, 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;
}

am plus version simplifiée de mon code réel, comme il vient stocke les « côté » des valeurs dans un tableau distinct, 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 écrivez uniquement les valeurs de « gauche » dans votre boucle. Ensuite, lorsque la profondeur diminue, cela signifie que vous avez retourné la hiérarchie, de sorte que le tableau des parents est épissé pour éliminer ceux qui ne sont plus pertinentes, et ils sont bouclées sur (en sens inverse) définissant les valeurs « droite ». Enfin, vous devez boucler sur les autres parents à la fin.

Answer 2

Il est impossible de résoudre ce problème sans récursivité. 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
}