3

Based on this question: Getting a modified preorder tree traversal model (nested set) into a <ul>

The logic bellow is used to build an ordered list, but how to do the same with an array?

I want to build a nested array.

// bootstrap loop
$result = '';
$currDepth = -1;  // -1 to get the outer <ul>
while (!empty($tree)) {
  $currNode = array_shift($tree);
  // Level down?
  if ($currNode['depth'] > $currDepth) {
    // Yes, open <ul>
    $result .= '<ul>';
  }
  // Level up?
  if ($currNode['depth'] < $currDepth) {
    // Yes, close n open <ul>
    $result .= str_repeat('</ul>', $currDepth - $currNode['depth']);
  }
  // Always add node
  $result .= '<li>' . $currNode['title'] . '</li>';
  // Adjust current depth
  $currDepth = $currNode['depth'];
  // Are we finished?
  if (empty($tree)) {
    // Yes, close n open <ul>
    $result .= str_repeat('</ul>', $currDepth + 1);
  }
}

print $result;
Community
  • 1
  • 1
Keyne Viana
  • 6,194
  • 2
  • 24
  • 55

1 Answers1

2

Ah, finally something for which references are handy:

<?php
$tree = array(
    array('Cat 1', 'depth' => 0),
    array('Cat 2', 'depth' => 1),
    array('Cat 3', 'depth' => 1),
    array('Cat 4', 'depth' => 2),
    array('Cat 5', 'depth' => 1),
    array('Cat 6', 'depth' => 2),
    array('Cat 7', 'depth' => 3),
    array('Cat 8', 'depth' => 1)
);
//same as before
$currDepth = -1;

//initilialize result
$result = array();

//create path structure for depths
$path = array();

//create 'root' node
$olditem = array('children'=> &$result);


foreach($tree as $item){
    if($item['depth'] > $currDepth){
        //remove possible old reference (old depth of other branch
        if(isset($path[$item['depth']])) unset($path[$item['depth']]);

        //make sure we have an array entry
        if(!isset($olditem['children'])) $olditem['children'] = array();

        //acquire target
        $path[$item['depth']] = &$olditem['children'];
    }
    if($item['depth'] != $currDepth) unset($olditem);
    //set correct target
    $currDepth = $item['depth'];
    //add item
    $path[$currDepth][] = &$item;
    //copy & remove reference
    $olditem = &$item;
    unset($item);
}
//always nice to clean up reference bombs:
unset($path);
unset($olditem);

var_dump($result);
?>
Wrikken
  • 69,272
  • 8
  • 97
  • 136
  • Thanks a lot! I've tested and works fine, now I'm trying to understand. Does the first unset on the path variable make useless its declaration outside the loop? $path = array(0 => array('children'=> &$result)); AND if(isset($path[$item['depth']])) unset($path[$item['depth']]); At the first loop it will be deleted. – Keyne Viana Sep 14 '10 at 18:30
  • Hmm, you're right, that one can go, it was superseded by the `$olditem` I edited in later. I'll edit the answer just the slightest in a moment. – Wrikken Sep 14 '10 at 18:38
  • When you unset $olditem why this doesn't affect $path[$item['depth']] as it's passed by reference? I'm confunse on that part. Seems like this doesn't affect the final result, in other words, if I change, the reference value is affected, but not if I unset. – Keyne Viana Sep 15 '10 at 13:53
  • Hmm, step-by-step reference explaining is quite some work, I'll see what I can do later this evening. – Wrikken Sep 15 '10 at 16:58
  • This is really elegant. I'm still trying to wrap my head around how it works. Care to offer a walkthrough? – Shaan Feb 09 '12 at 19:26
  • It boils down to `path` being an array of references to child-items array at depth N, as a list of 'shortcuts' to the final location in the `$result` array. The discarding portions of `$path` if we know we are in a new 'branch' to make way for new ones might be a bit obscure. The first part of the loop (`$item['depth'] > $currDepth`) is about (1) unsetting 'stale' portions of the path (if the new depth is deeper then the old one, the item in `$path` at that new depth is stale (2) if the item has no place to put in `children`, make it. Second part is getting the current item in `$path`. – Wrikken Feb 09 '12 at 20:15