space_partitioning/quadtree/
node.rs

1use crate::quadtree::free_list;
2use std::fmt::{Debug, Formatter};
3
4pub type NodeElementCountType = u32;
5
6/// This value encodes that a node is a branch, i.e., not a leaf.
7const NODE_IS_BRANCH: u32 = NodeElementCountType::MAX;
8
9/// Represents a node in the quadtree.
10#[derive(Copy, Clone)]
11pub struct Node {
12    /// Contains
13    /// - the index of the first child if this node is a branch or
14    /// - the index of the first element if this node is a leaf or
15    /// - `free_list::SENTINEL` if neither of which exists.
16    ///
17    /// If this node is the first child node and pointed to by
18    /// the free node pointer, all subsequent nodes of the same parent (i.e., the next three nodes).
19    pub first_child_or_element: free_list::IndexType,
20    /// Stores the number of elements in the leaf or `NODE_INDEX_IS_BRANCH if it this node is
21    /// a branch (i.e., not a leaf).
22    pub element_count: NodeElementCountType,
23}
24
25impl Debug for Node {
26    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
27        match (self.element_count, self.first_child_or_element) {
28            (NODE_IS_BRANCH, free_list::SENTINEL) => {
29                write!(f, "Branch, no child nodes")
30            }
31            (NODE_IS_BRANCH, child_index) => write!(
32                f,
33                "Branch, child nodes at {}+{}..={}",
34                child_index,
35                child_index + 1,
36                child_index + 4
37            ),
38            (0, free_list::SENTINEL) => write!(f, "Leaf, no elements"),
39            (count, free_list::SENTINEL) => {
40                panic!("Got {} child elements but no data pointer", count)
41            }
42            (count, element_index) => write!(
43                f,
44                "Leaf, elements {}..={}",
45                element_index,
46                element_index + count
47            ),
48        }
49    }
50}
51
52impl Default for Node {
53    #[inline]
54    fn default() -> Self {
55        let node = Self {
56            // By setting the first element index to the sentinel value,
57            // we encode that this node has no data.
58            first_child_or_element: free_list::SENTINEL,
59            // By setting the element count to zero, this is now a leaf with 0 elements.
60            element_count: 0,
61        };
62        // For brevity:
63        debug_assert!(node.is_leaf() && node.is_empty());
64        node
65    }
66}
67
68impl Node {
69    /// Returns whether the node stores elements.
70    #[inline]
71    pub fn is_empty(&self) -> bool {
72        self.element_count == 0
73    }
74
75    /// Determines whether this node is a branch.
76    ///
77    /// Leaf nodes do not contain data, and their [`first_child_or_element`]
78    /// field points to the index of the child node.
79    #[inline]
80    pub fn is_branch(&self) -> bool {
81        self.element_count == NODE_IS_BRANCH
82    }
83
84    /// Determines whether this node is a leaf (i.e., not a branch).
85    ///
86    /// Leaf nodes may contain data, and their [`first_child_or_element`]
87    /// field points to the index of the first element.
88    #[inline]
89    pub fn is_leaf(&self) -> bool {
90        // If we have a nonzero element count, the [`first_child_or_element`] must be a valid index.
91        // If we have a zero element count, the [`first_child_or_element`] must be the sentinel value.
92        debug_assert!(self.element_count > 0 || self.first_child_or_element == free_list::SENTINEL);
93
94        !self.is_branch()
95    }
96
97    /// If the node is branch, gets the index of the first child node.
98    #[inline]
99    pub fn get_first_child_node_index(&self) -> free_list::IndexType {
100        debug_assert!(self.is_branch());
101        self.first_child_or_element
102    }
103
104    /// If the node is leaf, gets the index of the element node.
105    #[inline]
106    pub fn get_first_element_node_index(&self) -> free_list::IndexType {
107        debug_assert!(self.is_leaf());
108        self.first_child_or_element
109    }
110
111    /// Make this node an empty leaf.
112    #[inline]
113    pub fn make_empty_leaf(&mut self) {
114        self.first_child_or_element = free_list::SENTINEL;
115        self.element_count = 0;
116    }
117
118    /// Make this node a branch.
119    #[inline]
120    pub fn make_branch(&mut self, first_child: free_list::IndexType) {
121        self.first_child_or_element = first_child;
122        self.element_count = NODE_IS_BRANCH;
123    }
124}
125
126#[cfg(test)]
127mod test {
128    use super::*;
129
130    #[test]
131    fn quad_node_is_eight_bytes() {
132        assert_eq!(std::mem::size_of::<Node>(), 8);
133    }
134}
space_partitioning/quadtree/node.rs

space_partitioning/quadtree/
node.rs
