luct_core/tree/
node.rs

1use crate::{store::Hashable, tree::HashOutput};
2use serde::{Deserialize, Serialize};
3use sha2::{Digest, Sha256};
4use std::cmp::Ordering;
5
6#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Hash)]
7
8pub struct NodeKey {
9    pub(crate) start: u64,
10    pub(crate) end: u64,
11}
12
13impl NodeKey {
14    pub fn leaf(idx: u64) -> Self {
15        Self {
16            start: idx,
17            end: idx + 1,
18        }
19    }
20
21    pub(crate) fn full_range(end: u64) -> Self {
22        Self { start: 0, end }
23    }
24
25    pub(crate) fn size(&self) -> u64 {
26        self.end - self.start
27    }
28
29    pub(crate) fn split_idx(&self) -> u64 {
30        let size = self.size();
31        size.next_power_of_two() >> 1
32    }
33
34    pub fn split(&self) -> (Self, Self) {
35        let split = self.split_idx();
36        let split = self.start + split;
37        (
38            Self {
39                start: self.start,
40                end: split,
41            },
42            Self {
43                start: split,
44                end: self.end,
45            },
46        )
47    }
48
49    pub(crate) fn merge(&self, other: &Self) -> Option<Self> {
50        if self.end == other.start {
51            Some(Self {
52                start: self.start,
53                end: other.end,
54            })
55        } else {
56            None
57        }
58    }
59
60    pub fn is_balanced(&self) -> bool {
61        let diff = self.end - self.start;
62        diff.is_power_of_two()
63    }
64
65    pub(crate) fn is_leaf(&self) -> bool {
66        self.start + 1 == self.end
67    }
68}
69
70impl PartialOrd for NodeKey {
71    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
72        Some(self.cmp(other))
73    }
74}
75
76impl Ord for NodeKey {
77    fn cmp(&self, other: &Self) -> Ordering {
78        match self.end.cmp(&other.end) {
79            Ordering::Equal => {}
80            ord => return ord,
81        }
82        self.start.cmp(&other.start)
83    }
84}
85
86#[derive(Debug, Clone, PartialEq, Eq)]
87pub struct Node {
88    pub left: HashOutput,
89    pub right: HashOutput,
90}
91
92impl Hashable for Node {
93    fn hash(&self) -> HashOutput {
94        let mut hash = Sha256::new();
95        hash.update([1]);
96        hash.update(self.left);
97        hash.update(self.right);
98        hash.finalize().into()
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn node_key_split() {
108        let node_key = NodeKey { start: 0, end: 6 };
109        let (left, right) = node_key.split();
110        assert_eq!(left, NodeKey { start: 0, end: 4 });
111        assert_eq!(right, NodeKey { start: 4, end: 6 });
112
113        let node_key = NodeKey { start: 0, end: 8 };
114        let (left, right) = node_key.split();
115        assert_eq!(left, NodeKey { start: 0, end: 4 });
116        assert_eq!(right, NodeKey { start: 4, end: 8 });
117    }
118}
luct_core/tree/node.rs

luct_core/tree/
node.rs
