Skip to main content

ReduceBalancedIterExt

vortex_utils::iter

Trait ReduceBalancedIterExt 

Source 
pub trait ReduceBalancedIterExt: Iterator {
    // Required methods
    fn reduce_balanced<F>(self, combine: F) -> Option<Self::Item>
       where Self::Item: Clone,
             F: Fn(Self::Item, Self::Item) -> Self::Item;
    fn try_reduce_balanced<F, E>(
        self,
        combine: F,
    ) -> Result<Option<Self::Item>, E>
       where Self::Item: Clone,
             F: Fn(Self::Item, Self::Item) -> Result<Self::Item, E>;
}
Expand description

An extension trait for iterators that provides balanced binary tree reduction.

Unlike Iterator::reduce, which builds a left-leaning linear chain of depth N, reduce_balanced builds a balanced binary tree of depth log(N). This avoids deep nesting that can cause stack overflows on drop or suboptimal evaluation.

reduce:          reduce_balanced:
    f                  f
   / \                / \
  f   d              f   f
 / \                / \ / \
f   c              a  b c  d
|\
a b

Required Methods§

Source

fn reduce_balanced<F>(self, combine: F) -> Option<Self::Item>
where Self::Item: Clone, F: Fn(Self::Item, Self::Item) -> Self::Item,

Like Iterator::reduce, but builds a balanced binary tree instead of a linear chain.

[a, b, c, d] becomes combine(combine(a, b), combine(c, d)).

Returns None if the iterator is empty.

Source

fn try_reduce_balanced<F, E>(self, combine: F) -> Result<Option<Self::Item>, E>
where Self::Item: Clone, F: Fn(Self::Item, Self::Item) -> Result<Self::Item, E>,

Fallible version of reduce_balanced.

Short-circuits on the first error.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§