Struct LinkCutBstSpec

Source

struct LinkCutBstSpec<S>(PhantomData<fn() -> S>);

Tuple Fields§

§0: PhantomData<fn() -> S>

Implementations§

Source §

impl<S> LinkCutBstSpec<S>
where S: LinkCutTreeSpec,

Source

unsafe fn toggle( node: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, )

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 105)

99    fn top_down(mut node: BstDataMutRef<'_, Self>) {
100        let pointer = node.node;
101        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
102            node.data_mut().index_and_reverse &= !1;
103            let children = unsafe { pointer.as_ref().child };
104            for child in children.into_iter().flatten() {
105                unsafe { Self::toggle(child) };
106            }
107        }
108        let children = unsafe { pointer.as_ref().child };
109        let data = unsafe { &mut (*pointer.as_ptr()).data.inner };
110        let children =
111            children.map(|child| child.map(|child| unsafe { &mut (*child.as_ptr()).data.inner }));
112        S::top_down(data, children);
113    }
114
115    #[inline]
116    fn bottom_up(node: BstDataMutRef<'_, Self>) {
117        let pointer = node.node;
118        let children = unsafe { pointer.as_ref().child };
119        let data = unsafe { &mut (*pointer.as_ptr()).data.inner };
120        let children =
121            children.map(|child| child.map(|child| unsafe { &(*child.as_ptr()).data.inner }));
122        S::bottom_up(data, children);
123    }
124
125    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
126        unreachable!("link-cut trees do not merge auxiliary trees through BstSpec")
127    }
128
129    fn split<Seeker>(
130        _node: Option<BstRoot<Self>>,
131        _seeker: Seeker,
132        _equal_side: EqualSide,
133    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
134    where
135        Seeker: BstSeeker<Spec = Self>,
136    {
137        unreachable!("link-cut trees do not split auxiliary trees through BstSpec")
138    }
139}
140
141/// A link-cut forest with stable insertion-order node identifiers.
142///
143/// Its dynamic-tree operations take amortized `O(log n)` time when the spec
144/// hooks take constant time.
145pub struct LinkCutTree<S>
146where
147    S: LinkCutTreeSpec,
148{
149    nodes: Vec<LinkCutPtr<S>>,
150    allocator: MemoryPool<LinkCutNode<S>>,
151}
152
153impl<S> LinkCutTree<S>
154where
155    S: LinkCutTreeSpec,
156{
157    pub fn with_capacity(capacity: usize) -> Self {
158        Self {
159            nodes: Vec::with_capacity(capacity),
160            allocator: MemoryPool::with_capacity(capacity),
161        }
162    }
163
164    /// `edges` must form a tree over the values in iteration order.
165    pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
166    where
167        T: IntoIterator<Item = S::Value>,
168    {
169        let tree: Self = values.into_iter().collect();
170        for (child, parent, preferred) in
171            splay_operations::rooted_heavy_order(tree.nodes.len(), edges)
172                .into_iter()
173                .rev()
174        {
175            let child = tree.node(child);
176            let mut parent = tree.node(parent);
177            unsafe {
178                (*child.as_ptr()).parent.parent = Some(parent);
179                if preferred {
180                    parent.as_mut().child[1] = Some(child);
181                } else {
182                    LinkCutBstSpec::<S>::with_two_inner_mut(parent, child, S::attach_virtual);
183                }
184                Self::pull(parent);
185            }
186        }
187        tree
188    }
189
190    pub fn add_node(&mut self, value: S::Value) -> usize {
191        let index = self.nodes.len();
192        let node = self.allocator.allocate(BstNode::new(LinkCutData {
193            inner: S::new(value),
194            index_and_reverse: index << 1,
195        }));
196        self.nodes.push(node);
197        index
198    }
199
200    #[inline]
201    fn node(&self, index: usize) -> LinkCutPtr<S> {
202        self.nodes[index]
203    }
204
205    #[inline]
206    unsafe fn pull(node: LinkCutPtr<S>) {
207        unsafe {
208            LinkCutBstSpec::<S>::bottom_up(BstDataMutRef::new_unchecked(node));
209        }
210    }
211
212    #[inline]
213    unsafe fn splay(node: LinkCutPtr<S>) {
214        let root = if S::ROOT_TO_NODE_TOP_DOWN {
215            unsafe {
216                splay_operations::with_parent::splay::<LinkCutBstSpec<S>, LinkCutData<S>>(node)
217            }
218        } else {
219            unsafe {
220                splay_operations::with_parent::splay_with_local_top_down::<
221                    LinkCutBstSpec<S>,
222                    LinkCutData<S>,
223                >(node)
224            }
225        };
226        if root != node {
227            unsafe {
228                LinkCutBstSpec::<S>::with_two_inner_mut(root, node, S::transfer_path_parent);
229            }
230        }
231    }
232
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    }
255
256    pub fn get(&mut self, node: usize) -> &S::Value {
257        let node = self.node(node);
258        Self::access_node(node);
259        unsafe { S::value(&node.as_ref().data.inner) }
260    }
261
262    pub fn set(&mut self, node: usize, value: S::Value) {
263        self.modify(node, |_| value);
264    }
265
266    pub fn modify<F>(&mut self, node: usize, f: F)
267    where
268        F: FnOnce(&S::Value) -> S::Value,
269    {
270        let node = self.node(node);
271        if S::MODIFY_REQUIRES_ACCESS {
272            Self::access_node(node);
273        } else {
274            unsafe { Self::splay(node) };
275        }
276        unsafe {
277            let data = &mut (*node.as_ptr()).data.inner;
278            *S::value_mut(data) = f(S::value(data));
279            Self::pull(node);
280        }
281    }
282
283    pub fn reroot(&mut self, node: usize) {
284        let node = self.node(node);
285        Self::access_node(node);
286        unsafe { LinkCutBstSpec::<S>::toggle(node) };
287    }

