Берегись рекурсии смолоду (Часть 2)

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

typedef std::queue < Node* > NodeQueue;

void TraverseDir(Dir* dir) {
    // Получить все дочернии узлы директории и
    // положить из в очередь.
    NodeQueue currQueue(dir->GetSubNodesQueue());
    while(!currQueue.empty())
    {
        Node* currNode = currQueue.front();
        if(currNode->isDir()) {
            // Получить все узлы-дети дирректории
            // и запихнуть их в очередь
            currQueue.push_back(((Dir*)currNode)->GetSubNodesQueue);
            // Тут как-то обрабатываем директорию
            processDir(currNode);
        } else {
            // Как-то обработать файл
        }
        // Выкидываем обработанный узел из очереди
        currQueue.pop();
    }
}

Поясню смысл вышеприведенного кода. Никаких рекурсивных вызовов и излишнего использования стека вызовов. Грубо говоря, встроенный стек вызовов заменяется на явно определенный контейнер. В данном случае это очередь. Используемый контейнер (например, очередь или стек) определяет метод обхода. Не обращайте внимание на некрасивое currNode->isDir(). Это в данном случае не главное.

Слева — дерево без файлов, а справа — дерево с файлами. Файлы обозначены цифрами, а директории — буквами.

В случае с очередью порядок обхода будет следующий:

A B C 1 D 2 E F 3 G 4 5 I

А если использовать стек, то такой:

A 1 C 3 F I E 5 B 2 D 4 G

Т.е. алгоритм меняется от прохода «по уровням» в случае с очередью до прохода «в глубь» при использовании стека. Эксперименты с приоритетной очередью или другими более «хитрыми» контейнерами помогут достичь того поведения, которое вам нужно. В крайнем случае можно внести изменения в процедуру обхода.

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