AS3 recursive object scan without repeats?

Question

While recursive scans are commonly use to scan through nested objects / data. It can go on an infinite loop, if some of the objects references one another. So what is the most effective way to scan all items, without crashing the computer, nor skipping a specified parameter?

Here is an example of a recursive scanner...

/**
 * Triggers the scan function for each object given
 **/
function recursiveScanner( object:* , scanFunction:Function ):void {
    if( typeof(object) == 'object' ) {
        for( var key:String in object ) {
            recursiveScanner( object[key], scanFunction );
        }
    } else {
        scanFunction.call(this, object);
    }
}

However a huge problems occur when the following is passed in

//...
obj1.next = obj2;
//...
obj2.next = obj3;
//...
obj3.next = obj1;
//...
recursiveScanner(obj1, scanFuction);

The objects will trigger scans for one another in an eternal loop. So is there a way to solve this?

I do believe in C/C++ : Each scanFunction call, will be added into a list consisting of scanned 'memory address', thus preventing a repeat. Is this even possible in AS3? Is there a more elegent way?

grapefrukt · Accepted Answer · 2011-06-12 10:05:37Z

10

Use a Dictionary to keep a list of scanned objects and ignore them if they've been scanned before:

/**
 * Triggers the scan function for each object given
 **/
function recursiveScanner( object:* , scanFunction:Function, ignoreList:Dictonary = null ):void {
    // if we have no list, create one
    if (!ignoreList) ignoreList = new Dictionary();

    // if the item is in the list, we bail
    if (ignoreList[object]) return;

    // mark the item as scanned before recursing into it
    ignoreList[object] = true;

    if( typeof(object) == 'object' ) {
        for( var key:String in object ) {
            recursiveScanner( object[key], scanFunction, ignoreList );
        }
    } else {
        scanFunction.call(this, object);
    }
}

answered Jun 12, 2011 at 10:05

grapefrukt

27.1k6 gold badges52 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

PicoCreator Over a year ago

Ahh... The object ID would be used in the dictionary as a an attribute... Thx for the solution =)

mpdonadio · Accepted Answer · 2011-06-12 17:15:47Z

2

OK, accept the answer from @grapefrukt, but here is some background.

In computer science terms, the problem is equivalent to traversing a directed graph that can contain cycles.

There are essentially two naive ways (ie, not following a heuristic) to traverse, depth first or breadth first.

I'll leave it as an exercise to determine whether the sample code is BFS or DFS.

answered Jun 12, 2011 at 17:15

mpdonadio

2,9413 gold badges37 silver badges56 bronze badges

1 Comment

PicoCreator Over a year ago

Depth first :) Which is optimal for my deployment over breadth first, as I will have to read all nodes with no repeat in my deployment. So having a FIFO from BFS is a unneeded cost. Thx for the good read and reference anyway =) didn't know bout BFS before this :) will come useful in the future TY

Collectives™ on Stack Overflow

AS3 recursive object scan without repeats?

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related