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}