trailtree/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2#![allow(dead_code)]
3extern crate alloc;
4
5use alloc::vec::Vec;
6
7#[cfg(test)]
8mod tests;
9
10mod node; use node::{Node, NodeRel};
11mod cell; use cell::Cell;
12mod implement;
13
14/// A hierarchical search tree structure for efficiently searching paths.
15/// Operates over locally-unique, searchable keys `K` with associated data `T`.
16/// 
17/// # Examples
18/// 
19/// ```
20/// use trailtree::TrailTree;
21/// 
22/// let mut con = TrailTree::<u32,()>::new();
23/// 
24/// let leaf = con.insert(&[10, 12, 2]);
25/// 
26/// assert_eq!(&con.path(leaf), &[10, 12, 2]);
27/// ```
28pub struct TrailTree<K,T>
29where K: Clone + Ord
30{
31    pub(crate) cells:Vec<Cell<K,T>>,
32    pub(crate) root:usize,
33    pub(crate) next:usize,
34}
35
36impl<K,T> TrailTree<K,T>
37where K: Clone + Ord
38{
39    /// Constructs a new, empty structure.
40    /// 
41    /// ```
42    /// use trailtree::TrailTree;
43    /// 
44    /// let mut con = TrailTree::<u32,()>::new();
45    /// assert_eq!(con.capacity(), 0);
46    /// ```
47    pub const fn new() -> Self
48    {
49        Self {
50            cells:Vec::new(),
51            root:usize::MAX,
52            next:0,
53        }
54    }
55
56    /// Constructs a new structure with the requested capacity of preallocated cells.
57    /// 
58    /// ```
59    /// use trailtree::TrailTree;
60    /// 
61    /// let mut con = TrailTree::<u32,()>::with_capacity(10);
62    /// 
63    /// assert!(con.capacity() >= 10);
64    /// ```
65    pub fn with_capacity(capacity:usize) -> Self
66    {
67        let mut cells = Vec::with_capacity(capacity);
68        for i in 0..cells.capacity() {
69            cells.push(Cell::pointer(i + 1));
70        }
71
72        Self {
73            cells,
74            root:usize::MAX,
75            next:0,
76        }
77    }
78}
79
80#[cfg(feature = "std")]
81impl<K,T> std::fmt::Debug for TrailTree<K,T>
82where K: Clone + Ord + std::fmt::Debug
83{
84    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result
85    {
86        fn id_or(id:usize) -> String
87        {
88            if id != usize::MAX {
89                id.to_string()
90            } else {
91                "-".to_string()
92            }
93        }
94
95        let mut out = String::new();
96
97        let mut stack: Vec<_> = alloc::vec::Vec::new();
98        stack.push((self.root, 0));
99
100        while let Some((id, depth)) = stack.pop() {
101            if id != usize::MAX {
102                if let Some(node) = self.node(id) {
103                    out.push_str(&format!("{}#{} {:?} [{}:{}] [{}, {}, {}]\n", ".".repeat(depth),
104                        id,
105                        node.key,
106                        id_or(node.rel.root),
107                        id_or(node.rel.parent),
108                        id_or(node.rel.child[0]),
109                        id_or(node.rel.child[1]),
110                        id_or(node.rel.child[2]),
111                    ));
112
113                    stack.push((node.rel.child[2], depth + 1));
114                    stack.push((node.rel.child[0], depth + 1));
115                    stack.push((node.rel.child[1], depth + 1));
116                } else {
117                    out.push_str(&format!("{}invalid\n", " ".repeat(depth)));
118                }
119            }
120        }
121
122        write!(f, "{}", out)
123    }
124}
trailtree/lib.rs

trailtree/
lib.rs
