What is the quickest way to iterate through a Iterator in reverse

Question

Let's say I'd like to iterate through a generic iterator in reverse, without knowing about the internals of the iterator and essentially not cheating via untyped magic and assuming this could be any type of iterable, which serves a iterator; can we optimise the reverse of a iterator at runtime or even via macros?

Forwards

var a = [1, 2, 3, 4].iterator();
// Actual iteration bellow
for(i in a) {
   trace(i);
}

Backwards

var a = [1, 2, 3, 4].iterator();
// Actual reverse iteration bellow
var s = [];
for(i in a) {
    s.push(i);    
}
s.reverse();
for(i in s) {
    trace(i);    
}

I would assume that there has to be a simpler way, or at least fast way of doing this. We can't know a size because the Iterator class doesn't carry one, so we can't invert the push on to the temp array. But we can remove the reverse because we do know the size of the temp array.

var a = [1,2,3,4].iterator();
// Actual reverse iteration bellow
var s = [];
for(i in a) {
    s.push(i);    
}
var total = s.length;
var totalMinusOne = total - 1;
for(i in 0...total) {
    trace(s[totalMinusOne - i]);    
}

Is there any more optimisations that could be used to remove the possibility of the array?

Answer 1

It bugs me that you have to duplicate the list, though... that's nasty. I mean, the data structure would ALREADY be an array, if that was the right data format for it. A better thing (less memory fragmentation and reallocation) than an Array (the "[]") to copy it into might be a linked List or a Hash.

But if we're using arrays, then Array Comprehensions (http://haxe.org/manual/comprehension) are what we should be using, at least in Haxe 3 or better:

var s = array(for (i in a) i);

Ideally, at least for large iterators that are accessed multiple times, s should be cached.

To read the data back out, you could instead do something a little less wordy, but quite nasty, like:

for (i in 1-s.length ... 1) {
    trace(s[-i]);
}

But that's not very readable and if you're after speed, then creating a whole new iterator just to loop over an array is clunky anyhow. Instead I'd prefer the slightly longer, but cleaner, probably-faster, and probably-less-memory:

var i = s.length;
while (--i >= 0) {
    trace(s[i]);
}

Answer 2

First of all I agree with Dewi Morgan duplicating the output generated by an iterator to reverse it, somewhat defeats its purpose (or at least some of its benefits). Sometimes it's okay though.

Now, about a technical answer:

By definition a basic iterator in Haxe can only compute the next iteration.

On the why iterators are one-sided by default, here's what we can notice:

1. if all if iterators could run backwards and forwards, the Iterator classes would take more time to write.
2. not all iterators run on collections or series of numbers.

E.g. 1: an iterator running on the standard input.

E.g. 2: an iterator running on a parabolic or more complicated trajectory for a ball.

E.g. 3: slightly different but think about the performance problems running an iterator on a very large single-linked list (eg the class List). Some iterators can be interrupted in the middle of the iteration (Lambda.has() and Lambda.indexOf() for instance return as soon as there is a match, so you normally don't want to think of what's iterated as a collection but more as an interruptible series or process iterated step by step).

While this doesn't mean you shouldn't define two-ways iterators if you need them (I've never done it in Haxe but it doesn't seem impossible), in the absolute having two-ways iterators isn't that natural, and enforcing Iterators to be like that would complicate coding one.

An intermediate and more flexible solution is to simply have ReverseXxIter where you need, for instance ReverseIntIter, or Array.reverseIter() (with using a custom ArrayExt class). So it's left for every programmer to write their own answers, I think it's a good balance; while it takes more time and frustration in the beginning (everybody probably had the same kind of questions), you end up knowing the language better and in the end there are just benefits for you.