skog

瑞典语意为“森林”。Adobe 的 stlab::forest 数据结构的纯 Rust 实现。

简介

“森林”是一种类似树的数据结构。参考 Adobe stlab 的森林教程

森林是一种基于节点（双向）的数据结构，用于表示层次结构。节点之间的父子关系在容器类中维护，因此可以存储任何常规类型而不影响它。它配备了一系列强大的迭代器，用于遍历层次结构的多种方法，以下将分别描述。

教程本身对基本用法有很好的解释，合著者 Foster Brereton 的 介绍文章 对森林数据结构的结构有很好的洞察。

特别是，森林数据结构是序列化树状数据的优秀工具。《dirs》示例提供了一个简单的演示。

克隆 Adobe 的 stlab 仓库

git clone https://github.com/stlab/libraries.git
cd libraries

运行 dirs 对仓库进行操作

cargo run --example dirs -- $PWD/stlab

它将打印目录结构为 xml 格式

<stlab>
	<cmake>
		<stlab>
			<coroutines>
			</coroutines>
			<development>
			</development>
		</stlab>
	</cmake>
	<stlab>
		<concurrency>
		</concurrency>
		<algorithm>
		</algorithm>
		<test>
		</test>
		<iterator>
		</iterator>
	</stlab>
	<test>
	</test>
</stlab>

游标

由于 Rust 的更严格的所有权模型，无法安全地直接暴露 C++ 迭代器的直接翻译。相反，此 crate 采取了与 Rust 的 LinkedList 提出的相同方法 并引入了“游标”类型。

与 Rust 的迭代器不同，它可以自由地前后移动，并位于森林中的两个节点之间。此外，它还跟踪节点的“边缘”，因此与 C++ 森林迭代器的语义类似。

状态

这是一个非常早期的版本，还需要进行很多测试。

与原始的 C++ 版本相比，API 也已经大幅精简到最基本的要素，这主要是由于 Rust 的所有权模型带来的挑战。但是，为了避免发布一个高度实验性的 API，它在未来的变化可能性很大，我选择发布一个更小但更稳定的 API，我相信即使是在 1.0 版本发布后也不会发生变化。

在当前状态下，我预计未来 API 的唯一变化是将 size 的 self 参数从可变引用更改为不可变引用。目前它是一个可变引用，以便在此实现中与 C++ 实现相同，如果检测到内部 size 成员已过时，则可以修改它。