Build a tree from a flat array in PHP

Question 1

I've looked around the internet and haven't quite found what I'm looking for. I have a flat array with each element containing an 'id' and a 'parent_id'. Each element will only have ONE parent, but may have multiple children. If the parent_id = 0, it is considered a root level item. I'm trying to get my flat array into a tree. The other samples I have found only only copy the element to the parent, but the original still exists.

EDIT

Each element of the starting array is read from a separate XML file. The file itself will have '0' as the value for parent_id if it doesn't have a parent. The keys are actually strings.

I'm sorry for the confusion earlier. Hopefully this is more clear:

/EDIT

My starting array:

Array
(
    [_319_] => Array
        (
            [id] => 0
            [parent_id] => 0
        )

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
        )

    [_321_] => Array
        (
            [id] => _321_
            [parent_id] => _320_
        )

    [_322_] => Array
        (
            [id] => _322_
            [parent_id] => _321_
        )

    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
        )

    [_324_] => Array
        (
            [id] => _324_
            [parent_id] => _323_
        )

    [_325_] => Array
        (
            [id] => _325_
            [parent_id] => _320_
        )
)

The resulting array after the tree is made:

Array
(
    [_319_] => Array
        (
            [id] => _319_
            [parent_id] => 0
        )

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
            [children] => Array
                (
                    [_321_] => Array
                        (
                            [id] => _321_
                            [parent_id] => _320_
                            [children] => Array
                                (
                                    [_322_] => Array
                                        (
                                            [id] => _322_
                                            [parent_id] => _321_
                                        )
                                )
                        )
                    [_325_] => Array
                        (
                            [id] => _325_
                            [parent_id] => _320_
                        )
                )
    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
            [children] => Array
                (
                    [_324_] => Array
                        (
                            [id] => _324_
                            [parent_id] => _323_
                        )
                )
        )

Any help / guidance is greatly appreciated!

Some code I have so far:


        function buildTree(array &$elements, $parentId = 0) {
        $branch = array();

        foreach ($elements as $element) {
            if ($element['parent_id'] == $parentId) {
                $children = $this->buildTree($elements, $element['id']);
                if ($children) {
                    $element['children'] = $children;
                }
                $branch[] = $element;
            }
        }

        return $branch;
    }

Question 2

You forgot the unset() in there bro.

function buildTree(array &$elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($elements[$element['id']]);
        }
    }
    return $branch;
}

Question 3

The first key is to sort the SQL results by the number of ancestors. I did this in PHP since I avoid the complexities of multi-digit numbers.

This provides a list of nodes in an order in which they can be validly inserted.

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

    [4] => Array
        (
            [0] => 4
            [1] => 1
        )

    [2] => Array
        (
            [0] => 2
            [1] => 1
        )

    [3] => Array
        (
            [0] => 3
            [1] => 1
            [2] => 2
        )

)

At this point, I don't care about the keys, only the lists of ancestors. The path through the tree can be found between the intersection of available nodes and the remaining ancestors.

  function add_node($ancestors, &$tree) {
    if (count($ancestors) == 1) {
      $tree[array_pop($ancestors)] = array();
      return;
    }   
    $next_node = array_intersect($ancestors, array_keys($tree));
    $this->add_node(
        array_diff($ancestors, $next_node) , 
        $tree[array_pop($next_node)]
        );  
  }

Question 4

The best way would be to reformat the array so the keys were the directories, and the array values were arrays containing file names, like so:

$array = array( ..);
$reformatted = array();
foreach( $array as $k => $v) {
    list( $key, $value) = explode( '|', $v);
    if( !isset( $reformatted[$key])) 
        $reformatted[$key] = array();
    $reformatted[$key][] = $value;
}

Then you just have to iterate over the new array, like so:

foreach( $reformatted as $dir => $files) {
    echo $dir . "n";
    foreach( $files as $file)
        echo "t" . $file . "n";
}

This outputs:

dir0
    file0.txt
    file1.txt
dir1
    file2.txt
    filea.txt
dir2
    fileb.txt

Note that this will only work for plain text environment (such as <pre></pre>, like in the demo). Otherwise, you'll need to use <br /> instead of n for line breaks, or use an ordered or unordered list.

For HTML output, use this, whose output can be seen here

