FlowArena

一个基于所有权的 HashMap 管理图模型。

组件

该 flow_arena 包包括

1. 一个流数据模型表示 trait Flow 和 struct FlowArena
2. 一个节点表示 trait Node 和 struct FlowNode
3. 如 GraphNode 和 GraphArena 的变体。

动机

FlowArena 使您能够

1. 以内存安全的方式表示树/图数据模型
2. 使用“所有权”的概念在树形和图形之间切换，以及
   1. 以受控的方式递归地移动/删除节点的能力 - 如果节点 A 由节点 B 所拥有，那么 B 的删除将触发 A 的删除
   2. 以两种不同的方式访问和遍历数据模型的能力，即类似树的方式和类似图的方式

事实上，这一切都始于 Rust 的所有权规则...

竞技场

在关系驱动的数据模型中，Rustaceans 容易头痛 - 只需尝试编写一个安全的双向链表。因此，提出了 Arena 的概念，以实现此类模型的简单和内存安全的表示。 ^1

考虑一个树模型。本质上，它是一组节点，其中每个节点都可以指向其他节点。我们如何表示这种关系呢？好吧，我们给每个节点一个唯一的标记，以表明它的引用。我们过去使用指针，通过内存地址巧妙地标记这种唯一性；但由于Rust的所有权规则，这种方法实现起来很冗长。那么，为什么不我们自己通过索引或ID来标记这种唯一性呢？

Arena的想法很简单：使用一个Vec<Node>或一个HashMap<Id, Node<Id>>来包含所有节点，其中每个节点包含一个索引/ID的集合，例如Vec<Id>，以及其自己的数据。我们可以用索引/ID来标记节点，从而可以指定根节点；要遍历，只需递归地获取一个节点并遍历其“节点标记集合”。

流程

FlowArena代表了有向图，其灵感来自Arena。不仅如此，它还能够表示“流模型”。

流模型与图或树模型不同，因为它提供了所有（类似于树）和链接（类似于图）的功能。假设您要从树中删除一个节点，其子节点将自动被删除，这是节点对其子节点的“所有权”的体现。相比之下，图节点的删除不会导致周围节点被删除。

利用当前图模型中的所有权概念，我们产生了一种新的数据模型，可以自由地在两种模式之间切换其行为。我们称这种数据模型为“流模型”，这清楚地表明了FlowArena的功能。

重要：与Arena相比，FlowArena中有一些额外概念

1. 节点不仅有子节点（Vec<Id>），还有可选的父节点（Option<Id>）
   1. 从树的角度看，父节点表示所有权，None表示根；子节点只是表示可能所有权的额外标记
   2. 从图的角度看，子节点表示单向边
   3. 请注意，“纯链接”表示没有所有权的链接
   4. 然而，“所有权”意味着“链接”：如果A有父节点B，那么B必须有A作为其子节点之一
2. 如果有外部链接存在，任何节点都可以有它的子树或子图
   1. 由节点递归拥有的所有节点被称为该节点的“子节点”
   2. 节点分别称为“树节点”或“图节点”
3. 没有父节点的节点称为orphan，这与一组“根”节点相似。

用法

1. 直接使用 struct FlowNode<Id> 和 struct FlowArena<Id, Entity> 来表示流模型
2. 实现 trait Node<Id> 和 trait Flow - 请参阅特质实现以获取参考
3. 被调用时，使用相应的特质

Triat 实现

1. FlowBase：提供基本的节点反射能力；无检查
2. FlowCheck：检查 Flow 的属性并查看它们是否成立
3. FlowMap：提供哈希表功能
4. FlowLink：提供连接节点的能力；类似于图
5. FlowDevote：提供奉献/拥有节点的能力；类似于树
6. FlowDock：提供从节点剪切（脱钩）和复制（捕捉）流到另一个节点（停靠）的能力
7. FlowShift：提供使用 Direction 在流中移动的能力
8. Flow：检查所有特质是否已实现

相关应用

FlowArena 是笔记、思维导图、待办事项列表和日程安排应用 flow.er 的底层数据模型。