indextree/
node.rs

1//! Node.
2
3#[cfg(not(feature = "std"))]
4use core::fmt;
5
6#[cfg(feature = "deser")]
7use serde::{Deserialize, Serialize};
8
9#[cfg(feature = "std")]
10use std::fmt;
11
12use crate::{id::NodeStamp, NodeId};
13
14#[derive(PartialEq, Eq, Clone, Debug)]
15#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
16pub(crate) enum NodeData<T> {
17    /// The actual data store
18    Data(T),
19    /// The next free node position.
20    NextFree(Option<usize>),
21}
22
23#[derive(PartialEq, Eq, Clone, Debug)]
24#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
25/// A node within a particular `Arena`.
26pub struct Node<T> {
27    // Keep these private (with read-only accessors) so that we can keep them
28    // consistent. E.g. the parent of a node’s child is that node.
29    pub(crate) parent: Option<NodeId>,
30    pub(crate) previous_sibling: Option<NodeId>,
31    pub(crate) next_sibling: Option<NodeId>,
32    pub(crate) first_child: Option<NodeId>,
33    pub(crate) last_child: Option<NodeId>,
34    pub(crate) stamp: NodeStamp,
35    /// The actual data which will be stored within the tree.
36    pub(crate) data: NodeData<T>,
37}
38
39impl<T> Node<T> {
40    /// Returns a reference to the node data.
41    pub fn get(&self) -> &T {
42        if let NodeData::Data(ref data) = self.data {
43            data
44        } else {
45            unreachable!("Try to access a freed node")
46        }
47    }
48
49    /// Returns a mutable reference to the node data.
50    pub fn get_mut(&mut self) -> &mut T {
51        if let NodeData::Data(ref mut data) = self.data {
52            data
53        } else {
54            unreachable!("Try to access a freed node")
55        }
56    }
57
58    /// Creates a new `Node` with the default state and the given data.
59    pub(crate) fn new(data: T) -> Self {
60        Self {
61            parent: None,
62            previous_sibling: None,
63            next_sibling: None,
64            first_child: None,
65            last_child: None,
66            stamp: NodeStamp::default(),
67            data: NodeData::Data(data),
68        }
69    }
70
71    /// Convert a removed `Node` to normal with default state and given data.
72    pub(crate) fn reuse(&mut self, data: T) {
73        debug_assert!(matches!(self.data, NodeData::NextFree(_)));
74        debug_assert!(self.stamp.is_removed());
75        self.stamp.reuse();
76        self.parent = None;
77        self.previous_sibling = None;
78        self.next_sibling = None;
79        self.first_child = None;
80        self.last_child = None;
81        self.data = NodeData::Data(data);
82    }
83
84    /// Returns the ID of the parent node, unless this node is the root of the
85    /// tree.
86    ///
87    /// # Examples
88    ///
89    /// ```
90    /// # use indextree::Arena;
91    /// # let mut arena = Arena::new();
92    /// # let n1 = arena.new_node("1");
93    /// # let n1_1 = arena.new_node("1_1");
94    /// # let n1_2 = arena.new_node("1_2");
95    /// # n1.append(n1_2, &mut arena);
96    /// # let n1_3 = arena.new_node("1_3");
97    /// # n1.append(n1_3, &mut arena);
98    /// # n1.append(n1_1, &mut arena);
99    /// // arena
100    /// // `-- 1
101    /// //     |-- 1_1
102    /// //     |-- 1_2
103    /// //     `-- 1_3
104    /// assert_eq!(arena[n1].parent(), None);
105    /// assert_eq!(arena[n1_1].parent(), Some(n1));
106    /// assert_eq!(arena[n1_2].parent(), Some(n1));
107    /// assert_eq!(arena[n1_3].parent(), Some(n1));
108    /// ```
109    pub fn parent(&self) -> Option<NodeId> {
110        self.parent
111    }
112
113    /// Returns the ID of the first child of this node, unless it has no child.
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// # use indextree::Arena;
119    /// # let mut arena = Arena::new();
120    /// # let n1 = arena.new_node("1");
121    /// # let n1_1 = arena.new_node("1_1");
122    /// # n1.append(n1_1, &mut arena);
123    /// # let n1_2 = arena.new_node("1_2");
124    /// # n1.append(n1_2, &mut arena);
125    /// # let n1_3 = arena.new_node("1_3");
126    /// # n1.append(n1_3, &mut arena);
127    /// // arena
128    /// // `-- 1
129    /// //     |-- 1_1
130    /// //     |-- 1_2
131    /// //     `-- 1_3
132    /// assert_eq!(arena[n1].first_child(), Some(n1_1));
133    /// assert_eq!(arena[n1_1].first_child(), None);
134    /// assert_eq!(arena[n1_2].first_child(), None);
135    /// assert_eq!(arena[n1_3].first_child(), None);
136    /// ```
137    pub fn first_child(&self) -> Option<NodeId> {
138        self.first_child
139    }
140
141    /// Returns the ID of the last child of this node, unless it has no child.
142    ///
143    /// # Examples
144    ///
145    /// ```
146    /// # use indextree::Arena;
147    /// # let mut arena = Arena::new();
148    /// # let n1 = arena.new_node("1");
149    /// # let n1_1 = arena.new_node("1_1");
150    /// # n1.append(n1_1, &mut arena);
151    /// # let n1_2 = arena.new_node("1_2");
152    /// # n1.append(n1_2, &mut arena);
153    /// # let n1_3 = arena.new_node("1_3");
154    /// # n1.append(n1_3, &mut arena);
155    /// // arena
156    /// // `-- 1
157    /// //     |-- 1_1
158    /// //     |-- 1_2
159    /// //     `-- 1_3
160    /// assert_eq!(arena[n1].last_child(), Some(n1_3));
161    /// assert_eq!(arena[n1_1].last_child(), None);
162    /// assert_eq!(arena[n1_2].last_child(), None);
163    /// assert_eq!(arena[n1_3].last_child(), None);
164    /// ```
165    pub fn last_child(&self) -> Option<NodeId> {
166        self.last_child
167    }
168
169    /// Returns the ID of the previous sibling of this node, unless it is a
170    /// first child.
171    ///
172    /// # Examples
173    ///
174    /// ```
175    /// # use indextree::Arena;
176    /// # let mut arena = Arena::new();
177    /// # let n1 = arena.new_node("1");
178    /// # let n1_1 = arena.new_node("1_1");
179    /// # n1.append(n1_1, &mut arena);
180    /// # let n1_2 = arena.new_node("1_2");
181    /// # n1.append(n1_2, &mut arena);
182    /// # let n1_3 = arena.new_node("1_3");
183    /// # n1.append(n1_3, &mut arena);
184    /// // arena
185    /// // `-- 1
186    /// //     |-- 1_1
187    /// //     |-- 1_2
188    /// //     `-- 1_3
189    /// assert_eq!(arena[n1].previous_sibling(), None);
190    /// assert_eq!(arena[n1_1].previous_sibling(), None);
191    /// assert_eq!(arena[n1_2].previous_sibling(), Some(n1_1));
192    /// assert_eq!(arena[n1_3].previous_sibling(), Some(n1_2));
193    /// ```
194    ///
195    /// Note that newly created nodes are independent toplevel nodes, and they
196    /// are not siblings by default.
197    ///
198    /// ```
199    /// # use indextree::Arena;
200    /// let mut arena = Arena::new();
201    /// let n1 = arena.new_node("1");
202    /// let n2 = arena.new_node("2");
203    /// // arena
204    /// // |-- (implicit)
205    /// // |   `-- 1
206    /// // `-- (implicit)
207    /// //     `-- 2
208    /// assert_eq!(arena[n1].previous_sibling(), None);
209    /// assert_eq!(arena[n2].previous_sibling(), None);
210    ///
211    /// n1.insert_after(n2, &mut arena);
212    /// // arena
213    /// // `-- (implicit)
214    /// //     |-- 1
215    /// //     `-- 2
216    /// assert_eq!(arena[n1].previous_sibling(), None);
217    /// assert_eq!(arena[n2].previous_sibling(), Some(n1));
218    /// ```
219    pub fn previous_sibling(&self) -> Option<NodeId> {
220        self.previous_sibling
221    }
222
223    /// Returns the ID of the next sibling of this node, unless it is a
224    /// last child.
225    ///
226    /// # Examples
227    ///
228    /// ```
229    /// # use indextree::Arena;
230    /// # let mut arena = Arena::new();
231    /// # let n1 = arena.new_node("1");
232    /// # let n1_1 = arena.new_node("1_1");
233    /// # n1.append(n1_1, &mut arena);
234    /// # let n1_2 = arena.new_node("1_2");
235    /// # n1.append(n1_2, &mut arena);
236    /// # let n1_3 = arena.new_node("1_3");
237    /// # n1.append(n1_3, &mut arena);
238    /// // arena
239    /// // `-- 1
240    /// //     |-- 1_1
241    /// //     |-- 1_2
242    /// //     `-- 1_3
243    /// assert_eq!(arena[n1].next_sibling(), None);
244    /// assert_eq!(arena[n1_1].next_sibling(), Some(n1_2));
245    /// assert_eq!(arena[n1_2].next_sibling(), Some(n1_3));
246    /// assert_eq!(arena[n1_3].next_sibling(), None);
247    /// ```
248    ///
249    /// Note that newly created nodes are independent toplevel nodes, and they
250    /// are not siblings by default.
251    ///
252    /// ```
253    /// # use indextree::Arena;
254    /// let mut arena = Arena::new();
255    /// let n1 = arena.new_node("1");
256    /// let n2 = arena.new_node("2");
257    /// // arena
258    /// // |-- (implicit)
259    /// // |   `-- 1
260    /// // `-- (implicit)
261    /// //     `-- 2
262    /// assert_eq!(arena[n1].next_sibling(), None);
263    /// assert_eq!(arena[n2].next_sibling(), None);
264    ///
265    /// n1.insert_after(n2, &mut arena);
266    /// // arena
267    /// // `-- (implicit)
268    /// //     |-- 1
269    /// //     `-- 2
270    /// assert_eq!(arena[n1].next_sibling(), Some(n2));
271    /// assert_eq!(arena[n2].next_sibling(), None);
272    /// ```
273    pub fn next_sibling(&self) -> Option<NodeId> {
274        self.next_sibling
275    }
276
277    /// Checks if the node is marked as removed.
278    ///
279    /// # Examples
280    ///
281    /// ```
282    /// # use indextree::Arena;
283    /// # let mut arena = Arena::new();
284    /// # let n1 = arena.new_node("1");
285    /// # let n1_1 = arena.new_node("1_1");
286    /// # n1.append(n1_1, &mut arena);
287    /// # let n1_2 = arena.new_node("1_2");
288    /// # n1.append(n1_2, &mut arena);
289    /// # let n1_3 = arena.new_node("1_3");
290    /// # n1.append(n1_3, &mut arena);
291    /// // arena
292    /// // `-- 1
293    /// //     |-- 1_1
294    /// //     |-- 1_2 *
295    /// //     `-- 1_3
296    /// assert_eq!(arena[n1_1].next_sibling(), Some(n1_2));
297    /// assert_eq!(arena[n1_2].parent(), Some(n1));
298    /// assert!(!arena[n1_2].is_removed());
299    /// assert_eq!(arena[n1_3].previous_sibling(), Some(n1_2));
300    ///
301    /// n1_2.remove(&mut arena);
302    /// // arena
303    /// // `-- 1
304    /// //     |-- 1_1
305    /// //     `-- 1_3
306    /// assert_eq!(arena[n1_1].next_sibling(), Some(n1_3));
307    /// assert_eq!(arena[n1_2].parent(), None);
308    /// assert!(arena[n1_2].is_removed());
309    /// assert_eq!(arena[n1_3].previous_sibling(), Some(n1_1));
310    /// ```
311    pub fn is_removed(&self) -> bool {
312        self.stamp.is_removed()
313    }
314
315    /// Checks if the node is detached.
316    pub(crate) fn is_detached(&self) -> bool {
317        self.parent.is_none() && self.previous_sibling.is_none() && self.next_sibling.is_none()
318    }
319}
320
321impl<T> fmt::Display for Node<T> {
322    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
323        if let Some(parent) = self.parent {
324            write!(f, "parent: {}; ", parent)?;
325        } else {
326            write!(f, "no parent; ")?;
327        }
328        if let Some(previous_sibling) = self.previous_sibling {
329            write!(f, "previous sibling: {}; ", previous_sibling)?;
330        } else {
331            write!(f, "no previous sibling; ")?;
332        }
333        if let Some(next_sibling) = self.next_sibling {
334            write!(f, "next sibling: {}; ", next_sibling)?;
335        } else {
336            write!(f, "no next sibling; ")?;
337        }
338        if let Some(first_child) = self.first_child {
339            write!(f, "first child: {}; ", first_child)?;
340        } else {
341            write!(f, "no first child; ")?;
342        }
343        if let Some(last_child) = self.last_child {
344            write!(f, "last child: {}; ", last_child)?;
345        } else {
346            write!(f, "no last child; ")?;
347        }
348        Ok(())
349    }
350}
indextree/node.rs

indextree/
node.rs
