hextree/
node.rs

1use crate::{compaction::Compactor, digits::Digits, Cell};
2
3#[derive(Clone, Debug, PartialEq, Eq)]
4#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
5#[repr(align(64))]
6pub(crate) enum Node<V> {
7    Parent([Option<Box<Node<V>>>; 7]),
8    Leaf(V),
9}
10
11impl<V> Node<V> {
12    pub(crate) fn new() -> Self {
13        Self::Parent([None, None, None, None, None, None, None])
14    }
15
16    pub(crate) fn len(&self) -> usize {
17        match self {
18            Self::Leaf(_) => 1,
19            Self::Parent(children) => children.iter().flatten().map(|child| child.len()).sum(),
20        }
21    }
22
23    pub(crate) fn insert<C>(
24        &mut self,
25        cell: Cell,
26        res: u8,
27        mut digits: Digits,
28        value: V,
29        compactor: &mut C,
30    ) where
31        C: Compactor<V>,
32    {
33        match digits.next() {
34            None => *self = Self::Leaf(value),
35            Some(digit) => match self {
36                Self::Leaf(_) => {
37                    return;
38                }
39                Self::Parent(children) => {
40                    match children[digit as usize].as_mut() {
41                        Some(node) => node.insert(cell, res + 1, digits, value, compactor),
42                        None => {
43                            let mut node = Node::new();
44                            node.insert(cell, res + 1, digits, value, compactor);
45                            children[digit as usize] = Some(Box::new(node));
46                        }
47                    };
48                }
49            },
50        };
51        self.coalesce(cell.to_parent(res).unwrap(), compactor);
52    }
53
54    pub(crate) fn coalesce<C>(&mut self, cell: Cell, compactor: &mut C)
55    where
56        C: Compactor<V>,
57    {
58        if let Self::Parent(children) = self {
59            if children
60                .iter()
61                .any(|n| matches!(n.as_ref().map(|n| n.as_ref()), Some(Self::Parent(_))))
62            {
63                return;
64            }
65            let mut arr: [Option<&V>; 7] = [None, None, None, None, None, None, None];
66            for (v, n) in arr.iter_mut().zip(children.iter()) {
67                *v = n.as_ref().map(|n| n.as_ref()).and_then(Node::value);
68            }
69            if let Some(value) = compactor.compact(cell, arr) {
70                *self = Self::Leaf(value)
71            }
72        };
73    }
74
75    pub(crate) fn value(&self) -> Option<&V> {
76        match self {
77            Self::Leaf(value) => Some(value),
78            _ => None,
79        }
80    }
81
82    #[inline]
83    pub(crate) fn contains(&self, mut digits: Digits) -> bool {
84        match (digits.next(), self) {
85            (_, Self::Leaf(_)) => true,
86            (Some(digit), Self::Parent(children)) => {
87                // TODO check if this node is "full"
88                match &children.as_slice()[digit as usize] {
89                    Some(node) => node.contains(digits),
90                    None => false,
91                }
92            }
93            // No digits left, but `self` isn't full, so this cell
94            // can't fully contain the target.
95            (None, Self::Parent(_)) => false,
96        }
97    }
98
99    #[inline]
100    pub(crate) fn get(&self, res: u8, cell: Cell, mut digits: Digits) -> Option<(Cell, &Node<V>)> {
101        match (digits.next(), self) {
102            (None, _) => Some((cell, self)),
103            (Some(_), Self::Leaf(_)) => {
104                Some((cell.to_parent(res).expect("invalid condition"), self))
105            }
106            (Some(digit), Self::Parent(children)) => match &children.as_slice()[digit as usize] {
107                Some(node) => node.get(res + 1, cell, digits),
108                None => None,
109            },
110        }
111    }
112
113    #[inline]
114    pub(crate) fn get_mut(
115        &mut self,
116        res: u8,
117        cell: Cell,
118        mut digits: Digits,
119    ) -> Option<(Cell, &mut Node<V>)> {
120        match (digits.next(), self) {
121            (None, s) => Some((cell, s)),
122            (Some(_), s @ Self::Leaf(_)) => {
123                Some((cell.to_parent(res).expect("invalid condition"), s))
124            }
125            (Some(digit), Self::Parent(ref mut children)) => {
126                match children.as_mut_slice()[digit as usize].as_deref_mut() {
127                    Some(node) => node.get_mut(res + 1, cell, digits),
128                    None => None,
129                }
130            }
131        }
132    }
133}
hextree/node.rs

hextree/
node.rs
