PHP RecursiveIteratorIterator и вложенные наборы

У меня есть набор объектов в иерархии. Есть верхний «корневой» узел, у которого есть дочерние узлы, которые, в свою очередь, имеют дочерние узлы и т. д. Я пытаюсь сохранить эту структуру в БД, используя модель вложенного набора, где каждая «сторона» каждого узла пронумерована для определения иерархия, как в разделе Управление иерархическими данными в 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)

php recursion iterator nested-sets
person Jack Sleight    schedule 05.02.2009    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Я понял это, вот решение (упрощенное):

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

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

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

person Jack Sleight    schedule 05.02.2009

arrow_upward
0
arrow_downward

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

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
}
person soulmerge    schedule 05.02.2009