From 709dda59a506e0c4ad17b085aa381f35cd86176f Mon Sep 17 00:00:00 2001 From: Kaleb Keithley Date: Fri, 14 Nov 2003 16:48:49 +0000 Subject: Initial revision --- include/X11/Xmu/Lookup.h | 128 ++++ src/Clip.c | 1614 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 1742 insertions(+) create mode 100644 include/X11/Xmu/Lookup.h create mode 100644 src/Clip.c diff --git a/include/X11/Xmu/Lookup.h b/include/X11/Xmu/Lookup.h new file mode 100644 index 0000000..88ca4d4 --- /dev/null +++ b/include/X11/Xmu/Lookup.h @@ -0,0 +1,128 @@ +/* + * $XFree86: xc/lib/Xmu/Lookup.h,v 1.1 1999/03/21 07:34:38 dawes Exp $ + */ + +/************************************************************ + +Copyright 1999 by Thomas E. Dickey + + All Rights Reserved + +Permission is hereby granted, free of charge, to any person obtaining a +copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be included +in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS +OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT HOLDER(S) BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Except as contained in this notice, the name(s) of the above copyright +holders shall not be used in advertising or otherwise to promote the +sale, use or other dealings in this Software without prior written +authorization. + +********************************************************/ + +#ifndef included_xmu_lookup_h +#define included_xmu_lookup_h 1 + +#include +#include + +extern int XmuLookupString( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status, + unsigned long keysymSet); + +extern int XmuLookupLatin1( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupLatin2( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupLatin3( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupLatin4( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupKana( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupJISX0201( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupArabic( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupCyrillic( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupGreek( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupAPL( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +extern int XmuLookupHebrew( + XKeyEvent *event, + unsigned char *buffer, + int nbytes, + KeySym *keysym, + XComposeStatus *status); + +#endif /* included_xmu_lookup_h */ diff --git a/src/Clip.c b/src/Clip.c new file mode 100644 index 0000000..0f6d410 --- /dev/null +++ b/src/Clip.c @@ -0,0 +1,1614 @@ +/* + * Copyright (c) 1998 by The XFree86 Project, Inc. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF + * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * Except as contained in this notice, the name of the XFree86 Project shall + * not be used in advertising or otherwise to promote the sale, use or other + * dealings in this Software without prior written authorization from the + * XFree86 Project. + */ +/* $XFree86: xc/lib/Xmu/Clip.c,v 1.2 1999/08/15 13:00:44 dawes Exp $ */ + +#include + +#include +#include + +#define XmuMax(a, b) ((a) > (b) ? (a) : (b)) +#define XmuMin(a, b) ((a) < (b) ? (a) : (b)) + +/* + * Function: + * XmuNewArea + * + * Parameters: + * x1 - Coordinates of the rectangle + * y1 - "" + * x2 - "" + * y2 - "" + * + * Description: + * Creates a new rectangular clipping area + */ +XmuArea * +XmuNewArea(int x1, int y1, int x2, int y2) +{ + XmuArea *area; + + area = (XmuArea *)XtMalloc(sizeof(XmuArea)); + if (x2 > x1 && y2 > y1) + { + area->scanline = XmuNewScanline(y1, x1, x2); + area->scanline->next = XmuNewScanline(y2, 0, 0); + } + else + area->scanline = (XmuScanline *)NULL; + + return (area); +} + +/* + * Function: + * XmuAreaDup + * + * Parameters: + * area - Area to copy + * + * Description: + * Returns a copy of its argument + */ +XmuArea * +XmuAreaDup(XmuArea *area) +{ + XmuArea *dst; + + if (!area) + return ((XmuArea *)NULL); + + dst = XmuCreateArea(); + XmuAreaCopy(dst, area); + return (dst); +} + +/* + * Function: + * XmuAreaCopy + * + * Parameters: + * dst - destination area + * src - source area + * + * Description: + * Minimizes memory alocation, trying to use already alocated memory + * in dst, freeing what is not required anymore. + */ +XmuArea * +XmuAreaCopy(XmuArea *dst, XmuArea *src) +{ + XmuScanline *z, *p, *Z; + + if (!dst || !src || dst == src) + return (dst); + + z = p = dst->scanline; + Z = src->scanline; + + /*CONSTCOND*/ + while (1) + { + if (!Z) + { + if (z == dst->scanline) + { + XmuDestroyScanlineList(dst->scanline); + dst->scanline = (XmuScanline *)NULL; + } + else + { + XmuDestroyScanlineList(p->next); + p->next = (XmuScanline *)NULL; + } + return (dst); + } + if (z) + { + XmuScanlineCopy(z, Z); + z->y = Z->y; + } + else + { + z = XmuNewScanline(Z->y, 0, 0); + XmuScanlineCopy(z, Z); + if (p == dst->scanline && !dst->scanline) + p = dst->scanline = z; + else + p->next = z; + } + p = z; + z = z->next; + Z = Z->next; + } + + return (dst); +} + +/* + * Function: + * XmuAreaNot + * + * Parameters: + * area - area to operate + * x1 - retangle to clip the result against + * y1 - "" + * x2 - "" + * y2 - "" + * + * Description: + * (Input) + * (x1, y1) (x2, y1) + * +-------------+ + * +------------+ +----+ + * | +--------------+ + * +----------------+ + * (x1, y2) (x2, y2) + * + * (Output) + * (x1, y1) (x2, y1) + * +--------------+ +--------------------------+ + * | +------------+ +----+ | + * | | +--------------+ | + * +-+ +------------------------------------+ + * (x1, y2) (x2, y2) + */ +XmuArea * +XmuAreaNot(XmuArea *area, int x1, int y1, int x2, int y2) +{ + XmuScanline *z; + XmuArea *and; + + if (!area) + return (area); + + if (x1 > x2) + { + x1 ^= x2; x2 ^= x1; x1 ^= x2; + } + if (y1 > y2) + { + y1 ^= y2; y2 ^= y1; y1 ^= y2; + } + if (!area->scanline) + { + if ((area->scanline = XmuNewScanline(y1, x1, x2)) != NULL) + area->scanline->next = XmuNewScanline(y2, 0, 0); + return (area); + } + and = XmuNewArea(x1, y1, x2, y2); + XmuAreaAnd(area, and); + XmuDestroyArea(and); + z = area->scanline; + if (z->y != y1) + { + XmuScanline *q = XmuNewScanline(y1, x1, x2); + q->next = z; + area->scanline = q; + } + else + { + area->scanline = area->scanline->next; + XmuDestroyScanline(z); + XmuOptimizeArea(area); + if((z = area->scanline) == (XmuScanline *)NULL) + return (area); + } + + /* CONSTCOND */ + while (1) + { + XmuScanlineNot(z, x1, x2); + if (!z->next) + { + z->next = XmuNewScanline(y2, 0, 0); + break; + } + if (z->next->y == y2) + { + XmuDestroyScanlineList(z->next); + z->next = XmuNewScanline(y2, 0, 0); + break; + } + z = z->next; + } + + return (area); +} + +/* + * Function: + * XmuAreaOrXor + * + * Parameters: + * dst - destination area + * src - source area + * or - or operation if true, else xor operation + * + * Description: + * Executes Or (Union) or Xor (Reverse intesection) of the areas + */ +XmuArea * +XmuAreaOrXor(XmuArea *dst, XmuArea *src, Bool or) +{ + XmuScanline *z, *p, *Z, *P, *ins, *top; + + if (!dst || !src) + return (dst); + + if (dst == src) + { + if (or) + return (dst); + XmuDestroyScanlineList(dst->scanline); + dst->scanline = (XmuScanline *)NULL; + return (dst); + } + if (!XmuValidArea(src)) + return (dst); + if (!XmuValidArea(dst)) + { + XmuAreaCopy(dst, src); + return (dst); + } + + p = z = dst->scanline; + P = Z = src->scanline; + ins = XmuNewScanline(dst->scanline->y, 0, 0); + top = XmuNewScanline(dst->scanline->y, 0, 0); + XmuScanlineCopy(ins, dst->scanline); + XmuScanlineCopy(top, dst->scanline); + + /*CONSTCOND*/ + while (1) + { + if (!Z) + break; + else if (Z->y < z->y) + { + XmuScanline *q = XmuNewScanline(Z->y, 0, 0); + XmuScanlineCopy(q, Z); + + if (z == dst->scanline) + { + dst->scanline = p = q; + q->next = z; + } + else + { + p->next = q; + q->next = z; + if (Z->y >= p->y) + { + if (ins->y >= top->y + && (p->y != P->y || !XmuScanlineEqu(p, P) + || (ins->y <= P->y && !XmuScanlineEqu(ins, P)))) + { + if (or) + XmuScanlineOr(q, ins); + else + XmuScanlineXor(q, ins); + } + else if (Z->y >= top->y + && (top->y == p->y || top->y > ins->y + || !XmuValidScanline(Z) + || (p->y == P->y && XmuValidScanline(p) + && XmuValidScanline(P)) + || XmuScanlineEqu(ins, top))) + { + if (or) + XmuScanlineOr(q, top); + else + XmuScanlineXor(q, top); + } + if (ins->y != p->y && p->y != P->y) + { + XmuScanlineCopy(ins, p); + ins->y = p->y; + } + } + if (!XmuValidScanline(p) || Z->y <= p->y) + { + XmuScanlineCopy(top, p); + top->y = p->y; + } + p = q; + } + P = Z; + Z = Z->next; + continue; + } + else if (Z->y == z->y) + { + if (top->y != z->y) + { + XmuScanlineCopy(top, z); + top->y = z->y; + } + if (or) + XmuScanlineOr(z, Z); + else + XmuScanlineXor(z, Z); + P = Z; + Z = Z->next; + } + else if (P != Z) /* && Z->y > z->y */ + { + if (top->y == ins->y && top->y != z->y) + { + XmuScanlineCopy(top, z); + top->y = z->y; + } + if (ins->y != z->y) + { + XmuScanlineCopy(ins, z); + ins->y = z->y; + } + if (or) + XmuScanlineOr(z, P); + else + XmuScanlineXor(z, P); + } + else if (ins->y != z->y) + { + XmuScanlineCopy(ins, z); + ins->y = z->y; + } + p = z; + z = z->next; + if (!z) + { + while (Z) + { + p->next = XmuNewScanline(Z->y, 0, 0); + XmuScanlineCopy(p->next, Z); + p = p->next; + Z = Z->next; + } + break; + } + else if (ins->y > top->y && !XmuValidScanline(z) + && XmuValidScanline(ins)) + { + XmuScanlineCopy(top, ins); + top->y = ins->y; + } + } + XmuOptimizeArea(dst); + XmuDestroyScanline(ins); + XmuDestroyScanline(top); + + return (dst); +} + +/* + * Function: + * XmuAreaAnd(dst, src) + * + * Parameters: + * dst - destination area + * src - source area + * + * Description: + * Executes And (intersection) of the areas + */ +XmuArea * +XmuAreaAnd(XmuArea *dst, XmuArea *src) +{ + XmuScanline *z, *p, *Z, *P, *top; + + if (!dst || !src || dst == src) + return (dst); + if (!XmuValidArea(dst) || !XmuValidArea(src)) + { + XmuDestroyScanlineList(dst->scanline); + dst->scanline = (XmuScanline *)NULL; + return (dst); + } + z = p = dst->scanline; + Z = P = src->scanline; + top = XmuNewScanline(dst->scanline->y, 0, 0); + XmuScanlineCopy(top, dst->scanline); + + while (z) + { + while (Z->next && Z->next->y < z->y) + { + P = Z; + Z = Z->next; + if (Z->y >= p->y) + { + XmuScanline *q = XmuNewScanline(Z->y, 0, 0); + XmuScanlineCopy(q, Z); + + XmuScanlineAnd(q, top); + if (p->y != P->y) + { + XmuScanlineAnd(p, P); + p->y = XmuMax(p->y, P->y); + } + p->next = q; + q->next = z; + p = q; + } + } + if (!z->next) + { + z->y = XmuMax(z->y, Z->y); + break; + } + while (Z->y >= z->next->y) + { + if (z == dst->scanline) + { + p = dst->scanline = dst->scanline->next; + XmuDestroyScanline(z); + z = dst->scanline; + } + else + { + p->next = z->next; + XmuDestroyScanline(z); + z = p; + } + if (!z || !z->next) + { + XmuOptimizeArea(dst); + XmuDestroyScanline(top); + + return (dst); + } + } + if (Z->y > p->y) + z->y = XmuMax(z->y, Z->y); + if (top->y != z->y) + { + XmuScanlineCopy(top, z); + top->y = z->y; + } + XmuScanlineAnd(z, Z); + p = z; + z = z->next; + } + XmuOptimizeArea(dst); + XmuDestroyScanline(top); + + return (dst); +} + +/* + * Function: + * XmuValidArea(area) + * + * Parameters: + * area - area to verify + * + * Description: + * Verifies if the area is valid and/or useful + */ +Bool +XmuValidArea(XmuArea *area) +{ + XmuScanline *at; + + if (!area || !area->scanline) + return (False); + + at = area->scanline; + while (at) + { + if (XmuValidScanline(at)) + return (True); + at = at->next; + } + + return (False); +} + +/* + * Function: + * XmuValidScanline + * + * Parameters: + * scanline - scanline to verify + * + * Description: + * Verifies if a scanline is useful + */ +Bool +XmuValidScanline(XmuScanline *scanline) +{ + XmuSegment *z; + + if (!scanline) + return (False); + + z = scanline->segment; + while (z) + { + if (XmuValidSegment(z)) + return (True); + z = z->next; + } + + return (False); +} + +/* + * Function: + * XmuScanlineEqu + * + * Parameters: + * s1 - scanline 1 + * s2 - scanline 2 + * + * Description: + * Checks if s1 and s2 are equal + */ +Bool +XmuScanlineEqu(XmuScanline *s1, XmuScanline *s2) +{ + XmuSegment *z, *Z; + + if ((!s1 && !s2) || s1 == s2) + return (True); + if (!s1 || !s2) + return (False); + + z = s1->segment; + Z = s2->segment; + + /*CONSTCOND*/ + while (1) + { + if (!z && !Z) + return (True); + if (!z || !Z) + return (False); + if (!XmuSegmentEqu(z, Z)) + return (False); + z = z->next; + Z = Z->next; + } + /*NOTREACHED*/ +} + +/* + * Function: + * XmuNewSegment + * + * Parameters: + * x1 - coordinates of the segment + * x2 - "" + * + * Description: + * Creates a new segments with the coordinates x1 and x2 + * + * Returns: + * New Segment of NULL + */ +XmuSegment * +XmuNewSegment(int x1, int x2) +{ + XmuSegment *segment; + + if ((segment = (XmuSegment *)XtMalloc(sizeof(XmuSegment))) == NULL) + return (segment); + + segment->x1 = x1; + segment->x2 = x2; + segment->next = (XmuSegment *)NULL; + + return (segment); +} + +/* + * Function: + * XmuDestroySegmentList + * + * Parameters: + * segment - Segment to destroy + * + * Description: + * Frees the memory used by the list headed by segment + */ +void +XmuDestroySegmentList(XmuSegment *segment) +{ + XmuSegment *z; + + if (!segment) + return; + + while (segment) + { + z = segment; + segment = segment->next; + XmuDestroySegment(z); + } +} + +/* + * Function: + * XmuScanlineCopy + * + * Parameters: + * dst - destination scanline + * src - source scanline + * + * Description: + * Makes dst contain the same data as src + */ +XmuScanline * +XmuScanlineCopy(XmuScanline *dst, XmuScanline *src) +{ + XmuSegment *z, *p, *Z; + + if (!dst || !src || dst == src) + return (dst); + + z = p = dst->segment; + Z = src->segment; + + /*CONSTCOND*/ + while (1) + { + if (!Z) + { + if (z == dst->segment) + dst->segment = (XmuSegment *)NULL; + else + p->next = (XmuSegment *)NULL; + XmuDestroySegmentList(z); + return (dst); + } + if (z) + { + z->x1 = Z->x1; + z->x2 = Z->x2; + } + else + { + z = XmuNewSegment(Z->x1, Z->x2); + if (p == dst->segment && !dst->segment) + p = dst->segment = z; + else + p->next = z; + } + p = z; + z = z->next; + Z = Z->next; + } + /*NOTREACHED*/ +} + +/* + * Function: + * XmuAppendSegment + * + * Parameters: + * segment - destination segment + * append - segment to add + * + * Description: + * Adds a copy of the append list at the end of the segment list + */ +Bool +XmuAppendSegment(XmuSegment *segment, XmuSegment *append) +{ + if (!segment || !append) + return (False); + + if (segment->next) + /* Should not happen! */ + XmuDestroySegmentList(segment->next); + + while (append) + { + if (XmuValidSegment(append)) + { + if ((segment->next = XmuNewSegment(append->x1, append->x2)) == NULL) + return (False); + segment = segment->next; + } + append = append->next; + } + + return (True); +} + +/* + * Function: + * XmuOptimizeScanline + * + * Parameters: + * scanline - scanline to optimize + * + * Description: + * Some functions, when transforming Segments of Scanlines, left these + * with unnecessary data (that may cause error in these same functions). + * This function corrects these incorrect segments. + */ +XmuScanline * +XmuOptimizeScanline(XmuScanline *scanline) +{ + XmuSegment *z, *p; + + while (scanline->segment && !XmuValidSegment(scanline->segment)) + { + XmuSegment *s = scanline->segment; + + scanline->segment = scanline->segment->next; + XmuDestroySegment(s); + } + for (z = p = scanline->segment; z; p = z, z = z->next) + { + if (!XmuValidSegment(z)) + { + p->next = z->next; + XmuDestroySegment(z); + z = p; + } + } + return (scanline); +} + +/* + * Name: + * XmuScanlineNot(scanline, minx, maxx) + * + * Parameters: + * scanline - scanlines operate + * minx - minimum x coordinate + * maxx - maximum x coordinate + * + * Description: + * (minx) (maxx) + * + + + * (input) +---------+ +--------+ +--------+ + * (output) +-----+ +-----+ +--------+ +------------+ + */ +XmuScanline * +XmuScanlineNot(XmuScanline *scanline, int minx, int maxx) +{ + XmuSegment *z; + static XmuSegment x = { 0, 0, 0 }; + static XmuScanline and = { 0, &x, 0 }; + + if (!scanline) + return (scanline); + + XmuOptimizeScanline(scanline); + if (minx > maxx) + { + minx ^= maxx; maxx ^= minx; minx ^= maxx; + } + and.segment->x1 = minx; + and.segment->x2 = maxx; + XmuScanlineAnd(scanline, &and); + if (!scanline->segment) + { + scanline->segment = XmuNewSegment(minx, maxx); + return (scanline); + } + z = scanline->segment; + if (z->x1 != minx) + { + XmuSegment *q = XmuNewSegment(minx, z->x1); + + q->next = z; + scanline->segment = q; + } + + /*CONSTCOND*/ + while (1) + { + z->x1 = z->x2; + if (!z->next) + { + z->x2 = maxx; + break; + } + z->x2 = z->next->x1; + if (z->next->x2 == maxx) + { + XmuDestroySegment(z->next); + z->next = (XmuSegment *)NULL; + break; + } + z = z->next; + } + + return (scanline); +} + + +#ifndef notdef +/* + * Function: + * XmuScanlineOrSegment + * + * Parameters: + * dst - destionation scanline + * src - source segment + * + * Description: + * (input) +-----------+ +--------+ +---------+ + * (src) +-------------------+ + * (output) +-------------------------+ +---------+ + */ +XmuScanline * +XmuScanlineOrSegment(XmuScanline *dst, XmuSegment *src) +{ + XmuSegment *z, *p, ins; + + if (!src || !dst || !XmuValidSegment(src)) + return (dst); + + if (!dst->segment) + { + dst->segment = XmuNewSegment(src->x1, src->x2); + return (dst); + } + + z = p = dst->segment; + ins.x1 = src->x1; + ins.x2 = src->x2; + + /*CONSTCOND*/ + while (1) + { + if (!z) + { + XmuSegment *q = XmuNewSegment(ins.x1, ins.x2); + + if (p == dst->segment && z == p) + dst->segment = q; + else + p->next = q; + break; + } + else if (ins.x2 < z->x1) + { + XmuSegment *q = XmuNewSegment(ins.x1, ins.x2); + + if (p == dst->segment && z == p) + { + q->next = dst->segment; + dst->segment = q; + } + else + { + p->next = q; + q->next = z; + } + break; + } + else if (ins.x2 <= z->x2) + { + z->x1 = XmuMin(z->x1, ins.x1); + break; + } + else if (ins.x1 <= z->x2) + { + ins.x1 = XmuMin(z->x1, ins.x1); + if (!z->next) + { + z->x1 = ins.x1; + z->x2 = ins.x2; + break; + } + else + { + if (z == dst->segment) + { + p = dst->segment = dst->segment->next; + XmuDestroySegment(z); + z = dst->segment; + continue; + } + else + { + p->next = z->next; + XmuDestroySegment(z); + z = p; + } + } + } + p = z; + z = z->next; + } + + return (dst); +} + +/* + * Function: + * XmuScanlineAndSegment + * + * Parameters: + * dst - destination scanline + * src - source segment + * + * Description: + * (input) +------------+ +------+ +----------+ + * (src) +---------------------+ + * (output) +-------+ +------+ + */ +XmuScanline * +XmuScanlineAndSegment(XmuScanline *dst, XmuSegment *src) +{ + XmuSegment *z, *p; + + if (!dst || !src) + return (dst); + + if (!XmuValidSegment(src)) + { + XmuDestroySegmentList(dst->segment); + dst->segment = (XmuSegment *)NULL; + return (dst); + } + if (!dst->segment) + return (dst); + + z = p = dst->segment; + while (z) + { + if (src->x2 <= z->x1 || src->x1 >= z->x2) + { + if (z == dst->segment) + { + p = dst->segment = dst->segment->next; + XmuDestroySegment(z); + z = dst->segment; + continue; + } + else + { + p->next = z->next; + XmuDestroySegment(z); + z = p; + } + } + else + { + z->x1 = XmuMax(z->x1, src->x1); + z->x2 = XmuMin(z->x2, src->x2); + } + p = z; + z = z->next; + } + + return (dst); +} + +/* + * Function: + * XmuScanlineXorSegment + * + * Parameters: + * dst - destionation scanline + * src - source segment + * + * Descriptipn: + * (input) +------------+ +----------+ +-----------+ + * (src) +------------------------+ + * (output) +---+ +--+ +-+ +-----------+ + */ +XmuScanline * +XmuScanlineXorSegment(XmuScanline *dst, XmuSegment *src) +{ + XmuSegment *p, *z, ins; + int tmp1, tmp2; + + if (!dst || !src || !XmuValidSegment(src)) + return (dst); + if (!dst->segment) + { + dst->segment = XmuNewSegment(src->x1, src->x2); + return (dst); + } + + p = z = dst->segment; + ins.x1 = src->x1; + ins.x2 = src->x2; + + /*CONSTCOND*/ + while (1) + { + if (!XmuValidSegment((&ins))) + break; + if (!z || ins.x2 < z->x1) + { + XmuSegment *q = XmuNewSegment(ins.x1, ins.x2); + + q->next = z; + if (z == dst->segment) + dst->segment = q; + else + p->next = q; + break; + } + else if (ins.x2 == z->x1) + { + z->x1 = ins.x1; + break; + } + else if (ins.x1 < z->x2) + { + if (ins.x1 < z->x1) + { + tmp1 = ins.x2; + tmp2 = z->x2; + ins.x2 = XmuMax(ins.x2, z->x2); + z->x2 = z->x1; + z->x1 = ins.x1; + ins.x1 = XmuMin(tmp1, tmp2); + } + else if (ins.x1 > z->x1) + { + tmp1 = ins.x1; + ins.x1 = XmuMin(ins.x2, z->x2); + ins.x2 = XmuMax(z->x2, ins.x2); + z->x2 = tmp1; + } + else /* ins.x1 == z->x1 */ + { + if (ins.x2 < z->x2) + { + z->x1 = ins.x2; + break; + } + else + { + ins.x1 = z->x2; + if (z == dst->segment) + p = dst->segment = dst->segment->next; + else + p->next = z->next; + XmuDestroySegment(z); + z = p; + continue; + } + } + } + else if (ins.x1 == z->x2) + { + ins.x1 = z->x1; + if (z == dst->segment) + p = dst->segment = dst->segment->next; + else + p->next = z->next; + XmuDestroySegment(z); + z = p; + continue; + } + p = z; + z = z->next; + } + + return (dst); +} +#endif /* notdef */ + +/* + * Function: + * ScanlineOr + * + * Parameters: + * dst - destionation scanline + * src - source scanline + * + * Description: + * (input) +--------------+ +-----+ +----------+ + * (src) +---------------------+ +-----------+ + * (output) +-------------------------+ +----------------+ + */ +XmuScanline * +XmuScanlineOr(XmuScanline *dst, XmuScanline *src) +{ + XmuSegment *z, *p, *Z, ins; + + if (!src || !src->segment || !dst || dst == src) + return (dst); + if (!dst->segment) + { + XmuScanlineCopy(dst, src); + return (dst); + } + + z = p = dst->segment; + Z = src->segment; + ins.x1 = Z->x1; + ins.x2 = Z->x2; + + /*CONSTCOND*/ + while (1) + { + while (!XmuValidSegment((&ins))) + { + if ((Z = Z->next) == (XmuSegment *)NULL) + return (dst); + ins.x1 = Z->x1; + ins.x2 = Z->x2; + } + if (!z) + { + XmuSegment *q = XmuNewSegment(ins.x1, ins.x2); + + if (p == dst->segment && z == p) + dst->segment = p = q; + else + { + p->next = q; + p = q; + } + Z = Z->next; + XmuAppendSegment(p, Z); + break; + } + else if (ins.x2 < z->x1) + { + XmuSegment *r = XmuNewSegment(ins.x1, ins.x2); + + if (p == dst->segment && z == p) + { + r->next = dst->segment; + dst->segment = p = r; + } + else + { + p->next = r; + r->next = z; + p = r; + } + Z = Z->next; + if (!Z) + break; + else + { + ins.x1 = Z->x1; + ins.x2 = Z->x2; + continue; + } + } + else if (ins.x2 <= z->x2) + { + z->x1 = XmuMin(z->x1, ins.x1); + Z = Z->next; + if (!Z) + break; + else + { + ins.x1 = Z->x1; + ins.x2 = Z->x2; + continue; + } + } + else if (ins.x1 <= z->x2) + { + ins.x1 = XmuMin(z->x1, ins.x1); + if (!z->next) + { + z->x1 = ins.x1; + z->x2 = ins.x2; + p = z; + Z = Z->next; + XmuAppendSegment(p, Z); + break; + } + else + { + if (z == dst->segment) + { + p = dst->segment = dst->segment->next; + XmuDestroySegment(z); + z = p; + continue; + } + else + { + p->next = z->next; + XmuDestroySegment(z); + z = p; + } + } + } + p = z; + z = z->next; + } + + return (dst); +} + +/* + * Function: + * XmuScanlineAnd + * + * Parameters: + * dst - destination scanline + * src - source scanline + * + * Description: + * (input) +--------------+ +-----+ +----------+ + * (src) +---------------------+ +-----------+ + * (output) +----------+ +-----+ +-----+ + */ +XmuScanline * +XmuScanlineAnd(XmuScanline *dst, XmuScanline *src) +{ + XmuSegment *z, *p, *Z; + + if (!dst || !src || dst == src || !dst->segment) { + return (dst); + } + if (!src->segment) + { + XmuDestroySegmentList(dst->segment); + dst->segment = (XmuSegment *)NULL; + return (dst); + } + z = p = dst->segment; + Z = src->segment; + + while (z) + { + while (!XmuValidSegment(Z) || Z->x2 <= z->x1) + { + Z = Z->next; + if (!Z) + { + if (z == dst->segment) + dst->segment = (XmuSegment *)NULL; + else + p->next = (XmuSegment *)0; + XmuDestroySegmentList(z); + return (dst); + } + } + if (Z->x1 >= z->x2) + { + if (z == dst->segment) + { + p = dst->segment = dst->segment->next; + XmuDestroySegment(z); + z = dst->segment; + } + else + { + p->next = z->next; + XmuDestroySegment(z); + z = p->next; + } + if (!z) + return (dst); + else + continue; + } + z->x1 = XmuMax(z->x1, Z->x1); + if (z->x2 > Z->x2) + { + if (Z->next) + { + XmuSegment *q = XmuNewSegment(Z->x2, z->x2); + + q->next = z->next; + z->next = q; + } + z->x2 = Z->x2; + } + p = z; + z = z->next; + } + + return (dst); +} + +/* + * Function: + * ScanlineXor + * + * Parameters: + * dst - destination scanline + * src - source scanline + * + * Description: + * (input) +--------------+ +-----+ +----------+ + * (src) +---------------------+ +-----------+ + * (output) +---+ +--+ +-+ +----+ +-----+ + */ +XmuScanline * +XmuScanlineXor(XmuScanline *dst, XmuScanline *src) +{ + XmuSegment *z, *p, *Z, ins; + int tmp1, tmp2; + + if (!src || !dst || !src->segment) + return (dst); + if (src == dst) + { + XmuDestroySegmentList(dst->segment); + dst->segment = (XmuSegment *)NULL; + return (dst); + } + if (!dst->segment) + { + XmuScanlineCopy(dst, src); + return (dst); + } + + z = p = dst->segment; + Z = src->segment; + ins.x1 = Z->x1; + ins.x2 = Z->x2; + + /*CONSTCOND*/ + while (1) + { + while (!XmuValidSegment((&ins))) + { + if ((Z = Z->next) == (XmuSegment *)NULL) + return (dst); + ins.x1 = Z->x1; + ins.x2 = Z->x2; + } + if (!z) + { + XmuSegment *q = XmuNewSegment(ins.x1, ins.x2); + + if (!dst->segment) + dst->segment = q; + else + p->next = q; + p = q; + Z = Z->next; + XmuAppendSegment(p, Z); + break; + } + else if (ins.x2 < z->x1) + { + XmuSegment *q = XmuNewSegment(ins.x1, ins.x2); + + q->next = z; + if (z == dst->segment) + dst->segment = q; + else + p->next = q; + if ((Z = Z->next) == (XmuSegment *)NULL) + return (dst); + + p = q; + ins.x1 = Z->x1; + ins.x2 = Z->x2; + continue; + } + else if (ins.x2 == z->x1) + { + z->x1 = ins.x1; + if ((Z = Z->next) == (XmuSegment *)NULL) + break; + ins.x1 = Z->x1; + ins.x2 = Z->x2; + continue; + } + else if (ins.x1 < z->x2) + { + if (ins.x1 == z->x1) + { + if (ins.x2 < z->x2) + { + z->x1 = ins.x2; + if ((Z = Z->next) == (XmuSegment *)NULL) + break; + ins.x1 = Z->x1; + ins.x2 = Z->x2; + continue; + } + else + { + ins.x1 = z->x2; + if (z == dst->segment) + p = dst->segment = dst->segment->next; + else + p->next = z->next; + XmuDestroySegment(z); + z = p; + continue; + } + } + else + { + if (Z->x2 < z->x2) + { + XmuSegment *q = XmuNewSegment(XmuMin(ins.x1, z->x1), + XmuMax(z->x1, ins.x1)); + + q->next = z; + if (z == dst->segment) + dst->segment = q; + else + p->next = q; + ins.x1 = z->x2; + z->x1 = ins.x2; + p = q; + continue; + } + else + { + tmp1 = ins.x2; + tmp2 = z->x2; + ins.x2 = XmuMax(ins.x2, z->x2); + z->x2 = XmuMax(z->x1, ins.x1); + z->x1 = XmuMin(ins.x1, z->x1); + ins.x1 = XmuMin(tmp1, tmp2); + } + } + } + else if (ins.x1 == z->x2) + { + ins.x1 = z->x1; + if (z == dst->segment) + p = dst->segment = dst->segment->next; + else + p->next = z->next; + XmuDestroySegment(z); + z = p; + continue; + } + p = z; + z = z->next; + } + + return (dst); +} + +/* + * Function: + * XmuNewScanline + * + * Parameters: + * y - y coordinate + * x1 - left coordinate + * x2 - right coordinate + * + * Description: + * Creates a new Scanline + */ +XmuScanline * +XmuNewScanline(int y, int x1, int x2) +{ + XmuScanline *scanline; + + scanline = (XmuScanline *)XtMalloc(sizeof(XmuScanline)); + scanline->y = y; + if (x1 < x2) + scanline->segment = XmuNewSegment(x1, x2); + else + scanline->segment = (XmuSegment *)NULL; + + scanline->next = (XmuScanline *)NULL; + + return (scanline); +} + +/* + * Function: + * XmuDestroyScanlineList + * + * Parameters: + * scanline - scanline list to destroy + * + * Description: + * Destroy a scanline list + * + * Observation: + * Use as follow: + * XmuDestroyScanlineList(area->scanline); + * area->scanline = (XmuScanline *)NULL; + */ +void +XmuDestroyScanlineList(XmuScanline *scanline) +{ + XmuScanline *z; + + if (!scanline) + return; + + while (scanline) + { + z = scanline; + scanline = scanline->next; + XmuDestroyScanline(z); + } +} + +/* + * Function: + * XmuOptimizeArea + * + * Parameters: + * area - area to optimize + * + * Description: + * Optimizes an area. This function is called when finishing a + * operation between areas, since they can end with redundant data, + * and the algorithms for area combination waits a area with + * correct data (but can left unnecessary data in the area, to avoid + * to much paranoia tests). + */ +XmuArea *XmuOptimizeArea(XmuArea *area) +{ + XmuScanline *pr, *at; + + if (!area || !area->scanline) + return (area); + + if (!area->scanline->next) + { + XmuDestroyScanlineList(area->scanline); + area->scanline = (XmuScanline *)0; + return (area); + } + + pr = area->scanline; + at = area->scanline->next; + while (area->scanline && (!XmuValidScanline(area->scanline) + || (area->scanline->next && area->scanline->y + >= area->scanline->next->y))) + { + area->scanline = area->scanline->next; + XmuDestroyScanline(pr); + pr = area->scanline; + if (pr) + at = pr->next; + } + + for (; at; pr = at, at = at->next) + { + if (XmuScanlineEqu(at, pr) + || (!XmuValidScanline(at) && !XmuValidScanline(pr)) + || (at->next && at->y >= at->next->y)) + { + pr->next = at->next; + XmuDestroyScanline(at); + at = pr; + } + } + if (pr && XmuValidScanline(pr)) + { + XmuDestroySegmentList(pr->segment); + pr->segment = (XmuSegment *)NULL; + } + if (area->scanline && !area->scanline->next) + { + XmuDestroyScanlineList(area->scanline); + area->scanline = (XmuScanline *)NULL; + } + + return (area); +} -- cgit v1.2.1