Skip to main content

TopTree

competitive::tree

Struct TopTree 

Source 
pub struct TopTree<S, A = NoTopTreeAction>
where
    S: TopTreeSpec,
    A: TopTreeAction<S>,
{
    nodes: Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>,
    node_allocator: MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>,
    rake_allocator: MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>,
}
Expand description

A self-adjusting top tree, also called a strong link-cut tree.

This is not a classical worst-case-balanced top tree. Circular order and select are not supported.

Fields§

§nodes: Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>§node_allocator: MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>§rake_allocator: MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>

Implementations§

Source§

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

Source

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 646)
643    fn from_iter<T: IntoIterator<Item = S::Info>>(iter: T) -> Self {
644        let iter = iter.into_iter();
645        let (lower, _) = iter.size_hint();
646        let mut tree = Self::with_capacity(lower);
647        for info in iter {
648            tree.add_node(info);
649        }
650        tree
651    }
Source

pub fn from_edges<T>(values: T, edges: &[(usize, usize)]) -> Self
where T: IntoIterator<Item = S::Info>,

edges must form a tree over the values in iteration order.

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 69)
66pub fn dynamic_tree_vertex_add_path_sum_top_tree(reader: impl Read, writer: impl Write) {
67    prepare_io!(reader, writer);
68    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
69    let mut tree = TopTree::<SumTopTree>::from_edges(a, &edges);
70    for _ in 0..q {
71        sc!(query: Query);
72        match query {
73            Query::Relink { u, v, w, x } => {
74                tree.cut(u, v);
75                tree.link(w, x);
76            }
77            Query::Add { p, x } => tree.modify(p, |value| *value + x),
78            Query::Sum { u, v } => {
79                pp!(tree.fold_path(u, v).1);
80            }
81        }
82    }
83}
More examples
Hide additional examples
crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 125)
122pub fn dynamic_tree_vertex_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
123    prepare_io!(reader, writer);
124    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
125    let mut tree = TopTree::<SubtreeSum>::from_edges(a, &edges);
126    for _ in 0..q {
127        sc!(query: Query);
128        match query {
129            Query::Relink { u, v, w, x } => {
130                tree.cut(u, v);
131                tree.link(w, x);
132            }
133            Query::Add { p, x } => tree.modify(p, |value| *value + x),
134            Query::Sum { v, p } => {
135                pp!(tree.fold_subtree(v, p).0);
136            }
137        }
138    }
139}
crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 207)
204pub fn dynamic_tree_subtree_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
205    prepare_io!(reader, writer);
206    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
207    let mut tree = TopTree::<TopTreeSubtreeSum, AddAction>::from_edges(a, &edges);
208    for _ in 0..q {
209        sc!(query: Query);
210        match query {
211            Query::Relink { u, v, w, x } => {
212                tree.cut(u, v);
213                tree.link(w, x);
214            }
215            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
216            Query::Sum { v, p } => {
217                pp!(tree.fold_subtree(v, p).0);
218            }
219        }
220    }
221}
crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 113)
110pub fn dynamic_tree_vertex_set_path_composite_top_tree(reader: impl Read, writer: impl Write) {
111    prepare_io!(reader, writer);
112    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
113    let mut tree = TopTree::<PathComposite>::from_edges(ab, &edges);
114    for _ in 0..q {
115        sc!(query: Query);
116        match query {
117            Query::Relink { u, v, w, x } => {
118                tree.cut(u, v);
119                tree.link(w, x);
120            }
121            Query::Set { p, cd } => tree.set(p, cd),
122            Query::Apply { u, v, x } => {
123                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
124            }
125        }
126    }
127}
Source

pub fn add_node(&mut self, info: S::Info) -> usize

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 648)
643    fn from_iter<T: IntoIterator<Item = S::Info>>(iter: T) -> Self {
644        let iter = iter.into_iter();
645        let (lower, _) = iter.size_hint();
646        let mut tree = Self::with_capacity(lower);
647        for info in iter {
648            tree.add_node(info);
649        }
650        tree
651    }
Source

fn node( &self, index: usize, ) -> NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 329)
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    }
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    }
Source

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

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 341)
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    }
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    }
Source

unsafe fn pull_rake( node: NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>, )

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 433)
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    }
Source

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

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 475)
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    }
Source

unsafe fn splay_rake( node: NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>, )

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 444)
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    }
Source

unsafe fn rake_rightmost( node: NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>, ) -> NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 456)
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    }
Source

unsafe fn rake_insert( &mut self, root: Option<NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>>, key: S::Point, ) -> (NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>, NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>)

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 337)
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    }
Source

