Crate internal_iterator

source ·
Expand description

Internal iterator equivalent of std::iter::Iterator.

In some cases implementing Iterator can be difficult - for tree shaped structures you would need to store iteration state at every level, which implies dynamic allocation and nontrivial amounts of state. On the other hand, internal iteration is roughly equivalent to calling a provided function on every element you need to yield and is much simpler to implement.

This library aims to provide std-like iteration facilities, but based on internal iteration. The goal is to be easy to make use of and feel familiar to users of Iterator. There is one core trait, InternalIterator. By implementing it you can use its provided methods to construct iterator pipelines similar to those possible by using regular iterators.

Implementing InternalIterator

Whereas the driving method for regular iterators is Iterator::next, the one used here is InternalIterator::try_for_each.

use std::ops::ControlFlow;
use internal_iterator::{InternalIterator, IteratorExt};

struct Tree {
    value: i32,
    children: Vec<Tree>,
}

// We implement InternalIterator on the tree directly. You could also
// introduce a wrapper struct and create it in `.iter()`, `.iter_mut()`, just
// like with usual collections.
impl InternalIterator for Tree {
    type Item = i32;

    fn try_for_each<T, F>(self, mut f: F) -> ControlFlow<T>
    where
        F: FnMut(i32) -> ControlFlow<T>,
    {
        self.iter_helper(&mut f)
    }
}

impl Tree {
    fn iter_helper<T>(&self, f: &mut impl FnMut(i32) -> ControlFlow<T>) -> ControlFlow<T> {
        f(self.value)?;
        for child in &self.children {
            child.iter_helper(f)?;
        }
        ControlFlow::Continue(())
    }
}

// now we can use InternalIterator facilities to construct iterator pipelines

let tree = Tree {
    value: 1,
    children: vec![
        Tree {
            value: 2,
            children: Vec::new(),
        },
        Tree {
            value: 3,
            children: vec![
                Tree {
                    value: 4,
                    children: Vec::new(),
                },
            ]
        },
    ]
};

let result = tree
    .map(|x| x * 2)
    .filter(|&x| x > 3)
    .flat_map(|x| [x, x * 10])
    .collect::<Vec<_>>();

assert_eq!(result, vec![4, 40, 6, 60, 8, 80]);

Differences from std::iter::Iterator

The main difference between Iterator and InternalIterator traits is that all methods in InternalIterator consume the iterators. While for regular iterators you can for example call nth and then keep using the iterator with remaining elements being untouched, you cannot do so with InternalIterator. This is a deliberate choice, as the goal of this library allow having a simpler iterator implementation without losing too much power. Regular iterators must keep state to be able to implement next, but state is not a hard requirement for internal iteration and requiring it would defeat the purpose of the library.

Because internal iterators drive themselves instead of being driven by an outside called, some methods from Iterator are not possible to implement. The most prominent example is Iterator::zip.

nostd compatibility

This crate has two optional features:

  • alloc - includes FromInternalIterator and IntoInternalIterator impls for String, Vec, BTreeMap, and BTreeSet. Brings in a dependency on alloc.
  • std - includes FromInternalIterator and IntoInternalIterator impls for HashSet and HashMap. Brings in a dependency on std.

Both of these features are enabled by default, but you can disable them if you are compiling without std or even without alloc.

Structs

  • BreakValue
    A helper type used in from_fn.
  • Chain
    An iterator that links two iterators together, in a chain.
  • Cloned
    An iterator that clones the elements of an underlying iterator.
  • Copied
    An iterator that copies the elements of an underlying iterator.
  • Enumerate
    An iterator that yields the current count and the element during iteration.
  • Filter
    An iterator that filters the elements of iter with predicate.
  • FilterMap
    An iterator that uses f to both filter and map elements from iter.
  • FlatMap
    An iterator that maps each element to an iterator, and yields the elements of the produced iterators.
  • FromFn
    An iterator returned by from_fn.
  • Inspect
    An iterator that calls a function with a reference to each element before yielding it.
  • Internal
    A wrapper type to convert std::iter::Iterator to InternalIterator.
  • Map
    An iterator that maps the values of iter with f.
  • Skip
    An iterator that skips over n elements of iter.
  • Take
    An iterator that only iterates over the first n iterations of iter.

Traits

Functions

  • from_fn
    Creates an internal iterator from provided closure.