PHP parent/child iteration in single-dimension array

Question

I am at a little bit of a loss as to how to approach this, I suspect foreach is not the right answer, and I am aware of the existence of array_walk() and RecursiveArrayIterator, but I have no real-world experience of using either, so I could do with a bit of a pointer in the right direction. (I am working with PHP 7.1.9 if it makes any difference to the answer).

Source data

I have a single-dimension array that contains a parent/child tree of objects. You can assume the tree has unknown and variable nesting depth. A basic example would look like the following :

$sampleParent=array("id"=>101,"level"=>1,"parent_id"=>1,"name"=>"parent","otherparam"=>"bar");
$sampleChildD1=array("id"=>234,"level"=>2,"parent_id"=>101,"name"=>"level1","otherparam"=>"bar");
$sampleChildD2=array("id"=>499,"level"=>3,"parent_id"=>234,"name"=>"level2","otherparam"=>"bar"); 
$sampleTree=array($sampleParent,$sampleChildD1,$sampleChildD2);

Desired output

The ultimate goal is to output HTML lists (i.e. <ul><li></li></ul>), one list per parent. Nesting of children achieved by nesting <ul> tags. So for my example above :

<ul>
<li>
<a href="#">parent</a>
</li>
    <ul>
    <li>
    <a href="#">level1</a>
        <ul>
        <li>
        <a href="#">level2</a>
        </li>
        </ul>
    </li>
    </ul>
</ul>

What have you tried so far? How can a tree be stored in a single-dimension array? Is there always only one child per parent? — KIKO Software, Sep 08 '17 at 19:19
$sampleTree at the time of you doing '$sampleTree=array($sampleParent,$sampleChildD1,$sampleChildD2);' becomes an array with arrays or a multidimensional arrays. This isn't to help with your issue as much to clarify that during the time of processing / parsing the sampleTree you are no longer dealing with a single dimensional array. — Eric Mayfield, Sep 08 '17 at 19:47

score 1 · Answer 1 · answered Sep 08 '17 at 20:01

May I suggest to do this in an OOP manner? I'd create an object with the properties and a list of children. If you like, you could also add a link from a child to its parent, as in this sample

class TreeNode {
  // string
  public $name;
  // integer
  public $id;
  // TreeNode
  public $parent;
  // TreeNode[]
  public $children;
}

With this structure, it should be very straight forward to iterate it using foreach.

score 1 · Accepted Answer · answered Sep 08 '17 at 21:54

You can extend RecursiveArrayIterator:

class AdjacencyListIterator extends RecursiveArrayIterator
{
    private $adjacencyList;

    public function __construct(
        array $adjacencyList,
        array $array = null,
        $flags = 0
    ) {
        $this->adjacencyList = $adjacencyList;

        $array = !is_null($array)
            ? $array
            : array_filter($adjacencyList, function ($node) {
                return is_null($node['parent_id']);
            });

        parent::__construct($array, $flags);
    }

    private $children;

    public function hasChildren()
    {
        $children = array_filter($this->adjacencyList, function ($node) {
            return $node['parent_id'] === $this->current()['id'];
        });

        if (!empty($children)) {
            $this->children = $children;
            return true;
        }

        return false;
    }

    public function getChildren()
    {
        return new static($this->adjacencyList, $this->children);
    }
}

Then you can traverse this iterator with RecursiveIteratorIterator, or you can extend the former to somewhat semi-automatically decorate the tree with HTML:

class UlRecursiveIteratorIterator extends RecursiveIteratorIterator
{
    public function beginIteration()
    {
        echo '<ul>', PHP_EOL;
    }

    public function endIteration()
    {
        echo '</ul>', PHP_EOL;
    }

    public function beginChildren()
    {
        echo str_repeat("\t", $this->getDepth()), '<ul>', PHP_EOL;
    }

    public function endChildren()
    {
        echo str_repeat("\t", $this->getDepth()), '</ul>', PHP_EOL;
        echo str_repeat("\t", $this->getDepth()), '</li>', PHP_EOL;
    }
}

Having this two classes you can iterate your tree like this:

$iterator = new UlRecursiveIteratorIterator(
    new AdjacencyListIterator($sampleTree),
    RecursiveIteratorIterator::SELF_FIRST
);

foreach ($iterator as $leaf) {
    echo str_repeat("\t", $iterator->getDepth() + 1);
    echo '<li>', '<a href="#">', $leaf['name'], '</a>';
    echo $iterator->hasChildren() ? '' : '</li>', PHP_EOL;
}

Here is working demo.

Take a notice, that str_repeat and PHP_EOL used here only for presentation purpose and should be removed in real life code.

PHP parent/child iteration in single-dimension array

2 Answers2