Struct ReRooting

Source

pub struct ReRooting<'a, M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T> {
    graph: &'a UndirectedSparseGraph,
    pub dp: Vec<M::T>,
    pub ep: Vec<M::T>,
    rooting: F,
}

Expand description

dynamic programming on all-rooted trees

Neighbors are merged in adjacency order before applying rooting.

Fields§

§graph: &'a UndirectedSparseGraph§dp: Vec<M::T>

dp[v]: result of v-rooted tree

§ep: Vec<M::T>

ep[e]: result of e-subtree; e >= m denotes the reverse direction.

§rooting: F

rooting(data, vid, (Optional)eid): add root node(vid), result subtree is edge(eid)

Implementations§

Source §

impl<'a, M, F> ReRooting<'a, M, F>
where M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T,

Source

pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_b.rs (lines 8-10)

5pub fn grl_5_b(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
8    let re = ReRooting::<MaxOperation<u64>, _>::new(&graph, |d, _vid, eid_opt| {
9        d + eid_opt.map_or(0, |eid| w[eid])
10    });
11    pp!(@lf @it re.dp);
12}

Source

pub fn new_with_inverse(graph: &'a UndirectedSparseGraph, rooting: F) -> Self
where M: AbelianGroup,

Examples found in repository ?

crates/library_checker/src/tree/tree_path_composite_sum.rs (lines 11-23)

8pub fn tree_path_composite_sum(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, values: [M; n], (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
11    let dp = ReRooting::<(AdditiveOperation<M>, AdditiveOperation<i32>), _>::new_with_inverse(
12        &graph,
13        |&(sum, count), v, edge| {
14            let sum = sum + values[v];
15            let count = count + 1;
16            if let Some(edge) = edge {
17                let (a, b) = edges[edge];
18                (a * sum + b * M::new_unchecked(count as u32), count)
19            } else {
20                (sum, count)
21            }
22        },
23    );
24    pp!(@it dp.dp.iter().map(|value| value.0));
25}

Source

fn build( graph: &'a UndirectedSparseGraph, rooting: F, inverse: Option, ) -> Self
where I: Fn(&M::T, &M::T) -> M::T,

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 27)

26    pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self {
27        Self::build(graph, rooting, None::<fn(&M::T, &M::T) -> M::T>)
28    }
29
30    pub fn new_with_inverse(graph: &'a UndirectedSparseGraph, rooting: F) -> Self
31    where
32        M: AbelianGroup,
33    {
34        Self::build(graph, rooting, Some(M::rinv_operate))
35    }

Source

fn eidx(&self, u: usize, a: Neighbor<usize, usize>) -> usize

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 81)

72    fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>) {
73        let (order, parents) = self.graph.tree_order(0);
74        for &u in order.iter().skip(1).rev() {
75            let mut sum = M::unit();
76            let mut parent = None;
77            for a in self.graph.neighbors(u) {
78                if a.to == parents[u] {
79                    parent = Some(a);
80                } else {
81                    sum = self.merge(&sum, &self.ep[self.eidx(u, a)]);
82                }
83            }
84            let a = parent.unwrap();
85            let i = self.reidx(u, a);
86            self.ep[i] = self.add_subroot(&sum, u, a.label);
87            if inverse.is_some() {
88                self.dp[u] = sum;
89            }
90        }
91        if let Some(inverse) = inverse {
92            for u in order {
93                let sum = if u == 0 {
94                    self.graph.neighbors(u).fold(M::unit(), |sum, a| {
95                        self.merge(&sum, &self.ep[self.eidx(u, a)])
96                    })
97                } else {
98                    let a = self
99                        .graph
100                        .neighbors(u)
101                        .find(|a| a.to == parents[u])
102                        .unwrap();
103                    self.merge(&self.dp[u], &self.ep[self.eidx(u, a)])
104                };
105                self.dp[u] = self.add_root(&sum, u);
106                for a in self.graph.neighbors(u) {
107                    if a.to != parents[u] {
108                        let value = inverse(&sum, &self.ep[self.eidx(u, a)]);
109                        let i = self.reidx(u, a);
110                        self.ep[i] = self.add_subroot(&value, u, a.label);
111                    }
112                }
113            }
114            return;
115        }
116        let mut prefix = Vec::new();
117        for u in order {
118            prefix.clear();
119            prefix.push(M::unit());
120            for a in self.graph.neighbors(u) {
121                prefix.push(self.merge(prefix.last().unwrap(), &self.ep[self.eidx(u, a)]));
122            }
123            self.dp[u] = self.add_root(prefix.last().unwrap(), u);
124            let mut suffix = M::unit();
125            for (k, a) in self.graph.neighbors(u).enumerate().rev() {
126                if a.to != parents[u] {
127                    let i = self.reidx(u, a);
128                    self.ep[i] = self.add_subroot(&self.merge(&prefix[k], &suffix), u, a.label);
129                }
130                suffix = self.merge(&self.ep[self.eidx(u, a)], &suffix);
131            }
132        }
133    }

Source

fn reidx(&self, u: usize, a: Neighbor<usize, usize>) -> usize

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 85)

