// Copyright (c) 1997-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 <bitstd.h>

#include "BITPANIC.H"

// TCompareEdgesUpperY

NONSHARABLE_CLASS(TCompareEdgesUpperY) : public TKey

	{

public:

	TCompareEdgesUpperY(const CPolygonFiller::SFastData& aFastData);

private:

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

private:

	const CPolygonFiller::SFastData& iFastData;

	};

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

	iFastData(aFastData)

	{

	}

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;

	}

// TSwapEdges

NONSHARABLE_CLASS(TSwapEdges) : public TSwap

	{

public:

	TSwapEdges(CPolygonFiller::SFastData& aFastData);

private:

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

private:

	CPolygonFiller::SFastData& iFastData;

	};

TSwapEdges::TSwapEdges(CPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

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

	{

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

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

	const CPolygonFiller::SFastEdge temp(leftEdge);

	leftEdge=rightEdge;

	rightEdge=temp;

	}

// TCompareActiveEdgesFirstVertex

NONSHARABLE_CLASS(TCompareActiveEdgesFirstVertex) : public TKey

	{

public:

	TCompareActiveEdgesFirstVertex(const CPolygonFiller::SFastData& aFastData);

private:

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

private:

	const CPolygonFiller::SFastData& iFastData;

	};

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

	iFastData(aFastData)

	{

	}

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;

	}

// TSwapActiveEdges

NONSHARABLE_CLASS(TSwapActiveEdges) : public TSwap

	{

public:

	TSwapActiveEdges(CPolygonFiller::SFastData& aFastData);

private:

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

private:

	CPolygonFiller::SFastData& iFastData;

	};

TSwapActiveEdges::TSwapActiveEdges(CPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

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

	{

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

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

	const CPolygonFiller::SFastActiveEdge temp(leftActiveEdge);

	leftActiveEdge=rightActiveEdge;

	rightActiveEdge=temp;

	if (leftActiveEdge.scanLineIntersectionPtr!=NULL)

		leftActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&leftActiveEdge;

	if (rightActiveEdge.scanLineIntersectionPtr!=NULL)

		rightActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&rightActiveEdge;

	}

// TCompareScanLineIntersectionsFirstPixel

NONSHARABLE_CLASS(TCompareScanLineIntersectionsFirstPixel) : public TKey

	{

public:

	TCompareScanLineIntersectionsFirstPixel(const CPolygonFiller::SFastData& aFastData);

private:

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

private:

	const CPolygonFiller::SFastData& iFastData;

	};

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

	iFastData(aFastData)

	{

	}

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;

	}

// TSwapScanLineIntersections

NONSHARABLE_CLASS(TSwapScanLineIntersections) : public TSwap

	{

public:

	TSwapScanLineIntersections(CPolygonFiller::SFastData& aFastData);

private:

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

private:

	CPolygonFiller::SFastData& iFastData;

	};

TSwapScanLineIntersections::TSwapScanLineIntersections(CPolygonFiller::SFastData& aFastData):

	iFastData(aFastData)

	{

	}

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

	{

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

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

	const CPolygonFiller::SFastScanLineIntersection temp(leftScanLineIntersection);

	leftScanLineIntersection=rightScanLineIntersection;

	rightScanLineIntersection=temp;

	leftScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&leftScanLineIntersection;

	rightScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&rightScanLineIntersection;

	}

// the sorting function

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

	{

#if 1 // quick sort

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

	BG_ASSERT_ALWAYS_INVARIANT(error==KErrNone);

#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

			{

			BG_ASSERT_DEBUG_INVARIANT(startOfHeap>=0);

			if (startOfHeap!=0)

				{

				--startOfHeap;

				}

			else

				{

				--startOfSortedPortion;

				aSwap.Swap(startOfSortedPortion,0);

				BG_ASSERT_DEBUG_INVARIANT(startOfSortedPortion>=1);

				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)

		{

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

		}

	}

#endif

	}

/*

 CPolygonFiller

 */

/**

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

 TInt, TBool pointers respectively.

 */

