generational_indextree/id.rs
1//! Node ID.
2
3#[cfg(not(feature = "std"))]
4use core::fmt;
5#[cfg(feature = "std")]
6use std::fmt;
7
8use generational_arena::Index;
9#[cfg(feature = "deser")]
10use serde::{Deserialize, Serialize};
11
12use crate::{
13 relations::insert_with_neighbors, siblings_range::SiblingsRange, Ancestors, Arena, Children,
14 Descendants, FollowingSiblings, NodeError, PrecedingSiblings, ReverseChildren, ReverseTraverse,
15 Traverse,
16};
17
18#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Debug, Hash)]
19#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
20/// A node identifier within a particular [`Arena`].
21///
22/// This ID is used to get [`Node`] references from an [`Arena`].
23///
24/// [`Arena`]: struct.Arena.html
25/// [`Node`]: struct.Node.html
26pub struct NodeId {
27 index: Index,
28}
29
30impl fmt::Display for NodeId {
31 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32 write!(f, "{:?}", self.index)
33 }
34}
35
36impl From<NodeId> for Index {
37 fn from(node_id: NodeId) -> Index {
38 node_id.index
39 }
40}
41
42impl NodeId {
43 /// Returns index.
44 pub(crate) fn get_index(self) -> Index {
45 self.index
46 }
47
48 /// Creates a new `NodeId` from the given index.
49 pub(crate) fn from_index(index: Index) -> Self {
50 NodeId { index }
51 }
52
53 /// Returns an iterator of IDs of this node and its ancestors.
54 ///
55 /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
56 /// the node itself.
57 ///
58 /// # Examples
59 ///
60 /// ```
61 /// # use generational_indextree::Arena;
62 /// # let mut arena = Arena::new();
63 /// # let n1 = arena.new_node("1");
64 /// # let n1_1 = arena.new_node("1_1");
65 /// # n1.append(n1_1, &mut arena);
66 /// # let n1_1_1 = arena.new_node("1_1_1");
67 /// # n1_1.append(n1_1_1, &mut arena);
68 /// # let n1_1_1_1 = arena.new_node("1_1_1_1");
69 /// # n1_1_1.append(n1_1_1_1, &mut arena);
70 /// # let n1_2 = arena.new_node("1_2");
71 /// # n1.append(n1_2, &mut arena);
72 /// # let n1_3 = arena.new_node("1_3");
73 /// # n1.append(n1_3, &mut arena);
74 /// #
75 /// // arena
76 /// // `-- 1
77 /// // |-- 1_1
78 /// // | `-- 1_1_1
79 /// // | `-- 1_1_1_1
80 /// // _-- 1_2
81 /// // `-- 1_3
82 ///
83 /// let mut iter = n1_1_1.ancestors(&arena);
84 /// assert_eq!(iter.next(), Some(n1_1_1));
85 /// assert_eq!(iter.next(), Some(n1_1));
86 /// assert_eq!(iter.next(), Some(n1));
87 /// assert_eq!(iter.next(), None);
88 /// ```
89 ///
90 /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
91 pub fn ancestors<T>(self, arena: &Arena<T>) -> Ancestors<'_, T> {
92 Ancestors::new(arena, self)
93 }
94
95 /// Returns an iterator of IDs of this node and the siblings before
96 /// it.
97 ///
98 /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
99 /// the node itself.
100 ///
101 /// # Examples
102 ///
103 /// ```
104 /// # use generational_indextree::Arena;
105 /// # let mut arena = Arena::new();
106 /// # let n1 = arena.new_node("1");
107 /// # let n1_1 = arena.new_node("1_1");
108 /// # n1.append(n1_1, &mut arena);
109 /// # let n1_1_1 = arena.new_node("1_1_1");
110 /// # n1_1.append(n1_1_1, &mut arena);
111 /// # let n1_2 = arena.new_node("1_2");
112 /// # n1.append(n1_2, &mut arena);
113 /// # let n1_3 = arena.new_node("1_3");
114 /// # n1.append(n1_3, &mut arena);
115 /// #
116 /// // arena
117 /// // `-- 1
118 /// // |-- 1_1
119 /// // | `-- 1_1_1
120 /// // |-- 1_2
121 /// // `-- 1_3
122 ///
123 /// let mut iter = n1_2.preceding_siblings(&arena);
124 /// assert_eq!(iter.next(), Some(n1_2));
125 /// assert_eq!(iter.next(), Some(n1_1));
126 /// assert_eq!(iter.next(), None);
127 /// ```
128 ///
129 /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
130 pub fn preceding_siblings<T>(self, arena: &Arena<T>) -> PrecedingSiblings<'_, T> {
131 PrecedingSiblings::new(arena, self)
132 }
133
134 /// Returns an iterator of IDs of this node and the siblings after
135 /// it.
136 ///
137 /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
138 /// the node itself.
139 ///
140 /// # Examples
141 ///
142 /// ```
143 /// # use generational_indextree::Arena;
144 /// # let mut arena = Arena::new();
145 /// # let n1 = arena.new_node("1");
146 /// # let n1_1 = arena.new_node("1_1");
147 /// # n1.append(n1_1, &mut arena);
148 /// # let n1_1_1 = arena.new_node("1_1_1");
149 /// # n1_1.append(n1_1_1, &mut arena);
150 /// # let n1_2 = arena.new_node("1_2");
151 /// # n1.append(n1_2, &mut arena);
152 /// # let n1_3 = arena.new_node("1_3");
153 /// # n1.append(n1_3, &mut arena);
154 /// #
155 /// // arena
156 /// // `-- 1
157 /// // |-- 1_1
158 /// // | `-- 1_1_1
159 /// // |-- 1_2
160 /// // `-- 1_3
161 ///
162 /// let mut iter = n1_2.following_siblings(&arena);
163 /// assert_eq!(iter.next(), Some(n1_2));
164 /// assert_eq!(iter.next(), Some(n1_3));
165 /// assert_eq!(iter.next(), None);
166 /// ```
167 ///
168 /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
169 pub fn following_siblings<T>(self, arena: &Arena<T>) -> FollowingSiblings<'_, T> {
170 FollowingSiblings::new(arena, self)
171 }
172
173 /// Returns an iterator of IDs of this node’s children.
174 ///
175 /// # Examples
176 ///
177 /// ```
178 /// # use generational_indextree::Arena;
179 /// # let mut arena = Arena::new();
180 /// # let n1 = arena.new_node("1");
181 /// # let n1_1 = arena.new_node("1_1");
182 /// # n1.append(n1_1, &mut arena);
183 /// # let n1_1_1 = arena.new_node("1_1_1");
184 /// # n1_1.append(n1_1_1, &mut arena);
185 /// # let n1_2 = arena.new_node("1_2");
186 /// # n1.append(n1_2, &mut arena);
187 /// # let n1_3 = arena.new_node("1_3");
188 /// # n1.append(n1_3, &mut arena);
189 /// #
190 /// // arena
191 /// // `-- 1
192 /// // |-- 1_1
193 /// // | `-- 1_1_1
194 /// // |-- 1_2
195 /// // `-- 1_3
196 ///
197 /// let mut iter = n1.children(&arena);
198 /// assert_eq!(iter.next(), Some(n1_1));
199 /// assert_eq!(iter.next(), Some(n1_2));
200 /// assert_eq!(iter.next(), Some(n1_3));
201 /// assert_eq!(iter.next(), None);
202 /// ```
203 pub fn children<T>(self, arena: &Arena<T>) -> Children<'_, T> {
204 Children::new(arena, self)
205 }
206
207 /// Returns an iterator of IDs of this node’s children, in reverse
208 /// order.
209 ///
210 /// # Examples
211 ///
212 /// ```
213 /// # use generational_indextree::Arena;
214 /// # let mut arena = Arena::new();
215 /// # let n1 = arena.new_node("1");
216 /// # let n1_1 = arena.new_node("1_1");
217 /// # n1.append(n1_1, &mut arena);
218 /// # let n1_1_1 = arena.new_node("1_1_1");
219 /// # n1_1.append(n1_1_1, &mut arena);
220 /// # let n1_2 = arena.new_node("1_2");
221 /// # n1.append(n1_2, &mut arena);
222 /// # let n1_3 = arena.new_node("1_3");
223 /// # n1.append(n1_3, &mut arena);
224 /// #
225 /// // arena
226 /// // `-- 1
227 /// // |-- 1_1
228 /// // | `-- 1_1_1
229 /// // |-- 1_2
230 /// // `-- 1_3
231 ///
232 /// let mut iter = n1.reverse_children(&arena);
233 /// assert_eq!(iter.next(), Some(n1_3));
234 /// assert_eq!(iter.next(), Some(n1_2));
235 /// assert_eq!(iter.next(), Some(n1_1));
236 /// assert_eq!(iter.next(), None);
237 /// ```
238 pub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<'_, T> {
239 ReverseChildren::new(arena, self)
240 }
241
242 /// 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.
243 ///
244 /// i.e. node -> first child -> second child
245 ///
246 /// Parent nodes appear before the descendants.
247 /// Use [`.skip(1)`][`skip`] or call `.next()` once on the iterator to skip
248 /// the node itself.
249 ///
250 /// # Examples
251 ///
252 /// ```
253 /// # use generational_indextree::Arena;
254 /// # let mut arena = Arena::new();
255 /// # let n1 = arena.new_node("1");
256 /// # let n1_1 = arena.new_node("1_1");
257 /// # n1.append(n1_1, &mut arena);
258 /// # let n1_1_1 = arena.new_node("1_1_1");
259 /// # n1_1.append(n1_1_1, &mut arena);
260 /// # let n1_1_1_1 = arena.new_node("1_1_1_1");
261 /// # n1_1_1.append(n1_1_1_1, &mut arena);
262 /// # let n1_2 = arena.new_node("1_2");
263 /// # n1.append(n1_2, &mut arena);
264 /// # let n1_3 = arena.new_node("1_3");
265 /// # n1.append(n1_3, &mut arena);
266 /// #
267 /// // arena
268 /// // `-- 1
269 /// // |-- 1_1
270 /// // | `-- 1_1_1
271 /// // | `-- 1_1_1_1
272 /// // |-- 1_2
273 /// // `-- 1_3
274 ///
275 /// let mut iter = n1.descendants(&arena);
276 /// assert_eq!(iter.next(), Some(n1));
277 /// assert_eq!(iter.next(), Some(n1_1));
278 /// assert_eq!(iter.next(), Some(n1_1_1));
279 /// assert_eq!(iter.next(), Some(n1_1_1_1));
280 /// assert_eq!(iter.next(), Some(n1_2));
281 /// assert_eq!(iter.next(), Some(n1_3));
282 /// assert_eq!(iter.next(), None);
283 /// ```
284 ///
285 /// [`skip`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.skip
286 pub fn descendants<T>(self, arena: &Arena<T>) -> Descendants<'_, T> {
287 Descendants::new(arena, self)
288 }
289
290 /// An iterator of the "sides" of a node visited during a depth-first pre-order traversal,
291 /// where node sides are visited start to end and children are visited in insertion order.
292 ///
293 /// i.e. node.start -> first child -> second child -> node.end
294 ///
295 /// # Examples
296 ///
297 /// ```
298 /// # use generational_indextree::{Arena, NodeEdge};
299 /// # let mut arena = Arena::new();
300 /// # let n1 = arena.new_node("1");
301 /// # let n1_1 = arena.new_node("1_1");
302 /// # n1.append(n1_1, &mut arena);
303 /// # let n1_1_1 = arena.new_node("1_1_1");
304 /// # n1_1.append(n1_1_1, &mut arena);
305 /// # let n1_2 = arena.new_node("1_2");
306 /// # n1.append(n1_2, &mut arena);
307 /// # let n1_3 = arena.new_node("1_3");
308 /// # n1.append(n1_3, &mut arena);
309 /// #
310 /// // arena
311 /// // `-- 1
312 /// // |-- 1_1
313 /// // | `-- 1_1_1
314 /// // |-- 1_2
315 /// // `-- 1_3
316 ///
317 /// let mut iter = n1.traverse(&arena);
318 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));
319 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));
320 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1)));
321 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));
322 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));
323 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));
324 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));
325 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));
326 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));
327 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1)));
328 /// assert_eq!(iter.next(), None);
329 /// ```
330 pub fn traverse<T>(self, arena: &Arena<T>) -> Traverse<'_, T> {
331 Traverse::new(arena, self)
332 }
333
334 /// An iterator of the "sides" of a node visited during a depth-first pre-order traversal,
335 /// where nodes are visited end to start and children are visited in reverse insertion order.
336 ///
337 /// i.e. node.end -> second child -> first child -> node.start
338 ///
339 /// # Examples
340 ///
341 /// ```
342 /// # use generational_indextree::{Arena, NodeEdge};
343 /// # let mut arena = Arena::new();
344 /// # let n1 = arena.new_node("1");
345 /// # let n1_1 = arena.new_node("1_1");
346 /// # n1.append(n1_1, &mut arena);
347 /// # let n1_1_1 = arena.new_node("1_1_1");
348 /// # n1_1.append(n1_1_1, &mut arena);
349 /// # let n1_2 = arena.new_node("1_2");
350 /// # n1.append(n1_2, &mut arena);
351 /// # let n1_3 = arena.new_node("1_3");
352 /// # n1.append(n1_3, &mut arena);
353 /// #
354 /// // arena
355 /// // `-- 1
356 /// // |-- 1_1
357 /// // | `-- 1_1_1
358 /// // |-- 1_2
359 /// // `-- 1_3
360 ///
361 /// let mut iter = n1.reverse_traverse(&arena);
362 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1)));
363 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));
364 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));
365 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));
366 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));
367 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));
368 /// assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));
369 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1)));
370 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));
371 /// assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));
372 /// assert_eq!(iter.next(), None);
373 /// ```
374 ///
375 /// ```
376 /// # use generational_indextree::{Arena, NodeEdge};
377 /// # let mut arena = Arena::new();
378 /// # let n1 = arena.new_node("1");
379 /// # let n1_1 = arena.new_node("1_1");
380 /// # n1.append(n1_1, &mut arena);
381 /// # let n1_1_1 = arena.new_node("1_1_1");
382 /// # n1_1.append(n1_1_1, &mut arena);
383 /// # let n1_2 = arena.new_node("1_2");
384 /// # n1.append(n1_2, &mut arena);
385 /// # let n1_3 = arena.new_node("1_3");
386 /// # n1.append(n1_3, &mut arena);
387 /// #
388 /// # // arena
389 /// # // `-- 1
390 /// # // |-- 1_1
391 /// # // | `-- 1_1_1
392 /// # // |-- 1_2
393 /// # // `-- 1_3
394 /// #
395 /// let traverse = n1.traverse(&arena).collect::<Vec<_>>();
396 /// let mut reverse = n1.reverse_traverse(&arena).collect::<Vec<_>>();
397 /// reverse.reverse();
398 /// assert_eq!(traverse, reverse);
399 /// ```
400 pub fn reverse_traverse<T>(self, arena: &Arena<T>) -> ReverseTraverse<'_, T> {
401 ReverseTraverse::new(arena, self)
402 }
403
404 /// Detaches a node from its parent and siblings. Children are not affected.
405 ///
406 /// # Examples
407 ///
408 /// ```
409 /// # use generational_indextree::{Arena, NodeEdge};
410 /// # let mut arena = Arena::new();
411 /// # let n1 = arena.new_node("1");
412 /// # let n1_1 = arena.new_node("1_1");
413 /// # n1.append(n1_1, &mut arena);
414 /// # let n1_1_1 = arena.new_node("1_1_1");
415 /// # n1_1.append(n1_1_1, &mut arena);
416 /// # let n1_2 = arena.new_node("1_2");
417 /// # n1.append(n1_2, &mut arena);
418 /// # let n1_3 = arena.new_node("1_3");
419 /// # n1.append(n1_3, &mut arena);
420 /// #
421 /// // arena
422 /// // `-- (implicit)
423 /// // `-- 1
424 /// // |-- 1_1
425 /// // | `-- 1_1_1
426 /// // |-- 1_2 *
427 /// // `-- 1_3
428 ///
429 /// n1_2.detach(&mut arena);
430 /// // arena
431 /// // |-- (implicit)
432 /// // | `-- 1
433 /// // | |-- 1_1
434 /// // | | `-- 1_1_1
435 /// // | `-- 1_3
436 /// // `-- (implicit)
437 /// // `-- 1_2
438 ///
439 /// assert!(arena[n1_2].parent().is_none());
440 /// assert!(arena[n1_2].previous_sibling().is_none());
441 /// assert!(arena[n1_2].next_sibling().is_none());
442 ///
443 /// let mut iter = n1.descendants(&arena);
444 /// assert_eq!(iter.next(), Some(n1));
445 /// assert_eq!(iter.next(), Some(n1_1));
446 /// assert_eq!(iter.next(), Some(n1_1_1));
447 /// assert_eq!(iter.next(), Some(n1_3));
448 /// assert_eq!(iter.next(), None);
449 /// ```
450 pub fn detach<T>(self, arena: &mut Arena<T>) {
451 let range = SiblingsRange::new(self, self).detach_from_siblings(arena);
452 range
453 .rewrite_parents(arena, None)
454 .expect("Should never happen: `None` as parent is always valid");
455
456 // Ensure the node is surely detached.
457 debug_assert!(
458 arena[self].is_detached(),
459 "The node should be successfully detached"
460 );
461 }
462
463 /// Appends a new child to this node, after existing children.
464 ///
465 /// # Panics
466 ///
467 /// Panics if:
468 ///
469 /// * the given new child is `self`
470 ///
471 /// # Examples
472 ///
473 /// ```
474 /// # use generational_indextree::Arena;
475 /// let mut arena = Arena::new();
476 /// let n1 = arena.new_node("1");
477 /// let n1_1 = arena.new_node("1_1");
478 /// n1.append(n1_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
486 /// // |-- 1_1
487 /// // |-- 1_2
488 /// // `-- 1_3
489 ///
490 /// let mut iter = n1.descendants(&arena);
491 /// assert_eq!(iter.next(), Some(n1));
492 /// assert_eq!(iter.next(), Some(n1_1));
493 /// assert_eq!(iter.next(), Some(n1_2));
494 /// assert_eq!(iter.next(), Some(n1_3));
495 /// assert_eq!(iter.next(), None);
496 /// ```
497 ///
498 /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
499 /// [`remove`]: struct.NodeId.html#method.remove
500 pub fn append<T>(self, new_child: NodeId, arena: &mut Arena<T>) {
501 self.checked_append(new_child, arena)
502 .expect("Preconditions not met: invalid argument");
503 }
504
505 /// Appends a new child to this node, after existing children.
506 ///
507 /// # Failures
508 ///
509 /// * Returns [`NodeError::AppendSelf`] error if the given new child is
510 /// `self`.
511 /// * Returns [`NodeError::Removed`] error if the given new child or `self`
512 /// is [`remove`]d.
513 ///
514 /// # Examples
515 ///
516 /// ```
517 /// # use generational_indextree::Arena;
518 /// let mut arena = Arena::new();
519 /// let n1 = arena.new_node("1");
520 /// assert!(n1.checked_append(n1, &mut arena).is_err());
521 ///
522 /// let n1_1 = arena.new_node("1_1");
523 /// assert!(n1.checked_append(n1_1, &mut arena).is_ok());
524 /// ```
525 ///
526 /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
527 /// [`NodeError::AppendSelf`]: enum.NodeError.html#variant.AppendSelf
528 /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
529 /// [`remove`]: struct.NodeId.html#method.remove
530 pub fn checked_append<T>(
531 self,
532 new_child: NodeId,
533 arena: &mut Arena<T>,
534 ) -> Result<(), NodeError> {
535 if new_child == self {
536 return Err(NodeError::AppendSelf);
537 }
538 if !arena.nodes.contains(self.index) || !arena.nodes.contains(new_child.index) {
539 // if arena[self].is_removed() || arena[new_child].is_removed() {
540 return Err(NodeError::Removed);
541 }
542 new_child.detach(arena);
543 insert_with_neighbors(arena, new_child, Some(self), arena[self].last_child, None)
544 .expect("Should never fail: `new_child` is not `self` and they are not removed");
545
546 Ok(())
547 }
548
549 /// Prepends a new child to this node, before existing children.
550 ///
551 /// # Panics
552 ///
553 /// Panics if:
554 ///
555 /// * the given new child is `self`, or
556 /// * the current node or the given new child was already [`remove`]d.
557 ///
558 /// # Examples
559 ///
560 /// ```
561 /// # use generational_indextree::Arena;
562 /// let mut arena = Arena::new();
563 /// let n1 = arena.new_node("1");
564 /// let n1_1 = arena.new_node("1_1");
565 /// n1.prepend(n1_1, &mut arena);
566 /// let n1_2 = arena.new_node("1_2");
567 /// n1.prepend(n1_2, &mut arena);
568 /// let n1_3 = arena.new_node("1_3");
569 /// n1.prepend(n1_3, &mut arena);
570 ///
571 /// // arena
572 /// // `-- 1
573 /// // |-- 1_3
574 /// // |-- 1_2
575 /// // `-- 1_1
576 ///
577 /// let mut iter = n1.descendants(&arena);
578 /// assert_eq!(iter.next(), Some(n1));
579 /// assert_eq!(iter.next(), Some(n1_3));
580 /// assert_eq!(iter.next(), Some(n1_2));
581 /// assert_eq!(iter.next(), Some(n1_1));
582 /// assert_eq!(iter.next(), None);
583 /// ```
584 ///
585 /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
586 /// [`remove`]: struct.NodeId.html#method.remove
587 pub fn prepend<T>(self, new_child: NodeId, arena: &mut Arena<T>) {
588 self.checked_prepend(new_child, arena)
589 .expect("Preconditions not met: invalid argument");
590 }
591
592 /// Prepends a new child to this node, before existing children.
593 ///
594 /// # Failures
595 ///
596 /// * Returns [`NodeError::PrependSelf`] error if the given new child is
597 /// `self`.
598 /// * Returns [`NodeError::Removed`] error if the given new child or `self`
599 /// is [`remove`]d.
600 ///
601 /// # Examples
602 ///
603 /// ```
604 /// # use generational_indextree::Arena;
605 /// let mut arena = Arena::new();
606 /// let n1 = arena.new_node("1");
607 /// assert!(n1.checked_prepend(n1, &mut arena).is_err());
608 ///
609 /// let n1_1 = arena.new_node("1_1");
610 /// assert!(n1.checked_prepend(n1_1, &mut arena).is_ok());
611 /// ```
612 ///
613 /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
614 /// [`NodeError::PrependSelf`]: enum.NodeError.html#variant.PrependSelf
615 /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
616 /// [`remove`]: struct.NodeId.html#method.remove
617 pub fn checked_prepend<T>(
618 self,
619 new_child: NodeId,
620 arena: &mut Arena<T>,
621 ) -> Result<(), NodeError> {
622 if new_child == self {
623 return Err(NodeError::PrependSelf);
624 }
625 if !arena.nodes.contains(self.index) || !arena.nodes.contains(new_child.index) {
626 return Err(NodeError::Removed);
627 }
628 insert_with_neighbors(arena, new_child, Some(self), None, arena[self].first_child)
629 .expect("Should never fail: `new_child` is not `self` and they are not removed");
630
631 Ok(())
632 }
633
634 /// Inserts a new sibling after this node.
635 ///
636 /// # Panics
637 ///
638 /// Panics if:
639 ///
640 /// * the given new sibling is `self`, or
641 /// * the current node or the given new sibling was already [`remove`]d.
642 ///
643 /// # Examples
644 ///
645 /// ```
646 /// # use generational_indextree::Arena;
647 /// # let mut arena = Arena::new();
648 /// # let n1 = arena.new_node("1");
649 /// # let n1_1 = arena.new_node("1_1");
650 /// # n1.append(n1_1, &mut arena);
651 /// # let n1_2 = arena.new_node("1_2");
652 /// # n1.append(n1_2, &mut arena);
653 /// #
654 /// // arena
655 /// // `-- 1
656 /// // |-- 1_1
657 /// // `-- 1_2
658 ///
659 /// let n1_3 = arena.new_node("1_3");
660 /// n1_1.insert_after(n1_3, &mut arena);
661 ///
662 /// // arena
663 /// // `-- 1
664 /// // |-- 1_1
665 /// // |-- 1_3
666 /// // `-- 1_2
667 ///
668 /// let mut iter = n1.descendants(&arena);
669 /// assert_eq!(iter.next(), Some(n1));
670 /// assert_eq!(iter.next(), Some(n1_1));
671 /// assert_eq!(iter.next(), Some(n1_3));
672 /// assert_eq!(iter.next(), Some(n1_2));
673 /// assert_eq!(iter.next(), None);
674 /// ```
675 ///
676 /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
677 /// [`remove`]: struct.NodeId.html#method.remove
678 pub fn insert_after<T>(self, new_sibling: NodeId, arena: &mut Arena<T>) {
679 self.checked_insert_after(new_sibling, arena)
680 .expect("Preconditions not met: invalid argument");
681 }
682
683 /// Inserts a new sibling after this node.
684 ///
685 /// # Failures
686 ///
687 /// * Returns [`NodeError::InsertAfterSelf`] error if the given new sibling
688 /// is `self`.
689 /// * Returns [`NodeError::Removed`] error if the given new sibling or
690 /// `self` is [`remove`]d.
691 ///
692 /// # Examples
693 ///
694 /// ```
695 /// # use generational_indextree::Arena;
696 /// let mut arena = Arena::new();
697 /// let n1 = arena.new_node("1");
698 /// assert!(n1.checked_insert_after(n1, &mut arena).is_err());
699 ///
700 /// let n2 = arena.new_node("2");
701 /// assert!(n1.checked_insert_after(n2, &mut arena).is_ok());
702 /// ```
703 ///
704 /// [`Node::is_removed()`]: struct.Node.html#method.is_removed
705 /// [`NodeError::InsertAfterSelf`]: enum.NodeError.html#variant.InsertAfterSelf
706 /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
707 /// [`remove`]: struct.NodeId.html#method.remove
708 pub fn checked_insert_after<T>(
709 self,
710 new_sibling: NodeId,
711 arena: &mut Arena<T>,
712 ) -> Result<(), NodeError> {
713 if new_sibling == self {
714 return Err(NodeError::InsertAfterSelf);
715 }
716 if !arena.nodes.contains(self.index) || !arena.nodes.contains(new_sibling.index) {
717 return Err(NodeError::Removed);
718 }
719 new_sibling.detach(arena);
720 let (next_sibling, parent) = {
721 let current = &arena[self];
722 (current.next_sibling, current.parent)
723 };
724 insert_with_neighbors(arena, new_sibling, parent, Some(self), next_sibling)
725 .expect("Should never fail: `new_sibling` is not `self` and they are not removed");
726
727 Ok(())
728 }
729
730 /// Inserts a new sibling before this node.
731 ///
732 /// # Panics
733 ///
734 /// Panics if:
735 ///
736 /// * the given new sibling is `self`, or
737 /// * the current node or the given new sibling was already [`remove`]d.
738 ///
739 /// # Examples
740 ///
741 /// ```
742 /// # use generational_indextree::Arena;
743 /// let mut arena = Arena::new();
744 /// let n1 = arena.new_node("1");
745 /// let n1_1 = arena.new_node("1_1");
746 /// n1.append(n1_1, &mut arena);
747 /// let n1_2 = arena.new_node("1_2");
748 /// n1.append(n1_2, &mut arena);
749 ///
750 /// // arena
751 /// // `-- 1
752 /// // |-- 1_1
753 /// // `-- 1_2
754 ///
755 /// let n1_3 = arena.new_node("1_3");
756 /// n1_2.insert_before(n1_3, &mut arena);
757 ///
758 /// // arena
759 /// // `-- 1
760 /// // |-- 1_1
761 /// // |-- 1_3
762 /// // `-- 1_2
763 ///
764 /// let mut iter = n1.descendants(&arena);
765 /// assert_eq!(iter.next(), Some(n1));
766 /// assert_eq!(iter.next(), Some(n1_1));
767 /// assert_eq!(iter.next(), Some(n1_3));
768 /// assert_eq!(iter.next(), Some(n1_2));
769 /// assert_eq!(iter.next(), None);
770 /// ```
771 ///
772 /// [`remove`]: struct.NodeId.html#method.remove
773 pub fn insert_before<T>(self, new_sibling: NodeId, arena: &mut Arena<T>) {
774 self.checked_insert_before(new_sibling, arena)
775 .expect("Preconditions not met: invalid argument");
776 }
777
778 /// Inserts a new sibling before this node.
779 ///
780 /// # Failures
781 ///
782 /// * Returns [`NodeError::InsertBeforeSelf`] error if the given new sibling
783 /// is `self`.
784 /// * Returns [`NodeError::Removed`] error if the given new sibling or
785 /// `self` is [`remove`]d.
786 ///
787 /// # Examples
788 ///
789 /// ```
790 /// # use generational_indextree::Arena;
791 /// let mut arena = Arena::new();
792 /// let n1 = arena.new_node("1");
793 /// assert!(n1.checked_insert_before(n1, &mut arena).is_err());
794 ///
795 /// let n2 = arena.new_node("2");
796 /// assert!(n1.checked_insert_before(n2, &mut arena).is_ok());
797 /// ```
798 ///
799 /// [`NodeError::InsertBeforeSelf`]: enum.NodeError.html#variant.InsertBeforeSelf
800 /// [`NodeError::Removed`]: enum.NodeError.html#variant.Removed
801 /// [`remove`]: struct.NodeId.html#method.remove
802 pub fn checked_insert_before<T>(
803 self,
804 new_sibling: NodeId,
805 arena: &mut Arena<T>,
806 ) -> Result<(), NodeError> {
807 if new_sibling == self {
808 return Err(NodeError::InsertBeforeSelf);
809 }
810 if !arena.nodes.contains(self.index) || !arena.nodes.contains(new_sibling.index) {
811 return Err(NodeError::Removed);
812 }
813 new_sibling.detach(arena);
814 let (previous_sibling, parent) = {
815 let current = &arena[self];
816 (current.previous_sibling, current.parent)
817 };
818 insert_with_neighbors(arena, new_sibling, parent, previous_sibling, Some(self))
819 .expect("Should never fail: `new_sibling` is not `self` and they are not removed");
820
821 Ok(())
822 }
823
824 /// Removes a node from the arena.
825 ///
826 /// Children of the removed node will be inserted to the place where the
827 /// removed node was.
828 ///
829 /// Please note that the node will not be removed from the internal arena
830 /// storage, but marked as `removed`. Traversing the arena returns a
831 /// plain iterator and contains removed elements too.
832 ///
833 /// # Examples
834 ///
835 /// ```
836 /// # use generational_indextree::Arena;
837 /// # let mut arena = Arena::new();
838 /// # let n1 = arena.new_node("1");
839 /// # let n1_1 = arena.new_node("1_1");
840 /// # n1.append(n1_1, &mut arena);
841 /// # let n1_2 = arena.new_node("1_2");
842 /// # n1.append(n1_2, &mut arena);
843 /// # let n1_2_1 = arena.new_node("1_2_1");
844 /// # n1_2.append(n1_2_1, &mut arena);
845 /// # let n1_2_2 = arena.new_node("1_2_2");
846 /// # n1_2.append(n1_2_2, &mut arena);
847 /// # let n1_3 = arena.new_node("1_3");
848 /// # n1.append(n1_3, &mut arena);
849 /// #
850 /// // arena
851 /// // `-- 1
852 /// // |-- 1_1
853 /// // |-- 1_2
854 /// // | |-- 1_2_1
855 /// // | `-- 1_2_2
856 /// // `-- 1_3
857 ///
858 /// n1_2.remove(&mut arena);
859 ///
860 /// let mut iter = n1.descendants(&arena);
861 /// assert_eq!(iter.next(), Some(n1));
862 /// assert_eq!(iter.next(), Some(n1_1));
863 /// assert_eq!(iter.next(), Some(n1_2_1));
864 /// assert_eq!(iter.next(), Some(n1_2_2));
865 /// assert_eq!(iter.next(), Some(n1_3));
866 /// assert_eq!(iter.next(), None);
867 /// ```
868 ///
869 pub fn remove<T>(self, arena: &mut Arena<T>) {
870 debug_assert_triangle_nodes!(
871 arena,
872 arena[self].parent,
873 arena[self].previous_sibling,
874 Some(self)
875 );
876 debug_assert_triangle_nodes!(
877 arena,
878 arena[self].parent,
879 Some(self),
880 arena[self].next_sibling
881 );
882 debug_assert_triangle_nodes!(arena, Some(self), None, arena[self].first_child);
883 debug_assert_triangle_nodes!(arena, Some(self), arena[self].last_child, None);
884
885 // Retrieve needed values.
886 let (parent, previous_sibling, next_sibling, first_child, last_child) = {
887 let node = &arena[self];
888 (
889 node.parent,
890 node.previous_sibling,
891 node.next_sibling,
892 node.first_child,
893 node.last_child,
894 )
895 };
896
897 assert_eq!(first_child.is_some(), last_child.is_some());
898 self.detach(arena);
899 if let (Some(first_child), Some(last_child)) = (first_child, last_child) {
900 let range = SiblingsRange::new(first_child, last_child).detach_from_siblings(arena);
901 range
902 .transplant(arena, parent, previous_sibling, next_sibling)
903 .expect("Should never fail: neighbors and children must be consistent");
904 }
905 debug_assert!(arena[self].is_detached());
906 arena.nodes.remove(self.index);
907 }
908
909 /// Removes a node and its descendants from the arena.
910 /// # Examples
911 ///
912 /// ```
913 /// # use generational_indextree::Arena;
914 /// # let mut arena = Arena::new();
915 /// # let n1 = arena.new_node("1");
916 /// # let n1_1 = arena.new_node("1_1");
917 /// # n1.append(n1_1, &mut arena);
918 /// # let n1_2 = arena.new_node("1_2");
919 /// # n1.append(n1_2, &mut arena);
920 /// # let n1_2_1 = arena.new_node("1_2_1");
921 /// # n1_2.append(n1_2_1, &mut arena);
922 /// # let n1_2_2 = arena.new_node("1_2_2");
923 /// # n1_2.append(n1_2_2, &mut arena);
924 /// # let n1_3 = arena.new_node("1_3");
925 /// # n1.append(n1_3, &mut arena);
926 /// #
927 /// // arena
928 /// // `-- 1
929 /// // |-- 1_1
930 /// // |-- 1_2
931 /// // | |-- 1_2_1
932 /// // | `-- 1_2_2
933 /// // `-- 1_3
934 ///
935 /// n1_2.remove_subtree(&mut arena);
936 ///
937 /// let mut iter = n1.descendants(&arena);
938 /// assert_eq!(iter.next(), Some(n1));
939 /// assert_eq!(iter.next(), Some(n1_1));
940 /// assert_eq!(iter.next(), Some(n1_3));
941 /// assert_eq!(iter.next(), None);
942 /// ```
943 ///
944 pub fn remove_subtree<T>(self, arena: &mut Arena<T>) {
945 self.detach(arena);
946
947 // // use a preorder traversal to remove node.
948 // let mut cursor = Some(self);
949 // while let Some(id) = cursor {
950 // arena.free_node(id);
951 // let node = &arena[id];
952 // cursor = node
953 // .first_child
954 // .or(node.next_sibling)
955 // .or_else(|| node.parent.and_then(|p| arena[p].next_sibling));
956 // }
957 }
958}