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!

And how your program should guess which item is children of which one? — artahian
– artahian, Commented Mar 19, 2013 at 10:32
I supposed so, because we do not know how many depth levels will be in input array — Vit
– Vit, Commented Mar 19, 2013 at 10:41

artahian · Accepted Answer · 2013-03-19 11:00:16Z

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

answered Mar 19, 2013 at 11:00

artahian

2,10314 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Vit Over a year ago

Cool! I'm surprised that it can be done this way, but you proved it. I'll try to compare which one is faster some while later.

Vit Over a year ago

How can I mark both answers as correct in this site? Is it possible?

Bilal Akil Over a year ago

Unfortunately you can't, but you must keep your question in mind: "I'm stuck trying write a recursive function" :( Just up vote the answers such to pass on the recognition :D

Bilal Akil · Accepted Answer · 2013-03-19 10:57:23Z

0

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

answered Mar 19, 2013 at 10:57

Bilal Akil

4,7556 gold badges37 silver badges54 bronze badges

3 Comments

Bilal Akil Over a year ago

Thank you :D I enjoyed solving that one! Good question :)

Vit Over a year ago

@aram90 posted a "non recursive" solution downhere. Its also works fine. It'll be interesting to compare which one is faster.

Bilal Akil Over a year ago

Well this isn't traditional recursion like the typical Fibonacci examples, so it's not exponential time. It is, in fact, linear - as is his - so the difference won't be very noticeable.

Collectives™ on Stack Overflow

converting plain array to multidimensional one using recursion

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related