#ifndef lint
static char sccsid[] = "@(#)difference.c 9.2 88/01/19 Copyright 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc. 
 */

/*-
	Trapezon difference routine

		"Meditation here
		 May think down hours to moments.  Here the heart
		 May give a useful lesson to the head,
		 And learning, wiser grow without his books."
						-- William Cowper

		            difference.c,
		            Mon Jul 1 16:18:03 1985

 */

#include <stdio.h>
#ifdef REF
#include <sys/types.h>
#include <ref/config.h>
#endif
#include "qalloc.h"
#include "shape.h"

struct shape_trapezon *
difference_one_trap(a, b)	/* computes a-b */
    struct shape_trapezon *a, *b;
{
    register struct shape_trapseg *p;
    register struct shape_trapezon *ret1, *ret2;
    if (a->bottom <= b->top || a->top >= b->bottom || a->right <= b->left || a->left >= b->right) {
	/*-	register    size = sizeof(struct shape_trapezon) + a->used * sizeof(struct shape_trapseg);
		QALLOC(ret1, size, (struct shape_trapezon *));
		bcopy(a, ret1, size);
		return ret1; */
	return a;
    }
    {
	register    size = sizeof(struct shape_trapezon) + (a->bottom - a->top + 1) * sizeof(struct shape_trapseg);
	QALLOC(ret1, size, (struct shape_trapezon *));
    }
    ret1->next = 0;
    ret1->refcnt = 1;
    ret1->size = a->bottom - a->top + 2;
    ret1->left = a->left;
    ret1->right = a->right;
    p = ret1->segs;
    ret2 = 0;
    {
	register struct shape_trapseg *ap, *bp;
	register    y;
	int         bottom = min(a->bottom, b->bottom);
	int         lastret2y;
	ap = a->segs;
	bp = b->segs;
	if (ap->y < bp->y) {
	    do
		*p++ = *ap++;
	    while (ap->y < bp->y);
	    if (ap->y > bp->y)
		ap--;
	    y = bp->y;
	}
	else {
	    while (bp->y < ap->y)
		bp++;
	    if (bp->y > ap->y)
		bp--;
	    y = ap->y;
	}
	while (y < bottom) {
	    p->y = y;
	    if (ap->x1 < bp->x1) {
		if (ap->x2 <= bp->x1) {	/* AABB */
		    p->x1 = ap->x1;
		    p->x2 = ap->x2;
		}
		else if (ap->x2 <= bp->x2) {	/* ABAB */
		    p->x1 = ap->x1;
		    p->x2 = bp->x1;
		}
		else {		/* ABBA */
		    p->x1 = ap->x1;
		    p->x2 = bp->x1;
		    if (ret2 == 0) {
			register    size = sizeof(struct shape_trapezon)
			+ (a->bottom - y + 1) * sizeof(struct shape_trapseg);
			QALLOC(ret2, size, (struct shape_trapezon *));
			ret1->next = ret2;
			ret2->next = 0;
			ret2->refcnt = 1;
			ret2->top = y;
			ret2->left = a->left;
			ret2->right = a->right;
			ret2->used = 0;
			ret2->size = a->bottom - y + 2;
		    }
		    else if (lastret2y != y) {
			register struct shape_trapseg *r2p = &ret2->segs[ret2->used++];
			r2p->y = lastret2y;
			r2p->x1 = 0;
			r2p->x2 = 0;
			assert(ret2->used < ret2->size);
		    }
		    {
			register struct shape_trapseg *r2p = &ret2->segs[ret2->used++];
			r2p->y = y;
			r2p->x1 = bp->x2;
			r2p->x2 = ap->x2;
			assert(ret2->used < ret2->size);
		    }
		    lastret2y = min(ap[1].y, bp[1].y);
		}
	    }
	    else if (ap->x1 < bp->x2) {
		if (ap->x2 <= bp->x2) {	/* BAAB */
		    if (p == ret1->segs || p[-1].x1 == p[-1].x2)
			goto skip;
		    p->x1 = 0;
		    p->x2 = 0;
		}
		else {		/* BABA */
		    p->x1 = bp->x2;
		    p->x2 = ap->x2;
		}
	    }
	    else {		/* BBAA */
		p->x1 = ap->x1;
		p->x2 = ap->x2;
	    }
	    if (p[-1].x1 != p[0].x1 || p[-1].x2 != p[0].x2 || p == ret1->segs)
		p++;
    skip:
	    if (ap[1].y == bp[1].y) {
		bp++;
		ap++;
		y = ap->y;
	    }
	    else if (ap[1].y < bp[1].y) {
		ap++;
		y = ap->y;
	    }
	    else {
		bp++;
		y = bp->y;
	    }
	}
	if (ap->y < bottom) {
	    assert(bp->y == y && ap[1].y > bottom);
	    *p = *ap++;
	    p->y = bottom;
	    y = ap->y;
	    p++;
	}
	assert(ap->y >= bottom);
	if (ap->y < a->bottom) {
	    while (ap->y < a->bottom)
		*p++ = *ap++;
	    y = a->bottom;
	    assert(ap->y == y);
	}
	if (p == ret1->segs) {
	    QFREE(ret1);
	    ret1 = 0;
	}
	else {
	    ret1->top = ret1->segs[0].y;
	    if (p[-1].x1 == p[-1].x2) {
		while (p[-1].x1 == p[-1].x2 && p > ret1->segs)
		    p--;
	    }
	    else
		p->y = y;
	    p->x1 = 0;
	    p->x2 = 0;
	    ret1->used = p - ret1->segs;
	    ret1->bottom = p->y;
	    assert(ret1->used < ret1->size);
	}
	if (ret2) {
	    register struct shape_trapseg *r2p = &ret2->segs[ret2->used];
	    ret2->bottom = lastret2y;
	    r2p->y = lastret2y;
	    r2p->x1 = 0;
	    r2p->x2 = 0;
	    assert(ret2->used < ret2->size);
	    assert(ret1 != 0);
	}
    }
    return ret1;
}

