Struct fingertrees::FingerTree
source · Expand description
FingerTree implemenetation
FingerTree is parametrized by two type parpameters
Implementations§
source§impl<R, V> FingerTree<R, V>where
R: Refs<V>,
V: Measured,
impl<R, V> FingerTree<R, V>where
R: Refs<V>,
V: Measured,
sourcepub fn push_left(&self, value: V) -> Self
pub fn push_left(&self, value: V) -> Self
Creates new tree with value prepended to the left side of the tree
Amortized complexity: O(1)
sourcepub fn push_right(&self, value: V) -> Self
pub fn push_right(&self, value: V) -> Self
Creates new tree with value prepended to the right side of the tree
Amortized complexity: O(1)
sourcepub fn view_left(&self) -> Option<(V, Self)>
pub fn view_left(&self) -> Option<(V, Self)>
Destrutures tree into a tuple with first element of it containing first element from the left side of the tree, and second element contains tree with reset of the elements
Amortized complexity: O(1)
sourcepub fn view_right(&self) -> Option<(V, Self)>
pub fn view_right(&self) -> Option<(V, Self)>
Destrutures tree into a tuple with first element of it containing first element from the left side of the tree, and second element contains tree with reset of the elements
Amortized complexity: O(1)
sourcepub fn split<F>(&self, pred: F) -> (FingerTree<R, V>, FingerTree<R, V>)where
F: FnMut(&V::Measure) -> bool,
pub fn split<F>(&self, pred: F) -> (FingerTree<R, V>, FingerTree<R, V>)where
F: FnMut(&V::Measure) -> bool,
Destructures tree into two three, using provided predicate.
Predicate must be monotinic function accepting accumulated measure of elments
and changing its value from true
to false
. This function basically behave
as if we would iterate all elements from left to right, and accumlating measure
of all iterated elements, calling predicate on this accumulated value and once
its value flips from true
to false
we stop iteration and form two threes
from already iterated elements and the rest of the elements.
Complexity: O(ln(N))
Trait Implementations§
source§impl<'a, 'b, R, V> Add<&'b FingerTree<R, V>> for &'a FingerTree<R, V>where
R: Refs<V>,
V: Measured,
impl<'a, 'b, R, V> Add<&'b FingerTree<R, V>> for &'a FingerTree<R, V>where
R: Refs<V>,
V: Measured,
§type Output = FingerTree<R, V>
type Output = FingerTree<R, V>
+
operator.