dir_path_2_tree/
lib.rs

1use std::collections::BTreeMap;
2use std::io::{self, Write};
3
4#[derive(Default, Debug, PartialEq, Clone)]
5pub struct Tree(pub BTreeMap<String, Box<Tree>>);
6
7/// Drops the tree without recursion.
8///
9/// The derived drop of `Box<Tree>` recurses once per level, so a deep tree would overflow the stack when it goes
10/// out of scope, even if it was built and printed iteratively. The maps are taken out one by one instead; every
11/// child is dropped with an empty map.
12impl Drop for Tree {
13    fn drop(&mut self) {
14        let mut pending = vec![std::mem::take(&mut self.0)];
15        while let Some(map) = pending.pop() {
16            for (_, mut child) in map {
17                pending.push(std::mem::take(&mut child.0));
18            }
19        }
20    }
21}
22
23/// Inserts a path (as dot-separated parts) into the tree structure (RECURSIVE VERSION)
24/// 
25/// # Arguments
26/// * `tree` - The tree node to insert into
27/// * `parts` - Slice of path parts to insert
28/// 
29/// # Example
30/// ```
31/// use dir_path_2_tree::*;
32/// let mut tree = Tree::default();
33/// insert_path(&mut tree.0, &["a", "b", "c"]);
34/// ```
35pub fn insert_path(tree: &mut BTreeMap<String, Box<Tree>>, parts: &[&str]) {
36    if let Some((key, rest)) = parts.split_first() {
37        let subtree = tree
38            .entry((*key).to_string())
39            .or_insert_with(|| Box::new(Tree::default()));
40        if !rest.is_empty() {
41            insert_path(&mut subtree.0, rest);
42        }
43    }
44}
45
46/// Inserts a path (as dot-separated parts) into the tree structure (ITERATIVE VERSION - Simple)
47/// 
48/// This version iterates through path parts without recursion, using only heap-allocated
49/// mutable references. No explicit stack data structure needed.
50///
51/// # Arguments
52/// * `tree` - The tree node to insert into
53/// * `parts` - Slice of path parts to insert
54/// 
55/// # Example
56/// ```
57/// use dir_path_2_tree::*;
58/// let mut tree = Tree::default();
59/// insert_path_iterative(&mut tree.0, &["a", "b", "c"]);
60/// ```
61pub fn insert_path_iterative(tree: &mut BTreeMap<String, Box<Tree>>, parts: &[&str]) {
62    let mut current_tree = tree;
63    
64    for key in parts {
65        let subtree = current_tree
66            .entry((*key).to_string())
67            .or_insert_with(|| Box::new(Tree::default()));
68        current_tree = &mut subtree.0;
69    }
70}
71
72/// Inserts a path (as dot-separated parts) into the tree structure (ITERATIVE VERSION - Explicit Stack)
73/// 
74/// This version uses an explicit stack to simulate the recursive call stack.
75/// More complex but demonstrates the principle of converting recursion to iteration.
76///
77/// # Arguments
78/// * `tree` - The tree node to insert into
79/// * `parts` - Slice of path parts to insert
80pub fn insert_path_iterative_with_stack(tree: &mut BTreeMap<String, Box<Tree>>, parts: &[&str]) {
81    // Stack contains remaining parts to process
82    let mut stack = vec![parts];
83    let mut tree_stack: Vec<*mut BTreeMap<String, Box<Tree>>> = vec![tree];
84    
85    while let Some(current_parts) = stack.pop() {
86        if let Some(current_tree_ptr) = tree_stack.pop() {
87            if let Some((key, rest)) = current_parts.split_first() {
88                let subtree = unsafe {
89                    (*current_tree_ptr)
90                        .entry((*key).to_string())
91                        .or_insert_with(|| Box::new(Tree::default()))
92                };
93                
94                if !rest.is_empty() {
95                    // Push the remaining parts and the subtree for processing
96                    tree_stack.push(&mut subtree.0);
97                    stack.push(rest);
98                }
99            }
100        }
101    }
102}
103
104/// Writes the tree with indentation based on depth (RECURSIVE VERSION)
105///
106/// Pre-order: a node, then its subtree, then its next sibling. The writer makes the traversal
107/// testable and measurable without a console: a `Vec<u8>` in tests, `std::io::sink()` in benchmarks.
108///
109/// # Arguments
110/// * `out` - Where the lines go
111/// * `tree` - The tree to write
112/// * `depth` - Current depth level for indentation
113pub fn write_tree<W: Write>(out: &mut W, tree: &BTreeMap<String, Box<Tree>>, depth: usize) -> io::Result<()> {
114    for (key, subtree) in tree {
115        writeln!(out, "{}{}", " ".repeat(depth), key)?;
116        write_tree(out, &subtree.0, depth + 1)?;
117    }
118    Ok(())
119}
120
121/// Writes the tree with indentation based on depth (ITERATIVE VERSION)
122///
123/// An explicit stack of iterators, one per open level, replaces the call stack: the same pre-order
124/// as `write_tree`, but the depth of the tree costs heap, not call stack.
125///
126/// # Arguments
127/// * `out` - Where the lines go
128/// * `tree` - The tree to write
129/// * `initial_depth` - Depth level of the first line for indentation
130pub fn write_tree_iterative<W: Write>(
131    out: &mut W,
132    tree: &BTreeMap<String, Box<Tree>>,
133    initial_depth: usize,
134) -> io::Result<()> {
135    let mut stack = vec![(tree.iter(), initial_depth)];
136    loop {
137        let next = match stack.last_mut() {
138            Some((children, depth)) => children.next().map(|(key, subtree)| (key, subtree, *depth)),
139            None => break,
140        };
141        match next {
142            Some((key, subtree, depth)) => {
143                writeln!(out, "{}{}", " ".repeat(depth), key)?;
144                stack.push((subtree.0.iter(), depth + 1));
145            }
146            None => {
147                stack.pop();
148            }
149        }
150    }
151    Ok(())
152}
153
154/// Writes the tree with indentation based on depth (SAFE RECURSIVE VERSION)
155///
156/// Recursive like `write_tree`, but a tree deeper than `max_depth` ends with an error of kind
157/// `InvalidInput` instead of a stack overflow. The lines up to that depth are written.
158/// The cost of the depth check is measured in the benchmarks (README, section Benchmarks).
159///
160/// # Arguments
161/// * `out` - Where the lines go
162/// * `tree` - The tree to write
163/// * `depth` - Current depth level for indentation
164/// * `max_depth` - Maximum allowed recursion depth (typical: 1000-5000)
165pub fn write_tree_safe<W: Write>(
166    out: &mut W,
167    tree: &BTreeMap<String, Box<Tree>>,
168    depth: usize,
169    max_depth: usize,
170) -> io::Result<()> {
171    if depth > max_depth {
172        return Err(io::Error::new(
173            io::ErrorKind::InvalidInput,
174            format!("Maximum tree depth {} exceeded (current depth: {})", max_depth, depth),
175        ));
176    }
177    for (key, subtree) in tree {
178        writeln!(out, "{}{}", " ".repeat(depth), key)?;
179        write_tree_safe(out, &subtree.0, depth + 1, max_depth)?;
180    }
181    Ok(())
182}
183
184/// Prints the tree structure with indentation based on depth (RECURSIVE VERSION)
185///
186/// # Arguments
187/// * `tree` - The tree to print
188/// * `depth` - Current depth level for indentation
189pub fn print_tree(tree: &BTreeMap<String, Box<Tree>>, depth: usize) {
190    write_tree(&mut io::stdout().lock(), tree, depth).expect("failed printing to stdout");
191}
192
193/// Prints the tree structure with indentation based on depth (ITERATIVE VERSION)
194///
195/// Uses an explicit stack to avoid recursion while keeping the order of `print_tree`.
196///
197/// # Arguments
198/// * `tree` - The tree to print
199/// * `initial_depth` - Depth level of the first line for indentation
200pub fn print_tree_iterative(tree: &BTreeMap<String, Box<Tree>>, initial_depth: usize) {
201    write_tree_iterative(&mut io::stdout().lock(), tree, initial_depth).expect("failed printing to stdout");
202}
203
204/// Prints the tree structure with indentation based on depth (SAFE RECURSIVE VERSION)
205///
206/// This version prevents stack overflow by enforcing a maximum recursion depth limit.
207/// If the depth exceeds the limit, an error is returned instead of crashing.
208/// The depth check costs less than the measurement noise (README, section Benchmarks).
209///
210/// # Arguments
211/// * `tree` - The tree to print
212/// * `depth` - Current depth level for indentation
213/// * `max_depth` - Maximum allowed recursion depth (typical: 1000-5000)
214///
215/// # Returns
216/// * `Ok(())` if printing succeeded
217/// * `Err(String)` if maximum depth exceeded
218///
219/// # Example
220/// ```
221/// use dir_path_2_tree::*;
222/// let tree = Tree::default();
223/// match print_tree_safe(&tree.0, 0, 1000) {
224///     Ok(()) => println!("Successfully printed tree"),
225///     Err(e) => eprintln!("Error: {}", e),
226/// }
227/// ```
228pub fn print_tree_safe(
229    tree: &BTreeMap<String, Box<Tree>>,
230    depth: usize,
231    max_depth: usize,
232) -> Result<(), String> {
233    write_tree_safe(&mut io::stdout().lock(), tree, depth, max_depth).map_err(|e| e.to_string())
234}
235
236#[cfg(test)]
237mod tests {
238    use super::*;
239
240    #[test]
241    fn test_insert_single_path() {
242        let mut tree = Tree::default();
243        insert_path(&mut tree.0, &["a", "b", "c"]);
244        
245        assert!(tree.0.contains_key("a"));
246        assert!(tree.0["a"].0.contains_key("b"));
247        assert!(tree.0["a"].0["b"].0.contains_key("c"));
248        assert!(tree.0["a"].0["b"].0["c"].0.is_empty());
249    }
250
251    #[test]
252    fn test_insert_multiple_paths() {
253        let mut tree = Tree::default();
254        insert_path(&mut tree.0, &["a", "b", "c"]);
255        insert_path(&mut tree.0, &["a", "b", "d"]);
256        insert_path(&mut tree.0, &["a", "e"]);
257        
258        assert!(tree.0.contains_key("a"));
259        let a_subtree = &tree.0["a"].0;
260        
261        assert!(a_subtree.contains_key("b"));
262        assert!(a_subtree.contains_key("e"));
263        
264        let b_subtree = &a_subtree["b"].0;
265        assert!(b_subtree.contains_key("c"));
266        assert!(b_subtree.contains_key("d"));
267    }
268
269    #[test]
270    fn test_insert_single_element() {
271        let mut tree = Tree::default();
272        insert_path(&mut tree.0, &["single"]);
273        
274        assert!(tree.0.contains_key("single"));
275        assert!(tree.0["single"].0.is_empty());
276    }
277
278    #[test]
279    fn test_insert_empty_parts() {
280        let mut tree = Tree::default();
281        let original = tree.clone();
282        insert_path(&mut tree.0, &[]);
283        
284        assert_eq!(tree, original);
285    }
286
287    #[test]
288    fn test_tree_structure_is_sorted() {
289        let mut tree = Tree::default();
290        insert_path(&mut tree.0, &["z"]);
291        insert_path(&mut tree.0, &["a"]);
292        insert_path(&mut tree.0, &["m"]);
293        
294        let keys: Vec<_> = tree.0.keys().collect();
295        assert_eq!(keys, vec![&"a".to_string(), &"m".to_string(), &"z".to_string()]);
296    }
297
298    #[test]
299    fn test_complex_tree_structure() {
300        let mut tree = Tree::default();
301        insert_path(&mut tree.0, &["config", "database", "host"]);
302        insert_path(&mut tree.0, &["config", "database", "port"]);
303        insert_path(&mut tree.0, &["config", "app", "name"]);
304        insert_path(&mut tree.0, &["logs", "error"]);
305        
306        assert_eq!(tree.0.len(), 2);
307        assert!(tree.0.contains_key("config"));
308        assert!(tree.0.contains_key("logs"));
309        
310        let config = &tree.0["config"].0;
311        assert_eq!(config.len(), 2);
312        assert!(config.contains_key("database"));
313        assert!(config.contains_key("app"));
314        
315        let database = &config["database"].0;
316        assert_eq!(database.len(), 2);
317    }
318
319    #[test]
320    fn test_insert_overlapping_paths() {
321        let mut tree = Tree::default();
322        insert_path(&mut tree.0, &["a", "b"]);
323        insert_path(&mut tree.0, &["a", "b", "c"]);
324        
325        assert!(tree.0["a"].0["b"].0.contains_key("c"));
326    }
327}
dir_path_2_tree/lib.rs

dir_path_2_tree/
lib.rs
