platform_trees/trees/
iterative_size_balanced_tree.rs

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

platform_trees/trees/
iterative_size_balanced_tree.rs
