README

灵活的树结构
树构建器（物化路径树、递归树、数据包装器）
树遍历迭代器，过滤器迭代器。

💿 composer require dakujem/oliva

此包是 oliva/tree 的现代重实现。

树

树是一种图的形式，具体来说是有向无环图（DAG）。
树中的每个节点最多有一个父节点和任意数量的子节点。
没有父节点的节点称为根。
没有子节点的节点称为叶子。

更多内容请参阅维基百科：树（数据结构）。

Oliva 树由实现 TreeNodeContract 的节点实例组成。

use Dakujem\Oliva\TreeNodeContract;

构建器

Oliva 提供了 树构建器，这些是用于从非结构化数据构建结构化树的类。数据通常以可迭代集合的形式存在，通常是 SQL 查询、API 调用、YAML 配置等的结果。

$tree = (new TreeBuilder(
    node: fn(mixed $data) => new Node($data), // A node factory.
))->build(
    input: $anyDataCollection,                // An iterable collection to build a tree from.
);

构建器非常灵活，允许通过 节点工厂 参数创建任何节点实例。
最简单的工厂可能看起来像这样

fn(mixed $data) => new \Dakujem\Oliva\Node($data);

... 但实际上，集成者需要根据他的需求提供节点工厂

fn(mixed $anyItem) => new MyNode(MyTransformer::transform($anyItem)),

任何 可调用的 对象都可以作为节点工厂，只要它返回一个实现 \Dakujem\Oliva\MovableNodeContract 的类实例。

use Dakujem\Oliva\MovableNodeContract;

💡

节点工厂可调用函数的完整签名是 fn(mixed $data, mixed $dataIndex): MovableNodeContract。
这意味着输入集合的键（索引）也可以用于节点构建。

每个构建器还要求 提取器，以下将描述，提供有关树结构的信息的可调用函数。

物化路径树

MPT 指的是在数据中存储节点相对于根节点（即“路径”）位置的技术。

实际上有多种方法可以实现这一点，而 Oliva 对此不敏感。
一个节点的典型路径可能如下所示

"1.33.2"，"/1/33/2"，也称为 分隔符 变体
"001033002"，称为固定（或固定宽度）变体，每级宽度为 3 个字符（此处 001、033 和 002）
[1,33,2]，作为整数数组，此处也称为向量

此外，单个引用可以是给定级别上的其他同辈的相对位置，也可以是直接节点引用（祖先 ID）。也就是说，路径 1.2.3 可以表示“根的第一个子节点的第二个子节点的第三个子节点”，也可以表示节点的一个祖先 ID 是 [1,2,3]，其中 3 是父节点的 ID。

为了启用所有不同的技术，Oliva MPT TreeBuilder 要求用户传递一个向量提取器函数，例如 fn($item) => explode('.', $item->path)。Oliva 附带了两个常见的提取器工厂：Path::fixed() 和 Path::delimited()。

以下树将在下面的示例中使用

[0]  (the root)
|
+--[1]
|  |
|  +--[4]
|  |
|  +--[7]
|
+--[6]
|  |
|  +--[5]
|
+--[2]
|
+--[3]

固定长度 MPT 的简单示例

use Any\Item;
use Dakujem\Oliva\MaterializedPath\Path;
use Dakujem\Oliva\MaterializedPath\TreeBuilder;
use Dakujem\Oliva\Node;

// The input data may be a result of an SQL query or any other iterable collection.
$collection = [
    new Item(id: 0, path: ''), // the root
    new Item(id: 1, path: '000'),
    new Item(id: 2, path: '001'),
    new Item(id: 3, path: '003'),
    new Item(id: 4, path: '000000'),
    new Item(id: 5, path: '002000'),
    new Item(id: 6, path: '002'),
    new Item(id: 7, path: '000001'),
];

$builder = new TreeBuilder(
    node: fn(Item $item) => new Node($item),      // How to create a node.
    vector: Path::fixed(                          // How to extract path vector.
        levelWidth: 3,
        accessor: fn(Item $item) => $item->path,
    ),
);

