trailtree/
lib.rs

1//! # TrailTree
2//!
3//! `TrailTree` is a hierarchical search tree structure designed for efficiently searching and traversing paths using layer-scoped, unique keys.
4//!
5//! ## Features
6//! - **Path-based Operations**: Provides efficient insertion and retrieval of paths using subtrees.
7//! - **Generic Keys and Data**: Supports keys `K: Clone + Ord` and associated data `T`.
8//! - **Persistent Identification**: Operations return stable `usize` identifiers (except where explicitly stated as a side effect).
9//!
10//! ## Implementation
11//! `TrailTree` is implemented as a recursive, tertiary, AVL search tree—such that the Equal child of each element is the root of its subtree—stored on
12//! top of an object pool.
13//!
14//! ### Time
15//! Efficiencies are expressed in terms of fundamental operations—complex operations will need to be multiplied by path length or number of operations.
16//! The term `n` refers to the number of elements in the local tree, while `m` refers to the number of elements in the complete subtree.
17//!
18//! - Insert—binary search + rebalance, `O(log n)`
19//! - Delete—subtree deletion + rebalance, `O(m + log n)`
20//! - Relocate—binary search + rebalance (x2), `O(log n)`
21//! - Key Search—binary search, `O(log n)`
22//! - Enumeration—exhaustive iteration, `O(n)`
23//! - Sibling key traversal—subtree traversal, `O(log n)`
24//! - Upward traversal—`O(1)`
25//! - Access—`O(1)`
26//!
27//! ### Memory
28//! `TrailTree` trades some memory overhead for improved time efficiency, resulting in nonoptimal memory usage.
29//! Update operations may incur memory spikes due to the use of an underlying `Vec`.
30//!
31//! ### Caching
32//! While the structure uses continuous memory, the positions of related elements are not guaranteed to be cache efficient.
33//!
34//! ## Example
35//! ```
36//! use trailtree::TrailTree;
37//!
38//! let mut tree = TrailTree::<u32, ()>::new();
39//!
40//! // Insert a path into the tree
41//! let leaf = tree.insert(&[10, 12, 2]);
42//!
43//! // Retrieve the path associated with the leaf
44//! assert_eq!(&tree.path(leaf), &[10, 12, 2]);
45//! ```
46//!
47//! ## When to Use
48//! `TrailTree` is best suited for workloads where paths are queried incrementally, subtrees are traversed frequently, and element identity must remain stable across mutations.
49//! 
50//! - File systems
51//! - Namespaces
52//! - Type systems
53//! - Organizational charts
54//!
55
56#![cfg_attr(not(feature = "std"), no_std)]
57#![allow(dead_code)]
58extern crate alloc;
59
60use alloc::vec::Vec;
61
62#[cfg(test)]
63mod tests;
64
65mod node; use node::{Node, NodeRel};
66mod cell; use cell::Cell;
67mod implement;
68
69/// A hierarchical search tree structure for efficiently searching paths.
70/// Operates over locally-unique, searchable keys `K` with associated data `T`.
71/// 
72/// # Examples
73/// 
74/// ```
75/// use trailtree::TrailTree;
76/// 
77/// let mut con = TrailTree::<u32,()>::new();
78/// 
79/// let leaf = con.insert(&[10, 12, 2]);
80/// 
81/// assert_eq!(&con.path(leaf), &[10, 12, 2]);
82/// ```
83pub struct TrailTree<K,T>
84where K: Clone + Ord
85{
86    pub(crate) cells:Vec<Cell<K,T>>,
87    pub(crate) root:usize,
88    pub(crate) next:usize,
89}
90
91impl<K,T> TrailTree<K,T>
92where K: Clone + Ord
93{
94    /// Constructs a new, empty structure.
95    /// 
96    /// ```
97    /// use trailtree::TrailTree;
98    /// 
99    /// let mut con = TrailTree::<u32,()>::new();
100    /// assert_eq!(con.capacity(), 0);
101    /// ```
102    pub const fn new() -> Self
103    {
104        Self {
105            cells:Vec::new(),
106            root:usize::MAX,
107            next:0,
108        }
109    }
110
111    /// Constructs a new structure with the requested capacity of preallocated cells.
112    /// 
113    /// ```
114    /// use trailtree::TrailTree;
115    /// 
116    /// let mut con = TrailTree::<u32,()>::with_capacity(10);
117    /// 
118    /// assert!(con.capacity() >= 10);
119    /// ```
120    pub fn with_capacity(capacity:usize) -> Self
121    {
122        Self {
123            cells:Vec::with_capacity(capacity),
124            root:usize::MAX,
125            next:0,
126        }
127    }
128}
129
130#[cfg(feature = "std")]
131impl<K,T> std::fmt::Debug for TrailTree<K,T>
132where K: Clone + Ord + std::fmt::Debug
133{
134    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result
135    {
136        fn id_or(id:usize) -> String
137        {
138            if id != usize::MAX {
139                id.to_string()
140            } else {
141                "-".to_string()
142            }
143        }
144
145        let mut out = String::new();
146
147        let mut stack: Vec<_> = alloc::vec::Vec::new();
148        stack.push((self.root, 0));
149
150        while let Some((id, depth)) = stack.pop() {
151            if id != usize::MAX {
152                if let Some(node) = self.node(id) {
153                    out.push_str(&format!("{}#{} {:?} [{}:{}] [{}, {}, {}]\n", ".".repeat(depth),
154                        id,
155                        node.key,
156                        id_or(node.rel.root),
157                        id_or(node.rel.parent),
158                        id_or(node.rel.child[0]),
159                        id_or(node.rel.child[1]),
160                        id_or(node.rel.child[2]),
161                    ));
162
163                    stack.push((node.rel.child[2], depth + 1));
164                    stack.push((node.rel.child[0], depth + 1));
165                    stack.push((node.rel.child[1], depth + 1));
166                } else {
167                    out.push_str(&format!("{}invalid\n", " ".repeat(depth)));
168                }
169            }
170        }
171
172        write!(f, "{}", out)
173    }
174}
trailtree/lib.rs

trailtree/
lib.rs
