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

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

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

     5 // which accompanies this distribution, and is available

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

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 //

    15 

    16 #include <e32def.h>

    17 #include "regionextend.h"

    18 

    19 //Only call this if certain neither rectangle is empty.

    20 //Region rectangles are always non-empty

    21 inline /*static*/

    22 TRegionExtend::TOverlapFlags TestDifferenceNotEmpty(const TRect& aThis,const TRect& aThat)

    23 	{

    24 	struct SubAdd

    25 	{

    26 		inline static TRegionExtend::TOverlapFlags Conv(TInt delta)

    27 			{	//returns sub, exact or add for delta of each edge pair

    28 				//neg --> +1	//pos --> +2	//zero ==> 0	

    29 				return TRegionExtend::TOverlapFlags(	

    30 						((delta>>31)&1)	+(((-delta)>>30)&2)		);

    31 			}

    32 	};

    33 	//could use SubAdd for this if...

    34 	if (	aThis.iTl.iX>=aThat.iBr.iX

    35 		||	aThis.iTl.iY>=aThat.iBr.iY

    36 		||					aThat.iTl.iX>=aThis.iBr.iX

    37 		||					aThat.iTl.iY>=aThis.iBr.iY

    38 	)

    39 		return TRegionExtend::TOverlapFlags(TRegionExtend::EDiffers|TRegionExtend::ENoIntersect);

    40 

    41 	TInt subAdd=(	SubAdd::Conv(aThis.iTl.iX-aThat.iTl.iX)

    42 					|	SubAdd::Conv(aThis.iTl.iY-aThat.iTl.iY)

    43 					|	SubAdd::Conv(aThat.iBr.iX-aThis.iBr.iX)

    44 					|	SubAdd::Conv(aThat.iBr.iY-aThis.iBr.iY)

    45 				);

    46 	return 

    47 	TRegionExtend::TOverlapFlags(subAdd);

    48 	}

    49 

    50 /**	Calc total area of a list of non-intersecting rectangles (ie a region)

    51  * 	@param	aThisRects	the array of rectangles

    52  * 	@param	aThisCount	the number in the array

    53  */

    54 inline TUint RectListArea(const TRect* aThisRects,TInt aThisCount)

    55 	{

    56 	TInt thisArea=0;

    57 	for (TInt stepThis=aThisCount-1;stepThis>=0;stepThis--)

    58 		{

    59 		TSize size=aThisRects[stepThis].Size();

    60 		__ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),4003));

    61 		thisArea+=size.iWidth*size.iHeight;

    62 		}

    63 	return thisArea;

    64 	}

    65 /**	Returns the result code flag based on the calculated intersection of two areas

    66  * 	The intersection is always less than or equal to this and that.

    67  * 	@param 	aThisArea		Start area

    68  * 	@param	aIntersectArea	Intersection

    69  * 	@param	aThatArea		Final area

    70  * 	@return

    71  * 		-	EDiffers 	if both this and that differ from intersect 

    72  * 		-	EExact		if both this and that are same as intersect

    73  * 		-	ESub		if only that is same as intersect, so this is bigger

    74  * 		-	EAdd		if only this is same as intersect, so that is bigger

    75  * 		

    76  **/

    77 inline TRegionExtend::TOverlapFlags AreaDiffResults(TUint aThisArea,TUint aIntersectArea,TUint aThatArea)

    78 	{

    79 	if (aThisArea>aIntersectArea)

    80 		if (aThatArea>aIntersectArea)

    81 			return TRegionExtend::EDiffers;

    82 		else

    83 			return TRegionExtend::ESub;

    84 	else

    85 		if (aThatArea>aIntersectArea)

    86 			return TRegionExtend::EAdd;

    87 		else

    88 			return TRegionExtend::EExact;

    89 	}

    90 /**	Calculates the intersection area of one rectangle with an array of non intersecting rectangles

    91  * 	It is presumed that the caller will loop through all the cells of a target region,

    92  * 	repeating this call for a source region, so we can add an extra optimisation 

    93  * 	to avoid revisiting any source rectangles that have been consumed completely in later passes.

    94  * 	The simplest test is that the source cell is wholy inside the target rect.

    95  * 	The simplest record is a bit field, but that only works up to 32 elements, then will not optimise further elements.

    96  * 	@param	aThisCount 			num elements in rect array

    97  * 	@param	aThisRects			array of rectangles

    98  * 	@param	aThatRect			intersecting rectangle

    99  * 	@param	aOptimiseThisBits	record of elements of rect aray that have been fully consumed

   100  * 	@return	total intersection area

   101  **/

   102 inline TUint TestDifferenceRegionInnerLoop(TInt aThisCount,const TRect* aThisRects,TRect& aThatRect,TUint& aOptimiseThisBits)

   103 	{

   104 	TUint intersectArea=0;

   105 	for (TInt stepThis=aThisCount-1,bit=1;stepThis>=0;stepThis--,bit<<=1)

   106 		{

   107 		if (!(aOptimiseThisBits&bit))

   108 			{

   109 			const TRect& thisRect=aThisRects[stepThis];

   110 			TRegionExtend::TOverlapFlags flags=TestDifferenceNotEmpty(thisRect,aThatRect);

   111 			if (!(flags&TRegionExtend::ENoIntersect))

   112 				{

   113 				if (!(flags&TRegionExtend::EAdd))

   114 					{	//Skip rest of inner loop if a containing rect is found

   115 					TSize size=aThatRect.Size();

   116 					intersectArea+=size.iWidth*size.iHeight;

   117 					if (!(flags&TRegionExtend::ESub))	//equal rects...

   118 						{	//skip this cell for rest of outer loop if a contains rect is found

   119 						aOptimiseThisBits|=bit;

   120 						}

   121 					break;	//this cell contains the target rect so don't bother checking any more

   122 					}

   123 				else

   124 					if (!(flags&TRegionExtend::ESub))

   125 						{	//skip this cell for rest of outer loop if a contains rect is found

   126 						aOptimiseThisBits|=bit;

   127 						TSize size=thisRect.Size();

   128 						intersectArea+=size.iWidth*size.iHeight;

   129 						}

   130 					else

   131 						{

   132 						TRect intersect=thisRect;

   133 						intersect.Intersection(aThatRect);

   134 						TSize size=intersect.Size();

   135 						intersectArea+=size.iWidth*size.iHeight;

   136 						}

   137 				}

   138 			}

   139 		}

   140 	return intersectArea;

   141 	}

   142 /** Avoids the use of a temp region by performing area calc on the fly.

   143  * If both regions are empty then EOverlapNoIntersect only is returned.

   144  * @param	aThat	target region

   145  * @return	flags from TOverlapFlags enumeration

   146  * 		-	EExact			=0 if rgions are exactly identical

   147  * 		-	ESub			Flagged if some rectangles are removed converting current region to that target

   148  * 		-	EAdd			Flagged if some rectangles are added converting current region to that target

   149  * 		- 	ENoIntersect	if there is no common region between the current region and that target

   150  * 		-	EErrorRegion	One of the regions is signalling CheckError()

   151  **/

   152 TRegionExtend::TOverlapFlags	TRegionExtend::TestDifference(const TRegion& aThat)const

   153 	{

   154 	TInt intersectArea=0;

   155 	TInt thisArea=0;

   156 	TInt thatArea=0;

   157 	const TRect* thisRects=RectangleList();

   158 	const TRect* thatRects=aThat.RectangleList();

   159 	TInt thatCount=aThat.Count();

   160 	TInt thisCount=Count();

   161 	

   162 	if (CheckError()||aThat.CheckError())

   163 		return EErrorRegion;

   164 	if (thisCount==0)

   165 		if (thatCount==0)

   166 			return ENoIntersect;

   167 		else

   168 			return TOverlapFlags(ENoIntersect|EAdd);

   169 	//both regions are populated. How big is the intersection?

   170 	//The following optimisation bit is that 

   171 	//if any rect is fully contained by a rect in the opposite region 

   172 	//then further compares against that rect are skipped. For this, inner loop is skipped immediately

   173 	//Can track the first 32 rects of aThat. The remainder won't benefit from the optimisation

   174 	TUint optimiseThisBits=0;	

   175 	for (TInt stepThat=thatCount-1;stepThat>=0;stepThat--)

   176 		{

   177 		TRect thatRect=thatRects[stepThat];

   178 		intersectArea+=TestDifferenceRegionInnerLoop(thisCount,thisRects,thatRect,optimiseThisBits);

   179 		}

   180 	if (intersectArea==0)

   181 		if (thatCount==0)

   182 			return TOverlapFlags(ENoIntersect|ESub);

   183 		else

   184 			return 	TOverlapFlags(ENoIntersect|EAdd|ESub);

   185 	thatArea=RectListArea(thatRects,thatCount);

   186 	thisArea=RectListArea(thisRects,thisCount);

   187 	return AreaDiffResults( thisArea, intersectArea, thatArea );

   188 	}

   189 

   190 /** Avoids the use of a temp region by performing area calc on the fly.

   191  * This version further optimises the process by avoiding the client having to re-origin either region.

   192   * If both regions are empty then EOverlapNoIntersect only is returned.

   193  * @param	aThat	target region

   194  * @return	flags from TOverlapFlags enumeration

   195  * 		-	EExact			=0 if rgions are exactly identical

   196  * 		-	ESub			Flagged if some rectangles are removed converting current region to that target

   197  * 		-	EAdd			Flagged if some rectangles are added converting current region to that target

   198  * 		- 	ENoIntersect	if there is no common region between the current region and that target

   199  * 		-	EErrorRegion	One of the regions is signalling CheckError()

   200  **/

   201 TRegionExtend::TOverlapFlags	TRegionExtend::TestDifference(const TRegion& aThat,TPoint aOffsetToThat)const

   202 	{

   203 	TInt intersectArea=0;

   204 	TInt thisArea=0;

   205 	TInt thatArea=0;

   206 	const TRect* thisRects=RectangleList();

   207 	const TRect* thatRects=aThat.RectangleList();

   208 	TInt thatCount=aThat.Count();

   209 	TInt thisCount=Count();

   210 	

   211 	if (CheckError()||aThat.CheckError())

   212 		return EErrorRegion;

   213 	if (thisCount==0)

   214 		if (thatCount==0)

   215 			return ENoIntersect;

   216 		else

   217 			return TOverlapFlags(ENoIntersect|EAdd);

   218 	//both regions are populated. How big is the intersection?

   219 	//The following optimisation bit is that 

   220 	//if any rect is fully contained by a rect in the opposite region 

   221 	//then further compares against that rect are skipped. For this, inner loop is skipped immediately

   222 	//Can track the first 32 rects of aThat. The remainder won't benefit from the optimisation

   223 	TUint optimiseThisBits=0;	

   224 	for (TInt stepThat=thatCount-1;stepThat>=0;stepThat--)

   225 		{

   226 		TRect thatRect=thatRects[stepThat];

   227 		thatRect.Move(-aOffsetToThat.iX,-aOffsetToThat.iY);	//this line is the only difference, but the next lump has a lot of parameters...

   228 		intersectArea+=TestDifferenceRegionInnerLoop(thisCount,thisRects,thatRect,optimiseThisBits);

   229 		}

   230 	if (intersectArea==0)

   231 		if (thatCount==0)

   232 			return TOverlapFlags(ENoIntersect|ESub);

   233 		else

   234 			return 	TOverlapFlags(ENoIntersect|EAdd|ESub);

   235 	

   236 	thatArea=RectListArea(thatRects,thatCount);

   237 	thisArea=RectListArea(thisRects,thisCount);

   238 	return AreaDiffResults( thisArea, intersectArea, thatArea );

   239 	}

   240 

   241 /** This returns the same comparrison flags between two rectangles.

   242  *	Note that a zero return means exact intersection... 

   243  *  Intended as an internal method, but there doesn't seem to be a useful public alternative.

   244  * 	@param  aThis	source rectangle

   245  *	@param	aThat	target rectangle

   246  * 	@return	flags from TOverlapFlags enumeration

   247  * 		-	EExact			=0 if rgions are exactly identical

   248  * 		-	ESub			Flagged if some rectangles are removed converting this source rectangle to that target

   249  * 		-	EAdd			Flagged if some rectangles are added converting this source rectangle to that target

   250  * 		- 	ENoIntersect	if there is no common region between this source rectangle and that target

   251  **/

   252 TRegionExtend::TOverlapFlags TRegionExtend::TestDifference(const TRect& aThis,const TRect& aThat)

   253 	{

   254 	if (aThis.IsEmpty())

   255 		if (aThat.IsEmpty())

   256 			return ENoIntersect;

   257 		else

   258 			return TOverlapFlags(EAdd|ENoIntersect);

   259 	else

   260 		if (aThat.IsEmpty())

   261 			return TOverlapFlags(ESub|ENoIntersect);

   262 	return TestDifferenceNotEmpty(aThis,aThat);

   263 	}	

   264 

   265 

   266 /** Returns total area of the region

   267  * 	@return total area

   268  **/

   269 TUint	TRegionExtend::Area()const

   270 { 

   271 return RectListArea(RectangleList(),Count());

   272 }

   273 

   274 /** Avoids the use of a temp region by performing area calc on the fly.

   275  * If both are empty then EOverlapNoIntersect only is returned.

   276  * @param	aThat	target rectangle

   277  * @return	flags from TOverlapFlags enumeration

   278  * 		-	EExact			=0 if region exactly fills rectangle

   279  * 		-	ESub			Flagged if some rectangles are removed converting current region to that target

   280  * 		-	EAdd			Flagged if some rectangles are added converting current region to that target

   281  * 		- 	ENoIntersect	if there is no common region between the current region and that target

   282  * 		-	EErrorRegion	One of the region is signalling CheckError()

   283  **/

   284 TRegionExtend::TOverlapFlags	TRegionExtend::TestDifference(const TRect& aThat)const

   285 	{

   286 	TInt intersectArea=0;

   287 	const TRect* thisRects=RectangleList();

   288 	TInt thisCount=Count();

   289 	

   290 	if (aThat.IsEmpty())

   291 		if (thisCount==0)

   292 			return ENoIntersect;

   293 		else

   294 			return TOverlapFlags(ENoIntersect|ESub);

   295 	if (CheckError())

   296 		return EErrorRegion;

   297 	TInt output=ENoIntersect;

   298 	for (TInt stepThis=thisCount-1,bit=1;stepThis>=0;stepThis--,bit+=bit)

   299 		{

   300 		TOverlapFlags flags=TestDifferenceNotEmpty(thisRects[stepThis],aThat);

   301 		if (!(flags&ENoIntersect))

   302 			{

   303 			if (!(flags&EAdd))		//the target rect does not add anything to this region element

   304 				{	//Skip rest of inner loop if a containing rect is found

   305 				if ((flags&ESub)||thisCount>1)

   306 					return ESub;	//the region element is bigger or there are more region elements

   307 				else

   308 					return EExact;

   309 				}

   310 			else

   311 				{

   312 				TRect intersect=thisRects[stepThis];

   313 				intersect.Intersection(aThat);

   314 				TSize size=intersect.Size();

   315 				__ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),1003));

   316 				intersectArea+=size.iWidth*size.iHeight;

   317 				

   318 				}

   319 			output&=~ENoIntersect;

   320 			}

   321 		output|=(flags&ESub);

   322 		}

   323 	if (intersectArea==0)

   324 		{

   325 		return TOverlapFlags(output|EAdd);

   326 		}

   327 	TSize size=aThat.Size();

   328 	__ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),2003));

   329 	TInt thatArea=size.iWidth*size.iHeight;

   330 	if (thatArea>intersectArea)

   331 		return TOverlapFlags(output|EAdd);

   332 	else

   333 		return TOverlapFlags(output);

   334 	}

   335 	

   336