unsafe fn rake_remove( &mut self, node: NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>, ) -> (Option<NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>>, A::Action)

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 489)
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    }
Source

fn access_node( &mut self, node: NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>, )

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 505)
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    }
Source

pub fn get(&mut self, node: usize) -> &S::Info

Source

pub fn set(&mut self, node: usize, info: S::Info)

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 121)
110pub fn dynamic_tree_vertex_set_path_composite_top_tree(reader: impl Read, writer: impl Write) {
111    prepare_io!(reader, writer);
112    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
113    let mut tree = TopTree::<PathComposite>::from_edges(ab, &edges);
114    for _ in 0..q {
115        sc!(query: Query);
116        match query {
117            Query::Relink { u, v, w, x } => {
118                tree.cut(u, v);
119                tree.link(w, x);
120            }
121            Query::Set { p, cd } => tree.set(p, cd),
122            Query::Apply { u, v, x } => {
123                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
124            }
125        }
126    }
127}
Source

pub fn modify<F>(&mut self, node: usize, f: F)
where F: FnOnce(&S::Info) -> S::Info,

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 510)
509    pub fn set(&mut self, node: usize, info: S::Info) {
510        self.modify(node, |_| info);
511    }
More examples
Hide additional examples
crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 77)
66pub fn dynamic_tree_vertex_add_path_sum_top_tree(reader: impl Read, writer: impl Write) {
67    prepare_io!(reader, writer);
68    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
69    let mut tree = TopTree::<SumTopTree>::from_edges(a, &edges);
70    for _ in 0..q {
71        sc!(query: Query);
72        match query {
73            Query::Relink { u, v, w, x } => {
74                tree.cut(u, v);
75                tree.link(w, x);
76            }
77            Query::Add { p, x } => tree.modify(p, |value| *value + x),
78            Query::Sum { u, v } => {
79                pp!(tree.fold_path(u, v).1);
80            }
81        }
82    }
83}
crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 133)
122pub fn dynamic_tree_vertex_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
123    prepare_io!(reader, writer);
124    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
125    let mut tree = TopTree::<SubtreeSum>::from_edges(a, &edges);
126    for _ in 0..q {
127        sc!(query: Query);
128        match query {
129            Query::Relink { u, v, w, x } => {
130                tree.cut(u, v);
131                tree.link(w, x);
132            }
133            Query::Add { p, x } => tree.modify(p, |value| *value + x),
134            Query::Sum { v, p } => {
135                pp!(tree.fold_subtree(v, p).0);
136            }
137        }
138    }
139}
Source

pub fn reroot(&mut self, node: usize)

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 534)
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    }

child and parent must belong to different trees.

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 75)
66pub fn dynamic_tree_vertex_add_path_sum_top_tree(reader: impl Read, writer: impl Write) {
67    prepare_io!(reader, writer);
68    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
69    let mut tree = TopTree::<SumTopTree>::from_edges(a, &edges);
70    for _ in 0..q {
71        sc!(query: Query);
72        match query {
73            Query::Relink { u, v, w, x } => {
74                tree.cut(u, v);
75                tree.link(w, x);
76            }
77            Query::Add { p, x } => tree.modify(p, |value| *value + x),
78            Query::Sum { u, v } => {
79                pp!(tree.fold_path(u, v).1);
80            }
81        }
82    }
83}
More examples
Hide additional examples
crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 131)
122pub fn dynamic_tree_vertex_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
123    prepare_io!(reader, writer);
124    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
125    let mut tree = TopTree::<SubtreeSum>::from_edges(a, &edges);
126    for _ in 0..q {
127        sc!(query: Query);
128        match query {
129            Query::Relink { u, v, w, x } => {
130                tree.cut(u, v);
131                tree.link(w, x);
132            }
133            Query::Add { p, x } => tree.modify(p, |value| *value + x),
134            Query::Sum { v, p } => {
135                pp!(tree.fold_subtree(v, p).0);
136            }
137        }
138    }
139}
crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 213)
204pub fn dynamic_tree_subtree_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
205    prepare_io!(reader, writer);
206    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
207    let mut tree = TopTree::<TopTreeSubtreeSum, AddAction>::from_edges(a, &edges);
208    for _ in 0..q {
209        sc!(query: Query);
210        match query {
211            Query::Relink { u, v, w, x } => {
212                tree.cut(u, v);
213                tree.link(w, x);
214            }
215            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
216            Query::Sum { v, p } => {
217                pp!(tree.fold_subtree(v, p).0);
218            }
219        }
220    }
221}
crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 119)
110pub fn dynamic_tree_vertex_set_path_composite_top_tree(reader: impl Read, writer: impl Write) {
111    prepare_io!(reader, writer);
112    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
113    let mut tree = TopTree::<PathComposite>::from_edges(ab, &edges);
114    for _ in 0..q {
115        sc!(query: Query);
116        match query {
117            Query::Relink { u, v, w, x } => {
118                tree.cut(u, v);
119                tree.link(w, x);
120            }
121            Query::Set { p, cd } => tree.set(p, cd),
122            Query::Apply { u, v, x } => {
123                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
124            }
125        }
126    }
127}
Source