$root = $builder->build(
    input: $collection,
);

具有等效分隔符 MPT 的相同示例

use Any\Item;
use Dakujem\Oliva\MaterializedPath\Path;
use Dakujem\Oliva\MaterializedPath\TreeBuilder;
use Dakujem\Oliva\Node;

$collection = [
    new Item(id: 0, path: null), // the root
    new Item(id: 1, path: '.0'),
    new Item(id: 2, path: '.1'),
    new Item(id: 3, path: '.3'),
    new Item(id: 4, path: '.0.0'),
    new Item(id: 5, path: '.2.0'),
    new Item(id: 6, path: '.2'),
    new Item(id: 7, path: '.0.1'),
];

$builder = new TreeBuilder(
    node: fn(Item $item) => new Node($item),      // How to create a node.
    vector: Path::delimited(                      // How to extract path vector.
        delimiter: '.',
        accessor: fn(Item $item) => $item->path,
    ),
);

$root = $builder->build(
    input: $collection,
);

💡

由于子节点按顺序（即没有特定键）添加到父节点中，在源数据中出现它们的顺序，在构建树之前按路径对源集合进行排序可能是一个好主意。

如果需要在树构建之后对同辈进行排序，可以使用 LevelOrderTraversal 来遍历和修改树。

对于需要按特定键对子节点进行索引的情况，也是如此。使用LevelOrderTraversal，移除子节点，然后对它们进行排序和/或计算它们的键，并在新键和/或新顺序下将它们添加回来。

递归树

每个节点的数据都包含对其父节点数据的（递归）引用。
可能是持久化树最常见且最简单的方式。

use Any\Item;
use Dakujem\Oliva\Recursive\TreeBuilder;
use Dakujem\Oliva\Node;

$collection = [
    new Item(id: 0, parent: null),
    new Item(id: 1, parent: 0),
    new Item(id: 2, parent: 0),
    new Item(id: 3, parent: 0),
    new Item(id: 4, parent: 1),
    new Item(id: 5, parent: 6),
    new Item(id: 6, parent: 0),
    new Item(id: 7, parent: 1),
];

$builder = new TreeBuilder(
    node: fn(Item $item) => new Node($item),      // How to create a node.
    selfRef: fn(Item $item) => $item->id,         // How to get ID of self.
    parentRef: fn(Item $item) => $item->parent,   // How to get parent ID.
    root: null,                                   // The root node's parent value.
);

$root = $builder->build(
    input: $collection,
);

上面，self和parent参数期望有签名为fn(mixed $data, mixed $dataIndex, TreeNodeContract $node): string|int的提取器，
而root期望根节点父节点的值。具有此父值节点将被返回。

root最自然的情况是null，因为没有父节点的节点被认为是根节点。该值可以更改为0、""或适合特定数据集的其他任何值。
这在构建子树时很有用。

包装数组、JSON、YAML...

如果数据已经以树数据结构化，可以使用简单的包装器来构建树结构。

use Any\Item;
use Dakujem\Oliva\Simple\TreeWrapper;
use Dakujem\Oliva\Node;

// $json = (new External\ApiConnector())->call('getJsonData');
// $rawData = json_decode($json);

// $rawData = yaml_parse_file('/config.yaml');

$rawData = [
    'children' => [
        [
            'attributes' => [ ... ],
            'children' => [
                [
                    'attributes' => [ ... ],
                    'children' => [],
                ]
            ],
        ],
        [
            'attributes' => [ ... ],
            'children' => [ ... ],
        ],
    ],
];

$builder = new TreeWrapper(
    node: function(array $item) {                                // How to create a node.
        unset($item['children']);                                // Note the unset call optimization.
        return new Node($item);
    },                   
    children: fn(array $item):array => $item['children'] ?? [],  // How to extract children.
);

$root = $builder->wrap($rawData);

上面，children期望一个签名为fn(mixed $data, TreeNodeContract $node): ?iterable的提取器。

💡

