pub trait BstSpec: Sized {
type Parent: ParentStrategy<Data = Self::Data>;
type Data;
// Required methods
fn merge(
left: Option<BstRoot<Self>>,
right: Option<BstRoot<Self>>,
) -> Option<BstRoot<Self>>;
fn split<Seeker>(
node: Option<BstRoot<Self>>,
seeker: Seeker,
eq_left: bool,
) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
where Seeker: BstSeeker<Spec = Self>;
// Provided methods
fn top_down(_node: BstDataMutRef<'_, Self>) { ... }
fn bottom_up(_node: BstDataMutRef<'_, Self>) { ... }
}Required Associated Types§
Required Methods§
fn merge( left: Option<BstRoot<Self>>, right: Option<BstRoot<Self>>, ) -> Option<BstRoot<Self>>
fn split<Seeker>(
node: Option<BstRoot<Self>>,
seeker: Seeker,
eq_left: bool,
) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)where
Seeker: BstSeeker<Spec = Self>,
Provided Methods§
Sourcefn top_down(_node: BstDataMutRef<'_, Self>)
fn top_down(_node: BstDataMutRef<'_, Self>)
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 130)
123 pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
124 where
125 Spec: BstSpec<Data = Data, Parent = Self>,
126 {
127 unsafe {
128 let (mut node, mut stack) = node.root_path();
129 while let Some(is_left) = stack.pop() {
130 Spec::top_down(node.reborrow_datamut());
131 if is_left {
132 node = node.left().descend().unwrap_unchecked();
133 } else {
134 node = node.right().descend().unwrap_unchecked();
135 }
136 }
137 Spec::top_down(node.reborrow_datamut());
138 }
139 }More examples
crates/competitive/src/data_structure/treap.rs (line 126)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }Sourcefn bottom_up(_node: BstDataMutRef<'_, Self>)
fn bottom_up(_node: BstDataMutRef<'_, Self>)
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 146)
141 pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
142 where
143 Spec: BstSpec<Data = Data, Parent = Self>,
144 {
145 loop {
146 Spec::bottom_up(node.reborrow_datamut());
147 match node.ascend() {
148 Ok(parent) => node = parent,
149 Err(_) => break,
150 }
151 }
152 }
153
154 pub fn is_root<Spec>(node: BstNodeRef<marker::Immut<'_>, Spec>) -> bool
155 where
156 Spec: BstSpec<Data = Data, Parent = Self>,
157 {
158 unsafe { node.node.as_ref().parent.parent.is_none() }
159 }
160
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }More examples
crates/competitive/src/data_structure/treap.rs (line 130)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.