Reverse Loop Array

[Adam Holland]

Hopefully a simple question. Is there a way to do a reverse loop through an Array? I need to loop through it and splice elements out of it. Thanks

[Juraj Kirchheim]

There's a number of ways to go about that.

Your approach:

var a = [...];
for (i in 0...a.length)
if (!keep(a[a.length-i]])
a.splice(a.length-1, 1);

Given that a.splice is actually O(R) (where R is the length of the
"right" array), this is actually rather expensive.
If for every element, the probability, that it should be removed is p,
then for the k-th element from the end of the array, the average cost
is O(p * (p-1) * k), so the overall complexity is O(N + N * (p-1) * p
* N / 2), which is O(N^2) unless p is sufficiently close to 0 or 1.

I suggest building a new array:

var ret = [];
for (e in a)
if (keep(e))
a.push(e);

Or perhaps like this:

using Lambda;
a.filter(keep).array();

The last one does involve quite a lot of overhead, but has overall
linear complexity.

On Tue, Jan 10, 2012 at 1:45 PM, Adam Holland <adgho...@gmail.com> wrote:
> Hopefully a simple question. Is there a way to do a reverse loop through an
> Array? I need to loop through it and splice elements out of it. Thanks
>

> --
> To post to this group haxe...@googlegroups.com
> http://groups.google.com/group/haxelang?hl=en

[Baluta Cristian]

You could simply reverse() it then iterate in the normal way.

--
Băluță Cristian
http://ralcr.com
http://imagin.ro

[Juraj Kirchheim]

I think the point of reverse iteration is that you can remove elements
*while* you iterate.
If you remove elements during forward iteration, you mess up the
iteration itself, because the elements that you haven't touched yet
change their position, whereas if you do it from the end, then then
the elements you haven't touched yet are unaffected by the splice.

[Adam Holland]

ah so it's not as simple as I was hoping, thanks for some solutions but they all seem quite expensive as its is part of a game loop. I guess I will just use a list instead as removing the items shouldn't be a problem.

Thanks!

Perhaps for Haxe v3 we could add it, some thing simple like "for(i in arrayLength...0)" or "var iter = new IntIter(arrayLength, 0)"

[Baluta Cristian]

the "..." is a shortcut to an Iterator, so you can create yours.

I made once this one but i don't remember if i used it and if works

class ReversedIntIter {

    var min : Int;

    var max : Int;

    public function new (max:Int, min:Int) {

        this.min = min;

        this.max = max;

    }

    public function hasNext() {

        return ( min < max );

    }

    public function next() {

        return max--;

    }

}

--

To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en

[Simon Krajewski]

Am 10.01.2012 14:05, schrieb Juraj Kirchheim:
> Or perhaps like this:
>
> using Lambda;
> a.filter(keep).array();

I always cringe when I see .array(), but it's the best you can currently
do with Lambda. Are there any plans to unify the collections for haxe 3
so that Array, List and FastList share a basic Collection interface that
defines add/remove/length operations? This would allow Lambda functions
to be defined like e.g.

static public function filter<S>(input:Iterable<S>, f: S->Bool,
?output:Collection<S>):Collection<S>
{
if (output == null) output = new List<S>();
for ( x in input )
if( f(x) )
output.add(x);
return output;
}

so the caller could supply a new List() or new FastList() if he so desires:

var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var colList = MyLambda.filter(array, function(i) return i > 5);
// works just like before
var colArray = MyLambda.filter(array, function(i) return i > 5,
new Array()); // works on an array
var colFastList = MyLambda.filter(array, function(i) return i >
5, new FastList()); // sort of works on a FastList

(Actually FastList is a bad example because it does everything in
reverse.) This would even allow Lambda usage for custom collections if
they implement the Collection interface.

Regards
Simon

[Adam Holland]

Hey thanks, I should have thought of creating my own iterator but I did think there would be something else somewhere in the API that would already do this. Thanks, I will give it a go.

[Juraj Kirchheim]

Again: reverse looping through an array and splicing is likely to turn
out O(N^2) (depending on the distribution and frequency of the
elements that need removal). Building a new array is cheaper.

Imagine the following (constructed) scenario:

You have 10000 entries in your array, and all the elements at even
indices need removal.

When splicing at index 9998, you need to copy 1 entry to a new
position, when at index 9996, you will need to copy 2 entries, at 9994
it's 3 entries and at 0 it's 5000 entries, which means that in the end
you are going to cause 12502500 copy operations.
If you build a new array instead you have 5000 copy operations.

So for the sake of your game speed, don't do that.

[Adam Holland]

back2Dos thanks for the example, I have always hated rever iterating through arrays but never thought creative a new array would be a better option. Thanks!

[JLM]

So can you clarify something I am not sure I follow, you can't do

for (i in a.length...0 )

or a negative while loop...

because internally it has to loop through the rest to find the nth?

[Martijn Loots]

Hi Adam.

I posted this on the haXe site some time ago. IMHO the most efficient
solution for you: http://haxe.org/doc/snip/countdownintiter

Good luck,
--
-Martijn

--
-Martijn @..@ ( Martijn Loots - Hengelo [NL] )
- (`--') ( martijn<@>cosix.com - www.cosix.com )
- ( >__< ) ----------------------------------------
- ^^^ ^^^ ( Netwerken, Security, Open Source )

[JLM]

Martjn

ok so you can't iterate backwards mores the pitty, but still don't see why something like this would not be as good?

var i = arr.length;
while( --i > -1 ) keep( arr[ i ] );

Cheers

;j

[Justin Donaldson]

Reversing doesn't let you remove elements from the array safely in all cases, just the tail.  If you're looking for (theoretically) quick edits just for the tail, you can do:

while(arr[arr.length-1] == some_condition) arr.pop();

But, if you're removing stuff in the middle, you might as well create a new array, the memory manager will do it anyways behind the scenes.  The only other thing to keep in mind is that some run times like php use int hashes for arrays. 

There's other reasons for wanting a count down iterator though, of course.

-Justin

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en

--
Justin Donaldson, BigML, Inc.
o: 313-31BIGML | c: 919-BUZZJJD

[Martijn Loots]

On Tue, 10 Jan 2012, JLM wrote:

> Martjn
>
Hiya.

It would be perfect. He *did* ask for a reverse iterator though... :)

[Thomas Fétiveau]

Hi,

I'm currently using haxe remoting with a haxe.remoting.HttpConnection.

Is there a way to set custom haxe remoting headers in call ?

If not, is there a way to set custom HTTP headers with
haxe.remoting.HttpConnection and how to read them on the receiving side ?

Cheers,

zabojad

[JLM]

Thomas - Can you try creating a new thread, it's confusing to post it
in this thread. I can create one or maybe the next person to reply can
create one. Cheers ;j

[thomas....@gmail.com]

Ups, I've just realized my mail has been attached to this thread.

Sure, I'll create a new thread, sorry for that.

I've actually just sent a new mail to haxe[at]lists.motion-twin.com thinking that it would create a new thread...

[Żabojad]

Hi,

I'm currently using haxe remoting with a haxe.remoting.HttpConnection.

Is there a way to set custom haxe remoting headers in calls ?

[Cauê Waneck]

I don't think there is, you should need to subclass HtppConnection and add your custom headers.

But anyway haxe already sets a custom header for its remoting, I think it's called X-Haxe-Remoting

Cheers! :)

2012/1/16 Żabojad <thomas.fet...@googlemail.com>

--