sl@0: // Copyright (c) 2008-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: //
sl@0: 
sl@0: #include <e32def.h>
sl@0: #include "regionextend.h"
sl@0: 
sl@0: //Only call this if certain neither rectangle is empty.
sl@0: //Region rectangles are always non-empty
sl@0: inline /*static*/
sl@0: TRegionExtend::TOverlapFlags TestDifferenceNotEmpty(const TRect& aThis,const TRect& aThat)
sl@0: 	{
sl@0: 	struct SubAdd
sl@0: 	{
sl@0: 		inline static TRegionExtend::TOverlapFlags Conv(TInt delta)
sl@0: 			{	//returns sub, exact or add for delta of each edge pair
sl@0: 				//neg --> +1	//pos --> +2	//zero ==> 0	
sl@0: 				return TRegionExtend::TOverlapFlags(	
sl@0: 						((delta>>31)&1)	+(((-delta)>>30)&2)		);
sl@0: 			}
sl@0: 	};
sl@0: 	//could use SubAdd for this if...
sl@0: 	if (	aThis.iTl.iX>=aThat.iBr.iX
sl@0: 		||	aThis.iTl.iY>=aThat.iBr.iY
sl@0: 		||					aThat.iTl.iX>=aThis.iBr.iX
sl@0: 		||					aThat.iTl.iY>=aThis.iBr.iY
sl@0: 	)
sl@0: 		return TRegionExtend::TOverlapFlags(TRegionExtend::EDiffers|TRegionExtend::ENoIntersect);
sl@0: 
sl@0: 	TInt subAdd=(	SubAdd::Conv(aThis.iTl.iX-aThat.iTl.iX)
sl@0: 					|	SubAdd::Conv(aThis.iTl.iY-aThat.iTl.iY)
sl@0: 					|	SubAdd::Conv(aThat.iBr.iX-aThis.iBr.iX)
sl@0: 					|	SubAdd::Conv(aThat.iBr.iY-aThis.iBr.iY)
sl@0: 				);
sl@0: 	return 
sl@0: 	TRegionExtend::TOverlapFlags(subAdd);
sl@0: 	}
sl@0: 
sl@0: /**	Calc total area of a list of non-intersecting rectangles (ie a region)
sl@0:  * 	@param	aThisRects	the array of rectangles
sl@0:  * 	@param	aThisCount	the number in the array
sl@0:  */
sl@0: inline TUint RectListArea(const TRect* aThisRects,TInt aThisCount)
sl@0: 	{
sl@0: 	TInt thisArea=0;
sl@0: 	for (TInt stepThis=aThisCount-1;stepThis>=0;stepThis--)
sl@0: 		{
sl@0: 		TSize size=aThisRects[stepThis].Size();
sl@0: 		__ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),4003));
sl@0: 		thisArea+=size.iWidth*size.iHeight;
sl@0: 		}
sl@0: 	return thisArea;
sl@0: 	}
sl@0: /**	Returns the result code flag based on the calculated intersection of two areas
sl@0:  * 	The intersection is always less than or equal to this and that.
sl@0:  * 	@param 	aThisArea		Start area
sl@0:  * 	@param	aIntersectArea	Intersection
sl@0:  * 	@param	aThatArea		Final area
sl@0:  * 	@return
sl@0:  * 		-	EDiffers 	if both this and that differ from intersect 
sl@0:  * 		-	EExact		if both this and that are same as intersect
sl@0:  * 		-	ESub		if only that is same as intersect, so this is bigger
sl@0:  * 		-	EAdd		if only this is same as intersect, so that is bigger
sl@0:  * 		
sl@0:  **/
sl@0: inline TRegionExtend::TOverlapFlags AreaDiffResults(TUint aThisArea,TUint aIntersectArea,TUint aThatArea)
sl@0: 	{
sl@0: 	if (aThisArea>aIntersectArea)
sl@0: 		if (aThatArea>aIntersectArea)
sl@0: 			return TRegionExtend::EDiffers;
sl@0: 		else
sl@0: 			return TRegionExtend::ESub;
sl@0: 	else
sl@0: 		if (aThatArea>aIntersectArea)
sl@0: 			return TRegionExtend::EAdd;
sl@0: 		else
sl@0: 			return TRegionExtend::EExact;
sl@0: 	}
sl@0: /**	Calculates the intersection area of one rectangle with an array of non intersecting rectangles
sl@0:  * 	It is presumed that the caller will loop through all the cells of a target region,
sl@0:  * 	repeating this call for a source region, so we can add an extra optimisation 
sl@0:  * 	to avoid revisiting any source rectangles that have been consumed completely in later passes.
sl@0:  * 	The simplest test is that the source cell is wholy inside the target rect.
sl@0:  * 	The simplest record is a bit field, but that only works up to 32 elements, then will not optimise further elements.
sl@0:  * 	@param	aThisCount 			num elements in rect array
sl@0:  * 	@param	aThisRects			array of rectangles
sl@0:  * 	@param	aThatRect			intersecting rectangle
sl@0:  * 	@param	aOptimiseThisBits	record of elements of rect aray that have been fully consumed
sl@0:  * 	@return	total intersection area
sl@0:  **/
sl@0: inline TUint TestDifferenceRegionInnerLoop(TInt aThisCount,const TRect* aThisRects,TRect& aThatRect,TUint& aOptimiseThisBits)
sl@0: 	{
sl@0: 	TUint intersectArea=0;
sl@0: 	for (TInt stepThis=aThisCount-1,bit=1;stepThis>=0;stepThis--,bit<<=1)
sl@0: 		{
sl@0: 		if (!(aOptimiseThisBits&bit))
sl@0: 			{
sl@0: 			const TRect& thisRect=aThisRects[stepThis];
sl@0: 			TRegionExtend::TOverlapFlags flags=TestDifferenceNotEmpty(thisRect,aThatRect);
sl@0: 			if (!(flags&TRegionExtend::ENoIntersect))
sl@0: 				{
sl@0: 				if (!(flags&TRegionExtend::EAdd))
sl@0: 					{	//Skip rest of inner loop if a containing rect is found
sl@0: 					TSize size=aThatRect.Size();
sl@0: 					intersectArea+=size.iWidth*size.iHeight;
sl@0: 					if (!(flags&TRegionExtend::ESub))	//equal rects...
sl@0: 						{	//skip this cell for rest of outer loop if a contains rect is found
sl@0: 						aOptimiseThisBits|=bit;
sl@0: 						}
sl@0: 					break;	//this cell contains the target rect so don't bother checking any more
sl@0: 					}
sl@0: 				else
sl@0: 					if (!(flags&TRegionExtend::ESub))
sl@0: 						{	//skip this cell for rest of outer loop if a contains rect is found
sl@0: 						aOptimiseThisBits|=bit;
sl@0: 						TSize size=thisRect.Size();
sl@0: 						intersectArea+=size.iWidth*size.iHeight;
sl@0: 						}
sl@0: 					else
sl@0: 						{
sl@0: 						TRect intersect=thisRect;
sl@0: 						intersect.Intersection(aThatRect);
sl@0: 						TSize size=intersect.Size();
sl@0: 						intersectArea+=size.iWidth*size.iHeight;
sl@0: 						}
sl@0: 				}
sl@0: 			}
sl@0: 		}
sl@0: 	return intersectArea;
sl@0: 	}
sl@0: /** Avoids the use of a temp region by performing area calc on the fly.
sl@0:  * If both regions are empty then EOverlapNoIntersect only is returned.
sl@0:  * @param	aThat	target region
sl@0:  * @return	flags from TOverlapFlags enumeration
sl@0:  * 		-	EExact			=0 if rgions are exactly identical
sl@0:  * 		-	ESub			Flagged if some rectangles are removed converting current region to that target
sl@0:  * 		-	EAdd			Flagged if some rectangles are added converting current region to that target
sl@0:  * 		- 	ENoIntersect	if there is no common region between the current region and that target
sl@0:  * 		-	EErrorRegion	One of the regions is signalling CheckError()
sl@0:  **/
sl@0: TRegionExtend::TOverlapFlags	TRegionExtend::TestDifference(const TRegion& aThat)const
sl@0: 	{
sl@0: 	TInt intersectArea=0;
sl@0: 	TInt thisArea=0;
sl@0: 	TInt thatArea=0;
sl@0: 	const TRect* thisRects=RectangleList();
sl@0: 	const TRect* thatRects=aThat.RectangleList();
sl@0: 	TInt thatCount=aThat.Count();
sl@0: 	TInt thisCount=Count();
sl@0: 	
sl@0: 	if (CheckError()||aThat.CheckError())
sl@0: 		return EErrorRegion;
sl@0: 	if (thisCount==0)
sl@0: 		if (thatCount==0)
sl@0: 			return ENoIntersect;
sl@0: 		else
sl@0: 			return TOverlapFlags(ENoIntersect|EAdd);
sl@0: 	//both regions are populated. How big is the intersection?
sl@0: 	//The following optimisation bit is that 
sl@0: 	//if any rect is fully contained by a rect in the opposite region 
sl@0: 	//then further compares against that rect are skipped. For this, inner loop is skipped immediately
sl@0: 	//Can track the first 32 rects of aThat. The remainder won't benefit from the optimisation
sl@0: 	TUint optimiseThisBits=0;	
sl@0: 	for (TInt stepThat=thatCount-1;stepThat>=0;stepThat--)
sl@0: 		{
sl@0: 		TRect thatRect=thatRects[stepThat];
sl@0: 		intersectArea+=TestDifferenceRegionInnerLoop(thisCount,thisRects,thatRect,optimiseThisBits);
sl@0: 		}
sl@0: 	if (intersectArea==0)
sl@0: 		if (thatCount==0)
sl@0: 			return TOverlapFlags(ENoIntersect|ESub);
sl@0: 		else
sl@0: 			return 	TOverlapFlags(ENoIntersect|EAdd|ESub);
sl@0: 	thatArea=RectListArea(thatRects,thatCount);
sl@0: 	thisArea=RectListArea(thisRects,thisCount);
sl@0: 	return AreaDiffResults( thisArea, intersectArea, thatArea );
sl@0: 	}
sl@0: 
sl@0: /** Avoids the use of a temp region by performing area calc on the fly.
sl@0:  * This version further optimises the process by avoiding the client having to re-origin either region.
sl@0:   * If both regions are empty then EOverlapNoIntersect only is returned.
sl@0:  * @param	aThat	target region
sl@0:  * @return	flags from TOverlapFlags enumeration
sl@0:  * 		-	EExact			=0 if rgions are exactly identical
sl@0:  * 		-	ESub			Flagged if some rectangles are removed converting current region to that target
sl@0:  * 		-	EAdd			Flagged if some rectangles are added converting current region to that target
sl@0:  * 		- 	ENoIntersect	if there is no common region between the current region and that target
sl@0:  * 		-	EErrorRegion	One of the regions is signalling CheckError()
sl@0:  **/
sl@0: TRegionExtend::TOverlapFlags	TRegionExtend::TestDifference(const TRegion& aThat,TPoint aOffsetToThat)const
sl@0: 	{
sl@0: 	TInt intersectArea=0;
sl@0: 	TInt thisArea=0;
sl@0: 	TInt thatArea=0;
sl@0: 	const TRect* thisRects=RectangleList();
sl@0: 	const TRect* thatRects=aThat.RectangleList();
sl@0: 	TInt thatCount=aThat.Count();
sl@0: 	TInt thisCount=Count();
sl@0: 	
sl@0: 	if (CheckError()||aThat.CheckError())
sl@0: 		return EErrorRegion;
sl@0: 	if (thisCount==0)
sl@0: 		if (thatCount==0)
sl@0: 			return ENoIntersect;
sl@0: 		else
sl@0: 			return TOverlapFlags(ENoIntersect|EAdd);
sl@0: 	//both regions are populated. How big is the intersection?
sl@0: 	//The following optimisation bit is that 
sl@0: 	//if any rect is fully contained by a rect in the opposite region 
sl@0: 	//then further compares against that rect are skipped. For this, inner loop is skipped immediately
sl@0: 	//Can track the first 32 rects of aThat. The remainder won't benefit from the optimisation
sl@0: 	TUint optimiseThisBits=0;	
sl@0: 	for (TInt stepThat=thatCount-1;stepThat>=0;stepThat--)
sl@0: 		{
sl@0: 		TRect thatRect=thatRects[stepThat];
sl@0: 		thatRect.Move(-aOffsetToThat.iX,-aOffsetToThat.iY);	//this line is the only difference, but the next lump has a lot of parameters...
sl@0: 		intersectArea+=TestDifferenceRegionInnerLoop(thisCount,thisRects,thatRect,optimiseThisBits);
sl@0: 		}
sl@0: 	if (intersectArea==0)
sl@0: 		if (thatCount==0)
sl@0: 			return TOverlapFlags(ENoIntersect|ESub);
sl@0: 		else
sl@0: 			return 	TOverlapFlags(ENoIntersect|EAdd|ESub);
sl@0: 	
sl@0: 	thatArea=RectListArea(thatRects,thatCount);
sl@0: 	thisArea=RectListArea(thisRects,thisCount);
sl@0: 	return AreaDiffResults( thisArea, intersectArea, thatArea );
sl@0: 	}
sl@0: 
sl@0: /** This returns the same comparrison flags between two rectangles.
sl@0:  *	Note that a zero return means exact intersection... 
sl@0:  *  Intended as an internal method, but there doesn't seem to be a useful public alternative.
sl@0:  * 	@param  aThis	source rectangle
sl@0:  *	@param	aThat	target rectangle
sl@0:  * 	@return	flags from TOverlapFlags enumeration
sl@0:  * 		-	EExact			=0 if rgions are exactly identical
sl@0:  * 		-	ESub			Flagged if some rectangles are removed converting this source rectangle to that target
sl@0:  * 		-	EAdd			Flagged if some rectangles are added converting this source rectangle to that target
sl@0:  * 		- 	ENoIntersect	if there is no common region between this source rectangle and that target
sl@0:  **/
sl@0: TRegionExtend::TOverlapFlags TRegionExtend::TestDifference(const TRect& aThis,const TRect& aThat)
sl@0: 	{
sl@0: 	if (aThis.IsEmpty())
sl@0: 		if (aThat.IsEmpty())
sl@0: 			return ENoIntersect;
sl@0: 		else
sl@0: 			return TOverlapFlags(EAdd|ENoIntersect);
sl@0: 	else
sl@0: 		if (aThat.IsEmpty())
sl@0: 			return TOverlapFlags(ESub|ENoIntersect);
sl@0: 	return TestDifferenceNotEmpty(aThis,aThat);
sl@0: 	}	
sl@0: 
sl@0: 
sl@0: /** Returns total area of the region
sl@0:  * 	@return total area
sl@0:  **/
sl@0: TUint	TRegionExtend::Area()const
sl@0: { 
sl@0: return RectListArea(RectangleList(),Count());
sl@0: }
sl@0: 
sl@0: /** Avoids the use of a temp region by performing area calc on the fly.
sl@0:  * If both are empty then EOverlapNoIntersect only is returned.
sl@0:  * @param	aThat	target rectangle
sl@0:  * @return	flags from TOverlapFlags enumeration
sl@0:  * 		-	EExact			=0 if region exactly fills rectangle
sl@0:  * 		-	ESub			Flagged if some rectangles are removed converting current region to that target
sl@0:  * 		-	EAdd			Flagged if some rectangles are added converting current region to that target
sl@0:  * 		- 	ENoIntersect	if there is no common region between the current region and that target
sl@0:  * 		-	EErrorRegion	One of the region is signalling CheckError()
sl@0:  **/
sl@0: TRegionExtend::TOverlapFlags	TRegionExtend::TestDifference(const TRect& aThat)const
sl@0: 	{
sl@0: 	TInt intersectArea=0;
sl@0: 	const TRect* thisRects=RectangleList();
sl@0: 	TInt thisCount=Count();
sl@0: 	
sl@0: 	if (aThat.IsEmpty())
sl@0: 		if (thisCount==0)
sl@0: 			return ENoIntersect;
sl@0: 		else
sl@0: 			return TOverlapFlags(ENoIntersect|ESub);
sl@0: 	if (CheckError())
sl@0: 		return EErrorRegion;
sl@0: 	TInt output=ENoIntersect;
sl@0: 	for (TInt stepThis=thisCount-1,bit=1;stepThis>=0;stepThis--,bit+=bit)
sl@0: 		{
sl@0: 		TOverlapFlags flags=TestDifferenceNotEmpty(thisRects[stepThis],aThat);
sl@0: 		if (!(flags&ENoIntersect))
sl@0: 			{
sl@0: 			if (!(flags&EAdd))		//the target rect does not add anything to this region element
sl@0: 				{	//Skip rest of inner loop if a containing rect is found
sl@0: 				if ((flags&ESub)||thisCount>1)
sl@0: 					return ESub;	//the region element is bigger or there are more region elements
sl@0: 				else
sl@0: 					return EExact;
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				TRect intersect=thisRects[stepThis];
sl@0: 				intersect.Intersection(aThat);
sl@0: 				TSize size=intersect.Size();
sl@0: 				__ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),1003));
sl@0: 				intersectArea+=size.iWidth*size.iHeight;
sl@0: 				
sl@0: 				}
sl@0: 			output&=~ENoIntersect;
sl@0: 			}
sl@0: 		output|=(flags&ESub);
sl@0: 		}
sl@0: 	if (intersectArea==0)
sl@0: 		{
sl@0: 		return TOverlapFlags(output|EAdd);
sl@0: 		}
sl@0: 	TSize size=aThat.Size();
sl@0: 	__ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),2003));
sl@0: 	TInt thatArea=size.iWidth*size.iHeight;
sl@0: 	if (thatArea>intersectArea)
sl@0: 		return TOverlapFlags(output|EAdd);
sl@0: 	else
sl@0: 		return TOverlapFlags(output);
sl@0: 	}
sl@0: 	
sl@0: