PHP RecursiveIteratorIterator und verschachtelte Sätze

Question

Ich habe eine Reihe von Objekten in einer Hierarchie. Es gibt einen obersten "root" -Knoten, der untergeordnete Knoten hat, die wiederum untergeordnete Knoten usw. haben. Ich versuche, diese Struktur unter Verwendung des geschachtelten Mengenmodells in einem DB zu speichern, wobei jede "Seite" jedes Knotens zur Definition nummeriert wird die Hierarchie, wie in Managing Hierarchical Data in MySQL:

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

Mein Problem der linken und rechten Werte berechnet wird. Normalerweise verwende ich RecursiveIteratorIterator, um über die Hierarchie zu iterieren, aber ich kann nicht herausfinden, wie man die Zahlen berechnet, ohne auf eine rekursive Funktion zurückzugreifen, die eine Indexvariable als Referenz analysiert.

Irgendwelche Ideen?

Es ist wahrscheinlich nichts, aber dies ist die (falsche) Code, den ich derzeit haben:

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

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

Wie Sie sehen können, dass so etwas wie dieses geben würde:

Node 
    Node 
    Node 

Linke und richtige Werte von:

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

Wenn sie sein sollten:

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

Answer 1

ich es herausgefunden, hier ist die Lösung (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; 
} 

Dies ist am über vereinfachte Version meiner eigentlichen Code, wie es die nur speichert " Seite "Werte in einem separaten Array, aber es zeigt das Prinzip.

Die Grundidee ist, dass Sie alle übergeordneten Knoten (nach dem Tiefenwert) in einem Array speichern und nur die "linken" Werte in Ihre Schleife schreiben. Dann, wenn die Tiefe abnimmt, bedeutet das, dass Sie die Hierarchie wieder hochgefahren haben, also wird das Eltern-Array gespleißt, um diejenigen zu entfernen, die nicht mehr relevant sind, und sie werden umgekehrt (umgekehrt) und die "richtigen" Werte eingestellt. Schließlich müssen Sie am Ende die restlichen Eltern durchlaufen.

Answer 2

Es ist nicht möglich, dieses Problem ohne Rekursion zu lösen. Sie brauchen etwas wie folgt aus:

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 
}