Crate internal_iterator[−][src]

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::find_map.

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 find_map<T, F>(self, mut f: F) -> Option<T>
    where
        F: FnMut(i32) -> Option<T>,
    {
        self.find_map_helper(&mut f)
    }
}

impl Tree {
    fn find_map_helper<T>(&self, f: &mut impl FnMut(i32) -> Option<T>) -> Option<T> {
        let result = f(self.value);
        if result.is_some() {
            return result;
        }
        for child in &self.children {
            let result = child.find_map_helper(f);
            if result.is_some() {
                return result;
            }
        }
        None
    }
}

// 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| vec![x, x * 10]
        .into_iter()
        .into_internal())
    .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 FromIterator impls for String, Vec, BTreeMap, and BTreeSet. Brings in a dependency on alloc.
std - includes FromIterator impls for HashSet and HashMap. Brings in a dependency on std.