1 //! Node.
2 
3 #[cfg(not(feature = "std"))]
4 use core::fmt;
5 
6 #[cfg(feature = "deser")]
7 use serde::{Deserialize, Serialize};
8 
9 #[cfg(feature = "std")]
10 use std::fmt;
11 
12 use crate::{id::NodeStamp, NodeId};
13 
14 #[derive(PartialEq, Eq, Clone, Debug)]
15 #[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
16 pub(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`.
26 pub 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 
39 impl<T> Node<T> {
40     /// Returns a reference to the node data.
get(&self) -> &T41     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.
get_mut(&mut self) -> &mut T50     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.
new(data: T) -> Self59     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.
reuse(&mut self, data: T)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     /// ```
parent(&self) -> Option<NodeId>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     /// ```
first_child(&self) -> Option<NodeId>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     /// ```
last_child(&self) -> Option<NodeId>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     /// ```
previous_sibling(&self) -> Option<NodeId>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     /// ```
next_sibling(&self) -> Option<NodeId>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     /// ```
is_removed(&self) -> bool311     pub fn is_removed(&self) -> bool {
312         self.stamp.is_removed()
313     }
314 
315     /// Checks if the node is detached.
is_detached(&self) -> bool316     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 
321 impl<T> fmt::Display for Node<T> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result322     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 }
351