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