Crate flow_arena[−][src]

FlowArena

A HashMap managed graph model with the concept of ownership.

Components

The flow_arena package consists of

  1. a flow data model representation trait Flow and struct FlowArena
  2. a node representation trait Node and struct FlowNode
  3. variants like GraphNode and GraphArena.

Motivation

FlowArena grants you the ability to:

  1. represent a tree / graph data model in a memory-safe way
  2. use the concept of “ownership” to switch between the tree form and the graph form, along with:
    1. the ability to move / delete nodes recursively in a controlled way - if node A is owned by node B, then B’s removal will trigger A’s removal
    2. the ability to visit and traverse the data model in two different ways, namely the tree-ish way and the graph-ish way

In fact, it all started with Rust’s ownership rules…

Arena

When it comes to relation driven data models, it’s easy to make Rustaceans headache - just try and write a safe doubly-linked list. The concept of Arena, therefore, is raised to implement a simple and memory-safe representation of such models. 1

Consider a tree model. Basically it’s a group of nodes where each node can point to some other nodes. How do we denote this relation? Well, we give every node a unique mark which claims its reference. We used to use pointers to cleverly mark this uniqueness with the help of memory addresses; but due to Rust’s ownership rule, this approach is verbose to implement. So, why not mark this uniqueness by ourselves, with indices or ids?

The idea of the Arena is simple: use a Vec<Node> or a HashMap<Id, Node<Id>> to contain all the nodes, where each node contains a collection of indices / ids, e.g. Vec<Id>, as well as its own data. We can mark a node with its index / id, thus we can designate a root node; to traverse, just recursively get a node and traverse its “node marker collection”.

Flow

FlowArena represents a directed graph with the idea of Arena. More than that, it’s also able to represent the “flow model”.

Flow model is different from graph or tree model alone because it provides both ownership (tree-ish) and linkage (graph-ish) features. Suppose you are removing a node from a tree, the children of it will automatically be removed, which is an implication of the “ownership” of a node to its children. In contrast, a graph node’s removal will not cause the surrounding nodes to be removed.

Using the concept of ownership in the current graph-ish model, we yield a new kind of data model that can freely switch its behaviour between the two modes. We call such a data model a “flow model”, which clearly indicates the functionality of FlowArena.

Important: there are some extra concepts in FlowArena compared to Arena:

  1. nodes have not only children(Vec<Id>), but also a optional parent (Option<Id>)
    1. from tree-ish prospective, parent implies ownership, None means root; and children is only extra notation for possible ownership
    2. from graph-ish prospective, children implies one-way edge
    3. note that a “pure link” means linkage without ownership
    4. however, “ownership” implies “linkage”: if A has parent B, then B must have A as one of its children
  2. any node can have its sub tree or sub graph, given that no external linkage exist
    1. all the nodes owned recursively by the node are called “sub-nodes” of the node
    2. the node is called “tree node” or “graph node”, respectively
  3. the nodes with no parent are called orphans which is similar to a group of “root” nodes.

Usage

  1. directly use struct FlowNode<Id> and the struct FlowArena<Id, Entity> to represent a flow model
  2. impl trait Node<Id> and trait Flow - see Trait Implementation for reference
  3. when called upon, use the corresponding trait

Triat Implementation

  1. FlowBase: provides basic node-reflection abiliy; no check
  2. FlowCheck: checks the Flow’s properties and see whether they hold
  3. FlowMap: provides hashmap functionality
  4. FlowLink: provides ability to link nodes; graph-ish
  5. FlowDevote: provides ability to devote / own nodes; tree-ish
  6. FlowDock: provides ability to cut (undock) and copy (snap) a flow from a node and paste it to another node (dock)
  7. FlowShift: provides ability to move around in flow with Direction
  8. Flow: checks all the traits are implemented

The FlowArena is serving as the underlying data model of flow.er, a notebook, mindmap, todo-list and agenda app.

  1. no-more-tears-no-more-knots-arena-allocated-trees-in-rust ↩

Modules

prelude

Structs

FlowArena
FlowNode
GraphNode

Enums

Direction

Direction under FlowView:

FlowError

Represents all possible Errors in Flow Operations

Traits

Flow

The overall Flow trait, checking whether anything is missing.

FlowBase

provides basic node-reflection abiliy; no check

FlowCheck

checks the Flow’s properties and see whether they hold

FlowDevote

provides ability to devote / own nodes; tree-ish

FlowDock

provides ability to cut (undock) and copy (snap) a flow from a node and paste it to another node (dock)

FlowLink

provides ability to link nodes; graph-ish

FlowMap

provides hashmap functionality

FlowShift

provides ability to move around in flow

Node

Type Definitions

FlowPure
GraphArena
NodePure