C #: как сделать этот метод нерекурсивным

Question

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

    private void DeleteEmpty(DirectoryInfo directory)
    {
        foreach (var d in directory.GetDirectories())
        {
            DeleteEmpty(d);
        }

        if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }

Как я могу изменить этот метод, чтобы он не был рекурсивным?

Answer 1

Попробуйте это:

private void DeleteEmpty(string path)
{
    string[] directories = Directory.GetDirectories(
        path, "*", SearchOption.AllDirectories);

    // you should delete deeper directories first
    //      .OrderByDescending(
    //          dir => dir.Split(Path.DirectorySeparatorChar).Length)
    //              .ToArray();

    foreach (string directory in directories)
    {
        DirectoryInfo info = new DirectoryInfo(directory);
        if (info.GetFileSystemInfos().Length == 0)
        {
            info.Delete();
        }
    }

    // If you wanna a LINQ-ish version
    // directories.Where(dir => 
    //     new DirectoryInfo(dir).GetFileSystemInfos().Length == 0)
    //         .ToList().ForEach(dir => Directory.Delete(dir));
}

Еще одним шагом производительности может быть: если вы попытались удалить каталог и он содержит файлы, все родительские уровни должны быть пропущены, так как они тоже НЕ БУДУТ.

Answer 2

private static Queue<DirectoryInfo> directoryQueue = new Queue<DirectoryInfo>();
private void DeleteEmpty(DirectoryInfo directory)
{
    directoryQueue.Enqueue(directory);
    while (directoryQueue.Count > 0)
    {
        var current = directoryQueue.Dequeue();
        foreach (var d in current.GetDirectories())
        {
            directoryQueue.Enqueue(d);
        }

        if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }
}

Answer 3

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

Если вы можете определить функцию «следующего брата», вы можете посещать узлы с постоянным дополнительным пробелом. Это связано с тем, что граф каталогов (без файлов) по существу является ненаправленным из-за родительских указателей. Псевдокод:

nextBranchingSibling(sibling):
  while sibling exists
    if sibling has children
      return sibling
    sibling = nextSibling(sibling)
  return null

nextBranch(node):
  if node is marked
      unmark node
  else
      if nextBranchingSibling(firstChild(node)) exists
          return nextBranchingSibling(firstChild(node))
  if nextBranchingSibling(nextSibling(node)) exists
      return nextBranchingSibling(nextSibling(node))
  mark parent(node)
  return parent(node)

prune(node):
  while node exists:
    tmpNode = node
    node    = nextBranch(node)
    if count of tmpNode's children is 0
      delete tmpNode

Обратите внимание, что вы фактически не используете O (1) всего пространства, поскольку структура каталогов сама по себе O (n). Методы типа DirectoryInfo.GetDirectories могут устранить необходимость в циклах в nextBranchingSibling.

Answer 4

У меня была та же проблема, и я создал хорошее (imho) решение: начиная с корневого каталога, я "рекурсивно" получаю дочерние каталоги и сохраняю их в объекте ArrayList. Таким образом, я создаю список, включающий сначала каталоги более высокого уровня, а в конце - более глубокие вложенные каталоги. Этот массив идеально разделяется на подмассивы с использованием индексов, хранящихся в объекте уровней ArrayList. Делая это, я могу сначала проверить более глубокие каталоги и удалить их, если они пусты, а затем вернуться на корневой уровень за уровнем.

Например:

    private void directoryCleanup(string root)
    {
        try
        {
            // Create directory "tree"
            ArrayList dirs = new ArrayList();
            // Beginning and ending indexes for each level
            ArrayList levels = new ArrayList();
            int start = 0;
            dirs.Add(root);
            while (start < dirs.Count)
            {
                ArrayList temp = new ArrayList();
                for (int i = start; i < dirs.Count; i++)
                {
                    DirectoryInfo dinfo = new DirectoryInfo((string)dirs[i]);
                    DirectoryInfo[] children = dinfo.GetDirectories();
                    for (int j = 0; j < children.Length; j++)
                    {
                        temp.Add(children[j].FullName);
                    }
                    Array.Clear(children, 0, children.Length);
                    children = null;
                    dinfo = null;
                }
                start = dirs.Count;
                levels.Add(dirs.Count);
                dirs.AddRange(temp);
                temp.Clear();
                temp = null;
            }
            levels.Reverse();
            // Navigate the directory tree level by level, starting with the deepest one
            for (int i = 0; i < levels.Count - 1; i++)
            {
                int end = (int)levels[i] - 1;
                int begin = (int)levels[i + 1];
                for (int j = end; j >= begin; j--)
                {
                    string path = (string)dirs[j];
                    if (Directory.GetFileSystemEntries(path).Length == 0)
                    {
                        Directory.Delete(path);
                    }
                }
            }
            levels.Clear();
            levels = null;
            dirs.Clear();
            dirs = null;
        }
        catch (IOException ioex)
        {
            // Manage exception
            return;
        }
        catch (Exception e)
        {
            // Manage exception
            return;
        }
    }

Answer 5

Вы можете использовать локальный стек и цикл, пока стек не пуст.

public void DeleteDirectories(DirectoryInfo directoryInfo, bool deleteFiles)
{
    Stack<DirectoryInfo> directories = new Stack<DirectoryInfo>();
    directories.Push(directoryInfo);

    while (directories.Count > 0)
    {
        var current = directories.Peek();

        foreach (var d in current.GetDirectories())
            directories.Push(d);

        if (current != directories.Peek())
            continue;

        if (deleteFiles)
            foreach (var f in current.GetFiles())
            {
                f.Delete();
            }

        if (current.GetFiles().Length > 0 || current.GetDirectories().Length > 0)
            throw new InvalidOperationException("The directory " + current.FullName + " was not empty and could not be deleted.");

        current.Delete();

        directories.Pop();
    }
}

Answer 6

Создайте очередь, в которой есть все каталоги в начальном каталоге, затем, пока он не пуст, возьмите следующий элемент, проверьте, пуст ли каталог, если он удален, если нет, добавьте все подкаталоги в очередь.

Я не знаю C #, но если нет стандартного типа очереди, то связанный список или изменяемый тип массива будет работать так же хорошо.

псевдокод;

directories = empty queue
until directories is not empty
    next = directories.shift
    if next is an empty folder
        delete it
    or else
        add all the subdiretories to the queue