current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

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!

share|improve this question
    
And how your program should guess which item is children of which one? –  aram90 Mar 19 '13 at 10:32
    
they are already sorted in right order –  Vit Mar 19 '13 at 10:35
    
Does it have to be recursive? –  2unco Mar 19 '13 at 10:38
    
I supposed so, because we do not know how many depth levels will be in input array –  Vit Mar 19 '13 at 10:41
    
Challenge accepted :D –  2unco Mar 19 '13 at 10:58

2 Answers 2

up vote 0 down vote accepted

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);
share|improve this answer
    
Wow!!! That's it! Thank a lot, you saved my day! =) –  Vit Mar 19 '13 at 11:04
    
Thank you :D I enjoyed solving that one! Good question :) –  2unco Mar 19 '13 at 11:05
    
@aram90 posted a "non recursive" solution downhere. Its also works fine. It'll be interesting to compare which one is faster. –  Vit Mar 19 '13 at 11:14
    
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. –  2unco Mar 19 '13 at 11:24
    
Any way, thanks a lot again! –  Vit Mar 19 '13 at 11:49
up vote 1 down vote

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));
share|improve this answer
    
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 Mar 19 '13 at 11:11
    
How can I mark both answers as correct in this site? Is it possible? –  Vit Mar 19 '13 at 11:12
    
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 –  2unco Mar 19 '13 at 11:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.