#include "regionstr.h"
#include "Xprotostr.h"
#include "gc.h"
#include "mi.h"
#include "mispans.h"
#if defined (__GNUC__) && !defined (NO_INLINES)
#define INLINE __inline
#else
#define INLINE
#endif
#undef assert
#ifdef DEBUG
#define assert(expr) {if (!(expr)) \
FatalError("Assertion failed file %s, line %d: expr\n", \
__FILE__, __LINE__); }
#else
#define assert(expr)
#endif
#define good(reg) assert(miValidRegion(reg))
#define EXTENTCHECK(r1,r2) \
(!( ((r1)->x2 <= (r2)->x1) || \
((r1)->x1 >= (r2)->x2) || \
((r1)->y2 <= (r2)->y1) || \
((r1)->y1 >= (r2)->y2) ) )
#define INBOX(r,x,y) \
( ((r)->x2 > x) && \
((r)->x1 <= x) && \
((r)->y2 > y) && \
((r)->y1 <= y) )
#define SUBSUMES(r1,r2) \
( ((r1)->x1 <= (r2)->x1) && \
((r1)->x2 >= (r2)->x2) && \
((r1)->y1 <= (r2)->y1) && \
((r1)->y2 >= (r2)->y2) )
#define xallocData(n) (RegDataPtr)xalloc(REGION_SZOF(n))
#define xfreeData(reg) if ((reg)->data && (reg)->data->size) xfree((reg)->data)
#define RECTALLOC_BAIL(pReg,n,bail) \
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
if (!miRectAlloc(pReg, n)) { goto bail; }
#define RECTALLOC(pReg,n) \
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
if (!miRectAlloc(pReg, n)) { return FALSE; }
#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
{ \
pNextRect->x1 = nx1; \
pNextRect->y1 = ny1; \
pNextRect->x2 = nx2; \
pNextRect->y2 = ny2; \
pNextRect++; \
}
#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
{ \
if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
{ \
if (!miRectAlloc(pReg, 1)) \
return FALSE; \
pNextRect = REGION_TOP(pReg); \
} \
ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
pReg->data->numRects++; \
assert(pReg->data->numRects<=pReg->data->size); \
}
#define DOWNSIZE(reg,numRects) \
if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
{ \
RegDataPtr NewData; \
NewData = (RegDataPtr)xrealloc((reg)->data, REGION_SZOF(numRects)); \
if (NewData) \
{ \
NewData->size = (numRects); \
(reg)->data = NewData; \
} \
}
BoxRec miEmptyBox = {0, 0, 0, 0};
RegDataRec miEmptyData = {0, 0};
RegDataRec miBrokenData = {0, 0};
RegionRec miBrokenRegion = { { 0, 0, 0, 0 }, &miBrokenData };
#ifdef DEBUG
int
miPrintRegion(rgn)
RegionPtr rgn;
{
int num, size;
register int i;
BoxPtr rects;
num = REGION_NUM_RECTS(rgn);
size = REGION_SIZE(rgn);
rects = REGION_RECTS(rgn);
ErrorF("num: %d size: %d\n", num, size);
ErrorF("extents: %d %d %d %d\n",
rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
for (i = 0; i < num; i++)
ErrorF("%d %d %d %d \n",
rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
ErrorF("\n");
return(num);
}
#endif
Bool
miRegionEqual(reg1, reg2)
RegionPtr reg1;
RegionPtr reg2;
{
int i, num;
BoxPtr rects1, rects2;
if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
num = REGION_NUM_RECTS(reg1);
if (num != REGION_NUM_RECTS(reg2)) return FALSE;
rects1 = REGION_RECTS(reg1);
rects2 = REGION_RECTS(reg2);
for (i = 0; i != num; i++) {
if (rects1[i].x1 != rects2[i].x1) return FALSE;
if (rects1[i].x2 != rects2[i].x2) return FALSE;
if (rects1[i].y1 != rects2[i].y1) return FALSE;
if (rects1[i].y2 != rects2[i].y2) return FALSE;
}
return TRUE;
}
#ifdef DEBUG
Bool
miValidRegion(reg)
RegionPtr reg;
{
register int i, numRects;
if ((reg->extents.x1 > reg->extents.x2) ||
(reg->extents.y1 > reg->extents.y2))
return FALSE;
numRects = REGION_NUM_RECTS(reg);
if (!numRects)
return ((reg->extents.x1 == reg->extents.x2) &&
(reg->extents.y1 == reg->extents.y2) &&
(reg->data->size || (reg->data == &miEmptyData)));
else if (numRects == 1)
return (!reg->data);
else
{
register BoxPtr pboxP, pboxN;
BoxRec box;
pboxP = REGION_RECTS(reg);
box = *pboxP;
box.y2 = pboxP[numRects-1].y2;
pboxN = pboxP + 1;
for (i = numRects; --i > 0; pboxP++, pboxN++)
{
if ((pboxN->x1 >= pboxN->x2) ||
(pboxN->y1 >= pboxN->y2))
return FALSE;
if (pboxN->x1 < box.x1)
box.x1 = pboxN->x1;
if (pboxN->x2 > box.x2)
box.x2 = pboxN->x2;
if ((pboxN->y1 < pboxP->y1) ||
((pboxN->y1 == pboxP->y1) &&
((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
return FALSE;
}
return ((box.x1 == reg->extents.x1) &&
(box.x2 == reg->extents.x2) &&
(box.y1 == reg->extents.y1) &&
(box.y2 == reg->extents.y2));
}
}
#endif
RegionPtr
miRegionCreate(rect, size)
BoxPtr rect;
int size;
{
register RegionPtr pReg;
pReg = (RegionPtr)xalloc(sizeof(RegionRec));
if (!pReg)
return &miBrokenRegion;
if (rect)
{
pReg->extents = *rect;
pReg->data = (RegDataPtr)NULL;
}
else
{
pReg->extents = miEmptyBox;
if ((size > 1) && (pReg->data = xallocData(size)))
{
pReg->data->size = size;
pReg->data->numRects = 0;
}
else
pReg->data = &miEmptyData;
}
return(pReg);
}
void
miRegionInit(pReg, rect, size)
RegionPtr pReg;
BoxPtr rect;
int size;
{
if (rect)
{
pReg->extents = *rect;
pReg->data = (RegDataPtr)NULL;
}
else
{
pReg->extents = miEmptyBox;
if ((size > 1) && (pReg->data = xallocData(size)))
{
pReg->data->size = size;
pReg->data->numRects = 0;
}
else
pReg->data = &miEmptyData;
}
}
void
miRegionDestroy(pReg)
RegionPtr pReg;
{
good(pReg);
xfreeData(pReg);
if (pReg != &miBrokenRegion)
xfree(pReg);
}
void
miRegionUninit(pReg)
RegionPtr pReg;
{
good(pReg);
xfreeData(pReg);
}
Bool
miRegionBreak (pReg)
RegionPtr pReg;
{
xfreeData (pReg);
pReg->extents = miEmptyBox;
pReg->data = &miBrokenData;
return FALSE;
}
Bool
miRectAlloc(
register RegionPtr pRgn,
int n)
{
RegDataPtr data;
if (!pRgn->data)
{
n++;
pRgn->data = xallocData(n);
if (!pRgn->data)
return miRegionBreak (pRgn);
pRgn->data->numRects = 1;
*REGION_BOXPTR(pRgn) = pRgn->extents;
}
else if (!pRgn->data->size)
{
pRgn->data = xallocData(n);
if (!pRgn->data)
return miRegionBreak (pRgn);
pRgn->data->numRects = 0;
}
else
{
if (n == 1)
{
n = pRgn->data->numRects;
if (n > 500)
n = 250;
}
n += pRgn->data->numRects;
data = (RegDataPtr)xrealloc(pRgn->data, REGION_SZOF(n));
if (!data)
return miRegionBreak (pRgn);
pRgn->data = data;
}
pRgn->data->size = n;
return TRUE;
}
Bool
miRegionCopy(dst, src)
register RegionPtr dst;
register RegionPtr src;
{
good(dst);
good(src);
if (dst == src)
return TRUE;
dst->extents = src->extents;
if (!src->data || !src->data->size)
{
xfreeData(dst);
dst->data = src->data;
return TRUE;
}
if (!dst->data || (dst->data->size < src->data->numRects))
{
xfreeData(dst);
dst->data = xallocData(src->data->numRects);
if (!dst->data)
return miRegionBreak (dst);
dst->data->size = src->data->numRects;
}
dst->data->numRects = src->data->numRects;
memmove((char *)REGION_BOXPTR(dst),(char *)REGION_BOXPTR(src),
dst->data->numRects * sizeof(BoxRec));
return TRUE;
}
INLINE static int
miCoalesce (
register RegionPtr pReg,
int prevStart,
int curStart)
{
register BoxPtr pPrevBox;
register BoxPtr pCurBox;
register int numRects;
register int y2;
numRects = curStart - prevStart;
assert(numRects == pReg->data->numRects - curStart);
if (!numRects) return curStart;
pPrevBox = REGION_BOX(pReg, prevStart);
pCurBox = REGION_BOX(pReg, curStart);
if (pPrevBox->y2 != pCurBox->y1) return curStart;
y2 = pCurBox->y2;
do {
if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
return (curStart);
}
pPrevBox++;
pCurBox++;
numRects--;
} while (numRects);
numRects = curStart - prevStart;
pReg->data->numRects -= numRects;
do {
pPrevBox--;
pPrevBox->y2 = y2;
numRects--;
} while (numRects);
return prevStart;
}
#define Coalesce(newReg, prevBand, curBand) \
if (curBand - prevBand == newReg->data->numRects - curBand) { \
prevBand = miCoalesce(newReg, prevBand, curBand); \
} else { \
prevBand = curBand; \
}
INLINE static Bool
miAppendNonO (
register RegionPtr pReg,
register BoxPtr r,
BoxPtr rEnd,
register int y1,
register int y2)
{
register BoxPtr pNextRect;
register int newRects;
newRects = rEnd - r;
assert(y1 < y2);
assert(newRects != 0);
RECTALLOC(pReg, newRects);
pNextRect = REGION_TOP(pReg);
pReg->data->numRects += newRects;
do {
assert(r->x1 < r->x2);
ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
r++;
} while (r != rEnd);
return TRUE;
}
#define FindBand(r, rBandEnd, rEnd, ry1) \
{ \
ry1 = r->y1; \
rBandEnd = r+1; \
while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
rBandEnd++; \
} \
}
#define AppendRegions(newReg, r, rEnd) \
{ \
int newRects; \
if ((newRects = rEnd - r)) { \
RECTALLOC(newReg, newRects); \
memmove((char *)REGION_TOP(newReg),(char *)r, \
newRects * sizeof(BoxRec)); \
newReg->data->numRects += newRects; \
} \
}
typedef Bool (*OverlapProcPtr)(
RegionPtr pReg,
BoxPtr r1,
BoxPtr r1End,
BoxPtr r2,
BoxPtr r2End,
short y1,
short y2,
Bool *pOverlap);
static Bool
miRegionOp(
RegionPtr newReg,
RegionPtr reg1,
RegionPtr reg2,
OverlapProcPtr overlapFunc,
Bool appendNon1,
Bool appendNon2,
Bool *pOverlap)
{
register BoxPtr r1;
register BoxPtr r2;
BoxPtr r1End;
BoxPtr r2End;
short ybot;
short ytop;
RegDataPtr oldData;
int prevBand;
int curBand;
register BoxPtr r1BandEnd;
register BoxPtr r2BandEnd;
short top;
short bot;
register int r1y1;
register int r2y1;
int newSize;
int numRects;
if (REGION_NAR (reg1) || REGION_NAR(reg2))
return miRegionBreak (newReg);
r1 = REGION_RECTS(reg1);
newSize = REGION_NUM_RECTS(reg1);
r1End = r1 + newSize;
numRects = REGION_NUM_RECTS(reg2);
r2 = REGION_RECTS(reg2);
r2End = r2 + numRects;
assert(r1 != r1End);
assert(r2 != r2End);
oldData = (RegDataPtr)NULL;
if (((newReg == reg1) && (newSize > 1)) ||
((newReg == reg2) && (numRects > 1)))
{
oldData = newReg->data;
newReg->data = &miEmptyData;
}
if (numRects > newSize)
newSize = numRects;
newSize <<= 1;
if (!newReg->data)
newReg->data = &miEmptyData;
else if (newReg->data->size)
newReg->data->numRects = 0;
if (newSize > newReg->data->size)
if (!miRectAlloc(newReg, newSize))
return FALSE;
ybot = min(r1->y1, r2->y1);
prevBand = 0;
do {
assert(r1 != r1End);
assert(r2 != r2End);
FindBand(r1, r1BandEnd, r1End, r1y1);
FindBand(r2, r2BandEnd, r2End, r2y1);
if (r1y1 < r2y1) {
if (appendNon1) {
top = max(r1y1, ybot);
bot = min(r1->y2, r2y1);
if (top != bot) {
curBand = newReg->data->numRects;
miAppendNonO(newReg, r1, r1BandEnd, top, bot);
Coalesce(newReg, prevBand, curBand);
}
}
ytop = r2y1;
} else if (r2y1 < r1y1) {
if (appendNon2) {
top = max(r2y1, ybot);
bot = min(r2->y2, r1y1);
if (top != bot) {
curBand = newReg->data->numRects;
miAppendNonO(newReg, r2, r2BandEnd, top, bot);
Coalesce(newReg, prevBand, curBand);
}
}
ytop = r1y1;
} else {
ytop = r1y1;
}
ybot = min(r1->y2, r2->y2);
if (ybot > ytop) {
curBand = newReg->data->numRects;
(* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
pOverlap);
Coalesce(newReg, prevBand, curBand);
}
if (r1->y2 == ybot) r1 = r1BandEnd;
if (r2->y2 == ybot) r2 = r2BandEnd;
} while (r1 != r1End && r2 != r2End);
if ((r1 != r1End) && appendNon1) {
FindBand(r1, r1BandEnd, r1End, r1y1);
curBand = newReg->data->numRects;
miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2);
Coalesce(newReg, prevBand, curBand);
AppendRegions(newReg, r1BandEnd, r1End);
} else if ((r2 != r2End) && appendNon2) {
FindBand(r2, r2BandEnd, r2End, r2y1);
curBand = newReg->data->numRects;
miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);
Coalesce(newReg, prevBand, curBand);
AppendRegions(newReg, r2BandEnd, r2End);
}
if (oldData)
xfree(oldData);
if (!(numRects = newReg->data->numRects))
{
xfreeData(newReg);
newReg->data = &miEmptyData;
}
else if (numRects == 1)
{
newReg->extents = *REGION_BOXPTR(newReg);
xfreeData(newReg);
newReg->data = (RegDataPtr)NULL;
}
else
{
DOWNSIZE(newReg, numRects);
}
return TRUE;
}
void
miSetExtents (pReg)
register RegionPtr pReg;
{
register BoxPtr pBox, pBoxEnd;
if (!pReg->data)
return;
if (!pReg->data->size)
{
pReg->extents.x2 = pReg->extents.x1;
pReg->extents.y2 = pReg->extents.y1;
return;
}
pBox = REGION_BOXPTR(pReg);
pBoxEnd = REGION_END(pReg);
pReg->extents.x1 = pBox->x1;
pReg->extents.y1 = pBox->y1;
pReg->extents.x2 = pBoxEnd->x2;
pReg->extents.y2 = pBoxEnd->y2;
assert(pReg->extents.y1 < pReg->extents.y2);
while (pBox <= pBoxEnd) {
if (pBox->x1 < pReg->extents.x1)
pReg->extents.x1 = pBox->x1;
if (pBox->x2 > pReg->extents.x2)
pReg->extents.x2 = pBox->x2;
pBox++;
};
assert(pReg->extents.x1 < pReg->extents.x2);
}
static Bool
miIntersectO (
register RegionPtr pReg,
register BoxPtr r1,
BoxPtr r1End,
register BoxPtr r2,
BoxPtr r2End,
short y1,
short y2,
Bool *pOverlap)
{
register int x1;
register int x2;
register BoxPtr pNextRect;
pNextRect = REGION_TOP(pReg);
assert(y1 < y2);
assert(r1 != r1End && r2 != r2End);
do {
x1 = max(r1->x1, r2->x1);
x2 = min(r1->x2, r2->x2);
if (x1 < x2)
NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
if (r1->x2 == x2) {
r1++;
}
if (r2->x2 == x2) {
r2++;
}
} while ((r1 != r1End) && (r2 != r2End));
return TRUE;
}
Bool
miIntersect(newReg, reg1, reg2)
register RegionPtr newReg;
register RegionPtr reg1;
register RegionPtr reg2;
{
good(reg1);
good(reg2);
good(newReg);
if (REGION_NIL(reg1) || REGION_NIL(reg2) ||
!EXTENTCHECK(®1->extents, ®2->extents))
{
xfreeData(newReg);
newReg->extents.x2 = newReg->extents.x1;
newReg->extents.y2 = newReg->extents.y1;
if (REGION_NAR(reg1) || REGION_NAR(reg2))
{
newReg->data = &miBrokenData;
return FALSE;
}
else
newReg->data = &miEmptyData;
}
else if (!reg1->data && !reg2->data)
{
newReg->extents.x1 = max(reg1->extents.x1, reg2->extents.x1);
newReg->extents.y1 = max(reg1->extents.y1, reg2->extents.y1);
newReg->extents.x2 = min(reg1->extents.x2, reg2->extents.x2);
newReg->extents.y2 = min(reg1->extents.y2, reg2->extents.y2);
xfreeData(newReg);
newReg->data = (RegDataPtr)NULL;
}
else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
{
return miRegionCopy(newReg, reg1);
}
else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
{
return miRegionCopy(newReg, reg2);
}
else if (reg1 == reg2)
{
return miRegionCopy(newReg, reg1);
}
else
{
Bool overlap;
if (!miRegionOp(newReg, reg1, reg2, miIntersectO, FALSE, FALSE,
&overlap))
return FALSE;
miSetExtents(newReg);
}
good(newReg);
return(TRUE);
}
#define MERGERECT(r) \
{ \
if (r->x1 <= x2) { \
\
if (r->x1 < x2) *pOverlap = TRUE; \
if (x2 < r->x2) x2 = r->x2; \
} else { \
\
NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \
x1 = r->x1; \
x2 = r->x2; \
} \
r++; \
}
static Bool
miUnionO (
register RegionPtr pReg,
register BoxPtr r1,
BoxPtr r1End,
register BoxPtr r2,
BoxPtr r2End,
short y1,
short y2,
Bool *pOverlap)
{
register BoxPtr pNextRect;
register int x1;
register int x2;
assert (y1 < y2);
assert(r1 != r1End && r2 != r2End);
pNextRect = REGION_TOP(pReg);
if (r1->x1 < r2->x1)
{
x1 = r1->x1;
x2 = r1->x2;
r1++;
}
else
{
x1 = r2->x1;
x2 = r2->x2;
r2++;
}
while (r1 != r1End && r2 != r2End)
{
if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
}
if (r1 != r1End)
{
do
{
MERGERECT(r1);
} while (r1 != r1End);
}
else if (r2 != r2End)
{
do
{
MERGERECT(r2);
} while (r2 != r2End);
}
NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
return TRUE;
}
Bool
miUnion(newReg, reg1, reg2)
RegionPtr newReg;
register RegionPtr reg1;
register RegionPtr reg2;
{
Bool overlap;
good(reg1);
good(reg2);
good(newReg);
if (reg1 == reg2)
{
return miRegionCopy(newReg, reg1);
}
if (REGION_NIL(reg1))
{
if (REGION_NAR(reg1))
return miRegionBreak (newReg);
if (newReg != reg2)
return miRegionCopy(newReg, reg2);
return TRUE;
}
if (REGION_NIL(reg2))
{
if (REGION_NAR(reg2))
return miRegionBreak (newReg);
if (newReg != reg1)
return miRegionCopy(newReg, reg1);
return TRUE;
}
if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
{
if (newReg != reg1)
return miRegionCopy(newReg, reg1);
return TRUE;
}
if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
{
if (newReg != reg2)
return miRegionCopy(newReg, reg2);
return TRUE;
}
if (!miRegionOp(newReg, reg1, reg2, miUnionO, TRUE, TRUE, &overlap))
return FALSE;
newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
good(newReg);
return TRUE;
}
Bool
miRegionAppend(dstrgn, rgn)
register RegionPtr dstrgn;
register RegionPtr rgn;
{
int numRects, dnumRects, size;
BoxPtr new, old;
Bool prepend;
if (REGION_NAR(rgn))
return miRegionBreak (dstrgn);
if (!rgn->data && (dstrgn->data == &miEmptyData))
{
dstrgn->extents = rgn->extents;
dstrgn->data = (RegDataPtr)NULL;
return TRUE;
}
numRects = REGION_NUM_RECTS(rgn);
if (!numRects)
return TRUE;
prepend = FALSE;
size = numRects;
dnumRects = REGION_NUM_RECTS(dstrgn);
if (!dnumRects && (size < 200))
size = 200;
RECTALLOC(dstrgn, size);
old = REGION_RECTS(rgn);
if (!dnumRects)
dstrgn->extents = rgn->extents;
else if (dstrgn->extents.x2 > dstrgn->extents.x1)
{
register BoxPtr first, last;
first = old;
last = REGION_BOXPTR(dstrgn) + (dnumRects - 1);
if ((first->y1 > last->y2) ||
((first->y1 == last->y1) && (first->y2 == last->y2) &&
(first->x1 > last->x2)))
{
if (rgn->extents.x1 < dstrgn->extents.x1)
dstrgn->extents.x1 = rgn->extents.x1;
if (rgn->extents.x2 > dstrgn->extents.x2)
dstrgn->extents.x2 = rgn->extents.x2;
dstrgn->extents.y2 = rgn->extents.y2;
}
else
{
first = REGION_BOXPTR(dstrgn);
last = old + (numRects - 1);
if ((first->y1 > last->y2) ||
((first->y1 == last->y1) && (first->y2 == last->y2) &&
(first->x1 > last->x2)))
{
prepend = TRUE;
if (rgn->extents.x1 < dstrgn->extents.x1)
dstrgn->extents.x1 = rgn->extents.x1;
if (rgn->extents.x2 > dstrgn->extents.x2)
dstrgn->extents.x2 = rgn->extents.x2;
dstrgn->extents.y1 = rgn->extents.y1;
}
else
dstrgn->extents.x2 = dstrgn->extents.x1;
}
}
if (prepend)
{
new = REGION_BOX(dstrgn, numRects);
if (dnumRects == 1)
*new = *REGION_BOXPTR(dstrgn);
else
memmove((char *)new,(char *)REGION_BOXPTR(dstrgn),
dnumRects * sizeof(BoxRec));
new = REGION_BOXPTR(dstrgn);
}
else
new = REGION_BOXPTR(dstrgn) + dnumRects;
if (numRects == 1)
*new = *old;
else
memmove((char *)new, (char *)old, numRects * sizeof(BoxRec));
dstrgn->data->numRects += numRects;
return TRUE;
}
#define ExchangeRects(a, b) \
{ \
BoxRec t; \
t = rects[a]; \
rects[a] = rects[b]; \
rects[b] = t; \
}
static void
QuickSortRects(
register BoxRec rects[],
register int numRects)
{
register int y1;
register int x1;
register int i, j;
register BoxPtr r;
do
{
if (numRects == 2)
{
if (rects[0].y1 > rects[1].y1 ||
(rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
ExchangeRects(0, 1);
return;
}
ExchangeRects(0, numRects >> 1);
y1 = rects[0].y1;
x1 = rects[0].x1;
i = 0;
j = numRects;
do
{
r = &(rects[i]);
do
{
r++;
i++;
} while (i != numRects &&
(r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
r = &(rects[j]);
do
{
r--;
j--;
} while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
if (i < j)
ExchangeRects(i, j);
} while (i < j);
ExchangeRects(0, j);
if (numRects-j-1 > 1)
QuickSortRects(&rects[j+1], numRects-j-1);
numRects = j;
} while (numRects > 1);
}
Bool
miRegionValidate(badreg, pOverlap)
RegionPtr badreg;
Bool *pOverlap;
{
typedef struct {
RegionRec reg;
int prevBand;
int curBand;
} RegionInfo;
int numRects;
RegionInfo *ri;
int numRI;
int sizeRI;
int i;
register int j;
register RegionInfo *rit;
register RegionPtr reg;
register BoxPtr box;
register BoxPtr riBox;
register RegionPtr hreg;
Bool ret = TRUE;
*pOverlap = FALSE;
if (!badreg->data)
{
good(badreg);
return TRUE;
}
numRects = badreg->data->numRects;
if (!numRects)
{
if (REGION_NAR(badreg))
return FALSE;
good(badreg);
return TRUE;
}
if (badreg->extents.x1 < badreg->extents.x2)
{
if ((numRects) == 1)
{
xfreeData(badreg);
badreg->data = (RegDataPtr) NULL;
}
else
{
DOWNSIZE(badreg, numRects);
}
good(badreg);
return TRUE;
}
QuickSortRects(REGION_BOXPTR(badreg), numRects);
ri = (RegionInfo *) xalloc(4 * sizeof(RegionInfo));
if (!ri)
return miRegionBreak (badreg);
sizeRI = 4;
numRI = 1;
ri[0].prevBand = 0;
ri[0].curBand = 0;
ri[0].reg = *badreg;
box = REGION_BOXPTR(&ri[0].reg);
ri[0].reg.extents = *box;
ri[0].reg.data->numRects = 1;
for (i = numRects; --i > 0;)
{
box++;
for (j = numRI, rit = ri; --j >= 0; rit++)
{
reg = &rit->reg;
riBox = REGION_END(reg);
if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
{
if (box->x1 <= riBox->x2)
{
if (box->x1 < riBox->x2) *pOverlap = TRUE;
if (box->x2 > riBox->x2) riBox->x2 = box->x2;
}
else
{
RECTALLOC_BAIL(reg, 1, bail);
*REGION_TOP(reg) = *box;
reg->data->numRects++;
}
goto NextRect;
}
else if (box->y1 >= riBox->y2)
{
if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
Coalesce(reg, rit->prevBand, rit->curBand);
rit->curBand = reg->data->numRects;
RECTALLOC_BAIL(reg, 1, bail);
*REGION_TOP(reg) = *box;
reg->data->numRects++;
goto NextRect;
}
}
if (sizeRI == numRI)
{
sizeRI <<= 1;
rit = (RegionInfo *) xrealloc(ri, sizeRI * sizeof(RegionInfo));
if (!rit)
goto bail;
ri = rit;
rit = &ri[numRI];
}
numRI++;
rit->prevBand = 0;
rit->curBand = 0;
rit->reg.extents = *box;
rit->reg.data = (RegDataPtr)NULL;
if (!miRectAlloc(&rit->reg, (i+numRI) / numRI))
goto bail;
NextRect: ;
}
for (j = numRI, rit = ri; --j >= 0; rit++)
{
reg = &rit->reg;
riBox = REGION_END(reg);
reg->extents.y2 = riBox->y2;
if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
Coalesce(reg, rit->prevBand, rit->curBand);
if (reg->data->numRects == 1)
{
xfreeData(reg);
reg->data = (RegDataPtr)NULL;
}
}
while (numRI > 1)
{
int half = numRI/2;
for (j = numRI & 1; j < (half + (numRI & 1)); j++)
{
reg = &ri[j].reg;
hreg = &ri[j+half].reg;
if (!miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap))
ret = FALSE;
if (hreg->extents.x1 < reg->extents.x1)
reg->extents.x1 = hreg->extents.x1;
if (hreg->extents.y1 < reg->extents.y1)
reg->extents.y1 = hreg->extents.y1;
if (hreg->extents.x2 > reg->extents.x2)
reg->extents.x2 = hreg->extents.x2;
if (hreg->extents.y2 > reg->extents.y2)
reg->extents.y2 = hreg->extents.y2;
xfreeData(hreg);
}
numRI -= half;
}
*badreg = ri[0].reg;
xfree(ri);
good(badreg);
return ret;
bail:
for (i = 0; i < numRI; i++)
xfreeData(&ri[i].reg);
xfree (ri);
return miRegionBreak (badreg);
}
RegionPtr
miRectsToRegion(nrects, prect, ctype)
int nrects;
register xRectangle *prect;
int ctype;
{
register RegionPtr pRgn;
register RegDataPtr pData;
register BoxPtr pBox;
register int i;
int x1, y1, x2, y2;
pRgn = miRegionCreate(NullBox, 0);
if (REGION_NAR (pRgn))
return pRgn;
if (!nrects)
return pRgn;
if (nrects == 1)
{
x1 = prect->x;
y1 = prect->y;
if ((x2 = x1 + (int) prect->width) > MAXSHORT)
x2 = MAXSHORT;
if ((y2 = y1 + (int) prect->height) > MAXSHORT)
y2 = MAXSHORT;
if (x1 != x2 && y1 != y2)
{
pRgn->extents.x1 = x1;
pRgn->extents.y1 = y1;
pRgn->extents.x2 = x2;
pRgn->extents.y2 = y2;
pRgn->data = (RegDataPtr)NULL;
}
return pRgn;
}
pData = xallocData(nrects);
if (!pData)
{
miRegionBreak (pRgn);
return pRgn;
}
pBox = (BoxPtr) (pData + 1);
for (i = nrects; --i >= 0; prect++)
{
x1 = prect->x;
y1 = prect->y;
if ((x2 = x1 + (int) prect->width) > MAXSHORT)
x2 = MAXSHORT;
if ((y2 = y1 + (int) prect->height) > MAXSHORT)
y2 = MAXSHORT;
if (x1 != x2 && y1 != y2)
{
pBox->x1 = x1;
pBox->y1 = y1;
pBox->x2 = x2;
pBox->y2 = y2;
pBox++;
}
}
if (pBox != (BoxPtr) (pData + 1))
{
pData->size = nrects;
pData->numRects = pBox - (BoxPtr) (pData + 1);
pRgn->data = pData;
if (ctype != CT_YXBANDED)
{
Bool overlap;
pRgn->extents.x1 = pRgn->extents.x2 = 0;
miRegionValidate(pRgn, &overlap);
}
else
miSetExtents(pRgn);
good(pRgn);
}
else
{
xfree (pData);
}
return pRgn;
}
static Bool
miSubtractO (
register RegionPtr pReg,
register BoxPtr r1,
BoxPtr r1End,
register BoxPtr r2,
BoxPtr r2End,
register short y1,
short y2,
Bool *pOverlap)
{
register BoxPtr pNextRect;
register int x1;
x1 = r1->x1;
assert(y1<y2);
assert(r1 != r1End && r2 != r2End);
pNextRect = REGION_TOP(pReg);
do
{
if (r2->x2 <= x1)
{
r2++;
}
else if (r2->x1 <= x1)
{
x1 = r2->x2;
if (x1 >= r1->x2)
{
r1++;
if (r1 != r1End)
x1 = r1->x1;
}
else
{
r2++;
}
}
else if (r2->x1 < r1->x2)
{
assert(x1<r2->x1);
NEWRECT(pReg, pNextRect, x1, y1, r2->x1, y2);
x1 = r2->x2;
if (x1 >= r1->x2)
{
r1++;
if (r1 != r1End)
x1 = r1->x1;
}
else
{
r2++;
}
}
else
{
if (r1->x2 > x1)
NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
r1++;
if (r1 != r1End)
x1 = r1->x1;
}
} while ((r1 != r1End) && (r2 != r2End));
while (r1 != r1End)
{
assert(x1<r1->x2);
NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
r1++;
if (r1 != r1End)
x1 = r1->x1;
}
return TRUE;
}
Bool
miSubtract(regD, regM, regS)
register RegionPtr regD;
register RegionPtr regM;
register RegionPtr regS;
{
Bool overlap;
good(regM);
good(regS);
good(regD);
if (REGION_NIL(regM) || REGION_NIL(regS) ||
!EXTENTCHECK(®M->extents, ®S->extents))
{
if (REGION_NAR (regS))
return miRegionBreak (regD);
return miRegionCopy(regD, regM);
}
else if (regM == regS)
{
xfreeData(regD);
regD->extents.x2 = regD->extents.x1;
regD->extents.y2 = regD->extents.y1;
regD->data = &miEmptyData;
return TRUE;
}
if (!miRegionOp(regD, regM, regS, miSubtractO, TRUE, FALSE, &overlap))
return FALSE;
miSetExtents(regD);
good(regD);
return TRUE;
}
Bool
miInverse(newReg, reg1, invRect)
RegionPtr newReg;
RegionPtr reg1;
BoxPtr invRect;
{
RegionRec invReg;
Bool overlap;
good(reg1);
good(newReg);
if (REGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
{
if (REGION_NAR(reg1))
return miRegionBreak (newReg);
newReg->extents = *invRect;
xfreeData(newReg);
newReg->data = (RegDataPtr)NULL;
return TRUE;
}
invReg.extents = *invRect;
invReg.data = (RegDataPtr)NULL;
if (!miRegionOp(newReg, &invReg, reg1, miSubtractO, TRUE, FALSE, &overlap))
return FALSE;
miSetExtents(newReg);
good(newReg);
return TRUE;
}
int
miRectIn(region, prect)
register RegionPtr region;
register BoxPtr prect;
{
register int x;
register int y;
register BoxPtr pbox;
register BoxPtr pboxEnd;
int partIn, partOut;
int numRects;
good(region);
numRects = REGION_NUM_RECTS(region);
if (!numRects || !EXTENTCHECK(®ion->extents, prect))
return(rgnOUT);
if (numRects == 1)
{
if (SUBSUMES(®ion->extents, prect))
return(rgnIN);
else
return(rgnPART);
}
partOut = FALSE;
partIn = FALSE;
x = prect->x1;
y = prect->y1;
for (pbox = REGION_BOXPTR(region), pboxEnd = pbox + numRects;
pbox != pboxEnd;
pbox++)
{
if (pbox->y2 <= y)
continue;
if (pbox->y1 > y)
{
partOut = TRUE;
if (partIn || (pbox->y1 >= prect->y2))
break;
y = pbox->y1;
}
if (pbox->x2 <= x)
continue;
if (pbox->x1 > x)
{
partOut = TRUE;
if (partIn)
break;
}
if (pbox->x1 < prect->x2)
{
partIn = TRUE;
if (partOut)
break;
}
if (pbox->x2 >= prect->x2)
{
y = pbox->y2;
if (y >= prect->y2)
break;
x = prect->x1;
}
else
{
partOut = TRUE;
break;
}
}
return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
}
void
miTranslateRegion(pReg, x, y)
register RegionPtr pReg;
register int x;
register int y;
{
int x1, x2, y1, y2;
register int nbox;
register BoxPtr pbox;
good(pReg);
pReg->extents.x1 = x1 = pReg->extents.x1 + x;
pReg->extents.y1 = y1 = pReg->extents.y1 + y;
pReg->extents.x2 = x2 = pReg->extents.x2 + x;
pReg->extents.y2 = y2 = pReg->extents.y2 + y;
if (((x1 - MINSHORT)|(y1 - MINSHORT)|(MAXSHORT - x2)|(MAXSHORT - y2)) >= 0)
{
if (pReg->data && (nbox = pReg->data->numRects))
{
for (pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
{
pbox->x1 += x;
pbox->y1 += y;
pbox->x2 += x;
pbox->y2 += y;
}
}
return;
}
if (((x2 - MINSHORT)|(y2 - MINSHORT)|(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
{
pReg->extents.x2 = pReg->extents.x1;
pReg->extents.y2 = pReg->extents.y1;
xfreeData(pReg);
pReg->data = &miEmptyData;
return;
}
if (x1 < MINSHORT)
pReg->extents.x1 = MINSHORT;
else if (x2 > MAXSHORT)
pReg->extents.x2 = MAXSHORT;
if (y1 < MINSHORT)
pReg->extents.y1 = MINSHORT;
else if (y2 > MAXSHORT)
pReg->extents.y2 = MAXSHORT;
if (pReg->data && (nbox = pReg->data->numRects))
{
register BoxPtr pboxout;
for (pboxout = pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
{
pboxout->x1 = x1 = pbox->x1 + x;
pboxout->y1 = y1 = pbox->y1 + y;
pboxout->x2 = x2 = pbox->x2 + x;
pboxout->y2 = y2 = pbox->y2 + y;
if (((x2 - MINSHORT)|(y2 - MINSHORT)|
(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
{
pReg->data->numRects--;
continue;
}
if (x1 < MINSHORT)
pboxout->x1 = MINSHORT;
else if (x2 > MAXSHORT)
pboxout->x2 = MAXSHORT;
if (y1 < MINSHORT)
pboxout->y1 = MINSHORT;
else if (y2 > MAXSHORT)
pboxout->y2 = MAXSHORT;
pboxout++;
}
if (pboxout != pbox)
{
if (pReg->data->numRects == 1)
{
pReg->extents = *REGION_BOXPTR(pReg);
xfreeData(pReg);
pReg->data = (RegDataPtr)NULL;
}
else
miSetExtents(pReg);
}
}
}
Bool
miRegionDataCopy(
register RegionPtr dst,
register RegionPtr src)
{
good(dst);
good(src);
if (dst->data)
return TRUE;
if (dst == src)
return TRUE;
if (!src->data || !src->data->size)
{
xfreeData(dst);
dst->data = (RegDataPtr)NULL;
return TRUE;
}
if (!dst->data || (dst->data->size < src->data->numRects))
{
xfreeData(dst);
dst->data = xallocData(src->data->numRects);
if (!dst->data)
return miRegionBreak (dst);
}
dst->data->size = src->data->size;
dst->data->numRects = src->data->numRects;
return TRUE;
}
void
miRegionReset(pReg, pBox)
RegionPtr pReg;
BoxPtr pBox;
{
good(pReg);
assert(pBox->x1<=pBox->x2);
assert(pBox->y1<=pBox->y2);
pReg->extents = *pBox;
xfreeData(pReg);
pReg->data = (RegDataPtr)NULL;
}
Bool
miPointInRegion(pReg, x, y, box)
register RegionPtr pReg;
register int x, y;
BoxPtr box;
{
register BoxPtr pbox, pboxEnd;
int numRects;
good(pReg);
numRects = REGION_NUM_RECTS(pReg);
if (!numRects || !INBOX(&pReg->extents, x, y))
return(FALSE);
if (numRects == 1)
{
*box = pReg->extents;
return(TRUE);
}
for (pbox = REGION_BOXPTR(pReg), pboxEnd = pbox + numRects;
pbox != pboxEnd;
pbox++)
{
if (y >= pbox->y2)
continue;
if ((y < pbox->y1) || (x < pbox->x1))
break;
if (x >= pbox->x2)
continue;
*box = *pbox;
return(TRUE);
}
return(FALSE);
}
Bool
miRegionNotEmpty(pReg)
RegionPtr pReg;
{
good(pReg);
return(!REGION_NIL(pReg));
}
Bool
miRegionBroken(RegionPtr pReg)
{
good(pReg);
return (REGION_NAR(pReg));
}
void
miRegionEmpty(pReg)
RegionPtr pReg;
{
good(pReg);
xfreeData(pReg);
pReg->extents.x2 = pReg->extents.x1;
pReg->extents.y2 = pReg->extents.y1;
pReg->data = &miEmptyData;
}
BoxPtr
miRegionExtents(pReg)
RegionPtr pReg;
{
good(pReg);
return(&pReg->extents);
}
#define ExchangeSpans(a, b) \
{ \
DDXPointRec tpt; \
register int tw; \
\
tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \
tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
}
static void QuickSortSpans(
register DDXPointRec spans[],
register int widths[],
register int numSpans)
{
register int y;
register int i, j, m;
register DDXPointPtr r;
do
{
if (numSpans < 9)
{
register int yprev;
yprev = spans[0].y;
i = 1;
do
{
y = spans[i].y;
if (yprev > y)
{
DDXPointRec tpt;
int tw, k;
for (j = 0; y >= spans[j].y; j++) {}
tpt = spans[i];
tw = widths[i];
for (k = i; k != j; k--)
{
spans[k] = spans[k-1];
widths[k] = widths[k-1];
}
spans[j] = tpt;
widths[j] = tw;
y = spans[i].y;
}
yprev = y;
i++;
} while (i != numSpans);
return;
}
m = numSpans / 2;
if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1);
if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
y = spans[0].y;
i = 0;
j = numSpans;
do
{
r = &(spans[i]);
do
{
r++;
i++;
} while (i != numSpans && r->y < y);
r = &(spans[j]);
do
{
r--;
j--;
} while (y < r->y);
if (i < j)
ExchangeSpans(i, j);
} while (i < j);
ExchangeSpans(0, j);
if (numSpans-j-1 > 1)
QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
numSpans = j;
} while (numSpans > 1);
}
#define NextBand() \
{ \
clipy1 = pboxBandStart->y1; \
clipy2 = pboxBandStart->y2; \
pboxBandEnd = pboxBandStart + 1; \
while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \
pboxBandEnd++; \
} \
for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
}
int
miClipSpans(
RegionPtr prgnDst,
register DDXPointPtr ppt,
register int *pwidth,
int nspans,
register DDXPointPtr pptNew,
int *pwidthNew,
int fSorted)
{
register DDXPointPtr pptLast;
int *pwidthNewStart;
register int y, x1, x2;
register int numRects;
good(prgnDst);
pptLast = ppt + nspans;
pwidthNewStart = pwidthNew;
if (!prgnDst->data)
{
register int clipx1, clipx2, clipy1, clipy2;
clipx1 = prgnDst->extents.x1;
clipy1 = prgnDst->extents.y1;
clipx2 = prgnDst->extents.x2;
clipy2 = prgnDst->extents.y2;
for (; ppt != pptLast; ppt++, pwidth++)
{
y = ppt->y;
x1 = ppt->x;
if (clipy1 <= y && y < clipy2)
{
x2 = x1 + *pwidth;
if (x1 < clipx1) x1 = clipx1;
if (x2 > clipx2) x2 = clipx2;
if (x1 < x2)
{
pptNew->x = x1;
pptNew->y = y;
*pwidthNew = x2 - x1;
pptNew++;
pwidthNew++;
}
}
}
}
else if ((numRects = prgnDst->data->numRects))
{
BoxPtr pboxBandStart, pboxBandEnd;
register BoxPtr pbox;
register BoxPtr pboxLast;
register int clipy1, clipy2;
if ((! fSorted) && (nspans > 1))
QuickSortSpans(ppt, pwidth, nspans);
pboxBandStart = REGION_BOXPTR(prgnDst);
pboxLast = pboxBandStart + numRects;
NextBand();
for (; ppt != pptLast; )
{
y = ppt->y;
if (y < clipy2)
{
pbox = pboxBandStart;
x1 = ppt->x;
x2 = x1 + *pwidth;
do
{
register int newx1, newx2;
newx1 = x1;
newx2 = x2;
if (newx1 < pbox->x1) newx1 = pbox->x1;
if (newx2 > pbox->x2) newx2 = pbox->x2;
if (newx1 < newx2)
{
pptNew->x = newx1;
pptNew->y = y;
*pwidthNew = newx2 - newx1;
pptNew++;
pwidthNew++;
}
pbox++;
} while (pbox != pboxBandEnd);
ppt++;
pwidth++;
}
else
{
pboxBandStart = pboxBandEnd;
if (pboxBandStart == pboxLast)
break;
NextBand();
}
}
}
return (pwidthNew - pwidthNewStart);
}
int
miFindMaxBand(prgn)
RegionPtr prgn;
{
register int nbox;
register BoxPtr pbox;
register int nThisBand;
register int nMaxBand = 0;
short yThisBand;
good(prgn);
nbox = REGION_NUM_RECTS(prgn);
pbox = REGION_RECTS(prgn);
while(nbox > 0)
{
yThisBand = pbox->y1;
nThisBand = 0;
while((nbox > 0) && (pbox->y1 == yThisBand))
{
nbox--;
pbox++;
nThisBand++;
}
if (nThisBand > nMaxBand)
nMaxBand = nThisBand;
}
return (nMaxBand);
}