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