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;

}

@ChinLeung I'm still trying to tweak the code: ideone.com/YhgxdI — Vegetus
– Vegetus, Commented Feb 22, 2019 at 14:54
From your desired output I'm assuming that all depth => 2 are children of Root_1 and Root_2. But how do you differentiate which "Children of depth 2" are assigned the "Children of depth 3" ? — Clément Baconnier
– Clément Baconnier, Commented Feb 22, 2019 at 16:17

Yoshi · Accepted Answer · 2019-02-26 08:22:12Z

3

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

edited Feb 26, 2019 at 8:22

answered Feb 25, 2019 at 8:18

Yoshi

54.8k14 gold badges93 silver badges108 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rarst Over a year ago

Nice! :) I didn't have a good idea for how to implement what you did with $path there.

Yoshi Over a year ago

@Rarst Thanks! I'm still wondering if it can be done without references, but I have a feeling that then multiple loops would be necessary. 😅

Rarst · Accepted Answer · 2019-02-22 19:24:09Z

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?

Child has a depth larger than the parent.
Child has an index larger than the parent.
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:

Function that gets children for given index, depth, and limit.
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) {
            }
          }
        }
      }
    }
  }
}

Collectives™ on Stack Overflow

Array for multidimensional array with depth

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related