Skip to main content

TopBstSpec

competitive::tree::top_tree

Struct TopBstSpec 

Source 
struct TopBstSpec<S, A>(PhantomData<fn() -> (S, A)>);

Tuple Fields§

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

Implementations§

Source§

impl<S, A> TopBstSpec<S, A>
where S: TopTreeSpec, A: TopTreeAction<S>,

Source

fn is_unit(action: &A::Action) -> bool

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 136)
135    unsafe fn apply_all(mut node: TopPtr<S, A>, action: &A::Action) {
136        if Self::is_unit(action) {
137            return;
138        }
139        let data = unsafe { &mut node.as_mut().data };
140        Self::compose(&mut data.heavy_action, action);
141        Self::compose(&mut data.light_action, action);
142        A::act_info(&mut data.info, action);
143        A::act_path(&mut data.sum, action);
144        A::act_path_light(&mut data.sum, action);
145    }
146}
147
148impl<S, A> BstSpec for TopBstSpec<S, A>
149where
150    S: TopTreeSpec,
151    A: TopTreeAction<S>,
152{
153    type Parent = WithParent<Self::Data>;
154    type Data = TopTreeData<S, A>;
155
156    #[inline]
157    fn top_down(mut node: BstDataMutRef<'_, Self>) {
158        let pointer = node.node;
159        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
160            node.data_mut().index_and_reverse &= !1;
161            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
162                unsafe { Self::toggle(child) };
163            }
164        }
165
166        if !Self::is_unit(&node.reborrow().into_data().heavy_action) {
167            let action = replace(
168                &mut node.data_mut().heavy_action,
169                <A::ActionMonoid as Unital>::unit(),
170            );
171            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
172                unsafe { Self::apply_heavy(child, &action) };
173            }
174        }
175        if !Self::is_unit(&node.reborrow().into_data().light_action) {
176            let action = replace(
177                &mut node.data_mut().light_action,
178                <A::ActionMonoid as Unital>::unit(),
179            );
180            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
181                unsafe { Self::apply_light(child, &action) };
182            }
183            if let Some(light) = node.reborrow().into_data().light {
184                unsafe { RakeBstSpec::<S, A>::apply(light, &action) };
185            }
186        }
187    }
188
189    #[inline]
190    fn bottom_up(node: BstDataMutRef<'_, Self>) {
191        let pointer = node.node;
192        let data = unsafe { &mut (*pointer.as_ptr()).data };
193        let mut sum = if let Some(light) = data.light {
194            S::add_vertex(unsafe { &light.as_ref().data.sum }, &data.info)
195        } else {
196            S::vertex(&data.info)
197        };
198        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
199            sum = S::compress(unsafe { &left.as_ref().data.sum }, &sum);
200        }
201        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
202            sum = S::compress(&sum, unsafe { &right.as_ref().data.sum });
203        }
204        data.sum = sum;
205    }
206
207    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
208        unreachable!("top trees do not merge auxiliary trees through BstSpec")
209    }
210
211    fn split<Seeker>(
212        _node: Option<BstRoot<Self>>,
213        _seeker: Seeker,
214        _equal_side: EqualSide,
215    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
216    where
217        Seeker: BstSeeker<Spec = Self>,
218    {
219        unreachable!("top trees do not split auxiliary trees through BstSpec")
220    }
221}
222
223impl<S, A> RakeBstSpec<S, A>
224where
225    S: TopTreeSpec,
226    A: TopTreeAction<S>,
227{
228    #[inline]
229    unsafe fn apply(mut node: RakePtr<S, A>, action: &A::Action) {
230        let data = unsafe { &mut node.as_mut().data };
231        A::act_point(&mut data.key, action);
232        A::act_point(&mut data.sum, action);
233        TopBstSpec::<S, A>::compose(&mut data.action, action);
234        TopBstSpec::<S, A>::compose(&mut data.buffer, action);
235    }
236}
237
238impl<S, A> BstSpec for RakeBstSpec<S, A>
239where
240    S: TopTreeSpec,
241    A: TopTreeAction<S>,
242{
243    type Parent = WithParent<Self::Data>;
244    type Data = RakeData<S, A>;
245
246    #[inline]
247    fn top_down(mut node: BstDataMutRef<'_, Self>) {
248        if TopBstSpec::<S, A>::is_unit(&node.reborrow().into_data().action) {
249            return;
250        }
251        let pointer = node.node;
252        let action = replace(
253            &mut node.data_mut().action,
254            <A::ActionMonoid as Unital>::unit(),
255        );
256        for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
257            unsafe { Self::apply(child, &action) };
258        }
259    }
260
261    #[inline]
262    fn bottom_up(node: BstDataMutRef<'_, Self>) {
263        let pointer = node.node;
264        let data = unsafe { &mut (*pointer.as_ptr()).data };
265        let mut sum = data.key.clone();
266        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
267            sum = S::rake(&sum, unsafe { &left.as_ref().data.sum });
268        }
269        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
270            sum = S::rake(&sum, unsafe { &right.as_ref().data.sum });
271        }
272        data.sum = sum;
273    }
274
275    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
276        unreachable!("rake trees use their dedicated merge operation")
277    }
278
279    fn split<Seeker>(
280        _node: Option<BstRoot<Self>>,
281        _seeker: Seeker,
282        _equal_side: EqualSide,
283    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
284    where
285        Seeker: BstSeeker<Spec = Self>,
286    {
287        unreachable!("rake trees do not use BstSpec::split")
288    }
289}
290
291/// A self-adjusting top tree, also called a strong link-cut tree.
292///
293/// This is not a classical worst-case-balanced top tree. Circular order and
294/// `select` are not supported.
295pub struct TopTree<S, A = NoTopTreeAction>
296where
297    S: TopTreeSpec,
298    A: TopTreeAction<S>,
299{
300    nodes: Vec<TopPtr<S, A>>,
301    node_allocator: MemoryPool<TopNode<S, A>>,
302    rake_allocator: MemoryPool<RakeNode<S, A>>,
303}
304
305impl<S, A> TopTree<S, A>
306where
307    S: TopTreeSpec,
308    A: TopTreeAction<S>,
309{
310    pub fn with_capacity(capacity: usize) -> Self {
311        Self {
312            nodes: Vec::with_capacity(capacity),
313            node_allocator: MemoryPool::with_capacity(capacity),
314            rake_allocator: MemoryPool::with_capacity(capacity),
315        }
316    }
317
318    /// `edges` must form a tree over the values in iteration order.
319    pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
320    where
321        T: IntoIterator<Item = S::Info>,
322    {
323        let mut tree: Self = values.into_iter().collect();
324        for (child, parent, preferred) in
325            splay_operations::rooted_heavy_order(tree.nodes.len(), edges)
326                .into_iter()
327                .rev()
328        {
329            let child = tree.node(child);
330            let mut parent = tree.node(parent);
331            unsafe {
332                (*child.as_ptr()).parent.parent = Some(parent);
333                if preferred {
334                    parent.as_mut().child[1] = Some(child);
335                } else {
336                    let point = S::add_edge(&child.as_ref().data.sum);
337                    let (light, entry) = tree.rake_insert(parent.as_ref().data.light, point);
338                    parent.as_mut().data.light = Some(light);
339                    (*child.as_ptr()).data.belong = Some(entry);
340                }
341                Self::pull_top(parent);
342            }
343        }
344        tree
345    }
346
347    pub fn add_node(&mut self, info: S::Info) -> usize {
348        let index = self.nodes.len();
349        let sum = S::vertex(&info);
350        let node = self.node_allocator.allocate(BstNode::new(TopTreeData {
351            info,
352            sum,
353            light: None,
354            belong: None,
355            heavy_action: <A::ActionMonoid as Unital>::unit(),
356            light_action: <A::ActionMonoid as Unital>::unit(),
357            index_and_reverse: index << 1,
358        }));
359        self.nodes.push(node);
360        index
361    }
362
363    fn node(&self, index: usize) -> TopPtr<S, A> {
364        self.nodes[index]
365    }
366
367    #[inline]
368    unsafe fn pull_top(node: TopPtr<S, A>) {
369        unsafe { TopBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
370    }
371
372    #[inline]
373    unsafe fn pull_rake(node: RakePtr<S, A>) {
374        unsafe { RakeBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
375    }
376
377    #[inline]
378    unsafe fn splay_top(node: TopPtr<S, A>) {
379        let root = if A::ROOT_TO_NODE_TOP_DOWN {
380            unsafe {
381                splay_operations::with_parent::splay::<TopBstSpec<S, A>, TopTreeData<S, A>>(node)
382            }
383        } else {
384            unsafe {
385                splay_operations::with_parent::splay_with_local_top_down::<
386                    TopBstSpec<S, A>,
387                    TopTreeData<S, A>,
388                >(node)
389            }
390        };
391        if root != node {
392            unsafe {
393                (*node.as_ptr()).data.belong = (*root.as_ptr()).data.belong.take();
394            }
395        }
396    }
397
398    #[inline]
399    unsafe fn splay_rake(node: RakePtr<S, A>) {
400        unsafe {
401            splay_operations::with_parent::splay_with_local_top_down::<
402                RakeBstSpec<S, A>,
403                RakeData<S, A>,
404            >(node)
405        };
406    }
407
408    unsafe fn rake_rightmost(mut node: RakePtr<S, A>) -> RakePtr<S, A> {
409        loop {
410            unsafe { RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node)) };
411            match unsafe { node.as_ref().child[1] } {
412                Some(right) => node = right,
413                None => return node,
414            }
415        }
416    }
417
418    unsafe fn rake_insert(
419        &mut self,
420        root: Option<RakePtr<S, A>>,
421        key: S::Point,
422    ) -> (RakePtr<S, A>, RakePtr<S, A>) {
423        let mut node = self.rake_allocator.allocate(BstNode::new(RakeData {
424            sum: key.clone(),
425            key,
426            action: <A::ActionMonoid as Unital>::unit(),
427            buffer: <A::ActionMonoid as Unital>::unit(),
428        }));
429        if let Some(mut root) = root {
430            unsafe {
431                node.as_mut().child[0] = Some(root);
432                root.as_mut().parent.parent = Some(node);
433                Self::pull_rake(node);
434            }
435        }
436        (node, node)
437    }
438
439    unsafe fn rake_remove(
440        &mut self,
441        mut node: RakePtr<S, A>,
442    ) -> (Option<RakePtr<S, A>>, A::Action) {
443        unsafe {
444            Self::splay_rake(node);
445            RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node));
446        }
447        let left = unsafe { node.as_mut().child[0].take() };
448        let right = unsafe { node.as_mut().child[1].take() };
449        for mut child in [left, right].into_iter().flatten() {
450            unsafe { child.as_mut().parent.parent = None };
451        }
452        let root = match (left, right) {
453            (None, right) => right,
454            (left, None) => left,
455            (Some(left), Some(right)) => {
456                let mut root = unsafe { Self::rake_rightmost(left) };
457                unsafe {
458                    Self::splay_rake(root);
459                    root.as_mut().child[1] = Some(right);
460                    (*right.as_ptr()).parent.parent = Some(root);
461                    Self::pull_rake(root);
462                }
463                Some(root)
464            }
465        };
466        let node = self.rake_allocator.deallocate(node);
467        (root, node.data.buffer)
468    }
469
470    fn access_node(&mut self, node: TopPtr<S, A>) {
471        unsafe {
472            let mut previous: Option<TopPtr<S, A>> = None;
473            let mut current = Some(node);
474            while let Some(mut cursor) = current {
475                Self::splay_top(cursor);
476                let next = cursor.as_ref().parent.parent;
477                if let Some(right) = cursor.as_mut().child[1].take() {
478                    let point = S::add_edge(&right.as_ref().data.sum);
479                    let (light, entry) = self.rake_insert(cursor.as_ref().data.light, point);
480                    cursor.as_mut().data.light = Some(light);
481                    (*right.as_ptr()).data.belong = Some(entry);
482                }
483                if let Some(previous) = previous {
484                    let entry = (*previous.as_ptr())
485                        .data
486                        .belong
487                        .take()
488                        .expect("a virtual path must have a rake-tree entry");
489                    let (light, action) = self.rake_remove(entry);
490                    cursor.as_mut().data.light = light;
491                    TopBstSpec::<S, A>::apply_all(previous, &action);
492                    cursor.as_mut().child[1] = Some(previous);
493                    (*previous.as_ptr()).parent.parent = Some(cursor);
494                }
495                Self::pull_top(cursor);
496                previous = Some(cursor);
497                current = next;
498            }
499            Self::splay_top(node);
500        }
501    }
502
503    pub fn get(&mut self, node: usize) -> &S::Info {
504        let node = self.node(node);
505        self.access_node(node);
506        unsafe { &node.as_ref().data.info }
507    }
508
509    pub fn set(&mut self, node: usize, info: S::Info) {
510        self.modify(node, |_| info);
511    }
512
513    pub fn modify<F>(&mut self, node: usize, f: F)
514    where
515        F: FnOnce(&S::Info) -> S::Info,
516    {
517        let mut node = self.node(node);
518        self.access_node(node);
519        unsafe {
520            node.as_mut().data.info = f(&node.as_ref().data.info);
521            Self::pull_top(node);
522        }
523    }
524
525    pub fn reroot(&mut self, node: usize) {
526        let node = self.node(node);
527        self.access_node(node);
528        unsafe { TopBstSpec::<S, A>::toggle(node) };
529    }
530
531    /// `child` and `parent` must belong to different trees.
532    pub fn link(&mut self, child: usize, parent: usize) {
533        assert_ne!(child, parent);
534        self.reroot(child);
535        let child = self.node(child);
536        let mut parent = self.node(parent);
537        self.access_node(parent);
538        unsafe {
539            (*child.as_ptr()).parent.parent = Some(parent);
540            let point = S::add_edge(&child.as_ref().data.sum);
541            let (light, entry) = self.rake_insert(parent.as_ref().data.light, point);
542            parent.as_mut().data.light = Some(light);
543            (*child.as_ptr()).data.belong = Some(entry);
544            Self::pull_top(parent);
545        }
546    }
547
548    /// `(u, v)` must be an edge.
549    pub fn cut(&mut self, u: usize, v: usize) {
550        assert_ne!(u, v);
551        self.reroot(u);
552        let mut v = self.node(v);
553        self.access_node(v);
554        unsafe {
555            let mut left = v.as_mut().child[0]
556                .take()
557                .expect("the specified edge must exist");
558            left.as_mut().parent.parent = None;
559            Self::pull_top(v);
560        }
561    }
562
563    pub fn root(&mut self, node: usize) -> usize {
564        let mut root = self.node(node);
565        self.access_node(root);
566        unsafe {
567            loop {
568                TopBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(root));
569                match root.as_ref().child[0] {
570                    Some(left) => root = left,
571                    None => break,
572                }
573            }
574            Self::splay_top(root);
575            root.as_ref().data.index_and_reverse >> 1
576        }
577    }
578
579    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
580        self.root(u) == self.root(v)
581    }
582
583    /// `u` and `v` must be connected.
584    pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path {
585        self.reroot(u);
586        let v = self.node(v);
587        self.access_node(v);
588        unsafe { v.as_ref().data.sum.clone() }
589    }
590
591    /// `u` and `v` must be connected.
592    pub fn update_path(&mut self, u: usize, v: usize, action: &A::Action) {
593        self.reroot(u);
594        let v = self.node(v);
595        self.access_node(v);
596        if !TopBstSpec::<S, A>::is_unit(action) {
597            unsafe { TopBstSpec::<S, A>::apply_heavy(v, action) };
598        }
599    }
Source

