> On 7/25/06, Mark Winterhalder <[EMAIL PROTECTED]> wrote:
> > On 7/25/06, Steven Sacks | BLITZ <[EMAIL PROTECTED]> wrote:
> > > It is iterating. It still needs to iterate through all nested arrays
> > > using the same method, which means recursion.
> >
> > Yes, but function calls aren't the only way to do recursion.
> >
> > What you're doing is essentially like a depth-first search, which can
> > be done with a stack.
>
> Hmm... now that I'm having coffee and slowly waking up, I'm getting
> serious doubts about how to do depth-first without function calls. I'm
> probably wrong, sorry.
No, it's always possible to unroll a recursion, and usually faster. What
about this concept? (I'm sure it could be optimised some more!):
function flatten(a:Array) {
var r:Array = new Array(); // the flattened array
var p:Array = new Array(); // the index stack
var s:Array = new Array(); // the array stack
var c = a; // the currently evaluating array
var i = 0; // the current array index
var t:Boolean; // a flag to show if we've finished a level
while (true&&!Key.isDown(Key.SHIFT)) {
t = true;
for (var i; i < c.length; i++) {
var e = c[i];
if (e instanceof Array) {
p.push(i+1);
i = 0;
s.push(c);
c = e;
t = false;
break;
}
r.push(e);
}
if (t) {
if (p.length) {
i = p.pop();
c = s.pop();
} else {
break;
}
}
}
return r;
};
Here's what I used to test it:
function randomArray(p) {
var l = random(5)
var a = new Array();
for (var i = 0; i < l; i++) {
if (Math.random() < p) {
a.push(i);
} else {
a.push(randomArray(p + 0.2));
}
}
return a;
}
var a:Array = randomArray(0.4);
trace(a+" "+a.length)
var r:Array = flatten(a)
trace(r+" "+r.length);
And here's the result:
,0,1,2,1,0,1,2,3,0,0,1,2 4
0,1,2,1,0,1,2,3,0,0,1,2 12
Note that it works fine even with empty arrays.
Danny
_______________________________________________
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
