src/Clip.c

   1 /*
   2  * Copyright (c) 1998 by The XFree86 Project, Inc.
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  17  * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  18  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  19  * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  *
  22  * Except as contained in this notice, the name of the XFree86 Project shall
  23  * not be used in advertising or otherwise to promote the sale, use or other
  24  * dealings in this Software without prior written authorization from the
  25  * XFree86 Project.
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include <config.h>
  30 #endif
  31 #include <stdlib.h>
  32
  33 #include <X11/IntrinsicP.h>
  34 #include <X11/Xmu/Xmu.h>
  35
  36 #define XmuMax(a, b)    ((a) > (b) ? (a) : (b))
  37 #define XmuMin(a, b)    ((a) < (b) ? (a) : (b))
  38
  39 /*
  40  * Function:
  41  *      XmuNewArea
  42  *
  43  * Parameters:
  44  *      x1 - Coordinates of the rectangle
  45  *      y1 - ""
  46  *      x2 - ""
  47  *      y2 - ""
  48  *
  49  * Description:
  50  *      Creates a new rectangular clipping area
  51  */
  52 XmuArea *
  53 XmuNewArea(int x1, int y1, int x2, int y2)
  54 {
  55   XmuArea *area;
  56
  57   area = (XmuArea *)XtMalloc(sizeof(XmuArea));
  58   if (x2 > x1 && y2 > y1)
  59     {
  60       area->scanline = XmuNewScanline(y1, x1, x2);
  61       area->scanline->next = XmuNewScanline(y2, 0, 0);
  62     }
  63   else
  64     area->scanline = (XmuScanline *)NULL;
  65
  66   return (area);
  67 }
  68
  69 /*
  70  * Function:
  71  *      XmuAreaDup
  72  *
  73  * Parameters:
  74  *      area - Area to copy
  75  *
  76  * Description:
  77  *      Returns a copy of its argument
  78  */
  79 XmuArea *
  80 XmuAreaDup(XmuArea *area)
  81 {
  82   XmuArea *dst;
  83
  84   if (!area)
  85     return ((XmuArea *)NULL);
  86
  87   dst = XmuCreateArea();
  88   XmuAreaCopy(dst, area);
  89   return (dst);
  90 }
  91
  92 /*
  93  * Function:
  94  *      XmuAreaCopy
  95  *
  96  * Parameters:
  97  *      dst - destination area
  98  *      src - source area
  99  *
 100  * Description:
 101  *      Minimizes memory alocation, trying to use already alocated memory
 102  *      in dst, freeing what is not required anymore.
 103  */
 104 XmuArea *
 105 XmuAreaCopy(XmuArea *dst, XmuArea *src)
 106 {
 107   XmuScanline *z, *p, *Z;
 108
 109   if (!dst || !src || dst == src)
 110     return (dst);
 111
 112   z = p = dst->scanline;
 113   Z = src->scanline;
 114
 115   /*CONSTCOND*/
 116   while (1)
 117     {
 118       if (!Z)
 119         {
 120           if (z == dst->scanline)
 121             {
 122               XmuDestroyScanlineList(dst->scanline);
 123               dst->scanline = (XmuScanline *)NULL;
 124             }
 125           else
 126             {
 127               XmuDestroyScanlineList(p->next);
 128               p->next = (XmuScanline *)NULL;
 129             }
 130           return (dst);
 131         }
 132       if (z)
 133         {
 134           XmuScanlineCopy(z, Z);
 135           z->y = Z->y;
 136         }
 137       else
 138         {
 139           z = XmuNewScanline(Z->y, 0, 0);
 140           XmuScanlineCopy(z, Z);
 141           if (p == dst->scanline && !dst->scanline)
 142             p = dst->scanline = z;
 143           else
 144             p->next = z;
 145         }
 146       p = z;
 147       z = z->next;
 148       Z = Z->next;
 149     }
 150
 151   return (dst);
 152 }
 153
 154 /*
 155  * Function:
 156  *   XmuAreaNot
 157  *
 158  * Parameters:
 159  *      area - area to operate
 160  *      x1   - retangle to clip the result against
 161  *      y1   - ""
 162  *      x2   - ""
 163  *      y2   - ""
 164  *
 165  * Description:
 166  * (Input)
 167  * (x1, y1)                                                (x2, y1)
 168  *                   +-------------+
 169  *      +------------+             +----+
 170  *      |                +--------------+
 171  *      +----------------+
 172  * (x1, y2)                                                (x2, y2)
 173  *
 174  * (Output)
 175  * (x1, y1)                                                (x2, y1)
 176  *    +--------------+             +--------------------------+
 177  *    | +------------+             +----+                     |
 178  *    | |                +--------------+                     |
 179  *    +-+                +------------------------------------+
 180  * (x1, y2)                                                (x2, y2)
 181  */
 182 XmuArea *
 183 XmuAreaNot(XmuArea *area, int x1, int y1, int x2, int y2)
 184 {
 185   XmuScanline *z;
 186   XmuArea *and;
 187
 188   if (!area)
 189     return (area);
 190
 191   if (x1 > x2)
 192     {
 193       x1 ^= x2; x2 ^= x1; x1 ^= x2;
 194     }
 195     if (y1 > y2)
 196       {
 197         y1 ^= y2; y2 ^= y1; y1 ^= y2;
 198       }
 199     if (!area->scanline)
 200       {
 201         if ((area->scanline = XmuNewScanline(y1, x1, x2)) != NULL)
 202           area->scanline->next = XmuNewScanline(y2, 0, 0);
 203         return (area);
 204       }
 205     and = XmuNewArea(x1, y1, x2, y2);
 206     XmuAreaAnd(area, and);
 207     XmuDestroyArea(and);
 208     z = area->scanline;
 209     if (z->y != y1)
 210       {
 211         XmuScanline *q = XmuNewScanline(y1, x1, x2);
 212         q->next = z;
 213         area->scanline = q;
 214       }
 215     else
 216       {
 217         area->scanline = area->scanline->next;
 218         XmuDestroyScanline(z);
 219         XmuOptimizeArea(area);
 220         if((z = area->scanline) == (XmuScanline *)NULL)
 221           return (area);
 222       }
 223
 224     /* CONSTCOND */
 225     while (1)
 226       {
 227         XmuScanlineNot(z, x1, x2);
 228         if (!z->next)
 229           {
 230             z->next = XmuNewScanline(y2, 0, 0);
 231             break;
 232           }
 233         if (z->next->y == y2)
 234           {
 235             XmuDestroyScanlineList(z->next);
 236             z->next = XmuNewScanline(y2, 0, 0);
 237             break;
 238           }
 239         z = z->next;
 240       }
 241
 242     return (area);
 243 }
 244
 245 /*
 246  * Function:
 247  *      XmuAreaOrXor
 248  *
 249  * Parameters:
 250  *      dst - destination area
 251  *      src - source area
 252  *      or  - or operation if true, else xor operation
 253  *
 254  * Description:
 255  *      Executes Or (Union) or Xor (Reverse intesection) of the areas
 256  */
 257 XmuArea *
 258 XmuAreaOrXor(XmuArea *dst, XmuArea *src, Bool or)
 259 {
 260   XmuScanline *z, *p, *Z, *P, *ins, *top;
 261
 262   if (!dst || !src)
 263     return (dst);
 264
 265   if (dst == src)
 266     {
 267       if (or)
 268         return (dst);
 269       XmuDestroyScanlineList(dst->scanline);
 270       dst->scanline = (XmuScanline *)NULL;
 271       return (dst);
 272     }
 273   if (!XmuValidArea(src))
 274     return (dst);
 275   if (!XmuValidArea(dst))
 276     {
 277       XmuAreaCopy(dst, src);
 278       return (dst);
 279     }
 280
 281   p = z = dst->scanline;
 282   P = Z = src->scanline;
 283   ins = XmuNewScanline(dst->scanline->y, 0, 0);
 284   top = XmuNewScanline(dst->scanline->y, 0, 0);
 285   XmuScanlineCopy(ins, dst->scanline);
 286   XmuScanlineCopy(top, dst->scanline);
 287
 288   /*CONSTCOND*/
 289   while (1)
 290     {
 291       if (!Z)
 292         break;
 293       else if (Z->y < z->y)
 294         {
 295           XmuScanline  *q = XmuNewScanline(Z->y, 0, 0);
 296           XmuScanlineCopy(q, Z);
 297
 298           if (z == dst->scanline)
 299             {
 300               dst->scanline = p = q;
 301               q->next = z;
 302             }
 303           else
 304             {
 305               p->next = q;
 306               q->next = z;
 307               if (Z->y >= p->y)
 308                 {
 309                   if (ins->y >= top->y
 310                       && (p->y != P->y || !XmuScanlineEqu(p, P)
 311                           || (ins->y <= P->y && !XmuScanlineEqu(ins, P))))
 312                     {
 313                       if (or)
 314                         XmuScanlineOr(q, ins);
 315                       else
 316                         XmuScanlineXor(q, ins);
 317                     }
 318                   else if (Z->y >= top->y
 319                            && (top->y == p->y || top->y > ins->y
 320                                || !XmuValidScanline(Z)
 321                                || (p->y == P->y && XmuValidScanline(p)
 322                                    && XmuValidScanline(P))
 323                                || XmuScanlineEqu(ins, top)))
 324                     {
 325                       if (or)
 326                         XmuScanlineOr(q, top);
 327                       else
 328                         XmuScanlineXor(q, top);
 329                     }
 330                   if (ins->y != p->y && p->y != P->y)
 331                     {
 332                       XmuScanlineCopy(ins, p);
 333                       ins->y = p->y;
 334                     }
 335                 }
 336               if (!XmuValidScanline(p) || Z->y <= p->y)
 337                 {
 338                   XmuScanlineCopy(top, p);
 339                   top->y = p->y;
 340                 }
 341               p = q;
 342             }
 343           P = Z;
 344           Z = Z->next;
 345           continue;
 346         }
 347       else if (Z->y == z->y)
 348         {
 349           if (top->y != z->y)
 350             {
 351               XmuScanlineCopy(top, z);
 352               top->y = z->y;
 353             }
 354           if (or)
 355             XmuScanlineOr(z, Z);
 356           else
 357             XmuScanlineXor(z, Z);
 358           P = Z;
 359           Z = Z->next;
 360         }
 361       else if (P != Z)          /* && Z->y > z->y */
 362         {
 363           if (top->y == ins->y && top->y != z->y)
 364             {
 365               XmuScanlineCopy(top, z);
 366               top->y = z->y;
 367             }
 368           if (ins->y != z->y)
 369             {
 370               XmuScanlineCopy(ins, z);
 371               ins->y = z->y;
 372             }
 373           if (or)
 374             XmuScanlineOr(z, P);
 375           else
 376             XmuScanlineXor(z, P);
 377         }
 378       else if (ins->y != z->y)
 379         {
 380           XmuScanlineCopy(ins, z);
 381           ins->y = z->y;
 382         }
 383       p = z;
 384       z = z->next;
 385       if (!z)
 386         {
 387           while (Z)
 388             {
 389               p->next = XmuNewScanline(Z->y, 0, 0);
 390               XmuScanlineCopy(p->next, Z);
 391               p = p->next;
 392               Z = Z->next;
 393             }
 394           break;
 395         }
 396       else if (ins->y > top->y && !XmuValidScanline(z)
 397                && XmuValidScanline(ins))
 398         {
 399           XmuScanlineCopy(top, ins);
 400           top->y = ins->y;
 401         }
 402     }
 403   XmuOptimizeArea(dst);
 404   XmuDestroyScanline(ins);
 405   XmuDestroyScanline(top);
 406
 407   return (dst);
 408 }
 409
 410 /*
 411  * Function:
 412  *      XmuAreaAnd(dst, src)
 413  *
 414  * Parameters:
 415  *      dst - destination area
 416  *      src - source area
 417  *
 418  * Description:
 419  *      Executes And (intersection) of the areas
 420  */
 421 XmuArea *
 422 XmuAreaAnd(XmuArea *dst, XmuArea *src)
 423 {
 424   XmuScanline *z, *p, *Z, *P, *top;
 425
 426   if (!dst || !src || dst == src)
 427     return (dst);
 428   if (!XmuValidArea(dst) || !XmuValidArea(src))
 429     {
 430       XmuDestroyScanlineList(dst->scanline);
 431       dst->scanline = (XmuScanline *)NULL;
 432       return (dst);
 433     }
 434   z = p = dst->scanline;
 435   Z = P = src->scanline;
 436   top = XmuNewScanline(dst->scanline->y, 0, 0);
 437   XmuScanlineCopy(top, dst->scanline);
 438
 439   while (z)
 440     {
 441       while (Z->next && Z->next->y < z->y)
 442         {
 443           P = Z;
 444           Z = Z->next;
 445           if (Z->y >= p->y)
 446             {
 447               XmuScanline *q = XmuNewScanline(Z->y, 0, 0);
 448               XmuScanlineCopy(q, Z);
 449
 450               XmuScanlineAnd(q, top);
 451               if (p->y != P->y)
 452                 {
 453                   XmuScanlineAnd(p, P);
 454                   p->y = XmuMax(p->y, P->y);
 455                 }
 456               p->next = q;
 457               q->next = z;
 458               p = q;
 459             }
 460         }
 461       if (!z->next)
 462         {
 463           z->y = XmuMax(z->y, Z->y);
 464           break;
 465         }
 466       while (Z->y >= z->next->y)
 467         {
 468           if (z == dst->scanline)
 469             {
 470               p = dst->scanline = dst->scanline->next;
 471               XmuDestroyScanline(z);
 472               z = dst->scanline;
 473             }
 474           else
 475             {
 476               p->next = z->next;
 477               XmuDestroyScanline(z);
 478               z = p;
 479             }
 480           if (!z || !z->next)
 481             {
 482               XmuOptimizeArea(dst);
 483               XmuDestroyScanline(top);
 484
 485               return (dst);
 486             }
 487         }
 488       if (Z->y > p->y)
 489         z->y = XmuMax(z->y, Z->y);
 490       if (top->y != z->y)
 491         {
 492           XmuScanlineCopy(top, z);
 493           top->y = z->y;
 494         }
 495       XmuScanlineAnd(z, Z);
 496       p = z;
 497       z = z->next;
 498     }
 499   XmuOptimizeArea(dst);
 500   XmuDestroyScanline(top);
 501
 502   return (dst);
 503 }
 504
 505 /*
 506  * Function:
 507  *   XmuValidArea(area)
 508  *
 509  * Parameters:
 510  *      area - area to verify
 511  *
 512  * Description:
 513  *      Verifies if the area is valid and/or useful
 514  */
 515 Bool
 516 XmuValidArea(XmuArea *area)
 517 {
 518   XmuScanline *at;
 519
 520   if (!area || !area->scanline)
 521     return (False);
 522
 523   at = area->scanline;
 524   while (at)
 525     {
 526       if (XmuValidScanline(at))
 527         return (True);
 528       at = at->next;
 529     }
 530
 531   return (False);
 532 }
 533
 534 /*
 535  * Function:
 536  *      XmuValidScanline
 537  *
 538  * Parameters:
 539  *      scanline - scanline to verify
 540  *
 541  * Description:
 542  *      Verifies if a scanline is useful
 543  */
 544 Bool
 545 XmuValidScanline(XmuScanline *scanline)
 546 {
 547   XmuSegment *z;
 548
 549   if (!scanline)
 550     return (False);
 551
 552   z = scanline->segment;
 553   while (z)
 554     {
 555       if (XmuValidSegment(z))
 556         return (True);
 557       z = z->next;
 558     }
 559
 560   return (False);
 561 }
 562
 563 /*
 564  * Function:
 565  *   XmuScanlineEqu
 566  *
 567  * Parameters:
 568  *      s1 - scanline 1
 569  *      s2 - scanline 2
 570  *
 571  * Description:
 572  *      Checks if s1 and s2 are equal
 573  */
 574 Bool
 575 XmuScanlineEqu(XmuScanline *s1, XmuScanline *s2)
 576 {
 577   XmuSegment *z, *Z;
 578
 579   if ((!s1 && !s2) || s1 == s2)
 580     return (True);
 581   if (!s1 || !s2)
 582     return (False);
 583
 584   z = s1->segment;
 585   Z = s2->segment;
 586
 587   /*CONSTCOND*/
 588   while (1)
 589     {
 590       if (!z && !Z)
 591         return (True);
 592       if (!z || !Z)
 593         return (False);
 594       if (!XmuSegmentEqu(z, Z))
 595         return (False);
 596       z = z->next;
 597       Z = Z->next;
 598     }
 599   /*NOTREACHED*/
 600 }
 601
 602 /*
 603  * Function:
 604  *      XmuNewSegment
 605  *
 606  * Parameters:
 607  *      x1 - coordinates of the segment
 608  *      x2 - ""
 609  *
 610  * Description:
 611  *      Creates a new segments with the coordinates x1 and x2
 612  *
 613  * Returns:
 614  *      New Segment of NULL
 615  */
 616 XmuSegment *
 617 XmuNewSegment(int x1, int x2)
 618 {
 619   XmuSegment *segment;
 620
 621   if ((segment = (XmuSegment *)XtMalloc(sizeof(XmuSegment))) == NULL)
 622     return (segment);
 623
 624   segment->x1 = x1;
 625   segment->x2 = x2;
 626   segment->next = (XmuSegment *)NULL;
 627
 628   return (segment);
 629 }
 630
 631 /*
 632  * Function:
 633  *      XmuDestroySegmentList
 634  *
 635  * Parameters:
 636  *      segment - Segment to destroy
 637  *
 638  * Description:
 639  *      Frees the memory used by the list headed by segment
 640  */
 641 void
 642 XmuDestroySegmentList(XmuSegment *segment)
 643 {
 644   XmuSegment *z;
 645
 646   if (!segment)
 647     return;
 648
 649   while (segment)
 650     {
 651       z = segment;
 652       segment = segment->next;
 653       XmuDestroySegment(z);
 654     }
 655 }
 656
 657 /*
 658  * Function:
 659  *      XmuScanlineCopy
 660  *
 661  * Parameters:
 662  *      dst - destination scanline
 663  *      src - source scanline
 664  *
 665  * Description:
 666  *      Makes dst contain the same data as src
 667  */
 668 XmuScanline *
 669 XmuScanlineCopy(XmuScanline *dst, XmuScanline *src)
 670 {
 671   XmuSegment *z, *p, *Z;
 672
 673   if (!dst || !src || dst == src)
 674     return (dst);
 675
 676   z = p = dst->segment;
 677   Z = src->segment;
 678
 679   /*CONSTCOND*/
 680   while (1)
 681     {
 682       if (!Z)
 683         {
 684           if (z == dst->segment)
 685             dst->segment = (XmuSegment *)NULL;
 686           else
 687             p->next = (XmuSegment *)NULL;
 688           XmuDestroySegmentList(z);
 689           return (dst);
 690         }
 691       if (z)
 692         {
 693           z->x1 = Z->x1;
 694           z->x2 = Z->x2;
 695         }
 696       else
 697         {
 698           z = XmuNewSegment(Z->x1, Z->x2);
 699           if (p == dst->segment && !dst->segment)
 700             p = dst->segment = z;
 701           else
 702             p->next = z;
 703         }
 704       p = z;
 705       z = z->next;
 706       Z = Z->next;
 707     }
 708   /*NOTREACHED*/
 709 }
 710
 711 /*
 712  * Function:
 713  *      XmuAppendSegment
 714  *
 715  * Parameters:
 716  *      segment - destination segment
 717  *      append  - segment to add
 718  *
 719  * Description:
 720  *      Adds a copy of the append list at the end of the segment list
 721  */
 722 Bool
 723 XmuAppendSegment(XmuSegment *segment, XmuSegment *append)
 724 {
 725   if (!segment || !append)
 726     return (False);
 727
 728   if (segment->next)
 729     /* Should not happen! */
 730     XmuDestroySegmentList(segment->next);
 731
 732   while (append)
 733     {
 734       if (XmuValidSegment(append))
 735         {
 736           if ((segment->next = XmuNewSegment(append->x1, append->x2)) == NULL)
 737             return (False);
 738           segment = segment->next;
 739         }
 740       append = append->next;
 741     }
 742
 743   return (True);
 744 }
 745
 746 /*
 747  * Function:
 748  *      XmuOptimizeScanline
 749  *
 750  * Parameters:
 751  *      scanline - scanline to optimize
 752  *
 753  * Description:
 754  *        Some functions, when transforming Segments of Scanlines, left these
 755  *      with unnecessary data (that may cause error in these same functions).
 756  *        This function corrects these incorrect segments.
 757  */
 758 XmuScanline *
 759 XmuOptimizeScanline(XmuScanline *scanline)
 760 {
 761   XmuSegment *z, *p;
 762
 763   while (scanline->segment && !XmuValidSegment(scanline->segment))
 764     {
 765       XmuSegment *s = scanline->segment;
 766
 767       scanline->segment = scanline->segment->next;
 768       XmuDestroySegment(s);
 769     }
 770   for (z = p = scanline->segment; z; p = z, z = z->next)
 771     {
 772       if (!XmuValidSegment(z))
 773         {
 774           p->next = z->next;
 775           XmuDestroySegment(z);
 776           z = p;
 777         }
 778     }
 779   return (scanline);
 780 }
 781
 782 /*
 783  * Name:
 784  *      XmuScanlineNot(scanline, minx, maxx)
 785  *
 786  * Parameters:
 787  *      scanline - scanlines operate
 788  *      minx     - minimum x coordinate
 789  *      maxx     - maximum x coordinate
 790  *
 791  * Description:
 792  *         (minx)                                                        (maxx)
 793  *           +                                                             +
 794  * (input)         +---------+     +--------+        +--------+
 795  * (output)  +-----+         +-----+        +--------+        +------------+
 796  */
 797 XmuScanline *
 798 XmuScanlineNot(XmuScanline *scanline, int minx, int maxx)
 799 {
 800   XmuSegment *z;
 801   static XmuSegment x = { 0, 0, NULL };
 802   static XmuScanline and = { 0, &x, NULL };
 803
 804   if (!scanline)
 805     return (scanline);
 806
 807   XmuOptimizeScanline(scanline);
 808   if (minx > maxx)
 809     {
 810       minx ^= maxx; maxx ^= minx; minx ^= maxx;
 811     }
 812   and.segment->x1 = minx;
 813   and.segment->x2 = maxx;
 814   XmuScanlineAnd(scanline, &and);
 815   if (!scanline->segment)
 816     {
 817       scanline->segment = XmuNewSegment(minx, maxx);
 818       return (scanline);
 819     }
 820   z = scanline->segment;
 821   if (z->x1 != minx)
 822     {
 823       XmuSegment *q = XmuNewSegment(minx, z->x1);
 824
 825       q->next = z;
 826       scanline->segment = q;
 827     }
 828
 829   /*CONSTCOND*/
 830   while (1)
 831     {
 832       z->x1 = z->x2;
 833       if (!z->next)
 834         {
 835           z->x2 = maxx;
 836           break;
 837         }
 838       z->x2 = z->next->x1;
 839       if (z->next->x2 == maxx)
 840         {
 841           XmuDestroySegment(z->next);
 842           z->next = (XmuSegment *)NULL;
 843           break;
 844         }
 845       z = z->next;
 846     }
 847
 848   return (scanline);
 849 }
 850
 851
 852 #ifndef notdef
 853 /*
 854  * Function:
 855  *      XmuScanlineOrSegment
 856  *
 857  * Parameters:
 858  *      dst - destionation scanline
 859  *      src - source segment
 860  *
 861  * Description:
 862  * (input)      +-----------+  +--------+    +---------+
 863  * (src)              +-------------------+
 864  * (output)     +-------------------------+  +---------+
 865  */
 866 XmuScanline *
 867 XmuScanlineOrSegment(XmuScanline *dst, XmuSegment *src)
 868 {
 869   XmuSegment *z, *p, ins;
 870
 871   if (!src || !dst || !XmuValidSegment(src))
 872     return (dst);
 873
 874   if (!dst->segment)
 875     {
 876       dst->segment = XmuNewSegment(src->x1, src->x2);
 877       return (dst);
 878     }
 879
 880   z = p = dst->segment;
 881   ins.x1 = src->x1;
 882   ins.x2 = src->x2;
 883
 884   /*CONSTCOND*/
 885   while (1)
 886     {
 887       if (!z)
 888         {
 889             XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
 890
 891             if (p == dst->segment && z == p)
 892               dst->segment = q;
 893             else
 894               p->next = q;
 895             break;
 896         }
 897       else if (ins.x2 < z->x1)
 898         {
 899           XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
 900
 901           if (p == dst->segment && z == p)
 902             {
 903               q->next = dst->segment;
 904               dst->segment = q;
 905             }
 906           else
 907             {
 908               p->next = q;
 909               q->next = z;
 910             }
 911           break;
 912         }
 913       else if (ins.x2 <= z->x2)
 914         {
 915           z->x1 = XmuMin(z->x1, ins.x1);
 916           break;
 917         }
 918       else if (ins.x1 <= z->x2)
 919         {
 920           ins.x1 = XmuMin(z->x1, ins.x1);
 921           if (!z->next)
 922             {
 923               z->x1 = ins.x1;
 924               z->x2 = ins.x2;
 925               break;
 926             }
 927           else
 928             {
 929               if (z == dst->segment)
 930                 {
 931                   p = dst->segment = dst->segment->next;
 932                   XmuDestroySegment(z);
 933                   z = dst->segment;
 934                   continue;
 935                 }
 936               else
 937                 {
 938                   p->next = z->next;
 939                   XmuDestroySegment(z);
 940                   z = p;
 941                 }
 942             }
 943         }
 944       p = z;
 945       z = z->next;
 946     }
 947
 948   return (dst);
 949 }
 950
 951 /*
 952  * Function:
 953  *      XmuScanlineAndSegment
 954  *
 955  * Parameters:
 956  *      dst - destination scanline
 957  *      src - source segment
 958  *
 959  * Description:
 960  * (input)      +------------+   +------+     +----------+
 961  * (src)             +---------------------+
 962  * (output)          +-------+   +------+
 963  */
 964 XmuScanline *
 965 XmuScanlineAndSegment(XmuScanline *dst, XmuSegment *src)
 966 {
 967   XmuSegment *z, *p;
 968
 969   if (!dst || !src)
 970     return (dst);
 971
 972   if (!XmuValidSegment(src))
 973     {
 974       XmuDestroySegmentList(dst->segment);
 975       dst->segment = (XmuSegment *)NULL;
 976       return (dst);
 977     }
 978   if (!dst->segment)
 979     return (dst);
 980
 981   z = p = dst->segment;
 982   while (z)
 983     {
 984       if (src->x2 <= z->x1 || src->x1 >= z->x2)
 985         {
 986           if (z == dst->segment)
 987             {
 988               p = dst->segment = dst->segment->next;
 989               XmuDestroySegment(z);
 990               z = dst->segment;
 991               continue;
 992             }
 993           else
 994             {
 995               p->next = z->next;
 996               XmuDestroySegment(z);
 997               z = p;
 998             }
 999         }
1000       else
1001         {
1002           z->x1 = XmuMax(z->x1, src->x1);
1003           z->x2 = XmuMin(z->x2, src->x2);
1004         }
1005       p = z;
1006       z = z->next;
1007     }
1008
1009   return (dst);
1010 }
1011
1012 /*
1013  * Function:
1014  *      XmuScanlineXorSegment
1015  *
1016  * Parameters:
1017  *      dst - destionation scanline
1018  *      src - source segment
1019  *
1020  * Descriptipn:
1021  * (input)     +------------+  +----------+    +-----------+
1022  * (src)           +------------------------+
1023  * (output)    +---+        +--+          +-+  +-----------+
1024  */
1025 XmuScanline *
1026 XmuScanlineXorSegment(XmuScanline *dst, XmuSegment *src)
1027 {
1028   XmuSegment *p, *z, ins;
1029   int tmp1, tmp2;
1030
1031   if (!dst || !src || !XmuValidSegment(src))
1032     return (dst);
1033   if (!dst->segment)
1034     {
1035       dst->segment = XmuNewSegment(src->x1, src->x2);
1036       return (dst);
1037     }
1038
1039   p = z = dst->segment;
1040   ins.x1 = src->x1;
1041   ins.x2 = src->x2;
1042
1043   /*CONSTCOND*/
1044   while (1)
1045     {
1046       if (!XmuValidSegment((&ins)))
1047         break;
1048       if (!z || ins.x2 < z->x1)
1049         {
1050           XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1051
1052           q->next = z;
1053           if (z == dst->segment)
1054             dst->segment = q;
1055           else
1056             p->next = q;
1057           break;
1058         }
1059       else if (ins.x2 == z->x1)
1060         {
1061           z->x1 = ins.x1;
1062           break;
1063         }
1064       else if (ins.x1 < z->x2)
1065         {
1066           if (ins.x1 < z->x1)
1067             {
1068               tmp1 = ins.x2;
1069               tmp2 = z->x2;
1070               ins.x2 = XmuMax(ins.x2, z->x2);
1071               z->x2 = z->x1;
1072               z->x1 = ins.x1;
1073               ins.x1 = XmuMin(tmp1, tmp2);
1074             }
1075           else if (ins.x1 > z->x1)
1076             {
1077               tmp1 = ins.x1;
1078               ins.x1 = XmuMin(ins.x2, z->x2);
1079               ins.x2 = XmuMax(z->x2, ins.x2);
1080               z->x2 = tmp1;
1081             }
1082           else  /* ins.x1 == z->x1 */
1083             {
1084               if (ins.x2 < z->x2)
1085                 {
1086                   z->x1 = ins.x2;
1087                   break;
1088                 }
1089               else
1090                 {
1091                   ins.x1 = z->x2;
1092                   if (z == dst->segment)
1093                     p = dst->segment = dst->segment->next;
1094                   else
1095                     p->next = z->next;
1096                   XmuDestroySegment(z);
1097                   z = p;
1098                   continue;
1099                 }
1100             }
1101         }
1102       else if (ins.x1 == z->x2)
1103         {
1104           ins.x1 = z->x1;
1105           if (z == dst->segment)
1106             p = dst->segment = dst->segment->next;
1107           else
1108             p->next = z->next;
1109           XmuDestroySegment(z);
1110           z = p;
1111           continue;
1112         }
1113       p = z;
1114       z = z->next;
1115     }
1116
1117   return (dst);
1118 }
1119 #endif /* notdef */
1120
1121 /*
1122  * Function:
1123  *      ScanlineOr
1124  *
1125  * Parameters:
1126  *      dst - destionation scanline
1127  *      src - source scanline
1128  *
1129  * Description:
1130  * (input)    +--------------+  +-----+    +----------+
1131  * (src)          +---------------------+       +-----------+
1132  * (output)   +-------------------------+  +----------------+
1133  */
1134 XmuScanline *
1135 XmuScanlineOr(XmuScanline *dst, XmuScanline *src)
1136 {
1137   XmuSegment *z, *p, *Z, ins;
1138
1139   if (!src || !src->segment || !dst || dst == src)
1140     return (dst);
1141   if (!dst->segment)
1142     {
1143       XmuScanlineCopy(dst, src);
1144       return (dst);
1145     }
1146
1147   z = p = dst->segment;
1148   Z = src->segment;
1149   ins.x1 = Z->x1;
1150   ins.x2 = Z->x2;
1151
1152   /*CONSTCOND*/
1153   while (1)
1154     {
1155       while (!XmuValidSegment((&ins)))
1156         {
1157           if ((Z = Z->next) == (XmuSegment *)NULL)
1158             return (dst);
1159           ins.x1 = Z->x1;
1160           ins.x2 = Z->x2;
1161         }
1162         if (!z)
1163           {
1164             XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1165
1166             if (p == dst->segment && z == p)
1167               dst->segment = p = q;
1168             else
1169               {
1170                 p->next = q;
1171                 p = q;
1172               }
1173             Z = Z->next;
1174             XmuAppendSegment(p, Z);
1175             break;
1176           }
1177         else if (ins.x2 < z->x1)
1178           {
1179             XmuSegment *r = XmuNewSegment(ins.x1, ins.x2);
1180
1181             if (p == dst->segment && z == p)
1182               {
1183                 r->next = dst->segment;
1184                 dst->segment = p = r;
1185               }
1186             else
1187               {
1188                 p->next = r;
1189                 r->next = z;
1190                 p = r;
1191               }
1192             Z = Z->next;
1193             if (!Z)
1194               break;
1195             else
1196               {
1197                 ins.x1 = Z->x1;
1198                 ins.x2 = Z->x2;
1199                 continue;
1200               }
1201           }
1202         else if (ins.x2 <= z->x2)
1203           {
1204             z->x1 = XmuMin(z->x1, ins.x1);
1205             Z = Z->next;
1206             if (!Z)
1207               break;
1208             else
1209               {
1210                 ins.x1 = Z->x1;
1211                 ins.x2 = Z->x2;
1212                 continue;
1213               }
1214           }
1215         else if (ins.x1 <= z->x2)
1216           {
1217             ins.x1 = XmuMin(z->x1, ins.x1);
1218             if (!z->next)
1219               {
1220                 z->x1 = ins.x1;
1221                 z->x2 = ins.x2;
1222                 p = z;
1223                 Z = Z->next;
1224                 XmuAppendSegment(p, Z);
1225                 break;
1226               }
1227             else
1228               {
1229                 if (z == dst->segment)
1230                   {
1231                     p = dst->segment = dst->segment->next;
1232                     XmuDestroySegment(z);
1233                     z = p;
1234                     continue;
1235                   }
1236                 else
1237                   {
1238                     p->next = z->next;
1239                     XmuDestroySegment(z);
1240                     z = p;
1241                   }
1242               }
1243           }
1244         p = z;
1245         z = z->next;
1246     }
1247
1248   return (dst);
1249 }
1250
1251 /*
1252  * Function:
1253  *      XmuScanlineAnd
1254  *
1255  * Parameters:
1256  *      dst - destination scanline
1257  *      src - source scanline
1258  *
1259  * Description:
1260  * (input)    +--------------+  +-----+    +----------+
1261  * (src)          +---------------------+       +-----------+
1262  * (output)       +----------+  +-----+         +-----+
1263  */
1264 XmuScanline *
1265 XmuScanlineAnd(XmuScanline *dst, XmuScanline *src)
1266 {
1267   XmuSegment  *z, *p, *Z;
1268
1269   if (!dst || !src || dst == src || !dst->segment) {
1270         return (dst);
1271   }
1272   if (!src->segment)
1273     {
1274       XmuDestroySegmentList(dst->segment);
1275       dst->segment = (XmuSegment *)NULL;
1276       return (dst);
1277     }
1278   z = p = dst->segment;
1279   Z = src->segment;
1280
1281   while (z)
1282     {
1283       while (!XmuValidSegment(Z) || Z->x2 <= z->x1)
1284         {
1285           Z = Z->next;
1286           if (!Z)
1287             {
1288               if (z == dst->segment)
1289                 dst->segment = (XmuSegment *)NULL;
1290               else
1291                 p->next = (XmuSegment *)0;
1292               XmuDestroySegmentList(z);
1293               return (dst);
1294             }
1295         }
1296       if (Z->x1 >= z->x2)
1297         {
1298           if (z == dst->segment)
1299             {
1300               p = dst->segment = dst->segment->next;
1301               XmuDestroySegment(z);
1302               z = dst->segment;
1303             }
1304           else
1305             {
1306               p->next = z->next;
1307               XmuDestroySegment(z);
1308               z = p->next;
1309             }
1310           if (!z)
1311             return (dst);
1312           else
1313             continue;
1314         }
1315         z->x1 = XmuMax(z->x1, Z->x1);
1316         if (z->x2 > Z->x2)
1317           {
1318             if (Z->next)
1319               {
1320                 XmuSegment *q = XmuNewSegment(Z->x2, z->x2);
1321
1322                 q->next = z->next;
1323                 z->next = q;
1324               }
1325             z->x2 = Z->x2;
1326           }
1327         p = z;
1328         z = z->next;
1329     }
1330
1331   return (dst);
1332 }
1333
1334 /*
1335  * Function:
1336  *      ScanlineXor
1337  *
1338  * Parameters:
1339  *      dst - destination scanline
1340  *      src - source scanline
1341  *
1342  * Description:
1343  * (input)    +--------------+  +-----+    +----------+
1344  * (src)          +---------------------+       +-----------+
1345  * (output)   +---+          +--+     +-+  +----+     +-----+
1346  */
1347 XmuScanline *
1348 XmuScanlineXor(XmuScanline *dst, XmuScanline *src)
1349 {
1350   XmuSegment *z, *p, *Z, ins;
1351   int tmp1, tmp2;
1352
1353   if (!src || !dst || !src->segment)
1354     return (dst);
1355   if (src == dst)
1356     {
1357       XmuDestroySegmentList(dst->segment);
1358       dst->segment = (XmuSegment *)NULL;
1359       return (dst);
1360     }
1361   if (!dst->segment)
1362     {
1363       XmuScanlineCopy(dst, src);
1364       return (dst);
1365     }
1366
1367   z = p = dst->segment;
1368   Z = src->segment;
1369   ins.x1 = Z->x1;
1370   ins.x2 = Z->x2;
1371
1372   /*CONSTCOND*/
1373   while (1)
1374     {
1375       while (!XmuValidSegment((&ins)))
1376         {
1377           if ((Z = Z->next) == (XmuSegment *)NULL)
1378             return (dst);
1379           ins.x1 = Z->x1;
1380           ins.x2 = Z->x2;
1381         }
1382       if (!z)
1383         {
1384           XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1385
1386             if (!dst->segment)
1387               dst->segment = q;
1388             else
1389               p->next = q;
1390             p = q;
1391             Z = Z->next;
1392             XmuAppendSegment(p, Z);
1393             break;
1394         }
1395       else if (ins.x2 < z->x1)
1396         {
1397           XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1398
1399           q->next = z;
1400           if (z == dst->segment)
1401             dst->segment = q;
1402           else
1403             p->next = q;
1404           if ((Z = Z->next) == (XmuSegment *)NULL)
1405             return (dst);
1406
1407           p = q;
1408           ins.x1 = Z->x1;
1409           ins.x2 = Z->x2;
1410           continue;
1411         }
1412       else if (ins.x2 == z->x1)
1413         {
1414           z->x1 = ins.x1;
1415           if ((Z = Z->next) == (XmuSegment *)NULL)
1416             break;
1417           ins.x1 = Z->x1;
1418           ins.x2 = Z->x2;
1419           continue;
1420         }
1421       else if (ins.x1 < z->x2)
1422         {
1423           if (ins.x1 == z->x1)
1424             {
1425               if (ins.x2 < z->x2)
1426                 {
1427                   z->x1 = ins.x2;
1428                   if ((Z = Z->next) == (XmuSegment *)NULL)
1429                     break;
1430                   ins.x1 = Z->x1;
1431                   ins.x2 = Z->x2;
1432                   continue;
1433                 }
1434               else
1435                 {
1436                   ins.x1 = z->x2;
1437                   if (z == dst->segment)
1438                     p = dst->segment = dst->segment->next;
1439                   else
1440                     p->next = z->next;
1441                   XmuDestroySegment(z);
1442                   z = p;
1443                   continue;
1444                 }
1445             }
1446           else
1447             {
1448               if (Z->x2 < z->x2)
1449                 {
1450                   XmuSegment  *q = XmuNewSegment(XmuMin(ins.x1, z->x1),
1451                                                  XmuMax(z->x1, ins.x1));
1452
1453                   q->next = z;
1454                   if (z == dst->segment)
1455                     dst->segment = q;
1456                   else
1457                     p->next = q;
1458                   ins.x1 = z->x2;
1459                   z->x1 = ins.x2;
1460                   p = q;
1461                   continue;
1462                 }
1463               else
1464                 {
1465                   tmp1 = ins.x2;
1466                   tmp2 = z->x2;
1467                   ins.x2 = XmuMax(ins.x2, z->x2);
1468                   z->x2 = XmuMax(z->x1, ins.x1);
1469                   z->x1 = XmuMin(ins.x1, z->x1);
1470                   ins.x1 = XmuMin(tmp1, tmp2);
1471                 }
1472             }
1473         }
1474       else if (ins.x1 == z->x2)
1475         {
1476           ins.x1 = z->x1;
1477           if (z == dst->segment)
1478             p = dst->segment = dst->segment->next;
1479           else
1480             p->next = z->next;
1481           XmuDestroySegment(z);
1482           z = p;
1483           continue;
1484         }
1485       p = z;
1486       z = z->next;
1487     }
1488
1489   return (dst);
1490 }
1491
1492 /*
1493  * Function:
1494  *      XmuNewScanline
1495  *
1496  * Parameters:
1497  *      y  - y coordinate
1498  *      x1 - left coordinate
1499  *      x2 - right coordinate
1500  *
1501  * Description:
1502  *      Creates a new Scanline
1503  */
1504 XmuScanline *
1505 XmuNewScanline(int y, int x1, int x2)
1506 {
1507   XmuScanline *scanline;
1508
1509   scanline = (XmuScanline *)XtMalloc(sizeof(XmuScanline));
1510   scanline->y = y;
1511   if (x1 < x2)
1512     scanline->segment = XmuNewSegment(x1, x2);
1513   else
1514     scanline->segment = (XmuSegment *)NULL;
1515
1516   scanline->next = (XmuScanline *)NULL;
1517
1518   return (scanline);
1519 }
1520
1521 /*
1522  * Function:
1523  *      XmuDestroyScanlineList
1524  *
1525  * Parameters:
1526  *      scanline - scanline list to destroy
1527  *
1528  * Description:
1529  *      Destroy a scanline list
1530  *
1531  * Observation:
1532  *      Use as follow:
1533  *      XmuDestroyScanlineList(area->scanline);
1534  *      area->scanline = (XmuScanline *)NULL;
1535  */
1536 void
1537 XmuDestroyScanlineList(XmuScanline *scanline)
1538 {
1539   XmuScanline *z;
1540
1541   if (!scanline)
1542     return;
1543
1544   while (scanline)
1545     {
1546       z = scanline;
1547       scanline = scanline->next;
1548       XmuDestroyScanline(z);
1549     }
1550 }
1551
1552 /*
1553  * Function:
1554  *      XmuOptimizeArea
1555  *
1556  * Parameters:
1557  *      area - area to optimize
1558  *
1559  * Description:
1560  *        Optimizes an area. This function is called when finishing a
1561  *      operation between areas, since they can end with redundant data,
1562  *      and the algorithms for area combination waits a area with
1563  *      correct data (but can left unnecessary data in the area, to avoid
1564  *      to much paranoia tests).
1565  */
1566 XmuArea *XmuOptimizeArea(XmuArea *area)
1567 {
1568   XmuScanline *pr, *at;
1569
1570   if (!area || !area->scanline)
1571     return (area);
1572
1573   if (!area->scanline->next)
1574     {
1575       XmuDestroyScanlineList(area->scanline);
1576       area->scanline = (XmuScanline *)0;
1577       return (area);
1578     }
1579
1580   pr = area->scanline;
1581   at = area->scanline->next;
1582   while (area->scanline && (!XmuValidScanline(area->scanline)
1583                             || (area->scanline->next && area->scanline->y
1584                                 >= area->scanline->next->y)))
1585     {
1586       area->scanline = area->scanline->next;
1587       XmuDestroyScanline(pr);
1588       pr = area->scanline;
1589       if (pr)
1590         at = pr->next;
1591     }
1592
1593   for (; at; pr = at, at = at->next)
1594     {
1595       if (XmuScanlineEqu(at, pr)
1596           || (!XmuValidScanline(at) && !XmuValidScanline(pr))
1597           || (at->next && at->y >= at->next->y))
1598         {
1599           pr->next = at->next;
1600           XmuDestroyScanline(at);
1601           at = pr;
1602         }
1603     }
1604   if (pr && XmuValidScanline(pr))
1605     {
1606       XmuDestroySegmentList(pr->segment);
1607       pr->segment = (XmuSegment *)NULL;
1608     }
1609   if (area->scanline && !area->scanline->next)
1610     {
1611       XmuDestroyScanlineList(area->scanline);
1612       area->scanline = (XmuScanline *)NULL;
1613     }
1614
1615   return (area);
1616 }