Оптимизация закрітия месяца

Процедура РассчитатьСписаниеПоСредней(ТаблицаТоваров, ДатаНач, ДатаКон, СтруктураДопПараметров) Экспорт
	
	// Основное допущение данного метода - игнорирование замкнутой цепочки перемещений между состояниями ("холостого хода"):
	// считаем, что если товар в ходе перемещений снова попал в исходное состояние, то он как бы не перемещался, 
	// это движение можно исключить из общего оборота, а стоимость движения принять равной 0. Цепочки перемещений 
	// таким образом размыкаются, что позволяет рассчитать стоимости движений, начиная от конца цепочки.
	
	// Получим все состояния для товара, которые он принимал за период в виде таблицы
	//	---------------------------------------------------------------------------------------------------------------------------------
	// |Состояние 1 (Источник) |Состояние 2 (Приемник)| Перемещаемое количество| Стоимость (нужна для упрощения последующей корректировки)
	
	// Последовательно обходя состояния, выделим контуры (пути, начала и концы которых совпадают)
	// В каждом контуре найдем количество, которое совершило перемещение по замкнутому кругу ("холостой ход"), 
	// и уменьшим каждое движение из контура на данное количество.
	// Будем выбирать другие состояния для получения всех контуров и применим к ним то же правило.
	
	// После нахождения контуров в графах перемещений и сокращения "холостого хода" получаем совокупность разомкнутых 
	// путей перехода товара между состояниями (остовные деревья). Внутри каждой такой цепочки выполняем расчет.
	// Важно:  в общем случае результат сокращения зависит от последовательности обхода контуров, поэтому
	// для повторяемости результата она должна подчиняться какому-либо правилу (например, чтобы сводные перемещения
	// упорядочивались по возрастанию даты первого перемещения)
	
	// Получим таблицу перемещений, содержащую суммарные перемещения между состояниями
	
	// Получаемая таблица должна содержать колонку "Количество", "Стоимость" и колонки, описывающие старое и новое состояние,
	// причем имена колонок нового состояния заканчиваются на ПрефиксПараметровНовогоСостояния
	ПрефиксПараметровНовогоСостояния="_НовоеСостояние";
	
	Таб = ПолучитьТаблицуПеремещений(ТаблицаТоваров, ДатаНач, ДатаКон, ПрефиксПараметровНовогоСостояния, СтруктураДопПараметров);
	
	
	//1. Приведем переданную таблицу перемещений к тербуемому виду:
	// Таблица имеет колонки Источник, Приемник, Количество
	// строка таблицы соответствует перемещению из состояния 1 в состояние 2, перемещения не повторяются.
	
	// Количество колонок без ПрефиксПараметровНовогоСостояния должно быть равно количеству колонок с ПрефиксПараметровНовогоСостояния
	// Сформируем также структуру, которая содержит параметры состояния товара
	СтруктураСостояния = Новый Структура;
	
	Инд=0;
	Пока Инд< Таб.Колонки.Количество() Цикл
		
		Колонка = Таб.Колонки[Инд];
		
		Если ВРег(Колонка.Имя) <> ВРег("Количество") 
			И ВРег(Колонка.Имя) <> ВРег("КоличествоПриемник")
			И ВРег(Колонка.Имя) <> ВРег("ЕстьИзменениеНоменклатуры")
			И ВРег(Колонка.Имя) <> ВРег("Стоимость") 
			И ВРег(Колонка.Имя) <> ВРег("НДС") Тогда
			
			// Колонки, оканчивающиеся на ПрефиксПараметровНовогоСостояния - правые (новое состояние), им должны соответствовать такие же левые, оканчивающиеся на ПрефиксПараметровНовогоСостояния
			Если Прав(Колонка.Имя, СтрДлина(ПрефиксПараметровНовогоСостояния)) = ПрефиксПараметровНовогоСостояния  Тогда
				ИмяСоответствующейКолонки=Лев(Колонка.Имя, СтрДлина(Колонка.Имя)-СтрДлина(ПрефиксПараметровНовогоСостояния));
				Если Таб.Колонки.Найти(ИмяСоответствующейКолонки)=Неопределено Тогда
					Таб.Колонки.Добавить(ИмяСоответствующейКолонки, Колонка.ТипЗначения)
				КонецЕсли;
				// И наоборот, колонки, не оканчивающиеся на ПрефиксПараметровНовогоСостояния - левые (новое состояние), им должны соответствовать такие же правые, оканчивающиеся на ПрефиксПараметровНовогоСостояния
			Иначе
				ИмяСоответствующейКолонки=Колонка.Имя+ПрефиксПараметровНовогоСостояния;
				Если Таб.Колонки.Найти(ИмяСоответствующейКолонки)=Неопределено Тогда
					Таб.Колонки.Добавить(ИмяСоответствующейКолонки, Колонка.ТипЗначения)
				КонецЕсли;
				
				СтруктураСостояния.Вставить(Колонка.Имя);
			КонецЕсли;
		КонецЕсли;
		
		Инд=Инд+1;
	КонецЦикла;
	
	// В таблице перемещений заменим параметры состояний индексами состояний, сами параметры будут храниться в СоотвПараметровСостояний
	
	Таб.Колонки.Добавить("Источник", Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(5,0)));
	Таб.Колонки.Добавить("Приемник", Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(5,0)));
	
	СоотвПараметровСостояний = Новый Соответствие;
	
	Для Каждого Строка Из Таб Цикл // поиск выплняется полным перебором
		
		// Состояния-источники
		// Найдем состояние в соответсвии
		НайденоСостояние=Ложь;
		Для Каждого ЭлементСостояние Из СоотвПараметровСостояний Цикл
			
			НайденоСостояние=Истина;
			Для Каждого Элемент Из СтруктураСостояния Цикл
				НайденоСостояние = НайденоСостояние И (ЭлементСостояние.Значение[Элемент.Ключ] = Строка[Элемент.Ключ]);
			КонецЦикла;
			
			Если НайденоСостояние Тогда
				Прервать;
			КонецЕсли;
		КонецЦикла;
		
		Если НайденоСостояние Тогда
			ИндексСостояния = ЭлементСостояние.Ключ;
		Иначе
			// Переносим в соответствие
			СтрСост = Новый Структура;
			Для Каждого Элемент Из СтруктураСостояния Цикл
				СтрСост.Вставить(Элемент.Ключ, Строка[Элемент.Ключ]);
			КонецЦикла;
			
			ИндексСостояния = СоотвПараметровСостояний.Количество();
			СоотвПараметровСостояний.Вставить(ИндексСостояния, СтрСост);
		КонецЕсли;
		
		// Оставим в таблице ссылку на состояние
		Строка.Источник = ИндексСостояния;
		
		// То же самое для состояний-приемников
		// Найдем состояние в соответствии
		НайденоСостояние=Ложь;
		Для Каждого ЭлементСостояние Из СоотвПараметровСостояний Цикл
			
			НайденоСостояние=Истина;
			Для Каждого Элемент Из СтруктураСостояния Цикл
				НайденоСостояние = НайденоСостояние И (ЭлементСостояние.Значение[Элемент.Ключ] = Строка[Элемент.Ключ+ПрефиксПараметровНовогоСостояния]);
			КонецЦикла;
			
			Если НайденоСостояние Тогда
				Прервать;
			КонецЕсли;
		КонецЦикла;
		
		Если НайденоСостояние Тогда
			ИндексСостояния = ЭлементСостояние.Ключ;
		Иначе
			// Переносим в соответствие
			СтрСост = Новый Структура;
			Для Каждого Элемент Из СтруктураСостояния Цикл
				СтрСост.Вставить(Элемент.Ключ, Строка[Элемент.Ключ+ПрефиксПараметровНовогоСостояния]);
			КонецЦикла;
			
			ИндексСостояния = СоотвПараметровСостояний.Количество();
			СоотвПараметровСостояний.Вставить(ИндексСостояния, СтрСост);
		КонецЕсли;
		
		// Оставим в таблице ссылку на состояние
		Строка.Приемник = ИндексСостояния;
		
	КонецЦикла;
	
	// "Свернем" встречные перемещения: вместо двух перемещений типа 1->2 и 2->1 оставим одно 
	// с количеством |Кол12 - Кол21| в направлении большего перемещения.
	
	// Проведем следующее преобразование: повернем пары так, чтобы количество перемещения стало положительным
	Для Каждого Строка Из Таб Цикл
		
		Если Строка.Количество<0 Тогда
			Буф=Строка.Приемник;
			Строка.Приемник = Строка.Источник;
			Строка.Источник = Буф;
			Строка.Количество 	= - Строка.Количество;
			Строка.Стоимость 	= - Строка.Стоимость;
			Строка.НДС 			= - Строка.НДС;
		КонецЕсли;
	КонецЦикла;
	
	// "Свертка" встречных перемещений
	Инд=0;
	КолВо = Таб.Количество();
	
	Пока Инд<КолВо Цикл
		
		Инд2 = Инд+1;
		Пока Инд2<КолВо Цикл
			
			Строка2 = Таб[Инд2];
			Строка  = Таб[Инд];
			
			// Если найдено соответствующее встречное перемещение
			Если Строка.Источник = Строка2.Приемник
				И Строка.Приемник = Строка2.Источник 
				И НЕ Строка.ЕстьИзменениеНоменклатуры
				Тогда
				
				Если Строка.Количество>Строка2.Количество Тогда
					УменьшитьНаКоличество 	= Строка2.Количество;
					УменьшитьНаСтоимость 	= Строка2.Стоимость;
					УменьшитьНаНДС 			= Строка2.НДС;
				Иначе
					УменьшитьНаКоличество 	= Строка.Количество;
					УменьшитьНаСтоимость 	= Строка.Стоимость;
					УменьшитьНаНДС 			= Строка.НДС;
				КонецЕсли;
				
				Строка.Количество  	= Строка.Количество  	- УменьшитьНаКоличество;
				Строка2.Количество 	= Строка2.Количество 	- УменьшитьНаКоличество;
				
				// То же самое - со стоимостью
				Строка.Стоимость  	= Строка.Стоимость  	- УменьшитьНаСтоимость;
				Строка2.Стоимость  	= Строка2.Стоимость  	- УменьшитьНаСтоимость;
				
				// То же самое - с НДС
				Строка.НДС  		= Строка.НДС  			- УменьшитьНаНДС;
				Строка2.НДС  		= Строка2.НДС  			- УменьшитьНаНДС;
				
				Строка.КоличествоПриемник  	= Строка.КоличествоПриемник  	- УменьшитьНаКоличество;
				Строка2.КоличествоПриемник 	= Строка2.КоличествоПриемник 	- УменьшитьНаКоличество;
				
				// На этом обход можно прервать: быть не более одной пары встречных перемещений
				Прервать;
				
			Иначе
				Инд2 = Инд2+1;
			КонецЕсли;
			
		КонецЦикла;
		
		Инд = Инд+1;
		
	КонецЦикла;
	
	// Удалим обнулившиеся строки
	
	КолВо = Таб.Количество();
	Инд=0;
	Пока Инд<КолВо Цикл
		
		Строка  = Таб[Инд];
		
		Если Строка.Количество = 0 Тогда
			Таб.Удалить(Строка);
			
			КолВо = КолВо-1;
		Иначе
			Инд=Инд+1;
		КонецЕсли;
	КонецЦикла;
	
	
	// Получили таблицу перемещений в требуемом формате
	ТаблицаПеремещений = Таб;	
	
	ТаблицаПеремещений.Колонки.Добавить("НеКорректироватьСтоимость", Новый ОписаниеТипов("Булево"));
	
	// Таблица перемещений содержит несколько несвязанных частей, относящихся к отдельным партиям - строкам таблицы ТаблицаТоваров
	
	// Обработка перемещений: разрыв контуров
	// Получим наборы смежных вершин для каждой вершины
	// Соотв СмежныеВершины Вершина, СмежныеВершины
	
	Источники = Новый Соответствие;
	Приемники = Новый Соответствие;
	МассивНачалДеревьев = Новый Массив;
	
	Для Каждого Строка Из ТаблицаПеремещений Цикл
		
		ПараметрыИсточника = Источники[Строка.Источник];
		Если ПараметрыИсточника = Неопределено Тогда
			СмежныеВершины= Новый Соответствие;
			ПараметрыИсточника = Новый Структура("Пройден, СмежныеВершины", Ложь, СмежныеВершины);
		КонецЕсли;
		
		ПараметрыИсточника.СмежныеВершины.Вставить(Строка.Приемник, ТаблицаПеремещений.Индекс(Строка)); // во вложенной структуре храним смежную вершину и номер строки перемещения
		
		Источники.Вставить(Строка.Источник, ПараметрыИсточника);
		
	КонецЦикла;
	
	// Чтобы рассчитать перемещения, заменим каждый связный граф перемещений его остовным дерево
	// Для этого обойдем их все, найдем и разорвем все контуры по предложенному выше правилу.
	Для Каждого Элемент Из Источники Цикл
		//ПройденныеВершины = Новый Соответствие;
		//НомерВершины = Элемент.Ключ;
		//ПройденныеВершины.Вставить(НомерВершины, -1);
		ПройденныеВершины = Новый ТаблицаЗначений;
		ПройденныеВершины.Колонки.Добавить("Ключ");
		ПройденныеВершины.Колонки.Добавить("Значение");
		ПройденныеВершины.Индексы.Добавить("Ключ");
		
		НоваяСтрока = ПройденныеВершины.Добавить();
		НоваяСтрока.Ключ = Элемент.Ключ;
		НоваяСтрока.Значение = -1;
		
		НомерВершины = Элемент.Ключ;
		
		Если НЕ Элемент.Значение.Пройден Тогда // если от вершины еще не строился контур, обрабатываем
			РазорватьКонтуры(НомерВершины, Источники, ПройденныеВершины, ТаблицаПеремещений);
		КонецЕсли;
	КонецЦикла;
	
	// После этого таблица содержит незамкнутую последовательность перемещений. 
	// Стоимость перемещений с количеством = 0 в таблице тоже должна быть приведена к 0.
	
	Для Каждого Строка Из ТаблицаПеремещений Цикл
		
		Если Строка.Количество=0 Тогда
			
			ДобавитьЗаписиПоПеремещению(СоотвПараметровСостояний[Строка.Источник], СоотвПараметровСостояний[Строка.Приемник], -Строка.Стоимость, -Строка.НДС, СтруктураДопПараметров)
			
		ИначеЕсли НЕ Строка.НеКорректироватьСтоимость Тогда
			
			Приемники.Вставить(Строка.Приемник, Строка.Приемник);
			
		КонецЕсли;
		
	КонецЦикла;
	
	// Теперь нужно выделить отдельные деревья, определить среднюю стоимость для каждого дерева, 
	// и начиная с самого начала каждого дерева последовательно рассчитать стоимость для каждого состояния/перемещения
	
	// Найдем начало каждого дерева - его нет в приемниках
	Для каждого Строка Из ТаблицаПеремещений Цикл
		
		// Анализируем только ненулевые дуги
		Если Строка.Количество<>0 Тогда
			
			// Если источника нет среди приемников, значит это начало дерева
			Если Приемники[Строка.Источник]=Неопределено Тогда
				
				ВершинаНайдена = Ложь; // признак того, что вершина уже есть в массиве
				Для Каждого НачалоДерева Из МассивНачалДеревьев Цикл
					
					// Такая вершина уже имеется в списке начал
					Если Строка.Источник = НачалоДерева Тогда
						ВершинаНайдена = Истина;
						Прервать;
					КонецЕсли;
				КонецЦикла;
				
				Если НЕ ВершинаНайдена Тогда
					МассивНачалДеревьев.Добавить(Строка.Источник);
				КонецЕсли;
			
			КонецЕсли;
		КонецЕсли;
	КонецЦикла;
	
	// На данном этапе нужна информация о начальном состоянии и внешнем поступлении в каждую вершину
	
	// Будем использовать список вершин, для каждой из которых указаны смежные вершины - приемники и 
	Вершины = Новый Соответствие; // здесь нам понадобится общее количество источников, приемники
	Для Каждого Строка Из ТаблицаПеремещений Цикл
		
		Если Строка.Количество=0 Тогда
			Продолжить;
		КонецЕсли;
		
		// Обработаем источник
		ПодчСтруктура = Вершины[Строка.Источник];
		Если ПодчСтруктура=Неопределено Тогда
			ПодчСтруктура = Новый Структура("КоличествоИсточников, Приемники, КоличествоРассчитанныхВходов", 0, Новый Соответствие, 0);
		КонецЕсли;
		
		// перемещения с фиксированной стоимостью не добавляются в получатели, фиксированная стоимость ниже будет добавлена к начальным остаткам и приходам
		// для этого такие состояния-приемники гарантированно должны быть в списке вершин, даже если они окажутся началами деревьев
		Если НЕ Строка.НеКорректироватьСтоимость Тогда
			ПодчСтруктура.Приемники.Вставить(Строка.Приемник, Новый Структура("Количество, КоличествоПриемник, Стоимость, НДС", Строка.Количество, Строка.КоличествоПриемник, Строка.Стоимость, Строка.НДС));
		КонецЕсли;
		
		Вершины.Вставить(Строка.Источник, ПодчСтруктура);
		
		// Обработаем приемник
		ПодчСтруктура = Вершины[Строка.Приемник];
		Если ПодчСтруктура=Неопределено Тогда
			ПодчСтруктура = Новый Структура("КоличествоИсточников, Приемники, КоличествоРассчитанныхВходов", 1, Новый Соответствие, 0);
		Иначе
			ПодчСтруктура.КоличествоИсточников = ПодчСтруктура.КоличествоИсточников + ?(Строка.НеКорректироватьСтоимость, 0, 1);
		КонецЕсли;
		
		Вершины.Вставить(Строка.Приемник, ПодчСтруктура);
	КонецЦикла;
	
	// В структуру Вершины нужно добавить данные о начальном остатке и внешнем поступлении для каждого из состояний,
	// Можно также добавить состояний, не участвовавших в перемещениях, тогда для них тоже будет рассчитано внешнее списание
	МассивДобавленныеВершины = Новый Массив;
	ДобавитьНачальныйОстатокИВнешнееПоступление(ТаблицаТоваров, Вершины, СоотвПараметровСостояний, ДатаНач, ДатаКон, СтруктураДопПараметров, МассивДобавленныеВершины);
	
	Для Каждого Строка Из ТаблицаПеремещений Цикл
		
		Если Строка.НеКорректироватьСтоимость И Строка.Количество <> 0 Тогда
			
			Состояние = Вершины[Строка.Приемник];
			
			Состояние.Количество = Состояние.Количество + Строка.КоличествоПриемник;
			Состояние.Стоимость = Состояние.Стоимость + Строка.Стоимость;
			Состояние.НДС = Состояние.НДС + Строка.НДС;
			
			Состояние = Вершины[Строка.Источник];
			
			Состояние.Количество = Состояние.Количество - Строка.Количество;
			Состояние.Стоимость = Состояние.Стоимость - Строка.Стоимость;
			Состояние.НДС = Состояние.НДС - Строка.НДС;
		
		КонецЕсли;
		
	КонецЦикла;	
	
	// Добавдленные состояния возвращаются специальным массивом, который добавляется к началам деревьев
	Для Каждого Элемент Из МассивДобавленныеВершины Цикл
		МассивНачалДеревьев.Добавить(Элемент)
	КонецЦикла;
	
	// Теперь будем обходить деревья с начала, и рассчитывать состояния и переходы между ними
	Для Каждого НачалоДерева Из МассивНачалДеревьев Цикл
		РассчитатьПуть(НачалоДерева, Вершины, СоотвПараметровСостояний, СтруктураДопПараметров);
	КонецЦикла;
	
КонецПроцедуры