Jak sformatować zagnieżdżone dane modelu zestawu w tablicy?

Question

Chodźmy kopać głównego problemu od razu, mam wejście jak ten

$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), 
); 

Chcę wyjście być coś takiego

$tree = array(
    array('A', 'B'), 
    array('A', 'C', 'D'), 
    array('E'), 
); 

który z nich jest najlepszy i szybki funkcję pętli chociaż tablica wejściowa i utworzyć wynik wyjściowy w ten sposób?

Answer 1

Praca z zestawem zagnieżdżonym jest doskonałym przypadkiem dla rekursji.

Biorąc pod uwagę dane:

$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), 
); 

Poniższa złamie zagnieżdżonych zestawów danych w dół do odpowiednio zagnieżdżonego tablicy w 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); 

wyjściowa:

Array 
(
    [A] => Array 
     (
      [B] => Array 
       (
       ) 

      [C] => Array 
       (
        [D] => Array 
         (
         ) 

       ) 

     ) 

    [E] => Array 
     (
     ) 

) 

wtedy może spłaszczyć odpowiednie drzewo do pożądanego formatu za pomocą:

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); 

wyjściowa:

Array 
(
    [0] => Array 
     (
      [0] => A 
      [1] => B 
     ) 

    [1] => Array 
     (
      [0] => A 
      [1] => C 
      [2] => D 
     ) 

    [2] => Array 
     (
      [0] => E 
     ) 

) 

Answer 2

Jeśli nie chcesz korzystać z rekurencji:

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(); 
     } 
    } 
} 

Answer 3

Innym rozwiązaniem, bez rekursji (test proszę)

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

Answer 4

Jest błąd z powyższą funkcją. Górna kategoria drugiej tablicy @tree zostanie usunięta. To jest poprawka:

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]); 
    } 
} 

Answer 5

Ja trochę zmodyfikowałem kod Stivena.

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