azul_core/
id_tree.rs

1use std::{
2    ops::{Index, IndexMut},
3    slice::{Iter, IterMut},
4};
5
6pub use self::node_id::NodeId;
7pub type NodeDepths = Vec<(usize, NodeId)>;
8
9// Since private fields are module-based, this prevents any module from accessing
10// `NodeId.index` directly. To get the correct node index is by using `NodeId::index()`,
11// which subtracts 1 from the ID (because of Option<NodeId> optimizations)
12mod node_id {
13
14    use std::{
15        fmt,
16        num::NonZeroUsize,
17        ops::{Add, AddAssign},
18    };
19
20    /// A node identifier within a particular `Arena`.
21    #[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
22    pub struct NodeId {
23        index: NonZeroUsize,
24    }
25
26    impl NodeId {
27
28        pub const ZERO: NodeId = NodeId { index: unsafe { NonZeroUsize::new_unchecked(1) } };
29
30        /// **NOTE**: In debug mode, it panics on overflow, since having a
31        /// pointer that is zero is undefined behaviour (it would basically be
32        /// cast to a `None`), which is incorrect, so we rather panic on overflow
33        /// to prevent that.
34        ///
35        /// To trigger an overflow however, you'd need more that 4 billion DOM nodes -
36        /// it is more likely that you run out of RAM before you do that. The only thing
37        /// that could lead to an overflow would be a bug. Therefore, overflow-checking is
38        /// disabled in release mode.
39        #[inline(always)]
40        pub fn new(value: usize) -> Self {
41            NodeId { index: unsafe { NonZeroUsize::new_unchecked(value + 1) } }
42        }
43
44        #[inline(always)]
45        pub fn index(&self) -> usize {
46            self.index.get() - 1
47        }
48
49        /// Return an iterator of references to this node’s children.
50        #[inline]
51        pub fn range(start: Self, end: Self) -> Vec<NodeId> {
52            (start.index()..end.index()).map(NodeId::new).collect()
53        }
54    }
55
56    impl Add<usize> for NodeId {
57        type Output = NodeId;
58        #[inline(always)]
59        fn add(self, other: usize) -> NodeId {
60            NodeId::new(self.index() + other)
61        }
62    }
63
64    impl AddAssign<usize> for NodeId {
65        #[inline(always)]
66        fn add_assign(&mut self, other: usize) {
67            *self = *self + other;
68        }
69    }
70
71    impl fmt::Display for NodeId {
72        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
73            write!(f, "{}", self.index())
74        }
75    }
76
77    impl fmt::Debug for NodeId {
78        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
79            write!(f, "NodeId({})", self.index())
80        }
81    }
82}
83
84/// Hierarchical information about a node (stores the indicies of the parent / child nodes).
85#[derive(Debug, Default, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
86pub struct Node {
87    pub parent: Option<NodeId>,
88    pub previous_sibling: Option<NodeId>,
89    pub next_sibling: Option<NodeId>,
90    pub first_child: Option<NodeId>,
91    pub last_child: Option<NodeId>,
92}
93
94// Node that initializes a Dom
95pub const ROOT_NODE: Node = Node {
96    parent: None,
97    previous_sibling: None,
98    next_sibling: None,
99    first_child: None,
100    last_child: None,
101};
102
103impl Node {
104    pub const ROOT: Node = ROOT_NODE;
105    #[inline]
106    pub fn has_parent(&self) -> bool { self.parent.is_some() }
107    #[inline]
108    pub fn has_previous_sibling(&self) -> bool { self.previous_sibling.is_some() }
109    #[inline]
110    pub fn has_next_sibling(&self) -> bool { self.next_sibling.is_some() }
111    #[inline]
112    pub fn has_first_child(&self) -> bool { self.first_child.is_some() }
113    #[inline]
114    pub fn has_last_child(&self) -> bool { self.last_child.is_some() }
115}
116
117#[derive(Debug, Default, Clone, PartialEq, Hash, Eq)]
118pub struct Arena<T> {
119    pub node_hierarchy: NodeHierarchy,
120    pub node_data: NodeDataContainer<T>,
121}
122
123/// The hierarchy of nodes is stored separately from the actual node content in order
124/// to save on memory, since the hierarchy can be re-used across several DOM trees even
125/// if the content changes.
126#[derive(Debug, Default, Clone, PartialEq, Hash, Eq)]
127pub struct NodeHierarchy {
128    pub internal: Vec<Node>,
129}
130
131impl NodeHierarchy {
132
133    #[inline]
134    pub const fn new(data: Vec<Node>) -> Self {
135        Self {
136            internal: data,
137        }
138    }
139
140    #[inline]
141    pub fn len(&self) -> usize {
142        self.internal.len()
143    }
144
145    #[inline]
146    pub fn get(&self, id: NodeId) -> Option<&Node> {
147        self.internal.get(id.index())
148    }
149
150    #[inline]
151    pub fn linear_iter(&self) -> LinearIterator {
152        LinearIterator {
153            arena_len: self.len(),
154            position: 0,
155        }
156    }
157
158    /// Returns the `(depth, NodeId)` of all parent nodes (i.e. nodes that have a
159    /// `first_child`), in depth sorted order, (i.e. `NodeId(0)` with a depth of 0) is
160    /// the first element.
161    ///
162    /// Runtime: O(n) max
163    pub fn get_parents_sorted_by_depth(&self) -> NodeDepths {
164
165        let mut non_leaf_nodes = Vec::new();
166        let mut current_children = vec![(0, NodeId::new(0))];
167        let mut next_children = Vec::new();
168        let mut depth = 1;
169
170        loop {
171
172            for id in &current_children {
173                for child_id in id.1.children(self).filter(|id| self[*id].first_child.is_some()) {
174                    next_children.push((depth, child_id));
175                }
176            }
177
178            non_leaf_nodes.extend(&mut current_children.drain(..));
179
180            if next_children.is_empty() {
181                break;
182            } else {
183                current_children.extend(&mut next_children.drain(..));
184                depth += 1;
185            }
186        }
187
188        non_leaf_nodes
189    }
190
191    /// Returns the number of all subtree items - runtime O(1)
192    #[inline]
193    pub fn subtree_len(&self, parent_id: NodeId) -> usize {
194        let self_item_index = parent_id.index();
195        let next_item_index = match self[parent_id].next_sibling {
196            None => self.len(),
197            Some(s) => s.index(),
198        };
199        next_item_index - self_item_index - 1
200    }
201
202    /// Returns the index in the parent node of a certain NodeId
203    /// (starts at 0, i.e. the first node has the index of 0).
204    #[inline]
205    pub fn get_index_in_parent(&self, node_id: NodeId) -> usize {
206        node_id.preceding_siblings(&self).count() - 1
207    }
208}
209
210#[derive(Debug, Clone, PartialEq, Hash, Eq, PartialOrd, Ord)]
211pub struct NodeDataContainer<T> {
212    pub internal: Vec<T>,
213}
214
215impl<T> Default for NodeDataContainer<T> {
216    fn default() -> Self {
217        Self { internal: Vec::new() }
218    }
219}
220
221impl Index<NodeId> for NodeHierarchy {
222    type Output = Node;
223
224    #[inline]
225    fn index(&self, node_id: NodeId) -> &Node {
226        unsafe { self.internal.get_unchecked(node_id.index()) }
227    }
228}
229
230impl IndexMut<NodeId> for NodeHierarchy {
231
232    #[inline]
233    fn index_mut(&mut self, node_id: NodeId) -> &mut Node {
234        unsafe { self.internal.get_unchecked_mut(node_id.index()) }
235    }
236}
237
238impl<T> NodeDataContainer<T> {
239
240    #[inline]
241    pub const fn new(data: Vec<T>) -> Self {
242        Self { internal: data }
243    }
244
245    pub fn len(&self) -> usize { self.internal.len() }
246
247    pub fn transform<U, F>(&self, mut closure: F) -> NodeDataContainer<U> where F: FnMut(&T, NodeId) -> U {
248        // TODO if T: Send (which is usually the case), then we could use rayon here!
249        NodeDataContainer {
250            internal: self.internal.iter().enumerate().map(|(node_id, node)| closure(node, NodeId::new(node_id))).collect(),
251        }
252    }
253
254    pub fn get(&self, id: NodeId) -> Option<&T> {
255        self.internal.get(id.index())
256    }
257
258    pub fn iter(&self) -> Iter<T> {
259        self.internal.iter()
260    }
261
262    pub fn iter_mut(&mut self) -> IterMut<T> {
263        self.internal.iter_mut()
264    }
265
266    pub fn linear_iter(&self) -> LinearIterator {
267        LinearIterator {
268            arena_len: self.len(),
269            position: 0,
270        }
271    }
272}
273
274impl<T> Index<NodeId> for NodeDataContainer<T> {
275    type Output = T;
276
277    #[inline]
278    fn index(&self, node_id: NodeId) -> &T {
279        unsafe { self.internal.get_unchecked(node_id.index()) }
280    }
281}
282
283impl<T> IndexMut<NodeId> for NodeDataContainer<T> {
284
285    #[inline]
286    fn index_mut(&mut self, node_id: NodeId) -> &mut T {
287        unsafe { self.internal.get_unchecked_mut(node_id.index()) }
288    }
289}
290
291impl<T> Arena<T> {
292
293    #[inline]
294    pub fn new() -> Arena<T> {
295        // NOTE: This is a separate function, since Vec::new() is a const fn (so this function doesn't allocate)
296        Arena {
297            node_hierarchy: NodeHierarchy { internal: Vec::new() },
298            node_data: NodeDataContainer { internal: Vec::<T>::new() },
299        }
300    }
301
302    #[inline]
303    pub fn with_capacity(cap: usize) -> Arena<T> {
304        Arena {
305            node_hierarchy: NodeHierarchy { internal: Vec::with_capacity(cap) },
306            node_data: NodeDataContainer { internal: Vec::<T>::with_capacity(cap) },
307        }
308    }
309
310    /// Create a new node from its associated data.
311    #[inline]
312    pub fn new_node(&mut self, data: T) -> NodeId {
313        let next_index = self.node_hierarchy.len();
314        self.node_hierarchy.internal.push(Node {
315            parent: None,
316            first_child: None,
317            last_child: None,
318            previous_sibling: None,
319            next_sibling: None,
320        });
321        self.node_data.internal.push(data);
322        NodeId::new(next_index)
323    }
324
325    // Returns how many nodes there are in the arena
326    #[inline]
327    pub fn len(&self) -> usize {
328        self.node_hierarchy.len()
329    }
330
331    #[inline]
332    pub fn is_empty(&self) -> bool {
333        self.len() == 0
334    }
335
336    /// Return an iterator over the indices in the internal arenas Vec<T>
337    #[inline]
338    pub fn linear_iter(&self) -> LinearIterator {
339        LinearIterator {
340            arena_len: self.node_hierarchy.len(),
341            position: 0,
342        }
343    }
344
345    /// Appends another arena to the end of the current arena
346    /// (by simply appending the two Vec of nodes)
347    /// Can potentially mess up internal IDs, only use this if you
348    /// know what you're doing
349    #[inline]
350    pub fn append_arena(&mut self, other: &mut Arena<T>) {
351        self.node_hierarchy.internal.append(&mut other.node_hierarchy.internal);
352        self.node_data.internal.append(&mut other.node_data.internal);
353    }
354
355    /// Transform keeps the relative order of parents / children
356    /// but transforms an Arena<T> into an Arena<U>, by running the closure on each of the
357    /// items. The `NodeId` for the root is then valid for the newly created `Arena<U>`, too.
358    #[inline]
359    pub fn transform<U, F>(&self, closure: F) -> Arena<U> where F: Fn(&T, NodeId) -> U {
360        // TODO if T: Send (which is usually the case), then we could use rayon here!
361        Arena {
362            node_hierarchy: self.node_hierarchy.clone(),
363            node_data: self.node_data.transform(closure),
364        }
365    }
366}
367
368impl NodeId {
369
370    /// Return an iterator of references to this node and its ancestors.
371    ///
372    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
373    #[inline]
374    pub const fn ancestors(self, node_hierarchy: &NodeHierarchy) -> Ancestors {
375        Ancestors {
376            node_hierarchy,
377            node: Some(self),
378        }
379    }
380
381    /// Return an iterator of references to this node and the siblings before it.
382    ///
383    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
384    #[inline]
385    pub const fn preceding_siblings(self, node_hierarchy: &NodeHierarchy) -> PrecedingSiblings {
386        PrecedingSiblings {
387            node_hierarchy,
388            node: Some(self),
389        }
390    }
391
392    /// Return an iterator of references to this node and the siblings after it.
393    ///
394    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
395    #[inline]
396    pub const fn following_siblings(self, node_hierarchy: &NodeHierarchy) -> FollowingSiblings {
397        FollowingSiblings {
398            node_hierarchy,
399            node: Some(self),
400        }
401    }
402
403    /// Return an iterator of references to this node’s children.
404    #[inline]
405    pub fn children(self, node_hierarchy: &NodeHierarchy) -> Children {
406        Children {
407            node_hierarchy,
408            node: node_hierarchy[self].first_child,
409        }
410    }
411
412    /// Return an iterator of references to this node’s children, in reverse order.
413    #[inline]
414    pub fn reverse_children(self, node_hierarchy: &NodeHierarchy) -> ReverseChildren {
415        ReverseChildren {
416            node_hierarchy,
417            node: node_hierarchy[self].last_child,
418        }
419    }
420
421    /// Return an iterator of references to this node and its descendants, in tree order.
422    ///
423    /// Parent nodes appear before the descendants.
424    /// Call `.next().unwrap()` once on the iterator to skip the node itself.
425    #[inline]
426    pub const fn descendants(self, node_hierarchy: &NodeHierarchy) -> Descendants {
427        Descendants(self.traverse(node_hierarchy))
428    }
429
430    /// Return an iterator of references to this node and its descendants, in tree order.
431    #[inline]
432    pub const fn traverse(self, node_hierarchy: &NodeHierarchy) -> Traverse {
433        Traverse {
434            node_hierarchy,
435            root: self,
436            next: Some(NodeEdge::Start(self)),
437        }
438    }
439
440    /// Return an iterator of references to this node and its descendants, in tree order.
441    #[inline]
442    pub const fn reverse_traverse(self, node_hierarchy: &NodeHierarchy) -> ReverseTraverse {
443        ReverseTraverse {
444            node_hierarchy,
445            root: self,
446            next: Some(NodeEdge::End(self)),
447        }
448    }
449}
450
451
452macro_rules! impl_node_iterator {
453    ($name: ident, $next: expr) => {
454        impl<'a> Iterator for $name<'a> {
455            type Item = NodeId;
456
457            fn next(&mut self) -> Option<NodeId> {
458                match self.node.take() {
459                    Some(node) => {
460                        self.node = $next(&self.node_hierarchy[node]);
461                        Some(node)
462                    }
463                    None => None
464                }
465            }
466        }
467    }
468}
469
470/// An linear iterator, does not respect the DOM in any way,
471/// it just iterates over the nodes like a Vec
472#[derive(Debug, Copy, Clone)]
473pub struct LinearIterator {
474    arena_len: usize,
475    position: usize,
476}
477
478impl Iterator for LinearIterator {
479    type Item = NodeId;
480
481    fn next(&mut self) -> Option<NodeId> {
482        if self.arena_len < 1 || self.position > (self.arena_len - 1){
483            None
484        } else {
485            let new_id = Some(NodeId::new(self.position));
486            self.position += 1;
487            new_id
488        }
489    }
490}
491
492/// An iterator of references to the ancestors a given node.
493pub struct Ancestors<'a> {
494    node_hierarchy: &'a NodeHierarchy,
495    node: Option<NodeId>,
496}
497
498impl_node_iterator!(Ancestors, |node: &Node| node.parent);
499
500/// An iterator of references to the siblings before a given node.
501pub struct PrecedingSiblings<'a> {
502    node_hierarchy: &'a NodeHierarchy,
503    node: Option<NodeId>,
504}
505
506impl_node_iterator!(PrecedingSiblings, |node: &Node| node.previous_sibling);
507
508/// An iterator of references to the siblings after a given node.
509pub struct FollowingSiblings<'a> {
510    node_hierarchy: &'a NodeHierarchy,
511    node: Option<NodeId>,
512}
513
514impl_node_iterator!(FollowingSiblings, |node: &Node| node.next_sibling);
515
516/// An iterator of references to the children of a given node.
517pub struct Children<'a> {
518    node_hierarchy: &'a NodeHierarchy,
519    node: Option<NodeId>,
520}
521
522impl_node_iterator!(Children, |node: &Node| node.next_sibling);
523
524/// An iterator of references to the children of a given node, in reverse order.
525pub struct ReverseChildren<'a> {
526    node_hierarchy: &'a NodeHierarchy,
527    node: Option<NodeId>,
528}
529
530impl_node_iterator!(ReverseChildren, |node: &Node| node.previous_sibling);
531
532/// An iterator of references to a given node and its descendants, in tree order.
533pub struct Descendants<'a>(Traverse<'a>);
534
535impl<'a> Iterator for Descendants<'a> {
536    type Item = NodeId;
537
538    fn next(&mut self) -> Option<NodeId> {
539        loop {
540            match self.0.next() {
541                Some(NodeEdge::Start(node)) => return Some(node),
542                Some(NodeEdge::End(_)) => {}
543                None => return None
544            }
545        }
546    }
547}
548
549#[derive(Debug, Clone)]
550pub enum NodeEdge<T> {
551    /// Indicates that start of a node that has children.
552    /// Yielded by `Traverse::next` before the node’s descendants.
553    /// In HTML or XML, this corresponds to an opening tag like `<div>`
554    Start(T),
555
556    /// Indicates that end of a node that has children.
557    /// Yielded by `Traverse::next` after the node’s descendants.
558    /// In HTML or XML, this corresponds to a closing tag like `</div>`
559    End(T),
560}
561
562impl<T> NodeEdge<T> {
563    pub fn inner_value(self) -> T {
564        use self::NodeEdge::*;
565        match self {
566            Start(t) => t,
567            End(t) => t,
568        }
569    }
570}
571
572/// An iterator of references to a given node and its descendants, in tree order.
573pub struct Traverse<'a> {
574    node_hierarchy: &'a NodeHierarchy,
575    root: NodeId,
576    next: Option<NodeEdge<NodeId>>,
577}
578
579impl<'a> Iterator for Traverse<'a> {
580    type Item = NodeEdge<NodeId>;
581
582    fn next(&mut self) -> Option<NodeEdge<NodeId>> {
583        match self.next.take() {
584            Some(item) => {
585                self.next = match item {
586                    NodeEdge::Start(node) => {
587                        match self.node_hierarchy[node].first_child {
588                            Some(first_child) => Some(NodeEdge::Start(first_child)),
589                            None => Some(NodeEdge::End(node.clone()))
590                        }
591                    }
592                    NodeEdge::End(node) => {
593                        if node == self.root {
594                            None
595                        } else {
596                            match self.node_hierarchy[node].next_sibling {
597                                Some(next_sibling) => Some(NodeEdge::Start(next_sibling)),
598                                None => match self.node_hierarchy[node].parent {
599                                    Some(parent) => Some(NodeEdge::End(parent)),
600
601                                    // `node.parent()` here can only be `None`
602                                    // if the tree has been modified during iteration,
603                                    // but silently stopping iteration
604                                    // seems a more sensible behavior than panicking.
605                                    None => None
606                                }
607                            }
608                        }
609                    }
610                };
611                Some(item)
612            }
613            None => None
614        }
615    }
616}
617
618/// An iterator of references to a given node and its descendants, in reverse tree order.
619pub struct ReverseTraverse<'a> {
620    node_hierarchy: &'a NodeHierarchy,
621    root: NodeId,
622    next: Option<NodeEdge<NodeId>>,
623}
624
625impl<'a> Iterator for ReverseTraverse<'a> {
626    type Item = NodeEdge<NodeId>;
627
628    fn next(&mut self) -> Option<NodeEdge<NodeId>> {
629        match self.next.take() {
630            Some(item) => {
631                self.next = match item {
632                    NodeEdge::End(node) => {
633                        match self.node_hierarchy[node].last_child {
634                            Some(last_child) => Some(NodeEdge::End(last_child)),
635                            None => Some(NodeEdge::Start(node.clone()))
636                        }
637                    }
638                    NodeEdge::Start(node) => {
639                        if node == self.root {
640                            None
641                        } else {
642                            match self.node_hierarchy[node].previous_sibling {
643                                Some(previous_sibling) => Some(NodeEdge::End(previous_sibling)),
644                                None => match self.node_hierarchy[node].parent {
645                                    Some(parent) => Some(NodeEdge::Start(parent)),
646
647                                    // `node.parent()` here can only be `None`
648                                    // if the tree has been modified during iteration,
649                                    // but silently stopping iteration
650                                    // seems a more sensible behavior than panicking.
651                                    None => None
652                                }
653                            }
654                        }
655                    }
656                };
657                Some(item)
658            }
659            None => None
660        }
661    }
662}
azul_core/id_tree.rs

azul_core/
id_tree.rs