EXPORT_C CPolygonFiller::CPolygonFiller():

	CBase(),

	iPointArray(NULL),

	iPointList(NULL),

	iFillRule(CGraphicsContext::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.

*/

EXPORT_C CPolygonFiller::~CPolygonFiller()

	{

	Reset();

	}

/**

Takes a list of points to be the points for the new polygon and sets the number of points in the shape. 

After this has been done it transfers the task to <code>Construct(aFillRule,aUsage)</code>. This should not fail.

@param aPointList A list of points for the polygon. 

@param aNumPoints The number of points in the list.

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

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

*/

EXPORT_C void CPolygonFiller::Construct(const TPoint* aPointList,TInt aNumPoints, 

										CGraphicsContext::TFillRule aFillRule, TUsage aUsage)

	{

	BG_ASSERT_ALWAYS(aPointList!=NULL,EBitgdiPanicPolygonFiller);

	iPointList=aPointList;

	iNumVertexes=aNumPoints;

	Construct(aFillRule,aUsage);

	}

/**

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 PointArray 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 CGraphicsContext::TFillRule object.

@param aUsage How the polygon should be used.

*/

EXPORT_C void CPolygonFiller::Construct(const CArrayFix<TPoint>* aPointArray, 

										CGraphicsContext::TFillRule aFillRule, TUsage aUsage)

	{

	BG_ASSERT_ALWAYS(aPointArray!=NULL,EBitgdiPanicPolygonFiller);

	iPointArray=aPointArray;

	iNumVertexes=iPointArray->Count();

	Construct(aFillRule,aUsage);

	}

void CPolygonFiller::Construct(CGraphicsContext::TFillRule aFillRule, TUsage aUsage)

	{

	BG_ASSERT_ALWAYS((aFillRule==CGraphicsContext::EAlternate) || (aFillRule==CGraphicsContext::EWinding),

																					EBitgdiPanicPolygonFiller);

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

																					EBitgdiPanicPolygonFiller);

	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;

	if (iNumVertexes==0)

		return;

	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 uesd for speed since CArrayXxxs are slower for indexing into than built-in arrays

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

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

		// create edge-list

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

			{

			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

		iFirstScanLine=KMaxTInt;

		iLastScanLine=KMinTInt;

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

			{

			TInt y=Point(i).iY;

			if (iFirstScanLine>y)

				iFirstScanLine=y;

			if (iLastScanLine<y)

				iLastScanLine=y;

			}

		}

	iCurrentScanLine=iFirstScanLine;

	}

/**

Frees any data held in the polygons lists of all edges, vertexs and scan lines and sets these values to NULL.

It also has the feature of setting iUseFastAlgorithm = EFalse.

*/

EXPORT_C void CPolygonFiller::Reset()

	{

	if(iUseFastAlgorithm)

		{

		if(iFastData.vertexList)

			{

			User::Free(iFastData.vertexList);

			iFastData.vertexList=NULL;

			}

		if(iFastData.edgeList)

			{

			User::Free(iFastData.edgeList);

			iFastData.edgeList=NULL;

			}

		if(iFastData.activeEdgeList)

			{

			User::Free(iFastData.activeEdgeList);

			iFastData.activeEdgeList=NULL;

			}

		if(iFastData.scanLineIntersectionList)

			{

			User::Free(iFastData.scanLineIntersectionList);

			iFastData.scanLineIntersectionList=NULL;

			}

		iUseFastAlgorithm=EFalse;

		}

	}

/**

Method is used to calculate the locations of vertex interactions between the polygon and scan lines. 

An initial scan line is required. It calculates the start and end positions on the line. The method

can use either the fast or slow polygon algorithm depending upon the state of aUsage. Polygon filling

is also addressed by this method.

@param aExists Will be set to false if a polygon with no vertexes is passed in, otherwise ETrue on return.

@param aScanline On return will contain iScanline at the beginning of the operation.

@param aStart The position on the scan line to start the run, on returned.

@param aEnd The position on the scan line to end the run, returned.

*/

EXPORT_C void CPolygonFiller::GetNextPixelRun(TBool& aExists, TInt& aScanLine, TInt& aStart, 

											  TInt& aEnd)

	{

	if (iNumVertexes==0 || iCurrentScanLine>iLastScanLine)

		{

		aExists=EFalse;

		return;

		}

	aExists=ETrue;

	aScanLine=iCurrentScanLine;

	if (iPolygonIsAllHorizontal)

		{

		// set the start after the end

		aStart=KMinTInt+1;

		aEnd=KMinTInt;

		++iCurrentScanLine;

		return;

		}

	if (iUseFastAlgorithm)

		{

		TInt i, j;

		if (iScanLineIntersection==0)