Когда мы придумываем проект для курса, оказывается, что он связан с деревьями. И текущий проект не исключение. Если посмотреть на файловую структуру, то можно увидеть, что это тоже дерево:
В корне у нас будет корневая директория, которая обычно обозначается как слэш — /. Внутри нее лежит большое количество директорий,
которые тоже могут содержать директории. И в самой глубине у нас хранятся листья — узлы, у которых нет дочерних элементов. Это файлы.
Вся структура представляет глубокое дерево — это файловая структура. Если бы мы писали библиотеку для работы с файлами без курсов, которые делаются на Хекслете, то мы бы ее так и начали писать. Но мы знаем, что существует барьер абстракции, и понимаем, что наша задача включает в себя две подзадачи:
- Работа с файловой структурой, как с некоторым деревом, в котором есть стандартные операции. Например, добавить детей, удалить детей, проверить их количество
- Работа с файловой системой, обеспечением инвариантов файловой системы, обработкой ошибок и прочее
Это две независимые подзадачи. Нам нужно построить между ними барьер абстракции и создать библиотеку для работы с деревьями. В итоге она будет давать нам примитивы. Они будут использоваться в библиотеке, чтобы построить файловую систему.
В этом уроке мы напишем библиотеку для работы с произвольными деревьями. Она станет фундаментом для построения файловой системы.
Дизайн
Спроектируем дизайн. Для этого будем основываться на тестах, так как они дают возможность посмотреть, как будет использоваться библиотека, и какой лучше сделать дизайн.
Допустим, мы хотим создать следующую файловую структуру:
home/
config
etc/
На верхнем уровне находятся папки home и etc, и внутри папки home находится файл config.
Чтобы передать туда название элемента, который является основным на текущем уровне, создадим объект класса Tree:
const tree = new Tree('/') ;
const child = tree.addChild('home')
.addChild('config', 'data');
tree.addChild('etc');
Далее мы можем добавить детей этому элементу. Для этого вызываем метод tree.addChild() и передаем в него имя home. Метод tree.addChild('home') возвращает новую ноду, которая является ребенком корневой директории /.
Дальше мы продолжаем через точку вызывать снова addChild('config', 'data') — производим добавление узла config. Получается структура, где внутри home содержится config. Второй параметр data разберем позже.
Далее ниже на корневом элементе вызываем addChild('etc'). В итоге внутри корневой директории у нас появляется на одном уровне несколько детей: home и etc.
Также у нас есть тесты:
assert.ok(tree.hasChildren());
assert.ok(tree.hasChild('home'));
С их помощью мы проверяем, что у дерева есть дети, один из которых home.
На этом этапе может показаться, что мы уже строим файловую структуру, но это еще не так. Сейчас это просто имена или идентификаторы, конкретные ноды. Мы используем имена, которые совпадают со структурой нашей файловой системы. При этом там может быть всё что угодно. Связи между файловой структурой и этой библиотекой нет.
Теперь посмотрим уже построенную структуру, но при этом извлечем из нее некоторые данные.
Берем дерево и вызываем уже getChild(), которому передаем ключ. Мы использовали его при создании ребенка:
const node = tree.getChild('home')
.getChild('config');
В итоге getChild('home') возвращает нам ребенка, у которого мы также можем сделать вызов getChild('config'). В итоге мы получаем ноду.
Файл представляет ноду, так же как и папка. Получается, что любой общий элемент в этой системе является нодой.
Некоторые ноды содержат детей, некоторые нет. Причем эта библиотека не накладывает никаких ограничений.
Ограничения формируются в библиотеках, которые построены поверх этой библиотеки. Например, библиотека, которая предоставляет файловую структуру, будет накладывать ограничения на файл, чтобы запретить ему иметь детей. Но это не будет выполняться в более низкоуровневой библиотеке, которая представляет дерево.
При этом все ноды обладают одинаковым интерфейсом. Также в ноде есть базовые методы: getKey() и getMeta():
assert.equal(node.getKey(), 'config');
assert.equal(node.getMeta(), 'data');
getMeta() — это все что угодно, потому что у нас универсальная библиотека. При одном из вызовов addChild() был передан второй параметр data.
То есть мы какие-то данные поместили в ноду в виде строки. А ключ — это имя, которое мы указали при GetChild. Этого достаточно, чтобы построить файловую систему поверх этой системы.
Реализация
У реализации есть некоторая особенность. Мы будем создавать класс, который называется Tree — просто дерево:
class Tree {
constructor(key, meta, parent) {
this.parent = parent;
this.key = key;
this.meta = meta;
this.children = new Map();
}
addChild(key, meta) {
const child = new Tree(key, meta, this);
this.children.set(key, child);
return child;
}
}
По сути это и есть нода — рекурсивная структура, у которой дальше внутри есть деревья. Она рекурсивная по определению, поэтому так же и работает.
Еще у нас есть конструктор, который принимает на вход три параметра: key, meta и parent. Последний мы не всегда будем использовать. Если parent нет, он не передается.
Все это устанавливаем внутрь через this и дополнительно внутри устанавливаем свойство children, которому присваиваем объект класса Map. То есть у нас будет некоторый ассоциативный массив — ключ значения, в котором содержится children.
Рассмотрим, как выглядит метод добавления ребенка:
addChild(key, meta) {
const child = new Tree(key, meta, this);
this.children.set(key, child);
return child;
}
Здесь мы передаем ключ и мета, который тоже не обязательно передавать. Если у нас достаточно ключа, то можно передать только его. И внутри мы создаем уже child — объект класса Tree, передаем в него key и meta, которые пришли из параметров.
Также обязательно передаем this. Так мы сохраним контекст родителя, внутри он будет установлен как parent. Благодаря этому мы сможем всегда из дочерних нод обратиться к родителю и тем самым подниматься по файловой структуре вверх до корневой директории.
Еще нам нужно не забыть поместить ребенка в список детей текущего элемента: делаем this.children.set(), под ключом складываем туда текущего нового ребенка и возвращаем его наружу.
Текучий интерфейс позволяет делать вызовы цепочек методов. Но тут может возникнуть вопрос, является ли это ошибкой.
Ошибки
Предположим, мы создали такое дерево:
tree = new Tree('animals');
tree.addChild('cats');
const dogs = tree.getChild('dogs');
Мы записали ключ animals и добавили ребенка с ключом cats. При этом ниже делаем getChild('dogs'), но dogs внутри у нас нет.
Но это не является ошибкой, потому что getChild() выполнил свою работу: проверил, что там нет этого ребенка. По умолчанию вызов этой функции для ребенка, которого не существует, будет возвращать нам undefined.
Это нормальное поведение, и мы должны возвращать undefined. Библиотека, которая построена поверх библиотеки работы с деревьями,
уже сама решает, является ли это ошибочной ситуацией или нет. Это зависит от того, как ее используют, и для чего она создана.
При этом есть еще один момент, который касается файловой системы. Из-за него хочется добавить еще один метод внутри библиотеки работы с деревьями. Рассмотрим его.
Чаще всего мы будем работать вот с такими путями:
const path = '/etc/nginx/conf.d/hexlet.conf';
Здесь у нас будет достаточно глубокая иерархия.
Представим, что нам нужно сделать выборку и достать ноду hexlet.conf. Например, нам нужно сделать запись в этот файл, удалить его или перезаписать. Для этого нам придется постоянно рекурсивно дергать getChild() до тех пор, пока мы не дойдем до цели. Такое будет встречаться практически в каждой функции, которую мы напишем внутри библиотеки для работы с файловой системой.
Чтобы это упростить, мы можем добавить в интерфейс библиотеки для работы с деревьями еще один метод — getDeepChild(). Он выполняет эту рутинную работу — шаблонный код, который всё повторяет за нас:
const keys = ['etc', 'nginx', 'conf.d', 'hexlet.conf'];
const subtree = tree.getDeepChild(keys);
assert.equal(subtree.getParent().getKey(), 'conf.d');
Для этого мы передаем ему список ключей, по которым он внутри рекурсивно вызывает getChild(), пока он не вернет последний элемент.
При этом если мы возьмем parent и посмотрим у него ключ, то это будет conf.d'. То есть conf.d' является parent для hexlet.conf.
Если мы делаем обращение к элементу, которого не существует, то функция должна вести себя так же, как getChild() — должна возвращать undefined:
const keys = ['etc', 'init', 'nginx.conf'];
const subtree = tree.getDeepChild(keys);
assert.equal(subtree, undefined);
Неважно, на каком элементе произошел сбой. Когда мы поняли, что в дереве нет этого элемента, мы дальше просто не смотрим. Мы останавливаемся и возвращаем undefined.
Выводы
В этом уроке мы научились писать библиотеку для работы с произвольными деревьями. Она станет фундаментом для построения файловой системы. Нам удалось спроектировать дизайн, создать класс, который называется Tree, а также разобрали, что может считаться ошибкой, а что нормальным поведением.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
