PHP RecursiveIteratorIterator i zestawy zagnieżdżone

Question

Mam zestaw obiektów w hierarchii. Istnieje węzeł górny "root", który ma węzły potomne, które z kolei mają węzły potomne itp. Próbuję zapisać tę strukturę w DB przy użyciu modelu zestawu zagnieżdżonego, gdzie każda "strona" każdego węzła jest ponumerowana, aby zdefiniować hierarchia, jak w Managing Hierarchical Data in MySQL:

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

Mój problem polega na obliczaniu wartości lewej i prawej stronie. Zwykle używam programu RecursiveIteratorIterator do iterowania w hierarchii, ale nie mogę obliczyć, jak obliczyć liczby bez odwoływania się do funkcji rekursywnej, która analizuje zmienną indeksu przez odniesienie.

Wszelkie pomysły?

To prawdopodobnie bezużyteczna, ale jest to (niepoprawne) Kod Obecnie mam:

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

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

Jak widać, że dałoby coś takiego:

Node 
    Node 
    Node 

lewo i prawo wartości:

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

kiedy powinny być:

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

Answer 1

I zorientowaliśmy się, oto rozwiązanie (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; 
} 

To am nad uproszczoną wersją mojego aktualnego kodu, jak to tylko przechowuje " "wartości" w osobnej tablicy, ale demonstruje zasadę.

Podstawową ideą jest przechowywanie wszystkich węzłów macierzystych (śledzonych przez wartość głębokości) w tablicy i zapisywanie tylko "lewych" wartości w pętli. Następnie, gdy głębokość maleje, oznacza to, że powróciłeś do hierarchii, więc macierz rodziców jest połączona w celu usunięcia tych, które już nie są istotne, i są zapętlone (odwrotnie), ustawiając "prawidłowe" wartości. Wreszcie, na końcu musisz zapętlić pozostałych rodziców.

Answer 2

Nie można rozwiązać tego problemu bez rekursji. Trzeba coś jak następuje:

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 
}