Yoanm\CommonDSA\Factory\NAryTreeFactory

Complexity

Total Complexity

6

Size/Duplication

Total Lines	40
Duplicated Lines	0 %

Test Coverage

Coverage

100%

Importance

Changes	1
Bugs	0	Features	0

1 Method

Rating	Name	Duplication	Size	Complexity
A	fromLevelOrderList()	0	29	6

<?php

declare(strict_types=1);

namespace Yoanm\CommonDSA\Factory;

use Yoanm\CommonDSA\DataStructure\NAryTree\Node;

/**
 * @template TNode of Node The actual Node class
 * @template TValue of mixed The actual Node value type
 *
 * @phpstan-type TNodeCreator callable(TValue $v): TNode
 *
 */
class NAryTreeFactory
{
    /**
     * @TODO write example regarding expecting list format !
     *
     * @param mixed[] $list
     * @phpstan-param list<TValue|null> $list
     * @phpstan-param TNodeCreator $nodeCreator
     *
     * @phpstan-return ?TNode
     */
    public static function fromLevelOrderList(array $list, callable $nodeCreator): ?Node
    {
        $tailIdx = count($list) - 1;
        if ($tailIdx < 0 || (0 === $tailIdx && null === $list[0])) {
            return null;
        }

        /** @var \SplQueue<Node> $queue */
        $queue = new \SplQueue();

        $root = call_user_func($nodeCreator, $list[0]); // @phpstan-ignore argument.type
        $queue->enqueue($root);

        $idx = 2; // Should be index 1, but it contains the null value indicating end of children for "root" level !
        while ($idx <= $tailIdx) {
            $parentNode = $queue->bottom(); // =peek() => next value to dequeue from a SplQueue!

            // Append children to the current parent node until a null value is found
            if (null !== $list[$idx]) {
                $parentNode->children[] = $node = call_user_func($nodeCreator, $list[$idx]);
                $queue->enqueue($node);
            } else {
                // Drop current parent node as there is no more children to attach
                $queue->dequeue();
            }
            ++$idx;
        }

        return $root;
    }
}