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 не перестанет отвечать условию или мы не выйдем из цикла самостоятельно (к примеру, с помощью оператора 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
}
Вот и все.
Супер!Спасибо!