Поиск по файловой системе — операция, выполняющаяся крайне часто. Она открывает большой простор для интересных задачек. Разберём одну из них с несколькими вариациями. Предположим, что мы хотим вывести список всех пустых директорий. Используя reduce, выполнить данную задачу тривиально. Возьмём следующую файловую структуру:

import { mkdir, mkfile } from 'hexlet-immutable-fs-trees';

const tree = mkdir('/', [
  mkdir('etc', [
    mkdir('apache'),
    mkdir('nginx', [
      mkfile('nginx.conf'),
    ]),
    mkdir('consul', [
      mkfile('config.json'),
      mkdir('data'),
    ]),
  ]),
  mkfile('hosts'),
  mkfile('resolve'),
]);

В этой структуре две пустых директории: /etc/apache и /etc/consul/data. Алгоритм поиска примитивный:

  1. Инициализируем reduce массивом;
  2. Если тип ноды directory и у неё нет детей — добавляем в массив;
import { reduce } from 'hexlet-immutable-fs-trees';

const dirs = reduce((acc, n) => {
  if (n.type === 'directory' && n.children.length === 0) {
    return [...acc, n.name];
  }
  return acc;
}, tree, []);

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

Попробуем усложнить задачу. Найдём все пустые директории, но с максимальной глубиной поиска 2 уровень. То есть пустая директория /etc/apache подходит под это условие, а вот /etc/consul/data — нет. Навскидку можно сразу назвать следующие способы решения:

  1. Так как наша реализация reduce не предоставляет информацию о том, на какой глубине текущая нода, то можно выполнить обход вручную, передавая два аккумулятора: один с итоговым массивом, второй с уровнем вложенности;
  2. Можно расширить само описание дерева, добавив туда информацию об уровне вложенности. С одной стороны, такой способ не потребует изменения прикладного кода, так как достаточно изменить реализацию интерфейсных функций mkdir и mkfile. С другой, в такой схеме глубина всех нод будет посчитана относительно корня, что неудобно;
  3. Можно написать reduce которому можно сказать насколько глубоко идти. А затем решить задачу с его использованием.

Попробуем решить эту задачу, используя первый способ.

const findEmptyDirsDepth = (root, depth = 1) => {
  const iter = (n, currentDepth, acc) => {
    if (n.type === 'file' || currentDepth > depth) {
      return acc;
    }

    if (n.children.length === 0) {
      return [...acc, n.name];
    }
    return n.children.reduce((cAcc, nn) => iter(nn, currentDepth + 1, cAcc), acc);
  };

  return iter(root, 0, []);
};

const dirs = findEmptyDirsDepth(tree, 2);
console.log(dirs); // => ['apache']

Несколько важных моментов:

  1. Теперь нужно отслеживать текущую глубину, поэтому она передаётся в iter, с каждой итерацией увеличиваясь на единицу;
  2. Если зашли глубже, чем надо, то возвращаем результат.

В остальном код такой же, как и в обычном reduce.

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →