Skip to main content

EulerTourKind

competitive::tree::euler_tour

Trait EulerTourKind 

Source 
pub trait EulerTourKind {
    const USE_LAST: bool = false;
    const USE_VISIT: bool = false;

    // Provided method
    fn size(n: usize) -> usize { ... }
}

Provided Associated Constants§

Source

const USE_LAST: bool = false

Source

const USE_VISIT: bool = false

Provided Methods§

Source

fn size(n: usize) -> usize

Examples found in repository?
crates/competitive/src/tree/euler_tour.rs (line 123)
118    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::First>, Vec<T>)
119    where
120        T: Clone,
121    {
122        assert_eq!(s.len(), self.tree.vertices_size());
123        let mut trace = Vec::with_capacity(marker::First::size(s.len()));
124        let tour = self.build_with_trace(|u| {
125            trace.push(s[u].clone());
126        });
127        (tour, trace)
128    }
129}
130
131impl EulerTourBuilder<'_, marker::FirstLast> {
132    pub fn build_with_rearrange<T>(
133        self,
134        s: &[T],
135        mut inverse: impl FnMut(T) -> T,
136    ) -> (EulerTour<marker::FirstLast>, Vec<T>)
137    where
138        T: Clone,
139    {
140        assert_eq!(s.len(), self.tree.vertices_size());
141        let mut visited = vec![false; s.len()];
142        let mut trace = Vec::with_capacity(marker::FirstLast::size(s.len()));
143        let tour = self.build_with_trace(|u| {
144            if !visited[u] {
145                trace.push(s[u].clone());
146                visited[u] = true;
147            } else {
148                trace.push(inverse(s[u].clone()));
149            }
150        });
151        (tour, trace)
152    }
153}
154
155impl EulerTourBuilder<'_, marker::Visit> {
156    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::Visit>, Vec<T>)
157    where
158        T: Clone,
159    {
160        assert_eq!(s.len(), self.tree.vertices_size());
161        let mut trace = Vec::with_capacity(marker::Visit::size(s.len()));
162        let tour = self.build_with_trace(|u| {
163            trace.push(s[u].clone());
164        });
165        (tour, trace)
166    }

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§