Build directory tree from flat array of paths in PHP

Question

So, the title maybe confusing but I'm not sure how to word this kind of array structure. It's a tree structure for sure, but as to its creation, that's where I'm hankering. It doesn't appear to follow prototypical recursive array tree building.

I'm trying to create a column directory layout from a flat array of paths, each path being inside its own multi dimensional array.

This array is designed to build a macOS Finder column view style interface, using FinderJS like follows (from the data below):

| elections   > | id                    |           |            |
|               | name                  |           |            |
|               | description         > | field     |            |
|               | dynamic_parent_id   > | field     |            |
|               | method              > | field   > | field_more |

The library requires an array of 'item' objects, in JS, in the following example format:

[{
    label: 'elections',
    children: [{
        label: 'id'
    }, {
        label: 'name'
    }, {
        label: 'description',
        children: [{
            label: 'field'
        }]
    }, {
        label: 'dynamic_parent_id',
        children: [{
            label: 'field'
        }]
    }, {
        label: 'method',
        children: [{
            label: 'field',
            children: [{
                label: 'field_more'
            }]
        }]
    }]
}]

I'm trying to get the above from the following PHP array, this array named $fields:

Array
(
    [0] => Array
        (
            [0] => elections
            [1] => id
        )

    [1] => Array
        (
            [0] => elections
            [1] => name
        )

    [2] => Array
        (
            [0] => elections
            [1] => description
            [2] => field
        )

    [3] => Array
        (
            [0] => elections
            [1] => dynamic_parent_id
            [2] => field
        )

    [4] => Array
        (
            [0] => elections
            [1] => method
            [2] => field
            [3] => field_more
        )

...[and so forth]...
];

which needs to be reformed into the following structure, allowing a json_encode to take place and passed to the client to load:

I've tried creating lookup arrays to calculate and store parent keys to lookup during another build loop by the required structure level, but that isn't working either.

I've tried to re-factor the loops to build a tree based on level initially, but realised that would have to be recursive in order to build the child arrays first or go by level to see if the item already exists before generation on said level.

It seems on the surface fairly simple, as you are constructing an array at each level, but checking if the 'directory' exists yet at that level, if it does, enter it and then check that the next level item exists at that level, creating if it doesn't and then entering that array. Performing the last part recursively, I assume, going down the chain as many times as required for each path.

But at this point, all avenues I've tried I've exhausted and I'm a little stuck on this brain teaser. Any help would be greatly appreciated!

The best I've got so far is this little tree builder I've made, but only for each branch. I'd need another loop I assume to take all the keys at level 1 and merge them together, same with 2, 3, etc...

function buildTree(array $branches): array
{
    if (count($branches)) {
        $branches = array_values($branches);
        $newBranch = $branches[0];
        unset($branches[0]);

        return [
            'label' => $newBranch,
            'children' => $this->buildTree($branches)
        ];
    } else {
        return [];
    }
}

foreach ($fields as $field) {
    $treePieces[] = $this->buildTree($field);
}

print_r($treePieces);

gives the following output:

Array
(
    [0] => Array
        (
            [label] => elections
            [children] => Array
                (
                    [label] => id
                    [children] => Array
                        (
                        )
                )
        )
    [1] => Array
        (
            [label] => elections
            [children] => Array
                (
                    [label] => name
                    [children] => Array
                        (
                        )
                )
        )
    [2] => Array
        (
            [label] => elections
            [children] => Array
                (
                    [label] => description
                    [children] => Array
                        (
                        )
                )
        )
... and so forth ...
)

Which is so close, but not quite there for obvious reasons, it's not traversing down into the directory if the parent already exists. Does it follow typical tree building? I feel it does, but I can't quite see it...

trincot · Accepted Answer

You could do this in two steps:

Create a hierarchy of associative arrays, where the labels are the keys, and nested arrays correspond to children.
Transform that structure to the target structure

Code:

function buildTree($branches) {
    // Create a hierchy where keys are the labels
    $rootChildren = [];
    foreach($branches as $branch) {
        $children =& $rootChildren;
        foreach($branch as $label) {
            if (!isset($children[$label])) $children[$label] = [];
            $children =& $children[$label];
        }
    }
    // Create target structure from that hierarchy
    function recur($children) {
        $result = [];
        foreach($children as $label => $grandchildren) {
            $node = ["label" => $label];
            if (count($grandchildren)) $node["children"] = recur($grandchildren);
            $result[] = $node;
        }
        return $result;
    }
    return recur($rootChildren);
}

Call it likes this:

$tree = buildTree($branches);

The above will omit the children key when there are no children. If you need to have a children key in those cases as well, then just remove the if (count($grandchildren)) condition, and simplify to the following version:

function buildTree($branches) {
    // Create a hierchy where keys are the labels
    $rootChildren = [];
    foreach($branches as $branch) {
        $children =& $rootChildren;
        foreach($branch as $label) {
            if (!isset($children[$label])) $children[$label] = [];
            $children =& $children[$label];
        }
    }
    // Create target structure from that hierarchy
    function recur($children) {
        $result = [];
        foreach($children as $label => $grandchildren) {
            $result[] = ["label" => $label, "children" => recur($grandchildren)];
        }
        return $result;
    }
    return recur($rootChildren);
}

Build directory tree from flat array of paths in PHP

Answers (1)

Related Questions