xref: /aoo42x/main/vcl/source/gdi/regband.cxx (revision d2b26721)
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_vcl.hxx"
26 #include <tools/debug.hxx>
27 #include <vcl/salbtype.hxx>
28 #include <vcl/regband.hxx>
29 
30 #include <algorithm>
31 
32 
33 // =======================================================================
34 //
35 // ImplRegionBand
36 //
37 // Jedes Band enthaelt die zwischen der enthaltenen Ober- und Untergrenze
38 // enthaltenen Rechtecke. Bei den Operationen Union, Intersect, XOr und
39 // Exclude werden immer Rechtecke der gleichen Hoehe ausgewerte; die
40 // Grenzen der Baender sind immer so zu waehlen, dasz dies moeglich ist.
41 //
42 // Die Rechtecke in den Baendern werden nach Moeglichkeit zusammengefaszt.
43 //
44 // Bei der Umwandlung von Polygonen werden alle Punkte des Polygons
45 // in die einzelnen Baender eingetragen (sie stehen fuer jedes Band als
46 // Punkte in einer Liste). Nach dem Eintragen der Punkte werden diese
47 // in Rechtecke umgewandelt und die Liste der Punkte geloescht.
48 //
49 // -----------------------------------------------------------------------
50 
ImplRegionBand(long nTop,long nBottom)51 ImplRegionBand::ImplRegionBand( long nTop, long nBottom )
52 {
53 	// save boundaries
54 	mnYTop				= nTop;
55 	mnYBottom			= nBottom;
56 
57 	// initialize lists
58 	mpNextBand			= NULL;
59 	mpPrevBand			= NULL;
60 	mpFirstSep			= NULL;
61 	mpFirstBandPoint	= NULL;
62 	mbTouched			= false;
63 }
64 
65 // -----------------------------------------------------------------------
66 
ImplRegionBand(const ImplRegionBand & rRegionBand,const bool bIgnorePoints)67 ImplRegionBand::ImplRegionBand(
68     const ImplRegionBand& rRegionBand,
69     const bool bIgnorePoints)
70 {
71 	// copy boundaries
72 	mnYTop				= rRegionBand.mnYTop;
73 	mnYBottom			= rRegionBand.mnYBottom;
74 	mbTouched			= rRegionBand.mbTouched;
75 
76 	// initialisation
77 	mpNextBand			= NULL;
78 	mpPrevBand			= NULL;
79 	mpFirstSep			= NULL;
80 	mpFirstBandPoint	= NULL;
81 
82 	// copy all elements of the list with separations
83 	ImplRegionBandSep* pNewSep;
84 	ImplRegionBandSep* pPrevSep = 0;
85 	ImplRegionBandSep* pSep = rRegionBand.mpFirstSep;
86 	while ( pSep )
87 	{
88 		// create new and copy data
89 		pNewSep 			= new ImplRegionBandSep;
90 		pNewSep->mnXLeft	= pSep->mnXLeft;
91 		pNewSep->mnXRight	= pSep->mnXRight;
92 		pNewSep->mbRemoved	= pSep->mbRemoved;
93 		pNewSep->mpNextSep	= NULL;
94 		if ( pSep == rRegionBand.mpFirstSep )
95 			mpFirstSep = pNewSep;
96 		else
97 			pPrevSep->mpNextSep = pNewSep;
98 
99 		pPrevSep = pNewSep;
100 		pSep = pSep->mpNextSep;
101 	}
102 
103     if ( ! bIgnorePoints)
104     {
105     	// Copy points.
106         ImplRegionBandPoint* pPoint = rRegionBand.mpFirstBandPoint;
107         ImplRegionBandPoint* pPrevPointCopy = NULL;
108         while (pPoint != NULL)
109         {
110             ImplRegionBandPoint* pPointCopy = new ImplRegionBandPoint();
111             pPointCopy->mnX = pPoint->mnX;
112             pPointCopy->mnLineId = pPoint->mnLineId;
113             pPointCopy->mbEndPoint = pPoint->mbEndPoint;
114             pPointCopy->meLineType = pPoint->meLineType;
115 
116             if (pPrevPointCopy != NULL)
117                 pPrevPointCopy->mpNextBandPoint = pPointCopy;
118             else
119                 mpFirstBandPoint = pPointCopy;
120 
121             pPrevPointCopy = pPointCopy;
122             pPoint = pPoint->mpNextBandPoint;
123         }
124     }
125 }
126 
127 // -----------------------------------------------------------------------
128 
~ImplRegionBand()129 ImplRegionBand::~ImplRegionBand()
130 {
131 	DBG_ASSERT( mpFirstBandPoint == NULL, "ImplRegionBand::~ImplRegionBand -> pointlist not empty" );
132 
133 	// delete elements of the list
134 	ImplRegionBandSep* pSep = mpFirstSep;
135 	while ( pSep )
136 	{
137 		ImplRegionBandSep* pTempSep = pSep->mpNextSep;
138 		delete pSep;
139 		pSep = pTempSep;
140 	}
141 
142 	// delete elements of the list
143 	ImplRegionBandPoint* pPoint = mpFirstBandPoint;
144 	while ( pPoint )
145 	{
146 		ImplRegionBandPoint* pTempPoint = pPoint->mpNextBandPoint;
147 		delete pPoint;
148 		pPoint = pTempPoint;
149 	}
150 }
151 
152 // -----------------------------------------------------------------------
153 //
154 // generate separations from lines and process union with existing
155 // separations
156 
ProcessPoints()157 void ImplRegionBand::ProcessPoints()
158 {
159 	// check Pointlist
160 	ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
161 	while ( pRegionBandPoint )
162 	{
163 		// within list?
164 		if ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
165 		{
166 			// start/stop?
167 			if ( pRegionBandPoint->mbEndPoint && pRegionBandPoint->mpNextBandPoint->mbEndPoint )
168 			{
169 				// same direction? -> remove next point!
170 				if ( pRegionBandPoint->meLineType == pRegionBandPoint->mpNextBandPoint->meLineType )
171 				{
172 					ImplRegionBandPoint* pSaveRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
173 					pRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
174 					delete pSaveRegionBandPoint;
175 				}
176 			}
177 		}
178 
179 		// continue with next element in the list
180 		pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
181 	}
182 
183 	pRegionBandPoint = mpFirstBandPoint;
184 	while ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
185 	{
186 		Union( pRegionBandPoint->mnX, pRegionBandPoint->mpNextBandPoint->mnX );
187 
188 		ImplRegionBandPoint* pNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
189 
190 		// remove already processed points
191 		delete pRegionBandPoint->mpNextBandPoint;
192 		delete pRegionBandPoint;
193 
194 		// continue with next element in the list
195 		pRegionBandPoint = pNextBandPoint;
196 	}
197 
198 	// remove last element if necessary
199 	if ( pRegionBandPoint )
200 		delete pRegionBandPoint;
201 
202 	// list is now empty
203 	mpFirstBandPoint = NULL;
204 }
205 
206 // -----------------------------------------------------------------------
207 //
208 // generate separations from lines and process union with existing
209 // separations
210 
InsertPoint(long nX,long nLineId,bool bEndPoint,LineType eLineType)211 bool ImplRegionBand::InsertPoint( long nX, long nLineId,
212 								  bool bEndPoint, LineType eLineType )
213 {
214 	if ( !mpFirstBandPoint )
215 	{
216 		mpFirstBandPoint				  = new ImplRegionBandPoint;
217 		mpFirstBandPoint->mnX			  = nX;
218 		mpFirstBandPoint->mnLineId		  = nLineId;
219 		mpFirstBandPoint->mbEndPoint	  = bEndPoint;
220 		mpFirstBandPoint->meLineType	  = eLineType;
221 		mpFirstBandPoint->mpNextBandPoint = NULL;
222 		return true;
223 	}
224 
225 	// look if line already touched the band
226 	ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
227 	ImplRegionBandPoint* pLastTestedRegionBandPoint = NULL;
228 	while( pRegionBandPoint )
229 	{
230 		if ( pRegionBandPoint->mnLineId == nLineId )
231 		{
232 			if ( bEndPoint )
233 			{
234 				if( !pRegionBandPoint->mbEndPoint )
235 				{
236 					// remove old band point
237 					if( !mpFirstBandPoint->mpNextBandPoint )
238 					{
239 						// if we've only got one point => replace first point
240 						pRegionBandPoint->mnX = nX;
241 						pRegionBandPoint->mbEndPoint = true;
242 						return true;
243 					}
244 					else
245 					{
246 						// remove current point
247 						if( !pLastTestedRegionBandPoint )
248 						{
249 							// remove and delete old first point
250 							ImplRegionBandPoint* pSaveBandPoint = mpFirstBandPoint;
251 							mpFirstBandPoint = mpFirstBandPoint->mpNextBandPoint;
252 							delete pSaveBandPoint;
253 						}
254 						else
255 						{
256 							// remove and delete current band point
257 							pLastTestedRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint;
258 							delete pRegionBandPoint;
259 						}
260 
261 						break;
262 					}
263 				}
264 			}
265 			else
266 				return false;
267 		}
268 
269 		// use next element
270 		pLastTestedRegionBandPoint = pRegionBandPoint;
271 		pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
272 	}
273 
274 	// search appropriate position and insert point into the list
275 	ImplRegionBandPoint* pNewRegionBandPoint;
276 
277 	pRegionBandPoint = mpFirstBandPoint;
278 	pLastTestedRegionBandPoint = NULL;
279 	while ( pRegionBandPoint )
280 	{
281 		// new point completely left? -> insert as first point
282 		if ( nX <= pRegionBandPoint->mnX )
283 		{
284 			pNewRegionBandPoint 					= new ImplRegionBandPoint;
285 			pNewRegionBandPoint->mnX				= nX;
286 			pNewRegionBandPoint->mnLineId			= nLineId;
287 			pNewRegionBandPoint->mbEndPoint 		= bEndPoint;
288 			pNewRegionBandPoint->meLineType 		= eLineType;
289 			pNewRegionBandPoint->mpNextBandPoint	= pRegionBandPoint;
290 
291 			// connections to the new point
292 			if ( !pLastTestedRegionBandPoint )
293 				mpFirstBandPoint = pNewRegionBandPoint;
294 			else
295 				pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
296 
297 			return true;
298 		}
299 
300 		// use next element
301 		pLastTestedRegionBandPoint = pRegionBandPoint;
302 		pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
303 	}
304 
305 	// not inserted -> add to the end of the list
306 	pNewRegionBandPoint 					= new ImplRegionBandPoint;
307 	pNewRegionBandPoint->mnX				= nX;
308 	pNewRegionBandPoint->mnLineId			= nLineId;
309 	pNewRegionBandPoint->mbEndPoint 		= bEndPoint;
310 	pNewRegionBandPoint->meLineType 		= eLineType;
311 	pNewRegionBandPoint->mpNextBandPoint	= NULL;
312 
313 	// connections to the new point
314 	pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
315 
316 	return true;
317 }
318 
319 // -----------------------------------------------------------------------
320 
MoveX(long nHorzMove)321 void ImplRegionBand::MoveX( long nHorzMove )
322 {
323 	// move all x-separations
324 	ImplRegionBandSep* pSep = mpFirstSep;
325 	while ( pSep )
326 	{
327 		pSep->mnXLeft  += nHorzMove;
328 		pSep->mnXRight += nHorzMove;
329 		pSep = pSep->mpNextSep;
330 	}
331 }
332 
333 // -----------------------------------------------------------------------
334 
ScaleX(double fHorzScale)335 void ImplRegionBand::ScaleX( double fHorzScale )
336 {
337 	ImplRegionBandSep* pSep = mpFirstSep;
338 	while ( pSep )
339 	{
340 		pSep->mnXLeft	= FRound( pSep->mnXLeft * fHorzScale );
341 		pSep->mnXRight	= FRound( pSep->mnXRight * fHorzScale );
342 		pSep = pSep->mpNextSep;
343 	}
344 }
345 
346 // -----------------------------------------------------------------------
347 //
348 // combine overlapping separations
349 
OptimizeBand()350 bool ImplRegionBand::OptimizeBand()
351 {
352 	ImplRegionBandSep* pPrevSep = 0;
353 	ImplRegionBandSep* pSep = mpFirstSep;
354 	while ( pSep )
355 	{
356 		// remove?
357 		if ( pSep->mbRemoved || (pSep->mnXRight < pSep->mnXLeft) )
358 		{
359 			ImplRegionBandSep* pOldSep = pSep;
360 			if ( pSep == mpFirstSep )
361 				mpFirstSep = pSep->mpNextSep;
362 			else
363 				pPrevSep->mpNextSep = pSep->mpNextSep;
364 			pSep = pSep->mpNextSep;
365 			delete pOldSep;
366 			continue;
367 		}
368 
369 		// overlapping separations? -> combine!
370 		if ( pSep->mpNextSep )
371 		{
372 			if ( (pSep->mnXRight+1) >= pSep->mpNextSep->mnXLeft )
373 			{
374 				if ( pSep->mpNextSep->mnXRight > pSep->mnXRight )
375 					pSep->mnXRight = pSep->mpNextSep->mnXRight;
376 
377 				ImplRegionBandSep* pOldSep = pSep->mpNextSep;
378 				pSep->mpNextSep = pOldSep->mpNextSep;
379 				delete pOldSep;
380 				continue;
381 			}
382 		}
383 
384 		pPrevSep = pSep;
385 		pSep = pSep->mpNextSep;
386 	}
387 
388 	return true;
389 }
390 
391 // -----------------------------------------------------------------------
392 
Union(long nXLeft,long nXRight)393 void ImplRegionBand::Union( long nXLeft, long nXRight )
394 {
395 	DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Union(): nxLeft > nXRight" );
396 
397 	// band empty? -> add element
398 	if ( !mpFirstSep )
399 	{
400 		mpFirstSep				= new ImplRegionBandSep;
401 		mpFirstSep->mnXLeft 	= nXLeft;
402 		mpFirstSep->mnXRight	= nXRight;
403 		mpFirstSep->mbRemoved	= false;
404 		mpFirstSep->mpNextSep	= NULL;
405 		return;
406 	}
407 
408 	// process real union
409 	ImplRegionBandSep* pNewSep;
410 	ImplRegionBandSep* pPrevSep = 0;
411 	ImplRegionBandSep* pSep = mpFirstSep;
412 	while ( pSep )
413 	{
414 		// new separation completely inside? nothing to do!
415 		if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
416 			return;
417 
418 		// new separation completely left? -> new separation!
419 		if ( nXRight < pSep->mnXLeft )
420 		{
421 			pNewSep 			= new ImplRegionBandSep;
422 			pNewSep->mnXLeft	= nXLeft;
423 			pNewSep->mnXRight	= nXRight;
424 			pNewSep->mbRemoved	= false;
425 
426 			pNewSep->mpNextSep = pSep;
427 			if ( pSep == mpFirstSep )
428 				mpFirstSep = pNewSep;
429 			else
430 				pPrevSep->mpNextSep = pNewSep;
431 			break;
432 		}
433 
434 		// new separation overlapping from left? -> extend boundary
435 		if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
436 			pSep->mnXLeft = nXLeft;
437 
438 		// new separation overlapping from right? -> extend boundary
439 		if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
440 		{
441 			pSep->mnXRight = nXRight;
442 			break;
443 		}
444 
445 		// not inserted, but last element? -> add to the end of the list
446 		if ( !pSep->mpNextSep && (nXLeft > pSep->mnXRight) )
447 		{
448 			pNewSep 			= new ImplRegionBandSep;
449 			pNewSep->mnXLeft	= nXLeft;
450 			pNewSep->mnXRight	= nXRight;
451 			pNewSep->mbRemoved	= false;
452 
453 			pSep->mpNextSep 	= pNewSep;
454 			pNewSep->mpNextSep	= NULL;
455 			break;
456 		}
457 
458 		pPrevSep = pSep;
459 		pSep = pSep->mpNextSep;
460 	}
461 
462 	OptimizeBand();
463 }
464 
465 // -----------------------------------------------------------------------
466 
Intersect(long nXLeft,long nXRight)467 void ImplRegionBand::Intersect( long nXLeft, long nXRight )
468 {
469 	DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Intersect(): nxLeft > nXRight" );
470 
471 	// band has been touched
472 	mbTouched = true;
473 
474 	// band empty? -> nothing to do
475 	if ( !mpFirstSep )
476 		return;
477 
478 	// process real intersection
479 	ImplRegionBandSep* pSep = mpFirstSep;
480 	while ( pSep )
481 	{
482 		// new separation completely outside? -> remove separation
483 		if ( (nXRight < pSep->mnXLeft) || (nXLeft > pSep->mnXRight) )
484 			// will be removed from the optimizer
485 			pSep->mbRemoved = true;
486 
487 		// new separation overlapping from left? -> reduce right boundary
488 		if ( (nXLeft <= pSep->mnXLeft) &&
489 			 (nXRight <= pSep->mnXRight) &&
490 			 (nXRight >= pSep->mnXLeft) )
491 			pSep->mnXRight = nXRight;
492 
493 		// new separation overlapping from right? -> reduce right boundary
494 		if ( (nXLeft >= pSep->mnXLeft) &&
495 			 (nXLeft <= pSep->mnXRight) &&
496 			 (nXRight >= pSep->mnXRight) )
497 			pSep->mnXLeft = nXLeft;
498 
499 		// new separation within the actual one? -> reduce both boundaries
500 		if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
501 		{
502 			pSep->mnXRight = nXRight;
503 			pSep->mnXLeft = nXLeft;
504 		}
505 
506 		pSep = pSep->mpNextSep;
507 	}
508 
509 	OptimizeBand();
510 }
511 
512 // -----------------------------------------------------------------------
513 
Exclude(long nXLeft,long nXRight)514 void ImplRegionBand::Exclude( long nXLeft, long nXRight )
515 {
516 	DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Exclude(): nxLeft > nXRight" );
517 
518 	// band has been touched
519 	mbTouched = true;
520 
521 	// band empty? -> nothing to do
522 	if ( !mpFirstSep )
523 		return;
524 
525 	// process real exclusion
526 	ImplRegionBandSep* pNewSep;
527 	ImplRegionBandSep* pPrevSep = 0;
528 	ImplRegionBandSep* pSep = mpFirstSep;
529 	while ( pSep  )
530 	{
531 		bool bSepProcessed = false;
532 
533 		// new separation completely overlapping? -> remove separation
534 		if ( (nXLeft <= pSep->mnXLeft) && (nXRight >= pSep->mnXRight) )
535 		{
536 			// will be removed from the optimizer
537 			pSep->mbRemoved = true;
538 			bSepProcessed = true;
539 		}
540 
541 		// new separation overlapping from left? -> reduce boundary
542 		if ( !bSepProcessed )
543 		{
544 			if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
545 			{
546 				pSep->mnXLeft = nXRight+1;
547 				bSepProcessed = true;
548 			}
549 		}
550 
551 		// new separation overlapping from right? -> reduce boundary
552 		if ( !bSepProcessed )
553 		{
554 			if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
555 			{
556 				pSep->mnXRight = nXLeft-1;
557 				bSepProcessed = true;
558 			}
559 		}
560 
561 		// new separation within the actual one? -> reduce boundary
562 		// and add new entry for reminder
563 		if ( !bSepProcessed )
564 		{
565 			if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
566 			{
567 				pNewSep 			= new ImplRegionBandSep;
568 				pNewSep->mnXLeft	= pSep->mnXLeft;
569 				pNewSep->mnXRight	= nXLeft-1;
570 				pNewSep->mbRemoved	= false;
571 
572 				pSep->mnXLeft = nXRight+1;
573 
574 				// connections from the new separation
575 				pNewSep->mpNextSep = pSep;
576 
577 				// connections to the new separation
578 				if ( pSep == mpFirstSep )
579 					mpFirstSep = pNewSep;
580 				else
581 					pPrevSep->mpNextSep = pNewSep;
582 			}
583 		}
584 
585 		pPrevSep = pSep;
586 		pSep = pSep->mpNextSep;
587 	}
588 
589 	OptimizeBand();
590 }
591 
592 // -----------------------------------------------------------------------
593 
XOr(long nXLeft,long nXRight)594 void ImplRegionBand::XOr( long nXLeft, long nXRight )
595 {
596 	DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::XOr(): nxLeft > nXRight" );
597 
598     // #i46602# Reworked rectangle Xor
599     //
600     // In general, we can distinguish 11 cases of intersection
601     // (details below). The old implementation explicitly handled 7
602     // cases (numbered in the order of appearance, use CVS to get your
603     // hands on the old version), therefore, I've sticked to that
604     // order, and added four more cases. The code below references
605     // those numbers via #1, #2, etc.
606     //
607     // Num Mnem        newX:oldX newY:oldY  Description                                             Result			Can quit?
608     //
609     // #1  Empty band      -         -      The band is empty, thus, simply add new bandSep         just add		Yes
610     //
611     // #2  apart           -         -      The rectangles are disjunct, add new one as is          just add		Yes
612     //
613     // #3  atop            ==        ==     The rectangles are _exactly_ the same, remove existing  just remove		Yes
614     //
615     // #4  around          <         >      The new rectangle extends the old to both sides         intersect		No
616     //
617     // #5  left            <         <      The new rectangle is left of the old (but intersects)   intersect		Yes
618     //
619     // #5b left-atop       <         ==     The new is left of the old, and coincides on the right  intersect		Yes
620     //
621     // #6  right           >         >      The new is right of the old (but intersects)			intersect		No
622     //
623     // #6b right-atop      ==        >      The new is right of the old, and coincides on the left	intersect		No
624     //
625     // #7 inside           >         <      The new is fully inside the old							intersect		Yes
626     //
627     // #8 inside-right     >         ==     The new is fully inside the old, coincides on the right	intersect		Yes
628     //
629     // #9 inside-left      ==        <      The new is fully inside the old, coincides on the left	intersect		Yes
630     //
631     //
632     // Then, to correctly perform XOr, the segment that's switched off
633     // (i.e. the overlapping part of the old and the new segment) must
634     // be extended by one pixel value at each border:
635     //           1   1
636     // 0   4     0   4
637     // 111100000001111
638     //
639     // Clearly, the leading band sep now goes from 0 to 3, and the
640     // trailing band sep from 11 to 14. This mimicks the xor look of a
641     // bitmap operation.
642     //
643 
644 	// band empty? -> add element
645 	if ( !mpFirstSep )
646 	{
647 		mpFirstSep				= new ImplRegionBandSep;
648 		mpFirstSep->mnXLeft 	= nXLeft;
649 		mpFirstSep->mnXRight	= nXRight;
650 		mpFirstSep->mbRemoved	= false;
651 		mpFirstSep->mpNextSep	= NULL;
652 		return;
653 	}
654 
655 	// process real xor
656 	ImplRegionBandSep* pNewSep;
657 	ImplRegionBandSep* pPrevSep = 0;
658 	ImplRegionBandSep* pSep = mpFirstSep;
659 
660     while ( pSep  )
661     {
662         long nOldLeft( pSep->mnXLeft );
663         long nOldRight( pSep->mnXRight );
664 
665         // did the current segment actually touch the new rect? If
666         // not, skip all comparisons, go on, loop and try to find
667         // intersecting bandSep
668         if( nXLeft <= nOldRight )
669         {
670             if( nXRight < nOldLeft )
671             {
672                 // #2
673 
674                 // add _before_ current bandSep
675                 pNewSep             = new ImplRegionBandSep;
676                 pNewSep->mnXLeft    = nXLeft;
677                 pNewSep->mnXRight   = nXRight;
678                 pNewSep->mpNextSep  = pSep;
679                 pNewSep->mbRemoved  = false;
680 
681                 // connections from the new separation
682                 pNewSep->mpNextSep = pSep;
683 
684                 // connections to the new separation
685                 if ( pSep == mpFirstSep )
686                     mpFirstSep = pNewSep;
687                 else
688                     pPrevSep->mpNextSep = pNewSep;
689                 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
690                 break;
691             }
692             else if( nXLeft == nOldLeft && nXRight == nOldRight )
693             {
694                 // #3
695                 pSep->mbRemoved = true;
696                 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
697                 break;
698             }
699             else if( nXLeft != nOldLeft && nXRight == nOldRight )
700             {
701                 // # 5b, 8
702                 if( nXLeft < nOldLeft )
703                 {
704                     nXRight = nOldLeft; // 5b
705                 }
706                 else
707                 {
708                     nXRight = nXLeft; // 8
709                     nXLeft = nOldLeft;
710                 }
711 
712                 pSep->mnXLeft = nXLeft;
713                 pSep->mnXRight = nXRight-1;
714 
715                 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
716                 break;
717             }
718             else if( nXLeft == nOldLeft && nXRight != nOldRight )
719             {
720                 // # 6b, 9
721 
722                 if( nXRight > nOldRight )
723                 {
724                     nXLeft = nOldRight+1; // 6b
725 
726                     // cannot break here, simply mark segment as removed,
727                     // and go on with adapted nXLeft/nXRight
728                     pSep->mbRemoved = true;
729                 }
730                 else
731                 {
732                     pSep->mnXLeft = nXRight+1; // 9
733 
734                     pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
735                     break;
736                 }
737             }
738             else // if( nXLeft != nOldLeft && nXRight != nOldRight ) follows automatically
739             {
740                 // #4,5,6,7
741                 DBG_ASSERT( nXLeft != nOldLeft && nXRight != nOldRight,
742                             "ImplRegionBand::XOr(): Case 4,5,6,7 expected all coordinates to be not equal!" );
743 
744                 // The plain-jane check would look like this:
745                 //
746                 // if( nXLeft < nOldLeft )
747                 // {
748                 //     // #4,5
749                 //     if( nXRight > nOldRight )
750                 //     {
751                 //        // #4
752                 //     }
753                 //     else
754                 //     {
755                 //         // #5 done!
756                 //     }
757                 // }
758                 // else
759                 // {
760                 //     // #6,7
761                 //     if( nXRight > nOldRight )
762                 //     {
763                 //         // #6
764                 //     }
765                 //     else
766                 //     {
767                 //         // #7 done!
768                 //     }
769                 // }
770                 //
771                 // but since we generally don't have to care whether
772                 // it's 4 or 6 (only that we must not stop processing
773                 // here), condensed that in such a way that only the
774                 // coordinates get shuffled into correct ordering.
775 
776                 if( nXLeft < nOldLeft )
777                     ::std::swap( nOldLeft, nXLeft );
778 
779                 bool bDone( false );
780 
781                 if( nXRight < nOldRight )
782                 {
783                     ::std::swap( nOldRight, nXRight );
784                     bDone = true;
785                 }
786 
787                 // now, nOldLeft<nXLeft<=nOldRight<nXRight always
788                 // holds. Note that we need the nXLeft<=nOldRight here, as
789                 // the intersection part might be only one pixel (original
790                 // nXLeft==nXRight)
791                 DBG_ASSERT( nOldLeft<nXLeft && nXLeft<=nOldRight && nOldRight<nXRight,
792                             "ImplRegionBand::XOr(): Case 4,5,6,7 expected coordinates to be ordered now!" );
793 
794                 pSep->mnXLeft = nOldLeft;
795                 pSep->mnXRight = nXLeft-1;
796 
797                 nXLeft = nOldRight+1;
798                 // nxRight is already setup correctly
799 
800                 if( bDone )
801                 {
802                     // add behind current bandSep
803                     pNewSep = new ImplRegionBandSep;
804 
805                     pNewSep->mnXLeft    = nXLeft;
806                     pNewSep->mnXRight   = nXRight;
807                     pNewSep->mpNextSep  = pSep->mpNextSep;
808                     pNewSep->mbRemoved  = false;
809 
810                     // connections from the new separation
811                     pSep->mpNextSep = pNewSep;
812 
813                     pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
814                     break;
815                 }
816             }
817         }
818 
819         pPrevSep = pSep;
820         pSep = pSep->mpNextSep;
821     }
822 
823     // new separation completely right of existing bandSeps ?
824     if( pPrevSep && nXLeft >= pPrevSep->mnXRight )
825     {
826         pNewSep             = new ImplRegionBandSep;
827         pNewSep->mnXLeft    = nXLeft;
828         pNewSep->mnXRight   = nXRight;
829         pNewSep->mpNextSep  = NULL;
830         pNewSep->mbRemoved  = false;
831 
832         // connections from the new separation
833         pPrevSep->mpNextSep = pNewSep;
834     }
835 
836 	OptimizeBand();
837 }
838 
839 // -----------------------------------------------------------------------
840 
IsInside(long nX)841 bool ImplRegionBand::IsInside( long nX )
842 {
843 	ImplRegionBandSep* pSep = mpFirstSep;
844 	while ( pSep )
845 	{
846 		if ( (pSep->mnXLeft <= nX) && (pSep->mnXRight >= nX) )
847 			return true;
848 
849 		pSep = pSep->mpNextSep;
850 	}
851 
852 	return false;
853 }
854 
855 // -----------------------------------------------------------------------
856 
IsOver(long nLeft,long nRight)857 bool ImplRegionBand::IsOver( long nLeft, long nRight )
858 {
859 	ImplRegionBandSep* pSep = mpFirstSep;
860 	while ( pSep )
861 	{
862 		if ( (pSep->mnXLeft < nRight) && (pSep->mnXRight > nLeft) )
863 			return true;
864 
865 		pSep = pSep->mpNextSep;
866 	}
867 
868 	return false;
869 }
870 
871 // -----------------------------------------------------------------------
872 
IsInside(long nLeft,long nRight)873 bool ImplRegionBand::IsInside( long nLeft, long nRight )
874 {
875 	ImplRegionBandSep* pSep = mpFirstSep;
876 	while ( pSep )
877 	{
878 		if ( (pSep->mnXLeft >= nLeft) && (nRight <= pSep->mnXRight) )
879 			return true;
880 
881 		pSep = pSep->mpNextSep;
882 	}
883 
884 	return false;
885 }
886 
887 // -----------------------------------------------------------------------
888 
GetXLeftBoundary() const889 long ImplRegionBand::GetXLeftBoundary() const
890 {
891 	DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XLeftBoundary -> no separation in band!" );
892 
893 	return mpFirstSep->mnXLeft;
894 }
895 
896 // -----------------------------------------------------------------------
897 
GetXRightBoundary() const898 long ImplRegionBand::GetXRightBoundary() const
899 {
900 	DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XRightBoundary -> no separation in band!" );
901 
902 	// search last separation
903 	ImplRegionBandSep* pSep = mpFirstSep;
904 	while ( pSep->mpNextSep )
905 		pSep = pSep->mpNextSep;
906 	return pSep->mnXRight;
907 }
908 
909 // -----------------------------------------------------------------------
910 
operator ==(const ImplRegionBand & rRegionBand) const911 bool ImplRegionBand::operator==( const ImplRegionBand& rRegionBand ) const
912 {
913 	ImplRegionBandSep*	 pOwnRectBandSep = mpFirstSep;
914 	ImplRegionBandSep*	 pSecondRectBandSep = rRegionBand.mpFirstSep;
915 	while ( pOwnRectBandSep && pSecondRectBandSep )
916 	{
917 		// get boundaries of current rectangle
918 		long nOwnXLeft = pOwnRectBandSep->mnXLeft;
919 		long nSecondXLeft = pSecondRectBandSep->mnXLeft;
920 		if ( nOwnXLeft != nSecondXLeft )
921 			return false;
922 
923 		long nOwnXRight = pOwnRectBandSep->mnXRight;
924 		long nSecondXRight = pSecondRectBandSep->mnXRight;
925 		if ( nOwnXRight != nSecondXRight )
926 			return false;
927 
928 		// get next separation from current band
929 		pOwnRectBandSep = pOwnRectBandSep->mpNextSep;
930 
931 		// get next separation from current band
932 		pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
933 	}
934 
935 	// different number of separations?
936 	if ( pOwnRectBandSep || pSecondRectBandSep )
937 		return false;
938 
939 	return true;
940 }
941 
942 // -----------------------------------------------------------------------
943 
SplitBand(const sal_Int32 nY)944 ImplRegionBand* ImplRegionBand::SplitBand (const sal_Int32 nY)
945 {
946     OSL_ASSERT(nY>mnYTop);
947     OSL_ASSERT(nY<=mnYBottom);
948 
949     // Create a copy of the given band (we tell the constructor to copy the points together
950     // with the seps.)
951     ImplRegionBand* pLowerBand = new ImplRegionBand(*this, false);
952 
953     // Adapt vertical coordinates.
954     mnYBottom = nY-1;
955     pLowerBand->mnYTop = nY;
956 
957     // Insert new band into list of bands.
958     pLowerBand->mpNextBand = mpNextBand;
959     mpNextBand = pLowerBand;
960     pLowerBand->mpPrevBand = this;
961     if (pLowerBand->mpNextBand != NULL)
962         pLowerBand->mpNextBand->mpPrevBand = pLowerBand;
963 
964     return pLowerBand;
965 }
966