Creating a recursive array in PHP

Question

I'm trying to create a recursive array based on string's length : string length is the level of the node. This is actually to build a treeview on Yii framework. Here comes an example...

I've a list of strings :

Array
(
    [0] => A
    [1] => C
    [2] => CC
    [3] => CCC
    [4] => P
    [5] => PP
    [6] => PPP
    [7] => PPPE
    [8] => PS
    [9] => PSA
)

And I want to sort them like that :

Array
(
    [0] => Array
        (
            [text] => A
        )

    [1] => Array
        (
            [text] => C
            [children] => Array
                (
                    [0] => Array
                        (
                            [text] => CC
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [text] => CCC
                                        )
                                )
                        )
                )
        )

    [2] => Array
        (
            [text] => P
            [children] => Array
                (
                    [0] => Array
                        (
                            [text] => PP
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [text] => PPP
                                            [children] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [text] => PPPE
                                                        )
                                                )
                                        )
                                )
                        )

                    [1] => Array
                        (
                            [text] => PS
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [text] => PSA
                                        )
                                )
                        )
                )
        )
)

I know I've to figure out something with recursive functions but I just don't know how to do it, despite the fact i'm trying for days... Did somebody done something like that ? Many thanks...

Answer 1

This should give you what you want:

function &createNodeFromText(&$tree, $text)
{
    if(strlen($text) > 1) {
        //Make sure we have created the parent node(s) we need:
        $parent = &createNodeFromText($tree, substr($text, 0, -1));

        //Create a new tree level for the current node if needed:
        if(!isset($parent["children"])) {
            $parent["children"] = array();
        }
        $currentLevel = &$parent["children"];
    }
    else {
        //New root node:
        $currentLevel = &$tree;
    }

    //Look for the requested node..
    $nodeText = $text;
    $currentNode = null;
    for ($i = 0; $i < count($currentLevel); ++$i) {

        $node = &$currentLevel[$i];
        if($node["text"] === $nodeText)
        {
            $currentNode = &$node;
            break;
        }
    }
    //..and create a new one only if we have to:
    if($currentNode === null) {
        $currentNode = array("text" => $nodeText);
        $currentLevel[] = &$currentNode;
    }

    return $currentNode;
}


$source = array("A", "C", "CC", "CCC", "P", "PP", "PPP", "PPPE", "PS", "PSA");
$final = array();
foreach($source as $s) {
    createNodeFromText($final, $s);
}

print_r($final);

Answer 2

Your question is a peculiar one, and one that I couldn't help but try to wrap my head around.

I do not think you will find that recursion is going to solve your problem. The reason being is that in order to do some recursion you must have your function call itself. By the time the function is invoking itself you have likely done some work on your original array - making it (almost) necessary to pass what is left of the array by reference. The problem in your case is that you want rebuild your array in a manner that will not be achieved by recursion. (At least not without creating a nasty mess of if/else branches to handle your conditions.)

In your situation I would suggest that you work on a class that can categorize as you want based on a number of conditions. Your problem requires that you track some overhead to rebuild your array as you would like. You need to able to check for (but not limited to) things like:

1. Has an index been created for text.
2. Has an index been created for children.
3. Does the item being evaluated need to be assigned to text or children.
4. Am I in the correct level in the array or do I need to traverse backwards?

All of these conditions, coupled with your desired sorting requirements, make this task best suited to a class. Your class could have various fields that would keep track of all those conditions and would allow any recursion that you are using to become more effective. (The good news is that if you build such a class and keep the internal workings within the class, it will port easily to other projects.)

At any rate, here is a recursive function that will almost get what you want.

<?php

$source = array("A", "C", "CC", "CCC", "P", "PP", "PPP", "PPPE", "PS", "PSA");

$rebuilt = array();
function categorize(&$array)
{
    $newArray = array();
    if(isset($array[0])) {
        $newArray["text"] = $array[0];
        array_shift($array);
        if(isset($array[0]) && (strlen($newArray["text"]) < strlen($array[0]))) {
            if(substr_compare($array[0], $newArray["text"], 0, strlen($newArray["text"])) == 0) {
                $newArray["children"] = array(categorize($array));
            }
        }
    }
    return $newArray;
}

//Usage:

$sorted = array();
while(count($source) > 0) {
    $sorted[] = categorize($source);
}
print_r($sorted);

?>

The output will be:

Array
(
    [0] => Array
        (
            [text] => A
        )

    [1] => Array
        (
            [text] => C
            [children] => Array
                (
                    [0] => Array
                        (
                            [text] => CC
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [text] => CCC
                                        )

                                )

                        )

                )

        )

    [2] => Array
        (
            [text] => P
            [children] => Array
                (
                    [0] => Array
                        (
                            [text] => PP
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [text] => PPP
                                            [children] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [text] => PPPE
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

    [3] => Array
        (
            [text] => PS
            [children] => Array
                (
                    [0] => Array
                        (
                            [text] => PSA
                        )

                )

        )

)