Устранение рекурсии из «Удалить пустые каталоги» Алгоритм

Question

Я думаю, что раньше знал, как это сделать, но, похоже, я забыл.

У меня есть рекурсивный алгоритм, чтобы удалить все пустые каталоги в дереве каталогов:

static bool DeleteDirectoriesRecursive(string path) 
{ 
    var remove = true; 
    foreach (var dir in System.IO.Directory.GetDirectories(path)) 
    { 
     remove &= DeleteDirectoriesRecursive(dir); 
    } 
    if (remove &= (System.IO.Directory.GetFiles(path).Length == 0)) 
     System.IO.Directory.Delete(path); 
    return remove; 
} 

Я пытаюсь устранить рекурсии из этого алгоритма, не так много, чтобы «исправить» алгоритм (т.е. the similar question не использует переменную remove, но я хотел бы ее сохранить).

Я начал новую функцию, используя класс Stack<>, но я не могу придумать хороший способ вернуться к базовому пути и выполнить действия, которые определены подкаталогами. Я думаю, что распутывание нерегулярной рекурсии требует немного больших усилий.

Answer 1

С Гейбами ​​упомянули возможность StackOverflowException при использовании рекурсии я был вдохновлен, чтобы сделать эту работу без него. В качестве отправной точки я использовал код here. И вот что я придумал ...

public static bool DeleteDirectories(string root) 
{ 
    bool removed = false; 

    var dirs = new Stack<string>(); 
    var emptyDirStack = new Stack<string>(); 
    var emptyDirs = new Dictionary<string, int>(); 

    if (!System.IO.Directory.Exists(root)) 
    { 
     throw new ArgumentException(); 
    } 
    dirs.Push(root); 

    while (dirs.Count > 0) 
    { 
     string currentDir = dirs.Pop(); 

     string[] subDirs; 
     try 
     { 
      subDirs = System.IO.Directory.GetDirectories(currentDir); 
     } 
     catch (UnauthorizedAccessException e) 
     { 
      Console.WriteLine(e.Message); 
      continue; 
     } 
     catch (System.IO.DirectoryNotFoundException e) 
     { 
      Console.WriteLine(e.Message); 
      continue; 
     } 

     if (Directory.GetFiles(currentDir).Length == 0) 
     { 
      emptyDirStack.Push(currentDir); 
      emptyDirs.Add(currentDir, subDirs.Length); // add directory path and number of sub directories 
     } 

     // Push the subdirectories onto the stack for traversal. 
     foreach (string str in subDirs) 
      dirs.Push(str); 
    } 

    while (emptyDirStack.Count > 0) 
    { 
     string currentDir = emptyDirStack.Pop(); 
     if (emptyDirs[currentDir] == 0) 
     { 
      string parentDir = Directory.GetParent(currentDir).FullName; 
      Console.WriteLine(currentDir); // comment this line 
      //Directory.Delete(currentDir); // uncomment this line to delete 
      if (emptyDirs.ContainsKey(parentDir)) 
      { 
       emptyDirs[parentDir]--; // decrement number of subdirectories of parent 
      } 
      removed = true; 
     } 
    } 

    return removed; 
} 

Несколько примечаний:

1. Обход дерева без рекурсии не слишком невероятно трудно, и это достигается в статье MSDN я связан выше. Но этот конкретный пример немного сложнее, чем их.
2. Я храню каждый каталог, который не содержит файлов в словаре emptyDirs, а также количество содержащихся в нем подкаталогов.
3. Поскольку заказ, в котором удалены каталоги, имеет решающее значение, мне пришлось пробежать словарь emptyDirs в обратном порядке (я использовал Linq для выполнения этого).

Я полагаю, что существуют более эффективные методы, но это не так уж плохо, и, похоже, это работает в моем тестировании.

UPDATE: Я избавился от словаря в обратном порядке в пользу второго стека. Однако я все же использую словарь для быстрого поиска.

Answer 2

Версия sans-recursion намного сложнее и не намного эффективнее, поэтому я бы рекомендовал сохранить рекурсию. Кроме того, вот версия, которая немного чище:

static bool DeleteDirectoriesRecursive(DirectoryInfo d) 
{ 
    bool remove = true; 

    foreach (DirectoryInfo c in d.GetDirectories()) 
    { 
     remove &= DeleteDirectoriesRecursive(c); 
    } 

    if (remove && d.GetFiles().Length == 0) { 
     d.Delete(); 
     return true; 
    } 

    return false; 
}