// Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

//

#include "swdirectgdipolygon.h"

/**

A utility class used to sort vertex lists based on y coordinates.

@see CSwDirectGdiPolygonFiller

@see TKey

@internalComponent

*/

NONSHARABLE_CLASS(TCompareEdgesUpperY) : public TKey

	{

public:

	TCompareEdgesUpperY(const CSwDirectGdiPolygonFiller::SFastData& aFastData);

private:

	virtual TInt Compare(TInt aLeft,TInt aRight) const;

private:

	const CSwDirectGdiPolygonFiller::SFastData& iFastData;

	};

TCompareEdgesUpperY::TCompareEdgesUpperY(const CSwDirectGdiPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

/**

Compare edges based on their upper Y coordinate.

@param aLeft Index corresponding to the "left" side of the comparison. 

@param aRight Index corresponding to the "right" side of the comparison.

@return Zero, if the two keys are equal; negative, if the left key is less than the right key; positive, if the left key is greater than the right key.

@see TKey::Compare

*/

TInt TCompareEdgesUpperY::Compare(TInt aLeft,TInt aRight) const

	{

	const TInt leftUpperY=iFastData.vertexList[iFastData.edgeList[aLeft].upperVertex].iY;

	const TInt rightUpperY=iFastData.vertexList[iFastData.edgeList[aRight].upperVertex].iY;

	if (leftUpperY<rightUpperY)

		return -1;

	if (leftUpperY>rightUpperY)

		return 1;

	return 0;

	}

/**

A utility class used to swap entries in edgeList arrays during sort operations.

@see CSwDirectGdiPolygonFiller

@see TSwap

@internalComponent

*/

NONSHARABLE_CLASS(TSwapEdges) : public TSwap

	{

public:

	TSwapEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData);

private:

	virtual void Swap(TInt aLeft,TInt aRight) const;

private:

	CSwDirectGdiPolygonFiller::SFastData& iFastData;

	};

TSwapEdges::TSwapEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

/**

Swaps two elements of an edgeList array. 

@param aLeft The index of an array element participating in the swap. 

@param aRight The index of an array element participating in the swap.

@see TSwap::Swap

*/

void TSwapEdges::Swap(TInt aLeft,TInt aRight) const

	{

	CSwDirectGdiPolygonFiller::SFastEdge& leftEdge=iFastData.edgeList[aLeft];

	CSwDirectGdiPolygonFiller::SFastEdge& rightEdge=iFastData.edgeList[aRight];

	const CSwDirectGdiPolygonFiller::SFastEdge temp(leftEdge);

	leftEdge=rightEdge;

	rightEdge=temp;

	}

/**

A utility class used to sort active edge lists based on the order of their vertexes.

@see CSwDirectGdiPolygonFiller

@see TKey

@internalComponent

*/

NONSHARABLE_CLASS(TCompareActiveEdgesFirstVertex) : public TKey

	{

public:

	TCompareActiveEdgesFirstVertex(const CSwDirectGdiPolygonFiller::SFastData& aFastData);

private:

	virtual TInt Compare(TInt aLeft,TInt aRight) const;

private:

	const CSwDirectGdiPolygonFiller::SFastData& iFastData;

	};

TCompareActiveEdgesFirstVertex::TCompareActiveEdgesFirstVertex(const CSwDirectGdiPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

/**

Compare edges based on the order of their vertexes.

@param aLeft Index corresponding to the "left" side of the comparison. 

@param aRight Index corresponding to the "right" side of the comparison.

@return Zero, if the two keys are equal; negative, if the left key is less than the right key; positive, if the left key is greater than the right key.

@see TKey::Compare

*/

TInt TCompareActiveEdgesFirstVertex::Compare(TInt aLeft,TInt aRight) const

	{

	const TInt leftFirstVertex=iFastData.activeEdgeList[aLeft].edgePtr->firstVertex;

	const TInt rightFirstVertex=iFastData.activeEdgeList[aRight].edgePtr->firstVertex;

	if (leftFirstVertex<rightFirstVertex)

		return -1;

	if (leftFirstVertex>rightFirstVertex)

		return 1;

	return 0;

	}

/**

A utility class used to swap entries in activeEdgeList arrays during sort operations.

@see CSwDirectGdiPolygonFiller

@see TSwap

@internalComponent

*/

NONSHARABLE_CLASS(TSwapActiveEdges) : public TSwap

	{

public:

	TSwapActiveEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData);

private:

	virtual void Swap(TInt aLeft,TInt aRight) const;

private:

	CSwDirectGdiPolygonFiller::SFastData& iFastData;

	};

TSwapActiveEdges::TSwapActiveEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