记住，构建树节点是集成者的责任。可以使用数据执行任何转换，只要返回一个实现MovableNodeContract的节点。

手动树构建

使用手动节点构建器

use Dakujem\Oliva\Node;
use Dakujem\Oliva\Simple\NodeBuilder;

// Tell the builder how to create a node.
// The `$item` parameter of the node factory
// will contain the first argument to each `NodeBuilder::node` call.
$proxy = new NodeBuilder(
    node: fn(mixed $item) => new Node($item),
);

$root = 
    $proxy->node('root', [
        $proxy->node('first child', [
            $proxy->node('leaf of the first child node'),
            $proxy->node('another leaf of the first child node'),
        ]),
        $proxy->node('second child'), 
    ]);

使用低级节点接口（MovableNodeContract）构建树

use Dakujem\Oliva\Node;

$root = new Node('root');
$root->addChild($child1 = new Node('first child'));
$root->addChild($child2 = new Node('second child'));
$child1->setParent($root);
$child2->setParent($root);
$leaf1 = new Node('leaf of the first child node');
$child1->addChild($leaf1);
$leaf1->setParent($child1);
$leaf2 = new Node('another leaf of the first child node');
$child1->addChild($leaf2);
$leaf2->setParent($child1);

...是的，这不是构建树最优化方式。

使用高级操纵器（Tree）做同样的事情

use Dakujem\Oliva\Node;
use Dakujem\Oliva\Tree;

$root = new Node('root');
Tree::link(node: $child1 = new Node('first child'), parent: $root);
Tree::link(node: $child2 = new Node('second child'), parent: $root);
Tree::link(node: new Node('leaf of the first child node'), parent: $child1);
Tree::link(node: new Node('another leaf of the first child node'), parent: $child1);

...或者一个更简洁的方式

use Dakujem\Oliva\Node;
use Dakujem\Oliva\Tree;

Tree::linkChildren(node: $root = new Node('root'), children: [
    Tree::linkChildren(node: new Node('first child'), children: [
        new Node('leaf of the first child node'),
        new Node('another leaf of the first child node'),
    ]),
    new Node('second child'),
]);

移动节点

TL;DR 使用Tree::link静态方法。

在某些情况下，使用节点的低级接口（setParent、addChild、removeChild方法）就足够了，但大多数情况下Tree::link效果更好

use Dakujem\Oliva\Iterator\Filter;
use Dakujem\Oliva\Node;
use Dakujem\Oliva\Seed;
use Dakujem\Oliva\Tree;

// Create a find-by-id function (see Iterators section below):
$findById = fn(int $id, Node $tree) => Seed::firstOf(
    new Filter($tree, fn(Node $node) => $node->data()?->id === $id)
);

// Move node with ID 7 into node ID 14:
$node = $findById(7, $root);
$parent = $findById(14, $root);
Tree::link($node, $parent);

Tree::link调用将处理所有关系：断开原始父节点的连接并将子树链接到新的父节点。

树遍历和迭代器

Oliva提供了树遍历迭代器、生成器和过滤器迭代器。

遍历迭代器和生成器将按照特定顺序遍历树的所有节点。

深度优先搜索，前序遍历

Traversal::preOrder生成器
PreOrderTraversal迭代器

深度优先搜索，后序遍历

Traversal::postOrder生成器
PostOrderTraversal迭代器

广度优先搜索，层次遍历

Traversal::levelOrder生成器
LevelOrderTraversal迭代器

如果不确定不同的遍历是什么意思，请阅读有关树遍历的更多信息。

use Dakujem\Oliva\Iterator\Traversal;
use Dakujem\Oliva\Iterator\PreOrderTraversal;
use Dakujem\Oliva\Iterator\PostOrderTraversal;
use Dakujem\Oliva\Iterator\LevelOrderTraversal;

foreach(Traversal::levelOrder($root) as $node) { /* ... */ }
foreach(new LevelOrderTraversal($root) as $node) { /* ... */ }

💡

迭代器类和生成器方法之间关键的差异在于键。如果遍历中的键不重要，请使用Traversal的生成器方法以获得更好的性能。

