Struct seg_tree::utils::PersistentWrapper

pub struct PersistentWrapper<T> where
    T: Node,  { /* private fields */ }

A simple wrapper for nodes to easily implement PersistentNode. If the wrapped node implements LazyNode the wrapper also implements it.

Trait Implementations

impl<T: Clone> Clone for PersistentWrapper<T> where
    T: Node, 

fn clone(&self) -> PersistentWrapper<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> LazyNode for PersistentWrapper<T> where
    T: LazyNode, 

fn lazy_update(&mut self, i: usize, j: usize)

The following invariant must be met while implementing this method, if lazy_value is called immediately after this function then it must return None. (See Option::take)

fn update_lazy_value(&mut self, new_value: &<Self as Node>::Value)

The following invariant must be met while implementing this method, if lazy_value is called immediately after this function then it must return Some(&value).

fn lazy_value(&self) -> Option<&<Self as Node>::Value>

Must return a reference to the current lazy value only if it exists.

impl<T> Node for PersistentWrapper<T> where
    T: Node, 

type Value = <T as Node>::Value

This type corresponds to the type of the information to create the node with Node::initialize.

fn initialize(value: &Self::Value) -> Self

Function to create nodes from saved value, it is assumed that even if there’s more data saved in the node, value should have enough data to recreate all of the data in the node.

fn combine(a: &Self, b: &Self) -> Self

Function which will combine nodes a and b, where each corresponds to segments [i,j] and [j+1,k] respectively, into a node which corresponds to the segment [i,k]. This function must be associative (taking * as a symbol for combine, we have that a*(b*c)==(a*b)*c is true), but need not be commutative (it’s not necessarily true that a*b==b*a).

fn value(&self) -> &Self::Value

Method which returns a reference to the current saved value.

impl<T> PersistentNode for PersistentWrapper<T> where
    T: Node, 

fn left_child(&self) -> usize

Gives index of left child.

fn right_child(&self) -> usize

Gives index of right child.

fn set_children(&mut self, left: usize, right: usize)

Sets saved index of both left and right children. (It’s assumed that before a call to this, the node has invalid indices.)