converting plain array to multidimensional one using recursion

Question

everyone!

I'm stuck trying write a recursive function. =( This is my function, which, as I expected, will turn my plain array into multidimensional one.

function BuildTree($src, $index=0) {
    foreach ($src as $index=>$curentItem) {
        $nextItem = (is_array($src[$index+1]))?$src[$index+1]:false;
        unset($src[$index]);
        if ($nextItem['d']==$curentItem['d']) $brunchArray[] = $curentItem['n'];
        if ($nextItem['d']>$curentItem['d']) $brunchArray['childrens'] = BuildTree($src, $index);
        if (!$nextItem || $nextItem['d']<$curentItem['d']) return $brunchArray;
    }
}

Input array is something like this:

$input = array (
array(
        'n' => 'Articles',
        'd' => 0
    ),
array(
        'n' => 'Article 1',
        'd' => 1
    ),
array(
        'n' => 'Books',
        'd' => 0
    ),
array(
        'n' => 'Book 1',
        'd' => 1
    ),
array(
        'n' => 'Book 2',
        'd' => 1
    ),
array(
        'n' => 'Chapter 1',
        'd' => 2
    ),
array(
        'n' => 'Chapter 2',
        'd' => 2
    )
);

And I want it to be converted into this:

array (
    array(
            'n' => 'Articles',
            'd' => 0,
            'childrens' => array (
                array(
                        'n' => 'Article 1',
                        'd' => 1
                    ),
            )
        ),
    array(
            'n' => 'Books',
            'd' => 0,
            'childrens' => array (
                array(
                        'n' => 'Book 1',
                        'd' => 1
                    ),
                array(
                        'n' => 'Book 2',
                        'd' => 1
                        'childrens' => array (
                            array(
                                    'n' => 'Chapter 1',
                                    'd' => 2
                                ),
                            array(
                                    'n' => 'Chapter 2',
                                    'd' => 2
                                )
                        )
                    )
            )
        )
)

I already spent three hours trying to solve this. =( Any help will be highly appreciated!

Answer 1

Here is a solution without recursion:

function convert($arr) {
    $stack = array();
    $output = array();
    $arr[] = array('d' => -1); // Dummy record at the end
    for($i = 0; $i < count($arr); $i++) {
        while(!empty($stack) && $stack[count($stack) - 1]['d'] > $arr[$i]['d']) {
            $current_d = $stack[count($stack) - 1]['d'];
            $children = array();
            while(!empty($stack) && $stack[count($stack) - 1]['d'] >= $current_d) {
                $children[] = array_pop($stack);
            }
            $children = array_reverse($children);
            if(empty($stack)) {
                foreach($children as $child) {
                    $output[] = $child;
                }
            } else {
                $stack[count($stack) - 1]['children'] = $children;
            }
        }
        $stack[] = $arr[$i];
    }
    return $output;
}

$input = array (
array(
        'n' => 'Articles',
        'd' => 0
    ),
array(
        'n' => 'Article 1',
        'd' => 1
    ),
array(
        'n' => 'Books',
        'd' => 0
    ),
array(
        'n' => 'Book 1',
        'd' => 1
    ),
array(
        'n' => 'Book 2',
        'd' => 1
    ),
array(
        'n' => 'Chapter 1',
        'd' => 2
    ),
array(
        'n' => 'Chapter 2',
        'd' => 2
    )
);

var_dump(convert($input));

Answer 2

Using the same $input:

$output = array();

function buildTree(&$input, &$output, &$current, $level = 0) {
    if(!$input)
        return;
    $next = array_shift($input);
    if($next['d'] == $level) {
        $current[] = $next;
        return buildTree($input, $output, $current, $level);
    } else if($next['d'] == $level + 1) {
        $current[count($current) - 1]['childrens'] = array($next);
        return buildTree($input, $output, $current[count($current) - 1]['childrens'], $level + 1);
    } else {
        $output[] = $next;
        return buildTree($input, $output, $output, 0);
    }
}

buildTree($input, $output, $output);

var_dump($output);