rust_black_trees/
unbalancetree.rs

1use std::cell::RefCell;
2use std::rc::Rc;
3
4use super::tree::BaseTree;
5use super::tree::Tree;
6
7use super::node::Node;
8use super::node::*;
9
10/// a nice convenient macro which allows a user to initialize a tree with
11/// a number of elements
12/// usage: bst!{1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
13#[macro_export]
14macro_rules! bst {
15    ( $( $x:expr ),* ) => {
16        {
17            let mut temp_tree = BSTree::new();
18            $(
19                temp_tree.insert($x);
20            )*
21            temp_tree
22        }
23    };
24}
25
26#[derive(Debug)]
27pub struct RegularNode<T> {
28    pub value: T,
29    pub ptr: usize,
30    pub parent: Option<usize>,
31    pub lchild: Option<usize>,
32    pub rchild: Option<usize>,
33    data: Rc<RefCell<Vec<RegularNode<T>>>>,
34}
35
36impl<T> RegularNode<T> {
37    fn new(val: T, selfptr: usize, data: Rc<RefCell<Vec<RegularNode<T>>>>) -> Self {
38        Self {
39            value: val,
40            ptr: selfptr,
41            parent: None,
42            lchild: None,
43            rchild: None,
44            data: data,
45        }
46    }
47}
48
49impl<T: std::fmt::Debug + std::cmp::PartialOrd> Node<T> for RegularNode<T> {
50    fn to_self_string(&self) -> String {
51        format!("[P:{:?} V:{:?}]", self.parent, self.value)
52    }
53
54    fn to_self_string_display(&self) -> (String, usize) {
55        let s = format!("{:?}", self.value);
56        let l = s.len();
57        (s, l)
58    }
59
60    fn is(&self, val: &T) -> bool {
61        &self.value == val
62    }
63    fn greater(&self, val: &T) -> bool {
64        &self.value > val
65    }
66    fn lesser(&self, val: &T) -> bool {
67        &self.value < val
68    }
69
70    fn get_value(&self) -> &T {
71        &self.value
72    }
73    /**
74     * In order to return a reference to a value of a vector contained within a
75     * refcell, a raw pointer is used. The unsafe code could be avoided by
76     * replacing each call to self.get(n) with &self.data.borrow()[n] and each call
77     * to self.get_mut(n) with &mut self.data.borrow()[n]
78     */
79    fn get(&self, ptr: usize) -> &RegularNode<T> {
80        unsafe { &(*self.data.as_ptr())[ptr] }
81    }
82
83    fn get_mut(&self, ptr: usize) -> &mut RegularNode<T> {
84        unsafe { &mut (*self.data.as_ptr())[ptr] }
85    }
86
87    fn get_child(&self, side: Side) -> Option<usize> {
88        match side {
89            Side::Left => self.lchild,
90            Side::Right => self.rchild,
91        }
92    }
93
94    fn set_child(&mut self, child: usize, side: Side) {
95        self.set_child_opt(Some(child), side)
96    }
97
98    fn set_child_opt(&mut self, c: Option<usize>, side: Side) {
99        match side {
100            Side::Left => self.lchild = c,
101            Side::Right => self.rchild = c,
102        };
103        if let Some(child) = c {
104            self.get_mut(child).parent = Some(self.location());
105        }
106    }
107    fn set_parent(&mut self, p: Option<usize>) {
108        self.parent = p;
109    }
110
111    fn get_parent(&self) -> Option<usize> {
112        self.parent
113    }
114
115    fn location(&self) -> usize {
116        self.ptr
117    }
118}
119
120/**
121 * Arena based memory tree structure
122*/
123#[derive(Debug)]
124pub struct BSTree<T> {
125    root: Option<usize>,
126    size: usize,
127    data: Rc<RefCell<Vec<RegularNode<T>>>>,
128    free: Vec<usize>,
129}
130
131impl<T> Tree<T> for BSTree<T>
132where
133    T: PartialOrd,
134    T: PartialEq,
135    T: std::fmt::Debug,
136{
137    fn new() -> Self {
138        Self {
139            root: None,
140            data: Rc::new(RefCell::new(Vec::new())),
141            size: 0,
142            free: Vec::new(),
143        }
144    }
145}
146
147impl<T> BaseTree<T> for BSTree<T>
148where
149    T: PartialOrd,
150    T: PartialEq,
151    T: std::fmt::Debug,
152{
153    type MNode = RegularNode<T>;
154    /**
155     * In order to return a reference to a value of a vector contained within a refcell, a raw
156     * pointer is used. The unsafe code could be avoided by replacing each call to self.get(n) with
157     * &self.data.borrow()[n] and each call to self.get_mut(n) with &mut self.data.borrow()[n]. This
158     * allows us to do the same thing with less keystrokes. It does make the program not
159     * thread-safe, but a this data structure is a pretty terrible choice for a multi-threaded data
160     * structure anyways, since re-balancing can require that most of the tree be locked to one
161     * thread during an insertion or deletion
162     */
163    fn get(&self, val: usize) -> &Self::MNode {
164        unsafe { &(*self.data.as_ptr())[val] }
165    }
166
167    fn get_mut(&self, val: usize) -> &mut Self::MNode {
168        unsafe { &mut (*self.data.as_ptr())[val] }
169    }
170
171    fn get_root(&self) -> Option<usize> {
172        self.root
173    }
174
175    fn set_root(&mut self, new_root: Option<usize>) {
176        self.root = new_root
177    }
178
179    fn crement_size(&mut self, amount: isize) {
180        self.size = (self.size as isize + amount) as usize;
181    }
182
183    fn attach_child(&self, p: usize, c: usize, side: Side) {
184        self.get_mut(p).set_child(c, side)
185    }
186
187    fn rebalance_ins(&mut self, _n: usize) {}
188
189    fn rebalance_del(&mut self, _n: usize, _child: usize) {}
190
191    fn delete_replace(&mut self, n: usize) -> usize {
192        let node = self.get(n);
193        match (node.lchild, node.rchild) {
194            (Some(lc), Some(rc)) => {
195                let p = node.parent;
196                let successor = self.get(rc).find_min();
197                self.delete_replace(successor);
198                self.data.borrow_mut().swap(successor, n);
199
200                self.get_mut(n).lchild = Some(lc);
201                self.get_mut(n).rchild = Some(rc);
202                self.get_mut(n).parent = p;
203                self.get_mut(n).ptr = n;
204                return successor;
205            }
206            (None, Some(_rc)) => self.replace_node(n, self.get(n).rchild),
207            (Some(_lc), None) => self.replace_node(n, self.get(n).lchild),
208            (None, None) => self.replace_node(n, None),
209        };
210        n
211    }
212
213    fn replace_node(&mut self, to_delete: usize, to_attach: Option<usize>) {
214        let node = self.get(to_delete);
215        if let Some(p) = node.parent {
216            if node.is_child(Side::Left) {
217                self.get_mut(p).lchild = to_attach;
218            } else {
219                self.get_mut(p).rchild = to_attach;
220            }
221        } else {
222            self.root = to_attach;
223        }
224    }
225
226    fn get_size(&self) -> usize {
227        return self.size;
228    }
229
230    fn create_node(&mut self, val: T) -> usize {
231        // update this so it reuses deleted slots
232        if self.free.len() > 0 {
233            let n = self.free.pop().expect("pop should not fail if len > 0");
234            let mut d = self.get_mut(n);
235            d.ptr = n;
236            d.lchild = None;
237            d.rchild = None;
238            d.parent = None;
239            n
240        } else {
241            let loc = self.data.borrow().len();
242            self.data
243                .borrow_mut()
244                .push(RegularNode::new(val, loc, self.data.clone()));
245            loc
246        }
247    }
248
249    fn delete_node(&mut self, index: usize) {
250        self.free.push(index);
251    }
252}
253
254impl<T> BSTree<T>
255where
256    T: PartialOrd,
257    T: PartialEq,
258    T: std::fmt::Debug,
259{
260    #[allow(dead_code)]
261    fn get_size_recursive(&self) -> usize {
262        if let Some(root) = self.root {
263            self.get(root).get_size()
264        } else {
265            0
266        }
267    }
268}
269
270#[cfg(test)]
271mod tests {
272    use super::*;
273    fn make_fake_tree_node_no_balance() -> BSTree<i32> {
274        let mut tree = BSTree::new();
275        for x in vec![50, 25, 75, 15, 35, 65, 85, 0, 20, 30, 40, 60, 70, 80, 100] {
276            tree.insert(x);
277        }
278
279        tree
280    }
281
282    #[test]
283    fn test_tree_print() {
284        let tree = make_fake_tree_node_no_balance();
285        assert_eq!(tree.to_string(), "([P:None V:50] ([P:Some(0) V:25] ([P:Some(1) V:15] ([P:Some(3) V:0] () ()) ([P:Some(3) V:20] () ())) ([P:Some(1) V:35] ([P:Some(4) V:30] () ()) ([P:Some(4) V:40] () ()))) ([P:Some(0) V:75] ([P:Some(2) V:65] ([P:Some(5) V:60] () ()) ([P:Some(5) V:70] () ())) ([P:Some(2) V:85] ([P:Some(6) V:80] () ()) ([P:Some(6) V:100] () ()))))");
286        let tree_empty = BSTree::<i32>::new();
287        assert_eq!(tree_empty.to_string(), "(Empty tree)");
288    }
289
290    #[test]
291    fn test_contains() {
292        let tree = make_fake_tree_node_no_balance();
293        assert!(tree.contains(&100));
294        assert!(tree.contains(&0));
295        assert!(tree.contains(&50));
296        assert!(tree.contains(&25));
297        assert!(tree.contains(&75));
298        assert!(tree.contains(&60));
299        assert!(tree.contains(&40));
300
301        assert!(!tree.contains(&42));
302        assert!(!tree.contains(&99));
303        assert!(!tree.contains(&1));
304    }
305
306    #[test]
307    fn test_insert() {
308        let mut tree = BSTree::<i32>::new();
309        for x in 0..10 {
310            double_size_test(&tree, x as usize);
311            tree.insert(x);
312            double_size_test(&tree, (x + 1) as usize);
313        }
314
315        assert_eq!(tree.to_string(), "([P:None V:0] () ([P:Some(0) V:1] () ([P:Some(1) V:2] () ([P:Some(2) V:3] () ([P:Some(3) V:4] () ([P:Some(4) V:5] () ([P:Some(5) V:6] () ([P:Some(6) V:7] () ([P:Some(7) V:8] () ([P:Some(8) V:9] () ()))))))))))");
316    }
317
318    fn double_size_test<T: PartialEq + PartialOrd + std::fmt::Debug>(
319        tree: &BSTree<T>,
320        expect: usize,
321    ) {
322        assert_eq!(tree.get_size(), expect);
323        assert_eq!(tree.get_size_recursive(), expect);
324    }
325
326    #[test]
327    fn test_height() {
328        let tree = make_fake_tree_node_no_balance();
329        assert_eq!(tree.get_height(), 4);
330
331        let mut tree2 = BSTree::<i32>::new();
332        for x in 0..10 {
333            tree2.insert(x);
334        }
335        assert_eq!(tree2.get_height(), 10);
336
337        let tree3 = BSTree::<i32>::new();
338        assert_eq!(tree3.get_height(), 0);
339    }
340
341    #[test]
342    fn test_delete_mem() {
343        let mut tree = make_fake_tree_node_no_balance();
344        double_size_test(&tree, 15);
345
346        tree.delete(1);
347        double_size_test(&tree, 15);
348
349        tree.delete(0);
350        double_size_test(&tree, 14);
351        assert_eq!(tree.data.borrow().len(), 15);
352        tree.insert(0);
353        assert_eq!(tree.data.borrow().len(), 15);
354        double_size_test(&tree, 15);
355
356        tree.delete(50);
357        double_size_test(&tree, 14);
358        assert_eq!(tree.data.borrow().len(), 15);
359        tree.insert(50);
360        assert_eq!(tree.data.borrow().len(), 15);
361        double_size_test(&tree, 15);
362    }
363
364    #[test]
365    fn test_delete() {
366        let mut tree = make_fake_tree_node_no_balance();
367        double_size_test(&tree, 15);
368        tree.delete(100);
369        tree.delete(80);
370        tree.delete(85);
371        assert_eq!(tree.to_string(), "([P:None V:50] ([P:Some(0) V:25] ([P:Some(1) V:15] ([P:Some(3) V:0] () ()) ([P:Some(3) V:20] () ())) ([P:Some(1) V:35] ([P:Some(4) V:30] () ()) ([P:Some(4) V:40] () ()))) ([P:Some(0) V:75] ([P:Some(2) V:65] ([P:Some(5) V:60] () ()) ([P:Some(5) V:70] () ())) ()))");
372    }
373}
rust_black_trees/unbalancetree.rs

rust_black_trees/
unbalancetree.rs
