I think I see now; you are trying to make the optimizations of InfiniteIterator
transparent, so that the benefits are received even when using the standard iterator API. To be honest, I hadn't even thought that far ahead!
What I was talking about in the sentence that leonardo quoted was the problem that having InfiniteIterator
will end up requiring at least two extremely-similar looking impls for many iterators. For instance, here's an iterator that takes two sorted iterators of Item=<(usize, _)>
and produces pairs from the matching indices:
impl<A,B,T,U> Iterator for SparseIntersection<A,B>
where A: Iterator<Item=(usize,T)>,
B: Iterator<Item=(usize,U)>,
{
type Item = (usize,(T,U));
fn next(&mut self) -> Option<Self::Item> {
let &mut SparseIntersection { ref mut a, ref mut b } = self;
if let (Some((i0,a0)),Some((k0,b0))) = (a.next(),b.next()) {
let (mut icur,mut acur) = (i0,a0);
let (mut kcur,mut bcur) = (k0,b0);
loop {
// scan to an index present in both vectors
while icur < kcur {
if let Some((inext,anext)) = a.next() { acur = anext; icur = inext; }
else { return None } // stop immediately if either iterator ends
}
while kcur < icur {
if let Some((knext,bnext)) = b.next() { bcur = bnext; kcur = knext; }
else { return None }
}
// at this point, kcur >= icur
if icur == kcur {
return Some((icur, (acur,bcur)));
}
}
// at least one iterator had no elements remaining
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, aupper) = self.a.size_hint();
let (_, bupper) = self.b.size_hint();
(0, ::std::cmp::min(aupper,bupper)) // any number of items may not match, so no lower bound
}
}
This is infinite when both inputs are infinite. Let's implement InfiniteIterator
for it:
impl<A,B,T,U> InfiniteIterator for SparseIntersection<A,B>
where A: InfiniteIterator<Item=(usize,T)>,
B: InfiniteIterator<Item=(usize,U)>,
{
type Item = (usize,(T,U));
fn nooxt(&mut self) -> Self::Item {
let &mut SparseIntersection { ref mut a, ref mut b } = self;
let ((i0,a0),(k0,b0)) = (a.nooxt(),b.nooxt());
let (mut icur,mut acur) = (i0,a0);
let (mut kcur,mut bcur) = (k0,b0);
loop {
// scan to an index present in both vectors
while icur < kcur {
let (inext,anext) = a.nooxt();
acur = anext; icur = inext;
}
while kcur < icur {
let (knext,bnext) = b.nooxt();
bcur = bnext; kcur = knext;
}
// at this point, kcur >= icur
if icur == kcur {
return (icur, (acur,bcur));
}
}
}
}
Writing the method was easy; I just copied, pasted, and collapsed the if let
s. The true burden lies in maintaining it:
- We have a strikingly similar method to the first one...
- ...which differs in ways that are not simple to factor out without obscuring the logic...
- ...which clearly requires a wide gamut of unit tests if it is not factored...
- ...and it will be nontrivial to derive said unit tests from those that already exist for
next
.
These are many of the same reasons which make next_back
impls rightfully scary, although the differences between next
and next_back
are often at least easier to factor out (and the payoff is far greater!)
SparseIntersection
has a sister function SparseUnion
, which is infinite when either input iterator is infinite. Even assuming that coherence weren't an issue, the algorithm would need to be implemented four times (one Iterator
plus three impl InfiniteIterator
s) to have unambiguous implementations under a lattice rule. A scenario such as that calls for some... creative refactorizations. (which I can very well imagine might involve macros and Always<T>
)