/**

Swaps two elements of an activeEdgeList array. 

@param aLeft The index of an array element participating in the swap. 

@param aRight The index of an array element participating in the swap.

@see TSwap::Swap

*/

void TSwapActiveEdges::Swap(TInt aLeft,TInt aRight) const

	{

	CSwDirectGdiPolygonFiller::SFastActiveEdge& leftActiveEdge=iFastData.activeEdgeList[aLeft];

	CSwDirectGdiPolygonFiller::SFastActiveEdge& rightActiveEdge=iFastData.activeEdgeList[aRight];

	const CSwDirectGdiPolygonFiller::SFastActiveEdge temp(leftActiveEdge);

	leftActiveEdge=rightActiveEdge;

	rightActiveEdge=temp;

	if (leftActiveEdge.scanLineIntersectionPtr!=NULL)

		leftActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&leftActiveEdge;

	if (rightActiveEdge.scanLineIntersectionPtr!=NULL)

		rightActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&rightActiveEdge;

	}

/**

A utility class used to sort intersection lists based on the position of their first pixel.

@see CSwDirectGdiPolygonFiller

@see TKey

@internalComponent

*/

NONSHARABLE_CLASS(TCompareScanLineIntersectionsFirstPixel) : public TKey

	{

public:

	TCompareScanLineIntersectionsFirstPixel(const CSwDirectGdiPolygonFiller::SFastData& aFastData);

private:

	virtual TInt Compare(TInt aLeft,TInt aRight) const;

private:

	const CSwDirectGdiPolygonFiller::SFastData& iFastData;

	};

