Ordering Ouput Based On Parent/Child Relationship

Question

I'm currently using a something called jstree to create "Folder View" of items on my website. The folders that make up this folder view are saved in the MySQL database as such:

----------------------------------
| id   | folder_name | parent_id |
|------+-------------+-----------|
| 1    | Folder 1    | 0         |
|------+-------------+-----------|
| 2    | Folder 2    | 0         |
|------+-------------+-----------|
| 3    | Sub 1       | 1         |
|------+-------------+-----------|
| 4    | Sub 2       | 1         |
|------+-------------+-----------|
| 5    | Sub 3       | 2         |
|------+-------------+-----------|
| 6    | SubSub 1    | 3         |
----------------------------------

On a different page, I'm looking to display the folders, properly arranged in a dropdown box. The output I hope to achieve inside the dropdown would look something like this:

Folder 1
-- Sub 1
---- SubSub 1
-- Sub 2
Folder 2
-- Sub 3

Any thoughts on how to achieve the above? It seems like some form of recursive function to sort through them would work but I'm struggling to get it worked out. Any help would be greatly appreciated.

Edit:

Here's what I have so far. It appears to be working but it's hard to imagine this is the best way to do it. Any improvement ideas?

$folders = [
    [ "id" => 1, "folder_name" => "Folder 1", "parent_id" => 0 ],
    [ "id" => 2, "folder_name" => "Folder 2", "parent_id" => 0 ],
    [ "id" => 3, "folder_name" => "Sub 1", "parent_id" => 1 ],
    [ "id" => 4, "folder_name" => "Sub 2", "parent_id" => 1 ],
    [ "id" => 5, "folder_name" => "Sub 3", "parent_id" => 2 ],
    [ "id" => 6, "folder_name" => "SubSub 1", "parent_id" => 3 ]
];

function sortedFolders( $parentId, $folders, $depth = 0 )
{
    if( count( $folders ) == 0 )
    {
        return "";
    }

    $str = "";

    for( $i = 0; $i < count( $folders ); $i++ )
    {
        if( $folders[$i]['parent_id'] == $parentId )
        {
            $newFolders = $folders;
            unset( $newFolders[$i] );
            $newFolders = array_values( $newFolders );
            $str .= "<option value='" . $folders[$i]['id'] . "'>";

            for( $j = 0; $j < $depth; $j++ )
            {
                $str .= "-- ";
            }

            $str .= $folders[$i]['folder_name'] . "</option>";
            $str .= sortedFolders( $folders[$i]['id'], $newFolders, ($depth + 1)  );
        }
    }

    return $str;
}

echo sortedFolders( 0, $folders );

Can you share what you have tried? – Jay Blanchard Mar 10 '15 at 18:09 — Jay Blanchard, Mar 10 '15 at 18:09

score 0 · Answer 1 · edited May 23 '17 at 12:12

I think you're having trouble because the data structure you really want is a tree, but the data you have is flat. What I recommend doing is running a recursive algorithm to go through the results of querying this table first, and build a tree with your folder hierarchy represented.

function buildFolderTree(array $elements) {
    // Give a root element
    array_unshift($elements, ['id' => 0, 'folder_name' => 'root']);

    // Recursive closure
    $buildTree = function(array &$elements, $parentId = 0) use (&$buildTree) {
        // Build all the nodes in this branch of the tree
        $branch = [];

        foreach ($elements as $k => $element) {
            if (array_key_exists('parent_id', $element) && 
                $element['parent_id'] === $parentId) {
                $children = $buildTree($elements, $element['id']);
                if ($children) {
                    $element['children'] = $children;
                }

                // No need for this, it's in our tree
                unset($element['parent_id']);
                $branch[] = $element;

                // Don't need to keep looking for this one's parent anymore
                unset($elements[$k]);
            }
        }
        return $branch;
    };

    return $buildTree($elements);
}

There's probably a dozen ways to set the root element, but I decided not to add any special-casing inside the loop itself, and instead just use a recursive closure after putting a root-element at the front of your array. I'm not sure what context you'll be doing this in, and this approach seems the easiest to re-use elsewhere.

For your example, running buildFolderTree($folders) yields the following associative array (json_encoded here for reading convenience):

[
    {
        "id": 1,
        "folder_name": "Folder 1",
        "children": [
            {
                "id": 3,
                "folder_name": "Sub 1",
                "children": [
                    {
                        "id": 6,
                        "folder_name": "SubSub 1"
                    }
                ]
            },
            {
                "id": 4,
                "folder_name": "Sub 2"
            }
        ]
    },
    {
        "id": 2,
        "folder_name": "Folder 2",
        "children": [
            {
                "id": 5,
                "folder_name": "Sub 3"
            }
        ]
    }
]

For me, I'd just stop here -- spit out some JSON, and use that to render in a client-side template like React. Building strings inside your loop like you're trying above will definitely just lead to headaches down the road when you need to refer to this folder tree elsewhere, or modify the way you display those options.

Take a look at this thread for info on building a recursive iterator to run through exactly this sort of thing: How does RecursiveIteratorIterator work in PHP? .

Alternatively (and what's a lot less work, so if this is just used in a couple places do this) you can just use a recursive closure again to render these data:

$renderTreeLevel = function(array $nodes, $depthMarker = '-') use (&$renderTreeLevel) {
    foreach ($nodes as $node) {
        echo '<option value="' . $node['id'] . '">' . $depthMarker . ' ' . $node['folder_name'] . '</option>';
        if (array_key_exists('children', $node)) {
            $renderTreeLevel($node['children'], $depthMarker . '-');
        }
    }
};
?>
<p>some other html...</p>
<select>
<?php $renderTreeLevel($builtTree) ?>
</select>

and that outputs

<select>
<option value="1">- Folder 1</option><option value="3">-- Sub 1</option><option value="6">--- SubSub 1</option><option value="4">-- Sub 2</option><option value="2">- Folder 2</option><option value="5">-- Sub 3</option></select>

Which is nice, since you're keeping the details of how you fetch and build such a tree separate from this much more straight-forward going through the tree and rendering it. In MVC/MVP/MVVM, you'd typically see the former in your model, and the latter in your view. I think the view would be a bit simpler + cleaner with its own Iterator, but like I said earlier, I'd only bother if this is something I planned on using a lot.

Ordering Ouput Based On Parent/Child Relationship

1 Answers1