PHP RecursiveIteratorIterator y conjuntos anidados

Question

Tengo un conjunto de objetos en una jerarquía. Hay un nodo "raíz" superior y tiene nodos secundarios, que a su vez tienen nodos secundarios, etc. Estoy tratando de guardar esta estructura en una base de datos usando el modelo de conjunto anidado, donde cada "lado" de cada nodo está numerado para definir la jerarquía, como en Managing Hierarchical Data in MySQL:

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

Mi problema es el cálculo de los valores de izquierda y derecha. Normalmente utilizo RecursiveIteratorIterator para iterar sobre la jerarquía, pero no puedo calcular cómo calcular los números sin recurrir a una función recursiva que analiza una variable de índice por referencia.

¿Alguna idea?

es probable que sea de ninguna utilidad, pero este es el código (incorrecta) En este momento tengo:

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

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

Como se puede ver, que daría algo como esto:

Node 
    Node 
    Node 

izquierda y valores correctos de:

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

cuando deberían ser:

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

Answer 1

lo he descubierto, aquí está la solución (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; 
} 

Se trata de la mañana sobre la versión simplificada de mi código real, ya que sólo se almacena el " "lado" valores en una matriz separada, pero demuestra el principio.

La idea básica es que almacene todos los nodos principales (seguidos por el valor de profundidad) en una matriz, y solo escriba los valores "izquierdos" en su ciclo. Luego, cuando la profundidad disminuye, significa que ha vuelto a la jerarquía, por lo que la matriz de padres se empalma para eliminar los que ya no son relevantes y se vuelven a en bucle (en reversa) configurando los valores "correctos". Finalmente, tienes que pasar por encima de los padres restantes al final.

Answer 2

No es posible resolver este problema sin recursividad. Es necesario algo como lo siguiente:

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 
}