src/osx/carbon/region.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // File:      src/osx/carbon/region.cpp
   3 // Purpose:   Region class
   4 // Author:    Stefan Csomor
   5 // Created:   Fri Oct 24 10:46:34 MET 1997
   6 // Copyright: (c) 1997 Stefan Csomor
   7 // Licence:   wxWindows licence
   8 /////////////////////////////////////////////////////////////////////////////
   9
  10 #include "wx/wxprec.h"
  11
  12 #if wxOSX_USE_COCOA_OR_CARBON
  13
  14 #include "wx/region.h"
  15
  16 #ifndef WX_PRECOMP
  17     #include "wx/gdicmn.h"
  18     #include "wx/dcmemory.h"
  19 #endif
  20
  21 #include "wx/osx/private.h"
  22
  23 IMPLEMENT_DYNAMIC_CLASS(wxRegion, wxGDIObject)
  24 IMPLEMENT_DYNAMIC_CLASS(wxRegionIterator, wxObject)
  25
  26 #define OSX_USE_SCANLINES 1
  27
  28 //-----------------------------------------------------------------------------
  29 // wxRegionRefData implementation
  30 //-----------------------------------------------------------------------------
  31
  32 class WXDLLEXPORT wxRegionRefData : public wxGDIRefData
  33 {
  34 public:
  35     wxRegionRefData()
  36     {
  37         m_macRgn.reset( HIShapeCreateMutable() );
  38     }
  39
  40     wxRegionRefData(wxCFRef<HIShapeRef> &region)
  41     {
  42         m_macRgn.reset( HIShapeCreateMutableCopy(region) );
  43     }
  44
  45     wxRegionRefData(long x, long y, long w, long h)
  46     {
  47         CGRect r = CGRectMake(x,y,w,h);
  48         wxCFRef<HIShapeRef> rect(HIShapeCreateWithRect(&r));
  49         m_macRgn.reset( HIShapeCreateMutableCopy(rect) );
  50     }
  51
  52     wxRegionRefData(const wxRegionRefData& data)
  53         : wxGDIRefData()
  54     {
  55         m_macRgn.reset( HIShapeCreateMutableCopy(data.m_macRgn) );
  56     }
  57
  58     virtual ~wxRegionRefData()
  59     {
  60     }
  61
  62     wxCFRef<HIMutableShapeRef> m_macRgn;
  63 };
  64
  65 #define M_REGION (((wxRegionRefData*)m_refData)->m_macRgn)
  66 #define OTHER_M_REGION(a) (((wxRegionRefData*)(a.m_refData))->m_macRgn)
  67
  68 //-----------------------------------------------------------------------------
  69 // wxRegion
  70 //-----------------------------------------------------------------------------
  71
  72 wxRegion::wxRegion(WXHRGN hRegion )
  73 {
  74     wxCFRef< HIShapeRef > shape( (HIShapeRef) hRegion );
  75     m_refData = new wxRegionRefData(shape);
  76 }
  77
  78 wxRegion::wxRegion(long x, long y, long w, long h)
  79 {
  80     m_refData = new wxRegionRefData(x , y , w , h );
  81 }
  82
  83 wxRegion::wxRegion(const wxPoint& topLeft, const wxPoint& bottomRight)
  84 {
  85     m_refData = new wxRegionRefData(topLeft.x , topLeft.y ,
  86                                     bottomRight.x - topLeft.x,
  87                                     bottomRight.y - topLeft.y);
  88 }
  89
  90 wxRegion::wxRegion(const wxRect& rect)
  91 {
  92     m_refData = new wxRegionRefData(rect.x , rect.y , rect.width , rect.height);
  93 }
  94
  95 #if OSX_USE_SCANLINES
  96
  97 /*
  98
  99  Copyright 1987, 1998  The Open Group
 100
 101  Permission to use, copy, modify, distribute, and sell this software and its
 102  documentation for any purpose is hereby granted without fee, provided that
 103  the above copyright notice appear in all copies and that both that
 104  copyright notice and this permission notice appear in supporting
 105  documentation.
 106
 107  The above copyright notice and this permission notice shall be included
 108  in all copies or substantial portions of the Software.
 109
 110  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 111  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 112  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 113  IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
 114  OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 115  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 116  OTHER DEALINGS IN THE SOFTWARE.
 117
 118  Except as contained in this notice, the name of The Open Group shall
 119  not be used in advertising or otherwise to promote the sale, use or
 120  other dealings in this Software without prior written authorization
 121  from The Open Group.
 122
 123  */
 124
 125 /* miscanfill.h */
 126
 127 /*
 128  *     scanfill.h
 129  *
 130  *     Written by Brian Kelleher; Jan 1985
 131  *
 132  *     This file contains a few macros to help track
 133  *     the edge of a filled object.  The object is assumed
 134  *     to be filled in scanline order, and thus the
 135  *     algorithm used is an extension of Bresenham's line
 136  *     drawing algorithm which assumes that y is always the
 137  *     major axis.
 138  *     Since these pieces of code are the same for any filled shape,
 139  *     it is more convenient to gather the library in one
 140  *     place, but since these pieces of code are also in
 141  *     the inner loops of output primitives, procedure call
 142  *     overhead is out of the question.
 143  *     See the author for a derivation if needed.
 144  */
 145
 146
 147 /*
 148  *  In scan converting polygons, we want to choose those pixels
 149  *  which are inside the polygon.  Thus, we add .5 to the starting
 150  *  x coordinate for both left and right edges.  Now we choose the
 151  *  first pixel which is inside the pgon for the left edge and the
 152  *  first pixel which is outside the pgon for the right edge.
 153  *  Draw the left pixel, but not the right.
 154  *
 155  *  How to add .5 to the starting x coordinate:
 156  *      If the edge is moving to the right, then subtract dy from the
 157  *  error term from the general form of the algorithm.
 158  *      If the edge is moving to the left, then add dy to the error term.
 159  *
 160  *  The reason for the difference between edges moving to the left
 161  *  and edges moving to the right is simple:  If an edge is moving
 162  *  to the right, then we want the algorithm to flip immediately.
 163  *  If it is moving to the left, then we don't want it to flip until
 164  *  we traverse an entire pixel.
 165  */
 166 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
 167 int dx;      /* local storage */ \
 168 \
 169 /* \
 170 *  if the edge is horizontal, then it is ignored \
 171 *  and assumed not to be processed.  Otherwise, do this stuff. \
 172 */ \
 173 if ((dy) != 0) { \
 174 xStart = (x1); \
 175 dx = (x2) - xStart; \
 176 if (dx < 0) { \
 177 m = dx / (dy); \
 178 m1 = m - 1; \
 179 incr1 = -2 * dx + 2 * (dy) * m1; \
 180 incr2 = -2 * dx + 2 * (dy) * m; \
 181 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
 182 } else { \
 183 m = dx / (dy); \
 184 m1 = m + 1; \
 185 incr1 = 2 * dx - 2 * (dy) * m1; \
 186 incr2 = 2 * dx - 2 * (dy) * m; \
 187 d = -2 * m * (dy) + 2 * dx; \
 188 } \
 189 } \
 190 }
 191
 192 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
 193 if (m1 > 0) { \
 194 if (d > 0) { \
 195 minval += m1; \
 196 d += incr1; \
 197 } \
 198 else { \
 199 minval += m; \
 200 d += incr2; \
 201 } \
 202 } else {\
 203 if (d >= 0) { \
 204 minval += m1; \
 205 d += incr1; \
 206 } \
 207 else { \
 208 minval += m; \
 209 d += incr2; \
 210 } \
 211 } \
 212 }
 213
 214
 215 /*
 216  *     This structure contains all of the information needed
 217  *     to run the bresenham algorithm.
 218  *     The variables may be hardcoded into the declarations
 219  *     instead of using this structure to make use of
 220  *     register declarations.
 221  */
 222 typedef struct {
 223     int minor;         /* minor axis        */
 224     int d;           /* decision variable */
 225     int m, m1;       /* slope and slope+1 */
 226     int incr1, incr2; /* error increments */
 227 } BRESINFO;
 228
 229
 230 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
 231 BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \
 232 bres.m, bres.m1, bres.incr1, bres.incr2)
 233
 234 #define BRESINCRPGONSTRUCT(bres) \
 235 BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2)
 236
 237
 238 /* mipoly.h */
 239
 240 /*
 241  *     fill.h
 242  *
 243  *     Created by Brian Kelleher; Oct 1985
 244  *
 245  *     Include file for filled polygon routines.
 246  *
 247  *     These are the data structures needed to scan
 248  *     convert regions.  Two different scan conversion
 249  *     methods are available -- the even-odd method, and
 250  *     the winding number method.
 251  *     The even-odd rule states that a point is inside
 252  *     the polygon if a ray drawn from that point in any
 253  *     direction will pass through an odd number of
 254  *     path segments.
 255  *     By the winding number rule, a point is decided
 256  *     to be inside the polygon if a ray drawn from that
 257  *     point in any direction passes through a different
 258  *     number of clockwise and counter-clockwise path
 259  *     segments.
 260  *
 261  *     These data structures are adapted somewhat from
 262  *     the algorithm in (Foley/Van Dam) for scan converting
 263  *     polygons.
 264  *     The basic algorithm is to start at the top (smallest y)
 265  *     of the polygon, stepping down to the bottom of
 266  *     the polygon by incrementing the y coordinate.  We
 267  *     keep a list of edges which the current scanline crosses,
 268  *     sorted by x.  This list is called the Active Edge Table (AET)
 269  *     As we change the y-coordinate, we update each entry in
 270  *     in the active edge table to reflect the edges new xcoord.
 271  *     This list must be sorted at each scanline in case
 272  *     two edges intersect.
 273  *     We also keep a data structure known as the Edge Table (ET),
 274  *     which keeps track of all the edges which the current
 275  *     scanline has not yet reached.  The ET is basically a
 276  *     list of ScanLineList structures containing a list of
 277  *     edges which are entered at a given scanline.  There is one
 278  *     ScanLineList per scanline at which an edge is entered.
 279  *     When we enter a new edge, we move it from the ET to the AET.
 280  *
 281  *     From the AET, we can implement the even-odd rule as in
 282  *     (Foley/Van Dam).
 283  *     The winding number rule is a little trickier.  We also
 284  *     keep the EdgeTableEntries in the AET linked by the
 285  *     nextWETE (winding EdgeTableEntry) link.  This allows
 286  *     the edges to be linked just as before for updating
 287  *     purposes, but only uses the edges linked by the nextWETE
 288  *     link as edges representing spans of the polygon to
 289  *     drawn (as with the even-odd rule).
 290  */
 291
 292 /*
 293  * for the winding number rule
 294  */
 295 #define CLOCKWISE          1
 296 #define COUNTERCLOCKWISE  -1
 297
 298 typedef struct _EdgeTableEntry {
 299     int ymax;             /* ycoord at which we exit this edge. */
 300     BRESINFO bres;        /* Bresenham info to run the edge     */
 301     struct _EdgeTableEntry *next;       /* next in the list     */
 302     struct _EdgeTableEntry *back;       /* for insertion sort   */
 303     struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
 304     int ClockWise;        /* flag for winding number rule       */
 305 } EdgeTableEntry;
 306
 307
 308 typedef struct _ScanLineList{
 309     int scanline;              /* the scanline represented */
 310     EdgeTableEntry *edgelist;  /* header node              */
 311     struct _ScanLineList *next;  /* next in the list       */
 312 } ScanLineList;
 313
 314
 315 typedef struct {
 316     int ymax;                 /* ymax for the polygon     */
 317     int ymin;                 /* ymin for the polygon     */
 318     ScanLineList scanlines;   /* header node              */
 319 } EdgeTable;
 320
 321
 322 /*
 323  * Here is a struct to help with storage allocation
 324  * so we can allocate a big chunk at a time, and then take
 325  * pieces from this heap when we need to.
 326  */
 327 #define SLLSPERBLOCK 25
 328
 329 typedef struct _ScanLineListBlock {
 330     ScanLineList SLLs[SLLSPERBLOCK];
 331     struct _ScanLineListBlock *next;
 332 } ScanLineListBlock;
 333
 334 /*
 335  * number of points to buffer before sending them off
 336  * to scanlines() :  Must be an even number
 337  */
 338 #define NUMPTSTOBUFFER 200
 339
 340
 341 /*
 342  *
 343  *     a few macros for the inner loops of the fill code where
 344  *     performance considerations don't allow a procedure call.
 345  *
 346  *     Evaluate the given edge at the given scanline.
 347  *     If the edge has expired, then we leave it and fix up
 348  *     the active edge table; otherwise, we increment the
 349  *     x value to be ready for the next scanline.
 350  *     The winding number rule is in effect, so we must notify
 351  *     the caller when the edge has been removed so he
 352  *     can reorder the Winding Active Edge Table.
 353  */
 354 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
 355 if (pAET->ymax == y) {          /* leaving this edge */ \
 356 pPrevAET->next = pAET->next; \
 357 pAET = pPrevAET->next; \
 358 fixWAET = 1; \
 359 if (pAET) \
 360 pAET->back = pPrevAET; \
 361 } \
 362 else { \
 363 BRESINCRPGONSTRUCT(pAET->bres); \
 364 pPrevAET = pAET; \
 365 pAET = pAET->next; \
 366 } \
 367 }
 368
 369
 370 /*
 371  *     Evaluate the given edge at the given scanline.
 372  *     If the edge has expired, then we leave it and fix up
 373  *     the active edge table; otherwise, we increment the
 374  *     x value to be ready for the next scanline.
 375  *     The even-odd rule is in effect.
 376  */
 377 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
 378 if (pAET->ymax == y) {          /* leaving this edge */ \
 379 pPrevAET->next = pAET->next; \
 380 pAET = pPrevAET->next; \
 381 if (pAET) \
 382 pAET->back = pPrevAET; \
 383 } \
 384 else { \
 385 BRESINCRPGONSTRUCT(pAET->bres); \
 386 pPrevAET = pAET; \
 387 pAET = pAET->next; \
 388 } \
 389 }
 390
 391 /* mipolyutil.c */
 392
 393 static bool miCreateETandAET(
 394                              int /*count*/,
 395                              const wxPoint * /*pts*/,
 396                              EdgeTable * /*ET*/,
 397                              EdgeTableEntry * /*AET*/,
 398                              EdgeTableEntry * /*pETEs*/,
 399                              ScanLineListBlock * /*pSLLBlock*/
 400                              );
 401
 402 static void miloadAET(
 403                       EdgeTableEntry * /*AET*/,
 404                       EdgeTableEntry * /*ETEs*/
 405                       );
 406
 407 static void micomputeWAET(
 408                           EdgeTableEntry * /*AET*/
 409                           );
 410
 411 static int miInsertionSort(
 412                            EdgeTableEntry * /*AET*/
 413                            );
 414
 415 static void miFreeStorage(
 416                           ScanLineListBlock * /*pSLLBlock*/
 417                           );
 418
 419 /*
 420  *     fillUtils.c
 421  *
 422  *     Written by Brian Kelleher;  Oct. 1985
 423  *
 424  *     This module contains all of the utility functions
 425  *     needed to scan convert a polygon.
 426  *
 427  */
 428
 429 /*
 430  *     InsertEdgeInET
 431  *
 432  *     Insert the given edge into the edge table.
 433  *     First we must find the correct bucket in the
 434  *     Edge table, then find the right slot in the
 435  *     bucket.  Finally, we can insert it.
 436  *
 437  */
 438 static bool
 439 miInsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,  int scanline,
 440                  ScanLineListBlock **SLLBlock, int *iSLLBlock)
 441 {
 442     EdgeTableEntry *start, *prev;
 443     ScanLineList *pSLL, *pPrevSLL;
 444     ScanLineListBlock *tmpSLLBlock;
 445
 446     /*
 447      * find the right bucket to put the edge into
 448      */
 449     pPrevSLL = &ET->scanlines;
 450     pSLL = pPrevSLL->next;
 451     while (pSLL && (pSLL->scanline < scanline))
 452     {
 453         pPrevSLL = pSLL;
 454         pSLL = pSLL->next;
 455     }
 456
 457     /*
 458      * reassign pSLL (pointer to ScanLineList) if necessary
 459      */
 460     if ((!pSLL) || (pSLL->scanline > scanline))
 461     {
 462         if (*iSLLBlock > SLLSPERBLOCK-1)
 463         {
 464             tmpSLLBlock =
 465             (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
 466             if (!tmpSLLBlock)
 467                 return FALSE;
 468             (*SLLBlock)->next = tmpSLLBlock;
 469             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
 470             *SLLBlock = tmpSLLBlock;
 471             *iSLLBlock = 0;
 472         }
 473         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 474
 475         pSLL->next = pPrevSLL->next;
 476         pSLL->edgelist = (EdgeTableEntry *)NULL;
 477         pPrevSLL->next = pSLL;
 478     }
 479     pSLL->scanline = scanline;
 480
 481     /*
 482      * now insert the edge in the right bucket
 483      */
 484     prev = (EdgeTableEntry *)NULL;
 485     start = pSLL->edgelist;
 486     while (start && (start->bres.minor < ETE->bres.minor))
 487     {
 488         prev = start;
 489         start = start->next;
 490     }
 491     ETE->next = start;
 492
 493     if (prev)
 494         prev->next = ETE;
 495     else
 496         pSLL->edgelist = ETE;
 497     return TRUE;
 498 }
 499
 500 /*
 501  *     CreateEdgeTable
 502  *
 503  *     This routine creates the edge table for
 504  *     scan converting polygons.
 505  *     The Edge Table (ET) looks like:
 506  *
 507  *    EdgeTable
 508  *     --------
 509  *    |  ymax  |        ScanLineLists
 510  *    |scanline|-->------------>-------------->...
 511  *     --------   |scanline|   |scanline|
 512  *                |edgelist|   |edgelist|
 513  *                ---------    ---------
 514  *                    |             |
 515  *                    |             |
 516  *                    V             V
 517  *              list of ETEs   list of ETEs
 518  *
 519  *     where ETE is an EdgeTableEntry data structure,
 520  *     and there is one ScanLineList per scanline at
 521  *     which an edge is initially entered.
 522  *
 523  */
 524
 525 static bool
 526 miCreateETandAET(int count, const wxPoint * pts, EdgeTable *ET, EdgeTableEntry *AET,
 527                  EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
 528 {
 529     const wxPoint* top, *bottom;
 530     const wxPoint* PrevPt, *CurrPt;
 531     int iSLLBlock = 0;
 532
 533     int dy;
 534
 535     if (count < 2)  return TRUE;
 536
 537     /*
 538      *  initialize the Active Edge Table
 539      */
 540     AET->next = (EdgeTableEntry *)NULL;
 541     AET->back = (EdgeTableEntry *)NULL;
 542     AET->nextWETE = (EdgeTableEntry *)NULL;
 543     AET->bres.minor = INT_MIN;
 544
 545     /*
 546      *  initialize the Edge Table.
 547      */
 548     ET->scanlines.next = (ScanLineList *)NULL;
 549     ET->ymax = INT_MIN;
 550     ET->ymin = INT_MAX;
 551     pSLLBlock->next = (ScanLineListBlock *)NULL;
 552
 553     PrevPt = &pts[count-1];
 554
 555     /*
 556      *  for each vertex in the array of points.
 557      *  In this loop we are dealing with two vertices at
 558      *  a time -- these make up one edge of the polygon.
 559      */
 560     while (count--)
 561     {
 562         CurrPt = pts++;
 563
 564         /*
 565          *  find out which point is above and which is below.
 566          */
 567         if (PrevPt->y > CurrPt->y)
 568         {
 569             bottom = PrevPt, top = CurrPt;
 570             pETEs->ClockWise = 0;
 571         }
 572         else
 573         {
 574             bottom = CurrPt, top = PrevPt;
 575             pETEs->ClockWise = 1;
 576         }
 577
 578         /*
 579          * don't add horizontal edges to the Edge table.
 580          */
 581         if (bottom->y != top->y)
 582         {
 583             pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
 584
 585             /*
 586              *  initialize integer edge algorithm
 587              */
 588             dy = bottom->y - top->y;
 589             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
 590
 591             if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
 592             {
 593                 miFreeStorage(pSLLBlock->next);
 594                 return FALSE;
 595             }
 596
 597             ET->ymax = wxMax(ET->ymax, PrevPt->y);
 598             ET->ymin = wxMin(ET->ymin, PrevPt->y);
 599             pETEs++;
 600         }
 601
 602         PrevPt = CurrPt;
 603     }
 604     return TRUE;
 605 }
 606
 607 /*
 608  *     loadAET
 609  *
 610  *     This routine moves EdgeTableEntries from the
 611  *     EdgeTable into the Active Edge Table,
 612  *     leaving them sorted by smaller x coordinate.
 613  *
 614  */
 615
 616 static void
 617 miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
 618 {
 619     EdgeTableEntry *pPrevAET;
 620     EdgeTableEntry *tmp;
 621
 622     pPrevAET = AET;
 623     AET = AET->next;
 624     while (ETEs)
 625     {
 626         while (AET && (AET->bres.minor < ETEs->bres.minor))
 627         {
 628             pPrevAET = AET;
 629             AET = AET->next;
 630         }
 631         tmp = ETEs->next;
 632         ETEs->next = AET;
 633         if (AET)
 634             AET->back = ETEs;
 635         ETEs->back = pPrevAET;
 636         pPrevAET->next = ETEs;
 637         pPrevAET = ETEs;
 638
 639         ETEs = tmp;
 640     }
 641 }
 642
 643 /*
 644  *     computeWAET
 645  *
 646  *     This routine links the AET by the
 647  *     nextWETE (winding EdgeTableEntry) link for
 648  *     use by the winding number rule.  The final
 649  *     Active Edge Table (AET) might look something
 650  *     like:
 651  *
 652  *     AET
 653  *     ----------  ---------   ---------
 654  *     |ymax    |  |ymax    |  |ymax    |
 655  *     | ...    |  |...     |  |...     |
 656  *     |next    |->|next    |->|next    |->...
 657  *     |nextWETE|  |nextWETE|  |nextWETE|
 658  *     ---------   ---------   ^--------
 659  *         |                   |       |
 660  *         V------------------->       V---> ...
 661  *
 662  */
 663 static void
 664 micomputeWAET(EdgeTableEntry *AET)
 665 {
 666     EdgeTableEntry *pWETE;
 667     int inside = 1;
 668     int isInside = 0;
 669
 670     AET->nextWETE = (EdgeTableEntry *)NULL;
 671     pWETE = AET;
 672     AET = AET->next;
 673     while (AET)
 674     {
 675         if (AET->ClockWise)
 676             isInside++;
 677         else
 678             isInside--;
 679
 680         if ((!inside && !isInside) ||
 681             ( inside &&  isInside))
 682         {
 683             pWETE->nextWETE = AET;
 684             pWETE = AET;
 685             inside = !inside;
 686         }
 687         AET = AET->next;
 688     }
 689     pWETE->nextWETE = (EdgeTableEntry *)NULL;
 690 }
 691
 692 /*
 693  *     InsertionSort
 694  *
 695  *     Just a simple insertion sort using
 696  *     pointers and back pointers to sort the Active
 697  *     Edge Table.
 698  *
 699  */
 700
 701 static int
 702 miInsertionSort(EdgeTableEntry *AET)
 703 {
 704     EdgeTableEntry *pETEchase;
 705     EdgeTableEntry *pETEinsert;
 706     EdgeTableEntry *pETEchaseBackTMP;
 707     int changed = 0;
 708
 709     AET = AET->next;
 710     while (AET)
 711     {
 712         pETEinsert = AET;
 713         pETEchase = AET;
 714         while (pETEchase->back->bres.minor > AET->bres.minor)
 715             pETEchase = pETEchase->back;
 716
 717         AET = AET->next;
 718         if (pETEchase != pETEinsert)
 719         {
 720             pETEchaseBackTMP = pETEchase->back;
 721             pETEinsert->back->next = AET;
 722             if (AET)
 723                 AET->back = pETEinsert->back;
 724             pETEinsert->next = pETEchase;
 725             pETEchase->back->next = pETEinsert;
 726             pETEchase->back = pETEinsert;
 727             pETEinsert->back = pETEchaseBackTMP;
 728             changed = 1;
 729         }
 730     }
 731     return(changed);
 732 }
 733
 734 /*
 735  *     Clean up our act.
 736  */
 737 static void
 738 miFreeStorage(ScanLineListBlock *pSLLBlock)
 739 {
 740     ScanLineListBlock   *tmpSLLBlock;
 741
 742     while (pSLLBlock)
 743     {
 744         tmpSLLBlock = pSLLBlock->next;
 745         free(pSLLBlock);
 746         pSLLBlock = tmpSLLBlock;
 747     }
 748 }
 749
 750 /* mipolygen.c */
 751
 752 static bool
 753 scanFillGeneralPoly( wxRegion* rgn,
 754                   int   count,              /* number of points        */
 755                   const wxPoint *ptsIn,               /* the points              */
 756                   wxPolygonFillMode fillStyle
 757                   )
 758 {
 759     EdgeTableEntry *pAET;  /* the Active Edge Table   */
 760     int y;                 /* the current scanline    */
 761     int nPts = 0;          /* number of pts in buffer */
 762     EdgeTableEntry *pWETE; /* Winding Edge Table      */
 763     ScanLineList *pSLL;    /* Current ScanLineList    */
 764     wxPoint * ptsOut;      /* ptr to output buffers   */
 765     int *width;
 766     wxPoint FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */
 767     int FirstWidth[NUMPTSTOBUFFER];
 768     EdgeTableEntry *pPrevAET;       /* previous AET entry      */
 769     EdgeTable ET;                   /* Edge Table header node  */
 770     EdgeTableEntry AET;             /* Active ET header node   */
 771     EdgeTableEntry *pETEs;          /* Edge Table Entries buff */
 772     ScanLineListBlock SLLBlock;     /* header for ScanLineList */
 773     int fixWAET = 0;
 774
 775     if (count < 3)
 776         return(TRUE);
 777
 778     if(!(pETEs = (EdgeTableEntry *)
 779          malloc(sizeof(EdgeTableEntry) * count)))
 780         return(FALSE);
 781     ptsOut = FirstPoint;
 782     width = FirstWidth;
 783     if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock))
 784     {
 785         free(pETEs);
 786         return(FALSE);
 787     }
 788     pSLL = ET.scanlines.next;
 789
 790     if (fillStyle == wxODDEVEN_RULE)
 791     {
 792         /*
 793          *  for each scanline
 794          */
 795         for (y = ET.ymin; y < ET.ymax; y++)
 796         {
 797             /*
 798              *  Add a new edge to the active edge table when we
 799              *  get to the next edge.
 800              */
 801             if (pSLL && y == pSLL->scanline)
 802             {
 803                 miloadAET(&AET, pSLL->edgelist);
 804                 pSLL = pSLL->next;
 805             }
 806             pPrevAET = &AET;
 807             pAET = AET.next;
 808
 809             /*
 810              *  for each active edge
 811              */
 812             while (pAET)
 813             {
 814                 ptsOut->x = pAET->bres.minor;
 815                 ptsOut++->y = y;
 816                 *width++ = pAET->next->bres.minor - pAET->bres.minor;
 817                 nPts++;
 818
 819                 /*
 820                  *  send out the buffer when its full
 821                  */
 822                 if (nPts == NUMPTSTOBUFFER)
 823                 {
 824                     // (*pgc->ops->FillSpans)(dst, pgc,
 825                     //     nPts, FirstPoint, FirstWidth,1);
 826
 827                     for ( int i = 0 ; i < nPts; ++i)
 828                     {
 829                         wxRect rect;
 830                         rect.y = FirstPoint[i].y;
 831                         rect.x = FirstPoint[i].x;
 832                         rect.height = 1;
 833                         rect.width = FirstWidth[i];
 834                         rgn->Union(rect);
 835                     }
 836                     ptsOut = FirstPoint;
 837                     width = FirstWidth;
 838                     nPts = 0;
 839                 }
 840                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
 841                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
 842             }
 843             miInsertionSort(&AET);
 844         }
 845     }
 846     else      /* default to WindingNumber */
 847     {
 848         /*
 849          *  for each scanline
 850          */
 851         for (y = ET.ymin; y < ET.ymax; y++)
 852         {
 853             /*
 854              *  Add a new edge to the active edge table when we
 855              *  get to the next edge.
 856              */
 857             if (pSLL && y == pSLL->scanline)
 858             {
 859                 miloadAET(&AET, pSLL->edgelist);
 860                 micomputeWAET(&AET);
 861                 pSLL = pSLL->next;
 862             }
 863             pPrevAET = &AET;
 864             pAET = AET.next;
 865             pWETE = pAET;
 866
 867             /*
 868              *  for each active edge
 869              */
 870             while (pAET)
 871             {
 872                 /*
 873                  *  if the next edge in the active edge table is
 874                  *  also the next edge in the winding active edge
 875                  *  table.
 876                  */
 877                 if (pWETE == pAET)
 878                 {
 879                     ptsOut->x = pAET->bres.minor;
 880                     ptsOut++->y = y;
 881                     *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor;
 882                     nPts++;
 883
 884                     /*
 885                      *  send out the buffer
 886                      */
 887                     if (nPts == NUMPTSTOBUFFER)
 888                     {
 889                         // (*pgc->ops->FillSpans)(dst, pgc,
 890                         //     nPts, FirstPoint, FirstWidth,1);
 891                         for ( int i = 0 ; i < nPts ; ++i)
 892                         {
 893                             wxRect rect;
 894                             rect.y = FirstPoint[i].y;
 895                             rect.x = FirstPoint[i].x;
 896                             rect.height = 1;
 897                             rect.width = FirstWidth[i];
 898                             rgn->Union(rect);
 899                         }
 900                         ptsOut = FirstPoint;
 901                         width  = FirstWidth;
 902                         nPts = 0;
 903                     }
 904
 905                     pWETE = pWETE->nextWETE;
 906                     while (pWETE != pAET)
 907                         EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
 908                     pWETE = pWETE->nextWETE;
 909                 }
 910                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
 911             }
 912
 913             /*
 914              *  reevaluate the Winding active edge table if we
 915              *  just had to resort it or if we just exited an edge.
 916              */
 917             if (miInsertionSort(&AET) || fixWAET)
 918             {
 919                 micomputeWAET(&AET);
 920                 fixWAET = 0;
 921             }
 922         }
 923     }
 924
 925     /*
 926      *     Get any spans that we missed by buffering
 927      */
 928     // (*pgc->ops->FillSpans)(dst, pgc,
 929     //     nPts, FirstPoint, FirstWidth,1);
 930     for ( int i = 0 ; i < nPts; ++i)
 931     {
 932         wxRect rect;
 933         rect.y = FirstPoint[i].y;
 934         rect.x = FirstPoint[i].x;
 935         rect.height = 1;
 936         rect.width = FirstWidth[i];
 937         rgn->Union(rect);
 938     }
 939
 940     free(pETEs);
 941     miFreeStorage(SLLBlock.next);
 942     return(TRUE);
 943 }
 944
 945 #endif
 946
 947 wxRegion::wxRegion(size_t n, const wxPoint *points, wxPolygonFillMode fillStyle)
 948 {
 949     // Set the region to a polygon shape generically using a bitmap with the
 950     // polygon drawn on it.
 951
 952     m_refData = new wxRegionRefData();
 953
 954 #if OSX_USE_SCANLINES
 955     scanFillGeneralPoly(this,n,points,fillStyle);
 956 #else
 957     wxCoord mx = 0;
 958     wxCoord my = 0;
 959     wxPoint p;
 960     size_t idx;
 961
 962     // Find the max size needed to draw the polygon
 963     for (idx=0; idx<n; idx++)
 964     {
 965         wxPoint pt = points[idx];
 966         if (pt.x > mx)
 967             mx = pt.x;
 968         if (pt.y > my)
 969             my = pt.y;
 970     }
 971
 972     // Make the bitmap
 973     wxBitmap bmp(mx, my);
 974     wxMemoryDC dc(bmp);
 975     dc.SetBackground(*wxBLACK_BRUSH);
 976     dc.Clear();
 977     dc.SetPen(*wxWHITE_PEN);
 978     dc.SetBrush(*wxWHITE_BRUSH);
 979     dc.DrawPolygon(n, (wxPoint*)points, 0, 0, fillStyle);
 980     dc.SelectObject(wxNullBitmap);
 981     bmp.SetMask(new wxMask(bmp, *wxBLACK));
 982
 983     // Use it to set this region
 984     Union(bmp);
 985 #endif
 986 }
 987
 988 wxRegion::~wxRegion()
 989 {
 990     // m_refData unrefed in ~wxObject
 991 }
 992
 993 wxGDIRefData *wxRegion::CreateGDIRefData() const
 994 {
 995     return new wxRegionRefData;
 996 }
 997
 998 wxGDIRefData *wxRegion::CloneGDIRefData(const wxGDIRefData *data) const
 999 {
1000     return new wxRegionRefData(*static_cast<const wxRegionRefData *>(data));
1001 }
1002
1003 //-----------------------------------------------------------------------------
1004 //# Modify region
1005 //-----------------------------------------------------------------------------
1006
1007 //! Clear current region
1008 void wxRegion::Clear()
1009 {
1010     UnRef();
1011 }
1012
1013 // Move the region
1014 bool wxRegion::DoOffset(wxCoord x, wxCoord y)
1015 {
1016     wxCHECK_MSG( m_refData, false, wxT("invalid wxRegion") );
1017
1018     if ( !x && !y )
1019         // nothing to do
1020         return true;
1021
1022     AllocExclusive();
1023
1024     verify_noerr( HIShapeOffset( M_REGION , x , y ) ) ;
1025
1026     return true ;
1027 }
1028
1029 bool wxRegion::DoUnionWithRect(const wxRect& rect)
1030 {
1031     if ( !m_refData )
1032     {
1033         m_refData = new wxRegionRefData(rect.x , rect.y , rect.width , rect.height);
1034         return true;
1035     }
1036
1037     AllocExclusive();
1038
1039     CGRect r = CGRectMake(rect.x , rect.y , rect.width , rect.height);
1040     HIShapeUnionWithRect(M_REGION , &r);
1041
1042     return true;
1043 }
1044
1045 //! Union /e region with this.
1046 bool wxRegion::DoCombine(const wxRegion& region, wxRegionOp op)
1047 {
1048     wxCHECK_MSG( region.IsOk(), false, wxT("invalid wxRegion") );
1049
1050     // Handle the special case of not initialized (e.g. default constructed)
1051     // region as we can't use HIShape functions if we don't have any shape.
1052     if ( !m_refData )
1053     {
1054         switch ( op )
1055         {
1056             case wxRGN_COPY:
1057             case wxRGN_OR:
1058             case wxRGN_XOR:
1059                 // These operations make sense with a null region.
1060                 *this = region;
1061                 return true;
1062
1063             case wxRGN_AND:
1064             case wxRGN_DIFF:
1065                 // Those ones don't really make sense so just leave this region
1066                 // empty/invalid.
1067                 return false;
1068         }
1069
1070         wxFAIL_MSG( wxT("Unknown region operation") );
1071         return false;
1072     }
1073
1074     AllocExclusive();
1075
1076     switch (op)
1077     {
1078         case wxRGN_AND:
1079             verify_noerr( HIShapeIntersect( M_REGION , OTHER_M_REGION(region) , M_REGION ) );
1080             break ;
1081
1082         case wxRGN_OR:
1083             verify_noerr( HIShapeUnion( M_REGION , OTHER_M_REGION(region) , M_REGION ) );
1084             break ;
1085
1086         case wxRGN_XOR:
1087             {
1088                 // XOR is defined as the difference between union and intersection
1089                 wxCFRef< HIShapeRef > unionshape( HIShapeCreateUnion( M_REGION , OTHER_M_REGION(region) ) );
1090                 wxCFRef< HIShapeRef > intersectionshape( HIShapeCreateIntersection( M_REGION , OTHER_M_REGION(region) ) );
1091                 verify_noerr( HIShapeDifference( unionshape, intersectionshape, M_REGION ) );
1092             }
1093             break ;
1094
1095         case wxRGN_DIFF:
1096             verify_noerr( HIShapeDifference( M_REGION , OTHER_M_REGION(region) , M_REGION ) ) ;
1097             break ;
1098
1099         case wxRGN_COPY:
1100         default:
1101             M_REGION.reset( HIShapeCreateMutableCopy( OTHER_M_REGION(region) ) );
1102             break ;
1103     }
1104
1105     return true;
1106 }
1107
1108 //-----------------------------------------------------------------------------
1109 //# Information on region
1110 //-----------------------------------------------------------------------------
1111
1112 bool wxRegion::DoIsEqual(const wxRegion& region) const
1113 {
1114     // There doesn't seem to be any native function for checking the equality
1115     // of HIShapes so we compute their differences to determine if they are
1116     // equal.
1117     wxRegion r(*this);
1118     r.Subtract(region);
1119
1120     if ( !r.IsEmpty() )
1121         return false;
1122
1123     wxRegion r2(region);
1124     r2.Subtract(*this);
1125
1126     return r2.IsEmpty();
1127 }
1128
1129 // Outer bounds of region
1130 bool wxRegion::DoGetBox(wxCoord& x, wxCoord& y, wxCoord& w, wxCoord& h) const
1131 {
1132     if (m_refData)
1133     {
1134         CGRect box ;
1135         HIShapeGetBounds( M_REGION , &box ) ;
1136         x = static_cast<int>(box.origin.x);
1137         y = static_cast<int>(box.origin.y);
1138         w = static_cast<int>(box.size.width);
1139         h = static_cast<int>(box.size.height);
1140
1141         return true;
1142     }
1143     else
1144     {
1145         x = y = w = h = 0;
1146
1147         return false;
1148     }
1149 }
1150
1151 // Is region empty?
1152 bool wxRegion::IsEmpty() const
1153 {
1154     if ( m_refData )
1155         return HIShapeIsEmpty( M_REGION ) ;
1156     else
1157         return true ;
1158 }
1159
1160 WXHRGN wxRegion::GetWXHRGN() const
1161 {
1162     if ( !m_refData )
1163         return NULL;
1164
1165     return M_REGION ;
1166 }
1167
1168 //-----------------------------------------------------------------------------
1169 //# Tests
1170 //-----------------------------------------------------------------------------
1171
1172 // Does the region contain the point?
1173 wxRegionContain wxRegion::DoContainsPoint(wxCoord x, wxCoord y) const
1174 {
1175     if (!m_refData)
1176         return wxOutRegion;
1177
1178     CGPoint p = CGPointMake( x, y ) ;
1179     if (HIShapeContainsPoint( M_REGION , &p ) )
1180         return wxInRegion;
1181
1182     return wxOutRegion;
1183 }
1184
1185 // Does the region contain the rectangle (x, y, w, h)?
1186 wxRegionContain wxRegion::DoContainsRect(const wxRect& r) const
1187 {
1188     if (!m_refData)
1189         return wxOutRegion;
1190
1191     CGRect rect = CGRectMake(r.x,r.y,r.width,r.height);
1192     wxCFRef<HIShapeRef> rectshape(HIShapeCreateWithRect(&rect));
1193     wxCFRef<HIShapeRef> intersect(HIShapeCreateIntersection(rectshape,M_REGION));
1194     CGRect bounds;
1195     HIShapeGetBounds(intersect, &bounds);
1196
1197     if ( HIShapeIsRectangular(intersect) && CGRectEqualToRect(rect,bounds) )
1198         return wxInRegion;
1199     else if ( HIShapeIsEmpty( intersect ) )
1200         return wxOutRegion;
1201     else
1202         return wxPartRegion;
1203 }
1204
1205 ///////////////////////////////////////////////////////////////////////////////
1206 //                                                                           //
1207 //                               wxRegionIterator                            //
1208 //                                                                           //
1209 ///////////////////////////////////////////////////////////////////////////////
1210
1211 /*!
1212  * Initialize empty iterator
1213  */
1214 wxRegionIterator::wxRegionIterator()
1215     : m_current(0), m_numRects(0), m_rects(NULL)
1216 {
1217 }
1218
1219 wxRegionIterator::~wxRegionIterator()
1220 {
1221     wxDELETEA(m_rects);
1222 }
1223
1224 wxRegionIterator::wxRegionIterator(const wxRegionIterator& iterator)
1225     : wxObject()
1226     , m_current(iterator.m_current)
1227     , m_numRects(0)
1228     , m_rects(NULL)
1229 {
1230     SetRects(iterator.m_numRects, iterator.m_rects);
1231 }
1232
1233 wxRegionIterator& wxRegionIterator::operator=(const wxRegionIterator& iterator)
1234 {
1235     m_current  = iterator.m_current;
1236     SetRects(iterator.m_numRects, iterator.m_rects);
1237
1238     return *this;
1239 }
1240
1241 /*!
1242  * Set iterator rects for region
1243  */
1244 void wxRegionIterator::SetRects(long numRects, wxRect *rects)
1245 {
1246     wxDELETEA(m_rects);
1247
1248     if (rects && (numRects > 0))
1249     {
1250         int i;
1251
1252         m_rects = new wxRect[numRects];
1253         for (i = 0; i < numRects; i++)
1254             m_rects[i] = rects[i];
1255     }
1256
1257     m_numRects = numRects;
1258 }
1259
1260 /*!
1261  * Initialize iterator for region
1262  */
1263 wxRegionIterator::wxRegionIterator(const wxRegion& region)
1264 {
1265     m_rects = NULL;
1266
1267     Reset(region);
1268 }
1269
1270 /*!
1271  * Reset iterator for a new /e region.
1272  */
1273
1274 class RegionToRectsCallbackData
1275 {
1276 public :
1277     wxRect* m_rects ;
1278     long m_current ;
1279 };
1280
1281 OSStatus wxOSXRegionToRectsCounterCallback(
1282     int message, HIShapeRef WXUNUSED(region), const CGRect *WXUNUSED(rect), void *data )
1283 {
1284     long *m_numRects = (long*) data ;
1285     if ( message == kHIShapeEnumerateInit )
1286     {
1287         (*m_numRects) = 0 ;
1288     }
1289     else if (message == kHIShapeEnumerateRect)
1290     {
1291         (*m_numRects) += 1 ;
1292     }
1293
1294     return noErr;
1295 }
1296
1297 OSStatus wxOSXRegionToRectsSetterCallback(
1298     int message, HIShapeRef WXUNUSED(region), const CGRect *rect, void *data )
1299 {
1300     if (message == kHIShapeEnumerateRect)
1301     {
1302         RegionToRectsCallbackData *cb = (RegionToRectsCallbackData*) data ;
1303         cb->m_rects[cb->m_current++] = wxRect( rect->origin.x , rect->origin.y , rect->size.width , rect->size.height ) ;
1304     }
1305
1306     return noErr;
1307 }
1308
1309 void wxRegionIterator::Reset(const wxRegion& region)
1310 {
1311     m_current = 0;
1312     m_region = region;
1313
1314     wxDELETEA(m_rects);
1315
1316     if (m_region.IsEmpty())
1317     {
1318         m_numRects = 0;
1319     }
1320     else
1321     {
1322 #if 0
1323         // fallback code in case we ever need it again
1324         // copying this to a path and dissecting the path would be an option
1325         m_numRects = 1;
1326         m_rects = new wxRect[m_numRects];
1327         m_rects[0] = m_region.GetBox();
1328 #endif
1329         OSStatus err = HIShapeEnumerate (OTHER_M_REGION(region), kHIShapeParseFromTopLeft, wxOSXRegionToRectsCounterCallback,
1330             (void*)&m_numRects);
1331         if (err == noErr)
1332         {
1333             m_rects = new wxRect[m_numRects];
1334             RegionToRectsCallbackData data ;
1335             data.m_rects = m_rects ;
1336             data.m_current = 0 ;
1337             HIShapeEnumerate( OTHER_M_REGION(region), kHIShapeParseFromTopLeft, wxOSXRegionToRectsSetterCallback,
1338                 (void*)&data );
1339         }
1340         else
1341         {
1342             m_numRects = 0;
1343         }
1344     }
1345 }
1346
1347 /*!
1348  * Increment iterator. The rectangle returned is the one after the
1349  * incrementation.
1350  */
1351 wxRegionIterator& wxRegionIterator::operator ++ ()
1352 {
1353     if (m_current < m_numRects)
1354         ++m_current;
1355
1356     return *this;
1357 }
1358
1359 /*!
1360  * Increment iterator. The rectangle returned is the one before the
1361  * incrementation.
1362  */
1363 wxRegionIterator wxRegionIterator::operator ++ (int)
1364 {
1365     wxRegionIterator previous(*this);
1366
1367     if (m_current < m_numRects)
1368         ++m_current;
1369
1370     return previous;
1371 }
1372
1373 long wxRegionIterator::GetX() const
1374 {
1375     if (m_current < m_numRects)
1376         return m_rects[m_current].x;
1377
1378     return 0;
1379 }
1380
1381 long wxRegionIterator::GetY() const
1382 {
1383     if (m_current < m_numRects)
1384         return m_rects[m_current].y;
1385
1386     return 0;
1387 }
1388
1389 long wxRegionIterator::GetW() const
1390 {
1391     if (m_current < m_numRects)
1392         return m_rects[m_current].width ;
1393
1394     return 0;
1395 }
1396
1397 long wxRegionIterator::GetH() const
1398 {
1399     if (m_current < m_numRects)
1400         return m_rects[m_current].height;
1401
1402     return 0;
1403 }
1404
1405 #endif