PHP RecursiveIteratorIterator e set nidificati

Question

Ho una serie di oggetti in una gerarchia. C'è un nodo "root" in alto e che ha nodi figli, che a loro volta hanno nodi figli ecc. Sto provando a salvare questa struttura in un DB usando il modello del set nidificato, dove ogni "lato" di ciascun nodo è numerato per definire la gerarchia, come in Managing Hierarchical Data in MySQL:

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

il mio problema è il calcolo dei valori di sinistra e destra. In genere utilizzo RecursiveIteratorIterator per scorrere la gerarchia, ma non riesco a calcolare come calcolare i numeri senza ricorrere a una funzione ricorsiva che analizza una variabile di indice per riferimento.

Qualche idea?

è probabilmente di alcuna utilità, ma questo è il codice (errato) attualmente ho:

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

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

Come si può vedere, che darebbe qualcosa di simile:

Node 
    Node 
    Node 

Sinistra e giusti valori di:

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

quando dovrebbero essere:

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

Answer 1

ho capito, ecco la soluzione (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; 
} 

Questo è am over versione semplificata del mio codice vero e proprio, in quanto memorizza solo il " lato "valori in un array separato, ma dimostra il principio.

L'idea di base è di archiviare tutti i nodi padre (tracciati dal valore di profondità) in un array e di scrivere solo i valori "di sinistra" nel ciclo. Quindi, quando la profondità diminuisce significa che hai risalito la gerarchia, quindi l'array dei genitori è giuntato per rimuovere quelli che non sono più rilevanti, e sono ritorti sopra (al contrario) impostando i valori "giusti". Alla fine, dovrai ricorrere ai genitori rimasti alla fine.

Answer 2

Non è possibile risolvere questo problema senza ricorsione. Hai bisogno di qualcosa di simile al seguente:

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 
}