#pragma once

#include "volumeshop.h"

#include <iostream>
#include <vector>
#include <map>
#include <limits>

#include "Vector.h"
#include "Label.h"
#include "Attribute.h"
#include "Element.h"


class SilhouetteLayout
{
public:
	SilhouetteLayout()
	{
	};

	~SilhouetteLayout()
	{
	};

	void SetPoints(const std::vector<Vector> & vecPoints)
	{
		m_vecPoints.clear();
		convexify(vecPoints);

		if (m_vecPoints.size() > 0)
		{
			m_vecLengths.resize(m_vecPoints.size(),0.0f);
			m_vecLengths[0] = 0.0f;

			for (unsigned int i=1;i < m_vecPoints.size();i++)
			{
				const float vfDifference[2] = { m_vecPoints[i].GetX()-m_vecPoints[i-1].GetX(),m_vecPoints[i].GetY()-m_vecPoints[i-1].GetY() };
				const float fLength = sqrtf(vfDifference[0]*vfDifference[0] + vfDifference[1]*vfDifference[1]);
				m_vecLengths[i] = m_vecLengths[i-1] + fLength;
			}
		}
	};

	const std::vector<Vector> & GetPoints() const
	{
		return m_vecPoints;
	};

	const std::vector<Label> & GetLabels() const
	{
		return m_vecLabels;
	};

	std::vector<Label> & GetLabels()
	{
		return m_vecLabels;
	};

	void add(const Label & labLabel)
	{
		m_vecLabels.push_back(labLabel);
		Label & labNew = m_vecLabels.back();

		// calculate parameter

		float fMinimumDistance = std::numeric_limits<float>::max();
		float vfNearestPosition[2] = {0.0f,0.0f};
		float fNearestU = 0.0f;
		unsigned int uNearestIndex = 0;

		for (unsigned int i=1;i<m_vecPoints.size();i++)
		{
			const Vector & vecA = m_vecPoints[i-1];
			const Vector & vecB = m_vecPoints[i];
			const float vfDistance[2] = {vecB.GetX() - vecA.GetX(),vecB.GetY() - vecA.GetY()};

			float fU = ((labNew.GetAnchorX() - vecA.GetX())*(vecB.GetX() - vecA.GetX()) + (labNew.GetAnchorY() - vecA.GetY())*(vecB.GetY() - vecA.GetY())) / (vfDistance[0]*vfDistance[0] + vfDistance[1]*vfDistance[1]);
			fU = std::min(1.0f,std::max(0.0f,fU));

			const float vfPosition[2] = {vecA.GetX() + fU * (vecB.GetX() - vecA.GetX()), vecA.GetY() + fU * (vecB.GetY() - vecA.GetY())};		
			const float vfDifference[2] = {vfPosition[0] - labNew.GetAnchorX(), (vfPosition[1] - labNew.GetAnchorY())};
			const float fDistance = GetDistance(vfDifference);//vfDifference[0] * vfDifference[0] + vfDifference[1] * vfDifference[1];

			if (fDistance < fMinimumDistance)
			{
				fMinimumDistance = fDistance;
				vfNearestPosition[0] = vfPosition[0];
				vfNearestPosition[1] = vfPosition[1];
				fNearestU = fU;
				uNearestIndex = i-1;
			}		
		}

		//labNew.SetPosition(vfNearestPosition);
		float fPosition = (GetLength(0,uNearestIndex) + GetLength(uNearestIndex,uNearestIndex+1) * fNearestU) / GetLength();

		while (fPosition > 1.0f)
			fPosition -= 1.0f;

		while (fPosition < 0.0f)
			fPosition += 1.0f;

		while (m_mapIndices.find(fPosition) != m_mapIndices.end())
		{
			fPosition += 0.00125f;

			while (fPosition > 1.0f)
				fPosition -= 1.0f;

			while (fPosition < 0.0f)
				fPosition += 1.0f;
		}

		m_mapIndices[fPosition] = unsigned int(m_vecLabels.size()-1);
		place(labNew,fPosition);
		//labNew.SetText(toString(fPosition));
	};

