Дано: Справочник где элемент (Условно: "Главный") содержит табличную часть со ссылками на другие элементы этого же справочника (условно: "подчиненные элементы")
Т.е. любые элементы содержат ссылки на "подчиненные элементы". А те в свою очередь ссылаются еще на БОЛЕЕ "подчиненные"... Количество "подчиненности" не ограничено.
Задача:
1) Проверить структуру подчиненности на рекурсию (Чтобы подчиненный элемент из "цепочки" не ссылался на Главный - рекурсия)
2) Получить упорядоченную структуру элементов, где сначала выбираются все элементы без подчиненных, потом "самые" подчиненные, затем главные для них...
БУДУ БЛАГОДАРЕН ЗА ИДЕИ И ПОДСКАЗКИ...
Пример (в скобках - подчиненные):
Элемент 1 (Элемент 2, Элемент 3)
Элемент 2 (Элемент 5, Элемент 3)
Элемент 3
Элемент 4 (Элемент 2)
Элемент 5 (Элемент 1) ЭТО РЕКУРСИЯ. до её устранения не упорядочиваемым.
5.
blockcode
4014.06.21 15:59 Сейчас в теме+0.5 $m
(1) Чтобы упорядочивание элементов не занимало много времени предлагаю ввести числовой реквизит, допустим Вес. Который будет увеличиваться с каждой ссылкой на него. И потом упорядочить элементы по возрастанию Веса. Выкладываю пример контроля от зацикленности и расчета Веса каждого элемента.
&НаСервере
Функция ПроверкаЗацикленности(Эл,Эл0)
лТекст = "
|ВЫБРАТЬ
| Справочник1Таблица.Элемент КАК Элемент
|ИЗ
| Справочник.Справочник1.Таблица КАК Справочник1Таблица
|ГДЕ
| Справочник1Таблица.Ссылка = &Ссылка
|";
лЗапрос = Новый Запрос(лТекст);
лЗапрос.УстановитьПараметр("Ссылка", Эл);
лВыборка = лЗапрос.Выполнить().Выбрать();
Пока лВыборка.Следующий() Цикл
Эл1 = лВыборка.Элемент;
Если ЗначениеЗаполнено(Эл1) тогда
Если Эл1 = Эл0 тогда
Возврат истина;
ИначеЕсли ПроверкаЗацикленности(Эл1,Эл0) тогда
Возврат истина;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Возврат ложь;
КонецФункции
&НаСервере
Процедура ИзменениеВеса(Эл,шаг)
лТекст = "
|ВЫБРАТЬ
| Справочник1Таблица.Элемент КАК Элемент
|ИЗ
| Справочник.Справочник1.Таблица КАК Справочник1Таблица
|ГДЕ
| Справочник1Таблица.Ссылка = &Ссылка
|";
лЗапрос = Новый Запрос(лТекст);
лЗапрос.УстановитьПараметр("Ссылка", Эл);
лВыборка = лЗапрос.Выполнить().Выбрать();
Пока лВыборка.Следующий() Цикл
Эл1 = лВыборка.Элемент;
Если ЗначениеЗаполнено(Эл1) тогда
Объ = Эл1.ПолучитьОбъект();
Объ.Вес = Объ.Вес + шаг;
Объ.Записать();
ИзменениеВеса(Эл1,шаг);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
&НаКлиенте
Процедура ТаблицаПередНачаломИзменения(Элемент, Отказ)
стр = Элементы.Таблица.ТекущиеДанные;
Если не стр = Неопределено тогда
ПередИзменением = стр.Элемент;
КонецЕсли;
КонецПроцедуры
&НаКлиенте
Процедура ТаблицаЭлементПриИзменении(Элемент)
стр = Элементы.Таблица.ТекущиеДанные;
Если не стр = Неопределено тогда
Если ПроверкаЗацикленности(стр.Элемент,стр.Элемент) тогда
Сообщить(строка(стр.Элемент)+" создаст зацикливание");
стр.Элемент = ПередИзменением;
ИначеЕсли не стр.Элемент = ПередИзменением тогда
Если ЗначениеЗаполнено(ПередИзменением) тогда
ИзменениеВеса(ПередИзменением,-1);
КонецЕсли;
Если ЗначениеЗаполнено(стр.Элемент) тогда
ИзменениеВеса(стр.Элемент, 1);
КонецЕсли;
КонецЕсли;
КонецЕсли;
КонецПроцедуры
Для того, чтобы делать проверку на зацикленность есть несколько подходов:
1. Выбирать все главные элементы и спускаться по иерархии вниз, накапливая при этом информация обо всех родителей (например в массиве) и делать проверку, что элементы на каждом уровне ниже не входят в перечень родителей.
При текущей архитектуре и при очень большом справочнике этот подход не применим, так как для того чтобы определить самого верхнего родителя нужно сделать запрос, который будет анализировать ВСЕ записи в табличной части с подчиненными элементами.
...
ИЗ
Справочник.Справочник1 КАК Справочник1
Левое Соединение Справочник.Справочник1.ПодчиненныеЭлементы КАК ТЧ_ПодчиненныеЭлементы
ПО Справочник1.Ссылка = ТЧ_ПодчиненныеЭлементы.ПодчиненныйЭлемент
ГДЕ
ТЧ_ПодчиненныеЭлементы ЕСТЬ NULL
Показать
2. Можно наоборот, взять элементы снизу иерархии и подниматься по уровням. Самые "низшие" элементы можно взять запросом, отобрав те элементы справочника у которых не заполнена табличная часть с подчиненными элементами (чтобы быстро отбирать такие элементы, можно добавить реквизит "НетПодчиненныхЭлементов" с типом Булево, который будет взводиться ПередЗаписью, если табличная часть - пустая).
Но этот подход не применим, если в справочнике существуют зацикленные элементы, так как у зацикленных цепочек не будет элементов без подчиненных
3. Для маленьких справочников можно загрузить все данные во временную таблицу запроса и крутить их там.
При этом все решить задачу №2 - Получить упорядоченную структуру элементов,
позволяет только пункт 1 и 3.
Я бы изменил архитектуру хранения данных о связях "родитель - подчиненный", и контроль наличия зацикленной иерархии лучше делать каждый раз при записи элемента справочника, как как при этом нужно будет анализировать только одну цепочку, а не все элементы сразу.
Архитектуру бы поменял так:
- хранил бы в таблице не подчиненные элементы, а элементы родителей (как я понял у одного элемента может быть несколько родителей - Элемент 2 в приведенном примере). Тогда можно без проблем получать все верхние элементы, а затем спускаться по иерархии
Если по каким то причинам, так переделать уже нельзя, то тогда нужно создать дополнительную таблицу, которая будет хранить избыточную информацию, но будет позволять быстро получать всю иерархию. Вот интересная статья на эту тему: https://infostart.ru/1c/articles/1105799/. Таблицу можно сделать в виде регистра сведений с двумя измерениями: Элемент / Родитель
- ну и как уже предложили выше, для упорядочивания элементов можно добавить реквизит, который будет хранить номер для сортировки, при этом номер должен устанавливаться перед записью, как максимальный номер из всех родителей + 1. Тут возникнут проблемы, если пользователь будет перемещать элементы по иерархии: например, когда Главный элемент становится подчиненным элементом в другой цепочке. В этом случае придется перечитывать этот номер для все подчиненных элементов: как для новой цепочки, так и для старой
5.
blockcode
4014.06.21 15:59 Сейчас в теме+0.5 $m
(1) Чтобы упорядочивание элементов не занимало много времени предлагаю ввести числовой реквизит, допустим Вес. Который будет увеличиваться с каждой ссылкой на него. И потом упорядочить элементы по возрастанию Веса. Выкладываю пример контроля от зацикленности и расчета Веса каждого элемента.
&НаСервере
Функция ПроверкаЗацикленности(Эл,Эл0)
лТекст = "
|ВЫБРАТЬ
| Справочник1Таблица.Элемент КАК Элемент
|ИЗ
| Справочник.Справочник1.Таблица КАК Справочник1Таблица
|ГДЕ
| Справочник1Таблица.Ссылка = &Ссылка
|";
лЗапрос = Новый Запрос(лТекст);
лЗапрос.УстановитьПараметр("Ссылка", Эл);
лВыборка = лЗапрос.Выполнить().Выбрать();
Пока лВыборка.Следующий() Цикл
Эл1 = лВыборка.Элемент;
Если ЗначениеЗаполнено(Эл1) тогда
Если Эл1 = Эл0 тогда
Возврат истина;
ИначеЕсли ПроверкаЗацикленности(Эл1,Эл0) тогда
Возврат истина;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Возврат ложь;
КонецФункции
&НаСервере
Процедура ИзменениеВеса(Эл,шаг)
лТекст = "
|ВЫБРАТЬ
| Справочник1Таблица.Элемент КАК Элемент
|ИЗ
| Справочник.Справочник1.Таблица КАК Справочник1Таблица
|ГДЕ
| Справочник1Таблица.Ссылка = &Ссылка
|";
лЗапрос = Новый Запрос(лТекст);
лЗапрос.УстановитьПараметр("Ссылка", Эл);
лВыборка = лЗапрос.Выполнить().Выбрать();
Пока лВыборка.Следующий() Цикл
Эл1 = лВыборка.Элемент;
Если ЗначениеЗаполнено(Эл1) тогда
Объ = Эл1.ПолучитьОбъект();
Объ.Вес = Объ.Вес + шаг;
Объ.Записать();
ИзменениеВеса(Эл1,шаг);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
&НаКлиенте
Процедура ТаблицаПередНачаломИзменения(Элемент, Отказ)
стр = Элементы.Таблица.ТекущиеДанные;
Если не стр = Неопределено тогда
ПередИзменением = стр.Элемент;
КонецЕсли;
КонецПроцедуры
&НаКлиенте
Процедура ТаблицаЭлементПриИзменении(Элемент)
стр = Элементы.Таблица.ТекущиеДанные;
Если не стр = Неопределено тогда
Если ПроверкаЗацикленности(стр.Элемент,стр.Элемент) тогда
Сообщить(строка(стр.Элемент)+" создаст зацикливание");
стр.Элемент = ПередИзменением;
ИначеЕсли не стр.Элемент = ПередИзменением тогда
Если ЗначениеЗаполнено(ПередИзменением) тогда
ИзменениеВеса(ПередИзменением,-1);
КонецЕсли;
Если ЗначениеЗаполнено(стр.Элемент) тогда
ИзменениеВеса(стр.Элемент, 1);
КонецЕсли;
КонецЕсли;
КонецЕсли;
КонецПроцедуры
Это при принципиально ограниченном (хотя бы конечным размером базы) количестве элементов справочника?
1) Проверить структуру подчиненности на рекурсию (Чтобы подчиненный элемент из "цепочки" не ссылался на Главный - рекурсия)
Любой второй по уровню подчиненности элемент будет ссылаться на главный - не?
А вообще для проверки зацикленности ссылок можно для каждого элемента пройти по цепочке родителей (то есть снизу вверх!), заполняя кодами или идентификаторами список значений, после чего отсортировать этот список и проверить (тоже в цикле) на отсутствие дублирующих соседних строк - чтобы никакой элемент не повторял предыдущий.
1-я задача решается с помощью .. рекурсии. Рекурсивной функции
Вариантов алгоритмов множество. Предлагаю следующий:
функция (назовем ее, например, НеСодержитРекурсию) получает 2 параметра: массив (изначально пустой) и ссылку на элемент справочника
Проверяет, что полученный массив содержит / не содержит ссылку на полученный элемент справочника
Если содержит, то возвращает, например, значение Ложь (или какое придумаешь, например, ссылку на этот элемент справочника)
Если не содержит, то добавляет к полученному массиву полученную ссылку
и в цикле получает для каждого подчиненного элемента справочника значения рекурсивного вызова самой себя (функции НеСодержитРекурсию),
передавая в качестве параметров обновленный массив и, разумеется, ссылку на каждый элемент справочника из подчиненной таблицы
Если хотя бы одно из полученных значений Ложь (или какое придумал на предыдущем шаге), то функция тоже возвращает Ложь
Иначе возвращает Истина (или, как писал выше, есть другие варианты возвращаемого значения)
Что получаем в итоге: Функция НеСодержитРекурсию обойдет полностью дерево подчиненных ссылок
и вернет Ложь, если найдет хотя бы одну "неправильную" ссылку или вернет Истина, если все хорошо
По 2-й задаче. Условие не понятно вообще. Но если нужно обойти дерево ссылок и что-то в нем проанализировать,
то решение всегда, абсолютно всегда, - рекурсивная функция. Без вариантов
Справочник содержит произвольную структуру отчета, которая состоит из статей.
Каждая статья вычисляется по некоторой формуле или состоит из суммы/разности других статей.
Нужно сделать выборку чтобы вначале вычислились статьи по формулам, затем суммировались статьи для которых уже вычислены все слагаемые, ну и так далее...
Пример (выше без рекурсии):
выборка:
1) 5 или 3 - не являются слагаемыми для других
2) 4 (является слагаемым для 2)
3) 2 (слагаемое для 1)
4) 1
Обе задачи решаются примерно одинаково. Необходимо сформировать таблицу расчетов и обойти ее рекурсивно. Примерно так:
Функция ТаблицаРасчетов()
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| ЗНАЧЕНИЕ(Справочник.Статьи.ПустаяСсылка) КАК Статья,
| Статьи.Ссылка КАК ПодчиненнаяСтатья
|ИЗ
| Справочник.Статьи КАК Статьи
|
|ОБЪЕДИНИТЬ ВСЕ
|
|ВЫБРАТЬ
| СтатьиПодчиненные.Ссылка,
| СтатьиПодчиненные.Статья
|ИЗ
| Справочник.Статьи.Подчиненные КАК СтатьиПодчиненные";
ТаблицаРасчетов = Запрос.Выполнить().Выгрузить();
ТаблицаРасчетов.Колонки.Добавить("Пометка", Новый ОписаниеТипов("Булево"));
Возврат ТаблицаРасчетов;
КонецФункции
Функция ЕстьЗацикливание(ТаблицаРасчетов, Родитель)
СтруктураПоиска = Новый Структура;
СтруктураПоиска.Вставить("Статья", Родитель);
МассивСтрок = ТаблицаРасчетов.НайтиСтроки(СтруктураПоиска);
Для Каждого Стр Из МассивСтрок Цикл
Если Стр.Пометка Тогда
Возврат Истина;
КонецЕсли;
Стр.Пометка = Истина;
Если ЕстьЗацикливание(ТаблицаРасчетов, Стр.ПодчиненнаяСтатья) Тогда
Возврат Истина;
КонецЕсли;
Стр.Пометка = Ложь;
КонецЦикла;
Возврат Ложь;
КонецФункции
Показать
Для второй задачи необходимо просто опускаться до самого последнего элемента в рекурсии и вычислять его. Вышестоящий элемент должен вычисляться только при условии что все подчиненные элементы уже вычислены (т.е. для них установлены все пометки).
Массив = Новый Массив;
КорневойЭлемент = ...;
ЕстьЗацикливание = Ложь;
ПроверкаЗацикливания(КорневойЭлемент, Массив, ЕстьЗацикливание);
Процедура ПроверкаЗацикливания(Элемент, Знач Массив, ЕстьЗацикливание)
Если ЕстьЗацикливание Тогда
Возврат;
КонецЕсли;
Массив.Добавить(Элемент);
Для Каждого ПодчиненныйЭлемент Из Элемент.Подчиненные Цикл
Если Массив.Найти(ПодчиненныйЭлемент) <> Неопределено Тогда
ЕстьЗацикливание = Истина;
Возврат;
КонецЕсли;
ПроверкаЗацикливания(ПодчиненныйЭлемент, Массив, ЕстьЗацикливание);
КонецЦикла;
КонецПроцедуры
Показать
думаю, что не сложно добавить еще какой-то массив/соответствие, чтобы он был не через Знач Массив, в котором после проверки получиться цепочка / дерево от верхнего к нижнему
p.s. в голову еще не пришел оптимальный вариант через запрос)))
(13)
если глубина таблиц не огромная, то можно не париться и использовать как в (8)
ну и естественно замер производительности бы сделать)))
а то вариант с созданием запроса в цикле не особо радует...
Для того, чтобы делать проверку на зацикленность есть несколько подходов:
1. Выбирать все главные элементы и спускаться по иерархии вниз, накапливая при этом информация обо всех родителей (например в массиве) и делать проверку, что элементы на каждом уровне ниже не входят в перечень родителей.
При текущей архитектуре и при очень большом справочнике этот подход не применим, так как для того чтобы определить самого верхнего родителя нужно сделать запрос, который будет анализировать ВСЕ записи в табличной части с подчиненными элементами.
...
ИЗ
Справочник.Справочник1 КАК Справочник1
Левое Соединение Справочник.Справочник1.ПодчиненныеЭлементы КАК ТЧ_ПодчиненныеЭлементы
ПО Справочник1.Ссылка = ТЧ_ПодчиненныеЭлементы.ПодчиненныйЭлемент
ГДЕ
ТЧ_ПодчиненныеЭлементы ЕСТЬ NULL
Показать
2. Можно наоборот, взять элементы снизу иерархии и подниматься по уровням. Самые "низшие" элементы можно взять запросом, отобрав те элементы справочника у которых не заполнена табличная часть с подчиненными элементами (чтобы быстро отбирать такие элементы, можно добавить реквизит "НетПодчиненныхЭлементов" с типом Булево, который будет взводиться ПередЗаписью, если табличная часть - пустая).
Но этот подход не применим, если в справочнике существуют зацикленные элементы, так как у зацикленных цепочек не будет элементов без подчиненных
3. Для маленьких справочников можно загрузить все данные во временную таблицу запроса и крутить их там.
При этом все решить задачу №2 - Получить упорядоченную структуру элементов,
позволяет только пункт 1 и 3.
Я бы изменил архитектуру хранения данных о связях "родитель - подчиненный", и контроль наличия зацикленной иерархии лучше делать каждый раз при записи элемента справочника, как как при этом нужно будет анализировать только одну цепочку, а не все элементы сразу.
Архитектуру бы поменял так:
- хранил бы в таблице не подчиненные элементы, а элементы родителей (как я понял у одного элемента может быть несколько родителей - Элемент 2 в приведенном примере). Тогда можно без проблем получать все верхние элементы, а затем спускаться по иерархии
Если по каким то причинам, так переделать уже нельзя, то тогда нужно создать дополнительную таблицу, которая будет хранить избыточную информацию, но будет позволять быстро получать всю иерархию. Вот интересная статья на эту тему: https://infostart.ru/1c/articles/1105799/. Таблицу можно сделать в виде регистра сведений с двумя измерениями: Элемент / Родитель
- ну и как уже предложили выше, для упорядочивания элементов можно добавить реквизит, который будет хранить номер для сортировки, при этом номер должен устанавливаться перед записью, как максимальный номер из всех родителей + 1. Тут возникнут проблемы, если пользователь будет перемещать элементы по иерархии: например, когда Главный элемент становится подчиненным элементом в другой цепочке. В этом случае придется перечитывать этот номер для все подчиненных элементов: как для новой цепочки, так и для старой
Реализовал так:
- перебор ТЗ с ссылками - если в строке есть ссылка на более раннюю - перемещается в начало. И заново перебор
- ограничение "проходов" по счётчику - предположительно рекурсия...