// 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

		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 polygon’s lists of edges, vertexes and scan lines, and sets these values to NULL.

It also has the feature of setting iUseFastAlgorithm = EFalse.

*/

void CSwDirectGdiPolygonFiller::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 EFalse 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 On return, contains the position on the scan line to start the run.

@param aEnd On return, contains the position on the scan line to end the run.

@panic DGDIAdapter 1015 (debug only)

*/

void CSwDirectGdiPolygonFiller::GetNextPixelRun(TBool& aExists, TInt& aScanLine, TInt& aStart, 

											  TInt& aEnd)

	{

	if (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)

			{

			// add any new edges to the active-edge-list

			for (; (iFastData.nextEdgeToActivate<iNumVertexes) &&

					(iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].upperVertex].iY==iCurrentScanLine);

					++iFastData.numActiveEdges, ++iFastData.nextEdgeToActivate)

				{

				iFastData.activeEdgeList[iFastData.numActiveEdges].edgePtr=&iFastData.edgeList[iFastData.nextEdgeToActivate];

				iFastData.activeEdgeList[iFastData.numActiveEdges].lineGenerator.Construct(

														iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].upperVertex],

														iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].lowerVertex]);

				iFastData.activeEdgeList[iFastData.numActiveEdges].scanLineIntersectionPtr=NULL;

				}

			// sort the active-edge-list into order of adjacent edges (if possible)

			Sort(iFastData.numActiveEdges,TCompareActiveEdgesFirstVertex(iFastData),TSwapActiveEdges(iFastData));

			// find the intersection of each active-edge with the current scan-line

			// for max/min vertex-runs (e.g. \/, \_/, \__/, etc.) add 2 intersections for each run

			// for other vertex-runs (e.g. /----/) add 1 intersection for each run

			for (i=0; i<iFastData.numActiveEdges; ++i)

				{

				// check that active-edge i is not horizontal

				GRAPHICS_ASSERT_DEBUG(iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->upperVertex].iY!=

							   iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY, EDirectGdiPanicPolygonFiller);

				if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->upperVertex].iY==iCurrentScanLine)

					// the scan-line is intersecting active-edge i at its upper-vertex

					FastHandleVertexIntersection(i, EFalse);

				else if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY==iCurrentScanLine)

					// the scan-line is intersecting active-edge i at its lower-vertex

					FastHandleVertexIntersection(i, ETrue);

				else

					// the scan-line is intersecting active-edge i at neither of its vertexes

					SetFastIntersection(iFastData.activeEdgeList[i],*iFastData.activeEdgeList[i].scanLineIntersectionPtr);

				}

			// N.B. iFastData.numScanLineIntersections is less than or equal to iFastData.numActiveEdges

			// sort the intersection-list into increasing order of first-pixel

			Sort(iFastData.numScanLineIntersections,TCompareScanLineIntersectionsFirstPixel(iFastData),TSwapScanLineIntersections(iFastData));

			GRAPHICS_ASSERT_DEBUG(iFastData.numScanLineIntersections>=2, EDirectGdiPanicPolygonFiller);

			}

		// depending on the rule used, find the pixel-run

		TBool doFill=EFalse; // dummy initialization to prevent compiler warning

		if (iScanLineIntersection<iFastData.numScanLineIntersections-1)

			{

			switch (iFillRule)

				{

			case DirectGdi::EAlternate:

				iToggler=!iToggler;

				doFill=iToggler;

				break;

			case DirectGdi::EWinding:

					GRAPHICS_ASSERT_DEBUG(iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex].iY!=

								   iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex].iY,

																										EDirectGdiPanicPolygonFiller);

					if (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex==

						(iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex+1)%iNumVertexes)

						++iNestingLevel;

					else

						--iNestingLevel;

				doFill=(iNestingLevel!=0);

				break;

				}

			if (doFill)

				{

				aStart=Max(iRightMostPixelOnScanLine, iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel)+1;

				aEnd=iFastData.scanLineIntersectionList[iScanLineIntersection+1].firstPixel-1;

				}

			else

				{

				// set the start after the end

				aStart=KMinTInt+1;

				aEnd=KMinTInt;

				}

			if (iRightMostPixelOnScanLine<iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel)

				iRightMostPixelOnScanLine=iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel;

			++iScanLineIntersection;

			}

		if (iScanLineIntersection==iFastData.numScanLineIntersections-1)

			{

			GRAPHICS_ASSERT_DEBUG(iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex].iY!=

						   iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex].iY,

																											EDirectGdiPanicPolygonFiller);

			switch (iFillRule)

				{

			case DirectGdi::EAlternate:

				iToggler=!iToggler;

				GRAPHICS_ASSERT_DEBUG(iToggler==0, EDirectGdiPanicPolygonFiller);

				break;

			case DirectGdi::EWinding:

				if (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex==

					(iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex+1)%iNumVertexes)

					++iNestingLevel;

				else

					--iNestingLevel;

				GRAPHICS_ASSERT_DEBUG((iNumVertexes==2) || (iNestingLevel==0), EDirectGdiPanicPolygonFiller);

				break;

				}

			// remove any scan-line-intersections associated with old active-edges

			for (i=0; i<iFastData.numScanLineIntersections; )

				if (iFastData.vertexList[iFastData.scanLineIntersectionList[i].activeEdgePtr->edgePtr->lowerVertex].iY==iCurrentScanLine)

					{

					iFastData.scanLineIntersectionList[i].activeEdgePtr->scanLineIntersectionPtr=NULL;

					// ripple all the entries in the scan-line-intersection-list after this one back one place

					for (j=i+1; j<iFastData.numScanLineIntersections; ++j)

						{

						iFastData.scanLineIntersectionList[j-1]=iFastData.scanLineIntersectionList[j];

						iFastData.scanLineIntersectionList[j-1].activeEdgePtr->scanLineIntersectionPtr=&iFastData.scanLineIntersectionList[j-1];

						}

					iFastData.scanLineIntersectionList[j-1].activeEdgePtr=NULL;

					--iFastData.numScanLineIntersections;

					}

				else

					++i;

			// remove any old edges from the active-edge-list

			for (i=0; i<iFastData.numActiveEdges; )

				if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY==iCurrentScanLine)

					{

					GRAPHICS_ASSERT_DEBUG(iFastData.activeEdgeList[i].scanLineIntersectionPtr==NULL, EDirectGdiPanicPolygonFiller);

					// ripple all the entries in the active-edge-list after this one back one place

					for (j=i+1; j<iFastData.numActiveEdges; ++j)

						{

						iFastData.activeEdgeList[j-1]=iFastData.activeEdgeList[j];

						if (iFastData.activeEdgeList[j-1].scanLineIntersectionPtr)

							iFastData.activeEdgeList[j-1].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[j-1];

						}

					iFastData.activeEdgeList[j-1].scanLineIntersectionPtr=NULL;

					--iFastData.numActiveEdges;

					}

				else

					++i;

