1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#![forbid(unsafe_code)]

//!
//! # slab_tree
//!
//! [![Build Status](https://travis-ci.org/iwburns/slab-tree.svg?branch=master)](https://travis-ci.org/iwburns/slab-tree)
//! [![](https://tokei.rs/b1/github/iwburns/slab-tree)](https://github.com/iwburns/slab-tree)
//!
//! A vec-backed tree structure with tree-specific generational indexes.
//!
//! ## Overview
//!
//! This library provides a `Tree<T>` struct which allows the creation and manipulation of in-memory trees.
//! The tree itself is backed by a vector and the tree's node relationships are managed by tree-specific
//! generational indexes called `NodeId`s (more below). In addition, "views" of tree nodes are handed out
//! which are either immutable (`NodeRef`) or mutable (`NodeMut`) instead of handing out references
//! directly. Most tree mutations are achieved by modifying `NodeMut`s instead of talking to the tree
//! itself.
//!
//! `Tree`s in this crate are "just" trees. They do not allow cycles, and they do not allow arbitrary
//! graph structures to be created. Each node in the tree can have an arbitrary number of children, and
//! there is no weight associated with edges between the nodes in the tree.
//!
//! **Please Note:** this crate does not support comparison-based data insertion. In other words, this is
//! not a binary search tree (or any other kind of search tree) crate. It is purely a crate for storing
//! data in a hierarchical manner. The caller must know the structure that they wish to build and then use
//! this crate to do so; this library will not make those structural decisions for you.
//!
//! ## Safety
//! This crate uses `#![forbid(unsafe_code)]` to prevent any and all `unsafe` code usage.
//!
//! ## Example Usage
//! ```
//! use slab_tree::*;
//!
//! //      "hello"
//! //        / \
//! // "world"   "trees"
//! //              |
//! //            "are"
//! //              |
//! //            "cool"
//!
//! let mut tree = TreeBuilder::new().with_root("hello").build();
//! let root_id = tree.root_id().expect("root doesn't exist?");
//! let mut hello = tree.get_mut(root_id).unwrap();
//!
//! hello.append("world");
//! hello
//!     .append("trees")
//!     .append("are")
//!     .append("cool");
//! ```
//!
//! ## `NodeId`s
//! `NodeId`s are tree-specific generational indexes. Using generational indexes means that we can re-use
//! space inside the tree (after nodes have been removed) without also having to re-use the same tree
//! indexes which could potentially cause confusion and bugs. The "tree-specific" part means that indexes
//! from one tree cannot be confused for indexes for another tree. This is because each index contains a
//! process-unique-id which is shared by the tree from which that index originated.
//!
//! ## Project Goals
//! * Allow caller control of as many allocations as possible (through pre-allocation)
//! * Fast and Ergonomic Node insertion and removal
//! * Arbitrary Tree structure creation and manipulation
//!
//! ## Non-Goals
//! * Arbitrary _Graph_ structure creation and manipulation
//! * Comparison-based node insertion of any kind
//!

pub mod behaviors;
mod core_tree;
pub mod iter;
pub mod node;
mod slab;
pub mod tree;

pub use crate::behaviors::RemoveBehavior;
pub use crate::iter::Ancestors;
pub use crate::iter::NextSiblings;
pub use crate::node::NodeMut;
pub use crate::node::NodeRef;
pub use crate::tree::Tree;
pub use crate::tree::TreeBuilder;
use snowflake::ProcessUniqueId;

///
/// An identifier used to differentiate between Nodes and tie
/// them to a specific tree.
///
#[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
pub struct NodeId {
    tree_id: ProcessUniqueId,
    index: slab::Index,
}