pub unsafe fn rotate<Spec, Data>(
node: BstNodePtr<<Spec as BstSpec>::Data, <Spec as BstSpec>::Parent>,
)where
Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,Examples found in repository?
crates/competitive/src/tree/link_cut_tree.rs (line 249)
233 fn access_node(mut node: LinkCutPtr<S>) {
234 unsafe {
235 Self::splay(node);
236 if let Some(right) = node.as_mut().child[1].take() {
237 LinkCutBstSpec::<S>::with_two_inner_mut(node, right, S::attach_virtual);
238 }
239 Self::pull(node);
240 while let Some(mut parent) = node.as_ref().parent.parent {
241 Self::splay(parent);
242 if let Some(right) = parent.as_mut().child[1].take() {
243 LinkCutBstSpec::<S>::with_two_inner_mut(parent, right, S::attach_virtual);
244 }
245 LinkCutBstSpec::<S>::with_two_inner_mut(parent, node, S::detach_virtual);
246 parent.as_mut().child[1] = Some(node);
247 node.as_mut().parent.parent = Some(parent);
248 LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(node));
249 splay_operations::with_parent::rotate::<LinkCutBstSpec<S>, LinkCutData<S>>(node);
250 Self::pull(node);
251 LinkCutBstSpec::<S>::with_two_inner_mut(parent, node, S::transfer_path_parent);
252 }
253 }
254 }More examples
crates/competitive/src/data_structure/splay_operations.rs (line 111)
76 pub unsafe fn splay<Spec, Data>(node: NodePtr<Spec>) -> NodePtr<Spec>
77 where
78 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
79 {
80 let mut inline_stack = [const { MaybeUninit::uninit() }; 64];
81 let mut inline_len = 0;
82 let mut overflow_stack = Vec::new();
83 let mut current = node;
84 loop {
85 if inline_len < inline_stack.len() {
86 inline_stack[inline_len].write(current);
87 inline_len += 1;
88 } else {
89 overflow_stack.push(current);
90 }
91 match unsafe { internal_parent::<Spec, Data>(current) } {
92 Ok((parent, _)) => current = parent,
93 Err(_) => break,
94 }
95 }
96 for &node in overflow_stack.iter().rev() {
97 unsafe { Spec::top_down(BstDataMutRef::new_unchecked(node)) };
98 }
99 while inline_len > 0 {
100 inline_len -= 1;
101 unsafe {
102 Spec::top_down(BstDataMutRef::new_unchecked(
103 *inline_stack[inline_len].assume_init_ref(),
104 ));
105 }
106 }
107
108 while let Ok((parent, node_direction)) = unsafe { internal_parent::<Spec, Data>(node) } {
109 if let Ok((_, parent_direction)) = unsafe { internal_parent::<Spec, Data>(parent) } {
110 if node_direction == parent_direction {
111 unsafe { rotate::<Spec, Data>(parent) };
112 } else {
113 unsafe { rotate::<Spec, Data>(node) };
114 }
115 }
116 unsafe { rotate::<Spec, Data>(node) };
117 }
118 unsafe { Spec::bottom_up(BstDataMutRef::new_unchecked(node)) };
119 current
120 }