#if defined(_DEBUG)

			for (i=0; i<iFastData.numActiveEdges; ++i)

				{

				GRAPHICS_ASSERT_DEBUG(iFastData.activeEdgeList[i].scanLineIntersectionPtr->activeEdgePtr==

								&iFastData.activeEdgeList[i], EDirectGdiPanicPolygonFiller);

				}

			for (i=0; i<iFastData.numScanLineIntersections; ++i)

				{

				GRAPHICS_ASSERT_DEBUG(iFastData.scanLineIntersectionList[i].activeEdgePtr->scanLineIntersectionPtr==

								&iFastData.scanLineIntersectionList[i], EDirectGdiPanicPolygonFiller);

				}

#endif

			iScanLineIntersection=0;

			++iCurrentScanLine;

			iRightMostPixelOnScanLine=KMinTInt;

			}

		}

	else

		{

		GetNextPixelRunOnSpecifiedScanLine(aExists, iCurrentScanLine, aStart, aEnd);

		if (!aExists)

			GetNextPixelRunOnSpecifiedScanLine(aExists, ++iCurrentScanLine, aStart, aEnd);

		}

	}

/**

Similar to GetNextPixelRun(aExists, aScanLine, aStart, aEnd) this method is used to draw the relevant 

vertex intersections for a polygon but only for an individual specified scan line. The method

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

@param aExists Will be set to false if the line does not pass through the polygon or if

a polygon with no vertexes is specified, otherwise ETrue on return.

@param aScanLine The scan line to be drawn on. Used to set iScanline

@param aStart On return, contains the position on the scan line to start the run.

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

@panic DGDIAdapter 1015, if iUseFastAlgorithm is ETrue (debug only).

*/