	void arrange()
	{
		if (m_vecLabels.size() == 0)
			return;

		unsigned int uIterations = 0;
		float fTemperature = 1.0f;

		do
		{
			resolveDistances();
			resolveIntersections();

			std::map<float, unsigned int> mapNewIndices;

			std::map<float, unsigned int>::const_iterator j = --m_mapIndices.end();
			for (std::map<float, unsigned int>::const_iterator i = m_mapIndices.begin(); i != m_mapIndices.end(); i++)
			{
				std::map<float, unsigned int>::const_iterator k = i;
				k = (++k == m_mapIndices.end()) ? m_mapIndices.begin() : k;

				const unsigned int uPreviousIndex = j->second;
				const float fPreviousPosition = j->first;
				const Label & labPrevious = m_vecLabels[uPreviousIndex];

				const unsigned int uCurrentIndex = i->second;
				const float fCurrentPosition = i->first;
				const Label & labCurrent = m_vecLabels[uCurrentIndex];

				const unsigned int uNextIndex = k->second;
				const float fNextPosition = k->first;
				const Label & labNext = m_vecLabels[uNextIndex];

				float fNewPosition = fCurrentPosition;
				const bool bOverlap = (uPreviousIndex != uCurrentIndex) && labPrevious.IsOverlapping(labCurrent);

				if (bOverlap)
				{
					//const float fDisplacement = 0.00625f+0.025f*(GetDistance(labCurrent.GetAnchorX()-labCurrent.GetPositionX(),labCurrent.GetAnchorY()-labCurrent.GetPositionY()));
					const float fDisplacement = fTemperature*0.0125f+(1.0f-fTemperature)*0.0125f*(GetDistance(labCurrent.GetAnchorX()-labCurrent.GetPositionX(),labCurrent.GetAnchorY()-labCurrent.GetPositionY()));

					if (m_vecLabels.size() > 2)
						fNewPosition += fDisplacement;
					else
						fNewPosition += 0.5f*(fCurrentPosition-fPreviousPosition)/fabs(fCurrentPosition-fPreviousPosition)*fDisplacement;
				
					while (fNewPosition > 1.0f)
						fNewPosition -= 1.0f;

					while (fNewPosition < 0.0f)
						fNewPosition += 1.0f;
				}

				while (!(mapNewIndices.find(fNewPosition) == mapNewIndices.end()))
				{
					fNewPosition += 0.00125f;

					while (fNewPosition > 1.0f)
						fNewPosition -= 1.0f;

					while (fNewPosition < 0.0f)
						fNewPosition += 1.0f;
				}
				
				mapNewIndices[fNewPosition] = uCurrentIndex;
				j = i;
			}
				
			m_mapIndices.swap(mapNewIndices);

			for (std::map<float, unsigned int>::iterator iteCurrent = m_mapIndices.begin(); iteCurrent != m_mapIndices.end(); iteCurrent++)
			{
				const float fCurrentPosition = iteCurrent->first;
				const unsigned int uCurrentIndex = iteCurrent->second;
				Label & labCurrent = m_vecLabels[uCurrentIndex];
				place(labCurrent,fCurrentPosition);
			}

			fTemperature *= 0.995f;
			uIterations++;
		}
		while (uIterations < 64);

		resolveDistances();
		resolveIntersections();
		resolveOverlaps();
	};

	void resolveOverlaps()
	{
		bool bAnyOverlap = false;

		do
		{
			bAnyOverlap = false;

			std::map<float, unsigned int>::const_iterator j = --m_mapIndices.end();

			while(!m_vecLabels[j->second].IsVisible())
				j--;

			std::map<float, unsigned int>::const_iterator i = m_mapIndices.begin();

			while(!m_vecLabels[i->second].IsVisible())
				i++;

			for (; i != m_mapIndices.end(); ++i)
			{
				const unsigned int uPreviousIndex = j->second;
				const float fPreviousPosition = j->first;
				Label & labPrevious = m_vecLabels[uPreviousIndex];

				const unsigned int uCurrentIndex = i->second;
				const float fCurrentPosition = i->first;
				Label & labCurrent = m_vecLabels[uCurrentIndex];

				if (!labCurrent.IsVisible())
					continue;

				const bool bOverlap = (uPreviousIndex != uCurrentIndex) && labPrevious.IsVisible() && labCurrent.IsVisible() && labPrevious.IsOverlapping(labCurrent);

				if (bOverlap)
				{
					if (labPrevious.GetDepth() > labCurrent.GetDepth())
						labPrevious.SetVisible(false);
					else
						labCurrent.SetVisible(false);


					bAnyOverlap = true;
					break;
				}

				j = i;
			}

		}
		while (bAnyOverlap);

	};

	operator Element() const
	{
		Element eleElement("silhouettelayout");
		return eleElement;		
	};

