Smoren\TreeTools\TreeWalker

Complexity

Total Complexity

13

Size/Duplication

Total Lines	84
Duplicated Lines	0 %

Test Coverage

Coverage

100%

Importance

Changes	2
Bugs	0	Features	0

3 Methods

Rating	Name	Duplication	Size	Complexity
B	traverseBreadthFirst()	0	24	7
A	traverseDepthFirst()	0	3	1
A	traverseDepthFirstRecursive()	0	18	5

<?php

declare(strict_types=1);

namespace Smoren\TreeTools;

use ArrayAccess;
use Generator;
use Smoren\TypeTools\MapAccess;

/**
 * @phpstan-type DictAccess = array<string, mixed>|ArrayAccess<string, mixed>|object
 */
class TreeWalker
{
    /**
     * Iterates a tree like a flat collection using depth-first traversal.
     *
     * If $childrenContainerKey is not null looks for children items using by this key only.
     *
     * Otherwise, considers any subarray to contain children.
     *
     * @param iterable<DictAccess> $data
     * @param ?string $childrenContainerKey
     *
     * @return Generator
     */
    public static function traverseDepthFirst(iterable $data, ?string $childrenContainerKey = null): Generator
    {
        yield from static::traverseDepthFirstRecursive($data, $childrenContainerKey);
    }

    /**
     * Iterates a tree like a flat collection using breadth-first traversal.
     *
     * If $childrenContainerKey is not null looks for children items using by this key only.
     *
     * Otherwise, considers any subarray to contain children.
     *
     * @param iterable<DictAccess> $data
     * @param ?string $childrenContainerKey
     *
     * @return Generator
     */
    public static function traverseBreadthFirst(iterable $data, ?string $childrenContainerKey = null): Generator
    {
        $level = 0;
        do {
            $subLevelContainer = [];
            foreach($data as $datum) {
                if($childrenContainerKey !== null) {
                    yield $level => $datum;
                    $childrenContainer = MapAccess::get($datum, $childrenContainerKey);
                } else {
                    if(!is_iterable($datum)) {
                        yield $level => $datum;
                    }
                    $childrenContainer = $datum;
                }
                if(is_iterable($childrenContainer)) {
                    foreach($childrenContainer as $child) {
                        $subLevelContainer[] = $child;
                    }
                }
            }
            $data = $subLevelContainer;
            ++$level;
        } while(count($subLevelContainer));
    }

    /**
     * Recursive helper method for wide traversal.
     *
     * @param iterable<DictAccess> $data
     * @param ?string $childrenContainerKey
     * @param int $initialLevel
     *
     * @return Generator
     */
    protected static function traverseDepthFirstRecursive(
        iterable $data,
        ?string $childrenContainerKey = null,
        int $initialLevel = 0
    ): Generator {
        $level = $initialLevel;
        foreach($data as $datum) {
            if($childrenContainerKey !== null) {
                yield $level => $datum;
                $childrenContainer = MapAccess::get($datum, $childrenContainerKey);
            } else {
                if(!is_iterable($datum)) {
                    yield $level => $datum;
                }
                $childrenContainer = $datum;
            }
            if(is_iterable($childrenContainer)) {
                yield from static::traverseDepthFirstRecursive($childrenContainer, $childrenContainerKey, $level + 1);
            }
        }
    }
}