platform_trees/trees/
iterative_size_balanced_tree.rs

1use crate::{LinkType, RecursiveSizeBalancedTree};
2
3/// Extends [`RecursiveSizeBalancedTree`] with iterative `attach` and
4/// `detach` operations.
5///
6/// The iterative approach avoids stack overflow on deep trees by using
7/// a loop with pointer-chasing instead of recursion.
8///
9/// # Usage
10///
11/// Implement [`RecursiveSizeBalancedTree`] for your storage type, then
12/// add an empty `impl IterativeSizeBalancedTree<T> for MyStorage {}`.
13///
14/// # Safety
15///
16/// All methods are `unsafe` — the caller must ensure that `root` points
17/// to a valid, writable location and that `node` indices are valid.
18pub trait IterativeSizeBalancedTree<T: LinkType>: RecursiveSizeBalancedTree<T> {
19    /// Inserts `node` into the tree rooted at `*root`.
20    ///
21    /// If `*root` is zero (empty tree), `node` becomes the root with
22    /// size 1. Otherwise the tree is rebalanced after insertion.
23    unsafe fn attach(&mut self, root: *mut T, node: T) {
24        unsafe {
25            if *root == T::funty(0) {
26                self.set_size(node, T::funty(1));
27                *root = node;
28                return;
29            }
30            self.attach_core(root, node);
31        }
32    }
33    /// Removes `node` from the tree rooted at `*root`.
34    ///
35    /// The tree is rebalanced after removal. After detach, `node`'s
36    /// left, right, and size fields are cleared to zero.
37    unsafe fn detach(&mut self, root: *mut T, node: T) {
38        unsafe {
39            self.detach_core(root, node);
40        }
41    }
42
43    unsafe fn attach_core(&mut self, mut root: *mut T, node: T) {
44        unsafe {
45            loop {
46                let left = self.get_mut_left_reference(*root);
47                let left_size = self.get_size_or_zero(*left);
48                let right = self.get_mut_right_reference(*root);
49                let right_size = self.get_size_or_zero(*right);
50                if self.first_is_to_the_left_of_second(node, *root) {
51                    if *left == T::funty(0) {
52                        self.inc_size(*root);
53                        self.set_size(node, T::funty(1));
54                        *left = node;
55                        return;
56                    }
57                    if self.first_is_to_the_left_of_second(node, *left) {
58                        if (left_size + T::funty(1)) > right_size {
59                            self.right_rotate(root);
60                        } else {
61                            self.inc_size(*root);
62                            root = left;
63                        }
64                    } else {
65                        let left_right_size = self.get_size_or_zero(self.get_right(*left));
66                        if (left_right_size + T::funty(1)) > right_size {
67                            if left_right_size == T::funty(0) && right_size == T::funty(0) {
68                                self.set_left(node, *left);
69                                self.set_right(node, *root);
70                                self.set_size(node, left_size + T::funty(1) + T::funty(1));
71                                self.set_left(*root, T::funty(0));
72                                self.set_size(*root, T::funty(1));
73                                *root = node;
74                                return;
75                            }
76                            self.left_rotate(left);
77                            self.right_rotate(root);
78                        } else {
79                            self.inc_size(*root);
80                            root = left;
81                        }
82                    }
83                } else {
84                    if *right == T::funty(0) {
85                        self.inc_size(*root);
86                        self.set_size(node, T::funty(1));
87                        *right = node;
88                        return;
89                    }
90                    if self.first_is_to_the_right_of_second(node, *right) {
91                        if (right_size + T::funty(1)) > left_size {
92                            self.left_rotate(root);
93                        } else {
94                            self.inc_size(*root);
95                            root = right;
96                        }
97                    } else {
98                        let right_left_size = self.get_size_or_zero(self.get_left(*right));
99                        if (right_left_size + T::funty(1)) > left_size {
100                            if right_left_size == T::funty(0) && left_size == T::funty(0) {
101                                self.set_left(node, *root);
102                                self.set_right(node, *right);
103                                self.set_size(node, right_size + T::funty(1) + T::funty(1));
104                                self.set_right(*root, T::funty(0));
105                                self.set_size(*root, T::funty(1));
106                                *root = node;
107                                return;
108                            }
109                            self.right_rotate(right);
110                            self.left_rotate(root);
111                        } else {
112                            self.inc_size(*root);
113                            root = right;
114                        }
115                    }
116                }
117            }
118        }
119    }
120
121    unsafe fn detach_core(&mut self, mut root: *mut T, node: T) {
122        unsafe {
123            loop {
124                let left = self.get_mut_left_reference(*root);
125                let left_size = self.get_size_or_zero(*left);
126                let right = self.get_mut_right_reference(*root);
127                let right_size = self.get_size_or_zero(*right);
128                if self.first_is_to_the_left_of_second(node, *root) {
129                    let decremented_left_size = left_size - T::funty(1);
130                    if self.get_size_or_zero(self.get_right_or_default(*right))
131                        > decremented_left_size
132                    {
133                        self.left_rotate(root);
134                    } else if self.get_size_or_zero(self.get_left_or_default(*right))
135                        > decremented_left_size
136                    {
137                        self.right_rotate(right);
138                        self.left_rotate(root);
139                    } else {
140                        self.dec_size(*root);
141                        root = left;
142                    }
143                } else if self.first_is_to_the_right_of_second(node, *root) {
144                    let decremented_right_size = right_size - T::funty(1);
145                    if self.get_size_or_zero(self.get_left_or_default(*left))
146                        > decremented_right_size
147                    {
148                        self.right_rotate(root);
149                    } else if self.get_size_or_zero(self.get_right_or_default(*left))
150                        > decremented_right_size
151                    {
152                        self.left_rotate(left);
153                        self.right_rotate(root);
154                    } else {
155                        self.dec_size(*root);
156                        root = right;
157                    }
158                } else {
159                    if left_size > T::funty(0) && right_size > T::funty(0) {
160                        let replacement;
161                        if left_size > right_size {
162                            replacement = self.get_rightest(*left);
163                            self.detach_core(left, replacement);
164                        } else {
165                            replacement = self.get_leftest(*right);
166                            self.detach_core(right, replacement);
167                        }
168                        self.set_left(replacement, *left);
169                        self.set_right(replacement, *right);
170                        self.set_size(replacement, left_size + right_size);
171                        *root = replacement;
172                    } else if left_size > T::funty(0) {
173                        *root = *left;
174                    } else if right_size > T::funty(0) {
175                        *root = *right;
176                    } else {
177                        *root = T::funty(0);
178                    }
179                    self.clear_node(node);
180                    return;
181                }
182            }
183        }
184    }
185}
platform_trees/trees/iterative_size_balanced_tree.rs

platform_trees/trees/
iterative_size_balanced_tree.rs
