algae_trees/data/btree/
btree.rs

1/*
2   Appellation: btree
3   Context: module
4   Creator: FL03 <jo3mccain@icloud.com>
5   Description:
6*/
7use std::convert::TryFrom;
8
9struct Node<T> {
10    keys: Vec<T>,
11    children: Vec<Node<T>>,
12}
13
14impl<T> Node<T>
15where
16    T: Ord,
17{
18    fn new(degree: usize, _keys: Option<Vec<T>>, _children: Option<Vec<Node<T>>>) -> Self {
19        Node {
20            keys: match _keys {
21                Some(_keys) => _keys,
22                None => Vec::with_capacity(degree - 1),
23            },
24            children: match _children {
25                Some(_children) => _children,
26                None => Vec::with_capacity(degree),
27            },
28        }
29    }
30
31    fn is_leaf(&self) -> bool {
32        self.children.is_empty()
33    }
34}
35
36pub struct BTree<T> {
37    root: Node<T>,
38    props: BTreeProps,
39}
40
41impl<T> BTree<T>
42    where
43        T: Ord + Copy + std::fmt::Debug + Default,
44{
45    pub fn new(branch_factor: usize) -> Self {
46        let degree = 2 * branch_factor;
47        Self {
48            root: Node::new(degree, None, None),
49            props: BTreeProps::new(degree),
50        }
51    }
52
53    pub fn insert(&mut self, key: T) {
54        if self.props.is_maxed_out(&self.root) {
55            let mut new_root = Node::new(self.props.degree, None, None);
56            std::mem::swap(&mut new_root, &mut self.root);
57            self.root.children.insert(0, new_root);
58            self.props.split_child(&mut self.root, 0);
59        }
60
61        self.props.insert_non_full(&mut self.root, key);
62    }
63
64    pub fn transverse(&self) {
65        self.props.transverse_node(&self.root, 0);
66        println!();
67    }
68
69    pub fn search(&self, key: T) -> bool {
70        let mut current_node = &self.root;
71        let mut index: isize;
72        loop {
73            index = isize::try_from(current_node.keys.len()).ok().unwrap() - 1;
74            while index >= 0 && current_node.keys[index as usize] > key {
75                index -= 1;
76            }
77
78            let u_index: usize = usize::try_from(index + 1).ok().unwrap();
79            if index >= 0 && current_node.keys[u_index - 1] == key {
80                break true;
81            } else if current_node.is_leaf() {
82                break false;
83            } else {
84                current_node = &current_node.children[u_index];
85            }
86        }
87    }
88}
89
90struct BTreeProps {
91    degree: usize,
92    max_keys: usize,
93    mid_key_index: usize,
94}
95
96impl BTreeProps {
97    fn new(degree: usize) -> Self {
98        Self {
99            degree,
100            max_keys: degree - 1,
101            mid_key_index: (degree - 1) / 2,
102        }
103    }
104
105    fn is_maxed_out<T: Ord + Copy>(&self, node: &Node<T>) -> bool {
106        node.keys.len() == self.max_keys
107    }
108
109    fn split_child<T: Ord + Copy + Default>(&self, parent: &mut Node<T>, child_index: usize) {
110        let child = &mut parent.children[child_index];
111        let middle_key = child.keys[self.mid_key_index];
112        let right_keys = match child.keys.split_off(self.mid_key_index).split_first() {
113            Some((_first, _others)) => _others.to_vec(),
114            None => Vec::with_capacity(self.max_keys),
115        };
116        let right_children = if !child.is_leaf() {
117            Some(child.children.split_off(self.mid_key_index + 1))
118        } else {
119            None
120        };
121        let new_child_node: Node<T> = Node::new(self.degree, Some(right_keys), right_children);
122
123        parent.keys.insert(child_index, middle_key);
124        parent.children.insert(child_index + 1, new_child_node);
125    }
126
127    fn insert_non_full<T: Ord + Copy + Default>(&mut self, node: &mut Node<T>, key: T) {
128        let mut index: isize = isize::try_from(node.keys.len()).ok().unwrap() - 1;
129        while index >= 0 && node.keys[index as usize] >= key {
130            index -= 1;
131        }
132
133        let mut u_index: usize = usize::try_from(index + 1).ok().unwrap();
134        if node.is_leaf() {
135            node.keys.insert(u_index, key);
136        } else {
137            if self.is_maxed_out(&node.children[u_index]) {
138                self.split_child(node, u_index);
139                if node.keys[u_index] < key {
140                    u_index += 1;
141                }
142            }
143
144            self.insert_non_full(&mut node.children[u_index], key);
145        }
146    }
147
148    fn transverse_node<T: Ord + std::fmt::Debug>(&self, node: &Node<T>, depth: usize) {
149        if node.is_leaf() {
150            print!(" {0:{<1$}{2:?}{0:}<1$} ", "", depth, node.keys);
151        } else {
152            let _depth = depth + 1;
153            for (index, key) in node.keys.iter().enumerate() {
154                self.transverse_node(&node.children[index], _depth);
155                print!("{0:{<1$}{2:?}{0:}<1$}", "", depth, key);
156            }
157
158            self.transverse_node(node.children.last().unwrap(), _depth);
159        }
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::BTree;
166
167    #[test]
168    fn test_search() {
169        let values = [10, 20, 30, 5, 6, 7, 11, 12, 15];
170        let mut tree = BTree::new(2);
171        for i in 0..values.len() {
172            tree.insert(values[i])
173        }
174        assert!(tree.search(15));
175        assert_eq!(tree.search(16), false);
176    }
177}
algae_trees/data/btree/btree.rs

algae_trees/data/btree/
btree.rs
