/* 
 * ctkRegion.c (CTk) --
 *
 *	Geometry manipulation routines - regions (free form 2-D shapes),
 *	rectangles, and spans (horizontal segments).
 *
 *	Beware, some of theses routines have special constraints that
 *	are not obvious from their title.  Be sure to examine headers
 *	for constraints.
 *
 * Copyright (c) 1994-1995 Cleveland Clinic Foundation
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
 *
 * @(#) $Id: ctk.shar,v 1.50 1996/01/15 14:47:16 andrewm Exp andrewm $
 */

#include "tkPort.h"
#include "tkInt.h"

/*
 * Notes on Geometry Types.
 *
 * Spans -
 *	Horizontal line segment.  Between left point (inclusive)
 *	and right point (exclusive).  Any span with right <= left
 *	is considered empty.
 *
 * Rectangles -
 *	Analogous to spans top and left points are include,
 *	and right and bottom points are excluded from area
 *	rectangle.  Any rectangle with right <= left or
 *	bottom <= top is considered empty.
 *
 * Region -
 *	Free form area.  Contents of structure are opaque.
 *	!!! Vertical bounds of region cannot increase !!!
 *	The rectangle used with CtkCreateRegion() must have the
 *	maximum top and bottom for the region (the rectangle
 *	may still be empty if right <= left).
 */

/*
 *  Limits for x and y coordinates
 *  (choose these to work with systems where int is 16-bit).
 */
#define COORD_MAX           32767
#define COORD_MIN           -32768


/*
 * Component of a region
 */
typedef struct {
    int left;
    int right;
    int next;           /* Index of next span */
} RegionSpan;
#define NO_SPAN (-1)    /* Invalid index (indicates end of span list) */

struct CtkRegion {
    int top;
    int bottom;
    int free;
    int num_spans;
    RegionSpan *spans;
};

#define CopySpan(dst, src) (memcpy((dst), (src), sizeof(RegionSpan)))
#define FreeSpan(rgnPtr, index) \
	((rgnPtr)->spans[(index)].next \
	= (rgnPtr)->free, (rgnPtr)->free = (index))

/*
 * Private Function Declarations
 */
static void	PseudoUnionSpans _ANSI_ARGS_((int *leftPtr, int *rightPtr,
		    int left2, int right2));
static int	DeleteSpan _ANSI_ARGS_((CtkRegion * rgnPtr, int index,
		    int priorIndex));
static void	AppendSpan _ANSI_ARGS_((CtkRegion * rgnPtr, int index,
		    int left, int right));
static void	PrependSpan _ANSI_ARGS_((CtkRegion * rgnPtr, int index,
		    int left, int right));
static int	AllocSpan _ANSI_ARGS_((CtkRegion * rgnPtr));
static void	MergeSpan _ANSI_ARGS_((CtkRegion * rgnPtr, int left,
		    int right, int y));


