id_tree/lib.rs
1//! A library for creating and modifying Tree structures.
2//!
3//! ## Overview
4//! In this implementation, the `Tree` owns all of the `Node`s and all inter-`Node` relationships
5//! are managed with `NodeId`s.
6//!
7//! `Tree`s in this library are "just" trees. They do not allow cycles. They do not allow
8//! the creation of arbitrary Graph structures. There is no weight associated with edges between
9//! `Node`s. In addition, each `Node` can have an arbitrary number of child `Node`s.
10//!
11//! It is important to note that this library does not support comparison-based `Node` insertion.
12//! In other words, this is not a Binary Search Tree (or any other kind of search tree) library.
13//! It is purely a library for storing data in a hierarchical manner. The caller must know the
14//! structure that they wish to build and then use this library to do so; this library will not
15//! make those structural decisions for you.
16//!
17//! ## Example Usage
18//! ```
19//! use id_tree::*;
20//!
21//! fn main() {
22//! use id_tree::InsertBehavior::*;
23//!
24//! // 0
25//! // / \
26//! // 1 2
27//! // / \
28//! // 3 4
29//! let mut tree: Tree<i32> = TreeBuilder::new()
30//! .with_node_capacity(5)
31//! .build();
32//!
33//! let root_id: NodeId = tree.insert(Node::new(0), AsRoot).unwrap();
34//! let child_id: NodeId = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
35//! tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
36//! tree.insert(Node::new(3), UnderNode(&child_id)).unwrap();
37//! tree.insert(Node::new(4), UnderNode(&child_id)).unwrap();
38//!
39//! println!("Pre-order:");
40//! for node in tree.traverse_pre_order(&root_id).unwrap() {
41//! print!("{}, ", node.data());
42//! }
43//! // results in the output "0, 1, 3, 4, 2, "
44//! }
45//! ```
46//!
47//! ## Project Goals
48//! * Allow caller control of as many allocations as possible (through pre-allocation)
49//! * Fast `Node` insertion and removal
50//! * Arbitrary _Tree_ structure creation and manipulation
51//!
52//! ## Non-Goals
53//! * Arbitrary _Graph_ structure creation and manipulation
54//! * Comparison-based node insertion of any kind
55//!
56//! #### Drawbacks of this Library
57//! Sadly, Rust's ownership/reference system is sidestepped a bit by this implementation and this
58//! can cause issues if the caller doesn't pay attention to what they are doing with `NodeId`s.
59//!
60//! We try to solve these issues with very careful usage of `NodeId`s so that the caller doesn't
61//! have to be bothered (too much) with these concerns.
62//!
63//! Please see the [Potential `NodeId` Issues](struct.NodeId.html#potential-nodeid-issues) section
64//! of the `NodeId` documentation for more info on what these issues are and how this library
65//! attempts to solve them.
66//!
67
68#[cfg(feature = "serde_support")]
69extern crate serde;
70
71#[cfg(feature = "serde_support")]
72#[macro_use]
73extern crate serde_derive;
74
75extern crate snowflake;
76use self::snowflake::ProcessUniqueId;
77
78mod behaviors;
79mod error;
80mod iterators;
81mod node;
82mod tree;
83
84pub use behaviors::InsertBehavior;
85pub use behaviors::MoveBehavior;
86pub use behaviors::RemoveBehavior;
87pub use behaviors::SwapBehavior;
88pub use error::NodeIdError;
89pub use iterators::AncestorIds;
90pub use iterators::Ancestors;
91pub use iterators::Children;
92pub use iterators::ChildrenIds;
93pub use iterators::LevelOrderTraversal;
94pub use iterators::LevelOrderTraversalIds;
95pub use iterators::PostOrderTraversal;
96pub use iterators::PostOrderTraversalIds;
97pub use iterators::PreOrderTraversal;
98pub use iterators::PreOrderTraversalIds;
99pub use node::Node;
100pub use node::NodeBuilder;
101pub use tree::Tree;
102pub use tree::TreeBuilder;
103
104///
105/// An identifier used to differentiate between `Node`s within a `Tree`.
106///
107/// `NodeId`s are not something that the calling context will ever have to worry about generating.
108/// `Tree`s generate `NodeId`s as `Node`s are inserted into them.
109///
110/// In addition, each `NodeId` is specific to the `Tree` that generated it. This means that if
111/// there are two `Tree`s - `A` and `B` - there's no worry of trying to access a `Node` in `A` with
112/// an identifier that came from `B`. Doing so will return a `Result::Err` value instead of
113/// returning the wrong `Node`.
114///
115/// #### Potential `NodeId` Issues
116///
117/// Because `Tree`s pass out `NodeId`s as `Node`s are inserted, several issues can occur:
118///
119/// 1. If a `Node` is removed, the `NodeId` that previously identified it now points to nothing
120/// (technically a `None` value in this case).
121/// 2. If a `Node` is removed and then another is inserted later, the "new" `NodeId` that is
122/// returned can (and will) be the same `NodeId` that was used to identify a different `Node`
123/// previously.
124///
125/// The above issues may seem like deal-breakers, but our situation isn't as bad as it seems:
126///
127/// The first issue can be easily detected by the library itself. In this situation, a
128/// `Result::Err` will be returned with the appropriate `NodeIdError`. The second issue, however, is
129/// not something that the library can detect. To mitigate this problem, this library ensures the
130/// following:
131///
132/// 1. All `Node` methods that provide `NodeId`s will **return** `&NodeId`s instead of `NodeId`s.
133/// 2. All `Tree` methods that **read** or **insert** data accept `&NodeId`s instead of taking
134/// `NodeId`s.
135/// 3. All `Tree` methods that **remove** data take `NodeId`s instead of accepting `&NodeId`s.
136/// 4. All `Node`s that have been removed from a `Tree` will have their parent and child references
137/// cleared (to avoid leaking extra `NodeId` copies).
138/// 5. `NodeId`s themselves are `Clone`, but not `Copy`.
139///
140/// This means that no methods will ever take ownership of a `NodeId` except for methods that remove
141/// a `Node` from a `Tree`. The resulting behavior is that unless the caller **explicitly `Clone`s a
142/// `NodeId`** they should never be in a situation where they accidentally hold onto a `NodeId` too
143/// long. This means that we have "almost safe references" that the caller can clone if they choose
144/// to. Doing so, however, will open up the possibility of confusing which `NodeId`s refer to which
145/// `Node`s in the calling context.
146///
147/// This _does_ transfer some of the burden to the caller, but any errors should be fairly easy to
148/// sort out because an explicit `Clone` is required for such an error to occur.
149///
150#[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
151#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
152pub struct NodeId {
153 tree_id: ProcessUniqueId,
154 index: usize,
155}