72    fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>) {
73        let (order, parents) = self.graph.tree_order(0);
74        for &u in order.iter().skip(1).rev() {
75            let mut sum = M::unit();
76            let mut parent = None;
77            for a in self.graph.neighbors(u) {
78                if a.to == parents[u] {
79                    parent = Some(a);
80                } else {
81                    sum = self.merge(&sum, &self.ep[self.eidx(u, a)]);
82                }
83            }
84            let a = parent.unwrap();
85            let i = self.reidx(u, a);
86            self.ep[i] = self.add_subroot(&sum, u, a.label);
87            if inverse.is_some() {
88                self.dp[u] = sum;
89            }
90        }
91        if let Some(inverse) = inverse {
92            for u in order {
93                let sum = if u == 0 {
94                    self.graph.neighbors(u).fold(M::unit(), |sum, a| {
95                        self.merge(&sum, &self.ep[self.eidx(u, a)])
96                    })
97                } else {
98                    let a = self
99                        .graph
100                        .neighbors(u)
101                        .find(|a| a.to == parents[u])
102                        .unwrap();
103                    self.merge(&self.dp[u], &self.ep[self.eidx(u, a)])
104                };
105                self.dp[u] = self.add_root(&sum, u);
106                for a in self.graph.neighbors(u) {
107                    if a.to != parents[u] {
108                        let value = inverse(&sum, &self.ep[self.eidx(u, a)]);
109                        let i = self.reidx(u, a);
110                        self.ep[i] = self.add_subroot(&value, u, a.label);
111                    }
112                }
113            }
114            return;
115        }
116        let mut prefix = Vec::new();
117        for u in order {
118            prefix.clear();
119            prefix.push(M::unit());
120            for a in self.graph.neighbors(u) {
121                prefix.push(self.merge(prefix.last().unwrap(), &self.ep[self.eidx(u, a)]));
122            }
123            self.dp[u] = self.add_root(prefix.last().unwrap(), u);
124            let mut suffix = M::unit();
125            for (k, a) in self.graph.neighbors(u).enumerate().rev() {
126                if a.to != parents[u] {
127                    let i = self.reidx(u, a);
128                    self.ep[i] = self.add_subroot(&self.merge(&prefix[k], &suffix), u, a.label);
129                }
130                suffix = self.merge(&self.ep[self.eidx(u, a)], &suffix);
131            }
132        }
133    }

Source

fn merge(&self, x: &M::T, y: &M::T) -> M::T

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 81)