pub fn cut(&mut self, u: usize, v: usize)

(u, v) must be an edge.

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 74)
66pub fn dynamic_tree_vertex_add_path_sum_top_tree(reader: impl Read, writer: impl Write) {
67    prepare_io!(reader, writer);
68    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
69    let mut tree = TopTree::<SumTopTree>::from_edges(a, &edges);
70    for _ in 0..q {
71        sc!(query: Query);
72        match query {
73            Query::Relink { u, v, w, x } => {
74                tree.cut(u, v);
75                tree.link(w, x);
76            }
77            Query::Add { p, x } => tree.modify(p, |value| *value + x),
78            Query::Sum { u, v } => {
79                pp!(tree.fold_path(u, v).1);
80            }
81        }
82    }
83}
More examples
Hide additional examples
crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 130)
122pub fn dynamic_tree_vertex_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
123    prepare_io!(reader, writer);
124    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
125    let mut tree = TopTree::<SubtreeSum>::from_edges(a, &edges);
126    for _ in 0..q {
127        sc!(query: Query);
128        match query {
129            Query::Relink { u, v, w, x } => {
130                tree.cut(u, v);
131                tree.link(w, x);
132            }
133            Query::Add { p, x } => tree.modify(p, |value| *value + x),
134            Query::Sum { v, p } => {
135                pp!(tree.fold_subtree(v, p).0);
136            }
137        }
138    }
139}
crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 212)
204pub fn dynamic_tree_subtree_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
205    prepare_io!(reader, writer);
206    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
207    let mut tree = TopTree::<TopTreeSubtreeSum, AddAction>::from_edges(a, &edges);
208    for _ in 0..q {
209        sc!(query: Query);
210        match query {
211            Query::Relink { u, v, w, x } => {
212                tree.cut(u, v);
213                tree.link(w, x);
214            }
215            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
216            Query::Sum { v, p } => {
217                pp!(tree.fold_subtree(v, p).0);
218            }
219        }
220    }
221}
crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 118)
110pub fn dynamic_tree_vertex_set_path_composite_top_tree(reader: impl Read, writer: impl Write) {
111    prepare_io!(reader, writer);
112    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
113    let mut tree = TopTree::<PathComposite>::from_edges(ab, &edges);
114    for _ in 0..q {
115        sc!(query: Query);
116        match query {
117            Query::Relink { u, v, w, x } => {
118                tree.cut(u, v);
119                tree.link(w, x);
120            }
121            Query::Set { p, cd } => tree.set(p, cd),
122            Query::Apply { u, v, x } => {
123                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
124            }
125        }
126    }
127}
Source

pub fn root(&mut self, node: usize) -> usize

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 580)
579    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
580        self.root(u) == self.root(v)
581    }
Source

pub fn is_connected(&mut self, u: usize, v: usize) -> bool

Source

pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path

u and v must be connected.

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_vertex_add_path_sum.rs (line 79)
66pub fn dynamic_tree_vertex_add_path_sum_top_tree(reader: impl Read, writer: impl Write) {
67    prepare_io!(reader, writer);
68    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
69    let mut tree = TopTree::<SumTopTree>::from_edges(a, &edges);
70    for _ in 0..q {
71        sc!(query: Query);
72        match query {
73            Query::Relink { u, v, w, x } => {
74                tree.cut(u, v);
75                tree.link(w, x);
76            }
77            Query::Add { p, x } => tree.modify(p, |value| *value + x),
78            Query::Sum { u, v } => {
79                pp!(tree.fold_path(u, v).1);
80            }
81        }
82    }
83}
More examples
Hide additional examples
crates/library_checker/src/tree/dynamic_tree_vertex_set_path_composite.rs (line 123)
110pub fn dynamic_tree_vertex_set_path_composite_top_tree(reader: impl Read, writer: impl Write) {
111    prepare_io!(reader, writer);
112    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
113    let mut tree = TopTree::<PathComposite>::from_edges(ab, &edges);
114    for _ in 0..q {
115        sc!(query: Query);
116        match query {
117            Query::Relink { u, v, w, x } => {
118                tree.cut(u, v);
119                tree.link(w, x);
120            }
121            Query::Set { p, cd } => tree.set(p, cd),
122            Query::Apply { u, v, x } => {
123                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
124            }
125        }
126    }
127}
Source