TCompareScanLineIntersectionsFirstPixel::TCompareScanLineIntersectionsFirstPixel(const CSwDirectGdiPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

/**

Compare intersections based on the order of their first pixel.

@param aLeft Index corresponding to the "left" side of the comparison. 

@param aRight Index corresponding to the "right" side of the comparison.

@return Zero, if the two keys are equal; negative, if the left key is less than the right key; positive, if the left key is greater than the right key.

@see TKey::Compare

*/

TInt TCompareScanLineIntersectionsFirstPixel::Compare(TInt aLeft,TInt aRight) const

	{

	const TInt leftFirstPixel=iFastData.scanLineIntersectionList[aLeft].firstPixel;

	const TInt rightFirstPixel=iFastData.scanLineIntersectionList[aRight].firstPixel;

	if (leftFirstPixel<rightFirstPixel)

		return -1;

	if (leftFirstPixel>rightFirstPixel)

		return 1;

	return 0;

	}

/**

A utility class used to swap entries in intersection list arrays during sort operations.

@see CSwDirectGdiPolygonFiller

@see TSwap

@internalComponent

*/

NONSHARABLE_CLASS(TSwapScanLineIntersections) : public TSwap

	{

public:

	TSwapScanLineIntersections(CSwDirectGdiPolygonFiller::SFastData& aFastData);

private:

	virtual void Swap(TInt aLeft,TInt aRight) const;

private:

	CSwDirectGdiPolygonFiller::SFastData& iFastData;

	};

TSwapScanLineIntersections::TSwapScanLineIntersections(CSwDirectGdiPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

/**

Swaps two elements of a scanLineIntersectionList array. 

@param aLeft The index of an array element participating in the swap. 

@param aRight The index of an array element participating in the swap.

@see TSwap::Swap

*/

void TSwapScanLineIntersections::Swap(TInt aLeft,TInt aRight) const

	{

	CSwDirectGdiPolygonFiller::SFastScanLineIntersection& leftScanLineIntersection=iFastData.scanLineIntersectionList[aLeft];

	CSwDirectGdiPolygonFiller::SFastScanLineIntersection& rightScanLineIntersection=iFastData.scanLineIntersectionList[aRight];

	const CSwDirectGdiPolygonFiller::SFastScanLineIntersection temp(leftScanLineIntersection);

	leftScanLineIntersection=rightScanLineIntersection;

	rightScanLineIntersection=temp;

	leftScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&leftScanLineIntersection;

	rightScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&rightScanLineIntersection;

	}

/**

Sorts array elements

@param aCount The number of elements in the array.

@param aKey A reference to a suitably initialised TKey derived object.

@param aSwap A reference to a suitably initialised TSwap derived object.

@panic DGDIAdapter 1015, if QuickSort failed.

@internalComponent

*/

LOCAL_C void Sort(TInt aCount,const TKey& aKey,const TSwap& aSwap)

	{

#if 1 // quick sort

	const TInt error=User::QuickSort(aCount,aKey,aSwap);

	GRAPHICS_ASSERT_ALWAYS(error==KErrNone, EDirectGdiPanicPolygonFiller);

#elif 0 // bubble sort

	for (TInt i=1; i<aCount; ++i)

		{

		for (TInt j=i; j>0; --j)

			{

			if (aKey.Compare(j-1,j)>0)

				{

				aSwap.Swap(j-1,j);

				}

			}

		}

#else // heap sort

	TInt startOfSortedPortion=aCount;

	if (startOfSortedPortion>1)

		{

		TInt startOfHeap=startOfSortedPortion>>1;

		FOREVER

			{

			GRAPHICS_ASSERT_DEBUG(startOfHeap>=0, EDirectGdiPanicPolygonFiller);

			if (startOfHeap!=0)

				{

				--startOfHeap;

				}

			else

				{

				--startOfSortedPortion;

				aSwap.Swap(startOfSortedPortion,0);

				GRAPHICS_ASSERT_DEBUG(startOfSortedPortion>=1, EDirectGdiPanicPolygonFiller);

				if (startOfSortedPortion==1)

					{

					break;

					}

				}

			// put aArray[startOfHeap] into the correct place in the heap

			TInt i=startOfHeap;

			FOREVER

				{

				TInt j=(i+1)<<1;

				if ((j>=startOfSortedPortion) || (aKey.Compare(j-1,j)>0))

					{

					--j;

					}

				if ((j>=startOfSortedPortion) || (aKey.Compare(i,j)>=0))

					{

					break;

					}

				aSwap.Swap(i,j);

				i=j;

				}

			}

		}

#endif

#if defined(_DEBUG)

	{

	for (TInt i=1; i<aCount; ++i)

		{

		GRAPHICS_ASSERT_DEBUG(aKey.Compare(i-1,i)<=0, EDirectGdiPanicPolygonFiller);

		}

	}

#endif

	}

/*

 CSwDirectGdiPolygonFiller

 */

/**

 Constructor which initialises all member data to zero, EFalse or null for 

 TInt, TBool pointers respectively.

 */

CSwDirectGdiPolygonFiller::CSwDirectGdiPolygonFiller():

	CBase(),

	iPointArray(NULL),

	iFillRule(DirectGdi::EAlternate),

	iUseFastAlgorithm(EFalse),

	iNumVertexes(0),

	iToggler(EFalse),

	iNestingLevel(0),

	iScanLineIntersection(0),

	iRightMostPixelOnScanLine(0),

	iFirstVertex(0),

	iPolygonIsAllHorizontal(EFalse),

	iFirstScanLine(0),

	iLastScanLine(0),

	iCurrentScanLine(0)

	{

	iFastData.vertexList=NULL;

	iFastData.edgeList=NULL;

	iFastData.activeEdgeList=NULL;

	iFastData.scanLineIntersectionList=NULL;

	iFastData.numActiveEdges=0;

	iFastData.numScanLineIntersections=0;

	iFastData.nextEdgeToActivate=0;

	iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;

	iSlowData.numIntersectionsWithSameFirstPixelMetThisTime=0;

	iSlowData.numScanLineIntersections=0;

	iSlowData.scanLineComplete=EFalse;

	iSlowData.firstPixelOfLastIntersectionInPrevBuffer=0;

	}

/**

Destructor calls reset on the polygon.

*/

CSwDirectGdiPolygonFiller::~CSwDirectGdiPolygonFiller()

	{

	Reset();

	}

/**

An overloaded version of Construct which allows the list of points to be passed in as a point array.

Exactly the same behaviour and structure as above. This should not fail. This method does not require the 

number of nodes to be given as a parameter.

@param aPointArray A pointer to point array, as opposed to a pointer to a point list.

@param aFillRule How filling should be achieved, as described by a DirectGdi::TFillRule object.

@param aUsage How the polygon should be used.

@panic DGDIAdapter 1015, if aPointArray is NULL.

*/

void CSwDirectGdiPolygonFiller::Construct(const TArray<TPoint>* aPointArray, 

										DirectGdi::TFillRule aFillRule, TUsage aUsage)

	{

	GRAPHICS_ASSERT_ALWAYS(aPointArray!=NULL,EDirectGdiPanicPolygonFiller);

	iPointArray=aPointArray;

	iNumVertexes=iPointArray->Count();

	Construct(aFillRule,aUsage);

	}

/**

Builds up the internal meta-data needed to fill the polygon.

@param aFillRule How filling should be achieved, as described by a DirectGdi::TFillRule object.

@param aUsage How the polygon should be used, see TUsage enumeration.

@panic DGDIAdapter 1015, if aFillRule is invalid, or aUsage is invalid. 

*/

void CSwDirectGdiPolygonFiller::Construct(DirectGdi::TFillRule aFillRule, TUsage aUsage)

	{

	GRAPHICS_ASSERT_ALWAYS((aFillRule==DirectGdi::EAlternate) || (aFillRule==DirectGdi::EWinding),

																					EDirectGdiPanicPolygonFiller);

	GRAPHICS_ASSERT_ALWAYS((aUsage==EGetAllPixelRunsSequentially) || (aUsage==EGetPixelRunsSequentiallyForSpecifiedScanLines),

																					EDirectGdiPanicPolygonFiller);

	TInt i, j;

	iFillRule=aFillRule;

	iUseFastAlgorithm=(aUsage==EGetAllPixelRunsSequentially);

	iToggler=EFalse;

	iNestingLevel=0;

	iScanLineIntersection=0;

	iRightMostPixelOnScanLine=KMinTInt;

	// find the first vertex and see if the polygon is all horizontal

	iFirstVertex=0; // dummy default value

	iPolygonIsAllHorizontal=ETrue;

	for (i=0; i<iNumVertexes; ++i)

		if (Point(i).iY!=Point((i+1)%iNumVertexes).iY)

			{

			// i is now set to the vertex before the first non-horizontal edge

			// set j%iNumVertexes to the vertex before the next non-horizontal edge

			for (j=i+1; Point(j%iNumVertexes).iY==Point((j+1)%iNumVertexes).iY; ++j)

				;

			j%=iNumVertexes;

			TInt first=Point(i).iY;

			TInt middle=Point(j).iY;

			TInt last=Point((j+1)%iNumVertexes).iY;

			// if vertex j is a max or min point, set the first-vertex to be j

			if ((middle<first)==(middle<last))

				{

				iFirstVertex=j;

				iPolygonIsAllHorizontal=EFalse;

				break;

				}

			}

	if (iUseFastAlgorithm)

		{

		iFastData.vertexList=(TPoint*)User::Alloc(sizeof(TPoint)*iNumVertexes);

		iFastData.edgeList=(SFastEdge*)User::Alloc(sizeof(SFastEdge)*iNumVertexes);

		iFastData.activeEdgeList=(SFastActiveEdge*)User::Alloc(sizeof(SFastActiveEdge)*iNumVertexes);

		iFastData.scanLineIntersectionList=(SFastScanLineIntersection*)User::Alloc(sizeof(SFastScanLineIntersection)*iNumVertexes);

		if ((iFastData.vertexList==NULL) ||

			(iFastData.edgeList==NULL) ||

			(iFastData.activeEdgeList==NULL) ||

			(iFastData.scanLineIntersectionList==NULL))

			{

			Reset(); // sets iUseFastAlgorithm to EFalse among other things

			}

		}

	if (iUseFastAlgorithm)

		{

		for(TInt vertexcount=0;vertexcount<iNumVertexes;vertexcount++)

			new(&iFastData.activeEdgeList[vertexcount]) SFastActiveEdge;

		iFastData.numActiveEdges=0;

		iFastData.numScanLineIntersections=0;

		iFastData.nextEdgeToActivate=0;

		// put the points into the vertex-list

		// N.B. this array is used for speed since CArrayXxxs are slower for indexing into than built-in arrays

		for (i=0; i<iNumVertexes; ++i)

			{

			// If iFastData.vertexList is NULL this will never be run. iFastData.vertexList is checked 

			// above after which iUseFastAlgorithm is set to EFalse if it is NULL (in Reset())

			// coverity[var_deref_op]

			iFastData.vertexList[i]=Point((i+iFirstVertex)%iNumVertexes);

			}

		// create edge-list

		for (i=0; i<iNumVertexes; ++i)

			{

			// See preceding coverity comment

			// coverity[var_deref_op]

			if (iFastData.vertexList[i].iY<iFastData.vertexList[(i+1)%iNumVertexes].iY)

				{

				iFastData.edgeList[i].upperVertex=i;

				iFastData.edgeList[i].lowerVertex=(i+1)%iNumVertexes;

				}

			else

				{

				iFastData.edgeList[i].upperVertex=(i+1)%iNumVertexes;

				iFastData.edgeList[i].lowerVertex=i;

				}

			iFastData.edgeList[i].firstVertex=i;

			}

		// sort edge-list into order of increasing upper y-position

		Sort(iNumVertexes,TCompareEdgesUpperY(iFastData),TSwapEdges(iFastData));

		// find the first scan-line

		iFirstScanLine=iFastData.vertexList[iFastData.edgeList[0].upperVertex].iY;

		// find the last scan-line

		iLastScanLine=iFirstScanLine;

		for (i=0; i<iNumVertexes; ++i)

			if (iLastScanLine<iFastData.vertexList[i].iY)

				iLastScanLine=iFastData.vertexList[i].iY;

		}

	else

		{

		iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;

		iSlowData.scanLineComplete=EFalse;

		iSlowData.firstPixelOfLastIntersectionInPrevBuffer=KMinTInt;

		// find the first and last scan-lines