unsafe fn rotate_at<Spec, Data>(
node: BstNodePtr<<Spec as BstSpec>::Data, <Spec as BstSpec>::Parent>,
parent: BstNodePtr<<Spec as BstSpec>::Data, <Spec as BstSpec>::Parent>,
direction: usize,
)where
Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,Examples found in repository?
crates/competitive/src/data_structure/splay_operations.rs (line 64)
53 pub unsafe fn rotate<Spec, Data>(mut node: NodePtr<Spec>)
54 where
55 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
56 {
57 let (parent, direction) = unsafe { internal_parent::<Spec, Data>(node) }
58 .expect("an auxiliary root cannot be rotated");
59 unsafe {
60 node.as_mut().parent.parent = parent.as_ref().parent.parent;
61 if let Ok((mut grandparent, direction)) = internal_parent::<Spec, Data>(parent) {
62 grandparent.as_mut().child[direction] = Some(node);
63 }
64 rotate_at::<Spec, Data>(node, parent, direction);
65 Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
66 }
67 }
68
69 /// Moves `node` to the root of its auxiliary tree and returns the previous root.
70 ///
71 /// # Safety
72 ///
73 /// `node` and every pointer reachable through its auxiliary-parent chain must
74 /// refer to live nodes of the same tree.
75 #[inline(always)]
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 }
121
122 /// Moves `node` to the root by propagating only the nodes involved in each rotation and
123 /// returns the previous root.
124 ///
125 /// # Safety
126 ///
127 /// `node` and every pointer reachable through its auxiliary-parent chain must refer to live
128 /// nodes of the same tree. Propagating an ancestor after its descendant must be valid for
129 /// `Spec`.
130 #[inline(always)]
131 pub unsafe fn splay_with_local_top_down<Spec, Data>(mut node: NodePtr<Spec>) -> NodePtr<Spec>
132 where
133 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
134 {
135 let mut current = node;
136 unsafe { Spec::top_down(BstDataMutRef::new_unchecked(node)) };
137 while let Ok((parent, _)) = unsafe { internal_parent::<Spec, Data>(node) } {
138 match unsafe { internal_parent::<Spec, Data>(parent) } {
139 Ok((grandparent, _)) => {
140 current = grandparent;
141 unsafe {
142 Spec::top_down(BstDataMutRef::new_unchecked(grandparent));
143 Spec::top_down(BstDataMutRef::new_unchecked(parent));
144 Spec::top_down(BstDataMutRef::new_unchecked(node));
145 let node_direction = usize::from(parent.as_ref().child[1] == Some(node));
146 let parent_direction =
147 usize::from(grandparent.as_ref().child[1] == Some(parent));
148 node.as_mut().parent.parent = grandparent.as_ref().parent.parent;
149 if let Ok((mut ancestor, direction)) =
150 internal_parent::<Spec, Data>(grandparent)
151 {
152 ancestor.as_mut().child[direction] = Some(node);
153 }
154 if node_direction == parent_direction {
155 rotate_at::<Spec, Data>(parent, grandparent, parent_direction);
156 rotate_at::<Spec, Data>(node, parent, node_direction);
157 Spec::bottom_up(BstDataMutRef::new_unchecked(grandparent));
158 Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
159 } else {
160 rotate_at::<Spec, Data>(node, parent, node_direction);
161 rotate_at::<Spec, Data>(node, grandparent, parent_direction);
162 Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
163 Spec::bottom_up(BstDataMutRef::new_unchecked(grandparent));
164 }
165 }
166 }
167 Err(ancestor) => {
168 current = parent;
169 unsafe {
170 Spec::top_down(BstDataMutRef::new_unchecked(parent));
171 Spec::top_down(BstDataMutRef::new_unchecked(node));
172 let direction = usize::from(parent.as_ref().child[1] == Some(node));
173 node.as_mut().parent.parent = ancestor;
174 rotate_at::<Spec, Data>(node, parent, direction);
175 Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
176 }
177 }
178 }
179 }
180 unsafe { Spec::bottom_up(BstDataMutRef::new_unchecked(node)) };
181 current
182 }