Source

unsafe fn with_two_inner_mut<R>( left: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, right: NonNull<BstNode<LinkCutData<S>, WithParent<LinkCutData<S>>>>, f: impl FnOnce(&mut S::Data, &mut S::Data) -> R, ) -> R

Examples found in repository ?

crates/competitive/src/tree/link_cut_tree.rs (line 182)

165    pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
166    where
167        T: IntoIterator<Item = S::Value>,
168    {
169        let tree: Self = values.into_iter().collect();
170        for (child, parent, preferred) in
171            splay_operations::rooted_heavy_order(tree.nodes.len(), edges)
172                .into_iter()
173                .rev()
174        {
175            let child = tree.node(child);
176            let mut parent = tree.node(parent);
177            unsafe {
178                (*child.as_ptr()).parent.parent = Some(parent);
179                if preferred {
180                    parent.as_mut().child[1] = Some(child);
181                } else {
182                    LinkCutBstSpec::<S>::with_two_inner_mut(parent, child, S::attach_virtual);
183                }
184                Self::pull(parent);
185            }
186        }
187        tree
188    }
189
190    pub fn add_node(&mut self, value: S::Value) -> usize {
191        let index = self.nodes.len();
192        let node = self.allocator.allocate(BstNode::new(LinkCutData {
193            inner: S::new(value),
194            index_and_reverse: index << 1,
195        }));
196        self.nodes.push(node);
197        index
198    }
199
200    #[inline]
201    fn node(&self, index: usize) -> LinkCutPtr<S> {
202        self.nodes[index]
203    }
204
205    #[inline]
206    unsafe fn pull(node: LinkCutPtr<S>) {
207        unsafe {
208            LinkCutBstSpec::<S>::bottom_up(BstDataMutRef::new_unchecked(node));
209        }
210    }
211
212    #[inline]
213    unsafe fn splay(node: LinkCutPtr<S>) {
214        let root = if S::ROOT_TO_NODE_TOP_DOWN {
215            unsafe {
216                splay_operations::with_parent::splay::<LinkCutBstSpec<S>, LinkCutData<S>>(node)
217            }
218        } else {
219            unsafe {
220                splay_operations::with_parent::splay_with_local_top_down::<
221                    LinkCutBstSpec<S>,
222                    LinkCutData<S>,
223                >(node)
224            }
225        };
226        if root != node {
227            unsafe {
228                LinkCutBstSpec::<S>::with_two_inner_mut(root, node, S::transfer_path_parent);
229            }
230        }
231    }
232
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    }
255
256    pub fn get(&mut self, node: usize) -> &S::Value {
257        let node = self.node(node);
258        Self::access_node(node);
259        unsafe { S::value(&node.as_ref().data.inner) }
260    }
261
262    pub fn set(&mut self, node: usize, value: S::Value) {
263        self.modify(node, |_| value);
264    }
265
266    pub fn modify<F>(&mut self, node: usize, f: F)
267    where
268        F: FnOnce(&S::Value) -> S::Value,
269    {
270        let node = self.node(node);
271        if S::MODIFY_REQUIRES_ACCESS {
272            Self::access_node(node);
273        } else {
274            unsafe { Self::splay(node) };
275        }
276        unsafe {
277            let data = &mut (*node.as_ptr()).data.inner;
278            *S::value_mut(data) = f(S::value(data));
279            Self::pull(node);
280        }
281    }
282
283    pub fn reroot(&mut self, node: usize) {
284        let node = self.node(node);
285        Self::access_node(node);
286        unsafe { LinkCutBstSpec::<S>::toggle(node) };
287    }
288
289    /// `child` and `parent` must belong to different trees.
290    pub fn link(&mut self, child: usize, parent: usize) {
291        assert_ne!(child, parent);
292        self.reroot(child);
293        let child = self.node(child);
294        let parent = self.node(parent);
295        Self::access_node(parent);
296        unsafe {
297            (*child.as_ptr()).parent.parent = Some(parent);
298            LinkCutBstSpec::<S>::with_two_inner_mut(parent, child, S::attach_virtual);
299            Self::pull(parent);
300        }
301    }