如果遍历顺序不重要，可以直接迭代Node实例

use Dakujem\Oliva\Node;

$root = new Node( ... );

foreach ($root as $node) {
    // do something useful with the node
}

上面的代码将遍历整个子树，包括节点本身及其所有后代。

💡

遍历可以用作装饰节点或甚至修改树。
在遍历中修改树结构之前，请务必了解每个遍历的工作方式，否则可能会遇到意外情况。

过滤节点

最后，可以使用Iterator\Filter的filter iterator对输入数据或树节点进行过滤。

use Dakujem\Oliva\Iterator\Filter;
use Dakujem\Oliva\Node;
use Dakujem\Oliva\Seed;

// Filter the input before building a tree.
$filteredCollection = new Filter($sourceCollection, fn(Item $item): bool => $item->id > 5);
$root = (new TreeBuilder( ... ))->build(
    $filteredCollection,
);

// Iterate over leafs only.
$filter = new Filter($root, fn(Node $node): bool => $node->isLeaf());
foreach($filter as $node){
    // ...
}

// Find the first node that matches a criterion (data with ID = 42).
$node = Seed::firstOf(new Filter(
    input: $root,
    accept: fn(Node $node): bool => $node->data()?->id === 42),
);

搜索特定节点

Oliva不提供直接搜索特定节点的方法，但可以轻松创建一个

use Dakujem\Oliva\Iterator\Filter;
use Dakujem\Oliva\Node;
use Dakujem\Oliva\Seed;

// Create a find-by-id function.
$findById = fn(int $id, Node $tree): ?Node => Seed::firstOf(
    new Filter($tree, fn(Node $node) => $node->data()?->id === $id)
);

// Search for any node by ID.
$node_42 = $findById(42, $root);

一个类可能也合适...

class TreeFinder
{
    public function __construct(
        public Node $tree,
    ) {
    }
    
    public function byId(int $id){ ... }
    
    public function byName(string $name){ ... }
}

节点键

通常，键会在遍历时递增（使用任何遍历迭代器或生成器）。

use Dakujem\Oliva\Node;

$root = new Node( ... );

foreach ($root as $key => $node) {
    // The keys will increment 0, 1, 2, 3, ... and so on.
}

当使用任何遍历迭代器时，可以使用键调用修改键序列。
此示例生成一个分隔的物化路径

use Dakujem\Oliva\Iterator\PreOrderTraversal;
use Dakujem\Oliva\Node;

$iterator = new PreOrderTraversal(
    node: $root,
    key: fn(Node $node, array $vector): string => '.' . implode('.', $vector),
    startingVector: [],
);
$result = iterator_to_array($iterator);
//[
//    '.' => 'F',
//    '.0' => 'B',
//    '.0.0' => 'A',
//    '.0.1' => 'D',
//    '.0.1.0' => 'C',
//    '.0.1.1' => 'E',
//    '.1' => 'G',
//    '.1.0' => 'I',
//    '.1.0.0' => 'H',
//];

此示例通过数据中找到的ID对节点进行索引

use Dakujem\Oliva\Iterator\PreOrderTraversal;
use Dakujem\Oliva\Node;

$iterator = new PreOrderTraversal(
    node: $root,
    key: fn(Node $node): int => $node->data()->id,
);

键可调用的完整签名是

fn(
    Dakujem\Oliva\TreeNodeContract $node, 
    array $vector, // array<int, string|int>
    int $seq, 
    int $counter
): string|int

其中

$node是当前节点
$vector是节点在树中的向量
- 它是一个从根到节点的路径，其中子索引是向量的元素
- 根的向量是空的[]（或如果传递给迭代器构造函数，等于$startingVector）
- 当前节点在其父节点子节点中的索引是向量的最后一个元素
$seq是当前同辈分子（第一个子节点是0，第二个子节点是1，以此类推）
$counter是默认迭代分子，每次节点递增1（0，1，2，...）
- 如果没有键可调用，这是键序列

