treena/dynamic/hierarchy.rs
1//! Dynamic hierarchy for trees and forests.
2
3pub(crate) mod traverse;
4
5use core::fmt;
6
7use alloc::vec::Vec;
8
9use crate::dynamic::forest::StructureError;
10use crate::dynamic::hierarchy::traverse::AncestorsTraverser;
11use crate::dynamic::{InsertAs, InternalNodeId};
12
13/// A forest without custom data tied to nodes.
14#[derive(Debug, Clone)]
15pub(crate) struct Hierarchy<Id> {
16 /// Neighbors storage.
17 neighbors: Vec<Neighbors<Id>>,
18}
19
20impl<Id: InternalNodeId> Hierarchy<Id> {
21 /// Creates a new root node.
22 ///
23 /// # Panics
24 ///
25 /// Panics if the node ID overflows.
26 pub(crate) fn create_root(&mut self) -> Id {
27 let new_id = Id::from_usize(self.neighbors.len())
28 .expect("[precondition] node ID overflowed presumably due to too many node creations");
29 self.neighbors.push(Neighbors::new_root(new_id));
30
31 new_id
32 }
33
34 /// Returns a reference to the neighbors for the node if the node is alive.
35 ///
36 /// Returns `None` if the node ID is invalid or the node has already been removed.
37 #[must_use]
38 pub(crate) fn neighbors(&self, id: Id) -> Option<&Neighbors<Id>> {
39 self.neighbors.get(id.to_usize()).filter(|v| v.is_alive())
40 }
41
42 /// Returns a mutable reference to the neighbors for the node if the node is alive.
43 ///
44 /// Returns `None` if the node ID is invalid or the node has already been removed.
45 #[must_use]
46 pub(crate) fn neighbors_mut(&mut self, id: Id) -> Option<&mut Neighbors<Id>> {
47 self.neighbors
48 .get_mut(id.to_usize())
49 .filter(|v| v.is_alive())
50 }
51
52 /// Returns true if the ID is valid inside this forest.
53 #[must_use]
54 pub(crate) fn is_valid(&self, id: Id) -> bool {
55 id.to_usize() < self.neighbors.len()
56 }
57
58 /// Returns true if the node is alive.
59 #[must_use]
60 pub(crate) fn is_alive(&self, id: Id) -> bool {
61 self.neighbors
62 .get(id.to_usize())
63 .map_or(false, |v| v.is_alive())
64 }
65
66 /// Connects the given adjacent neighbors and updates fields properly.
67 ///
68 /// This function connects the given three nodes and update fields to make
69 /// them consistent.
70 ///
71 /// ```text
72 /// parent
73 /// / \
74 /// / \
75 /// prev -> next
76 /// ```
77 ///
78 /// More precisely, the fields below will be updated:
79 ///
80 /// * `parent->first_child`,
81 /// + Updated if `prev_child` is `None`, i.e. when `next_child` will be
82 /// the first child or the parent have no child.
83 /// * `prev_child->parent`,
84 /// * `prev_child->next_sibling`,
85 /// * `next_child->parent`, and
86 /// * `next_child->prev_sibling_cyclic`.
87 /// + `prev_sibling` is used if available.
88 /// + If `next_child` will be the first child of the parent, the last
89 /// child is used.
90 /// + Otherwise (if both `prev_sibling` and `parent` is `None`),
91 /// `next_child` is used since this means that `next_child` is the
92 /// root of a tree.
93 ///
94 /// In order to update `prev_sibling_cyclic` of the first sibling,
95 /// **nodes should be connected in order** and the last node should be
96 /// updated at last.
97 ///
98 /// # Panics
99 ///
100 /// * Panics if the `parent` is `None` while both of `prev_child` and
101 /// `next_child` are `Some`, since nodes cannot have siblings without
102 /// having a parent.
103 /// * Panics if `prev_child` and `next_child` are both `Some(_)` and are
104 /// identical, since a node cannot be adjacent sibling of itself.
105 fn connect_triangle(
106 &mut self,
107 parent: Option<Id>,
108 prev_child: Option<Id>,
109 next_child: Option<Id>,
110 ) {
111 if parent.is_none() && prev_child.is_some() && next_child.is_some() {
112 panic!("[precondition] nodes cannot have siblings without having a parent");
113 }
114 if prev_child
115 .zip(next_child)
116 .map_or(false, |(prev, next)| prev == next)
117 {
118 panic!("[precondition] a node cannot be adjacent sibling of itself");
119 }
120
121 if let Some(prev_child) = prev_child {
122 let prev_child_nbs = self
123 .neighbors_mut(prev_child)
124 .expect("[precondition] the given `prev_child` node must be alive");
125 // Set prev->parent.
126 prev_child_nbs.parent = parent;
127 // Set prev->next.
128 prev_child_nbs.next_sibling = next_child;
129 }
130
131 if let Some(next_child) = next_child {
132 let next_child_prev_cyclic = match prev_child {
133 // If the real previous child exist, just use it.
134 Some(prev_child) => prev_child,
135 None => match parent {
136 // If `prev_child` is `None` but the parent is available,
137 // then `next_child` is the first child, and
138 // `prev_sibling_cyclic` should be the last child of the
139 // parent.
140 // If the parent does not have any children, then
141 // `next_child` will be the first child.
142 Some(parent) => self
143 .neighbors(parent)
144 .expect("[precondition] the given `parent` node must be alive")
145 .last_child(self)
146 .unwrap_or(next_child),
147 // `next_child` is a root of the tree.
148 None => next_child,
149 },
150 };
151
152 let next_child_nbs = self
153 .neighbors_mut(next_child)
154 .expect("[precondition] the given `next_child` node must be alive");
155 // Set next->parent.
156 next_child_nbs.parent = parent;
157 // Set next->prev.
158 next_child_nbs.prev_sibling_cyclic = Some(next_child_prev_cyclic);
159 }
160
161 // Neighbors of the parent must be modified after `next_child`, since
162 // setting `next_child` requires last child of the non-modified parent.
163 if let Some(parent) = parent {
164 if prev_child.is_none() {
165 let parent_nbs = self
166 .neighbors_mut(parent)
167 .expect("[precondition] the given `parent` node must be alive");
168 // `next_child` is the first child (if available).
169 parent_nbs.first_child = next_child;
170 } else if next_child.is_none() {
171 // `prev_child` has no next sibling. This means that
172 // `prev_child` is the last child of the parent.
173 let first_child = self
174 .neighbors(parent)
175 .expect("[precondition] the given `parent` node must be alive")
176 .first_child()
177 .expect("[consistency] `parent` must have a child including `prev_child`");
178 if let Some(prev_child) = prev_child {
179 self.neighbors_mut(first_child)
180 .expect("[precondition] the first child of the `parent` must be alive")
181 .prev_sibling_cyclic = Some(prev_child);
182 }
183 }
184 }
185 }
186
187 /// Detaches the tree from neighbors.
188 ///
189 /// Tree structure under the given node will be preserved.
190 /// The detached node will become a root node.
191 ///
192 /// If you want to detach not subtree but single node, use
193 /// [`detach_single`][`Self::detach_single`] method.
194 ///
195 /// ```text
196 /// Before `detach`:
197 ///
198 /// root
199 /// |-- 0
200 /// |-- 1
201 /// | |-- 1-0
202 /// | |-- 1-1
203 /// | `-- 1-2
204 /// `-- 2
205 ///
206 /// After `detach`:
207 ///
208 /// root
209 /// |-- 0
210 /// `-- 2
211 ///
212 /// 1
213 /// |-- 1-0
214 /// |-- 1-1
215 /// `-- 1-2
216 /// ```
217 ///
218 /// # Panics
219 ///
220 /// Panics if the node is not alive.
221 pub(crate) fn detach(&mut self, node: Id) {
222 let nbs = self
223 .neighbors(node)
224 .expect("[precondition] the node must be alive");
225 // If the node has no parent, the tree can be considered already detached.
226 let parent = match nbs.parent() {
227 Some(v) => v,
228 None => return,
229 };
230 let prev = nbs.prev_sibling(self);
231 let next = nbs.next_sibling();
232
233 // Connect the siblings before and after the node.
234 self.connect_triangle(Some(parent), prev, next);
235
236 // Reset the neighbors info of the node.
237 let mut nbs = self
238 .neighbors_mut(node)
239 .expect("[precondition] the node must be alive");
240 nbs.parent = None;
241 nbs.next_sibling = None;
242 nbs.prev_sibling_cyclic = Some(node);
243 }
244
245 /// Detaches the node from neighbors and make it orphan root.
246 ///
247 /// Children are inserted to the place where the detached node was.
248 ///
249 /// If you want to detach not single node but subtree, use
250 /// [`detach`][`Self::detach`] method.
251 ///
252 /// ```text
253 /// Before `detach_single`:
254 ///
255 /// root
256 /// |-- 0
257 /// |-- 1
258 /// | |-- 1-0
259 /// | |-- 1-1
260 /// | `-- 1-2
261 /// `-- 2
262 ///
263 /// After `detach_single`:
264 ///
265 /// root
266 /// |-- 0
267 /// |-- 1-0
268 /// |-- 1-1
269 /// |-- 1-2
270 /// `-- 2
271 ///
272 /// 1
273 /// ```
274 ///
275 /// # Errors
276 ///
277 /// Returns [`StructureError::SiblingsWithoutParent`] when the node has
278 /// multiple children but has no parent.
279 ///
280 /// # Panics
281 ///
282 /// Panics if the node is not alive.
283 pub(crate) fn detach_single(&mut self, node: Id) -> Result<(), StructureError> {
284 let nbs = self
285 .neighbors(node)
286 .expect("[precondition] the node must be alive");
287
288 let (first_child, last_child) = match nbs.first_last_child(self) {
289 Some(v) => v,
290 None => {
291 // No children.
292 self.detach(node);
293 return Ok(());
294 }
295 };
296
297 let parent = match nbs.parent() {
298 Some(v) => v,
299 None => {
300 if first_child != last_child {
301 return Err(StructureError::SiblingsWithoutParent);
302 }
303 // Single child and no parent.
304 // The single child becomes the new root.
305 self.detach(first_child);
306 // Now the node has no children.
307 self.detach(node);
308 return Ok(());
309 }
310 };
311
312 let prev = nbs.prev_sibling(self);
313 let next = nbs.next_sibling();
314
315 // Connect the siblings before and after the node.
316 self.connect_triangle(Some(parent), prev, next);
317
318 // Insert the children between the prev and next siblings.
319 SiblingsRange::new(self, first_child, last_child)
320 .transplant(self, parent, prev, next)
321 .expect("[consistency] structure being created must be valid");
322
323 // Reset the neighbors info of the node.
324 let mut nbs = self
325 .neighbors_mut(node)
326 .expect("[precondition] the node must be alive");
327 nbs.parent = None;
328 nbs.next_sibling = None;
329 nbs.prev_sibling_cyclic = Some(node);
330 debug_assert_eq!(
331 nbs.first_child(),
332 None,
333 "[consistency] the children have been transplanted"
334 );
335
336 Ok(())
337 }
338
339 /// Detaches `node` and inserts the given node to the target position.
340 ///
341 /// # Panics
342 ///
343 /// Panics if any of the given nodes (including the anchor of the destination)
344 /// are not alive.
345 ///
346 /// # Errors
347 ///
348 /// * [`StructureError::AncestorDescendantLoop`]
349 /// + In case `dest` is `FirstChildOf(node)` or `LastChildOf(node)`.
350 /// * [`StructureError::UnorderableSiblings`]
351 /// + In case `dest` is `PreviousSiblingOf(node)` or `NextSiblingOf(node)`.
352 /// * [`StructureError::SiblingsWithoutParent`]
353 /// + In case `dest` is `PreviousSiblingOf(v)` or `NextSiblingOf(v)`, and
354 /// `v` does not have a parent.
355 pub(crate) fn insert(&mut self, node: Id, dest: InsertAs<Id>) -> Result<(), StructureError> {
356 match dest {
357 InsertAs::FirstChildOf(parent) => self.prepend_child(node, parent),
358 InsertAs::LastChildOf(parent) => self.append_child(node, parent),
359 InsertAs::PreviousSiblingOf(next) => self.insert_before(node, next),
360 InsertAs::NextSiblingOf(prev) => self.insert_after(node, prev),
361 }
362 }
363
364 /// Detaches and prepends the given node to children of `self` as the first child.
365 ///
366 /// # Errors
367 ///
368 /// Returns [`StructureError::AncestorDescendantLoop`] error when
369 /// `new_first_child` is `parent` or its ancestor.
370 ///
371 /// # Panics
372 ///
373 /// Panics if any of the given nodes are not alive.
374 fn prepend_child(&mut self, new_first_child: Id, parent: Id) -> Result<(), StructureError> {
375 let old_first_child = self
376 .neighbors(parent)
377 .expect("[precondition] the node must be alive")
378 .first_child();
379 SiblingsRange::with_single_toplevel(self, new_first_child).transplant(
380 self,
381 parent,
382 None,
383 old_first_child,
384 )
385 }
386
387 /// Detaches and appends the given node to children of `self` as the last child.
388 ///
389 /// # Errors
390 ///
391 /// Returns [`StructureError::AncestorDescendantLoop`] error when
392 /// `new_last_child` is `parent` or its ancestor.
393 ///
394 /// # Panics
395 ///
396 /// Panics if any of the given nodes are not alive.
397 fn append_child(&mut self, new_last_child: Id, parent: Id) -> Result<(), StructureError> {
398 let old_last_child = self
399 .neighbors(parent)
400 .expect("[precondition] the parent must be alive")
401 .last_child(self);
402 // `new_last_child` is an independent tree, so transplanting won't fail.
403 SiblingsRange::with_single_toplevel(self, new_last_child).transplant(
404 self,
405 parent,
406 old_last_child,
407 None,
408 )
409 }
410
411 /// Detaches and inserts the given node as the previous sibling of `next_sibling`.
412 ///
413 /// # Errors
414 ///
415 /// Returns [`StructureError::UnorderableSiblings`] error when `node` and
416 /// `next_sibling` are identical.
417 ///
418 /// # Panics
419 ///
420 /// Panics if any of the given nodes are not alive.
421 /// Panics if the `next_sibling` does not have a parent.
422 fn insert_before(&mut self, node: Id, next_sibling: Id) -> Result<(), StructureError> {
423 if node == next_sibling {
424 return Err(StructureError::UnorderableSiblings);
425 }
426
427 let next_nbs = self
428 .neighbors(next_sibling)
429 .expect("[precondition] the next sibling must be alive");
430 let parent = next_nbs
431 .parent()
432 .expect("[precondition] the parent must be alive to have siblings");
433 let prev_sibling = next_nbs.prev_sibling(self);
434 SiblingsRange::with_single_toplevel(self, node).transplant(
435 self,
436 parent,
437 prev_sibling,
438 Some(next_sibling),
439 )
440 }
441
442 /// Detaches and inserts the given node as the next sibling of `prev_sibling`.
443 ///
444 /// # Errors
445 ///
446 /// Returns [`StructureError::UnorderableSiblings`] error when `node` and
447 /// `prev_sibling` are identical.
448 ///
449 /// # Panics
450 ///
451 /// Panics if any of the given nodes are not alive.
452 /// Panics if the `prev_sibling` does not have a parent.
453 fn insert_after(&mut self, node: Id, prev_sibling: Id) -> Result<(), StructureError> {
454 if node == prev_sibling {
455 return Err(StructureError::UnorderableSiblings);
456 }
457
458 let prev_nbs = self
459 .neighbors(prev_sibling)
460 .expect("[precondition] the previous sibling must be alive");
461 let parent = prev_nbs
462 .parent()
463 .expect("[precondition] the parent must be alive to have siblings");
464 let next_sibling = prev_nbs.next_sibling();
465 SiblingsRange::with_single_toplevel(self, node).transplant(
466 self,
467 parent,
468 Some(prev_sibling),
469 next_sibling,
470 )
471 }
472}
473
474impl<Id: InternalNodeId> Default for Hierarchy<Id> {
475 #[inline]
476 fn default() -> Self {
477 Self {
478 neighbors: Default::default(),
479 }
480 }
481}
482
483/// Neighbors.
484#[derive(Clone, Copy, PartialEq, Eq)]
485pub(crate) struct Neighbors<Id> {
486 /// Parent.
487 parent: Option<Id>,
488 /// Cyclic previous sibling.
489 ///
490 /// `None` if the node has already been removed.
491 /// If the node is alive and is the first sibling, node ID of the last sibling.
492 /// Otherwise (i.e. the node is alive but is not the first sibling),
493 /// node ID of the previous sibling.
494 ///
495 /// By making this field cyclic, "last child" field becomes unnecessary.
496 ///
497 /// See
498 /// <http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html#data-structures-for-the-document-object-model>.
499 prev_sibling_cyclic: Option<Id>,
500 /// Next sibling.
501 next_sibling: Option<Id>,
502 /// First child.
503 first_child: Option<Id>,
504}
505
506impl<Id: InternalNodeId> Neighbors<Id> {
507 /// Creates a new `Neighbors` that is not connected to anyone.
508 #[inline]
509 #[must_use]
510 fn new_root(id: Id) -> Self {
511 Self {
512 parent: None,
513 prev_sibling_cyclic: Some(id),
514 next_sibling: None,
515 first_child: None,
516 }
517 }
518
519 /// Returns true if the node is alive.
520 #[inline]
521 #[must_use]
522 fn is_alive(&self) -> bool {
523 self.prev_sibling_cyclic.is_some()
524 }
525
526 /// Returns the node ID of the parent.
527 ///
528 /// # Panics
529 ///
530 /// Panics if the `self` node has already been removed.
531 #[inline]
532 #[must_use]
533 pub(crate) fn parent(&self) -> Option<Id> {
534 if !self.is_alive() {
535 panic!("[precondition] the node must be alive");
536 }
537 self.parent
538 }
539
540 /// Returns the node ID of the next sibling.
541 ///
542 /// # Panics
543 ///
544 /// Panics if the `self` node has already been removed.
545 #[inline]
546 #[must_use]
547 pub(crate) fn next_sibling(&self) -> Option<Id> {
548 if !self.is_alive() {
549 panic!("[precondition] the node must be alive");
550 }
551 self.next_sibling
552 }
553
554 /// Returns the node ID of the previous sibling.
555 ///
556 /// # Panics
557 ///
558 /// Panics if the `self` node has already been removed.
559 #[must_use]
560 pub(crate) fn prev_sibling(&self, hier: &Hierarchy<Id>) -> Option<Id> {
561 let prev_sibling_cyclic = match self.prev_sibling_cyclic {
562 Some(v) => v,
563 None => panic!("[precondition] the node must be alive"),
564 };
565 let prev_cyc_node = hier
566 .neighbors(prev_sibling_cyclic)
567 .expect("[consistency] the `prev_sibling_cyclic` node must be alive");
568
569 // If `next_sibling` is available, `prev_sibling_cyclic` is a previous node.
570 // If `next_sibling` is `None`, `prev_sibling_cyclic` is not a previous
571 // node but the last sibling.
572 prev_cyc_node.next_sibling.and(Some(prev_sibling_cyclic))
573 }
574
575 /// Returns the node ID of the first child.
576 ///
577 /// # Panics
578 ///
579 /// Panics if the `self` node has already been removed.
580 #[inline]
581 #[must_use]
582 pub(crate) fn first_child(&self) -> Option<Id> {
583 if !self.is_alive() {
584 panic!("[precondition] the node must be alive");
585 }
586 self.first_child
587 }
588
589 /// Returns the node ID of the last child.
590 ///
591 /// # Panics
592 ///
593 /// Panics if the `self` node has already been removed.
594 #[must_use]
595 pub(crate) fn last_child(&self, hier: &Hierarchy<Id>) -> Option<Id> {
596 self.first_last_child(hier).map(|(_first, last)| last)
597 }
598
599 /// Returns the node IDs of the first child and the last child.
600 ///
601 /// # Panics
602 ///
603 /// Panics if the `self` node has already been removed.
604 #[inline]
605 #[must_use]
606 pub(crate) fn first_last_child(&self, hier: &Hierarchy<Id>) -> Option<(Id, Id)> {
607 if !self.is_alive() {
608 panic!("[precondition] the node must be alive");
609 }
610
611 let first_child = self.first_child()?;
612 let last_child = hier
613 .neighbors(first_child)
614 .expect("[consistency] children of a live node must also be alive")
615 .prev_sibling_cyclic;
616
617 match last_child {
618 Some(last_child) => Some((first_child, last_child)),
619 None => panic!("[consistency] the last child must be alive"),
620 }
621 }
622
623 /// Returns true if the node has no neighbors.
624 ///
625 /// # Panics
626 ///
627 /// Panics if the `self` node has already been removed.
628 #[must_use]
629 pub(crate) fn is_alone(&self) -> bool {
630 if !self.is_alive() {
631 panic!("[precondition] the node must be alive");
632 }
633 self.parent.is_none() && self.next_sibling.is_none() && self.first_child.is_none()
634 }
635
636 /// Makes the node removed state.
637 ///
638 /// It is caller's responsibility to make the node alone and keep the
639 /// hierarchy consistent.
640 ///
641 /// # Panics
642 ///
643 /// Panics if the `self` node has already been removed.
644 /// Panics if the `self` node is not alone.
645 pub(crate) fn make_removed(&mut self) {
646 if !self.is_alone() {
647 panic!("[precondition] the node must be alive and alone");
648 }
649 self.force_make_removed();
650 }
651
652 /// Makes the node removed state **even if it can make the arena inconsistent**.
653 ///
654 /// It is caller's responsibility to make the node alone and/or make the
655 /// hierarchy finally consistent.
656 ///
657 /// # Panics
658 ///
659 /// Panics if the `self` node has already been removed.
660 pub(crate) fn force_make_removed(&mut self) {
661 if !self.is_alive() {
662 panic!("[precondition] the node must be alive");
663 }
664 self.parent = None;
665 self.prev_sibling_cyclic = None;
666 self.next_sibling = None;
667 self.first_child = None;
668 }
669}
670
671// For compact printing.
672impl<Id: fmt::Debug> fmt::Debug for Neighbors<Id> {
673 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
674 /// A wrapper to print optional node ID in compact form.
675 #[derive(Clone, Copy)]
676 struct OptNodeId<'a, Id>(&'a Option<Id>);
677 impl<Id: fmt::Debug> fmt::Debug for OptNodeId<'_, Id> {
678 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
679 match self.0 {
680 Some(id) => id.fmt(f),
681 None => f.write_str("None"),
682 }
683 }
684 }
685
686 f.debug_struct("Neighbors")
687 .field("parent", &OptNodeId(&self.parent))
688 .field("prev_sibling_cyclic", &OptNodeId(&self.prev_sibling_cyclic))
689 .field("next_sibling", &OptNodeId(&self.next_sibling))
690 .field("first_child", &OptNodeId(&self.first_child))
691 .finish()
692 }
693}
694
695/// Siblings range.
696#[derive(Debug)]
697struct SiblingsRange<Id> {
698 /// First node in the range.
699 first: Id,
700 /// Last node in the range.
701 last: Id,
702}
703
704impl<Id: InternalNodeId> SiblingsRange<Id> {
705 /// Creates a new siblings range.
706 ///
707 /// # Panics
708 ///
709 /// * Panics if `first` or `last` is not alive.
710 /// * Panics if `first` and `last` does not have the same parent node.
711 // TODO: Ordering:
712 // This should panic if `first` is a succeeding sibling of `prev`.
713 // However, this won't be O(1) operation. The hierarchy does not have an
714 // efficient way to test siblings orders.
715 // Without testing this, the function should be considered as unsafe.
716 // For now, it is caller's responsibility to ensure siblings order.
717 fn new(hier: &Hierarchy<Id>, first: Id, last: Id) -> Self {
718 if first == last {
719 return Self::with_single_toplevel(hier, first);
720 }
721
722 let first_parent = hier
723 .neighbors(first)
724 .expect("[precondition] `first` node must be alive")
725 .parent();
726 let last_parent = hier
727 .neighbors(last)
728 .expect("[precondition] `last` node must be alive")
729 .parent();
730 if first_parent != last_parent {
731 panic!("[precondition] `first` and `last` must have the same parent");
732 }
733
734 Self { first, last }
735 }
736
737 /// Creates a new siblings range from a single toplevel node.
738 ///
739 /// # Panics
740 ///
741 /// * Panics if the node is not alive.
742 fn with_single_toplevel(hier: &Hierarchy<Id>, node: Id) -> Self {
743 if !hier.is_alive(node) {
744 panic!("[precondition] the node must be alive");
745 }
746
747 Self {
748 first: node,
749 last: node,
750 }
751 }
752
753 /// Inserts the nodes in the range to the given place.
754 ///
755 /// ```text
756 /// Before:
757 ///
758 /// parent
759 /// / \
760 /// / \
761 /// prev_sibling -> next_sibling
762 ///
763 /// (possible parent)
764 /// _____________/ __/ \___ \______________
765 /// / / \ \
766 /// PREV_OF_FIRST -> self.first --...-> self.last -> NEXT_OF_LAST
767 ///
768 ///
769 /// After:
770 ///
771 /// parent
772 /// _____________/ __/ \___ \______________
773 /// / / \ \
774 /// prev_sibling -> self.first --...-> self.last -> next_sibling
775 ///
776 /// (possible parent)
777 /// / \
778 /// / \
779 /// PREV_OF_FIRST -> NEXT_OF_LAST
780 /// ```
781 ///
782 /// # Failures
783 ///
784 /// * Returns `Err(StructureError::AncestorDescendantLoop)` if the `parent`
785 /// is a descendant of the node in the range.
786 ///
787 /// # Panics
788 ///
789 /// * Panics if the `parent`, `prev_sibling`, or `next_sibling` is not alive.
790 /// * Panics if the `parent` is not the actual parent of `prev_sibling` and
791 /// `next_sibling`.
792 /// * Panics if any node in the range (`self`) is not alive.
793 fn transplant(
794 self,
795 hier: &mut Hierarchy<Id>,
796 parent: Id,
797 prev_sibling: Option<Id>,
798 next_sibling: Option<Id>,
799 ) -> Result<(), StructureError> {
800 // Detect possible ancestor-descendant loop beforehand.
801 if self.transplant_would_make_cyclic_links(hier, parent) {
802 return Err(StructureError::AncestorDescendantLoop);
803 }
804
805 // Detach the nodes.
806 {
807 let first_nbs = hier
808 .neighbors(self.first)
809 .expect("[consistency] nodes in the range must be alive");
810 let range_parent = first_nbs.parent();
811 let prev_of_range = first_nbs.prev_sibling(hier);
812 let next_of_range = hier
813 .neighbors(self.last)
814 .expect("[consistency] nodes in the range must be alive")
815 .next_sibling();
816 // Connect the nodes before and after the range.
817 hier.connect_triangle(range_parent, prev_of_range, next_of_range);
818 }
819
820 // Rewrite parents in the range.
821 {
822 let mut child_opt = Some(self.first);
823 while let Some(child) = child_opt {
824 assert_ne!(
825 child, parent,
826 "[consistency] possibility of ancestor-descendant loop is already tested"
827 );
828 let child_nbs = hier
829 .neighbors_mut(child)
830 .expect("[consistency] nodes in the range must be alive");
831 child_nbs.parent = Some(parent);
832 if child == self.last {
833 break;
834 }
835 child_opt = child_nbs.next_sibling();
836 }
837 }
838
839 // Connect the first node in the range to the previous sibling.
840 // If they are identical, no need to update neighbors info.
841 if prev_sibling != Some(self.first) {
842 hier.connect_triangle(Some(parent), prev_sibling, Some(self.first));
843 }
844
845 // Connect the last node in the range to the next sibling.
846 // If they are identical, no need to update neighbors info.
847 if next_sibling != Some(self.last) {
848 hier.connect_triangle(Some(parent), Some(self.last), next_sibling);
849 }
850
851 Ok(())
852 }
853
854 /// Returns true if `transplant()` would create cyclic links.
855 fn transplant_would_make_cyclic_links(&self, hier: &Hierarchy<Id>, parent: Id) -> bool {
856 let first_nbs = hier
857 .neighbors(self.first)
858 .expect("[consistency] nodes in the range must be alive");
859
860 if self.first == self.last {
861 let range_root = self.first;
862
863 let mut ancestors = AncestorsTraverser::with_start(parent, hier);
864 while let Some(ancestor) = ancestors.next(hier) {
865 if ancestor == range_root {
866 // `parent` is a descendant node of the range root.
867 return true;
868 }
869 }
870 } else {
871 // Every tree in the hierarchy has root node. So, if the toplevel
872 // nodes in the range don't have parent, then it means the range
873 // consists of single toplevel node. Such case is already handled
874 // by `self.first == self.last` branch.
875 let range_parent = first_nbs
876 .parent()
877 .expect("[consistency] range with multiple toplevel nodes must have a parent");
878 if range_parent == parent {
879 // The range will be transplanted under the same parent again.
880 return false;
881 }
882
883 let mut ancestors = AncestorsTraverser::with_start(parent, hier);
884 // Initially `prev_ancestor` is `parent`.
885 let mut prev_ancestor = ancestors
886 .next(hier)
887 .expect("[validity] start node itself must be iterated");
888 while let Some(ancestor) = ancestors.next(hier) {
889 if ancestor != range_parent {
890 continue;
891 }
892 // root:range_parent
893 // |-- 0
894 // | `-- 0-0:parent
895 // |-- 1
896 // |-- 2
897 // `-- 3
898 //
899 // Consider transplanting [1,2] under 0-0. This should be valid.
900 //
901 // root
902 // |-- 0
903 // | `-- 0-0
904 // | |-- 1
905 // | `-- 2
906 // `-- 3
907 //
908 // `range_parent` is an ancestor of `parent`, but `parent` is
909 // not the descendant of the range [1, 2].
910 // Detect such case here.
911 // In this example, `ancestor` now refers `root` and
912 // `prev_ancestor` refers `0`.
913 let mut current = Some(self.first);
914 while let Some(toplevel) = current {
915 if toplevel == prev_ancestor {
916 // `parent` is a descendant of `toplevel`.
917 return true;
918 }
919 if toplevel == self.last {
920 break;
921 }
922 current = hier
923 .neighbors(toplevel)
924 .expect("[consistency] nodes in the range must be alive")
925 .next_sibling();
926 }
927
928 prev_ancestor = ancestor;
929 }
930 }
931
932 false
933 }
934}