fn compose(target: &mut A::Action, action: &A::Action)

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 122)
120    unsafe fn apply_heavy(mut node: TopPtr<S, A>, action: &A::Action) {
121        let data = unsafe { &mut node.as_mut().data };
122        Self::compose(&mut data.heavy_action, action);
123        A::act_info(&mut data.info, action);
124        A::act_path(&mut data.sum, action);
125    }
126
127    #[inline]
128    unsafe fn apply_light(mut node: TopPtr<S, A>, action: &A::Action) {
129        let data = unsafe { &mut node.as_mut().data };
130        Self::compose(&mut data.light_action, action);
131        A::act_path_light(&mut data.sum, action);
132    }
133
134    #[inline]
135    unsafe fn apply_all(mut node: TopPtr<S, A>, action: &A::Action) {
136        if Self::is_unit(action) {
137            return;
138        }
139        let data = unsafe { &mut node.as_mut().data };
140        Self::compose(&mut data.heavy_action, action);
141        Self::compose(&mut data.light_action, action);
142        A::act_info(&mut data.info, action);
143        A::act_path(&mut data.sum, action);
144        A::act_path_light(&mut data.sum, action);
145    }
146}
147
148impl<S, A> BstSpec for TopBstSpec<S, A>
149where
150    S: TopTreeSpec,
151    A: TopTreeAction<S>,
152{
153    type Parent = WithParent<Self::Data>;
154    type Data = TopTreeData<S, A>;
155
156    #[inline]
157    fn top_down(mut node: BstDataMutRef<'_, Self>) {
158        let pointer = node.node;
159        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
160            node.data_mut().index_and_reverse &= !1;
161            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
162                unsafe { Self::toggle(child) };
163            }
164        }
165
166        if !Self::is_unit(&node.reborrow().into_data().heavy_action) {
167            let action = replace(
168                &mut node.data_mut().heavy_action,
169                <A::ActionMonoid as Unital>::unit(),
170            );
171            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
172                unsafe { Self::apply_heavy(child, &action) };
173            }
174        }
175        if !Self::is_unit(&node.reborrow().into_data().light_action) {
176            let action = replace(
177                &mut node.data_mut().light_action,
178                <A::ActionMonoid as Unital>::unit(),
179            );
180            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
181                unsafe { Self::apply_light(child, &action) };
182            }
183            if let Some(light) = node.reborrow().into_data().light {
184                unsafe { RakeBstSpec::<S, A>::apply(light, &action) };
185            }
186        }
187    }
188
189    #[inline]
190    fn bottom_up(node: BstDataMutRef<'_, Self>) {
191        let pointer = node.node;
192        let data = unsafe { &mut (*pointer.as_ptr()).data };
193        let mut sum = if let Some(light) = data.light {
194            S::add_vertex(unsafe { &light.as_ref().data.sum }, &data.info)
195        } else {
196            S::vertex(&data.info)
197        };
198        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
199            sum = S::compress(unsafe { &left.as_ref().data.sum }, &sum);
200        }
201        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
202            sum = S::compress(&sum, unsafe { &right.as_ref().data.sum });
203        }
204        data.sum = sum;
205    }
206
207    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
208        unreachable!("top trees do not merge auxiliary trees through BstSpec")
209    }
210
211    fn split<Seeker>(
212        _node: Option<BstRoot<Self>>,
213        _seeker: Seeker,
214        _equal_side: EqualSide,
215    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
216    where
217        Seeker: BstSeeker<Spec = Self>,
218    {
219        unreachable!("top trees do not split auxiliary trees through BstSpec")
220    }
221}
222
223impl<S, A> RakeBstSpec<S, A>
224where
225    S: TopTreeSpec,
226    A: TopTreeAction<S>,
227{
228    #[inline]
229    unsafe fn apply(mut node: RakePtr<S, A>, action: &A::Action) {
230        let data = unsafe { &mut node.as_mut().data };
231        A::act_point(&mut data.key, action);
232        A::act_point(&mut data.sum, action);
233        TopBstSpec::<S, A>::compose(&mut data.action, action);
234        TopBstSpec::<S, A>::compose(&mut data.buffer, action);
235    }
Source

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

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 162)
157    fn top_down(mut node: BstDataMutRef<'_, Self>) {
158        let pointer = node.node;
159        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
160            node.data_mut().index_and_reverse &= !1;
161            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
162                unsafe { Self::toggle(child) };
163            }
164        }
165
166        if !Self::is_unit(&node.reborrow().into_data().heavy_action) {
167            let action = replace(
168                &mut node.data_mut().heavy_action,
169                <A::ActionMonoid as Unital>::unit(),
170            );
171            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
172                unsafe { Self::apply_heavy(child, &action) };
173            }
174        }
175        if !Self::is_unit(&node.reborrow().into_data().light_action) {
176            let action = replace(
177                &mut node.data_mut().light_action,
178                <A::ActionMonoid as Unital>::unit(),
179            );
180            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
181                unsafe { Self::apply_light(child, &action) };
182            }
183            if let Some(light) = node.reborrow().into_data().light {
184                unsafe { RakeBstSpec::<S, A>::apply(light, &action) };
185            }
186        }
187    }
188
189    #[inline]
190    fn bottom_up(node: BstDataMutRef<'_, Self>) {
191        let pointer = node.node;
192        let data = unsafe { &mut (*pointer.as_ptr()).data };
193        let mut sum = if let Some(light) = data.light {
194            S::add_vertex(unsafe { &light.as_ref().data.sum }, &data.info)
195        } else {
196            S::vertex(&data.info)
197        };
198        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
199            sum = S::compress(unsafe { &left.as_ref().data.sum }, &sum);
200        }
201        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
202            sum = S::compress(&sum, unsafe { &right.as_ref().data.sum });
203        }
204        data.sum = sum;
205    }
206
207    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
208        unreachable!("top trees do not merge auxiliary trees through BstSpec")
209    }
210
211    fn split<Seeker>(
212        _node: Option<BstRoot<Self>>,
213        _seeker: Seeker,
214        _equal_side: EqualSide,
215    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
216    where
217        Seeker: BstSeeker<Spec = Self>,
218    {
219        unreachable!("top trees do not split auxiliary trees through BstSpec")
220    }
221}
222
223impl<S, A> RakeBstSpec<S, A>
224where
225    S: TopTreeSpec,
226    A: TopTreeAction<S>,
227{
228    #[inline]
229    unsafe fn apply(mut node: RakePtr<S, A>, action: &A::Action) {
230        let data = unsafe { &mut node.as_mut().data };
231        A::act_point(&mut data.key, action);
232        A::act_point(&mut data.sum, action);
233        TopBstSpec::<S, A>::compose(&mut data.action, action);
234        TopBstSpec::<S, A>::compose(&mut data.buffer, action);
235    }
236}
237
238impl<S, A> BstSpec for RakeBstSpec<S, A>
239where
240    S: TopTreeSpec,
241    A: TopTreeAction<S>,
242{
243    type Parent = WithParent<Self::Data>;
244    type Data = RakeData<S, A>;
245
246    #[inline]
247    fn top_down(mut node: BstDataMutRef<'_, Self>) {
248        if TopBstSpec::<S, A>::is_unit(&node.reborrow().into_data().action) {
249            return;
250        }
251        let pointer = node.node;
252        let action = replace(
253            &mut node.data_mut().action,
254            <A::ActionMonoid as Unital>::unit(),
255        );
256        for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
257            unsafe { Self::apply(child, &action) };
258        }
259    }
260
261    #[inline]
262    fn bottom_up(node: BstDataMutRef<'_, Self>) {
263        let pointer = node.node;
264        let data = unsafe { &mut (*pointer.as_ptr()).data };
265        let mut sum = data.key.clone();
266        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
267            sum = S::rake(&sum, unsafe { &left.as_ref().data.sum });
268        }
269        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
270            sum = S::rake(&sum, unsafe { &right.as_ref().data.sum });
271        }
272        data.sum = sum;
273    }
274
275    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
276        unreachable!("rake trees use their dedicated merge operation")
277    }
278
279    fn split<Seeker>(
280        _node: Option<BstRoot<Self>>,
281        _seeker: Seeker,
282        _equal_side: EqualSide,
283    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
284    where
285        Seeker: BstSeeker<Spec = Self>,
286    {
287        unreachable!("rake trees do not use BstSpec::split")
288    }
289}
290
291/// A self-adjusting top tree, also called a strong link-cut tree.
292///
293/// This is not a classical worst-case-balanced top tree. Circular order and
294/// `select` are not supported.
295pub struct TopTree<S, A = NoTopTreeAction>
296where
297    S: TopTreeSpec,
298    A: TopTreeAction<S>,
299{
300    nodes: Vec<TopPtr<S, A>>,
301    node_allocator: MemoryPool<TopNode<S, A>>,
302    rake_allocator: MemoryPool<RakeNode<S, A>>,
303}
304
305impl<S, A> TopTree<S, A>
306where
307    S: TopTreeSpec,
308    A: TopTreeAction<S>,
309{
310    pub fn with_capacity(capacity: usize) -> Self {
311        Self {
312            nodes: Vec::with_capacity(capacity),
313            node_allocator: MemoryPool::with_capacity(capacity),
314            rake_allocator: MemoryPool::with_capacity(capacity),
315        }
316    }
317
318    /// `edges` must form a tree over the values in iteration order.
319    pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
320    where
321        T: IntoIterator<Item = S::Info>,
322    {
323        let mut tree: Self = values.into_iter().collect();
324        for (child, parent, preferred) in
325            splay_operations::rooted_heavy_order(tree.nodes.len(), edges)
326                .into_iter()
327                .rev()
328        {
329            let child = tree.node(child);
330            let mut parent = tree.node(parent);
331            unsafe {
332                (*child.as_ptr()).parent.parent = Some(parent);
333                if preferred {
334                    parent.as_mut().child[1] = Some(child);
335                } else {
336                    let point = S::add_edge(&child.as_ref().data.sum);
337                    let (light, entry) = tree.rake_insert(parent.as_ref().data.light, point);
338                    parent.as_mut().data.light = Some(light);
339                    (*child.as_ptr()).data.belong = Some(entry);
340                }
341                Self::pull_top(parent);
342            }
343        }
344        tree
345    }
346
347    pub fn add_node(&mut self, info: S::Info) -> usize {
348        let index = self.nodes.len();
349        let sum = S::vertex(&info);
350        let node = self.node_allocator.allocate(BstNode::new(TopTreeData {
351            info,
352            sum,
353            light: None,
354            belong: None,
355            heavy_action: <A::ActionMonoid as Unital>::unit(),
356            light_action: <A::ActionMonoid as Unital>::unit(),
357            index_and_reverse: index << 1,
358        }));
359        self.nodes.push(node);
360        index
361    }
362
363    fn node(&self, index: usize) -> TopPtr<S, A> {
364        self.nodes[index]
365    }
366
367    #[inline]
368    unsafe fn pull_top(node: TopPtr<S, A>) {
369        unsafe { TopBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
370    }
371
372    #[inline]
373    unsafe fn pull_rake(node: RakePtr<S, A>) {
374        unsafe { RakeBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
375    }
376
377    #[inline]
378    unsafe fn splay_top(node: TopPtr<S, A>) {
379        let root = if A::ROOT_TO_NODE_TOP_DOWN {
380            unsafe {
381                splay_operations::with_parent::splay::<TopBstSpec<S, A>, TopTreeData<S, A>>(node)
382            }
383        } else {
384            unsafe {
385                splay_operations::with_parent::splay_with_local_top_down::<
386                    TopBstSpec<S, A>,
387                    TopTreeData<S, A>,
388                >(node)
389            }
390        };
391        if root != node {
392            unsafe {
393                (*node.as_ptr()).data.belong = (*root.as_ptr()).data.belong.take();
394            }
395        }
396    }
397
398    #[inline]
399    unsafe fn splay_rake(node: RakePtr<S, A>) {
400        unsafe {
401            splay_operations::with_parent::splay_with_local_top_down::<
402                RakeBstSpec<S, A>,
403                RakeData<S, A>,
404            >(node)
405        };
406    }
407
408    unsafe fn rake_rightmost(mut node: RakePtr<S, A>) -> RakePtr<S, A> {
409        loop {
410            unsafe { RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node)) };
411            match unsafe { node.as_ref().child[1] } {
412                Some(right) => node = right,
413                None => return node,
414            }
415        }
416    }
417
418    unsafe fn rake_insert(
419        &mut self,
420        root: Option<RakePtr<S, A>>,
421        key: S::Point,
422    ) -> (RakePtr<S, A>, RakePtr<S, A>) {
423        let mut node = self.rake_allocator.allocate(BstNode::new(RakeData {
424            sum: key.clone(),
425            key,
426            action: <A::ActionMonoid as Unital>::unit(),
427            buffer: <A::ActionMonoid as Unital>::unit(),
428        }));
429        if let Some(mut root) = root {
430            unsafe {
431                node.as_mut().child[0] = Some(root);
432                root.as_mut().parent.parent = Some(node);
433                Self::pull_rake(node);
434            }
435        }
436        (node, node)
437    }
438
439    unsafe fn rake_remove(
440        &mut self,
441        mut node: RakePtr<S, A>,
442    ) -> (Option<RakePtr<S, A>>, A::Action) {
443        unsafe {
444            Self::splay_rake(node);
445            RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node));
446        }
447        let left = unsafe { node.as_mut().child[0].take() };
448        let right = unsafe { node.as_mut().child[1].take() };
449        for mut child in [left, right].into_iter().flatten() {
450            unsafe { child.as_mut().parent.parent = None };
451        }
452        let root = match (left, right) {
453            (None, right) => right,
454            (left, None) => left,
455            (Some(left), Some(right)) => {
456                let mut root = unsafe { Self::rake_rightmost(left) };
457                unsafe {
458                    Self::splay_rake(root);
459                    root.as_mut().child[1] = Some(right);
460                    (*right.as_ptr()).parent.parent = Some(root);
461                    Self::pull_rake(root);
462                }
463                Some(root)
464            }
465        };
466        let node = self.rake_allocator.deallocate(node);
467        (root, node.data.buffer)
468    }
469
470    fn access_node(&mut self, node: TopPtr<S, A>) {
471        unsafe {
472            let mut previous: Option<TopPtr<S, A>> = None;
473            let mut current = Some(node);
474            while let Some(mut cursor) = current {
475                Self::splay_top(cursor);
476                let next = cursor.as_ref().parent.parent;
477                if let Some(right) = cursor.as_mut().child[1].take() {
478                    let point = S::add_edge(&right.as_ref().data.sum);
479                    let (light, entry) = self.rake_insert(cursor.as_ref().data.light, point);
480                    cursor.as_mut().data.light = Some(light);
481                    (*right.as_ptr()).data.belong = Some(entry);
482                }
483                if let Some(previous) = previous {
484                    let entry = (*previous.as_ptr())
485                        .data
486                        .belong
487                        .take()
488                        .expect("a virtual path must have a rake-tree entry");
489                    let (light, action) = self.rake_remove(entry);
490                    cursor.as_mut().data.light = light;
491                    TopBstSpec::<S, A>::apply_all(previous, &action);
492                    cursor.as_mut().child[1] = Some(previous);
493                    (*previous.as_ptr()).parent.parent = Some(cursor);
494                }
495                Self::pull_top(cursor);
496                previous = Some(cursor);
497                current = next;
498            }
499            Self::splay_top(node);
500        }
501    }
502
503    pub fn get(&mut self, node: usize) -> &S::Info {
504        let node = self.node(node);
505        self.access_node(node);
506        unsafe { &node.as_ref().data.info }
507    }
508
509    pub fn set(&mut self, node: usize, info: S::Info) {
510        self.modify(node, |_| info);
511    }
512
513    pub fn modify<F>(&mut self, node: usize, f: F)
514    where
515        F: FnOnce(&S::Info) -> S::Info,
516    {
517        let mut node = self.node(node);
518        self.access_node(node);
519        unsafe {
520            node.as_mut().data.info = f(&node.as_ref().data.info);
521            Self::pull_top(node);
522        }
523    }
524
525    pub fn reroot(&mut self, node: usize) {
526        let node = self.node(node);
527        self.access_node(node);
528        unsafe { TopBstSpec::<S, A>::toggle(node) };
529    }
Source

