Proposal: Add ReverseArrayIterator and ForwardArrayIterator to SPL

Hello, everyone!

This proposal adds two new classes to the SPL:

• Spl\ReverseArrayIterator. It iterates over an array in reverse
  order. It does not duplicate the array.
• Spl\ForwardArrayIterator. It iterates over an array in forward
  (normal) order. It does not duplicate the array.

They both implement Countable which returns the count() of the
array. The PR has some examples and discusses why I am proposing
ForwardArrayIterator when there is already ArrayIterator, the
short of which is for performance. There are timing numbers in one of
the comments.

When it comes time to vote I may merge this into another RFC with
CachedIterable by Tyson Andre, which I recommend readers also
take a look at. Whether we team up for the RFC vote or not, I wanted
to get this out there for discussion and review.

Hey Levi,

I like the general idea of having an "ArrayIterator but sane".

That said, I don't think that the ReverseArrayIterator + ForwardArrayIterator pair of iterators approaches this problem correctly. There are plenty of iterators that could be run in reverse, and I think it would be silly to create two classes for each of them. E.g. if we introduce an ObjectPropertyIterator, should there be both ForwardObjectPropertyIterator and ReverseObjectPropertyIterator? I don't think so.

I think the correct abstraction for bidirectional iterators is to introduce an interface

// Or "ReversibleIterator"
interface BidrectionalIterator extends Iterator {
public function prev(): void;
public function end(): void;
}

and then a class along the lines of:

class ReverseIterator implements BidirectionalIterator {
public function __construct(private BidirectionalIterator $iter) {}

public function `next()` { $this->iter->prev(); }
// etc.

}

This would replace "new ReverseArrayIterator($array)" with "new ReverseIterator(new ArrayIterator($array))", but in a way that is general, and composes.

Regards,
Nikita

I wrote an implementation of this idea two years ago:
https://github.com/php/php-src/compare/master...morrisonlevi:BidirectionalArrayIterator

It's fine for arrays, but not all structures that you can iterate
through forward or reverse. For instance, tree structures can be
traversed forward or reverse, but bidirectionally is far more
difficult (and I did not find any pre-existing solutions in this
space, btw). I do have repositories with tree structures, so it's not
just theoretical.

Another factor for abandonment was ergonomics. This is not great: new ReverseIterator(new BidirectionalArrayIterator($array)). It's mildly
less performant as well, having to create two objects, and then having
delegation through methods.

Let me know if you think of any way to reconcile these issues, and
I'll do the same.

Hello, everyone!

This proposal adds two new classes to the SPL:

• Spl\ReverseArrayIterator. It iterates over an array in reverse
  order. It does not duplicate the array.
• Spl\ForwardArrayIterator. It iterates over an array in forward
  (normal) order. It does not duplicate the array.

They both implement Countable which returns the count() of the
array. The PR has some examples and discusses why I am proposing
ForwardArrayIterator when there is already ArrayIterator, the
short of which is for performance. There are timing numbers in one of
the comments.

When it comes time to vote I may merge this into another RFC with
CachedIterable by Tyson Andre, which I recommend readers also
take a look at. Whether we team up for the RFC vote or not, I wanted
to get this out there for discussion and review.

Hey Levi,

I like the general idea of having an "ArrayIterator but sane".

That said, I don't think that the ReverseArrayIterator +
ForwardArrayIterator pair of iterators approaches this problem correctly.
There are plenty of iterators that could be run in reverse, and I think it
would be silly to create two classes for each of them. E.g. if we introduce
an ObjectPropertyIterator, should there be both
ForwardObjectPropertyIterator and ReverseObjectPropertyIterator? I don't
think so.

I think the correct abstraction for bidirectional iterators is to introduce
an interface

// Or "ReversibleIterator"
interface BidrectionalIterator extends Iterator {
public function prev(): void;
public function end(): void;
}

and then a class along the lines of:

class ReverseIterator implements BidirectionalIterator {
public function __construct(private BidirectionalIterator $iter) {}

public function `next()` { $this->iter->prev(); }
// etc.

}

This would replace "new ReverseArrayIterator($array)" with "new
ReverseIterator(new ArrayIterator($array))", but in a way that is general,
and composes.

Regards,
Nikita

After thinking about it for a while, I think this will be fine. It
doesn't encroach on the reversible IteratorAggregate space, which is
the space that I didn't like from my previous proof-of-concept.

I'd like it if BidirectionalArrayIterator was shorter, but plain
\Spl\ArrayIterator is too likely to be confusing with
\ArrayIterator and that's the only meaningfully shorter name I've
thought of yet. This also plays into the bad ergonomics of the
reversed array iterator:
new ReverseIterator(new BidirectionalArrayIterator($array))

But as you say, the reversed version will not be common.

I'll code this up soon unless someone objects. I'm very open to naming
suggestions for a better performing, simpler array iterator.