Array for multidimensional array with depth

Question

I have a big problem (apparently so simple to solve) that I have been trying for more than 24 hours to create a function to turn the array into multidimensional with depth.

My array is

$array = array(
    array("name" => "Root_1", "depth"=> "1"),
    array("name" => "Children","depth"=> "2"),
    array("name" => "Children", "depth"=> "2"),
    array("name" => "Children", "depth"=> "2"),
    array("name" => "Children","depth"=> "3"),
    array("name" => "Children","depth"=> "3"),
    array("name" => "Children","depth"=> "3"),
    array("name" => "Root_2", "depth"=> "1"),
    array("name" => "Children", "depth"=> "2"),
    array("name" => "Children", "depth"=> "2"),
    array("name" => "Children", "depth"=> "2")
)

And I want the output to be:

$array = array(
  array("name" => "Root_1", "depth"=> "1", "children" => array(
        array("name" => "Children", "depth"=> "2", "children" => array()),
        array("name" => "Children", "depth"=> "2", "children" => array()),
        array("name" => "Children", "depth"=> "2", "children" => array(
                array("name" => "Children", "depth"=> "3", "children" => array()),
                array("name" => "Children", "depth"=> "3", "children" => array()),
                array("name" => "Children", "depth"=> "3", "children" => array())
            )
        )), 
  array("name" => "Root_2", "depth"=> "1", "children" => array(
        array("name" => "Children", "depth"=> "2", "children" => array()),
        array("name" => "Children", "depth"=> "2", "children" => array()),
        array("name" => "Children", "depth"=> "2", "children" => array(
                array("name" => "Children", "depth"=> "3", "children" => array()),
                array("name" => "Children", "depth"=> "3", "children" => array()),
                array("name" => "Children", "depth"=> "3", "children" => array())
            )
        )), 
);

What I've tried:

<?php


function createArray($array, $depth) {
$result = array();
$item = array();


if(isset($array["depth"])) {
    if(intval($array["depth"]) >= $depth) {
        array_push($result, $array);
    }
} else {
    foreach($array as $value) {
        $depthToInt = intval($value["depth"]);
        if($depthToInt === $depth) {
            array_push($result, $value);
            $item = $value;
        } else {
            $item["children"] = createArray($value, $item["depth"]);
        }
    }
}
return $result; 

}

Answer 1

I'm a bit late, but if you're interested in an non-recursive solution, here's a simple one-pass-only loop (O(n)):

<?php

function treeify(array $input): array
{
    $result = [];
    $path = [];

    foreach ($input as &$entry) {
        $entry['children'] = [];

        $depth = $entry['depth'] - 1;
        $path = \array_slice($path, 0, $depth);
        $path[] = &$entry;

        0 === $depth
            ? $result[] = &$entry
            : $path[$depth - 1]['children'][] = &$entry;
    }

    return $result;
}

print_r(treeify([
    ['name' => 'Root_1', 'depth' => 1],
        ['name' => 'Children', 'depth' => 2],
        ['name' => 'Children', 'depth' => 2],
        ['name' => 'Children', 'depth' => 2],
            ['name' => 'Children', 'depth' => 3],
            ['name' => 'Children', 'depth' => 3],
            ['name' => 'Children', 'depth' => 3],
                ['name' => 'Children', 'depth' => 4],
        ['name' => 'Children', 'depth' => 2],
    ['name' => 'Root_2', 'depth'=> 1],
        ['name' => 'Children', 'depth' => 2],
        ['name' => 'Children', 'depth' => 2],
        ['name' => 'Children', 'depth' => 2],
            ['name' => 'Children', 'depth' => 3],
    ['name' => 'Root_3', 'depth' => 1],
    ['name' => 'Root_4', 'depth' => 1],
        ['name' => 'Children', 'depth' => 2],
]));

demo: https://3v4l.org/1YkvY

Answer 2

Ok, so clearly we want a recursive solution.

For each item (starting with virtual root) we want to retrieve children. Let's say we get children by filtering out everything that is not children.

What are our criteria for the filter?

1. Child has a depth larger than the parent.
2. Child has an index larger than the parent.
3. Child belongs in a block of items with same depth. Let's shuffle this as child has index smaller than start of next block. Let's call this index smaller than a limit.

So we need:

1. Function that gets children for given index, depth, and limit.
2. Helper function that gets limit for given index.

Here is what I ended up with. I don't think this is perfect (I vaguely doubt my limit logic there), but it's mostly there for your example data.

$array = array(
    array( 'name' => 'Root_1', 'depth' => '1' ),
    array( 'name' => 'Children 1-1', 'depth' => '2' ),
    array( 'name' => 'Children 1-2', 'depth' => '2' ),
    array( 'name' => 'Children 1-2-1', 'depth' => '3' ),
    array( 'name' => 'Children 1-3', 'depth' => '2' ),
    array( 'name' => 'Children 1-3-1', 'depth' => '3' ),
    array( 'name' => 'Children 1-3-2', 'depth' => '3' ),
    array( 'name' => 'Children 1-3-3', 'depth' => '3' ),
    array( 'name' => 'Root_2', 'depth' => '1' ),
    array( 'name' => 'Children 2-1', 'depth' => '2' ),
    array( 'name' => 'Children 2-2', 'depth' => '2' ),
    array( 'name' => 'Children 2-3', 'depth' => '2' ),
    array( 'name' => 'Children 2-3-1', 'depth' => '3' ),
    array( 'name' => 'Children 2-3-2', 'depth' => '3' ),
    array( 'name' => 'Children 2-3-3', 'depth' => '3' ),
);

function getChildren( $array, $index = - 1 ) {

    $depth = isset( $array[ $index ]['depth'] ) ? (int) $array[ $index ]['depth'] : 0;
    $limit = $index === - 1 ? count( $array ) - 1 : findLimit( $array, $index );

    $result = array_filter( $array, function ( $item, $key ) use ( $index, $depth, $limit ) {

        $isDeeper      = (int) $item['depth'] === $depth + 1;
        $isAfter       = $key > $index;
        $isBeforeLimit = $key <= $limit;

        return $isDeeper && $isAfter && $isBeforeLimit;
    }, ARRAY_FILTER_USE_BOTH );

    foreach ( $result as $key => $item ) {
        $result[ $key ]['children'] = getChildren( $array, $key );
    }

    return $result;
}

function findLimit( $array, $index ) {
    $depth   = (int) $array[ $index ]['depth'];
    $limit   = $index;
    $current = $limit + 1;

    while ( isset( $array[ $current ] ) && ( (int) $array[ $current ]['depth'] > $depth ) ) {
        $current ++;
        $limit ++;
    }

    return $limit;
}

$result = getChildren( $array );

var_dump( $result );

Result:

array(2) {
  [0]=>
  array(3) {
    ["name"]=>
    string(6) "Root_1"
    ["depth"]=>
    string(1) "1"
    ["children"]=>
    array(3) {
      [1]=>
      array(3) {
        ["name"]=>
        string(12) "Children 1-1"
        ["depth"]=>
        string(1) "2"
        ["children"]=>
        array(0) {
        }
      }
      [2]=>
      array(3) {
        ["name"]=>
        string(12) "Children 1-2"
        ["depth"]=>
        string(1) "2"
        ["children"]=>
        array(1) {
          [3]=>
          array(3) {
            ["name"]=>
            string(14) "Children 1-2-1"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
        }
      }
      [4]=>
      array(3) {
        ["name"]=>
        string(12) "Children 1-3"
        ["depth"]=>
        string(1) "2"
        ["children"]=>
        array(3) {
          [5]=>
          array(3) {
            ["name"]=>
            string(14) "Children 1-3-1"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
          [6]=>
          array(3) {
            ["name"]=>
            string(14) "Children 1-3-2"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
          [7]=>
          array(3) {
            ["name"]=>
            string(14) "Children 1-3-3"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
        }
      }
    }
  }
  [8]=>
  array(3) {
    ["name"]=>
    string(6) "Root_2"
    ["depth"]=>
    string(1) "1"
    ["children"]=>
    array(3) {
      [9]=>
      array(3) {
        ["name"]=>
        string(12) "Children 2-1"
        ["depth"]=>
        string(1) "2"
        ["children"]=>
        array(0) {
        }
      }
      [10]=>
      array(3) {
        ["name"]=>
        string(12) "Children 2-2"
        ["depth"]=>
        string(1) "2"
        ["children"]=>
        array(0) {
        }
      }
      [11]=>
      array(3) {
        ["name"]=>
        string(12) "Children 2-3"
        ["depth"]=>
        string(1) "2"
        ["children"]=>
        array(3) {
          [12]=>
          array(3) {
            ["name"]=>
            string(14) "Children 2-3-1"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
          [13]=>
          array(3) {
            ["name"]=>
            string(14) "Children 2-3-2"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
          [14]=>
          array(3) {
            ["name"]=>
            string(14) "Children 2-3-3"
            ["depth"]=>
            string(1) "3"
            ["children"]=>
            array(0) {
            }
          }
        }
      }
    }
  }
}