преобразовать Nested Set

22 сентября 2019, 23:00

я через api получаю json который декодирую в массив, этот массив содержит дерево категорий в формате nested set перед тем как записать в базу нужно для каждого элемента определить parent_id(родительский элемент), именно это и не могу сделать. вот пример массива:

[0] => Array
    (
        [id] => 3633
        [name] => Мобильные телефоны и аксессуары
        [left] => 1
        [right] => 22
        [level] => 1
        [elements] => 0
    )
[1] => Array
    (
        [id] => 3638
        [name] => Мобильные телефоны
        [left] => 2
        [right] => 3
        [level] => 2
        [elements] => 84
    )
[2] => Array
    (
        [id] => 3639
        [name] => Портативные зарядные устройства
        [left] => 4
        [right] => 5
        [level] => 2
        [elements] => 42
    )
[3] => Array
    (
        [id] => 3637
        [name] => Кабели
        [left] => 6
        [right] => 7
        [level] => 2
        [elements] => 47
    )
[4] => Array
    (
        [id] => 3634
        [name] => Зарядные устройства
        [left] => 8
        [right] => 9
        [level] => 2
        [elements] => 48
    )
[5] => Array
    (
        [id] => 3642
        [name] => Фитнес трекеры
        [left] => 10
        [right] => 11
        [level] => 2
        [elements] => 25
    )

...

Предварительное решение:

$result = [];
        $i = 1;
        $parent_id = 0;
        foreach($categories as $category)
        {
            foreach ($categories as $cat){
                if($category['left'] > $cat['left'] && $category['right'] < $cat['right']){
                    $parent_id = $cat['id'];
                }
            }
            $result[$i]['id'] = $category['id'];
            $result[$i]['parent_id'] = $parent_id;
            $result[$i]['name'] = $category['name'];
            $i = ++$i;
            $parent_id = 0;
        }
        print_r($result);

Answer 1

В общем говоря, чтобы подытожить комментарии. Возьмем для примера дерево:

Опишем его следующим образом

$data = [
    [ 'id' => 1,  'level' => 1, 'l' => 1,  'r' => 32 ],
    [ 'id' => 2,  'level' => 2, 'l' => 2,  'r' => 9],
    [ 'id' => 3,  'level' => 2, 'l' => 10, 'r' => 23 ],
    [ 'id' => 4,  'level' => 2, 'l' => 24, 'r' => 31],
    [ 'id' => 5,  'level' => 3, 'l' => 3,  'r' => 8],
    [ 'id' => 6,  'level' => 3, 'l' => 11, 'r' => 12],
    [ 'id' => 7,  'level' => 3, 'l' => 13, 'r' => 20],
    [ 'id' => 8,  'level' => 3, 'l' => 21, 'r' => 22],
    [ 'id' => 9,  'level' => 3, 'l' => 25, 'r' => 30],
    [ 'id' => 10, 'level' => 4, 'l' => 4,  'r' => 5],
    [ 'id' => 11, 'level' => 4, 'l' => 6,  'r' => 7],
    [ 'id' => 12, 'level' => 4, 'l' => 14, 'r' => 15],
    [ 'id' => 13, 'level' => 4, 'l' => 16, 'r' => 17],
    [ 'id' => 14, 'level' => 4, 'l' => 18, 'r' => 19],
    [ 'id' => 15, 'level' => 4, 'l' => 26, 'r' => 27],
    [ 'id' => 16, 'level' => 4, 'l' => 28, 'r' => 29],
];

родительские элементы следует искать только среди тех узлов, где уровень на единицу меньше. Так что раскидаем элементы по уровням:

$levels = array_unique(array_column($data, 'level'));
$ldata = [[]];
foreach($data as &$d){
    $ldata[ $d['level'] ][] = $d;
}

Теперь собственно проходим по массиву, берем узел и просматриваем тех кто на уровень выше. Попался подходящий - записываем id, переходим к следующему узлу.

foreach($data as &$d){
    $l = $d['level'];
    foreach($ldata[$l-1] as $ln){
        if($d['l'] > $ln['l'] && $d['r'] < $ln['r']){
            $d['parent_id'] = $ln['id'];
            break;
        }
    }
}