Cartesian product of iterators

At the moment of writing, this crate provides only Hom2FCartProd and Hom3FCartProd types, which are a two-fold and three-fold Cartesian products of iterators that are "homogenous" in the sense that they produce elements of the same type. Iterators of Hom2FCartProd allow to iterate over all distinct pairs [x,y] that can be formed from elements x and y of the original iterators. Similarly, Hom3FCartProd allows iteration over triples [x,y,z]. The order of the elements in the pairs is preserved.

Example

use cart_prod::specs::Hom2FCartProd;

let it1 = 0..=2;
let it2 = 0..=1;

let mut it = Hom2FCartProd::new(it1, it2);
assert!(it.next() == Some([0, 0]));
assert!(it.next() == Some([0, 1]));
assert!(it.next() == Some([1, 0]));
assert!(it.next() == Some([1, 1]));
assert!(it.next() == Some([2, 0]));
assert!(it.next() == Some([2, 1]));
assert!(it.next() == None);

Features

• Support for no_std environments.
• Usage of arrays instead of tuples for the elements of the Cartesian product can simplify and speed up the code in some cases.

Implementation notes

No variadic genericity

Ideally, Hom*FCartProd should be types-aliases for a partial specializations of CartProd (variadic) generic type. However, Rust does not support variadic generics. See https://github.com/rust-lang/rust/issues/10124. For forward compatibility, the Hom2FCartProd and Hom3FCartProd types are defined in the cart_prod::specs module.

Workaround for absence of variadic genericity

It is possible to provide the type definitions as well as implementations (locally) via macros. However, note that at the moment macros cannot evaluate constants, let alone constant expressions. See https://github.com/rust-lang/rfcs/issues/2279. Due to that (and scarcity of time), such macros are currently not provided.

No support for tuple indexing

Unlike in C++ with std::get, In Rust there's no way to index a tuple by a constant expression. Therefore, it's also impossible to iterate over the tuple of iterators. While its possible to take advantage of trait objects, it's still impossible to generically construct iterators due to absence of variadic genericity.

No top-notch performance guarantees

While the implementations are reasonably efficient, no work was done to benchmark it or to optimize it. While implementation of core::iter::Iterator::next is sufficient for implementation of the trait, it is not the most efficient way to implement it. Only the default implementation of core::iter::Iterator::size_hint was overridden.

No correctness guarantees

The implementation of cart_prod has only a few simple tests. In case of issues, please report them.

Alternatives

• itertools crate provides iproduct! macro that can be used to create an n-fold Cartesian product of iterators. However, the macro can't check if the iterators are homogenous, so it will always iterate over tuples.

• cartesian crate provides cartesian! macro that also can be used to create an n-fold Cartesian product of iterators. However, the macro can't check if the iterators are homogenous, so it will always iterate over tuples. Also, at the moment of writing, the crate has not been maintained for 2+ years.

• permutator crate provides cartesian_product, cartesian_product_cell, and cartesian_product_sync functions that can be used to create an n-fold Cartesian product of slices (and not iterators).

License