Николай
27 февр. 2021 г., 15:37

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

Всем привет!

Выкатил на сайт еще несколько обновлений.

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


- Добавление проектов (пока на главной странице офиса, но планирую добавить отдельную кнопку в сайдбар)

- Добавление задач и подзадач (да, таки были добавлены вложенные задачи)

И вот именно с последней задачей была самая заморочка. Если посмотреть лог выполнения, то я на нее потратил более 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

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

Сам код формирования многоуровневого массива вот:
const makeTasksListWithHierarchy = (tasks: Task_Fragment[]) => { /** * Делаем копию исходного массива задач */ const tasksListWithHierarchy: OfficeProjectPageViewTaskProps['task'][] = [ ...tasks, ].map((n) => { /** * Обязательно делаем копию объекта, так как изначальные объекты заморожены */ return { ...n, /** * В каждую копию исходной задачи добавляем массив дочерних элементов */ children: [], } }) /** * Выполняем цикл, пока не местим все элементы с учетом их родителя */ // let item: OfficeProjectPageViewTaskProps['task'] | null | undefined = undefined; // let parent: OfficeProjectPageViewTaskProps['task'] | null | undefined = undefined; /** * На всякий случай счетчик, если вдруг в бесконечную рекурсию уйдем */ let count = tasksListWithHierarchy.length /** * Находим элемент, у которого указан родитель, родитель есть в корне списка и на этот элемент из корня списка задач никто не ссылается */ do { count-- // Элемент должен иметь ссылку на родителя const item = tasksListWithHierarchy.find( (n) => n.Parent && // На этот элемент не должны ссылаться другие элементы из корня tasksListWithHierarchy.findIndex((i) => i.Parent?.id === n.id) === -1 && // Получить родителя в корне списка и это не должен быть сам элемент tasksListWithHierarchy.findIndex( (p) => p.id !== n.id && p.id === n.Parent?.id ) !== -1 ) /** * Если элемент не был найден, выходим из цикла */ if (!item) { break } const parent = tasksListWithHierarchy.find( (p) => p.id !== item.id && p.id === item.Parent?.id ) /** * Такая ситуация совсем вряд ли, но на всякий случай проверка */ if (!parent) { console.error('Не был получен родитель') break } /** * Если элемент был найден, выдергиваем его из массива и добавляем к родительскому компоненту */ tasksListWithHierarchy.splice(tasksListWithHierarchy.indexOf(item), 1) if (!parent.children) { parent.children = [] } parent.children.push(item) } while (count > 0) return tasksListWithHierarchy }

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

Хотелось отметить еще одну фишку: как в styled-components можно прописать стили для селектора, вложенного в сабя же (ведь у нас же выводятся дочерние задачи вложенные в родительский, при этом и у тех и у других один общий селектор).
export const OfficeProjectPageViewTaskStyled = styled.div` & > & { margin-left: 3rem; } `
Кто использовал в своей практике LESS, SASS или типа того, знает, что & - это текущий селектор. К примеру, если мы напишем так:
.container { color: blue; & .item { color: red; } }
То будет сформировано два правила:
.container { color: blue; } .container .item { color: red; } }
А можно и так:
.container { color: blue; .item & { color: red; } }
В таком случае конечное второе правило будет кардинально другое
.container { color: blue; } .item .container { color: red; } }
То есть здесь уже самому контейнеру будет задан цвет шрифта красный, если он вложен в элемент с классом item.

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

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

Что интересно, почему-то не сработало вот такое правило:
export const OfficeProjectPageViewTaskStyled = styled.div` > & { margin-left: 3rem; } `
Хотя по идее должно, ведь здесь тоже конструкция на прямого потомка с таким же селектором. Но тем не менее, такое не проканало.


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

UPD: Добавил кнопку "Отметить задачу выполненной" прям в списке задач и таймеров.
Вопрос: мы второй раз обошли массив, чтобы найти Задача 2.1, так как в первый раз на него ссылались подзадачи и его трогать было нельзя?
Ты про это?
>> Теперь на 2.1 уже никто не ссылается. Перемещаем его в 2.1 (он туда уходит вместе со своими дочерними)

Тут опечатка. Перемещаем его конечно же 2, а не в 2.1

Спасибо, поправил.
Это понятно, что опечатка, я про другое: мы уже прошли 2.1 в начале, но на него ссылались 2.1.1 и 2.1.2 и мы его оставили на месте. Мы повторно обошли массив, чтобы найти его снова?
Смотри, у нас цикл do...while. Читай документацию и пройди урок.

То есть у нас сразу выполняется блок do {} и потом, если while удовлетворяет условию, то опять do {} выполняется в полной мере, пока while не перестанет отвечать условию или мы не выйдем из цикла самостоятельно (к примеру, с помощью оператора break, который мы здесь так же используем).

Так вот, перед началом цикла мы уже создали массив tasksListWithHierarchy, засунув в него все таски. Далее, в do мы работаем именно с этим массивом, при чем не создавая какой-либо копии, а именно меняя его, то есть переставляя элементы. При этом массив остается одним и тем же объектом (обрати внимание, что переменная объявлена как const, при этом мы нигде не создаем новую переменную). И тут важно понимать, что при каждой итерации блок do {} выполняется от начала и до конца (или до точки выхода), как будто в первый раз. Вот и смотри что происходит внутри этого блока. Первое - мы получаем искомый элемент.
const item = tasksListWithHierarchy.find( (n) => n.Parent && // На этот элемент не должны ссылаться другие элементы из корня tasksListWithHierarchy.findIndex((i) => i.Parent?.id === n.id) === -1 && // Получить родителя в корне списка и это не должен быть сам элемент tasksListWithHierarchy.findIndex( (p) => p.id !== n.id && p.id === n.Parent?.id ) !== -1 )
Хоть тут условие поиска и не простое, но все же принцип один и тот же - мы используем нативный метод Array.find(). Опять-таки, смотри документацию. Метод find() всегда работает с начала массива. То есть тут нет логики "Мы перебирали массив, нашли элемент, и потом опять перебираем дальше массив с найденного элемента". Тут всегда логика "Ищем элемент с начала массива". Просто каждый раз у нас измененный массив. То же самый, но измененный (то есть элементы переставленные). Вот и получается, что сначала мы искали, и на 2.1 кто-то ссылался, а потом опять искали, но получилось, что на него уже никто не ссылается (те, что ссылались, переместили). И в этот момент он у нас первый найденный элемент, отвечающий условию. И вот мы его и переместили. И пошли опять выполнять do {}. Но в какой-то момент мы не нашли ни одного элемента, отвечающего условию, и вышли из цикла.
/** * Если элемент не был найден, выходим из цикла */ if (!item) { break }
Вот и все.

Добавить комментарий