
#include <stdio.h>
#include <stdlib.h>
#include "area.h"

#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))

static void *AreaMalloc(long int size);
static void *AreaRealloc(void *buffer, long int size);
static void AreaFree(void *buffer);

static Area *AreaFixup(Area *a, Area *b, int (*overlapfunc)(Area *a, Rect *ra, Rect *rb));
static void AreaFixBounds(Area *a);

static int GetNextLeft(Rect **ra, Rect **rb, int y, int *x1, int *x2);
static int _Union(Area *a, Rect *ra, Rect *rb);
static int _Intersect(Area *a, Rect *ra, Rect *rb);
static int _Subtract(Area *a, Rect *ra, Rect *rb);

Area *AreaCreate(void)
{
	Area *temp = AreaMalloc(sizeof(Area));

	temp->count = 0;
	temp->rectspace = 1;
	temp->rects = AreaMalloc(sizeof(Rect) * temp->rectspace);
	temp->bound.x1 = 0;
	temp->bound.y1 = 0;
	temp->bound.x2 = 0;
	temp->bound.y2 = 0;

	return(temp);
}

void AreaDestroy(Area *a)
{
	free(a->rects);
	free(a);
}

Area *AreaUnionRect(Area *a, int x1, int y1, int x2, int y2)
{
	Area *temp = AreaCreate();
	Area *temp2;

	temp->count = 1;
	temp->rects[0].x1 = x1;
	temp->rects[0].y1 = y1;
	temp->rects[0].x2 = x2;
	temp->rects[0].y2 = y2;

	temp2 = AreaUnionArea(a, temp);
	AreaDestroy(temp);
	return(temp2);
}

Area *AreaIntersectRect(Area *a, int x1, int y1, int x2, int y2)
{
	Area *temp = AreaCreate();
	Area *temp2;

	temp->count = 1;
	temp->rects[0].x1 = x1;
	temp->rects[0].y1 = y1;
	temp->rects[0].x2 = x2;
	temp->rects[0].y2 = y2;

	temp2 = AreaIntersectArea(a, temp);
	AreaDestroy(temp);
	return(temp2);
}

Area *AreaSubRect(Area *a, int x1, int y1, int x2, int y2)
{
	Area *temp = AreaCreate();
	Area *temp2;

	temp->count = 1;
	temp->rects[0].x1 = x1;
	temp->rects[0].y1 = y1;
	temp->rects[0].x2 = x2;
	temp->rects[0].y2 = y2;

	temp2 = AreaSubArea(a, temp);
	AreaDestroy(temp);
	return(temp2);
}

Area *AreaUnionArea(Area *a, Area *b)
{
	Area *n = AreaFixup(a, b, _Union);

	n->bound.x1 = MIN(a->bound.x1, b->bound.x1);
	n->bound.y1 = MIN(a->bound.y1, b->bound.y1);
	n->bound.x2 = MAX(a->bound.x2, b->bound.x2);
	n->bound.y2 = MAX(a->bound.y2, b->bound.y2);

	return(n);
}

Area *AreaIntersectArea(Area *a, Area *b)
{
	Area *n = AreaFixup(a, b, _Intersect);
	AreaFixBounds(n);
	return(n);
}

Area *AreaSubArea(Area *a, Area *b)
{
	Area *n = AreaFixup(a, b, _Subtract);
	AreaFixBounds(n);
	return(n);
}

static void AreaFixBounds(Area *a)
{
	Rect *box, *boxend, *bound;

	if (a->count == 0) {
		a->bound.x1 = 0;
		a->bound.y1 = 0;
		a->bound.x2 = 0;
		a->bound.y2 = 0;
		return;
	}

	bound = &a->bound;
	boxend = &box[a->count - 1];

	bound->x1 = box->x1;
	bound->y1 = box->y1;
	bound->x2 = boxend->x2;
	bound->y2 = boxend->y2;

	for (box = a->rects; box <= boxend; box++) {
                if (box->x1 < bound->x1) bound->x1 = box->x1;
		if (box->x2 > bound->x2) bound->x2 = box->x2;
	}
}

static void *AreaMalloc(long int size)
{
	void *temp = malloc(size);

	if (temp == NULL) {
		fprintf(stderr, "Unable to allocate enough memory.  %ld bytes not available.\n", size);
                exit(0);
        }

	return(temp);
}

