1/* $Xorg: Region.c,v 1.6 2001/02/09 02:03:35 xorgcvs Exp $ */
2/************************************************************************
3
4Copyright 1987, 1988, 1998  The Open Group
5
6Permission to use, copy, modify, distribute, and sell this software and its
7documentation for any purpose is hereby granted without fee, provided that
8the above copyright notice appear in all copies and that both that
9copyright notice and this permission notice appear in supporting
10documentation.
11
12The above copyright notice and this permission notice shall be included in
13all copies or substantial portions of the Software.
14
15THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
18OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21
22Except as contained in this notice, the name of The Open Group shall not be
23used in advertising or otherwise to promote the sale, use or other dealings
24in this Software without prior written authorization from The Open Group.
25
26
27Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
28
29                        All Rights Reserved
30
31Permission to use, copy, modify, and distribute this software and its
32documentation for any purpose and without fee is hereby granted,
33provided that the above copyright notice appear in all copies and that
34both that copyright notice and this permission notice appear in
35supporting documentation, and that the name of Digital not be
36used in advertising or publicity pertaining to distribution of the
37software without specific, written prior permission.
38
39DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
45SOFTWARE.
46
47************************************************************************/
48/* $XFree86: xc/lib/X11/Region.c,v 1.9 2002/06/04 22:19:57 dawes Exp $ */
49/*
50 * The functions in this file implement the BRegion* abstraction, similar to one
51 * used in the X11 sample server. A BRegion* is simply an area, as the name
52 * implies, and is implemented as a "y-x-banded" array of rectangles. To
53 * explain: Each BRegion* is made up of a certain number of rectangles sorted
54 * by y coordinate first, and then by x coordinate.
55 *
56 * Furthermore, the rectangles are banded such that every rectangle with a
57 * given upper-left y coordinate (top) will have the same lower-right y
58 * coordinate (bottom) and vice versa. If a rectangle has scanlines in a band, it
59 * will span the entire vertical distance of the band. This means that some
60 * areas that could be merged into a taller rectangle will be represented as
61 * several shorter rectangles to account for shorter rectangles to its left
62 * or right but within its "vertical scope".
63 *
64 * An added constraint on the rectangles is that they must cover as much
65 * horizontal area as possible. E.g. no two rectangles in a band are allowed
66 * to touch.
67 *
68 * Whenever possible, bands will be merged together to cover a greater vertical
69 * distance (and thus reduce the number of rectangles). Two bands can be merged
70 * only if the bottom of one touches the top of the other and they have
71 * rectangles in the same places (of the same width, of course). This maintains
72 * the y-x-banding that's so nice to have...
73 */
74
75#include "RegionSupport.h"
76
77#include <stdlib.h>
78#include <new>
79
80using std::nothrow;
81
82#include <SupportDefs.h>
83
84
85#ifdef DEBUG
86#include <stdio.h>
87#define assert(expr) {if (!(expr)) fprintf(stderr,\
88"Assertion failed file %s, line %d: " #expr "\n", __FILE__, __LINE__); }
89#else
90#define assert(expr)
91#endif
92
93
94/*  1 if two clipping_rects overlap.
95 *  0 if two clipping_rects do not overlap.
96 *  Remember, right and bottom are not in the region
97 */
98#define EXTENTCHECK(r1, r2) \
99	((r1)->right > (r2)->left && \
100	 (r1)->left < (r2)->right && \
101	 (r1)->bottom > (r2)->top && \
102	 (r1)->top < (r2)->bottom)
103
104/*
105 *  update region fBounds
106 */
107#define EXTENTS(r,idRect){\
108            if ((r)->left < (idRect)->fBounds.left)\
109              (idRect)->fBounds.left = (r)->left;\
110            if ((r)->top < (idRect)->fBounds.top)\
111              (idRect)->fBounds.top = (r)->top;\
112            if ((r)->right > (idRect)->fBounds.right)\
113              (idRect)->fBounds.right = (r)->right;\
114            if ((r)->bottom > (idRect)->fBounds.bottom)\
115              (idRect)->fBounds.bottom = (r)->bottom;\
116        }
117
118/*
119 *   Check to see if there is enough memory in the present region.
120 */
121#define MEMCHECK(reg, rect, firstrect){\
122        if ((reg)->fCount >= ((reg)->fDataSize - 1)){\
123          (firstrect) = (clipping_rect *) realloc \
124          ((char *)(firstrect), (unsigned) (2 * (sizeof(clipping_rect)) * ((reg)->fDataSize)));\
125          if ((firstrect) == 0)\
126            return(0);\
127          (reg)->fDataSize *= 2;\
128          (rect) = &(firstrect)[(reg)->fCount];\
129         }\
130       }
131
132/*  this routine checks to see if the previous rectangle is the same
133 *  or subsumes the new rectangle to add.
134 */
135
136#define CHECK_PREVIOUS(Reg, R, Rx1, Ry1, Rx2, Ry2)\
137               (!(((Reg)->fCount > 0)&&\
138                  ((R-1)->top == (Ry1)) &&\
139                  ((R-1)->bottom == (Ry2)) &&\
140                  ((R-1)->left <= (Rx1)) &&\
141                  ((R-1)->right >= (Rx2))))
142
143/*  add a rectangle to the given BRegion */
144#define ADDRECT(reg, r, rx1, ry1, rx2, ry2){\
145    if (((rx1) < (rx2)) && ((ry1) < (ry2)) &&\
146        CHECK_PREVIOUS((reg), (r), (rx1), (ry1), (rx2), (ry2))){\
147              (r)->left = (rx1);\
148              (r)->top = (ry1);\
149              (r)->right = (rx2);\
150              (r)->bottom = (ry2);\
151              EXTENTS((r), (reg));\
152              (reg)->fCount++;\
153              (r)++;\
154            }\
155        }
156
157
158
159/*  add a rectangle to the given BRegion */
160#define ADDRECTNOX(reg, r, rx1, ry1, rx2, ry2){\
161            if ((rx1 < rx2) && (ry1 < ry2) &&\
162                CHECK_PREVIOUS((reg), (r), (rx1), (ry1), (rx2), (ry2))){\
163              (r)->left = (rx1);\
164              (r)->top = (ry1);\
165              (r)->right = (rx2);\
166              (r)->bottom = (ry2);\
167              (reg)->fCount++;\
168              (r)++;\
169            }\
170        }
171
172#define EMPTY_REGION(pReg) pReg->MakeEmpty()
173
174#define REGION_NOT_EMPTY(pReg) pReg->fCount
175
176#define INBOX(r, x, y) \
177      ( ( ((r).right >  x)) && \
178        ( ((r).left <= x)) && \
179        ( ((r).bottom >  y)) && \
180        ( ((r).top <= y)) )
181
182
183
184/*	Create a new empty region	*/
185BRegion*
186BRegion::Support::CreateRegion(void)
187{
188    return new (nothrow) BRegion();
189}
190
191void
192BRegion::Support::DestroyRegion(BRegion* r)
193{
194	delete r;
195}
196
197
198/*-
199 *-----------------------------------------------------------------------
200 * miSetExtents --
201 *	Reset the fBounds of a region to what they should be. Called by
202 *	miSubtract and miIntersect b/c they can't figure it out along the
203 *	way or do so easily, as miUnion can.
204 *
205 * Results:
206 *	None.
207 *
208 * Side Effects:
209 *	The region's 'fBounds' structure is overwritten.
210 *
211 *-----------------------------------------------------------------------
212 */
213void
214BRegion::Support::miSetExtents(BRegion* pReg)
215{
216    register clipping_rect*	pBox;
217	clipping_rect* pBoxEnd;
218	clipping_rect* pExtents;
219
220    if (pReg->fCount == 0)
221    {
222	pReg->fBounds.left = 0;
223	pReg->fBounds.top = 0;
224	pReg->fBounds.right = 0;
225	pReg->fBounds.bottom = 0;
226	return;
227    }
228
229    pExtents = &pReg->fBounds;
230    pBox = pReg->fData;
231    pBoxEnd = &pBox[pReg->fCount - 1];
232
233    /*
234     * Since pBox is the first rectangle in the region, it must have the
235     * smallest top and since pBoxEnd is the last rectangle in the region,
236     * it must have the largest bottom, because of banding. Initialize left and
237     * right from  pBox and pBoxEnd, resp., as good things to initialize them
238     * to...
239     */
240    pExtents->left = pBox->left;
241    pExtents->top = pBox->top;
242    pExtents->right = pBoxEnd->right;
243    pExtents->bottom = pBoxEnd->bottom;
244
245    assert(pExtents->top < pExtents->bottom);
246    while (pBox <= pBoxEnd)
247    {
248	if (pBox->left < pExtents->left)
249	{
250	    pExtents->left = pBox->left;
251	}
252	if (pBox->right > pExtents->right)
253	{
254	    pExtents->right = pBox->right;
255	}
256	pBox++;
257    }
258    assert(pExtents->left < pExtents->right);
259}
260
261
262/* TranslateRegion(pRegion, x, y)
263   translates in place
264   added by raymond
265*/
266void
267BRegion::Support::XOffsetRegion(
268    register BRegion* pRegion,
269    register int x,
270    register int y)
271{
272    register int nbox;
273    register clipping_rect *pbox;
274
275    pbox = pRegion->fData;
276    nbox = pRegion->fCount;
277
278    while(nbox--)
279    {
280	pbox->left += x;
281	pbox->right += x;
282	pbox->top += y;
283	pbox->bottom += y;
284	pbox++;
285    }
286    pRegion->fBounds.left += x;
287    pRegion->fBounds.right += x;
288    pRegion->fBounds.top += y;
289    pRegion->fBounds.bottom += y;
290}
291
292/*
293   Utility procedure Compress:
294   Replace r by the region r', where
295     p in r' iff (Quantifer m <= dx) (p + m in r), and
296     Quantifier is Exists if grow is true, For all if grow is false, and
297     (x,y) + m = (x+m,y) if xdir is true; (x,y+m) if xdir is false.
298
299   Thus, if xdir is true and grow is false, r is replaced by the region
300   of all points p such that p and the next dx points on the same
301   horizontal scan line are all in r.  We do this using by noting
302   that p is the head of a run of length 2^i + k iff p is the head
303   of a run of length 2^i and p+2^i is the head of a run of length
304   k. Thus, the loop invariant: s contains the region corresponding
305   to the runs of length shift.  r contains the region corresponding
306   to the runs of length 1 + dxo & (shift-1), where dxo is the original
307   value of dx.  dx = dxo & ~(shift-1).  As parameters, s and t are
308   scratch regions, so that we don't have to allocate them on every
309   call.
310*/
311
312#if 0
313#define ZOpRegion(a,b,c) if (grow) BRegion::Support::XUnionRegion(a,b,c); \
314			 else BRegion::Support::XIntersectRegion(a,b,c)
315#define ZShiftRegion(a,b) if (xdir) BRegion::Support::XOffsetRegion(a,b,0); \
316			  else BRegion::Support::XOffsetRegion(a,0,b)
317#define ZCopyRegion(a,b) BRegion::Support::XUnionRegion(a,a,b)
318
319static void
320Compress(
321    BRegion* r, BRegion* s, BRegion* t,
322    register unsigned dx,
323    register int xdir, register int grow)
324{
325    register unsigned shift = 1;
326
327    ZCopyRegion(r, s);
328    while (dx) {
329        if (dx & shift) {
330            ZShiftRegion(r, -(int)shift);
331            ZOpRegion(r, s, r);
332            dx -= shift;
333            if (!dx) break;
334        }
335        ZCopyRegion(s, t);
336        ZShiftRegion(s, -(int)shift);
337        ZOpRegion(s, t, s);
338        shift <<= 1;
339    }
340}
341
342#undef ZOpRegion
343#undef ZShiftRegion
344#undef ZCopyRegion
345
346int
347XShrinkRegion(
348    BRegion* r,
349    int dx, int dy)
350{
351    BRegion* s;
352    BRegion* t;
353    int grow;
354
355    if (!dx && !dy) return 0;
356    if ((! (s = CreateRegion()))  || (! (t = CreateRegion()))) return 0;
357    if ((grow = (dx < 0))) dx = -dx;
358    if (dx) Compress(r, s, t, (unsigned) 2*dx, true, grow);
359    if ((grow = (dy < 0))) dy = -dy;
360    if (dy) Compress(r, s, t, (unsigned) 2*dy, false, grow);
361    XOffsetRegion(r, dx, dy);
362    DestroyRegion(s);
363    DestroyRegion(t);
364    return 0;
365}
366
367#ifdef notdef
368/***********************************************************
369 *     Bop down the array of fData until we have passed
370 *     scanline y.  fCount is the fDataSize of the array.
371 ***********************************************************/
372
373static clipping_rect*
374IndexRects(
375    register clipping_rect *rect,
376    register int rectCount,
377    register int y)
378{
379     while ((rectCount--) && (rect->bottom <= y))
380        rect++;
381     return(rect);
382}
383#endif
384#endif // 0
385
386/*======================================================================
387 *	    BRegion* Intersection
388 *====================================================================*/
389/*-
390 *-----------------------------------------------------------------------
391 * miIntersectO --
392 *	Handle an overlapping band for miIntersect.
393 *
394 * Results:
395 *	None.
396 *
397 * Side Effects:
398 *	Rectangles may be added to the region.
399 *
400 *-----------------------------------------------------------------------
401 */
402int
403BRegion::Support::miIntersectO (
404    register BRegion*	pReg,
405    register clipping_rect*	r1,
406    clipping_rect*  	  	r1End,
407    register clipping_rect*	r2,
408    clipping_rect*  	  	r2End,
409    int    	  	top,
410    int    	  	bottom)
411{
412    register int  	left;
413    register int  	right;
414    register clipping_rect*	pNextRect;
415
416    pNextRect = &pReg->fData[pReg->fCount];
417
418    while ((r1 != r1End) && (r2 != r2End))
419    {
420	left = max_c(r1->left,r2->left);
421	right = min_c(r1->right,r2->right);
422
423	/*
424	 * If there's any overlap between the two rectangles, add that
425	 * overlap to the new region.
426	 * There's no need to check for subsumption because the only way
427	 * such a need could arise is if some region has two rectangles
428	 * right next to each other. Since that should never happen...
429	 */
430	if (left < right)
431	{
432	    assert(top<bottom);
433
434	    MEMCHECK(pReg, pNextRect, pReg->fData);
435	    pNextRect->left = left;
436	    pNextRect->top = top;
437	    pNextRect->right = right;
438	    pNextRect->bottom = bottom;
439	    pReg->fCount += 1;
440	    pNextRect++;
441	    assert(pReg->fCount <= pReg->fDataSize);
442	}
443
444	/*
445	 * Need to advance the pointers. Shift the one that extends
446	 * to the right the least, since the other still has a chance to
447	 * overlap with that region's next rectangle, if you see what I mean.
448	 */
449	if (r1->right < r2->right)
450	{
451	    r1++;
452	}
453	else if (r2->right < r1->right)
454	{
455	    r2++;
456	}
457	else
458	{
459	    r1++;
460	    r2++;
461	}
462    }
463    return 0;	/* lint */
464}
465
466int
467BRegion::Support::XIntersectRegion(
468    const BRegion* 	  	reg1,
469    const BRegion*	  	reg2,          /* source regions     */
470    register BRegion* 	newReg)               /* destination BRegion* */
471{
472   /* check for trivial reject */
473    if ( (!(reg1->fCount)) || (!(reg2->fCount))  ||
474	(!EXTENTCHECK(&reg1->fBounds, &reg2->fBounds)))
475        newReg->fCount = 0;
476    else
477	miRegionOp (newReg, reg1, reg2,
478    		miIntersectO, NULL, NULL);
479
480    /*
481     * Can't alter newReg's fBounds before we call miRegionOp because
482     * it might be one of the source regions and miRegionOp depends
483     * on the fBounds of those regions being the same. Besides, this
484     * way there's no checking against rectangles that will be nuked
485     * due to coalescing, so we have to examine fewer rectangles.
486     */
487    miSetExtents(newReg);
488    return 1;
489}
490
491void
492BRegion::Support::miRegionCopy(
493    register BRegion* dstrgn,
494    register const BRegion* rgn)
495
496{
497	*dstrgn = *rgn;
498}
499
500#if 0
501#ifdef notdef
502
503/*
504 *  combinRegs(newReg, reg1, reg2)
505 *    if one region is above or below the other.
506*/
507
508static void
509combineRegs(
510    register BRegion* newReg,
511    BRegion* reg1,
512    BRegion* reg2)
513{
514    register BRegion* tempReg;
515    register clipping_rect *rects_;
516    register clipping_rect *rects1;
517    register clipping_rect *rects2;
518    register int total;
519
520    rects1 = reg1->fData;
521    rects2 = reg2->fData;
522
523    total = reg1->fCount + reg2->fCount;
524    if (! (tempReg = CreateRegion()))
525	return;
526    tempReg->fDataSize = total;
527    /*  region 1 is below region 2  */
528    if (reg1->fBounds.top > reg2->fBounds.top)
529    {
530        miRegionCopy(tempReg, reg2);
531        rects_ = &tempReg->fData[tempReg->fCount];
532        total -= tempReg->fCount;
533        while (total--)
534            *rects_++ = *rects1++;
535    }
536    else
537    {
538        miRegionCopy(tempReg, reg1);
539        rects_ = &tempReg->fData[tempReg->fCount];
540        total -= tempReg->fCount;
541        while (total--)
542            *rects_++ = *rects2++;
543    }
544    tempReg->fBounds = reg1->fBounds;
545    tempReg->fCount = reg1->fCount + reg2->fCount;
546    EXTENTS(&reg2->fBounds, tempReg);
547    miRegionCopy(newReg, tempReg);
548
549    DestroyRegion(tempReg);
550}
551
552/*
553 *  QuickCheck checks to see if it does not have to go through all the
554 *  the ugly code for the region call.  It returns 1 if it did all
555 *  the work for Union, otherwise 0 - still work to be done.
556*/
557
558static int
559QuickCheck(BRegion* newReg, BRegion* reg1, BRegion* reg2)
560{
561
562    /*  if unioning with itself or no fData to union with  */
563    if ( (reg1 == reg2) || (!(reg1->fCount)) )
564    {
565        miRegionCopy(newReg, reg2);
566        return true;
567    }
568
569    /*   if nothing to union   */
570    if (!(reg2->fCount))
571    {
572        miRegionCopy(newReg, reg1);
573        return true;
574    }
575
576    /*   could put an extent check to see if add above or below */
577
578    if ((reg1->fBounds.top >= reg2->fBounds.bottom) ||
579        (reg2->fBounds.top >= reg1->fBounds.bottom) )
580    {
581        combineRegs(newReg, reg1, reg2);
582        return true;
583    }
584    return false;
585}
586
587/*   TopRects(fData, reg1, reg2)
588 * N.B. We now assume that reg1 and reg2 intersect.  Therefore we are
589 * NOT checking in the two while loops for stepping off the end of the
590 * region.
591 */
592
593static int
594TopRects(
595    register BRegion* newReg,
596    register clipping_rect *rects_,
597    register BRegion* reg1,
598    register BRegion* reg2,
599    clipping_rect *FirstRect)
600{
601    register clipping_rect *tempRects;
602
603    /*  need to add some fData from region 1 */
604    if (reg1->fBounds.top < reg2->fBounds.top)
605    {
606        tempRects = reg1->fData;
607        while(tempRects->top < reg2->fBounds.top)
608	{
609	    MEMCHECK(newReg, rects_, FirstRect);
610            ADDRECTNOX(newReg,rects_, tempRects->left, tempRects->top,
611		       tempRects->right, min_c(tempRects->bottom, reg2->fBounds.top));
612            tempRects++;
613	}
614    }
615    /*  need to add some fData from region 2 */
616    if (reg2->fBounds.top < reg1->fBounds.top)
617    {
618        tempRects = reg2->fData;
619        while (tempRects->top < reg1->fBounds.top)
620        {
621            MEMCHECK(newReg, rects_, FirstRect);
622            ADDRECTNOX(newReg, rects_, tempRects->left,tempRects->top,
623		       tempRects->right, min_c(tempRects->bottom, reg1->fBounds.top));
624            tempRects++;
625	}
626    }
627    return 1;
628}
629#endif // notdef
630#endif // 0
631
632/*======================================================================
633 *	    Generic BRegion* Operator
634 *====================================================================*/
635
636/*-
637 *-----------------------------------------------------------------------
638 * miCoalesce --
639 *	Attempt to merge the boxes in the current band with those in the
640 *	previous one. Used only by miRegionOp.
641 *
642 * Results:
643 *	The new index for the previous band.
644 *
645 * Side Effects:
646 *	If coalescing takes place:
647 *	    - rectangles in the previous band will have their bottom fields
648 *	      altered.
649 *	    - pReg->fCount will be decreased.
650 *
651 *-----------------------------------------------------------------------
652 */
653int
654BRegion::Support::miCoalesce(
655    register BRegion*	pReg,	    	/* BRegion* to coalesce */
656    int	    	  	prevStart,  	/* Index of start of previous band */
657    int	    	  	curStart)   	/* Index of start of current band */
658{
659    register clipping_rect*	pPrevBox;   	/* Current box in previous band */
660    register clipping_rect*	pCurBox;    	/* Current box in current band */
661    register clipping_rect*	pRegEnd;    	/* End of region */
662    int	    	  	curNumRects;	/* Number of rectangles in current
663					 * band */
664    int	    	  	prevNumRects;	/* Number of rectangles in previous
665					 * band */
666    int	    	  	bandY1;	    	/* Y1 coordinate for current band */
667
668    pRegEnd = &pReg->fData[pReg->fCount];
669
670    pPrevBox = &pReg->fData[prevStart];
671    prevNumRects = curStart - prevStart;
672
673    /*
674     * Figure out how many rectangles are in the current band. Have to do
675     * this because multiple bands could have been added in miRegionOp
676     * at the end when one region has been exhausted.
677     */
678    pCurBox = &pReg->fData[curStart];
679    bandY1 = pCurBox->top;
680    for (curNumRects = 0;
681	 (pCurBox != pRegEnd) && (pCurBox->top == bandY1);
682	 curNumRects++)
683    {
684	pCurBox++;
685    }
686
687    if (pCurBox != pRegEnd)
688    {
689	/*
690	 * If more than one band was added, we have to find the start
691	 * of the last band added so the next coalescing job can start
692	 * at the right place... (given when multiple bands are added,
693	 * this may be pointless -- see above).
694	 */
695	pRegEnd--;
696	while (pRegEnd[-1].top == pRegEnd->top)
697	{
698	    pRegEnd--;
699	}
700	curStart = pRegEnd - pReg->fData;
701	pRegEnd = pReg->fData + pReg->fCount;
702    }
703
704    if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
705	pCurBox -= curNumRects;
706	/*
707	 * The bands may only be coalesced if the bottom of the previous
708	 * matches the top scanline of the current.
709	 */
710	if (pPrevBox->bottom == pCurBox->top)
711	{
712	    /*
713	     * Make sure the bands have boxes in the same places. This
714	     * assumes that boxes have been added in such a way that they
715	     * cover the most area possible. I.e. two boxes in a band must
716	     * have some horizontal space between them.
717	     */
718	    do
719	    {
720		if ((pPrevBox->left != pCurBox->left) ||
721		    (pPrevBox->right != pCurBox->right))
722		{
723		    /*
724		     * The bands don't line up so they can't be coalesced.
725		     */
726		    return (curStart);
727		}
728		pPrevBox++;
729		pCurBox++;
730		prevNumRects -= 1;
731	    } while (prevNumRects != 0);
732
733	    pReg->fCount -= curNumRects;
734	    pCurBox -= curNumRects;
735	    pPrevBox -= curNumRects;
736
737	    /*
738	     * The bands may be merged, so set the bottom y of each box
739	     * in the previous band to that of the corresponding box in
740	     * the current band.
741	     */
742	    do
743	    {
744		pPrevBox->bottom = pCurBox->bottom;
745		pPrevBox++;
746		pCurBox++;
747		curNumRects -= 1;
748	    } while (curNumRects != 0);
749
750	    /*
751	     * If only one band was added to the region, we have to backup
752	     * curStart to the start of the previous band.
753	     *
754	     * If more than one band was added to the region, copy the
755	     * other bands down. The assumption here is that the other bands
756	     * came from the same region as the current one and no further
757	     * coalescing can be done on them since it's all been done
758	     * already... curStart is already in the right place.
759	     */
760	    if (pCurBox == pRegEnd)
761	    {
762		curStart = prevStart;
763	    }
764	    else
765	    {
766		do
767		{
768		    *pPrevBox++ = *pCurBox++;
769		} while (pCurBox != pRegEnd);
770	    }
771
772	}
773    }
774    return (curStart);
775}
776
777/*-
778 *-----------------------------------------------------------------------
779 * miRegionOp --
780 *	Apply an operation to two regions. Called by miUnion, miInverse,
781 *	miSubtract, miIntersect...
782 *
783 * Results:
784 *	None.
785 *
786 * Side Effects:
787 *	The new region is overwritten.
788 *
789 * Notes:
790 *	The idea behind this function is to view the two regions as sets.
791 *	Together they cover a rectangle of area that this function divides
792 *	into horizontal bands where points are covered only by one region
793 *	or by both. For the first case, the nonOverlapFunc is called with
794 *	each the band and the band's upper and lower fBounds. For the
795 *	second, the overlapFunc is called to process the entire band. It
796 *	is responsible for clipping the rectangles in the band, though
797 *	this function provides the boundaries.
798 *	At the end of each band, the new region is coalesced, if possible,
799 *	to reduce the number of rectangles in the region.
800 *
801 *-----------------------------------------------------------------------
802 */
803void
804BRegion::Support::miRegionOp(
805    register BRegion* 	newReg,	    	    	/* Place to store result */
806    const BRegion*	  	reg1,	    	    	/* First region in operation */
807    const BRegion*	  	reg2,	    	    	/* 2d region in operation */
808    int    	  	(*overlapFunc)(
809        register BRegion*     pReg,
810        register clipping_rect*     r1,
811        clipping_rect*              r1End,
812        register clipping_rect*     r2,
813        clipping_rect*              r2End,
814        int               top,
815        int               bottom),                /* Function to call for over-
816						 * lapping bands */
817    int    	  	(*nonOverlap1Func)(
818        register BRegion*     pReg,
819        register clipping_rect*     r,
820        clipping_rect*              rEnd,
821        register int      top,
822        register int      bottom),                /* Function to call for non-
823						 * overlapping bands in region
824						 * 1 */
825    int    	  	(*nonOverlap2Func)(
826        register BRegion*     pReg,
827        register clipping_rect*     r,
828        clipping_rect*              rEnd,
829        register int      top,
830        register int      bottom))                /* Function to call for non-
831						 * overlapping bands in region
832						 * 2 */
833{
834    register clipping_rect*	r1; 	    	    	/* Pointer into first region */
835    register clipping_rect*	r2; 	    	    	/* Pointer into 2d region */
836    clipping_rect*  	  	r1End;	    	    	/* End of 1st region */
837    clipping_rect*  	  	r2End;	    	    	/* End of 2d region */
838    register int  	ybot;	    	    	/* Bottom of intersection */
839    register int  	ytop;	    	    	/* Top of intersection */
840 //   clipping_rect*  	  	oldRects;   	    	/* Old fData for newReg */
841    int	    	  	prevBand;   	    	/* Index of start of
842						 * previous band in newReg */
843    int	    	  	curBand;    	    	/* Index of start of current
844						 * band in newReg */
845    register clipping_rect* 	r1BandEnd;  	    	/* End of current band in r1 */
846    register clipping_rect* 	r2BandEnd;  	    	/* End of current band in r2 */
847    int     	  	top;	    	    	/* Top of non-overlapping
848						 * band */
849    int     	  	bot;	    	    	/* Bottom of non-overlapping
850						 * band */
851
852    /*
853     * Initialization:
854     *	set r1, r2, r1End and r2End appropriately, preserve the important
855     * parts of the destination region until the end in case it's one of
856     * the two source regions, then mark the "new" region empty, allocating
857     * another array of rectangles for it to use.
858     */
859    r1 = reg1->fData;
860    r2 = reg2->fData;
861    r1End = r1 + reg1->fCount;
862    r2End = r2 + reg2->fCount;
863
864//    oldRects = newReg->fData;
865
866    EMPTY_REGION(newReg);
867
868    /*
869     * Allocate a reasonable number of rectangles for the new region. The idea
870     * is to allocate enough so the individual functions don't need to
871     * reallocate and copy the array, which is time consuming, yet we don't
872     * have to worry about using too much memory. I hope to be able to
873     * nuke the realloc() at the end of this function eventually.
874     */
875    if (!newReg->_SetSize(max_c(reg1->fCount,reg2->fCount) * 2)) {
876		return;
877    }
878
879    /*
880     * Initialize ybot and ytop.
881     * In the upcoming loop, ybot and ytop serve different functions depending
882     * on whether the band being handled is an overlapping or non-overlapping
883     * band.
884     * 	In the case of a non-overlapping band (only one of the regions
885     * has points in the band), ybot is the bottom of the most recent
886     * intersection and thus clips the top of the rectangles in that band.
887     * ytop is the top of the next intersection between the two regions and
888     * serves to clip the bottom of the rectangles in the current band.
889     *	For an overlapping band (where the two regions intersect), ytop clips
890     * the top of the rectangles of both regions and ybot clips the bottoms.
891     */
892    if (reg1->fBounds.top < reg2->fBounds.top)
893	ybot = reg1->fBounds.top;
894    else
895	ybot = reg2->fBounds.top;
896
897    /*
898     * prevBand serves to mark the start of the previous band so rectangles
899     * can be coalesced into larger rectangles. qv. miCoalesce, above.
900     * In the beginning, there is no previous band, so prevBand == curBand
901     * (curBand is set later on, of course, but the first band will always
902     * start at index 0). prevBand and curBand must be indices because of
903     * the possible expansion, and resultant moving, of the new region's
904     * array of rectangles.
905     */
906    prevBand = 0;
907
908    do
909    {
910	curBand = newReg->fCount;
911
912	/*
913	 * This algorithm proceeds one source-band (as opposed to a
914	 * destination band, which is determined by where the two regions
915	 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
916	 * rectangle after the last one in the current band for their
917	 * respective regions.
918	 */
919	r1BandEnd = r1;
920	while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
921	{
922	    r1BandEnd++;
923	}
924
925	r2BandEnd = r2;
926	while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
927	{
928	    r2BandEnd++;
929	}
930
931	/*
932	 * First handle the band that doesn't intersect, if any.
933	 *
934	 * Note that attention is restricted to one band in the
935	 * non-intersecting region at once, so if a region has n
936	 * bands between the current position and the next place it overlaps
937	 * the other, this entire loop will be passed through n times.
938	 */
939	if (r1->top < r2->top)
940	{
941	    top = max_c(r1->top,ybot);
942	    bot = min_c(r1->bottom,r2->top);
943
944	    if ((top != bot) && (nonOverlap1Func != NULL))
945	    {
946		(* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
947	    }
948
949	    ytop = r2->top;
950	}
951	else if (r2->top < r1->top)
952	{
953	    top = max_c(r2->top,ybot);
954	    bot = min_c(r2->bottom,r1->top);
955
956	    if ((top != bot) && (nonOverlap2Func != NULL))
957	    {
958		(* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
959	    }
960
961	    ytop = r1->top;
962	}
963	else
964	{
965	    ytop = r1->top;
966	}
967
968	/*
969	 * If any rectangles got added to the region, try and coalesce them
970	 * with rectangles from the previous band. Note we could just do
971	 * this test in miCoalesce, but some machines incur a not
972	 * inconsiderable cost for function calls, so...
973	 */
974	if (newReg->fCount != curBand)
975	{
976	    prevBand = miCoalesce (newReg, prevBand, curBand);
977	}
978
979	/*
980	 * Now see if we've hit an intersecting band. The two bands only
981	 * intersect if ybot > ytop
982	 */
983	ybot = min_c(r1->bottom, r2->bottom);
984	curBand = newReg->fCount;
985	if (ybot > ytop)
986	{
987	    (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
988
989	}
990
991	if (newReg->fCount != curBand)
992	{
993	    prevBand = miCoalesce (newReg, prevBand, curBand);
994	}
995
996	/*
997	 * If we've finished with a band (bottom == ybot) we skip forward
998	 * in the region to the next band.
999	 */
1000	if (r1->bottom == ybot)
1001	{
1002	    r1 = r1BandEnd;
1003	}
1004	if (r2->bottom == ybot)
1005	{
1006	    r2 = r2BandEnd;
1007	}
1008    } while ((r1 != r1End) && (r2 != r2End));
1009
1010    /*
1011     * Deal with whichever region still has rectangles left.
1012     */
1013    curBand = newReg->fCount;
1014    if (r1 != r1End)
1015    {
1016	if (nonOverlap1Func != NULL)
1017	{
1018	    do
1019	    {
1020		r1BandEnd = r1;
1021		while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1022		{
1023		    r1BandEnd++;
1024		}
1025		(* nonOverlap1Func) (newReg, r1, r1BandEnd,
1026				     max_c(r1->top,ybot), r1->bottom);
1027		r1 = r1BandEnd;
1028	    } while (r1 != r1End);
1029	}
1030    }
1031    else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1032    {
1033	do
1034	{
1035	    r2BandEnd = r2;
1036	    while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1037	    {
1038		 r2BandEnd++;
1039	    }
1040	    (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1041				max_c(r2->top,ybot), r2->bottom);
1042	    r2 = r2BandEnd;
1043	} while (r2 != r2End);
1044    }
1045
1046    if (newReg->fCount != curBand)
1047    {
1048	(void) miCoalesce (newReg, prevBand, curBand);
1049    }
1050
1051    /*
1052     * A bit of cleanup. To keep regions from growing without bound,
1053     * we shrink the array of rectangles to match the new number of
1054     * rectangles in the region. This never goes to 0, however...
1055     *
1056     * Only do this stuff if the number of rectangles allocated is more than
1057     * twice the number of rectangles in the region (a simple optimization...).
1058     */
1059//    if (newReg->fCount < (newReg->fDataSize >> 1))
1060//    {
1061//	if (REGION_NOT_EMPTY(newReg))
1062//	{
1063//	    clipping_rect* prev_rects = newReg->fData;
1064//	    newReg->fDataSize = newReg->fCount;
1065//	    newReg->fData = (clipping_rect*) realloc ((char *) newReg->fData,
1066//				   (unsigned) (sizeof(clipping_rect) * newReg->fDataSize));
1067//	    if (! newReg->fData)
1068//		newReg->fData = prev_rects;
1069//	}
1070//	else
1071//	{
1072//	    /*
1073//	     * No point in doing the extra work involved in an realloc if
1074//	     * the region is empty
1075//	     */
1076//	    newReg->fDataSize = 1;
1077//	    free((char *) newReg->fData);
1078//	    newReg->fData = (clipping_rect*) malloc(sizeof(clipping_rect));
1079//	}
1080//    }
1081//    free ((char *) oldRects);
1082    return;
1083}
1084
1085
1086/*======================================================================
1087 *	    BRegion* Union
1088 *====================================================================*/
1089
1090/*-
1091 *-----------------------------------------------------------------------
1092 * miUnionNonO --
1093 *	Handle a non-overlapping band for the union operation. Just
1094 *	Adds the rectangles into the region. Doesn't have to check for
1095 *	subsumption or anything.
1096 *
1097 * Results:
1098 *	None.
1099 *
1100 * Side Effects:
1101 *	pReg->fCount is incremented and the final rectangles overwritten
1102 *	with the rectangles we're passed.
1103 *
1104 *-----------------------------------------------------------------------
1105 */
1106int
1107BRegion::Support::miUnionNonO(register BRegion* pReg,
1108	register clipping_rect* r, clipping_rect* rEnd,
1109    register int top, register int bottom)
1110{
1111	register clipping_rect*	pNextRect = &pReg->fData[pReg->fCount];
1112
1113	assert(top < bottom);
1114
1115	while (r != rEnd) {
1116		assert(r->left < r->right);
1117		MEMCHECK(pReg, pNextRect, pReg->fData);
1118		pNextRect->left = r->left;
1119		pNextRect->top = top;
1120		pNextRect->right = r->right;
1121		pNextRect->bottom = bottom;
1122		pReg->fCount += 1;
1123		pNextRect++;
1124
1125		assert(pReg->fCount<=pReg->fDataSize);
1126		r++;
1127	}
1128	return 0;
1129}
1130
1131
1132/*-
1133 *-----------------------------------------------------------------------
1134 * miUnionO --
1135 *	Handle an overlapping band for the union operation. Picks the
1136 *	left-most rectangle each time and merges it into the region.
1137 *
1138 * Results:
1139 *	None.
1140 *
1141 * Side Effects:
1142 *	Rectangles are overwritten in pReg->fData and pReg->fCount will
1143 *	be changed.
1144 *
1145 *-----------------------------------------------------------------------
1146 */
1147
1148int
1149BRegion::Support::miUnionO (
1150    register BRegion*	pReg,
1151    register clipping_rect*	r1,
1152    clipping_rect*  	  	r1End,
1153    register clipping_rect*	r2,
1154    clipping_rect*  	  	r2End,
1155    register int	top,
1156    register int	bottom)
1157{
1158    register clipping_rect*	pNextRect;
1159
1160    pNextRect = &pReg->fData[pReg->fCount];
1161
1162#define MERGERECT(r) \
1163    if ((pReg->fCount != 0) &&  \
1164	(pNextRect[-1].top == top) &&  \
1165	(pNextRect[-1].bottom == bottom) &&  \
1166	(pNextRect[-1].right >= r->left))  \
1167    {  \
1168	if (pNextRect[-1].right < r->right)  \
1169	{  \
1170	    pNextRect[-1].right = r->right;  \
1171	    assert(pNextRect[-1].left<pNextRect[-1].right); \
1172	}  \
1173    }  \
1174    else  \
1175    {  \
1176	MEMCHECK(pReg, pNextRect, pReg->fData);  \
1177	pNextRect->top = top;  \
1178	pNextRect->bottom = bottom;  \
1179	pNextRect->left = r->left;  \
1180	pNextRect->right = r->right;  \
1181	pReg->fCount += 1;  \
1182        pNextRect += 1;  \
1183    }  \
1184    assert(pReg->fCount<=pReg->fDataSize);\
1185    r++;
1186
1187    assert (top<bottom);
1188    while ((r1 != r1End) && (r2 != r2End))
1189    {
1190	if (r1->left < r2->left)
1191	{
1192	    MERGERECT(r1);
1193	}
1194	else
1195	{
1196	    MERGERECT(r2);
1197	}
1198    }
1199
1200    if (r1 != r1End)
1201    {
1202	do
1203	{
1204	    MERGERECT(r1);
1205	} while (r1 != r1End);
1206    }
1207    else while (r2 != r2End)
1208    {
1209	MERGERECT(r2);
1210    }
1211    return 0;	/* lint */
1212}
1213
1214int
1215BRegion::Support::XUnionRegion(
1216    const BRegion* 	  reg1,
1217    const BRegion*	  reg2,             /* source regions     */
1218    BRegion* 	  newReg)                  /* destination BRegion* */
1219{
1220    /*  checks all the simple cases */
1221
1222    /*
1223     * BRegion* 1 and 2 are the same or region 1 is empty
1224     */
1225    if ( (reg1 == reg2) || (!(reg1->fCount)) )
1226    {
1227        if (newReg != reg2)
1228            miRegionCopy(newReg, reg2);
1229        return 1;
1230    }
1231
1232    /*
1233     * if nothing to union (region 2 empty)
1234     */
1235    if (!(reg2->fCount))
1236    {
1237        if (newReg != reg1)
1238            miRegionCopy(newReg, reg1);
1239        return 1;
1240    }
1241
1242    /*
1243     * BRegion* 1 completely subsumes region 2
1244     */
1245    if ((reg1->fCount == 1) &&
1246	(reg1->fBounds.left <= reg2->fBounds.left) &&
1247	(reg1->fBounds.top <= reg2->fBounds.top) &&
1248	(reg1->fBounds.right >= reg2->fBounds.right) &&
1249	(reg1->fBounds.bottom >= reg2->fBounds.bottom))
1250    {
1251        if (newReg != reg1)
1252            miRegionCopy(newReg, reg1);
1253        return 1;
1254    }
1255
1256    /*
1257     * BRegion* 2 completely subsumes region 1
1258     */
1259    if ((reg2->fCount == 1) &&
1260	(reg2->fBounds.left <= reg1->fBounds.left) &&
1261	(reg2->fBounds.top <= reg1->fBounds.top) &&
1262	(reg2->fBounds.right >= reg1->fBounds.right) &&
1263	(reg2->fBounds.bottom >= reg1->fBounds.bottom))
1264    {
1265        if (newReg != reg2)
1266            miRegionCopy(newReg, reg2);
1267        return 1;
1268    }
1269
1270    miRegionOp (newReg, reg1, reg2, miUnionO,
1271    		miUnionNonO, miUnionNonO);
1272
1273    newReg->fBounds.left = min_c(reg1->fBounds.left, reg2->fBounds.left);
1274    newReg->fBounds.top = min_c(reg1->fBounds.top, reg2->fBounds.top);
1275    newReg->fBounds.right = max_c(reg1->fBounds.right, reg2->fBounds.right);
1276    newReg->fBounds.bottom = max_c(reg1->fBounds.bottom, reg2->fBounds.bottom);
1277
1278    return 1;
1279}
1280
1281
1282/*======================================================================
1283 * 	    	  BRegion* Subtraction
1284 *====================================================================*/
1285
1286/*-
1287 *-----------------------------------------------------------------------
1288 * miSubtractNonO --
1289 *	Deal with non-overlapping band for subtraction. Any parts from
1290 *	region 2 we discard. Anything from region 1 we add to the region.
1291 *
1292 * Results:
1293 *	None.
1294 *
1295 * Side Effects:
1296 *	pReg may be affected.
1297 *
1298 *-----------------------------------------------------------------------
1299 */
1300int
1301BRegion::Support::miSubtractNonO1 (
1302    register BRegion*	pReg,
1303    register clipping_rect*	r,
1304    clipping_rect*  	  	rEnd,
1305    register int  	top,
1306    register int   	bottom)
1307{
1308    register clipping_rect*	pNextRect;
1309
1310    pNextRect = &pReg->fData[pReg->fCount];
1311
1312    assert(top<bottom);
1313
1314    while (r != rEnd)
1315    {
1316	assert(r->left<r->right);
1317	MEMCHECK(pReg, pNextRect, pReg->fData);
1318	pNextRect->left = r->left;
1319	pNextRect->top = top;
1320	pNextRect->right = r->right;
1321	pNextRect->bottom = bottom;
1322	pReg->fCount += 1;
1323	pNextRect++;
1324
1325	assert(pReg->fCount <= pReg->fDataSize);
1326
1327	r++;
1328    }
1329    return 0;	/* lint */
1330}
1331
1332/*-
1333 *-----------------------------------------------------------------------
1334 * miSubtractO --
1335 *	Overlapping band subtraction. left is the left-most point not yet
1336 *	checked.
1337 *
1338 * Results:
1339 *	None.
1340 *
1341 * Side Effects:
1342 *	pReg may have rectangles added to it.
1343 *
1344 *-----------------------------------------------------------------------
1345 */
1346int
1347BRegion::Support::miSubtractO(
1348    register BRegion*	pReg,
1349    register clipping_rect*	r1,
1350    clipping_rect*  	  	r1End,
1351    register clipping_rect*	r2,
1352    clipping_rect*  	  	r2End,
1353    register int  	top,
1354    register int  	bottom)
1355{
1356    register clipping_rect*	pNextRect;
1357    register int  	left;
1358
1359    left = r1->left;
1360
1361    assert(top<bottom);
1362    pNextRect = &pReg->fData[pReg->fCount];
1363
1364    while ((r1 != r1End) && (r2 != r2End))
1365    {
1366	if (r2->right <= left)
1367	{
1368	    /*
1369	     * Subtrahend missed the boat: go to next subtrahend.
1370	     */
1371	    r2++;
1372	}
1373	else if (r2->left <= left)
1374	{
1375	    /*
1376	     * Subtrahend preceeds minuend: nuke left edge of minuend.
1377	     */
1378	    left = r2->right;
1379	    if (left >= r1->right)
1380	    {
1381		/*
1382		 * Minuend completely covered: advance to next minuend and
1383		 * reset left fence to edge of new minuend.
1384		 */
1385		r1++;
1386		if (r1 != r1End)
1387		    left = r1->left;
1388	    }
1389	    else
1390	    {
1391		/*
1392		 * Subtrahend now used up since it doesn't extend beyond
1393		 * minuend
1394		 */
1395		r2++;
1396	    }
1397	}
1398	else if (r2->left < r1->right)
1399	{
1400	    /*
1401	     * Left part of subtrahend covers part of minuend: add uncovered
1402	     * part of minuend to region and skip to next subtrahend.
1403	     */
1404	    assert(left<r2->left);
1405	    MEMCHECK(pReg, pNextRect, pReg->fData);
1406	    pNextRect->left = left;
1407	    pNextRect->top = top;
1408	    pNextRect->right = r2->left;
1409	    pNextRect->bottom = bottom;
1410	    pReg->fCount += 1;
1411	    pNextRect++;
1412
1413	    assert(pReg->fCount<=pReg->fDataSize);
1414
1415	    left = r2->right;
1416	    if (left >= r1->right)
1417	    {
1418		/*
1419		 * Minuend used up: advance to new...
1420		 */
1421		r1++;
1422		if (r1 != r1End)
1423		    left = r1->left;
1424	    }
1425	    else
1426	    {
1427		/*
1428		 * Subtrahend used up
1429		 */
1430		r2++;
1431	    }
1432	}
1433	else
1434	{
1435	    /*
1436	     * Minuend used up: add any remaining piece before advancing.
1437	     */
1438	    if (r1->right > left)
1439	    {
1440		MEMCHECK(pReg, pNextRect, pReg->fData);
1441		pNextRect->left = left;
1442		pNextRect->top = top;
1443		pNextRect->right = r1->right;
1444		pNextRect->bottom = bottom;
1445		pReg->fCount += 1;
1446		pNextRect++;
1447		assert(pReg->fCount<=pReg->fDataSize);
1448	    }
1449	    r1++;
1450	    if (r1 != r1End)
1451		left = r1->left;
1452	}
1453    }
1454
1455    /*
1456     * Add remaining minuend rectangles to region.
1457     */
1458    while (r1 != r1End)
1459    {
1460	assert(left<r1->right);
1461	MEMCHECK(pReg, pNextRect, pReg->fData);
1462	pNextRect->left = left;
1463	pNextRect->top = top;
1464	pNextRect->right = r1->right;
1465	pNextRect->bottom = bottom;
1466	pReg->fCount += 1;
1467	pNextRect++;
1468
1469	assert(pReg->fCount<=pReg->fDataSize);
1470
1471	r1++;
1472	if (r1 != r1End)
1473	{
1474	    left = r1->left;
1475	}
1476    }
1477    return 0;	/* lint */
1478}
1479
1480/*-
1481 *-----------------------------------------------------------------------
1482 * miSubtract --
1483 *	Subtract regS from regM and leave the result in regD.
1484 *	S stands for subtrahend, M for minuend and D for difference.
1485 *
1486 * Results:
1487 *	true.
1488 *
1489 * Side Effects:
1490 *	regD is overwritten.
1491 *
1492 *-----------------------------------------------------------------------
1493 */
1494
1495int
1496BRegion::Support::XSubtractRegion(
1497    const BRegion* 	  	regM,
1498    const BRegion*	  	regS,
1499    register BRegion*	regD)
1500{
1501   /* check for trivial reject */
1502    if ( (!(regM->fCount)) || (!(regS->fCount))  ||
1503	(!EXTENTCHECK(&regM->fBounds, &regS->fBounds)) )
1504    {
1505	miRegionCopy(regD, regM);
1506        return 1;
1507    }
1508
1509    miRegionOp (regD, regM, regS, miSubtractO,
1510    		miSubtractNonO1, NULL);
1511
1512    /*
1513     * Can't alter newReg's fBounds before we call miRegionOp because
1514     * it might be one of the source regions and miRegionOp depends
1515     * on the fBounds of those regions being the unaltered. Besides, this
1516     * way there's no checking against rectangles that will be nuked
1517     * due to coalescing, so we have to examine fewer rectangles.
1518     */
1519    miSetExtents (regD);
1520    return 1;
1521}
1522
1523int
1524BRegion::Support::XXorRegion(const BRegion* sra, const BRegion* srb,
1525	BRegion* dr)
1526{
1527    BRegion* tra = NULL;
1528    BRegion* trb = NULL;
1529
1530    if ((! (tra = CreateRegion())) || (! (trb = CreateRegion())))
1531    {
1532        DestroyRegion(tra);
1533        DestroyRegion(trb);
1534		return 0;
1535    }
1536    (void) XSubtractRegion(sra,srb,tra);
1537    (void) XSubtractRegion(srb,sra,trb);
1538    (void) XUnionRegion(tra,trb,dr);
1539    DestroyRegion(tra);
1540    DestroyRegion(trb);
1541    return 0;
1542}
1543
1544
1545bool
1546BRegion::Support::XPointInRegion(
1547    const BRegion* pRegion,
1548    int x, int y)
1549{
1550	// TODO: binary search by "y"!
1551    int i;
1552
1553    if (pRegion->fCount == 0)
1554        return false;
1555    if (!INBOX(pRegion->fBounds, x, y))
1556        return false;
1557    for (i=0; i<pRegion->fCount; i++)
1558    {
1559        if (INBOX (pRegion->fData[i], x, y))
1560	    return true;
1561    }
1562    return false;
1563}
1564
1565int
1566BRegion::Support::XRectInRegion(
1567    register const BRegion* region,
1568    const clipping_rect& rect)
1569{
1570    register clipping_rect* pbox;
1571    register clipping_rect* pboxEnd;
1572    register const clipping_rect* prect = &rect;
1573    bool      partIn, partOut;
1574
1575    int rx = prect->left;
1576    int ry = prect->top;
1577
1578    /* this is (just) a useful optimization */
1579    if ((region->fCount == 0) || !EXTENTCHECK(&region->fBounds, prect))
1580        return(RectangleOut);
1581
1582    partOut = false;
1583    partIn = false;
1584
1585    /* can stop when both partOut and partIn are true, or we reach prect->bottom */
1586    for (pbox = region->fData, pboxEnd = pbox + region->fCount;
1587	 pbox < pboxEnd;
1588	 pbox++)
1589    {
1590
1591	if (pbox->bottom <= ry)
1592	   continue;	/* getting up to speed or skipping remainder of band */
1593
1594	if (pbox->top > ry)
1595	{
1596	   partOut = true;	/* missed part of rectangle above */
1597	   if (partIn || (pbox->top >= prect->bottom))
1598	      break;
1599	   ry = pbox->top;	/* x guaranteed to be == prect->left */
1600	}
1601
1602	if (pbox->right <= rx)
1603	   continue;		/* not far enough over yet */
1604
1605	if (pbox->left > rx)
1606	{
1607	   partOut = true;	/* missed part of rectangle to left */
1608	   if (partIn)
1609	      break;
1610	}
1611
1612	if (pbox->left < prect->right)
1613	{
1614	    partIn = true;	/* definitely overlap */
1615	    if (partOut)
1616	       break;
1617	}
1618
1619	if (pbox->right >= prect->right)
1620	{
1621	   ry = pbox->bottom;	/* finished with this band */
1622	   if (ry >= prect->bottom)
1623	      break;
1624	   rx = prect->left;	/* reset x out to left again */
1625	} else
1626	{
1627	    /*
1628	     * Because boxes in a band are maximal width, if the first box
1629	     * to overlap the rectangle doesn't completely cover it in that
1630	     * band, the rectangle must be partially out, since some of it
1631	     * will be uncovered in that band. partIn will have been set true
1632	     * by now...
1633	     */
1634	    break;
1635	}
1636
1637    }
1638
1639    return(partIn ? ((ry < prect->bottom) ? RectanglePart : RectangleIn) :
1640		RectangleOut);
1641}
1642