trim_traps(sh)
    register struct shape *sh;
{
    register struct shape_trapezon *t;
    register    top,
                bottom,
                left,
                right;
    struct shape_trapezon **prev;
    register struct shape *nsh;
    if (sh == 0 || sh->is_rect)
	return;
    top = TOP(sh);
    bottom = BOTTOM(sh);
    left = LEFT(sh);
    right = RIGHT(sh);
    for (t = sh->trapset; t; t = t->next)
	if (t->left < left || t->right > right
	    || t->top < top || t->bottom > bottom)
	    break;
    if (t == 0)
	return;
    if (sh->trapset->refcnt == 1)
	nsh = sh;
    else {
	sh_incref(sh);		/* !! (copy does a decref) */
	nsh = sh_copy(sh);
    }
    prev = &nsh->trapset;
    while (t = *prev) {
	register struct shape_trapseg *s,
	           *d;
	if (t->right <= left || t->left >= right
	    || t->top >= bottom || t->bottom <= top) {
	    *prev = t->next;
	    QFREE(t);
	    continue;
	}
	else if (t->left < left || t->right > right
		 || t->top < top || t->bottom > bottom) {
	    s = t->segs;
	    d = s;
	    if (t->top < top) {
		while (s->y < top)
		    s++;
		if (s->y > top) {
		    s--;
		    s->y = top;
		}
	    }
	    if (t->bottom < bottom)
		bottom = t->bottom;
	    while (s->y < bottom) {
		if (s->x1 < left)
		    s->x1 = left;
		if (s->x2 > right)
		    s->x2 = right;
		if (d > t->segs) {
		    if (s->x1 != d[-1].x1
			|| s->x2 != d[-1].x2)
			*d++ = *s;
		}
		else if (s->x1 < s->x2)
		    *d++ = *s;
		s++;
	    }
	    d->y = bottom;
	    while (d[-1].x1 >= d[-1].x2 && d > t->segs) {
		d--;
		bottom = d->y;
	    }
	    d->x1 = 0;
	    d->x2 = 0;
	    t->top = t->segs[0].y;
	    if ((t->used = d - t->segs) <= 0) {
		*prev = t->next;
		QFREE(t);
		bottom = BOTTOM(sh);
		continue;
	    }
	    t->bottom = bottom;
	    if (t->left < left)
		t->left = left;
	    if (t->right > right)
		t->right = right;
	    bottom = BOTTOM(sh);
	}
	prev = &t->next;
    }
    {
	register struct shape_trapezon *t = sh->trapset;
	if (sh != nsh) {
	    sh->trapset = nsh->trapset;
	    nsh->trapset = t;
	    sh_decref(nsh);
	    t = sh->trapset;
	}
	if (t == 0) {
	    sh->size.x = 0;
	    sh->size.y = 0;
	    sh->is_rect = 1;
	}
	else if (t->used == 1 && t->next == 0) {
	    sh->pos.x = t->segs[0].x1;
	    sh->pos.y = t->segs[0].y;
	    sh->size.x = t->segs[0].x2 - t->segs[0].x1;
	    sh->size.y = t->segs[1].y - t->segs[0].y;
	    QFREE(t);
	    sh->trapset = 0;
	    sh->is_rect = 1;
	}
    }
}

struct shape *
sh_difference(as, bs)
    register struct shape *as, *bs;
{
    register struct shape *rets;
    static struct {
	struct shape_trapezon trap;
	struct shape_trapseg second_array_element;
    }           atrap, btrap;
    if (as == 0 || as == bs)
	return 0;
    if (bs == 0) {
	sh_incref(as);
	return as;
    }
    if (as->pos.x == bs->pos.x
	    && as->size.x == bs->size.x
	    && as->pos.y == bs->pos.y
	    && as->size.y == bs->size.y
	    && as->is_rect == bs->is_rect
	    && (as->is_rect || sh_equal(as, bs))) {
	return 0;
    }
    qtalloc(rets, (struct shape *));
    *rets = *as;
    rets->refcnt = 1;
    if (RIGHT(as) <= LEFT(bs) || LEFT(as) >= RIGHT(bs)
	    || BOTTOM(as) <= TOP(bs) || TOP(as) >= BOTTOM(bs)
	    || bs->size.y == 0 || as->size.y == 0) {
CheckReturn:
	if (rets->size.x <= 0 || rets->size.y <= 0) {
	    qtfree(rets);
	    return 0;
	}
	if (!rets->is_rect) {
	    assert(rets->trapset != 0);
	    sh_incref(rets->trapset);
	}
	trim_traps(rets);	/* DEBUG */
	return rets;
    }
    trim_traps(bs);
    if (bs->is_rect) {
	if (TOP(bs) <= TOP(as) && BOTTOM(bs) >= BOTTOM(as)) {
	    if (RIGHT(bs) >= RIGHT(as)) {
		rets->size.x = LEFT(bs) - LEFT(as);
		goto CheckReturn;
	    }
	    if (LEFT(bs) <= LEFT(as)) {
		rets->pos.x = RIGHT(bs);
		rets->size.x = RIGHT(as) - RIGHT(bs);
		goto CheckReturn;
	    }
	}
	if (LEFT(bs) <= LEFT(as) && RIGHT(bs) >= RIGHT(as)) {
	    if (TOP(bs) <= TOP(as)) {
		rets->size.y = BOTTOM(as) - BOTTOM(bs);
		rets->pos.y = BOTTOM(bs);
		goto CheckReturn;
	    }
	    if (BOTTOM(bs) >= BOTTOM(as)) {
		rets->size.y = TOP(bs) - TOP(as);
		goto CheckReturn;
	    }
	}
	btrap.trap.next = 0;
	btrap.trap.bottom = BOTTOM(bs);
	btrap.trap.top = TOP(bs);
	btrap.trap.left = LEFT(bs);
	btrap.trap.right = RIGHT(bs);
	btrap.trap.size = 1;
	btrap.trap.used = 1;
	btrap.trap.segs[0].y = btrap.trap.top;
	btrap.trap.segs[0].x1 = btrap.trap.left;
	btrap.trap.segs[0].x2 = btrap.trap.right;
	btrap.trap.segs[1].y = btrap.trap.bottom;
	bs->trapset = &btrap.trap;
    }
    if (as->is_rect) {
	atrap.trap.next = 0;
	atrap.trap.bottom = BOTTOM(as);
	atrap.trap.top = TOP(as);
	atrap.trap.left = LEFT(as);
	atrap.trap.right = RIGHT(as);
	atrap.trap.size = 1;
	atrap.trap.used = 1;
	atrap.trap.segs[0].y = atrap.trap.top;
	atrap.trap.segs[0].x1 = atrap.trap.left;
	atrap.trap.segs[0].x2 = atrap.trap.right;
	atrap.trap.segs[1].y = atrap.trap.bottom;
	as->trapset = &atrap.trap;
    }
    {
	register struct shape_trapezon *a = as->trapset,
	           *b = bs->trapset;
	struct shape_trapezon *first = 0;
	struct shape_trapezon *ret;
	if (a == b) {
	    qtfree(rets);
	    return 0;
	}
	while (a) {
	    if (b == 0 || a->bottom <= b->top) {
		register    size = sizeof(struct shape_trapezon) + a->used * sizeof(struct shape_trapseg);
		register struct shape_trapezon **p = &first;
		QALLOC(ret, size, (struct shape_trapezon *));
		bcopy(a, ret, size);
		while (*p && (*p)->top <= ret->top)
		    p = &(*p)->next;
		ret->next = *p;
		ret->refcnt = 1;
		*p = ret;
		a = a->next;
	    }
	    else if (b->bottom <= a->top)
		b = b->next;
	    else {
		struct shape_trapezon *bprime = b;
		struct shape_trapezon *retset = a;
		while (bprime && bprime->top < a->bottom) {
		    struct shape_trapezon **rp,
		              **next;
		    for (rp = &retset; *rp; rp = next) {
			next = &(*rp)->next;
			ret = difference_one_trap(*rp, bprime);
			if (ret == a) {
			    assert(rp == &retset);
			    break;
			}
			if (*rp == a) {
			    *rp = ret;
			    assert(rp == &retset);
			    break;
			}
			if (ret == *rp)
			    continue;
			if (ret == 0) {
			    register struct shape_trapezon *Tp = *rp;
			    *rp = (*rp)->next;
			    QFREE(Tp);
			    next = rp;
			}
			else {
			    if (ret->next) {
				assert(ret->next->next == 0);
				ret->next->next = *next;
				next = &ret->next->next;
			    }
			    else {
				ret->next = *next;
				next = &ret->next;
			    }
			    QFREE(*rp);
			    *rp = ret;
			}
		    }
		    bprime = bprime->next;
		}
		if (retset == a) {
		    register struct shape_trapezon *T;
		    register    size;
		    size = sizeof(struct shape_trapezon)
			+ a->used * sizeof(struct shape_trapseg);
		    QALLOC(T, size, (struct shape_trapezon *));
		    bcopy(a, T, size);
		    T->refcnt = 1;
		    T->next = 0;
		    retset = T;
		}
		while (retset) {
		    struct shape_trapezon *next = retset->next;
		    if (first == 0) {
			first = retset;
			first->next = 0;
		    }
		    else {	/* Insertion sort */
			register struct shape_trapezon **p = &first;
			while (*p && (*p)->top <= retset->top)
			    p = &(*p)->next;
			retset->next = *p;
			*p = retset;
		    }
		    retset = next;
		}
		a = a->next;
	    }
	}
	if (first == 0) {
	    qtfree(rets);
	    return 0;
	}
	if (as->is_rect)
	    as->trapset = 0;
	if (bs->is_rect)
	    bs->trapset = 0;
	if (first->next == 0 && first->used == 1) {	/* Rectangular! */
	    register    T;
	    if ((T = first->top - rets->pos.y) > 0) {
		rets->pos.y += T;
		rets->size.y -= T;
	    }
	    if (first->bottom < rets->pos.y + rets->size.y)
		rets->size.y = first->bottom - rets->pos.y;
	    if ((T = first->segs[0].x1 - rets->pos.x) > 0) {
		rets->pos.x += T;
		rets->size.x -= T;
	    }
	    if (first->segs[0].x2 < rets->pos.x + rets->size.x)
		rets->size.x = first->segs[0].x2 - rets->pos.x;
	    QFREE(first);
	    if (rets->size.x <= 0 || rets->size.y <= 0) {
		qtfree(rets);
		return 0;
	    }
	    rets->is_rect = 1;
	    rets->trapset = 0;
	}
	else {
	    rets->is_rect = 0;
	    rets->trapset = first;
	}
	rets->refcnt = 1;
	return rets;
    }
}