При решении задач планирования, учета скидок, расчета стажа или резервирования ресурсов разработчики часто сталкиваются с задачей слияния пересекающихся периодов. Например, если у нас есть несколько интервалов, которые перекрывают друг друга полностью или частично, их необходимо «схлопнуть» в непрерывные временные отрезки. Разберем, как реализовать подобное слияние как средствами языка запросов 1С, так и с помощью оптимизированного обхода во встроенном языке.
Представим, что во временную таблицу или параметр передается исходный набор интервалов дат:
На выходе требуется получить результирующий список объединенных интервалов:
Главная сложность заключается в том, что в языке запросов платформы 1С:Предприятие отсутствуют стандартные оконные функции (OVER, LEAD, LAG) и рекурсивные запросы (WITH RECURSIVE). Рассмотрим возможные варианты реализации поставленной цели.
Проанализируем природу результирующих дат. Дата начала объединенного интервала всегда является датой начала одного из исходных периодов, причем она не накрывается ни одним другим интервалом «слева» (то есть не лежит строго внутри другого периода). Аналогично, дата окончания объединенного интервала — это дата окончания исходного периода, которая не перекрывается ни одним другим интервалом «справа».
Используем этот принцип для компактного решения:
ЛевыеКрая все даты начала, которые не лежат строго внутри какого-либо другого периода.ПравыеКрая все даты окончания, которые не перекрываются другими периодами.Посмотрим на практическую реализацию этого алгоритма в запросе:
ВЫБРАТЬ РАЗЛИЧНЫЕ
Край.От КАК От
ПОМЕСТИТЬ ЛевыеКрая
ИЗ
Интервалы КАК Край
ЛЕВОЕ СОЕДИНЕНИЕ Интервалы КАК Интервалы
ПО (Интервалы.От < Край.От)
И (Край.От <= Интервалы.До)
ГДЕ
Интервалы.От ЕСТЬ NULL
;
////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
Край.До КАК До
ПОМЕСТИТЬ ПравыеКрая
ИЗ
Интервалы КАК Край
ЛЕВОЕ СОЕДИНЕНИЕ Интервалы КАК Интервалы
ПО (Интервалы.От <= Край.До)
И (Край.До < Интервалы.До)
ГДЕ
Интервалы.От ЕСТЬ NULL
;
////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
ЛевыеКрая.От КАК ДатаНачала,
МИНИМУМ(ПравыеКрая.До) КАК ДатаОкончания
ИЗ
ЛевыеКрая КАК ЛевыеКрая
ВНУТРЕННЕЕ СОЕДИНЕНИЕ ПравыеКрая КАК ПравыеКрая
ПО ЛевыеКрая.От <= ПравыеКрая.До
СГРУППИРОВАТЬ ПО
ЛевыеКрая.От
Разберем подробнее, как работают условия в этом запросе. В первом пакете левое соединение ищет интервал, который начался раньше текущей даты Край.От и закончился не раньше нее. Если такой период найден, значит, Край.От находится внутри чужого диапазона и не может быть началом объединенной группы. Проверка ГДЕ Интервалы.От ЕСТЬ NULL отсекает такие строки и оставляет только истинные стартовые точки.
Рассмотрим альтернативную технику, которая собирает все граничные точки (как левые, так и правые) в единый список, нумерует их по возрастанию даты через соединение таблицы с собой и разбивает на пары «начало — конец»:
ВЫБРАТЬ РАЗЛИЧНЫЕ
Край.От КАК От
ПОМЕСТИТЬ Края
ИЗ
Интервалы КАК Край
ЛЕВОЕ СОЕДИНЕНИЕ Интервалы КАК Интервалы
ПО (Интервалы.От < Край.От)
И (Край.От <= Интервалы.До)
ГДЕ
Интервалы.От ЕСТЬ NULL
ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ РАЗЛИЧНЫЕ
Край.До
ИЗ
Интервалы КАК Край
ЛЕВОЕ СОЕДИНЕНИЕ Интервалы КАК Интервалы
ПО (Интервалы.От <= Край.До)
И (Край.До < Интервалы.До)
ГДЕ
Интервалы.От ЕСТЬ NULL
;
////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
МИНИМУМ(Края.От) КАК ДатаНачала,
МАКСИМУМ(Края.От) КАК ДатаОкончания
ИЗ
(ВЫБРАТЬ
КОЛИЧЕСТВО(Раньше.От) КАК Номер,
Позже.От КАК От
ИЗ
Края КАК Позже
ВНУТРЕННЕЕ СОЕДИНЕНИЕ Края КАК Раньше
ПО (Раньше.От <= Позже.От)
СГРУППИРОВАТЬ ПО
Позже.От) КАК Края
СГРУППИРОВАТЬ ПО
ВЫРАЗИТЬ(Края.Номер / 2 КАК ЧИСЛО(10, 0))
В этом варианте объединение левых и правых точек дает упорядоченный список парных границ: [Начало1, Конец1, Начало2, Конец2, ...]. Деление порядкового номера на 2 с округлением позволяет сгруппировать точки строго по парам.
При использовании запросов для склеивания диапазонов важно учитывать технические особенности СУБД и платформы:
0001-01-01), сравнения <= и >= отработают некорректно. В таких случаях пустую дату необходимо заменять на максимальную возможную дату через конструкцию ВЫБОР КОГДА ... ТОГДА ДАТАВРЕМЯ(3999, 12, 31).ДОБАВИТЬКДАТЕ(..., ДЕНЬ, 1).Интервалы1.Договор = Интервалы2.Договор), а во временных таблицах следует применять директиву ИНДЕКСИРОВАТЬ ПО.Если объем исходных периодов велик (сотни или тысячи записей), выгрузка данных в коллекцию ТаблицаЗначений с последующей обработкой в цикле будет работать на порядки быстрее запроса. Сортировка таблицы выполняется со сложностью $O(N \log N)$, а итоговый проход — за линейное время $O(N)$.
Посмотрим на пример кода с алгоритмом слияния в цикле:
// Предположим, что ТаблицаИнтервалов содержит колонки: ДатаНачала, ДатаОкончания
ТаблицаИнтервалов.Сортировать("ДатаНачала Возр, ДатаОкончания Возр");
ТаблицаРезультат = ТаблицаИнтервалов.СкопироватьКолонки();
Если ТаблицаИнтервалов.Количество() > 0 Тогда
ТекущаяСтрока = ТаблицаРезультат.Добавить();
ЗаполнитьЗначенияСвойств(ТекущаяСтрока, ТаблицаИнтервалов[0]);
Для Индекс = 1 По ТаблицаИнтервалов.Количество() - 1 Цикл
СтрокаИсходная = ТаблицаИнтервалов[Индекс];
// Проверяем пересечение или стыковку текущего накопленного периода со следующим
Если СтрокаИсходная.ДатаНачала <= ТекущаяСтрока.ДатаОкончания Тогда
// Расширяем правую границу, если следующий период выходит за текущий
Если СтрокаИсходная.ДатаОкончания > ТекущаяСтрока.ДатаОкончания Тогда
ТекущаяСтрока.ДатаОкончания = СтрокаИсходная.ДатаОкончания;
КонецЕсли;
Иначе
// Обнаружен разрыв: фиксируем новый независимый интервал
ТекущаяСтрока = ТаблицаРезультат.Добавить();
ЗаполнитьЗначенияСвойств(ТекущаяСтрока, СтрокаИсходная);
КонецЕсли;
КонецЦикла;
КонецЕсли;
Таким образом, для небольших массивов данных и задач внутри сложных отчетов СКД отлично подходит вариант решения на чистом языке запросов через определение граничных точек. Для высоконагруженных участков и больших списков документов оптимальным выбором остается предварительная сортировка и обработка в цикле средствами встроенного языка.