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", so this trait is not object safe.

Implementors§