tree-tools-php

1
<?php
2

3
declare(strict_types=1);
4

5
namespace Smoren\TreeTools;
6

7
use ArrayAccess;
8
use Generator;
9
use Smoren\TypeTools\MapAccess;
10

11
/**
12
 * @phpstan-type DictAccess = array<string, mixed>|ArrayAccess<string, mixed>|object
13
 */
14
class TreeWalker
15
{
16
    /**
17
     * Iterates a tree like a flat collection using depth-first traversal.
18
     *
19
     * If $childrenContainerKey is not null looks for children items using by this key only.
20
     *
21
     * Otherwise, considers any subarray to contain children.
22
     *
23
     * @param iterable<DictAccess> $data
24
     * @param ?string $childrenContainerKey
25
     *
26
     * @return Generator
27
     */
28
    public static function traverseDepthFirst(iterable $data, ?string $childrenContainerKey = null): Generator
29
    {
30
        yield from static::traverseDepthFirstRecursive($data, $childrenContainerKey);
31
    }
32

33
    /**
34
     * Iterates a tree like a flat collection using breadth-first traversal.
35
     *
36
     * If $childrenContainerKey is not null looks for children items using by this key only.
37
     *
38
     * Otherwise, considers any subarray to contain children.
39
     *
40
     * @param iterable<DictAccess> $data
41
     * @param ?string $childrenContainerKey
42
     *
43
     * @return Generator
44
     */
45
    public static function traverseBreadthFirst(iterable $data, ?string $childrenContainerKey = null): Generator
46
    {
47
        $level = 0;
48
        do {
49
            $subLevelContainer = [];
50
            foreach($data as $datum) {
51
                if($childrenContainerKey !== null) {
52
                    yield $level => $datum;
53
                    $childrenContainer = MapAccess::get($datum, $childrenContainerKey);
54
                } else {
55
                    if(!is_iterable($datum)) {
56
                        yield $level => $datum;
57
                    }
58
                    $childrenContainer = $datum;
59
                }
60
                if(is_iterable($childrenContainer)) {
61
                    foreach($childrenContainer as $child) {
62
                        $subLevelContainer[] = $child;
63
                    }
64
                }
65
            }
66
            $data = $subLevelContainer;
67
            ++$level;
68
        } while(count($subLevelContainer));
69
    }
70

71
    /**
72
     * Recursive helper method for wide traversal.
73
     *
74
     * @param iterable<DictAccess> $data
75
     * @param ?string $childrenContainerKey
76
     * @param int $initialLevel
77
     *
78
     * @return Generator
79
     */
80
    protected static function traverseDepthFirstRecursive(
81
        iterable $data,
82
        ?string $childrenContainerKey = null,
83
        int $initialLevel = 0
84
    ): Generator {
85
        $level = $initialLevel;
86
        foreach($data as $datum) {
87
            if($childrenContainerKey !== null) {
88
                yield $level => $datum;
89
                $childrenContainer = MapAccess::get($datum, $childrenContainerKey);
90
            } else {
91
                if(!is_iterable($datum)) {
92
                    yield $level => $datum;
93
                }
94
                $childrenContainer = $datum;
95
            }
96
            if(is_iterable($childrenContainer)) {
97
                yield from static::traverseDepthFirstRecursive($childrenContainer, $childrenContainerKey, $level + 1);
98
            }
99
        }
100
    }
101
}
102