Note #1. Вычисления суммы на каждом сегменте в иерархии

Совсем недавно мне в руки попалась задачка со следующим содержанием:

Необходимо создать отчет по сотрудникам за выбранный период времени. При формировании необходимо отразить кол-во занесенных часов с учетом времени подчиненных. У каждого сотрудника могут быть подчинённые, причем у подчиненных могут быть свои подчиненные и т.д.

Пример входных данных:

Таблица сотрудников:

id (int) name (string) email (string) employer (int) info (text)
1 Петр petr@tm.ru 0
2 Федор fedor@tm.ru 1
3 Николай nik@tm.ru 0
4 Яна yana@tm.ru 2
5 Антон anton@tm.ru 3
6 Екатерина katya@tm.ru 1

Рабочее время по каждому сотруднику:

employeeId (int) time (string) date (date)
3 2:00:00 2017-02-10
1 5:00:00 2017-02-15
2 1:00:00 2017-02-11
3 4:30:00 2017-02-12

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

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

Визуально это выглядит так:

Вычисления суммы на каждом сегменте в иерархии

Теперь нам остается только подсчитать сумму часов по каждому работнику, но следует помнить, что сумма часов у работника с id:2 будет равняться сумме часов этого же работника и всех его подчиненных, в данном случае id:2+id:4. А вот уже сумма id:1=id:2+id:4+id:6.

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

  1. sumLevel() – будет считать сумму на текущем уровне иерархии.
  2. sumAll() – спускается по иерархии и считает общую сумму по каждому сотруднику.

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

Функция sumLevel():

Функция sumAll():

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

Результат со входными данными получился следующий:

# Имя E-mail Кол-во часов с подчиненными Кол-во часов без подчиненных
1 Петр petr@tm.ru 6 5
2 –Федор fedor@tm.ru 1 1
3 —-Яна yana@tm.ru 0 0
4 –Екатерина katya@tm.ru 0 0
5 Николай nik@tm.ru 6.5 6.5
6 –Антон anton@tm.ru 0 0

Полный код можно скачать здесь.

Может быть полезно