Freecode Academy

Создание вложенных задач и разбор алгоритма построения дерева значений

Николай Ланец
Николай Ланец
Feb 27, 2021

Всем привет! Выкатил на сайт еще несколько обновлений. Новый личный кабинет (найзванный мной Офисом) более прокачался, и хотя пока еще не занял главную страницу сайта, тем не менее хотя бы обзавелся своим пунктом в главном меню. Советую почаще им пользоваться (если вы авторизованный пользователь, ибо для анонимных пользователей там пока практически ничего полезного нет). Из полезных функций:

И вот именно с последней задачей была самая заморочка. Если посмотреть лог выполнения, то я на нее потратил более 3 часов, при чем за два дня. В первый день я ее в итоге вообще стопнул с формулировкой "Слишком много тонкостей, а выхлоп не велик".

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

Так в чем же оказался подвох по этой задаче? Суть в том, что в базе данных связь с родительскими задачами идет через значение в колонке Parent. То есть все задачи лежат в одной и той же таблице и ее можно расценивать как одноуровневый массив. Собственно данные мы и получаем в виде одноуровнего массива по запросу Tasks where Project = project.id (условно).

То есть если рассмотреть фактическую структуру задачь типа:

  • Задача 1
  • Задача 1.1
  • Задача 2
  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2.2
  • Задача 3
  • Задача 4

по сути мы с сервера данные задач получим в виде:

  • Задача 1
  • Задача 1.1
  • Задача 2
  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2.2
  • Задача 3
  • Задача 4

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

Но такой фокус бы проканал, если бы у нас был максимум двухуровневый массив. Но у нас многоуровневый (с неизвестным уровнем вложенности).

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

К примеру, мы получили задачи вот в такой последовательности:

  • Задача 2.1.1
  • Задача 2.1
  • Задача 2.1.2
  • Задача 2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Возьмем первый элемент (2.1.1) и найдем его родителя в корне массива (это 2.1) и переместим в него. Получим вот такую структуру:

  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Теперь возьмем следующий элемент (это 2.1 (каждый раз мы ищем с начала массива)) и перемещаем его в 2. Получаем следующую структуру:

  • Задача 2.1.2
  • Задача 2
  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

А вот теперь, когда мы берем очередной элемент (2.1.2), для него родитель должен быть 2.1. А где мы его найдем? В корне массива его уже нет. То есть надо уже искать не только в корне массива, но и во всех его вложенностях. И вот этот вот момент мне очень сильно не нравился...

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

Как видите, тут несколько похожих запросов с getNodes и id. То есть когда мы раскладываем какой-либо элемент (хотим вывести дочерние элементы для него), у нас отправляется на сервер новый запрос за данными дочерних элементов конкретно этого элемента. То есть если вы хотите вывести сразу дерево со 100500 элементов со всеми вложенностями, на сервер у вас будет выполнено огромное количество запросов, чтобы получить все данные для всех уровней.

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

Здесь стоит отметить, что как часто это и бывает, нельзя сказать, что именно вот такой способ правильный, а другой совсем не правильный и его никогда не надо применять. Это не так. Во многом это зависит именно от задачи. То есть если вот как здесь, я хочу точно сразу вывести все элементы, и я знаю, что там вряд ли их будет больше тысячи, мне уместно использовать именно механизм с одним запросом. Но если рассматривать вариант как с меню в MODX, где мы вручную раскладываем дерево элементов, там вариант с множеством запросов может оказаться более приемлемый, если на сайте очень много ресурсов, ведь в таком случае мы получаем сначала какое-то совсем небольшое количество, потом еще немного только там и на том уровне, где нам надо и так далее. Если на сайте тысяч 100 и более ресурсов, то вариант с одним запросом может просто положить браузер на несколько минут, а то и вовсе убить. Так что всегда смотрите по задаче и правильно выбирайте инструменты.

Итак, я разобрался что я хочу сделать, разобрался как не надо делать, но вот я долго не мог разобраться как надо делать (по описанным выше причинам). И по этой причине я как раз и стопнул эту задачу.

Но как это часто бывает в таких ситуациях, нормально спать я не смог. Я обдумывал различные варианты как же перестроить это дерево, чтобы было быстро, эффективно и надежно. И в итоге я придумал :)

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