/*
 *----------------------------------------------------------------------
 *
 * CtkIntersectSpans -- compute intersection of 2 spans
 *
 *	Compute the intersection of the span (*leftPtr,*rightPtr)
 *	and the span (left2,right2).
 *
 * Results:
 *	Stores the resulting span in `leftPtr' and `rightPtr'.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

void
CtkIntersectSpans(leftPtr, rightPtr, left2, right2)
    int *leftPtr;
    int *rightPtr;
    int left2;
    int right2;
{
    if (*leftPtr < left2)  *leftPtr = left2;
    if (*rightPtr > right2)  *rightPtr = right2;
}

/*
 *----------------------------------------------------------------------
 *
 * PseudoUnionSpans -- compute union of 2 spans
 *
 *	Compute the union of the span (*leftPtr,*rightPtr)
 *	and the span (left2,right2).  Assumes that the spans overlap.
 *	If they don't, the result will contain the area between the
 *	spans also.  (A real union would have to be capable of
 *	returning two disjoint spans.)
 *
 * Results:
 *	Stores the resulting span in `leftPtr' and `rightPtr'.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

static void
PseudoUnionSpans(leftPtr, rightPtr, left2, right2)
    int *leftPtr;
    int *rightPtr;
    int left2;
    int right2;
{
    if (*leftPtr > left2)  *leftPtr = left2;
    if (*rightPtr < right2)  *rightPtr = right2;
}

/*
 *----------------------------------------------------------------------
 *
 * CtkSpanMinusSpan - compute difference of 2 spans
 *
 *	Substract span (subL, subR) from span (srcL, srcR).
 *	(Find segment(s) in first span that do not overlap with
 *	second span.)
 *
 * Results:
 *	Returns the number of resultin spans (0-2).
 *	Stores the resulting span(s) in remsL[] and remsR[].
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

int
CtkSpanMinusSpan(srcL, srcR, subL, subR, remsL, remsR)
    int srcL;
    int srcR;
    int subL;
    int subR;
    int *remsL;
    int *remsR;
{
    int numRems = 0;

    if (srcR <= subL || srcL >= subR)  return (numRems);
    if (srcL < subL) {
	remsL[numRems] = srcL;
	remsR[numRems] = subL;
	numRems += 1;
    }
    if (srcR > subR) {
	remsL[numRems] = subR;
	remsR[numRems] = srcR;
	numRems += 1;
    }
    return (numRems);

}

/*
 *----------------------------------------------------------------------
 *
 * CtkIntersectRects -- compute intersection of two rectangles
 *
 *	Computer overlap between rectangles pointed to by
 *	r1Ptr and r2Ptr.
 *
 * Results:
 *	Stores clipped down rectangle in `r1Ptr'.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

void
CtkIntersectRects(r1Ptr, r2Ptr)
    Ctk_Rect * r1Ptr;
    CONST Ctk_Rect * r2Ptr;
{

    if (r1Ptr->left < r2Ptr->left)  r1Ptr->left = r2Ptr->left;
    if (r1Ptr->top < r2Ptr->top)  r1Ptr->top = r2Ptr->top;
    if (r1Ptr->right > r2Ptr->right)  r1Ptr->right = r2Ptr->right;
    if (r1Ptr->bottom > r2Ptr->bottom)  r1Ptr->bottom = r2Ptr->bottom;

}

/*
 *----------------------------------------------------------------------
 *
 * CtkCreateRegion -- create a new region
 *
 *	Create a new region and initialize it to the area of
 *	`rect'.
 *
 * Results:
 *	Returns pointer to new region.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

CtkRegion *
CtkCreateRegion(rect)
    Ctk_Rect * rect;
{
    CtkRegion * rgnPtr;
    int i;
    rgnPtr = (CtkRegion *) ckalloc(sizeof(CtkRegion));

    rgnPtr->top = rect->top;
    rgnPtr->bottom = rect->bottom;
    rgnPtr->free = NO_SPAN;
    rgnPtr->num_spans = rgnPtr->bottom - rgnPtr->top;
    if (rgnPtr->num_spans <= 0) {
    	rgnPtr->num_spans = 0;
    	rgnPtr->spans = (RegionSpan *) NULL;
    } else {
	rgnPtr->spans = (RegionSpan *)
		ckalloc(rgnPtr->num_spans * sizeof(RegionSpan));
	for (i=0; i < rgnPtr->num_spans; i++) {
	    rgnPtr->spans[i].left = rect->left;
	    rgnPtr->spans[i].right = rect->right;
	    rgnPtr->spans[i].next = NO_SPAN;
	}
    }
    return rgnPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * CtkDestroyRegion - release resources held by a region
 *
 *	Free resources for a region - region may not be referenced
 *	again.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Memory is freed.
 *
 *----------------------------------------------------------------------
 */