72    fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>) {
73        let (order, parents) = self.graph.tree_order(0);
74        for &u in order.iter().skip(1).rev() {
75            let mut sum = M::unit();
76            let mut parent = None;
77            for a in self.graph.neighbors(u) {
78                if a.to == parents[u] {
79                    parent = Some(a);
80                } else {
81                    sum = self.merge(&sum, &self.ep[self.eidx(u, a)]);
82                }
83            }
84            let a = parent.unwrap();
85            let i = self.reidx(u, a);
86            self.ep[i] = self.add_subroot(&sum, u, a.label);
87            if inverse.is_some() {
88                self.dp[u] = sum;
89            }
90        }
91        if let Some(inverse) = inverse {
92            for u in order {
93                let sum = if u == 0 {
94                    self.graph.neighbors(u).fold(M::unit(), |sum, a| {
95                        self.merge(&sum, &self.ep[self.eidx(u, a)])
96                    })
97                } else {
98                    let a = self
99                        .graph
100                        .neighbors(u)
101                        .find(|a| a.to == parents[u])
102                        .unwrap();
103                    self.merge(&self.dp[u], &self.ep[self.eidx(u, a)])
104                };
105                self.dp[u] = self.add_root(&sum, u);
106                for a in self.graph.neighbors(u) {
107                    if a.to != parents[u] {
108                        let value = inverse(&sum, &self.ep[self.eidx(u, a)]);
109                        let i = self.reidx(u, a);
110                        self.ep[i] = self.add_subroot(&value, u, a.label);
111                    }
112                }
113            }
114            return;
115        }
116        let mut prefix = Vec::new();
117        for u in order {
118            prefix.clear();
119            prefix.push(M::unit());
120            for a in self.graph.neighbors(u) {
121                prefix.push(self.merge(prefix.last().unwrap(), &self.ep[self.eidx(u, a)]));
122            }
123            self.dp[u] = self.add_root(prefix.last().unwrap(), u);
124            let mut suffix = M::unit();
125            for (k, a) in self.graph.neighbors(u).enumerate().rev() {
126                if a.to != parents[u] {
127                    let i = self.reidx(u, a);
128                    self.ep[i] = self.add_subroot(&self.merge(&prefix[k], &suffix), u, a.label);
129                }
130                suffix = self.merge(&self.ep[self.eidx(u, a)], &suffix);
131            }
132        }
133    }

Source

fn add_subroot(&self, x: &M::T, vid: usize, eid: usize) -> M::T

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 86)

72    fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>) {
73        let (order, parents) = self.graph.tree_order(0);
74        for &u in order.iter().skip(1).rev() {
75            let mut sum = M::unit();
76            let mut parent = None;
77            for a in self.graph.neighbors(u) {
78                if a.to == parents[u] {
79                    parent = Some(a);
80                } else {
81                    sum = self.merge(&sum, &self.ep[self.eidx(u, a)]);
82                }
83            }
84            let a = parent.unwrap();
85            let i = self.reidx(u, a);
86            self.ep[i] = self.add_subroot(&sum, u, a.label);
87            if inverse.is_some() {
88                self.dp[u] = sum;
89            }
90        }
91        if let Some(inverse) = inverse {
92            for u in order {
93                let sum = if u == 0 {
94                    self.graph.neighbors(u).fold(M::unit(), |sum, a| {
95                        self.merge(&sum, &self.ep[self.eidx(u, a)])
96                    })
97                } else {
98                    let a = self
99                        .graph
100                        .neighbors(u)
101                        .find(|a| a.to == parents[u])
102                        .unwrap();
103                    self.merge(&self.dp[u], &self.ep[self.eidx(u, a)])
104                };
105                self.dp[u] = self.add_root(&sum, u);
106                for a in self.graph.neighbors(u) {
107                    if a.to != parents[u] {
108                        let value = inverse(&sum, &self.ep[self.eidx(u, a)]);
109                        let i = self.reidx(u, a);
110                        self.ep[i] = self.add_subroot(&value, u, a.label);
111                    }
112                }
113            }
114            return;
115        }
116        let mut prefix = Vec::new();
117        for u in order {
118            prefix.clear();
119            prefix.push(M::unit());
120            for a in self.graph.neighbors(u) {
121                prefix.push(self.merge(prefix.last().unwrap(), &self.ep[self.eidx(u, a)]));
122            }
123            self.dp[u] = self.add_root(prefix.last().unwrap(), u);
124            let mut suffix = M::unit();
125            for (k, a) in self.graph.neighbors(u).enumerate().rev() {
126                if a.to != parents[u] {
127                    let i = self.reidx(u, a);
128                    self.ep[i] = self.add_subroot(&self.merge(&prefix[k], &suffix), u, a.label);
129                }
130                suffix = self.merge(&self.ep[self.eidx(u, a)], &suffix);
131            }
132        }
133    }

Source

fn add_root(&self, x: &M::T, vid: usize) -> M::T

Examples found in repository ?

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