void CSwDirectGdiPolygonFiller::GetNextPixelRunOnSpecifiedScanLine(TBool& aExists, 

																 TInt aScanLine, 

																 TInt& aStart, 

																 TInt& aEnd)

	{

	TInt i, j, k;

	GRAPHICS_ASSERT_DEBUG(!iUseFastAlgorithm, EDirectGdiPanicPolygonFiller);

	if (aScanLine<iCurrentScanLine || aScanLine>iLastScanLine)

		{

		aExists=EFalse;

		return;

		}

	aExists=ETrue;

	iCurrentScanLine=aScanLine;

	if (iPolygonIsAllHorizontal)

		{

		// set the start after the end

		aStart=KMinTInt+1;

		aEnd=KMinTInt;

		++iCurrentScanLine;

		return;

		}

	if (iScanLineIntersection==0)

		{

		iSlowData.numIntersectionsWithSameFirstPixelMetThisTime=0;

		iSlowData.numScanLineIntersections=0;

		iSlowData.scanLineComplete=ETrue;

		// find the left-most iSlowData::EStoreSize number (or less) of intersections with this scan-line

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

			{

			TPoint upper=Point(i%iNumVertexes);

			TPoint lower=Point((i+1)%iNumVertexes);

			if (upper.iY>lower.iY)

				{

				TPoint temp=upper;

				upper=lower;

				lower=temp;

				}

			if ((iCurrentScanLine>=upper.iY) && (iCurrentScanLine<=lower.iY))

				{

				// check that the edge starting at vertex i%iNumVertexes is not horizontal

				GRAPHICS_ASSERT_DEBUG(upper.iY!=lower.iY, EDirectGdiPanicPolygonFiller);

				// step through the line-generator until the current scan-line is reached

				TPoint startPos, endPos;

				JumpToCurrentScanLine(iSlowData.lineGenerator, upper, lower, startPos, endPos);

				// find the intersection start and end pixels

				SSlowScanLineIntersection scanLineIntersection;

				scanLineIntersection.firstPixel=Min(startPos.iX, endPos.iX);

				scanLineIntersection.lastPixel=Max(startPos.iX, endPos.iX);

				scanLineIntersection.firstVertexOfEdge=i%iNumVertexes;

				// handle horizontal runs and minima/maxima

				if (upper.iY==iCurrentScanLine)

					SlowHandleVertexIntersection(scanLineIntersection, i, EFalse);

				else if (lower.iY==iCurrentScanLine)

					SlowHandleVertexIntersection(scanLineIntersection, i, ETrue);

				// see if there have been other intersections with the same first-pixel

				if (scanLineIntersection.firstPixel==iSlowData.firstPixelOfLastIntersectionInPrevBuffer)

					++iSlowData.numIntersectionsWithSameFirstPixelMetThisTime;

				// if the intersection has not already been included in a previous buffer-load

				if ((scanLineIntersection.firstPixel>iSlowData.firstPixelOfLastIntersectionInPrevBuffer) ||

					((scanLineIntersection.firstPixel==iSlowData.firstPixelOfLastIntersectionInPrevBuffer) &&

													(iSlowData.numIntersectionsWithSameFirstPixelMetThisTime>=

													iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet)))

					{

					// put the intersection in the right place in the intersection list (if there is room)

					for (j=0; j<iSlowData.numScanLineIntersections; ++j)

						if (scanLineIntersection.firstPixel<iSlowData.scanLineIntersectionList[j].firstPixel)

							{

							if (iSlowData.numScanLineIntersections<SSlowData::EStoreSize)

								++iSlowData.numScanLineIntersections;

							else

								iSlowData.scanLineComplete=EFalse;

							for (k=iSlowData.numScanLineIntersections-1; k>j; --k)

								iSlowData.scanLineIntersectionList[k]=iSlowData.scanLineIntersectionList[k-1];

							iSlowData.scanLineIntersectionList[j]=scanLineIntersection;

							break;

							}

					if (j==iSlowData.numScanLineIntersections)

						{

						if (iSlowData.numScanLineIntersections<SSlowData::EStoreSize)

							iSlowData.scanLineIntersectionList[iSlowData.numScanLineIntersections++]=scanLineIntersection;

						else

							iSlowData.scanLineComplete=EFalse;

						}

					}

				}

			}

		if (!iSlowData.scanLineComplete)

			{

			GRAPHICS_ASSERT_DEBUG(iSlowData.numScanLineIntersections==SSlowData::EStoreSize, EDirectGdiPanicPolygonFiller);

			if (iSlowData.firstPixelOfLastIntersectionInPrevBuffer==iSlowData.scanLineIntersectionList[SSlowData::EStoreSize-1].firstPixel)

				iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet+=SSlowData::EStoreSize-1;

			else

				{

				iSlowData.firstPixelOfLastIntersectionInPrevBuffer=iSlowData.scanLineIntersectionList[SSlowData::EStoreSize-1].firstPixel;

				iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=1;

				for (i=SSlowData::EStoreSize-1; (i>0) && (iSlowData.firstPixelOfLastIntersectionInPrevBuffer==

															iSlowData.scanLineIntersectionList[i-1].firstPixel); --i)

					++iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet;

				}

			}

		}

	// depending on the rule used, find the pixel-run

	TBool doFill=EFalse; // dummy initialization to prevent compiler warning

	if (iScanLineIntersection<iSlowData.numScanLineIntersections-1)

		{

		switch (iFillRule)

			{

		case DirectGdi::EAlternate:

			iToggler=!iToggler;

			doFill=iToggler;

			break;

		case DirectGdi::EWinding:

				GRAPHICS_ASSERT_DEBUG(Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY!=

							   Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY,

																										EDirectGdiPanicPolygonFiller);

				if (Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY>

					Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY)

					++iNestingLevel;

				else

					--iNestingLevel;

			doFill=(iNestingLevel!=0);

			break;

			}

		if (doFill)

			{

			aStart=Max(iRightMostPixelOnScanLine, iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel)+1;

			aEnd=iSlowData.scanLineIntersectionList[iScanLineIntersection+1].firstPixel-1;

			}

		else

			{

			// set the start after the end

			aStart=KMinTInt+1;

			aEnd=KMinTInt;

			}

		if (iRightMostPixelOnScanLine<iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel)

			iRightMostPixelOnScanLine=iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel;

		++iScanLineIntersection;

		}

	if (iScanLineIntersection==iSlowData.numScanLineIntersections-1)

		{

		if (iSlowData.scanLineComplete)

			{

			GRAPHICS_ASSERT_DEBUG(Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY!=

						   Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY,

																											EDirectGdiPanicPolygonFiller);

			switch (iFillRule)

				{

			case DirectGdi::EAlternate:

				iToggler=!iToggler;

				GRAPHICS_ASSERT_DEBUG(iToggler==0, EDirectGdiPanicPolygonFiller);

				break;

			case DirectGdi::EWinding:

				if (Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY>

					Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY)

					++iNestingLevel;

				else

					--iNestingLevel;

				GRAPHICS_ASSERT_DEBUG((!iSlowData.scanLineComplete) || (iNumVertexes==2) || (iNestingLevel==0), EDirectGdiPanicPolygonFiller);

				break;

				}

			}

		iScanLineIntersection=0;

		if (iSlowData.scanLineComplete)

			{

			++iCurrentScanLine;

			iRightMostPixelOnScanLine=KMinTInt;

			iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;

			iSlowData.scanLineComplete=EFalse;

			iSlowData.firstPixelOfLastIntersectionInPrevBuffer=KMinTInt;

			}