static void *AreaRealloc(void *buffer, long int size)
{
	void *temp = realloc(buffer, size);

	if (temp == NULL) {
		fprintf(stderr, "Unable to allocate enough memory.  %ld bytes not available.\n", size);
		exit(0);
        }

        return(temp);
}

Area *AreaCopy(Area *src)
{
	Area *dest;

	dest = AreaCreate();
	dest->rects = realloc(dest->rects, sizeof(Rect) * src->count);
	dest->rectspace = src->count;

        dest->count = src->count;
	dest->bound.x1 = src->bound.x1;
	dest->bound.y1 = src->bound.y1;
	dest->bound.x2 = src->bound.x2;
	dest->bound.y2 = src->bound.y2;

	memcpy((char *)dest->rects, (char *)src->rects, src->count * sizeof(Rect));

	return(dest);
}

static Area *AreaFixup(Area *a, Area *b, int (*overlapfunc)(Area *a, Rect *ra, Rect *rb))
{
	int i, j, k;
	Area *temp2, *temp, *newarea;

	/* First step is to duplicate all the incoming rectangles, since
	   we're not allowed to modify the input */

	temp2 = AreaCopy(a);
	temp = AreaCopy(b);

	/* Second step is to split all the rectangles on each others' y1
	   and y2 bounds.  i iterates through the first area.  j iterates
	   through the second, though its motion is dependent on that of i. */

	for (i = 0, j = 0; i < temp2->count; i++) {
		if (temp2->rects[i].y1 > temp->rects[j].y1 && temp->rects[j].y1 <= temp2->rects[i].y2) {
			/* i's band needs to be split at [j].y1 */
			i = AreaSplitBand(temp2, i, temp->rects[j].y1) - 1;
                }
		else if (temp2->rects[i].y1 > temp->rects[j].y2-1 && temp->rects[j].y2-1 <= temp2->rects[i].y2) {
			/* i's band needs to be split at [j].y2-1 */
			i = AreaSplitBand(temp2, i, temp->rects[j].y2-1) - 1;
                }
        }

	/* Okay, we've split up one list nicely.  Now do the other. */

	for (i = 0, j = 0; i < temp->count; i++) {
		if (temp->rects[i].y1 > temp2->rects[j].y1 && temp2->rects[j].y1 <= temp->rects[i].y2) {
			/* i's band needs to be split at [j].y1 */
			i = AreaSplitBand(temp, i, temp2->rects[j].y1) - 1;
                }
		else if (temp->rects[i].y1 > temp2->rects[j].y2-1 && temp2->rects[j].y2-1 <= temp->rects[i].y2) {
			/* i's band needs to be split at [j].y2-1 */
			i = AreaSplitBand(temp, i, temp2->rects[j].y2-1) - 1;
                }
        }

	/* Step three.	Perform a merge on the two arrays, letting the supplied
	   function handle overlap. */

	newarea = AreaCreate();

	for (i = 0; i < temp2->count + temp->count;) {
		if (temp2->rects[i].y1 < temp->rects[j].y1)
			/* Copy the i band */
			i += (*overlapfunc)(newarea, &(temp2->rects[i]), NULL);

                else if (temp2->rects[i].y1 > temp->rects[j].y1)
			/* Copy the j band */
			i += (*overlapfunc)(newarea, NULL, &(temp->rects[j]));

		else
			/* Merge them however necessary */
                        i += (*overlapfunc)(newarea, &(temp2->rects[i]), &(temp->rects[j]));
        }

	AreaDestroy(temp);
	AreaDestroy(temp2);

	return(newarea);
}

/* The y below that gets passed in is the top edge of the new bottom band
   and y-1 is the bottom edge of the new top band. */

