Давайте сразу же перейдем к основной проблеме, у меня есть вход, подобный этому
$category = array( 'A' => array('left' => 1, 'right' => 8), 'B' => array('left' => 2, 'right' => 3), 'C' => array('left' => 4, 'right' => 7), 'D' => array('left' => 5, 'right' => 6), 'E' => array('left' => 9, 'right' => 10), );
Я хочу, чтобы результат был чем-то вроде этого
$tree = array( array('A', 'B'), array('A', 'C', 'D'), array('E'), );
какая из них лучшая и быстрая функция для петли, хотя входной массив и создать выходной результат, как это?
Работа с вложенным множеством – идеальный случай для рекурсии.
Учитывая ваши данные:
$category = array( 'A' => array('left' => 1, 'right' => 9), 'B' => array('left' => 2, 'right' => 4), 'C' => array('left' => 5, 'right' => 8), 'D' => array('left' => 6, 'right' => 7), 'E' => array('left' => 10, 'right' => 11), );
Ниже будут разбиты ваши вложенные данные набора на правильно вложенный массив в PHP:
function createTree($category, $left = 0, $right = null) { $tree = array(); foreach ($category as $cat => $range) { if ($range['left'] == $left + 1 && (is_null($right) || $range['right'] < $right)) { $tree[$cat] = createTree($category, $range['left'], $range['right']); $left = $range['right']; } } return $tree; } $tree = createTree($category); print_r($tree);
Вывод:
Array ( [A] => Array ( [B] => Array ( ) [C] => Array ( [D] => Array ( ) ) ) [E] => Array ( ) )
Затем вы можете сгладить свое правильное дерево в нужном вам формате со следующим:
function flattenTree($tree, $parent_tree = array()) { $out = array(); foreach ($tree as $key => $children) { $new_tree = $parent_tree; $new_tree[] = $key; if (count($children)) { $child_trees = flattenTree($children, $new_tree); foreach ($child_trees as $tree) { $out[] = $tree; } } else { $out[] = $new_tree; } } return $out; } $tree = flattenTree($tree); print_r($tree);
Вывод:
Array ( [0] => Array ( [0] => A [1] => B ) [1] => Array ( [0] => A [1] => C [2] => D ) [2] => Array ( [0] => E ) )
Если вы не хотите использовать рекурсию:
foreach ($category as $name => $range) { $line[$range['left']] = $name; $line[$range['right']] = $name; } ksort($line); $count = 0; foreach($line as $name) { if ( ! isset($open[$name])) { $open[$name] = true; $result[$name] = true; $count++; } else { unset($open[$name]); if ($count > 0) { $count = 0; $tree[] = array_keys($result); $result = $open; } else { $result = array(); } } }
сforeach ($category as $name => $range) { $line[$range['left']] = $name; $line[$range['right']] = $name; } ksort($line); $count = 0; foreach($line as $name) { if ( ! isset($open[$name])) { $open[$name] = true; $result[$name] = true; $count++; } else { unset($open[$name]); if ($count > 0) { $count = 0; $tree[] = array_keys($result); $result = $open; } else { $result = array(); } } }
Другое решение, без рекурсии (пожалуйста, протестируйте)
$result = array(); foreach($category as $key => $value) { /*Get current row index*/ $i = count($result); if($i == 0) { $result[] = array($key); } else { $iParent = -1; /*Find parent index*/ for($j = count($result[$i-1]) - 1; $j >= 0; $j--) { if($value['left'] > $category[$result[$i-1][$j]]['left'] && $value['right'] < $category[$result[$i-1][$j]]['right']) { $iParent = $j; break; } } if($iParent == -1) { $result[] = array($key);} if($iParent == count($result[$i-1]) - 1) { // append to last $result[$i-1][] = $key; } else { // make new list $result[$i] = array_slice($result[$i-1], 0, $iParent + 1); $result[$i][] = $key; } } } print_r($result);
Существует ошибка с вышеуказанной функцией. Верхняя категория второго массива @tree удаляется. Это исправление:
foreach ($category as $name => $range) { $line[$range['left']] = $name; $line[$range['right']] = $name; } ksort($line); $tree = array(); $count = 0; foreach ($line as $name) { if (!isset($open[$name])) { $open[$name] = true; $count++; } else { if ($count > 0) { $count = 0; $tree[] = array_keys($open); } unset($open[$name]); } }
сforeach ($category as $name => $range) { $line[$range['left']] = $name; $line[$range['right']] = $name; } ksort($line); $tree = array(); $count = 0; foreach ($line as $name) { if (!isset($open[$name])) { $open[$name] = true; $count++; } else { if ($count > 0) { $count = 0; $tree[] = array_keys($open); } unset($open[$name]); } }
Я немного изменил код Стива.
public function createTree($category, $left = 0, $right = null) { $tree = array(); foreach ($category as $cat => $range) { if ($range['clf'] == $left + 1 && (is_null($right) || $range['crt'] < $right)) { $tree[$cat]= array(); $tree[$cat]['title']=$range['title']; if($range['crt']-$range['clf']>1){ $tree[$cat]['sub'] = $this->createTree($category, $range['clf'], $range['crt']); } $left = $range['crt']; } } return $tree; }