void
CtkDestroyRegion(rgnPtr)
    CtkRegion *rgnPtr;
{
    if (rgnPtr->spans) {
	ckfree((char *) rgnPtr->spans);
    }
    ckfree((char *) rgnPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * CtkRegionMinusRect - remove rectangular area from region
 *
 *	Substract area of rectangle `rectPtr' from region `rgnPtr'.
 *
 * Results:
 *	If `wantInter', returns the intersection of the region and
 *	the rectangle (as a new region - use CtkDestroyRegion() to
 *	get rid of it).
 *	Otherwise, returns NULL.
 *
 * Side effects:
 *	Contents of `rgnPtr' is changed.
 *
 *----------------------------------------------------------------------
 */

CtkRegion *
CtkRegionMinusRect(rgnPtr, rectPtr, wantInter)
    CtkRegion *rgnPtr;
    Ctk_Rect *rectPtr;
    int wantInter;
{
    int itop = rectPtr->top;
    int ibottom = rectPtr->bottom;
    RegionSpan *spans = rgnPtr->spans;
    int y;
    int idx;
    int lastIdx;
    int rems;
    int newLefts[2];
    int newRights[2];
    Ctk_Rect emptyRect;
    CtkRegion * intersection = NULL;

    CtkIntersectSpans(&itop, &ibottom, rgnPtr->top, rgnPtr->bottom);
    if (wantInter) {
	emptyRect.left = 0;
	emptyRect.top = itop;
	emptyRect.right = 0;
	emptyRect.bottom = ibottom;
	intersection = (CtkRegion *) CtkCreateRegion(&emptyRect);
    }

    for (y = itop; y < ibottom; y++) {
	lastIdx = NO_SPAN;
	idx = y - rgnPtr->top;
	while (idx != NO_SPAN) {
	    if (spans[idx].left >= rectPtr->right) {
		/*
		 * Remaining spans on this line are right of `rectPtr'
		 */
		break;
	    }
	    if (spans[idx].right <= rectPtr->left) {
		/*
		 * No overlap
		 */
		lastIdx = idx;
		idx = spans[idx].next;
	    } else {
		/*
		 * Rect and span overlap
		 */
		rems = CtkSpanMinusSpan(
		    spans[idx].left, spans[idx].right,
		    rectPtr->left, rectPtr->right,
		    newLefts, newRights);
		if (wantInter) {
		    CtkIntersectSpans(
			&spans[idx].left, &spans[idx].right,
			rectPtr->left, rectPtr->right );
		    MergeSpan(intersection,
			spans[idx].left, spans[idx].right, y);
		}
		switch (rems) {
		case 0:
		    idx = DeleteSpan(rgnPtr, idx, lastIdx);
		    break;
		case 1:
		    spans[idx].left = newLefts[0];
		    spans[idx].right = newRights[0];
		    lastIdx = idx;
		    idx = spans[idx].next;
		    break;
		case 2:
		    spans[idx].left = newLefts[0];
		    spans[idx].right = newRights[0];
		    AppendSpan(rgnPtr, idx, newLefts[1], newRights[1]);
		    spans = rgnPtr->spans;
		    lastIdx = spans[idx].next;
		    idx = spans[lastIdx].next;
		    break;
		}
	    }
	} /* for (idx) */
    } /* for (y) */
    return intersection;
}

/*
 *----------------------------------------------------------------------
 *
 * CtkUnionRegions - merge one region into another
 *
 *	Computes the union of the regions `rgn1Ptr' and `rgn2Ptr',
 *	and stores it in `rgn1Ptr'.
 *	!!! The union cannot increase the top and bottom of `rgn1' !!!
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	`rgn1Ptr' was is (possibly) expanded.
 *
 *----------------------------------------------------------------------
 */

void
CtkUnionRegions(rgn1Ptr, rgn2Ptr)
    CtkRegion *rgn1Ptr;
    CtkRegion *rgn2Ptr;
{
    RegionSpan *spans2 = rgn2Ptr->spans;
    int top2 = rgn2Ptr->top;
    int bottom2 = rgn2Ptr->bottom;
    int y;
    int idx;

    for (y = top2; y < bottom2; y++) {
	idx = y - top2;
	if (spans2[idx].left >= spans2[idx].right) {
	    /* Empty scan line */
	    continue;
	}
	/*
	 * Could eventually expand (repack) region 1 here,
	 * if line is not within the vertical bounds of the
	 * first region.
	 */
	while (idx != NO_SPAN) {
	    MergeSpan(rgn1Ptr, spans2[idx].left, spans2[idx].right, y);
	    idx = spans2[idx].next;
	}
    }
}

/*
 *----------------------------------------------------------------------
 *
 * CtkForEachSpan -- perform function on every span in a region
 *
 *	Executes function `spanProcPtr' for each span in region.
 *	Passes `clientData' and the span as arguments to `spanProcPtr'.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	`spanProcPtr' is executed.
 *
 *----------------------------------------------------------------------
 */

void
CtkForEachSpan(spanProcPtr, clientData, rgnPtr)
    CtkSpanProc *spanProcPtr;
    ClientData clientData;
    CtkRegion *rgnPtr;
{
    RegionSpan *spans = rgnPtr->spans;
    int top = rgnPtr->top;
    int bottom = rgnPtr->bottom;
    int y;
    int idx;

    for (y = top; y < bottom; y++) {
	idx = y - top;
	if (spans[idx].left >= spans[idx].right) {
	    /* Empty scan line */
	    continue;
	}
	while (idx != NO_SPAN) {
	    (*spanProcPtr)(spans[idx].left, spans[idx].right, y, clientData);
	    idx = spans[idx].next;
	}
    }
}

/*
 *----------------------------------------------------------------------
 *
 * CtkForEachIntersectingSpan -- perform function on region/span intersection
 *
 *	Computes the intersection of region `rgnPtr' and the
 *	span `left',`right' at vertical position `y'.  Executes
 *	function `spanProcPtr' for each span in the intersection.
 *	Passes `clientData' and the span as arguments to `spanProcPtr'.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	`spanProcPtr' is executed.
 *
 *----------------------------------------------------------------------
 */

void
CtkForEachIntersectingSpan(spanProcPtr, clientData, left, right, y, rgnPtr)
    CtkSpanProc *spanProcPtr;
    ClientData clientData;
    int left;
    int right;
    int y;
    CtkRegion *rgnPtr;
{
    RegionSpan *spans = rgnPtr->spans;
    int idx;
    int ileft;
    int iright;

    if (y < rgnPtr->top || y >= rgnPtr->bottom)  return;

    for (idx = y - rgnPtr->top; idx != NO_SPAN; idx = spans[idx].next) {
	if (spans[idx].left >= right)  break;
	if (spans[idx].right > left) {
	    /*
	     * Spans overlap.
	     */
	    ileft = spans[idx].left;
	    iright = spans[idx].right;
	    CtkIntersectSpans(&ileft, &iright, left, right);
	    (*spanProcPtr)(ileft, iright, y, clientData);
	}
    } /* for (idx) */
}

/*
 *----------------------------------------------------------------------
 *
 * CtkPointInRegion -- check if point is contained in region
 *
 *	Check if point (x,y) is in the region `rgnPtr'.
 *
 * Results:
 *	Returns 1 if point is in region, otherwise returns 0.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

int
CtkPointInRegion(x, y, rgnPtr)
    int x, y;
    CtkRegion *rgnPtr;
{
    RegionSpan *spans = rgnPtr->spans;
    int idx;

    if (y >= rgnPtr->top && y < rgnPtr->bottom) {
	for (idx = y - rgnPtr->top; idx != NO_SPAN; idx = spans[idx].next) {
	    if (spans[idx].left > x)  break;
	    if (spans[idx].right > x) {
		return 1;
	    }
	}
    }
    return 0;
}

/*
 *----------------------------------------------------------------------
 *
 * CtkRegionGetRect -- compute enclosing rectangle of a region
 *
 *	Compute the smallest rectangle that will enclose the
 *	area of `rgnPtr'.
 *
 * Results:
 *	Stores the resulting rectangle in `rectPtr'.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

void
CtkRegionGetRect(rgnPtr, rectPtr)
    CtkRegion *rgnPtr;
    Ctk_Rect *rectPtr;
{
    RegionSpan *spans = rgnPtr->spans;
    int top = rgnPtr->top;
    int numLines = rgnPtr->bottom - top;
    int topLine;           /* Index of top non-empty scan line */
    int bottomLine;        /* Index of bottom non-empty scan line */
    int left = COORD_MAX;
    int right = COORD_MIN;
    int line;
    int i;

    for (topLine = 0; topLine < numLines; topLine++) {
	if (spans[topLine].left < spans[topLine].right) {
	    /* Non-empty scan line */
	    break;
	}
    }
    for (bottomLine = numLines-1 ; bottomLine >= topLine; bottomLine--) {
	if (spans[bottomLine].left < spans[bottomLine].right) {
	    /* Non-empty scan line */
	    break;
	}
    }
    bottomLine++;

    for (line = topLine; line < bottomLine; line++)
    {
	if (spans[line].left < spans[line].right) {
	    /*
	     *	Non-empty scan line, if it goes outside the current
	     *	left and right bounds, then expand the bounds.
	     */
	    if (spans[line].left < left) {
		left = spans[line].left;
	    }
	    for (i = line; spans[i].next != NO_SPAN; i++);
	    if (spans[i].right > right) {
		right = spans[i].right;
	    }
	}
    }

    if (left < right && topLine < bottomLine) {
	CtkSetRect(rectPtr, left, top+topLine, right, top+bottomLine);
    } else {
	CtkSetRect(rectPtr, 0, 0, 0, 0);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * DeleteSpan -- remove a span from a region
 *
 *	Removes the span at `index' from `rgnPtr'.  `priorIndex'
 *	must point to the preceding span, or be NO_SPAN if this
 *	is the first span of a line.
 *
 * Results:
 *	Index of the next span (one after the deleted one).
 *
 * Side effects:
 *	The span at the specified index is removed, unless it is the
 *	first span of scan line in which case is is set to empty.
 *
 *----------------------------------------------------------------------
 */

static int
DeleteSpan(rgnPtr, index, priorIndex)
    CtkRegion *rgnPtr;
    int index;
    int priorIndex;
{
    int nextIndex = rgnPtr->spans[index].next;

    if (priorIndex == NO_SPAN) {
	if (nextIndex == NO_SPAN) {
	    rgnPtr->spans[index].left = rgnPtr->spans[index].right;
	} else {
	    CopySpan(&rgnPtr->spans[index], &rgnPtr->spans[nextIndex]);
	    FreeSpan(rgnPtr, nextIndex);
	    nextIndex = index;
	}
    } else {
	rgnPtr->spans[priorIndex].next = nextIndex;
	FreeSpan(rgnPtr, index);
    }
    return nextIndex;
}

/*
 *----------------------------------------------------------------------
 *
 * AppendSpan -- add a span to a region
 *
 *	Adds span `left',`right' to region `rgnPtr'
 *	after the span at `index'.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Changes contents of `rgnPtr'.
 *	!!! May change the value of rgnPtr->spans !!!
 *
 *----------------------------------------------------------------------
 */

static void
AppendSpan(rgnPtr, index, left, right)
    CtkRegion * rgnPtr;
    int index;
    int left;
    int right;
{
    int newIndex = AllocSpan(rgnPtr);
    RegionSpan *spans = rgnPtr->spans;

    spans[newIndex].left = left;
    spans[newIndex].right = right;
    spans[newIndex].next = spans[index].next;
    spans[index].next = newIndex;
}

/*
 *----------------------------------------------------------------------
 *
 * PrependSpan -- add a span to a region
 *
 *	Adds span `left',`right' to region `rgnPtr'
 *	before the span at `index'.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Changes contents of `rgnPtr'.
 *	!!! May change the value of rgnPtr->spans !!!
 *
 *----------------------------------------------------------------------
 */

static void
PrependSpan(rgnPtr, index, left, right)
    CtkRegion * rgnPtr;
    int index;
    int left;
    int right;
{
    int newIndex = AllocSpan(rgnPtr);
    RegionSpan *spans = rgnPtr->spans;

    CopySpan(&spans[newIndex], &spans[index]);
    spans[index].left = left;
    spans[index].right = right;
    spans[index].next = newIndex;
    
}

/*
 *----------------------------------------------------------------------
 *
 * AllocSpan -- get a new span for a region
 *
 *	Allocates another span for region `rgnPtr'.
 *
 * Results:
 *	Returns index of new span.
 *
 * Side effects:
 *	!!! May change the value of rgnPtr->spans !!!
 *
 *----------------------------------------------------------------------
 */

static int
AllocSpan(rgnPtr)
    CtkRegion * rgnPtr;
{
    int i;
    int old_num;
    int new_num;

    if (rgnPtr->free == NO_SPAN) {
	/*
	 *  No spans in free list, allocate some more.
	 */
	old_num = rgnPtr->num_spans;
	new_num = old_num + 20;
	rgnPtr->spans = (RegionSpan *)
	    ckrealloc((char *) rgnPtr->spans, (new_num)*sizeof(RegionSpan));
	rgnPtr->num_spans = new_num;

	/*
	 *  Add the new spans (except one) to the regions free list.
	 */
	for (i=old_num+1; i < new_num; i++) {
	    rgnPtr->spans[i-1].next = i;
	}
	rgnPtr->spans[new_num-1].next = NO_SPAN;
	rgnPtr->free = old_num+1;

	/*
	 * Return the remaining new span.
	 */
	return (old_num);
    } else {
	/*
	 *  Spans in free list, return one.
	 */
	i = rgnPtr->free;
	rgnPtr->free = rgnPtr->spans[rgnPtr->free].next;
	return (i);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * MergeSpan -- union a span into a region
 *
 *	Computes the union of region `rgnPtr' and span `left',`right'
 *	at line y, and stores it in `rgnPtr'.
 *	!!! `y' must be within rgnPtr->top and rgnPtr->bottom !!!
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	(Possibly) expands the region `rgnPtr'.
 *
 *----------------------------------------------------------------------
 */

static void
MergeSpan(rgnPtr, left, right, y)
    CtkRegion * rgnPtr;
    int left;
    int right;
    int y;
{
    RegionSpan *spans = rgnPtr->spans;
    int idx = y - rgnPtr->top;
    int lastIdx = NO_SPAN;
    int mergeIdx = NO_SPAN;

    if (y < rgnPtr->top || y > rgnPtr->bottom) {
    	panic("Merge span (y=%d) outside of regions vertical bounds (%d-%d)",
    		y, rgnPtr->top, rgnPtr->bottom);
    }

    if (spans[idx].left >= spans[idx].right) {
	/*
	 *  Empty scan line, replace it with the new span.
	 */
	spans[idx].left = left;
	spans[idx].right = right;
	return;
    }

    while (idx != NO_SPAN) {
	if (spans[idx].right >= left) {
	    /*
	     *	This spans is not left of the merge span.
	     */

	    if (spans[idx].left > right)  break; /* right of merge */

	    if (mergeIdx == NO_SPAN) {
		PseudoUnionSpans(
		    &spans[idx].left, &spans[idx].right, left, right);
		mergeIdx = idx;
	    } else {
		if (spans[mergeIdx].right < spans[idx].right) {
		    spans[mergeIdx].right = spans[idx].right;
		}
		idx = DeleteSpan(rgnPtr, idx, lastIdx);
		continue;
	    }
	}
    
	lastIdx = idx;
	idx = spans[idx].next;
    }

    if (mergeIdx == NO_SPAN) {
	/*
	 *  No merge performed, append merge span to scan line.
	 */
	if (lastIdx == NO_SPAN) {
	    PrependSpan(rgnPtr, idx, left, right);
	} else {
	    AppendSpan(rgnPtr, lastIdx, left, right);
	}
    }
}