int AreaSplitBand(Area *a, int bandstart, int y)
{
	Rect *temp = malloc(sizeof(Rect) * a->count * 2);	/* The *2 is guaranteed to encompass all possible growth */
	int yorg = a->rects[bandstart].y1;
	int bandtemp = bandstart;
	int bandtemp2;

	/* Duplicate up to just before this band */

	for (bandtemp = 0; bandtemp < bandstart; bandtemp++) {
		temp[bandtemp].x1 = a->rects[bandtemp].x1;
		temp[bandtemp].y1 = a->rects[bandtemp].y1;
		temp[bandtemp].x2 = a->rects[bandtemp].x2;
		temp[bandtemp].y2 = a->rects[bandtemp].y2;
	}

	/* Duplicate this band once, but make it shorter, and move it up */

	for (bandtemp = bandstart, yorg = a->rects[bandtemp].y1, bandtemp2 = 0;
	     a->rects[bandtemp].y1 == yorg;
	     bandtemp++, bandtemp2++) {
		temp[bandtemp2].x1 = a->rects[bandtemp].x1;
		temp[bandtemp2].y1 = a->rects[bandtemp].y1;
		temp[bandtemp2].x2 = a->rects[bandtemp].x2;
		temp[bandtemp2].y2 = y - 1;
        }

	/* Duplicate this band again, but make it shorter, and move it down */

	for (bandtemp = bandstart, yorg = a->rects[bandtemp].y1, bandtemp2 = 0;
	     a->rects[bandtemp].y1 == yorg;
	     bandtemp++, bandtemp2++) {
		temp[bandtemp2].x1 = a->rects[bandtemp].x1;
		temp[bandtemp2].y1 = y;
		temp[bandtemp2].x2 = a->rects[bandtemp].x2;
		temp[bandtemp2].y2 = a->rects[bandtemp].y2;
        }

	bandstart = bandtemp;

	/* Copy the leftover stuff */

	for (; bandtemp < a->count; bandtemp++, bandtemp2++) {
		temp[bandtemp2].x1 = a->rects[bandtemp].x1;
		temp[bandtemp2].y1 = a->rects[bandtemp].y1;
		temp[bandtemp2].x2 = a->rects[bandtemp].x2;
		temp[bandtemp2].y2 = a->rects[bandtemp].y2;
        }

	free(a->rects);

	a->rectspace = a->count * 2;
        a->rects = temp;
	a->count = bandtemp2;

	return(bandstart);
}

static int GetNextLeft(Rect **ra, Rect **rb, int y, int *x1, int *x2)
{
	if ((*ra) != NULL && (*ra)->y1 == y) {
		*x1 = (*ra)->x1;
		if ((*rb) != NULL && (*rb)->y1 == y && (*rb)->x1 < *x1) {
			*x1 = (*rb)->x1;
			*x2 = (*rb)->x2;
			(*rb)++;
                }
		else {
			*x2 = (*ra)->x2;
                        (*ra)++;
		}
                return(1);
        }
	else if ((*rb) != NULL && (*rb)->y1 == y) {
		(*x1) = (*rb)->x1;
		(*x2) = (*rb)->x2;
		(*rb)++;
		return(1);
        }
	else return(0);
}

static int _Union(Area *a, Rect *ra, Rect *rb)
{
        int ox1, ox2;
        int x1, x2;
	int gotleft;
	int y1, y2;
	int count;

	if (ra != NULL && rb != NULL) {
		if (ra->y1 <= rb->y1) {
			y1 = ra->y1;
			y2 = ra->y2;
		}
		else {
			y1 = rb->y1;
			y2 = rb->y2;
		}
	}
	else if (ra != NULL) {
		y1 = ra->y1;
		y2 = ra->y2;
        }
	else if (rb != NULL) {
		y1 = rb->y1;
		y2 = rb->y2;
        }
	else return(0);

	while (1) {
		if (!GetNextLeft(&ra, &rb, y1, &ox1, &ox2)) break;
		count++;

		do {
			if (!(gotleft = GetNextLeft(&ra, &rb, y1, &x1, &x2))) break;
			count++;
                        if (x1 <= ox2+1 && x2 > ox2) ox2 = x2;
		} while (x1 <= ox2+1);

		if (!gotleft) break;

		if (a->count >= rectspace)
			a->rects = realloc((void *)a->rects, a->count * 2);

                a->rects[a->count].y1 = y1;
		a->rects[a->count].y2 = y2;
		a->rects[a->count].x1 = ox1;
		a->rects[a->count].x2 = ox2;

		(a->count)++;
        }

	return(count);
}

static int _Intersect(Area *a, Rect *ra, Rect *rb)
{

}

static int _Subtract(Area *a, Rect *ra, Rect *rb)
{

}

