steel_core/java_block_pos_set/
removal.rs

1use super::{EMPTY, JavaBlockPosSet};
2
3impl JavaBlockPosSet {
4    pub(super) fn remove_from_tree(&mut self, node: u32) {
5        let mut root = self.tree_root(node);
6        let left = self.links(node).left;
7        let right = self.links(node).right;
8        let replacement = if left != EMPTY && right != EMPTY {
9            let mut successor = right;
10            while self.links(successor).left != EMPTY {
11                successor = self.links(successor).left;
12            }
13            let successor_was_red = self.links(successor).red;
14            self.links_mut(successor).red = self.links(node).red;
15            self.links_mut(node).red = successor_was_red;
16            let successor_right = self.links(successor).right;
17            let node_parent = self.links(node).parent;
18
19            if successor == right {
20                self.links_mut(node).parent = successor;
21                self.links_mut(successor).right = node;
22            } else {
23                let successor_parent = self.links(successor).parent;
24                self.links_mut(node).parent = successor_parent;
25                if successor_parent != EMPTY {
26                    if self.links(successor_parent).left == successor {
27                        self.links_mut(successor_parent).left = node;
28                    } else {
29                        self.links_mut(successor_parent).right = node;
30                    }
31                }
32                self.links_mut(successor).right = right;
33                self.links_mut(right).parent = successor;
34            }
35
36            self.links_mut(node).left = EMPTY;
37            self.links_mut(node).right = successor_right;
38            if successor_right != EMPTY {
39                self.links_mut(successor_right).parent = node;
40            }
41            self.links_mut(successor).left = left;
42            self.links_mut(left).parent = successor;
43            self.links_mut(successor).parent = node_parent;
44            if node_parent == EMPTY {
45                root = successor;
46            } else if self.links(node_parent).left == node {
47                self.links_mut(node_parent).left = successor;
48            } else {
49                self.links_mut(node_parent).right = successor;
50            }
51
52            if successor_right == EMPTY {
53                node
54            } else {
55                successor_right
56            }
57        } else if left != EMPTY {
58            left
59        } else if right != EMPTY {
60            right
61        } else {
62            node
63        };
64
65        if replacement != node {
66            let parent = self.links(node).parent;
67            self.links_mut(replacement).parent = parent;
68            if parent == EMPTY {
69                root = replacement;
70                self.links_mut(replacement).red = false;
71            } else if self.links(parent).left == node {
72                self.links_mut(parent).left = replacement;
73            } else {
74                self.links_mut(parent).right = replacement;
75            }
76            self.links_mut(node).parent = EMPTY;
77            self.links_mut(node).left = EMPTY;
78            self.links_mut(node).right = EMPTY;
79        }
80
81        if !self.links(node).red {
82            self.balance_deletion(root, replacement);
83        }
84
85        let parent = self.links(node).parent;
86        if replacement == node && parent != EMPTY {
87            self.links_mut(node).parent = EMPTY;
88            if self.links(parent).left == node {
89                self.links_mut(parent).left = EMPTY;
90            } else if self.links(parent).right == node {
91                self.links_mut(parent).right = EMPTY;
92            }
93        }
94    }
95
96    fn is_red(&self, node: u32) -> bool {
97        node != EMPTY && self.links(node).red
98    }
99
100    fn child(&self, node: u32, left: bool) -> u32 {
101        if left {
102            self.links(node).left
103        } else {
104            self.links(node).right
105        }
106    }
107
108    fn balance_deletion(&mut self, mut root: u32, mut node: u32) {
109        loop {
110            if node == root {
111                return;
112            }
113            let mut parent = self.links(node).parent;
114            if parent == EMPTY {
115                self.links_mut(node).red = false;
116                return;
117            }
118            if self.links(node).red {
119                self.links_mut(node).red = false;
120                return;
121            }
122
123            let left = self.links(parent).left == node;
124            let mut sibling = self.child(parent, !left);
125            if self.is_red(sibling) {
126                self.links_mut(sibling).red = false;
127                self.links_mut(parent).red = true;
128                root = self.rotate(root, parent, left);
129                parent = self.links(node).parent;
130                sibling = self.child(parent, !left);
131            }
132            if sibling == EMPTY {
133                node = parent;
134                continue;
135            }
136            let inner = self.child(sibling, left);
137            let outer = self.child(sibling, !left);
138            if !self.is_red(inner) && !self.is_red(outer) {
139                self.links_mut(sibling).red = true;
140                node = parent;
141                continue;
142            }
143            if !self.is_red(outer) {
144                if inner != EMPTY {
145                    self.links_mut(inner).red = false;
146                }
147                self.links_mut(sibling).red = true;
148                root = self.rotate(root, sibling, !left);
149                parent = self.links(node).parent;
150                sibling = self.child(parent, !left);
151            }
152            if sibling != EMPTY {
153                self.links_mut(sibling).red = self.links(parent).red;
154                let outer = self.child(sibling, !left);
155                if outer != EMPTY {
156                    self.links_mut(outer).red = false;
157                }
158            }
159            self.links_mut(parent).red = false;
160            root = self.rotate(root, parent, left);
161            node = root;
162        }
163    }
164}
steel_core/java_block_pos_set/removal.rs

steel_core/java_block_pos_set/
removal.rs