pub fn update_path(&mut self, u: usize, v: usize, action: &A::Action)

u and v must be connected.

Source

fn detach_left<R>( node: NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>, f: impl FnOnce(NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>) -> R, ) -> R

Examples found in repository?
crates/competitive/src/tree/top_tree.rs (line 623)
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    }
Source

pub fn fold_subtree(&mut self, node: usize, parent: usize) -> S::Path

(node, parent) must be an edge.

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_vertex_add_subtree_sum.rs (line 135)
122pub fn dynamic_tree_vertex_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
123    prepare_io!(reader, writer);
124    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
125    let mut tree = TopTree::<SubtreeSum>::from_edges(a, &edges);
126    for _ in 0..q {
127        sc!(query: Query);
128        match query {
129            Query::Relink { u, v, w, x } => {
130                tree.cut(u, v);
131                tree.link(w, x);
132            }
133            Query::Add { p, x } => tree.modify(p, |value| *value + x),
134            Query::Sum { v, p } => {
135                pp!(tree.fold_subtree(v, p).0);
136            }
137        }
138    }
139}
More examples
Hide additional examples
crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 217)
204pub fn dynamic_tree_subtree_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
205    prepare_io!(reader, writer);
206    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
207    let mut tree = TopTree::<TopTreeSubtreeSum, AddAction>::from_edges(a, &edges);
208    for _ in 0..q {
209        sc!(query: Query);
210        match query {
211            Query::Relink { u, v, w, x } => {
212                tree.cut(u, v);
213                tree.link(w, x);
214            }
215            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
216            Query::Sum { v, p } => {
217                pp!(tree.fold_subtree(v, p).0);
218            }
219        }
220    }
221}
Source

pub fn update_subtree(&mut self, node: usize, parent: usize, action: &A::Action)

(node, parent) must be an edge.

Examples found in repository?
crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 215)
204pub fn dynamic_tree_subtree_add_subtree_sum_top_tree(reader: impl Read, writer: impl Write) {
205    prepare_io!(reader, writer);
206    sc!(n, q, a: [u64; n], edges: [(usize, usize); n - 1]);
207    let mut tree = TopTree::<TopTreeSubtreeSum, AddAction>::from_edges(a, &edges);
208    for _ in 0..q {
209        sc!(query: Query);
210        match query {
211            Query::Relink { u, v, w, x } => {
212                tree.cut(u, v);
213                tree.link(w, x);
214            }
215            Query::Add { v, p, x } => tree.update_subtree(v, p, &x),
216            Query::Sum { v, p } => {
217                pp!(tree.fold_subtree(v, p).0);
218            }
219        }
220    }
221}

Trait Implementations§

Source§

impl<S, A> FromIterator<<S as TopTreeSpec>::Info> for TopTree<S, A>
where S: TopTreeSpec, A: TopTreeAction<S>,

Source§

fn from_iter<T: IntoIterator<Item = S::Info>>(iter: T) -> Self

Creates a value from an iterator. Read more

Auto Trait Implementations§

§

impl<S, A = NoTopTreeAction> !Send for TopTree<S, A>

§

impl<S, A = NoTopTreeAction> !Sync for TopTree<S, A>

§

impl<S, A> Freeze for TopTree<S, A>
where Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>: Freeze, MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>: Freeze, MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>: Freeze,

§

impl<S, A> RefUnwindSafe for TopTree<S, A>
where Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>: RefUnwindSafe, MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>: RefUnwindSafe, MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>: RefUnwindSafe,

§

impl<S, A> Unpin for TopTree<S, A>
where Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>: Unpin, MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>: Unpin, MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>: Unpin,

§

impl<S, A> UnsafeUnpin for TopTree<S, A>
where Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>: UnsafeUnpin, MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>: UnsafeUnpin, MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>: UnsafeUnpin,

§

impl<S, A> UnwindSafe for TopTree<S, A>
where Vec<NonNull<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>>: UnwindSafe, MemoryPool<BstNode<TopTreeData<S, A>, WithParent<TopTreeData<S, A>>>>: UnwindSafe, MemoryPool<BstNode<RakeData<S, A>, WithParent<RakeData<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.