azul_core/
id_tree.rs

1use alloc::vec::Vec;
2use core::{
3    ops::{Index, IndexMut},
4    slice::Iter,
5};
6
7pub use self::node_id::NodeId;
8use crate::styled_dom::NodeHierarchyItem;
9pub type NodeDepths = Vec<(usize, NodeId)>;
10#[cfg(not(feature = "std"))]
11use alloc::string::ToString;
12
13// Since private fields are module-based, this prevents any module from accessing
14// `NodeId.index` directly. To get the correct node index is by using `NodeId::index()`,
15// which subtracts 1 from the ID (because of Option<NodeId> optimizations)
16mod node_id {
17
18    use alloc::vec::Vec;
19    use core::{
20        fmt,
21        num::NonZeroUsize,
22        ops::{Add, AddAssign},
23    };
24
25    /// A node identifier within a particular `Arena`.
26    #[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
27    pub struct NodeId {
28        index: NonZeroUsize,
29    }
30
31    impl NodeId {
32        pub const ZERO: NodeId = NodeId {
33            index: unsafe { NonZeroUsize::new_unchecked(1) },
34        };
35
36        /// **NOTE**: In debug mode, it panics on overflow, since having a
37        /// pointer that is zero is undefined behaviour (it would basically be
38        /// cast to a `None`), which is incorrect, so we rather panic on overflow
39        /// to prevent that.
40        ///
41        /// To trigger an overflow however, you'd need more that 4 billion DOM nodes -
42        /// it is more likely that you run out of RAM before you do that. The only thing
43        /// that could lead to an overflow would be a bug. Therefore, overflow-checking is
44        /// disabled in release mode.
45        #[inline(always)]
46        pub const fn new(value: usize) -> Self {
47            NodeId {
48                index: unsafe { NonZeroUsize::new_unchecked(value.saturating_add(1)) },
49            }
50        }
51
52        pub const fn from_usize(value: usize) -> Option<Self> {
53            match value {
54                0 => None,
55                i => Some(NodeId::new(i - 1)),
56            }
57        }
58
59        pub const fn into_usize(val: &Option<Self>) -> usize {
60            match val {
61                None => 0,
62                Some(s) => s.index.get(),
63            }
64        }
65
66        #[inline(always)]
67        pub fn index(&self) -> usize {
68            self.index.get() - 1
69        }
70
71        /// Return an iterator of references to this node’s children.
72        #[inline]
73        pub fn range(start: Self, end: Self) -> Vec<NodeId> {
74            (start.index()..end.index())
75                .map(|u| NodeId::new(u))
76                .collect()
77        }
78    }
79
80    impl Add<usize> for NodeId {
81        type Output = NodeId;
82        #[inline(always)]
83        fn add(self, other: usize) -> NodeId {
84            NodeId::new(self.index() + other)
85        }
86    }
87
88    impl AddAssign<usize> for NodeId {
89        #[inline(always)]
90        fn add_assign(&mut self, other: usize) {
91            *self = *self + other;
92        }
93    }
94
95    impl fmt::Display for NodeId {
96        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
97            write!(f, "{}", self.index())
98        }
99    }
100
101    impl fmt::Debug for NodeId {
102        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
103            write!(f, "NodeId({})", self.index())
104        }
105    }
106}
107
108/// Hierarchical information about a node (stores the indicies of the parent / child nodes).
109#[derive(Debug, Default, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
110pub struct Node {
111    pub parent: Option<NodeId>,
112    pub previous_sibling: Option<NodeId>,
113    pub next_sibling: Option<NodeId>,
114    pub last_child: Option<NodeId>,
115    // NOTE: first_child can be calculated on the fly:
116    //
117    //   - if last_child is None, first_child is None
118    //   - if last_child is Some, first_child is parent_index + 1
119    //
120    // This makes the "Node" struct take up 4 registers instead of 5
121    //
122    // pub first_child: Option<NodeId>,
123}
124
125// Node that initializes a Dom
126pub const ROOT_NODE: Node = Node {
127    parent: None,
128    previous_sibling: None,
129    next_sibling: None,
130    last_child: None,
131};
132
133impl Node {
134    pub const ROOT: Node = ROOT_NODE;
135
136    #[inline]
137    pub const fn has_parent(&self) -> bool {
138        self.parent.is_some()
139    }
140    #[inline]
141    pub const fn has_previous_sibling(&self) -> bool {
142        self.previous_sibling.is_some()
143    }
144    #[inline]
145    pub const fn has_next_sibling(&self) -> bool {
146        self.next_sibling.is_some()
147    }
148    #[inline]
149    pub const fn has_first_child(&self) -> bool {
150        self.last_child.is_some() /* last_child and first_child are always set together */
151    }
152    #[inline]
153    pub const fn has_last_child(&self) -> bool {
154        self.last_child.is_some()
155    }
156
157    #[inline]
158    pub(crate) fn get_first_child(&self, current_node_id: NodeId) -> Option<NodeId> {
159        // last_child and first_child are always set together
160        self.last_child.map(|_| current_node_id + 1)
161    }
162}
163
164/// The hierarchy of nodes is stored separately from the actual node content in order
165/// to save on memory, since the hierarchy can be re-used across several DOM trees even
166/// if the content changes.
167#[derive(Debug, Default, Clone, PartialEq, Hash, Eq, PartialOrd, Ord)]
168pub struct NodeHierarchy {
169    pub internal: Vec<Node>,
170}
171
172impl NodeHierarchy {
173    #[inline(always)]
174    pub const fn new(data: Vec<Node>) -> Self {
175        Self { internal: data }
176    }
177
178    #[inline(always)]
179    pub fn as_ref<'a>(&'a self) -> NodeHierarchyRef<'a> {
180        NodeHierarchyRef {
181            internal: &self.internal[..],
182        }
183    }
184
185    #[inline(always)]
186    pub fn as_ref_mut<'a>(&'a mut self) -> NodeHierarchyRefMut<'a> {
187        NodeHierarchyRefMut {
188            internal: &mut self.internal[..],
189        }
190    }
191}
192
193/// The hierarchy of nodes is stored separately from the actual node content in order
194/// to save on memory, since the hierarchy can be re-used across several DOM trees even
195/// if the content changes.
196#[derive(Debug, PartialEq, Hash, Eq)]
197pub struct NodeHierarchyRef<'a> {
198    pub internal: &'a [Node],
199}
200
201#[derive(Debug, PartialEq, Hash, Eq)]
202pub struct NodeHierarchyRefMut<'a> {
203    pub internal: &'a mut [Node],
204}
205
206impl<'a> NodeHierarchyRef<'a> {
207    #[inline(always)]
208    pub fn from_slice(data: &'a [Node]) -> NodeHierarchyRef<'a> {
209        NodeHierarchyRef { internal: data }
210    }
211
212    #[inline(always)]
213    pub fn len(&self) -> usize {
214        self.internal.len()
215    }
216
217    #[inline(always)]
218    pub fn get(&self, id: NodeId) -> Option<&Node> {
219        self.internal.get(id.index())
220    }
221
222    #[inline(always)]
223    pub fn linear_iter(&self) -> LinearIterator {
224        LinearIterator {
225            arena_len: self.len(),
226            position: 0,
227        }
228    }
229
230    /// Returns the `(depth, NodeId)` of all parent nodes (i.e. nodes that have a
231    /// `first_child`), in depth sorted order, (i.e. `NodeId(0)` with a depth of 0) is
232    /// the first element.
233    ///
234    /// Runtime: O(n) max
235    pub fn get_parents_sorted_by_depth(&self) -> NodeDepths {
236        let mut non_leaf_nodes = Vec::new();
237        let mut current_children = vec![(0, NodeId::new(0))];
238        let mut next_children = Vec::new();
239        let mut depth = 1_usize;
240
241        loop {
242            for id in &current_children {
243                for child_id in id.1.children(self).filter(|id| self[*id].has_first_child()) {
244                    next_children.push((depth, child_id));
245                }
246            }
247
248            non_leaf_nodes.extend(&mut current_children.drain(..));
249
250            if next_children.is_empty() {
251                break;
252            } else {
253                current_children.extend(&mut next_children.drain(..));
254                depth += 1;
255            }
256        }
257
258        non_leaf_nodes
259    }
260
261    /// Returns the number of all subtree items - runtime O(1)
262    #[inline]
263    pub fn subtree_len(&self, parent_id: NodeId) -> usize {
264        let self_item_index = parent_id.index();
265        let next_item_index = match self[parent_id].next_sibling {
266            None => self.len(),
267            Some(s) => s.index(),
268        };
269        next_item_index - self_item_index - 1
270    }
271
272    /// Returns the index in the parent node of a certain NodeId
273    /// (starts at 0, i.e. the first node has the index of 0).
274    #[inline]
275    pub fn get_index_in_parent(&self, node_id: NodeId) -> usize {
276        node_id.preceding_siblings(&self).count() - 1
277    }
278}
279
280impl<'a> NodeHierarchyRefMut<'a> {
281    pub fn from_slice(data: &'a mut [Node]) -> NodeHierarchyRefMut<'a> {
282        NodeHierarchyRefMut { internal: data }
283    }
284}
285
286#[derive(Debug, Clone, PartialEq, Hash, Eq, PartialOrd, Ord)]
287pub struct NodeDataContainer<T> {
288    pub internal: Vec<T>,
289}
290
291impl<T> From<Vec<T>> for NodeDataContainer<T> {
292    fn from(v: Vec<T>) -> NodeDataContainer<T> {
293        NodeDataContainer { internal: v }
294    }
295}
296
297#[derive(Debug, PartialEq, Hash, Eq, PartialOrd, Ord)]
298pub struct NodeDataContainerRef<'a, T> {
299    pub internal: &'a [T],
300}
301
302#[derive(Debug, PartialEq, Hash, Eq, PartialOrd, Ord)]
303pub struct NodeDataContainerRefMut<'a, T> {
304    pub internal: &'a mut [T],
305}
306
307impl<T> Default for NodeDataContainer<T> {
308    fn default() -> Self {
309        Self {
310            internal: Vec::new(),
311        }
312    }
313}
314
315impl<'a> Index<NodeId> for NodeHierarchyRef<'a> {
316    type Output = Node;
317
318    #[inline(always)]
319    fn index(&self, node_id: NodeId) -> &Node {
320        &self.internal[node_id.index()]
321    }
322}
323
324impl<'a> Index<NodeId> for NodeHierarchyRefMut<'a> {
325    type Output = Node;
326
327    #[inline(always)]
328    fn index(&self, node_id: NodeId) -> &Node {
329        &self.internal[node_id.index()]
330    }
331}
332
333impl<'a> IndexMut<NodeId> for NodeHierarchyRefMut<'a> {
334    #[inline(always)]
335    fn index_mut(&mut self, node_id: NodeId) -> &mut Node {
336        &mut self.internal[node_id.index()]
337    }
338}
339
340impl<T> NodeDataContainer<T> {
341    #[inline(always)]
342    pub const fn new(data: Vec<T>) -> Self {
343        Self { internal: data }
344    }
345
346    #[inline(always)]
347    pub fn is_empty(&self) -> bool {
348        self.internal.len() == 0
349    }
350
351    #[inline(always)]
352    pub fn as_ref<'a>(&'a self) -> NodeDataContainerRef<'a, T> {
353        NodeDataContainerRef {
354            internal: &self.internal[..],
355        }
356    }
357
358    #[inline(always)]
359    pub fn as_ref_mut<'a>(&'a mut self) -> NodeDataContainerRefMut<'a, T> {
360        NodeDataContainerRefMut {
361            internal: &mut self.internal[..],
362        }
363    }
364
365    #[inline(always)]
366    pub fn len(&self) -> usize {
367        self.internal.len()
368    }
369}
370
371impl<'a, T: 'a> NodeDataContainerRefMut<'a, T> {
372    #[inline(always)]
373    pub fn from_slice(data: &'a mut [T]) -> NodeDataContainerRefMut<'a, T> {
374        NodeDataContainerRefMut { internal: data }
375    }
376}
377
378impl<'a, T: 'a> NodeDataContainerRefMut<'a, T> {
379    #[inline(always)]
380    pub fn get_mut(&mut self, id: NodeId) -> Option<&mut T> {
381        self.internal.get_mut(id.index())
382    }
383    #[inline(always)]
384    pub fn get_mut_extended_lifetime(&'a mut self, id: NodeId) -> Option<&'a mut T> {
385        self.internal.get_mut(id.index())
386    }
387}
388
389impl<'a, T: Send + 'a> NodeDataContainerRefMut<'a, T> {
390    pub fn transform_multithread<U: Send, F: Send + Sync>(
391        &mut self,
392        closure: F,
393    ) -> NodeDataContainer<U>
394    where
395        F: Fn(&mut T, NodeId) -> U,
396    {
397        NodeDataContainer {
398            internal: self
399                .internal
400                .iter_mut()
401                .enumerate()
402                .map(|(node_id, node)| closure(node, NodeId::new(node_id)))
403                .collect::<Vec<U>>(),
404        }
405    }
406
407    pub fn transform_multithread_optional<U: Send, F: Send + Sync>(&mut self, closure: F) -> Vec<U>
408    where
409        F: Fn(&mut T, NodeId) -> Option<U>,
410    {
411        self.internal
412            .iter_mut()
413            .enumerate()
414            .filter_map(|(node_id, node)| closure(node, NodeId::new(node_id)))
415            .collect::<Vec<U>>()
416    }
417}
418
419impl<'a, T: Send + 'a> NodeDataContainerRef<'a, T> {
420    pub fn transform_nodeid<U: Send, F: Send + Sync>(&self, closure: F) -> NodeDataContainer<U>
421    where
422        F: Fn(NodeId) -> U,
423    {
424        let len = self.len();
425        NodeDataContainer {
426            internal: (0..len)
427                .into_iter()
428                .map(|node_id| closure(NodeId::new(node_id)))
429                .collect::<Vec<U>>(),
430        }
431    }
432
433    pub fn transform_nodeid_multithreaded_optional<U: Send, F: Send + Sync>(
434        &self,
435        closure: F,
436    ) -> NodeDataContainer<U>
437    where
438        F: Fn(NodeId) -> Option<U>,
439    {
440        let len = self.len();
441        NodeDataContainer {
442            internal: (0..len)
443                .into_iter()
444                .filter_map(|node_id| closure(NodeId::new(node_id)))
445                .collect::<Vec<U>>(),
446        }
447    }
448}
449
450impl<'a, T: 'a> NodeDataContainerRef<'a, T> {
451    #[inline(always)]
452    pub fn get_extended_lifetime(&self, id: NodeId) -> Option<&'a T> {
453        self.internal.get(id.index())
454    }
455
456    #[inline(always)]
457    pub fn from_slice(data: &'a [T]) -> NodeDataContainerRef<'a, T> {
458        NodeDataContainerRef { internal: data }
459    }
460
461    #[inline(always)]
462    pub fn len(&self) -> usize {
463        self.internal.len()
464    }
465
466    pub fn transform_singlethread<U, F>(&self, mut closure: F) -> NodeDataContainer<U>
467    where
468        F: FnMut(&T, NodeId) -> U,
469    {
470        // TODO if T: Send (which is usually the case), then we could use rayon here!
471        NodeDataContainer {
472            internal: self
473                .internal
474                .iter()
475                .enumerate()
476                .map(|(node_id, node)| closure(node, NodeId::new(node_id)))
477                .collect(),
478        }
479    }
480
481    #[inline(always)]
482    pub fn get(&self, id: NodeId) -> Option<&T> {
483        self.internal.get(id.index())
484    }
485
486    #[inline(always)]
487    pub fn iter(&self) -> Iter<T> {
488        self.internal.iter()
489    }
490
491    #[inline(always)]
492    pub fn linear_iter(&self) -> LinearIterator {
493        LinearIterator {
494            arena_len: self.len(),
495            position: 0,
496        }
497    }
498}
499
500impl<'a, T> Index<NodeId> for NodeDataContainerRef<'a, T> {
501    type Output = T;
502
503    #[inline(always)]
504    fn index(&self, node_id: NodeId) -> &T {
505        &self.internal[node_id.index()]
506    }
507}
508
509impl<'a, T> Index<NodeId> for NodeDataContainerRefMut<'a, T> {
510    type Output = T;
511
512    #[inline(always)]
513    fn index(&self, node_id: NodeId) -> &T {
514        &self.internal[node_id.index()]
515    }
516}
517
518impl<'a, T> IndexMut<NodeId> for NodeDataContainerRefMut<'a, T> {
519    #[inline(always)]
520    fn index_mut(&mut self, node_id: NodeId) -> &mut T {
521        &mut self.internal[node_id.index()]
522    }
523}
524
525impl NodeId {
526    /// Return an iterator of references to this node and its ancestors.
527    ///
528    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
529    #[inline]
530    pub const fn ancestors<'a>(self, node_hierarchy: &'a NodeHierarchyRef<'a>) -> Ancestors<'a> {
531        Ancestors {
532            node_hierarchy,
533            node: Some(self),
534        }
535    }
536
537    /// Return an iterator of references to this node and the siblings before it.
538    ///
539    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
540    #[inline]
541    pub const fn preceding_siblings<'a>(
542        self,
543        node_hierarchy: &'a NodeHierarchyRef<'a>,
544    ) -> PrecedingSiblings<'a> {
545        PrecedingSiblings {
546            node_hierarchy,
547            node: Some(self),
548        }
549    }
550
551    /// Return an iterator of references to this node and the siblings after it.
552    ///
553    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
554    #[inline]
555    pub const fn following_siblings<'a>(
556        self,
557        node_hierarchy: &'a NodeHierarchyRef<'a>,
558    ) -> FollowingSiblings<'a> {
559        FollowingSiblings {
560            node_hierarchy,
561            node: Some(self),
562        }
563    }
564
565    /// Return an iterator of references to this node’s children.
566    #[inline]
567    pub fn children<'a>(self, node_hierarchy: &'a NodeHierarchyRef<'a>) -> Children<'a> {
568        Children {
569            node_hierarchy,
570            node: node_hierarchy[self].get_first_child(self),
571        }
572    }
573
574    /// Return an iterator of references to this node’s children, in reverse order.
575    #[inline]
576    pub fn reverse_children<'a>(
577        self,
578        node_hierarchy: &'a NodeHierarchyRef<'a>,
579    ) -> ReverseChildren<'a> {
580        ReverseChildren {
581            node_hierarchy,
582            node: node_hierarchy[self].last_child,
583        }
584    }
585
586    /// Return an iterator of references to this node and its descendants, in tree order.
587    ///
588    /// Parent nodes appear before the descendants.
589    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
590    #[inline]
591    pub const fn descendants<'a>(
592        self,
593        node_hierarchy: &'a NodeHierarchyRef<'a>,
594    ) -> Descendants<'a> {
595        Descendants(self.traverse(node_hierarchy))
596    }
597
598    /// Return an iterator of references to this node and its descendants, in tree order.
599    #[inline]
600    pub const fn traverse<'a>(self, node_hierarchy: &'a NodeHierarchyRef<'a>) -> Traverse<'a> {
601        Traverse {
602            node_hierarchy,
603            root: self,
604            next: Some(NodeEdge::Start(self)),
605        }
606    }
607
608    /// Return an iterator of references to this node and its descendants, in tree order.
609    #[inline]
610    pub const fn reverse_traverse<'a>(
611        self,
612        node_hierarchy: &'a NodeHierarchyRef<'a>,
613    ) -> ReverseTraverse<'a> {
614        ReverseTraverse {
615            node_hierarchy,
616            root: self,
617            next: Some(NodeEdge::End(self)),
618        }
619    }
620}
621
622macro_rules! impl_node_iterator {
623    ($name:ident, $next:expr) => {
624        impl<'a> Iterator for $name<'a> {
625            type Item = NodeId;
626
627            fn next(&mut self) -> Option<NodeId> {
628                match self.node.take() {
629                    Some(node) => {
630                        self.node = $next(&self.node_hierarchy[node]);
631                        Some(node)
632                    }
633                    None => None,
634                }
635            }
636        }
637    };
638}
639
640/// An linear iterator, does not respect the DOM in any way,
641/// it just iterates over the nodes like a Vec
642#[derive(Debug, Copy, Clone)]
643pub struct LinearIterator {
644    arena_len: usize,
645    position: usize,
646}
647
648impl Iterator for LinearIterator {
649    type Item = NodeId;
650
651    fn next(&mut self) -> Option<NodeId> {
652        if self.arena_len < 1 || self.position > (self.arena_len - 1) {
653            None
654        } else {
655            let new_id = Some(NodeId::new(self.position));
656            self.position += 1;
657            new_id
658        }
659    }
660}
661
662/// An iterator of references to the ancestors a given node.
663pub struct Ancestors<'a> {
664    node_hierarchy: &'a NodeHierarchyRef<'a>,
665    node: Option<NodeId>,
666}
667
668impl_node_iterator!(Ancestors, |node: &Node| node.parent);
669
670/// An iterator of references to the siblings before a given node.
671pub struct PrecedingSiblings<'a> {
672    node_hierarchy: &'a NodeHierarchyRef<'a>,
673    node: Option<NodeId>,
674}
675
676impl_node_iterator!(PrecedingSiblings, |node: &Node| node.previous_sibling);
677
678/// An iterator of references to the siblings after a given node.
679pub struct FollowingSiblings<'a> {
680    node_hierarchy: &'a NodeHierarchyRef<'a>,
681    node: Option<NodeId>,
682}
683
684impl_node_iterator!(FollowingSiblings, |node: &Node| node.next_sibling);
685
686/// Special iterator for using NodeDataContainerRef<AzNode> instead of NodeHierarchy
687pub struct AzChildren<'a> {
688    node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
689    node: Option<NodeId>,
690}
691
692impl<'a> Iterator for AzChildren<'a> {
693    type Item = NodeId;
694
695    fn next(&mut self) -> Option<NodeId> {
696        match self.node.take() {
697            Some(node) => {
698                self.node = self.node_hierarchy[node].next_sibling_id();
699                Some(node)
700            }
701            None => None,
702        }
703    }
704}
705
706/// Special iterator for using NodeDataContainerRef<AzNode> instead of NodeHierarchy
707pub struct AzReverseChildren<'a> {
708    node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
709    node: Option<NodeId>,
710}
711
712impl<'a> Iterator for AzReverseChildren<'a> {
713    type Item = NodeId;
714
715    fn next(&mut self) -> Option<NodeId> {
716        match self.node.take() {
717            Some(node) => {
718                self.node = self.node_hierarchy[node].previous_sibling_id();
719                Some(node)
720            }
721            None => None,
722        }
723    }
724}
725
726impl NodeId {
727    // Traverse up through the hierarchy a node matching the predicate is found
728    //
729    // Necessary to resolve the last positioned (= relative)
730    // element of an absolute ndoe
731    pub fn get_nearest_matching_parent<'a, F>(
732        self,
733        node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
734        predicate: F,
735    ) -> Option<NodeId>
736    where
737        F: Fn(NodeId) -> bool,
738    {
739        let mut current_node = node_hierarchy[self].parent_id()?;
740        loop {
741            match predicate(current_node) {
742                true => {
743                    return Some(current_node);
744                }
745                false => {
746                    current_node = node_hierarchy[current_node].parent_id()?;
747                }
748            }
749        }
750    }
751
752    /// Return the children of this node (necessary for parallel iteration over children)
753    #[inline]
754    pub fn az_children_collect<'a>(
755        self,
756        node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
757    ) -> Vec<NodeId> {
758        self.az_children(node_hierarchy).collect()
759    }
760
761    /// Return an iterator of references to this node’s children.
762    #[inline]
763    pub fn az_children<'a>(
764        self,
765        node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
766    ) -> AzChildren<'a> {
767        AzChildren {
768            node_hierarchy,
769            node: node_hierarchy[self].first_child_id(self),
770        }
771    }
772
773    /// Return an iterator of references to this node’s children.
774    #[inline]
775    pub fn az_reverse_children<'a>(
776        self,
777        node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
778    ) -> AzReverseChildren<'a> {
779        AzReverseChildren {
780            node_hierarchy,
781            node: node_hierarchy[self].last_child_id(),
782        }
783    }
784}
785
786/// An iterator of references to the children of a given node.
787pub struct Children<'a> {
788    node_hierarchy: &'a NodeHierarchyRef<'a>,
789    node: Option<NodeId>,
790}
791
792impl_node_iterator!(Children, |node: &Node| node.next_sibling);
793
794/// An iterator of references to the children of a given node, in reverse order.
795pub struct ReverseChildren<'a> {
796    node_hierarchy: &'a NodeHierarchyRef<'a>,
797    node: Option<NodeId>,
798}
799
800impl_node_iterator!(ReverseChildren, |node: &Node| node.previous_sibling);
801
802/// An iterator of references to a given node and its descendants, in tree order.
803pub struct Descendants<'a>(Traverse<'a>);
804
805impl<'a> Iterator for Descendants<'a> {
806    type Item = NodeId;
807
808    fn next(&mut self) -> Option<NodeId> {
809        loop {
810            match self.0.next() {
811                Some(NodeEdge::Start(node)) => return Some(node),
812                Some(NodeEdge::End(_)) => {}
813                None => return None,
814            }
815        }
816    }
817}
818
819#[derive(Debug, Clone)]
820pub enum NodeEdge<T> {
821    /// Indicates that start of a node that has children.
822    /// Yielded by `Traverse::next` before the node’s descendants.
823    /// In HTML or XML, this corresponds to an opening tag like `<div>`
824    Start(T),
825
826    /// Indicates that end of a node that has children.
827    /// Yielded by `Traverse::next` after the node’s descendants.
828    /// In HTML or XML, this corresponds to a closing tag like `</div>`
829    End(T),
830}
831
832impl<T> NodeEdge<T> {
833    pub fn inner_value(self) -> T {
834        use self::NodeEdge::*;
835        match self {
836            Start(t) => t,
837            End(t) => t,
838        }
839    }
840}
841
842/// An iterator of references to a given node and its descendants, in tree order.
843pub struct Traverse<'a> {
844    node_hierarchy: &'a NodeHierarchyRef<'a>,
845    root: NodeId,
846    next: Option<NodeEdge<NodeId>>,
847}
848
849impl<'a> Iterator for Traverse<'a> {
850    type Item = NodeEdge<NodeId>;
851
852    fn next(&mut self) -> Option<NodeEdge<NodeId>> {
853        match self.next.take() {
854            Some(item) => {
855                self.next = match item {
856                    NodeEdge::Start(node) => {
857                        match self.node_hierarchy[node].get_first_child(node) {
858                            Some(first_child) => Some(NodeEdge::Start(first_child)),
859                            None => Some(NodeEdge::End(node.clone())),
860                        }
861                    }
862                    NodeEdge::End(node) => {
863                        if node == self.root {
864                            None
865                        } else {
866                            match self.node_hierarchy[node].next_sibling {
867                                Some(next_sibling) => Some(NodeEdge::Start(next_sibling)),
868                                None => match self.node_hierarchy[node].parent {
869                                    Some(parent) => Some(NodeEdge::End(parent)),
870
871                                    // `node.parent()` here can only be `None`
872                                    // if the tree has been modified during iteration,
873                                    // but silently stopping iteration
874                                    // seems a more sensible behavior than panicking.
875                                    None => None,
876                                },
877                            }
878                        }
879                    }
880                };
881                Some(item)
882            }
883            None => None,
884        }
885    }
886}
887
888/// An iterator of references to a given node and its descendants, in reverse tree order.
889pub struct ReverseTraverse<'a> {
890    node_hierarchy: &'a NodeHierarchyRef<'a>,
891    root: NodeId,
892    next: Option<NodeEdge<NodeId>>,
893}
894
895impl<'a> Iterator for ReverseTraverse<'a> {
896    type Item = NodeEdge<NodeId>;
897
898    fn next(&mut self) -> Option<NodeEdge<NodeId>> {
899        match self.next.take() {
900            Some(item) => {
901                self.next = match item {
902                    NodeEdge::End(node) => match self.node_hierarchy[node].last_child {
903                        Some(last_child) => Some(NodeEdge::End(last_child)),
904                        None => Some(NodeEdge::Start(node.clone())),
905                    },
906                    NodeEdge::Start(node) => {
907                        if node == self.root {
908                            None
909                        } else {
910                            match self.node_hierarchy[node].previous_sibling {
911                                Some(previous_sibling) => Some(NodeEdge::End(previous_sibling)),
912                                None => match self.node_hierarchy[node].parent {
913                                    Some(parent) => Some(NodeEdge::Start(parent)),
914
915                                    // `node.parent()` here can only be `None`
916                                    // if the tree has been modified during iteration,
917                                    // but silently stopping iteration
918                                    // seems a more sensible behavior than panicking.
919                                    None => None,
920                                },
921                            }
922                        }
923                    }
924                };
925                Some(item)
926            }
927            None => None,
928        }
929    }
930}
azul_core/id_tree.rs

azul_core/
id_tree.rs
