AS3 рекурсивное сканирование объекта без повторов?

Question

В то время как рекурсивное сканирование обычно используется для сканирования вложенных объектов / данных. Он может идти по бесконечному циклу, если некоторые объекты ссылаются друг на друга. Итак, каков наиболее эффективный способ сканирования всех элементов без сбоя компьютера и пропуска указанного параметра?

Вот пример рекурсивного сканера ...

/**
 * 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);
    }
}

Однако огромные проблемы возникают, когда в * 1006 передается следующее

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

Объекты будут запускать сканирование друг друга в вечном цикле. Так есть ли способ решить эту проблему?

Я верю в C / C ++: каждый вызов scanFunction будет добавляться в список, состоящий из сканированного «адреса памяти», что предотвращает повторение Это вообще возможно в AS3? Есть ли более изящный способ?

Answer 1

Используйте Dictionary для сохранения списка проверенных объектов и игнорируйте их, если они были проверены ранее:

/**
 * 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);
    }
}

Answer 2

ОК, примите ответ от @grapefrukt, но здесь есть некоторая предыстория.

С точки зрения компьютерных наук, проблема эквивалентна обходу ориентированного графа , который может содержать циклы.

Существуют два наивных пути (т. Е. Не следование эвристике) для прохождения: глубина сначала или ширина сначала .

Я будуоставьте это в качестве упражнения, чтобы определить, является ли образец кода BFS или DFS.