platform_trees/trees/
recursive_size_balanced_tree.rs

1use crate::LinkType;
2
3pub trait RecursiveSizeBalancedTree<T: LinkType> {
4    unsafe fn get_mut_left_reference(&mut self, node: T) -> *mut T;
5
6    unsafe fn get_mut_right_reference(&mut self, node: T) -> *mut T;
7
8    unsafe fn get_left_reference(&self, node: T) -> *const T;
9
10    unsafe fn get_right_reference(&self, node: T) -> *const T;
11
12    unsafe fn get_left(&self, node: T) -> T;
13
14    unsafe fn get_right(&self, node: T) -> T;
15
16    unsafe fn get_size(&self, node: T) -> T;
17
18    unsafe fn set_left(&mut self, node: T, left: T);
19
20    unsafe fn set_right(&mut self, node: T, right: T);
21
22    unsafe fn set_size(&mut self, node: T, size: T);
23
24    unsafe fn first_is_to_the_left_of_second(&self, first: T, second: T) -> bool;
25
26    unsafe fn first_is_to_the_right_of_second(&self, first: T, second: T) -> bool;
27
28    unsafe fn get_left_or_default(&self, node: T) -> T {
29        if node == T::funty(0) {
30            T::funty(0)
31        } else {
32            self.get_left(node)
33        }
34    }
35
36    unsafe fn get_right_or_default(&self, node: T) -> T {
37        if node == T::funty(0) {
38            T::funty(0)
39        } else {
40            self.get_right(node)
41        }
42    }
43
44    unsafe fn get_size_or_zero(&self, node: T) -> T {
45        if node == T::funty(0) {
46            T::funty(0)
47        } else {
48            self.get_size(node)
49        }
50    }
51
52    unsafe fn inc_size(&mut self, node: T) {
53        self.set_size(node, self.get_size(node) + T::funty(1));
54    }
55
56    unsafe fn dec_size(&mut self, node: T) {
57        self.set_size(node, self.get_size(node) - T::funty(1));
58    }
59
60    unsafe fn get_left_size(&self, node: T) -> T {
61        self.get_size_or_zero(self.get_left_or_default(node))
62    }
63
64    unsafe fn get_right_size(&self, node: T) -> T {
65        self.get_size_or_zero(self.get_right_or_default(node))
66    }
67
68    unsafe fn fix_size(&mut self, node: T) {
69        self.set_size(
70            node,
71            (self.get_left_size(node) + self.get_right_size(node)) + T::funty(1),
72        );
73    }
74
75    unsafe fn left_rotate(&mut self, root: *mut T) {
76        *root = self.left_rotate_core(*root);
77    }
78
79    unsafe fn left_rotate_core(&mut self, root: T) -> T {
80        let right = self.get_right(root);
81        self.set_right(root, self.get_left(right));
82        self.set_left(right, root);
83        self.set_size(right, self.get_size(root));
84        self.fix_size(root);
85        right
86    }
87
88    unsafe fn right_rotate(&mut self, root: *mut T) {
89        *root = self.right_rotate_core(*root);
90    }
91
92    unsafe fn right_rotate_core(&mut self, root: T) -> T {
93        let left = self.get_left(root);
94        self.set_left(root, self.get_right(left));
95        self.set_right(left, root);
96        self.set_size(left, self.get_size(root));
97        self.fix_size(root);
98        left
99    }
100
101    unsafe fn get_rightest(&self, mut current: T) -> T {
102        let mut current_right = self.get_right(current);
103        while current_right != T::funty(0) {
104            current = current_right;
105            current_right = self.get_right(current);
106        }
107        current
108    }
109
110    unsafe fn get_leftest(&self, mut current: T) -> T {
111        let mut current_left = self.get_left(current);
112        while current_left != T::funty(0) {
113            current = current_left;
114            current_left = self.get_left(current);
115        }
116        current
117    }
118
119    unsafe fn get_next(&self, node: T) -> T {
120        self.get_leftest(self.get_right(node))
121    }
122
123    unsafe fn get_previous(&self, node: T) -> T {
124        self.get_rightest(self.get_left(node))
125    }
126
127    unsafe fn contains(&self, node: T, mut root: T) -> bool {
128        while root != T::funty(0) {
129            if self.first_is_to_the_left_of_second(node, root) {
130                root = self.get_left(root);
131            } else if self.first_is_to_the_right_of_second(node, root) {
132                root = self.get_right(root);
133            } else {
134                return true;
135            }
136        }
137        false
138    }
139
140    unsafe fn clear_node(&mut self, node: T) {
141        self.set_left(node, T::funty(0));
142        self.set_right(node, T::funty(0));
143        self.set_size(node, T::funty(0));
144    }
145}
platform_trees/trees/recursive_size_balanced_tree.rs

platform_trees/trees/
recursive_size_balanced_tree.rs