echo '<ul>';
foreach( $reformatted as $dir => $files) {
    echo "<li>$dir</li>";
    echo '<ul>';
    foreach( $files as $file)
        echo "<li>$file</li>";
    echo '</ul>';
}
echo '</ul>';

Generates:

dir0

file0.txt
file1.txt

dir1

file2.txt
filea.txt

dir2

fileb.txt

For your updated array, here is the solution:

$reformatted = array(); $weights = array();
foreach( $paths as $k => $v) {
    list( $key, $value) = explode( '|', $v[0]);

    if( !isset( $reformatted[$key])) 
        $reformatted[$key] = array();

    if( !isset( $weights[$key]))
        $weights[$key] = 0;

    $reformatted[$key][] = array( $value, $v[1]);
    $weights[$key] += $v[1];    
}

foreach( $reformatted as $dir => $files) {
    echo $dir . ' (' . $weights[$dir] . ")n";
    foreach( $files as $file)
        echo "t" . $file[0] . ' (' . $file[1] . ")n";
}

This outputs:

dir0 (900)
    file0.txt (400)
    filea.txt (500)
dir1 (1300)
    file1.txt (600)
    fileb.txt (700)
dir2 (700)
    filec.txt (700)

I'll leave it up to you to translate that into HTML if necessary.

Question 5

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

Question 6

Explanations can be found as inline comments. This function provides your exact desired output. Also pay attention to the query that I've rewritten to set up $resultset.

Code: (Demo)

function findParent(&$array,$parentid=0,$childarray=[]){  // make $array modifiable
    foreach($array as $i=>&$row){                         // make $row modifiable
        if($parentid){                                    // if not zero
            if($row['id']==$parentid){                    // found parent
                $row['nodes'][]=$childarray;              // append child to parent's nodes subarray
            }elseif(isset($row['nodes'])){                // go down rabbit hole looking for parent
                findParent($row['nodes'],$parentid,$childarray);  // look deeper for parent while preserving the initial parent_id and row
            }                                             // else continue;
        }elseif($row['parent_id']){                       // child requires adoption
            unset($array[$i]);                            // remove child from level because it will be store elsewhere and won't be its own parent (reduce iterations in next loop & avoid infinite recursion)
            findParent($array,$row['parent_id'],$row);    // look for parent using parent_id while carrying the entire row as the childarray
        }                                                 // else continue;
    }
    return $array;                                        // return the modified array
}


// $db->query('SELECT id,name_a AS name,parent_id FROM accounts_tree ORDER BY id');
// for($resultset=[]; $row=$res->fetch_assoc(); $resultset[]=$row);  // inspired by: http://php.net/manual/en/mysqli-result.fetch-assoc.php#112924

$resultset=[
    ['id'=>1,'name'=>'folder 1','parent_id'=>0],
    ['id'=>2,'name'=>'folder 2','parent_id'=>0],
    ['id'=>3,'name'=>'sub 1-1','parent_id'=>1],
    ['id'=>4,'name'=>'sub 2-1','parent_id'=>2],
    ['id'=>5,'name'=>'Sub 1-1-1','parent_id'=>3],
    ['id'=>6,'name'=>'folder 3','parent_id'=>0],
    ['id'=>7,'name'=>'sub 1-1-1-1','parent_id'=>5]
];

print_r(findParent($resultset));

Output:

Array
(
    [0] => Array
        (
            [id] => 1
            [name] => folder 1
            [parent_id] => 0
            [nodes] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [name] => sub 1-1
                            [parent_id] => 1
                            [nodes] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 5
                                            [name] => Sub 1-1-1
                                            [parent_id] => 3
                                            [nodes] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [id] => 7
                                                            [name] => sub 1-1-1-1
                                                            [parent_id] => 5
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

    [1] => Array
        (
            [id] => 2
            [name] => folder 2
            [parent_id] => 0
            [nodes] => Array
                (
                    [0] => Array
                        (
                            [id] => 4
                            [name] => sub 2-1
                            [parent_id] => 2
                        )

                )

        )

    [5] => Array
        (
            [id] => 6
            [name] => folder 3
            [parent_id] => 0
        )

)

Build a tree from a flat array in PHP

Answers

php,arrays,tree,flat