text: ﻿/*---------------------------------------------------------------------------------------------
   *  Copyright (c) Howaajin. All rights reserved.
   *  Licensed under the MIT License. See License in the project root for license information.
   *--------------------------------------------------------------------------------------------*/
  
  #include "FastAndSimplePositioningStrategy.h"
  #include "FormatterGraph.h"
  #include "FormatterSettings.h"
  
  void FFastAndSimplePositioningStrategy::Initialize()
  {
  	for (auto& Layer : LayeredNodes)
  	{
  		for (int32 i = 0; i < Layer.Num(); i++)
  		{
  			PosMap.Add(Layer[i], i);
  			if (i != 0)
  			{
  				PredecessorMap.Add(Layer[i], Layer[i - 1]);
  			}
  			else
  			{
  				PredecessorMap.Add(Layer[i], nullptr);
  			}
  			if (i != Layer.Num() - 1)
  			{
  				SuccessorMap.Add(Layer[i], Layer[i + 1]);
  			}
  			else
  			{
  				SuccessorMap.Add(Layer[i], nullptr);
  			}
  		}
  	}
  	MarkConflicts();
  }
  
  void FFastAndSimplePositioningStrategy::MarkConflicts()
  {
  	for (int32 i = 1; i < LayeredNodes.Num() - 1; i++)
  	{
  		int32 k0 = 0;
  		int32 l = 1;
  		for (int32 l1 = 0; l1 < LayeredNodes[i + 1].Num(); l1++)
  		{
  			auto Node = LayeredNodes[i + 1][l1];
  			bool IsCrossingInnerSegment = Node->IsCrossingInnerSegment(LayeredNodes[i + 1], LayeredNodes[i]);
  			if (l1 == LayeredNodes[i + 1].Num() - 1 || IsCrossingInnerSegment)
  			{
  				int32 k1 = LayeredNodes[i].Num();
  				if (IsCrossingInnerSegment)
  				{
  					const auto MedianUpper = Node->GetMedianUpper();
  					k1 = PosMap[MedianUpper];
  				}
  				while (l < l1)
  				{
  					auto UpperNodes = Node->GetUppers();
  					for (auto UpperNode : UpperNodes)
  					{
  						auto k = PosMap[UpperNode];
  						if (k < k0 || k > k1)
  						{
  							ConflictMarks.Add(UpperNode, Node);
  						}
  					}
  					++l;
  				}
  				k0 = k1;
  			}
  		}
  	}
  }
  
  void FFastAndSimplePositioningStrategy::DoVerticalAlignment()
  {
  	RootMap.Empty();
  	AlignMap.Empty();
  	for (auto Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			RootMap.Add(Node, Node);
  			AlignMap.Add(Node, Node);
  		}
  	}
  	int32 LayerStep = IsUpperDirection ? 1 : -1;
  	int32 LayerStart = IsUpperDirection ? 0 : LayeredNodes.Num() - 1;
  	int32 LayerEnd = IsUpperDirection ? LayeredNodes.Num() : -1;
  	for (int32 i = LayerStart; i != LayerEnd; i += LayerStep)
  	{
  		float Weight = 0.0f;
  		int32 Guide = IsLeftDirection ? -1 : INT_MAX;
  		int32 Step = IsLeftDirection ? 1 : -1;
  		int32 Start = IsLeftDirection ? 0 : LayeredNodes[i].Num() - 1;
  		int32 End = IsLeftDirection ? LayeredNodes[i].Num() : -1;
  		for (int32 k = Start; k != End; k += Step)
  		{
  			auto Node = LayeredNodes[i][k];
  			auto Adjacencies = IsUpperDirection ? Node->GetUppers() : Node->GetLowers();
  			if (Adjacencies.Num() > 0)
  			{
  				int32 ma = FMath::TruncToInt((Adjacencies.Num() + 1) / 2.0f - 1);
  				int32 mb = FMath::CeilToInt((Adjacencies.Num() + 1) / 2.0f - 1);
  				for (int32 m = ma; m <= mb; m++)
  				{
  					if (AlignMap[Node] == Node)
  					{
  						auto& MedianNode = Adjacencies[m];
  						bool IsMarked = ConflictMarks.Contains(MedianNode) && ConflictMarks[MedianNode] == Node;
  						float MaxWeight = MedianNode->GetMaxWeight(IsUpperDirection ? EGPD_Output : EGPD_Input);
  						float LinkWeight = Node->GetMaxWeightToNode(MedianNode, IsUpperDirection ? EGPD_Input : EGPD_Output);
  						const auto MedianNodePos = PosMap[MedianNode];
  						bool IsGuideAccepted = IsLeftDirection ? MedianNodePos > Guide : MedianNodePos < Guide;
  						if (!IsMarked)
  						{
  							if (IsGuideAccepted && LinkWeight == MaxWeight)
  							{
  								AlignMap[MedianNode] = Node;
  								RootMap[Node] = RootMap[MedianNode];
  								AlignMap[Node] = RootMap[Node];
  								Guide = MedianNodePos;
  							}
  						}
  					}
  				}
  			}
  		}
  	}
  }
  
  void FFastAndSimplePositioningStrategy::DoHorizontalCompaction()
  {
  	SinkMap.Empty();
  	ShiftMap.Empty();
  	XMap->Empty();
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			SinkMap.Add(Node, Node);
  			if (IsLeftDirection)
  			{
  				ShiftMap.Add(Node, FLT_MAX);
  			}
  			else
  			{
  				ShiftMap.Add(Node, -FLT_MAX);
  			}
  			XMap->Add(Node, NAN);
  		}
  	}
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			if (RootMap[Node] == Node)
  			{
  				PlaceBlock(Node);
  			}
  		}
  	}
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			auto& RootNode = RootMap[Node];
  			(*XMap)[Node] = (*XMap)[RootNode];
  		}
  	}
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			auto& RootNode = RootMap[Node];
  			const float Shift = ShiftMap[SinkMap[RootNode]];
  			if (IsLeftDirection && Shift < FLT_MAX || !IsLeftDirection&& Shift > -FLT_MAX)
  			{
  				(*XMap)[Node] = (*XMap)[Node] + Shift;
  			}
  		}
  	}
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			(*XMap)[Node] += InnerShiftMap[Node];
  		}
  	}
  }
  
  void FFastAndSimplePositioningStrategy::PlaceBlock(FFormatterNode* BlockRoot)
  {
  	const UFormatterSettings& Settings = *GetDefault<UFormatterSettings>();
  	if (FMath::IsNaN((*XMap)[BlockRoot]))
  	{
  		bool Initial = true;
  		(*XMap)[BlockRoot] = 0;
  		auto Node = BlockRoot;
  		do
  		{
  			const auto Adjacency = IsLeftDirection ? PredecessorMap[Node] : SuccessorMap[Node];
  			if (Adjacency != nullptr)
  			{
  				float AdjacencyHeight, NodeHeight;
  				float Spacing;
  				if (IsHorizontalDirection)
  				{
  					AdjacencyHeight = Adjacency->Size.Y;
  					NodeHeight = Node->Size.Y;
  					Spacing = Settings.VerticalSpacing;
  				}
  				else
  				{
  					AdjacencyHeight = Adjacency->Size.X;
  					NodeHeight = Node->Size.X;
  					Spacing = Settings.HorizontalSpacing;
  				}
  
  				const auto PrevBlockRoot = RootMap[Adjacency];
  				PlaceBlock(PrevBlockRoot);
  				if (SinkMap[BlockRoot] == BlockRoot)
  				{
  					SinkMap[BlockRoot] = SinkMap[PrevBlockRoot];
  				}
  				if (SinkMap[BlockRoot] != SinkMap[PrevBlockRoot])
  				{
  					float LeftShift = (*XMap)[BlockRoot] - (*XMap)[PrevBlockRoot] + InnerShiftMap[Node] - InnerShiftMap[Adjacency] - AdjacencyHeight - Spacing;
  					float RightShift = (*XMap)[BlockRoot] - (*XMap)[PrevBlockRoot] - InnerShiftMap[Node] + InnerShiftMap[Adjacency] + NodeHeight + Spacing;
  					float Shift = IsLeftDirection ? FMath::Min(ShiftMap[SinkMap[PrevBlockRoot]], LeftShift) : FMath::Max(ShiftMap[SinkMap[PrevBlockRoot]], RightShift);
  					ShiftMap[SinkMap[PrevBlockRoot]] = Shift;
  				}
  				else
  				{
  					float LeftShift = InnerShiftMap[Adjacency] + AdjacencyHeight - InnerShiftMap[Node] + Spacing;
  					float RightShift = -NodeHeight - Spacing + InnerShiftMap[Adjacency] - InnerShiftMap[Node];
  					float Shift = IsLeftDirection ? LeftShift : RightShift;
  					float Position = (*XMap)[PrevBlockRoot] + Shift;
  					if (Initial)
  					{
  						(*XMap)[BlockRoot] = Position;
  						Initial = false;
  					}
  					else
  					{
  						Position = IsLeftDirection ? FMath::Max((*XMap)[BlockRoot], Position) : FMath::Min((*XMap)[BlockRoot], Position);
  						(*XMap)[BlockRoot] = Position;
  					}
  				}
  			}
  			Node = AlignMap[Node];
  		} while (Node != BlockRoot);
  	}
  }
  
  void FFastAndSimplePositioningStrategy::CalculateInnerShift()
  {
  	InnerShiftMap.Empty();
  	BlockWidthMap.Empty();
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			if (RootMap[Node] == Node)
  			{
  				InnerShiftMap.Add(Node, 0);
  				float Left = 0, Right = IsHorizontalDirection ? Node->Size.Y : Node->Size.X;
  				auto RootNode = Node;
  				auto UpperNode = Node;
  				auto LowerNode = AlignMap[RootNode];
  				while (true)
  				{
  					const float UpperPosition = UpperNode->GetLinkedPositionToNode(LowerNode, IsUpperDirection ? EGPD_Output : EGPD_Input, IsHorizontalDirection);
  					const float LowerPosition = LowerNode->GetLinkedPositionToNode(UpperNode, IsUpperDirection ? EGPD_Input : EGPD_Output, IsHorizontalDirection);
  					const float Shift = InnerShiftMap[UpperNode] + UpperPosition - LowerPosition;
  					InnerShiftMap.FindOrAdd(LowerNode) = Shift;
  					Left = FMath::Min(Left, Shift);
  					Right = FMath::Max(Right, Shift + (IsHorizontalDirection ? LowerNode->Size.Y : LowerNode->Size.X));
  					UpperNode = LowerNode;
  					LowerNode = AlignMap[UpperNode];
  					if (LowerNode == RootNode)
  					{
  						break;
  					}
  				}
  				auto CheckNode = Node;
  				do
  				{
  					InnerShiftMap[CheckNode] -= Left;
  					CheckNode = AlignMap[CheckNode];
  				} while (CheckNode != Node);
  				BlockWidthMap.FindOrAdd(Node) = Right - Left;
  			}
  		}
  	}
  }
  
  void FFastAndSimplePositioningStrategy::Sweep()
  {
  	IsUpperDirection = true;
  	IsLeftDirection = true;
  	XMap = &UpperLeftPositionMap;
  	DoOnePass();
  
  	IsUpperDirection = true;
  	IsLeftDirection = false;
  	XMap = &UpperRightPositionMap;
  	DoOnePass();
  
  	IsUpperDirection = false;
  	IsLeftDirection = true;
  	XMap = &LowerLeftPositionMap;
  	DoOnePass();
  
  	IsUpperDirection = false;
  	IsLeftDirection = false;
  	XMap = &LowerRightPositionMap;
  	DoOnePass();
  
  	Combine();
  }
  
  void FFastAndSimplePositioningStrategy::Combine()
  {
  	TArray<TMap<FFormatterNode*, float>> Layouts = { UpperLeftPositionMap, UpperRightPositionMap, LowerLeftPositionMap, LowerRightPositionMap };
  	TArray<TTuple<float, float>> Bounds;
  	Bounds.SetNumUninitialized(Layouts.Num());
  	int32 MinWidthIndex = -1;
  	float MinWidth = FLT_MAX;
  	for (int32 i = 0; i < Layouts.Num(); i++)
  	{
  		auto& Layout = Layouts[i];
  		float LeftMost = FLT_MAX, RightMost = -FLT_MAX;
  		for (auto& Pair : Layout)
  		{
  			if (Pair.Value < LeftMost)
  			{
  				LeftMost = Pair.Value;
  			}
  			if (Pair.Value > RightMost)
  			{
  				RightMost = Pair.Value;
  			}
  		}
  		if (RightMost - LeftMost < MinWidth)
  		{
  			MinWidth = RightMost - LeftMost;
  			MinWidthIndex = i;
  		}
  		Bounds[i] = TTuple<float, float>(LeftMost, RightMost);
  	}
  	for (int32 i = 0; i < Layouts.Num(); i++)
  	{
  		if (i != MinWidthIndex)
  		{
  			float Offset = Bounds[MinWidthIndex].Get<0>() - Bounds[i].Get<0>();
  			for (auto& Pair : Layouts[i])
  			{
  				Pair.Value += Offset;
  			}
  		}
  	}
  	const UFormatterSettings& Settings = *GetDefault<UFormatterSettings>();
  	for (auto& Layer : LayeredNodes)
  	{
  		for (auto Node : Layer)
  		{
  			TArray<float> Values = { Layouts[0][Node], Layouts[1][Node], Layouts[2][Node], Layouts[3][Node] };
  			Values.Sort();
  			if (!IsHorizontalDirection)
  			{
  				CombinedPositionMap.Add(Node, (Values[0] + Values[3]) / 2.0f);
  			}
  			else
  			{
  				if (Settings.PositioningAlgorithm == EGraphFormatterPositioningAlgorithm::EFastAndSimpleMethodTop)
  				{
  					CombinedPositionMap.Add(Node, (Values[1] + Values[2]) / 2.0f);
  				}
  				else if (Settings.PositioningAlgorithm == EGraphFormatterPositioningAlgorithm::EFastAndSimpleMethodMedian)
  				{
  					CombinedPositionMap.Add(Node, (Values[0] + Values[3]) / 2.0f);
  				}
  			}
  		}
  	}
  	XMap = &CombinedPositionMap;
  }
  
  void FFastAndSimplePositioningStrategy::DoOnePass()
  {
  	DoVerticalAlignment();
  	CalculateInnerShift();
  	DoHorizontalCompaction();
  }
  
  FFastAndSimplePositioningStrategy::FFastAndSimplePositioningStrategy(TArray<TArray<FFormatterNode*>>& InLayeredNodes, bool IsHorizontalDirection)
  	: IPositioningStrategy(InLayeredNodes), IsHorizontalDirection(IsHorizontalDirection)
  {
  	const auto LayersBound = FFormatterGraph::CalculateLayersBound(InLayeredNodes, IsHorizontalDirection);
  	FFormatterNode* FirstNode = InLayeredNodes[0][0];
  	const FVector2D OldPosition = FirstNode->GetPosition();
  	Initialize();
  	Sweep();
  	for (int i = 0; i < LayeredNodes.Num(); i++)
  	{
  		auto& Layer = LayeredNodes[i];
  		for (auto Node : Layer)
  		{
  			float X, Y;
  			float *pX, *pY;
  			if (IsHorizontalDirection)
  			{
  				pX = &X;
  				pY = &Y;
  			}
  			else
  			{
  				pX = &Y;
  				pY = &X;
  			}
  			if (Node->InEdges.Num() == 0)
  			{
  				if (IsHorizontalDirection)
  				{
  					*pX = LayersBound[i].GetTopRight().X - Node->Size.X;
  				}
  				else
  				{
  					*pX = LayersBound[i].GetBottomRight().Y - Node->Size.Y;
  				}
  			}
  			else
  			{
  				if (IsHorizontalDirection)
  				{
  					*pX = LayersBound[i].GetTopLeft().X;
  				}
  				else
  				{
  					*pX = LayersBound[i].GetTopRight().Y;
  				}
  			}
  			*pY = (*XMap)[Node];
  			Node->SetPosition(FVector2D(X, Y));
  		}
  	}
  	const FVector2D NewPosition = FirstNode->GetPosition();
  	const FVector2D Offset = OldPosition - NewPosition;
  	FSlateRect Bound;
  	for (int32 i = 0; i < InLayeredNodes.Num(); i++)
  	{
  		for (auto Node : InLayeredNodes[i])
  		{
  			Node->SetPosition(Node->GetPosition() + Offset);
  			if (Bound.IsValid())
  			{
  				Bound = Bound.Expand(FSlateRect::FromPointAndExtent(Node->GetPosition(), Node->Size));
  			}
  			else
  			{
  				Bound = FSlateRect::FromPointAndExtent(Node->GetPosition(), Node->Size);
  			}
  		}
  	}
  	TotalBound = Bound;
  }
  