72    fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>) {
73        let (order, parents) = self.graph.tree_order(0);
74        for &u in order.iter().skip(1).rev() {
75            let mut sum = M::unit();
76            let mut parent = None;
77            for a in self.graph.neighbors(u) {
78                if a.to == parents[u] {
79                    parent = Some(a);
80                } else {
81                    sum = self.merge(&sum, &self.ep[self.eidx(u, a)]);
82                }
83            }
84            let a = parent.unwrap();
85            let i = self.reidx(u, a);
86            self.ep[i] = self.add_subroot(&sum, u, a.label);
87            if inverse.is_some() {
88                self.dp[u] = sum;
89            }
90        }
91        if let Some(inverse) = inverse {
92            for u in order {
93                let sum = if u == 0 {
94                    self.graph.neighbors(u).fold(M::unit(), |sum, a| {
95                        self.merge(&sum, &self.ep[self.eidx(u, a)])
96                    })
97                } else {
98                    let a = self
99                        .graph
100                        .neighbors(u)
101                        .find(|a| a.to == parents[u])
102                        .unwrap();
103                    self.merge(&self.dp[u], &self.ep[self.eidx(u, a)])
104                };
105                self.dp[u] = self.add_root(&sum, u);
106                for a in self.graph.neighbors(u) {
107                    if a.to != parents[u] {
108                        let value = inverse(&sum, &self.ep[self.eidx(u, a)]);
109                        let i = self.reidx(u, a);
110                        self.ep[i] = self.add_subroot(&value, u, a.label);
111                    }
112                }
113            }
114            return;
115        }
116        let mut prefix = Vec::new();
117        for u in order {
118            prefix.clear();
119            prefix.push(M::unit());
120            for a in self.graph.neighbors(u) {
121                prefix.push(self.merge(prefix.last().unwrap(), &self.ep[self.eidx(u, a)]));
122            }
123            self.dp[u] = self.add_root(prefix.last().unwrap(), u);
124            let mut suffix = M::unit();
125            for (k, a) in self.graph.neighbors(u).enumerate().rev() {
126                if a.to != parents[u] {
127                    let i = self.reidx(u, a);
128                    self.ep[i] = self.add_subroot(&self.merge(&prefix[k], &suffix), u, a.label);
129                }
130                suffix = self.merge(&self.ep[self.eidx(u, a)], &suffix);
131            }
132        }
133    }

Source

fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option)

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 49)

37    fn build<I>(graph: &'a UndirectedSparseGraph, rooting: F, inverse: Option<I>) -> Self
38    where
39        I: Fn(&M::T, &M::T) -> M::T,
40    {
41        let dp = vec![M::unit(); graph.vertices_size()];
42        let ep = vec![M::unit(); graph.vertices_size() * 2];
43        let mut self_ = Self {
44            graph,
45            dp,
46            ep,
47            rooting,
48        };
49        self_.rerooting(inverse);
50        self_
51    }

Trait Implementations§

Source §

impl<'a, M: Clone + Monoid, F: Clone + Fn(&M::T, usize, Option<usize>) -> M::T> Clone for ReRooting<'a, M, F>
where M::T: Clone,

Source §

fn clone(&self) -> Self

Returns a duplicate of the value. Read more

1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more

Source §

impl<'a, M: Debug + Monoid, F: Debug + Fn(&M::T, usize, Option<usize>) -> M::T> Debug for ReRooting<'a, M, F>
where M::T: Debug,

Source §

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<'a, M, F> Freeze for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Freeze, F: Freeze,

§

impl<'a, M, F> RefUnwindSafe for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: RefUnwindSafe, F: RefUnwindSafe,

§

impl<'a, M, F> Send for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Send, F: Send,

§

impl<'a, M, F> Sync for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Sync, F: Sync,

§

impl<'a, M, F> Unpin for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Unpin, F: Unpin,

§

impl<'a, M, F> UnsafeUnpin for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: UnsafeUnpin, F: UnsafeUnpin,

§

impl<'a, M, F> UnwindSafe for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: UnwindSafe, F: 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> CloneToUninit for T
where T: Clone,

Source §

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)

Performs copy-assignment from self to dest. Read more

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

impl<T, U> Into 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 §

type Owned = T

The resulting type after obtaining ownership.

Source §

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more

Source §

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more

Source §

impl<T, U> TryFrom 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 for T
where U: TryFrom<T>,

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

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

Performs the conversion.

Struct ReRooting Copy item path

Fields§

Implementations§

impl<'a, M, F> ReRooting<'a, M, F>where M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T,

pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self

pub fn new_with_inverse(graph: &'a UndirectedSparseGraph, rooting: F) -> Selfwhere M: AbelianGroup,

fn build<I>( graph: &'a UndirectedSparseGraph, rooting: F, inverse: Option<I>, ) -> Selfwhere I: Fn(&M::T, &M::T) -> M::T,

fn eidx(&self, u: usize, a: Neighbor<usize, usize>) -> usize

fn reidx(&self, u: usize, a: Neighbor<usize, usize>) -> usize

fn merge(&self, x: &M::T, y: &M::T) -> M::T

fn add_subroot(&self, x: &M::T, vid: usize, eid: usize) -> M::T

fn add_root(&self, x: &M::T, vid: usize) -> M::T

fn rerooting<I: Fn(&M::T, &M::T) -> M::T>(&mut self, inverse: Option<I>)

Trait Implementations§

impl<'a, M: Clone + Monoid, F: Clone + Fn(&M::T, usize, Option<usize>) -> M::T> Clone for ReRooting<'a, M, F>where M::T: Clone,

fn clone(&self) -> Self

fn clone_from(&mut self, source: &Self)

impl<'a, M: Debug + Monoid, F: Debug + Fn(&M::T, usize, Option<usize>) -> M::T> Debug for ReRooting<'a, M, F>where M::T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Auto Trait Implementations§

impl<'a, M, F> Freeze for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: Freeze, F: Freeze,

impl<'a, M, F> RefUnwindSafe for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: RefUnwindSafe, F: RefUnwindSafe,

impl<'a, M, F> Send for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: Send, F: Send,

impl<'a, M, F> Sync for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: Sync, F: Sync,

impl<'a, M, F> Unpin for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: Unpin, F: Unpin,

impl<'a, M, F> UnsafeUnpin for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: UnsafeUnpin, F: UnsafeUnpin,

impl<'a, M, F> UnwindSafe for ReRooting<'a, M, F>where Vec<<M as Magma>::T>: UnwindSafe, F: UnwindSafe,

Blanket Implementations§

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

fn type_id(&self) -> TypeId

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

fn borrow(&self) -> &T

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

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

impl<T> CloneToUninit for Twhere T: Clone,

unsafe fn clone_to_uninit(&self, dest: *mut u8)

impl<T> From<T> for T

fn from(t: T) -> T

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

fn into(self) -> U

impl<T> ToArrayVecScalar for T

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

impl<T> ToOwned for Twhere T: Clone,

type Owned = T

fn to_owned(&self) -> T

fn clone_into(&self, target: &mut T)

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

type Error = !

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

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

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

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

Struct ReRooting

impl<'a, M, F> ReRooting<'a, M, F>
where M: Monoid, F: Fn(&M::T, usize, Option<usize>) -> M::T,

pub fn new_with_inverse(graph: &'a UndirectedSparseGraph, rooting: F) -> Self
where M: AbelianGroup,

fn build<I>( graph: &'a UndirectedSparseGraph, rooting: F, inverse: Option<I>, ) -> Self
where I: Fn(&M::T, &M::T) -> M::T,

impl<'a, M: Clone + Monoid, F: Clone + Fn(&M::T, usize, Option<usize>) -> M::T> Clone for ReRooting<'a, M, F>
where M::T: Clone,

impl<'a, M: Debug + Monoid, F: Debug + Fn(&M::T, usize, Option<usize>) -> M::T> Debug for ReRooting<'a, M, F>
where M::T: Debug,

impl<'a, M, F> Freeze for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Freeze, F: Freeze,

impl<'a, M, F> RefUnwindSafe for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: RefUnwindSafe, F: RefUnwindSafe,

impl<'a, M, F> Send for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Send, F: Send,

impl<'a, M, F> Sync for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Sync, F: Sync,

impl<'a, M, F> Unpin for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: Unpin, F: Unpin,

impl<'a, M, F> UnsafeUnpin for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: UnsafeUnpin, F: UnsafeUnpin,

impl<'a, M, F> UnwindSafe for ReRooting<'a, M, F>
where Vec<<M as Magma>::T>: UnwindSafe, F: UnwindSafe,

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

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

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

impl<T> CloneToUninit for T
where T: Clone,

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

impl<T> ToOwned for T
where T: Clone,

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

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