所有Oliva遍历迭代器都接受键可调用和一个起始向量（$vector的前缀）。

💡

当使用键可调用时，请注意iterator_to_array，因为冲突的键将在没有警告的情况下被覆盖。
键可调用应该生成唯一的键。

食谱

无根数据的物化路径树

可能存在源数据不包含根的情况。
这可能是因为存储文章评论、菜单或论坛帖子，并考虑父对象（文章、线程或站点）为根。

一种解决方案是添加一个空的数据元素，然后在不需要迭代根的情况下忽略它。

观察使用Seed辅助类

use Dakujem\Oliva\MaterializedPath;
use Dakujem\Oliva\Seed;

$source = Sql::getMeTheCommentsFor($article);

// When prepending `null`, care must be taken that both the extractor and the factory are able to cope with `null` values.
// Note the use of `?` nullable type hint indicator and null-safe `?->` operator.
$factory = fn(?Item $item) => new Node($item);
$pathExtractor = fn(?Item $item) => $item?->path;

$builder = new MaterializedPath\TreeBuilder( ... );
$root = $builder->build(
    input: Seed::nullFirst($source),       // `null` is prepended to the data
);

foreach(Seed::omitNull($root) as $node) {  // The node with `null` data is omitted from the iteration
    display($node);
}

我们也可以使用Seed::merged来添加一个具有虚构根数据的项目，但那时必须使用Seed::omitRoot来忽略根

use Dakujem\Oliva\MaterializedPath;
use Dakujem\Oliva\Seed;

$source = Sql::getMeTheCommentsFor($article);

// We need not take care of null values anymore.
$factory = fn(Item $item) => new Node($item);
$pathExtractor = fn(Item $item) => $item->path;

$builder = new MaterializedPath\TreeBuilder( ... );
$root = $builder->build(
    input: Seed::merged([new Item(id: 0, path: '')], $source),
);

foreach(Seed::omitRoot($root) as $node) {  // The root node is omitted from the iteration
    display($node);
}

无根数据的递归树

当使用具有非空父节点的子树的递归构建器时，可能会发生类似的情况。

通过将$root参数传递给树构建器可以非常简单地解决这个问题。

use Any\Item;
use Dakujem\Oliva\Recursive\TreeBuilder;
use Dakujem\Oliva\Node;

$collection = [
    new Item(id: 100, parent: 99),             // Note that no data with ID 99 is present
    new Item(id: 101, parent: 100),
    new Item(id: 102, parent: 100),
    new Item(id: 103, parent: 100),
    new Item(id: 104, parent: 101),
    new Item(id: 105, parent: 106),
    new Item(id: 106, parent: 100),
    new Item(id: 107, parent: 101),
];

$builder = new TreeBuilder(
    node: fn(Item $item) => new Node($item),
    self: fn(Item $item) => $item->id,
    parent: fn(Item $item) => $item->parent,
    root: 99,                                  // Here we indicate what the parent of the root is
);

$root = $builder->build(
    input: $collection,
);

如果节点的父节点与值匹配，则认为它是根节点。

从旧的oliva/tree库迁移

构建器和迭代器

如果从之前的库（oliva/tree）迁移，最常见的问题是

新构建器不会自动添加空根节点
新迭代器遍历根节点

对于这两个问题，请参阅上面“食谱”部分中的“无根数据的物化路径树”和“无根数据的递归树”部分。

节点类

不支持通过代理魔法属性或数组访问Oliva\Utils\Tree\Node\Node。
建议迁移到新的Dakujem\Oliva\Node类，而不是尝试重新创建旧的行为。

Dakujem\Oliva\Node与Oliva\Utils\Tree\Node\SimpleNode非常相似，从后者迁移应该很简单（迁移getter/setter的使用）。

测试

使用以下命令运行单元测试

composer test

贡献

欢迎提出想法、问题或代码贡献。请发送PR或提交问题。

如果您喜欢这个库，请给它加星并传播信息 🙏。

dakujem / oliva

维护者

详细信息