indextree/
id.rs

1//! Node ID.
2
3#[cfg(not(feature = "std"))]
4use core::{fmt, num::NonZeroUsize};
5
6#[cfg(feature = "deser")]
7use serde::{Deserialize, Serialize};
8
9#[cfg(feature = "std")]
10use std::{fmt, num::NonZeroUsize};
11
12#[allow(deprecated)]
13use crate::{
14    debug_pretty_print::DebugPrettyPrint,
15    relations::{insert_last_unchecked, insert_with_neighbors},
16    siblings_range::SiblingsRange,
17    Ancestors, Arena, Children, Descendants, FollowingSiblings, NodeError, PrecedingSiblings,
18    Predecessors, ReverseChildren, ReverseTraverse, Traverse,
19};
20
21#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Debug, Hash)]
22#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
23/// A node identifier within a particular [`Arena`].
24///
25/// This ID is used to get [`Node`] references from an [`Arena`].
26///
27/// [`Arena`]: struct.Arena.html
28/// [`Node`]: struct.Node.html
29pub struct NodeId {
30    /// One-based index.
31    index1: NonZeroUsize,
32    stamp: NodeStamp,
33}
34
35/// A stamp for node reuse, use to detect if the node of a `NodeId` point to
36/// is still the same node.
37#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Debug, Hash, Default)]
38#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
39pub(crate) struct NodeStamp(i16);
40
41impl NodeStamp {
42    pub fn is_removed(self) -> bool {
43        self.0.is_negative()
44    }
45
46    pub fn as_removed(&mut self) {
47        debug_assert!(!self.is_removed());
48        self.0 = if self.0 < i16::MAX {
49            -self.0 - 1
50        } else {
51            -self.0
52        };
53    }
54
55    pub fn reuseable(self) -> bool {
56        debug_assert!(self.is_removed());
57        self.0 > i16::MIN
58    }
59
60    pub fn reuse(&mut self) -> Self {
61        debug_assert!(self.reuseable());
62        self.0 = -self.0;
63        *self
64    }
65}
66
67impl fmt::Display for NodeId {
68    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69        write!(f, "{}", self.index1)
70    }
71}
72
73impl From<NodeId> for NonZeroUsize {
74    fn from(value: NodeId) -> NonZeroUsize {
75        value.index1
76    }
77}
78
79impl From<NodeId> for usize {
80    fn from(value: NodeId) -> usize {
81        value.index1.get()
82    }
83}
84
85impl NodeId {
86    /// Returns zero-based index.
87    pub(crate) fn index0(self) -> usize {
88        // This is totally safe because `self.index1 >= 1` is guaranteed by
89        // `NonZeroUsize` type.
90        self.index1.get() - 1
91    }
92
93    /// Creates a new `NodeId` from the given one-based index.
94    pub(crate) fn from_non_zero_usize(index1: NonZeroUsize, stamp: NodeStamp) -> Self {
95        NodeId { index1, stamp }
96    }
97
98    /// Return if the `Node` of NodeId point to is removed.
99    pub fn is_removed<T>(self, arena: &Arena<T>) -> bool {
100        arena[self].stamp != self.stamp
101    }
102
103    /// Returns an iterator of IDs of this node and its ancestors.
104    ///
105    /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
106    /// the node itself.
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// # use indextree::Arena;
112    /// # let mut arena = Arena::new();
113    /// # let n1 = arena.new_node("1");
114    /// # let n1_1 = arena.new_node("1_1");
115    /// # n1.append(n1_1, &mut arena);
116    /// # let n1_1_1 = arena.new_node("1_1_1");
117    /// # n1_1.append(n1_1_1, &mut arena);
118    /// # let n1_1_1_1 = arena.new_node("1_1_1_1");
119    /// # n1_1_1.append(n1_1_1_1, &mut arena);
120    /// # let n1_2 = arena.new_node("1_2");
121    /// # n1.append(n1_2, &mut arena);
122    /// # let n1_3 = arena.new_node("1_3");
123    /// # n1.append(n1_3, &mut arena);
124    /// #
125    /// // arena
126    /// // `-- 1                                                // #3
127    /// //     |-- 1_1                                          // #2
128    /// //     |   `-- 1_1_1 *                                  // #1
129    /// //     |       `-- 1_1_1_1
130    /// //     _-- 1_2
131    /// //     `-- 1_3
132    ///
133    /// let mut iter = n1_1_1.ancestors(&arena);
134    /// assert_eq!(iter.next(), Some(n1_1_1));                  // #1
135    /// assert_eq!(iter.next(), Some(n1_1));                    // #2
136    /// assert_eq!(iter.next(), Some(n1));                      // #3
137    /// assert_eq!(iter.next(), None);
138    /// ```
139    ///
140    /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
141    pub fn ancestors<T>(self, arena: &Arena<T>) -> Ancestors<'_, T> {
142        Ancestors::new(arena, self)
143    }
144
145    /// Returns an iterator of IDs of this node and its predecessors.
146    ///
147    /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
148    /// the node itself.
149    ///
150    /// # Examples
151    ///
152    /// ```
153    /// # use indextree::Arena;
154    /// # let mut arena = Arena::new();
155    /// # let n1 = arena.new_node("1");
156    /// # let n1_1 = arena.new_node("1_1");
157    /// # n1.append(n1_1, &mut arena);
158    /// # let n1_1_1 = arena.new_node("1_1_1");
159    /// # n1_1.append(n1_1_1, &mut arena);
160    /// # let n1_1_1_1 = arena.new_node("1_1_1_1");
161    /// # n1_1_1.append(n1_1_1_1, &mut arena);
162    /// # let n1_2 = arena.new_node("1_2");
163    /// # n1.append(n1_2, &mut arena);
164    /// # let n1_3 = arena.new_node("1_3");
165    /// # n1.append(n1_3, &mut arena);
166    /// #
167    /// // arena
168    /// // `-- 1                                                // #3
169    /// //     |-- 1_1                                          // #2
170    /// //     |   `-- 1_1_1 *                                  // #1
171    /// //     |       `-- 1_1_1_1
172    /// //     _-- 1_2
173    /// //     `-- 1_3
174    ///
175    /// let mut iter = n1_1_1.predecessors(&arena);
176    /// assert_eq!(iter.next(), Some(n1_1_1));                  // #1
177    /// assert_eq!(iter.next(), Some(n1_1));                    // #2
178    /// assert_eq!(iter.next(), Some(n1));                      // #3
179    /// assert_eq!(iter.next(), None);
180    /// ```
181    ///
182    /// ```
183    /// # use indextree::Arena;
184    /// # let mut arena = Arena::new();
185    /// # let n1 = arena.new_node("1");
186    /// # let n1_1 = arena.new_node("1_1");
187    /// # n1.append(n1_1, &mut arena);
188    /// # let n1_2 = arena.new_node("1_2");
189    /// # n1.append(n1_2, &mut arena);
190    /// # let n1_2_1 = arena.new_node("1_2_1");
191    /// # n1_2.append(n1_2_1, &mut arena);
192    /// # let n1_2_1_1 = arena.new_node("1_2_1_1");
193    /// # n1_2_1.append(n1_2_1_1, &mut arena);
194    /// # let n1_3 = arena.new_node("1_3");
195    /// # n1.append(n1_3, &mut arena);
196    /// # let n1_4 = arena.new_node("1_4");
197    /// # n1.append(n1_4, &mut arena);
198    /// #
199    /// // arena
200    /// // `-- 1                                                // #4
201    /// //     |-- 1_1                                          // #3
202    /// //     |-- 1_2                                          // #2
203    /// //     |   `-- 1_2_1 *                                  // #1
204    /// //     |       `-- 1_2_1_1
205    /// //     _-- 1_3
206    /// //     `-- 1_4
207    ///
208    /// let mut iter = n1_2_1.predecessors(&arena);
209    /// assert_eq!(iter.next(), Some(n1_2_1));                  // #1
210    /// assert_eq!(iter.next(), Some(n1_2));                    // #2
211    /// assert_eq!(iter.next(), Some(n1_1));                    // #3
212    /// assert_eq!(iter.next(), Some(n1));                      // #4
213    /// assert_eq!(iter.next(), None);
214    /// ```
215    ///
216    /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
217    pub fn predecessors<T>(self, arena: &Arena<T>) -> Predecessors<'_, T> {
218        Predecessors::new(arena, self)
219    }
220
221    /// Returns an iterator of IDs of this node and the siblings before it.
222    ///
223    /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
224    /// the node itself.
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_1_1 = arena.new_node("1_1_1");
235    /// # n1_1.append(n1_1_1, &mut arena);
236    /// # let n1_2 = arena.new_node("1_2");
237    /// # n1.append(n1_2, &mut arena);
238    /// # let n1_3 = arena.new_node("1_3");
239    /// # n1.append(n1_3, &mut arena);
240    /// #
241    /// // arena
242    /// // `-- 1
243    /// //     |-- 1_1                                          // #2
244    /// //     |   `-- 1_1_1
245    /// //     |-- 1_2                                          // #1
246    /// //     `-- 1_3
247    ///
248    /// let mut iter = n1_2.preceding_siblings(&arena);
249    /// assert_eq!(iter.next(), Some(n1_2));                    // #1
250    /// assert_eq!(iter.next(), Some(n1_1));                    // #2
251    /// assert_eq!(iter.next(), None);
252    /// ```
253    ///
254    /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
255    pub fn preceding_siblings<T>(self, arena: &Arena<T>) -> PrecedingSiblings<'_, T> {
256        PrecedingSiblings::new(arena, self)
257    }
258
259    /// Returns an iterator of IDs of this node and the siblings after
260    /// it.
261    ///
262    /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
263    /// the node itself.
264    ///
265    /// # Examples
266    ///
267    /// ```
268    /// # use indextree::Arena;
269    /// # let mut arena = Arena::new();
270    /// # let n1 = arena.new_node("1");
271    /// # let n1_1 = arena.new_node("1_1");
272    /// # n1.append(n1_1, &mut arena);
273    /// # let n1_1_1 = arena.new_node("1_1_1");
274    /// # n1_1.append(n1_1_1, &mut arena);
275    /// # let n1_2 = arena.new_node("1_2");
276    /// # n1.append(n1_2, &mut arena);
277    /// # let n1_3 = arena.new_node("1_3");
278    /// # n1.append(n1_3, &mut arena);
279    /// #
280    /// // arena
281    /// // `-- 1
282    /// //     |-- 1_1
283    /// //     |   `-- 1_1_1
284    /// //     |-- 1_2                                          // #1
285    /// //     `-- 1_3                                          // #2
286    ///
287    /// let mut iter = n1_2.following_siblings(&arena);
288    /// assert_eq!(iter.next(), Some(n1_2));                    // #1
289    /// assert_eq!(iter.next(), Some(n1_3));                    // #2
290    /// assert_eq!(iter.next(), None);
291    /// ```
292    ///
293    /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
294    pub fn following_siblings<T>(self, arena: &Arena<T>) -> FollowingSiblings<'_, T> {
295        FollowingSiblings::new(arena, self)
296    }
297
298    /// Returns an iterator of IDs of this node’s children.
299    ///
300    /// # Examples
301    ///
302    /// ```
303    /// # use indextree::Arena;
304    /// # let mut arena = Arena::new();
305    /// # let n1 = arena.new_node("1");
306    /// # let n1_1 = arena.new_node("1_1");
307    /// # n1.append(n1_1, &mut arena);
308    /// # let n1_1_1 = arena.new_node("1_1_1");
309    /// # n1_1.append(n1_1_1, &mut arena);
310    /// # let n1_2 = arena.new_node("1_2");
311    /// # n1.append(n1_2, &mut arena);
312    /// # let n1_3 = arena.new_node("1_3");
313    /// # n1.append(n1_3, &mut arena);
314    /// #
315    /// // arena
316    /// // `-- 1
317    /// //     |-- 1_1                                          // #1
318    /// //     |   `-- 1_1_1
319    /// //     |-- 1_2                                          // #2
320    /// //     `-- 1_3                                          // #3
321    ///
322    /// let mut iter = n1.children(&arena);
323    /// assert_eq!(iter.next(), Some(n1_1));                    // #1
324    /// assert_eq!(iter.next(), Some(n1_2));                    // #2
325    /// assert_eq!(iter.next(), Some(n1_3));                    // #3
326    /// assert_eq!(iter.next(), None);
327    /// ```
328    pub fn children<T>(self, arena: &Arena<T>) -> Children<'_, T> {
329        Children::new(arena, self)
330    }
331
332    /// Returns an iterator of IDs of this node’s children, in reverse
333    /// order.
334    ///
335    /// # Examples
336    ///
337    /// ```
338    /// # use indextree::Arena;
339    /// # let mut arena = Arena::new();
340    /// # let n1 = arena.new_node("1");
341    /// # let n1_1 = arena.new_node("1_1");
342    /// # n1.append(n1_1, &mut arena);
343    /// # let n1_1_1 = arena.new_node("1_1_1");
344    /// # n1_1.append(n1_1_1, &mut arena);
345    /// # let n1_2 = arena.new_node("1_2");
346    /// # n1.append(n1_2, &mut arena);
347    /// # let n1_3 = arena.new_node("1_3");
348    /// # n1.append(n1_3, &mut arena);
349    /// #
350    /// // arena
351    /// // `-- 1
352    /// //     |-- 1_1                                          // #3
353    /// //     |   `-- 1_1_1
354    /// //     |-- 1_2                                          // #2
355    /// //     `-- 1_3                                          // #1
356    ///
357    /// let mut iter = n1.reverse_children(&arena);
358    /// assert_eq!(iter.next(), Some(n1_3));                    // #1
359    /// assert_eq!(iter.next(), Some(n1_2));                    // #2
360    /// assert_eq!(iter.next(), Some(n1_1));                    // #3
361    /// assert_eq!(iter.next(), None);
362    /// ```
363    #[allow(deprecated)]
364    #[deprecated(
365        since = "4.7.0",
366        note = "please, use `NodeId::children().rev()` instead if you want to iterate in reverse"
367    )]
368    pub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<'_, T> {
369        ReverseChildren::new(arena, self)
370    }
371
372    /// An iterator of the IDs of a given node and its descendants, as a pre-order depth-first search where children are visited in insertion order.
373    ///
374    /// i.e. node -> first child -> second child
375    ///
376    /// Parent nodes appear before the descendants.
377    /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
378    /// the node itself.
379    ///
380    /// # Examples
381    ///
382    /// ```
383    /// # use indextree::Arena;
384    /// # let mut arena = Arena::new();
385    /// # let n1 = arena.new_node("1");
386    /// # let n1_1 = arena.new_node("1_1");
387    /// # n1.append(n1_1, &mut arena);
388    /// # let n1_1_1 = arena.new_node("1_1_1");
389    /// # n1_1.append(n1_1_1, &mut arena);
390    /// # let n1_1_1_1 = arena.new_node("1_1_1_1");
391    /// # n1_1_1.append(n1_1_1_1, &mut arena);
392    /// # let n1_2 = arena.new_node("1_2");
393    /// # n1.append(n1_2, &mut arena);
394    /// # let n1_3 = arena.new_node("1_3");
395    /// # n1.append(n1_3, &mut arena);
396    /// #
397    /// // arena
398    /// // `-- 1                                                // #1
399    /// //     |-- 1_1                                          // #2
400    /// //     |   `-- 1_1_1                                    // #3
401    /// //     |       `-- 1_1_1_1                              // #4
402    /// //     |-- 1_2                                          // #5
403    /// //     `-- 1_3                                          // #6
404    ///
405    /// let mut iter = n1.descendants(&arena);
406    /// assert_eq!(iter.next(), Some(n1));                      // #1
407    /// assert_eq!(iter.next(), Some(n1_1));                    // #2
408    /// assert_eq!(iter.next(), Some(n1_1_1));                  // #3
409    /// assert_eq!(iter.next(), Some(n1_1_1_1));                // #4
410    /// assert_eq!(iter.next(), Some(n1_2));                    // #5
411    /// assert_eq!(iter.next(), Some(n1_3));                    // #6
412    /// assert_eq!(iter.next(), None);
413    /// ```
414    ///
415    /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
416    pub fn descendants<T>(self, arena: &Arena<T>) -> Descendants<'_, T> {
417        Descendants::new(arena, self)
418    }
419
420    /// An iterator of the "sides" of a node visited during a depth-first pre-order traversal,
421    /// where node sides are visited start to end and children are visited in insertion order.
422    ///
423    /// i.e. node.start -> first child -> second child -> node.end
424    ///
425    /// # Examples
426    ///
427    /// ```
428    /// # use indextree::{Arena, NodeEdge};
429    /// # let mut arena = Arena::new();
430    /// # let n1 = arena.new_node("1");
431    /// # let n1_1 = arena.new_node("1_1");
432    /// # n1.append(n1_1, &mut arena);
433    /// # let n1_1_1 = arena.new_node("1_1_1");
434    /// # n1_1.append(n1_1_1, &mut arena);
435    /// # let n1_2 = arena.new_node("1_2");
436    /// # n1.append(n1_2, &mut arena);
437    /// # let n1_3 = arena.new_node("1_3");
438    /// # n1.append(n1_3, &mut arena);
439    /// #
440    /// // arena
441    /// // `-- 1                                                // #1, #10
442    /// //     |-- 1_1                                          // #2, #5
443    /// //     |   `-- 1_1_1                                    // #3, #4
444    /// //     |-- 1_2                                          // #6, #7
445    /// //     `-- 1_3                                          // #8, #9
446    ///
447    /// let mut iter = n1.traverse(&arena);
448    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));     // #1
449    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));   // #2
450    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1))); // #3
451    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));   // #4
452    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));     // #5
453    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));   // #6
454    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));     // #7
455    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));   // #8
456    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));     // #9
457    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1)));       // #10
458    /// assert_eq!(iter.next(), None);
459    /// ```
460    pub fn traverse<T>(self, arena: &Arena<T>) -> Traverse<'_, T> {
461        Traverse::new(arena, self)
462    }
463
464    /// An iterator of the "sides" of a node visited during a depth-first pre-order traversal,
465    /// where nodes are visited end to start and children are visited in reverse insertion order.
466    ///
467    /// i.e. node.end -> second child -> first child -> node.start
468    ///
469    /// # Examples
470    ///
471    /// ```
472    /// # use indextree::{Arena, NodeEdge};
473    /// # let mut arena = Arena::new();
474    /// # let n1 = arena.new_node("1");
475    /// # let n1_1 = arena.new_node("1_1");
476    /// # n1.append(n1_1, &mut arena);
477    /// # let n1_1_1 = arena.new_node("1_1_1");
478    /// # n1_1.append(n1_1_1, &mut arena);
479    /// # let n1_2 = arena.new_node("1_2");
480    /// # n1.append(n1_2, &mut arena);
481    /// # let n1_3 = arena.new_node("1_3");
482    /// # n1.append(n1_3, &mut arena);
483    /// #
484    /// // arena
485    /// // `-- 1                                                // #1, #10
486    /// //     |-- 1_1                                          // #6, #9
487    /// //     |   `-- 1_1_1                                    // #7, #8
488    /// //     |-- 1_2                                          // #4, #5
489    /// //     `-- 1_3                                          // #2, #3
490    ///
491    /// let mut iter = n1.reverse_traverse(&arena);
492    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1)));       // #1
493    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));     // #2
494    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));   // #3
495    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));     // #4
496    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));   // #5
497    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));     // #6
498    /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));   // #7
499    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1))); // #8
500    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));   // #9
501    /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));     // #10
502    /// assert_eq!(iter.next(), None);
503    /// ```
504    ///
505    /// ```
506    /// # use indextree::{Arena, NodeEdge};
507    /// # let mut arena = Arena::new();
508    /// # let n1 = arena.new_node("1");
509    /// # let n1_1 = arena.new_node("1_1");
510    /// # n1.append(n1_1, &mut arena);
511    /// # let n1_1_1 = arena.new_node("1_1_1");
512    /// # n1_1.append(n1_1_1, &mut arena);
513    /// # let n1_2 = arena.new_node("1_2");
514    /// # n1.append(n1_2, &mut arena);
515    /// # let n1_3 = arena.new_node("1_3");
516    /// # n1.append(n1_3, &mut arena);
517    /// #
518    /// // arena
519    /// // `-- 1                                                // #1, #10
520    /// //     |-- 1_1                                          // #6, #9
521    /// //     |   `-- 1_1_1                                    // #7, #8
522    /// //     |-- 1_2                                          // #4, #5
523    /// //     `-- 1_3                                          // #2, #3
524    /// let traverse = n1.traverse(&arena).collect::<Vec<_>>();
525    /// let mut reverse = n1.reverse_traverse(&arena).collect::<Vec<_>>();
526    /// reverse.reverse();
527    /// assert_eq!(traverse, reverse);
528    /// ```
529    pub fn reverse_traverse<T>(self, arena: &Arena<T>) -> ReverseTraverse<'_, T> {
530        ReverseTraverse::new(arena, self)
531    }
532
533    /// Detaches a node from its parent and siblings. Children are not affected.
534    ///
535    /// # Examples
536    ///
537    /// ```
538    /// # use indextree::{Arena, NodeEdge};
539    /// # let mut arena = Arena::new();
540    /// # let n1 = arena.new_node("1");
541    /// # let n1_1 = arena.new_node("1_1");
542    /// # n1.append(n1_1, &mut arena);
543    /// # let n1_1_1 = arena.new_node("1_1_1");
544    /// # n1_1.append(n1_1_1, &mut arena);
545    /// # let n1_2 = arena.new_node("1_2");
546    /// # n1.append(n1_2, &mut arena);
547    /// # let n1_3 = arena.new_node("1_3");
548    /// # n1.append(n1_3, &mut arena);
549    /// #
550    /// // arena
551    /// // `-- (implicit)
552    /// //     `-- 1
553    /// //         |-- 1_1
554    /// //         |   `-- 1_1_1
555    /// //         |-- 1_2 *
556    /// //         `-- 1_3
557    ///
558    /// n1_2.detach(&mut arena);
559    /// // arena
560    /// // |-- (implicit)
561    /// // |   `-- 1
562    /// // |       |-- 1_1
563    /// // |       |   `-- 1_1_1
564    /// // |       `-- 1_3
565    /// // `-- (implicit)
566    /// //     `-- 1_2 *
567    ///
568    /// assert!(arena[n1_2].parent().is_none());
569    /// assert!(arena[n1_2].previous_sibling().is_none());
570    /// assert!(arena[n1_2].next_sibling().is_none());
571    ///
572    /// let mut iter = n1.descendants(&arena);
573    /// assert_eq!(iter.next(), Some(n1));
574    /// assert_eq!(iter.next(), Some(n1_1));
575    /// assert_eq!(iter.next(), Some(n1_1_1));
576    /// assert_eq!(iter.next(), Some(n1_3));
577    /// assert_eq!(iter.next(), None);
578    /// ```
579    pub fn detach<T>(self, arena: &mut Arena<T>) {
580        let range = SiblingsRange::new(self, self).detach_from_siblings(arena);
581        range
582            .rewrite_parents(arena, None)
583            .expect("Should never happen: `None` as parent is always valid");
584
585        // Ensure the node is surely detached.
586        debug_assert!(
587            arena[self].is_detached(),
588            "The node should be successfully detached"
589        );
590    }
591
592    /// Appends a new child to this node, after existing children.
593    ///
594    /// # Panics
595    ///
596    /// Panics if:
597    ///
598    /// * the given new child is `self`, or
599    /// * the given new child is an ancestor of `self`, or
600    /// * the current node or the given new child was already [`remove`]d.
601    ///
602    /// To check if the node is removed or not, use [`Node::is_removed()`].
603    ///
604    /// # Examples
605    ///
606    /// ```
607    /// # use indextree::Arena;
608    /// let mut arena = Arena::new();
609    /// let n1 = arena.new_node("1");
610    /// let n1_1 = arena.new_node("1_1");
611    /// n1.append(n1_1, &mut arena);
612    /// let n1_2 = arena.new_node("1_2");
613    /// n1.append(n1_2, &mut arena);
614    /// let n1_3 = arena.new_node("1_3");
615    /// n1.append(n1_3, &mut arena);
616    ///
617    /// // arena
618    /// // `-- 1
619    /// //     |-- 1_1
620    /// //     |-- 1_2
621    /// //     `-- 1_3
622    ///
623    /// let mut iter = n1.descendants(&arena);
624    /// assert_eq!(iter.next(), Some(n1));
625    /// assert_eq!(iter.next(), Some(n1_1));
626    /// assert_eq!(iter.next(), Some(n1_2));
627    /// assert_eq!(iter.next(), Some(n1_3));
628    /// assert_eq!(iter.next(), None);
629    /// ```
630    ///
631    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
632    /// [`remove`]: struct.NodeId.html#method.remove
633    pub fn append<T>(self, new_child: NodeId, arena: &mut Arena<T>) {
634        self.checked_append(new_child, arena)
635            .expect("Preconditions not met: invalid argument");
636    }
637
638    /// Appends a new child to this node, after existing children.
639    ///
640    /// # Failures
641    ///
642    /// * Returns [`NodeError::AppendSelf`] error if the given new child is
643    ///   `self`.
644    /// * Returns [`NodeError::AppendAncestor`] error if the given new child is
645    ///   an ancestor of `self`.
646    /// * Returns [`NodeError::Removed`] error if the given new child or `self`
647    ///   is [`remove`]d.
648    ///
649    /// To check if the node is removed or not, use [`Node::is_removed()`].
650    ///
651    /// # Examples
652    ///
653    /// ```
654    /// # use indextree::Arena;
655    /// let mut arena = Arena::new();
656    /// let n1 = arena.new_node("1");
657    /// assert!(n1.checked_append(n1, &mut arena).is_err());
658    ///
659    /// let n1_1 = arena.new_node("1_1");
660    /// assert!(n1.checked_append(n1_1, &mut arena).is_ok());
661    /// ```
662    ///
663    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
664    /// [`NodeError::AppendSelf`]: enum.NodeError.html#variant.AppendSelf
665    /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
666    /// [`remove`]: struct.NodeId.html#method.remove
667    pub fn checked_append<T>(
668        self,
669        new_child: NodeId,
670        arena: &mut Arena<T>,
671    ) -> Result<(), NodeError> {
672        if new_child == self {
673            return Err(NodeError::AppendSelf);
674        }
675        if arena[self].is_removed() || arena[new_child].is_removed() {
676            return Err(NodeError::Removed);
677        }
678        if self.ancestors(arena).any(|ancestor| new_child == ancestor) {
679            return Err(NodeError::AppendAncestor);
680        }
681        new_child.detach(arena);
682        insert_with_neighbors(arena, new_child, Some(self), arena[self].last_child, None)
683            .expect("Should never fail: `new_child` is not `self` and they are not removed");
684
685        Ok(())
686    }
687
688    /// Creates and appends a new node (from its associated data) as the last child.
689    /// This method is a fast path for the common case of appending a new node. It is quicker than [`append`].
690    ///
691    /// # Panics
692    ///
693    /// Panics if the arena already has `usize::max_value()` nodes.
694    ///
695    /// # Examples
696    ///
697    /// ```
698    /// # use indextree::Arena;
699    /// let mut arena = Arena::new();
700    /// let n1 = arena.new_node("1");
701    /// let n1_1 = n1.append_value("1_1", &mut arena);
702    /// let n1_1_1 = n1_1.append_value("1_1_1", &mut arena);
703    /// let n1_1_2 = n1_1.append_value("1_1_2", &mut arena);
704    ///
705    /// // arena
706    /// // `-- 1
707    /// //     |-- 1_1
708    /// //  1_1_1 --|-- 1_1_2
709    ///
710    /// let mut iter = n1.descendants(&arena);
711    /// assert_eq!(iter.next(), Some(n1));
712    /// assert_eq!(iter.next(), Some(n1_1));
713    /// assert_eq!(iter.next(), Some(n1_1_1));
714    /// assert_eq!(iter.next(), Some(n1_1_2));
715    /// assert_eq!(iter.next(), None);
716    /// ```
717    /// [`append`]: struct.NodeId.html#method.append
718    pub fn append_value<T>(self, value: T, arena: &mut Arena<T>) -> NodeId {
719        let new_child = arena.new_node(value);
720        self.append_new_node_unchecked(new_child, arena);
721
722        new_child
723    }
724
725    /// Appends a new child to this node, after all existing children (if any).
726    /// This method is a fast path for the common case of appending a new node.
727    /// `new_child` requirements:
728    /// 1. Must be detached. No parents or siblings.
729    /// 2. Has not been [`remove`]d.
730    /// 3. `append_new_node()` was not called on itself
731    ///
732    /// # Examples
733    ///
734    /// ```
735    /// # use indextree::Arena;
736    /// let mut arena = Arena::new();
737    /// let n1 = arena.new_node("1");
738    /// assert!(n1.checked_append(n1, &mut arena).is_err());
739    ///
740    /// let n1_1 = arena.new_node("1_1");
741    /// assert!(n1.checked_append(n1_1, &mut arena).is_ok());
742    /// ```
743    ///
744    /// [`remove`]: struct.NodeId.html#method.remove
745    fn append_new_node_unchecked<T>(self, new_child: NodeId, arena: &mut Arena<T>) {
746        insert_last_unchecked(arena, new_child, self);
747    }
748
749    /// Prepends a new child to this node, before existing children.
750    ///
751    /// # Panics
752    ///
753    /// Panics if:
754    ///
755    /// * the given new child is `self`, or
756    /// * the given new child is an ancestor of `self`, or
757    /// * the current node or the given new child was already [`remove`]d.
758    ///
759    /// To check if the node is removed or not, use [`Node::is_removed()`].
760    ///
761    /// # Examples
762    ///
763    /// ```
764    /// # use indextree::Arena;
765    /// let mut arena = Arena::new();
766    /// let n1 = arena.new_node("1");
767    /// let n1_1 = arena.new_node("1_1");
768    /// n1.prepend(n1_1, &mut arena);
769    /// let n1_2 = arena.new_node("1_2");
770    /// n1.prepend(n1_2, &mut arena);
771    /// let n1_3 = arena.new_node("1_3");
772    /// n1.prepend(n1_3, &mut arena);
773    ///
774    /// // arena
775    /// // `-- 1
776    /// //     |-- 1_3
777    /// //     |-- 1_2
778    /// //     `-- 1_1
779    ///
780    /// let mut iter = n1.descendants(&arena);
781    /// assert_eq!(iter.next(), Some(n1));
782    /// assert_eq!(iter.next(), Some(n1_3));
783    /// assert_eq!(iter.next(), Some(n1_2));
784    /// assert_eq!(iter.next(), Some(n1_1));
785    /// assert_eq!(iter.next(), None);
786    /// ```
787    ///
788    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
789    /// [`remove`]: struct.NodeId.html#method.remove
790    pub fn prepend<T>(self, new_child: NodeId, arena: &mut Arena<T>) {
791        self.checked_prepend(new_child, arena)
792            .expect("Preconditions not met: invalid argument");
793    }
794
795    /// Prepends a new child to this node, before existing children.
796    ///
797    /// # Failures
798    ///
799    /// * Returns [`NodeError::PrependSelf`] error if the given new child is
800    ///   `self`.
801    /// * Returns [`NodeError::PrependAncestor`] error if the given new child is
802    ///   an ancestor of `self`.
803    /// * Returns [`NodeError::Removed`] error if the given new child or `self`
804    ///   is [`remove`]d.
805    ///
806    /// To check if the node is removed or not, use [`Node::is_removed()`].
807    ///
808    /// # Examples
809    ///
810    /// ```
811    /// # use indextree::Arena;
812    /// let mut arena = Arena::new();
813    /// let n1 = arena.new_node("1");
814    /// assert!(n1.checked_prepend(n1, &mut arena).is_err());
815    ///
816    /// let n1_1 = arena.new_node("1_1");
817    /// assert!(n1.checked_prepend(n1_1, &mut arena).is_ok());
818    /// ```
819    ///
820    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
821    /// [`NodeError::PrependSelf`]: enum.NodeError.html#variant.PrependSelf
822    /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
823    /// [`remove`]: struct.NodeId.html#method.remove
824    pub fn checked_prepend<T>(
825        self,
826        new_child: NodeId,
827        arena: &mut Arena<T>,
828    ) -> Result<(), NodeError> {
829        if new_child == self {
830            return Err(NodeError::PrependSelf);
831        }
832        if arena[self].is_removed() || arena[new_child].is_removed() {
833            return Err(NodeError::Removed);
834        }
835        if self.ancestors(arena).any(|ancestor| new_child == ancestor) {
836            return Err(NodeError::PrependAncestor);
837        }
838        insert_with_neighbors(arena, new_child, Some(self), None, arena[self].first_child)
839            .expect("Should never fail: `new_child` is not `self` and they are not removed");
840
841        Ok(())
842    }
843
844    /// Inserts a new sibling after this node.
845    ///
846    /// # Panics
847    ///
848    /// Panics if:
849    ///
850    /// * the given new sibling is `self`, or
851    /// * the current node or the given new sibling was already [`remove`]d.
852    ///
853    /// To check if the node is removed or not, use [`Node::is_removed()`].
854    ///
855    /// # Examples
856    ///
857    /// ```
858    /// # use indextree::Arena;
859    /// # let mut arena = Arena::new();
860    /// # let n1 = arena.new_node("1");
861    /// # let n1_1 = arena.new_node("1_1");
862    /// # n1.append(n1_1, &mut arena);
863    /// # let n1_2 = arena.new_node("1_2");
864    /// # n1.append(n1_2, &mut arena);
865    /// #
866    /// // arena
867    /// // `-- 1
868    /// //     |-- 1_1 *
869    /// //     `-- 1_2
870    ///
871    /// let n1_3 = arena.new_node("1_3");
872    /// n1_1.insert_after(n1_3, &mut arena);
873    ///
874    /// // arena
875    /// // `-- 1
876    /// //     |-- 1_1
877    /// //     |-- 1_3 *
878    /// //     `-- 1_2
879    ///
880    /// let mut iter = n1.descendants(&arena);
881    /// assert_eq!(iter.next(), Some(n1));
882    /// assert_eq!(iter.next(), Some(n1_1));
883    /// assert_eq!(iter.next(), Some(n1_3));
884    /// assert_eq!(iter.next(), Some(n1_2));
885    /// assert_eq!(iter.next(), None);
886    /// ```
887    ///
888    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
889    /// [`remove`]: struct.NodeId.html#method.remove
890    pub fn insert_after<T>(self, new_sibling: NodeId, arena: &mut Arena<T>) {
891        self.checked_insert_after(new_sibling, arena)
892            .expect("Preconditions not met: invalid argument");
893    }
894
895    /// Inserts a new sibling after this node.
896    ///
897    /// # Failures
898    ///
899    /// * Returns [`NodeError::InsertAfterSelf`] error if the given new sibling
900    ///   is `self`.
901    /// * Returns [`NodeError::Removed`] error if the given new sibling or
902    ///   `self` is [`remove`]d.
903    ///
904    /// To check if the node is removed or not, use [`Node::is_removed()`].
905    ///
906    /// # Examples
907    ///
908    /// ```
909    /// # use indextree::Arena;
910    /// let mut arena = Arena::new();
911    /// let n1 = arena.new_node("1");
912    /// assert!(n1.checked_insert_after(n1, &mut arena).is_err());
913    ///
914    /// let n2 = arena.new_node("2");
915    /// assert!(n1.checked_insert_after(n2, &mut arena).is_ok());
916    /// ```
917    ///
918    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
919    /// [`NodeError::InsertAfterSelf`]: enum.NodeError.html#variant.InsertAfterSelf
920    /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
921    /// [`remove`]: struct.NodeId.html#method.remove
922    pub fn checked_insert_after<T>(
923        self,
924        new_sibling: NodeId,
925        arena: &mut Arena<T>,
926    ) -> Result<(), NodeError> {
927        if new_sibling == self {
928            return Err(NodeError::InsertAfterSelf);
929        }
930        if arena[self].is_removed() || arena[new_sibling].is_removed() {
931            return Err(NodeError::Removed);
932        }
933        new_sibling.detach(arena);
934        let (next_sibling, parent) = {
935            let current = &arena[self];
936            (current.next_sibling, current.parent)
937        };
938        insert_with_neighbors(arena, new_sibling, parent, Some(self), next_sibling)
939            .expect("Should never fail: `new_sibling` is not `self` and they are not removed");
940
941        Ok(())
942    }
943
944    /// Inserts a new sibling before this node.
945    ///
946    /// # Panics
947    ///
948    /// Panics if:
949    ///
950    /// * the given new sibling is `self`, or
951    /// * the current node or the given new sibling was already [`remove`]d.
952    ///
953    /// To check if the node is removed or not, use [`Node::is_removed()`].
954    ///
955    /// # Examples
956    ///
957    /// ```
958    /// # use indextree::Arena;
959    /// let mut arena = Arena::new();
960    /// let n1 = arena.new_node("1");
961    /// let n1_1 = arena.new_node("1_1");
962    /// n1.append(n1_1, &mut arena);
963    /// let n1_2 = arena.new_node("1_2");
964    /// n1.append(n1_2, &mut arena);
965    ///
966    /// // arena
967    /// // `-- 1
968    /// //     |-- 1_1
969    /// //     `-- 1_2 *
970    ///
971    /// let n1_3 = arena.new_node("1_3");
972    /// n1_2.insert_before(n1_3, &mut arena);
973    ///
974    /// // arena
975    /// // `-- 1
976    /// //     |-- 1_1
977    /// //     |-- 1_3 *
978    /// //     `-- 1_2
979    ///
980    /// let mut iter = n1.descendants(&arena);
981    /// assert_eq!(iter.next(), Some(n1));
982    /// assert_eq!(iter.next(), Some(n1_1));
983    /// assert_eq!(iter.next(), Some(n1_3));
984    /// assert_eq!(iter.next(), Some(n1_2));
985    /// assert_eq!(iter.next(), None);
986    /// ```
987    ///
988    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
989    /// [`remove`]: struct.NodeId.html#method.remove
990    pub fn insert_before<T>(self, new_sibling: NodeId, arena: &mut Arena<T>) {
991        self.checked_insert_before(new_sibling, arena)
992            .expect("Preconditions not met: invalid argument");
993    }
994
995    /// Inserts a new sibling before this node.
996    ///
997    /// # Failures
998    ///
999    /// * Returns [`NodeError::InsertBeforeSelf`] error if the given new sibling
1000    ///   is `self`.
1001    /// * Returns [`NodeError::Removed`] error if the given new sibling or
1002    ///   `self` is [`remove`]d.
1003    ///
1004    /// To check if the node is removed or not, use [`Node::is_removed()`].
1005    ///
1006    /// # Examples
1007    ///
1008    /// ```
1009    /// # use indextree::Arena;
1010    /// let mut arena = Arena::new();
1011    /// let n1 = arena.new_node("1");
1012    /// assert!(n1.checked_insert_before(n1, &mut arena).is_err());
1013    ///
1014    /// let n2 = arena.new_node("2");
1015    /// assert!(n1.checked_insert_before(n2, &mut arena).is_ok());
1016    /// ```
1017    ///
1018    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
1019    /// [`NodeError::InsertBeforeSelf`]: enum.NodeError.html#variant.InsertBeforeSelf
1020    /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
1021    /// [`remove`]: struct.NodeId.html#method.remove
1022    pub fn checked_insert_before<T>(
1023        self,
1024        new_sibling: NodeId,
1025        arena: &mut Arena<T>,
1026    ) -> Result<(), NodeError> {
1027        if new_sibling == self {
1028            return Err(NodeError::InsertBeforeSelf);
1029        }
1030        if arena[self].is_removed() || arena[new_sibling].is_removed() {
1031            return Err(NodeError::Removed);
1032        }
1033        new_sibling.detach(arena);
1034        let (previous_sibling, parent) = {
1035            let current = &arena[self];
1036            (current.previous_sibling, current.parent)
1037        };
1038        insert_with_neighbors(arena, new_sibling, parent, previous_sibling, Some(self))
1039            .expect("Should never fail: `new_sibling` is not `self` and they are not removed");
1040
1041        Ok(())
1042    }
1043
1044    /// Removes a node from the arena.
1045    ///
1046    /// Children of the removed node will be inserted to the place where the
1047    /// removed node was.
1048    ///
1049    /// Please note that the node will not be removed from the internal arena
1050    /// storage, but marked as `removed`. Traversing the arena returns a
1051    /// plain iterator and contains removed elements too.
1052    ///
1053    /// To check if the node is removed or not, use [`Node::is_removed()`].
1054    ///
1055    /// # Examples
1056    ///
1057    /// ```
1058    /// # use indextree::Arena;
1059    /// # let mut arena = Arena::new();
1060    /// # let n1 = arena.new_node("1");
1061    /// # let n1_1 = arena.new_node("1_1");
1062    /// # n1.append(n1_1, &mut arena);
1063    /// # let n1_2 = arena.new_node("1_2");
1064    /// # n1.append(n1_2, &mut arena);
1065    /// # let n1_2_1 = arena.new_node("1_2_1");
1066    /// # n1_2.append(n1_2_1, &mut arena);
1067    /// # let n1_2_2 = arena.new_node("1_2_2");
1068    /// # n1_2.append(n1_2_2, &mut arena);
1069    /// # let n1_3 = arena.new_node("1_3");
1070    /// # n1.append(n1_3, &mut arena);
1071    /// #
1072    /// // arena
1073    /// // `-- 1
1074    /// //     |-- 1_1
1075    /// //     |-- 1_2 *
1076    /// //     |   |-- 1_2_1
1077    /// //     |   `-- 1_2_2
1078    /// //     `-- 1_3
1079    ///
1080    /// n1_2.remove(&mut arena);
1081    ///
1082    /// // arena
1083    /// // `-- 1
1084    /// //     |-- 1_1
1085    /// //     |-- 1_2_1
1086    /// //     |-- 1_2_2
1087    /// //     `-- 1_3
1088    ///
1089    /// let mut iter = n1.descendants(&arena);
1090    /// assert_eq!(iter.next(), Some(n1));
1091    /// assert_eq!(iter.next(), Some(n1_1));
1092    /// assert_eq!(iter.next(), Some(n1_2_1));
1093    /// assert_eq!(iter.next(), Some(n1_2_2));
1094    /// assert_eq!(iter.next(), Some(n1_3));
1095    /// assert_eq!(iter.next(), None);
1096    /// ```
1097    ///
1098    /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
1099    pub fn remove<T>(self, arena: &mut Arena<T>) {
1100        debug_assert_triangle_nodes!(
1101            arena,
1102            arena[self].parent,
1103            arena[self].previous_sibling,
1104            Some(self)
1105        );
1106        debug_assert_triangle_nodes!(
1107            arena,
1108            arena[self].parent,
1109            Some(self),
1110            arena[self].next_sibling
1111        );
1112        debug_assert_triangle_nodes!(arena, Some(self), None, arena[self].first_child);
1113        debug_assert_triangle_nodes!(arena, Some(self), arena[self].last_child, None);
1114
1115        // Retrieve needed values.
1116        let (parent, previous_sibling, next_sibling, first_child, last_child) = {
1117            let node = &arena[self];
1118            (
1119                node.parent,
1120                node.previous_sibling,
1121                node.next_sibling,
1122                node.first_child,
1123                node.last_child,
1124            )
1125        };
1126
1127        assert_eq!(first_child.is_some(), last_child.is_some());
1128        self.detach(arena);
1129        if let (Some(first_child), Some(last_child)) = (first_child, last_child) {
1130            let range = SiblingsRange::new(first_child, last_child).detach_from_siblings(arena);
1131            range
1132                .transplant(arena, parent, previous_sibling, next_sibling)
1133                .expect("Should never fail: neighbors and children must be consistent");
1134        }
1135        arena.free_node(self);
1136        debug_assert!(arena[self].is_detached());
1137    }
1138
1139    /// Removes a node and its descendants from the arena.
1140    /// # Examples
1141    ///
1142    /// ```
1143    /// # use indextree::Arena;
1144    /// # let mut arena = Arena::new();
1145    /// # let n1 = arena.new_node("1");
1146    /// # let n1_1 = arena.new_node("1_1");
1147    /// # n1.append(n1_1, &mut arena);
1148    /// # let n1_2 = arena.new_node("1_2");
1149    /// # n1.append(n1_2, &mut arena);
1150    /// # let n1_2_1 = arena.new_node("1_2_1");
1151    /// # n1_2.append(n1_2_1, &mut arena);
1152    /// # let n1_2_2 = arena.new_node("1_2_2");
1153    /// # n1_2.append(n1_2_2, &mut arena);
1154    /// # let n1_3 = arena.new_node("1_3");
1155    /// # n1.append(n1_3, &mut arena);
1156    /// #
1157    /// // arena
1158    /// // `-- 1
1159    /// //     |-- 1_1
1160    /// //     |-- 1_2 *
1161    /// //     |   |-- 1_2_1
1162    /// //     |   `-- 1_2_2
1163    /// //     `-- 1_3
1164    ///
1165    /// n1_2.remove_subtree(&mut arena);
1166    ///
1167    /// // arena
1168    /// // `-- 1
1169    /// //     |-- 1_1
1170    /// //     `-- 1_3
1171    ///
1172    /// let mut iter = n1.descendants(&arena);
1173    /// assert_eq!(iter.next(), Some(n1));
1174    /// assert_eq!(iter.next(), Some(n1_1));
1175    /// assert_eq!(iter.next(), Some(n1_3));
1176    /// assert_eq!(iter.next(), None);
1177    /// ```
1178    ///
1179    pub fn remove_subtree<T>(self, arena: &mut Arena<T>) {
1180        self.detach(arena);
1181
1182        // use a preorder traversal to remove node.
1183        let mut cursor = Some(self);
1184        while let Some(id) = cursor {
1185            arena.free_node(id);
1186            let node = &arena[id];
1187            cursor = node.first_child.or(node.next_sibling).or_else(|| {
1188                id.ancestors(arena) // traverse ancestors upwards
1189                    .skip(1) // skip the starting node itself
1190                    .find(|n| arena[*n].next_sibling.is_some()) // first ancestor with a sibling
1191                    .and_then(|n| arena[n].next_sibling) // the sibling is the new cursor
1192            });
1193        }
1194    }
1195
1196    /// Returns the pretty-printable proxy object to the node and descendants.
1197    ///
1198    /// # (No) guarantees
1199    ///
1200    /// This is provided mainly for debugging purpose. Node that the output
1201    /// format is not guaranteed to be stable, and any format changes won't be
1202    /// considered as breaking changes.
1203    ///
1204    /// # Examples
1205    ///
1206    /// ```
1207    /// # use indextree::Arena;
1208    /// #
1209    /// # let mut arena = Arena::new();
1210    /// # let root = arena.new_node("root");
1211    /// # let n0 = arena.new_node("0");
1212    /// # root.append(n0, &mut arena);
1213    /// # let n0_0 = arena.new_node("0\n0");
1214    /// # n0.append(n0_0, &mut arena);
1215    /// # let n0_1 = arena.new_node("0\n1");
1216    /// # n0.append(n0_1, &mut arena);
1217    /// # let n1 = arena.new_node("1");
1218    /// # root.append(n1, &mut arena);
1219    /// # let n2 = arena.new_node("2");
1220    /// # root.append(n2, &mut arena);
1221    /// # let n2_0 = arena.new_node("2\n0");
1222    /// # n2.append(n2_0, &mut arena);
1223    /// # let n2_0_0 = arena.new_node("2\n0\n0");
1224    /// # n2_0.append(n2_0_0, &mut arena);
1225    ///
1226    /// //  arena
1227    /// //  `-- "root"
1228    /// //      |-- "0"
1229    /// //      |   |-- "0\n0"
1230    /// //      |   `-- "0\n1"
1231    /// //      |-- "1"
1232    /// //      `-- "2"
1233    /// //          `-- "2\n0"
1234    /// //              `-- "2\n0\n0"
1235    ///
1236    /// let printable = root.debug_pretty_print(&arena);
1237    ///
1238    /// let expected_debug = r#""root"
1239    /// |-- "0"
1240    /// |   |-- "0\n0"
1241    /// |   `-- "0\n1"
1242    /// |-- "1"
1243    /// `-- "2"
1244    ///     `-- "2\n0"
1245    ///         `-- "2\n0\n0""#;
1246    /// assert_eq!(format!("{:?}", printable), expected_debug);
1247    ///
1248    /// let expected_display = r#"root
1249    /// |-- 0
1250    /// |   |-- 0
1251    /// |   |   0
1252    /// |   `-- 0
1253    /// |       1
1254    /// |-- 1
1255    /// `-- 2
1256    ///     `-- 2
1257    ///         0
1258    ///         `-- 2
1259    ///             0
1260    ///             0"#;
1261    /// assert_eq!(printable.to_string(), expected_display);
1262    /// ```
1263    ///
1264    /// Alternate styles (`{:#?}` and `{:#}`) are also supported.
1265    ///
1266    /// ```
1267    /// # use indextree::Arena;
1268    /// #
1269    /// # let mut arena = Arena::new();
1270    /// # let root = arena.new_node(Ok(42));
1271    /// # let child = arena.new_node(Err("err"));
1272    /// # root.append(child, &mut arena);
1273    ///
1274    /// //  arena
1275    /// //  `-- Ok(42)
1276    /// //      `-- Err("err")
1277    ///
1278    /// let printable = root.debug_pretty_print(&arena);
1279    ///
1280    /// let expected_debug = r#"Ok(42)
1281    /// `-- Err("err")"#;
1282    /// assert_eq!(format!("{:?}", printable), expected_debug);
1283    ///
1284    /// let expected_debug_alternate = r#"Ok(
1285    ///     42,
1286    /// )
1287    /// `-- Err(
1288    ///         "err",
1289    ///     )"#;
1290    /// assert_eq!(format!("{:#?}", printable), expected_debug_alternate);
1291    /// ```
1292    #[inline]
1293    #[must_use]
1294    pub fn debug_pretty_print<'a, T>(&'a self, arena: &'a Arena<T>) -> DebugPrettyPrint<'a, T> {
1295        DebugPrettyPrint::new(self, arena)
1296    }
1297}
1298
1299#[cfg(test)]
1300mod tests {
1301    use super::*;
1302
1303    #[test]
1304    fn test_remove_subtree_complex() {
1305        // arena
1306        // `-- 1
1307        //     |-- 1_1
1308        //     |-- 1_2
1309        //     |   |-- 1_2_1
1310        //     |   |   `-- 1_2_1_1
1311        //     |   |       `-- 1_2_1_1_1
1312        //     |   `-- 1_2_2
1313        //     `-- 1_3
1314        let mut arena = Arena::new();
1315        let n1 = arena.new_node("1");
1316        let n1_1 = arena.new_node("1_1");
1317        n1.append(n1_1, &mut arena);
1318        let n1_2 = arena.new_node("1_2");
1319        n1.append(n1_2, &mut arena);
1320        let n1_2_1 = arena.new_node("1_2_1");
1321        n1_2.append(n1_2_1, &mut arena);
1322        let n1_2_1_1 = arena.new_node("1_2_1_1");
1323        n1_2_1.append(n1_2_1_1, &mut arena);
1324        let n1_2_1_1_1 = arena.new_node("1_2_1_1_1");
1325        n1_2_1_1.append(n1_2_1_1_1, &mut arena);
1326        let n1_2_2 = arena.new_node("1_2_2");
1327        n1_2.append(n1_2_2, &mut arena);
1328        let n1_3 = arena.new_node("1_3");
1329        n1.append(n1_3, &mut arena);
1330
1331        n1_2.remove_subtree(&mut arena);
1332
1333        assert!(!n1.is_removed(&arena));
1334        assert!(!n1_1.is_removed(&arena));
1335        assert!(!n1_3.is_removed(&arena));
1336
1337        assert!(n1_2.is_removed(&arena));
1338        assert!(n1_2_1.is_removed(&arena));
1339        assert!(n1_2_1_1.is_removed(&arena));
1340        assert!(n1_2_1_1_1.is_removed(&arena));
1341        assert!(n1_2_2.is_removed(&arena));
1342    }
1343
1344    #[test]
1345    fn test_conversions() {
1346        let mut arena = Arena::new();
1347        let n1 = arena.new_node("1");
1348        assert_eq!(usize::from(n1), 1);
1349        assert_eq!(NonZeroUsize::from(n1), NonZeroUsize::new(1).unwrap());
1350        assert_eq!(n1.to_string(), "1");
1351    }
1352}