	SilhouetteLayout & operator=(const Element & eleElement)
	{
		return *this;
	};

protected:

	const float GetLength(const unsigned int uStart, const unsigned int uEnd)
	{
		return m_vecLengths[uEnd] - m_vecLengths[uStart];
	};

	const float GetLength(const unsigned int uEnd)
	{
		return m_vecLengths[uEnd];
	};

	const float GetLength() const
	{
		return m_vecLengths.back();
	};

	const float GetDistance(const float vfVector[]) const
	{
		return vfVector[0]*vfVector[0] + vfVector[1]*vfVector[1];
	};

	const float GetDistance(const float fX, const float fY) const
	{
		const float vfVector[] = {fY,fY};
		return GetDistance(vfVector);
	};

	const float GetRepulsion(const float fDelta) const
	{
		return (fDelta >= 0.0f ? 1.0f : -1.0f) * (std::max(0.0f,0.5f-0.5f*(2.0f*fabs(fDelta))*(2.0f*fabs(fDelta))));
	};

	const float GetAttraction(const float fDelta) const
	{
		return fDelta*fDelta / 0.1f;
	};

	void place(Label & labLabel, const float fPosition)
	{
		float fPositionX = 0.0f;
		float fPositionY = 0.0f;
		
		float fOffsetX = 0.0f;
		float fOffsetY = 0.0f;

		float fNormalX = 0.0f;
		float fNormalY = 0.0f;
		float fNormalD = 0.0f;

		const float fLength = fPosition * GetLength();

		for (unsigned int j=0;j<m_vecPoints.size()-1;j++)
		{
			if (GetLength(j+1) > fLength)
			{
				const float fUd = (fLength - GetLength(j)) / GetLength(j,j+1);
				const float fXd = m_vecPoints[j+1].GetX() - m_vecPoints[j].GetX(); 
				const float fYd = m_vecPoints[j+1].GetY() - m_vecPoints[j].GetY();

				fNormalX = m_vecPoints[j+1].GetY() - m_vecPoints[j].GetY();
				fNormalY = m_vecPoints[j].GetX() - m_vecPoints[j+1].GetX();
				const float fNormalLength = sqrtf(fNormalX*fNormalX + fNormalY*fNormalY);
				
				fNormalX /= fNormalLength;
				fNormalY /= fNormalLength;

				fNormalD = m_vecPoints[j+1].GetX()*m_vecPoints[j].GetY() - m_vecPoints[j].GetX()*m_vecPoints[j+1].GetY();

				fPositionX = m_vecPoints[j].GetX() + fXd * fUd;
				fPositionY = m_vecPoints[j].GetY() + fYd * fUd;

				break;
			}
		}

		if (fabs(fNormalX) <= 0.5f)
			fOffsetX = -0.5f*labLabel.GetWidth();
		else
			fOffsetX = -float(fNormalX < 0.0f)*labLabel.GetWidth();

		if (fabs(fNormalY) <= 0.5f)
			fOffsetY = -0.5f*labLabel.GetHeight();
		else
			fOffsetY = -float(fNormalY < 0.0f)*labLabel.GetHeight();

		labLabel.SetLinkX(-fOffsetX);
		labLabel.SetLinkY(-fOffsetY);
		labLabel.SetPositionX(fPositionX+fOffsetX);
		labLabel.SetPositionY(fPositionY+fOffsetY);
	};

	void convexify(const std::vector<Vector> & vecPoints)
	{
		if (vecPoints.size() > 2)
		{
			unsigned int uLowest = 0;

			for (unsigned int i=1;i<vecPoints.size();i++)
			{
				const Vector & vecLowest = vecPoints[uLowest];
				const Vector & vecVector = vecPoints[i];

				if (vecVector.GetY() < vecLowest.GetY())
					uLowest = i;
				else if (vecVector.GetY() == vecLowest.GetY())
				{
					if (vecVector.GetX() < vecLowest.GetX())
						uLowest = i;
				}
			}

			m_vecPoints.push_back(vecPoints[uLowest]);
			unsigned int uReference = uLowest;

			do
			{
				uReference = uReference != 0 ? 0 : 1;
				const Vector & vecCurrent = m_vecPoints.back();

				for (unsigned int i = 0; i<vecPoints.size(); i++)
				{
					const Vector & vecReference = vecPoints[uReference];
					const Vector & vecVector = vecPoints[i];

					const float fX0 = vecVector.GetX() - vecCurrent.GetX();
					const float fY0 = vecVector.GetY() - vecCurrent.GetY();

					const float fX1 = vecReference.GetX() - vecCurrent.GetX();
					const float fY1 = vecReference.GetY() - vecCurrent.GetY();

					const float fProduct = fX0*fY1 - fX1*fY0;

					if (fProduct > std::numeric_limits<float>::epsilon())
						uReference = i;
					else if (fProduct == 0.0f)
						if ((fX0*fX0 + fY0*fY0) > (fX1*fX1 + fY1*fY1))
							uReference = i;
				}

				m_vecPoints.push_back(vecPoints[uReference]);
			}
			while( uReference != uLowest );
			
		}
	};

