Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Аккумулятор JS: Деревья

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

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

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

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

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

В этой структуре три пустых директории: /logs, /etc/apache и /etc/consul/data. Код, решающий эту задачу, выглядит так:

const findEmptyDirPaths = (tree) => {
  const name = getName(tree);
  const children = getChildren(tree);
  // Если детей нет, то добавляем директорию
  if (children.length === 0) {
    return name;
  }

  // Фильтруем файлы, они нас не интересуют 
  const emptyDirNames = children.filter((child) => !isFile(child))
    // Ищем пустые директории внутри текущей
    // flatMap выправляет массив, так что он остаётся плоским
    .flatMap(findEmptyDirPaths);

  return emptyDirNames;
};

findEmptyDirPaths(tree); // ['apache', 'data', 'logs']

https://repl.it/@hexlet/js-trees-search-findEmptyDirs-nodejs

Самое необычное в этой реализации функция flatMap(). Зачем она нужна? Если оставить только map(), то результат может удивить:

findEmptyDirPaths(tree);

// [ [ 'apache', [], [ 'data' ] ], 'logs' ]

Такое происходит из-за возврата массива на каждом уровне вложенности. На выходе получается массив массивов, напоминающий по структуре исходное файловое дерево. Чтобы этого не происходило, нужно выправлять код с помощью flat(), либо сразу использовать flatMap().

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

Для начала нужно понять, откуда брать глубину. В деревьях глубина считается как количество рёбер от корня до нужного узла. Визуально её посчитать легко, а что насчёт кода? Глубину конкретного узла можно представить как глубину предыдущего узла плюс единица.

Следующий шаг – добавить переменную, которая передаётся при каждом рекурсивном вызове (проваливающемся в директорию). Эта переменная, в случае нашей задачи, содержит внутри себя текущую глубину. То есть на каждом уровне (внутри каждой директории) к ней добавляется единица. Такую переменную называют аккумулятором, так как она аккумулирует, то есть накапливает данные.

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

const findEmptyDirPaths = (tree) => {
  // Внутренняя функция, которая может передавать аккумулятор
  // В качестве аккумулятора выступает depth, переменная, содержащая текущую глубину
  const iter = (node, depth) => {
    const name = getName(node);
    const children = getChildren(node);

    // Если директория пустая, то добавляем ее в список
    if (children.length === 0) {
      return name;
    }

    // Если это второй уровень вложенности, и директория не пустая
    // то не имеет смысла смотреть дальше
    if (depth === 2) {
      // Почему возвращается именно пустой массив?
      // Потому что снаружи выполняется flat
      // Он раскрывает пустые массивы
      return [];
    }

    // Оставляем только директории
    return children.filter(isDirectory)
      // Не забываем увеличивать глубину
      .flatMap((child) => iter(child, depth + 1));

  };

  // Начинаем с глубины 0
  return iter(tree, 0);
};

findEmptyDirPaths(tree); // ['apache', 'logs']

https://repl.it/@hexlet/js-trees-accumulator-findEmptyDirsWithDepth

Можно пойти ещё дальше и позволить указывать максимальную глубину снаружи:

const findEmptyDirPaths = (tree, maxDepth = 2) => {
  // ...
}

Но возникает вопрос, а как сделать так, чтобы по умолчанию просматривалось всё дерево? Например, можно взять заведомо большое число и сделать его значением по умолчанию. Такой подход сработает, но это хак. Правильный способ сделать это – использовать в качестве значения по умолчанию бесконечность Infinity:

const findEmptyDirPaths = (tree, maxDepth = Infinity) => {
  // ...
}

Дополнительные материалы

  1. Параметры для внутренних нужд

Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы

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

Иконка программы Фронтенд-разработчик
Профессия
Разработка фронтенд-компонентов веб-приложений
26 января 8 месяцев
Иконка программы Node.js-разработчик
Профессия
Разработка бэкенд-компонентов веб-приложений
26 января 8 месяцев

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»