orinium_browser/engine/
tree.rs

1//! Generic tree structure for DOM, render tree, or other hierarchical data.
2//!
3//! # Overview
4//! - `TreeNode<T>` stores a node value, parent, and children.
5//! - `Tree<T>` stores a root node and provides traversal, mapping, and searching utilities.
6
7use std::cell::RefCell;
8use std::fmt::{self, Debug, Display, Formatter};
9use std::rc::{Rc, Weak};
10
11/// Alias for a reference-counted tree node
12pub type NodeRef<T> = Rc<RefCell<TreeNode<T>>>;
13
14/// A single tree node
15#[derive(Clone)]
16pub struct TreeNode<T> {
17    pub value: T,
18    parent: Option<Weak<RefCell<TreeNode<T>>>>,
19    children: Vec<NodeRef<T>>,
20}
21
22impl<T> TreeNode<T> {
23    /// Create a new node wrapped in Rc<RefCell<_>>
24    pub fn new(value: T) -> NodeRef<T> {
25        Rc::new(RefCell::new(Self {
26            value,
27            parent: None,
28            children: Vec::new(),
29        }))
30    }
31
32    /// Returns the parent node, if any
33    pub fn parent(&self) -> Option<NodeRef<T>> {
34        self.parent.as_ref().and_then(|w| w.upgrade())
35    }
36
37    /// Returns slice of child nodes
38    pub fn children(&self) -> &[NodeRef<T>] {
39        &self.children
40    }
41
42    /// Remove all children of this node
43    pub fn clear_children(&mut self) {
44        self.children.clear();
45    }
46
47    /// Add a child node
48    pub fn add_child(parent: &NodeRef<T>, child: NodeRef<T>) {
49        child.borrow_mut().parent = Some(Rc::downgrade(parent));
50        parent.borrow_mut().children.push(child);
51    }
52
53    /// Insert a child at a given position
54    pub fn insert_child_at(parent: &NodeRef<T>, index: usize, child: NodeRef<T>) {
55        child.borrow_mut().parent = Some(Rc::downgrade(parent));
56        parent.borrow_mut().children.insert(index, child);
57    }
58
59    /// Create a child with value and add it to parent
60    pub fn add_child_value(parent: &NodeRef<T>, value: T) -> NodeRef<T> {
61        let child = Self::new(value);
62        Self::add_child(parent, Rc::clone(&child));
63        child
64    }
65
66    /// Replace child at given index
67    pub fn replace_child(
68        parent: &NodeRef<T>,
69        index: usize,
70        new_child: NodeRef<T>,
71    ) -> Option<NodeRef<T>> {
72        let mut p = parent.borrow_mut();
73        if index < p.children.len() {
74            let old_child = std::mem::replace(&mut p.children[index], new_child);
75            old_child.borrow_mut().parent = None;
76            Some(old_child)
77        } else {
78            None
79        }
80    }
81
82    /// Find direct children matching predicate
83    pub fn find_children_by<F>(&self, predicate: F) -> Vec<NodeRef<T>>
84    where
85        F: Fn(&T) -> bool,
86    {
87        self.children
88            .iter()
89            .filter(|c| predicate(&c.borrow().value))
90            .cloned()
91            .collect()
92    }
93
94    /// Clone node (optionally deep)
95    pub fn clone_node(&self, deep: bool) -> NodeRef<T>
96    where
97        T: Clone,
98    {
99        let new_node = Rc::new(RefCell::new(TreeNode {
100            value: self.value.clone(),
101            children: Vec::new(),
102            parent: None,
103        }));
104
105        if deep {
106            for child in &self.children {
107                let child_clone = child.borrow().clone_node(true);
108                child_clone.borrow_mut().parent = Some(Rc::downgrade(&new_node));
109                new_node.borrow_mut().children.push(child_clone);
110            }
111        }
112
113        new_node
114    }
115}
116
117/// Represents a tree with a single root node
118#[derive(Clone)]
119pub struct Tree<T> {
120    pub root: NodeRef<T>,
121}
122
123impl<T: Clone> Tree<T> {
124    /// Create a new tree with root value
125    pub fn new(root_value: T) -> Self {
126        Self {
127            root: TreeNode::new(root_value),
128        }
129    }
130
131    /// Recursively traverse all nodes, applying a function
132    pub fn traverse<F>(&self, mut f: F)
133    where
134        F: FnMut(&NodeRef<T>),
135    {
136        fn visit<T, F>(node: &NodeRef<T>, f: &mut F)
137        where
138            F: FnMut(&NodeRef<T>),
139        {
140            f(node);
141            for child in &node.borrow().children {
142                visit(child, f);
143            }
144        }
145        visit(&self.root, &mut f);
146    }
147
148    /// Map each node value to another type, returning a new Tree
149    pub fn map<U, F>(&self, f: F) -> Tree<U>
150    where
151        F: Fn(&T) -> U,
152        U: Clone,
153    {
154        fn map_node<T, U, F>(node: &NodeRef<T>, f: &F) -> NodeRef<U>
155        where
156            F: Fn(&T) -> U,
157            U: Clone,
158        {
159            let n = node.borrow();
160            let new_node = TreeNode::new(f(&n.value));
161            for child in &n.children {
162                let mapped_child = map_node(child, f);
163                TreeNode::add_child(&new_node, mapped_child);
164            }
165            new_node
166        }
167
168        Tree {
169            root: map_node(&self.root, &f),
170        }
171    }
172
173    /// Map using the NodeRef itself (for access to parent/children)
174    pub fn map_with_node<U, F>(&self, f: F) -> Tree<U>
175    where
176        F: Fn(&NodeRef<T>) -> U,
177        U: Clone,
178    {
179        fn map_node<T, U, F>(node: &NodeRef<T>, f: &F) -> NodeRef<U>
180        where
181            F: Fn(&NodeRef<T>) -> U,
182            U: Clone,
183        {
184            let new_node = TreeNode::new(f(node));
185            for child in &node.borrow().children {
186                let mapped_child = map_node(child, f);
187                TreeNode::add_child(&new_node, mapped_child);
188            }
189            new_node
190        }
191
192        Tree {
193            root: map_node(&self.root, &f),
194        }
195    }
196
197    /// Find all nodes in the tree that satisfy a predicate
198    pub fn find_all<F>(&self, predicate: F) -> Vec<NodeRef<T>>
199    where
200        F: Fn(&T) -> bool,
201    {
202        let mut result = Vec::new();
203        self.traverse(|node| {
204            if predicate(&node.borrow().value) {
205                result.push(Rc::clone(node));
206            }
207        });
208        result
209    }
210}
211
212impl<T: Clone + Debug> Display for Tree<T> {
213    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
214        fn fmt_node<T: Clone + Debug>(
215            node: &NodeRef<T>,
216            f: &mut Formatter<'_>,
217            prefix: &str,
218            is_last: bool,
219        ) -> fmt::Result {
220            let n = node.borrow();
221            let connector = if prefix.is_empty() {
222                ""
223            } else if is_last {
224                "└── "
225            } else {
226                "├── "
227            };
228            writeln!(f, "{}{}{:?}", prefix, connector, n.value)?;
229            let child_count = n.children.len();
230            for (i, child) in n.children.iter().enumerate() {
231                let mut new_prefix = prefix.to_string();
232                new_prefix.push_str(if is_last { "    " } else { "│   " });
233                fmt_node(child, f, &new_prefix, i == child_count - 1)?;
234            }
235            Ok(())
236        }
237        fmt_node(&self.root, f, "", true)
238    }
239}
240
241impl<T: Clone + Debug> Debug for Tree<T> {
242    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
243        write!(f, "{}", self)
244    }
245}
orinium_browser/engine/tree.rs

orinium_browser/engine/
tree.rs
