Struct fingertrees::FingerTree

pub struct FingerTree<R, V> where
    R: Refs<V>,
    V: Measured,  { /* fields omitted */ }

FingerTree implemenetation

FingerTree is parametrized by two type parpameters

• R - type family trick which determines type of references used in implementation. This crate implementes ArcRefs which is based on Arc atomic reference counter, and RcRefs which is based on Rc.
• V - value type which must be measurable and cheaply clonable.

Implementations

impl<R, V> FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

pub fn new() -> Self

Constructs a new, empty FingerTree

Complexity: O(1)

pub fn is_empty(&self) -> bool

Returns true if finger tree is empty

Complexity: O(1)

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)

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)

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)

pub fn view_right(&self) -> Option<(V, Self)>

Destrutures tree into a tuple with first element of it containing first element from the right side of the tree, and second element contains tree with reset of the elements

Amortized complexity: O(1)

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 elements and changing its value from false to true. 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 false to true we stop iteration and form two trees from already iterated elements and the rest of the elements.

Complexity: O(ln(N))

pub fn split_left<F>(&self, pred: F) -> FingerTree<R, V> where
    F: FnMut(&V::Measure) -> bool, 

partial logic from .split(...) with only left part returned

pub fn split_right<F>(&self, pred: F) -> FingerTree<R, V> where
    F: FnMut(&V::Measure) -> bool, 

partial logic from .split(...) with only right part returned

pub fn find<F>(&self, pred: F) -> Option<&V> where
    F: FnMut(&V::Measure) -> bool, 

Find element for which predicate function pred flips from false to true

pub fn concat(&self, other: &Self) -> Self

Construct new finger tree wich is concatination of self and other

Complexity: O(ln(N))

pub fn iter(&self) -> Iter<R, V>

Double ended iterator visiting all elements of the tree from left to right

Trait Implementations

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>

The resulting type after applying the + operator.

fn add(self, other: &'b FingerTree<R, V>) -> Self::Output

Performs the + operation.

impl<R, V> Add<FingerTree<R, V>> for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

type Output = FingerTree<R, V>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self::Output

Performs the + operation.

impl<R, V> Clone for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<R, V> Debug for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured + Debug, 

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

Formats the value using the given formatter.

impl<R, V> Default for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

fn default() -> Self

Returns the “default value” for a type.

impl<R, V> FromIterator<V> for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, R, V> IntoIterator for &'a FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

type Item = V

The type of the elements being iterated over.

type IntoIter = Iter<R, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<R, V> IntoIterator for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

type Item = V

The type of the elements being iterated over.

type IntoIter = Iter<R, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<R, V> Measured for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured, 

type Measure = V::Measure

Measure type

fn measure(&self) -> Self::Measure

Assocated measure with given value

impl<R, V> PartialEq<FingerTree<R, V>> for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured + PartialEq, 

fn eq(&self, other: &FingerTree<R, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<R, V> Eq for FingerTree<R, V> where
    R: Refs<V>,
    V: Measured + Eq,