unsafe fn apply_heavy( node: NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>, action: &A::Action, )

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 172)
157    fn top_down(mut node: BstDataMutRef<'_, Self>) {
158        let pointer = node.node;
159        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
160            node.data_mut().index_and_reverse &= !1;
161            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
162                unsafe { Self::toggle(child) };
163            }
164        }
165
166        if !Self::is_unit(&node.reborrow().into_data().heavy_action) {
167            let action = replace(
168                &mut node.data_mut().heavy_action,
169                <A::ActionMonoid as Unital>::unit(),
170            );
171            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
172                unsafe { Self::apply_heavy(child, &action) };
173            }
174        }
175        if !Self::is_unit(&node.reborrow().into_data().light_action) {
176            let action = replace(
177                &mut node.data_mut().light_action,
178                <A::ActionMonoid as Unital>::unit(),
179            );
180            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
181                unsafe { Self::apply_light(child, &action) };
182            }
183            if let Some(light) = node.reborrow().into_data().light {
184                unsafe { RakeBstSpec::<S, A>::apply(light, &action) };
185            }
186        }
187    }
188
189    #[inline]
190    fn bottom_up(node: BstDataMutRef<'_, Self>) {
191        let pointer = node.node;
192        let data = unsafe { &mut (*pointer.as_ptr()).data };
193        let mut sum = if let Some(light) = data.light {
194            S::add_vertex(unsafe { &light.as_ref().data.sum }, &data.info)
195        } else {
196            S::vertex(&data.info)
197        };
198        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
199            sum = S::compress(unsafe { &left.as_ref().data.sum }, &sum);
200        }
201        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
202            sum = S::compress(&sum, unsafe { &right.as_ref().data.sum });
203        }
204        data.sum = sum;
205    }
206
207    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
208        unreachable!("top trees do not merge auxiliary trees through BstSpec")
209    }
210
211    fn split<Seeker>(
212        _node: Option<BstRoot<Self>>,
213        _seeker: Seeker,
214        _equal_side: EqualSide,
215    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
216    where
217        Seeker: BstSeeker<Spec = Self>,
218    {
219        unreachable!("top trees do not split auxiliary trees through BstSpec")
220    }
221}
222
223impl<S, A> RakeBstSpec<S, A>
224where
225    S: TopTreeSpec,
226    A: TopTreeAction<S>,
227{
228    #[inline]
229    unsafe fn apply(mut node: RakePtr<S, A>, action: &A::Action) {
230        let data = unsafe { &mut node.as_mut().data };
231        A::act_point(&mut data.key, action);
232        A::act_point(&mut data.sum, action);
233        TopBstSpec::<S, A>::compose(&mut data.action, action);
234        TopBstSpec::<S, A>::compose(&mut data.buffer, action);
235    }
236}
237
238impl<S, A> BstSpec for RakeBstSpec<S, A>
239where
240    S: TopTreeSpec,
241    A: TopTreeAction<S>,
242{
243    type Parent = WithParent<Self::Data>;
244    type Data = RakeData<S, A>;
245
246    #[inline]
247    fn top_down(mut node: BstDataMutRef<'_, Self>) {
248        if TopBstSpec::<S, A>::is_unit(&node.reborrow().into_data().action) {
249            return;
250        }
251        let pointer = node.node;
252        let action = replace(
253            &mut node.data_mut().action,
254            <A::ActionMonoid as Unital>::unit(),
255        );
256        for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
257            unsafe { Self::apply(child, &action) };
258        }
259    }
260
261    #[inline]
262    fn bottom_up(node: BstDataMutRef<'_, Self>) {
263        let pointer = node.node;
264        let data = unsafe { &mut (*pointer.as_ptr()).data };
265        let mut sum = data.key.clone();
266        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
267            sum = S::rake(&sum, unsafe { &left.as_ref().data.sum });
268        }
269        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
270            sum = S::rake(&sum, unsafe { &right.as_ref().data.sum });
271        }
272        data.sum = sum;
273    }
274
275    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
276        unreachable!("rake trees use their dedicated merge operation")
277    }
278
279    fn split<Seeker>(
280        _node: Option<BstRoot<Self>>,
281        _seeker: Seeker,
282        _equal_side: EqualSide,
283    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
284    where
285        Seeker: BstSeeker<Spec = Self>,
286    {
287        unreachable!("rake trees do not use BstSpec::split")
288    }
289}
290
291/// A self-adjusting top tree, also called a strong link-cut tree.
292///
293/// This is not a classical worst-case-balanced top tree. Circular order and
294/// `select` are not supported.
295pub struct TopTree<S, A = NoTopTreeAction>
296where
297    S: TopTreeSpec,
298    A: TopTreeAction<S>,
299{
300    nodes: Vec<TopPtr<S, A>>,
301    node_allocator: MemoryPool<TopNode<S, A>>,
302    rake_allocator: MemoryPool<RakeNode<S, A>>,
303}
304
305impl<S, A> TopTree<S, A>
306where
307    S: TopTreeSpec,
308    A: TopTreeAction<S>,
309{
310    pub fn with_capacity(capacity: usize) -> Self {
311        Self {
312            nodes: Vec::with_capacity(capacity),
313            node_allocator: MemoryPool::with_capacity(capacity),
314            rake_allocator: MemoryPool::with_capacity(capacity),
315        }
316    }
317
318    /// `edges` must form a tree over the values in iteration order.
319    pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
320    where
321        T: IntoIterator<Item = S::Info>,
322    {
323        let mut tree: Self = values.into_iter().collect();
324        for (child, parent, preferred) in
325            splay_operations::rooted_heavy_order(tree.nodes.len(), edges)
326                .into_iter()
327                .rev()
328        {
329            let child = tree.node(child);
330            let mut parent = tree.node(parent);
331            unsafe {
332                (*child.as_ptr()).parent.parent = Some(parent);
333                if preferred {
334                    parent.as_mut().child[1] = Some(child);
335                } else {
336                    let point = S::add_edge(&child.as_ref().data.sum);
337                    let (light, entry) = tree.rake_insert(parent.as_ref().data.light, point);
338                    parent.as_mut().data.light = Some(light);
339                    (*child.as_ptr()).data.belong = Some(entry);
340                }
341                Self::pull_top(parent);
342            }
343        }
344        tree
345    }
346
347    pub fn add_node(&mut self, info: S::Info) -> usize {
348        let index = self.nodes.len();
349        let sum = S::vertex(&info);
350        let node = self.node_allocator.allocate(BstNode::new(TopTreeData {
351            info,
352            sum,
353            light: None,
354            belong: None,
355            heavy_action: <A::ActionMonoid as Unital>::unit(),
356            light_action: <A::ActionMonoid as Unital>::unit(),
357            index_and_reverse: index << 1,
358        }));
359        self.nodes.push(node);
360        index
361    }
362
363    fn node(&self, index: usize) -> TopPtr<S, A> {
364        self.nodes[index]
365    }
366
367    #[inline]
368    unsafe fn pull_top(node: TopPtr<S, A>) {
369        unsafe { TopBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
370    }
371
372    #[inline]
373    unsafe fn pull_rake(node: RakePtr<S, A>) {
374        unsafe { RakeBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
375    }
376
377    #[inline]
378    unsafe fn splay_top(node: TopPtr<S, A>) {
379        let root = if A::ROOT_TO_NODE_TOP_DOWN {
380            unsafe {
381                splay_operations::with_parent::splay::<TopBstSpec<S, A>, TopTreeData<S, A>>(node)
382            }
383        } else {
384            unsafe {
385                splay_operations::with_parent::splay_with_local_top_down::<
386                    TopBstSpec<S, A>,
387                    TopTreeData<S, A>,
388                >(node)
389            }
390        };
391        if root != node {
392            unsafe {
393                (*node.as_ptr()).data.belong = (*root.as_ptr()).data.belong.take();
394            }
395        }
396    }
397
398    #[inline]
399    unsafe fn splay_rake(node: RakePtr<S, A>) {
400        unsafe {
401            splay_operations::with_parent::splay_with_local_top_down::<
402                RakeBstSpec<S, A>,
403                RakeData<S, A>,
404            >(node)
405        };
406    }
407
408    unsafe fn rake_rightmost(mut node: RakePtr<S, A>) -> RakePtr<S, A> {
409        loop {
410            unsafe { RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node)) };
411            match unsafe { node.as_ref().child[1] } {
412                Some(right) => node = right,
413                None => return node,
414            }
415        }
416    }
417
418    unsafe fn rake_insert(
419        &mut self,
420        root: Option<RakePtr<S, A>>,
421        key: S::Point,
422    ) -> (RakePtr<S, A>, RakePtr<S, A>) {
423        let mut node = self.rake_allocator.allocate(BstNode::new(RakeData {
424            sum: key.clone(),
425            key,
426            action: <A::ActionMonoid as Unital>::unit(),
427            buffer: <A::ActionMonoid as Unital>::unit(),
428        }));
429        if let Some(mut root) = root {
430            unsafe {
431                node.as_mut().child[0] = Some(root);
432                root.as_mut().parent.parent = Some(node);
433                Self::pull_rake(node);
434            }
435        }
436        (node, node)
437    }
438
439    unsafe fn rake_remove(
440        &mut self,
441        mut node: RakePtr<S, A>,
442    ) -> (Option<RakePtr<S, A>>, A::Action) {
443        unsafe {
444            Self::splay_rake(node);
445            RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node));
446        }
447        let left = unsafe { node.as_mut().child[0].take() };
448        let right = unsafe { node.as_mut().child[1].take() };
449        for mut child in [left, right].into_iter().flatten() {
450            unsafe { child.as_mut().parent.parent = None };
451        }
452        let root = match (left, right) {
453            (None, right) => right,
454            (left, None) => left,
455            (Some(left), Some(right)) => {
456                let mut root = unsafe { Self::rake_rightmost(left) };
457                unsafe {
458                    Self::splay_rake(root);
459                    root.as_mut().child[1] = Some(right);
460                    (*right.as_ptr()).parent.parent = Some(root);
461                    Self::pull_rake(root);
462                }
463                Some(root)
464            }
465        };
466        let node = self.rake_allocator.deallocate(node);
467        (root, node.data.buffer)
468    }
469
470    fn access_node(&mut self, node: TopPtr<S, A>) {
471        unsafe {
472            let mut previous: Option<TopPtr<S, A>> = None;
473            let mut current = Some(node);
474            while let Some(mut cursor) = current {
475                Self::splay_top(cursor);
476                let next = cursor.as_ref().parent.parent;
477                if let Some(right) = cursor.as_mut().child[1].take() {
478                    let point = S::add_edge(&right.as_ref().data.sum);
479                    let (light, entry) = self.rake_insert(cursor.as_ref().data.light, point);
480                    cursor.as_mut().data.light = Some(light);
481                    (*right.as_ptr()).data.belong = Some(entry);
482                }
483                if let Some(previous) = previous {
484                    let entry = (*previous.as_ptr())
485                        .data
486                        .belong
487                        .take()
488                        .expect("a virtual path must have a rake-tree entry");
489                    let (light, action) = self.rake_remove(entry);
490                    cursor.as_mut().data.light = light;
491                    TopBstSpec::<S, A>::apply_all(previous, &action);
492                    cursor.as_mut().child[1] = Some(previous);
493                    (*previous.as_ptr()).parent.parent = Some(cursor);
494                }
495                Self::pull_top(cursor);
496                previous = Some(cursor);
497                current = next;
498            }
499            Self::splay_top(node);
500        }
501    }
502
503    pub fn get(&mut self, node: usize) -> &S::Info {
504        let node = self.node(node);
505        self.access_node(node);
506        unsafe { &node.as_ref().data.info }
507    }
508
509    pub fn set(&mut self, node: usize, info: S::Info) {
510        self.modify(node, |_| info);
511    }
512
513    pub fn modify<F>(&mut self, node: usize, f: F)
514    where
515        F: FnOnce(&S::Info) -> S::Info,
516    {
517        let mut node = self.node(node);
518        self.access_node(node);
519        unsafe {
520            node.as_mut().data.info = f(&node.as_ref().data.info);
521            Self::pull_top(node);
522        }
523    }
524
525    pub fn reroot(&mut self, node: usize) {
526        let node = self.node(node);
527        self.access_node(node);
528        unsafe { TopBstSpec::<S, A>::toggle(node) };
529    }
530
531    /// `child` and `parent` must belong to different trees.
532    pub fn link(&mut self, child: usize, parent: usize) {
533        assert_ne!(child, parent);
534        self.reroot(child);
535        let child = self.node(child);
536        let mut parent = self.node(parent);
537        self.access_node(parent);
538        unsafe {
539            (*child.as_ptr()).parent.parent = Some(parent);
540            let point = S::add_edge(&child.as_ref().data.sum);
541            let (light, entry) = self.rake_insert(parent.as_ref().data.light, point);
542            parent.as_mut().data.light = Some(light);
543            (*child.as_ptr()).data.belong = Some(entry);
544            Self::pull_top(parent);
545        }
546    }
547
548    /// `(u, v)` must be an edge.
549    pub fn cut(&mut self, u: usize, v: usize) {
550        assert_ne!(u, v);
551        self.reroot(u);
552        let mut v = self.node(v);
553        self.access_node(v);
554        unsafe {
555            let mut left = v.as_mut().child[0]
556                .take()
557                .expect("the specified edge must exist");
558            left.as_mut().parent.parent = None;
559            Self::pull_top(v);
560        }
561    }
562
563    pub fn root(&mut self, node: usize) -> usize {
564        let mut root = self.node(node);
565        self.access_node(root);
566        unsafe {
567            loop {
568                TopBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(root));
569                match root.as_ref().child[0] {
570                    Some(left) => root = left,
571                    None => break,
572                }
573            }
574            Self::splay_top(root);
575            root.as_ref().data.index_and_reverse >> 1
576        }
577    }
578
579    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
580        self.root(u) == self.root(v)
581    }
582
583    /// `u` and `v` must be connected.
584    pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path {
585        self.reroot(u);
586        let v = self.node(v);
587        self.access_node(v);
588        unsafe { v.as_ref().data.sum.clone() }
589    }
590
591    /// `u` and `v` must be connected.
592    pub fn update_path(&mut self, u: usize, v: usize, action: &A::Action) {
593        self.reroot(u);
594        let v = self.node(v);
595        self.access_node(v);
596        if !TopBstSpec::<S, A>::is_unit(action) {
597            unsafe { TopBstSpec::<S, A>::apply_heavy(v, action) };
598        }
599    }
Source