Исходный массив:

  • Задача 2.1.1
  • Задача 2.1
  • Задача 2.1.2
  • Задача 2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Первый элемент, на который никто не ссылается, это 2.1.1. Перемещаем его в 2.1. Получаем:

  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Следующий элемент в корне, на который никто не ссылается, это 2.1.2. Перемещаем его тоже в 2.1.

  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Теперь на 2.1 уже никто не ссылается. Перемещаем его в 2 (он туда уходит вместе со своими дочерними).

  • Задача 2
  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Затем 2.2

  • Задача 2
  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

Далее 1.1 (1 мы пропускаем, потому что на нее ссылаются).

  • Задача 2
  • Задача 2.1
  • Задача 2.1.1
  • Задача 2.1.2
  • Задача 2.2
  • Задача 1
  • Задача 1.1
  • Задача 3
  • Задача 4

И все. У нас в корне не осталось элементов, которые ссылались бы на другие элементы. При этом нам не пришлось искать на всех уровнях и сделали мы все за количество циклов, число которых меньше количеству элементов в массиве.

Вот такой алгоритм мне нравится :) И не кажется, что в нем могут быть какие-то ошибки (во всяком случае для текущей задачи).

Сам код формирования многоуровневого массива вот:

А вот здесь хотелось вот какой момент отметить: вот это, наверно, как раз и стоит называть программированием. Сам же я про себя говорил не раз: я не правильный программист. В как таковое программирование я, наверно, не умею. В моем понимание программировать - это прям жить математикой, понимать ее, всякие там формулы и т.п. Наверняка какой-нибудь не программист, но студент физмата, буквально второго курса, за 5 минут такой алгоритм придумал, или вовсе сразу бы сказал "А надо так в таких случаях". У меня же ушел не один час на то, что бы придумать этот алгоритм.

Ну сильная моя сторона в том, что я отталкиваюсь не от того, что знаю и умею, а от того, как я хочу сделать. То есть сначала я просто придумываю как должно работать в принципе (это доступно любому человеку, даже не программисту совсем. Ведь каждый может сказать "Я хочу зайти на страницу проекта и увидеть все задачи проекта, при чем не в одну колонку, а структурно"). А потом уже начинаю выполнять задачу, думая о более оптимальном решении.

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

Вот я считаю - это все моральные качества. И считаю, что каждый должен в себе формировать именно это моральное качество, то есть желание делать как надо, а не как умеешь. Именно это заставляет всегда развиваться, не стоять на месте. И если вы столкнулись с чем-то, что не знаете как решать, для начала следует для себя ответить на следующий вопрос: "А понимаю ли я вообще, как оно должно работать в принципе?". Чаще всего, программист просто не до конца понимает что именно он хочет сделать. И получается совсем уж тупик: мало того, что не знает как делать, так еще и не знает что делать. В общем, изучайте себя, изучайте свои алгоритмы.

Хотелось отметить еще одну фишку: как в styled-components можно прописать стили для селектора, вложенного в сабя же (ведь у нас же выводятся дочерние задачи вложенные в родительский, при этом и у тех и у других один общий селектор).

Кто использовал в своей практике LESS, SASS или типа того, знает, что & - это текущий селектор. К примеру, если мы напишем так: пример кода

То будет сформировано два правила: пример кода

А можно и так: пример кода

В таком случае конечное второе правило будет кардинально другое пример кода

То есть здесь уже самому контейнеру будет задан цвет шрифта красный, если он вложен в элемент с классом item.

Здесь же можно делать без пробелов (чтобы формировать типа .conteiner.item), использовать >, * и прочие радости. И вот & > &, что я использовал, как раз и создает правило для элементов, вложенных в себя же, при чем именно для прямых потомков. То есть если где-то на более нижних уровнях будут такие контейнеры, но не являющиеся прямыми потомками таких же, на них правило не распространится (но распространится конечно же на их прямых таких же потомков).

В итоге вот такой результат: пример кода

Что интересно, почему-то не сработало вот такое правило: пример кода

Хотя по идее должно, ведь здесь тоже конструкция на прямого потомка с таким же селектором. Но тем не менее, такое не проканало.

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

UPD: Добавил кнопку "Отметить задачу выполненной" прям в списке задач и таймеров.