	void resolveIntersections()
	{
		for (std::map<float, unsigned int>::iterator i = m_mapIndices.begin(); i != m_mapIndices.end(); i++)
		{
			for (std::map<float, unsigned int>::iterator j = m_mapIndices.begin(); j != m_mapIndices.end(); j++)
			{
				Label & labFirst = m_vecLabels[i->second];
				Label & labSecond = m_vecLabels[j->second];

				if (i != j)
				{
					const float fX1 = labFirst.GetPositionX() + labFirst.GetLinkX();
					const float fY1 = labFirst.GetPositionY() + labFirst.GetLinkY();
					const float fX2 = labFirst.GetAnchorX();
					const float fY2 = labFirst.GetAnchorY();

					const float fX3 = labSecond.GetPositionX() + labSecond.GetLinkX();
					const float fY3 = labSecond.GetPositionY() + labSecond.GetLinkY();
					const float fX4 = labSecond.GetAnchorX();
					const float fY4 = labSecond.GetAnchorY();

					const float fDenominator = ((fY4-fY3)*(fX2-fX1) - (fX4-fX3)*(fY2-fY1));

					if (fDenominator != 0.0f)
					{
						const float fUa = ((fX4-fX3)*(fY1-fY3) - (fY4-fY3)*(fX1-fX3)) / fDenominator;
						const float fUb = ((fX2-fX1)*(fY1-fY3) - (fY2-fY1)*(fX1-fX3)) / fDenominator;

						if (fUa > 0.01f && fUa < 0.99f && fUb > 0.01f && fUb < 0.99f)
						{
							const unsigned int uTemporary = i->second;
							i->second = j->second;
							j->second = uTemporary;
							
							place(labSecond,i->first);
							place(labFirst,j->first);
						}
					}
				}
			}
		}		
	};

	void resolveDistances()
	{
		for (std::map<float, unsigned int>::iterator i = m_mapIndices.begin(); i != m_mapIndices.end(); i++)
		{
			for (std::map<float, unsigned int>::iterator j = m_mapIndices.begin(); j != m_mapIndices.end(); j++)
			{
				Label & labFirst = m_vecLabels[i->second];
				Label & labSecond = m_vecLabels[j->second];

				if (i != j)
				{
					const float fX1 = labFirst.GetPositionX();
					const float fY1 = labFirst.GetPositionY();
					const float fX2 = labFirst.GetAnchorX();
					const float fY2 = labFirst.GetAnchorY();


					const float fX3 = labSecond.GetPositionX();
					const float fY3 = labSecond.GetPositionY();
					const float fX4 = labSecond.GetAnchorX();
					const float fY4 = labSecond.GetAnchorY();

					const float fFirstDistanceCurrent = GetDistance(fX2-fX1,fY2-fY1);
					const float fFirstDistanceTest = GetDistance(fX2-fX3,fY2-fY3);

					const float fSecondDistanceCurrent = GetDistance(fX4-fX3,fY4-fY3);
					const float fSecondDistanceTest = GetDistance(fX4-fX1,fY4-fY1);

					if (fFirstDistanceTest < fFirstDistanceCurrent && fSecondDistanceTest < fSecondDistanceCurrent)
					{
						const unsigned int uTemporary = i->second;
						i->second = j->second;
						j->second = uTemporary;

						place(labSecond,i->first);
						place(labFirst,j->first);
					}
				}
			}
		}		
	};

private:

	std::vector<Vector> m_vecPoints;
	std::vector<float> m_vecLengths;
	
	std::map<float, unsigned int> m_mapIndices;
	std::vector<Label> m_vecLabels;
};

inline std::ostream & operator<< (std::ostream & os, const SilhouetteLayout & vecSilhouetteLayout)
{
	return os;
}