Iterating a List in Reverse

[Nathan Hüsken]

There seems to be no option for that. Or am I missing something?

I need a optimized solution, so copying into an array or duplicating the
list I would like to avoid.

[Juraj Kirchheim]

Since it's not a doubly linked list, you can only iterate it in one direction.

Generally I advise against using List and just stick to arrays. They are easily iterated in both directions and pop and push have very decent amortized speed (not so much shift/unshift or insert/splice/remove towards the beginning). On most platforms arrays are simply faster.

If you have a concrete performance sensitive use case, then roll your own data structure optimized for the operations you need and the space requirements at hand.

Best,

Juraj

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---
You received this message because you are subscribed to the Google Groups "Haxe" group.
For more options, visit https://groups.google.com/d/optout.

[Philippe Elsass]

I think the question is more about:

- why isn't it possible to write: for(i in 10...0)

- and why isn't there a reversed order: for(a in b)

--

Philippe

[Juraj Kirchheim]

On Tue, Mar 24, 2015 at 11:45 AM, Philippe Elsass <philipp...@gmail.com> wrote:

I think the question is more about:

I think not, but ok ;)

 

- why isn't it possible to write: for(i in 10...0)

It is possible. The loop will start with i = 10 and run while i < 0. Might seem like a stupid thing to do, but when it's `for (i in min...max) {}` then I'd rather not just wind up with a backward loop for min > max. 

There's also the issue of not knowing at compile time which direction the loop will be, which most likely leads to less efficient code.

The loop must be explicitly defined. One solution is tink_lang's `for (i -= i in 10...0) {}`, another is detailed below.

- and why isn't there a reversed order: for(a in b)

Because in general, that is impossible. Iterators and singly linked list are unidirectional by their very nature. So the general solution to that is to buffer the whole thing and then loop through the buffer in reverse order. That and a solution for the above problem is implemented here: http://try.haxe.org/#6a4E0

Notice how efficient the resulting code is for the optimized cases.

Best,

Juraj

[Rafael Oliveira]

for a array, the inverse is
for (i in -array.length...0)
var n = -i;

[Juraj Kirchheim]

That should be `var n = 1 - i;` ;)

[Rafael Oliveira]

if the length of the array is 10, the first value will be -10, so
n = -(-10) = 10

[Nathan Hüsken]

Am 24.03.2015 um 13:54 schrieb Rafael Oliveira:
> if the length of the array is 10, the first value will be -10, so
> n = -(-10) = 10
>

Which is not the last index of the array, but "9" is.

Thanks for all the input. I was unaware that "List" is not double linked.
Also, I will re-evaluate if I should use arrays or my own data structure.

[Mike Robinson]

Waxing philosophic here for a sec, I'm always of the opinion that you should define your own data-structure (class), even if the underlying representation is (say, for the moment, at least), "an array."  Likewise, if you need an iterator that runs backwards, coin one and put it into the class.  Put all of the logic that anyone, anywhere, uses, right there into that class ... so that, when looking just at the definition of the class, you know that you're looking at what "everyone, everywhere" is using to get to that data and to do everything that need be done to it.  If later on you decide a more sophisticated data structure needs to be "dropped in," you only have to "drop it in" once.

[Justin L Mills]

Did you do any tests against

haxelib polygonal-ds

since it includes an DLL.

Documented here

http://polygonal.github.io/ds/doc/

Possible use

var dll = new DLL<String>();
dll.append( 'a' );
dll.append( 'b' );
dll.append( 'c' );
dll.reverse();
for( i in dll.iterator() ){ trace( i ); }
dll.reverse();