unsafe fn apply_light( node: NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>, action: &A::Action, )

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 181)
157    fn top_down(mut node: BstDataMutRef<'_, Self>) {
158        let pointer = node.node;
159        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
160            node.data_mut().index_and_reverse &= !1;
161            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
162                unsafe { Self::toggle(child) };
163            }
164        }
165
166        if !Self::is_unit(&node.reborrow().into_data().heavy_action) {
167            let action = replace(
168                &mut node.data_mut().heavy_action,
169                <A::ActionMonoid as Unital>::unit(),
170            );
171            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
172                unsafe { Self::apply_heavy(child, &action) };
173            }
174        }
175        if !Self::is_unit(&node.reborrow().into_data().light_action) {
176            let action = replace(
177                &mut node.data_mut().light_action,
178                <A::ActionMonoid as Unital>::unit(),
179            );
180            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
181                unsafe { Self::apply_light(child, &action) };
182            }
183            if let Some(light) = node.reborrow().into_data().light {
184                unsafe { RakeBstSpec::<S, A>::apply(light, &action) };
185            }
186        }
187    }
Source

unsafe fn apply_all( node: NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>, action: &A::Action, )

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 491)
470    fn access_node(&mut self, node: TopPtr<S, A>) {
471        unsafe {
472            let mut previous: Option<TopPtr<S, A>> = None;
473            let mut current = Some(node);
474            while let Some(mut cursor) = current {
475                Self::splay_top(cursor);
476                let next = cursor.as_ref().parent.parent;
477                if let Some(right) = cursor.as_mut().child[1].take() {
478                    let point = S::add_edge(&right.as_ref().data.sum);
479                    let (light, entry) = self.rake_insert(cursor.as_ref().data.light, point);
480                    cursor.as_mut().data.light = Some(light);
481                    (*right.as_ptr()).data.belong = Some(entry);
482                }
483                if let Some(previous) = previous {
484                    let entry = (*previous.as_ptr())
485                        .data
486                        .belong
487                        .take()
488                        .expect("a virtual path must have a rake-tree entry");
489                    let (light, action) = self.rake_remove(entry);
490                    cursor.as_mut().data.light = light;
491                    TopBstSpec::<S, A>::apply_all(previous, &action);
492                    cursor.as_mut().child[1] = Some(previous);
493                    (*previous.as_ptr()).parent.parent = Some(cursor);
494                }
495                Self::pull_top(cursor);
496                previous = Some(cursor);
497                current = next;
498            }
499            Self::splay_top(node);
500        }
501    }
502
503    pub fn get(&mut self, node: usize) -> &S::Info {
504        let node = self.node(node);
505        self.access_node(node);
506        unsafe { &node.as_ref().data.info }
507    }
508
509    pub fn set(&mut self, node: usize, info: S::Info) {
510        self.modify(node, |_| info);
511    }
512
513    pub fn modify<F>(&mut self, node: usize, f: F)
514    where
515        F: FnOnce(&S::Info) -> S::Info,
516    {
517        let mut node = self.node(node);
518        self.access_node(node);
519        unsafe {
520            node.as_mut().data.info = f(&node.as_ref().data.info);
521            Self::pull_top(node);
522        }
523    }
524
525    pub fn reroot(&mut self, node: usize) {
526        let node = self.node(node);
527        self.access_node(node);
528        unsafe { TopBstSpec::<S, A>::toggle(node) };
529    }
530
531    /// `child` and `parent` must belong to different trees.
532    pub fn link(&mut self, child: usize, parent: usize) {
533        assert_ne!(child, parent);
534        self.reroot(child);
535        let child = self.node(child);
536        let mut parent = self.node(parent);
537        self.access_node(parent);
538        unsafe {
539            (*child.as_ptr()).parent.parent = Some(parent);
540            let point = S::add_edge(&child.as_ref().data.sum);
541            let (light, entry) = self.rake_insert(parent.as_ref().data.light, point);
542            parent.as_mut().data.light = Some(light);
543            (*child.as_ptr()).data.belong = Some(entry);
544            Self::pull_top(parent);
545        }
546    }
547
548    /// `(u, v)` must be an edge.
549    pub fn cut(&mut self, u: usize, v: usize) {
550        assert_ne!(u, v);
551        self.reroot(u);
552        let mut v = self.node(v);
553        self.access_node(v);
554        unsafe {
555            let mut left = v.as_mut().child[0]
556                .take()
557                .expect("the specified edge must exist");
558            left.as_mut().parent.parent = None;
559            Self::pull_top(v);
560        }
561    }
562
563    pub fn root(&mut self, node: usize) -> usize {
564        let mut root = self.node(node);
565        self.access_node(root);
566        unsafe {
567            loop {
568                TopBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(root));
569                match root.as_ref().child[0] {
570                    Some(left) => root = left,
571                    None => break,
572                }
573            }
574            Self::splay_top(root);
575            root.as_ref().data.index_and_reverse >> 1
576        }
577    }
578
579    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
580        self.root(u) == self.root(v)
581    }
582
583    /// `u` and `v` must be connected.
584    pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path {
585        self.reroot(u);
586        let v = self.node(v);
587        self.access_node(v);
588        unsafe { v.as_ref().data.sum.clone() }
589    }
590
591    /// `u` and `v` must be connected.
592    pub fn update_path(&mut self, u: usize, v: usize, action: &A::Action) {
593        self.reroot(u);
594        let v = self.node(v);
595        self.access_node(v);
596        if !TopBstSpec::<S, A>::is_unit(action) {
597            unsafe { TopBstSpec::<S, A>::apply_heavy(v, action) };
598        }
599    }
600
601    fn detach_left<R>(mut node: TopPtr<S, A>, f: impl FnOnce(TopPtr<S, A>) -> R) -> R {
602        unsafe {
603            let left = node.as_mut().child[0].take();
604            if let Some(mut left) = left {
605                left.as_mut().parent.parent = None;
606            }
607            Self::pull_top(node);
608            let result = f(node);
609            node.as_mut().child[0] = left;
610            if let Some(mut left) = left {
611                left.as_mut().parent.parent = Some(node);
612            }
613            Self::pull_top(node);
614            result
615        }
616    }
617
618    /// `(node, parent)` must be an edge.
619    pub fn fold_subtree(&mut self, node: usize, parent: usize) -> S::Path {
620        self.reroot(parent);
621        let node = self.node(node);
622        self.access_node(node);
623        Self::detach_left(node, |node| unsafe { node.as_ref().data.sum.clone() })
624    }
625
626    /// `(node, parent)` must be an edge.
627    pub fn update_subtree(&mut self, node: usize, parent: usize, action: &A::Action) {
628        self.reroot(parent);
629        let node = self.node(node);
630        self.access_node(node);
631        Self::detach_left(node, |node| unsafe {
632            TopBstSpec::<S, A>::apply_all(node, action);
633            TopBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node));
634        });
635    }

Trait Implementations§

Source§

impl<S, A> BstSpec for TopBstSpec<S, A>
where S: TopTreeSpec, A: TopTreeAction<S>,

Source§

type Parent = WithParent<<TopBstSpec<S, A> as BstSpec>::Data>

Source§

type Data = TopTreeData<S, A>

Source§

fn top_down(node: BstDataMutRef<'_, Self>)

Source§

fn bottom_up(node: BstDataMutRef<'_, Self>)

Source§

fn merge( _left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>, ) -> Option<BstRoot<Self>>

Source§

fn split<Seeker>( _node: Option<BstRoot<Self>>, _seeker: Seeker, _equal_side: EqualSide, ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
where Seeker: BstSeeker<Spec = Self>,

Auto Trait Implementations§

§

impl<S, A> Freeze for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: Freeze,

§

impl<S, A> RefUnwindSafe for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: RefUnwindSafe,

§

impl<S, A> Send for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: Send,

§

impl<S, A> Sync for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: Sync,

§

impl<S, A> Unpin for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: Unpin,

§

impl<S, A> UnsafeUnpin for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: UnsafeUnpin,

§

impl<S, A> UnwindSafe for TopBstSpec<S, A>
where PhantomData<fn() -> (S, A)>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.