PHP RecursiveIteratorIterator и вложенные множества - PullRequest
Новая
       11

PHP RecursiveIteratorIterator и вложенные множества

5 голосов
/ 06 февраля 2009

У меня есть набор объектов в иерархии. Есть верхний «корневой» узел, который имеет дочерние узлы, которые в свою очередь имеют дочерние узлы и т. Д. Я пытаюсь сохранить эту структуру в БД, используя модель вложенного множества, где каждая «сторона» каждого узла пронумерована, чтобы определить иерархия, как в Управление иерархическими данными в MySQL :

alt text
(источник: mysql.com )

Моя проблема - вычисление левого и правого значений. Обычно я использую RecursiveIteratorIterator для итерации по иерархии, но я не могу понять, как вычислять числа, не прибегая к рекурсивной функции, которая анализирует индексную переменную по ссылке.

Есть идеи?

Это, вероятно, бесполезно, но у меня есть (неправильный) код: 

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

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

Как видите, это выглядело бы примерно так: 

Node 
    Node 
    Node

Левое и правое значения: 

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

Когда они должны быть: 

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

Ответы [ 2 ]

4 голосов
/ 06 февраля 2009

Я разобрался, вот решение (упрощенное): 

$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;
}

Это слишком упрощенная версия моего фактического кода, поскольку он просто хранит "побочные" значения в отдельном массиве, но демонстрирует принцип.

Основная идея заключается в том, что вы храните все родительские узлы (отслеживаемые по значению глубины) в массиве и записываете только «левые» значения в вашем цикле. Затем, когда глубина уменьшается, это означает, что вы вернулись в иерархию, поэтому родительский массив разделен, чтобы удалить ненужные, и они зациклены на (в обратном порядке), устанавливая «правильные» значения. Наконец, вам нужно перебрать остальных родителей в конце.

0 голосов
/ 06 февраля 2009

Невозможно решить эту проблему без рекурсии. Вам нужно что-то вроде следующего: 

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
}
...